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