git.ozlabs.org Git - ccan/blob - 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 successor 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