Update.cvs/libc-ud-970920

1997-09-21 03:19  Ulrich Drepper  <drepper@cygnus.com>

	* libio/libio.h: More libstdc++ cleanups.  Define _IO_USE_DTOA if
	_G_HAVE_PRINTF_FP is not defined.
	* libio/strops.c: Undo patch of 1997-07-08 02:18.  Must find a
	different solution for the problem.

	* misc/search.h [__USE_GNU]: Define comparison_fn_t.
	* stdlib/stdlib.h: Define comparison_fn_t only if __COMPAR_FN_T is
	not defined.
	Fix typo.  Pretty print inline functions.

	* sysdeps/i386/i486/string.h (__stpcpy_small): Increment __cp not cp.
	Patch by HJ Lu <hjl@gnu.ai.mit.edu>.

1997-09-20 16:45  Ulrich Drepper  <drepper@cygnus.com>

	* hesiod/hesiod.c (hesiod_init): Use __secure_getenv to get
	HES_DOMAIN environment variable.
	Suggested by Mark Kettenis <kettenis@phys.uva.nl>.

	* hesiod/README.hesiod: A bit of information about Hesiod and how
	to use it.  Written by Mark Kettenis <kettenis@phys.uva.nl>.

1997-09-20 05:15  Ulrich Drepper  <drepper@cygnus.com>

	* manual/maint.texi: Update requirement list.

	* io/ftw.h: Don't use parameter names from global namespace in
	prototypes.

	* stdlib/strtol.c: If used outside glibc handle broken systems
	which have character classification functions which are not 8-bit
	clean gracefully.  Patch by Bruno Haible <haible@ilog.fr>.

1997-09-19 21:42  David S. Miller  <davem@tanya.rutgers.edu>

	* sysdeps/unix/sysv/linux/sparc/sparc64/bits/types.h: ssize_t is
	a long long int.

1997-09-19 15:12  H.J. Lu  <hjl@gnu.ai.mit.edu>

	* posix/Makefile (test-srcs): New, set to globtest.

1997-09-20 00:24  Ulrich Drepper  <drepper@cygnus.com>

	* manual/filesys.texi: Document ftw, nftw and needed data types.

1997-09-19 12:53  H.J. Lu  <hjl@gnu.ai.mit.edu>

	* sysdeps/i386/i486/bits/string.h: Fix typo.

1997-09-19 14:11  Ulrich Drepper  <drepper@cygnus.com>

	* io/ftwtest.c (cb): Print level.
	* io/ftwtest-sh: Updated for ftwtest.c change.

	* string/argz.h (__argz_next): Cast NULL to char * to satisfy C++
	compilers.
	Reported by Mirko Streckenbach <mirko@ramz.ing.tu-bs.de>.

	* catgets/catgets.c (catopen): Correctly allocate string of nlspath.
	Reported by Charles C. Fu <ccwf@klab.caltech.edu>.

1997-09-18 13:30  Klaus Espenlaub  <kespenla@student.informatik.uni-ulm.de>

	* sysdeps/i386/init-first.c: Call __getopt_clean_environment with
	additional argument.
	* sysdeps/mach/hurd/i386/init-first.c: Likewise.
	* sysdeps/mach/hurd/mips/init-first.c: Likewise.
	* sysdeps/stub/init-first.c: Likewise.

1997-09-18 03:16  Ulrich Drepper  <drepper@cygnus.com>

	* manual/search.texi: Document lsearch, lfind, the hsearch and
	tsearch functions.

1997-09-18 00:04  Ulrich Drepper  <drepper@cygnus.com>

	* misc/hsearch_r.c (hsearch_r): Only return error for ENTER action
	if the table is full and we *really* have to enter a new entry.

1997-09-17 19:44  Ulrich Drepper  <drepper@cygnus.com>

	* sysdeps/sparc/sparc32/dl-machine.h (elf_machine_rela): Get rid
	of hack for handling flush opcode.
	Patch by Richard Henderson <rth@cygnus.com>.

3 files changed, 621 insertions, 11 deletions

diff --git a/manual/filesys.texi b/manual/filesys.texi
index 5ddd8a2..7e8a1a1 100644
--- a/manual/filesys.texi
+++ b/manual/filesys.texi
@@ -17,6 +17,8 @@ access permissions and modification times.
 				 file names.
 * Accessing Directories::       Finding out what files a directory
 				 contains.
+* Working on Directory Trees::  Apply actions to all files or a selectable
+                                 subset of a directory hierachy.
 * Hard Links::                  Adding alternate names to a file.
 * Symbolic Links::              A file that ``points to'' a file name.
 * Deleting Files::              How to delete a file, and what that means.
@@ -500,6 +502,210 @@ Please note the simple selector function for this example.  Since
 we want to see all directory entries we always return @code{1}.
 
 
+@node Working on Directory Trees
+@section Working on Directory Trees
+@cindex directory hierachy
+@cindex hierachy, directory
+@cindex tree, directory
+
+The functions to handle files in directories described so far allowed to
+retrieve all the information in small pieces or process all files in a
+directory (see @code{scandir}).  Sometimes it is useful to process whole
+hierachies of directories and the contained files.  The X/Open
+specification define two functions to do this.  The simpler form is
+derived from an early definition in @w{System V} systems and therefore
+this function is available on SVID derived systems.  The prototypes and
+required definitions can be found in the @file{ftw.h} header.
+
+Both functions of this @code{ftw} family take as one of the arguments a
+reference to a callback function.  The functions must be of these types.
+
+@deftp {Data Type} __ftw_func_t
+
+@smallexample
+int (*) (const char *, const struct stat *, int)
+@end smallexample
+
+Type for callback functions given to the @code{ftw} function.  The first
+parameter will contain a pointer to the filename, the second parameter
+will point to an object of type @code{struct stat} which will be filled
+for the file named by the first parameter.
+
+@noindent
+The last parameter is a flag given more information about the current
+file.  It can have the following values:
+
+@vindex FTW_F
+@vindex FTW_D
+@vindex FTW_NS
+@vindex FTW_DNR
+@vindex FTW_SL
+@table @code
+@item FTW_F
+The current item is a normal file or files which do not fit into one of
+the following categories.  This means especially special files, sockets
+etc.
+@item FTW_D
+The current item is a directory.
+@item FTW_NS
+The @code{stat} call to fill the object pointed to by the second
+parameter failed and so the information is invalid.
+@item FTW_DNR
+The item is a directory which cannot be read.
+@item FTW_SL
+The item is a symbolic link.  Since symbolic links are normally followed
+seeing this value in a @code{ftw} callback function means the referenced
+file does not exist.  The situation for @code{nftw} is different.
+
+This value is only available if the program is compiled with
+@code{_BSD_SOURCE} or @code{_XOPEN_EXTENDED} defined before including
+the first header.  The original SVID systems do not have symbolic links.
+@end table
+@end deftp
+
+@deftp {Data Type} __nftw_func_t
+
+@smallexample
+int (*) (const char *, const struct stat *, int, struct FTW *)
+@end smallexample
+
+@vindex FTW_DP
+@vindex FTW_SLN
+The first three arguments have the same as for the @code{__ftw_func_t}
+type.  A difference is that for the third argument some additional
+values are defined to allow finer differentiation:
+@table @code
+@item FTW_DP
+The current item is a directory and all subdirectories have already been
+visited and reported.  This flag is returned instead of @code{FTW_D} if
+the @code{FTW_DEPTH} flag is given to @code{nftw} (see below).
+@item FTW_SLN
+The current item is a stale symbolic link.  The file it points to does
+not exist.
+@end table
+
+The last parameter of the callback function is a pointer to a structure
+with some extra information as described below.
+@end deftp
+
+@deftp {Data Type} {struct FTW}
+The contained information helps to interpret the name parameter and
+gives some information about current state of the traversal of the
+directory hierachy.
+
+@table @code
+@item int base
+The value specifies which part of the filename argument given in the
+first parameter to the callback function is the name of the file.  The
+rest of the string is the path to locate the file.  This information is
+especially important if the @code{FTW_CHDIR} flag for @code{nftw} was
+set since then the current directory is the one the current item is
+found in.
+@item int level
+While processing the directory the functions tracks how many directories
+have been examine to find the current item.  This nesting level is
+@math{0} for the item given starting item (file or directory) and is
+incremented by one for each entered directory.
+@end table
+@end deftp
+
+
+@comment ftw.h
+@comment SVID
+@deftypefun int ftw (const char *@var{filename}, __ftw_func_t @var{func}, int @var{descriptors})
+The @code{ftw} function calls the callback function given in the
+parameter @var{func} for every item which is found in the directory
+specified by @var{filename} and all directories below.  The function
+follows symbolic links if necessary but does not process an item twice.
+If @var{filename} names no directory this item is the only object
+reported by calling the callback function.
+
+The filename given to the callback function is constructed by taking the
+@var{filename} parameter and appending the names of all passed
+directories and then the local file name.  So the callback function can
+use this parameter to access the file.  Before the callback function is
+called @code{ftw} calls @code{stat} for this file and passes the
+information up to the callback function.  If this @code{stat} call was
+not successful the failure is indicated by setting the falg argument of
+the callback function to @code{FTW_NS}.  Otherwise the flag is set
+according to the description given in the description of
+@code{__ftw_func_t} above.
+
+The callback function is expected to return @math{0} to indicate that no
+error occurred and the processing should be continued.  If an error
+occurred in the callback function or the call to @code{ftw} shall return
+immediately the callback function can return a value other than
+@math{0}.  This is the only correct way to stop the function.  The
+program must not use @code{setjmp} or similar techniques to continue the
+program in another place.  This would leave the resources allocated in
+the @code{ftw} function allocated.
+
+The @var{descriptors} parameter to the @code{ftw} function specifies how
+many file descriptors the @code{ftw} function is allowed to consume.
+The more descriptors can be used the faster the function can run.  For
+each level of directories at most one descriptor is used so that for
+very deep directory hierachies the limit on open file descriptors for
+the process or the system can be exceeded.  Beside this the limit on
+file descriptors is counted together for all threads in a multi-threaded
+program and therefore it is always good too limit the maximal number of
+open descriptors to a reasonable number.
+
+The return value of the @code{ftw} function is @math{0} if all callback
+function calls returned @math{0} and all actions performed by the
+@code{ftw} succeeded.  If some function call failed (other than calling
+@code{stat} on an item) the function return @math{-1}.  If a callback
+function returns a value other than @math{0} this value is returned as
+the return value of @code{ftw}.
+@end deftypefun
+
+@comment ftw.h
+@comment XPG4.2
+@deftypefun int nftw (const char *@var{filename}, __nftw_func_t @var{func}, int @var{descriptors}, int @var{flag})
+The @code{nftw} functions works like the @code{ftw} functions.  It calls
+the callback function @var{func} for all items it finds in the directory
+@var{filename} and below.  At most @var{descriptors} file descriptors
+are consumed during the @code{nftw} call.
+
+The differences are that for one the callback function is of a different
+type.  It is of type @w{@code{struct FTW *}} and provides the callback
+functions the information described above.
+
+The second difference is that @code{nftw} takes an additional fourth
+argument which is @math{0} or a combination of any of the following
+values, combined using bitwise OR.
+
+@table @code
+@item FTW_PHYS
+While traversing the directory symbolic links are not followed.  I.e.,
+if this flag is given symbolic links are reported using the
+@code{FTW_SL} value for the type parameter to the callback function.
+Please note that if this flag is used the appearence of @code{FTW_SL} in
+a callback function does not mean the referenced file does not exist.
+To indicate this the extra value @code{FTW_SLN} exists.
+@item FTW_MOUNT
+The callback function is only called for items which are on the same
+mounted filesystem as the directory given as the @var{filename}
+parameter to @code{nftw}.
+@item FTW_CHDIR
+If this flag is given the current working directory is changed to the
+directory containing the reported object before the callback function is
+called.
+@item FTW_DEPTH
+If this option is given the function visits first all files and
+subdirectories before the callback function is called for the directory
+itself (depth-first processing).  This also means the type flag given to
+the callback function is @code{FTW_DP} and not @code{FTW_D}.
+@end table
+
+The return value is computed in the same way as for @code{ftw}.
+@code{nftw} return @math{0} if no failure occurred in @code{nftw} and
+all callback function call return values are also @math{0}.  For
+internal errors such as memory problems @math{-1} is returned and
+@var{errno} is set accordingly.  If the return value of a callback
+invocation is nonzero this very same value is returned.
+@end deftypefun
+
+
 @node Hard Links
 @section Hard Links
 @cindex hard link
diff --git a/manual/maint.texi b/manual/maint.texi
index 3675c4f..d8e835f 100644
--- a/manual/maint.texi
+++ b/manual/maint.texi
@@ -176,11 +176,15 @@ facilities, type @code{make check}.  This will produce several files
 with names like @file{@var{program}.out}.
 
 To format the @cite{GNU C Library Reference Manual} for printing, type
-@w{@code{make dvi}}.
+@w{@code{make dvi}}.  You need a working @TeX{} installation to do this.
 
 To install the library and its header files, and the Info files of the
 manual, type @code{make install}.  This will build things if necessary,
-before installing them.@refill
+before installing them.  If you want to install the files in a different
+place than the one specified at configuration time you can specify a
+value for the Makefile variable @code{install_root} on the command line.
+This is useful to create chroot'ed environment or to prepare binary
+releases.@refill
 
 @node Tools for Installation
 @appendixsubsec Recommended Tools to Install the GNU C Library
@@ -192,15 +196,17 @@ build the GNU C library:
 
 @itemize @bullet
 @item
-@code{make} 3.75
+@code{make} 3.76.1
 
 You need the latest version of GNU @code{make}.  Modifying the GNU C
 Library to work with other @code{make} programs would be so hard that we
-recommend you port GNU @code{make} instead.  @strong{Really.}
-We recommend version GNU @code{make} version 3.75 or later.
+recommend you port GNU @code{make} instead.  @strong{Really.}  We
+recommend version GNU @code{make} version 3.75, 3.76.1 or later.
+Version 3.76 is known to have a bug which only shows up in big projects
+like GNU @code{libc}.
 
 @item
-GCC 2.7.2
+GCC 2.7.2.3
 
 On most platforms, the GNU C library can only be compiled with the GNU C
 compiler.  We recommend GCC version 2.7.2 or later; earlier versions may
@@ -216,8 +222,43 @@ Using the GNU @code{binutils} (assembler, linker, and related tools) is
 preferable when possible, and they are required to build an ELF shared C
 library.  We recommend @code{binutils} version 2.8.1 or later; earlier
 versions are known to have problems or to not support all architectures.
+
+@item
+@code{texinfo} 3.11
+
+To correctly translate and install the Texinfo documentation you need
+this version of the @code{texinfo} package.  Former versions did not
+understand all the tags used in the document and also the installation
+mechanisms for the info files was not present or worked differently.
+
+On some Debian Linux based systems the used @code{install-info} program
+works differently.  Here you have to run make like this:
+
+@smallexample
+make INSTALL_INFO=/path/to/GNU/install-info install
+@end smallexample
+@end itemize
+
+If you change any configuration file you will need also
+
+@itemize @bullet
+@item
+@code{autoconf} 2.12
 @end itemize
 
+@noindent
+and if you change any of the message translation files you will also need
+
+@itemize @bullet
+@item
+@code{GNU gettext} 0.10 or later
+@end itemize
+
+@noindent
+If you upgrade your source tree using the patches made available you probably
+will need those package above in any case.
+
+
 @node Supported Configurations
 @appendixsubsec Supported Configurations
 @cindex configurations, all supported
@@ -834,7 +875,7 @@ The DES encryption function @code{crypt} and related functions were
 contributed by Michael Glad.
 
 @item
-The @code{ftw} function was contributed by Ian Lance Taylor.
+The @code{ftw} and @code{nftw} function was contributed by Ulrich Drepper.
 
 @item
 The startup code to support SunOS shared libraries was contributed by
@@ -894,6 +935,11 @@ The port to Linux/m68k (@code{m68k-@var{anything}-linux}) was
 contributed by Andreas Schwab.
 
 @item
+The ports to Linux/ARM (@code{arm-@var{ANYTHING}-linuxaout}) and ARM
+standalone (@code{arm-@var{ANYTHING}-none}), as well as parts of the
+IPv6 support code, were contributed by Philip Blundell.
+
+@item
 Richard Henderson contributed the ELF dynamic linking code and other
 support for the Alpha processor.
 
diff --git a/manual/search.texi b/manual/search.texi
index abb93bb..356d976 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -14,9 +14,11 @@ and the total number of elements.
 * Array Search Function::       The @code{bsearch} function.
 * Array Sort Function::         The @code{qsort} function.
 * Search/Sort Example::         An example program.
+* Hash Search Function::        The @code{hsearch} function.
+* Tree Search Function::        The @code{tsearch} function.
 @end menu
 
-@node Comparison Functions, Array Search Function,  , Searching and Sorting
+@node Comparison Functions
 @section Defining the Comparison Function
 @cindex Comparison Function
 
@@ -52,12 +54,53 @@ comparison functions.  This type is a GNU extension.
 int comparison_fn_t (const void *, const void *);
 @end smallexample
 
-@node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
+@node Array Search Function
 @section Array Search Function
 @cindex search function (for arrays)
 @cindex binary search function (for arrays)
 @cindex array search function
 
+Generally searching for a specific element in an array means that
+potentially all elements must be checked.  The GNU C library contains
+functions to perform linear search.  The prototypes for the following
+two functions can be found in @file{search.h}.
+
+@comment search.h
+@comment SVID
+@deftypefun {void *} lfind (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
+The @code{lfind} function searches in the array with @code{*@var{nmemb}}
+elements of @var{size} bytes pointed to by @var{base} for an element
+which matches the one pointed to by @var{key}.  The function pointed to
+by @var{compar} is used decide whether two elements match.
+
+The return value is a pointer to the matching element in the array
+starting at @var{base} if it is found.  If no matching element is
+available @code{NULL} is returned.
+
+The mean runtime of this function is @code{*@var{nmemb}}/2.  This
+function should only be used elements often get added to or deleted from
+the array in which case it might not be useful to sort the array before
+searching.
+@end deftypefun
+
+@comment search.h
+@comment SVID
+@deftypefun {void *} lsearch (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
+The @code{lsearch} function is similar to the @code{lfind} function.  It
+searches the given array for an element and returns it if found.  The
+difference is that if no matching element is found the @code{lsearch}
+function adds the object pointed to by @var{key} (with a size of
+@var{size} bytes) at the end of the array and it increments the value of
+@code{*@var{nmemb}} to reflect this addition.
+
+This means for the caller that if it is not sure that the array contains
+the element one is searching for the memory allocated for the array
+starting at @var{base} must have room for at least @var{size} more
+bytes.  If one is sure the element is in the array it is better to use
+@code{lfind} so having more room in the array is always necessary when
+calling @code{lsearch}.
+@end deftypefun
+
 To search a sorted array for an element matching the key, use the
 @code{bsearch} function.  The prototype for this function is in
 the header file @file{stdlib.h}.
@@ -85,7 +128,7 @@ This function derives its name from the fact that it is implemented
 using the binary search algorithm.
 @end deftypefun
 
-@node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
+@node Array Sort Function
 @section Array Sort Function
 @cindex sort function (for arrays)
 @cindex quick sort function (for arrays)
@@ -138,7 +181,7 @@ The @code{qsort} function derives its name from the fact that it was
 originally implemented using the ``quick sort'' algorithm.
 @end deftypefun
 
-@node Search/Sort Example,  , Array Sort Function, Searching and Sorting
+@node Search/Sort Example
 @section Searching and Sorting Example
 
 Here is an example showing the use of @code{qsort} and @code{bsearch}
@@ -191,3 +234,318 @@ Kermit, the frog
 Gonzo, the whatever
 Couldn't find Janice.
 @end smallexample
+
+
+@node Hash Search Function
+@section The @code{hsearch} function.
+
+The functions mentioned so far in this chapter are searching in a sorted
+or unsorted array.  There are other methods to organize information
+which later should be searched.  The costs of insert, delete and search
+differ.  One possible implementation is using hashing tables.
+
+@comment search.h
+@comment SVID
+@deftypefun int hcreate (size_t @var{nel})
+The @code{hcreate} function creates a hashing table which can contain at
+least @var{nel} elements.  There is no possibility to grow this table so
+it is necessary to choose the value for @var{nel} wisely.  The used
+methods to implement this function might make it necessary to make the
+number of elements in the hashing table larger than the expected maximal
+number of elements.  Hashing tables usually work inefficient if they are
+filled 80% or more.  The constant access time guaranteed by hashing can
+only be achieved if few collisions exist.  See Knuth's ``The Art of
+Computer Programming, Part 3: Searching and Sorting'' for more
+information.
+
+The weakest aspect of this function is that there can be at most one
+hashing table used throught the whole program.  The table is allocated
+in local memory out of control of the programmer.  As an extension the
+GNU C library provides an additional set of functions with an reentrant
+interface which provide a similar interface but which allow to keep
+arbitrary many hashing tables.
+
+It is possible to use more than one hashing table in the program run if
+the former table is first destroyed by a call to @code{hdestroy}.
+
+The function returns a non-zero value if successful.  If it return zero
+something went wrong.  This could either mean there is already a hashing
+table in use or the program runs out of memory.
+@end deftypefun
+
+@comment search.h
+@comment SVID
+@deftypefun void hdestroy (void)
+The @code{hdestroy} function can be used to free all the resources
+allocated in a previous call of @code{hcreate}.  After a call to this
+function it is again possible to call @code{hcreate} and allocate a new
+table with possibly different size.
+
+It is important to remember that the elements contained in the hashing
+table at the time @code{hdestroy} is called are @emph{not} freed by this
+function.  It is the responsibility of the program code to free those
+strings (if necessary at all).  Freeing all the element memory iss not
+possible without extra, separately kept information since there is no
+function to iterate through all available elements in the hashing table.
+If it is really necessary to free a table and all elements the
+programmer has to keep a list of all table elements and before calling
+@code{hdestroy} s/he has to free all element's data using this list.
+This is a very unpleasent mechanism and it also shows that this kind of
+hashing tables is mainly meant for tables which are created once and
+used until the end of the program run.
+@end deftypefun
+
+Entries of the hashing table and keys for the search are defined using
+this type:
+
+@deftp {Data type} {struct ENTRY}
+Both elements of this structure are pointers to zero-terminated strings.
+This is a limiting restriction of the functionality of the
+@code{hsearch} functions.  They can only be used for data sets which use
+the NUL character always and solely to terminate the records.  It is not
+possible to handle general binary data.
+
+@table @code
+@item char *key
+Pointer to a zero-terminated string of characters describing the key for
+the search or the element in the hashing table.
+@item char *data
+Pointer to a zero-terminated string of characters describing the data.
+If the functions will be called only for searching an existing entry
+this element might stay undefined since it is not used.
+@end table
+@end deftp
+
+@comment search.h
+@comment SVID
+@deftypefun {ENTRY *} hsearch (ENTRY @var{item}, ACTION @var{action})
+To search in a hashing table created using @code{hcreate} the
+@code{hsearch} function must be used.  This function can perform simple
+search for an element (if @var{action} has the @code{FIND}) or it can
+alternatively insert the key element into the hashing table, possibly
+replacing a previous value (if @var{action} is @code{ENTER}).
+
+The key is denoted by a pointer to an object of type @code{ENTRY}.  For
+locating the corresponding position in the hashing table only the
+@code{key} element of the structure is used.
+
+The return value depends on the @var{action} parameter value.  If it is
+@code{FIND} the value is a pointer to the matching element in the
+hashing table or @code{NULL} if no matching element exists.  If
+@var{action} is @code{ENTER} the return value is only @code{NULL} if the
+programs runs out of memory while adding the new element to the table.
+Otherwise the return value is a pointer to the element in the hashing
+table which contains newly added element based on the data in @var{key}.
+@end deftypefun
+
+As mentioned before the hashing table used by the functions described so
+far is global and there can be at any time at most one hashing table in
+the program.  A solution is to use the following functions which are a
+GNU extension.  All have in common that they operate on a hashing table
+which is described by the content of an object of the type @code{struct
+hsearch_data}.  This type should be treated as opaque, none of its
+members should be changed directly.
+
+@comment search.h
+@comment GNU
+@deftypefun int hcreate_r (size_t @var{nel}, struct hsearch_data *@var{htab})
+The @code{hcreate_r} function intializes the object pointed to by
+@var{htab} to contain a hashing table with at least @var{nel} elements.
+So this function is equivalent to the @code{hcreate} function except
+that the initialized data structure is controlled by the user.
+
+This allows to have more than once hashing table at one time.  The
+memory necessary for the @code{struct hsearch_data} object can be
+allocated dynamically.
+
+The return value is non-zero if the operation were successful.  if the
+return value is zero something went wrong which probably means the
+programs runs out of memory.
+@end deftypefun
+
+@comment search.h
+@comment GNU
+@deftypefun void hdestroy_r (struct hsearch_data *@var{htab})
+The @code{hdestroy_r} function frees all resources allocated by the
+@code{hcreate_r} function for this very same object @var{htab}.  As for
+@code{hdestroy} it is the programs responsibility to free the strings
+for the elements of the table.
+@end deftypefun
+
+@comment search.h
+@comment GNU
+@deftypefun int hsearch_r (ENTRY @var{item}, ACTION @var{action}, ENTRY **@var{retval}, struct hsearch_data *@var{htab})
+The @code{hsearch_r} function is equivalent to @code{hsearch}.  The
+meaning of the first two arguments is identical.  But instead of
+operating on a single global hashing table the functio works on the
+table described by the object pointed to by @var{htab} (which is
+initialized by a call to @code{hcreate_r}).
+
+Another difference to @code{hcreate} is that the pointer to the found
+entry in the table is not the return value of the functions.  It is
+returned by storing it in a pointer variables pointed to by the
+@var{retval} parameter.  The return value of the function is an integer
+value indicating success if it is non-zero and failure if it is zero.
+In the later case the global variable @var{errno} signals the reason for
+the failure.
+
+@table @code
+@item ENOMEM
+The table is filled and @code{hsearch_r} was called with an so far
+unknown key and @var{action} set to @code{ENTER}.
+@item ESRCH
+The @var{action} parameter is @code{FIND} and no corresponding element
+is found in the table.
+@end table
+@end deftypefun
+
+
+@node Tree Search Function
+@section The @code{tsearch} function.
+
+Another common form to organize data for efficient search is to use
+trees.  The @code{tsearch} function family provides a nice interface to
+functions to organize possibly large amounts of data by providing a mean
+access time proportional to the logarithm of the number of elements.
+The GNU C library implementation even guarantees that this bound is
+never exceeded even for input data which cause problems for simple
+binary tree implementations.
+
+The functions desribed in the chapter are all described in the @w{System
+V} and X/Open specifications and are therefore quite portable.
+
+In contrast to the @code{hsearch} functions the @code{tsearch} functions
+can be used with arbitrary data and not only zero-terminated strings.
+
+The @code{tsearch} functions have the advantage that no function to
+initialize data structures is necessary.  A simple pointer of type
+@code{void *} initialized to @code{NULL} is a valid tree and can be
+extended or searched.
+
+@comment search.h
+@comment SVID
+@deftypefun {void *} tsearch (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
+The @code{tsearch} function searches in the tree pointed to by
+@code{*@var{rootp}} for an element matching @var{key}.  The function
+pointed to by @var{compar} is used to determine wether two elements
+match.  @xref{Comparison Functions} for a specification of the functions
+which can be used for the @var{compar} parameter.
+
+If the tree does not contain a matching entry the @var{key} value will
+be added to the tree.  @code{tsearch} does not make a copy of the object
+pointed to by @var{key} (how could it since the size is unknown).
+Instead it adds a reference to this object which means the object must
+be available as long as the tree data structure is used.
+
+The tree is represented by a pointer to a pointer since it is sometimes
+necessary to change the root node of the tree.  So it must not be
+assumed that the variable pointed to by @var{rootp} has the same value
+after the call.  This also shows that it is not safe to call the
+@code{tsearch} function more than once at the same time using the same
+tree.  It is no problem to run it more than once at a time on different
+trees.
+
+The return value is a pointer to the matching element in the tree.  If a
+new element was created the pointer points to the new data (which is in
+fact @var{key}).  If an entry had to be created and the program ran out
+of space @code{NULL} is returned.
+@end deftypefun
+
+@comment search.h
+@comment SVID
+@deftypefun {void *} tfind (const void *@var{key}, void *const *@var{rootp}, comparison_fn_t @var{compar})
+The @code{tfind} function is similar to the @code{tsearch} function.  It
+locates an element matching the one pointed to by @var{key} and returns
+a pointer to this element.  But if no matching element is available no
+new element is entered (note that the @var{rootp} parameter points to a
+constant pointer).  Instead the function returns @code{NULL}.
+@end deftypefun
+
+Another advantage of the @code{tsearch} function in contrast to the
+@code{hsearch} functions is that there is an easy way to remove
+elements.
+
+@comment search.h
+@comment SVID
+@deftypefun {void *} tdelete (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
+To remove a specific element matching @var{key} from the tree
+@code{tdelete} can be used.  It locates the matching element using the
+same method as @code{tfind}.  The corresponding element is then removed
+and the data if this tree node is returned by the function.  If there is
+no matching entry in the tree nothing can be deleted and the function
+returns @code{NULL}.
+@end deftypefun
+
+@comment search.h
+@comment GNU
+@deftypefun void tdestroy (void *@var{vroot}, __free_fn_t @var{freefct})
+If the complete search tree has to be removed one can use
+@code{tdestroy}.  It frees all resources allocated by the @code{tsearch}
+function to generate the tree pointed to by @var{vroot}.
+
+For the data in each tree node the function @var{freefct} is called.
+The pointer to the data is passed as the argument to the function.  If
+no such work is necessary @var{freefct} must point to a function doing
+nothing.  It is called in any case.
+
+This function is a GNU extension and not covered by the @w{System V} or
+X/Open specifications.
+@end deftypefun
+
+In addition to the function to create and destroy the tree data
+structure there is another function which allows to apply a function on
+all elements of the tree.  The function must have this type:
+
+@smallexample
+int __action_fn_t (const void *nodep, VISIT value, int level);
+@end smallexample
+
+The @var{nodep} is the data value of the current node (nce given as the
+@var{key} argument to @code{tsearch}).  @var{level} is a numeric value
+which corresponds to the depth of the current node in the tree.  The
+root node has the depth @math{0} and its children have a depth of
+@math{1} and so on.  The @code{VISIT} type is an enumeration type.
+
+@deftp {Data Type} VISIT
+The @code{VISIT} value indicates the status of the current node in the
+tree and how the function is called.  The status of a node is either
+`leaf' or `internal node'.  For each leaf node the function is called
+exactly once, for each internal node it is called three times: before
+the first child is processed, after the first child is processed and
+after both childs are processed.  This makes it possible to handle all
+three methods of tree traversal (or even a combination of them).
+
+@table @code
+@item preorder
+The current node is an internal node and the function is called before
+the first child was processed.
+@item endorder
+The current node is an internal node and the function is called after
+the first child was processed.
+@item postorder
+The current node is an internal node and the function is called after
+the second child was processed.
+@item leaf
+The current node is a leaf.
+@end table
+@end deftp
+
+@comment search.h
+@comment SVID
+@deftypefun void twalk (const void *@var{root}, __action_fn_t @var{action})
+For each node in the tree with a node pointed to by @var{root} the
+@code{twalk} function calls the function provided by the parameter
+@var{action}.  For leaf nodes the function is called exactly once with
+@var{value} set to @code{leaf}.  For internal nodes the function is
+called three times, setting the @var{value} parameter or @var{action} to
+the appropriate value.  The @var{level} argument for the @var{action}
+function is computed while descending the tree with increasing the value
+by one for the escend to a child, starting with the value @math{0} for
+the root node.
+
+Since the functions used for the @var{action} parameter to @code{twalk}
+must not modify the tree data it is safe to run @code{twalk} is more
+than one thread at the same time working on the same tree.  It is also
+safe to call @code{tfind} in parallel.  Functions which modify the tree
+must not be used.  Otherwise the behaviour is undefined.
+@end deftypefun