talloc: allow replacement allocator
[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)
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);
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 we came from a destructor and temp!=NULL  this means we
554            did the node-swap but now the tree still contains the old
555            node  which was freed in the destructor. Not good.
556         */
557         if (temp) {
558                 temp->key32    = node->key32;
559                 temp->rb_color = node->rb_color;
560
561                 temp->data = node->data;
562                 talloc_steal(temp->data, temp);
563
564                 temp->parent = node->parent;
565                 if (temp->parent) {
566                         if (temp->parent->left == node) {
567                                 temp->parent->left = temp;
568                         } else {
569                                 temp->parent->right = temp;
570                         }
571                 }
572
573                 temp->left = node->left;
574                 if (temp->left) {
575                         temp->left->parent = temp;
576                 }
577                 temp->right = node->right;
578                 if (temp->right) {
579                         temp->right->parent = temp;
580                 }
581
582                 if (temp->tree->root == node) {
583                         temp->tree->root = temp;
584                 }
585         }
586
587         if ( (node->tree->flags & TRBT_AUTOFREE)
588         &&   (node->tree->root == NULL) ) {
589                 talloc_free(node->tree);
590         }
591
592         return;
593 }
594
595 /*
596   destroy a node and remove it from its tree
597  */
598 static int node_destructor(trbt_node_t *node)
599 {
600         delete_node(node);
601
602         return 0;
603 }
604
605 static inline trbt_node_t *
606 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
607 {
608         trbt_node_t *node;
609
610         node=talloc_zero(tree, trbt_node_t);
611         if (node == NULL) {
612                 fprintf(stderr, "Failed to allocate memory for rb node\n");
613                 return NULL;
614         }
615
616         node->tree=tree;
617         node->rb_color=TRBT_BLACK;
618         node->parent=parent;
619         node->left=NULL;
620         node->right=NULL;
621         node->key32=key;
622         node->data = data;
623
624         /* let this node hang off data so that it is removed when
625            data is freed
626          */
627         talloc_steal(data, node);
628         talloc_set_destructor(node, node_destructor);
629
630         return node;
631 }
632
633 /* insert a new node in the tree.
634    if there is already a node with a matching key in the tree
635    we replace it with the new data and return a pointer to the old data
636    in case the caller wants to take any special action
637  */
638 void *
639 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
640 {
641         trbt_node_t *node;
642
643         node=tree->root;
644
645         /* is this the first node ?*/
646         if(!node){
647                 node = trbt_create_node(tree, NULL, key, data);
648
649                 tree->root=node;
650                 return NULL;
651         }
652
653         /* it was not the new root so walk the tree until we find where to
654          * insert this new leaf.
655          */
656         while(1){
657                 /* this node already exists, replace data and return the
658                    old data
659                  */
660                 if(key==node->key32){
661                         void *old_data;
662
663                         old_data = node->data;
664                         node->data  = data;
665                         /* Let the node now be owned by the new data
666                            so the node is freed when the enw data is released
667                         */
668                         talloc_steal(node->data, node);
669
670                         return old_data;
671                 }
672                 if(key<node->key32) {
673                         if(!node->left){
674                                 /* new node to the left */
675                                 trbt_node_t *new_node;
676
677                                 new_node = trbt_create_node(tree, node, key, data);
678                                 node->left=new_node;
679                                 node=new_node;
680
681                                 break;
682                         }
683                         node=node->left;
684                         continue;
685                 }
686                 if(key>node->key32) {
687                         if(!node->right){
688                                 /* new node to the right */
689                                 trbt_node_t *new_node;
690
691                                 new_node = trbt_create_node(tree, node, key, data);
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