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