diff options
author | alfred <alfred@FreeBSD.org> | 2000-07-01 06:55:11 +0000 |
---|---|---|
committer | alfred <alfred@FreeBSD.org> | 2000-07-01 06:55:11 +0000 |
commit | 5a1e6c960d9a13a4078c249a02eea6c731abd3c5 (patch) | |
tree | ac4858db9bf0905af84e0d5b7542d95bf1cd9e17 /lib/libc/stdlib/tfind.c | |
parent | 2cd7c167097741abca2a3cd42f54cd066b988858 (diff) | |
download | FreeBSD-src-5a1e6c960d9a13a4078c249a02eea6c731abd3c5.zip FreeBSD-src-5a1e6c960d9a13a4078c249a02eea6c731abd3c5.tar.gz |
bring in binary search tree code.
Obtained from: NetBSD
Diffstat (limited to 'lib/libc/stdlib/tfind.c')
-rw-r--r-- | lib/libc/stdlib/tfind.c | 47 |
1 files changed, 47 insertions, 0 deletions
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; +} |