vfs: Remove files_struct->posix_flags
[Samba.git] / ctdb / common / rb_tree.c
blob8e13dff969e1e598fb966fee70413130fcbe20b5
1 /*
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/>.
20 #include "replace.h"
22 #include <talloc.h>
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__)); \
31 exit(10); \
32 }} while (0)
35 static void
36 tree_destructor_traverse_node(TALLOC_CTX *mem_ctx, trbt_node_t *node)
38 talloc_set_destructor(node, NULL);
39 if (node->left) {
40 tree_destructor_traverse_node(mem_ctx, node->left);
42 if (node->right) {
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)
53 TALLOC_CTX *tmp_ctx;
54 trbt_node_t *node;
56 if (tree == NULL) {
57 return 0;
60 node=tree->root;
61 if (node == NULL) {
62 return 0;
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
71 individual nodes
73 tmp_ctx = talloc_new(NULL);
74 tree_destructor_traverse_node(tmp_ctx, node);
75 talloc_free(tmp_ctx);
77 return 0;
81 /* create a red black tree */
82 trbt_tree_t *
83 trbt_create(TALLOC_CTX *memctx, uint32_t flags)
85 trbt_tree_t *tree;
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);
96 tree->flags = flags;
98 return tree;
101 static inline trbt_node_t *
102 trbt_parent(trbt_node_t *node)
104 return node->parent;
107 static inline trbt_node_t *
108 trbt_grandparent(trbt_node_t *node)
110 trbt_node_t *parent;
112 parent=trbt_parent(node);
113 if(parent){
114 return parent->parent;
116 return NULL;
119 static inline trbt_node_t *
120 trbt_uncle(trbt_node_t *node)
122 trbt_node_t *parent, *grandparent;
124 parent=trbt_parent(node);
125 if(!parent){
126 return NULL;
128 grandparent=trbt_parent(parent);
129 if(!grandparent){
130 return NULL;
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);
142 static inline void
143 trbt_rotate_left(trbt_node_t *node)
145 trbt_tree_t *tree = node->tree;
147 if(node->parent){
148 if(node->parent->left==node){
149 node->parent->left=node->right;
150 } else {
151 node->parent->right=node->right;
153 } else {
154 tree->root=node->right;
156 node->right->parent=node->parent;
157 node->parent=node->right;
158 node->right=node->right->left;
159 if(node->right){
160 node->right->parent=node;
162 node->parent->left=node;
165 static inline void
166 trbt_rotate_right(trbt_node_t *node)
168 trbt_tree_t *tree = node->tree;
170 if(node->parent){
171 if(node->parent->left==node){
172 node->parent->left=node->left;
173 } else {
174 node->parent->right=node->left;
176 } else {
177 tree->root=node->left;
179 node->left->parent=node->parent;
180 node->parent=node->left;
181 node->left=node->left->right;
182 if(node->left){
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)
191 if (node==NULL) {
192 return TRBT_BLACK;
194 return node->rb_color;
196 static inline int trbt_get_color_left(trbt_node_t *node)
198 if (node==NULL) {
199 return TRBT_BLACK;
201 if (node->left==NULL) {
202 return TRBT_BLACK;
204 return node->left->rb_color;
206 static inline int trbt_get_color_right(trbt_node_t *node)
208 if (node==NULL) {
209 return TRBT_BLACK;
211 if (node->right==NULL) {
212 return TRBT_BLACK;
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)
219 if (node == NULL) {
220 return;
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) {
227 return;
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) {
234 return;
236 node->right->rb_color = color;
239 static inline void
240 trbt_insert_case5(trbt_tree_t *tree, trbt_node_t *node)
242 trbt_node_t *grandparent;
243 trbt_node_t *parent;
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);
251 } else {
252 trbt_rotate_left(grandparent);
256 static inline void
257 trbt_insert_case4(trbt_tree_t *tree, trbt_node_t *node)
259 trbt_node_t *grandparent;
260 trbt_node_t *parent;
262 parent=trbt_parent(node);
263 grandparent=trbt_parent(parent);
264 if(!grandparent){
265 return;
267 if( (node==parent->right) && (parent==grandparent->left) ){
268 trbt_rotate_left(parent);
269 node=node->left;
270 } else if( (node==parent->left) && (parent==grandparent->right) ){
271 trbt_rotate_right(parent);
272 node=node->right;
274 trbt_insert_case5(tree, node);
277 static inline void
278 trbt_insert_case3(trbt_tree_t *tree, trbt_node_t *node)
280 trbt_node_t *grandparent;
281 trbt_node_t *parent;
282 trbt_node_t *uncle;
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);
292 } else {
293 trbt_insert_case4(tree, node);
297 static inline void
298 trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node)
300 trbt_node_t *parent;
302 parent=trbt_parent(node);
303 /* parent is always non-NULL here */
304 if(parent->rb_color==TRBT_BLACK){
305 return;
307 trbt_insert_case3(tree, node);
310 static inline void
311 trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node)
313 trbt_node_t *parent;
315 parent=trbt_parent(node);
316 if(!parent){
317 node->rb_color=TRBT_BLACK;
318 return;
320 trbt_insert_case2(tree, node);
323 static inline trbt_node_t *
324 trbt_sibling(trbt_node_t *node)
326 trbt_node_t *parent;
328 parent=trbt_parent(node);
329 if(!parent){
330 return NULL;
333 if (node == parent->left) {
334 return parent->right;
335 } else {
336 return parent->left;
340 static inline void
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);
353 } else {
354 trbt_set_color_left(sibling, TRBT_BLACK);
355 trbt_rotate_right(parent);
360 static inline void
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);
375 return;
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);
385 return;
388 trbt_delete_case6(node);
391 static inline void
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);
403 } else {
404 trbt_delete_case5(node);
408 static void trbt_delete_case1(trbt_node_t *node);
410 static inline void
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);
422 } else {
423 trbt_delete_case4(node);
427 static inline void
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);
438 } else {
439 trbt_rotate_right(node->parent);
442 trbt_delete_case3(node);
445 static void
446 trbt_delete_case1(trbt_node_t *node)
448 if (!node->parent) {
449 return;
450 } else {
451 trbt_delete_case2(node);
455 static void
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
463 predecessor instead.
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
467 it in the tree)
469 if (node->left != NULL && node->right != NULL) {
470 /* This node has two children, just copy the data */
471 /* find the predecessor */
472 temp = node->left;
474 while (temp->right != NULL) {
475 temp = temp->right;
478 /* swap the predecessor data and key with the node to
479 be deleted.
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);
486 temp->data = NULL;
487 temp->key32 = -1;
488 /* then delete the temp node.
489 this node is guaranteed to have at least one leaf
490 child */
491 delete_node(temp, from_destructor);
492 goto finished;
496 /* There is at most one child to this node to be deleted */
497 child = node->left;
498 if (node->right) {
499 child = node->right;
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.
510 if (!child) {
511 child = &dc;
512 child->tree = node->tree;
513 child->left=NULL;
514 child->right=NULL;
515 child->rb_color=TRBT_BLACK;
516 child->data=NULL;
519 /* replace node with child */
520 parent = trbt_parent(node);
521 if (parent) {
522 if (parent->left == node) {
523 parent->left = child;
524 } else {
525 parent->right = child;
527 } else {
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;
536 } else {
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
546 have occurred.
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
551 parent.
553 if (child == &dc) {
554 if (child->parent == NULL) {
555 node->tree->root = NULL;
556 } else if (child == child->parent->left) {
557 child->parent->left = NULL;
558 } else {
559 child->parent->right = NULL;
563 finished:
564 if (!from_destructor) {
565 talloc_free(node);
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;
580 if (temp->parent) {
581 if (temp->parent->left == node) {
582 temp->parent->left = temp;
583 } else {
584 temp->parent->right = temp;
588 temp->left = node->left;
589 if (temp->left) {
590 temp->left->parent = temp;
592 temp->right = node->right;
593 if (temp->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);
607 return;
611 destroy a node and remove it from its tree
613 static int node_destructor(trbt_node_t *node)
615 delete_node(node, true);
617 return 0;
620 static inline trbt_node_t *
621 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
623 trbt_node_t *node;
625 node=talloc_zero(tree, trbt_node_t);
626 NO_MEMORY_FATAL(node);
628 node->tree=tree;
629 node->rb_color=TRBT_BLACK;
630 node->parent=parent;
631 node->left=NULL;
632 node->right=NULL;
633 node->key32=key;
634 node->data = data;
636 /* let this node hang off data so that it is removed when
637 data is freed
639 talloc_steal(data, node);
640 talloc_set_destructor(node, node_destructor);
642 return node;
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
650 void *
651 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
653 trbt_node_t *node;
655 node=tree->root;
657 /* is this the first node ?*/
658 if(!node){
659 node = trbt_create_node(tree, NULL, key, data);
661 tree->root=node;
662 return NULL;
665 /* it was not the new root so walk the tree until we find where to
666 * insert this new leaf.
668 while(1){
669 /* this node already exists, replace data and return the
670 old data
672 if(key==node->key32){
673 void *old_data;
675 old_data = node->data;
676 node->data = 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);
682 return old_data;
684 if(key<node->key32) {
685 if(!node->left){
686 /* new node to the left */
687 trbt_node_t *new_node;
689 new_node = trbt_create_node(tree, node, key, data);
690 node->left=new_node;
691 node=new_node;
693 break;
695 node=node->left;
696 continue;
698 if(key>node->key32) {
699 if(!node->right){
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;
705 node=new_node;
706 break;
708 node=node->right;
709 continue;
713 /* node will now point to the newly created node */
714 node->rb_color=TRBT_RED;
715 trbt_insert_case1(tree, node);
716 return NULL;
719 void *
720 trbt_lookup32(trbt_tree_t *tree, uint32_t key)
722 trbt_node_t *node;
724 node=tree->root;
726 while(node){
727 if(key==node->key32){
728 return node->data;
730 if(key<node->key32){
731 node=node->left;
732 continue;
734 if(key>node->key32){
735 node=node->right;
736 continue;
739 return NULL;
743 /* This deletes a node from the tree.
744 Note that this does not release the data that the node points to
746 void
747 trbt_delete32(trbt_tree_t *tree, uint32_t key)
749 trbt_node_t *node;
751 node=tree->root;
753 while(node){
754 if(key==node->key32){
755 delete_node(node, false);
756 return;
758 if(key<node->key32){
759 node=node->left;
760 continue;
762 if(key>node->key32){
763 node=node->right;
764 continue;
770 void
771 trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
773 trbt_node_t *node;
775 node=tree->root;
777 /* is this the first node ?*/
778 if(!node){
779 node = trbt_create_node(tree, NULL, key,
780 callback(param, NULL));
782 tree->root=node;
783 return;
786 /* it was not the new root so walk the tree until we find where to
787 * insert this new leaf.
789 while(1){
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);
796 return;
798 if(key<node->key32) {
799 if(!node->left){
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));
805 node->left=new_node;
806 node=new_node;
808 break;
810 node=node->left;
811 continue;
813 if(key>node->key32) {
814 if(!node->right){
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;
821 node=new_node;
822 break;
824 node=node->right;
825 continue;
829 /* node will now point to the newly created node */
830 node->rb_color=TRBT_RED;
831 trbt_insert_case1(tree, node);
832 return;
836 struct trbt_array_param {
837 void *(*callback)(void *param, void *data);
838 void *param;
839 uint32_t keylen;
840 uint32_t *key;
841 trbt_tree_t *tree;
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.
861 if (data == NULL) {
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);
867 } else {
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
878 return tree;
883 /* insert into the tree using an array of uint32 as a key */
884 void
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.
892 tap.callback= cb;
893 tap.param = pm;
894 tap.keylen = keylen-1;
895 tap.key = &key[1];
896 tap.tree = tree;
898 trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
901 /* lookup the tree using an array of uint32 as a key */
902 void *
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
906 user
908 if (keylen == 1) {
909 return trbt_lookup32(tree, key[0]);
912 /* we need to lookup the next subtree */
913 tree = trbt_lookup32(tree, key[0]);
914 if (tree == NULL) {
915 /* the key does not exist, return NULL */
916 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 */
925 static int
926 trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
927 int (*callback)(void *param, void *data),
928 void *param)
930 trbt_node_t *left = node->left;
931 trbt_node_t *right = node->right;
933 if (left) {
934 int ret;
935 ret = trbt_traversearray32_node(left, keylen, callback, param);
936 if (ret != 0) {
937 return ret;
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
945 if (keylen == 0) {
946 int ret;
948 ret = callback(param, node->data);
949 if (ret != 0) {
950 return ret;
952 } else {
953 int ret;
955 ret = trbt_traversearray32(node->data, keylen, callback, param);
956 if (ret != 0) {
957 return ret;
961 if (right) {
962 int ret;
964 ret = trbt_traversearray32_node(right, keylen, callback, param);
965 if (ret != 0) {
966 return ret;
970 return 0;
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),
978 void *param)
980 trbt_node_t *node;
982 if (tree == NULL) {
983 return 0;
986 node=tree->root;
987 if (node == NULL) {
988 return 0;
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
998 void *
999 trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
1001 trbt_node_t *node;
1003 if (keylen < 1) {
1004 return NULL;
1007 if (tree == NULL) {
1008 return NULL;
1011 node=tree->root;
1012 if (node == NULL) {
1013 return NULL;
1016 while (node->left) {
1017 node = node->left;
1020 /* we found our node so return the data */
1021 if (keylen == 1) {
1022 return node->data;
1025 /* we are still traversing subtrees so find the first node in the
1026 next level of trees
1028 return trbt_findfirstarray32(node->data, keylen-1);
1032 #ifdef TEST_RB_TREE
1033 static void printtree(trbt_node_t *node, int levels)
1035 int i;
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);
1043 printf("\n");
1046 void print_tree(trbt_tree_t *tree)
1048 if(tree->root==NULL){
1049 printf("tree is empty\n");
1050 return;
1052 printf("---\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);
1056 printf("===\n");
1059 void
1060 test_tree(void)
1062 trbt_tree_t *tree;
1063 char *str;
1064 int i, ret;
1065 int NUM=15;
1066 int cnt=0;
1068 tree=trbt_create(talloc_new(NULL), 0);
1069 #if 0
1070 for(i=0;i<10;i++){
1071 printf("adding node %i\n",i);
1072 trbt_insert32(tree, i, NULL);
1073 print_tree(tree);
1075 printf("deleting node %i\n",3);
1076 trbt_delete32(tree, 3);
1077 print_tree(tree);
1078 for(i=0;i<10;i++){
1079 printf("deleting node %i\n",i);
1080 trbt_delete32(tree, i);
1081 print_tree(tree);
1083 exit(0);
1084 #endif
1085 while(++cnt){
1086 int i;
1087 printf("iteration : %d\n",cnt);
1088 i=random()%20;
1089 printf("adding node %i\n",i);
1090 trbt_insert32(tree, i, NULL);
1091 print_tree(tree);
1093 i=random()%20;
1094 printf("deleting node %i\n",i);
1095 trbt_delete32(tree, i);
1096 print_tree(tree);
1101 #endif /* TEST_RB_TREE */