1 static char rcsid[]="$Id: redblack.c,v 1.2 2004/11/10 05:44:00 bdemsky Exp $";
4 Redblack balanced tree algorithm
5 Copyright (C) Damian Ivereigh 2000
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU Lesser General Public License as published by
9 the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See the file COPYING for details.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU Lesser General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 /* Implement the red/black tree structure. It is designed to emulate
23 ** the standard tsearch() stuff. i.e. the calling conventions are
36 /* Uncomment this if you would rather use a raw sbrk to get memory
37 ** (however the memory is never released again (only re-used). Can't
38 ** see any point in using this these days.
40 /* #define USE_SBRK */
42 enum nodecolour { BLACK, RED };
45 struct rbnode *left; /* Left down */
46 struct rbnode *right; /* Right down */
47 struct rbnode *up; /* Up */
48 enum nodecolour colour; /* Node colour */
49 const void *key; /* Pointer to user's key (and data) */
55 /* Dummy (sentinel) node, so that we can make X->left->up = X
56 ** We then use this instead of NULL to mean the top or bottom
57 ** end of the rb tree. It is a black node.
59 struct rbnode rb_null={&rb_null, &rb_null, &rb_null, BLACK, NULL,NULL,NULL,NULL};
60 #define RBNULL (&rb_null)
64 static struct rbnode *rb_alloc();
65 static void rb_free(struct rbnode *);
69 #define rb_alloc() ((struct rbnode *) malloc(sizeof(struct rbnode)))
70 #define rb_free(x) (free(x))
74 static struct rbnode *rb_traverse(const void *, struct rbtree *);
75 static struct rbnode *rb_lookup(const void *low,const void *high, struct rbtree *);
76 static void rb_destroy(struct rbnode *,void (*)(void *));
77 static void rb_left_rotate(struct rbnode **, struct rbnode *);
78 static void rb_right_rotate(struct rbnode **, struct rbnode *);
79 static void rb_delete(struct rbnode **, struct rbnode *);
80 static void rb_delete_fix(struct rbnode **, struct rbnode *);
81 static struct rbnode *rb_successor(const struct rbnode *);
82 static struct rbnode *rb_preccessor(const struct rbnode *);
83 static void rb_walk(const struct rbnode *, void (*)(const void *, const VISIT, const int, void *), void *, int);
84 static RBLIST *rb_openlist(const struct rbnode *);
85 static const void *rb_readlist(RBLIST *);
86 static void rb_closelist(RBLIST *);
89 ** OK here we go, the balanced tree stuff. The algorithm is the
90 ** fairly standard red/black taken from "Introduction to Algorithms"
91 ** by Cormen, Leiserson & Rivest. Maybe one of these days I will
92 ** fully understand all this stuff.
94 ** Basically a red/black balanced tree has the following properties:-
95 ** 1) Every node is either red or black (colour is RED or BLACK)
96 ** 2) A leaf (RBNULL pointer) is considered black
97 ** 3) If a node is red then its children are black
98 ** 4) Every path from a node to a leaf contains the same no
101 ** 3) & 4) above guarantee that the longest path (alternating
102 ** red and black nodes) is only twice as long as the shortest
103 ** path (all black nodes). Thus the tree remains fairly balanced.
107 * Initialise a tree. Identifies the comparison routine and any config
108 * data that must be sent to it when called.
109 * Returns a pointer to the top of the tree.
111 struct rbtree * rbinit() {
112 struct rbtree *retval;
115 c=rcsid[0]; /* This does nothing but shutup the -Wall */
117 if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
120 retval->rb_root=RBNULL;
125 void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
129 if (rbinfo->rb_root!=RBNULL)
130 rb_destroy(rbinfo->rb_root,free_function);
135 const void * rbdelete(const void *key, struct rbtree *rbinfo) {
142 x=rb_traverse(key, rbinfo);
144 if (x==NULL||x==RBNULL) {
148 rb_delete(&rbinfo->rb_root, x);
154 void rbwalk(const struct rbtree *rbinfo, void (*action)(const void *, const VISIT, const int, void *), void *arg) {
158 rb_walk(rbinfo->rb_root, action, arg, 0);
161 RBLIST * rbopenlist(const struct rbtree *rbinfo) {
165 return(rb_openlist(rbinfo->rb_root));
168 const void * rbreadlist(RBLIST *rblistp) {
172 return(rb_readlist(rblistp));
175 void rbcloselist(RBLIST *rblistp) {
179 rb_closelist(rblistp);
182 void * rblookup(const void *low,const void *high, struct rbtree *rbinfo) {
185 /* If we have a NULL root (empty tree) then just return NULL */
186 if (rbinfo==NULL || rbinfo->rb_root==NULL)
189 x=rb_lookup(low, high, rbinfo);
191 return((x==RBNULL) ? NULL : x->object);
194 struct pair rbfind(const void *low,const void *high, struct rbtree *rbinfo) {
197 /* If we have a NULL root (empty tree) then just return NULL */
201 if (rbinfo==NULL || rbinfo->rb_root==NULL)
204 x=rb_lookup(low, high, rbinfo);
213 /* --------------------------------------------------------------------- */
215 /* Search for and if not found and insert is true, will add a new
216 ** node in. Returns a pointer to the new node, or the node found
218 int rbinsert(const void *key, const void * high, void *object,struct rbtree *rbinfo) {
219 struct rbnode *x,*y,*z, *tmp;
223 y=RBNULL; /* points to the parent of x */
226 /* walk x down the tree */
227 while(x!=RBNULL && found==0) {
229 /* printf("key=%s, x->key=%s\n", key, x->key); */
242 if ((z=rb_alloc())==NULL) {
243 /* Whoops, no memory */
274 /* colour this new node red */
277 /* Having added a red node, we must now walk back up the tree balancing
278 ** it, by a series of rotations and changing of colours
282 /* While we are not at the top and our parent node is red
283 ** N.B. Since the root node is garanteed black, then we
284 ** are also going to stop if we are the child of the root
287 while(x != rbinfo->rb_root && (x->up->colour == RED)) {
288 /* if our parent is on the left side of our grandparent */
289 if (x->up == x->up->up->left) {
290 /* get the right side of our grandparent (uncle?) */
292 if (y->colour == RED) {
293 /* make our parent black */
294 x->up->colour = BLACK;
295 /* make our uncle black */
297 /* make our grandparent red */
298 x->up->up->colour = RED;
300 /* now consider our grandparent */
303 /* if we are on the right side of our parent */
304 if (x == x->up->right) {
305 /* Move up to our parent */
307 rb_left_rotate(&rbinfo->rb_root, x);
310 /* make our parent black */
311 x->up->colour = BLACK;
312 /* make our grandparent red */
313 x->up->up->colour = RED;
314 /* right rotate our grandparent */
315 rb_right_rotate(&rbinfo->rb_root, x->up->up);
318 /* everything here is the same as above, but
319 ** exchanging left for right
323 if (y->colour == RED) {
324 x->up->colour = BLACK;
326 x->up->up->colour = RED;
330 if (x == x->up->left) {
332 rb_right_rotate(&rbinfo->rb_root, x);
335 x->up->colour = BLACK;
336 x->up->up->colour = RED;
337 rb_left_rotate(&rbinfo->rb_root, x->up->up);
342 /* Set the root node black */
343 (rbinfo->rb_root)->colour = BLACK;
348 /* Search for and if not found and insert is true, will add a new
349 ** node in. Returns a pointer to the new node, or the node found
351 static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
352 struct rbnode *x,*y,*z;
355 y=RBNULL; /* points to the parent of x */
358 /* walk x down the tree */
359 while(x!=RBNULL && found==0) {
374 /* Search for a key according (see redblack.h)
376 static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
381 /* walk x down the tree */
386 if (x->left!=RBNULL && x->left->max>low)
395 /* Search for a key according (see redblack.h)
397 int rbsearch(const void *low, const void *high, struct rbtree *rbinfo) {
404 /* walk x down the tree */
409 if (x->left!=RBNULL && x->left->max>low)
419 * Destroy all the elements blow us in the tree
420 * only useful as part of a complete tree destroy.
422 static void rb_destroy(struct rbnode *x,void (*free_function)(void *)) {
425 rb_destroy(x->left,free_function);
426 if (x->right!=RBNULL)
427 rb_destroy(x->right,free_function);
428 if (free_function!=NULL)
429 free_function(x->object);
435 ** Rotate our tree thus:-
437 ** X rb_left_rotate(X)---> Y
439 ** A Y <---rb_right_rotate(Y) X C
443 ** N.B. This does not change the ordering.
445 ** We assume that neither X or Y is NULL
448 static void rb_left_rotate(struct rbnode **rootp, struct rbnode *x) {
452 assert(x->right!=RBNULL);
454 y=x->right; /* set Y */
456 /* Turn Y's left subtree into X's right subtree (move B)*/
459 /* If B is not null, set it's parent to be X */
460 if (y->left != RBNULL)
463 /* Set Y's parent to be what X's parent was */
466 /* if X was the root */
467 if (x->up == RBNULL) {
470 /* Set X's parent's left or right pointer to be Y */
471 if (x == x->up->left) {
478 /* Put X on Y's left */
481 /* Set X's parent to be Y */
484 y->max=x->max; /* compute Y's max */
490 if (x->right!=RBNULL&&
498 static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
503 assert(y->left!=RBNULL);
505 x=y->left; /* set X */
507 /* Turn X's right subtree into Y's left subtree (move B) */
510 /* If B is not null, set it's parent to be Y */
511 if (x->right != RBNULL)
514 /* Set X's parent to be what Y's parent was */
517 /* if Y was the root */
518 if (y->up == RBNULL) {
521 /* Set Y's parent's left or right pointer to be X */
522 if (y == y->up->left) {
529 /* Put Y on X's right */
532 /* Set Y's parent to be X */
535 x->max=y->max; /* compute Y's max */
541 if (y->right!=RBNULL&&
549 /* Return a pointer to the smallest key greater than x
551 static struct rbnode * rb_successor(const struct rbnode *x) {
554 if (x->right!=RBNULL) {
555 /* If right is not NULL then go right one and
556 ** then keep going left until we find a node with
559 for (y=x->right; y->left!=RBNULL; y=y->left);
561 /* Go up the tree until we get to a node that is on the
562 ** left of its parent (or the root) and then return the
566 while(y!=RBNULL && x==y->right) {
574 /* Return a pointer to the largest key smaller than x
576 static struct rbnode * rb_preccessor(const struct rbnode *x) {
579 if (x->left!=RBNULL) {
580 /* If left is not NULL then go left one and
581 ** then keep going right until we find a node with
584 for (y=x->left; y->right!=RBNULL; y=y->right);
586 /* Go up the tree until we get to a node that is on the
587 ** right of its parent (or the root) and then return the
591 while(y!=RBNULL && x==y->left) {
599 /* Delete the node z, and free up the space
601 static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
602 struct rbnode *x, *y, *tmp;
605 if (z->left == RBNULL || z->right == RBNULL)
610 if (y->left != RBNULL)
617 if (y->up == RBNULL) {
634 if (tmp->left!=RBNULL)
636 if (tmp->right!=RBNULL&&
644 if (y->colour == BLACK)
645 rb_delete_fix(rootp, x);
650 /* Restore the reb-black properties after a delete */
651 static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
654 while (x!=*rootp && x->colour==BLACK) {
655 if (x==x->up->left) {
657 if (w->colour==RED) {
660 rb_left_rotate(rootp, x->up);
663 if (w->left->colour==BLACK && w->right->colour==BLACK) {
667 if (w->right->colour == BLACK) {
668 w->left->colour=BLACK;
670 rb_right_rotate(rootp, w);
673 w->colour=x->up->colour;
674 x->up->colour = BLACK;
675 w->right->colour = BLACK;
676 rb_left_rotate(rootp, x->up);
681 if (w->colour==RED) {
684 rb_right_rotate(rootp, x->up);
687 if (w->right->colour==BLACK && w->left->colour==BLACK) {
691 if (w->left->colour == BLACK) {
692 w->right->colour=BLACK;
694 rb_left_rotate(rootp, w);
697 w->colour=x->up->colour;
698 x->up->colour = BLACK;
699 w->left->colour = BLACK;
700 rb_right_rotate(rootp, x->up);
710 rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
714 if (x->left==RBNULL && x->right==RBNULL) {
716 (*action)(x->key, leaf, level, arg);
718 (*action)(x->key, preorder, level, arg);
720 rb_walk(x->left, action, arg, level+1);
722 (*action)(x->key, postorder, level, arg);
724 rb_walk(x->right, action, arg, level+1);
726 (*action)(x->key, endorder, level, arg);
730 static RBLIST * rb_openlist(const struct rbnode *rootp) {
733 rblistp=(RBLIST *) malloc(sizeof(RBLIST));
737 rblistp->rootp=rootp;
738 rblistp->nextp=rootp;
741 while(rblistp->nextp->left!=RBNULL) {
742 rblistp->nextp=rblistp->nextp->left;
749 static const void * rb_readlist(RBLIST *rblistp) {
750 const void *key=NULL;
752 if (rblistp!=NULL && rblistp->nextp!=RBNULL) {
753 key=rblistp->nextp->key;
754 rblistp->nextp=rb_successor(rblistp->nextp);
760 static void rb_closelist(RBLIST *rblistp) {
765 #if defined(USE_SBRK)
766 /* Allocate space for our nodes, allowing us to get space from
767 ** sbrk in larger chucks.
769 static struct rbnode *rbfreep=NULL;
771 #define RBNODEALLOC_CHUNK_SIZE 1000
772 static struct rbnode * rb_alloc() {
777 /* must grab some more space */
778 rbfreep=(struct rbnode *) sbrk(sizeof(struct rbnode) * RBNODEALLOC_CHUNK_SIZE);
780 if (rbfreep==(struct rbnode *) -1) {
784 /* tie them together in a linked list (use the up pointer) */
785 for (i=0, x=rbfreep; i<RBNODEALLOC_CHUNK_SIZE-1; i++, x++) {
792 rbfreep = rbfreep->up;
796 /* free (dealloc) an rbnode structure - add it onto the front of the list
797 ** N.B. rbnode need not have been allocated through rb_alloc()
799 static void rb_free(struct rbnode *x) {
807 int rb_check(struct rbnode *rootp) {
808 if (rootp==NULL || rootp==RBNULL)
811 if (rootp->up!=RBNULL) {
812 fprintf(stderr, "Root up pointer not RBNULL");
817 if (rb_check1(rootp)) {
822 if (count_black(rootp)==-1)
832 rb_check1(struct rbnode *x)
834 if (x->left==NULL || x->right==NULL)
836 fprintf(stderr, "Left or right is NULL");
842 if (x->left->colour!=BLACK && x->right->colour!=BLACK)
844 fprintf(stderr, "Children of red node not both black, x=%ld", x);
849 if (x->left != RBNULL)
851 if (x->left->up != x)
853 fprintf(stderr, "x->left->up != x, x=%ld", x);
857 if (rb_check1(x->left))
861 if (x->right != RBNULL)
863 if (x->right->up != x)
865 fprintf(stderr, "x->right->up != x, x=%ld", x);
869 if (rb_check1(x->right))
875 count_black(struct rbnode *x)
882 nleft=count_black(x->left);
883 nright=count_black(x->right);
885 if (nleft==-1 || nright==-1)
890 fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
894 if (x->colour == BLACK)
902 dumptree(struct rbnode *x, int n)
906 if (x!=NULL && x!=RBNULL)
909 fprintf(stderr, "Tree: %*s %ld: left=%ld, right=%ld, colour=%s, key=%s",
915 (x->colour==BLACK) ? "BLACK" : "RED",
918 dumptree(x->left, n);
919 dumptree(x->right, n);
925 * $Log: redblack.c,v $
926 * Revision 1.2 2004/11/10 05:44:00 bdemsky
929 * 1) Fixed some bugs in the redblack tree implementation...removing a non-present node resulted in a segfault.
931 * 2) Fixed bug in constructbindings method.
933 * Revision 1.1 2004/10/28 19:28:59 bdemsky
934 * Checking in C runtime.
936 * Revision 1.2 2004/03/10 06:15:03 bdemsky
940 * Concrete Interference rule that falsify a rule that quantifies over a set can't
941 * remove the last element of the set.
943 * Concrete Interference rule that updates that definitely falsify a rule can't modify
944 * the inclusion condition causing a possible addition.
946 * Intelligence in the GraphAnalysis package that computes must & cant remove sets.
947 * Search through only unique combinations.
949 * Revision 1.1 2004/03/07 22:02:43 bdemsky
952 * Still buggy, but getting closer...
954 * Revision 1.3 2003/06/18 06:06:18 bdemsky
957 * Added option to pass in function to free items in the redblack interval tree.
959 * Revision 1.5 2002/01/30 07:54:53 damo
960 * Fixed up the libtool versioning stuff (finally)
961 * Fixed bug 500600 (not detecting a NULL return from malloc)
962 * Fixed bug 509485 (no longer needs search.h)
963 * Cleaned up debugging section
964 * Allow multiple inclusions of redblack.h
965 * Thanks to Matthias Andree for reporting (and fixing) these
967 * Revision 1.4 2000/06/06 14:43:43 damo
968 * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
969 * Added two new examples
971 * Revision 1.3 2000/05/24 06:45:27 damo
972 * Converted everything over to using const
973 * Added a new example1.c file to demonstrate the worst case scenario
974 * Minor fixups of the spec file
976 * Revision 1.2 2000/05/24 06:17:10 damo
977 * Fixed up the License (now the LGPL)
979 * Revision 1.1 2000/05/24 04:15:53 damo
980 * Initial import of files. Versions are now all over the place. Oh well