changeset 7585:0cac6db530a1

New module 'tsearch'.
author Bruno Haible <bruno@clisp.org>
date Tue, 31 Oct 2006 19:16:02 +0000
parents a88f85e4728f
children 4a8b5467d8b2
files ChangeLog MODULES.html.sh lib/tsearch.c lib/tsearch.h m4/tsearch.m4 modules/tsearch
diffstat 6 files changed, 812 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2006-10-22  Bruno Haible  <bruno@clisp.org>
+
+	* modules/tsearch: New file.
+	* lib/tsearch.h: New file.
+	* lib/tsearch.c: New file, from glibc-2.5 with small modifications.
+	* m4/tsearch.m4: New file.
+	* MODULES.html.sh (Support for systems lacking POSIX:2001): Add tsearch.
+
 2006-10-29  Eric Blake  <ebb9@byu.net>
 
 	* lib/arcfour.c: Assume config.h.
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1864,6 +1864,7 @@
   func_module ssize_t
   func_module strtok_r
   func_module sys_stat
+  func_module tsearch
   func_module unistd
   func_module utime
   func_module wcwidth
new file mode 100644
--- /dev/null
+++ b/lib/tsearch.c
@@ -0,0 +1,679 @@
+/* Copyright (C) 1995, 1996, 1997, 2000, 2006 Free Software Foundation, Inc.
+   Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
+
+   NOTE: The canonical source of this file is maintained with the GNU C
+   Library.  Bugs can be reported to bug-glibc@gnu.org.
+
+   This program is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by the
+   Free Software Foundation; either version 2, or (at your option) any
+   later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; 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>
+
+/* Specification.  */
+#include "tsearch.h"
+
+#include <stdlib.h>
+
+typedef int (*__compar_fn_t) (const void *, const void *);
+typedef void (*__action_fn_t) (const void *, VISIT, int);
+
+#ifndef weak_alias
+# define __tsearch tsearch
+# define __tfind tfind
+# define __tdelete tdelete
+# define __twalk twalk
+#endif
+
+#ifndef internal_function
+/* Inside GNU libc we mark some function in a special way.  In other
+   environments simply ignore the marking.  */
+# 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 = 100;
+  int sp = 0;
+  node *nodestack[100];
+
+  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)
+	abort ();
+
+      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)
+	    abort ();
+	  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->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->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
+
+
+#ifdef _LIBC
+
+/* 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, __free_fn_t freefct)
+{
+  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, __free_fn_t freefct)
+{
+  node root = (node) vroot;
+
+  CHECK_TREE (root);
+
+  if (root != NULL)
+    tdestroy_recurse (root, freefct);
+}
+weak_alias (__tdestroy, tdestroy)
+
+#endif /* _LIBC */
new file mode 100644
--- /dev/null
+++ b/lib/tsearch.h
@@ -0,0 +1,82 @@
+/* Binary tree data structure.
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+#ifndef _TSEARCH_H
+#define _TSEARCH_H
+
+#if HAVE_TSEARCH
+
+/* Get tseach(), tfind(), tdelete(), twalk() declarations.  */
+#include <search.h>
+
+#else
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* See <http://www.opengroup.org/susv3xbd/search.h.html>,
+       <http://www.opengroup.org/susv3xsh/tsearch.html>
+   for details.  */
+
+typedef enum
+{ 
+  preorder,
+  postorder, 
+  endorder,
+  leaf
+}
+VISIT;
+
+/* Searches an element in the tree *VROOTP that compares equal to KEY.
+   If one is found, it is returned.  Otherwise, a new element equal to KEY
+   is inserted in the tree and is returned.  */
+extern void * tsearch (const void *key, void **vrootp,
+		       int (*compar) (const void *, const void *));
+
+/* Searches an element in the tree *VROOTP that compares equal to KEY.
+   If one is found, it is returned.  Otherwise, NULL is returned.  */
+extern void * tfind (const void *key, void *const *vrootp,
+		     int (*compar) (const void *, const void *));
+
+/* Searches an element in the tree *VROOTP that compares equal to KEY.
+   If one is found, it is removed from the tree, and its parent node is
+   returned.  Otherwise, NULL is returned.  */
+extern void * tdelete (const void *key, void **vrootp,
+		       int (*compar) (const void *, const void *));
+
+/* Perform a depth-first, left-to-right traversal of the tree VROOT.
+   The ACTION function is called:
+     - for non-leaf nodes: 3 times, before the left subtree traversal,
+       after the left subtree traversal but before the right subtree traversal,
+       and after the right subtree traversal,
+     - for leaf nodes: once.
+   The arguments passed to ACTION are:
+     1. the node; it can be casted to a 'const void * const *', i.e. into a
+        pointer to the key,
+     2. an indicator which visit of the node this is,
+     3. the level of the node in the tree (0 for the root).  */
+extern void twalk (const void *vroot,
+		   void (*action) (const void *, VISIT, int));
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
+#endif /* _TSEARCH_H */
new file mode 100644
--- /dev/null
+++ b/m4/tsearch.m4
@@ -0,0 +1,18 @@
+# tsearch.m4 serial 1
+dnl Copyright (C) 2006 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_FUNC_TSEARCH],
+[
+  AC_REPLACE_FUNCS(tsearch)
+  if test $ac_cv_func_tsearch = no; then
+    gl_PREREQ_TSEARCH
+  fi
+])
+
+# Prerequisites of lib/tsearch.c.
+AC_DEFUN([gl_PREREQ_TSEARCH], [
+  :
+])
new file mode 100644
--- /dev/null
+++ b/modules/tsearch
@@ -0,0 +1,24 @@
+Description:
+Binary tree data structure.
+
+Files:
+lib/tsearch.h
+lib/tsearch.c
+m4/tsearch.m4
+
+Depends-on:
+
+configure.ac:
+gl_FUNC_TSEARCH
+
+Makefile.am:
+
+Include:
+"tsearch.h"
+
+License:
+LGPL
+
+Maintainer:
+all, glibc
+