Update.

1997-03-29 17:39  Ulrich Drepper  <drepper@cygnus.com>

	* math/Makefile (routines): Add carg, s_ccosh and s_csinh.

	* math/complex.h: Add C++ protection.

	* math/libm-test.c (cexp_test): Correct a few bugs.
	(csinh_test): New function.
	(ccosh_test): New function.
	(cacos_test): New function.
	(cacosh_test): New function.
	(casinh_test): New function.
	(catanh_test): New function.
	(main): Add calls to csinh_test and ccosh_test.

	* misc/Makefile (tests): Add tst-tsearch.
	Add rule to link tst-tsearch against libm.
	* misc/tsearch.c: Rewritten to use Red-Black-Tree algorithm by
	Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>.
	* misc/tst-tsearch.c: New file.

	* stdio-common/bug5.c: Clear LD_LIBRARY_PATH environment variable
	before using system.
	* stdio-common/test-popen.c: Clear LD_LIBRARY_PATH environment variable
	before using popen.

	* sysdeps/libm-ieee754/s_cexp.c: Correct handling of special cases.
	* sysdeps/libm-ieee754/s_cexpf.c: Likewise.
	* sysdeps/libm-ieee754/s_cexpl.c: Likewise.

	* sysdeps/libm-i387/s_cexp.S: New file.  ix87 specific implementation
	of complex exponential function.
	* sysdeps/libm-i387/s_cexpf.S: New file.
	* sysdeps/libm-i387/s_cexpl.S: New file.

	* sysdeps/libm-ieee754/s_ccosh.c: New file.  Implementation of
	complex cosh function.
	* sysdeps/libm-ieee754/s_ccoshf.c: New file.
	* sysdeps/libm-ieee754/s_ccoshl.c: New file.
	* sysdeps/libm-ieee754/s_csinh.c: New file.  Implementation of
	complex sinh function.
	* sysdeps/libm-ieee754/s_csinhf.c: New file.
	* sysdeps/libm-ieee754/s_csinhl.c: New file.

	* math/carg.c: New file.  Generic implementatio of carg function.
	* math/cargf.c: New file.
	* math/cargl.c: New file.

1997-03-29 16:07  Ulrich Drepper  <drepper@cygnus.com>

	* sysdeps/posix/system.c: Update copyright.

1997-03-29 04:18  Ulrich Drepper  <drepper@cygnus.com>

	* elf/dl-error.c (_dl_catch_error): Add another argument which is
	passed to OPERATE.
	(_dl_receive_error): Likewise.
	* elf/link.h: Change prototypes for _dl_catch_error and
	_dl_receive_error to reflect above change.
	* elf/dl-deps.c: Don't use nested function.  Call _dl_catch_error
	with additional argument with pointer to data.
	* elf/dlclose.c: Likewise.
	* elf/dlerror.c: Likewise.
	* elf/dlopen.c: Likewise.
	* elf/dlsym.c: Likewise.
	* elf/dlvsym.c: Likewise.
	* elf/rtld.c: Likewise.
	* nss/nsswitch.c: Likewise.
	Patch by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>.

1997-03-28 21:14  Miguel de Icaza  <miguel@nuclecu.unam.mx>

	* elf/dl-error.c: Manually set up the values of "c", this avoids a
	call to memcpy and a zero 152 bytes structure.

	* sysdeps/sparc/dl-machine.h (elf_machine_rela): Test
	RTLD_BOOTSTRAP to avoid performing relative relocs on a second
	pass.

	* sysdeps/sparc/udiv_qrnnd.S: Make the code PIC aware.

	* sysdeps/unix/sysv/linux/sparc/Dist: Add kernel_stat.h and
	kernel_sigaction.h

	Add Linux/SPARC specific definitions.
	* sysdeps/unix/sysv/linux/sparc/fcntlbits.h: New file.
	* sysdeps/unix/sysv/linux/sparc/ioctls.h: New file.
	* sysdeps/unix/sysv/linux/sparc/kernel_sigaction.h: New file.
	* sysdeps/unix/sysv/linux/sparc/kernel_stat.h: New file.
	* sysdeps/unix/sysv/linux/sparc/sigaction.h: New file.
	* sysdeps/unix/sysv/linux/sparc/signum.h: New file.
	* sysdeps/unix/sysv/linux/sparc/termbits.h: New file.

1997-03-28 13:06  Philip Blundell  <pjb27@cam.ac.uk>

	* sysdeps/posix/getaddrinfo.c (gaih_inet_serv): Use
	__getservbyname_r() not getservbyname().
	(BROKEN_LIKE_POSIX): Define to 1 so we get strict POSIX behaviour.

3 files changed, 846 insertions, 103 deletions

diff --git a/misc/Makefile b/misc/Makefile
index b789659eaa..e2db14daa0 100644
--- a/misc/Makefile
+++ b/misc/Makefile
@@ -64,7 +64,7 @@ install-lib := libbsd-compat.a libg.a
 non-lib.a := libbsd-compat.a
 gpl2lgpl := error.c error.h
 
-tests := tst-dirname
+tests := tst-dirname tst-tsearch
 
 include ../Rules
 
@@ -77,3 +77,9 @@ $(objpfx)libg.a: $(dep-dummy-lib); $(make-dummy-lib)
 
 
 CFLAGS-init-misc.c = -fkeep-inline-functions
+
+ifeq ($(build-shared),yes)
+$(objpfx)tst-tsearch: $(common-objpfx)math/libm.so$(libm.so-version)
+else
+$(objpfx)tst-tsearch: $(common-objpfx)math/libm.a
+endif
diff --git a/misc/tsearch.c b/misc/tsearch.c
index 6af6536a72..466536bf34 100644
--- a/misc/tsearch.c
+++ b/misc/tsearch.c
@@ -1,5 +1,6 @@
-/* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
+/* Copyright (C) 1995, 1996, 1997 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
+   Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public License as
@@ -16,175 +17,584 @@
    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.  */
 
-/* Tree search generalized from Knuth (6.2.2) Algorithm T just like
-   the AT&T man page says.
-
-   The node_t structure is for internal use only, lint doesn't grok it.
-
-   Written by reading the System V Interface Definition, not the code.
+/* Tree search for red/black trees.
+   The algorithm for adding nodes is taken from one of the many "Algorithms"
+   books by Robert Sedgewick, although the implementation differs.
+   The algorithm for deleting nodes can probably be found in a book named
+   "Introduction to Algorithms" by Cormen/Leiserson/Rivest.  At least that's
+   the book that my professor took most algorithms from during the "Data
+   Structures" course...
 
    Totally public domain.  */
-/*LINTLIBRARY*/
+
+/* Red/black trees are binary trees in which the edges are colored either red
+   or black.  They have the following properties:
+   1. The number of black edges on every path from the root to a leaf is
+      constant.
+   2. No two red edges are adjacent.
+   Therefore there is an upper bound on the length of every path, it's
+   O(log n) where n is the number of nodes in the tree.  No path can be longer
+   than 1+2*P where P is the length of the shortest path in the tree.
+   Useful for the implementation:
+   3. If one of the children of a node is NULL, then the other one is red
+      (if it exists).
+
+   In the implementation, not the edges are colored, but the nodes.  The color
+   interpreted as the color of the edge leading to this node.  The color is
+   meaningless for the root node, but we color the root node black for
+   convenience.  All added nodes are red initially.
+
+   Adding to a red/black tree is rather easy.  The right place is searched
+   with a usual binary tree search.  Additionally, whenever a node N is
+   reached that has two red successors, the successors are colored black and
+   the node itself colored red.  This moves red edges up the tree where they
+   pose less of a problem once we get to really insert the new node.  Changing
+   N's color to red may violate rule 2, however, so rotations may become
+   necessary to restore the invariants.  Adding a new red leaf may violate
+   the same rule, so afterwards an additional check is run and the tree
+   possibly rotated.
+
+   Deleting is hairy.  There are mainly two nodes involved: the node to be
+   deleted (n1), and another node that is to be unchained from the tree (n2).
+   If n1 has a successor (the node with a smallest key that is larger than
+   n1), then the successor becomes n2 and its contents are copied into n1,
+   otherwise n1 becomes n2.
+   Unchaining a node may violate rule 1: if n2 is black, one subtree is
+   missing one black edge afterwards.  The algorithm must try to move this
+   error upwards towards the root, so that the subtree that does not have
+   enough black edges becomes the whole tree.  Once that happens, the error
+   has disappeared.  It may not be necessary to go all the way up, since it
+   is possible that rotations and recoloring can fix the error before that.
+
+   Although the deletion algorithm must walk upwards through the tree, we
+   do not store parent pointers in the nodes.  Instead, delete allocates a
+   small array of parent pointers and fills it while descending the tree.
+   Since we know that the length of a path is O(log n), where n is the number
+   of nodes, this is likely to use less memory.  */
+
+/* Tree rotations look like this:
+      A                C
+     / \              / \
+    B   C            A   G
+   / \ / \  -->     / \
+   D E F G         B   F
+                  / \
+                 D   E
+
+   In this case, A has been rotated left.  This preserves the ordering of the
+   binary tree.  */
 
 #include <stdlib.h>
 #include <search.h>
 
-/* This routine is not very bad.  It makes many assumptions about
-   the compiler. It assumes that the first field in the node must be
-   the "key" field, which points to the datum. It is very tricky
-   stuff. H.J.  */
-
 typedef struct node_t
 {
+  /* Callers expect this to be the first element in the structure - do not
+     move!  */
   const void *key;
   struct node_t *left;
   struct node_t *right;
+  unsigned int red:1;
+} *node;
+
+#undef DEBUGGING
+
+#ifdef DEBUGGING
+
+/* Routines to check tree invariants.  */
+
+#include <assert.h>
+
+#define CHECK_TREE(a) check_tree(a)
+
+static void
+check_tree_recurse (node p, int d_sofar, int d_total)
+{
+  if (p == NULL)
+    {
+      assert (d_sofar == d_total);
+      return;
+    }
+
+  check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total);
+  check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total);
+  if (p->left)
+    assert (!(p->left->red && p->red));
+  if (p->right)
+    assert (!(p->right->red && p->red));
+}
+
+static void
+check_tree (node root)
+{
+  int cnt = 0;
+  node p;
+  if (root == NULL)
+    return;
+  root->red = 0;
+  for(p = root->left; p; p = p->left)
+    cnt += !p->red;
+  check_tree_recurse (root, 0, cnt);
 }
-node;
 
-/* Prototype fpr local function.  */
-static void trecurse __P ((const void *vroot, __action_fn_t action, int level));
 
+#else
 
-/* find or insert datum into search tree.
-char 	*key;		 key to be located
-node	**rootp;	 address of tree root
-int	(*compar)();	 ordering function
-*/
+#define CHECK_TREE(a)
+
+#endif
+
+/* Possibly "split" a node with two red successors, and/or fix up two red
+   edges in a row.  ROOTP is a pointer to the lowest node we visited, PARENTP
+   and GPARENTP pointers to its parent/grandparent.  P_R and GP_R contain the
+   comparison values that determined which way was taken in the tree to reach
+   ROOTP.  MODE is 1 if we need not do the split, but must check for two red
+   edges between GPARENTP and ROOTP.  */
+static void
+maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
+			int p_r, int gp_r, int mode)
+{
+  node root = *rootp;
+  node *rp, *lp;
+  rp = &(*rootp)->right;
+  lp = &(*rootp)->left;
+
+  /* See if we have to split this node (both successors red).  */
+  if (mode == 1
+      || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
+    {
+      /* This node becomes red, its successors black.  */
+      root->red = 1;
+      if (*rp)
+	(*rp)->red = 0;
+      if (*lp)
+	(*lp)->red = 0;
+
+      /* If the parent of this node is also red, we have to do
+	 rotations.  */
+      if (parentp != NULL && (*parentp)->red)
+	{
+	  node gp = *gparentp;
+	  node p = *parentp;
+	  /* There are two main cases:
+	     1. The edge types (left or right) of the two red edges differ.
+	     2. Both red edges are of the same type.
+	     There exist two symmetries of each case, so there is a total of
+	     4 cases.  */
+	  if ((p_r > 0) != (gp_r > 0))
+	    {
+	      /* Put the child at the top of the tree, with its parent
+		 and grandparent as successors.  */
+	      p->red = 1;
+	      gp->red = 1;
+	      root->red = 0;
+	      if (p_r < 0)
+		{
+		  /* Child is left of parent.  */
+		  p->left = *rp;
+		  *rp = p;
+		  gp->right = *lp;
+		  *lp = gp;
+		}
+	      else
+		{
+		  /* Child is right of parent.  */
+		  p->right = *lp;
+		  *lp = p;
+		  gp->left = *rp;
+		  *rp = gp;
+		}
+	      *gparentp = root;
+	    }
+	  else
+	    {
+	      *gparentp = *parentp;
+	      /* Parent becomes the top of the tree, grandparent and
+		 child are its successors.  */
+	      p->red = 0;
+	      gp->red = 1;
+	      if (p_r < 0)
+		{
+		  /* Left edges.  */
+		  gp->left = p->right;
+		  p->right = gp;
+		}
+	      else
+		{
+		  /* Right edges.  */
+		  gp->right = p->left;
+		  p->left = gp;
+		}
+	    }
+	}
+    }
+}
+
+/* Find or insert datum into search tree.
+   KEY is the key to be located, ROOTP is the address of tree root,
+   COMPAR the ordering function.  */
 void *
-__tsearch (key, vrootp, compar)
-     const void *key;
-     void **vrootp;
-     __compar_fn_t compar;
+__tsearch (const void *key, void **vrootp, __compar_fn_t compar)
 {
-  node *q;
-  node **rootp = (node **) vrootp;
+  node q;
+  node *parentp = NULL, *gparentp = NULL;
+  node *rootp = (node *) vrootp;
+  node *nextp;
+  int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler.  */
 
   if (rootp == NULL)
     return NULL;
 
-  while (*rootp != NULL)		/* Knuth's T1: */
-    {
-      int r;
+  /* This saves some additional tests below.  */
+  if (*rootp != NULL)
+    (*rootp)->red = 0;
+
+  CHECK_TREE (*rootp);
 
-      r = (*compar) (key, (*rootp)->key);
-      if (r == 0)			/* T2: */
-	return *rootp;			/* we found it! */
-      rootp = (r < 0)
-	      ? &(*rootp)->left		/* T3: follow left branch */
-	      : &(*rootp)->right;	/* T4: follow right branch */
+  nextp = rootp;
+  while (*nextp != NULL)
+    {
+      node root = *rootp;
+      r = (*compar) (key, root->key);
+      if (r == 0)
+	return root;
+
+      maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
+      /* If that did any rotations, parentp and gparentp are now garbage.
+	 That doesn't matter, because the values they contain are never
+	 used again in that case.  */
+
+      nextp = r < 0 ? &root->left : &root->right;
+      if (*nextp == NULL)
+	break;
+
+      gparentp = parentp;
+      parentp = rootp;
+      rootp = nextp;
+
+      gp_r = p_r;
+      p_r = r;
     }
 
-  q = (node *) malloc (sizeof (node));	/* T5: key not found */
-  if (q != NULL)			/* make new node */
+  q = (struct node_t *) malloc (sizeof (struct node_t));
+  if (q != NULL)
     {
-      *rootp = q;			/* link new node to old */
+      *nextp = q;			/* link new node to old */
       q->key = key;			/* initialize new node */
+      q->red = 1;
       q->left = q->right = NULL;
     }
+  if (nextp != rootp)
+    /* There may be two red edges in a row now, which we must avoid by
+       rotating the tree.  */
+    maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
 
   return q;
 }
 weak_alias (__tsearch, tsearch)
 
 
+/* Find datum in search tree.
+   KEY is the key to be located, ROOTP is the address of tree root,
+   COMPAR the ordering function.  */
 void *
 __tfind (key, vrootp, compar)
      const void *key;
      const void **vrootp;
      __compar_fn_t compar;
 {
-  node **rootp = (node **) vrootp;
+  node *rootp = (node *) vrootp;
 
   if (rootp == NULL)
     return NULL;
 
-  while (*rootp != NULL)		/* Knuth's T1: */
+  CHECK_TREE (*rootp);
+
+  while (*rootp != NULL)
     {
+      node root = *rootp;
       int r;
 
-      r = (*compar)(key, (*rootp)->key);
-      if (r == 0)			/* T2: */
-	return *rootp;			/* we found it! */
+      r = (*compar) (key, root->key);
+      if (r == 0)
+	return root;
 
-      rootp = (r < 0)
-	      ? &(*rootp)->left		/* T3: follow left branch */
-	      : &(*rootp)->right;	/* T4: follow right branch */
+      rootp = r < 0 ? &root->left : &root->right;
     }
-    return NULL;
+  return NULL;
 }
 weak_alias (__tfind, tfind)
 
 
-/* delete node with given key
-char	*key;		key to be deleted
-node	**rootp;	address of the root of tree
-int	(*compar)();	comparison function
-*/
+/* Delete node with given key.
+   KEY is the key to be deleted, ROOTP is the address of the root of tree,
+   COMPAR the comparison function.  */
 void *
-__tdelete (key, vrootp, compar)
-     const void *key;
-     void **vrootp;
-     __compar_fn_t compar;
+__tdelete (const void *key, void **vrootp, __compar_fn_t compar)
 {
-  node *p;
-  node *q;
-  node *r;
+  node p, q, r, retval;
   int cmp;
-  node **rootp = (node **) vrootp;
+  node *rootp = (node *) vrootp;
+  node root, unchained;
+  /* Stack of nodes so we remember the parents without recursion.  It's
+     _very_ unlikely that there are paths longer than 40 nodes.  The tree
+     would need to have around 250.000 nodes.  */
+  int stacksize = 40;
+  int sp = 0;
+  node **nodestack = alloca (sizeof (node *) * stacksize);
 
-  if (rootp == NULL || (p = *rootp) == NULL)
+  if (rootp == NULL)
     return NULL;
+  p = *rootp;
+  if (p == NULL)
+    return NULL;
+
+  CHECK_TREE (p);
 
   while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
     {
+      if (sp == stacksize)
+	{
+	  node **newstack;
+	  stacksize += 20;
+	  newstack = alloca (sizeof (node *) * stacksize);
+	  memcpy (newstack, nodestack, sp * sizeof (node *));
+	  nodestack = newstack;
+	}
+
+      nodestack[sp++] = rootp;
       p = *rootp;
-      rootp = (cmp < 0)
-	      ? &(*rootp)->left		/* follow left branch */
-	      : &(*rootp)->right;	/* follow right branch */
+      rootp = ((cmp < 0)
+	       ? &(*rootp)->left
+	       : &(*rootp)->right);
       if (*rootp == NULL)
-	return NULL;			/* key not found */
+	return NULL;
     }
 
-  r = (*rootp)->right;			/* D1: */
-  q = (*rootp)->left;
-  if (q == NULL)			/* Left NULL? */
-    q = r;
-  else if (r != NULL)			/* Right link is NULL? */
+  /* This is bogus if the node to be deleted is the root... this routine
+     really should return an integer with 0 for success, -1 for failure
+     and errno = ESRCH or something.  */
+  retval = p;
+
+  /* We don't unchain the node we want to delete. Instead, we overwrite
+     it with its successor and unchain the successor.  If there is no
+     successor, we really unchain the node to be deleted.  */
+
+  root = *rootp;
+
+  r = root->right;
+  q = root->left;
+
+  if (q == NULL || r == NULL)
+    unchained = root;
+  else
     {
-      if (r->left == NULL)		/* D2: Find successor */
+      node *parent = rootp, *up = &root->right;
+      for (;;)
 	{
-	  r->left = q;
-	  q = r;
+	  if (sp == stacksize)
+	    {
+	      node **newstack;
+	      stacksize += 20;
+	      newstack = alloca (sizeof (node *) * stacksize);
+	      memcpy (newstack, nodestack, sp * sizeof (node *));
+	      nodestack = newstack;
+	    }
+	  nodestack[sp++] = parent;
+	  parent = up;
+	  if ((*up)->left == NULL)
+	    break;
+	  up = &(*up)->left;
 	}
+      unchained = *up;
+    }
+
+  /* We know that either the left or right successor of UNCHAINED is NULL.
+     R becomes the other one, it is chained into the parent of UNCHAINED.  */
+  r = unchained->left;
+  if (r == NULL)
+    r = unchained->right;
+  if (sp == 0)
+    *rootp = r;
+  else
+    {
+      q = *nodestack[sp-1];
+      if (unchained == q->right)
+	q->right = r;
       else
-	{				/* D3: Find (struct node_t *)0 link */
-	  for (q = r->left; q->left != NULL; q = r->left)
-	    r = q;
-	  r->left = q->right;
-	  q->left = (*rootp)->left;
-	  q->right = (*rootp)->right;
+	q->left = r;
+    }
+
+  if (unchained != root)
+    root->key = unchained->key;
+  if (!unchained->red)
+    {
+      /* Now we lost a black edge, which means that the number of black
+	 edges on every path is no longer constant.  We must balance the
+	 tree.  */
+      /* NODESTACK now contains all parents of R.  R is likely to be NULL
+	 in the first iteration.  */
+      /* NULL nodes are considered black throughout - this is necessary for
+	 correctness.  */
+      while (sp > 0 && (r == NULL || !r->red))
+	{
+	  node *pp = nodestack[sp - 1];
+	  p = *pp;
+	  /* Two symmetric cases.  */
+	  if (r == p->left)
+	    {
+	      /* Q is R's brother, P is R's parent.  The subtree with root
+		 R has one black edge less than the subtree with root Q.  */
+	      q = p->right;
+	      if (q != NULL && q->red)
+		{
+		  /* If Q is red, we know that P is black. We rotate P left
+		     so that Q becomes the top node in the tree, with P below
+		     it.  P is colored red, Q is colored black.
+		     This action does not change the black edge count for any
+		     leaf in the tree, but we will be able to recognize one
+		     of the following situations, which all require that Q
+		     is black.  */
+		  q->red = 0;
+		  p->red = 1;
+		  /* Left rotate p.  */
+		  p->right = q->left;
+		  q->left = p;
+		  *pp = q;
+		  /* Make sure pp is right if the case below tries to use
+		     it.  */
+		  nodestack[sp++] = pp = &q->left;
+		  q = p->right;
+		}
+	      /* We know that Q can't be NULL here.  We also know that Q is
+		 black.  */
+	      if ((q->left == NULL || !q->left->red)
+		  && (q->right == NULL || !q->right->red))
+		{
+		  /* Q has two black successors.  We can simply color Q red.
+		     The whole subtree with root P is now missing one black
+		     edge.  Note that this action can temporarily make the
+		     tree invalid (if P is red).  But we will exit the loop
+		     in that case and set P black, which both makes the tree
+		     valid and also makes the black edge count come out
+		     right.  If P is black, we are at least one step closer
+		     to the root and we'll try again the next iteration.  */
+		  q->red = 1;
+		  r = p;
+		}
+	      else
+		{
+		  /* Q is black, one of Q's successors is red.  We can
+		     repair the tree with one operation and will exit the
+		     loop afterwards.  */
+		  if (q->right == NULL || !q->right->red)
+		    {
+		      /* The left one is red.  We perform the same action as
+			 in maybe_split_for_insert where two red edges are
+			 adjacent but point in different directions:
+			 Q's left successor (let's call it Q2) becomes the
+			 top of the subtree we are looking at, its parent (Q)
+			 and grandparent (P) become its successors. The former
+			 successors of Q2 are placed below P and Q.
+			 P becomes black, and Q2 gets the color that P had.
+			 This changes the black edge count only for node R and
+			 its successors.  */
+		      node q2 = q->left;
+		      q2->red = p->red;
+		      p->right = q2->left;
+		      q->left = q2->right;
+		      q2->right = q;
+		      q2->left = p;
+		      *pp = q2;
+		      p->red = 0;
+		    }
+		  else
+		    {
+		      /* It's the right one.  Rotate P left. P becomes black,
+			 and Q gets the color that P had.  Q's right successor
+			 also becomes black.  This changes the black edge
+			 count only for node R and its successors.  */
+		      q->red = p->red;
+		      p->red = 0;
+
+		      q->right->red = 0;
+
+		      /* left rotate p */
+		      p->right = q->left;
+		      q->left = p;
+		      *pp = q;
+		    }
+
+		  /* We're done.  */
+		  sp = 1;
+		  r = NULL;
+		}
+	    }
+	  else
+	    {
+	      /* Comments: see above.  */
+	      q = p->left;
+	      if (q != NULL && q->red)
+		{
+		  q->red = 0;
+		  p->red = 1;
+		  p->left = q->right;
+		  q->right = p;
+		  *pp = q;
+		  nodestack[sp++] = pp = &q->right;
+		  q = p->left;
+		}
+	      if ((q->right == NULL || !q->right->red)
+		       && (q->left == NULL || !q->left->red))
+		{
+		  q->red = 1;
+		  r = p;
+		}
+	      else
+		{
+		  if (q->left == NULL || !q->left->red)
+		    {
+		      node q2 = q->right;
+		      q2->red = p->red;
+		      p->left = q2->right;
+		      q->right = q2->left;
+		      q2->left = q;
+		      q2->right = p;
+		      *pp = q2;
+		      p->red = 0;
+		    }
+		  else
+		    {
+		      q->red = p->red;
+		      p->red = 0;
+		      q->left->red = 0;
+		      p->left = q->right;
+		      q->right = p;
+		      *pp = q;
+		    }
+		  sp = 1;
+		  r = NULL;
+		}
+	    }
+	  --sp;
 	}
+      if (r != NULL)
+	r->red = 0;
     }
-  free ((struct node_t *) *rootp);	/* D4: Free node */
-  *rootp = q;				/* link parent to new node */
-  return p;
+
+  free (unchained);
+  return retval;
 }
 weak_alias (__tdelete, tdelete)
 
 
-/* Walk the nodes of a tree
-node	*root;		Root of the tree to be walked
-void	(*action)();	Function to be called at each node
-int	level;
-*/
+/* Walk the nodes of a tree.
+   ROOT is the root of the tree to be walked, ACTION the function to be
+   called at each node.  LEVEL is the level of ROOT in the whole tree.  */
 static void
-trecurse (vroot, action, level)
-     const void *vroot;
-     __action_fn_t action;
-     int level;
+trecurse (const void *vroot, __action_fn_t action, int level)
 {
-  node *root = (node *) vroot;
+  node root = (node ) vroot;
 
   if (root->left == NULL && root->right == NULL)
     (*action) (root, leaf, level);
@@ -201,17 +611,15 @@ trecurse (vroot, action, level)
 }
 
 
-/* void twalk(root, action)	Walk the nodes of a tree
-node	*root;			Root of the tree to be walked
-void	(*action)();		Function to be called at each node
-PTR
-*/
+/* Walk the nodes of a tree.
+   ROOT is the root of the tree to be walked, ACTION the function to be
+   called at each node.  */
 void
-__twalk (vroot, action)
-     const void *vroot;
-     __action_fn_t action;
+__twalk (const void *vroot, __action_fn_t action)
 {
-  const node *root = (node *) vroot;
+  const node root = (node) vroot;
+
+  CHECK_TREE (root);
 
   if (root != NULL && action != NULL)
     trecurse (root, action, 0);
diff --git a/misc/tst-tsearch.c b/misc/tst-tsearch.c
new file mode 100644
index 0000000000..eca11cbb95
--- /dev/null
+++ b/misc/tst-tsearch.c
@@ -0,0 +1,329 @@
+/* Test program for tsearch et al.
+   Copyright (C) 1997 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public
+   License along with the GNU C Library; see the file COPYING.LIB.  If not,
+   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+#define _GNU_SOURCE	1
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <search.h>
+
+#define SEED 0
+#define BALANCED 1
+#define PASSES 100
+
+#if BALANCED
+#include <math.h>
+#define SIZE 1000
+#else
+#define SIZE 100
+#endif
+
+enum order
+{
+  ascending,
+  descending,
+  randomorder
+};
+
+enum action
+{
+  build,
+  build_and_del,
+  delete,
+  find
+};
+
+/* Set to 1 if a test is flunked.  */
+static int error = 0;
+
+/* The keys we add to the tree.  */
+static int x[SIZE];
+
+/* Pointers into the key array, possibly permutated, to define an order
+   for insertion/removal.  */
+static int y[SIZE];
+
+/* Flags set for each element visited during a tree walk.  */
+static int z[SIZE];
+
+/* Depths for all the elements, to check that the depth is constant for
+   all three visits.  */
+static int depths[SIZE];
+
+/* Maximum depth during a tree walk.  */
+static int max_depth;
+
+/* Compare two keys.  */
+static int
+cmp_fn (const void *a, const void *b)
+{
+  return *(const int *) a - *(const int *) b;
+}
+
+/* Permute an array of integers.  */
+static void
+memfry (int *string)
+{
+  int i;
+
+  for (i = 0; i < SIZE; ++i)
+    {
+      int32_t j;
+      int c;
+
+      j = random () % SIZE;
+
+      c = string[i];
+      string[i] = string[j];
+      string[j] = c;
+    }
+}
+
+static void
+walk_action (const void *nodep, const VISIT which, const int depth)
+{
+  int key = **(int **) nodep;
+
+  if (depth > max_depth)
+    max_depth = depth;
+  if (which == leaf || which == preorder)
+    {
+      ++z[key];
+      depths[key] = depth;
+    }
+  else
+    {
+      if (depths[key] != depth)
+	{
+	  fputs ("Depth for one element is not constant during tree walk.\n",
+		 stderr);
+	}
+    }
+}
+
+static void
+walk_tree (void *root, int expected_count)
+{
+  int i;
+
+  memset (z, 0, sizeof z);
+  max_depth = 0;
+
+  twalk (root, walk_action);
+  for (i = 0; i < expected_count; ++i)
+    if (z[i] != 1)
+      {
+	fputs ("Node was not visited.\n", stderr);
+	error = 1;
+      }
+
+#if BALANCED
+  if (max_depth > log (expected_count) * 2 + 2)
+#else
+  if (max_depth > expected_count)
+#endif
+    {
+      fputs ("Depth too large during tree walk.\n", stderr);
+      error = 1;
+    }
+}
+
+/* Perform an operation on a tree.  */
+static void
+mangle_tree (enum order how, enum action what, void **root, int lag)
+{
+  int i;
+
+  if (how == randomorder)
+    {
+      for (i = 0; i < SIZE; ++i)
+	y[i] = i;
+      memfry (y);
+    }
+
+  for (i = 0; i < SIZE + lag; ++i)
+    {
+      void *elem;
+      int j, k;
+
+      switch (how)
+	{
+	case randomorder:
+	  if (i >= lag)
+	    k = y[i - lag];
+	  else
+	    k = y[SIZE - i - 1 + lag];
+	  j = y[i];
+	  break;
+
+	case ascending:
+	  k = i - lag;
+	  j = i;
+	  break;
+
+	case descending:
+	  k = SIZE - i - 1 + lag;
+	  j = SIZE - i - 1;
+	  break;
+
+	default:
+	  /* This never should happen, but gcc isn't smart enough to
+	     recognize it.  */
+	  abort ();
+	}
+
+      switch (what)
+	{
+	case build_and_del:
+	case build:
+	  if (i < SIZE)
+	    {
+	      if (tfind (x + j, (const void **) root, cmp_fn) != NULL)
+		{
+		  fputs ("Found element which is not in tree yet.\n", stderr);
+		  error = 1;
+		}
+	      elem = tsearch (x + j, root, cmp_fn);
+	      if (elem == 0
+		  || tfind (x + j, (const void **) root, cmp_fn) == NULL)
+		{
+		  fputs ("Couldn't find element after it was added.\n",
+			 stderr);
+		  error = 1;
+		}
+	    }
+
+	  if (what == build || i < lag)
+	    break;
+
+	  j = k;
+	  /* fall through */
+
+	case delete:
+	  elem = tfind (x + j, (const void **) root, cmp_fn);
+	  if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
+	    {
+	      fputs ("Error deleting element.\n", stderr);
+	      error = 1;
+	    }
+	  break;
+
+	case find:
+	  if (tfind (x + j, (const void **) root, cmp_fn) == NULL)
+	    {
+	      fputs ("Couldn't find element after it was added.\n", stderr);
+	      error = 1;
+	    }
+	  break;
+
+	}
+    }
+}
+
+
+int
+main (int argc, char **argv)
+{
+  int total_error = 0;
+  static int state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+  void *root = NULL;
+  int i, j;
+
+  initstate (SEED, state, 8);
+
+  for (i = 0; i < SIZE; ++i)
+    x[i] = i;
+
+  /* Do this loop several times to get different permutations for the
+     random case.  */
+  fputs ("Series I\n", stderr);
+  for (i = 0; i < PASSES; ++i)
+    {
+      fprintf (stderr, "Pass %d... ", i + 1);
+      fflush (stdout);
+      error = 0;
+
+      mangle_tree (ascending, build, &root, 0);
+      mangle_tree (ascending, find, &root, 0);
+      mangle_tree (descending, find, &root, 0);
+      mangle_tree (randomorder, find, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (ascending, delete, &root, 0);
+
+      mangle_tree (ascending, build, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (descending, delete, &root, 0);
+
+      mangle_tree (ascending, build, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (randomorder, delete, &root, 0);
+
+      mangle_tree (descending, build, &root, 0);
+      mangle_tree (ascending, find, &root, 0);
+      mangle_tree (descending, find, &root, 0);
+      mangle_tree (randomorder, find, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (descending, delete, &root, 0);
+
+      mangle_tree (descending, build, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (descending, delete, &root, 0);
+
+      mangle_tree (descending, build, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (randomorder, delete, &root, 0);
+
+      mangle_tree (randomorder, build, &root, 0);
+      mangle_tree (ascending, find, &root, 0);
+      mangle_tree (descending, find, &root, 0);
+      mangle_tree (randomorder, find, &root, 0);
+      walk_tree (root, SIZE);
+      mangle_tree (randomorder, delete, &root, 0);
+
+      for (j = 1; j < SIZE; j *= 2)
+	{
+	  mangle_tree (randomorder, build_and_del, &root, j);
+	}
+
+      fputs (error ? " failed!\n" : " ok.\n", stderr);
+      total_error |= error;
+    }
+
+  fputs ("Series II\n", stderr);
+  for (i = 1; i < SIZE; i *= 2)
+    {
+      fprintf (stderr, "For size %d... ", i);
+      fflush (stdout);
+      error = 0;
+
+      mangle_tree (ascending, build_and_del, &root, i);
+      mangle_tree (descending, build_and_del, &root, i);
+      mangle_tree (ascending, build_and_del, &root, i);
+      mangle_tree (descending, build_and_del, &root, i);
+      mangle_tree (ascending, build_and_del, &root, i);
+      mangle_tree (descending, build_and_del, &root, i);
+      mangle_tree (ascending, build_and_del, &root, i);
+      mangle_tree (descending, build_and_del, &root, i);
+
+      fputs (error ? " failed!\n" : " ok.\n", stderr);
+      total_error |= error;
+    }
+
+  return total_error;
+}