grass  7.8.6
About: GRASS (Geographic Resources Analysis Support System) is a raster- and vector-based GIS, image processing system, graphics production system and spatial modeling system.
  Fossies Dox: grass-7.8.6.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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
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 */
37int 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 */
108static 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 */
214int 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 */
304static int
305RTreeDeleteRect2F(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 */
408int 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) {
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) {
433 n->branch[i].child, n->level, t);
434 }
435 }
436 }
437 e = reInsertList;
438 reInsertList = reInsertList->next;
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}
#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:542
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:136
void RTreeAddNodePos(off_t, int, struct RTree *)
Definition: io.c:32
struct RTree_Node * RTreeGetNode(off_t, int, struct RTree *)
Definition: io.c:112
#define NODETYPE(l, fd)
Definition: index.h:31
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:126
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:198
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:542
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:99
int RTreeCompareRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:577
int RTreeSearchF(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Definition: indexf.c:37
int RTreeValidChildF(union RTree_Child *child)
Definition: indexf.c:27
int RTreeDeleteRectF(struct RTree_Rect *r, union RTree_Child child, struct RTree *t)
Definition: indexf.c:408
static int RTreeDeleteRect2F(struct RTree_Rect *r, union RTree_Child child, struct RTree *t, struct RTree_ListNode **ee)
Definition: indexf.c:305
int RTreeInsertRectF(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree *t)
Definition: indexf.c:214
static int RTreeInsertRect2F(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree_Node *newnode, off_t *newnode_pos, struct RTree *t, struct RTree_ListBranch **ee, char *overflow)
Definition: indexf.c:108
off_t RTreeGetNodePos(struct RTree *t)
Definition: io.c:72
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:169
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition: node.c:112
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:98
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:77
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
Definition: node.c:65
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:597
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:91
struct RTree_Rect rect
Definition: rtree.h:73
union RTree_Child child
Definition: rtree.h:74
struct RTree_ListBranch * next
Definition: index.h:48
struct RTree_Branch b
Definition: index.h:49
struct RTree_ListNode * next
Definition: index.h:36
struct RTree_Node * node
Definition: index.h:37
int count
Definition: rtree.h:79
int level
Definition: rtree.h:80
struct RTree_Branch * branch
Definition: rtree.h:81
Definition: rtree.h:129
Definition: rtree.h:104
off_t pos
Definition: rtree.h:107
struct RTree_Node * sn
Definition: rtree.h:105
int branch_id
Definition: rtree.h:106
static unsigned int s
Definition: unfl.c:9
off_t pos
Definition: rtree.h:68
int id
Definition: rtree.h:66
void RTreeFreeListNode(struct RTree_ListNode *p)
Definition: index.c:368
void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
Definition: index.c:377
void RTreeFreeListBranch(struct RTree_ListBranch *p)
Definition: index.c:389
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30