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(TALLOC_CTX *mem_ctx, trbt_node_t *node)
24 talloc_set_destructor(node, NULL);
26 tree_destructor_traverse_node(mem_ctx, node->left);
29 tree_destructor_traverse_node(mem_ctx, node->right);
31 talloc_steal(mem_ctx, node);
35 destroy a tree and remove all its nodes
37 static int tree_destructor(trbt_tree_t *tree)
51 /* traverse the tree and remove the node destructor and steal
52 the node to the temporary context.
53 we dont want to use the existing destructor for the node
54 since that will remove the nodes one by one from the tree.
55 since the entire tree will be completely destroyed we dont care
56 if it is inconsistent or unbalanced while freeing the
59 tmp_ctx = talloc_new(NULL);
60 tree_destructor_traverse_node(tmp_ctx, node);
67 /* create a red black tree */
69 trbt_create(TALLOC_CTX *memctx, uint32_t flags)
73 tree = talloc_zero(memctx, trbt_tree_t);
75 fprintf(stderr, "Failed to allocate memory for rb tree\n");
79 /* If the tree is freed, we must walk over all entries and steal the
80 node from the stored data pointer and release the node.
81 Note, when we free the tree we only free the tree and not any of
82 the data stored in the tree.
84 talloc_set_destructor(tree, tree_destructor);
90 static inline trbt_node_t *
91 trbt_parent(trbt_node_t *node)
96 static inline trbt_node_t *
97 trbt_grandparent(trbt_node_t *node)
101 parent=trbt_parent(node);
103 return parent->parent;
108 static inline trbt_node_t *
109 trbt_uncle(trbt_node_t *node)
111 trbt_node_t *parent, *grandparent;
113 parent=trbt_parent(node);
117 grandparent=trbt_parent(parent);
121 if(parent==grandparent->left){
122 return grandparent->right;
124 return grandparent->left;
128 static inline void trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node);
129 static inline void trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node);
132 trbt_rotate_left(trbt_node_t *node)
134 trbt_tree_t *tree = node->tree;
137 if(node->parent->left==node){
138 node->parent->left=node->right;
140 node->parent->right=node->right;
143 tree->root=node->right;
145 node->right->parent=node->parent;
146 node->parent=node->right;
147 node->right=node->right->left;
149 node->right->parent=node;
151 node->parent->left=node;
155 trbt_rotate_right(trbt_node_t *node)
157 trbt_tree_t *tree = node->tree;
160 if(node->parent->left==node){
161 node->parent->left=node->left;
163 node->parent->right=node->left;
166 tree->root=node->left;
168 node->left->parent=node->parent;
169 node->parent=node->left;
170 node->left=node->left->right;
172 node->left->parent=node;
174 node->parent->right=node;
177 /* NULL nodes are black by definition */
178 static inline int trbt_get_color(trbt_node_t *node)
183 return node->rb_color;
185 static inline int trbt_get_color_left(trbt_node_t *node)
190 if (node->left==NULL) {
193 return node->left->rb_color;
195 static inline int trbt_get_color_right(trbt_node_t *node)
200 if (node->right==NULL) {
203 return node->right->rb_color;
205 /* setting a NULL node to black is a nop */
206 static inline void trbt_set_color(trbt_node_t *node, int color)
208 if ( (node==NULL) && (color==TRBT_BLACK) ) {
211 node->rb_color = color;
213 static inline void trbt_set_color_left(trbt_node_t *node, int color)
215 if ( ((node==NULL)||(node->left==NULL)) && (color==TRBT_BLACK) ) {
218 node->left->rb_color = color;
220 static inline void trbt_set_color_right(trbt_node_t *node, int color)
222 if ( ((node==NULL)||(node->right==NULL)) && (color==TRBT_BLACK) ) {
225 node->right->rb_color = color;
229 trbt_insert_case5(trbt_node_t *node)
231 trbt_node_t *grandparent;
234 parent=trbt_parent(node);
235 grandparent=trbt_parent(parent);
236 parent->rb_color=TRBT_BLACK;
237 grandparent->rb_color=TRBT_RED;
238 if( (node==parent->left) && (parent==grandparent->left) ){
239 trbt_rotate_right(grandparent);
241 trbt_rotate_left(grandparent);
246 trbt_insert_case4(trbt_node_t *node)
248 trbt_node_t *grandparent;
251 parent=trbt_parent(node);
252 grandparent=trbt_parent(parent);
256 if( (node==parent->right) && (parent==grandparent->left) ){
257 trbt_rotate_left(parent);
259 } else if( (node==parent->left) && (parent==grandparent->right) ){
260 trbt_rotate_right(parent);
263 trbt_insert_case5(node);
267 trbt_insert_case3(trbt_tree_t *tree, trbt_node_t *node)
269 trbt_node_t *grandparent;
273 uncle=trbt_uncle(node);
274 if(uncle && (uncle->rb_color==TRBT_RED)){
275 parent=trbt_parent(node);
276 parent->rb_color=TRBT_BLACK;
277 uncle->rb_color=TRBT_BLACK;
278 grandparent=trbt_grandparent(node);
279 grandparent->rb_color=TRBT_RED;
280 trbt_insert_case1(tree, grandparent);
282 trbt_insert_case4(node);
287 trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node)
291 parent=trbt_parent(node);
292 /* parent is always non-NULL here */
293 if(parent->rb_color==TRBT_BLACK){
296 trbt_insert_case3(tree, node);
300 trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node)
304 parent=trbt_parent(node);
306 node->rb_color=TRBT_BLACK;
309 trbt_insert_case2(tree, node);
312 static inline trbt_node_t *
313 trbt_sibling(trbt_node_t *node)
317 parent=trbt_parent(node);
322 if (node == parent->left) {
323 return parent->right;
330 trbt_delete_case6(trbt_node_t *node)
332 trbt_node_t *sibling, *parent;
334 sibling = trbt_sibling(node);
335 parent = trbt_parent(node);
337 trbt_set_color(sibling, parent->rb_color);
338 trbt_set_color(parent, TRBT_BLACK);
339 if (node == parent->left) {
340 trbt_set_color_right(sibling, TRBT_BLACK);
341 trbt_rotate_left(parent);
343 trbt_set_color_left(sibling, TRBT_BLACK);
344 trbt_rotate_right(parent);
350 trbt_delete_case5(trbt_node_t *node)
352 trbt_node_t *parent, *sibling;
354 parent = trbt_parent(node);
355 sibling = trbt_sibling(node);
356 if ( (node == parent->left)
357 &&(trbt_get_color(sibling) == TRBT_BLACK)
358 &&(trbt_get_color_left(sibling) == TRBT_RED)
359 &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){
360 trbt_set_color(sibling, TRBT_RED);
361 trbt_set_color_left(sibling, TRBT_BLACK);
362 trbt_rotate_right(sibling);
363 trbt_delete_case6(node);
366 if ( (node == parent->right)
367 &&(trbt_get_color(sibling) == TRBT_BLACK)
368 &&(trbt_get_color_right(sibling) == TRBT_RED)
369 &&(trbt_get_color_left(sibling) == TRBT_BLACK) ){
370 trbt_set_color(sibling, TRBT_RED);
371 trbt_set_color_right(sibling, TRBT_BLACK);
372 trbt_rotate_left(sibling);
373 trbt_delete_case6(node);
377 trbt_delete_case6(node);
381 trbt_delete_case4(trbt_node_t *node)
383 trbt_node_t *sibling;
385 sibling = trbt_sibling(node);
386 if ( (trbt_get_color(node->parent) == TRBT_RED)
387 &&(trbt_get_color(sibling) == TRBT_BLACK)
388 &&(trbt_get_color_left(sibling) == TRBT_BLACK)
389 &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){
390 trbt_set_color(sibling, TRBT_RED);
391 trbt_set_color(node->parent, TRBT_BLACK);
393 trbt_delete_case5(node);
397 static void trbt_delete_case1(trbt_node_t *node);
400 trbt_delete_case3(trbt_node_t *node)
402 trbt_node_t *sibling;
404 sibling = trbt_sibling(node);
405 if ( (trbt_get_color(node->parent) == TRBT_BLACK)
406 &&(trbt_get_color(sibling) == TRBT_BLACK)
407 &&(trbt_get_color_left(sibling) == TRBT_BLACK)
408 &&(trbt_get_color_right(sibling) == TRBT_BLACK) ){
409 trbt_set_color(sibling, TRBT_RED);
410 trbt_delete_case1(node->parent);
412 trbt_delete_case4(node);
417 trbt_delete_case2(trbt_node_t *node)
419 trbt_node_t *sibling;
421 sibling = trbt_sibling(node);
422 if (trbt_get_color(sibling) == TRBT_RED) {
423 trbt_set_color(node->parent, TRBT_RED);
424 trbt_set_color(sibling, TRBT_BLACK);
425 if (node == node->parent->left) {
426 trbt_rotate_left(node->parent);
428 trbt_rotate_right(node->parent);
431 trbt_delete_case3(node);
435 trbt_delete_case1(trbt_node_t *node)
440 trbt_delete_case2(node);
445 delete_node(trbt_node_t *node)
447 trbt_node_t *parent, *child, dc;
448 trbt_node_t *temp = NULL;
450 /* This node has two child nodes, then just copy the content
451 from the next smaller node with this node and delete the
453 The predecessor is guaranteed to have at most one child
454 node since its right arm must be NULL
455 (It must be NULL since we are its sucessor and we are above
458 if (node->left != NULL && node->right != NULL) {
459 /* This node has two children, just copy the data */
460 /* find the predecessor */
463 while (temp->right != NULL) {
467 /* swap the predecessor data and key with the node to
470 node->key32 = temp->key32;
471 node->data = temp->data;
472 /* now we let node hang off the new data */
473 talloc_steal(node->data, node);
477 /* then delete the temp node.
478 this node is guaranteed to have at least one leaf
485 /* There is at most one child to this node to be deleted */
491 /* If the node to be deleted did not have any child at all we
492 create a temporary dummy node for the child and mark it black.
493 Once the delete of the node is finished, we remove this dummy
494 node, which is simple to do since it is guaranteed that it will
495 still not have any children after the delete operation.
496 This is because we dont represent the leaf-nodes as actual nodes
497 in this implementation.
501 child->tree = node->tree;
504 child->rb_color=TRBT_BLACK;
508 /* replace node with child */
509 parent = trbt_parent(node);
511 if (parent->left == node) {
512 parent->left = child;
514 parent->right = child;
517 node->tree->root = child;
519 child->parent = node->parent;
522 if (node->rb_color == TRBT_BLACK) {
523 if (trbt_get_color(child) == TRBT_RED) {
524 child->rb_color = TRBT_BLACK;
526 trbt_delete_case1(child);
530 /* If we had to create a temporary dummy node to represent a black
531 leaf child we now has to delete it.
532 This is simple since this dummy node originally had no children
533 and we are guaranteed that it will also not have any children
534 after the node has been deleted and any possible rotations
537 The only special case is if this was the last node of the tree
538 in which case we have to reset the root to NULL as well.
539 Othervise it is enough to just unlink the child from its new
543 if (child->parent == NULL) {
544 node->tree->root = NULL;
545 } else if (child == child->parent->left) {
546 child->parent->left = NULL;
548 child->parent->right = NULL;
553 /* if we came from a destructor and temp!=NULL this means we
554 did the node-swap but now the tree still contains the old
555 node which was freed in the destructor. Not good.
558 temp->key32 = node->key32;
559 temp->rb_color = node->rb_color;
561 temp->data = node->data;
562 talloc_steal(temp->data, temp);
564 temp->parent = node->parent;
566 if (temp->parent->left == node) {
567 temp->parent->left = temp;
569 temp->parent->right = temp;
573 temp->left = node->left;
575 temp->left->parent = temp;
577 temp->right = node->right;
579 temp->right->parent = temp;
582 if (temp->tree->root == node) {
583 temp->tree->root = temp;
587 if ( (node->tree->flags & TRBT_AUTOFREE)
588 && (node->tree->root == NULL) ) {
589 talloc_free(node->tree);
596 destroy a node and remove it from its tree
598 static int node_destructor(trbt_node_t *node)
605 static inline trbt_node_t *
606 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
610 node=talloc_zero(tree, trbt_node_t);
612 fprintf(stderr, "Failed to allocate memory for rb node\n");
617 node->rb_color=TRBT_BLACK;
624 /* let this node hang off data so that it is removed when
627 talloc_steal(data, node);
628 talloc_set_destructor(node, node_destructor);
633 /* insert a new node in the tree.
634 if there is already a node with a matching key in the tree
635 we replace it with the new data and return a pointer to the old data
636 in case the caller wants to take any special action
639 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
645 /* is this the first node ?*/
647 node = trbt_create_node(tree, NULL, key, data);
653 /* it was not the new root so walk the tree until we find where to
654 * insert this new leaf.
657 /* this node already exists, replace data and return the
660 if(key==node->key32){
663 old_data = node->data;
665 /* Let the node now be owned by the new data
666 so the node is freed when the enw data is released
668 talloc_steal(node->data, node);
672 if(key<node->key32) {
674 /* new node to the left */
675 trbt_node_t *new_node;
677 new_node = trbt_create_node(tree, node, key, data);
686 if(key>node->key32) {
688 /* new node to the right */
689 trbt_node_t *new_node;
691 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);