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