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