GRASS Programmer's Manual  6.4.1(2011)
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                             struct Node *child, 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, child, 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 = child;
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     assert(Level == 0);
00141     return RTreeInsertRect1(R, (struct Node *) Tid, Root, Level);
00142 }
00143 
00144 int RTreeInsertRect1(struct Rect *R, struct Node *Child, struct Node **Root, int Level)
00145 {
00146     register struct Rect *r = R;
00147     register struct Node *child = Child;
00148     register struct Node **root = Root;
00149     register int level = Level;
00150     register int i;
00151     register struct Node *newroot;
00152     struct Node *newnode;
00153     struct Branch b;
00154     int result;
00155 
00156     assert(r && root);
00157     assert(level >= 0 && level <= (*root)->level);
00158     for (i = 0; i < NUMDIMS; i++) {
00159         assert(r->boundary[i] <= r->boundary[NUMDIMS + i]);
00160     }
00161 
00162     if (RTreeInsertRect2(r, child, *root, &newnode, level)) {   /* root split */
00163         newroot = RTreeNewNode();       /* grow a new root, & tree taller */
00164         newroot->level = (*root)->level + 1;
00165         b.rect = RTreeNodeCover(*root);
00166         b.child = *root;
00167         RTreeAddBranch(&b, newroot, NULL);
00168         b.rect = RTreeNodeCover(newnode);
00169         b.child = newnode;
00170         RTreeAddBranch(&b, newroot, NULL);
00171         *root = newroot;
00172         result = 1;
00173     }
00174     else
00175         result = 0;
00176 
00177     return result;
00178 }
00179 
00180 /*
00181  * Allocate space for a node in the list used in DeletRect to
00182  * store Nodes that are too empty.
00183  */
00184 static struct ListNode *RTreeNewListNode(void)
00185 {
00186     return (struct ListNode *)malloc(sizeof(struct ListNode));
00187     /* return new ListNode; */
00188 }
00189 
00190 static void RTreeFreeListNode(struct ListNode *p)
00191 {
00192     free(p);
00193     /* delete(p); */
00194 }
00195 
00196 /* 
00197  * Add a node to the reinsertion list.  All its branches will later
00198  * be reinserted into the index structure.
00199  */
00200 static void RTreeReInsert(struct Node *n, struct ListNode **ee)
00201 {
00202     register struct ListNode *l;
00203 
00204     l = RTreeNewListNode();
00205     l->node = n;
00206     l->next = *ee;
00207     *ee = l;
00208 }
00209 
00210 /*
00211  * Delete a rectangle from non-root part of an index structure.
00212  * Called by RTreeDeleteRect.  Descends tree recursively,
00213  * merges branches on the way back up.
00214  * Returns 1 if record not found, 0 if success.
00215  */
00216 static int
00217 RTreeDeleteRect2(struct Rect *R, struct Node *Child, struct Node *N,
00218                  struct ListNode **Ee)
00219 {
00220     register struct Rect *r = R;
00221     register struct Node *child = Child;
00222     register struct Node *n = N;
00223     register struct ListNode **ee = Ee;
00224     register int i;
00225 
00226     assert(r && n && ee);
00227     assert(child);
00228     assert(n->level >= 0);
00229 
00230     if (n->level > 0) {         /* not a leaf node */
00231         for (i = 0; i < NODECARD; i++) {
00232             if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect))) {
00233                 if (!RTreeDeleteRect2(r, child, n->branch[i].child, ee)) {
00234                     if (n->branch[i].child->count >= MinNodeFill) {
00235                         n->branch[i].rect =
00236                             RTreeNodeCover(n->branch[i].child);
00237                     }
00238                     else {
00239                         /* not enough entries in child, eliminate child node */
00240                         RTreeReInsert(n->branch[i].child, ee);
00241                         RTreeDisconnectBranch(n, i);
00242                     }
00243                     return 0;
00244                 }
00245             }
00246         }
00247         return 1;
00248     }
00249     else {                      /* a leaf node */
00250 
00251         for (i = 0; i < LEAFCARD; i++) {
00252             if (n->branch[i].child &&
00253                 n->branch[i].child == child) {
00254                 RTreeDisconnectBranch(n, i);
00255                 return 0;
00256             }
00257         }
00258         return 1;
00259     }
00260 }
00261 
00262 /*
00263  * Delete a data rectangle from an index structure.
00264  * Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
00265  * Returns 1 if record not found, 0 if success.
00266  * RTreeDeleteRect provides for eliminating the root.
00267  */
00268 int RTreeDeleteRect(struct Rect *R, int Tid, struct Node **Nn)
00269 {
00270     /* wrapper not really needed, but restricts compile warnings to rtree lib */
00271     /* this way it's easier to fix if necessary? */
00272     return RTreeDeleteRect1(R, (struct Node *) Tid, Nn);
00273 }
00274 
00275 int RTreeDeleteRect1(struct Rect *R, struct Node *Child, struct Node **Nn)
00276 {
00277     register struct Rect *r = R;
00278     register struct Node *child = Child;
00279     register struct Node **nn = Nn;
00280     register int i;
00281     struct Node *tmp_nptr = NULL;
00282     struct ListNode *reInsertList = NULL;
00283     register struct ListNode *e;
00284 
00285     assert(r && nn);
00286     assert(*nn);
00287     assert(child);
00288 
00289     if (!RTreeDeleteRect2(r, child, *nn, &reInsertList)) {
00290         /* found and deleted a data item */
00291 
00292         /* reinsert any branches from eliminated nodes */
00293         while (reInsertList) {
00294             tmp_nptr = reInsertList->node;
00295             for (i = 0; i < MAXKIDS(tmp_nptr); i++) {
00296                 if (tmp_nptr->branch[i].child) {
00297                     RTreeInsertRect1(&(tmp_nptr->branch[i].rect),
00298                                     tmp_nptr->branch[i].child,
00299                                     nn, tmp_nptr->level);
00300                 }
00301             }
00302             e = reInsertList;
00303             reInsertList = reInsertList->next;
00304             RTreeFreeNode(e->node);
00305             RTreeFreeListNode(e);
00306         }
00307 
00308         /* check for redundant root (not leaf, 1 child) and eliminate */
00309         if ((*nn)->count == 1 && (*nn)->level > 0) {
00310             for (i = 0; i < NODECARD; i++) {
00311                 tmp_nptr = (*nn)->branch[i].child;
00312                 if (tmp_nptr)
00313                     break;
00314             }
00315             assert(tmp_nptr);
00316             RTreeFreeNode(*nn);
00317             *nn = tmp_nptr;
00318         }
00319         return 0;
00320     }
00321     else {
00322         return 1;
00323     }
00324 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines