index.c

R+树的c实现源码

#include <stdio.h>
#include "macros.h"
#include "options.h"
#include "index.h"
#include "global.h"
#include "assert.h"

extern	struct	Node	*SearchBuf[MAXLEVELS];

/* Make a new index, empty.  Consists of a single node.
*/
struct Node *
NewIndex()
{
        struct Node *x, *NewNode();
        x = NewNode();
        x->level = 0; /* leaf */
        LeafCount++;
        return x;
}

/* Print out all the nodes in an index.
** For graphics output, displays lower boxes first so they don't obscure
** enclosing boxes.  For printed output, prints from root downward.
*/
PrintIndex(idxp, n)
int idxp;
struct Node *n;
{
        int i, next;
        struct Node *nnn;
        struct Node *GetOnePage();
        assert(n);
        assert(n->level >= 0);

/*********************ho***************
        PrintNode( n );
*********************ho***************/
        if (n->level > 0)
        {
                for (i = 0; i < NODECARD; i++)
                {
                        if ((next = n->branch[i].son) > 0) {
				nnn = GetOnePage( idxp, next );
                                PrintIndex(idxp, nnn);
				myfree( nnn );
			}
                }
        }

}

/* Print out all the data rectangles in an index.
*/
PrintData(idxp, n)
int idxp;
struct Node *n;
{
        int i,next;
        struct Node *nnn;
        struct Node *GetOnePage();
        assert(n);
        assert(n->level >= 0);

        if (n->level == 0)
                TPrintNode(n);
        else
        {
                for (i = 0; i < NODECARD; i++)
                {
                        if ((next = n->branch[i].son) > 0) {
				nnn = GetOnePage( idxp, next );
                                PrintData(idxp, nnn);
				myfree( nnn ); 
                        }
                }
        }
}

/* SearchOneRect in an index tree or subtree for all data retangles that
** overlap the argument rectangle.
** Returns the number of qualifying data rects.
*/
int
SearchOneRect(idxp, n, r, rel, mode)
int idxp;
register struct Node *n;
register struct Rect *r;
char 	*rel;           /* topological or direction relation */
char 	*mode;          /* mode of relation: OBJ / MBR */
{
        register int hitCount = 0;
        register int i, j;
        register struct OverFlowNode *over, *rp;
	struct OverFlowNode *GetOverFlowPage();

        assert(n);
        assert(n->level >= 0);
        assert(r);

        SeTouchCount++;



	/* YANNIS...
		Irel(idxp, r1, r2, rel, mode) : relation for intermediate nodes
		Trel(idxp, r1, r2, rel, mode) : relation for terminal nodes
	*/

        if (n->level > 0) /* this is an internal node in the tree */
        {
                for (i=0; i<NODECARD; i++)
                    if (n->branch[i].son >= 0) 
			if ((n->level==1) && IsOverFlow(&n->branch[i].minrect)){
			    if (Irel(idxp, r, &n->branch[i].minrect, rel, mode)) {
				over = GetOverFlowPage( idxp, n->branch[i].son );
			  	rp = over;
				while ( rp != NULL ) {
				    for (j=0; j<rp->count; j++)
					if (Irel(idxp, r, &rp->rect[j], rel, mode)) {
					    /* printf("---->OVRFL Overlap with \n");
					    PrintRectIdent( &rp->rect[j] ); */
					}
				    rp = rp->next2;
				}
			    }
			    myfreeOFN( over );
			}
			else if (Irel(idxp, r, &n->branch[i].minrect, rel, mode)) {
				ReadOnePage( idxp, SearchBuf[n->level], n->branch[i].son , (n->level)-1);
                                hitCount += SearchOneRect(idxp, SearchBuf[n->level], r, rel, mode);
		        }
        }
        else /* this is a leaf node */
	{
                for (i=0; i<NODECARD; i++)
                {
                        if ((n->branch[i].son >= 0) 
				&& Trel(idxp, r, &n->branch[i].rect, rel, mode))
                        {
                                hitCount++;
				/* printf("---->  Overlap with rect id %d\n", n->branch[i].son - 5000); */
/* 				printf("---->  Overlap with \n");
				PrintRectIdent( &n->branch[i].rect ); */
                        }
                }
        }
        return hitCount;
}

/* Delete a data rectangle from an index structure.
** Pass in a pointer to a Rect, the r of the record, ptr to ptr to root node.
** Returns 1 if record not found, 0 if success.
** DeleteRect provides for eliminating the root.
*/
int
DeleteOneRect(idxp, nn, r)
int idxp;
register struct Node **nn;
register struct Rect *r;
{
        register int i;
        register struct Node *t;

        assert(r && nn );

        Deleting = TRUE;

#       ifdef PRINT
                printf("DeleteRect\n");
	  	PrintRect(r);
#       endif

        if (!DeleteRect2(idxp, r, *nn))
        {
                /* found and deleted a data item */
                if (StatFlag)
                        DeleteCount++;
                RectCount--;

                /* reinsert any branches from eliminated nodes */
                /* Non-leaf nodes not deleted in this version of R+ -trees */

                Deleting = FALSE;
		printf("---> The rectangle is deleted.\n" );
                return 1;
        }
        else
        {
                Deleting = FALSE;
		printf("---> The rectangle is not in R* tree.\n" );
                return 0;
        }
}

/* Delete a rectangle from non-root part of an index structure.
** Called by DeleteOneRect.  Descends tree recursively,
** merges branches on the way back up.
*/
int
DeleteRect2(idxp, r, n)
int idxp;
register struct Rect *r;
register struct Node *n;
{
        register int i, de;
        register int deleted = FALSE;
  	register struct OverFlowNode *over;
	struct OverFlowNode *GetOverFlowPage();
	struct Node *newnode;
        int SOverlap();
        struct Rect MinNodeCover(), MinOFNodeCover();
        struct Node *GetOnePage(), *nnn;

        assert(r && n );
        assert(n->level >= 0);

        if (StatFlag)
                DeTouchCount++;

        if (n->level > 0) /* not a leaf node */
        {
            for (i = 0; i < NODECARD; i++)
            {
                if (n->branch[i].son >= 0)
		    if ((n->level==1) && IsOverFlow(&n->branch[i].minrect)) {
			if (SOverlap(r, &n->branch[i].minrect))  {
			    over = GetOverFlowPage( idxp, n->branch[i].son );
			    if ((de=DeleteOFRect(r, over, &newnode, 
						      n->branch[i].rect)) == 0) 
				deleted = FALSE;
			    else if (de == 1) {
				n->branch[i].minrect = MinOFNodeCover(over, n->branch[i].rect);
				PutOverFlowPage( idxp, over );
				deleted = TRUE;
			    }
			    else {
				n->branch[i].minrect = MinNodeCover( newnode );
				PutOnePage( idxp, n->branch[i].son, newnode );
				deleted = TRUE;
			    }
			    myfreeOFN( over );
			}
			else SetOverFlow(&n->branch[i].minrect);
		    }
		    else if ( SOverlap(r, &(n->branch[i].minrect)) ) {
		        nnn = GetOnePage( idxp, n->branch[i].son );
                        if (!DeleteRect2(idxp, r, nnn))
                        {
                            n->branch[i].minrect = MinNodeCover(nnn);
                        /*
                        **  Non-leaf nodes not deleted in this version
                        **  of R+- trees
                        */
			    PutOnePage( idxp, n->branch[i].son, nnn );
                             deleted = TRUE;
                        }
		        myfree( nnn );
                    }
            }
            if (deleted)
                return 0;
            else
                return 1;
        }
        else  /* a leaf node */
        {
            for (i = 0; i < NODECARD; i++)
            {
                if ((n->branch[i].son >= 0)
			&& Equal2Rects( n->branch[i].rect, *r )) {
                    DisconBranch(n, i);
                    EntryCount--;
                    return 0;
                }
            }
            return 1;
        }
}

/*
** Delete rect in a list of overflow pages. If the specified rectangle is there,
** and delete the rectangle, o/w return 0. After deleting the rectangle, If the
** number of the remaining rectangles in the overflow pages is less than 
** NODECARD, the overflow page will be changed to normal page.
**
*/
int
DeleteOFRect( r, over, node, rect )
register struct Rect *r;
register struct OverFlowNode *over;
register struct Node **node;
register struct Rect rect;
{
    register struct OverFlowNode *rp, *rq;
    struct Rect IntersectRect();
    char *myalloc();
    register int i;

#ifdef DEBUG
    extern int magicNum;
    rp = over;
    while( rp!=NULL) {
        for (i=0; i<rp->count; i++)
	    if (rp->rect[i].boundary[0] == magicNum)
	       break;
        rp = rp->next2;
    }
#endif

    rp = over;
    while (rp!=NULL) {
	for (i=0; i<rp->count; i++)
	    if (Equal2Rects( *r, rp->rect[i] ))