1 static char rcsid[]="$Id: redblack.c,v 1.1 2004/05/06 21:16:22 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
31 //#include "dmalloc.h"
37 /* Uncomment this if you would rather use a raw sbrk to get memory
38 ** (however the memory is never released again (only re-used). Can't
39 ** see any point in using this these days.
41 /* #define USE_SBRK */
43 enum nodecolour { BLACK, RED };
46 struct rbnode *left; /* Left down */
47 struct rbnode *right; /* Right down */
48 struct rbnode *up; /* Up */
49 enum nodecolour colour; /* Node colour */
50 const void *key; /* Pointer to user's key (and data) */
56 /* Dummy (sentinel) node, so that we can make X->left->up = X
57 ** We then use this instead of NULL to mean the top or bottom
58 ** end of the rb tree. It is a black node.
60 struct rbnode rb_null={&rb_null, &rb_null, &rb_null, BLACK, NULL,NULL,NULL,NULL};
61 #define RBNULL (&rb_null)
65 static struct rbnode *rb_alloc();
66 static void rb_free(struct rbnode *);
70 #define rb_alloc() ((struct rbnode *) malloc(sizeof(struct rbnode)))
71 #define rb_free(x) (free(x))
75 static struct rbnode *rb_traverse(const void *, struct rbtree *);
76 static struct rbnode *rb_lookup(const void *low,const void *high, struct rbtree *);
77 static void rb_destroy(struct rbnode *,void (*)(void *));
78 static void rb_left_rotate(struct rbnode **, struct rbnode *);
79 static void rb_right_rotate(struct rbnode **, struct rbnode *);
80 static void rb_delete(struct rbnode **, struct rbnode *);
81 static void rb_delete_fix(struct rbnode **, struct rbnode *);
82 static struct rbnode *rb_successor(const struct rbnode *);
83 static struct rbnode *rb_preccessor(const struct rbnode *);
84 static void rb_walk(const struct rbnode *, void (*)(const void *, const VISIT, const int, void *), void *, int);
85 static RBLIST *rb_openlist(const struct rbnode *);
86 static const void *rb_readlist(RBLIST *);
87 static void rb_closelist(RBLIST *);
90 ** OK here we go, the balanced tree stuff. The algorithm is the
91 ** fairly standard red/black taken from "Introduction to Algorithms"
92 ** by Cormen, Leiserson & Rivest. Maybe one of these days I will
93 ** fully understand all this stuff.
95 ** Basically a red/black balanced tree has the following properties:-
96 ** 1) Every node is either red or black (colour is RED or BLACK)
97 ** 2) A leaf (RBNULL pointer) is considered black
98 ** 3) If a node is red then its children are black
99 ** 4) Every path from a node to a leaf contains the same no
102 ** 3) & 4) above guarantee that the longest path (alternating
103 ** red and black nodes) is only twice as long as the shortest
104 ** path (all black nodes). Thus the tree remains fairly balanced.
108 * Initialise a tree. Identifies the comparison routine and any config
109 * data that must be sent to it when called.
110 * Returns a pointer to the top of the tree.
112 struct rbtree * rbinit() {
113 struct rbtree *retval;
116 c=rcsid[0]; /* This does nothing but shutup the -Wall */
118 if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
121 retval->rb_root=RBNULL;
126 void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
130 if (rbinfo->rb_root!=RBNULL)
131 rb_destroy(rbinfo->rb_root,free_function);
136 const void * rbdelete(const void *key, struct rbtree *rbinfo) {
143 x=rb_traverse(key, rbinfo);
149 rb_delete(&rbinfo->rb_root, x);
155 void rbwalk(const struct rbtree *rbinfo, void (*action)(const void *, const VISIT, const int, void *), void *arg) {
159 rb_walk(rbinfo->rb_root, action, arg, 0);
162 RBLIST * rbopenlist(const struct rbtree *rbinfo) {
166 return(rb_openlist(rbinfo->rb_root));
169 const void * rbreadlist(RBLIST *rblistp) {
173 return(rb_readlist(rblistp));
176 void rbcloselist(RBLIST *rblistp) {
180 rb_closelist(rblistp);
184 * finds an overlapping region with low->high and returns the object associated with
187 void * rblookup(const void *low,const void *high, struct rbtree *rbinfo) {
190 /* If we have a NULL root (empty tree) then just return NULL */
191 if (rbinfo==NULL || rbinfo->rb_root==NULL)
194 x=rb_lookup(low, high, rbinfo);
196 return((x==RBNULL) ? NULL : x->object);
200 * finds an overlapping region with low->high and returns the pair <low, high>
202 struct pair rbfind(const void *low,const void *high, struct rbtree *rbinfo) {
205 /* If we have a NULL root (empty tree) then just return NULL */
209 if (rbinfo==NULL || rbinfo->rb_root==NULL)
212 x=rb_lookup(low, high, rbinfo);
221 /* --------------------------------------------------------------------- */
223 /* Search for and if not found and insert is true, will add a new
224 ** node in. Returns a pointer to the new node, or the node found
226 int rbinsert(const void *key, const void * high, void *object,struct rbtree *rbinfo) {
227 struct rbnode *x,*y,*z, *tmp;
231 y=RBNULL; /* points to the parent of x */
234 /* walk x down the tree */
235 while(x!=RBNULL && found==0) {
237 /* printf("key=%s, x->key=%s\n", key, x->key); */
250 if ((z=rb_alloc())==NULL) {
251 /* Whoops, no memory */
282 /* colour this new node red */
285 /* Having added a red node, we must now walk back up the tree balancing
286 ** it, by a series of rotations and changing of colours
290 /* While we are not at the top and our parent node is red
291 ** N.B. Since the root node is garanteed black, then we
292 ** are also going to stop if we are the child of the root
295 while(x != rbinfo->rb_root && (x->up->colour == RED)) {
296 /* if our parent is on the left side of our grandparent */
297 if (x->up == x->up->up->left) {
298 /* get the right side of our grandparent (uncle?) */
300 if (y->colour == RED) {
301 /* make our parent black */
302 x->up->colour = BLACK;
303 /* make our uncle black */
305 /* make our grandparent red */
306 x->up->up->colour = RED;
308 /* now consider our grandparent */
311 /* if we are on the right side of our parent */
312 if (x == x->up->right) {
313 /* Move up to our parent */
315 rb_left_rotate(&rbinfo->rb_root, x);
318 /* make our parent black */
319 x->up->colour = BLACK;
320 /* make our grandparent red */
321 x->up->up->colour = RED;
322 /* right rotate our grandparent */
323 rb_right_rotate(&rbinfo->rb_root, x->up->up);
326 /* everything here is the same as above, but
327 ** exchanging left for right
331 if (y->colour == RED) {
332 x->up->colour = BLACK;
334 x->up->up->colour = RED;
338 if (x == x->up->left) {
340 rb_right_rotate(&rbinfo->rb_root, x);
343 x->up->colour = BLACK;
344 x->up->up->colour = RED;
345 rb_left_rotate(&rbinfo->rb_root, x->up->up);
350 /* Set the root node black */
351 (rbinfo->rb_root)->colour = BLACK;
356 /* Search for and if not found and insert is true, will add a new
357 ** node in. Returns a pointer to the new node, or the node found
359 static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
360 struct rbnode *x,*y,*z;
363 y=RBNULL; /* points to the parent of x */
366 /* walk x down the tree */
367 while(x!=RBNULL && found==0) {
382 /* Search for a key according (see redblack.h)
384 static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
389 /* walk x down the tree */
394 if (x->left!=RBNULL && x->left->max>low)
403 /* Search for a key according (see redblack.h)
405 int rbsearch(const void *low, const void *high, struct rbtree *rbinfo) {
412 /* walk x down the tree */
417 if (x->left!=RBNULL && x->left->max>low)
427 * Destroy all the elements blow us in the tree
428 * only useful as part of a complete tree destroy.
430 static void rb_destroy(struct rbnode *x,void (*free_function)(void *)) {
433 rb_destroy(x->left,free_function);
434 if (x->right!=RBNULL)
435 rb_destroy(x->right,free_function);
436 if (free_function!=NULL)
437 free_function(x->object);
443 ** Rotate our tree thus:-
445 ** X rb_left_rotate(X)---> Y
447 ** A Y <---rb_right_rotate(Y) X C
451 ** N.B. This does not change the ordering.
453 ** We assume that neither X or Y is NULL
456 static void rb_left_rotate(struct rbnode **rootp, struct rbnode *x) {
460 assert(x->right!=RBNULL);
462 y=x->right; /* set Y */
464 /* Turn Y's left subtree into X's right subtree (move B)*/
467 /* If B is not null, set it's parent to be X */
468 if (y->left != RBNULL)
471 /* Set Y's parent to be what X's parent was */
474 /* if X was the root */
475 if (x->up == RBNULL) {
478 /* Set X's parent's left or right pointer to be Y */
479 if (x == x->up->left) {
486 /* Put X on Y's left */
489 /* Set X's parent to be Y */
492 y->max=x->max; /* compute Y's max */
498 if (x->right!=RBNULL&&
506 static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
511 assert(y->left!=RBNULL);
513 x=y->left; /* set X */
515 /* Turn X's right subtree into Y's left subtree (move B) */
518 /* If B is not null, set it's parent to be Y */
519 if (x->right != RBNULL)
522 /* Set X's parent to be what Y's parent was */
525 /* if Y was the root */
526 if (y->up == RBNULL) {
529 /* Set Y's parent's left or right pointer to be X */
530 if (y == y->up->left) {
537 /* Put Y on X's right */
540 /* Set Y's parent to be X */
543 x->max=y->max; /* compute Y's max */
549 if (y->right!=RBNULL&&
557 /* Return a pointer to the smallest key greater than x
559 static struct rbnode * rb_successor(const struct rbnode *x) {
562 if (x->right!=RBNULL) {
563 /* If right is not NULL then go right one and
564 ** then keep going left until we find a node with
567 for (y=x->right; y->left!=RBNULL; y=y->left);
569 /* Go up the tree until we get to a node that is on the
570 ** left of its parent (or the root) and then return the
574 while(y!=RBNULL && x==y->right) {
582 /* Return a pointer to the largest key smaller than x
584 static struct rbnode * rb_preccessor(const struct rbnode *x) {
587 if (x->left!=RBNULL) {
588 /* If left is not NULL then go left one and
589 ** then keep going right until we find a node with
592 for (y=x->left; y->right!=RBNULL; y=y->right);
594 /* Go up the tree until we get to a node that is on the
595 ** right of its parent (or the root) and then return the
599 while(y!=RBNULL && x==y->left) {
607 /* Delete the node z, and free up the space
609 static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
610 struct rbnode *x, *y, *tmp;
613 if (z->left == RBNULL || z->right == RBNULL)
618 if (y->left != RBNULL)
625 if (y->up == RBNULL) {
642 if (tmp->left!=RBNULL)
644 if (tmp->right!=RBNULL&&
652 if (y->colour == BLACK)
653 rb_delete_fix(rootp, x);
658 /* Restore the reb-black properties after a delete */
659 static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
662 while (x!=*rootp && x->colour==BLACK) {
663 if (x==x->up->left) {
665 if (w->colour==RED) {
668 rb_left_rotate(rootp, x->up);
671 if (w->left->colour==BLACK && w->right->colour==BLACK) {
675 if (w->right->colour == BLACK) {
676 w->left->colour=BLACK;
678 rb_right_rotate(rootp, w);
681 w->colour=x->up->colour;
682 x->up->colour = BLACK;
683 w->right->colour = BLACK;
684 rb_left_rotate(rootp, x->up);
689 if (w->colour==RED) {
692 rb_right_rotate(rootp, x->up);
695 if (w->right->colour==BLACK && w->left->colour==BLACK) {
699 if (w->left->colour == BLACK) {
700 w->right->colour=BLACK;
702 rb_left_rotate(rootp, w);
705 w->colour=x->up->colour;
706 x->up->colour = BLACK;
707 w->left->colour = BLACK;
708 rb_right_rotate(rootp, x->up);
718 rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
722 if (x->left==RBNULL && x->right==RBNULL) {
724 (*action)(x->key, leaf, level, arg);
726 (*action)(x->key, preorder, level, arg);
728 rb_walk(x->left, action, arg, level+1);
730 (*action)(x->key, postorder, level, arg);
732 rb_walk(x->right, action, arg, level+1);
734 (*action)(x->key, endorder, level, arg);
738 static RBLIST * rb_openlist(const struct rbnode *rootp) {
741 rblistp=(RBLIST *) malloc(sizeof(RBLIST));
745 rblistp->rootp=rootp;
746 rblistp->nextp=rootp;
749 while(rblistp->nextp->left!=RBNULL) {
750 rblistp->nextp=rblistp->nextp->left;
757 static const void * rb_readlist(RBLIST *rblistp) {
758 const void *key=NULL;
760 if (rblistp!=NULL && rblistp->nextp!=RBNULL) {
761 key=rblistp->nextp->key;
762 rblistp->nextp=rb_successor(rblistp->nextp);
768 static void rb_closelist(RBLIST *rblistp) {
773 #if defined(USE_SBRK)
774 /* Allocate space for our nodes, allowing us to get space from
775 ** sbrk in larger chucks.
777 static struct rbnode *rbfreep=NULL;
779 #define RBNODEALLOC_CHUNK_SIZE 1000
780 static struct rbnode * rb_alloc() {
785 /* must grab some more space */
786 rbfreep=(struct rbnode *) sbrk(sizeof(struct rbnode) * RBNODEALLOC_CHUNK_SIZE);
788 if (rbfreep==(struct rbnode *) -1) {
792 /* tie them together in a linked list (use the up pointer) */
793 for (i=0, x=rbfreep; i<RBNODEALLOC_CHUNK_SIZE-1; i++, x++) {
800 rbfreep = rbfreep->up;
804 /* free (dealloc) an rbnode structure - add it onto the front of the list
805 ** N.B. rbnode need not have been allocated through rb_alloc()
807 static void rb_free(struct rbnode *x) {
815 int rb_check(struct rbnode *rootp) {
816 if (rootp==NULL || rootp==RBNULL)
819 if (rootp->up!=RBNULL) {
820 fprintf(stderr, "Root up pointer not RBNULL");
825 if (rb_check1(rootp)) {
830 if (count_black(rootp)==-1)
840 rb_check1(struct rbnode *x)
842 if (x->left==NULL || x->right==NULL)
844 fprintf(stderr, "Left or right is NULL");
850 if (x->left->colour!=BLACK && x->right->colour!=BLACK)
852 fprintf(stderr, "Children of red node not both black, x=%ld", x);
857 if (x->left != RBNULL)
859 if (x->left->up != x)
861 fprintf(stderr, "x->left->up != x, x=%ld", x);
865 if (rb_check1(x->left))
869 if (x->right != RBNULL)
871 if (x->right->up != x)
873 fprintf(stderr, "x->right->up != x, x=%ld", x);
877 if (rb_check1(x->right))
883 count_black(struct rbnode *x)
890 nleft=count_black(x->left);
891 nright=count_black(x->right);
893 if (nleft==-1 || nright==-1)
898 fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
902 if (x->colour == BLACK)
910 dumptree(struct rbnode *x, int n)
914 if (x!=NULL && x!=RBNULL)
917 fprintf(stderr, "Tree: %*s %ld: left=%ld, right=%ld, colour=%s, key=%s",
923 (x->colour==BLACK) ? "BLACK" : "RED",
926 dumptree(x->left, n);
927 dumptree(x->right, n);
933 * $Log: redblack.c,v $
934 * Revision 1.1 2004/05/06 21:16:22 bdemsky
935 * Moved the interpreter
937 * Revision 1.6 2003/08/06 14:34:10 droy
940 * Revision 1.5 2003/06/18 18:39:05 bdemsky
943 * Changed header files/etc to allow dmalloc to easily be used.
944 * Changed some delete -> delete[] for correctness.
945 * Committed out parserange call. Cristian has some memory management bugs...
947 * Revision 1.4 2003/06/18 06:08:18 bdemsky
950 * Adding support for:
951 * 1) freeing the memory we use (imagine that)...will make dan's life easier &
952 * allow us to run cooler benchmarks. (not completed yet)
953 * 2) generating dot graphs of dependencies...not completed yet - the graphs aren't
954 * appropriately labeled.
956 * Revision 1.3 2003/06/18 06:06:18 bdemsky
959 * Added option to pass in function to free items in the redblack interval tree.
961 * Revision 1.5 2002/01/30 07:54:53 damo
962 * Fixed up the libtool versioning stuff (finally)
963 * Fixed bug 500600 (not detecting a NULL return from malloc)
964 * Fixed bug 509485 (no longer needs search.h)
965 * Cleaned up debugging section
966 * Allow multiple inclusions of redblack.h
967 * Thanks to Matthias Andree for reporting (and fixing) these
969 * Revision 1.4 2000/06/06 14:43:43 damo
970 * Added all the rbwalk & rbopenlist stuff. Fixed up malloc instead of sbrk.
971 * Added two new examples
973 * Revision 1.3 2000/05/24 06:45:27 damo
974 * Converted everything over to using const
975 * Added a new example1.c file to demonstrate the worst case scenario
976 * Minor fixups of the spec file
978 * Revision 1.2 2000/05/24 06:17:10 damo
979 * Fixed up the License (now the LGPL)
981 * Revision 1.1 2000/05/24 04:15:53 damo
982 * Initial import of files. Versions are now all over the place. Oh well