GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-6596d49e63
indexf.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) 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 <stdlib.h>
19 #include <stdio.h>
20 #include <string.h>
21 #include <sys/types.h>
22 #include <assert.h>
23 #include <grass/gis.h>
24 #include "index.h"
25 
26 int RTreeValidChildF(union RTree_Child *child)
27 {
28  return (child->pos > -1);
29 }
30 
31 /*
32  * Search in an index tree for all data rectangles that
33  * overlap the argument rectangle.
34  * Return the number of qualifying data rects.
35  */
36 int RTreeSearchF(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb,
37  void *cbarg)
38 {
39  struct RTree_Node *n;
40  int hitCount = 0, notfound, currlevel;
41  int i;
42  int top = 0;
43  struct nstack *s = t->ns;
44 
45  /* stack size of t->rootlevel + 1 is enough because of depth first search */
46  /* only one node per level on stack at any given time */
47 
48  /* add root node position to stack */
49  currlevel = t->rootlevel;
50  s[top].pos = t->rootpos;
51  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
52  s[top].branch_id = i = 0;
53 
54  while (top >= 0) {
55  n = s[top].sn;
56  if (s[top].sn->level > 0) { /* this is an internal node in the tree */
57  notfound = 1;
58  currlevel = s[top].sn->level - 1;
59  for (i = s[top].branch_id; i < t->nodecard; i++) {
60  if (s[top].sn->branch[i].child.pos > -1 &&
61  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
62  s[top++].branch_id = i + 1;
63  /* add next node to stack */
64  s[top].pos = n->branch[i].child.pos;
65  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
66  s[top].branch_id = 0;
67  notfound = 0;
68  break;
69  }
70  }
71  if (notfound) {
72  /* nothing else found, go back up */
73  s[top].branch_id = t->nodecard;
74  top--;
75  }
76  }
77  else { /* this is a leaf node */
78  for (i = 0; i < t->leafcard; i++) {
79  if (s[top].sn->branch[i].child.id &&
80  RTreeOverlap(r, &(s[top].sn->branch[i].rect), t)) {
81  hitCount++;
82  if (shcb) { /* call the user-provided callback */
83  if (!shcb(s[top].sn->branch[i].child.id,
84  &(s[top].sn->branch[i].rect), cbarg)) {
85  /* callback wants to terminate search early */
86  return hitCount;
87  }
88  }
89  }
90  }
91  top--;
92  }
93  }
94 
95  return hitCount;
96 }
97 
98 /*
99  * Inserts a new data rectangle into the index structure.
100  * Non-recursively descends tree, propagates splits back up.
101  * Returns 0 if node was not split. Old node updated.
102  * If node was split, returns 1 and sets the pointer pointed to by
103  * new_node to point to the new node. Old node updated to become one of two.
104  * The level argument specifies the number of steps up from the leaf
105  * level to insert; e.g. a data rectangle goes in at level = 0.
106  */
107 static int RTreeInsertRect2F(struct RTree_Rect *r, union RTree_Child child,
108  int level, struct RTree_Node *newnode,
109  off_t *newnode_pos, struct RTree *t,
110  struct RTree_ListBranch **ee, char *overflow)
111 {
112  int i, currlevel;
113  struct RTree_Node *n, *n2;
114  struct RTree_Rect *cover;
115  int top = 0, down = 0;
116  int result;
117  struct RTree_Branch *b = &(t->tmpb2);
118  struct nstack *s = t->ns;
119 
120  struct RTree_Rect *nr = &(t->orect);
121 
122  n2 = newnode;
123 
124  /* add root node position to stack */
125  currlevel = t->rootlevel;
126  s[top].pos = t->rootpos;
127  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
128 
129  /* go down to level of insertion */
130  while (s[top].sn->level > level) {
131  n = s[top].sn;
132  currlevel = s[top].sn->level - 1;
133  i = RTreePickBranch(r, n, t);
134  s[top++].branch_id = i;
135  /* add next node to stack */
136  s[top].pos = n->branch[i].child.pos;
137  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
138  }
139 
140  /* Have reached level for insertion. Add rect, split if necessary */
141  RTreeCopyRect(&(b->rect), r, t);
142  /* child field of leaves contains tid of data record */
143  b->child = child;
144  /* add branch, may split node or remove branches */
145  cover = NULL;
146  if (top)
147  cover = &(s[top - 1].sn->branch[s[top - 1].branch_id].rect);
148  result = RTreeAddBranch(b, s[top].sn, &n2, ee, cover, overflow, t);
149  /* update node */
150  RTreeNodeChanged(s[top].sn, s[top].pos, t);
151  /* write out new node if node was split */
152  if (result == 1) {
153  *newnode_pos = RTreeGetNodePos(t);
154  RTreeWriteNode(n2, t);
155  t->n_nodes++;
156  }
157 
158  /* go back up */
159  while (top) {
160  down = top--;
161  i = s[top].branch_id;
162  if (result == 0) { /* branch was added */
163  if (RTreeExpandRect(&(s[top].sn->branch[i].rect), r, t)) {
164  RTreeNodeChanged(s[top].sn, s[top].pos, t);
165  }
166  }
167  else if (result == 2) { /* branches were removed */
168  /* get node cover of previous node */
169  RTreeNodeCover(s[down].sn, nr, t);
170  /* rewrite rect */
171  if (!RTreeCompareRect(nr, &(s[top].sn->branch[i].rect), t)) {
172  RTreeCopyRect(&(s[top].sn->branch[i].rect), nr, t);
173  RTreeNodeChanged(s[top].sn, s[top].pos, t);
174  }
175  }
176  else if (result == 1) { /* node was split */
177  /* get node cover of previous node */
178  RTreeNodeCover(s[down].sn, &(s[top].sn->branch[i].rect), t);
179  /* add new branch for new node previously added by RTreeAddBranch()
180  */
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 = RTreeAddBranch(b, s[top].sn, &n2, ee, cover, overflow, t);
189 
190  /* update node */
191  RTreeNodeChanged(s[top].sn, s[top].pos, t);
192 
193  /* write out new node if node was split */
194  if (result == 1) {
195  *newnode_pos = RTreeGetNodePos(t);
196  RTreeWriteNode(n2, t);
197  t->n_nodes++;
198  }
199  }
200  }
201 
202  return result;
203 }
204 
205 /*
206  * Insert a data rectangle into an index structure.
207  * RTreeInsertRect provides for splitting the root;
208  * returns 1 if root was split, 0 if it was not.
209  * The level argument specifies the number of steps up from the leaf
210  * level to insert; e.g. a data rectangle goes in at level = 0.
211  * RTreeInsertRect2 does the actual insertion.
212  */
213 int RTreeInsertRectF(struct RTree_Rect *r, union RTree_Child child, int level,
214  struct RTree *t)
215 {
216  struct RTree_ListBranch *reInsertList = NULL;
217  struct RTree_ListBranch *e;
218  int result;
219  char overflow[MAXLEVEL];
220  struct RTree_Branch *b = &(t->tmpb1);
221  off_t newnode_pos = -1;
222 
223  struct RTree_Node *oldroot;
224  static struct RTree_Node *newroot = NULL, *newnode = NULL;
225 
226  if (!newroot) {
227  newroot = RTreeAllocNode(t, 1);
228  newnode = RTreeAllocNode(t, 1);
229  }
230 
231  /* R*-tree forced reinsertion: for each level only once */
232  memset(overflow, t->overflow, MAXLEVEL);
233 
234  result = RTreeInsertRect2F(r, child, level, newnode, &newnode_pos, t,
235  &reInsertList, overflow);
236 
237  if (result == 1) { /* root split */
238  oldroot = RTreeGetNode(t->rootpos, t->rootlevel, t);
239  /* grow a new root, & tree taller */
240  t->rootlevel++;
241  RTreeInitNode(t, newroot, NODETYPE(t->rootlevel, t->fd));
242  newroot->level = t->rootlevel;
243  /* branch for old root */
244  RTreeNodeCover(oldroot, &(b->rect), t);
245  b->child.pos = t->rootpos;
246  RTreeAddBranch(b, newroot, NULL, NULL, NULL, NULL, t);
247  /* branch for new node created by RTreeInsertRect2() */
248  RTreeNodeCover(newnode, &(b->rect), t);
249  b->child.pos = newnode_pos; /* offset to new node as returned by
250  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,
271  &newnode_pos, t, &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 RTreeDeleteRect2F(struct RTree_Rect *r, union RTree_Child child,
305  struct RTree *t, struct RTree_ListNode **ee)
306 {
307  int i, notfound = 1, currlevel;
308  struct RTree_Node *n;
309  int top = 0, down = 0;
310  int minfill;
311  struct nstack *s = t->ns;
312 
313  struct RTree_Rect *nr = &(t->orect);
314 
315  /* add root node position to stack */
316  currlevel = t->rootlevel;
317  s[top].pos = t->rootpos;
318  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
319  s[top].branch_id = 0;
320 
321  while (notfound && top >= 0) {
322  /* go down to level 0, remember path */
323  if (s[top].sn->level > 0) {
324  n = s[top].sn;
325  currlevel = s[top].sn->level - 1;
326  for (i = s[top].branch_id; i < t->nodecard; i++) {
327  if (n->branch[i].child.pos > -1 &&
328  RTreeOverlap(r, &(n->branch[i].rect), t)) {
329  s[top++].branch_id = i + 1;
330  /* add next node to stack */
331  s[top].pos = n->branch[i].child.pos;
332  s[top].sn = RTreeGetNode(s[top].pos, currlevel, t);
333  s[top].branch_id = 0;
334 
335  notfound = 0;
336  break;
337  }
338  }
339  if (notfound) {
340  /* nothing else found, go back up */
341  s[top].branch_id = t->nodecard;
342  top--;
343  }
344  else /* found a way down but not yet the item */
345  notfound = 1;
346  }
347  else {
348  for (i = 0; i < t->leafcard; i++) {
349  if (s[top].sn->branch[i].child.id &&
350  s[top].sn->branch[i].child.id ==
351  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,
409  struct RTree *t)
410 {
411  int i;
412  struct RTree_Node *n;
413  struct RTree_ListNode *e, *reInsertList = NULL;
414 
415  if (!RTreeDeleteRect2F(r, child, t, &reInsertList)) {
416  /* found and deleted a data item */
417 
418  /* reinsert any branches from eliminated nodes */
419  while (reInsertList) {
420  t->n_nodes--;
421  n = reInsertList->node;
422  if (n->level > 0) { /* reinsert node branches */
423  for (i = 0; i < t->nodecard; i++) {
424  if (n->branch[i].child.pos > -1) {
425  RTreeInsertRectF(&(n->branch[i].rect),
426  n->branch[i].child, n->level, t);
427  }
428  }
429  }
430  else { /* reinsert leaf branches */
431  for (i = 0; i < t->leafcard; i++) {
432  if (n->branch[i].child.id) {
433  RTreeInsertRectF(&(n->branch[i].rect),
434  n->branch[i].child, n->level, t);
435  }
436  }
437  }
438  e = reInsertList;
439  reInsertList = reInsertList->next;
440  RTreeFreeNode(e->node);
442  }
443 
444  /* check for redundant root (not leaf, 1 child) and eliminate */
445  n = RTreeGetNode(t->rootpos, t->rootlevel, t);
446 
447  if (n->count == 1 && n->level > 0) {
448  for (i = 0; i < t->nodecard; i++) {
449  if (n->branch[i].child.pos > -1)
450  break;
451  }
452  RTreeAddNodePos(t->rootpos, t->rootlevel, t);
453  t->rootpos = n->branch[i].child.pos;
454  t->rootlevel--;
455  t->n_nodes--;
456  }
457 
458  return 0;
459  }
460 
461  return 1;
462 }
#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 RTreeAddNodePos(off_t, int, struct RTree *)
Definition: io.c:31
#define NODETYPE(l, fd)
Definition: index.h:31
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:124
struct RTree_Node * RTreeGetNode(off_t, int, struct RTree *)
Definition: io.c:111
int RTreePickBranch(struct RTree_Rect *, struct RTree_Node *, struct RTree *)
Definition: node.c:236
void RTreeNodeChanged(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:201
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:536
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:100
int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:570
int RTreeSearchF(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Definition: indexf.c:36
int RTreeValidChildF(union RTree_Child *child)
Definition: indexf.c:26
int RTreeDeleteRectF(struct RTree_Rect *r, union RTree_Child child, struct RTree *t)
Definition: indexf.c:408
int RTreeInsertRectF(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree *t)
Definition: indexf.c:213
off_t RTreeGetNodePos(struct RTree *t)
Definition: io.c:71
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:170
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition: node.c:109
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:95
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:74
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
Definition: node.c:62
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
off_t pos
Definition: rtree.h:103
struct RTree_Node * sn
Definition: rtree.h:101
int branch_id
Definition: rtree.h:102
off_t pos
Definition: rtree.h:63
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