Index: stdlib/tdelete.c =================================================================== --- stdlib/tdelete.c +++ stdlib/tdelete.c @@ -1,72 +1,111 @@ -/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ * - * The node_t structure is for internal use only, lint doesn't grok it. + * 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. * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 -#if 0 -#if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $"); -#endif /* LIBC_SCCS and not lint */ -#endif __FBSDID("$FreeBSD$"); #define _SEARCH_PRIVATE #include +#include #include +#include "tnode.h" /* - * find a node with given key - * - * vkey: key to be found - * vrootp: address of the root of the tree - * compar: function to carry out node comparisons + * Extracts the key of the largest node from a tree, while maintaining + * its balance. */ -void * -tdelete(const void * __restrict vkey, void ** __restrict vrootp, - int (*compar)(const void *, const void *)) +static bool +tdelete_extract_largest(node_t **np, void **result) { - node_t **rootp = (node_t **)vrootp; - node_t *p, *q, *r; + node_t *n; + + n = *np; + if (n->rlink == NULL) { + /* Found the maximum node. Extract key and delete the node.*/ + *result = n->key; + *np = n->llink; + free(n); + return (true); + } else { + /* Extract the largest node from the right subtree. */ + return (tdelete_extract_largest(&n->rlink, result) && + !tnode_balance_increase(np)); + } +} + +static bool +tdelete_recurse(const void *key, node_t **n, + int (*compar)(const void *, const void *), void **result) +{ 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; + if (*n == NULL) { + /* Did not find a matching key in the tree. */ + *result = NULL; + return (false); + } else { + /* Use the comparison function to traverse the tree. */ + cmp = compar(key, (*n)->key); + if (cmp < 0) { + *result = &(*n)->key; + return (tdelete_recurse(key, &(*n)->llink, compar, + result) && !tnode_balance_decrease(n)); + } else if (cmp > 0) { + *result = &(*n)->key; + return (tdelete_recurse(key, &(*n)->rlink, compar, + result) && !tnode_balance_increase(n)); + } else { + /* Found a matching node to delete. */ + if ((*n)->llink == NULL) { + /* No left child. Replace by right subtree. */ + node_t *newroot = (*n)->rlink; + free(*n); + *n = newroot; + return (true); + } else { + /* + * Replace this node's key by its predecessor's + * and deallocate that node instead. + */ + return (tdelete_extract_largest(&(*n)->llink, + &(*n)->key) && !tnode_balance_decrease(n)); + } } } - if (p != *rootp) - free(*rootp); /* D4: Free node */ - *rootp = q; /* link parent to new node */ - return p; } + +void * +tdelete(const void *restrict key, void **restrict rootp, + int (*compar)(const void *, const void *)) +{ + void *result; + + if (result == NULL) + return (NULL); + result = (void *)1; + tdelete_recurse(key, (node_t **)rootp, compar, &result); + return (result); +} Index: stdlib/tnode.h =================================================================== --- stdlib/tnode.h +++ stdlib/tnode.h @@ -0,0 +1,167 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ + +#ifndef TNODE_H +#define TNODE_H + +#define _SEARCH_PRIVATE +#include +#include + +/* + * Increases the balance of a node by one, as the result of an insertion + * in its left subtree. If the balance becomes more than 1, rotations + * are applied to restore balance. This function returns whether the + * resulting tree has increased in height. + */ +static inline bool +tnode_balance_increase(node_t **n) +{ + node_t *x, *y, *z; + + x = *n; + if (x->balance > 0) { + y = x->llink; + if (y->balance < 0) { + /* + * Left-right case. + * + * x + * / \ z + * y D / \ + * / \ --> y x + * A z /| |\ + * / \ A B C D + * B C + */ + z = y->rlink; + y->rlink = z->llink; + z->llink = y; + x->llink = z->rlink; + z->rlink = x; + *n = z; + + x->balance = z->balance > 0 ? -1 : 0; + y->balance = z->balance < 0 ? 1 : 0; + z->balance = 0; + return (false); + } else { + /* + * Left-left case. + * + * x y + * / \ / \ + * y C --> A x + * / \ / \ + * A B B C + */ + x->llink = y->rlink; + y->rlink = x; + *n = y; + + if (y->balance > 0) { + x->balance = 0; + y->balance = 0; + return (false); + } else { + x->balance = 1; + y->balance = -1; + return (true); + } + } + } else { + return (++x->balance > 0); + } +} + +/* + * Decreases the balance of a node by one, as the result of an insertion + * in its right subtree. If the balance becomes less than -1, rotations + * are applied to restore balance. This function returns whether the + * resulting tree has increased in height. + */ +static inline bool +tnode_balance_decrease(node_t **n) +{ + node_t *x, *y, *z; + + x = *n; + if (x->balance < 0) { + y = x->rlink; + if (y->balance > 0) { + /* + * Right-left case. + * + * x + * / \ z + * A y / \ + * / \ --> x y + * z D /| |\ + * / \ A B C D + * B C + */ + z = y->llink; + x->rlink = z->llink; + z->llink = x; + y->llink = z->rlink; + z->rlink = y; + *n = z; + + x->balance = z->balance < 0 ? 1 : 0; + y->balance = z->balance > 0 ? -1 : 0; + z->balance = 0; + return (false); + } else { + /* + * Right-right case. + * + * x y + * / \ / \ + * A y --> x C + * / \ / \ + * B C A B + */ + x->rlink = y->llink; + y->llink = x; + *n = y; + + if (y->balance < 0) { + x->balance = 0; + y->balance = 0; + return (false); + } else { + x->balance = -1; + y->balance = 1; + return (true); + } + } + } else { + return (--x->balance < 0); + } +} + +#endif Index: stdlib/tsearch.3 =================================================================== --- stdlib/tsearch.3 +++ stdlib/tsearch.3 @@ -27,7 +27,7 @@ .\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp .\" $FreeBSD$ .\" -.Dd June 15, 1997 +.Dd December 6, 2015 .Dt TSEARCH 3 .Os .Sh NAME @@ -50,8 +50,12 @@ .Fn tsearch , and .Fn twalk -functions manage binary search trees based on algorithms T and D -from Knuth (6.2.2). +functions manage binary search trees. +This implementation uses a balanced AVL tree, +which due to its strong theoretical limit on the height of the tree has +the advantage of calling the comparison function relatively +infrequently. +.Pp The comparison function passed in by the user has the same style of return values as .Xr strcmp 3 . Index: stdlib/tsearch.c =================================================================== --- stdlib/tsearch.c +++ stdlib/tsearch.c @@ -1,55 +1,82 @@ -/* $NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ * - * The node_t structure is for internal use only, lint doesn't grok it. + * 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. * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 -#if 0 -#if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $"); -#endif /* LIBC_SCCS and not lint */ -#endif __FBSDID("$FreeBSD$"); #define _SEARCH_PRIVATE #include +#include #include -/* find or insert datum into search tree */ +#include "tnode.h" + +static bool +tsearch_recurse(const void *key, node_t **n, + int (*compar)(const void *, const void *), void **result) +{ + int cmp; + + if (*n == NULL) { + /* Did not find a matching key. Allocate a new node. */ + *n = malloc(sizeof(**n)); + if (*n == NULL) { + *result = NULL; + return (false); + } + (*n)->key = (void *)key; + (*n)->llink = NULL; + (*n)->rlink = NULL; + (*n)->balance = 0; + *result = &(*n)->key; + return (true); + } else { + /* Use the comparison function to traverse the tree. */ + cmp = compar(key, (*n)->key); + if (cmp < 0) { + return (tsearch_recurse(key, &(*n)->llink, compar, + result) && tnode_balance_increase(n)); + } else if (cmp > 0) { + return (tsearch_recurse(key, &(*n)->rlink, compar, + result) && tnode_balance_decrease(n)); + } else { + /* Found an already existing entry with the same key. */ + *result = &(*n)->key; + return (false); + } + } +} + void * -tsearch(const void *vkey, void **vrootp, +tsearch(const void *key, void **rootp, int (*compar)(const void *, const void *)) { - node_t *q; - node_t **rootp = (node_t **)vrootp; + void *result; 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 = __DECONST(void *, vkey);/* initialize new node */ - q->llink = q->rlink = NULL; - } - return q; + return (NULL); + tsearch_recurse(key, (node_t **)rootp, compar, &result); + return (result); } Index: tests/stdlib/Makefile =================================================================== --- tests/stdlib/Makefile +++ tests/stdlib/Makefile @@ -3,6 +3,7 @@ ATF_TESTS_C+= heapsort_test ATF_TESTS_C+= mergesort_test ATF_TESTS_C+= qsort_test +ATF_TESTS_C+= tsearch_test # TODO: t_getenv_thread, t_mi_vector_hash NETBSD_ATF_TESTS_C+= abs_test Index: tests/stdlib/tsearch_test.c =================================================================== --- tests/stdlib/tsearch_test.c +++ tests/stdlib/tsearch_test.c @@ -0,0 +1,118 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 +__FBSDID("$FreeBSD$"); + +#include +#define _SEARCH_PRIVATE +#include +#include +#include + +/* Validates the integrity of an AVL tree. */ +static inline unsigned int +tnode_assert(const node_t *n) +{ + unsigned int height_left, height_right; + int balance; + + if (n == NULL) + return 0; + height_left = tnode_assert(n->llink); + height_right = tnode_assert(n->rlink); + balance = (int)height_left - (int)height_right; + ATF_CHECK(balance >= -1); + ATF_CHECK(balance <= 1); + ATF_CHECK_EQ(balance, n->balance); + return (height_left > height_right ? height_left : height_right) + 1; +} + +static int +compar(const void *a, const void *b) +{ + + return *(int *)a - *(int *)b; +} + +ATF_TC_WITHOUT_HEAD(tsearch_test); +ATF_TC_BODY(tsearch_test, tc) { +#define NKEYS 1000 + /* Create 1000 possible keys. */ + int keys[NKEYS]; + for (int i = 0; i < NKEYS; ++i) + keys[i] = i; + + /* Apply random operations on a binary tree and check the results. */ + void *root = NULL; + bool present[NKEYS] = {}; + for (int i = 0; i < NKEYS * 10; ++i) { + int key = arc4random_uniform(NKEYS); + switch (arc4random_uniform(3)) { + case 0: /* tdelete(). */ + if (present[key]) { + ATF_CHECK(tdelete(&key, &root, compar) != NULL); + present[key] = false; + } else { + ATF_CHECK_EQ(NULL, + tdelete(&key, &root, compar)); + } + break; + case 1: /* tfind(). */ + if (present[key]) { + ATF_CHECK_EQ(&keys[key], + *(int **)tfind(&key, &root, compar)); + } else { + ATF_CHECK_EQ(NULL, tfind(&key, &root, compar)); + } + break; + case 2: /* tsearch(). */ + if (present[key]) { + ATF_CHECK_EQ(&keys[key], + *(int **)tsearch(&key, &root, compar)); + } else { + ATF_CHECK_EQ(&keys[key], *(int **)tsearch( + &keys[key], &root, compar)); + present[key] = true; + } + break; + } + tnode_assert(root); + } + + /* Remove all entries from the tree. */ + for (int key = 0; key < NKEYS; ++key) + if (present[key]) + ATF_CHECK(tdelete(&key, &root, compar) != NULL); + ATF_CHECK_EQ(NULL, root); +} + +ATF_TP_ADD_TCS(tp) +{ + + ATF_TP_ADD_TC(tp, tsearch_test); + + return (atf_no_error()); +}