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