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)  

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
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 */
34int 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 */
102static 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 */
186int 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 */
264static int
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 */
354int 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) {
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) {
380 n->branch[i].child, n->level, t);
381 }
382 }
383 }
384 e = reInsertList;
385 reInsertList = reInsertList->next;
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 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 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
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:542
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:99
int RTreeDeleteRectM(struct RTree_Rect *r, union RTree_Child child, struct RTree *t)
Definition: indexm.c:354
static int RTreeInsertRect2M(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree_Node **newnode, struct RTree *t, struct RTree_ListBranch **ee, char *overflow)
Definition: indexm.c:102
static int RTreeDeleteRect2M(struct RTree_Rect *r, union RTree_Child child, struct RTree *t, struct RTree_ListNode **ee)
Definition: indexm.c:265
int RTreeSearchM(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Definition: indexm.c:34
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:24
int RTreeInsertRectM(struct RTree_Rect *r, union RTree_Child child, int level, struct RTree *t)
Definition: indexm.c:186
#define assert(condition)
Definition: lz4.c:324
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:98
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:77
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
struct RTree_Node * sn
Definition: rtree.h:105
int branch_id
Definition: rtree.h:106
static unsigned int s
Definition: unfl.c:9
struct RTree_Node * ptr
Definition: rtree.h:67
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