summaryrefslogtreecommitdiff
path: root/lib/libc/stdlib
diff options
context:
space:
mode:
authorchristos <christos@NetBSD.org>1999-02-22 10:33:15 +0000
committerchristos <christos@NetBSD.org>1999-02-22 10:33:15 +0000
commit7975455d4528eaa09f0c561d2fde4088681231ab (patch)
tree076a6d79fc1c4c4a8ae0b580a9a037b2e0ef5b69 /lib/libc/stdlib
parent3d6a63081300320bc2a55149b681b8071d22a60b (diff)
t{search,find,walk,delete} from OpenBSD via Neil A. Carson
Diffstat (limited to 'lib/libc/stdlib')
-rw-r--r--lib/libc/stdlib/Makefile.inc8
-rw-r--r--lib/libc/stdlib/tdelete.c64
-rw-r--r--lib/libc/stdlib/tfind.c45
-rw-r--r--lib/libc/stdlib/tsearch.3117
-rw-r--r--lib/libc/stdlib/tsearch.c54
-rw-r--r--lib/libc/stdlib/twalk.c54
6 files changed, 339 insertions, 3 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index 200124cbca0..d592ec15d93 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.39 1999/02/06 15:04:05 kleink Exp $
+# $NetBSD: Makefile.inc,v 1.40 1999/02/22 10:33:15 christos Exp $
# from: @(#)Makefile.inc 8.3 (Berkeley) 2/4/95
# stdlib sources
@@ -10,7 +10,8 @@ SRCS+= _rand48.c _strtoq.c _strtouq.c a64l.c abort.c atexit.c atof.c \
lcong48.c lrand48.c malloc.c merge.c mrand48.c multibyte.c \
nrand48.c putenv.c qabs.c qdiv.c qsort.c radixsort.c rand.c \
rand_r.c random.c seed48.c setenv.c srand48.c strtod.c \
- strtol.c strtoq.c strtoq.c strtoul.c strtouq.c system.c
+ strtol.c strtoq.c strtoq.c strtoul.c strtouq.c system.c \
+ tdelete.c tfind.c tsearch.c twalk.c
# machine-dependent stdlib sources
# m-d Makefile.inc must include sources for:
@@ -22,7 +23,7 @@ MAN+= a64l.3 abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \
calloc.3 div.3 exit.3 free.3 getenv.3 getopt.3 getsubopt.3 \
labs.3 ldiv.3 malloc.3 memory.3 qabs.3 qdiv.3 qsort.3 \
radixsort.3 rand48.3 rand.3 random.3 realloc.3 strtod.3 \
- strtol.3 strtoul.3 system.3
+ strtol.3 strtoul.3 system.3 tsearch.3
MLINKS+=a64l.3 l64a.3
MLINKS+=a64l.3 l64a_r.3
@@ -36,3 +37,4 @@ MLINKS+=rand48.3 srand48.3 rand48.3 seed48.3 rand48.3 lcong48.3
MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3
MLINKS+=strtol.3 strtoq.3
MLINKS+=strtoul.3 strtouq.3
+MLINKS+=tsearch.3 tfind.3 tsearch.3 twalk.3 tsearch.3 tdelete.3
diff --git a/lib/libc/stdlib/tdelete.c b/lib/libc/stdlib/tdelete.c
new file mode 100644
index 00000000000..1b61386a569
--- /dev/null
+++ b/lib/libc/stdlib/tdelete.c
@@ -0,0 +1,64 @@
+/* $NetBSD: tdelete.c,v 1.1 1999/02/22 10:33:15 christos Exp $ */
+
+/*
+ * 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.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+__RCSID("$NetBSD: tdelete.c,v 1.1 1999/02/22 10:33:15 christos Exp $");
+#endif /* LIBC_SCCS and not lint */
+
+#define _SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+
+/* 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_t **rootp = (node_t **)vrootp;
+ node_t *p, *q, *r;
+ int cmp;
+
+ if (rootp == NULL || (p = *rootp) == NULL)
+ return NULL;
+
+ while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
+ p = *rootp;
+ rootp = (cmp < 0) ?
+ &(*rootp)->llink : /* follow llink branch */
+ &(*rootp)->rlink; /* follow rlink branch */
+ if (*rootp == NULL)
+ return NULL; /* key not found */
+ }
+ r = (*rootp)->rlink; /* D1: */
+ if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
+ q = r;
+ else if (r != NULL) { /* Right link is NULL? */
+ if (r->llink == NULL) { /* D2: Find successor */
+ r->llink = q;
+ q = r;
+ } else { /* D3: Find NULL link */
+ for (q = r->llink; q->llink != NULL; q = r->llink)
+ r = q;
+ r->llink = q->rlink;
+ q->llink = (*rootp)->llink;
+ q->rlink = (*rootp)->rlink;
+ }
+ }
+ free(*rootp); /* D4: Free node */
+ *rootp = q; /* link parent to new node */
+ return p;
+}
diff --git a/lib/libc/stdlib/tfind.c b/lib/libc/stdlib/tfind.c
new file mode 100644
index 00000000000..19b81110a26
--- /dev/null
+++ b/lib/libc/stdlib/tfind.c
@@ -0,0 +1,45 @@
+/* $NetBSD: tfind.c,v 1.1 1999/02/22 10:33:15 christos Exp $ */
+
+/*
+ * 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.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+__RCSID("$NetBSD: tfind.c,v 1.1 1999/02/22 10:33:15 christos Exp $");
+#endif /* LIBC_SCCS and not lint */
+
+#define _SEARCH_PRIVATE
+#include <stdlib.h>
+#include <search.h>
+
+/* 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 *));
+{
+ node_t **rootp = (node_t **)vrootp;
+
+ if (rootp == NULL)
+ return NULL;
+
+ while (*rootp != NULL) { /* T1: */
+ int r;
+
+ if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
+ return *rootp; /* key found */
+ rootp = (r < 0) ?
+ &(*rootp)->llink : /* T3: follow left branch */
+ &(*rootp)->rlink; /* T4: follow right branch */
+ }
+ return NULL;
+}
diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3
new file mode 100644
index 00000000000..25ff467991f
--- /dev/null
+++ b/lib/libc/stdlib/tsearch.3
@@ -0,0 +1,117 @@
+.\" $NetBSD: tsearch.3,v 1.1 1999/02/22 10:33:15 christos Exp $
+.\" 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
+.\"
+.Dd June 15, 1997
+.Dt TSEARCH 3
+.Os
+.Sh NAME
+.Nm tsearch, tfind, tdelete, 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" "const 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.
diff --git a/lib/libc/stdlib/tsearch.c b/lib/libc/stdlib/tsearch.c
new file mode 100644
index 00000000000..cf3e0f98af1
--- /dev/null
+++ b/lib/libc/stdlib/tsearch.c
@@ -0,0 +1,54 @@
+/* $NetBSD: tsearch.c,v 1.1 1999/02/22 10:33:16 christos Exp $ */
+
+/*
+ * 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.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+__RCSID("$NetBSD: tsearch.c,v 1.1 1999/02/22 10:33:16 christos Exp $");
+#endif /* LIBC_SCCS and not lint */
+
+#define _SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+/* 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 *));
+{
+ node_t *q;
+ node_t **rootp = (node_t **)vrootp;
+
+ if (rootp == NULL)
+ return NULL;
+
+ while (*rootp != NULL) { /* Knuth's T1: */
+ int r;
+
+ if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
+ return *rootp; /* we found it! */
+
+ rootp = (r < 0) ?
+ &(*rootp)->llink : /* T3: follow left branch */
+ &(*rootp)->rlink; /* T4: follow right branch */
+ }
+
+ q = malloc(sizeof(node_t)); /* T5: key not found */
+ if (q != 0) { /* make new node */
+ *rootp = q; /* link new node to old */
+ q->key = (void *)vkey; /* initialize new node */
+ q->llink = q->rlink = NULL;
+ }
+ return q;
+}
diff --git a/lib/libc/stdlib/twalk.c b/lib/libc/stdlib/twalk.c
new file mode 100644
index 00000000000..507e893bbec
--- /dev/null
+++ b/lib/libc/stdlib/twalk.c
@@ -0,0 +1,54 @@
+/* $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $ */
+
+/*
+ * 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.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+__RCSID("$NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $");
+#endif /* LIBC_SCCS and not lint */
+
+#define _SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+static void trecurse __P((const node_t *,
+ void (*action)(const void *, VISIT, int), int level));
+
+/* Walk the nodes of a tree */
+static void
+trecurse(root, action, level)
+ const node_t *root; /* Root of the tree to be walked */
+ void (*action) __P((const void *, VISIT, int));
+ int level;
+{
+ if (root->llink == NULL && root->rlink == NULL)
+ (*action)(root, leaf, level);
+ else {
+ (*action)(root, preorder, level);
+ if (root->llink != NULL)
+ trecurse(root->llink, action, level + 1);
+ (*action)(root, postorder, level);
+ if (root->rlink != NULL)
+ trecurse(root->rlink, 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));
+{
+ if (vroot != NULL && action != NULL)
+ trecurse(vroot, action, 0);
+}