lib/tsearch.c

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