GRASS GIS 8 Programmer's Manual 8.4.1(2025)-45ca3179ab
Loading...
Searching...
No Matches
rbtree.c
Go to the documentation of this file.
1/*!
2 * \file rbtree.c
3 *
4 * \brief binary search tree
5 *
6 * Generic balanced binary search tree (Red Black Tree) implementation
7 *
8 * (C) 2009 by the GRASS Development Team
9 *
10 * This program is free software under the GNU General Public License
11 * (>=v2). Read the file COPYING that comes with GRASS for details.
12 *
13 * \author Original author Julienne Walker 2003, 2008
14 * GRASS implementation Markus Metz, 2009
15 */
16
17/* balanced binary search tree implementation
18 *
19 * this one is a Red Black Tree, no parent pointers, no threads
20 * The core code comes from Julienne Walker's tutorials on binary search trees
21 * original license: public domain
22 * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
23 * some ideas come from libavl (GPL >= 2)
24 *
25 * Red Black Trees are used to maintain a data structure with
26 * search, insertion and deletion in O(log N) time
27 */
28
29#include <assert.h>
30#include <stdlib.h>
31#include <string.h>
32#include <grass/gis.h>
33#include <grass/glocale.h>
34#include <grass/rbtree.h>
35
36/* internal functions */
37static struct RB_NODE *rbtree_single(struct RB_NODE *, int);
38static struct RB_NODE *rbtree_double(struct RB_NODE *, int);
39static void *rbtree_first(struct RB_TRAV *);
40static void *rbtree_last(struct RB_TRAV *trav);
41static void *rbtree_next(struct RB_TRAV *);
42static void *rbtree_previous(struct RB_TRAV *);
43static struct RB_NODE *rbtree_make_node(size_t, void *);
44static int is_red(struct RB_NODE *);
45
46/* create new tree and initialize
47 * returns pointer to new tree, NULL for memory allocation error
48 */
49struct RB_TREE *rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
50{
51 struct RB_TREE *tree = (struct RB_TREE *)malloc(sizeof(struct RB_TREE));
52
53 if (tree == NULL) {
54 G_warning("RB tree: Out of memory!");
55 return NULL;
56 }
57
58 assert(compare);
59
60 tree->datasize = rb_datasize;
61 tree->rb_compare = compare;
62 tree->count = 0;
63 tree->root = NULL;
64
65 return tree;
66}
67
68/* add an item to a tree
69 * non-recursive top-down insertion
70 * the algorithm does not allow duplicates and also does not warn about a
71 * duplicate returns 1 on success, 0 on failure
72 */
73int rbtree_insert(struct RB_TREE *tree, void *data)
74{
75 assert(tree && data);
76
77 if (tree->root == NULL) {
78 /* create a new root node for tree */
79 tree->root = rbtree_make_node(tree->datasize, data);
80 if (tree->root == NULL)
81 return 0;
82 }
83 else {
84 struct RB_NODE head = {0, 0, {0, 0}}; /* False tree root */
85 struct RB_NODE *g, *t; /* Grandparent & parent */
86 struct RB_NODE *p, *q; /* Iterator & parent */
87 int dir = 0, last = 0;
88
89 /* Set up helpers */
90 t = &head;
91 g = p = NULL;
92 q = t->link[1] = tree->root;
93
94 /* Search down the tree */
95 for (;;) {
96 if (q == NULL) {
97 /* Insert new node at the bottom */
98 p->link[dir] = q = rbtree_make_node(tree->datasize, data);
99 if (q == NULL)
100 return 0;
101 }
102 else if (is_red(q->link[0]) && is_red(q->link[1])) {
103 /* Color flip */
104 q->red = 1;
105 q->link[0]->red = 0;
106 q->link[1]->red = 0;
107 }
108
109 /* Fix red violation */
110 if (is_red(q) && is_red(p)) {
111 int dir2 = t->link[1] == g;
112
113 if (q == p->link[last])
114 t->link[dir2] = rbtree_single(g, !last);
115 else
116 t->link[dir2] = rbtree_double(g, !last);
117 }
118
119 last = dir;
120 dir = tree->rb_compare(q->data, data);
121
122 /* Stop if found. This check also disallows duplicates in the tree
123 */
124 if (dir == 0)
125 break;
126
127 dir = dir < 0;
128
129 /* Move the helpers down */
130 if (g != NULL)
131 t = g;
132
133 g = p, p = q;
134 q = q->link[dir];
135 }
136
137 /* Update root */
138 tree->root = head.link[1];
139 }
140
141 /* Make root black */
142 tree->root->red = 0;
143
144 tree->count++;
145
146 return 1;
147}
148
149/* remove an item from a tree that matches given data
150 * non-recursive top-down removal
151 * returns 1 on successful removal
152 * returns 0 if data item was not found
153 */
154int rbtree_remove(struct RB_TREE *tree, const void *data)
155{
156 struct RB_NODE head = {0, 0, {0, 0}}; /* False tree root */
157 struct RB_NODE *q, *p, *g; /* Helpers */
158 struct RB_NODE *f = NULL; /* Found item */
159 int dir = 1, removed = 0;
160
161 assert(tree && data);
162
163 if (tree->root == NULL) {
164 return 0; /* empty tree, nothing to remove */
165 }
166
167 /* Set up helpers */
168 q = &head;
169 g = p = NULL;
170 q->link[1] = tree->root;
171
172 /* Search and push a red down */
173 while (q->link[dir] != NULL) {
174 int last = dir;
175
176 /* Update helpers */
177 g = p, p = q;
178 q = q->link[dir];
179 dir = tree->rb_compare(q->data, data);
180
181 /* Save found node */
182 if (dir == 0)
183 f = q;
184
185 dir = dir < 0;
186
187 /* Push the red node down */
188 if (!is_red(q) && !is_red(q->link[dir])) {
189 if (is_red(q->link[!dir]))
190 p = p->link[last] = rbtree_single(q, dir);
191 else if (!is_red(q->link[!dir])) {
192 struct RB_NODE *s = p->link[!last];
193
194 if (s != NULL) {
195 if (!is_red(s->link[!last]) && !is_red(s->link[last])) {
196 /* Color flip */
197 p->red = 0;
198 s->red = 1;
199 q->red = 1;
200 }
201 else {
202 int dir2 = g->link[1] == p;
203
204 if (is_red(s->link[last]))
205 g->link[dir2] = rbtree_double(p, last);
206 else if (is_red(s->link[!last]))
207 g->link[dir2] = rbtree_single(p, last);
208
209 /* Ensure correct coloring */
210 q->red = g->link[dir2]->red = 1;
211 g->link[dir2]->link[0]->red = 0;
212 g->link[dir2]->link[1]->red = 0;
213 }
214 }
215 }
216 }
217 }
218
219 /* Replace and remove if found */
220 if (f != NULL) {
221 free(f->data);
222 f->data = q->data;
223 p->link[p->link[1] == q] = q->link[q->link[0] == NULL];
224 free(q);
225 q = NULL;
226 tree->count--;
227 removed = 1;
228 }
229 else
230 G_debug(2, "RB tree: data not found in search tree");
231
232 /* Update root and make it black */
233 tree->root = head.link[1];
234 if (tree->root != NULL)
235 tree->root->red = 0;
236
237 return removed;
238}
239
240/* find data item in tree
241 * returns pointer to data item if found else NULL
242 */
243void *rbtree_find(struct RB_TREE *tree, const void *data)
244{
245 struct RB_NODE *curr_node = tree->root;
246 int cmp;
247
248 assert(tree && data);
249
250 while (curr_node != NULL) {
251 cmp = tree->rb_compare(curr_node->data, data);
252 if (cmp == 0)
253 return curr_node->data; /* found */
254
255 curr_node = curr_node->link[cmp < 0];
256 }
257 return NULL;
258}
259
260/* initialize tree traversal
261 * (re-)sets trav structure
262 * returns 0
263 */
264int rbtree_init_trav(struct RB_TRAV *trav, struct RB_TREE *tree)
265{
266 assert(trav && tree);
267
268 trav->tree = tree;
269 trav->curr_node = tree->root;
270 trav->first = 1;
271 trav->top = 0;
272
273 return 0;
274}
275
276/* traverse the tree in ascending order
277 * useful to get all items in the tree non-recursively
278 * struct RB_TRAV *trav needs to be initialized first
279 * returns pointer to data, NULL when finished
280 */
281void *rbtree_traverse(struct RB_TRAV *trav)
282{
283 assert(trav);
284
285 if (trav->curr_node == NULL) {
286 if (trav->first)
287 G_debug(1, "RB tree: empty tree");
288 else
289 G_debug(1, "RB tree: finished traversing");
290
291 return NULL;
292 }
293
294 if (!trav->first)
295 return rbtree_next(trav);
296 else {
297 trav->first = 0;
298 return rbtree_first(trav);
299 }
300}
301
302/* traverse the tree in descending order
303 * useful to get all items in the tree non-recursively
304 * struct RB_TRAV *trav needs to be initialized first
305 * returns pointer to data, NULL when finished
306 */
307void *rbtree_traverse_backwd(struct RB_TRAV *trav)
308{
309 assert(trav);
310
311 if (trav->curr_node == NULL) {
312 if (trav->first)
313 G_debug(1, "RB tree: empty tree");
314 else
315 G_debug(1, "RB tree: finished traversing");
316
317 return NULL;
318 }
319
320 if (!trav->first)
321 return rbtree_previous(trav);
322 else {
323 trav->first = 0;
324 return rbtree_last(trav);
325 }
326}
327
328/* find start point to traverse the tree in ascending order
329 * useful to get a selection of items in the tree
330 * magnitudes faster than traversing the whole tree
331 * may return first item that's smaller or first item that's larger
332 * struct RB_TRAV *trav needs to be initialized first
333 * returns pointer to data, NULL when finished
334 */
335void *rbtree_traverse_start(struct RB_TRAV *trav, const void *data)
336{
337 int dir = 0;
338
339 assert(trav && data);
340
341 if (trav->curr_node == NULL) {
342 if (trav->first)
343 G_warning("RB tree: empty tree");
344 else
345 G_warning("RB tree: finished traversing");
346
347 return NULL;
348 }
349
350 if (!trav->first)
351 return rbtree_next(trav);
352
353 /* else first time, get start node */
354
355 trav->first = 0;
356 trav->top = 0;
357
358 while (trav->curr_node != NULL) {
359 dir = trav->tree->rb_compare(trav->curr_node->data, data);
360 /* exact match, great! */
361 if (dir == 0)
362 return trav->curr_node->data;
363 else {
364 dir = dir < 0;
365 /* end of branch, also reached if
366 * smallest item is larger than search template or
367 * largest item is smaller than search template */
368 if (trav->curr_node->link[dir] == NULL)
369 return trav->curr_node->data;
370
371 trav->up[trav->top++] = trav->curr_node;
372 trav->curr_node = trav->curr_node->link[dir];
373 }
374 }
375
376 return NULL; /* should not happen */
377}
378
379/* two functions needed to fully traverse the tree: initialize and continue
380 * useful to get all items in the tree non-recursively
381 * this one here uses a stack
382 * parent pointers or threads would also be possible
383 * but these would need to be added to RB_NODE
384 * -> more memory needed for standard operations
385 */
386
387/* start traversing the tree
388 * returns pointer to smallest data item
389 */
390static void *rbtree_first(struct RB_TRAV *trav)
391{
392 /* get smallest item */
393 while (trav->curr_node->link[0] != NULL) {
394 trav->up[trav->top++] = trav->curr_node;
395 trav->curr_node = trav->curr_node->link[0];
396 }
397
398 return trav->curr_node->data; /* return smallest item */
399}
400
401/* start traversing the tree
402 * returns pointer to largest data item
403 */
404static void *rbtree_last(struct RB_TRAV *trav)
405{
406 /* get smallest item */
407 while (trav->curr_node->link[1] != NULL) {
408 trav->up[trav->top++] = trav->curr_node;
409 trav->curr_node = trav->curr_node->link[1];
410 }
411
412 return trav->curr_node->data; /* return smallest item */
413}
414
415/* continue traversing the tree in ascending order
416 * returns pointer to data item, NULL when finished
417 */
418void *rbtree_next(struct RB_TRAV *trav)
419{
420 if (trav->curr_node->link[1] != NULL) {
421 /* something on the right side: larger item */
422 trav->up[trav->top++] = trav->curr_node;
423 trav->curr_node = trav->curr_node->link[1];
424
425 /* go down, find smallest item in this branch */
426 while (trav->curr_node->link[0] != NULL) {
427 trav->up[trav->top++] = trav->curr_node;
428 trav->curr_node = trav->curr_node->link[0];
429 }
430 }
431 else {
432 /* at smallest item in this branch, go back up */
433 struct RB_NODE *last;
434
435 do {
436 if (trav->top == 0) {
437 trav->curr_node = NULL;
438 break;
439 }
440 last = trav->curr_node;
441 trav->curr_node = trav->up[--trav->top];
442 } while (last == trav->curr_node->link[1]);
443 }
444
445 if (trav->curr_node != NULL) {
446 return trav->curr_node->data;
447 }
448 else
449 return NULL; /* finished traversing */
450}
451
452/* continue traversing the tree in descending order
453 * returns pointer to data item, NULL when finished
454 */
455void *rbtree_previous(struct RB_TRAV *trav)
456{
457 if (trav->curr_node->link[0] != NULL) {
458 /* something on the left side: smaller item */
459 trav->up[trav->top++] = trav->curr_node;
460 trav->curr_node = trav->curr_node->link[0];
461
462 /* go down, find largest item in this branch */
463 while (trav->curr_node->link[1] != NULL) {
464 trav->up[trav->top++] = trav->curr_node;
465 trav->curr_node = trav->curr_node->link[1];
466 }
467 }
468 else {
469 /* at largest item in this branch, go back up */
470 struct RB_NODE *last;
471
472 do {
473 if (trav->top == 0) {
474 trav->curr_node = NULL;
475 break;
476 }
477 last = trav->curr_node;
478 trav->curr_node = trav->up[--trav->top];
479 } while (last == trav->curr_node->link[0]);
480 }
481
482 if (trav->curr_node != NULL) {
483 return trav->curr_node->data;
484 }
485 else
486 return NULL; /* finished traversing */
487}
488
489/* clear the tree, removing all entries */
490void rbtree_clear(struct RB_TREE *tree)
491{
492 struct RB_NODE *it;
493 struct RB_NODE *save = tree->root;
494
495 /*
496 Rotate away the left links so that
497 we can treat this like the destruction
498 of a linked list
499 */
500 while ((it = save) != NULL) {
501 if (it->link[0] == NULL) {
502 /* No left links, just kill the node and move on */
503 save = it->link[1];
504 free(it->data);
505 it->data = NULL;
506 free(it);
507 it = NULL;
508 }
509 else {
510 /* Rotate away the left link and check again */
511 save = it->link[0];
512 it->link[0] = save->link[1];
513 save->link[1] = it;
514 }
515 }
516 tree->root = NULL;
517}
518
519/* destroy the tree */
520void rbtree_destroy(struct RB_TREE *tree)
521{
522 /* remove all entries */
523 rbtree_clear(tree);
524
525 free(tree);
526 tree = NULL;
527}
528
529/* used for debugging: check for errors in tree structure */
530int rbtree_debug(struct RB_TREE *tree, struct RB_NODE *root)
531{
532 int lh, rh;
533
534 if (root == NULL)
535 return 1;
536 else {
537 struct RB_NODE *ln = root->link[0];
538 struct RB_NODE *rn = root->link[1];
539 int lcmp = 0, rcmp = 0;
540
541 /* Consecutive red links */
542 if (is_red(root)) {
543 if (is_red(ln) || is_red(rn)) {
544 G_warning("Red Black Tree debugging: Red violation");
545 return 0;
546 }
547 }
548
549 lh = rbtree_debug(tree, ln);
550 rh = rbtree_debug(tree, rn);
551
552 if (ln) {
553 lcmp = tree->rb_compare(ln->data, root->data);
554 }
555
556 if (rn) {
557 rcmp = tree->rb_compare(rn->data, root->data);
558 }
559
560 /* Invalid binary search tree:
561 * left node >= parent or right node <= parent */
562 if ((ln != NULL && lcmp > -1) || (rn != NULL && rcmp < 1)) {
563 G_warning("Red Black Tree debugging: Binary tree violation");
564 return 0;
565 }
566
567 /* Black height mismatch */
568 if (lh != 0 && rh != 0 && lh != rh) {
569 G_warning("Red Black Tree debugging: Black violation");
570 return 0;
571 }
572
573 /* Only count black links */
574 if (lh != 0 && rh != 0)
575 return is_red(root) ? lh : lh + 1;
576 else
577 return 0;
578 }
579}
580
581/*******************************************************
582 * *
583 * internal functions for Red Black Tree maintenance *
584 * *
585 *******************************************************/
586
587/* add a new node to the tree */
588static struct RB_NODE *rbtree_make_node(size_t datasize, void *data)
589{
590 struct RB_NODE *new_node = (struct RB_NODE *)malloc(sizeof(*new_node));
591
592 if (new_node == NULL)
593 G_fatal_error("RB Search Tree: Out of memory!");
594
595 new_node->data = malloc(datasize);
596 if (new_node->data == NULL)
597 G_fatal_error("RB Search Tree: Out of memory!");
598
599 memcpy(new_node->data, data, datasize);
600 new_node->red = 1; /* 1 is red, 0 is black */
601 new_node->link[0] = NULL;
602 new_node->link[1] = NULL;
603
604 return new_node;
605}
606
607/* check for red violation */
608static int is_red(struct RB_NODE *root)
609{
610 if (root)
611 return root->red == 1;
612
613 return 0;
614}
615
616/* single rotation */
617static struct RB_NODE *rbtree_single(struct RB_NODE *root, int dir)
618{
619 struct RB_NODE *newroot = root->link[!dir];
620
621 root->link[!dir] = newroot->link[dir];
622 newroot->link[dir] = root;
623
624 root->red = 1;
625 newroot->red = 0;
626
627 return newroot;
628}
629
630/* double rotation */
631static struct RB_NODE *rbtree_double(struct RB_NODE *root, int dir)
632{
633 root->link[!dir] = rbtree_single(root->link[!dir], !dir);
634 return rbtree_single(root, dir);
635}
#define NULL
Definition ccmath.h:32
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition debug.c:66
double t
void G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
Definition gis/error.c:159
void G_warning(const char *msg,...)
Print a warning message to stderr.
Definition gis/error.c:203
#define assert(condition)
Definition lz4.c:393
float g
Definition named_colr.c:7
void * rbtree_find(struct RB_TREE *tree, const void *data)
Definition rbtree.c:243
void rbtree_destroy(struct RB_TREE *tree)
Definition rbtree.c:520
int rbtree_remove(struct RB_TREE *tree, const void *data)
Definition rbtree.c:154
int rbtree_debug(struct RB_TREE *tree, struct RB_NODE *root)
Definition rbtree.c:530
void * rbtree_traverse(struct RB_TRAV *trav)
Definition rbtree.c:281
int rbtree_init_trav(struct RB_TRAV *trav, struct RB_TREE *tree)
Definition rbtree.c:264
void * rbtree_traverse_start(struct RB_TRAV *trav, const void *data)
Definition rbtree.c:335
void rbtree_clear(struct RB_TREE *tree)
Definition rbtree.c:490
void * rbtree_traverse_backwd(struct RB_TRAV *trav)
Definition rbtree.c:307
struct RB_TREE * rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
Definition rbtree.c:49
int rbtree_insert(struct RB_TREE *tree, void *data)
Definition rbtree.c:73