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, int from_destructor)
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
480 delete_node(temp, from_destructor);
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 (!from_destructor) {
557 /* if we came from a destructor and temp!=NULL this means we
558 did the node-swap but now the tree still contains the old
559 node which was freed in the destructor. Not good.
561 if (from_destructor && temp) {
562 temp->key32 = node->key32;
563 temp->rb_color = node->rb_color;
565 temp->data = node->data;
566 talloc_steal(temp->data, temp);
568 temp->parent = node->parent;
570 if (temp->parent->left == node) {
571 temp->parent->left = temp;
573 temp->parent->right = temp;
577 temp->left = node->left;
579 temp->left->parent = temp;
581 temp->right = node->right;
583 temp->right->parent = temp;
586 if (temp->tree->root == node) {
587 temp->tree->root = temp;
591 if ( (node->tree->flags & TRBT_AUTOFREE)
592 && (node->tree->root == NULL) ) {
593 talloc_free(node->tree);
600 destroy a node and remove it from its tree
602 static int node_destructor(trbt_node_t *node)
604 delete_node(node, 1);
609 static inline trbt_node_t *
610 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
614 node=talloc_zero(tree, trbt_node_t);
616 fprintf(stderr, "Failed to allocate memory for rb node\n");
621 node->rb_color=TRBT_BLACK;
628 /* let this node hang off data so that it is removed when
631 talloc_steal(data, node);
632 talloc_set_destructor(node, node_destructor);
637 /* insert a new node in the tree.
638 if there is already a node with a matching key in the tree
639 we replace it with the new data and return a pointer to the old data
640 in case the caller wants to take any special action
643 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
649 /* is this the first node ?*/
651 node = trbt_create_node(tree, NULL, key, data);
657 /* it was not the new root so walk the tree until we find where to
658 * insert this new leaf.
661 /* this node already exists, replace data and return the
664 if(key==node->key32){
667 old_data = node->data;
669 /* Let the node now be owned by the new data
670 so the node is freed when the enw data is released
672 talloc_steal(node->data, node);
676 if(key<node->key32) {
678 /* new node to the left */
679 trbt_node_t *new_node;
681 new_node = trbt_create_node(tree, node, key, data);
690 if(key>node->key32) {
692 /* new node to the right */
693 trbt_node_t *new_node;
695 new_node = trbt_create_node(tree, node, key, data);
696 node->right=new_node;
705 /* node will now point to the newly created node */
706 node->rb_color=TRBT_RED;
707 trbt_insert_case1(tree, node);
712 trbt_lookup32(trbt_tree_t *tree, uint32_t key)
719 if(key==node->key32){
735 /* This deletes a node from the tree.
736 Note that this does not release the data that the node points to
739 trbt_delete32(trbt_tree_t *tree, uint32_t key)
746 if(key==node->key32){
747 delete_node(node, 0);
763 trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
769 /* is this the first node ?*/
771 node = trbt_create_node(tree, NULL, key,
772 callback(param, NULL));
778 /* it was not the new root so walk the tree until we find where to
779 * insert this new leaf.
782 /* this node already exists, replace it
784 if(key==node->key32){
785 node->data = callback(param, node->data);
786 talloc_steal(node->data, node);
790 if(key<node->key32) {
792 /* new node to the left */
793 trbt_node_t *new_node;
795 new_node = trbt_create_node(tree, node, key,
796 callback(param, NULL));
805 if(key>node->key32) {
807 /* new node to the right */
808 trbt_node_t *new_node;
810 new_node = trbt_create_node(tree, node, key,
811 callback(param, NULL));
812 node->right=new_node;
821 /* node will now point to the newly created node */
822 node->rb_color=TRBT_RED;
823 trbt_insert_case1(tree, node);
828 struct trbt_array_param {
829 void *(*callback)(void *param, void *data);
835 static void *array_insert_callback(void *p, void *data)
837 struct trbt_array_param *param = (struct trbt_array_param *)p;
838 trbt_tree_t *tree = NULL;
841 /* if keylen has reached 0 we are done and can call the users
842 callback function with the users parameters
844 if (param->keylen == 0) {
845 return param->callback(param->param, data);
849 /* keylen is not zero yes so we must create/process more subtrees */
850 /* if data is NULL this means we did not yet have a subtree here
851 and we must create one.
854 /* create a new subtree and hang it off our current tree
855 set it to autofree so that the tree is freed when
856 the last node in it has been released.
858 tree = trbt_create(param->tree, TRBT_AUTOFREE);
860 /* we already have a subtree for this path */
861 tree = (trbt_tree_t *)data;
864 trbt_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param);
866 /* now return either the old tree we got in *data or the new tree
867 we created to our caller so he can update his pointer in his
868 tree to point to our subtree
875 /* insert into the tree using an array of uint32 as a key */
877 trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm)
879 struct trbt_array_param tap;
881 /* keylen-1 and key[1] since the call to insert32 will consume the
882 first part of the key.
886 tap.keylen = keylen-1;
890 trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
893 /* lookup the tree using an array of uint32 as a key */
895 trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
897 /* if keylen is 1 we can do a regular lookup and return this to the
901 return trbt_lookup32(tree, key[0]);
904 /* we need to lookup the next subtree */
905 tree = trbt_lookup32(tree, key[0]);
907 /* the key does not exist, return NULL */
911 /* now lookup the next part of the key in our new tree */
912 return trbt_lookuparray32(tree, keylen-1, &key[1]);
916 /* traverse a tree starting at node */
918 trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
919 void (*callback)(void *param, void *data),
923 trbt_traversearray32_node(node->left, keylen, callback, param);
926 /* this is the smallest node in this subtree
927 if keylen is 0 this means we can just call the callback
928 otherwise we must pull the next subtree and traverse that one as well
931 callback(param, node->data);
933 trbt_traversearray32(node->data, keylen, callback, param);
937 trbt_traversearray32_node(node->right, keylen, callback, param);
942 /* traverse the tree using an array of uint32 as a key */
944 trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen,
945 void (*callback)(void *param, void *data),
959 trbt_traversearray32_node(node, keylen-1, callback, param);
963 /* this function will return the first node in a tree where
964 the key is an array of uint32_t
967 trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
988 /* we found our node so return the data */
993 /* we are still traversing subtrees so find the first node in the
996 return trbt_findfirstarray32(node->data, keylen-1);