index.c

R+树的c实现源码

		break;
	if (i==rp->count) 
            rp = rp->next2;
	else break;
    }
    if (rp==NULL) return 0;
    rq = over;
    while (rq->next2 != NULL) {
	if (rq->next2->count == 1) {
	    rp->rect[i] = rq->next2->rect[0];
	    rq->next2 = NULL;
	    return 1;
	}
	rq = rq->next2;
    }
    rq->count --;
    rp->rect[i] = rq->rect[rq->count];
    if (over->count == NODECARD) {
	*node = (struct Node *)myalloc( sizeof( struct Node ) );
	for (i=0; i<NODECARD; i++) {
	    (*node)->branch[i].rect = rp->rect[i];
	    (*node)->branch[i].minrect = IntersectRect( &rp->rect[i], &rect );
	    (*node)->branch[i].son = 0;
	}
	(*node)->count = NODECARD;
	(*node)->rect = rect;
        (*node)->pageNo = over->pageNo;
	(*node)->level = 0;
        return 2; 
    }
    else return 1;
}
/* Add a node to the reinsertion list.  All its branches will later
** be reinserted into the index structure.
*/
ReInsert(n, ee)
register struct Node *n;
register struct ListNode **ee;
{
        register struct ListNode *l;
        struct ListNode *NewListNode();

        l = NewListNode();
        l->node = n;
        l->next = *ee;
        *ee = l;
}

/* Allocate space for a node in the list used in DeletRect to
** store Nodes that are too empty.
*/
struct ListNode *
NewListNode()
{
        char *myalloc();
        return (struct ListNode *) myalloc(sizeof(struct ListNode));
}

FreeListNode(p)
register struct ListNode *p;
{
        myfree(p);
}

/* Print out the data in a node.
*/
TPrintNode(n)
struct Node *n;
{
        int i;
        assert(n);

                printf("node");
                if (n->level == 0)
                        printf(" LEAF");
                else if (n->level > 0)
                        printf(" NONLEAF");
                else
                        printf(" TYPE=?");
                printf("  level=%d  count=%d  page=%d\n", n->level, n->count, n->pageNo);

		PrintRectIdent(&n->rect);
                for (i=0; i<n->count; i++)
                {
                        printf("branch %d\n", i);
                        PrintBranch(&n->branch[i]);
                }

}

/**********************************************************
      relations for intermediate and terminal nodes 
**********************************************************/

Irel(idxp, r1, r2, rel, mode)
int idxp;
register struct Rect *r1;
register struct Rect *r2;
char 	*rel;           /* topological or direction relation */
char 	*mode;          /* mode of relation: OBJ / MBR */
{
	int mbr;

        if (strcmp(mode,"OBJ")==0)
                mbr = 0;
        else if (strcmp(mode,"MBR")==0)
                mbr = 1;
	else
	{
		fprintf(stderr, "ERROR:\taccepted modes are: OBJ MBR\n");
		CloseIndex(idxp, Root);
		exit(1);
	}

	if (strcmp(rel,"OV")==0)
		return MyOverlap(r1, r2, NUMDIMS);
	else if (strcmp(rel,"DJ")==0)
	{
		if (mbr==0)
			return Disjoint1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"EO")==0)
	{
		if (mbr==0)
			return EOverlap1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"CV")==0)
	{
		if (mbr==0)
			return Cover1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"CN")==0)
	{
		if (mbr==0)
			return Contain1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"EQ")==0)
	{
		if (mbr==0)
			return Equal1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"IN")==0)
	{
		if (mbr==0)
			return Inside1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"CB")==0)
	{
		if (mbr==0)
			return Covered_by1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"MT")==0)
	{
		if (mbr==0)
			return Meet1(r1, r2, NUMDIMS);
		else
			return MyOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"SN")==0)
		return Strong_North1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"WN")==0)
		return Weak_North1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SBN")==0)
		return Strong_Bounded_North1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"WBN")==0)
		return Weak_Bounded_North1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SNE")==0)
		return Strong_NorthEast1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"WNE")==0)
		return Weak_NorthEast1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SL")==0)
		return Same_Level1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SSL")==0)
		return Strong_Same_Level1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"JN")==0)
		return Just_North1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"NS")==0)
		return North_South1(r1, r2, NUMDIMS);
	else if (strcmp(rel,"N")==0)
		return North1(r1, r2, NUMDIMS);
	else
	{
		fprintf(stderr, "ERROR:\taccepted topological relations are: OV DJ EO CV CN EQ IN CB MT\n");
		fprintf(stderr, "\taccepted direction relations are: SN WN SBN WBN SNE WNE SL SSL JN NS N\n");
		CloseIndex(idxp, Root);
		exit(1);
	}
}

Trel(idxp, r1, r2, rel, mode)
int idxp;
register struct Rect *r1;
register struct Rect *r2;
char 	*rel;           /* topological or direction relation */
char 	*mode;          /* mode of relation: OBJ / MBR */
{
	int mbr;

        if (strcmp(mode,"OBJ")==0)
                mbr = 0;
        else if (strcmp(mode,"MBR")==0)
                mbr = 1;
	else
	{
		fprintf(stderr, "ERROR:\taccepted modes are: OBJ MBR\n");
		CloseIndex(idxp, Root);
		exit(1);
	}


	if (strcmp(rel,"OV")==0)
		return MyOverlap(r1, r2, NUMDIMS);
	else if (strcmp(rel,"DJ")==0)
	{
		if (mbr==0)
			return Disjoint2(r1, r2, NUMDIMS);
		else
			return Disjoint(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"EO")==0)
	{
		if (mbr==0)
			return EOverlap2(r1, r2, NUMDIMS);
		else
			return EOverlap(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"CV")==0)
	{
		if (mbr==0)
			return Cover2(r1, r2, NUMDIMS);
		else
			return Cover(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"CN")==0)
	{
		if (mbr==0)
			return Contain2(r1, r2, NUMDIMS);
		else
			return Contain(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"EQ")==0)
	{
		if (mbr==0)
			return Equal2(r1, r2, NUMDIMS);
		else
			return Equal(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"IN")==0)
	{
		if (mbr==0)
			return Inside2(r1, r2, NUMDIMS);
		else
			return Inside(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"CB")==0)
	{
		if (mbr==0)
			return Covered_by2(r1, r2, NUMDIMS);
		else
			return Covered_by(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"MT")==0)
	{
		if (mbr==0)
			return Meet2(r1, r2, NUMDIMS);
		else
			return Meet(r1, r2, NUMDIMS);
	}
	else if (strcmp(rel,"SN")==0)
		return Strong_North(r1, r2, NUMDIMS);
	else if (strcmp(rel,"WN")==0)
		return Weak_North(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SBN")==0)
		return Strong_Bounded_North(r1, r2, NUMDIMS);
	else if (strcmp(rel,"WBN")==0)
		return Weak_Bounded_North(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SNE")==0)
		return Strong_NorthEast(r1, r2, NUMDIMS);
	else if (strcmp(rel,"WNE")==0)
		return Weak_NorthEast(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SL")==0)
		return Same_Level(r1, r2, NUMDIMS);
	else if (strcmp(rel,"SSL")==0)
		return Strong_Same_Level(r1, r2, NUMDIMS);
	else if (strcmp(rel,"JN")==0)
		return Just_North(r1, r2, NUMDIMS);
	else if (strcmp(rel,"NS")==0)
		return North_South(r1, r2, NUMDIMS);
	else if (strcmp(rel,"N")==0)
		return North(r1, r2, NUMDIMS);
	else
	{
		fprintf(stderr, "ERROR:\taccepted topological relations are: OV DJ EO CV CN EQ IN CB MT\n");
		fprintf(stderr, "\taccepted direction relations are: SN WN SBN WBN SNE WNE SL SSL JN NS N\n");
		CloseIndex(idxp, Root);
		exit(1);
	}
}