1 files changed, 127 insertions, 0 deletions

diff --git a/src/lib/libc/stdlib/tsearch.3 b/src/lib/libc/stdlib/tsearch.3
new file mode 100644
index 0000000000..0a52822620
--- /dev/null
+++ b/src/lib/libc/stdlib/tsearch.3
@@ -0,0 +1,127 @@
+.\" $OpenBSD: tsearch.3,v 1.16 2007/05/31 19:19:32 jmc Exp $
+.\"
+.\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: May 31 2007 $
+.Dt TSEARCH 3
+.Os
+.Sh NAME
+.Nm tsearch ,
+.Nm tfind ,
+.Nm tdelete ,
+.Nm twalk
+.Nd manipulate binary search trees
+.Sh SYNOPSIS
+.Fd #include <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 * const *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 (*action) (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
+.Dv 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 and a pointer to the new root will be returned.
+.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 RETURN VALUES
+The
+.Fn tsearch
+function returns
+.Dv 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
+.Dv NULL
+if
+.Fa rootp
+is
+.Dv NULL
+or the datum cannot be found.
+.Pp
+The
+.Fn twalk
+function returns no value.
+.Sh SEE ALSO
+.Xr bsearch 3 ,
+.Xr lsearch 3
+.Sh STANDARDS
+These functions conform to
+.St -p1003.1-2004 .
+.Sh CAVEATS
+The
+.St -p1003.1-2004
+standard does not specify what value should be returned when deleting the
+root node.
+Since implementations vary, the user of the
+.Fn tdelete
+function should not rely on a specific behaviour.