index.c

Go to the documentation of this file.
00001 /****************************************************************************
00002 * MODULE:       R-Tree library 
00003 *              
00004 * AUTHOR(S):    Antonin Guttman - original code
00005 *               Daniel Green (green@superliminal.com) - major clean-up
00006 *                               and implementation of bounding spheres
00007 *               
00008 * PURPOSE:      Multidimensional index
00009 *
00010 * COPYRIGHT:    (C) 2001 by the GRASS Development Team
00011 *
00012 *               This program is free software under the GNU General Public
00013 *               License (>=v2). Read the file COPYING that comes with GRASS
00014 *               for details.
00015 *****************************************************************************/
00016 
00017 #include <stdio.h>
00018 #include <stdlib.h>
00019 #include "assert.h"
00020 #include "index.h"
00021 #include "card.h"
00022 
00023 /* Make a new index, empty.  Consists of a single node. */
00024 struct Node * RTreeNewIndex(void)
00025 {
00026         struct Node *x;
00027         x = RTreeNewNode();
00028         x->level = 0; /* leaf */
00029         return x;
00030 }
00031 
00032 /*
00033  * Search in an index tree or subtree for all data retangles that
00034  * overlap the argument rectangle.
00035  * Return the number of qualifying data rects.
00036  */
00037 int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb, void* cbarg)
00038 {
00039         register struct Node *n = N;
00040         register struct Rect *r = R; /* NOTE: Suspected bug was R sent in as Node* and cast to Rect* here.*/
00041                                      /* Fix not yet tested. */
00042         register int hitCount = 0;
00043         register int i;
00044 
00045         assert(n);
00046         assert(n->level >= 0);
00047         assert(r);
00048 
00049         if (n->level > 0) /* this is an internal node in the tree */
00050         {
00051                 for (i=0; i<NODECARD; i++)
00052                         if (n->branch[i].child &&
00053                             RTreeOverlap(r,&n->branch[i].rect))
00054                         {
00055                                 hitCount += RTreeSearch(n->branch[i].child, R, shcb, cbarg);
00056                         }
00057         }
00058         else /* this is a leaf node */
00059         {
00060                 for (i=0; i<LEAFCARD; i++)
00061                         if (n->branch[i].child &&
00062                             RTreeOverlap(r,&n->branch[i].rect))
00063                         {
00064                                 hitCount++;
00065                                 if(shcb) /* call the user-provided callback */
00066                                         if( ! shcb((int)n->branch[i].child, cbarg))
00067                                                 return hitCount; /* callback wants to terminate search early */
00068                         }
00069         }
00070         return hitCount;
00071 }
00072 /*
00073  * Inserts a new data rectangle into the index structure.
00074  * Recursively descends tree, propagates splits back up.
00075  * Returns 0 if node was not split.  Old node updated.
00076  * If node was split, returns 1 and sets the pointer pointed to by
00077  * new_node to point to the new node.  Old node updated to become one of two.
00078  * The level argument specifies the number of steps up from the leaf
00079  * level to insert; e.g. a data rectangle goes in at level = 0.
00080  */
00081 static int RTreeInsertRect2(struct Rect *r,
00082                 int tid, struct Node *n, struct Node **new_node, int level)
00083 {
00084 /*
00085         register struct Rect *r = R;
00086         register int tid = Tid;
00087         register struct Node *n = N, **new_node = New_node;
00088         register int level = Level;
00089 */
00090 
00091         register int i;
00092         struct Branch b;
00093         struct Node *n2;
00094 
00095         assert(r && n && new_node);
00096         assert(level >= 0 && level <= n->level);
00097 
00098         /* Still above level for insertion, go down tree recursively */
00099         if (n->level > level)
00100         {
00101                 i = RTreePickBranch(r, n);
00102                 if (!RTreeInsertRect2(r, tid, n->branch[i].child, &n2, level))
00103                 {
00104                         /* child was not split */
00105                         n->branch[i].rect =
00106                                 RTreeCombineRect(r,&(n->branch[i].rect));
00107                         return 0;
00108                 }
00109                 else    /* child was split */
00110                 {
00111                         n->branch[i].rect = RTreeNodeCover(n->branch[i].child);
00112                         b.child = n2;
00113                         b.rect = RTreeNodeCover(n2);
00114                         return RTreeAddBranch(&b, n, new_node);
00115                 }
00116         }
00117 
00118         /* Have reached level for insertion. Add rect, split if necessary */
00119         else if (n->level == level)
00120         {
00121                 b.rect = *r;
00122                 b.child = (struct Node *) tid;
00123                 /* child field of leaves contains tid of data record */
00124                 return RTreeAddBranch(&b, n, new_node);
00125         }
00126         else
00127         {
00128                 /* Not supposed to happen */
00129                 assert (FALSE);
00130                 return 0;
00131         }
00132 }
00133 
00134 /* 
00135  * Insert a data rectangle into an index structure.
00136  * RTreeInsertRect provides for splitting the root;
00137  * returns 1 if root was split, 0 if it was not.
00138  * The level argument specifies the number of steps up from the leaf
00139  * level to insert; e.g. a data rectangle goes in at level = 0.
00140  * RTreeInsertRect2 does the recursion.
00141  */
00142 int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level)
00143 {
00144         register struct Rect *r = R;
00145         register int tid = Tid;
00146         register struct Node **root = Root;
00147         register int level = Level;
00148         register int i;
00149         register struct Node *newroot;
00150         struct Node *newnode;
00151         struct Branch b;
00152         int result;
00153 
00154         assert(r && root);
00155         assert(level >= 0 && level <= (*root)->level);
00156         for (i=0; i<NUMDIMS; i++) {
00157                 assert(r->boundary[i] <= r->boundary[NUMDIMS+i]);
00158         }
00159 
00160         if (RTreeInsertRect2(r, tid, *root, &newnode, level))  /* root split */
00161         {
00162                 newroot = RTreeNewNode();  /* grow a new root, & tree taller */
00163                 newroot->level = (*root)->level + 1;
00164                 b.rect = RTreeNodeCover(*root);
00165                 b.child = *root;
00166                 RTreeAddBranch(&b, newroot, NULL);
00167                 b.rect = RTreeNodeCover(newnode);
00168                 b.child = newnode;
00169                 RTreeAddBranch(&b, newroot, NULL);
00170                 *root = newroot;
00171                 result = 1;
00172         }
00173         else
00174                 result = 0;
00175 
00176         return result;
00177 }
00178 
00179 /*
00180  * Allocate space for a node in the list used in DeletRect to
00181  * store Nodes that are too empty.
00182  */
00183 static struct ListNode * RTreeNewListNode(void)
00184 {
00185         return (struct ListNode *) malloc(sizeof(struct ListNode));
00186         /* return new ListNode; */
00187 }
00188 
00189 static void RTreeFreeListNode(struct ListNode *p)
00190 {
00191         free(p);
00192         /* delete(p); */
00193 }
00194 
00195 /* 
00196  * Add a node to the reinsertion list.  All its branches will later
00197  * be reinserted into the index structure.
00198  */
00199 static void RTreeReInsert(struct Node *n, struct ListNode **ee)
00200 {
00201         register struct ListNode *l;
00202 
00203         l = RTreeNewListNode();
00204         l->node = n;
00205         l->next = *ee;
00206         *ee = l;
00207 }
00208 
00209 /*
00210  * Delete a rectangle from non-root part of an index structure.
00211  * Called by RTreeDeleteRect.  Descends tree recursively,
00212  * merges branches on the way back up.
00213  * Returns 1 if record not found, 0 if success.
00214  */
00215 static int
00216 RTreeDeleteRect2(struct Rect *R, int Tid, struct Node *N, struct ListNode **Ee)
00217 {
00218         register struct Rect *r = R;
00219         register int tid = Tid;
00220         register struct Node *n = N;
00221         register struct ListNode **ee = Ee;
00222         register int i;
00223 
00224         assert(r && n && ee);
00225         assert(tid >= 0);
00226         assert(n->level >= 0);
00227 
00228         if (n->level > 0)  /* not a leaf node */
00229         {
00230             for (i = 0; i < NODECARD; i++)
00231             {
00232                 if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect)))
00233                 {
00234                         if (!RTreeDeleteRect2(r, tid, n->branch[i].child, ee))
00235                         {
00236                                 if (n->branch[i].child->count >= MinNodeFill) {
00237                                         n->branch[i].rect = RTreeNodeCover(
00238                                                 n->branch[i].child);
00239                                 }
00240                                 else
00241                                 {
00242                                         /* not enough entries in child, eliminate child node */
00243                                         RTreeReInsert(n->branch[i].child, ee);
00244                                         RTreeDisconnectBranch(n, i);
00245                                 }
00246                                 return 0;
00247                         }
00248                 }
00249             }
00250             return 1;
00251         }
00252         else  /* a leaf node */
00253         {
00254                 for (i = 0; i < LEAFCARD; i++)
00255                 {
00256                         if (n->branch[i].child &&
00257                             n->branch[i].child == (struct Node *) tid)
00258                         {
00259                                 RTreeDisconnectBranch(n, i);
00260                                 return 0;
00261                         }
00262                 }
00263                 return 1;
00264         }
00265 }
00266 
00267 /*
00268  * Delete a data rectangle from an index structure.
00269  * Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
00270  * Returns 1 if record not found, 0 if success.
00271  * RTreeDeleteRect provides for eliminating the root.
00272  */
00273 int RTreeDeleteRect(struct Rect *R, int Tid, struct Node**Nn)
00274 {
00275         register struct Rect *r = R;
00276         register int tid = Tid;
00277         register struct Node **nn = Nn;
00278         register int i;
00279         struct Node *tmp_nptr = NULL;
00280         struct ListNode *reInsertList = NULL;
00281         register struct ListNode *e;
00282 
00283         assert(r && nn);
00284         assert(*nn);
00285         assert(tid >= 0);
00286 
00287         if (!RTreeDeleteRect2(r, tid, *nn, &reInsertList))
00288         {
00289                 /* found and deleted a data item */
00290 
00291                 /* reinsert any branches from eliminated nodes */
00292                 while (reInsertList)
00293                 {
00294                         tmp_nptr = reInsertList->node;
00295                         for (i = 0; i < MAXKIDS(tmp_nptr); i++)
00296                         {
00297                                 if (tmp_nptr->branch[i].child)
00298                                 {
00299                                         RTreeInsertRect(
00300                                                 &(tmp_nptr->branch[i].rect),
00301                                                 (int)tmp_nptr->branch[i].child,
00302                                                 nn,
00303                                                 tmp_nptr->level);
00304                                 }
00305                         }
00306                         e = reInsertList;
00307                         reInsertList = reInsertList->next;
00308                         RTreeFreeNode(e->node);
00309                         RTreeFreeListNode(e);
00310                 }
00311                 
00312                 /* check for redundant root (not leaf, 1 child) and eliminate */
00313                 if ((*nn)->count == 1 && (*nn)->level > 0)
00314                 {
00315                         for (i = 0; i < NODECARD; i++)
00316                         {
00317                                 tmp_nptr = (*nn)->branch[i].child;
00318                                 if(tmp_nptr)
00319                                         break;
00320                         }
00321                         assert(tmp_nptr);
00322                         RTreeFreeNode(*nn);
00323                         *nn = tmp_nptr;
00324                 }
00325                 return 0;
00326         }
00327         else
00328         {
00329                 return 1;
00330         }
00331 }
00332 

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5