lib/tsearch.c

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