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