2 Generic C code for red-black trees.
3 Copyright (C) 2000 James S. Plank,
6 This library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 This library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with this library; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 /* Revision 1.2. Jim Plank */
22 /* Original code by Jim Plank (plank@cs.utk.edu) */
23 /* modified for THINK C 6.0 for Macintosh by Chris Bartley */
31 static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il);
32 static Rb_node lprev(Rb_node n);
33 static Rb_node rprev(Rb_node n);
34 static void recolor(Rb_node n);
35 static void single_rotate(Rb_node y, int l);
36 static void rb_print_tree(Rb_node t, int level);
37 static void rb_iprint_tree(Rb_node t, int level);
39 /* Gcc complains if non-char* pointer is passed to printf %p */
40 #define DONT_COMPLAIN (char*)
42 #define isred(n) (n->s.red)
43 #define isblack(n) (!isred(n))
44 #define isleft(n) (n->s.left)
45 #define isright(n) (!isleft(n))
46 #define isint(n) (n->s.internal)
47 #define isext(n) (!isint(n))
48 #define ishead(n) (n->s.head)
49 #define isroot(n) (n->s.root)
50 #define setred(n) n->s.red = 1
51 #define setblack(n) n->s.red = 0
52 #define setleft(n) n->s.left = 1
53 #define setright(n) n->s.left = 0
54 #define sethead(n) n->s.head = 1
55 #define setroot(n) n->s.root = 1
56 #define setint(n) n->s.internal = 1
57 #define setext(n) n->s.internal = 0
58 #define setnormal(n) { n->s.root = 0; n ->s.head = 0; }
59 #define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \
60 : n->p.parent->c.child.left)
62 static void insert(Rb_node item, Rb_node list) /* Inserts to the end of a list */
66 last_node = list->c.list.blink;
68 list->c.list.blink = item;
69 last_node->c.list.flink = item;
70 item->c.list.blink = last_node;
71 item->c.list.flink = list;
74 static void delete_item(Rb_node item) /* Deletes an arbitrary iterm */
76 item->c.list.flink->c.list.blink = item->c.list.blink;
77 item->c.list.blink->c.list.flink = item->c.list.flink;
80 #define mk_new_ext(new, kkkey, vvval) {\
81 new = (Rb_node) malloc(sizeof(struct rb_node));\
82 if(new==NULL) return NULL;\
90 static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il)
94 newnode = (Rb_node) malloc(sizeof(struct rb_node));
98 newnode->c.child.left = l;
99 newnode->c.child.right = r;
100 newnode->p.parent = p;
103 l->p.parent = newnode;
104 r->p.parent = newnode;
112 p->c.child.left = newnode;
115 p->c.child.right = newnode;
121 Rb_node lprev(Rb_node n)
123 if (ishead(n)) return n;
125 if (isright(n)) return n->p.parent;
131 Rb_node rprev(Rb_node n)
133 if (ishead(n)) return n;
135 if (isleft(n)) return n->p.parent;
145 head = (Rb_node) malloc (sizeof(struct rb_node));
147 head->c.list.flink = head;
148 head->c.list.blink = head;
156 Rb_node rb_find_ikey_n(Rb_node n, int ikey, int *fnd)
160 fprintf(stderr, "rb_find_ikey_n called on non-head %p\n",
164 if (n->p.root == n) return n;
165 if (ikey == n->c.list.blink->k.ikey) {
167 return n->c.list.blink;
169 if (ikey > n->c.list.blink->k.ikey) return n;
172 if (isext(n)) return n;
173 if (ikey == n->k.lext->k.ikey) {
177 n = (ikey < n->k.lext->k.ikey) ? n->c.child.left : n->c.child.right;
181 Rb_node rb_find_ikey(Rb_node n, int ikey)
184 return rb_find_ikey_n(n, ikey, &fnd);
187 Rb_node rb_find_gkey_n(Rb_node n, const void *key, Rb_compfn *fxn, int *fnd)
193 fprintf(stderr, "rb_find_gkey_n called on non-head %p\n",
197 if (n->p.root == n) return n;
198 cmp = (*fxn)(key, n->c.list.blink->k.key);
201 return n->c.list.blink;
203 if (cmp > 0) return n;
206 if (isext(n)) return n;
207 cmp = (*fxn)(key, n->k.lext->k.key);
212 if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
216 Rb_node rb_find_gkey(Rb_node n, const void *key, Rb_compfn *fxn)
219 return rb_find_gkey_n(n, key, fxn, &fnd);
222 Rb_node rb_find_key_n(Rb_node n, const char *key, int *fnd)
224 return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, fnd);
227 Rb_node rb_find_key(Rb_node n, const char *key)
230 return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, &fnd);
233 static int ptrcmp(const void *a, const void *b)
235 return (a<b ? -1 : ((a==b) ? 0 : 1));
238 Rb_node rb_find_pkey_n(Rb_node n, const void *key, int *fnd)
240 return rb_find_gkey_n(n, key, ptrcmp, fnd);
243 Rb_node rb_find_pkey(Rb_node n, const void *key)
246 return rb_find_gkey_n(n, key, ptrcmp, &fnd);
249 Rb_node rb_insert_b(Rb_node n, const void *key, void *val)
251 Rb_node newleft, newright, newnode, list, p;
254 if (n->p.root == n) { /* Tree is empty */
255 mk_new_ext(newnode, key, val);
258 newnode->p.parent = n;
262 mk_new_ext(newright, key, val);
264 newleft = newright->c.list.blink;
266 mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft));
268 if (!ishead(p)) p->k.lext = newright;
272 mk_new_ext(newleft, key, val);
275 mk_new_int(newleft, n, n->p.parent, isleft(n));
277 if (!ishead(p)) p->v.rext = newleft;
282 static void recolor(Rb_node n)
295 if (isblack(p)) return;
313 /* p's sibling is black, p is red, gp is black */
315 if ((isleft(n) == 0) == (isleft(p) == 0)) {
316 single_rotate(gp, isleft(n));
320 single_rotate(p, isleft(n));
321 single_rotate(gp, isleft(n));
327 static void single_rotate(Rb_node y, int l)
330 Rb_node x=NULL, yp=NULL;
341 y->c.child.left = x->c.child.right;
342 setleft(y->c.child.left);
343 y->c.child.left->p.parent = y;
344 x->c.child.right = y;
347 x = y->c.child.right;
348 y->c.child.right = x->c.child.left;
349 setright(y->c.child.right);
350 y->c.child.right->p.parent = y;
363 yp->c.child.left = x;
366 yp->c.child.right = x;
372 void rb_delete_node(Rb_node n)
378 fprintf(stderr, "Cannot delete an internal node: %p\n", DONT_COMPLAIN n);
382 fprintf(stderr, "Cannot delete the head of an rb_tree: %p\n", DONT_COMPLAIN n);
385 delete_item(n); /* Delete it from the list */
386 p = n->p.parent; /* The only node */
392 s = sibling(n); /* The only node after deletion */
394 s->p.parent = p->p.parent;
395 s->p.parent->p.root = s;
401 gp = p->p.parent; /* Set parent to sibling */
404 gp->c.child.left = s;
407 gp->c.child.right = s;
414 if (isext(s)) { /* Update proper rext and lext values */
416 if (!ishead(p)) p->v.rext = s;
418 if (!ishead(p)) p->k.lext = s;
419 } else if (isblack(s)) {
420 fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
424 if (!ishead(p)) p->v.rext = s->c.child.left;
426 if (!ishead(p)) p->k.lext = s->c.child.right;
438 while(isblack(p) && isblack(s) && isint(s) &&
439 isblack(s->c.child.left) && isblack(s->c.child.right)) {
442 if (isroot(n)) return;
447 if (isblack(p) && isred(s)) { /* Rotation 2.3b */
448 single_rotate(p, isright(n));
454 { Rb_node x, z; char il;
457 fprintf(stderr, "DELETION ERROR: sibling not internal\n");
462 x = il ? s->c.child.left : s->c.child.right ;
465 if (isred(z)) { /* Rotation 2.3f */
466 single_rotate(p, !il);
468 if (isred(p)) setred(s); else setblack(s);
470 } else if (isblack(x)) { /* Recoloring only (2.3c) */
471 if (isred(s) || isblack(p)) {
472 fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
478 } else if (isred(p)) { /* 2.3d */
479 single_rotate(s, il);
480 single_rotate(p, !il);
485 single_rotate(s, il);
486 single_rotate(p, !il);
494 void rb_print_tree(Rb_node t, int level)
497 if (ishead(t) && t->p.parent == t) {
498 printf("tree %p is empty\n", DONT_COMPLAIN t);
499 } else if (ishead(t)) {
500 printf("Head: %p. Root = %p\n", DONT_COMPLAIN t, DONT_COMPLAIN t->p.root);
501 rb_print_tree(t->p.root, 0);
504 for (i = 0; i < level; i++) putchar(' ');
505 printf("Ext node %p: %c,%c: p=%p, k=%s\n",
506 DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
507 DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->k.key);
509 rb_print_tree(t->c.child.left, level+2);
510 rb_print_tree(t->c.child.right, level+2);
511 for (i = 0; i < level; i++) putchar(' ');
512 printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%s,%s)\n",
513 DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
514 DONT_COMPLAIN t->c.child.left, DONT_COMPLAIN t->c.child.right,
515 DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->k.lext->k.key,
516 DONT_COMPLAIN t->v.rext->k.key);
521 void rb_iprint_tree(Rb_node t, int level)
524 if (ishead(t) && t->p.parent == t) {
525 printf("tree %p is empty\n", DONT_COMPLAIN t);
526 } else if (ishead(t)) {
527 printf("Head: %p. Root = %p, < = %p, > = %p\n",
528 DONT_COMPLAIN t, DONT_COMPLAIN t->p.root,
529 DONT_COMPLAIN t->c.list.blink,
530 DONT_COMPLAIN t->c.list.flink);
531 rb_iprint_tree(t->p.root, 0);
534 for (i = 0; i < level; i++) putchar(' ');
535 printf("Ext node %p: %c,%c: p=%p, <=%p, >=%p k=%d\n",
536 DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
537 DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->c.list.blink,
538 DONT_COMPLAIN t->c.list.flink, t->k.ikey);
540 rb_iprint_tree(t->c.child.left, level+2);
541 rb_iprint_tree(t->c.child.right, level+2);
542 for (i = 0; i < level; i++) putchar(' ');
543 printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%d,%d)\n",
544 DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
545 DONT_COMPLAIN t->c.child.left, DONT_COMPLAIN t->c.child.right,
546 DONT_COMPLAIN t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey);
551 int rb_nblack(Rb_node n)
554 if (ishead(n) || isint(n)) {
555 fprintf(stderr, "ERROR: rb_nblack called on a non-external node %p\n",
561 if (isblack(n)) nb++;
567 int rb_plength(Rb_node n)
570 if (ishead(n) || isint(n)) {
571 fprintf(stderr, "ERROR: rb_plength called on a non-external node %p\n",
583 void rb_free_tree(Rb_node n)
586 fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
590 while(rb_first(n) != rb_nil(n)) {
591 rb_delete_node(rb_first(n));
596 void *rb_val(Rb_node n)
601 Rb_node rb_insert_a(Rb_node nd, const void *key, void *val)
603 return rb_insert_b(nd->c.list.flink, key, val);
606 Rb_node rb_insert(Rb_node tree, const char *key, void *val)
608 return rb_insert_b(rb_find_key(tree, key), key, val);
611 Rb_node rb_inserti(Rb_node tree, int ikey, void *val)
613 return rb_insert_b(rb_find_ikey(tree, ikey), (void *) ikey, val);
616 Rb_node rb_insertg(Rb_node tree, const void *key, void *val, Rb_compfn *func)
618 return rb_insert_b(rb_find_gkey(tree, key, func), key, val);
621 Rb_node rb_insertp(Rb_node tree, const void *key, void *val)
623 return rb_insertg(tree, key, val, ptrcmp);