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/>.
19 #include <ccan/rbtree/rbtree.h>
22 tree_destructor_traverse_node(trbt_node_t *node)
24 talloc_set_destructor(node, NULL);
26 tree_destructor_traverse_node(node->left);
29 tree_destructor_traverse_node(node->right);
35 destroy a tree and remove all its nodes
37 static int tree_destructor(trbt_tree_t *tree)
50 /* traverse the tree and remove the node destructor then delete it.
51 we don't want to use the existing destructor for the node
52 since that will remove the nodes one by one from the tree.
53 since the entire tree will be completely destroyed we don't care
54 if it is inconsistent or unbalanced while freeing the
57 tree_destructor_traverse_node(node);
63 /* create a red black tree */
65 trbt_create(TALLOC_CTX *memctx, uint32_t flags)
69 tree = talloc_zero(memctx, trbt_tree_t);
71 fprintf(stderr, "Failed to allocate memory for rb tree\n");
75 /* If the tree is freed, we must walk over all entries and steal the
76 node from the stored data pointer and release the node.
77 Note, when we free the tree we only free the tree and not any of
78 the data stored in the tree.
80 talloc_set_destructor(tree, tree_destructor);
86 static inline trbt_node_t *
87 trbt_parent(trbt_node_t *node)
92 static inline trbt_node_t *
93 trbt_grandparent(trbt_node_t *node)
97 parent=trbt_parent(node);
99 return parent->parent;
104 static inline trbt_node_t *
105 trbt_uncle(trbt_node_t *node)
107 trbt_node_t *parent, *grandparent;
109 parent=trbt_parent(node);
113 grandparent=trbt_parent(parent);
117 if(parent==grandparent->left){
118 return grandparent->right;
120 return grandparent->left;
124 static inline void trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node);
125 static inline void trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node);
128 trbt_rotate_left(trbt_node_t *node)
130 trbt_tree_t *tree = node->tree;
133 if(node->parent->left==node){
134 node->parent->left=node->right;
136 node->parent->right=node->right;
139 tree->root=node->right;
141 node->right->parent=node->parent;
142 node->parent=node->right;
143 node->right=node->right->left;
145 node->right->parent=node;
147 node->parent->left=node;
151 trbt_rotate_right(trbt_node_t *node)
153 trbt_tree_t *tree = node->tree;
156 if(node->parent->left==node){
157 node->parent->left=node->left;
159 node->parent->right=node->left;
162 tree->root=node->left;
164 node->left->parent=node->parent;
165 node->parent=node->left;
166 node->left=node->left->right;
168 node->left->parent=node;
170 node->parent->right=node;
173 /* NULL nodes are black by definition */
174 static inline int trbt_get_color(trbt_node_t *node)
179 return node->rb_color;
181 static inline int trbt_get_color_left(trbt_node_t *node)
186 if (node->left==NULL) {
189 return node->left->rb_color;
191 static inline int trbt_get_color_right(trbt_node_t *node)
196 if (node->right==NULL) {
199 return node->right->rb_color;
201 /* setting a NULL node to black is a nop */
202 static inline void trbt_set_color(trbt_node_t *node, int color)
204 if ( (node==NULL) && (color==TRBT_BLACK) ) {
207 node->rb_color = color;
209 static inline void trbt_set_color_left(trbt_node_t *node, int color)
211 if ( ((node==NULL)||(node->left==NULL)) && (color==TRBT_BLACK) ) {
214 node->left->rb_color = color;
216 static inline void trbt_set_color_right(trbt_node_t *node, int color)
218 if ( ((node==NULL)||(node->right==NULL)) && (color==TRBT_BLACK) ) {
221 node->right->rb_color = color;
225 trbt_insert_case5(trbt_node_t *node)
227 trbt_node_t *grandparent;
230 parent=trbt_parent(node);
231 grandparent=trbt_parent(parent);
232 parent->rb_color=TRBT_BLACK;
233 grandparent->rb_color=TRBT_RED;
234 if( (node==parent->left) && (parent==grandparent->left) ){
235 trbt_rotate_right(grandparent);
237 trbt_rotate_left(grandparent);
242 trbt_insert_case4(trbt_node_t *node)
244 trbt_node_t *grandparent;
247 parent=trbt_parent(node);
248 grandparent=trbt_parent(parent);
252 if( (node==parent->right) && (parent==grandparent->left) ){
253 trbt_rotate_left(parent);
255 } else if( (node==parent->left) && (parent==grandparent->right) ){
256 trbt_rotate_right(parent);
259 trbt_insert_case5(node);
263 trbt_insert_case3(trbt_tree_t *tree, trbt_node_t *node)
265 trbt_node_t *grandparent;
269 uncle=trbt_uncle(node);
270 if(uncle && (uncle->rb_color==TRBT_RED)){
271 parent=trbt_parent(node);
272 parent->rb_color=TRBT_BLACK;
273 uncle->rb_color=TRBT_BLACK;
274 grandparent=trbt_grandparent(node);
275 grandparent->rb_color=TRBT_RED;
276 trbt_insert_case1(tree, grandparent);
278 trbt_insert_case4(node);
283 trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node)
287 parent=trbt_parent(node);
288 /* parent is always non-NULL here */
289 if(parent->rb_color==TRBT_BLACK){
292 trbt_insert_case3(tree, node);
296 trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node)
300 parent=trbt_parent(node);
302 node->rb_color=TRBT_BLACK;
305 trbt_insert_case2(tree, node);
308 static inline trbt_node_t *
309 trbt_sibling(trbt_node_t *node)
313 parent=trbt_parent(node);
318 if (node == parent->left) {
319 return parent->right;
326 trbt_delete_case6(trbt_node_t *node)
328 trbt_node_t *sibling, *parent;
330 sibling = trbt_sibling(node);
331 parent = trbt_parent(node);
333 trbt_set_color(sibling, parent->rb_color);
334 trbt_set_color(parent, TRBT_BLACK);
335 if (node == parent->left) {
336 trbt_set_color_right(sibling, TRBT_BLACK);
337 trbt_rotate_left(parent);
339 trbt_set_color_left(sibling, TRBT_BLACK);
340 trbt_rotate_right(parent);
346 trbt_delete_case5(trbt_node_t *node)
348 trbt_node_t *parent, *sibling;
350 parent = trbt_parent(node);
351 sibling = trbt_sibling(node);
352 if ( (node == parent->left)
353 &&(trbt_get_color(sibling) == TRBT_BLACK)
354 &&(trbt_get_color_left(sibling) == TRBT_RED)
355 &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){
356 trbt_set_color(sibling, TRBT_RED);
357 trbt_set_color_left(sibling, TRBT_BLACK);
358 trbt_rotate_right(sibling);
359 trbt_delete_case6(node);
362 if ( (node == parent->right)
363 &&(trbt_get_color(sibling) == TRBT_BLACK)
364 &&(trbt_get_color_right(sibling) == TRBT_RED)
365 &&(trbt_get_color_left(sibling) == TRBT_BLACK) ){
366 trbt_set_color(sibling, TRBT_RED);
367 trbt_set_color_right(sibling, TRBT_BLACK);
368 trbt_rotate_left(sibling);
369 trbt_delete_case6(node);
373 trbt_delete_case6(node);
377 trbt_delete_case4(trbt_node_t *node)
379 trbt_node_t *sibling;
381 sibling = trbt_sibling(node);
382 if ( (trbt_get_color(node->parent) == TRBT_RED)
383 &&(trbt_get_color(sibling) == TRBT_BLACK)
384 &&(trbt_get_color_left(sibling) == TRBT_BLACK)
385 &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){
386 trbt_set_color(sibling, TRBT_RED);
387 trbt_set_color(node->parent, TRBT_BLACK);
389 trbt_delete_case5(node);
393 static void trbt_delete_case1(trbt_node_t *node);
396 trbt_delete_case3(trbt_node_t *node)
398 trbt_node_t *sibling;
400 sibling = trbt_sibling(node);
401 if ( (trbt_get_color(node->parent) == TRBT_BLACK)
402 &&(trbt_get_color(sibling) == TRBT_BLACK)
403 &&(trbt_get_color_left(sibling) == TRBT_BLACK)
404 &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){
405 trbt_set_color(sibling, TRBT_RED);
406 trbt_delete_case1(node->parent);
408 trbt_delete_case4(node);
413 trbt_delete_case2(trbt_node_t *node)
415 trbt_node_t *sibling;
417 sibling = trbt_sibling(node);
418 if (trbt_get_color(sibling) == TRBT_RED) {
419 trbt_set_color(node->parent, TRBT_RED);
420 trbt_set_color(sibling, TRBT_BLACK);
421 if (node == node->parent->left) {
422 trbt_rotate_left(node->parent);
424 trbt_rotate_right(node->parent);
427 trbt_delete_case3(node);
431 trbt_delete_case1(trbt_node_t *node)
436 trbt_delete_case2(node);
441 delete_node(trbt_node_t *node)
443 trbt_node_t *parent, *child, dc;
444 trbt_node_t *temp = NULL;
446 /* This node has two child nodes, then just copy the content
447 from the next smaller node with this node and delete the
449 The predecessor is guaranteed to have at most one child
450 node since its right arm must be NULL
451 (It must be NULL since we are its sucessor and we are above
454 if (node->left != NULL && node->right != NULL) {
455 /* This node has two children, just copy the data */
456 /* find the predecessor */
459 while (temp->right != NULL) {
463 /* swap the predecessor data and key with the node to
466 node->key32 = temp->key32;
467 node->data = temp->data;
468 /* now we let node hang off the new data */
469 talloc_steal(node->data, node);
473 /* then delete the temp node.
474 this node is guaranteed to have at least one leaf
481 /* There is at most one child to this node to be deleted */
487 /* If the node to be deleted did not have any child at all we
488 create a temporary dummy node for the child and mark it black.
489 Once the delete of the node is finished, we remove this dummy
490 node, which is simple to do since it is guaranteed that it will
491 still not have any children after the delete operation.
492 This is because we don't represent the leaf-nodes as actual nodes
493 in this implementation.
497 child->tree = node->tree;
500 child->rb_color=TRBT_BLACK;
504 /* replace node with child */
505 parent = trbt_parent(node);
507 if (parent->left == node) {
508 parent->left = child;
510 parent->right = child;
513 node->tree->root = child;
515 child->parent = node->parent;
518 if (node->rb_color == TRBT_BLACK) {
519 if (trbt_get_color(child) == TRBT_RED) {
520 child->rb_color = TRBT_BLACK;
522 trbt_delete_case1(child);
526 /* If we had to create a temporary dummy node to represent a black
527 leaf child we now has to delete it.
528 This is simple since this dummy node originally had no children
529 and we are guaranteed that it will also not have any children
530 after the node has been deleted and any possible rotations
533 The only special case is if this was the last node of the tree
534 in which case we have to reset the root to NULL as well.
535 Othervise it is enough to just unlink the child from its new
539 if (child->parent == NULL) {
540 node->tree->root = NULL;
541 } else if (child == child->parent->left) {
542 child->parent->left = NULL;
544 child->parent->right = NULL;
549 /* if we came from a destructor and temp!=NULL this means we
550 did the node-swap but now the tree still contains the old
551 node which was freed in the destructor. Not good.
554 temp->key32 = node->key32;
555 temp->rb_color = node->rb_color;
557 temp->data = node->data;
558 talloc_steal(temp->data, temp);
560 temp->parent = node->parent;
562 if (temp->parent->left == node) {
563 temp->parent->left = temp;
565 temp->parent->right = temp;
569 temp->left = node->left;
571 temp->left->parent = temp;
573 temp->right = node->right;
575 temp->right->parent = temp;
578 if (temp->tree->root == node) {
579 temp->tree->root = temp;
583 if ( (node->tree->flags & TRBT_AUTOFREE)
584 && (node->tree->root == NULL) ) {
585 talloc_free(node->tree);
592 destroy a node and remove it from its tree
594 static int node_destructor(trbt_node_t *node)
601 static inline trbt_node_t *
602 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
606 node=talloc_zero(tree, trbt_node_t);
608 fprintf(stderr, "Failed to allocate memory for rb node\n");
613 node->rb_color=TRBT_BLACK;
620 /* let this node hang off data so that it is removed when
623 talloc_steal(data, node);
624 talloc_set_destructor(node, node_destructor);
629 /* insert a new node in the tree.
630 if there is already a node with a matching key in the tree
631 we replace it with the new data and return a pointer to the old data
632 in case the caller wants to take any special action
635 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
641 /* is this the first node ?*/
643 node = trbt_create_node(tree, NULL, key, data);
649 /* it was not the new root so walk the tree until we find where to
650 * insert this new leaf.
653 /* this node already exists, replace data and return the
656 if(key==node->key32){
659 old_data = node->data;
661 /* Let the node now be owned by the new data
662 so the node is freed when the enw data is released
664 talloc_steal(node->data, node);
668 if(key<node->key32) {
670 /* new node to the left */
671 trbt_node_t *new_node;
673 new_node = trbt_create_node(tree, node, key, data);
684 if(key>node->key32) {
686 /* new node to the right */
687 trbt_node_t *new_node;
689 new_node = trbt_create_node(tree, node, key, data);
692 node->right=new_node;
701 /* node will now point to the newly created node */
702 node->rb_color=TRBT_RED;
703 trbt_insert_case1(tree, node);
708 trbt_lookup32(trbt_tree_t *tree, uint32_t key)
715 if(key==node->key32){
731 /* This deletes a node from the tree.
732 Note that this does not release the data that the node points to
735 trbt_delete32(trbt_tree_t *tree, uint32_t key)
742 if(key==node->key32){
759 trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
765 /* is this the first node ?*/
767 node = trbt_create_node(tree, NULL, key,
768 callback(param, NULL));
774 /* it was not the new root so walk the tree until we find where to
775 * insert this new leaf.
778 /* this node already exists, replace it
780 if(key==node->key32){
781 node->data = callback(param, node->data);
782 talloc_steal(node->data, node);
786 if(key<node->key32) {
788 /* new node to the left */
789 trbt_node_t *new_node;
791 new_node = trbt_create_node(tree, node, key,
792 callback(param, NULL));
801 if(key>node->key32) {
803 /* new node to the right */
804 trbt_node_t *new_node;
806 new_node = trbt_create_node(tree, node, key,
807 callback(param, NULL));
808 node->right=new_node;
817 /* node will now point to the newly created node */
818 node->rb_color=TRBT_RED;
819 trbt_insert_case1(tree, node);
824 struct trbt_array_param {
825 void *(*callback)(void *param, void *data);
831 static void *array_insert_callback(void *p, void *data)
833 struct trbt_array_param *param = (struct trbt_array_param *)p;
834 trbt_tree_t *tree = NULL;
837 /* if keylen has reached 0 we are done and can call the users
838 callback function with the users parameters
840 if (param->keylen == 0) {
841 return param->callback(param->param, data);
845 /* keylen is not zero yes so we must create/process more subtrees */
846 /* if data is NULL this means we did not yet have a subtree here
847 and we must create one.
850 /* create a new subtree and hang it off our current tree
851 set it to autofree so that the tree is freed when
852 the last node in it has been released.
854 tree = trbt_create(param->tree, TRBT_AUTOFREE);
856 /* we already have a subtree for this path */
857 tree = (trbt_tree_t *)data;
860 trbt_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param);
862 /* now return either the old tree we got in *data or the new tree
863 we created to our caller so he can update his pointer in his
864 tree to point to our subtree
871 /* insert into the tree using an array of uint32 as a key */
873 trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm)
875 struct trbt_array_param tap;
877 /* keylen-1 and key[1] since the call to insert32 will consume the
878 first part of the key.
882 tap.keylen = keylen-1;
886 trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
889 /* lookup the tree using an array of uint32 as a key */
891 trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
893 /* if keylen is 1 we can do a regular lookup and return this to the
897 return trbt_lookup32(tree, key[0]);
900 /* we need to lookup the next subtree */
901 tree = trbt_lookup32(tree, key[0]);
903 /* the key does not exist, return NULL */
907 /* now lookup the next part of the key in our new tree */
908 return trbt_lookuparray32(tree, keylen-1, &key[1]);
912 /* traverse a tree starting at node */
914 trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
915 void (*callback)(void *param, void *data),
919 trbt_traversearray32_node(node->left, keylen, callback, param);
922 /* this is the smallest node in this subtree
923 if keylen is 0 this means we can just call the callback
924 otherwise we must pull the next subtree and traverse that one as well
927 callback(param, node->data);
929 trbt_traversearray32(node->data, keylen, callback, param);
933 trbt_traversearray32_node(node->right, keylen, callback, param);
938 /* traverse the tree using an array of uint32 as a key */
940 trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen,
941 void (*callback)(void *param, void *data),
955 trbt_traversearray32_node(node, keylen-1, callback, param);
959 /* this function will return the first node in a tree where
960 the key is an array of uint32_t
963 trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
984 /* we found our node so return the data */
989 /* we are still traversing subtrees so find the first node in the
992 return trbt_findfirstarray32(node->data, keylen-1);