GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
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 */
37 static struct RB_NODE *rbtree_single(struct RB_NODE *, int);
38 static struct RB_NODE *rbtree_double(struct RB_NODE *, int);
39 static void *rbtree_first(struct RB_TRAV *);
40 static void *rbtree_last(struct RB_TRAV *trav);
41 static void *rbtree_next(struct RB_TRAV *);
42 static void *rbtree_previous(struct RB_TRAV *);
43 static struct RB_NODE *rbtree_make_node(size_t, void *);
44 static int is_red(struct RB_NODE *);
45 
46 
47 /* create new tree and initialize
48  * returns pointer to new tree, NULL for memory allocation error
49  */
50 struct RB_TREE *rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
51 {
52  struct RB_TREE *tree = (struct RB_TREE *)malloc(sizeof(struct RB_TREE));
53 
54  if (tree == NULL) {
55  G_warning("RB tree: Out of memory!");
56  return NULL;
57  }
58 
59  assert(compare);
60 
61  tree->datasize = rb_datasize;
62  tree->rb_compare = compare;
63  tree->count = 0;
64  tree->root = NULL;
65 
66  return tree;
67 }
68 
69 /* add an item to a tree
70  * non-recursive top-down insertion
71  * the algorithm does not allow duplicates and also does not warn about a duplicate
72  * returns 1 on success, 0 on failure
73  */
74 int rbtree_insert(struct RB_TREE *tree, void *data)
75 {
76  assert(tree && data);
77 
78  if (tree->root == NULL) {
79  /* create a new root node for tree */
80  tree->root = rbtree_make_node(tree->datasize, data);
81  if (tree->root == NULL)
82  return 0;
83  }
84  else {
85  struct RB_NODE head = { 0, 0, {0, 0} }; /* False tree root */
86  struct RB_NODE *g, *t; /* Grandparent & parent */
87  struct RB_NODE *p, *q; /* Iterator & parent */
88  int dir = 0, last = 0;
89 
90  /* Set up helpers */
91  t = &head;
92  g = p = NULL;
93  q = t->link[1] = tree->root;
94 
95  /* Search down the tree */
96  for (;;) {
97  if (q == NULL) {
98  /* Insert new node at the bottom */
99  p->link[dir] = q = rbtree_make_node(tree->datasize, data);
100  if (q == NULL)
101  return 0;
102  }
103  else if (is_red(q->link[0]) && is_red(q->link[1])) {
104  /* Color flip */
105  q->red = 1;
106  q->link[0]->red = 0;
107  q->link[1]->red = 0;
108  }
109 
110  /* Fix red violation */
111  if (is_red(q) && is_red(p)) {
112  int dir2 = t->link[1] == g;
113 
114  if (q == p->link[last])
115  t->link[dir2] = rbtree_single(g, !last);
116  else
117  t->link[dir2] = rbtree_double(g, !last);
118  }
119 
120  last = dir;
121  dir = tree->rb_compare(q->data, data);
122 
123  /* Stop if found. This check also disallows duplicates in the tree */
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  */
154 int 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  */
243 void *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  */
264 int 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  */
281 void *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  */
307 void *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  */
335 void *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  */
390 static 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  */
404 static 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  */
418 void *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  */
455 void *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 */
490 void 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 */
520 void 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 */
530 int 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)
563  || (rn != NULL && rcmp < 1)) {
564  G_warning("Red Black Tree debugging: Binary tree violation");
565  return 0;
566  }
567 
568  /* Black height mismatch */
569  if (lh != 0 && rh != 0 && lh != rh) {
570  G_warning("Red Black Tree debugging: Black violation");
571  return 0;
572  }
573 
574  /* Only count black links */
575  if (lh != 0 && rh != 0)
576  return is_red(root) ? lh : lh + 1;
577  else
578  return 0;
579  }
580 }
581 
582 /*******************************************************
583  * *
584  * internal functions for Red Black Tree maintenance *
585  * *
586  *******************************************************/
587 
588 /* add a new node to the tree */
589 static struct RB_NODE *rbtree_make_node(size_t datasize, void *data)
590 {
591  struct RB_NODE *new_node = (struct RB_NODE *)malloc(sizeof(*new_node));
592 
593  if (new_node == NULL)
594  G_fatal_error("RB Search Tree: Out of memory!");
595 
596  new_node->data = malloc(datasize);
597  if (new_node->data == NULL)
598  G_fatal_error("RB Search Tree: Out of memory!");
599 
600  memcpy(new_node->data, data, datasize);
601  new_node->red = 1; /* 1 is red, 0 is black */
602  new_node->link[0] = NULL;
603  new_node->link[1] = NULL;
604 
605  return new_node;
606 }
607 
608 /* check for red violation */
609 static int is_red(struct RB_NODE *root)
610 {
611  if (root)
612  return root->red == 1;
613 
614  return 0;
615 }
616 
617 /* single rotation */
618 static struct RB_NODE *rbtree_single(struct RB_NODE *root, int dir)
619 {
620  struct RB_NODE *newroot = root->link[!dir];
621 
622  root->link[!dir] = newroot->link[dir];
623  newroot->link[dir] = root;
624 
625  root->red = 1;
626  newroot->red = 0;
627 
628  return newroot;
629 }
630 
631 /* double rotation */
632 static struct RB_NODE *rbtree_double(struct RB_NODE *root, int dir)
633 {
634  root->link[!dir] = rbtree_single(root->link[!dir], !dir);
635  return rbtree_single(root, dir);
636 }
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
Definition: rbtree.h:78
void * rbtree_find(struct RB_TREE *tree, const void *data)
Definition: rbtree.c:243
int first
Definition: rbtree.h:99
void * rbtree_traverse_backwd(struct RB_TRAV *trav)
Definition: rbtree.c:307
void rbtree_clear(struct RB_TREE *tree)
Definition: rbtree.c:490
rb_compare_fn * rb_compare
Definition: rbtree.h:90
int top
Definition: rbtree.h:98
void rbtree_destroy(struct RB_TREE *tree)
Definition: rbtree.c:520
struct RB_TREE * rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
Definition: rbtree.c:50
Definition: rbtree.h:93
void free(void *)
#define NULL
Definition: ccmath.h:32
struct RB_TREE * tree
Definition: rbtree.h:95
Definition: rbtree.h:85
int rbtree_remove(struct RB_TREE *tree, const void *data)
Definition: rbtree.c:154
void * malloc(YYSIZE_T)
double t
Definition: r_raster.c:39
size_t count
Definition: rbtree.h:89
struct RB_NODE * link[2]
Definition: rbtree.h:82
#define assert(condition)
Definition: lz4.c:324
float g
Definition: named_colr.c:8
int rbtree_debug(struct RB_TREE *tree, struct RB_NODE *root)
Definition: rbtree.c:530
unsigned char red
Definition: rbtree.h:80
void * rbtree_traverse(struct RB_TRAV *trav)
Definition: rbtree.c:281
struct RB_NODE * curr_node
Definition: rbtree.h:96
size_t datasize
Definition: rbtree.h:88
void G_warning(const char *,...) __attribute__((format(printf
int compare(const void *a, const void *b)
Definition: dgraph.c:177
int rbtree_init_trav(struct RB_TRAV *trav, struct RB_TREE *tree)
Definition: rbtree.c:264
int rb_compare_fn(const void *rb_a, const void *rb_b)
Definition: rbtree.h:76
int rbtree_insert(struct RB_TREE *tree, void *data)
Definition: rbtree.c:74
struct RB_NODE * up[RBTREE_MAX_HEIGHT]
Definition: rbtree.h:97
int G_debug(int, const char *,...) __attribute__((format(printf
void * rbtree_traverse_start(struct RB_TRAV *trav, const void *data)
Definition: rbtree.c:335
void * data
Definition: rbtree.h:81
struct RB_NODE * root
Definition: rbtree.h:87