GRASS Programmer's Manual  6.5.svn(2014)-r66266
vector/rtree/index.c
Go to the documentation of this file.
1
2 /****************************************************************************
3 * MODULE: R-Tree library
4 *
5 * AUTHOR(S): Antonin Guttman - original code
6 * Daniel Green (green@superliminal.com) - major clean-up
7 * and implementation of bounding spheres
8 *
9 * PURPOSE: Multidimensional index
10 *
11 * COPYRIGHT: (C) 2001 by the GRASS Development Team
12 *
13 * This program is free software under the GNU General Public
14 * License (>=v2). Read the file COPYING that comes with GRASS
15 * for details.
16 *****************************************************************************/
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include "assert.h"
21 #include "index.h"
22 #include "card.h"
23
24 /* Make a new index, empty. Consists of a single node. */
25 struct Node *RTreeNewIndex(void)
26 {
27  struct Node *x;
28
29  x = RTreeNewNode();
30  x->level = 0; /* leaf */
31  return x;
32 }
33
34 /*
35  * Search in an index tree or subtree for all data retangles that
36  * overlap the argument rectangle.
37  * Return the number of qualifying data rects.
38  */
39 int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb,
40  void *cbarg)
41 {
42  register struct Node *n = N;
43  register struct Rect *r = R; /* NOTE: Suspected bug was R sent in as Node* and cast to Rect* here. */
44
45  /* Fix not yet tested. */
46  register int hitCount = 0;
47  register int i;
48
49  assert(n);
50  assert(n->level >= 0);
51  assert(r);
52
53  if (n->level > 0) { /* this is an internal node in the tree */
54  for (i = 0; i < NODECARD; i++)
55  if (n->branch[i].child && RTreeOverlap(r, &n->branch[i].rect)) {
56  hitCount += RTreeSearch(n->branch[i].child, r, shcb, cbarg);
57  }
58  }
59  else { /* this is a leaf node */
60
61  for (i = 0; i < LEAFCARD; i++)
62  if (n->branch[i].child && RTreeOverlap(r, &n->branch[i].rect)) {
63  hitCount++;
64  if (shcb) /* call the user-provided callback */
65  if (!shcb((int)n->branch[i].child, cbarg))
66  return hitCount; /* callback wants to terminate search early */
67  }
68  }
69  return hitCount;
70 }
71
72 /*
73  * Inserts a new data rectangle into the index structure.
74  * Recursively descends tree, propagates splits back up.
75  * Returns 0 if node was not split. Old node updated.
76  * If node was split, returns 1 and sets the pointer pointed to by
77  * new_node to point to the new node. Old node updated to become one of two.
78  * The level argument specifies the number of steps up from the leaf
79  * level to insert; e.g. a data rectangle goes in at level = 0.
80  */
81 static int RTreeInsertRect2(struct Rect *r,
82  struct Node *child, struct Node *n, struct Node **new_node,
83  int level)
84 {
85  /*
86  register struct Rect *r = R;
87  register int tid = Tid;
88  register struct Node *n = N, **new_node = New_node;
89  register int level = Level;
90  */
91
92  register int i;
93  struct Branch b;
94  struct Node *n2;
95
96  assert(r && n && new_node);
97  assert(level >= 0 && level <= n->level);
98
99  /* Still above level for insertion, go down tree recursively */
100  if (n->level > level) {
101  i = RTreePickBranch(r, n);
102  if (!RTreeInsertRect2(r, child, n->branch[i].child, &n2, level)) {
103  /* child was not split */
104  n->branch[i].rect = RTreeCombineRect(r, &(n->branch[i].rect));
105  return 0;
106  }
107  else { /* child was split */
108
109  n->branch[i].rect = RTreeNodeCover(n->branch[i].child);
110  b.child = n2;
111  b.rect = RTreeNodeCover(n2);
113  }
114  }
115
116  /* Have reached level for insertion. Add rect, split if necessary */
117  else if (n->level == level) {
118  b.rect = *r;
119  b.child = child;
120  /* child field of leaves contains tid of data record */
122  }
123  else {
124  /* Not supposed to happen */
125  assert(FALSE);
126  return 0;
127  }
128 }
129
130 /*
131  * Insert a data rectangle into an index structure.
132  * RTreeInsertRect provides for splitting the root;
133  * returns 1 if root was split, 0 if it was not.
134  * The level argument specifies the number of steps up from the leaf
135  * level to insert; e.g. a data rectangle goes in at level = 0.
136  * RTreeInsertRect2 does the recursion.
137  */
138 int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level)
139 {
140  assert(Level == 0);
141  return RTreeInsertRect1(R, (struct Node *) Tid, Root, Level);
142 }
143
144 int RTreeInsertRect1(struct Rect *R, struct Node *Child, struct Node **Root, int Level)
145 {
146  register struct Rect *r = R;
147  register struct Node *child = Child;
148  register struct Node **root = Root;
149  register int level = Level;
150  register int i;
151  register struct Node *newroot;
152  struct Node *newnode;
153  struct Branch b;
154  int result;
155
156  assert(r && root);
157  assert(level >= 0 && level <= (*root)->level);
158  for (i = 0; i < NUMDIMS; i++) {
159  assert(r->boundary[i] <= r->boundary[NUMDIMS + i]);
160  }
161
162  if (RTreeInsertRect2(r, child, *root, &newnode, level)) { /* root split */
163  newroot = RTreeNewNode(); /* grow a new root, & tree taller */
164  newroot->level = (*root)->level + 1;
165  b.rect = RTreeNodeCover(*root);
166  b.child = *root;
168  b.rect = RTreeNodeCover(newnode);
169  b.child = newnode;
171  *root = newroot;
172  result = 1;
173  }
174  else
175  result = 0;
176
177  return result;
178 }
179
180 /*
181  * Allocate space for a node in the list used in DeletRect to
182  * store Nodes that are too empty.
183  */
184 static struct ListNode *RTreeNewListNode(void)
185 {
186  return (struct ListNode *)malloc(sizeof(struct ListNode));
187  /* return new ListNode; */
188 }
189
190 static void RTreeFreeListNode(struct ListNode *p)
191 {
192  free(p);
193  /* delete(p); */
194 }
195
196 /*
197  * Add a node to the reinsertion list. All its branches will later
198  * be reinserted into the index structure.
199  */
200 static void RTreeReInsert(struct Node *n, struct ListNode **ee)
201 {
202  register struct ListNode *l;
203
204  l = RTreeNewListNode();
205  l->node = n;
206  l->next = *ee;
207  *ee = l;
208 }
209
210 /*
211  * Delete a rectangle from non-root part of an index structure.
212  * Called by RTreeDeleteRect. Descends tree recursively,
213  * merges branches on the way back up.
215  */
216 static int
217 RTreeDeleteRect2(struct Rect *R, struct Node *Child, struct Node *N,
218  struct ListNode **Ee)
219 {
220  register struct Rect *r = R;
221  register struct Node *child = Child;
222  register struct Node *n = N;
223  register struct ListNode **ee = Ee;
224  register int i;
225
226  assert(r && n && ee);
227  assert(child);
228  assert(n->level >= 0);
229
230  if (n->level > 0) { /* not a leaf node */
231  for (i = 0; i < NODECARD; i++) {
232  if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect))) {
233  if (!RTreeDeleteRect2(r, child, n->branch[i].child, ee)) {
234  if (n->branch[i].child->count >= MinNodeFill) {
235  n->branch[i].rect =
236  RTreeNodeCover(n->branch[i].child);
237  }
238  else {
239  /* not enough entries in child, eliminate child node */
240  RTreeReInsert(n->branch[i].child, ee);
241  RTreeDisconnectBranch(n, i);
242  }
243  return 0;
244  }
245  }
246  }
247  return 1;
248  }
249  else { /* a leaf node */
250
251  for (i = 0; i < LEAFCARD; i++) {
252  if (n->branch[i].child &&
253  n->branch[i].child == child) {
254  RTreeDisconnectBranch(n, i);
255  return 0;
256  }
257  }
258  return 1;
259  }
260 }
261
262 /*
263  * Delete a data rectangle from an index structure.
264  * Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
266  * RTreeDeleteRect provides for eliminating the root.
267  */
268 int RTreeDeleteRect(struct Rect *R, int Tid, struct Node **Nn)
269 {
270  /* wrapper not really needed, but restricts compile warnings to rtree lib */
271  /* this way it's easier to fix if necessary? */
272  return RTreeDeleteRect1(R, (struct Node *) Tid, Nn);
273 }
274
275 int RTreeDeleteRect1(struct Rect *R, struct Node *Child, struct Node **Nn)
276 {
277  register struct Rect *r = R;
278  register struct Node *child = Child;
279  register struct Node **nn = Nn;
280  register int i;
281  struct Node *tmp_nptr = NULL;
282  struct ListNode *reInsertList = NULL;
283  register struct ListNode *e;
284
285  assert(r && nn);
286  assert(*nn);
287  assert(child);
288
289  if (!RTreeDeleteRect2(r, child, *nn, &reInsertList)) {
290  /* found and deleted a data item */
291
292  /* reinsert any branches from eliminated nodes */
293  while (reInsertList) {
294  tmp_nptr = reInsertList->node;
295  for (i = 0; i < MAXKIDS(tmp_nptr); i++) {
296  if (tmp_nptr->branch[i].child) {
297  RTreeInsertRect1(&(tmp_nptr->branch[i].rect),
298  tmp_nptr->branch[i].child,
299  nn, tmp_nptr->level);
300  }
301  }
302  e = reInsertList;
303  reInsertList = reInsertList->next;
304  RTreeFreeNode(e->node);
305  RTreeFreeListNode(e);
306  }
307
308  /* check for redundant root (not leaf, 1 child) and eliminate */
309  if ((*nn)->count == 1 && (*nn)->level > 0) {
310  for (i = 0; i < NODECARD; i++) {
311  tmp_nptr = (*nn)->branch[i].child;
312  if (tmp_nptr)
313  break;
314  }
315  assert(tmp_nptr);
316  RTreeFreeNode(*nn);
317  *nn = tmp_nptr;
318  }
319  return 0;
320  }
321  else {
322  return 1;
323  }
324 }
RectReal boundary[NUMSIDES]
Definition: index.h:42
int RTreePickBranch(struct Rect *, struct Node *)
Definition: node.c:139
int l
float b
Definition: named_colr.c:8
struct Node * child
Definition: index.h:50
#define FALSE
Definition: dbfopen.c:117
struct Rect rect
Definition: index.h:49
int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb, void *cbarg)
float r
Definition: named_colr.c:8
Definition: index.h:56
int RTreeAddBranch(struct Branch *, struct Node *, struct Node **)
Definition: node.c:179
struct Node * node
Definition: index.h:66
int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level)
#define NUMDIMS
Definition: index.h:22
Definition: index.h:47
struct Node * RTreeNewNode(void)
Definition: node.c:44
void * malloc(YYSIZE_T)
int RTreeOverlap(struct Rect *, struct Rect *)
Definition: rect.c:331
struct Rect RTreeNodeCover(struct Node *)
Definition: node.c:111
int(* SearchHitCallback)(int id, void *arg)
Definition: index.h:76
int LEAFCARD
Definition: card.c:22
struct ListNode * next
Definition: index.h:65
return NULL
Definition: dbfopen.c:1394
struct Rect RTreeCombineRect(struct Rect *, struct Rect *)
Definition: rect.c:305
int count
Definition: index.h:58
#define MinNodeFill
Definition: card.h:26
void free(void *)
struct Node * RTreeNewIndex(void)
#define N
Definition: inverse.c:8
#define MAXKIDS(n)
Definition: card.h:29
int NODECARD
Definition: card.c:21
int level
Definition: index.h:59
int RTreeDeleteRect(struct Rect *R, int Tid, struct Node **Nn)
Definition: index.h:40
Definition: index.h:63
int n