GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-5f6977e40c
indexm.c
Go to the documentation of this file.
1 /****************************************************************************
2  * MODULE: R-Tree library
3  *
4  * AUTHOR(S): Antonin Guttman - original code
5  * Daniel Green (green@superliminal.com) - major clean-up
6  * and implementation of bounding spheres
7  * Markus Metz - file-based and memory-based R*-tree
8  *
9  * PURPOSE: Multidimensional index
10  *
11  * COPYRIGHT: (C) 2010 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 <stdlib.h>
19 #include <assert.h>
20 #include <grass/gis.h>
21 #include "index.h"
22 
23 int RTreeValidChildM(union RTree_Child *child)
24 {
25  return (child->ptr != NULL);
26 }
27 
28 /*
29  * Search in an index tree for all data rectangles that
30  * overlap the argument rectangle.
31  * Return the number of qualifying data rects.
32  */
33 int RTreeSearchM(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb,
34  void *cbarg)
35 {
36  struct RTree_Node *n;
37  int hitCount = 0, notfound;
38  int i;
39  int top = 0;
40  struct nstack *s = t->ns;
41 
42  /* stack size of t->rootlevel + 1 is enough because of depth first search */
43  /* only one node per level on stack at any given time */
44 
45  /* add root node position to stack */
46  s[top].sn = t->root;
47  s[top].branch_id = i = 0;
48  n = s[top].sn;
49 
50  while (top >= 0) {
51  n = s[top].sn;
52  if (s[top].sn->level > 0) { /* this is an internal node in the tree */
53  notfound = 1;
54  for (i = s[top].branch_id; i < t->nodecard; i++) {
55  if (s[top].sn->branch[i].child.ptr &&
56  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
57  s[top++].branch_id = i + 1;
58  /* add next node to stack */
59  s[top].sn = n->branch[i].child.ptr;
60  s[top].branch_id = 0;
61  notfound = 0;
62  break;
63  }
64  }
65  if (notfound) {
66  /* nothing else found, go back up */
67  s[top].branch_id = t->nodecard;
68  top--;
69  }
70  }
71  else { /* this is a leaf node */
72  for (i = 0; i < t->leafcard; i++) {
73  if (s[top].sn->branch[i].child.id &&
74  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
75  hitCount++;
76  if (shcb) { /* call the user-provided callback */
77  if (!shcb(s[top].sn->branch[i].child.id,
78  &s[top].sn->branch[i].rect, cbarg)) {
79  /* callback wants to terminate search early */
80  return hitCount;
81  }
82  }
83  }
84  }
85  top--;
86  }
87  }
88 
89  return hitCount;
90 }
91 
92 /*
93  * Inserts a new data rectangle into the index structure.
94  * Non-recursively descends tree.
95  * Returns 0 if node was not split and nothing was removed.
96  * Returns 1 if root node was split. Old node updated to become one of two.
97  * Returns 2 if branches need to be reinserted.
98  * The level argument specifies the number of steps up from the leaf
99  * level to insert; e.g. a data rectangle goes in at level = 0.
100  */
101 static int RTreeInsertRect2M(struct RTree_Rect *r, union RTree_Child child,
102  int level, struct RTree_Node **newnode,
103  struct RTree *t, struct RTree_ListBranch **ee,
104  char *overflow)
105 {
106  int i;
107  struct RTree_Node *n, *n2;
108  struct RTree_Rect *cover;
109  int top = 0, down = 0;
110  int result;
111  struct RTree_Branch *b = &(t->tmpb2);
112  struct nstack *s = t->ns;
113 
114  /* add root node to stack */
115  s[top].sn = t->root;
116 
117  /* go down to level of insertion */
118  while (s[top].sn->level > level) {
119  n = s[top].sn;
120  i = RTreePickBranch(r, n, t);
121  s[top++].branch_id = i;
122  /* add next node to stack */
123  s[top].sn = n->branch[i].child.ptr;
124  }
125 
126  /* Have reached level for insertion. Remove p rectangles or split */
127  RTreeCopyRect(&(b->rect), r, t);
128  /* child field of leaves contains tid of data record */
129  b->child = child;
130  /* add branch, may split node or remove branches */
131  cover = NULL;
132  if (top)
133  cover = &(s[top - 1].sn->branch[s[top - 1].branch_id].rect);
134  result = RTreeAddBranch(b, s[top].sn, &n2, ee, cover, overflow, t);
135  /* update node count */
136  if (result == 1) {
137  t->n_nodes++;
138  }
139 
140  /* go back up */
141  while (top) {
142  down = top--;
143  i = s[top].branch_id;
144  if (result == 0) { /* branch was added */
145  RTreeExpandRect(&(s[top].sn->branch[i].rect), r, t);
146  }
147  else if (result == 2) { /* branches were removed */
148  /* get node cover of previous node */
149  RTreeNodeCover(s[down].sn, &(s[top].sn->branch[i].rect), t);
150  }
151  else if (result == 1) { /* node was split */
152  /* get node cover of previous node */
153  RTreeNodeCover(s[down].sn, &(s[top].sn->branch[i].rect), t);
154  /* add new branch for new node previously added by RTreeAddBranch()
155  */
156  b->child.ptr = n2;
157  RTreeNodeCover(b->child.ptr, &(b->rect), t);
158 
159  /* add branch, may split node or remove branches */
160  cover = NULL;
161  if (top)
162  cover = &(s[top - 1].sn->branch[s[top - 1].branch_id].rect);
163  result = RTreeAddBranch(b, s[top].sn, &n2, ee, cover, overflow, t);
164 
165  /* update node count */
166  if (result == 1) {
167  t->n_nodes++;
168  }
169  }
170  }
171 
172  *newnode = n2;
173 
174  return result;
175 }
176 
177 /*
178  * Insert a data rectangle into an index structure.
179  * RTreeInsertRect provides for splitting the root;
180  * returns 1 if root was split, 0 if it was not.
181  * The level argument specifies the number of steps up from the leaf
182  * level to insert; e.g. a data rectangle goes in at level = 0.
183  * RTreeInsertRect2 does the actual insertion.
184  */
185 int RTreeInsertRectM(struct RTree_Rect *r, union RTree_Child child, int level,
186  struct RTree *t)
187 {
188  struct RTree_Node *newnode, *newroot;
189  struct RTree_ListBranch *reInsertList = NULL;
190  struct RTree_ListBranch *e;
191  int result;
192  char overflow[MAXLEVEL];
193  struct RTree_Branch *b = &(t->tmpb1);
194 
195  /* R*-tree forced reinsertion: for each level only once */
196  memset(overflow, t->overflow, MAXLEVEL);
197 
198  result = RTreeInsertRect2M(r, child, level, &newnode, t, &reInsertList,
199  overflow);
200 
201  if (result == 1) { /* root split */
202  /* grow a new root, & tree taller */
203  t->rootlevel++;
204  newroot = RTreeAllocNode(t, t->rootlevel);
205  newroot->level = t->rootlevel;
206  /* branch for old root */
207  RTreeNodeCover(t->root, &(b->rect), t);
208  b->child.ptr = t->root;
209  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
210  /* branch for new node created by RTreeInsertRect2() */
211  RTreeNodeCover(newnode, &(b->rect), t);
212  b->child.ptr = newnode;
213  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
214  /* set new root node */
215  t->root = newroot;
216  t->n_nodes++;
217 
218  return result;
219  }
220 
221  if (result == 2) { /* branches were removed */
222  while (reInsertList) {
223  /* get next branch in list */
224  RTreeCopyBranch(b, &(reInsertList->b), t);
225  level = reInsertList->level;
226  e = reInsertList;
227  reInsertList = reInsertList->next;
229  /* reinsert branches */
230  result = RTreeInsertRect2M(&(b->rect), b->child, level, &newnode, t,
231  &reInsertList, overflow);
232 
233  if (result == 1) { /* root split */
234  /* grow a new root, & tree taller */
235  t->rootlevel++;
236  newroot = RTreeAllocNode(t, t->rootlevel);
237  newroot->level = t->rootlevel;
238  /* branch for old root */
239  RTreeNodeCover(t->root, &(b->rect), t);
240  b->child.ptr = t->root;
241  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
242  /* branch for new node created by RTreeInsertRect2() */
243  RTreeNodeCover(newnode, &(b->rect), t);
244  b->child.ptr = newnode;
245  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
246  /* set new root node */
247  t->root = newroot;
248  t->n_nodes++;
249  }
250  }
251  }
252 
253  return result;
254 }
255 
256 /*
257  * Delete a rectangle from non-root part of an index structure.
258  * Called by RTreeDeleteRect. Descends tree non-recursively,
259  * merges branches on the way back up.
260  * Returns 1 if record not found, 0 if success.
261  */
262 static int RTreeDeleteRect2M(struct RTree_Rect *r, union RTree_Child child,
263  struct RTree *t, struct RTree_ListNode **ee)
264 {
265  int i, notfound = 1;
266  struct RTree_Node *n;
267  int top = 0, down = 0;
268  int minfill;
269  struct nstack *s = t->ns;
270 
271  assert(ee);
272 
273  /* add root node position to stack */
274  s[top].sn = t->root;
275  s[top].branch_id = 0;
276  n = s[top].sn;
277 
278  while (notfound && top >= 0) {
279  /* go down to level 0, remember path */
280  if (s[top].sn->level > 0) {
281  n = s[top].sn;
282  for (i = s[top].branch_id; i < t->nodecard; i++) {
283  if (n->branch[i].child.ptr &&
284  RTreeOverlap(r, &(n->branch[i].rect), t)) {
285  s[top++].branch_id = i + 1;
286  /* add next node to stack */
287  s[top].sn = n->branch[i].child.ptr;
288  s[top].branch_id = 0;
289 
290  notfound = 0;
291  break;
292  }
293  }
294  if (notfound) {
295  /* nothing else found, go back up */
296  s[top].branch_id = t->nodecard;
297  top--;
298  }
299  else /* found a way down but not yet the item */
300  notfound = 1;
301  }
302  else {
303  for (i = 0; i < t->leafcard; i++) {
304  if (s[top].sn->branch[i].child.id &&
305  s[top].sn->branch[i].child.id ==
306  child.id) { /* found item */
307  RTreeDisconnectBranch(s[top].sn, i, t);
308  t->n_leafs--;
309  notfound = 0;
310  break;
311  }
312  }
313  if (notfound) /* continue searching */
314  top--;
315  }
316  }
317 
318  if (notfound) {
319  return notfound;
320  }
321 
322  /* go back up */
323  while (top) {
324  down = top;
325  top--;
326  i = s[top].branch_id - 1;
327  assert(s[down].sn->level == s[top].sn->level - 1);
328 
329  minfill = (s[down].sn->level ? t->min_node_fill : t->min_leaf_fill);
330  if (s[down].sn->count >= minfill) {
331  /* just update node cover */
332  RTreeNodeCover(s[down].sn, &(s[top].sn->branch[i].rect), t);
333  }
334  else {
335  /* not enough entries in child, eliminate child node */
336  RTreeReInsertNode(s[top].sn->branch[i].child.ptr, ee);
337  RTreeDisconnectBranch(s[top].sn, i, t);
338  }
339  }
340 
341  return notfound;
342 }
343 
344 /*
345  * should be called by RTreeDeleteRect() only
346  *
347  * Delete a data rectangle from an index structure.
348  * Pass in a pointer to a Rect, the tid of the record, ptr RTree.
349  * Returns 1 if record not found, 0 if success.
350  * RTreeDeleteRect1 provides for eliminating the root.
351  */
352 int RTreeDeleteRectM(struct RTree_Rect *r, union RTree_Child child,
353  struct RTree *t)
354 {
355  int i;
356  struct RTree_Node *n;
357  struct RTree_ListNode *reInsertList = NULL;
358  struct RTree_ListNode *e;
359 
360  if (!RTreeDeleteRect2M(r, child, t, &reInsertList)) {
361  /* found and deleted a data item */
362 
363  /* reinsert any branches from eliminated nodes */
364  while (reInsertList) {
365  t->n_nodes--;
366  n = reInsertList->node;
367  if (n->level > 0) { /* reinsert node branches */
368  for (i = 0; i < t->nodecard; i++) {
369  if (n->branch[i].child.ptr) {
370  RTreeInsertRectM(&(n->branch[i].rect),
371  n->branch[i].child, n->level, t);
372  }
373  }
374  }
375  else { /* reinsert leaf branches */
376  for (i = 0; i < t->leafcard; i++) {
377  if (n->branch[i].child.id) {
378  RTreeInsertRectM(&(n->branch[i].rect),
379  n->branch[i].child, n->level, t);
380  }
381  }
382  }
383  e = reInsertList;
384  reInsertList = reInsertList->next;
385  RTreeFreeNode(e->node);
387  }
388 
389  /* check for redundant root (not leaf, 1 child) and eliminate */
390  n = t->root;
391 
392  if (n->count == 1 && n->level > 0) {
393  for (i = 0; i < t->nodecard; i++) {
394  if (n->branch[i].child.ptr)
395  break;
396  }
397  t->root = n->branch[i].child.ptr;
398  RTreeFreeNode(n);
399  t->rootlevel--;
400  }
401  return 0;
402  }
403 
404  return 1;
405 }
#define NULL
Definition: ccmath.h:32
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *)
Definition: node.c:544
void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *)
Definition: node.c:270
void RTreeNodeCover(struct RTree_Node *, struct RTree_Rect *, struct RTree *)
Definition: node.c:135
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:124
int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *)
Definition: node.c:236
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:536
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:100
int RTreeDeleteRectM(struct RTree_Rect *r, union RTree_Child child, struct RTree *t)
Definition: indexm.c:352
int RTreeSearchM(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Definition: indexm.c:33
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:23
int RTreeInsertRectM(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree *t)
Definition: indexm.c:185
#define assert(condition)
Definition: lz4.c:393
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:95
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:74
double b
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
int RTreeOverlap(struct RTree_Rect *r, struct RTree_Rect *s, struct RTree *t)
Definition: rect.c:590
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:86
struct RTree_Rect rect
Definition: rtree.h:68
union RTree_Child child
Definition: rtree.h:69
struct RTree_ListBranch * next
Definition: index.h:44
struct RTree_Branch b
Definition: index.h:45
struct RTree_ListNode * next
Definition: index.h:34
struct RTree_Node * node
Definition: index.h:35
int count
Definition: rtree.h:74
int level
Definition: rtree.h:75
struct RTree_Branch * branch
Definition: rtree.h:76
Definition: rtree.h:123
Definition: rtree.h:100
struct RTree_Node * sn
Definition: rtree.h:101
int branch_id
Definition: rtree.h:102
struct RTree_Node * ptr
Definition: rtree.h:62
int id
Definition: rtree.h:61
void RTreeFreeListNode(struct RTree_ListNode *p)
void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
void RTreeFreeListBranch(struct RTree_ListBranch *p)
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30