2 a talloc based red-black tree
4 Copyright (C) Ronnie Sahlberg 2007
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, see <http://www.gnu.org/licenses/>.
24 #include "lib/util/debug.h"
26 #include "common/logging.h"
27 #include "common/rb_tree.h"
29 #define NO_MEMORY_FATAL(p) do { if (!(p)) { \
30 DEBUG(DEBUG_CRIT,("Out of memory for %s at %s\n", #p, __location__)); \
36 tree_destructor_traverse_node(TALLOC_CTX
*mem_ctx
, trbt_node_t
*node
)
38 talloc_set_destructor(node
, NULL
);
40 tree_destructor_traverse_node(mem_ctx
, node
->left
);
43 tree_destructor_traverse_node(mem_ctx
, node
->right
);
45 talloc_steal(mem_ctx
, node
);
49 destroy a tree and remove all its nodes
51 static int tree_destructor(trbt_tree_t
*tree
)
65 /* traverse the tree and remove the node destructor and steal
66 the node to the temporary context.
67 we don't want to use the existing destructor for the node
68 since that will remove the nodes one by one from the tree.
69 since the entire tree will be completely destroyed we don't care
70 if it is inconsistent or unbalanced while freeing the
73 tmp_ctx
= talloc_new(NULL
);
74 tree_destructor_traverse_node(tmp_ctx
, node
);
81 /* create a red black tree */
83 trbt_create(TALLOC_CTX
*memctx
, uint32_t flags
)
87 tree
= talloc_zero(memctx
, trbt_tree_t
);
88 NO_MEMORY_FATAL(tree
);
90 /* If the tree is freed, we must walk over all entries and steal the
91 node from the stored data pointer and release the node.
92 Note, when we free the tree we only free the tree and not any of
93 the data stored in the tree.
95 talloc_set_destructor(tree
, tree_destructor
);
101 static inline trbt_node_t
*
102 trbt_parent(trbt_node_t
*node
)
107 static inline trbt_node_t
*
108 trbt_grandparent(trbt_node_t
*node
)
112 parent
=trbt_parent(node
);
114 return parent
->parent
;
119 static inline trbt_node_t
*
120 trbt_uncle(trbt_node_t
*node
)
122 trbt_node_t
*parent
, *grandparent
;
124 parent
=trbt_parent(node
);
128 grandparent
=trbt_parent(parent
);
132 if(parent
==grandparent
->left
){
133 return grandparent
->right
;
135 return grandparent
->left
;
139 static inline void trbt_insert_case1(trbt_tree_t
*tree
, trbt_node_t
*node
);
140 static inline void trbt_insert_case2(trbt_tree_t
*tree
, trbt_node_t
*node
);
143 trbt_rotate_left(trbt_node_t
*node
)
145 trbt_tree_t
*tree
= node
->tree
;
148 if(node
->parent
->left
==node
){
149 node
->parent
->left
=node
->right
;
151 node
->parent
->right
=node
->right
;
154 tree
->root
=node
->right
;
156 node
->right
->parent
=node
->parent
;
157 node
->parent
=node
->right
;
158 node
->right
=node
->right
->left
;
160 node
->right
->parent
=node
;
162 node
->parent
->left
=node
;
166 trbt_rotate_right(trbt_node_t
*node
)
168 trbt_tree_t
*tree
= node
->tree
;
171 if(node
->parent
->left
==node
){
172 node
->parent
->left
=node
->left
;
174 node
->parent
->right
=node
->left
;
177 tree
->root
=node
->left
;
179 node
->left
->parent
=node
->parent
;
180 node
->parent
=node
->left
;
181 node
->left
=node
->left
->right
;
183 node
->left
->parent
=node
;
185 node
->parent
->right
=node
;
188 /* NULL nodes are black by definition */
189 static inline int trbt_get_color(trbt_node_t
*node
)
194 return node
->rb_color
;
196 static inline int trbt_get_color_left(trbt_node_t
*node
)
201 if (node
->left
==NULL
) {
204 return node
->left
->rb_color
;
206 static inline int trbt_get_color_right(trbt_node_t
*node
)
211 if (node
->right
==NULL
) {
214 return node
->right
->rb_color
;
216 /* setting a NULL node to black is a nop */
217 static inline void trbt_set_color(trbt_node_t
*node
, int color
)
222 node
->rb_color
= color
;
224 static inline void trbt_set_color_left(trbt_node_t
*node
, int color
)
226 if (node
== NULL
|| node
->left
== NULL
) {
229 node
->left
->rb_color
= color
;
231 static inline void trbt_set_color_right(trbt_node_t
*node
, int color
)
233 if (node
== NULL
|| node
->right
== NULL
) {
236 node
->right
->rb_color
= color
;
240 trbt_insert_case5(trbt_tree_t
*tree
, trbt_node_t
*node
)
242 trbt_node_t
*grandparent
;
245 parent
=trbt_parent(node
);
246 grandparent
=trbt_parent(parent
);
247 parent
->rb_color
=TRBT_BLACK
;
248 grandparent
->rb_color
=TRBT_RED
;
249 if( (node
==parent
->left
) && (parent
==grandparent
->left
) ){
250 trbt_rotate_right(grandparent
);
252 trbt_rotate_left(grandparent
);
257 trbt_insert_case4(trbt_tree_t
*tree
, trbt_node_t
*node
)
259 trbt_node_t
*grandparent
;
262 parent
=trbt_parent(node
);
263 grandparent
=trbt_parent(parent
);
267 if( (node
==parent
->right
) && (parent
==grandparent
->left
) ){
268 trbt_rotate_left(parent
);
270 } else if( (node
==parent
->left
) && (parent
==grandparent
->right
) ){
271 trbt_rotate_right(parent
);
274 trbt_insert_case5(tree
, node
);
278 trbt_insert_case3(trbt_tree_t
*tree
, trbt_node_t
*node
)
280 trbt_node_t
*grandparent
;
284 uncle
=trbt_uncle(node
);
285 if(uncle
&& (uncle
->rb_color
==TRBT_RED
)){
286 parent
=trbt_parent(node
);
287 parent
->rb_color
=TRBT_BLACK
;
288 uncle
->rb_color
=TRBT_BLACK
;
289 grandparent
=trbt_grandparent(node
);
290 grandparent
->rb_color
=TRBT_RED
;
291 trbt_insert_case1(tree
, grandparent
);
293 trbt_insert_case4(tree
, node
);
298 trbt_insert_case2(trbt_tree_t
*tree
, trbt_node_t
*node
)
302 parent
=trbt_parent(node
);
303 /* parent is always non-NULL here */
304 if(parent
->rb_color
==TRBT_BLACK
){
307 trbt_insert_case3(tree
, node
);
311 trbt_insert_case1(trbt_tree_t
*tree
, trbt_node_t
*node
)
315 parent
=trbt_parent(node
);
317 node
->rb_color
=TRBT_BLACK
;
320 trbt_insert_case2(tree
, node
);
323 static inline trbt_node_t
*
324 trbt_sibling(trbt_node_t
*node
)
328 parent
=trbt_parent(node
);
333 if (node
== parent
->left
) {
334 return parent
->right
;
341 trbt_delete_case6(trbt_node_t
*node
)
343 trbt_node_t
*sibling
, *parent
;
345 sibling
= trbt_sibling(node
);
346 parent
= trbt_parent(node
);
348 trbt_set_color(sibling
, parent
->rb_color
);
349 trbt_set_color(parent
, TRBT_BLACK
);
350 if (node
== parent
->left
) {
351 trbt_set_color_right(sibling
, TRBT_BLACK
);
352 trbt_rotate_left(parent
);
354 trbt_set_color_left(sibling
, TRBT_BLACK
);
355 trbt_rotate_right(parent
);
361 trbt_delete_case5(trbt_node_t
*node
)
363 trbt_node_t
*parent
, *sibling
;
365 parent
= trbt_parent(node
);
366 sibling
= trbt_sibling(node
);
367 if ( (node
== parent
->left
)
368 &&(trbt_get_color(sibling
) == TRBT_BLACK
)
369 &&(trbt_get_color_left(sibling
) == TRBT_RED
)
370 &&(trbt_get_color_right(sibling
) == TRBT_BLACK
) ){
371 trbt_set_color(sibling
, TRBT_RED
);
372 trbt_set_color_left(sibling
, TRBT_BLACK
);
373 trbt_rotate_right(sibling
);
374 trbt_delete_case6(node
);
377 if ( (node
== parent
->right
)
378 &&(trbt_get_color(sibling
) == TRBT_BLACK
)
379 &&(trbt_get_color_right(sibling
) == TRBT_RED
)
380 &&(trbt_get_color_left(sibling
) == TRBT_BLACK
) ){
381 trbt_set_color(sibling
, TRBT_RED
);
382 trbt_set_color_right(sibling
, TRBT_BLACK
);
383 trbt_rotate_left(sibling
);
384 trbt_delete_case6(node
);
388 trbt_delete_case6(node
);
392 trbt_delete_case4(trbt_node_t
*node
)
394 trbt_node_t
*sibling
;
396 sibling
= trbt_sibling(node
);
397 if ( (trbt_get_color(node
->parent
) == TRBT_RED
)
398 &&(trbt_get_color(sibling
) == TRBT_BLACK
)
399 &&(trbt_get_color_left(sibling
) == TRBT_BLACK
)
400 &&(trbt_get_color_right(sibling
) == TRBT_BLACK
) ){
401 trbt_set_color(sibling
, TRBT_RED
);
402 trbt_set_color(node
->parent
, TRBT_BLACK
);
404 trbt_delete_case5(node
);
408 static void trbt_delete_case1(trbt_node_t
*node
);
411 trbt_delete_case3(trbt_node_t
*node
)
413 trbt_node_t
*sibling
;
415 sibling
= trbt_sibling(node
);
416 if ( (trbt_get_color(node
->parent
) == TRBT_BLACK
)
417 &&(trbt_get_color(sibling
) == TRBT_BLACK
)
418 &&(trbt_get_color_left(sibling
) == TRBT_BLACK
)
419 &&(trbt_get_color_right(sibling
) == TRBT_BLACK
) ){
420 trbt_set_color(sibling
, TRBT_RED
);
421 trbt_delete_case1(node
->parent
);
423 trbt_delete_case4(node
);
428 trbt_delete_case2(trbt_node_t
*node
)
430 trbt_node_t
*sibling
;
432 sibling
= trbt_sibling(node
);
433 if (trbt_get_color(sibling
) == TRBT_RED
) {
434 trbt_set_color(node
->parent
, TRBT_RED
);
435 trbt_set_color(sibling
, TRBT_BLACK
);
436 if (node
== node
->parent
->left
) {
437 trbt_rotate_left(node
->parent
);
439 trbt_rotate_right(node
->parent
);
442 trbt_delete_case3(node
);
446 trbt_delete_case1(trbt_node_t
*node
)
451 trbt_delete_case2(node
);
456 delete_node(trbt_node_t
*node
, bool from_destructor
)
458 trbt_node_t
*parent
, *child
, dc
;
459 trbt_node_t
*temp
= NULL
;
461 /* This node has two child nodes, then just copy the content
462 from the next smaller node with this node and delete the
464 The predecessor is guaranteed to have at most one child
465 node since its right arm must be NULL
466 (It must be NULL since we are its successor and we are above
469 if (node
->left
!= NULL
&& node
->right
!= NULL
) {
470 /* This node has two children, just copy the data */
471 /* find the predecessor */
474 while (temp
->right
!= NULL
) {
478 /* swap the predecessor data and key with the node to
481 node
->key32
= temp
->key32
;
482 node
->data
= temp
->data
;
483 /* now we let node hang off the new data */
484 talloc_steal(node
->data
, node
);
488 /* then delete the temp node.
489 this node is guaranteed to have at least one leaf
491 delete_node(temp
, from_destructor
);
496 /* There is at most one child to this node to be deleted */
502 /* If the node to be deleted did not have any child at all we
503 create a temporary dummy node for the child and mark it black.
504 Once the delete of the node is finished, we remove this dummy
505 node, which is simple to do since it is guaranteed that it will
506 still not have any children after the delete operation.
507 This is because we don't represent the leaf-nodes as actual nodes
508 in this implementation.
512 child
->tree
= node
->tree
;
515 child
->rb_color
=TRBT_BLACK
;
519 /* replace node with child */
520 parent
= trbt_parent(node
);
522 if (parent
->left
== node
) {
523 parent
->left
= child
;
525 parent
->right
= child
;
528 node
->tree
->root
= child
;
530 child
->parent
= node
->parent
;
533 if (node
->rb_color
== TRBT_BLACK
) {
534 if (trbt_get_color(child
) == TRBT_RED
) {
535 child
->rb_color
= TRBT_BLACK
;
537 trbt_delete_case1(child
);
541 /* If we had to create a temporary dummy node to represent a black
542 leaf child we now has to delete it.
543 This is simple since this dummy node originally had no children
544 and we are guaranteed that it will also not have any children
545 after the node has been deleted and any possible rotations
548 The only special case is if this was the last node of the tree
549 in which case we have to reset the root to NULL as well.
550 Othervise it is enough to just unlink the child from its new
554 if (child
->parent
== NULL
) {
555 node
->tree
->root
= NULL
;
556 } else if (child
== child
->parent
->left
) {
557 child
->parent
->left
= NULL
;
559 child
->parent
->right
= NULL
;
564 if (!from_destructor
) {
568 /* if we came from a destructor and temp!=NULL this means we
569 did the node-swap but now the tree still contains the old
570 node which was freed in the destructor. Not good.
572 if (from_destructor
&& temp
) {
573 temp
->key32
= node
->key32
;
574 temp
->rb_color
= node
->rb_color
;
576 temp
->data
= node
->data
;
577 talloc_steal(temp
->data
, temp
);
579 temp
->parent
= node
->parent
;
581 if (temp
->parent
->left
== node
) {
582 temp
->parent
->left
= temp
;
584 temp
->parent
->right
= temp
;
588 temp
->left
= node
->left
;
590 temp
->left
->parent
= temp
;
592 temp
->right
= node
->right
;
594 temp
->right
->parent
= temp
;
597 if (temp
->tree
->root
== node
) {
598 temp
->tree
->root
= temp
;
602 if ( (node
->tree
->flags
& TRBT_AUTOFREE
)
603 && (node
->tree
->root
== NULL
) ) {
604 talloc_free(node
->tree
);
611 destroy a node and remove it from its tree
613 static int node_destructor(trbt_node_t
*node
)
615 delete_node(node
, true);
620 static inline trbt_node_t
*
621 trbt_create_node(trbt_tree_t
*tree
, trbt_node_t
*parent
, uint32_t key
, void *data
)
625 node
=talloc_zero(tree
, trbt_node_t
);
626 NO_MEMORY_FATAL(node
);
629 node
->rb_color
=TRBT_BLACK
;
636 /* let this node hang off data so that it is removed when
639 talloc_steal(data
, node
);
640 talloc_set_destructor(node
, node_destructor
);
645 /* insert a new node in the tree.
646 if there is already a node with a matching key in the tree
647 we replace it with the new data and return a pointer to the old data
648 in case the caller wants to take any special action
651 trbt_insert32(trbt_tree_t
*tree
, uint32_t key
, void *data
)
657 /* is this the first node ?*/
659 node
= trbt_create_node(tree
, NULL
, key
, data
);
665 /* it was not the new root so walk the tree until we find where to
666 * insert this new leaf.
669 /* this node already exists, replace data and return the
672 if(key
==node
->key32
){
675 old_data
= node
->data
;
677 /* Let the node now be owned by the new data
678 so the node is freed when the enw data is released
680 talloc_steal(node
->data
, node
);
684 if(key
<node
->key32
) {
686 /* new node to the left */
687 trbt_node_t
*new_node
;
689 new_node
= trbt_create_node(tree
, node
, key
, data
);
698 if(key
>node
->key32
) {
700 /* new node to the right */
701 trbt_node_t
*new_node
;
703 new_node
= trbt_create_node(tree
, node
, key
, data
);
704 node
->right
=new_node
;
713 /* node will now point to the newly created node */
714 node
->rb_color
=TRBT_RED
;
715 trbt_insert_case1(tree
, node
);
720 trbt_lookup32(trbt_tree_t
*tree
, uint32_t key
)
727 if(key
==node
->key32
){
743 /* This deletes a node from the tree.
744 Note that this does not release the data that the node points to
747 trbt_delete32(trbt_tree_t
*tree
, uint32_t key
)
754 if(key
==node
->key32
){
755 delete_node(node
, false);
771 trbt_insert32_callback(trbt_tree_t
*tree
, uint32_t key
, void *(*callback
)(void *param
, void *data
), void *param
)
777 /* is this the first node ?*/
779 node
= trbt_create_node(tree
, NULL
, key
,
780 callback(param
, NULL
));
786 /* it was not the new root so walk the tree until we find where to
787 * insert this new leaf.
790 /* this node already exists, replace it
792 if(key
==node
->key32
){
793 node
->data
= callback(param
, node
->data
);
794 talloc_steal(node
->data
, node
);
798 if(key
<node
->key32
) {
800 /* new node to the left */
801 trbt_node_t
*new_node
;
803 new_node
= trbt_create_node(tree
, node
, key
,
804 callback(param
, NULL
));
813 if(key
>node
->key32
) {
815 /* new node to the right */
816 trbt_node_t
*new_node
;
818 new_node
= trbt_create_node(tree
, node
, key
,
819 callback(param
, NULL
));
820 node
->right
=new_node
;
829 /* node will now point to the newly created node */
830 node
->rb_color
=TRBT_RED
;
831 trbt_insert_case1(tree
, node
);
836 struct trbt_array_param
{
837 void *(*callback
)(void *param
, void *data
);
843 static void *array_insert_callback(void *p
, void *data
)
845 struct trbt_array_param
*param
= (struct trbt_array_param
*)p
;
846 trbt_tree_t
*tree
= NULL
;
849 /* if keylen has reached 0 we are done and can call the users
850 callback function with the users parameters
852 if (param
->keylen
== 0) {
853 return param
->callback(param
->param
, data
);
857 /* keylen is not zero yes so we must create/process more subtrees */
858 /* if data is NULL this means we did not yet have a subtree here
859 and we must create one.
862 /* create a new subtree and hang it off our current tree
863 set it to autofree so that the tree is freed when
864 the last node in it has been released.
866 tree
= trbt_create(param
->tree
, TRBT_AUTOFREE
);
868 /* we already have a subtree for this path */
869 tree
= (trbt_tree_t
*)data
;
872 trbt_insertarray32_callback(tree
, param
->keylen
, param
->key
, param
->callback
, param
->param
);
874 /* now return either the old tree we got in *data or the new tree
875 we created to our caller so he can update his pointer in his
876 tree to point to our subtree
883 /* insert into the tree using an array of uint32 as a key */
885 trbt_insertarray32_callback(trbt_tree_t
*tree
, uint32_t keylen
, uint32_t *key
, void *(*cb
)(void *param
, void *data
), void *pm
)
887 struct trbt_array_param tap
;
889 /* keylen-1 and key[1] since the call to insert32 will consume the
890 first part of the key.
894 tap
.keylen
= keylen
-1;
898 trbt_insert32_callback(tree
, key
[0], array_insert_callback
, &tap
);
901 /* lookup the tree using an array of uint32 as a key */
903 trbt_lookuparray32(trbt_tree_t
*tree
, uint32_t keylen
, uint32_t *key
)
905 /* if keylen is 1 we can do a regular lookup and return this to the
909 return trbt_lookup32(tree
, key
[0]);
912 /* we need to lookup the next subtree */
913 tree
= trbt_lookup32(tree
, key
[0]);
915 /* the key does not exist, return NULL */
919 /* now lookup the next part of the key in our new tree */
920 return trbt_lookuparray32(tree
, keylen
-1, &key
[1]);
924 /* traverse a tree starting at node */
926 trbt_traversearray32_node(trbt_node_t
*node
, uint32_t keylen
,
927 int (*callback
)(void *param
, void *data
),
930 trbt_node_t
*left
= node
->left
;
931 trbt_node_t
*right
= node
->right
;
935 ret
= trbt_traversearray32_node(left
, keylen
, callback
, param
);
941 /* this is the smallest node in this subtree
942 if keylen is 0 this means we can just call the callback
943 otherwise we must pull the next subtree and traverse that one as well
948 ret
= callback(param
, node
->data
);
955 ret
= trbt_traversearray32(node
->data
, keylen
, callback
, param
);
964 ret
= trbt_traversearray32_node(right
, keylen
, callback
, param
);
974 /* traverse the tree using an array of uint32 as a key */
976 trbt_traversearray32(trbt_tree_t
*tree
, uint32_t keylen
,
977 int (*callback
)(void *param
, void *data
),
991 return trbt_traversearray32_node(node
, keylen
-1, callback
, param
);
995 /* this function will return the first node in a tree where
996 the key is an array of uint32_t
999 trbt_findfirstarray32(trbt_tree_t
*tree
, uint32_t keylen
)
1016 while (node
->left
) {
1020 /* we found our node so return the data */
1025 /* we are still traversing subtrees so find the first node in the
1028 return trbt_findfirstarray32(node
->data
, keylen
-1);
1033 static void printtree(trbt_node_t
*node
, int levels
)
1036 if(node
==NULL
)return;
1037 printtree(node
->left
, levels
+1);
1039 for(i
=0;i
<levels
;i
++)printf(" ");
1040 printf("key:%d COLOR:%s (node:%p parent:%p left:%p right:%p)\n",node
->key32
,node
->rb_color
==TRBT_BLACK
?"BLACK":"RED", node
, node
->parent
, node
->left
, node
->right
);
1042 printtree(node
->right
, levels
+1);
1046 void print_tree(trbt_tree_t
*tree
)
1048 if(tree
->root
==NULL
){
1049 printf("tree is empty\n");
1053 printtree(tree
->root
->left
, 1);
1054 printf("root node key:%d COLOR:%s (node:%p left:%p right:%p)\n",tree
->root
->key32
,tree
->root
->rb_color
==TRBT_BLACK
?"BLACK":"RED", tree
->root
, tree
->root
->left
, tree
->root
->right
);
1055 printtree(tree
->root
->right
, 1);
1068 tree
=trbt_create(talloc_new(NULL
), 0);
1071 printf("adding node %i\n",i
);
1072 trbt_insert32(tree
, i
, NULL
);
1075 printf("deleting node %i\n",3);
1076 trbt_delete32(tree
, 3);
1079 printf("deleting node %i\n",i
);
1080 trbt_delete32(tree
, i
);
1087 printf("iteration : %d\n",cnt
);
1089 printf("adding node %i\n",i
);
1090 trbt_insert32(tree
, i
, NULL
);
1094 printf("deleting node %i\n",i
);
1095 trbt_delete32(tree
, i
);
1101 #endif /* TEST_RB_TREE */