lib/tsearch.c

   1 /* Copyright (C) 1995, 1996, 1997, 2000, 2005 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, write to the Free
  17    Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18    02110-1301 USA.  */
  19
  20 /* Tree search for red/black trees.
  21    The algorithm for adding nodes is taken from one of the many "Algorithms"
  22    books by Robert Sedgewick, although the implementation differs.
  23    The algorithm for deleting nodes can probably be found in a book named
  24    "Introduction to Algorithms" by Cormen/Leiserson/Rivest.  At least that's
  25    the book that my professor took most algorithms from during the "Data
  26    Structures" course...
  27
  28    Totally public domain.  */
  29
  30 /* Red/black trees are binary trees in which the edges are colored either red
  31    or black.  They have the following properties:
  32    1. The number of black edges on every path from the root to a leaf is
  33       constant.
  34    2. No two red edges are adjacent.
  35    Therefore there is an upper bound on the length of every path, it's
  36    O(log n) where n is the number of nodes in the tree.  No path can be longer
  37    than 1+2*P where P is the length of the shortest path in the tree.
  38    Useful for the implementation:
  39    3. If one of the children of a node is NULL, then the other one is red
  40       (if it exists).
  41
  42    In the implementation, not the edges are colored, but the nodes.  The color
  43    interpreted as the color of the edge leading to this node.  The color is
  44    meaningless for the root node, but we color the root node black for
  45    convenience.  All added nodes are red initially.
  46
  47    Adding to a red/black tree is rather easy.  The right place is searched
  48    with a usual binary tree search.  Additionally, whenever a node N is
  49    reached that has two red successors, the successors are colored black and
  50    the node itself colored red.  This moves red edges up the tree where they
  51    pose less of a problem once we get to really insert the new node.  Changing
  52    N's color to red may violate rule 2, however, so rotations may become
  53    necessary to restore the invariants.  Adding a new red leaf may violate
  54    the same rule, so afterwards an additional check is run and the tree
  55    possibly rotated.
  56
  57    Deleting is hairy.  There are mainly two nodes involved: the node to be
  58    deleted (n1), and another node that is to be unchained from the tree (n2).
  59    If n1 has a successor (the node with a smallest key that is larger than
  60    n1), then the successor becomes n2 and its contents are copied into n1,
  61    otherwise n1 becomes n2.
  62    Unchaining a node may violate rule 1: if n2 is black, one subtree is
  63    missing one black edge afterwards.  The algorithm must try to move this
  64    error upwards towards the root, so that the subtree that does not have
  65    enough black edges becomes the whole tree.  Once that happens, the error
  66    has disappeared.  It may not be necessary to go all the way up, since it
  67    is possible that rotations and recoloring can fix the error before that.
  68
  69    Although the deletion algorithm must walk upwards through the tree, we
  70    do not store parent pointers in the nodes.  Instead, delete allocates a
  71    small array of parent pointers and fills it while descending the tree.
  72    Since we know that the length of a path is O(log n), where n is the number
  73    of nodes, this is likely to use less memory.  */
  74
  75 /* Tree rotations look like this:
  76       A                C
  77      / \              / \
  78     B   C            A   G
  79    / \ / \  -->     / \
  80    D E F G         B   F
  81                   / \
  82                  D   E
  83
  84    In this case, A has been rotated left.  This preserves the ordering of the
  85    binary tree.  */
  86
  87 #ifdef HAVE_CONFIG_H
  88 # include <config.h>
  89 #endif
  90
  91 #if __GNUC__
  92 # define alloca __builtin_alloca
  93 #else
  94 # if HAVE_ALLOCA_H
  95 #  include <alloca.h>
  96 # else
  97 #  ifdef _AIX
  98  #  pragma alloca
  99 #  else
 100 char *alloca ();
 101 #  endif
 102 # endif
 103 #endif
 104
 105 #include <stdlib.h>
 106 #include <string.h>
 107 #include <search.h>
 108
 109 #ifndef weak_alias
 110 # define __tsearch tsearch
 111 # define __tfind tfind
 112 # define __tdelete tdelete
 113 # define __twalk twalk
 114 # define __tdestroy tdestroy
 115 #endif
 116
 117 #ifndef _LIBC
 118 # define weak_alias(f,g)
 119 # define internal_function
 120 #endif
 121
 122 typedef struct node_t
 123 {
 124   /* Callers expect this to be the first element in the structure - do not
 125      move!  */
 126   const void *key;
 127   struct node_t *left;
 128   struct node_t *right;
 129   unsigned int red:1;
 130 } *node;
 131 typedef const struct node_t *const_node;
 132
 133 #undef DEBUGGING
 134
 135 #ifdef DEBUGGING
 136
 137 /* Routines to check tree invariants.  */
 138
 139 # include <assert.h>
 140
 141 # define CHECK_TREE(a) check_tree(a)
 142
 143 static void
 144 check_tree_recurse (node p, int d_sofar, int d_total)
 145 {
 146   if (p == NULL)
 147     {
 148       assert (d_sofar == d_total);
 149       return;
 150     }
 151
 152   check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total);
 153   check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total);
 154   if (p->left)
 155     assert (!(p->left->red && p->red));
 156   if (p->right)
 157     assert (!(p->right->red && p->red));
 158 }
 159
 160 static void
 161 check_tree (node root)
 162 {
 163   int cnt = 0;
 164   node p;
 165   if (root == NULL)
 166     return;
 167   root->red = 0;
 168   for(p = root->left; p; p = p->left)
 169     cnt += !p->red;
 170   check_tree_recurse (root, 0, cnt);
 171 }
 172
 173
 174 #else
 175
 176 # define CHECK_TREE(a)
 177
 178 #endif
 179
 180 /* Possibly "split" a node with two red successors, and/or fix up two red
 181    edges in a row.  ROOTP is a pointer to the lowest node we visited, PARENTP
 182    and GPARENTP pointers to its parent/grandparent.  P_R and GP_R contain the
 183    comparison values that determined which way was taken in the tree to reach
 184    ROOTP.  MODE is 1 if we need not do the split, but must check for two red
 185    edges between GPARENTP and ROOTP.  */
 186 static void
 187 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 188                         int p_r, int gp_r, int mode)
 189 {
 190   node root = *rootp;
 191   node *rp, *lp;
 192   rp = &(*rootp)->right;
 193   lp = &(*rootp)->left;
 194
 195   /* See if we have to split this node (both successors red).  */
 196   if (mode == 1
 197       || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
 198     {
 199       /* This node becomes red, its successors black.  */
 200       root->red = 1;
 201       if (*rp)
 202         (*rp)->red = 0;
 203       if (*lp)
 204         (*lp)->red = 0;
 205
 206       /* If the parent of this node is also red, we have to do
 207          rotations.  */
 208       if (parentp != NULL && (*parentp)->red)
 209         {
 210           node gp = *gparentp;
 211           node p = *parentp;
 212           /* There are two main cases:
 213              1. The edge types (left or right) of the two red edges differ.
 214              2. Both red edges are of the same type.
 215              There exist two symmetries of each case, so there is a total of
 216              4 cases.  */
 217           if ((p_r > 0) != (gp_r > 0))
 218             {
 219               /* Put the child at the top of the tree, with its parent
 220                  and grandparent as successors.  */
 221               p->red = 1;
 222               gp->red = 1;
 223               root->red = 0;
 224               if (p_r < 0)
 225                 {
 226                   /* Child is left of parent.  */
 227                   p->left = *rp;
 228                   *rp = p;
 229                   gp->right = *lp;
 230                   *lp = gp;
 231                 }
 232               else
 233                 {
 234                   /* Child is right of parent.  */
 235                   p->right = *lp;
 236                   *lp = p;
 237                   gp->left = *rp;
 238                   *rp = gp;
 239                 }
 240               *gparentp = root;
 241             }
 242           else
 243             {
 244               *gparentp = *parentp;
 245               /* Parent becomes the top of the tree, grandparent and
 246                  child are its successors.  */
 247               p->red = 0;
 248               gp->red = 1;
 249               if (p_r < 0)
 250                 {
 251                   /* Left edges.  */
 252                   gp->left = p->right;
 253                   p->right = gp;
 254                 }
 255               else
 256                 {
 257                   /* Right edges.  */
 258                   gp->right = p->left;
 259                   p->left = gp;
 260                 }
 261             }
 262         }
 263     }
 264 }
 265
 266 /* Find or insert datum into search tree.
 267    KEY is the key to be located, ROOTP is the address of tree root,
 268    COMPAR the ordering function.  */
 269 void *
 270 __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 271 {
 272   node q;
 273   node *parentp = NULL, *gparentp = NULL;
 274   node *rootp = (node *) vrootp;
 275   node *nextp;
 276   int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler.  */
 277
 278   if (rootp == NULL)
 279     return NULL;
 280
 281   /* This saves some additional tests below.  */
 282   if (*rootp != NULL)
 283     (*rootp)->red = 0;
 284
 285   CHECK_TREE (*rootp);
 286
 287   nextp = rootp;
 288   while (*nextp != NULL)
 289     {
 290       node root = *rootp;
 291       r = (*compar) (key, root->key);
 292       if (r == 0)
 293         return root;
 294
 295       maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
 296       /* If that did any rotations, parentp and gparentp are now garbage.
 297          That doesn't matter, because the values they contain are never
 298          used again in that case.  */
 299
 300       nextp = r < 0 ? &root->left : &root->right;
 301       if (*nextp == NULL)
 302         break;
 303
 304       gparentp = parentp;
 305       parentp = rootp;
 306       rootp = nextp;
 307
 308       gp_r = p_r;
 309       p_r = r;
 310     }
 311
 312   q = (struct node_t *) malloc (sizeof (struct node_t));
 313   if (q != NULL)
 314     {
 315       *nextp = q;                       /* link new node to old */
 316       q->key = key;                     /* initialize new node */
 317       q->red = 1;
 318       q->left = q->right = NULL;
 319     }
 320   if (nextp != rootp)
 321     /* There may be two red edges in a row now, which we must avoid by
 322        rotating the tree.  */
 323     maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
 324
 325   return q;
 326 }
 327 #ifdef weak_alias
 328 weak_alias (__tsearch, tsearch)
 329 #endif
 330
 331
 332 /* Find datum in search tree.
 333    KEY is the key to be located, ROOTP is the address of tree root,
 334    COMPAR the ordering function.  */
 335 void *
 336 __tfind (key, vrootp, compar)
 337      const void *key;
 338      void *const *vrootp;
 339      __compar_fn_t compar;
 340 {
 341   node *rootp = (node *) vrootp;
 342
 343   if (rootp == NULL)
 344     return NULL;
 345
 346   CHECK_TREE (*rootp);
 347
 348   while (*rootp != NULL)
 349     {
 350       node root = *rootp;
 351       int r;
 352
 353       r = (*compar) (key, root->key);
 354       if (r == 0)
 355         return root;
 356
 357       rootp = r < 0 ? &root->left : &root->right;
 358     }
 359   return NULL;
 360 }
 361 #ifdef weak_alias
 362 weak_alias (__tfind, tfind)
 363 #endif
 364
 365
 366 /* Delete node with given key.
 367    KEY is the key to be deleted, ROOTP is the address of the root of tree,
 368    COMPAR the comparison function.  */
 369 void *
 370 __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 371 {
 372   node p, q, r, retval;
 373   int cmp;
 374   node *rootp = (node *) vrootp;
 375   node root, unchained;
 376   /* Stack of nodes so we remember the parents without recursion.  It's
 377      _very_ unlikely that there are paths longer than 40 nodes.  The tree
 378      would need to have around 250.000 nodes.  */
 379   int stacksize = 40;
 380   int sp = 0;
 381   node **nodestack = (node **) alloca (sizeof (node *) * stacksize);
 382
 383   if (rootp == NULL)
 384     return NULL;
 385   p = *rootp;
 386   if (p == NULL)
 387     return NULL;
 388
 389   CHECK_TREE (p);
 390
 391   while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
 392     {
 393       if (sp == stacksize)
 394         {
 395           node **newstack;
 396           stacksize += 20;
 397           newstack = (node **) alloca (sizeof (node *) * stacksize);
 398           nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
 399         }
 400
 401       nodestack[sp++] = rootp;
 402       p = *rootp;
 403       rootp = ((cmp < 0)
 404                ? &(*rootp)->left
 405                : &(*rootp)->right);
 406       if (*rootp == NULL)
 407         return NULL;
 408     }
 409
 410   /* This is bogus if the node to be deleted is the root... this routine
 411      really should return an integer with 0 for success, -1 for failure
 412      and errno = ESRCH or something.  */
 413   retval = p;
 414
 415   /* We don't unchain the node we want to delete. Instead, we overwrite
 416      it with its successor and unchain the successor.  If there is no
 417      successor, we really unchain the node to be deleted.  */
 418
 419   root = *rootp;
 420
 421   r = root->right;
 422   q = root->left;
 423
 424   if (q == NULL || r == NULL)
 425     unchained = root;
 426   else
 427     {
 428       node *parent = rootp, *up = &root->right;
 429       for (;;)
 430         {
 431           if (sp == stacksize)
 432             {
 433               node **newstack;
 434               stacksize += 20;
 435               newstack = (node **) alloca (sizeof (node *) * stacksize);
 436               nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
 437             }
 438           nodestack[sp++] = parent;
 439           parent = up;
 440           if ((*up)->left == NULL)
 441             break;
 442           up = &(*up)->left;
 443         }
 444       unchained = *up;
 445     }
 446
 447   /* We know that either the left or right successor of UNCHAINED is NULL.
 448      R becomes the other one, it is chained into the parent of UNCHAINED.  */
 449   r = unchained->left;
 450   if (r == NULL)
 451     r = unchained->right;
 452   if (sp == 0)
 453     *rootp = r;
 454   else
 455     {
 456       q = *nodestack[sp-1];
 457       if (unchained == q->right)
 458         q->right = r;
 459       else
 460         q->left = r;
 461     }
 462
 463   if (unchained != root)
 464     root->key = unchained->key;
 465   if (!unchained->red)
 466     {
 467       /* Now we lost a black edge, which means that the number of black
 468          edges on every path is no longer constant.  We must balance the
 469          tree.  */
 470       /* NODESTACK now contains all parents of R.  R is likely to be NULL
 471          in the first iteration.  */
 472       /* NULL nodes are considered black throughout - this is necessary for
 473          correctness.  */
 474       while (sp > 0 && (r == NULL || !r->red))
 475         {
 476           node *pp = nodestack[sp - 1];
 477           p = *pp;
 478           /* Two symmetric cases.  */
 479           if (r == p->left)
 480             {
 481               /* Q is R's brother, P is R's parent.  The subtree with root
 482                  R has one black edge less than the subtree with root Q.  */
 483               q = p->right;
 484               if (q != NULL && q->red)
 485                 {
 486                   /* If Q is red, we know that P is black. We rotate P left
 487                      so that Q becomes the top node in the tree, with P below
 488                      it.  P is colored red, Q is colored black.
 489                      This action does not change the black edge count for any
 490                      leaf in the tree, but we will be able to recognize one
 491                      of the following situations, which all require that Q
 492                      is black.  */
 493                   q->red = 0;
 494                   p->red = 1;
 495                   /* Left rotate p.  */
 496                   p->right = q->left;
 497                   q->left = p;
 498                   *pp = q;
 499                   /* Make sure pp is right if the case below tries to use
 500                      it.  */
 501                   nodestack[sp++] = pp = &q->left;
 502                   q = p->right;
 503                 }
 504               /* We know that Q can't be NULL here.  We also know that Q is
 505                  black.  */
 506               if ((q->left == NULL || !q->left->red)
 507                   && (q->right == NULL || !q->right->red))
 508                 {
 509                   /* Q has two black successors.  We can simply color Q red.
 510                      The whole subtree with root P is now missing one black
 511                      edge.  Note that this action can temporarily make the
 512                      tree invalid (if P is red).  But we will exit the loop
 513                      in that case and set P black, which both makes the tree
 514                      valid and also makes the black edge count come out
 515                      right.  If P is black, we are at least one step closer
 516                      to the root and we'll try again the next iteration.  */
 517                   q->red = 1;
 518                   r = p;
 519                 }
 520               else
 521                 {
 522                   /* Q is black, one of Q's successors is red.  We can
 523                      repair the tree with one operation and will exit the
 524                      loop afterwards.  */
 525                   if (q->right == NULL || !q->right->red)
 526                     {
 527                       /* The left one is red.  We perform the same action as
 528                          in maybe_split_for_insert where two red edges are
 529                          adjacent but point in different directions:
 530                          Q's left successor (let's call it Q2) becomes the
 531                          top of the subtree we are looking at, its parent (Q)
 532                          and grandparent (P) become its successors. The former
 533                          successors of Q2 are placed below P and Q.
 534                          P becomes black, and Q2 gets the color that P had.
 535                          This changes the black edge count only for node R and
 536                          its successors.  */
 537                       node q2 = q->left;
 538                       q2->red = p->red;
 539                       p->right = q2->left;
 540                       q->left = q2->right;
 541                       q2->right = q;
 542                       q2->left = p;
 543                       *pp = q2;
 544                       p->red = 0;
 545                     }
 546                   else
 547                     {
 548                       /* It's the right one.  Rotate P left. P becomes black,
 549                          and Q gets the color that P had.  Q's right successor
 550                          also becomes black.  This changes the black edge
 551                          count only for node R and its successors.  */
 552                       q->red = p->red;
 553                       p->red = 0;
 554
 555                       q->right->red = 0;
 556
 557                       /* left rotate p */
 558                       p->right = q->left;
 559                       q->left = p;
 560                       *pp = q;
 561                     }
 562
 563                   /* We're done.  */
 564                   sp = 1;
 565                   r = NULL;
 566                 }
 567             }
 568           else
 569             {
 570               /* Comments: see above.  */
 571               q = p->left;
 572               if (q != NULL && q->red)
 573                 {
 574                   q->red = 0;
 575                   p->red = 1;
 576                   p->left = q->right;
 577                   q->right = p;
 578                   *pp = q;
 579                   nodestack[sp++] = pp = &q->right;
 580                   q = p->left;
 581                 }
 582               if ((q->right == NULL || !q->right->red)
 583                        && (q->left == NULL || !q->left->red))
 584                 {
 585                   q->red = 1;
 586                   r = p;
 587                 }
 588               else
 589                 {
 590                   if (q->left == NULL || !q->left->red)
 591                     {
 592                       node q2 = q->right;
 593                       q2->red = p->red;
 594                       p->left = q2->right;
 595                       q->right = q2->left;
 596                       q2->left = q;
 597                       q2->right = p;
 598                       *pp = q2;
 599                       p->red = 0;
 600                     }
 601                   else
 602                     {
 603                       q->red = p->red;
 604                       p->red = 0;
 605                       q->left->red = 0;
 606                       p->left = q->right;
 607                       q->right = p;
 608                       *pp = q;
 609                     }
 610                   sp = 1;
 611                   r = NULL;
 612                 }
 613             }
 614           --sp;
 615         }
 616       if (r != NULL)
 617         r->red = 0;
 618     }
 619
 620   free (unchained);
 621   return retval;
 622 }
 623 #ifdef weak_alias
 624 weak_alias (__tdelete, tdelete)
 625 #endif
 626
 627
 628 /* Walk the nodes of a tree.
 629    ROOT is the root of the tree to be walked, ACTION the function to be
 630    called at each node.  LEVEL is the level of ROOT in the whole tree.  */
 631 static void
 632 internal_function
 633 trecurse (const void *vroot, __action_fn_t action, int level)
 634 {
 635   const_node root = (const_node) vroot;
 636
 637   if (root->left == NULL && root->right == NULL)
 638     (*action) (root, leaf, level);
 639   else
 640     {
 641       (*action) (root, preorder, level);
 642       if (root->left != NULL)
 643         trecurse (root->left, action, level + 1);
 644       (*action) (root, postorder, level);
 645       if (root->right != NULL)
 646         trecurse (root->right, action, level + 1);
 647       (*action) (root, endorder, level);
 648     }
 649 }
 650
 651
 652 /* Walk the nodes of a tree.
 653    ROOT is the root of the tree to be walked, ACTION the function to be
 654    called at each node.  */
 655 void
 656 __twalk (const void *vroot, __action_fn_t action)
 657 {
 658   const_node root = (const_node) vroot;
 659
 660   CHECK_TREE (root);
 661
 662   if (root != NULL && action != NULL)
 663     trecurse (root, action, 0);
 664 }
 665 #ifdef weak_alias
 666 weak_alias (__twalk, twalk)
 667 #endif
 668
 669
 670
 671 /* The standardized functions miss an important functionality: the
 672    tree cannot be removed easily.  We provide a function to do this.  */
 673 static void
 674 internal_function
 675 tdestroy_recurse (node root, void (*freefct)(void *))
 676 {
 677   if (root->left != NULL)
 678     tdestroy_recurse (root->left, freefct);
 679   if (root->right != NULL)
 680     tdestroy_recurse (root->right, freefct);
 681   (*freefct) ((void *) root->key);
 682   /* Free the node itself.  */
 683   free (root);
 684 }
 685
 686 void
 687 __tdestroy (void *vroot, void (*freefct)(void *))
 688 {
 689   node root = (node) vroot;
 690
 691   CHECK_TREE (root);
 692
 693   if (root != NULL)
 694     tdestroy_recurse (root, freefct);
 695 }
 696 #ifdef weak_alias
 697 weak_alias (__tdestroy, tdestroy)
 698 #endif