← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to lib/vector/rtree/index.c

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/vector/rtree/index.c
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
 
*               
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 <stdio.h>
 
1
/*!
 
2
   \file lib/vector/rtree/index.c
 
3
 
 
4
   \brief R-Tree library - Multidimensional index
 
5
 
 
6
   Higher level functions for managing R*-Trees.
 
7
 
 
8
   (C) 2010-2012 by the GRASS Development Team
 
9
 
 
10
   This program is free software under the 
 
11
   GNU General Public License (>=v2). 
 
12
   Read the file COPYING that comes with GRASS
 
13
   for details.
 
14
 
 
15
   \author Antonin Guttman - original code
 
16
   \author Daniel Green (green@superliminal.com) - major clean-up
 
17
               and implementation of bounding spheres
 
18
   \author Markus Metz - file-based and memory-based R*-tree
 
19
 */
 
20
 
 
21
/* Read these articles first before attempting to modify the code
 
22
 * 
 
23
 * R-Tree reference:
 
24
 * Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial
 
25
 * Searching". Proceedings of the 1984 ACM SIGMOD international 
 
26
 * conference on Management of data - SIGMOD '84. pp. 47.
 
27
 * DOI:10.1145/602259.602266
 
28
 * ISBN 0897911288
 
29
 *  
 
30
 * R*-Tree reference:
 
31
 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
 
32
 * "The R*-tree: an efficient and robust access method for points and 
 
33
 * rectangles". Proceedings of the 1990 ACM SIGMOD international 
 
34
 * conference on Management of data - SIGMOD '90. pp. 322.
 
35
 * DOI:10.1145/93597.98741
 
36
 * ISBN 0897913655
 
37
 */
 
38
 
19
39
#include <stdlib.h>
20
 
#include "assert.h"
 
40
#include <sys/types.h>
 
41
#include <unistd.h>
 
42
#include <assert.h>
 
43
#include <grass/gis.h>
21
44
#include "index.h"
22
 
#include "card.h"
23
 
 
24
 
/* Make a new index, empty.  Consists of a single node. */
25
 
struct Node *RTreeNewIndex(void)
26
 
{
27
 
    struct Node *x;
28
 
 
29
 
    x = RTreeNewNode();
30
 
    x->level = 0;               /* leaf */
31
 
    return x;
32
 
}
33
 
 
34
 
/*
35
 
 * Search in an index tree or subtree for all data retangles that
36
 
 * overlap the argument rectangle.
37
 
 * Return the number of qualifying data rects.
38
 
 */
39
 
int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb,
40
 
                void *cbarg)
41
 
{
42
 
    register struct Node *n = N;
43
 
    register struct Rect *r = R;        /* NOTE: Suspected bug was R sent in as Node* and cast to Rect* here. */
44
 
 
45
 
    /* Fix not yet tested. */
46
 
    register int hitCount = 0;
47
 
    register int i;
48
 
 
49
 
    assert(n);
50
 
    assert(n->level >= 0);
51
 
    assert(r);
52
 
 
53
 
    if (n->level > 0) {         /* this is an internal node in the tree */
54
 
        for (i = 0; i < NODECARD; i++)
55
 
            if (n->branch[i].child && RTreeOverlap(r, &n->branch[i].rect)) {
56
 
                hitCount += RTreeSearch(n->branch[i].child, r, shcb, cbarg);
57
 
            }
58
 
    }
59
 
    else {                      /* this is a leaf node */
60
 
 
61
 
        for (i = 0; i < LEAFCARD; i++)
62
 
            if (n->branch[i].child && RTreeOverlap(r, &n->branch[i].rect)) {
63
 
                hitCount++;
64
 
                if (shcb)       /* call the user-provided callback */
65
 
                    if (!shcb((int)n->branch[i].child, cbarg))
66
 
                        return hitCount;        /* callback wants to terminate search early */
67
 
            }
68
 
    }
69
 
    return hitCount;
70
 
}
71
 
 
72
 
/*
73
 
 * Inserts a new data rectangle into the index structure.
74
 
 * Recursively descends tree, propagates splits back up.
75
 
 * Returns 0 if node was not split.  Old node updated.
76
 
 * If node was split, returns 1 and sets the pointer pointed to by
77
 
 * new_node to point to the new node.  Old node updated to become one of two.
78
 
 * The level argument specifies the number of steps up from the leaf
79
 
 * level to insert; e.g. a data rectangle goes in at level = 0.
80
 
 */
81
 
static int RTreeInsertRect2(struct Rect *r,
82
 
                            struct Node *child, struct Node *n, struct Node **new_node,
83
 
                            int level)
84
 
{
85
 
    /*
86
 
       register struct Rect *r = R;
87
 
       register int tid = Tid;
88
 
       register struct Node *n = N, **new_node = New_node;
89
 
       register int level = Level;
90
 
     */
91
 
 
92
 
    register int i;
93
 
    struct Branch b;
94
 
    struct Node *n2;
95
 
 
96
 
    assert(r && n && new_node);
97
 
    assert(level >= 0 && level <= n->level);
98
 
 
99
 
    /* Still above level for insertion, go down tree recursively */
100
 
    if (n->level > level) {
101
 
        i = RTreePickBranch(r, n);
102
 
        if (!RTreeInsertRect2(r, child, n->branch[i].child, &n2, level)) {
103
 
            /* child was not split */
104
 
            n->branch[i].rect = RTreeCombineRect(r, &(n->branch[i].rect));
105
 
            return 0;
106
 
        }
107
 
        else {                  /* child was split */
108
 
 
109
 
            n->branch[i].rect = RTreeNodeCover(n->branch[i].child);
110
 
            b.child = n2;
111
 
            b.rect = RTreeNodeCover(n2);
112
 
            return RTreeAddBranch(&b, n, new_node);
113
 
        }
114
 
    }
115
 
 
116
 
    /* Have reached level for insertion. Add rect, split if necessary */
117
 
    else if (n->level == level) {
118
 
        b.rect = *r;
119
 
        b.child = child;
120
 
        /* child field of leaves contains tid of data record */
121
 
        return RTreeAddBranch(&b, n, new_node);
122
 
    }
123
 
    else {
124
 
        /* Not supposed to happen */
125
 
        assert(FALSE);
126
 
        return 0;
127
 
    }
128
 
}
129
 
 
130
 
/* 
131
 
 * Insert a data rectangle into an index structure.
132
 
 * RTreeInsertRect provides for splitting the root;
133
 
 * returns 1 if root was split, 0 if it was not.
134
 
 * The level argument specifies the number of steps up from the leaf
135
 
 * level to insert; e.g. a data rectangle goes in at level = 0.
136
 
 * RTreeInsertRect2 does the recursion.
137
 
 */
138
 
int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level)
139
 
{
140
 
    assert(Level == 0);
141
 
    return RTreeInsertRect1(R, (struct Node *) Tid, Root, Level);
142
 
}
143
 
 
144
 
int RTreeInsertRect1(struct Rect *R, struct Node *Child, struct Node **Root, int Level)
145
 
{
146
 
    register struct Rect *r = R;
147
 
    register struct Node *child = Child;
148
 
    register struct Node **root = Root;
149
 
    register int level = Level;
150
 
    register int i;
151
 
    register struct Node *newroot;
152
 
    struct Node *newnode;
153
 
    struct Branch b;
154
 
    int result;
155
 
 
156
 
    assert(r && root);
157
 
    assert(level >= 0 && level <= (*root)->level);
158
 
    for (i = 0; i < NUMDIMS; i++) {
159
 
        assert(r->boundary[i] <= r->boundary[NUMDIMS + i]);
160
 
    }
161
 
 
162
 
    if (RTreeInsertRect2(r, child, *root, &newnode, level)) {   /* root split */
163
 
        newroot = RTreeNewNode();       /* grow a new root, & tree taller */
164
 
        newroot->level = (*root)->level + 1;
165
 
        b.rect = RTreeNodeCover(*root);
166
 
        b.child = *root;
167
 
        RTreeAddBranch(&b, newroot, NULL);
168
 
        b.rect = RTreeNodeCover(newnode);
169
 
        b.child = newnode;
170
 
        RTreeAddBranch(&b, newroot, NULL);
171
 
        *root = newroot;
172
 
        result = 1;
173
 
    }
 
45
 
 
46
/*!
 
47
  \brief Create new empty R*-Tree
 
48
 
 
49
  This method creates a new RTree, either in memory (fd < 0) or in file.
 
50
  If the file descriptor is positive, the corresponding file must have 
 
51
  been opened for reading and writing.
 
52
  This method must also be called if an existing tree previously saved
 
53
  to file is going to be accessed.
 
54
 
 
55
  \param fd file descriptor to hold data, negative toggles memory mode
 
56
  \param rootpos offset in file to root node (past any header info)
 
57
  \param ndims number of dimensions for the new tree: min 2, max 20
 
58
 
 
59
  \return pointer to new RTree structure
 
60
*/
 
61
struct RTree *RTreeCreateTree(int fd, off_t rootpos, int ndims)
 
62
{
 
63
    struct RTree *new_rtree;
 
64
    struct RTree_Node *n;
 
65
    int i, j, k;
 
66
    
 
67
    new_rtree = (struct RTree *)malloc(sizeof(struct RTree));
 
68
 
 
69
    new_rtree->fd = fd;
 
70
    new_rtree->rootpos = rootpos;
 
71
    new_rtree->ndims = ndims;
 
72
    new_rtree->nsides = 2 * ndims;
 
73
    /* hack to keep compatibility */
 
74
    if (ndims < 3)
 
75
        new_rtree->ndims_alloc = 3;
174
76
    else
175
 
        result = 0;
176
 
 
177
 
    return result;
178
 
}
179
 
 
180
 
/*
181
 
 * Allocate space for a node in the list used in DeletRect to
 
77
        new_rtree->ndims_alloc = ndims;
 
78
 
 
79
    new_rtree->nsides_alloc = 2 * new_rtree->ndims_alloc;
 
80
 
 
81
    /* init free node positions */
 
82
    new_rtree->free_nodes.avail = 0;
 
83
    new_rtree->free_nodes.alloc = 0;
 
84
    new_rtree->free_nodes.pos = NULL;
 
85
 
 
86
    new_rtree->rectsize = new_rtree->nsides_alloc * sizeof(RectReal);
 
87
    new_rtree->nodesize = sizeof(struct RTree_Node) -
 
88
                          MAXCARD * sizeof(RectReal *) +
 
89
                          MAXCARD * new_rtree->rectsize;
 
90
 
 
91
    new_rtree->branchsize = sizeof(struct RTree_Branch) -
 
92
                            sizeof(RectReal *) + new_rtree->rectsize;
 
93
    
 
94
    /* create empty root node */
 
95
    n = RTreeAllocNode(new_rtree, 0);
 
96
    new_rtree->rootlevel = n->level = 0;       /* leaf */
 
97
    
 
98
    /* use overflow by default */
 
99
    new_rtree->overflow = 1;
 
100
 
 
101
    if (fd > -1) {  /* file based */
 
102
        /* nodecard and leafcard can be adjusted, must NOT be larger than MAXCARD */
 
103
        new_rtree->nodecard = MAXCARD;
 
104
        new_rtree->leafcard = MAXCARD;
 
105
 
 
106
        /* initialize node buffer */
 
107
        new_rtree->nb = calloc(MAXLEVEL, sizeof(struct NodeBuffer *));
 
108
        new_rtree->nb[0] = calloc(MAXLEVEL * NODE_BUFFER_SIZE, sizeof(struct NodeBuffer));
 
109
        for (i = 1; i < MAXLEVEL; i++) {
 
110
            new_rtree->nb[i] = new_rtree->nb[i - 1] + NODE_BUFFER_SIZE;
 
111
        }
 
112
 
 
113
        new_rtree->used = malloc(MAXLEVEL * sizeof(int *));
 
114
        new_rtree->used[0] = malloc(MAXLEVEL * NODE_BUFFER_SIZE * sizeof(int));
 
115
        for (i = 0; i < MAXLEVEL; i++) {
 
116
            if (i)
 
117
                new_rtree->used[i] = new_rtree->used[i - 1] + NODE_BUFFER_SIZE;
 
118
            for (j = 0; j < NODE_BUFFER_SIZE; j++) {
 
119
                new_rtree->nb[i][j].dirty = 0;
 
120
                new_rtree->nb[i][j].pos = -1;
 
121
                /* usage order */
 
122
                new_rtree->used[i][j] = j;
 
123
 
 
124
                new_rtree->nb[i][j].n.branch = malloc(MAXCARD * sizeof(struct RTree_Branch));
 
125
 
 
126
                /* alloc memory for rectangles */
 
127
                for (k = 0; k < MAXCARD; k++) {
 
128
                    new_rtree->nb[i][j].n.branch[k].rect.boundary = RTreeAllocBoundary(new_rtree);
 
129
                }
 
130
            }
 
131
        }
 
132
 
 
133
        /* write empty root node */
 
134
        lseek(new_rtree->fd, rootpos, SEEK_SET);
 
135
        RTreeWriteNode(n, new_rtree);
 
136
        RTreeFreeNode(n);
 
137
        new_rtree->root = NULL;
 
138
 
 
139
        new_rtree->insert_rect = RTreeInsertRectF;
 
140
        new_rtree->delete_rect = RTreeDeleteRectF;
 
141
        new_rtree->search_rect = RTreeSearchF;
 
142
        new_rtree->valid_child = RTreeValidChildF;
 
143
    }
 
144
    else {    /* memory based */
 
145
        new_rtree->nodecard = MAXCARD;
 
146
        new_rtree->leafcard = MAXCARD;
 
147
 
 
148
        new_rtree->insert_rect = RTreeInsertRectM;
 
149
        new_rtree->delete_rect = RTreeDeleteRectM;
 
150
        new_rtree->search_rect = RTreeSearchM;
 
151
        new_rtree->valid_child = RTreeValidChildM;
 
152
 
 
153
        new_rtree->root = n;
 
154
    }
 
155
 
 
156
    /* minimum number of remaining children for RTreeDeleteRect */
 
157
    /* NOTE: min fill can be changed if needed, must be < nodecard and leafcard. */
 
158
    new_rtree->min_node_fill = (new_rtree->nodecard - 2) / 2;
 
159
    new_rtree->min_leaf_fill = (new_rtree->leafcard - 2) / 2;
 
160
 
 
161
    /* balance criteria for node splitting */
 
162
    new_rtree->minfill_node_split = (new_rtree->nodecard - 1) / 2;
 
163
    new_rtree->minfill_leaf_split = (new_rtree->leafcard - 1) / 2;
 
164
 
 
165
    new_rtree->n_nodes = 1;
 
166
    new_rtree->n_leafs = 0;
 
167
 
 
168
    /* initialize temp variables */
 
169
    new_rtree->ns = malloc(MAXLEVEL * sizeof(struct nstack));
 
170
    
 
171
    new_rtree->p.cover[0].boundary = RTreeAllocBoundary(new_rtree);
 
172
    new_rtree->p.cover[1].boundary = RTreeAllocBoundary(new_rtree);
 
173
    
 
174
    new_rtree->tmpb1.rect.boundary = RTreeAllocBoundary(new_rtree);
 
175
    new_rtree->tmpb2.rect.boundary = RTreeAllocBoundary(new_rtree);
 
176
    new_rtree->c.rect.boundary = RTreeAllocBoundary(new_rtree);
 
177
 
 
178
    new_rtree->BranchBuf = malloc((MAXCARD + 1) * sizeof(struct RTree_Branch));
 
179
    for (i = 0; i <= MAXCARD; i++) {
 
180
        new_rtree->BranchBuf[i].rect.boundary = RTreeAllocBoundary(new_rtree);
 
181
    }
 
182
    new_rtree->rect_0.boundary = RTreeAllocBoundary(new_rtree);
 
183
    new_rtree->rect_1.boundary = RTreeAllocBoundary(new_rtree);
 
184
    new_rtree->upperrect.boundary = RTreeAllocBoundary(new_rtree);
 
185
    new_rtree->orect.boundary = RTreeAllocBoundary(new_rtree);
 
186
    new_rtree->center_n = (RectReal *)malloc(new_rtree->ndims_alloc * sizeof(RectReal));
 
187
 
 
188
    return new_rtree;
 
189
}
 
190
 
 
191
/*!
 
192
  \brief Enable/disable R*-tree forced reinsertion (overflow)
 
193
 
 
194
  For dynamic R*-trees with runtime insertion and deletion, 
 
195
  forced reinsertion results in a more compact tree, searches are a bit
 
196
  faster. For static R*-trees (no insertion/deletion after creation)
 
197
  forced reinsertion can be disabled at the cost of slower searches.
 
198
 
 
199
  \param t pointer to RTree structure
 
200
  \param overflow binary flag
 
201
 
 
202
  \return nothing
 
203
*/
 
204
void RTreeSetOverflow(struct RTree *t, char overflow)
 
205
{
 
206
    t->overflow = overflow != 0;
 
207
}
 
208
 
 
209
/*!
 
210
  \brief Destroy an R*-Tree
 
211
 
 
212
  This method releases all memory allocated to a RTree. It deletes all 
 
213
  rectangles and all memory allocated for internal support data.
 
214
  Note that for a file-based RTree, the file is not deleted and not 
 
215
  closed. The file can thus be used to permanently store an RTree.
 
216
 
 
217
  \param t pointer to RTree structure
 
218
 
 
219
  \return nothing
 
220
*/
 
221
 
 
222
void RTreeDestroyTree(struct RTree *t)
 
223
{
 
224
    int i;
 
225
 
 
226
    assert(t);
 
227
 
 
228
    if (t->fd > -1) {
 
229
        int j, k;
 
230
 
 
231
        for (i = 0; i < MAXLEVEL; i++) {
 
232
            for (j = 0; j < NODE_BUFFER_SIZE; j++) {
 
233
                for (k = 0; k < MAXCARD; k++) {
 
234
                    RTreeFreeBoundary(&t->nb[i][j].n.branch[k].rect);
 
235
                }
 
236
                free(t->nb[i][j].n.branch);
 
237
            }
 
238
        }
 
239
 
 
240
        if (t->free_nodes.alloc)
 
241
            free(t->free_nodes.pos);
 
242
        free(t->nb[0]);
 
243
        free(t->nb);
 
244
        free(t->used[0]);
 
245
        free(t->used);
 
246
    }
 
247
    else if (t->root)
 
248
        RTreeDestroyNode(t->root, t->root->level ? t->nodecard : t->leafcard);
 
249
 
 
250
    /* free temp variables */
 
251
    free(t->ns);
 
252
    
 
253
    RTreeFreeBoundary(&(t->p.cover[0]));
 
254
    RTreeFreeBoundary(&(t->p.cover[1]));
 
255
    
 
256
    RTreeFreeBoundary(&(t->tmpb1.rect));
 
257
    RTreeFreeBoundary(&(t->tmpb2.rect));
 
258
    RTreeFreeBoundary(&(t->c.rect));
 
259
    for (i = 0; i <= MAXCARD; i++) {
 
260
        RTreeFreeBoundary(&(t->BranchBuf[i].rect));
 
261
    }
 
262
    free(t->BranchBuf);
 
263
    RTreeFreeBoundary(&(t->rect_0));
 
264
    RTreeFreeBoundary(&(t->rect_1));
 
265
    RTreeFreeBoundary(&(t->upperrect));
 
266
    RTreeFreeBoundary(&(t->orect));
 
267
    free(t->center_n);
 
268
 
 
269
    free(t);
 
270
    
 
271
    return;
 
272
}
 
273
 
 
274
/*!
 
275
  \brief Search an R*-Tree
 
276
 
 
277
  Search in an RTree for all data retangles that overlap or touch the 
 
278
  argument rectangle.
 
279
  Return the number of qualifying data rectangles.
 
280
  The search stops if the SearchHitCallBack function returns 0 (zero)
 
281
  or if there are no more qualifying data rectangles.
 
282
 
 
283
  \param t pointer to RTree structure
 
284
  \param r pointer to rectangle to use for searching
 
285
  \param shcb Search Hit CallBack function
 
286
  \param cbarg custom pointer used as argument for the shcb fn
 
287
 
 
288
  \return number of qualifying data rectangles
 
289
*/
 
290
/*
 
291
 * 
 
292
 * add option to select operator to select rectangles ?
 
293
 * current: overlap
 
294
 * possible alternatives: 
 
295
 *  - select all rectangles that are fully contained in r
 
296
 *  - select all rectangles that fully contain r
 
297
 */
 
298
int RTreeSearch(struct RTree *t, struct RTree_Rect *r,
 
299
                SearchHitCallback *shcb, void *cbarg)
 
300
{
 
301
    assert(r && t);
 
302
 
 
303
    return t->search_rect(t, r, shcb, cbarg);
 
304
}
 
305
 
 
306
/*!
 
307
  \brief Insert an item into a R*-Tree
 
308
 
 
309
  \param r pointer to rectangle to use for searching
 
310
  \param tid data id stored with rectangle, must be > 0
 
311
  \param t pointer to RTree structure
 
312
 
 
313
  \return number of qualifying data rectangles
 
314
*/
 
315
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
 
316
{
 
317
    union RTree_Child newchild;
 
318
 
 
319
    assert(r && t && tid > 0);
 
320
    
 
321
    t->n_leafs++;
 
322
    newchild.id = tid;
 
323
    
 
324
    return t->insert_rect(r, newchild, 0, t);
 
325
}
 
326
 
 
327
/*!
 
328
  \brief Delete an item from a R*-Tree
 
329
  
 
330
  This method deletes an item from the RTree. The rectangle passed to 
 
331
  this method does not need to be the exact rectangle, the only
 
332
  requirement is that this rectangle overlaps with the rectangle to 
 
333
  be deleted. The rectangle to be deleted is identified by its id.
 
334
 
 
335
  \param r pointer to rectangle to use for searching
 
336
  \param tid id of the data to be deleted, must be > 0
 
337
  \param t pointer to RTree structure
 
338
 
 
339
  \return 0 on success
 
340
  \return 1 if data item not found
 
341
*/
 
342
int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
 
343
{
 
344
    union RTree_Child child;
 
345
    
 
346
    assert(r && t && tid > 0);
 
347
 
 
348
    child.id = tid;
 
349
 
 
350
    return t->delete_rect(r, child, t);
 
351
}
 
352
 
 
353
 
 
354
/***********************************
 
355
 *    internally used functions    *
 
356
 ***********************************/ 
 
357
 
 
358
 
 
359
/*
 
360
 * Allocate space for a node in the list used in DeleteRect to
182
361
 * store Nodes that are too empty.
183
362
 */
184
 
static struct ListNode *RTreeNewListNode(void)
 
363
struct RTree_ListNode *RTreeNewListNode(void)
185
364
{
186
 
    return (struct ListNode *)malloc(sizeof(struct ListNode));
187
 
    /* return new ListNode; */
 
365
    return (struct RTree_ListNode *)malloc(sizeof(struct RTree_ListNode));
188
366
}
189
367
 
190
 
static void RTreeFreeListNode(struct ListNode *p)
 
368
void RTreeFreeListNode(struct RTree_ListNode *p)
191
369
{
192
370
    free(p);
193
 
    /* delete(p); */
194
371
}
195
372
 
196
373
/* 
197
374
 * Add a node to the reinsertion list.  All its branches will later
198
375
 * be reinserted into the index structure.
199
376
 */
200
 
static void RTreeReInsert(struct Node *n, struct ListNode **ee)
 
377
void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
201
378
{
202
 
    register struct ListNode *l;
 
379
    struct RTree_ListNode *l = RTreeNewListNode();
203
380
 
204
 
    l = RTreeNewListNode();
205
381
    l->node = n;
206
382
    l->next = *ee;
207
383
    *ee = l;
208
384
}
209
385
 
210
 
/*
211
 
 * Delete a rectangle from non-root part of an index structure.
212
 
 * Called by RTreeDeleteRect.  Descends tree recursively,
213
 
 * merges branches on the way back up.
214
 
 * Returns 1 if record not found, 0 if success.
215
 
 */
216
 
static int
217
 
RTreeDeleteRect2(struct Rect *R, struct Node *Child, struct Node *N,
218
 
                 struct ListNode **Ee)
219
 
{
220
 
    register struct Rect *r = R;
221
 
    register struct Node *child = Child;
222
 
    register struct Node *n = N;
223
 
    register struct ListNode **ee = Ee;
224
 
    register int i;
225
 
 
226
 
    assert(r && n && ee);
227
 
    assert(child);
228
 
    assert(n->level >= 0);
229
 
 
230
 
    if (n->level > 0) {         /* not a leaf node */
231
 
        for (i = 0; i < NODECARD; i++) {
232
 
            if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect))) {
233
 
                if (!RTreeDeleteRect2(r, child, n->branch[i].child, ee)) {
234
 
                    if (n->branch[i].child->count >= MinNodeFill) {
235
 
                        n->branch[i].rect =
236
 
                            RTreeNodeCover(n->branch[i].child);
237
 
                    }
238
 
                    else {
239
 
                        /* not enough entries in child, eliminate child node */
240
 
                        RTreeReInsert(n->branch[i].child, ee);
241
 
                        RTreeDisconnectBranch(n, i);
242
 
                    }
243
 
                    return 0;
244
 
                }
245
 
            }
246
 
        }
247
 
        return 1;
248
 
    }
249
 
    else {                      /* a leaf node */
250
 
 
251
 
        for (i = 0; i < LEAFCARD; i++) {
252
 
            if (n->branch[i].child &&
253
 
                n->branch[i].child == child) {
254
 
                RTreeDisconnectBranch(n, i);
255
 
                return 0;
256
 
            }
257
 
        }
258
 
        return 1;
259
 
    }
260
 
}
261
 
 
262
 
/*
263
 
 * Delete a data rectangle from an index structure.
264
 
 * Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
265
 
 * Returns 1 if record not found, 0 if success.
266
 
 * RTreeDeleteRect provides for eliminating the root.
267
 
 */
268
 
int RTreeDeleteRect(struct Rect *R, int Tid, struct Node **Nn)
269
 
{
270
 
    /* wrapper not really needed, but restricts compile warnings to rtree lib */
271
 
    /* this way it's easier to fix if necessary? */
272
 
    return RTreeDeleteRect1(R, (struct Node *) Tid, Nn);
273
 
}
274
 
 
275
 
int RTreeDeleteRect1(struct Rect *R, struct Node *Child, struct Node **Nn)
276
 
{
277
 
    register struct Rect *r = R;
278
 
    register struct Node *child = Child;
279
 
    register struct Node **nn = Nn;
280
 
    register int i;
281
 
    struct Node *tmp_nptr = NULL;
282
 
    struct ListNode *reInsertList = NULL;
283
 
    register struct ListNode *e;
284
 
 
285
 
    assert(r && nn);
286
 
    assert(*nn);
287
 
    assert(child);
288
 
 
289
 
    if (!RTreeDeleteRect2(r, child, *nn, &reInsertList)) {
290
 
        /* found and deleted a data item */
291
 
 
292
 
        /* reinsert any branches from eliminated nodes */
293
 
        while (reInsertList) {
294
 
            tmp_nptr = reInsertList->node;
295
 
            for (i = 0; i < MAXKIDS(tmp_nptr); i++) {
296
 
                if (tmp_nptr->branch[i].child) {
297
 
                    RTreeInsertRect1(&(tmp_nptr->branch[i].rect),
298
 
                                    tmp_nptr->branch[i].child,
299
 
                                    nn, tmp_nptr->level);
300
 
                }
301
 
            }
302
 
            e = reInsertList;
303
 
            reInsertList = reInsertList->next;
304
 
            RTreeFreeNode(e->node);
305
 
            RTreeFreeListNode(e);
306
 
        }
307
 
 
308
 
        /* check for redundant root (not leaf, 1 child) and eliminate */
309
 
        if ((*nn)->count == 1 && (*nn)->level > 0) {
310
 
            for (i = 0; i < NODECARD; i++) {
311
 
                tmp_nptr = (*nn)->branch[i].child;
312
 
                if (tmp_nptr)
313
 
                    break;
314
 
            }
315
 
            assert(tmp_nptr);
316
 
            RTreeFreeNode(*nn);
317
 
            *nn = tmp_nptr;
318
 
        }
319
 
        return 0;
320
 
    }
321
 
    else {
322
 
        return 1;
323
 
    }
324
 
}
 
386
/* 
 
387
 * Free ListBranch, used by R*-type forced reinsertion
 
388
 */
 
389
void RTreeFreeListBranch(struct RTree_ListBranch *p)
 
390
{
 
391
    RTreeFreeBoundary(&(p->b.rect));
 
392
    free(p);
 
393
}
 
394
 
 
395
 
 
396