GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
indexf.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) 2001 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 <stdio.h>
21 #include <string.h>
22 #include <sys/types.h>
23 #include <assert.h>
24 #include <grass/gis.h>
25 #include "index.h"
26 
27 int RTreeValidChildF(union RTree_Child *child)
28 {
29  return (child->pos > -1);
30 }
31 
32 /*
33  * Search in an index tree for all data retangles that
34  * overlap the argument rectangle.
35  * Return the number of qualifying data rects.
36  */
37 int RTreeSearchF(struct RTree *t, struct RTree_Rect *r,
38  SearchHitCallback *shcb, void *cbarg)
39 {
40  struct RTree_Node *n;
41  int hitCount = 0, notfound, currlevel;
42  int i;
43  int top = 0;
44  struct nstack *s = t->ns;
45 
46  /* stack size of t->rootlevel + 1 is enough because of depth first search */
47  /* only one node per level on stack at any given time */
48 
49  /* add root node position to stack */
50  currlevel = t->rootlevel;
51  s[top].pos = t->rootpos;
52  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
53  s[top].branch_id = i = 0;
54 
55  while (top >= 0) {
56  n = s[top].sn;
57  if (s[top].sn->level > 0) { /* this is an internal node in the tree */
58  notfound = 1;
59  currlevel = s[top].sn->level - 1;
60  for (i = s[top].branch_id; i < t->nodecard; i++) {
61  if (s[top].sn->branch[i].child.pos > -1 &&
62  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
63  s[top++].branch_id = i + 1;
64  /* add next node to stack */
65  s[top].pos = n->branch[i].child.pos;
66  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
67  s[top].branch_id = 0;
68  notfound = 0;
69  break;
70  }
71  }
72  if (notfound) {
73  /* nothing else found, go back up */
74  s[top].branch_id = t->nodecard;
75  top--;
76  }
77  }
78  else { /* this is a leaf node */
79  for (i = 0; i < t->leafcard; i++) {
80  if (s[top].sn->branch[i].child.id &&
81  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
82  hitCount++;
83  if (shcb) { /* call the user-provided callback */
84  if (!shcb(s[top].sn->branch[i].child.id,
85  &(s[top].sn->branch[i].rect), cbarg)) {
86  /* callback wants to terminate search early */
87  return hitCount;
88  }
89  }
90  }
91  }
92  top--;
93  }
94  }
95 
96  return hitCount;
97 }
98 
99 /*
100  * Inserts a new data rectangle into the index structure.
101  * Non-recursively descends tree, propagates splits back up.
102  * Returns 0 if node was not split. Old node updated.
103  * If node was split, returns 1 and sets the pointer pointed to by
104  * new_node to point to the new node. Old node updated to become one of two.
105  * The level argument specifies the number of steps up from the leaf
106  * level to insert; e.g. a data rectangle goes in at level = 0.
107  */
108 static int RTreeInsertRect2F(struct RTree_Rect *r, union RTree_Child child, int level,
109  struct RTree_Node *newnode, off_t *newnode_pos,
110  struct RTree *t,
111  struct RTree_ListBranch **ee, char *overflow)
112 {
113  int i, currlevel;
114  struct RTree_Node *n, *n2;
115  struct RTree_Rect *cover;
116  int top = 0, down = 0;
117  int result;
118  struct RTree_Branch *b = &(t->tmpb2);
119  struct nstack *s = t->ns;
120 
121  struct RTree_Rect *nr = &(t->orect);
122 
123  n2 = newnode;
124 
125  /* add root node position to stack */
126  currlevel = t->rootlevel;
127  s[top].pos = t->rootpos;
128  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
129 
130  /* go down to level of insertion */
131  while (s[top].sn->level > level) {
132  n = s[top].sn;
133  currlevel = s[top].sn->level - 1;
134  i = RTreePickBranch(r, n, t);
135  s[top++].branch_id = i;
136  /* add next node to stack */
137  s[top].pos = n->branch[i].child.pos;
138  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
139  }
140 
141  /* Have reached level for insertion. Add rect, split if necessary */
142  RTreeCopyRect(&(b->rect), r, t);
143  /* child field of leaves contains tid of data record */
144  b->child = child;
145  /* add branch, may split node or remove branches */
146  cover = NULL;
147  if (top)
148  cover = &(s[top - 1].sn->branch[s[top - 1].branch_id].rect);
149  result = RTreeAddBranch(b, s[top].sn, &n2, ee, cover, overflow, t);
150  /* update node */
151  RTreeNodeChanged(s[top].sn, s[top].pos, t);
152  /* write out new node if node was split */
153  if (result == 1) {
154  *newnode_pos = RTreeGetNodePos(t);
155  RTreeWriteNode(n2, t);
156  t->n_nodes++;
157  }
158 
159  /* go back up */
160  while (top) {
161  down = top--;
162  i = s[top].branch_id;
163  if (result == 0) { /* branch was added */
164  if (RTreeExpandRect(&(s[top].sn->branch[i].rect), r, t)) {
165  RTreeNodeChanged(s[top].sn, s[top].pos, t);
166  }
167  }
168  else if (result == 2) { /* branches were removed */
169  /* get node cover of previous node */
170  RTreeNodeCover(s[down].sn, nr, t);
171  /* rewrite rect */
172  if (!RTreeCompareRect(nr, &(s[top].sn->branch[i].rect), t)) {
173  RTreeCopyRect(&(s[top].sn->branch[i].rect), nr, t);
174  RTreeNodeChanged(s[top].sn, s[top].pos, t);
175  }
176  }
177  else if (result == 1) { /* node was split */
178  /* get node cover of previous node */
179  RTreeNodeCover(s[down].sn, &(s[top].sn->branch[i].rect), t);
180  /* add new branch for new node previously added by RTreeAddBranch() */
181  b->child.pos = *newnode_pos;
182  RTreeNodeCover(n2, &(b->rect), t);
183 
184  /* add branch, may split node or remove branches */
185  cover = NULL;
186  if (top)
187  cover = &(s[top - 1].sn->branch[s[top - 1].branch_id].rect);
188  result =
189  RTreeAddBranch(b, s[top].sn, &n2, ee, cover, overflow, t);
190 
191  /* update node */
192  RTreeNodeChanged(s[top].sn, s[top].pos, t);
193 
194  /* write out new node if node was split */
195  if (result == 1) {
196  *newnode_pos = RTreeGetNodePos(t);
197  RTreeWriteNode(n2, t);
198  t->n_nodes++;
199  }
200  }
201  }
202 
203  return result;
204 }
205 
206 /*
207  * Insert a data rectangle into an index structure.
208  * RTreeInsertRect provides for splitting the root;
209  * returns 1 if root was split, 0 if it was not.
210  * The level argument specifies the number of steps up from the leaf
211  * level to insert; e.g. a data rectangle goes in at level = 0.
212  * RTreeInsertRect2 does the actual insertion.
213  */
214 int RTreeInsertRectF(struct RTree_Rect *r, union RTree_Child child, int level,
215  struct RTree *t)
216 {
217  struct RTree_ListBranch *reInsertList = NULL;
218  struct RTree_ListBranch *e;
219  int result;
220  char overflow[MAXLEVEL];
221  struct RTree_Branch *b = &(t->tmpb1);
222  off_t newnode_pos = -1;
223 
224  struct RTree_Node *oldroot;
225  static struct RTree_Node *newroot = NULL, *newnode = NULL;
226 
227  if (!newroot) {
228  newroot = RTreeAllocNode(t, 1);
229  newnode = RTreeAllocNode(t, 1);
230  }
231 
232  /* R*-tree forced reinsertion: for each level only once */
233  memset(overflow, t->overflow, MAXLEVEL);
234 
235  result = RTreeInsertRect2F(r, child, level, newnode, &newnode_pos,
236  t, &reInsertList, overflow);
237 
238  if (result == 1) { /* root split */
239  oldroot = RTreeGetNode(t->rootpos, t->rootlevel, t);
240  /* grow a new root, & tree taller */
241  t->rootlevel++;
242  RTreeInitNode(t, newroot, NODETYPE(t->rootlevel, t->fd));
243  newroot->level = t->rootlevel;
244  /* branch for old root */
245  RTreeNodeCover(oldroot, &(b->rect), t);
246  b->child.pos = t->rootpos;
247  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
248  /* branch for new node created by RTreeInsertRect2() */
249  RTreeNodeCover(newnode, &(b->rect), t);
250  b->child.pos = newnode_pos; /* offset to new node as returned by RTreeInsertRect2F() */
251  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
252  /* write new root node */
253  t->rootpos = RTreeGetNodePos(t);
254  RTreeWriteNode(newroot, t);
255  t->n_nodes++;
256 
257  return result;
258  }
259 
260  if (result == 2) { /* branches were removed */
261  while (reInsertList) {
262  /* get next branch in list */
263  RTreeCopyBranch(b, &(reInsertList->b), t);
264  level = reInsertList->level;
265  e = reInsertList;
266  reInsertList = reInsertList->next;
268  /* reinsert branches */
269  result =
270  RTreeInsertRect2F(&(b->rect), b->child, level, newnode, &newnode_pos, t,
271  &reInsertList, overflow);
272 
273  if (result == 1) { /* root split */
274  oldroot = RTreeGetNode(t->rootpos, t->rootlevel, t);
275  /* grow a new root, & tree taller */
276  t->rootlevel++;
277  RTreeInitNode(t, newroot, NODETYPE(t->rootlevel, t->fd));
278  newroot->level = t->rootlevel;
279  /* branch for old root */
280  RTreeNodeCover(oldroot, &(b->rect), t);
281  b->child.pos = t->rootpos;
282  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
283  /* branch for new node created by RTreeInsertRect2() */
284  RTreeNodeCover(newnode, &(b->rect), t);
285  b->child.pos = newnode_pos;
286  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
287  /* write new root node */
288  t->rootpos = RTreeGetNodePos(t);
289  RTreeWriteNode(newroot, t);
290  t->n_nodes++;
291  }
292  }
293  }
294 
295  return result;
296 }
297 
298 /*
299  * Delete a rectangle from non-root part of an index structure.
300  * Called by RTreeDeleteRect. Descends tree non-recursively,
301  * merges branches on the way back up.
302  * Returns 1 if record not found, 0 if success.
303  */
304 static int
305 RTreeDeleteRect2F(struct RTree_Rect *r, union RTree_Child child, struct RTree *t,
306  struct RTree_ListNode **ee)
307 {
308  int i, notfound = 1, currlevel;
309  struct RTree_Node *n;
310  int top = 0, down = 0;
311  int minfill;
312  struct nstack *s = t->ns;
313 
314  struct RTree_Rect *nr = &(t->orect);
315 
316  /* add root node position to stack */
317  currlevel = t->rootlevel;
318  s[top].pos = t->rootpos;
319  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
320  s[top].branch_id = 0;
321 
322  while (notfound && top >= 0) {
323  /* go down to level 0, remember path */
324  if (s[top].sn->level > 0) {
325  n = s[top].sn;
326  currlevel = s[top].sn->level - 1;
327  for (i = s[top].branch_id; i < t->nodecard; i++) {
328  if (n->branch[i].child.pos > -1 &&
329  RTreeOverlap(r, &(n->branch[i].rect), t)) {
330  s[top++].branch_id = i + 1;
331  /* add next node to stack */
332  s[top].pos = n->branch[i].child.pos;
333  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
334  s[top].branch_id = 0;
335 
336  notfound = 0;
337  break;
338  }
339  }
340  if (notfound) {
341  /* nothing else found, go back up */
342  s[top].branch_id = t->nodecard;
343  top--;
344  }
345  else /* found a way down but not yet the item */
346  notfound = 1;
347  }
348  else {
349  for (i = 0; i < t->leafcard; i++) {
350  if (s[top].sn->branch[i].child.id &&
351  s[top].sn->branch[i].child.id == child.id) { /* found item */
352  RTreeDisconnectBranch(s[top].sn, i, t);
353  RTreeNodeChanged(s[top].sn, s[top].pos, t);
354  t->n_leafs--;
355  notfound = 0;
356  break;
357  }
358  }
359  if (notfound) /* continue searching */
360  top--;
361  }
362  }
363 
364  if (notfound) {
365  return notfound;
366  }
367 
368  /* go back up */
369  while (top) {
370  down = top;
371  top--;
372  i = s[top].branch_id - 1;
373 
374  minfill = (s[down].sn->level ? t->min_node_fill : t->min_leaf_fill);
375  if (s[down].sn->count >= minfill) {
376  /* just update node cover */
377  RTreeNodeCover(s[down].sn, nr, t);
378  /* rewrite rect */
379  if (!RTreeCompareRect(nr, &(s[top].sn->branch[i].rect), t)) {
380  RTreeCopyRect(&(s[top].sn->branch[i].rect), nr, t);
381  RTreeNodeChanged(s[top].sn, s[top].pos, t);
382  }
383  }
384  else {
385  /* not enough entries in child, eliminate child node */
386  n = RTreeAllocNode(t, s[down].sn->level);
387  /* copy node */
388  RTreeCopyNode(n, s[down].sn, t);
389  RTreeAddNodePos(s[down].pos, s[down].sn->level, t);
390  RTreeReInsertNode(n, ee);
391  RTreeDisconnectBranch(s[top].sn, i, t);
392 
393  RTreeNodeChanged(s[top].sn, s[top].pos, t);
394  }
395  }
396 
397  return notfound;
398 }
399 
400 /*
401  * should be called by RTreeDeleteRect() only
402  *
403  * Delete a data rectangle from an index structure.
404  * Pass in a pointer to a Rect, the tid of the record, ptr RTree.
405  * Returns 1 if record not found, 0 if success.
406  * RTreeDeleteRect1 provides for eliminating the root.
407  */
408 int RTreeDeleteRectF(struct RTree_Rect *r, union RTree_Child child, struct RTree *t)
409 {
410  int i;
411  struct RTree_Node *n;
412  struct RTree_ListNode *e, *reInsertList = NULL;
413 
414  if (!RTreeDeleteRect2F(r, child, t, &reInsertList)) {
415  /* found and deleted a data item */
416 
417  /* reinsert any branches from eliminated nodes */
418  while (reInsertList) {
419  t->n_nodes--;
420  n = reInsertList->node;
421  if (n->level > 0) { /* reinsert node branches */
422  for (i = 0; i < t->nodecard; i++) {
423  if (n->branch[i].child.pos > -1) {
424  RTreeInsertRectF(&(n->branch[i].rect),
425  n->branch[i].child, n->level, t);
426  }
427  }
428  }
429  else { /* reinsert leaf branches */
430  for (i = 0; i < t->leafcard; i++) {
431  if (n->branch[i].child.id) {
432  RTreeInsertRectF(&(n->branch[i].rect),
433  n->branch[i].child, n->level, t);
434  }
435  }
436  }
437  e = reInsertList;
438  reInsertList = reInsertList->next;
439  RTreeFreeNode(e->node);
441  }
442 
443  /* check for redundant root (not leaf, 1 child) and eliminate */
444  n = RTreeGetNode(t->rootpos, t->rootlevel, t);
445 
446  if (n->count == 1 && n->level > 0) {
447  for (i = 0; i < t->nodecard; i++) {
448  if (n->branch[i].child.pos > -1)
449  break;
450  }
451  RTreeAddNodePos(t->rootpos, t->rootlevel, t);
452  t->rootpos = n->branch[i].child.pos;
453  t->rootlevel--;
454  t->n_nodes--;
455  }
456 
457  return 0;
458  }
459 
460  return 1;
461 }
struct RTree_Rect rect_0 rect_1 upperrect orect
Definition: rtree.h:189
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:99
int branch_id
Definition: rtree.h:106
struct RTree_Node * node
Definition: index.h:37
int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:576
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 rootlevel
Definition: rtree.h:143
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition: node.c:112
int count
Definition: rtree.h:79
off_t pos
Definition: rtree.h:68
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
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
Definition: node.c:65
int min_node_fill
Definition: rtree.h:148
int RTreeSearchF(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Definition: indexf.c:37
double t
Definition: r_raster.c:39
Definition: rtree.h:103
void RTreeFreeListNode(struct RTree_ListNode *p)
double b
Definition: r_raster.c:39
int RTreeDeleteRectF(struct RTree_Rect *r, union RTree_Child child, struct RTree *t)
Definition: indexf.c:408
int RTreeValidChildF(union RTree_Child *child)
Definition: indexf.c:27
void RTreeAddNodePos(off_t, int, struct RTree *)
Definition: io.c:32
void RTreeDisconnectBranch(struct RTree_Node *, int, struct RTree *)
Definition: node.c:270
int RTreeInsertRectF(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree *t)
Definition: indexf.c:214
struct RTree_Branch * branch
Definition: rtree.h:81
off_t rootpos
Definition: rtree.h:192
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
off_t RTreeGetNodePos(struct RTree *t)
Definition: io.c:72
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
int fd
Definition: rtree.h:131
union RTree_Child child
Definition: rtree.h:74
struct RTree_Branch b
Definition: index.h:49
void RTreeNodeChanged(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:198
struct RTree_Node * RTreeGetNode(off_t, int, struct RTree *)
Definition: io.c:112
int id
Definition: rtree.h:66
#define NODETYPE(l, fd)
Definition: index.h:31
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
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:169
off_t pos
Definition: rtree.h:107
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_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