Index: include/search.h =================================================================== --- include/search.h +++ include/search.h @@ -35,8 +35,9 @@ #ifdef _SEARCH_PRIVATE typedef struct node { - char *key; + void *key; struct node *llink, *rlink; + signed char balance; } node_t; struct que_elem { Index: lib/libc/stdlib/tdelete.c =================================================================== --- lib/libc/stdlib/tdelete.c +++ lib/libc/stdlib/tdelete.c @@ -1,72 +1,116 @@ -/* $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 if ((*n)->rlink == NULL) { + /* No right child. Replace by left subtree. */ + node_t *newroot = (*n)->llink; + 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; + + result = (void *)1; + tdelete_recurse(key, (node_t **)rootp, compar, &result); + tnode_assert(*rootp); + return (result); +} Index: lib/libc/stdlib/tnode.h =================================================================== --- lib/libc/stdlib/tnode.h +++ lib/libc/stdlib/tnode.h @@ -0,0 +1,185 @@ +/*- + * 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. + */ + +#ifndef TNODE_H +#define TNODE_H + +#include +#include +#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); + } +} + +/* Validates the integrity of an AVL tree. */ +static inline unsigned int +tnode_assert(const node_t *n) +{ + +#if 0 + if (n == NULL) + return (0); + unsigned int height_left = tnode_assert(n->llink); + unsigned int height_right = tnode_assert(n->rlink); + int balance = (int)height_left - (int)height_right; + assert(balance >= -1 && balance <= 1); + assert(balance == n->balance); + return ((height_left > height_right ? height_left : height_right) + 1); +#else + return (0); +#endif +} + +#endif Index: lib/libc/stdlib/tsearch.3 =================================================================== --- lib/libc/stdlib/tsearch.3 +++ lib/libc/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: lib/libc/stdlib/tsearch.c =================================================================== --- lib/libc/stdlib/tsearch.c +++ lib/libc/stdlib/tsearch.c @@ -1,55 +1,81 @@ -/* $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; + tsearch_recurse(key, (node_t **)rootp, compar, &result); + tnode_assert(*rootp); + return (result); }