Merge branch 'ronnie'
[ccan] / ccan / rbtree / rbtree.c
1 /*
2    a talloc based red-black tree
3
4    Copyright (C) Ronnie Sahlberg  2007
5
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.
10    
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.
15    
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/>.
18 */
19 #include <ccan/rbtree/rbtree.h>
20
21 static void
22 tree_destructor_traverse_node(TALLOC_CTX *mem_ctx, trbt_node_t *node)
23 {
24         talloc_set_destructor(node, NULL);
25         if (node->left) {
26                 tree_destructor_traverse_node(mem_ctx, node->left);
27         }
28         if (node->right) {
29                 tree_destructor_traverse_node(mem_ctx, node->right);
30         }
31         talloc_steal(mem_ctx, node);
32 }
33
34 /*
35   destroy a tree and remove all its nodes
36  */
37 static int tree_destructor(trbt_tree_t *tree)
38 {
39         TALLOC_CTX *tmp_ctx;
40         trbt_node_t *node;
41
42         if (tree == NULL) {
43                 return 0;
44         }
45
46         node=tree->root;
47         if (node == NULL) {
48                 return 0;
49         }
50
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
57            individual nodes
58         */
59         tmp_ctx = talloc_new(NULL);
60         tree_destructor_traverse_node(tmp_ctx, node);
61         talloc_free(tmp_ctx);
62
63         return 0;
64 }
65
66
67 /* create a red black tree */
68 trbt_tree_t *
69 trbt_create(TALLOC_CTX *memctx, uint32_t flags)
70 {
71         trbt_tree_t *tree;
72
73         tree = talloc_zero(memctx, trbt_tree_t);
74         if (tree == NULL) {
75                 fprintf(stderr, "Failed to allocate memory for rb tree\n");
76                 return NULL;
77         }
78
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.
83         */
84         talloc_set_destructor(tree, tree_destructor);
85         tree->flags = flags;
86
87         return tree;
88 }
89
90 static inline trbt_node_t *
91 trbt_parent(trbt_node_t *node)
92 {
93         return node->parent;
94 }
95
96 static inline trbt_node_t *
97 trbt_grandparent(trbt_node_t *node)
98 {
99         trbt_node_t *parent;
100
101         parent=trbt_parent(node);
102         if(parent){
103                 return parent->parent;
104         }
105         return NULL;
106 }
107
108 static inline trbt_node_t *
109 trbt_uncle(trbt_node_t *node)
110 {
111         trbt_node_t *parent, *grandparent;
112
113         parent=trbt_parent(node);
114         if(!parent){
115                 return NULL;
116         }
117         grandparent=trbt_parent(parent);
118         if(!grandparent){
119                 return NULL;
120         }
121         if(parent==grandparent->left){
122                 return grandparent->right;
123         }
124         return grandparent->left;
125 }
126
127
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);
130
131 static inline void
132 trbt_rotate_left(trbt_node_t *node)
133 {
134         trbt_tree_t *tree = node->tree;
135
136         if(node->parent){
137                 if(node->parent->left==node){
138                         node->parent->left=node->right;
139                 } else {
140                         node->parent->right=node->right;
141                 }
142         } else {
143                 tree->root=node->right;
144         }
145         node->right->parent=node->parent;
146         node->parent=node->right;
147         node->right=node->right->left;
148         if(node->right){
149                 node->right->parent=node;
150         }
151         node->parent->left=node;
152 }
153
154 static inline void
155 trbt_rotate_right(trbt_node_t *node)
156 {
157         trbt_tree_t *tree = node->tree;
158
159         if(node->parent){
160                 if(node->parent->left==node){
161                         node->parent->left=node->left;
162                 } else {
163                         node->parent->right=node->left;
164                 }
165         } else {
166                 tree->root=node->left;
167         }
168         node->left->parent=node->parent;
169         node->parent=node->left;
170         node->left=node->left->right;
171         if(node->left){
172                 node->left->parent=node;
173         }
174         node->parent->right=node;
175 }
176
177 /* NULL nodes are black by definition */
178 static inline int trbt_get_color(trbt_node_t *node)
179 {
180         if (node==NULL) {
181                 return TRBT_BLACK;
182         }
183         return node->rb_color;
184 }
185 static inline int trbt_get_color_left(trbt_node_t *node)
186 {
187         if (node==NULL) {
188                 return TRBT_BLACK;
189         }
190         if (node->left==NULL) {
191                 return TRBT_BLACK;
192         }
193         return node->left->rb_color;
194 }
195 static inline int trbt_get_color_right(trbt_node_t *node)
196 {
197         if (node==NULL) {
198                 return TRBT_BLACK;
199         }
200         if (node->right==NULL) {
201                 return TRBT_BLACK;
202         }
203         return node->right->rb_color;
204 }
205 /* setting a NULL node to black is a nop */
206 static inline void trbt_set_color(trbt_node_t *node, int color)
207 {
208         if ( (node==NULL) && (color==TRBT_BLACK) ) {
209                 return;
210         }
211         node->rb_color = color;
212 }
213 static inline void trbt_set_color_left(trbt_node_t *node, int color)
214 {
215         if ( ((node==NULL)||(node->left==NULL)) && (color==TRBT_BLACK) ) {
216                 return;
217         }
218         node->left->rb_color = color;
219 }
220 static inline void trbt_set_color_right(trbt_node_t *node, int color)
221 {
222         if ( ((node==NULL)||(node->right==NULL)) && (color==TRBT_BLACK) ) {
223                 return;
224         }
225         node->right->rb_color = color;
226 }
227
228 static inline void
229 trbt_insert_case5(trbt_node_t *node)
230 {
231         trbt_node_t *grandparent;
232         trbt_node_t *parent;
233
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);
240         } else {
241                 trbt_rotate_left(grandparent);
242         }
243 }
244
245 static inline void
246 trbt_insert_case4(trbt_node_t *node)
247 {
248         trbt_node_t *grandparent;
249         trbt_node_t *parent;
250
251         parent=trbt_parent(node);
252         grandparent=trbt_parent(parent);
253         if(!grandparent){
254                 return;
255         }
256         if( (node==parent->right) && (parent==grandparent->left) ){
257                 trbt_rotate_left(parent);
258                 node=node->left;
259         } else if( (node==parent->left) && (parent==grandparent->right) ){
260                 trbt_rotate_right(parent);
261                 node=node->right;
262         }
263         trbt_insert_case5(node);
264 }
265
266 static inline void
267 trbt_insert_case3(trbt_tree_t *tree, trbt_node_t *node)
268 {
269         trbt_node_t *grandparent;
270         trbt_node_t *parent;
271         trbt_node_t *uncle;
272
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);
281         } else {
282                 trbt_insert_case4(node);
283         }
284 }
285
286 static inline void
287 trbt_insert_case2(trbt_tree_t *tree, trbt_node_t *node)
288 {
289         trbt_node_t *parent;
290
291         parent=trbt_parent(node);
292         /* parent is always non-NULL here */
293         if(parent->rb_color==TRBT_BLACK){
294                 return;
295         }
296         trbt_insert_case3(tree, node);
297 }
298
299 static inline void
300 trbt_insert_case1(trbt_tree_t *tree, trbt_node_t *node)
301 {
302         trbt_node_t *parent;
303
304         parent=trbt_parent(node);
305         if(!parent){
306                 node->rb_color=TRBT_BLACK;
307                 return;
308         }
309         trbt_insert_case2(tree, node);
310 }
311
312 static inline trbt_node_t *
313 trbt_sibling(trbt_node_t *node)
314 {
315         trbt_node_t *parent;
316
317         parent=trbt_parent(node);
318         if(!parent){
319                 return NULL;
320         }
321
322         if (node == parent->left) {
323                 return parent->right;
324         } else {
325                 return parent->left;
326         }
327 }
328
329 static inline void
330 trbt_delete_case6(trbt_node_t *node)
331 {
332         trbt_node_t *sibling, *parent;
333
334         sibling = trbt_sibling(node);
335         parent  = trbt_parent(node);
336
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);
342         } else {
343                 trbt_set_color_left(sibling, TRBT_BLACK);
344                 trbt_rotate_right(parent);
345         }
346 }
347
348
349 static inline void
350 trbt_delete_case5(trbt_node_t *node)
351 {
352         trbt_node_t *parent, *sibling;
353
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);
364                 return;
365         }
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);
374                 return;
375         }
376
377         trbt_delete_case6(node);
378 }
379
380 static inline void
381 trbt_delete_case4(trbt_node_t *node)
382 {
383         trbt_node_t *sibling;
384
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);
392         } else {
393                 trbt_delete_case5(node);
394         }
395 }
396
397 static void trbt_delete_case1(trbt_node_t *node);
398
399 static inline void
400 trbt_delete_case3(trbt_node_t *node)
401 {
402         trbt_node_t *sibling;
403
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);
411         } else {
412                 trbt_delete_case4(node);
413         }
414 }
415         
416 static inline void
417 trbt_delete_case2(trbt_node_t *node)
418 {
419         trbt_node_t *sibling;
420
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);
427                 } else {
428                         trbt_rotate_right(node->parent);
429                 }
430         }
431         trbt_delete_case3(node);
432 }
433
434 static void
435 trbt_delete_case1(trbt_node_t *node)
436 {
437         if (!node->parent) {
438                 return;
439         } else {
440                 trbt_delete_case2(node);
441         }
442 }
443
444 static void
445 delete_node(trbt_node_t *node, int from_destructor)
446 {
447         trbt_node_t *parent, *child, dc;
448         trbt_node_t *temp = NULL;
449
450         /* This node has two child nodes, then just copy the content
451            from the next smaller node with this node and delete the
452            predecessor instead.
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
456             it in the tree)
457          */
458         if (node->left != NULL && node->right != NULL) {
459                 /* This node has two children, just copy the data */
460                 /* find the predecessor */
461                 temp = node->left;
462
463                 while (temp->right != NULL) {
464                         temp = temp->right;
465                 }
466
467                 /* swap the predecessor data and key with the node to
468                    be deleted.
469                  */
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);
474         
475                 temp->data  = NULL;
476                 temp->key32 = -1;
477                 /* then delete the temp node.
478                    this node is guaranteed to have at least one leaf
479                    child */
480                 delete_node(temp, from_destructor);
481                 goto finished;
482         }
483
484
485         /* There is at most one child to this node to be deleted */
486         child = node->left;
487         if (node->right) {
488                 child = node->right;
489         }
490
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.
498          */
499         if (!child) {
500                 child = &dc;
501                 child->tree = node->tree;
502                 child->left=NULL;
503                 child->right=NULL;
504                 child->rb_color=TRBT_BLACK;
505                 child->data=NULL;
506         }
507
508         /* replace node with child */
509         parent = trbt_parent(node);
510         if (parent) {
511                 if (parent->left == node) {
512                         parent->left = child;
513                 } else {
514                         parent->right = child;
515                 }
516         } else {
517                 node->tree->root = child;
518         }
519         child->parent = node->parent;
520
521
522         if (node->rb_color == TRBT_BLACK) {
523                 if (trbt_get_color(child) == TRBT_RED) {
524                         child->rb_color = TRBT_BLACK;
525                 } else {
526                         trbt_delete_case1(child);
527                 }
528         }
529
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
535            have occured.
536
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
540            parent.
541          */
542         if (child == &dc) {
543                 if (child->parent == NULL) {
544                         node->tree->root = NULL;
545                 } else if (child == child->parent->left) {
546                         child->parent->left = NULL;
547                 } else {
548                         child->parent->right = NULL;
549                 }
550         }
551
552 finished:
553         if (!from_destructor) {
554                 talloc_free(node);
555         }
556
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.
560         */
561         if (from_destructor && temp) {
562                 temp->key32    = node->key32;
563                 temp->rb_color = node->rb_color;
564
565                 temp->data = node->data;
566                 talloc_steal(temp->data, temp);
567
568                 temp->parent = node->parent;
569                 if (temp->parent) {
570                         if (temp->parent->left == node) {
571                                 temp->parent->left = temp;
572                         } else {
573                                 temp->parent->right = temp;
574                         }
575                 }
576
577                 temp->left = node->left;
578                 if (temp->left) {
579                         temp->left->parent = temp;
580                 }
581                 temp->right = node->right;
582                 if (temp->right) {
583                         temp->right->parent = temp;
584                 }
585
586                 if (temp->tree->root == node) {
587                         temp->tree->root = temp;
588                 }
589         }
590
591         if ( (node->tree->flags & TRBT_AUTOFREE)
592         &&   (node->tree->root == NULL) ) {
593                 talloc_free(node->tree);
594         }
595
596         return;
597 }
598
599 /*
600   destroy a node and remove it from its tree
601  */
602 static int node_destructor(trbt_node_t *node)
603 {
604         delete_node(node, 1);
605
606         return 0;
607 }
608
609 static inline trbt_node_t *
610 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
611 {
612         trbt_node_t *node;
613
614         node=talloc_zero(tree, trbt_node_t);
615         if (node == NULL) {
616                 fprintf(stderr, "Failed to allocate memory for rb node\n");
617                 return NULL;
618         }
619
620         node->tree=tree;
621         node->rb_color=TRBT_BLACK;
622         node->parent=parent;
623         node->left=NULL;
624         node->right=NULL;
625         node->key32=key;
626         node->data = data;
627
628         /* let this node hang off data so that it is removed when
629            data is freed
630          */
631         talloc_steal(data, node);
632         talloc_set_destructor(node, node_destructor);
633
634         return node;
635 }
636
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
641  */
642 void *
643 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
644 {
645         trbt_node_t *node;
646
647         node=tree->root;
648
649         /* is this the first node ?*/
650         if(!node){
651                 node = trbt_create_node(tree, NULL, key, data);
652
653                 tree->root=node;
654                 return NULL;
655         }
656
657         /* it was not the new root so walk the tree until we find where to
658          * insert this new leaf.
659          */
660         while(1){
661                 /* this node already exists, replace data and return the
662                    old data
663                  */
664                 if(key==node->key32){
665                         void *old_data;
666
667                         old_data = node->data;
668                         node->data  = data;
669                         /* Let the node now be owned by the new data
670                            so the node is freed when the enw data is released
671                         */
672                         talloc_steal(node->data, node);
673
674                         return old_data;
675                 }
676                 if(key<node->key32) {
677                         if(!node->left){
678                                 /* new node to the left */
679                                 trbt_node_t *new_node;
680
681                                 new_node = trbt_create_node(tree, node, key, data);
682                                 node->left=new_node;
683                                 node=new_node;
684
685                                 break;
686                         }
687                         node=node->left;
688                         continue;
689                 }
690                 if(key>node->key32) {
691                         if(!node->right){
692                                 /* new node to the right */
693                                 trbt_node_t *new_node;
694
695                                 new_node = trbt_create_node(tree, node, key, data);
696                                 node->right=new_node;
697                                 node=new_node;
698                                 break;
699                         }
700                         node=node->right;
701                         continue;
702                 }
703         }
704
705         /* node will now point to the newly created node */
706         node->rb_color=TRBT_RED;
707         trbt_insert_case1(tree, node);
708         return NULL;
709 }
710
711 void *
712 trbt_lookup32(trbt_tree_t *tree, uint32_t key)
713 {
714         trbt_node_t *node;
715
716         node=tree->root;
717
718         while(node){
719                 if(key==node->key32){
720                         return node->data;
721                 }
722                 if(key<node->key32){
723                         node=node->left;
724                         continue;
725                 }
726                 if(key>node->key32){
727                         node=node->right;
728                         continue;
729                 }
730         }
731         return NULL;
732 }
733
734
735 /* This deletes a node from the tree.
736    Note that this does not release the data that the node points to
737 */
738 void
739 trbt_delete32(trbt_tree_t *tree, uint32_t key)
740 {
741         trbt_node_t *node;
742
743         node=tree->root;
744
745         while(node){
746                 if(key==node->key32){
747                         delete_node(node, 0);
748                         return;
749                 }
750                 if(key<node->key32){
751                         node=node->left;
752                         continue;
753                 }
754                 if(key>node->key32){
755                         node=node->right;
756                         continue;
757                 }
758         }
759 }
760
761
762 void
763 trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
764 {
765         trbt_node_t *node;
766
767         node=tree->root;
768
769         /* is this the first node ?*/
770         if(!node){
771                 node = trbt_create_node(tree, NULL, key,
772                                 callback(param, NULL));
773
774                 tree->root=node;
775                 return;
776         }
777
778         /* it was not the new root so walk the tree until we find where to
779          * insert this new leaf.
780          */
781         while(1){
782                 /* this node already exists, replace it
783                  */
784                 if(key==node->key32){
785                         node->data  = callback(param, node->data);
786                         talloc_steal(node->data, node);
787
788                         return;
789                 }
790                 if(key<node->key32) {
791                         if(!node->left){
792                                 /* new node to the left */
793                                 trbt_node_t *new_node;
794
795                                 new_node = trbt_create_node(tree, node, key,
796                                                 callback(param, NULL));
797                                 node->left=new_node;
798                                 node=new_node;
799
800                                 break;
801                         }
802                         node=node->left;
803                         continue;
804                 }
805                 if(key>node->key32) {
806                         if(!node->right){
807                                 /* new node to the right */
808                                 trbt_node_t *new_node;
809
810                                 new_node = trbt_create_node(tree, node, key,
811                                                 callback(param, NULL));
812                                 node->right=new_node;
813                                 node=new_node;
814                                 break;
815                         }
816                         node=node->right;
817                         continue;
818                 }
819         }
820
821         /* node will now point to the newly created node */
822         node->rb_color=TRBT_RED;
823         trbt_insert_case1(tree, node);
824         return;
825 }
826
827
828 struct trbt_array_param {
829         void *(*callback)(void *param, void *data);
830         void *param;
831         uint32_t keylen;
832         uint32_t *key;
833         trbt_tree_t *tree;
834 };
835 static void *array_insert_callback(void *p, void *data)
836 {
837         struct trbt_array_param *param = (struct trbt_array_param *)p;
838         trbt_tree_t *tree = NULL;
839
840
841         /* if keylen has reached 0 we are done and can call the users
842            callback function with the users parameters
843         */
844         if (param->keylen == 0) {
845                 return param->callback(param->param, data);
846         }
847
848
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.
852         */
853         if (data == NULL) {
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.
857                 */
858                 tree = trbt_create(param->tree, TRBT_AUTOFREE);
859         } else {
860                 /* we already have a subtree for this path */
861                 tree = (trbt_tree_t *)data;
862         }
863                 
864         trbt_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param);
865
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
869         */
870         return tree;
871 }
872
873
874
875 /* insert into the tree using an array of uint32 as a key */
876 void
877 trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm)
878 {
879         struct trbt_array_param tap;
880
881         /* keylen-1 and key[1]  since the call to insert32 will consume the
882            first part of the key.
883         */
884         tap.callback= cb;
885         tap.param   = pm;
886         tap.keylen  = keylen-1;
887         tap.key     = &key[1];
888         tap.tree    = tree;
889
890         trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
891 }
892
893 /* lookup the tree using an array of uint32 as a key */
894 void *
895 trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
896 {
897         /* if keylen is 1 we can do a regular lookup and return this to the
898            user
899         */
900         if (keylen == 1) {
901                 return trbt_lookup32(tree, key[0]);
902         }
903
904         /* we need to lookup the next subtree */
905         tree = trbt_lookup32(tree, key[0]);
906         if (tree == NULL) {
907                 /* the key does not exist, return NULL */
908                 return NULL;
909         }
910
911         /* now lookup the next part of the key in our new tree */
912         return trbt_lookuparray32(tree, keylen-1, &key[1]);
913 }
914
915
916 /* traverse a tree starting at node */
917 static void
918 trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
919         void (*callback)(void *param, void *data),
920         void *param)
921 {
922         if (node->left) {
923                 trbt_traversearray32_node(node->left, keylen, callback, param);
924         }
925
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
929         */
930         if (keylen == 0) {
931                 callback(param, node->data);
932         } else {
933                 trbt_traversearray32(node->data, keylen, callback, param);
934         }
935
936         if (node->right) {
937                 trbt_traversearray32_node(node->right, keylen, callback, param);
938         }
939 }
940         
941
942 /* traverse the tree using an array of uint32 as a key */
943 void
944 trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen,
945         void (*callback)(void *param, void *data),
946         void *param)
947 {
948         trbt_node_t *node;
949
950         if (tree == NULL) {
951                 return;
952         }
953
954         node=tree->root;
955         if (node == NULL) {
956                 return;
957         }
958
959         trbt_traversearray32_node(node, keylen-1, callback, param);
960 }
961
962
963 /* this function will return the first node in a tree where
964    the key is an array of uint32_t
965 */
966 void *
967 trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
968 {
969         trbt_node_t *node;
970
971         if (keylen < 1) {
972                 return NULL;
973         }
974         
975         if (tree == NULL) {
976                 return NULL;
977         }
978
979         node=tree->root;
980         if (node == NULL) {
981                 return NULL;
982         }
983
984         while (node->left) {
985                 node = node->left;
986         }
987
988         /* we found our node so return the data */
989         if (keylen == 1) {
990                 return node->data;
991         }
992
993         /* we are still traversing subtrees so find the first node in the
994            next level of trees
995         */
996         return trbt_findfirstarray32(node->data, keylen-1);
997 }
998
999