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(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, int from_destructor)
 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, from_destructor);
 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 (!from_destructor) {
 554                 talloc_free(node);
 555         }
 556
 557         /* if we came from a destructor and temp!=NULL  this means we
 558            did the node-swap but now the tree still contains the old
 559            node  which was freed in the destructor. Not good.
 560         */
 561         if (from_destructor && temp) {
 562                 temp->key32    = node->key32;
 563                 temp->rb_color = node->rb_color;
 564
 565                 temp->data = node->data;
 566                 talloc_steal(temp->data, temp);
 567
 568                 temp->parent = node->parent;
 569                 if (temp->parent) {
 570                         if (temp->parent->left == node) {
 571                                 temp->parent->left = temp;
 572                         } else {
 573                                 temp->parent->right = temp;
 574                         }
 575                 }
 576
 577                 temp->left = node->left;
 578                 if (temp->left) {
 579                         temp->left->parent = temp;
 580                 }
 581                 temp->right = node->right;
 582                 if (temp->right) {
 583                         temp->right->parent = temp;
 584                 }
 585
 586                 if (temp->tree->root == node) {
 587                         temp->tree->root = temp;
 588                 }
 589         }
 590
 591         if ( (node->tree->flags & TRBT_AUTOFREE)
 592         &&   (node->tree->root == NULL) ) {
 593                 talloc_free(node->tree);
 594         }
 595
 596         return;
 597 }
 598
 599 /*
 600   destroy a node and remove it from its tree
 601  */
 602 static int node_destructor(trbt_node_t *node)
 603 {
 604         delete_node(node, 1);
 605
 606         return 0;
 607 }
 608
 609 static inline trbt_node_t *
 610 trbt_create_node(trbt_tree_t *tree, trbt_node_t *parent, uint32_t key, void *data)
 611 {
 612         trbt_node_t *node;
 613
 614         node=talloc_zero(tree, trbt_node_t);
 615         if (node == NULL) {
 616                 fprintf(stderr, "Failed to allocate memory for rb node\n");
 617                 return NULL;
 618         }
 619
 620         node->tree=tree;
 621         node->rb_color=TRBT_BLACK;
 622         node->parent=parent;
 623         node->left=NULL;
 624         node->right=NULL;
 625         node->key32=key;
 626         node->data = data;
 627
 628         /* let this node hang off data so that it is removed when
 629            data is freed
 630          */
 631         talloc_steal(data, node);
 632         talloc_set_destructor(node, node_destructor);
 633
 634         return node;
 635 }
 636
 637 /* insert a new node in the tree.
 638    if there is already a node with a matching key in the tree
 639    we replace it with the new data and return a pointer to the old data
 640    in case the caller wants to take any special action
 641  */
 642 void *
 643 trbt_insert32(trbt_tree_t *tree, uint32_t key, void *data)
 644 {
 645         trbt_node_t *node;
 646
 647         node=tree->root;
 648
 649         /* is this the first node ?*/
 650         if(!node){
 651                 node = trbt_create_node(tree, NULL, key, data);
 652
 653                 tree->root=node;
 654                 return NULL;
 655         }
 656
 657         /* it was not the new root so walk the tree until we find where to
 658          * insert this new leaf.
 659          */
 660         while(1){
 661                 /* this node already exists, replace data and return the
 662                    old data
 663                  */
 664                 if(key==node->key32){
 665                         void *old_data;
 666
 667                         old_data = node->data;
 668                         node->data  = data;
 669                         /* Let the node now be owned by the new data
 670                            so the node is freed when the enw data is released
 671                         */
 672                         talloc_steal(node->data, node);
 673
 674                         return old_data;
 675                 }
 676                 if(key<node->key32) {
 677                         if(!node->left){
 678                                 /* new node to the left */
 679                                 trbt_node_t *new_node;
 680
 681                                 new_node = trbt_create_node(tree, node, key, data);
 682                                 node->left=new_node;
 683                                 node=new_node;
 684
 685                                 break;
 686                         }
 687                         node=node->left;
 688                         continue;
 689                 }
 690                 if(key>node->key32) {
 691                         if(!node->right){
 692                                 /* new node to the right */
 693                                 trbt_node_t *new_node;
 694
 695                                 new_node = trbt_create_node(tree, node, key, data);
 696                                 node->right=new_node;
 697                                 node=new_node;
 698                                 break;
 699                         }
 700                         node=node->right;
 701                         continue;
 702                 }
 703         }
 704
 705         /* node will now point to the newly created node */
 706         node->rb_color=TRBT_RED;
 707         trbt_insert_case1(tree, node);
 708         return NULL;
 709 }
 710
 711 void *
 712 trbt_lookup32(trbt_tree_t *tree, uint32_t key)
 713 {
 714         trbt_node_t *node;
 715
 716         node=tree->root;
 717
 718         while(node){
 719                 if(key==node->key32){
 720                         return node->data;
 721                 }
 722                 if(key<node->key32){
 723                         node=node->left;
 724                         continue;
 725                 }
 726                 if(key>node->key32){
 727                         node=node->right;
 728                         continue;
 729                 }
 730         }
 731         return NULL;
 732 }
 733
 734
 735 /* This deletes a node from the tree.
 736    Note that this does not release the data that the node points to
 737 */
 738 void
 739 trbt_delete32(trbt_tree_t *tree, uint32_t key)
 740 {
 741         trbt_node_t *node;
 742
 743         node=tree->root;
 744
 745         while(node){
 746                 if(key==node->key32){
 747                         delete_node(node, 0);
 748                         return;
 749                 }
 750                 if(key<node->key32){
 751                         node=node->left;
 752                         continue;
 753                 }
 754                 if(key>node->key32){
 755                         node=node->right;
 756                         continue;
 757                 }
 758         }
 759 }
 760
 761
 762 void
 763 trbt_insert32_callback(trbt_tree_t *tree, uint32_t key, void *(*callback)(void *param, void *data), void *param)
 764 {
 765         trbt_node_t *node;
 766
 767         node=tree->root;
 768
 769         /* is this the first node ?*/
 770         if(!node){
 771                 node = trbt_create_node(tree, NULL, key,
 772                                 callback(param, NULL));
 773
 774                 tree->root=node;
 775                 return;
 776         }
 777
 778         /* it was not the new root so walk the tree until we find where to
 779          * insert this new leaf.
 780          */
 781         while(1){
 782                 /* this node already exists, replace it
 783                  */
 784                 if(key==node->key32){
 785                         node->data  = callback(param, node->data);
 786                         talloc_steal(node->data, node);
 787
 788                         return;
 789                 }
 790                 if(key<node->key32) {
 791                         if(!node->left){
 792                                 /* new node to the left */
 793                                 trbt_node_t *new_node;
 794
 795                                 new_node = trbt_create_node(tree, node, key,
 796                                                 callback(param, NULL));
 797                                 node->left=new_node;
 798                                 node=new_node;
 799
 800                                 break;
 801                         }
 802                         node=node->left;
 803                         continue;
 804                 }
 805                 if(key>node->key32) {
 806                         if(!node->right){
 807                                 /* new node to the right */
 808                                 trbt_node_t *new_node;
 809
 810                                 new_node = trbt_create_node(tree, node, key,
 811                                                 callback(param, NULL));
 812                                 node->right=new_node;
 813                                 node=new_node;
 814                                 break;
 815                         }
 816                         node=node->right;
 817                         continue;
 818                 }
 819         }
 820
 821         /* node will now point to the newly created node */
 822         node->rb_color=TRBT_RED;
 823         trbt_insert_case1(tree, node);
 824         return;
 825 }
 826
 827
 828 struct trbt_array_param {
 829         void *(*callback)(void *param, void *data);
 830         void *param;
 831         uint32_t keylen;
 832         uint32_t *key;
 833         trbt_tree_t *tree;
 834 };
 835 static void *array_insert_callback(void *p, void *data)
 836 {
 837         struct trbt_array_param *param = (struct trbt_array_param *)p;
 838         trbt_tree_t *tree = NULL;
 839
 840
 841         /* if keylen has reached 0 we are done and can call the users
 842            callback function with the users parameters
 843         */
 844         if (param->keylen == 0) {
 845                 return param->callback(param->param, data);
 846         }
 847
 848
 849         /* keylen is not zero yes so we must create/process more subtrees */
 850         /* if data is NULL this means we did not yet have a subtree here
 851            and we must create one.
 852         */
 853         if (data == NULL) {
 854                 /* create a new subtree and hang it off our current tree
 855                    set it to autofree so that the tree is freed when
 856                    the last node in it has been released.
 857                 */
 858                 tree = trbt_create(param->tree, TRBT_AUTOFREE);
 859         } else {
 860                 /* we already have a subtree for this path */
 861                 tree = (trbt_tree_t *)data;
 862         }
 863
 864         trbt_insertarray32_callback(tree, param->keylen, param->key, param->callback, param->param);
 865
 866         /* now return either the old tree we got in *data or the new tree
 867            we created to our caller so he can update his pointer in his
 868            tree to point to our subtree
 869         */
 870         return tree;
 871 }
 872
 873
 874
 875 /* insert into the tree using an array of uint32 as a key */
 876 void
 877 trbt_insertarray32_callback(trbt_tree_t *tree, uint32_t keylen, uint32_t *key, void *(*cb)(void *param, void *data), void *pm)
 878 {
 879         struct trbt_array_param tap;
 880
 881         /* keylen-1 and key[1]  since the call to insert32 will consume the
 882            first part of the key.
 883         */
 884         tap.callback= cb;
 885         tap.param   = pm;
 886         tap.keylen  = keylen-1;
 887         tap.key     = &key[1];
 888         tap.tree    = tree;
 889
 890         trbt_insert32_callback(tree, key[0], array_insert_callback, &tap);
 891 }
 892
 893 /* lookup the tree using an array of uint32 as a key */
 894 void *
 895 trbt_lookuparray32(trbt_tree_t *tree, uint32_t keylen, uint32_t *key)
 896 {
 897         /* if keylen is 1 we can do a regular lookup and return this to the
 898            user
 899         */
 900         if (keylen == 1) {
 901                 return trbt_lookup32(tree, key[0]);
 902         }
 903
 904         /* we need to lookup the next subtree */
 905         tree = trbt_lookup32(tree, key[0]);
 906         if (tree == NULL) {
 907                 /* the key does not exist, return NULL */
 908                 return NULL;
 909         }
 910
 911         /* now lookup the next part of the key in our new tree */
 912         return trbt_lookuparray32(tree, keylen-1, &key[1]);
 913 }
 914
 915
 916 /* traverse a tree starting at node */
 917 static void
 918 trbt_traversearray32_node(trbt_node_t *node, uint32_t keylen,
 919         void (*callback)(void *param, void *data),
 920         void *param)
 921 {
 922         if (node->left) {
 923                 trbt_traversearray32_node(node->left, keylen, callback, param);
 924         }
 925
 926         /* this is the smallest node in this subtree
 927            if keylen is 0 this means we can just call the callback
 928            otherwise we must pull the next subtree and traverse that one as well
 929         */
 930         if (keylen == 0) {
 931                 callback(param, node->data);
 932         } else {
 933                 trbt_traversearray32(node->data, keylen, callback, param);
 934         }
 935
 936         if (node->right) {
 937                 trbt_traversearray32_node(node->right, keylen, callback, param);
 938         }
 939 }
 940
 941
 942 /* traverse the tree using an array of uint32 as a key */
 943 void
 944 trbt_traversearray32(trbt_tree_t *tree, uint32_t keylen,
 945         void (*callback)(void *param, void *data),
 946         void *param)
 947 {
 948         trbt_node_t *node;
 949
 950         if (tree == NULL) {
 951                 return;
 952         }
 953
 954         node=tree->root;
 955         if (node == NULL) {
 956                 return;
 957         }
 958
 959         trbt_traversearray32_node(node, keylen-1, callback, param);
 960 }
 961
 962
 963 /* this function will return the first node in a tree where
 964    the key is an array of uint32_t
 965 */
 966 void *
 967 trbt_findfirstarray32(trbt_tree_t *tree, uint32_t keylen)
 968 {
 969         trbt_node_t *node;
 970
 971         if (keylen < 1) {
 972                 return NULL;
 973         }
 974
 975         if (tree == NULL) {
 976                 return NULL;
 977         }
 978
 979         node=tree->root;
 980         if (node == NULL) {
 981                 return NULL;
 982         }
 983
 984         while (node->left) {
 985                 node = node->left;
 986         }
 987
 988         /* we found our node so return the data */
 989         if (keylen == 1) {
 990                 return node->data;
 991         }
 992
 993         /* we are still traversing subtrees so find the first node in the
 994            next level of trees
 995         */
 996         return trbt_findfirstarray32(node->data, keylen-1);
 997 }
 998
 999