diff options
author | Thomas Fitzsimmons <fitzsim@redhat.com> | 2002-06-20 23:51:40 +0400 |
---|---|---|
committer | Thomas Fitzsimmons <fitzsim@redhat.com> | 2002-06-20 23:51:40 +0400 |
commit | a7b23a8f11b2e1f2ef333d2ed95d1c972acad12f (patch) | |
tree | 26eb76cc430a851b89de107870b4f6b177311072 /newlib/libc/search/tsearch.3 | |
parent | c25ebbaf55dbef934d85522616d898eef37438e4 (diff) |
* Makefile.am (LIB_OBJECTLISTS): Add
libc/search/objectlist.awk.in.
* libc/Makefile.am (SUBDIRS): Add search.
(SUBLIBS): Add search/libsearch.la.
* libc/configure.in (AC_OUTPUT): Add search/Makefile.
* libc/search: New directory.
* libc/search/Makefile.am: New file.
* libc/search/extern.h: New file.
* libc/search/hash.c: New file.
* libc/search/hash.h: New file.
* libc/search/hash_bigkey.c: New file.
* libc/search/hash_buf.c: New file.
* libc/search/hash_func.c: New file.
* libc/search/hash_log2.c: New file.
* libc/search/hash_page.c: New file.
* libc/search/hcreate.3: New file.
* libc/search/hcreate.c: New file.
* libc/search/hcreate.c~: New file.
* libc/search/hcreate_r.c: New file.
* libc/search/ndbm.c: New file.
* libc/search/page.h: New file.
* libc/search/tdelete.c: New file.
* libc/search/tdestroy.c: New file.
* libc/search/tfind.c: New file.
* libc/search/tsearch.3: New file.
* libc/search/tsearch.c: New file.
* libc/search/twalk.c: New file.
* libc/include/db.h: New file.
* libc/include/ndbm.h: New file.
* libc/include/search.h: New file.
* libc/include/sys/queue.h: New file.
* libc/include/sys/cdefs.h: New file.
* libc/include/sys/param.h
[__IEEE_LITTLE_ENDIAN,__IEEE_BIG_ENDIAN]: Set BYTE_ORDER to
LITTLE_ENDIAN or BIG_ENDIAN.
* libc/include/sys/errno.h (EFTYPE): New macro.
* libc/search/bsearch.c: Move from libc/stdlib.
* libc/search/qsort.c: Likewise.
* libc/stdlib/Makefile.am (LIB_SOURCES): Remove bsearch.c and
qsort.c.
(CHEWOUT_FILES): Remove bsearch.def and qsort.def.
* libc/stdlib/stdlib.tex: Remove references to bsearch and qsort.
Diffstat (limited to 'newlib/libc/search/tsearch.3')
-rw-r--r-- | newlib/libc/search/tsearch.3 | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/newlib/libc/search/tsearch.3 b/newlib/libc/search/tsearch.3 new file mode 100644 index 000000000..a36fe894f --- /dev/null +++ b/newlib/libc/search/tsearch.3 @@ -0,0 +1,118 @@ +.\" $NetBSD$ +.\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com> +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, +.\" INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY +.\" AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +.\" THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +.\" EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +.\" PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; +.\" OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, +.\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR +.\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF +.\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.\" +.\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp +.\" $FreeBSD: src/lib/libc/stdlib/tsearch.3,v 1.7 2001/09/07 14:46:36 asmodai Exp $ +.\" +.Dd June 15, 1997 +.Dt TSEARCH 3 +.Os +.Sh NAME +.Nm tsearch , tfind , tdelete , twalk +.Nd manipulate binary search trees +.Sh SYNOPSIS +.In search.h +.Ft void * +.Fn tdelete "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" +.Ft void * +.Fn tfind "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" +.Ft void * +.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" +.Ft void +.Fn twalk "const void *root" "void (*compar) (const void *, VISIT, int)" +.Sh DESCRIPTION +The +.Fn tdelete , +.Fn tfind , +.Fn tsearch , +and +.Fn twalk +functions manage binary search trees based on algorithms T and D +from Knuth (6.2.2). The comparison function passed in by +the user has the same style of return values as +.Xr strcmp 3 . +.Pp +.Fn Tfind +searches for the datum matched by the argument +.Fa key +in the binary tree rooted at +.Fa rootp , +returning a pointer to the datum if it is found and NULL +if it is not. +.Pp +.Fn Tsearch +is identical to +.Fn tfind +except that if no match is found, +.Fa key +is inserted into the tree and a pointer to it is returned. If +.Fa rootp +points to a NULL value a new binary search tree is created. +.Pp +.Fn Tdelete +deletes a node from the specified binary search tree and returns +a pointer to the parent of the node to be deleted. +It takes the same arguments as +.Fn tfind +and +.Fn tsearch . +If the node to be deleted is the root of the binary search tree, +.Fa rootp +will be adjusted. +.Pp +.Fn Twalk +walks the binary search tree rooted in +.Fa root +and calls the function +.Fa action +on each node. +.Fa Action +is called with three arguments: a pointer to the current node, +a value from the enum +.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;" +specifying the traversal type, and a node level (where level +zero is the root of the tree). +.Sh SEE ALSO +.Xr bsearch 3 , +.Xr hsearch 3 , +.Xr lsearch 3 +.Sh RETURN VALUES +The +.Fn tsearch +function returns NULL if allocation of a new node fails (usually +due to a lack of free memory). +.Pp +.Fn Tfind , +.Fn tsearch , +and +.Fn tdelete +return NULL if +.Fa rootp +is NULL or the datum cannot be found. +.Pp +The +.Fn twalk +function returns no value. |