1 /*
2 * Redblack balanced tree algorithm
3 * Copyright (C) Damian Ivereigh 2000
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later
9 * version. See the file COPYING for details.
10 *
11 * This program 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
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this program; if not, write to the Free
18 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139,
19 * USA.
20 */
21
22 /*
23 * Includes modifications made by Carnegie Mellon Univeristy,
24 * December 3, 2014, to work in a multi-threaded environment.
25 *
26 * Original source code is available from
27 * http://sourceforge.net/projects/libredblack/files/
28 *
29 * Documentation for the original source code is available at
30 * http://libredblack.sourceforge.net/
31 */
32
33 /* Implement the red/black tree structure. It is designed to emulate
34 ** the standard tsearch() stuff. i.e. the calling conventions are
35 ** exactly the same
36 */
37
38 #include <silk/silk.h>
39
40 RCSIDENT("$SiLK: redblack.c 9f00e19adb68 2014-12-03 23:15:22Z mthomas $");
41
42 #include <silk/redblack.h>
43
44
45 /* Uncomment this if you would rather use a raw sbrk to get memory
46 ** (however the memory is never released again (only re-used). Can't
47 ** see any point in using this these days.
48 */
49 /* #define USE_SBRK */
50
51 enum nodecolour { BLACK, RED };
52
53 struct rbnode {
54 struct rbnode *left; /* Left down */
55 struct rbnode *right; /* Right down */
56 struct rbnode *up; /* Up */
57 enum nodecolour colour; /* Node colour */
58 const void *key; /* Pointer to user's key (and data) */
59 };
60
61
62 #if defined(USE_SBRK)
63
64 static struct rbnode *rb_alloc();
65 static void rb_free(struct rbnode *);
66
67 #else
68
69 #define rb_alloc() ((struct rbnode *) malloc(sizeof(struct rbnode)))
70 #define rb_free(x) (free(x))
71
72 #endif
73
74 static struct rbnode *rb_traverse(int, const void *, struct rbtree *);
75 static struct rbnode *rb_lookup(int, const void *, struct rbtree *);
76 static void rb_destroy(struct rbnode *, const struct rbnode *);
77 static void
78 rb_left_rotate(
79 struct rbnode **,
80 struct rbnode *,
81 const struct rbnode *);
82 static void
83 rb_right_rotate(
84 struct rbnode **,
85 struct rbnode *,
86 const struct rbnode *);
87 static void
88 rb_delete(
89 struct rbnode **,
90 struct rbnode *,
91 const struct rbnode *);
92 static void
93 rb_delete_fix(
94 struct rbnode **,
95 struct rbnode *,
96 const struct rbnode *);
97 static struct rbnode *
98 rb_successor(
99 const struct rbnode *,
100 const struct rbnode *);
101 static struct rbnode *
102 rb_preccessor(
103 const struct rbnode *,
104 const struct rbnode *);
105 static void
106 rb_walk(
107 const struct rbnode *,
108 void (*)(const void *, const VISIT, const int, void *),
109 void *,
110 int,
111 const struct rbnode *);
112 static RBLIST *rb_openlist(const struct rbnode *, const struct rbnode *);
113 static const void *rb_readlist(RBLIST *);
114 static void rb_closelist(RBLIST *);
115
116 /*
117 * Macros to set the members of a struct rbnode.
118 */
119 #ifndef REDBLACK_DEBUG
120
121 #define NODE_SET_COLOUR(m_node, m_value) (m_node)->colour = (m_value)
122 #define NODE_SET_LEFT(m_node, m_value) (m_node)->left = (m_value)
123 #define NODE_SET_RIGHT(m_node, m_value) (m_node)->right = (m_value)
124 #define NODE_SET_UP(m_node, m_value) (m_node)->up = (m_value)
125
126 #else
127
128 #include <silk/sklog.h>
129
130 #define NODE_SET_COLOUR(m_node, m_value) \
131 do { \
132 if ((m_node) != RBNULL) { \
133 (m_node)->colour = (m_value); \
134 } else if ((m_value) != BLACK) { \
135 DEBUGMSG("%p %s:%d: Setting colour of %p to red", \
136 (void*)pthread_self(), __FILE__, __LINE__, \
137 (m_node)); \
138 (m_node)->colour = (m_value); \
139 } else if ((m_node)->colour != BLACK) { \
140 DEBUGMSG("%p %s:%d: Restoring colour of %p to black", \
141 (void*)pthread_self(), __FILE__, __LINE__, \
142 (m_node)); \
143 (m_node)->colour = (m_value); \
144 } \
145 } while(0)
146
147 #define NODE_SET_HELPER(m_node, m_value, m_member) \
148 do { \
149 if ((m_node) != RBNULL) { \
150 (m_node)-> m_member = (m_value); \
151 } else if ((m_value) != RBNULL) { \
152 DEBUGMSG("%p %s:%d: Setting %s of %p to non-RBNULL value %p", \
153 (void*)pthread_self(), __FILE__, __LINE__, \
154 #m_member, (m_node), (m_value)); \
155 (m_node)-> m_member = (m_value); \
156 } else if ((m_node)-> m_member != RBNULL) { \
157 DEBUGMSG("%p %s:%d: Restoring %s of %p to RBNULL value %p", \
158 (void*)pthread_self(), __FILE__, __LINE__, \
159 #m_member, (m_node), (m_value)); \
160 (m_node)-> m_member = (m_value); \
161 } \
162 } while(0)
163
164 #define NODE_SET_LEFT(m_node, m_value) \
165 NODE_SET_HELPER(m_node, m_value, left)
166
167 #define NODE_SET_RIGHT(m_node, m_value) \
168 NODE_SET_HELPER(m_node, m_value, right)
169
170 #define NODE_SET_UP(m_node, m_value) \
171 NODE_SET_HELPER(m_node, m_value, up)
172
173 #endif /* #else of #ifndef REDBLACK_DEBUG */
174
175
176 /*
177 ** OK here we go, the balanced tree stuff. The algorithm is the
178 ** fairly standard red/black taken from "Introduction to Algorithms"
179 ** by Cormen, Leiserson & Rivest. Maybe one of these days I will
180 ** fully understand all this stuff.
181 **
182 ** Basically a red/black balanced tree has the following properties:-
183 ** 1) Every node is either red or black (colour is RED or BLACK)
184 ** 2) A leaf (RBNULL pointer) is considered black
185 ** 3) If a node is red then its children are black
186 ** 4) Every path from a node to a leaf contains the same no
187 ** of black nodes
188 **
189 ** 3) & 4) above guarantee that the longest path (alternating
190 ** red and black nodes) is only twice as long as the shortest
191 ** path (all black nodes). Thus the tree remains fairly balanced.
192 */
193
194 /*
195 * Initialise a tree. Identifies the comparison routine and any config
196 * data that must be sent to it when called.
197 * Returns a pointer to the top of the tree.
198 */
199 struct rbtree *
rbinit(int (* cmp)(const void * p1,const void * p2,const void * cfg),const void * config)200 rbinit(
201 int (*cmp)(const void *p1, const void *p2, const void *cfg),
202 const void *config)
203 {
204 struct rbnode *RBNULL;
205 struct rbtree *retval;
206
207 retval = (struct rbtree *)malloc(sizeof(struct rbtree));
208 if (NULL == retval) {
209 return(NULL);
210 }
211
212 /* Dummy (sentinel) node, so that we can make X->left->up = X
213 * We then use this instead of NULL to mean the top or bottom
214 * end of the rb tree. It is a black node.
215 */
216 RBNULL = retval->rb_null = (struct rbnode *)malloc(sizeof(struct rbnode));
217 if (NULL == retval->rb_null) {
218 free(retval);
219 return NULL;
220 }
221 retval->rb_null->left = RBNULL;
222 retval->rb_null->right = RBNULL;
223 retval->rb_null->up = RBNULL;
224 retval->rb_null->colour = BLACK;
225 retval->rb_null->key = NULL;
226
227 retval->rb_cmp = cmp;
228 retval->rb_config = config;
229 retval->rb_root = RBNULL;
230
231 return(retval);
232 }
233
234 void
rbdestroy(struct rbtree * rbinfo)235 rbdestroy(
236 struct rbtree *rbinfo)
237 {
238 const struct rbnode *RBNULL;
239
240 if (rbinfo == NULL) {
241 return;
242 }
243 RBNULL = rbinfo->rb_null;
244
245 if (rbinfo->rb_root != RBNULL) {
246 rb_destroy(rbinfo->rb_root, RBNULL);
247 }
248
249 free(rbinfo->rb_null);
250 free(rbinfo);
251 }
252
253 const void *
rbsearch(const void * key,struct rbtree * rbinfo)254 rbsearch(
255 const void *key,
256 struct rbtree *rbinfo)
257 {
258 const struct rbnode *RBNULL;
259 struct rbnode *x;
260
261 if (rbinfo == NULL) {
262 return(NULL);
263 }
264 RBNULL = rbinfo->rb_null;
265
266 x = rb_traverse(1, key, rbinfo);
267
268 return((x == RBNULL) ? NULL : x->key);
269 }
270
271 const void *
rbfind(const void * key,struct rbtree * rbinfo)272 rbfind(
273 const void *key,
274 struct rbtree *rbinfo)
275 {
276 const struct rbnode *RBNULL;
277 struct rbnode *x;
278
279 if (rbinfo == NULL) {
280 return(NULL);
281 }
282 RBNULL = rbinfo->rb_null;
283
284 /* If we have a NULL root (empty tree) then just return */
285 if (rbinfo->rb_root == RBNULL) {
286 return(NULL);
287 }
288
289 x = rb_traverse(0, key, rbinfo);
290
291 return((x == RBNULL) ? NULL : x->key);
292 }
293
294 const void *
rbdelete(const void * key,struct rbtree * rbinfo)295 rbdelete(
296 const void *key,
297 struct rbtree *rbinfo)
298 {
299 const struct rbnode *RBNULL;
300 struct rbnode *x;
301 const void *y;
302
303 if (rbinfo == NULL) {
304 return(NULL);
305 }
306 RBNULL = rbinfo->rb_null;
307
308 x = rb_traverse(0, key, rbinfo);
309
310 if (x == RBNULL) {
311 return(NULL);
312 } else {
313 y = x->key;
314 rb_delete(&rbinfo->rb_root, x, RBNULL);
315 return(y);
316 }
317 }
318
319 void
rbwalk(const struct rbtree * rbinfo,void (* action)(const void *,const VISIT,const int,void *),void * arg)320 rbwalk(
321 const struct rbtree *rbinfo,
322 void (*action)(
323 const void *,
324 const VISIT,
325 const int,
326 void *),
327 void *arg)
328 {
329 if (rbinfo == NULL) {
330 return;
331 }
332
333 rb_walk(rbinfo->rb_root, action, arg, 0, rbinfo->rb_null);
334 }
335
336 RBLIST *
rbopenlist(const struct rbtree * rbinfo)337 rbopenlist(
338 const struct rbtree *rbinfo)
339 {
340 if (rbinfo == NULL) {
341 return(NULL);
342 }
343
344 return(rb_openlist(rbinfo->rb_root, rbinfo->rb_null));
345 }
346
347 const void *
rbreadlist(RBLIST * rblistp)348 rbreadlist(
349 RBLIST *rblistp)
350 {
351 if (rblistp == NULL) {
352 return(NULL);
353 }
354
355 return(rb_readlist(rblistp));
356 }
357
358 void
rbcloselist(RBLIST * rblistp)359 rbcloselist(
360 RBLIST *rblistp)
361 {
362 if (rblistp == NULL) {
363 return;
364 }
365
366 rb_closelist(rblistp);
367 }
368
369 const void *
rblookup(int mode,const void * key,struct rbtree * rbinfo)370 rblookup(
371 int mode,
372 const void *key,
373 struct rbtree *rbinfo)
374 {
375 const struct rbnode *RBNULL;
376 struct rbnode *x;
377
378 /* If we have a NULL root (empty tree) then just return NULL */
379 if (rbinfo == NULL || rbinfo->rb_root == NULL) {
380 return(NULL);
381 }
382 RBNULL = rbinfo->rb_null;
383
384 x = rb_lookup(mode, key, rbinfo);
385
386 return((x == RBNULL) ? NULL : x->key);
387 }
388
389 /* --------------------------------------------------------------------- */
390
391 /* Search for and if not found and insert is true, will add a new
392 ** node in. Returns a pointer to the new node, or the node found
393 */
394 static struct rbnode *
rb_traverse(int insert,const void * key,struct rbtree * rbinfo)395 rb_traverse(
396 int insert,
397 const void *key,
398 struct rbtree *rbinfo)
399 {
400 struct rbnode *RBNULL = rbinfo->rb_null;
401 struct rbnode *x, *y, *z;
402 int cmp;
403 int found = 0;
404 /* int cmpmods(); */
405
406 y = RBNULL; /* points to the parent of x */
407 x = rbinfo->rb_root;
408
409 /* walk x down the tree */
410 while (x != RBNULL && found == 0) {
411 y = x;
412 /* printf("key=%s, x->key=%s\n", key, x->key); */
413 cmp = (*rbinfo->rb_cmp)(key, x->key, rbinfo->rb_config);
414 if (cmp < 0) {
415 x = x->left;
416 } else if (cmp > 0) {
417 x = x->right;
418 } else {
419 found = 1;
420 }
421 }
422
423 if (found || !insert) {
424 return(x);
425 }
426
427 if ((z = rb_alloc()) == NULL) {
428 /* Whoops, no memory */
429 return(RBNULL);
430 }
431
432 z->key = key;
433 NODE_SET_UP(z, y);
434 if (y == RBNULL) {
435 rbinfo->rb_root = z;
436 } else {
437 cmp = (*rbinfo->rb_cmp)(z->key, y->key, rbinfo->rb_config);
438 if (cmp < 0) {
439 NODE_SET_LEFT(y, z);
440 } else {
441 NODE_SET_RIGHT(y, z);
442 }
443 }
444
445 NODE_SET_LEFT(z, RBNULL);
446 NODE_SET_RIGHT(z, RBNULL);
447
448 /* colour this new node red */
449 NODE_SET_COLOUR(z, RED);
450
451 /* Having added a red node, we must now walk back up the tree balancing
452 ** it, by a series of rotations and changing of colours
453 */
454 x = z;
455
456 /* While we are not at the top and our parent node is red
457 ** N.B. Since the root node is garanteed black, then we
458 ** are also going to stop if we are the child of the root
459 */
460
461 while (x != rbinfo->rb_root && (x->up->colour == RED)) {
462 /* if our parent is on the left side of our grandparent */
463 if (x->up == x->up->up->left) {
464 /* get the right side of our grandparent (uncle?) */
465 y = x->up->up->right;
466 if (y->colour == RED) {
467 /* make our parent black */
468 NODE_SET_COLOUR(x->up, BLACK);
469 /* make our uncle black */
470 NODE_SET_COLOUR(y, BLACK);
471 /* make our grandparent red */
472 NODE_SET_COLOUR(x->up->up, RED);
473
474 /* now consider our grandparent */
475 x = x->up->up;
476 } else {
477 /* if we are on the right side of our parent */
478 if (x == x->up->right) {
479 /* Move up to our parent */
480 x = x->up;
481 rb_left_rotate(&rbinfo->rb_root, x, RBNULL);
482 }
483
484 /* make our parent black */
485 NODE_SET_COLOUR(x->up, BLACK);
486 /* make our grandparent red */
487 NODE_SET_COLOUR(x->up->up, RED);
488 /* right rotate our grandparent */
489 rb_right_rotate(&rbinfo->rb_root, x->up->up, RBNULL);
490 }
491 } else {
492 /* everything here is the same as above, but
493 ** exchanging left for right
494 */
495
496 y = x->up->up->left;
497 if (y->colour == RED) {
498 NODE_SET_COLOUR(x->up, BLACK);
499 NODE_SET_COLOUR(y, BLACK);
500 NODE_SET_COLOUR(x->up->up, RED);
501
502 x = x->up->up;
503 } else {
504 if (x == x->up->left) {
505 x = x->up;
506 rb_right_rotate(&rbinfo->rb_root, x, RBNULL);
507 }
508
509 NODE_SET_COLOUR(x->up, BLACK);
510 NODE_SET_COLOUR(x->up->up, RED);
511 rb_left_rotate(&rbinfo->rb_root, x->up->up, RBNULL);
512 }
513 }
514 }
515
516 /* Set the root node black */
517 NODE_SET_COLOUR(rbinfo->rb_root, BLACK);
518
519 return(z);
520 }
521
522 /* Search for a key according to mode (see redblack.h)
523 */
524 static struct rbnode *
rb_lookup(int mode,const void * key,struct rbtree * rbinfo)525 rb_lookup(
526 int mode,
527 const void *key,
528 struct rbtree *rbinfo)
529 {
530 struct rbnode *RBNULL = rbinfo->rb_null;
531 struct rbnode *x, *y;
532 int cmp = 0;
533 int found = 0;
534
535 y = RBNULL; /* points to the parent of x */
536 x = rbinfo->rb_root;
537
538 if (mode == RB_LUFIRST) {
539 /* Keep going left until we hit a NULL */
540 while (x != RBNULL) {
541 y = x;
542 x = x->left;
543 }
544
545 return(y);
546 } else if (mode == RB_LULAST) {
547 /* Keep going right until we hit a NULL */
548 while (x != RBNULL) {
549 y = x;
550 x = x->right;
551 }
552
553 return(y);
554 }
555
556 /* walk x down the tree */
557 while (x != RBNULL && found == 0) {
558 y = x;
559 /* printf("key=%s, x->key=%s\n", key, x->key); */
560 cmp = (*rbinfo->rb_cmp)(key, x->key, rbinfo->rb_config);
561 if (cmp < 0) {
562 x = x->left;
563 } else if (cmp > 0) {
564 x = x->right;
565 } else {
566 found = 1;
567 }
568 }
569
570 if (found
571 && (mode == RB_LUEQUAL || mode == RB_LUGTEQ || mode == RB_LULTEQ))
572 {
573 return(x);
574 }
575
576 if (!found
577 && (mode == RB_LUEQUAL || mode == RB_LUNEXT || mode == RB_LUPREV))
578 {
579 return(RBNULL);
580 }
581
582 if (mode == RB_LUGTEQ || (!found && mode == RB_LUGREAT)) {
583 if (cmp > 0) {
584 return(rb_successor(y, RBNULL));
585 } else {
586 return(y);
587 }
588 }
589
590 if (mode == RB_LULTEQ || (!found && mode == RB_LULESS)) {
591 if (cmp < 0) {
592 return(rb_preccessor(y, RBNULL));
593 } else {
594 return(y);
595 }
596 }
597
598 if (mode == RB_LUNEXT || (found && mode == RB_LUGREAT)) {
599 return(rb_successor(x, RBNULL));
600 }
601
602 if (mode == RB_LUPREV || (found && mode == RB_LULESS)) {
603 return(rb_preccessor(x, RBNULL));
604 }
605
606 /* Shouldn't get here */
607 return(RBNULL);
608 }
609
610 /*
611 * Destroy all the elements blow us in the tree
612 * only useful as part of a complete tree destroy.
613 */
614 static void
rb_destroy(struct rbnode * x,const struct rbnode * RBNULL)615 rb_destroy(
616 struct rbnode *x,
617 const struct rbnode *RBNULL)
618 {
619 if (x != RBNULL) {
620 if (x->left != RBNULL) {
621 rb_destroy(x->left, RBNULL);
622 }
623 if (x->right != RBNULL) {
624 rb_destroy(x->right, RBNULL);
625 }
626 rb_free(x);
627 }
628 }
629
630 /*
631 ** Rotate our tree thus:-
632 **
633 ** X rb_left_rotate(X)---> Y
634 ** / \ / \
635 ** A Y <---rb_right_rotate(Y) X C
636 ** / \ / \
637 ** B C A B
638 **
639 ** N.B. This does not change the ordering.
640 **
641 ** We assume that neither X or Y is NULL
642 */
643
644 static void
rb_left_rotate(struct rbnode ** rootp,struct rbnode * x,const struct rbnode * RBNULL)645 rb_left_rotate(
646 struct rbnode **rootp,
647 struct rbnode *x,
648 const struct rbnode *RBNULL)
649 {
650 struct rbnode *y;
651
652 assert(x != RBNULL);
653 assert(x->right != RBNULL);
654
655 y = x->right; /* set Y */
656
657 /* Turn Y's left subtree into X's right subtree (move B)*/
658 NODE_SET_RIGHT(x, y->left);
659
660 /* If B is not null, set it's parent to be X */
661 if (y->left != RBNULL) {
662 NODE_SET_UP(y->left, x);
663 }
664
665 /* Set Y's parent to be what X's parent was */
666 NODE_SET_UP(y, x->up);
667
668 /* if X was the root */
669 if (x->up == RBNULL) {
670 *rootp = y;
671 } else {
672 /* Set X's parent's left or right pointer to be Y */
673 if (x == x->up->left) {
674 NODE_SET_LEFT(x->up, y);
675 } else {
676 NODE_SET_RIGHT(x->up, y);
677 }
678 }
679
680 /* Put X on Y's left */
681 NODE_SET_LEFT(y, x);
682
683 /* Set X's parent to be Y */
684 NODE_SET_UP(x, y);
685 }
686
687 static void
rb_right_rotate(struct rbnode ** rootp,struct rbnode * y,const struct rbnode * RBNULL)688 rb_right_rotate(
689 struct rbnode **rootp,
690 struct rbnode *y,
691 const struct rbnode *RBNULL)
692 {
693 struct rbnode *x;
694
695 assert(y != RBNULL);
696 assert(y->left != RBNULL);
697
698 x = y->left; /* set X */
699
700 /* Turn X's right subtree into Y's left subtree (move B) */
701 NODE_SET_LEFT(y, x->right);
702
703 /* If B is not null, set it's parent to be Y */
704 if (x->right != RBNULL) {
705 NODE_SET_UP(x->right, y);
706 }
707
708 /* Set X's parent to be what Y's parent was */
709 NODE_SET_UP(x, y->up);
710
711 /* if Y was the root */
712 if (y->up == RBNULL) {
713 *rootp = x;
714 } else {
715 /* Set Y's parent's left or right pointer to be X */
716 if (y == y->up->left) {
717 NODE_SET_LEFT(y->up, x);
718 } else {
719 NODE_SET_RIGHT(y->up, x);
720 }
721 }
722
723 /* Put Y on X's right */
724 NODE_SET_RIGHT(x, y);
725
726 /* Set Y's parent to be X */
727 NODE_SET_UP(y, x);
728 }
729
730 /* Return a pointer to the smallest key greater than x
731 */
732 static struct rbnode *
rb_successor(const struct rbnode * x,const struct rbnode * RBNULL)733 rb_successor(
734 const struct rbnode *x,
735 const struct rbnode *RBNULL)
736 {
737 struct rbnode *y;
738
739 if (x->right != RBNULL) {
740 /* If right is not NULL then go right one and
741 ** then keep going left until we find a node with
742 ** no left pointer.
743 */
744 for (y = x->right; y->left != RBNULL; y = y->left) ;
745 } else {
746 /* Go up the tree until we get to a node that is on the
747 ** left of its parent (or the root) and then return the
748 ** parent.
749 */
750 y = x->up;
751 while (y != RBNULL && x == y->right) {
752 x = y;
753 y = y->up;
754 }
755 }
756 return(y);
757 }
758
759 /* Return a pointer to the largest key smaller than x
760 */
761 static struct rbnode *
rb_preccessor(const struct rbnode * x,const struct rbnode * RBNULL)762 rb_preccessor(
763 const struct rbnode *x,
764 const struct rbnode *RBNULL)
765 {
766 struct rbnode *y;
767
768 if (x->left != RBNULL) {
769 /* If left is not NULL then go left one and
770 ** then keep going right until we find a node with
771 ** no right pointer.
772 */
773 for (y = x->left; y->right != RBNULL; y = y->right) ;
774 } else {
775 /* Go up the tree until we get to a node that is on the
776 ** right of its parent (or the root) and then return the
777 ** parent.
778 */
779 y = x->up;
780 while (y != RBNULL && x == y->left) {
781 x = y;
782 y = y->up;
783 }
784 }
785 return(y);
786 }
787
788 /* Delete the node z, and free up the space
789 */
790 static void
rb_delete(struct rbnode ** rootp,struct rbnode * z,const struct rbnode * RBNULL)791 rb_delete(
792 struct rbnode **rootp,
793 struct rbnode *z,
794 const struct rbnode *RBNULL)
795 {
796 struct rbnode *x, *y;
797
798 if (z->left == RBNULL || z->right == RBNULL) {
799 y = z;
800 } else {
801 y = rb_successor(z, RBNULL);
802 }
803
804 if (y->left != RBNULL) {
805 x = y->left;
806 } else {
807 x = y->right;
808 }
809
810 NODE_SET_UP(x, y->up);
811
812 if (y->up == RBNULL) {
813 *rootp = x;
814 } else {
815 if (y == y->up->left) {
816 NODE_SET_LEFT(y->up, x);
817 } else {
818 NODE_SET_RIGHT(y->up, x);
819 }
820 }
821
822 if (y != z) {
823 z->key = y->key;
824 }
825
826 if (y->colour == BLACK) {
827 rb_delete_fix(rootp, x, RBNULL);
828 }
829
830 rb_free(y);
831 }
832
833 /* Restore the reb-black properties after a delete */
834 static void
rb_delete_fix(struct rbnode ** rootp,struct rbnode * x,const struct rbnode * RBNULL)835 rb_delete_fix(
836 struct rbnode **rootp,
837 struct rbnode *x,
838 const struct rbnode *RBNULL)
839 {
840 struct rbnode *w;
841
842 while (x != *rootp && x->colour == BLACK) {
843 if (x == x->up->left) {
844 w = x->up->right;
845 if (w->colour == RED) {
846 NODE_SET_COLOUR(w, BLACK);
847 NODE_SET_COLOUR(x->up, RED);
848 rb_left_rotate(rootp, x->up, RBNULL);
849 w = x->up->right;
850 }
851
852 if (w->left->colour == BLACK && w->right->colour == BLACK) {
853 NODE_SET_COLOUR(w, RED);
854 x = x->up;
855 } else {
856 if (w->right->colour == BLACK) {
857 NODE_SET_COLOUR(w->left, BLACK);
858 NODE_SET_COLOUR(w, RED);
859 rb_right_rotate(rootp, w, RBNULL);
860 w = x->up->right;
861 }
862
863 NODE_SET_COLOUR(w, x->up->colour);
864 NODE_SET_COLOUR(x->up, BLACK);
865 NODE_SET_COLOUR(w->right, BLACK);
866 rb_left_rotate(rootp, x->up, RBNULL);
867 x = *rootp;
868 }
869 } else {
870 w = x->up->left;
871 if (w->colour == RED) {
872 NODE_SET_COLOUR(w, BLACK);
873 NODE_SET_COLOUR(x->up, RED);
874 rb_right_rotate(rootp, x->up, RBNULL);
875 w = x->up->left;
876 }
877
878 if (w->right->colour == BLACK && w->left->colour == BLACK) {
879 NODE_SET_COLOUR(w, RED);
880 x = x->up;
881 } else {
882 if (w->left->colour == BLACK) {
883 NODE_SET_COLOUR(w->right, BLACK);
884 NODE_SET_COLOUR(w, RED);
885 rb_left_rotate(rootp, w, RBNULL);
886 w = x->up->left;
887 }
888
889 NODE_SET_COLOUR(w, x->up->colour);
890 NODE_SET_COLOUR(x->up, BLACK);
891 NODE_SET_COLOUR(w->left, BLACK);
892 rb_right_rotate(rootp, x->up, RBNULL);
893 x = *rootp;
894 }
895 }
896 }
897
898 NODE_SET_COLOUR(x, BLACK);
899 }
900
901 static void
rb_walk(const struct rbnode * x,void (* action)(const void *,const VISIT,const int,void *),void * arg,int level,const struct rbnode * RBNULL)902 rb_walk(
903 const struct rbnode *x,
904 void (*action)(
905 const void *,
906 const VISIT,
907 const int,
908 void *),
909 void *arg,
910 int level,
911 const struct rbnode *RBNULL)
912 {
913 if (x == RBNULL) {
914 return;
915 }
916
917 if (x->left == RBNULL && x->right == RBNULL) {
918 /* leaf */
919 (*action)(x->key, leaf, level, arg);
920 } else {
921 (*action)(x->key, preorder, level, arg);
922
923 rb_walk(x->left, action, arg, level+1, RBNULL);
924
925 (*action)(x->key, postorder, level, arg);
926
927 rb_walk(x->right, action, arg, level+1, RBNULL);
928
929 (*action)(x->key, endorder, level, arg);
930 }
931 }
932
933 static RBLIST *
rb_openlist(const struct rbnode * rootp,const struct rbnode * RBNULL)934 rb_openlist(
935 const struct rbnode *rootp,
936 const struct rbnode *RBNULL)
937 {
938 RBLIST *rblistp;
939
940 rblistp = (RBLIST *)malloc(sizeof(RBLIST));
941 if (!rblistp) {
942 return(NULL);
943 }
944
945 rblistp->rootp = rootp;
946 rblistp->nextp = rootp;
947 rblistp->nullp = RBNULL;
948
949 if (rootp != RBNULL) {
950 while (rblistp->nextp->left != RBNULL) {
951 rblistp->nextp = rblistp->nextp->left;
952 }
953 }
954
955 return(rblistp);
956 }
957
958 static const void *
rb_readlist(RBLIST * rblistp)959 rb_readlist(
960 RBLIST *rblistp)
961 {
962 const void *key = NULL;
963 const struct rbnode *RBNULL;
964
965 if (rblistp != NULL) {
966 RBNULL = rblistp->nullp;
967 if (rblistp->nextp != RBNULL) {
968 key = rblistp->nextp->key;
969 rblistp->nextp = rb_successor(rblistp->nextp, RBNULL);
970 }
971 }
972
973 return(key);
974 }
975
976 static void
rb_closelist(RBLIST * rblistp)977 rb_closelist(
978 RBLIST *rblistp)
979 {
980 if (rblistp) {
981 free(rblistp);
982 }
983 }
984
985 #if defined(USE_SBRK)
986 /* Allocate space for our nodes, allowing us to get space from
987 ** sbrk in larger chucks.
988 */
989 static struct rbnode *rbfreep = NULL;
990
991 #define RBNODEALLOC_CHUNK_SIZE 1000
992 static struct rbnode *
rb_alloc()993 rb_alloc()
994 {
995 struct rbnode *x;
996 int i;
997
998 if (rbfreep == NULL) {
999 /* must grab some more space */
1000 rbfreep = ((struct rbnode *)
1001 sbrk(sizeof(struct rbnode) * RBNODEALLOC_CHUNK_SIZE));
1002
1003 if (rbfreep == (struct rbnode *) -1) {
1004 return(NULL);
1005 }
1006
1007 /* tie them together in a linked list (use the up pointer) */
1008 for (i = 0, x = rbfreep; i < RBNODEALLOC_CHUNK_SIZE - 1; i++, x++) {
1009 x->up = (x + 1);
1010 }
1011 NODE_SET_UP(x, NULL);
1012 }
1013
1014 x = rbfreep;
1015 rbfreep = rbfreep->up;
1016 return(x);
1017 }
1018
1019 /* free (dealloc) an rbnode structure - add it onto the front of the list
1020 ** N.B. rbnode need not have been allocated through rb_alloc()
1021 */
1022 static void
rb_free(struct rbnode * x)1023 rb_free(struct rbnode *x)
1024 {
1025 NODE_SET_UP(x, rbfreep);
1026 rbfreep = x;
1027 }
1028
1029 #endif
1030
1031 #if 0
1032 int
1033 rb_check(struct rbnode *rootp)
1034 {
1035 if (rootp == NULL || rootp == RBNULL) {
1036 return(0);
1037 }
1038
1039 if (rootp->up != RBNULL) {
1040 fprintf(stderr, "Root up pointer not RBNULL");
1041 dumptree(rootp, 0);
1042 return(1);
1043 }
1044
1045 if (rb_check1(rootp)) {
1046 dumptree(rootp, 0);
1047 return(1);
1048 }
1049
1050 if (count_black(rootp) == -1) {
1051 dumptree(rootp, 0);
1052 return(-1);
1053 }
1054
1055 return(0);
1056 }
1057
1058 int
1059 rb_check1(struct rbnode *x)
1060 {
1061 if (x->left == NULL || x->right == NULL) {
1062 fprintf(stderr, "Left or right is NULL");
1063 return(1);
1064 }
1065
1066 if (x->colour == RED) {
1067 if (x->left->colour != BLACK && x->right->colour != BLACK) {
1068 fprintf(stderr, "Children of red node not both black, x=%ld", x);
1069 return(1);
1070 }
1071 }
1072
1073 if (x->left != RBNULL) {
1074 if (x->left->up != x) {
1075 fprintf(stderr, "x->left->up != x, x=%ld", x);
1076 return(1);
1077 }
1078
1079 if (rb_check1(x->left)) {
1080 return(1);
1081 }
1082 }
1083
1084 if (x->right != RBNULL) {
1085 if (x->right->up != x) {
1086 fprintf(stderr, "x->right->up != x, x=%ld", x);
1087 return(1);
1088 }
1089
1090 if (rb_check1(x->right)) {
1091 return(1);
1092 }
1093 }
1094 return(0);
1095 }
1096
1097 count_black(struct rbnode *x)
1098 {
1099 int nleft, nright;
1100
1101 if (x == RBNULL) {
1102 return(1);
1103 }
1104
1105 nleft = count_black(x->left);
1106 nright = count_black(x->right);
1107
1108 if (nleft == -1 || nright == -1) {
1109 return(-1);
1110 }
1111
1112 if (nleft != nright) {
1113 fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
1114 return(-1);
1115 }
1116
1117 if (x->colour == BLACK) {
1118 nleft++;
1119 }
1120
1121 return(nleft);
1122 }
1123
1124 dumptree(struct rbnode *x, int n)
1125 {
1126 char *prkey();
1127
1128 if (x != NULL && x != RBNULL) {
1129 n++;
1130 fprintf(stderr, "Tree: %*s %ld: left=%ld, right=%ld, colour=%s, key=%s",
1131 n,
1132 "",
1133 x,
1134 x->left,
1135 x->right,
1136 (x->colour == BLACK) ? "BLACK" : "RED",
1137 prkey(x->key));
1138
1139 dumptree(x->left, n);
1140 dumptree(x->right, n);
1141 }
1142 }
1143 #endif
1144
1145
1146 /*
1147 ** Local Variables:
1148 ** mode:c
1149 ** indent-tabs-mode:nil
1150 ** c-basic-offset:4
1151 ** End:
1152 */
1153