index.c

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

Generated on Thu Jul 16 13:21:17 2009 for GRASS Programmer's Manual by  doxygen 1.5.6