Page MenuHomeFreeBSD
Files F152949442

D4412.id10818.diff
No OneTemporary
Actions

D4412.id10818.diff
View Options

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 <sys/cdefs.h>
-#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 <search.h>
+#include <stdbool.h>
#include <stdlib.h>
+#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 <assert.h>
+#include <search.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+/*
+ * 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 <sys/cdefs.h>
-#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 <search.h>
+#include <stdbool.h>
#include <stdlib.h>
-/* 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);
}

File Metadata

Mime Type
text/plain
Expires
Sun, Apr 19, 6:48 AM (9 h, 18 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31751852
Default Alt Text
D4412.id10818.diff (15 KB)

Event Timeline