lib/tsearch.c

   1 /* Copyright (C) 1995-1997, 2000, 2006-2007, 2009-2020 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 <https://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 #if GNULIB_defined_tsearch
 178
 179 /* Possibly "split" a node with two red successors, and/or fix up two red
 180    edges in a row.  ROOTP is a pointer to the lowest node we visited, PARENTP
 181    and GPARENTP pointers to its parent/grandparent.  P_R and GP_R contain the
 182    comparison values that determined which way was taken in the tree to reach
 183    ROOTP.  MODE is 1 if we need not do the split, but must check for two red
 184    edges between GPARENTP and ROOTP.  */
 185 static void
 186 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
 187                         int p_r, int gp_r, int mode)
 188 {
 189   node root = *rootp;
 190   node *rp, *lp;
 191   rp = &(*rootp)->right;
 192   lp = &(*rootp)->left;
 193
 194   /* See if we have to split this node (both successors red).  */
 195   if (mode == 1
 196       || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
 197     {
 198       /* This node becomes red, its successors black.  */
 199       root->red = 1;
 200       if (*rp)
 201         (*rp)->red = 0;
 202       if (*lp)
 203         (*lp)->red = 0;
 204
 205       /* If the parent of this node is also red, we have to do
 206          rotations.  */
 207       if (parentp != NULL && (*parentp)->red)
 208         {
 209           node gp = *gparentp;
 210           node p = *parentp;
 211           /* There are two main cases:
 212              1. The edge types (left or right) of the two red edges differ.
 213              2. Both red edges are of the same type.
 214              There exist two symmetries of each case, so there is a total of
 215              4 cases.  */
 216           if ((p_r > 0) != (gp_r > 0))
 217             {
 218               /* Put the child at the top of the tree, with its parent
 219                  and grandparent as successors.  */
 220               p->red = 1;
 221               gp->red = 1;
 222               root->red = 0;
 223               if (p_r < 0)
 224                 {
 225                   /* Child is left of parent.  */
 226                   p->left = *rp;
 227                   *rp = p;
 228                   gp->right = *lp;
 229                   *lp = gp;
 230                 }
 231               else
 232                 {
 233                   /* Child is right of parent.  */
 234                   p->right = *lp;
 235                   *lp = p;
 236                   gp->left = *rp;
 237                   *rp = gp;
 238                 }
 239               *gparentp = root;
 240             }
 241           else
 242             {
 243               *gparentp = *parentp;
 244               /* Parent becomes the top of the tree, grandparent and
 245                  child are its successors.  */
 246               p->red = 0;
 247               gp->red = 1;
 248               if (p_r < 0)
 249                 {
 250                   /* Left edges.  */
 251                   gp->left = p->right;
 252                   p->right = gp;
 253                 }
 254               else
 255                 {
 256                   /* Right edges.  */
 257                   gp->right = p->left;
 258                   p->left = gp;
 259                 }
 260             }
 261         }
 262     }
 263 }
 264
 265 /* Find or insert datum into search tree.
 266    KEY is the key to be located, ROOTP is the address of tree root,
 267    COMPAR the ordering function.  */
 268 void *
 269 __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 270 {
 271   node q;
 272   node *parentp = NULL, *gparentp = NULL;
 273   node *rootp = (node *) vrootp;
 274   node *nextp;
 275   int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler.  */
 276
 277   if (rootp == NULL)
 278     return NULL;
 279
 280   /* This saves some additional tests below.  */
 281   if (*rootp != NULL)
 282     (*rootp)->red = 0;
 283
 284   CHECK_TREE (*rootp);
 285
 286   nextp = rootp;
 287   while (*nextp != NULL)
 288     {
 289       node root = *rootp;
 290       r = (*compar) (key, root->key);
 291       if (r == 0)
 292         return root;
 293
 294       maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
 295       /* If that did any rotations, parentp and gparentp are now garbage.
 296          That doesn't matter, because the values they contain are never
 297          used again in that case.  */
 298
 299       nextp = r < 0 ? &root->left : &root->right;
 300       if (*nextp == NULL)
 301         break;
 302
 303       gparentp = parentp;
 304       parentp = rootp;
 305       rootp = nextp;
 306
 307       gp_r = p_r;
 308       p_r = r;
 309     }
 310
 311   q = (struct node_t *) malloc (sizeof (struct node_t));
 312   if (q != NULL)
 313     {
 314       *nextp = q;                       /* link new node to old */
 315       q->key = key;                     /* initialize new node */
 316       q->red = 1;
 317       q->left = q->right = NULL;
 318
 319       if (nextp != rootp)
 320         /* There may be two red edges in a row now, which we must avoid by
 321            rotating the tree.  */
 322         maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
 323     }
 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 (const void *key, void *const *vrootp, __compar_fn_t compar)
 337 {
 338   node *rootp = (node *) vrootp;
 339
 340   if (rootp == NULL)
 341     return NULL;
 342
 343   CHECK_TREE (*rootp);
 344
 345   while (*rootp != NULL)
 346     {
 347       node root = *rootp;
 348       int r;
 349
 350       r = (*compar) (key, root->key);
 351       if (r == 0)
 352         return root;
 353
 354       rootp = r < 0 ? &root->left : &root->right;
 355     }
 356   return NULL;
 357 }
 358 #ifdef weak_alias
 359 weak_alias (__tfind, tfind)
 360 #endif
 361
 362
 363 /* Delete node with given key.
 364    KEY is the key to be deleted, ROOTP is the address of the root of tree,
 365    COMPAR the comparison function.  */
 366 void *
 367 __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 368 {
 369   node p, q, r, retval;
 370   int cmp;
 371   node *rootp = (node *) vrootp;
 372   node root, unchained;
 373   /* Stack of nodes so we remember the parents without recursion.  It's
 374      _very_ unlikely that there are paths longer than 40 nodes.  The tree
 375      would need to have around 250.000 nodes.  */
 376   int stacksize = 100;
 377   int sp = 0;
 378   node *nodestack[100];
 379
 380   if (rootp == NULL)
 381     return NULL;
 382   p = *rootp;
 383   if (p == NULL)
 384     return NULL;
 385
 386   CHECK_TREE (p);
 387
 388   while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
 389     {
 390       if (sp == stacksize)
 391         abort ();
 392
 393       nodestack[sp++] = rootp;
 394       p = *rootp;
 395       rootp = ((cmp < 0)
 396                ? &(*rootp)->left
 397                : &(*rootp)->right);
 398       if (*rootp == NULL)
 399         return NULL;
 400     }
 401
 402   /* This is bogus if the node to be deleted is the root... this routine
 403      really should return an integer with 0 for success, -1 for failure
 404      and errno = ESRCH or something.  */
 405   retval = p;
 406
 407   /* We don't unchain the node we want to delete. Instead, we overwrite
 408      it with its successor and unchain the successor.  If there is no
 409      successor, we really unchain the node to be deleted.  */
 410
 411   root = *rootp;
 412
 413   r = root->right;
 414   q = root->left;
 415
 416   if (q == NULL || r == NULL)
 417     unchained = root;
 418   else
 419     {
 420       node *parent = rootp, *up = &root->right;
 421       for (;;)
 422         {
 423           if (sp == stacksize)
 424             abort ();
 425           nodestack[sp++] = parent;
 426           parent = up;
 427           if ((*up)->left == NULL)
 428             break;
 429           up = &(*up)->left;
 430         }
 431       unchained = *up;
 432     }
 433
 434   /* We know that either the left or right successor of UNCHAINED is NULL.
 435      R becomes the other one, it is chained into the parent of UNCHAINED.  */
 436   r = unchained->left;
 437   if (r == NULL)
 438     r = unchained->right;
 439   if (sp == 0)
 440     *rootp = r;
 441   else
 442     {
 443       q = *nodestack[sp-1];
 444       if (unchained == q->right)
 445         q->right = r;
 446       else
 447         q->left = r;
 448     }
 449
 450   if (unchained != root)
 451     root->key = unchained->key;
 452   if (!unchained->red)
 453     {
 454       /* Now we lost a black edge, which means that the number of black
 455          edges on every path is no longer constant.  We must balance the
 456          tree.  */
 457       /* NODESTACK now contains all parents of R.  R is likely to be NULL
 458          in the first iteration.  */
 459       /* NULL nodes are considered black throughout - this is necessary for
 460          correctness.  */
 461       while (sp > 0 && (r == NULL || !r->red))
 462         {
 463           node *pp = nodestack[sp - 1];
 464           p = *pp;
 465           /* Two symmetric cases.  */
 466           if (r == p->left)
 467             {
 468               /* Q is R's brother, P is R's parent.  The subtree with root
 469                  R has one black edge less than the subtree with root Q.  */
 470               q = p->right;
 471               if (q->red)
 472                 {
 473                   /* If Q is red, we know that P is black. We rotate P left
 474                      so that Q becomes the top node in the tree, with P below
 475                      it.  P is colored red, Q is colored black.
 476                      This action does not change the black edge count for any
 477                      leaf in the tree, but we will be able to recognize one
 478                      of the following situations, which all require that Q
 479                      is black.  */
 480                   q->red = 0;
 481                   p->red = 1;
 482                   /* Left rotate p.  */
 483                   p->right = q->left;
 484                   q->left = p;
 485                   *pp = q;
 486                   /* Make sure pp is right if the case below tries to use
 487                      it.  */
 488                   nodestack[sp++] = pp = &q->left;
 489                   q = p->right;
 490                 }
 491               /* We know that Q can't be NULL here.  We also know that Q is
 492                  black.  */
 493               if ((q->left == NULL || !q->left->red)
 494                   && (q->right == NULL || !q->right->red))
 495                 {
 496                   /* Q has two black successors.  We can simply color Q red.
 497                      The whole subtree with root P is now missing one black
 498                      edge.  Note that this action can temporarily make the
 499                      tree invalid (if P is red).  But we will exit the loop
 500                      in that case and set P black, which both makes the tree
 501                      valid and also makes the black edge count come out
 502                      right.  If P is black, we are at least one step closer
 503                      to the root and we'll try again the next iteration.  */
 504                   q->red = 1;
 505                   r = p;
 506                 }
 507               else
 508                 {
 509                   /* Q is black, one of Q's successors is red.  We can
 510                      repair the tree with one operation and will exit the
 511                      loop afterwards.  */
 512                   if (q->right == NULL || !q->right->red)
 513                     {
 514                       /* The left one is red.  We perform the same action as
 515                          in maybe_split_for_insert where two red edges are
 516                          adjacent but point in different directions:
 517                          Q's left successor (let's call it Q2) becomes the
 518                          top of the subtree we are looking at, its parent (Q)
 519                          and grandparent (P) become its successors. The former
 520                          successors of Q2 are placed below P and Q.
 521                          P becomes black, and Q2 gets the color that P had.
 522                          This changes the black edge count only for node R and
 523                          its successors.  */
 524                       node q2 = q->left;
 525                       q2->red = p->red;
 526                       p->right = q2->left;
 527                       q->left = q2->right;
 528                       q2->right = q;
 529                       q2->left = p;
 530                       *pp = q2;
 531                       p->red = 0;
 532                     }
 533                   else
 534                     {
 535                       /* It's the right one.  Rotate P left. P becomes black,
 536                          and Q gets the color that P had.  Q's right successor
 537                          also becomes black.  This changes the black edge
 538                          count only for node R and its successors.  */
 539                       q->red = p->red;
 540                       p->red = 0;
 541
 542                       q->right->red = 0;
 543
 544                       /* left rotate p */
 545                       p->right = q->left;
 546                       q->left = p;
 547                       *pp = q;
 548                     }
 549
 550                   /* We're done.  */
 551                   sp = 1;
 552                   r = NULL;
 553                 }
 554             }
 555           else
 556             {
 557               /* Comments: see above.  */
 558               q = p->left;
 559               if (q->red)
 560                 {
 561                   q->red = 0;
 562                   p->red = 1;
 563                   p->left = q->right;
 564                   q->right = p;
 565                   *pp = q;
 566                   nodestack[sp++] = pp = &q->right;
 567                   q = p->left;
 568                 }
 569               if ((q->right == NULL || !q->right->red)
 570                        && (q->left == NULL || !q->left->red))
 571                 {
 572                   q->red = 1;
 573                   r = p;
 574                 }
 575               else
 576                 {
 577                   if (q->left == NULL || !q->left->red)
 578                     {
 579                       node q2 = q->right;
 580                       q2->red = p->red;
 581                       p->left = q2->right;
 582                       q->right = q2->left;
 583                       q2->left = q;
 584                       q2->right = p;
 585                       *pp = q2;
 586                       p->red = 0;
 587                     }
 588                   else
 589                     {
 590                       q->red = p->red;
 591                       p->red = 0;
 592                       q->left->red = 0;
 593                       p->left = q->right;
 594                       q->right = p;
 595                       *pp = q;
 596                     }
 597                   sp = 1;
 598                   r = NULL;
 599                 }
 600             }
 601           --sp;
 602         }
 603       if (r != NULL)
 604         r->red = 0;
 605     }
 606
 607   free (unchained);
 608   return retval;
 609 }
 610 #ifdef weak_alias
 611 weak_alias (__tdelete, tdelete)
 612 #endif
 613
 614 #endif /* GNULIB_defined_tsearch */
 615
 616
 617 #if GNULIB_defined_twalk
 618
 619 /* Walk the nodes of a tree.
 620    ROOT is the root of the tree to be walked, ACTION the function to be
 621    called at each node.  LEVEL is the level of ROOT in the whole tree.  */
 622 static void
 623 internal_function
 624 trecurse (const void *vroot, __action_fn_t action, int level)
 625 {
 626   const_node root = (const_node) vroot;
 627
 628   if (root->left == NULL && root->right == NULL)
 629     (*action) (root, leaf, level);
 630   else
 631     {
 632       (*action) (root, preorder, level);
 633       if (root->left != NULL)
 634         trecurse (root->left, action, level + 1);
 635       (*action) (root, postorder, level);
 636       if (root->right != NULL)
 637         trecurse (root->right, action, level + 1);
 638       (*action) (root, endorder, level);
 639     }
 640 }
 641
 642
 643 /* Walk the nodes of a tree.
 644    ROOT is the root of the tree to be walked, ACTION the function to be
 645    called at each node.  */
 646 void
 647 __twalk (const void *vroot, __action_fn_t action)
 648 {
 649   const_node root = (const_node) vroot;
 650
 651   CHECK_TREE (root);
 652
 653   if (root != NULL && action != NULL)
 654     trecurse (root, action, 0);
 655 }
 656 #ifdef weak_alias
 657 weak_alias (__twalk, twalk)
 658 #endif
 659
 660 #endif /* GNULIB_defined_twalk */
 661
 662
 663 #ifdef _LIBC
 664
 665 /* The standardized functions miss an important functionality: the
 666    tree cannot be removed easily.  We provide a function to do this.  */
 667 static void
 668 internal_function
 669 tdestroy_recurse (node root, __free_fn_t freefct)
 670 {
 671   if (root->left != NULL)
 672     tdestroy_recurse (root->left, freefct);
 673   if (root->right != NULL)
 674     tdestroy_recurse (root->right, freefct);
 675   (*freefct) ((void *) root->key);
 676   /* Free the node itself.  */
 677   free (root);
 678 }
 679
 680 void
 681 __tdestroy (void *vroot, __free_fn_t freefct)
 682 {
 683   node root = (node) vroot;
 684
 685   CHECK_TREE (root);
 686
 687   if (root != NULL)
 688     tdestroy_recurse (root, freefct);
 689 }
 690 weak_alias (__tdestroy, tdestroy)
 691
 692 #endif /* _LIBC */