diff options
| -rw-r--r-- | include/Makefile | 3 | ||||
| -rw-r--r-- | include/search.h | 66 | ||||
| -rw-r--r-- | lib/libc/stdlib/Makefile.inc | 4 | ||||
| -rw-r--r-- | lib/libc/stdlib/tdelete.c | 66 | ||||
| -rw-r--r-- | lib/libc/stdlib/tfind.c | 47 | ||||
| -rw-r--r-- | lib/libc/stdlib/tsearch.3 | 118 | ||||
| -rw-r--r-- | lib/libc/stdlib/tsearch.c | 57 | ||||
| -rw-r--r-- | lib/libc/stdlib/twalk.c | 57 |
8 files changed, 415 insertions, 3 deletions
diff --git a/include/Makefile b/include/Makefile index 4cd856e..c6fd25e 100644 --- a/include/Makefile +++ b/include/Makefile @@ -14,7 +14,8 @@ FILES= a.out.h ar.h assert.h bitstring.h ctype.h db.h dirent.h disktab.h \ limits.h link.h locale.h malloc.h memory.h mpool.h \ ndbm.h netdb.h nl_types.h nlist.h objformat.h \ paths.h pthread.h pthread_np.h pwd.h \ - ranlib.h regex.h regexp.h resolv.h rune.h runetype.h setjmp.h sgtty.h \ + ranlib.h regex.h regexp.h resolv.h rune.h runetype.h \ + search.h setjmp.h sgtty.h \ signal.h stab.h stddef.h stdio.h stdlib.h string.h stringlist.h \ strings.h struct.h sysexits.h tar.h time.h timers.h \ ttyent.h unistd.h utime.h utmp.h vis.h diff --git a/include/search.h b/include/search.h new file mode 100644 index 0000000..c72b16f --- /dev/null +++ b/include/search.h @@ -0,0 +1,66 @@ +/* $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ */ +/* $FreeBSD$ */ + +/* + * Written by J.T. Conklin <jtc@netbsd.org> + * Public domain. + */ + +#ifndef _SEARCH_H_ +#define _SEARCH_H_ + +#include <sys/cdefs.h> +#include <machine/ansi.h> + +#ifdef _BSD_SIZE_T_ +typedef _BSD_SIZE_T_ size_t; +#undef _BSD_SIZE_T_ +#endif + +typedef struct entry { + char *key; + void *data; +} ENTRY; + +typedef enum { + FIND, ENTER +} ACTION; + +typedef enum { + preorder, + postorder, + endorder, + leaf +} VISIT; + +#ifdef _SEARCH_PRIVATE +typedef struct node { + char *key; + struct node *llink, *rlink; +} node_t; +#endif + +__BEGIN_DECLS +void *bsearch __P((const void *, const void *, size_t, size_t, + int (*)(const void *, const void *))); +int hcreate __P((size_t)); +void hdestroy __P((void)); +ENTRY *hsearch __P((ENTRY, ACTION)); + +void *lfind __P((const void *, const void *, size_t *, size_t, + int (*)(const void *, const void *))); +void *lsearch __P((const void *, const void *, size_t *, size_t, + int (*)(const void *, const void *))); +void insque __P((void *, void *)); +void remque __P((void *)); + +void *tdelete __P((const void *, void **, + int (*)(const void *, const void *))); +void *tfind __P((const void *, void **, + int (*)(const void *, const void *))); +void *tsearch __P((const void *, void **, + int (*)(const void *, const void *))); +void twalk __P((const void *, void (*)(const void *, VISIT, int))); +__END_DECLS + +#endif /* !_SEARCH_H_ */ diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index cb1d91f..12ec5d4 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -8,7 +8,7 @@ MISRCS+=abort.c abs.c atexit.c atof.c atoi.c atol.c bsearch.c calloc.c div.c \ exit.c getenv.c getopt.c getsubopt.c heapsort.c labs.c ldiv.c \ malloc.c merge.c putenv.c qsort.c radixsort.c rand.c random.c \ reallocf.c realpath.c setenv.c strhash.c strtol.c strtoq.c strtoul.c \ - strtouq.c system.c + strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c .if ${MACHINE_ARCH} == "alpha" # XXX Temporary until the assumption that a long is 32-bits is resolved @@ -26,7 +26,7 @@ SRCS+= strtod.c MAN3+= abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \ div.3 exit.3 getenv.3 getopt.3 getsubopt.3 labs.3 \ ldiv.3 malloc.3 memory.3 qsort.3 radixsort.3 rand.3 random.3 \ - realpath.3 strtod.3 strtol.3 strtoul.3 system.3 + realpath.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3 MLINKS+=getenv.3 putenv.3 getenv.3 setenv.3 getenv.3 unsetenv.3 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 diff --git a/lib/libc/stdlib/tdelete.c b/lib/libc/stdlib/tdelete.c new file mode 100644 index 0000000..daf4aa7 --- /dev/null +++ b/lib/libc/stdlib/tdelete.c @@ -0,0 +1,66 @@ +/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ +/* $FreeBSD$ */ + +/* + * 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.2 1999/09/16 11:45:37 lukem Exp $"); +#endif /* LIBC_SCCS and not lint */ + +#include <assert.h> +#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 0000000..b2c4b96 --- /dev/null +++ b/lib/libc/stdlib/tfind.c @@ -0,0 +1,47 @@ +/* $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ +/* $FreeBSD$ */ + +/* + * 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.2 1999/09/16 11:45:37 lukem Exp $"); +#endif /* LIBC_SCCS and not lint */ + +#include <assert.h> +#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 0000000..4dcf658 --- /dev/null +++ b/lib/libc/stdlib/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$ +.\" +.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 0000000..85832ce --- /dev/null +++ b/lib/libc/stdlib/tsearch.c @@ -0,0 +1,57 @@ +/* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ */ +/* $FreeBSD$ */ + +/* + * 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.3 1999/09/16 11:45:37 lukem Exp $"); +#endif /* LIBC_SCCS and not lint */ + +#include <assert.h> +#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 */ + /* LINTED const castaway ok */ + 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 0000000..eab71df --- /dev/null +++ b/lib/libc/stdlib/twalk.c @@ -0,0 +1,57 @@ +/* $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $ */ +/* $FreeBSD$ */ + +/* + * 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 */ + +#include <assert.h> +#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); +} |
