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