check_type: fix incorrect documentation.
[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 don't 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 don't 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 don't 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 occurred.
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                                 if (!new_node)
675                                         return NULL;
676                                 node->left=new_node;
677                                 node=new_node;
678
679                                 break;
680                         }
681                         node=node->left;
682                         continue;
683                 }
684                 if(key>node->key32) {
685                         if(!node->right){
686                                 /* new node to the right */
687                                 trbt_node_t *new_node;
688
689                                 new_node = trbt_create_node(tree, node, key, data);
690                                 if (!new_node)
691                                         return NULL;
692                                 node->right=new_node;
693                                 node=new_node;
694                                 break;
695                         }
696                         node=node->right;
697                         continue;
698                 }
699         }
700
701         /* node will now point to the newly created node */
702         node->rb_color=TRBT_RED;
703         trbt_insert_case1(tree, node);
704         return NULL;
705 }
706
707 void *
708 trbt_lookup32(trbt_tree_t *tree, uint32_t key)
709 {
710         trbt_node_t *node;
711
712         node=tree->root;
713
714         while(node){
715                 if(key==node->key32){
716                         return node->data;
717                 }
718                 if(key<node->key32){
719                         node=node->left;
720                         continue;
721                 }
722                 if(key>node->key32){
723                         node=node->right;
724                         continue;
725                 }
726         }
727         return NULL;
728 }
729
730
731 /* This deletes a node from the tree.
732    Note that this does not release the data that the node points to
733 */
734 void
735 trbt_delete32(trbt_tree_t *tree, uint32_t key)
736 {
737         trbt_node_t *node;
738
739         node=tree->root;
740
741         while(node){
742                 if(key==node->key32){
743                         talloc_free(node);
744                         return;
745                 }
746                 if(key<node->key32){
747                         node=node->left;
748                         continue;
749                 }
750                 if(key>node->key32){
751                         node=node->right;
752                         continue;
753                 }
754         }
755 }
756
757
758 void
759 trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
760 {
761         trbt_node_t *node;
762
763         node=tree->root;
764
765         /* is this the first node ?*/
766         if(!node){
767                 node = trbt_create_node(tree, NULL, key,
768                                 callback(param, NULL));
769
770                 tree->root=node;
771                 return;
772         }
773
774         /* it was not the new root so walk the tree until we find where to
775          * insert this new leaf.
776          */
777         while(1){
778                 /* this node already exists, replace it
779                  */
780                 if(key==node->key32){
781                         node->data  = callback(param, node->data);
782                         talloc_steal(node->data, node);
783
784                         return;
785                 }
786                 if(key<node->key32) {
787                         if(!node->left){
788                                 /* new node to the left */
789                                 trbt_node_t *new_node;
790
791                                 new_node = trbt_create_node(tree, node, key,
792                                                 callback(param, NULL));
793                                 node->left=new_node;
794                                 node=new_node;
795
796                                 break;
797                         }
798                         node=node->left;
799                         continue;
800                 }
801                 if(key>node->key32) {
802                         if(!node->right){
803                                 /* new node to the right */
804                                 trbt_node_t *new_node;
805
806                                 new_node = trbt_create_node(tree, node, key,
807                                                 callback(param, NULL));
808                                 node->right=new_node;
809                                 node=new_node;
810                                 break;
811                         }
812                         node=node->right;
813                         continue;
814                 }
815         }
816
817         /* node will now point to the newly created node */
818         node->rb_color=TRBT_RED;
819         trbt_insert_case1(tree, node);
820         return;
821 }
822
823
824 struct trbt_array_param {
825         void *(*callback)(void *param, void *data);
826         void *param;
827         uint32_t keylen;
828         uint32_t *key;
829         trbt_tree_t *tree;
830 };
831 static void *array_insert_callback(void *p, void *data)
832 {
833         struct trbt_array_param *param = (struct trbt_array_param *)p;
834         trbt_tree_t *tree = NULL;
835
836
837         /* if keylen has reached 0 we are done and can call the users
838            callback function with the users parameters
839         */
840         if (param->keylen == 0) {
841                 return param->callback(param->param, data);
842         }
843
844
845         /* keylen is not zero yes so we must create/process more subtrees */
846         /* if data is NULL this means we did not yet have a subtree here
847            and we must create one.
848         */
849         if (data == NULL) {
850                 /* create a new subtree and hang it off our current tree
851                    set it to autofree so that the tree is freed when
852                    the last node in it has been released.
853                 */
854                 tree = trbt_create(param->tree, TRBT_AUTOFREE);
855         } else {
856                 /* we already have a subtree for this path */
857                 tree = (trbt_tree_t *)data;
858         }
859                 
860         trbt_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param);
861
862         /* now return either the old tree we got in *data or the new tree
863            we created to our caller so he can update his pointer in his
864            tree to point to our subtree
865         */
866         return tree;
867 }
868
869
870
871 /* insert into the tree using an array of uint32 as a key */
872 void
873 trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm)
874 {
875         struct trbt_array_param tap;
876
877         /* keylen-1 and key[1]  since the call to insert32 will consume the
878            first part of the key.
879         */
880         tap.callback= cb;
881         tap.param   = pm;
882         tap.keylen  = keylen-1;
883         tap.key     = &key[1];
884         tap.tree    = tree;
885
886         trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
887 }
888
889 /* lookup the tree using an array of uint32 as a key */
890 void *
891 trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
892 {
893         /* if keylen is 1 we can do a regular lookup and return this to the
894            user
895         */
896         if (keylen == 1) {
897                 return trbt_lookup32(tree, key[0]);
898         }
899
900         /* we need to lookup the next subtree */
901         tree = trbt_lookup32(tree, key[0]);
902         if (tree == NULL) {
903                 /* the key does not exist, return NULL */
904                 return NULL;
905         }
906
907         /* now lookup the next part of the key in our new tree */
908         return trbt_lookuparray32(tree, keylen-1, &key[1]);
909 }
910
911
912 /* traverse a tree starting at node */
913 static void
914 trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
915         void (*callback)(void *param, void *data),
916         void *param)
917 {
918         if (node->left) {
919                 trbt_traversearray32_node(node->left, keylen, callback, param);
920         }
921
922         /* this is the smallest node in this subtree
923            if keylen is 0 this means we can just call the callback
924            otherwise we must pull the next subtree and traverse that one as well
925         */
926         if (keylen == 0) {
927                 callback(param, node->data);
928         } else {
929                 trbt_traversearray32(node->data, keylen, callback, param);
930         }
931
932         if (node->right) {
933                 trbt_traversearray32_node(node->right, keylen, callback, param);
934         }
935 }
936         
937
938 /* traverse the tree using an array of uint32 as a key */
939 void
940 trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen,
941         void (*callback)(void *param, void *data),
942         void *param)
943 {
944         trbt_node_t *node;
945
946         if (tree == NULL) {
947                 return;
948         }
949
950         node=tree->root;
951         if (node == NULL) {
952                 return;
953         }
954
955         trbt_traversearray32_node(node, keylen-1, callback, param);
956 }
957
958
959 /* this function will return the first node in a tree where
960    the key is an array of uint32_t
961 */
962 void *
963 trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
964 {
965         trbt_node_t *node;
966
967         if (keylen < 1) {
968                 return NULL;
969         }
970         
971         if (tree == NULL) {
972                 return NULL;
973         }
974
975         node=tree->root;
976         if (node == NULL) {
977                 return NULL;
978         }
979
980         while (node->left) {
981                 node = node->left;
982         }
983
984         /* we found our node so return the data */
985         if (keylen == 1) {
986                 return node->data;
987         }
988
989         /* we are still traversing subtrees so find the first node in the
990            next level of trees
991         */
992         return trbt_findfirstarray32(node->data, keylen-1);
993 }
994
995