PD tsearch as reqd by xpg; by esr

4 files changed, 174 insertions, 4 deletions

diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index f224baed541..4c7f9db8343 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile.inc,v 1.6 1996/08/21 03:47:21 tholo Exp $
+#	$OpenBDS: Makefile.inc,v 1.6 1996/08/21 03:47:21 tholo Exp $
 
 # stdlib sources
 .PATH: ${.CURDIR}/arch/${MACHINE_ARCH}/stdlib ${.CURDIR}/stdlib
@@ -7,6 +7,7 @@ SRCS+=	a64l.c abort.c atexit.c atoi.c atof.c atol.c bsearch.c calloc.c \
 	cfree.c exit.c getenv.c getopt.c heapsort.c l64a.c malloc.c merge.c \
 	multibyte.c putenv.c qsort.c radixsort.c rand.c random.c realpath.c \
 	setenv.c strtod.c strtol.c strtoq.c strtoul.c strtouq.c system.c \
+	tfind.c tsearch.c \
 	_rand48.c drand48.c erand48.c jrand48.c lcong48.c lrand48.c \
 	mrand48.c nrand48.c seed48.c srand48.c qabs.c qdiv.c
 
@@ -34,7 +35,7 @@ SRCS+=	abs.c div.c labs.c ldiv.c
 MAN+=	abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \
 	calloc.3 div.3 exit.3 getenv.3 getopt.3 labs.3 ldiv.3 malloc.3 \
 	memory.3 qabs.3 qdiv.3 qsort.3 radixsort.3 rand48.3 rand.3 \
-	random.3 realpath.3 strtod.3 strtol.3 strtoul.3 system.3
+	random.3 realpath.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3
 
 MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3
 MLINKS+=malloc.3 free.3 malloc.3 realloc.3
@@ -47,3 +48,6 @@ MLINKS+=rand48.3 mrand48.3 rand48.3 nrand48.3 rand48.3 jrand48.3
 MLINKS+=rand48.3 srand48.3 rand48.3 seed48.3 rand48.3 lcong48.3
 MLINKS+=strtol.3 strtoq.3
 MLINKS+=strtoul.3 strtouq.3
+MLINKS+=tsearch.3 tfind.3
+MLINKS+=tsearch.3 tdelete.3
+MLINKS+=tsearch.3 twalk.3
diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3
index 7cfa7162d35..570a4227b42 100644
--- a/lib/libc/stdlib/bsearch.3
+++ b/lib/libc/stdlib/bsearch.3
@@ -33,7 +33,7 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"	$OpenBSD: bsearch.3,v 1.2 1996/08/10 04:52:52 tholo Exp $
+.\"	$OpenBSD: bsearch.3,v 1.3 1997/06/13 23:41:35 deraadt Exp $
 .\"
 .Dd April 19, 1994
 .Dt BSEARCH 3
@@ -82,7 +82,7 @@ If two members compare as equal, which member is matched is unspecified.
 .Xr db 3 ,
 .Xr lsearch 3 ,
 .Xr qsort 3 ,
-.\" .Xr tsearch 3
+.Xr tsearch 3
 .Sh STANDARDS
 The
 .Fn bsearch
diff --git a/lib/libc/stdlib/tfind.c b/lib/libc/stdlib/tfind.c
new file mode 100644
index 00000000000..8e77527bf51
--- /dev/null
+++ b/lib/libc/stdlib/tfind.c
@@ -0,0 +1,41 @@
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+/*LINTLIBRARY*/
+#include <search.h>
+
+typedef struct node_t
+{
+    char	  *key;
+    struct node_t *llink, *rlink;
+} node;
+
+/* find a node, or return 0 */
+void *
+tfind(vkey, vrootp, compar)
+	const void	*vkey;		/* key to be found */
+	void		**vrootp;	/* address of the tree root */
+	int		(*compar) __P((const void *, const void *));
+{
+    char *key = (char *)vkey;
+    node **rootp = (node **)vrootp;
+
+    if (rootp == (struct node_t **)0)
+	return ((struct node_t *)0);
+    while (*rootp != (struct node_t *)0) {	/* T1: */
+	int r;
+	if ((r = (*compar)(key, (*rootp)->key)) == 0)	/* T2: */
+	    return (*rootp);		/* key found */
+	rootp = (r < 0) ?
+	    &(*rootp)->llink :		/* T3: follow left branch */
+	    &(*rootp)->rlink;		/* T4: follow right branch */
+    }
+    return (node *)0;
+}
diff --git a/lib/libc/stdlib/tsearch.c b/lib/libc/stdlib/tsearch.c
new file mode 100644
index 00000000000..defa8a30060
--- /dev/null
+++ b/lib/libc/stdlib/tsearch.c
@@ -0,0 +1,125 @@
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only, lint doesn't grok it.
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+/*LINTLIBRARY*/
+
+#include <search.h>
+
+typedef struct node_t {
+    char	  *key;
+    struct node_t *left, *right;
+} node;
+
+/* find or insert datum into search tree */
+void *
+tsearch(vkey, vrootp, compar)
+	const void 	*vkey;		/* key to be located */
+	void		**vrootp;	/* address of tree root */
+	int		(*compar) __P((const void *, const void *));
+{
+    register node *q;
+    char *key = (char *)vkey;
+    node **rootp = (node **)vrootp;
+
+    if (rootp == (struct node_t **)0)
+	return ((void *)0);
+    while (*rootp != (struct node_t *)0) {	/* Knuth's T1: */
+	int r;
+
+	if ((r = (*compar)(key, (*rootp)->key)) == 0)	/* T2: */
+	    return ((void *)*rootp);		/* we found it! */
+	rootp = (r < 0) ?
+	    &(*rootp)->left :		/* T3: follow left branch */
+	    &(*rootp)->right;		/* T4: follow right branch */
+    }
+    q = (node *) malloc(sizeof(node));	/* T5: key not found */
+    if (q != (struct node_t *)0) {	/* make new node */
+	*rootp = q;			/* link new node to old */
+	q->key = key;			/* initialize new node */
+	q->left = q->right = (struct node_t *)0;
+    }
+    return ((void *)q);
+}
+
+/* delete node with given key */
+void *
+tdelete(vkey, vrootp, compar)
+	const void	*vkey;		/* key to be deleted */
+	void		**vrootp;	/* address of the root of tree */
+	int		(*compar) __P((const void *, const void *));
+{
+    node **rootp = (node **)vrootp;
+    char *key = (char *)vkey;
+    node *p;
+    register node *q;
+    register node *r;
+    int cmp;
+
+    if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
+	return ((struct node_t *)0);
+    while ((cmp = (*compar)(key, (*rootp)->key)) != 0) {
+	p = *rootp;
+	rootp = (cmp < 0) ?
+	    &(*rootp)->left :		/* follow left branch */
+	    &(*rootp)->right;		/* follow right branch */
+	if (*rootp == (struct node_t *)0)
+	    return ((void *)0);		/* key not found */
+    }
+    r = (*rootp)->right;			/* D1: */
+    if ((q = (*rootp)->left) == (struct node_t *)0)	/* Left (struct node_t *)0? */
+	q = r;
+    else if (r != (struct node_t *)0) {		/* Right link is null? */
+	if (r->left == (struct node_t *)0) {	/* D2: Find successor */
+	    r->left = q;
+	    q = r;
+	} else {			/* D3: Find (struct node_t *)0 link */
+	    for (q = r->left; q->left != (struct node_t *)0; q = r->left)
+		r = q;
+	    r->left = q->right;
+	    q->left = (*rootp)->left;
+	    q->right = (*rootp)->right;
+	}
+    }
+    free((struct node_t *) *rootp);	/* D4: Free node */
+    *rootp = q;				/* link parent to new node */
+    return(p);
+}
+
+/* Walk the nodes of a tree */
+static void
+trecurse(root, action, level)
+	register node	*root;		/* Root of the tree to be walked */
+	register void	(*action)();	/* Function to be called at each node */
+	register int	level;
+{
+    if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
+	(*action)(root, leaf, level);
+    else {
+	(*action)(root, preorder, level);
+	if (root->left != (struct node_t *)0)
+	    trecurse(root->left, action, level + 1);
+	(*action)(root, postorder, level);
+	if (root->right != (struct node_t *)0)
+	    trecurse(root->right, action, level + 1);
+	(*action)(root, endorder, level);
+    }
+}
+
+/* Walk the nodes of a tree */
+void
+twalk(vroot, action)
+	const void	*vroot;		/* Root of the tree to be walked */
+	void		(*action) __P((const void *, VISIT, int));
+{
+    node *root = (node *)vroot;
+
+    if (root != (node *)0 && action != (void(*)())0)
+	trecurse(root, action, 0);
+}