1/* vim:set shiftwidth=4 ts=8: */
2
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * http://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: See CVS logs. Details at http://www.graphviz.org/
11 *************************************************************************/
12
13#include <stdlib.h>
14
15#include "index.h"
16#include <stdio.h>
17#include <assert.h>
18#include "logic.h"
19#include "memory.h"
20
21LeafList_t *RTreeNewLeafList(Leaf_t * lp)
22{
23 LeafList_t *llp;
24
25 if ((llp = NEW(LeafList_t))) {
26 llp->leaf = lp;
27 llp->next = 0;
28 }
29 return llp;
30}
31
32LeafList_t *RTreeLeafListAdd(LeafList_t * llp, Leaf_t * lp)
33{
34 LeafList_t *nlp;
35 if (!lp)
36 return llp;
37
38 nlp = RTreeNewLeafList(lp);
39 nlp->next = llp;
40 return nlp;
41}
42
43void RTreeLeafListFree(LeafList_t * llp)
44{
45 LeafList_t *tlp;
46 while (llp->next) {
47 tlp = llp->next;
48 free(llp);
49 llp = tlp;
50 }
51 free(llp);
52 return;
53}
54
55/* Allocate space for a node in the list used in DeletRect to
56 * store Nodes that are too empty.
57 */
58static struct ListNode *RTreeNewListNode(void)
59{
60 return NEW(struct ListNode);
61}
62
63#if UNUSED
64static void RTreeFreeListNode(struct ListNode *p)
65{
66 free(p);
67}
68#endif
69
70/* Add a node to the reinsertion list. All its branches will later
71 * be reinserted into the index structure.
72 */
73static int RTreeReInsert(RTree_t * rtp, Node_t * n, struct ListNode **ee)
74{
75 register struct ListNode *l;
76
77 if (!(l = RTreeNewListNode()))
78 return -1;
79 l->node = n;
80 l->next = *ee;
81 *ee = l;
82 return 0;
83}
84
85RTree_t *RTreeOpen()
86{
87 RTree_t *rtp;
88
89 if ((rtp = NEW(RTree_t)))
90 rtp->root = RTreeNewIndex(rtp);
91 return rtp;
92}
93
94/* Make a new index, empty. Consists of a single node. */
95Node_t *RTreeNewIndex(RTree_t * rtp)
96{
97 Node_t *x;
98 x = RTreeNewNode(rtp);
99 x->level = 0; /* leaf */
100 rtp->LeafCount++;
101 return x;
102}
103
104static int RTreeClose2(RTree_t * rtp, Node_t * n)
105{
106 int i;
107
108 if (n->level > 0) {
109 for (i = 0; i < NODECARD; i++) {
110 if (!n->branch[i].child)
111 continue;
112 if (!RTreeClose2(rtp, n->branch[i].child)) {
113 free(n->branch[i].child);
114 DisconBranch(n, i);
115 rtp->EntryCount--;
116 if (rtp->StatFlag)
117 rtp->ElimCount++;
118 }
119 }
120 } else {
121 for (i = 0; i < NODECARD; i++) {
122 if (!n->branch[i].child)
123 continue;
124 // free(n->branch[i].child);
125 DisconBranch(n, i);
126 rtp->EntryCount--;
127 if (rtp->StatFlag)
128 rtp->ElimCount++;
129 }
130 //free(n);
131 }
132 return 0;
133}
134
135
136int RTreeClose(RTree_t * rtp)
137{
138 RTreeClose2(rtp, rtp->root);
139 free(rtp->root);
140 free(rtp);
141 return 0;
142}
143
144#ifdef RTDEBUG
145/* Print out all the nodes in an index.
146** Prints from root downward.
147*/
148void PrintIndex(Node_t * n)
149{
150 int i;
151 Node_t *nn;
152 assert(n);
153 assert(n->level >= 0);
154
155 if (n->level > 0) {
156 for (i = 0; i < NODECARD; i++) {
157 if ((nn = n->branch[i].child) != NULL)
158 PrintIndex(nn);
159 }
160 }
161
162 PrintNode(n);
163}
164
165/* Print out all the data rectangles in an index.
166*/
167void PrintData(Node_t * n)
168{
169 int i;
170 Node_t *nn;
171 assert(n);
172 assert(n->level >= 0);
173
174 if (n->level == 0)
175 PrintNode(n);
176 else {
177 for (i = 0; i < NODECARD; i++) {
178 if ((nn = n->branch[i].child) != NULL)
179 PrintData(nn);
180 }
181 }
182}
183#endif
184
185/* RTreeSearch in an index tree or subtree for all data retangles that
186** overlap the argument rectangle.
187** Returns the number of qualifying data rects.
188*/
189LeafList_t *RTreeSearch(RTree_t * rtp, Node_t * n, Rect_t * r)
190{
191 register int i;
192 LeafList_t *llp = 0;
193
194 assert(n);
195 assert(n->level >= 0);
196 assert(r);
197
198 rtp->SeTouchCount++;
199
200 if (n->level > 0) { /* this is an internal node in the tree */
201 for (i = 0; i < NODECARD; i++)
202 if (n->branch[i].child && Overlap(r, &n->branch[i].rect)) {
203 LeafList_t *tlp = RTreeSearch(rtp, n->branch[i].child, r);
204 if (llp) {
205 LeafList_t *xlp = llp;
206 while (xlp->next)
207 xlp = xlp->next;
208 xlp->next = tlp;
209 } else
210 llp = tlp;
211 }
212 } else { /* this is a leaf node */
213 for (i = 0; i < NODECARD; i++) {
214 if (n->branch[i].child && Overlap(r, &n->branch[i].rect)) {
215 llp = RTreeLeafListAdd(llp, (Leaf_t *) & n->branch[i]);
216# ifdef RTDEBUG
217 PrintRect(&n->branch[i].rect);
218# endif
219 }
220 }
221 }
222 return llp;
223}
224
225/* Insert a data rectangle into an index structure.
226** RTreeInsert provides for splitting the root;
227** returns 1 if root was split, 0 if it was not.
228** The level argument specifies the number of steps up from the leaf
229** level to insert; e.g. a data rectangle goes in at level = 0.
230** RTreeInsert2 does the recursion.
231*/
232static int RTreeInsert2(RTree_t *, Rect_t *, void *, Node_t *, Node_t **,
233 int);
234/*static int RTreeInsert2(RTree_t*, Rect_t*, int, Node_t*, Node_t**, int); */
235
236int
237RTreeInsert(RTree_t * rtp, Rect_t * r, void *data, Node_t ** n, int level)
238{
239 /* RTreeInsert(RTree_t*rtp, Rect_t*r, int data, Node_t**n, int level) { */
240 register int i;
241 register Node_t *newroot;
242 Node_t *newnode=0;
243 Branch_t b;
244 int result = 0;
245
246
247 assert(r && n);
248 assert(level >= 0 && level <= (*n)->level);
249 for (i = 0; i < NUMDIMS; i++)
250 assert(r->boundary[i] <= r->boundary[NUMDIMS + i]);
251
252# ifdef RTDEBUG
253 fprintf(stderr, "RTreeInsert level=%d\n", level);
254# endif
255
256 if (rtp->StatFlag) {
257 if (rtp->Deleting)
258 rtp->ReInsertCount++;
259 else
260 rtp->InsertCount++;
261 }
262 if (!rtp->Deleting)
263 rtp->RectCount++;
264
265 if (RTreeInsert2(rtp, r, data, *n, &newnode, level)) { /* root was split */
266 if (rtp->StatFlag) {
267 if (rtp->Deleting)
268 rtp->DeTouchCount++;
269 else
270 rtp->InTouchCount++;
271 }
272
273 newroot = RTreeNewNode(rtp); /* grow a new root, make tree taller */
274 rtp->NonLeafCount++;
275 newroot->level = (*n)->level + 1;
276 b.rect = NodeCover(*n);
277 b.child = *n;
278 AddBranch(rtp, &b, newroot, NULL);
279 b.rect = NodeCover(newnode);
280 b.child = newnode;
281 AddBranch(rtp, &b, newroot, NULL);
282 *n = newroot;
283 // rtp->root = newroot;
284 rtp->EntryCount += 2;
285 result = 1;
286 }
287
288 return result;
289}
290
291/* Inserts a new data rectangle into the index structure.
292** Recursively descends tree, propagates splits back up.
293** Returns 0 if node was not split. Old node updated.
294** If node was split, returns 1 and sets the pointer pointed to by
295** new to point to the new node. Old node updated to become one of two.
296** The level argument specifies the number of steps up from the leaf
297** level to insert; e.g. a data rectangle goes in at level = 0.
298*/
299static int
300RTreeInsert2(RTree_t * rtp, Rect_t * r, void *data,
301 Node_t * n, Node_t ** new, int level)
302{
303 /*static int */
304 /* RTreeInsert2(RTree_t*rtp, Rect_t*r,
305 int data, Node_t*n, Node_t**new, int level) {
306 */
307 register int i=0;
308 Branch_t b;
309 Node_t *n2=0;
310
311 assert(r && n && new);
312 assert(level >= 0 && level <= n->level);
313
314 if (rtp->StatFlag) {
315 if (rtp->Deleting)
316 rtp->DeTouchCount++;
317 else
318 rtp->InTouchCount++;
319 }
320
321 /* Still above level for insertion, go down tree recursively */
322 if (n->level > level) {
323 i = PickBranch(r, n);
324 if (!RTreeInsert2(rtp, r, data, n->branch[i].child, &n2, level)) { /* recurse: child was not split */
325 n->branch[i].rect = CombineRect(r, &(n->branch[i].rect));
326 return 0;
327 } else { /* child was split */
328 n->branch[i].rect = NodeCover(n->branch[i].child);
329 b.child = n2;
330 b.rect = NodeCover(n2);
331 rtp->EntryCount++;
332 return AddBranch(rtp, &b, n, new);
333 }
334 } else if (n->level == level) { /* at level for insertion. */
335 /*Add rect, split if necessary */
336 b.rect = *r;
337 b.child = (Node_t *) data;
338 rtp->EntryCount++;
339 return AddBranch(rtp, &b, n, new);
340 } else { /* Not supposed to happen */
341 assert(FALSE);
342 return 0;
343 }
344}
345
346static void FreeListNode(register struct ListNode *p)
347{
348 free(p);
349}
350
351/* Delete a data rectangle from an index structure.
352** Pass in a pointer to a Rect, the data of the record, ptr to ptr to root node.
353** Returns 1 if record not found, 0 if success.
354** RTreeDelete provides for eliminating the root.
355*/
356static int RTreeDelete2(RTree_t *, Rect_t *, void *, Node_t *,
357 ListNode_t **);
358/* static int RTreeDelete2(RTree_t*, Rect_t*, int, Node_t*, ListNode_t**); */
359
360int RTreeDelete(RTree_t * rtp, Rect_t * r, void *data, Node_t ** nn)
361{
362 /* int */
363 /* RTreeDelete(RTree_t*rtp, Rect_t*r, int data, Node_t**nn) { */
364 register int i;
365 register Node_t *t;
366 struct ListNode *reInsertList = NULL;
367 register struct ListNode *e;
368
369 assert(r && nn);
370 assert(*nn);
371 assert(data);
372
373 rtp->Deleting = TRUE;
374
375# ifdef RTDEBUG
376 fprintf(stderr, "RTreeDelete\n");
377# endif
378
379 if (!RTreeDelete2(rtp, r, data, *nn, &reInsertList)) {
380 /* found and deleted a data item */
381 if (rtp->StatFlag)
382 rtp->DeleteCount++;
383 rtp->RectCount--;
384
385 /* reinsert any branches from eliminated nodes */
386 while (reInsertList) {
387 t = reInsertList->node;
388 for (i = 0; i < NODECARD; i++) {
389 if (t->branch[i].child) {
390 RTreeInsert(rtp, &(t->branch[i].rect),
391 /* (int)t->branch[i].child, nn, t->level); */
392 t->branch[i].child, nn, t->level);
393 rtp->EntryCount--;
394 }
395 }
396 e = reInsertList;
397 reInsertList = reInsertList->next;
398 RTreeFreeNode(rtp, e->node);
399 FreeListNode(e);
400 }
401
402 /* check for redundant root (not leaf, 1 child) and eliminate */
403 if ((*nn)->count == 1 && (*nn)->level > 0) {
404 if (rtp->StatFlag)
405 rtp->ElimCount++;
406 rtp->EntryCount--;
407 for (i = 0; i < NODECARD; i++) {
408 if ((t = (*nn)->branch[i].child))
409 break;
410 }
411 RTreeFreeNode(rtp, *nn);
412 *nn = t;
413 }
414 rtp->Deleting = FALSE;
415 return 0;
416 } else {
417 rtp->Deleting = FALSE;
418 return 1;
419 }
420}
421
422/* Delete a rectangle from non-root part of an index structure.
423** Called by RTreeDelete. Descends tree recursively,
424** merges branches on the way back up.
425*/
426static int
427RTreeDelete2(RTree_t * rtp, Rect_t * r, void *data, Node_t * n,
428 ListNode_t ** ee)
429/* static int */
430/* RTreeDelete2(RTree_t*rtp, Rect_t*r, int data, Node_t*n, ListNode_t**ee) */
431{
432 register int i;
433
434 assert(r && n && ee);
435 assert(data);
436 assert(n->level >= 0);
437
438 if (rtp->StatFlag)
439 rtp->DeTouchCount++;
440
441 if (n->level > 0) { /* not a leaf node */
442 for (i = 0; i < NODECARD; i++) {
443 if (n->branch[i].child && Overlap(r, &(n->branch[i].rect))) {
444 if (!RTreeDelete2(rtp, r, data, n->branch[i].child, ee)) { /*recurse */
445 if (n->branch[i].child->count >= rtp->MinFill)
446 n->branch[i].rect = NodeCover(n->branch[i].child);
447 else { /* not enough entries in child, eliminate child node */
448 RTreeReInsert(rtp, n->branch[i].child, ee);
449 DisconBranch(n, i);
450 rtp->EntryCount--;
451 if (rtp->StatFlag)
452 rtp->ElimCount++;
453 }
454 return 0;
455 }
456 }
457 }
458 return 1;
459 } else { /* a leaf node */
460 for (i = 0; i < NODECARD; i++) {
461 if (n->branch[i].child
462 && n->branch[i].child == (Node_t *) data) {
463 DisconBranch(n, i);
464 rtp->EntryCount--;
465 return 0;
466 }
467 }
468 return 1;
469 }
470}
471
472#ifdef UNUSED
473/* Allocate space for a node in the list used in DeletRect to
474** store Nodes that are too empty.
475*/
476struct ListNode *NewListNode()
477{
478 return (struct ListNode *) NEW(sizeof(struct ListNode));
479}
480
481#endif
482