33#include <grass/glocale.h>
34#include <grass/rbtree.h>
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 *);
49struct RB_TREE *
rbtree_create(rb_compare_fn *compare,
size_t rb_datasize)
51 struct RB_TREE *tree = (
struct RB_TREE *)malloc(
sizeof(
struct RB_TREE));
60 tree->datasize = rb_datasize;
61 tree->rb_compare = compare;
77 if (tree->root ==
NULL) {
79 tree->root = rbtree_make_node(tree->datasize, data);
80 if (tree->root ==
NULL)
84 struct RB_NODE head = {0, 0, {0, 0}};
85 struct RB_NODE *
g, *
t;
86 struct RB_NODE *p, *q;
87 int dir = 0, last = 0;
92 q =
t->link[1] = tree->root;
98 p->link[dir] = q = rbtree_make_node(tree->datasize, data);
102 else if (is_red(q->link[0]) && is_red(q->link[1])) {
110 if (is_red(q) && is_red(p)) {
111 int dir2 =
t->link[1] ==
g;
113 if (q == p->link[last])
114 t->link[dir2] = rbtree_single(
g, !last);
116 t->link[dir2] = rbtree_double(
g, !last);
120 dir = tree->rb_compare(q->data, data);
138 tree->root = head.link[1];
156 struct RB_NODE head = {0, 0, {0, 0}};
157 struct RB_NODE *q, *p, *
g;
158 struct RB_NODE *f =
NULL;
159 int dir = 1, removed = 0;
163 if (tree->root ==
NULL) {
170 q->link[1] = tree->root;
173 while (q->link[dir] !=
NULL) {
179 dir = tree->rb_compare(q->data, data);
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];
195 if (!is_red(s->link[!last]) && !is_red(s->link[last])) {
202 int dir2 =
g->link[1] == p;
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);
210 q->red =
g->link[dir2]->red = 1;
211 g->link[dir2]->link[0]->red = 0;
212 g->link[dir2]->link[1]->red = 0;
223 p->link[p->link[1] == q] = q->link[q->link[0] ==
NULL];
230 G_debug(2,
"RB tree: data not found in search tree");
233 tree->root = head.link[1];
234 if (tree->root !=
NULL)
245 struct RB_NODE *curr_node = tree->root;
250 while (curr_node !=
NULL) {
251 cmp = tree->rb_compare(curr_node->data, data);
253 return curr_node->data;
255 curr_node = curr_node->link[cmp < 0];
269 trav->curr_node = tree->root;
285 if (trav->curr_node ==
NULL) {
287 G_debug(1,
"RB tree: empty tree");
289 G_debug(1,
"RB tree: finished traversing");
295 return rbtree_next(trav);
298 return rbtree_first(trav);
311 if (trav->curr_node ==
NULL) {
313 G_debug(1,
"RB tree: empty tree");
315 G_debug(1,
"RB tree: finished traversing");
321 return rbtree_previous(trav);
324 return rbtree_last(trav);
341 if (trav->curr_node ==
NULL) {
345 G_warning(
"RB tree: finished traversing");
351 return rbtree_next(trav);
358 while (trav->curr_node !=
NULL) {
359 dir = trav->tree->rb_compare(trav->curr_node->data, data);
362 return trav->curr_node->data;
368 if (trav->curr_node->link[dir] ==
NULL)
369 return trav->curr_node->data;
371 trav->up[trav->top++] = trav->curr_node;
372 trav->curr_node = trav->curr_node->link[dir];
390static void *rbtree_first(
struct RB_TRAV *trav)
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];
398 return trav->curr_node->data;
404static void *rbtree_last(
struct RB_TRAV *trav)
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];
412 return trav->curr_node->data;
418void *rbtree_next(
struct RB_TRAV *trav)
420 if (trav->curr_node->link[1] !=
NULL) {
422 trav->up[trav->top++] = trav->curr_node;
423 trav->curr_node = trav->curr_node->link[1];
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];
433 struct RB_NODE *last;
436 if (trav->top == 0) {
437 trav->curr_node =
NULL;
440 last = trav->curr_node;
441 trav->curr_node = trav->up[--trav->top];
442 }
while (last == trav->curr_node->link[1]);
445 if (trav->curr_node !=
NULL) {
446 return trav->curr_node->data;
455void *rbtree_previous(
struct RB_TRAV *trav)
457 if (trav->curr_node->link[0] !=
NULL) {
459 trav->up[trav->top++] = trav->curr_node;
460 trav->curr_node = trav->curr_node->link[0];
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];
470 struct RB_NODE *last;
473 if (trav->top == 0) {
474 trav->curr_node =
NULL;
477 last = trav->curr_node;
478 trav->curr_node = trav->up[--trav->top];
479 }
while (last == trav->curr_node->link[0]);
482 if (trav->curr_node !=
NULL) {
483 return trav->curr_node->data;
493 struct RB_NODE *save = tree->root;
500 while ((it = save) !=
NULL) {
501 if (it->link[0] ==
NULL) {
512 it->link[0] = save->link[1];
537 struct RB_NODE *ln = root->link[0];
538 struct RB_NODE *rn = root->link[1];
539 int lcmp = 0, rcmp = 0;
543 if (is_red(ln) || is_red(rn)) {
544 G_warning(
"Red Black Tree debugging: Red violation");
553 lcmp = tree->rb_compare(ln->data, root->data);
557 rcmp = tree->rb_compare(rn->data, root->data);
562 if ((ln !=
NULL && lcmp > -1) || (rn !=
NULL && rcmp < 1)) {
563 G_warning(
"Red Black Tree debugging: Binary tree violation");
568 if (lh != 0 && rh != 0 && lh != rh) {
569 G_warning(
"Red Black Tree debugging: Black violation");
574 if (lh != 0 && rh != 0)
575 return is_red(root) ? lh : lh + 1;
588static struct RB_NODE *rbtree_make_node(
size_t datasize,
void *data)
590 struct RB_NODE *new_node = (
struct RB_NODE *)malloc(
sizeof(*new_node));
592 if (new_node ==
NULL)
595 new_node->data = malloc(datasize);
596 if (new_node->data ==
NULL)
599 memcpy(new_node->data, data, datasize);
601 new_node->link[0] =
NULL;
602 new_node->link[1] =
NULL;
608static int is_red(
struct RB_NODE *root)
611 return root->red == 1;
617static struct RB_NODE *rbtree_single(
struct RB_NODE *root,
int dir)
619 struct RB_NODE *newroot = root->link[!dir];
621 root->link[!dir] = newroot->link[dir];
622 newroot->link[dir] = root;
631static struct RB_NODE *rbtree_double(
struct RB_NODE *root,
int dir)
633 root->link[!dir] = rbtree_single(root->link[!dir], !dir);
634 return rbtree_single(root, dir);
int G_debug(int level, const char *msg,...)
Print debugging message.
void G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
void G_warning(const char *msg,...)
Print a warning message to stderr.
#define assert(condition)
void * rbtree_find(struct RB_TREE *tree, const void *data)
void rbtree_destroy(struct RB_TREE *tree)
int rbtree_remove(struct RB_TREE *tree, const void *data)
int rbtree_debug(struct RB_TREE *tree, struct RB_NODE *root)
void * rbtree_traverse(struct RB_TRAV *trav)
int rbtree_init_trav(struct RB_TRAV *trav, struct RB_TREE *tree)
void * rbtree_traverse_start(struct RB_TRAV *trav, const void *data)
void rbtree_clear(struct RB_TREE *tree)
void * rbtree_traverse_backwd(struct RB_TRAV *trav)
struct RB_TREE * rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
int rbtree_insert(struct RB_TREE *tree, void *data)