From 3e424d0a241f8ae5194514dabc4ad899f5a5416d Mon Sep 17 00:00:00 2001 From: Elliott Hughes Date: Wed, 23 Jul 2014 16:02:26 -0700 Subject: Implement twalk(3), add unit tests. I've also added insque(3) and remque(3) (from NetBSD because the OpenBSD ones are currently broken for non-circular lists). I've not added the three hash table functions that should be in this header because they operate on a single global hash table and thus aren't likely to be useful. Bug: https://code.google.com/p/android/issues/detail?id=73719 Change-Id: I97397a7b921e2e860fd9c8032cafd9097380498a --- libc/upstream-openbsd/lib/libc/stdlib/lsearch.c | 84 +++++++++++++++++ libc/upstream-openbsd/lib/libc/stdlib/tfind.c | 41 ++++++++ libc/upstream-openbsd/lib/libc/stdlib/tsearch.c | 119 ++++++++++++++++++++++++ 3 files changed, 244 insertions(+) create mode 100644 libc/upstream-openbsd/lib/libc/stdlib/lsearch.c create mode 100644 libc/upstream-openbsd/lib/libc/stdlib/tfind.c create mode 100644 libc/upstream-openbsd/lib/libc/stdlib/tsearch.c (limited to 'libc/upstream-openbsd') diff --git a/libc/upstream-openbsd/lib/libc/stdlib/lsearch.c b/libc/upstream-openbsd/lib/libc/stdlib/lsearch.c new file mode 100644 index 0000000..8cad05f --- /dev/null +++ b/libc/upstream-openbsd/lib/libc/stdlib/lsearch.c @@ -0,0 +1,84 @@ +/* $OpenBSD: lsearch.c,v 1.5 2014/07/18 04:16:09 matthew Exp $ */ + +/* + * Copyright (c) 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Roger L. Snyder. + * + * 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. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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. + */ + +#include +#include +#include + +typedef int (*cmp_fn_t)(const void *, const void *); +static void *linear_base(const void *, const void *, size_t *, size_t, + cmp_fn_t, int); + +void * +lsearch(const void *key, void *base, size_t *nelp, size_t width, + cmp_fn_t compar) +{ + + return(linear_base(key, base, nelp, width, compar, 1)); +} + +void * +lfind(const void *key, const void *base, size_t *nelp, size_t width, + cmp_fn_t compar) +{ + return(linear_base(key, base, nelp, width, compar, 0)); +} + +static void * +linear_base(const void *key, const void *base, size_t *nelp, size_t width, + cmp_fn_t compar, int add_flag) +{ + const char *element, *end; + + end = (const char *)base + *nelp * width; + for (element = base; element < end; element += width) + if (!compar(key, element)) /* key found */ + return((void *)element); + + if (!add_flag) /* key not found */ + return(NULL); + + /* + * The UNIX System User's Manual, 1986 edition claims that + * a NULL pointer is returned by lsearch with errno set + * appropriately, if there is not enough room in the table + * to add a new item. This can't be done as none of these + * routines have any method of determining the size of the + * table. This comment isn't in the 1986-87 System V + * manual. + */ + ++*nelp; + memcpy((void *)end, key, width); + return((void *)end); +} diff --git a/libc/upstream-openbsd/lib/libc/stdlib/tfind.c b/libc/upstream-openbsd/lib/libc/stdlib/tfind.c new file mode 100644 index 0000000..0d1d519 --- /dev/null +++ b/libc/upstream-openbsd/lib/libc/stdlib/tfind.c @@ -0,0 +1,41 @@ +/* $OpenBSD: tfind.c,v 1.6 2014/03/16 18:38:30 guenther 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 + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ +/*LINTLIBRARY*/ +#include + +typedef struct node_t +{ + char *key; + struct node_t *llink, *rlink; +} node; + +/* find a node, or return 0 */ +void * +tfind(const void *vkey, void * const *vrootp, + int (*compar)(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/libc/upstream-openbsd/lib/libc/stdlib/tsearch.c b/libc/upstream-openbsd/lib/libc/stdlib/tsearch.c new file mode 100644 index 0000000..a141085 --- /dev/null +++ b/libc/upstream-openbsd/lib/libc/stdlib/tsearch.c @@ -0,0 +1,119 @@ +/* $OpenBSD: tsearch.c,v 1.8 2014/03/16 18:38:30 guenther 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 + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ +/*LINTLIBRARY*/ + +#include +#include + +typedef struct node_t { + char *key; + struct node_t *left, *right; +} node; + +/* find or insert datum into search tree */ +void * +tsearch(const void *vkey, void **vrootp, + int (*compar)(const void *, const void *)) +{ + 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(const void *vkey, void **vrootp, + int (*compar)(const void *, const void *)) +{ + node **rootp = (node **)vrootp; + char *key = (char *)vkey; + node *p = (node *)1; + node *q; + node *r; + int cmp; + + if (rootp == (struct node_t **)0 || *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(node *root, void (*action)(const void *, VISIT, int), 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(const void *vroot, void (*action)(const void *, VISIT, int)) +{ + node *root = (node *)vroot; + + if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0) + trecurse(root, action, 0); +} -- cgit v1.1