diff options
Diffstat (limited to 'lib/libc/stdlib')
| -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 |
5 files changed, 0 insertions, 345 deletions
diff --git a/lib/libc/stdlib/tdelete.c b/lib/libc/stdlib/tdelete.c deleted file mode 100644 index daf4aa71400fe..0000000000000 --- a/lib/libc/stdlib/tdelete.c +++ /dev/null @@ -1,66 +0,0 @@ -/* $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 deleted file mode 100644 index b2c4b9618bb76..0000000000000 --- a/lib/libc/stdlib/tfind.c +++ /dev/null @@ -1,47 +0,0 @@ -/* $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 deleted file mode 100644 index 4dcf658cadca6..0000000000000 --- a/lib/libc/stdlib/tsearch.3 +++ /dev/null @@ -1,118 +0,0 @@ -.\" $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 deleted file mode 100644 index 85832ce480a38..0000000000000 --- a/lib/libc/stdlib/tsearch.c +++ /dev/null @@ -1,57 +0,0 @@ -/* $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 deleted file mode 100644 index eab71df638ca6..0000000000000 --- a/lib/libc/stdlib/twalk.c +++ /dev/null @@ -1,57 +0,0 @@ -/* $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); -} |