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