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