* tsearch.c: Remove unused file.

2 files changed, 4 insertions, 698 deletions

diff --git a/lib/ChangeLog b/lib/ChangeLog
index 2f833f71a..5e6418687 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,7 @@
+2007-02-28  Jim Meyering  <jim@meyering.net>
+
+	* tsearch.c: Remove unused file.
+
 2007-02-23  Jim Meyering  <jim@meyering.net>
 
 	* randperm.c (randperm_new): Comment: say that this function
diff --git a/lib/tsearch.c b/lib/tsearch.c
deleted file mode 100644
index 379f0db96..000000000
--- a/lib/tsearch.c
+++ /dev/null
@@ -1,698 +0,0 @@
-/* Copyright (C) 1995, 1996, 1997, 2000, 2005, 2006 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 Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2.1 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
-   Lesser General Public License for more details.
-
-   You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; if not, write to the Free
-   Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-   02110-1301 USA.  */
-
-/* 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.  */
-
-/* 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 <config.h>
-
-#if __GNUC__
-# define alloca __builtin_alloca
-#else
-# if HAVE_ALLOCA_H
-#  include <alloca.h>
-# else
-#  ifdef _AIX
- #  pragma alloca
-#  else
-char *alloca ();
-#  endif
-# endif
-#endif
-
-#include <stdlib.h>
-#include <string.h>
-#include <search.h>
-
-#ifndef weak_alias
-# define __tsearch tsearch
-# define __tfind tfind
-# define __tdelete tdelete
-# define __twalk twalk
-# define __tdestroy tdestroy
-#endif
-
-#ifndef _LIBC
-# define weak_alias(f,g)
-# define internal_function
-#endif
-
-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;
-typedef const struct node_t *const_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);
-}
-
-
-#else
-
-# 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 (const void *key, void **vrootp, __compar_fn_t compar)
-{
-  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;
-
-  /* This saves some additional tests below.  */
-  if (*rootp != NULL)
-    (*rootp)->red = 0;
-
-  CHECK_TREE (*rootp);
-
-  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 = (struct node_t *) malloc (sizeof (struct node_t));
-  if (q != NULL)
-    {
-      *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;
-}
-#ifdef weak_alias
-weak_alias (__tsearch, tsearch)
-#endif
-
-
-/* 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;
-     void *const *vrootp;
-     __compar_fn_t compar;
-{
-  node *rootp = (node *) vrootp;
-
-  if (rootp == NULL)
-    return NULL;
-
-  CHECK_TREE (*rootp);
-
-  while (*rootp != NULL)
-    {
-      node root = *rootp;
-      int r;
-
-      r = (*compar) (key, root->key);
-      if (r == 0)
-	return root;
-
-      rootp = r < 0 ? &root->left : &root->right;
-    }
-  return NULL;
-}
-#ifdef weak_alias
-weak_alias (__tfind, tfind)
-#endif
-
-
-/* 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 (const void *key, void **vrootp, __compar_fn_t compar)
-{
-  node p, q, r, retval;
-  int cmp;
-  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 = (node **) alloca (sizeof (node *) * stacksize);
-
-  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 = (node **) alloca (sizeof (node *) * stacksize);
-	  nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
-	}
-
-      nodestack[sp++] = rootp;
-      p = *rootp;
-      rootp = ((cmp < 0)
-	       ? &(*rootp)->left
-	       : &(*rootp)->right);
-      if (*rootp == NULL)
-	return 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
-    {
-      node *parent = rootp, *up = &root->right;
-      for (;;)
-	{
-	  if (sp == stacksize)
-	    {
-	      node **newstack;
-	      stacksize += 20;
-	      newstack = (node **) alloca (sizeof (node *) * stacksize);
-	      nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
-	    }
-	  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
-	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 (unchained);
-  return retval;
-}
-#ifdef weak_alias
-weak_alias (__tdelete, tdelete)
-#endif
-
-
-/* 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
-internal_function
-trecurse (const void *vroot, __action_fn_t action, int level)
-{
-  const_node root = (const_node) vroot;
-
-  if (root->left == NULL && root->right == NULL)
-    (*action) (root, leaf, level);
-  else
-    {
-      (*action) (root, preorder, level);
-      if (root->left != NULL)
-	trecurse (root->left, action, level + 1);
-      (*action) (root, postorder, level);
-      if (root->right != NULL)
-	trecurse (root->right, action, level + 1);
-      (*action) (root, endorder, 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.  */
-void
-__twalk (const void *vroot, __action_fn_t action)
-{
-  const_node root = (const_node) vroot;
-
-  CHECK_TREE (root);
-
-  if (root != NULL && action != NULL)
-    trecurse (root, action, 0);
-}
-#ifdef weak_alias
-weak_alias (__twalk, twalk)
-#endif
-
-
-
-/* The standardized functions miss an important functionality: the
-   tree cannot be removed easily.  We provide a function to do this.  */
-static void
-internal_function
-tdestroy_recurse (node root, void (*freefct)(void *))
-{
-  if (root->left != NULL)
-    tdestroy_recurse (root->left, freefct);
-  if (root->right != NULL)
-    tdestroy_recurse (root->right, freefct);
-  (*freefct) ((void *) root->key);
-  /* Free the node itself.  */
-  free (root);
-}
-
-void
-__tdestroy (void *vroot, void (*freefct)(void *))
-{
-  node root = (node) vroot;
-
-  CHECK_TREE (root);
-
-  if (root != NULL)
-    tdestroy_recurse (root, freefct);
-}
-#ifdef weak_alias
-weak_alias (__tdestroy, tdestroy)
-#endif