11 files changed, 808 insertions, 271 deletions

diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index 7cee03a..3c6ba17 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -6,7 +6,8 @@
 
 MISRCS+=_Exit.c a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
 	bsearch.c div.c exit.c getenv.c getopt.c getopt_long.c \
-	getsubopt.c hcreate.c heapsort.c heapsort_b.c imaxabs.c imaxdiv.c \
+	getsubopt.c hcreate.c hcreate_r.c hdestroy_r.c heapsort.c heapsort_b.c \
+	hsearch_r.c imaxabs.c imaxdiv.c \
 	insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c \
 	merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c quick_exit.c \
 	radixsort.c rand.c \
diff --git a/lib/libc/stdlib/hcreate.3 b/lib/libc/stdlib/hcreate.3
index 2161f92..5709157 100644
--- a/lib/libc/stdlib/hcreate.3
+++ b/lib/libc/stdlib/hcreate.3
@@ -28,7 +28,7 @@
 .\"
 .\" $FreeBSD$
 .\"
-.Dd July 21, 2014
+.Dd December 26, 2015
 .Dt HCREATE 3
 .Os
 .Sh NAME
@@ -76,8 +76,8 @@ The
 .Fa nel
 argument is an estimate of the maximum
 number of entries that the table should contain.
-This number may be adjusted upward by the
-algorithm in order to obtain certain mathematically favorable circumstances.
+As this implementation resizes the hash table dynamically,
+this argument is ignored.
 .Pp
 The
 .Fn hdestroy
@@ -274,8 +274,6 @@ functions will fail if:
 .Bl -tag -width Er
 .It Bq Er ENOMEM
 Insufficient memory is available.
-.It Bq Er EINVAL
-A table already exists.
 .El
 .Pp
 The
diff --git a/lib/libc/stdlib/hcreate.c b/lib/libc/stdlib/hcreate.c
index b3be9b4..2d5d943 100644
--- a/lib/libc/stdlib/hcreate.c
+++ b/lib/libc/stdlib/hcreate.c
@@ -1,9 +1,6 @@
-/* $NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 christos Exp $ */
-
-/*
- * Copyright (c) 2001 Christopher G. Demetriou
- * All rights reserved.
- * 
+/*-
+ * 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:
@@ -12,207 +9,65 @@
  * 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. The name of the author may not be used to endorse or promote products
- *    derived from this software without specific prior written permission.
- * 
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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.
- * 
- * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>>
- */
-
-/*
- * hcreate() / hsearch() / hdestroy()
  *
- * SysV/XPG4 hash table functions.
- *
- * Implementation done based on NetBSD manual page and Solaris manual page,
- * plus my own personal experience about how they're supposed to work.
- *
- * I tried to look at Knuth (as cited by the Solaris manual page), but
- * nobody had a copy in the office, so...
+ * 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: hcreate.c,v 1.8 2011/09/17 16:54:39 christos Exp $");
-#endif /* LIBC_SCCS and not lint */
-#endif
 __FBSDID("$FreeBSD$");
 
-#include <sys/types.h>
-#include <sys/queue.h>
-#include <errno.h>
 #include <search.h>
-#include <stdlib.h>
-#include <string.h>
+#include <stdbool.h>
+#include <stddef.h>
 
 /*
- * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit
- * ptr machine) without adjusting MAX_BUCKETS_LG2 below.
+ * Thread unsafe interface: use a single process-wide hash table and
+ * forward calls to *_r() functions.
  */
-struct internal_entry {
-	SLIST_ENTRY(internal_entry) link;
-	ENTRY ent;
-};
-SLIST_HEAD(internal_head, internal_entry);
-
-#define	MIN_BUCKETS_LG2	4
-#define	MIN_BUCKETS	(1 << MIN_BUCKETS_LG2)
 
-/*
- * max * sizeof internal_entry must fit into size_t.
- * assumes internal_entry is <= 32 (2^5) bytes.
- */
-#define	MAX_BUCKETS_LG2	(sizeof (size_t) * 8 - 1 - 5)
-#define	MAX_BUCKETS	((size_t)1 << MAX_BUCKETS_LG2)
-
-/* Default hash function, from db/hash/hash_func.c */
-extern u_int32_t (*__default_hash)(const void *, size_t);
-
-static struct hsearch_data htable;
+static struct hsearch_data global_hashtable;
+static bool global_hashtable_initialized = false;
 
 int
 hcreate(size_t nel)
 {
 
-	/* Make sure this is not called when a table already exists. */
-	if (htable.table != NULL) {
-		errno = EINVAL;
-		return 0;
-	}
-	return hcreate_r(nel, &htable);
-}
-
-int
-hcreate_r(size_t nel, struct hsearch_data *head)
-{
-	struct internal_head *table;
-	size_t idx;
-	unsigned int p2;
-	void *p;
-
-	/* If nel is too small, make it min sized. */
-	if (nel < MIN_BUCKETS)
-		nel = MIN_BUCKETS;
-
-	/* If it is too large, cap it. */
-	if (nel > MAX_BUCKETS)
-		nel = MAX_BUCKETS;
-
-	/* If it is not a power of two in size, round up. */
-	if ((nel & (nel - 1)) != 0) {
-		for (p2 = 0; nel != 0; p2++)
-			nel >>= 1;
-		nel = 1 << p2;
-	}
-	
-	/* Allocate the table. */
-	head->size = nel;
-	head->filled = 0;
-	p = malloc(nel * sizeof table[0]);
-	if (p == NULL) {
-		errno = ENOMEM;
-		return 0;
-	}
-	head->table = p;
-	table = p;
-
-	/* Initialize it. */
-	for (idx = 0; idx < nel; idx++)
-		SLIST_INIT(&table[idx]);
-
-	return 1;
+	return (1);
 }
 
 void
 hdestroy(void)
 {
-	hdestroy_r(&htable);
-}
-
-void
-hdestroy_r(struct hsearch_data *head)
-{
-	struct internal_entry *ie;
-	size_t idx;
-	void *p;
-	struct internal_head *table;
-
-	if (head == NULL)
-		return;
-
-	p = head->table;
-	head->table = NULL;
-	table = p;
 
-	for (idx = 0; idx < head->size; idx++) {
-		while (!SLIST_EMPTY(&table[idx])) {
-			ie = SLIST_FIRST(&table[idx]);
-			SLIST_REMOVE_HEAD(&table[idx], link);
-			free(ie);
-		}
+	/* Destroy global hash table if present. */
+	if (global_hashtable_initialized) {
+		hdestroy_r(&global_hashtable);
+		global_hashtable_initialized = false;
 	}
-	free(table);
 }
 
 ENTRY *
 hsearch(ENTRY item, ACTION action)
 {
-	ENTRY *ep;
-	(void)hsearch_r(item, action, &ep, &htable);
-	return ep;
-}
-
-int
-hsearch_r(ENTRY item, ACTION action, ENTRY **itemp, struct hsearch_data *head)
-{
-	struct internal_head *table, *chain;
-	struct internal_entry *ie;
-	uint32_t hashval;
-	size_t len;
-	void *p;
-
-	p = head->table;
-	table = p;
+	ENTRY *retval;
 
-	len = strlen(item.key);
-	hashval = (*__default_hash)(item.key, len);
-
-	chain = &table[hashval & (head->size - 1)];
-	ie = SLIST_FIRST(chain);
-	while (ie != NULL) {
-		if (strcmp(ie->ent.key, item.key) == 0)
-			break;
-		ie = SLIST_NEXT(ie, link);
-	}
-
-	if (ie != NULL) {
-		*itemp = &ie->ent;
-		return 1;
-	} else if (action == FIND) {
-		*itemp = NULL;
-		errno = ESRCH;
-		return 1;
+	/* Create global hash table if needed. */
+	if (!global_hashtable_initialized) {
+		if (hcreate_r(0, &global_hashtable) == 0)
+			return (NULL);
+		global_hashtable_initialized = true;
 	}
-
-	ie = malloc(sizeof *ie);
-	if (ie == NULL)
-		return 0;
-	ie->ent.key = item.key;
-	ie->ent.data = item.data;
-
-	SLIST_INSERT_HEAD(chain, ie, link);
-	*itemp = &ie->ent;
-	head->filled++;
-	return 1;
+	if (hsearch_r(item, action, &retval, &global_hashtable) == 0)
+		return (NULL);
+	return (retval);
 }
diff --git a/lib/libc/stdlib/hcreate_r.c b/lib/libc/stdlib/hcreate_r.c
new file mode 100644
index 0000000..83e322a
--- /dev/null
+++ b/lib/libc/stdlib/hcreate_r.c
@@ -0,0 +1,63 @@
+/*-
+ * 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 <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <search.h>
+#include <stdlib.h>
+
+#include "hsearch.h"
+
+int
+hcreate_r(size_t nel, struct hsearch_data *htab)
+{
+	struct __hsearch *hsearch;
+
+	/*
+	 * Allocate a hash table object. Ignore the provided hint and start
+	 * off with a table of sixteen entries. In most cases this hint is
+	 * just a wild guess. Resizing the table dynamically if the use
+	 * increases a threshold does not affect the worst-case running time.
+	 */
+	hsearch = malloc(sizeof(*hsearch));
+	if (hsearch == NULL)
+		return 0;
+	hsearch->entries = calloc(16, sizeof(ENTRY));
+	if (hsearch->entries == NULL) {
+		free(hsearch);
+		return 0;
+	}
+
+	/*
+	 * Pick a random initialization for the FNV-1a hashing. This makes it
+	 * hard to come up with a fixed set of keys to force hash collisions.
+	 */
+	arc4random_buf(&hsearch->offset_basis, sizeof(hsearch->offset_basis));
+	hsearch->index_mask = 0xf;
+	hsearch->entries_used = 0;
+	htab->__hsearch = hsearch;
+	return 1;
+}
diff --git a/lib/libc/stdlib/hdestroy_r.c b/lib/libc/stdlib/hdestroy_r.c
new file mode 100644
index 0000000..890bd085
--- /dev/null
+++ b/lib/libc/stdlib/hdestroy_r.c
@@ -0,0 +1,43 @@
+/*-
+ * 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 <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <search.h>
+#include <stdlib.h>
+
+#include "hsearch.h"
+
+void
+hdestroy_r(struct hsearch_data *htab)
+{
+	struct __hsearch *hsearch;
+
+	/* Free hash table object and its entries. */
+	hsearch = htab->__hsearch;
+	free(hsearch->entries);
+	free(hsearch);
+}
diff --git a/lib/libc/stdlib/hsearch.h b/lib/libc/stdlib/hsearch.h
new file mode 100644
index 0000000..649933d
--- /dev/null
+++ b/lib/libc/stdlib/hsearch.h
@@ -0,0 +1,40 @@
+/*-
+ * 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 HSEARCH_H
+#define HSEARCH_H
+
+#include <search.h>
+
+struct __hsearch {
+	size_t offset_basis;	/* Initial value for FNV-1a hashing. */
+	size_t index_mask;	/* Bitmask for indexing the table. */
+	size_t entries_used;	/* Number of entries currently used. */
+	ENTRY *entries;		/* Hash table entries. */
+};
+
+#endif
diff --git a/lib/libc/stdlib/hsearch_r.c b/lib/libc/stdlib/hsearch_r.c
new file mode 100644
index 0000000..2fb5991
--- /dev/null
+++ b/lib/libc/stdlib/hsearch_r.c
@@ -0,0 +1,150 @@
+/*-
+ * 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 <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <errno.h>
+#include <limits.h>
+#include <search.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "hsearch.h"
+
+/*
+ * Look up an unused entry in the hash table for a given hash. For this
+ * implementation we use quadratic probing. Quadratic probing has the
+ * advantage of preventing primary clustering.
+ */
+static ENTRY *
+hsearch_lookup_free(struct __hsearch *hsearch, size_t hash)
+{
+	size_t index, i;
+
+	for (index = hash, i = 0;; index += ++i) {
+		ENTRY *entry = &hsearch->entries[index & hsearch->index_mask];
+		if (entry->key == NULL)
+			return (entry);
+	}
+}
+
+/*
+ * Computes an FNV-1a hash of the key. Depending on the pointer size, this
+ * either uses the 32- or 64-bit FNV prime.
+ */
+static size_t
+hsearch_hash(size_t offset_basis, const char *str)
+{
+	size_t hash;
+
+	hash = offset_basis;
+	while (*str != '\0') {
+		hash ^= (uint8_t)*str++;
+		if (sizeof(size_t) * CHAR_BIT <= 32)
+			hash *= UINT32_C(16777619);
+		else
+			hash *= UINT64_C(1099511628211);
+	}
+	return (hash);
+}
+
+int
+hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
+{
+	struct __hsearch *hsearch;
+	ENTRY *entry, *old_entries, *new_entries;
+	size_t hash, index, i, old_hash, old_count, new_count;
+
+	hsearch = htab->__hsearch;
+	hash = hsearch_hash(hsearch->offset_basis, item.key);
+
+	/*
+	 * Search the hash table for an existing entry for this key.
+	 * Stop searching if we run into an unused hash table entry.
+	 */
+	for (index = hash, i = 0;; index += ++i) {
+		entry = &hsearch->entries[index & hsearch->index_mask];
+		if (entry->key == NULL)
+			break;
+		if (strcmp(entry->key, item.key) == 0) {
+			*retval = entry;
+			return (1);
+		}
+	}
+
+	/* Only perform the insertion if action is set to ENTER. */
+	if (action == FIND) {
+		errno = ESRCH;
+		return (0);
+	}
+
+	if (hsearch->entries_used * 2 >= hsearch->index_mask) {
+		/* Preserve the old hash table entries. */
+		old_count = hsearch->index_mask + 1;
+		old_entries = hsearch->entries;
+
+		/*
+		 * Allocate and install a new table if insertion would
+		 * yield a hash table that is more than 50% used. By
+		 * using 50% as a threshold, a lookup will only take up
+		 * to two steps on average.
+		 */
+		new_count = (hsearch->index_mask + 1) * 2;
+		new_entries = calloc(new_count, sizeof(ENTRY));
+		if (new_entries == NULL)
+			return (0);
+		hsearch->entries = new_entries;
+		hsearch->index_mask = new_count - 1;
+
+		/* Copy over the entries from the old table to the new table. */
+		for (i = 0; i < old_count; ++i) {
+			entry = &old_entries[i];
+			if (entry->key != NULL) {
+				old_hash = hsearch_hash(hsearch->offset_basis,
+				    entry->key);
+				*hsearch_lookup_free(hsearch, old_hash) =
+				    *entry;
+			}
+		}
+
+		/* Destroy the old hash table entries. */
+		free(old_entries);
+
+		/*
+		 * Perform a new lookup for a free table entry, so that
+		 * we insert the entry into the new hash table.
+		 */
+		hsearch = htab->__hsearch;
+		entry = hsearch_lookup_free(hsearch, hash);
+	}
+
+	/* Insert the new entry into the hash table. */
+	*entry = item;
+	++hsearch->entries_used;
+	*retval = entry;
+	return (1);
+}
diff --git a/lib/libc/stdlib/tdelete.c b/lib/libc/stdlib/tdelete.c
index bef187e..7799f35 100644
--- a/lib/libc/stdlib/tdelete.c
+++ b/lib/libc/stdlib/tdelete.c
@@ -1,72 +1,213 @@
-/*	$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
+#define	_SEARCH_PRIVATE
 #include <search.h>
+#include <stdbool.h>
 #include <stdlib.h>
 
+#include "tsearch_path.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
- */
+ * Makes a step to the left along the binary search tree. This step is
+ * also saved, so it can be replayed while rebalancing.
+*/
+#define	GO_LEFT() do {							\
+	if ((*leaf)->balance == 0 ||					\
+	    ((*leaf)->balance < 0 && (*leaf)->rlink->balance == 0)) {	\
+		/*							\
+		 * If we reach a node that is balanced, or has a child	\
+		 * in the opposite direction that is balanced, we know	\
+		 * that we won't need to perform any rotations above	\
+		 * this point. In this case rotations are always	\
+		 * capable of keeping the subtree in balance. Make	\
+		 * this the base node and reset the path.		\
+		 */							\
+		base = leaf;						\
+		path_init(&path);					\
+	}								\
+	path_taking_left(&path);					\
+	leaf = &(*leaf)->llink;						\
+} while (0)
+
+/* Makes a step to the right along the binary search tree. */
+#define	GO_RIGHT() do {							\
+	if ((*leaf)->balance == 0 ||					\
+	    ((*leaf)->balance > 0 && (*leaf)->llink->balance == 0)) {	\
+		base = leaf;						\
+		path_init(&path);					\
+	}								\
+	result = &(*leaf)->key;						\
+	path_taking_right(&path);					\
+	leaf = &(*leaf)->rlink;						\
+} while (0)
+
 void *
-tdelete(const void * __restrict vkey, void ** __restrict vrootp,
+tdelete(const void *restrict key, void **restrict rootp,
     int (*compar)(const void *, const void *))
 {
-	node_t **rootp = (node_t **)vrootp;
-	node_t *p, *q, *r;
+	struct path path;
+	node_t *root, **base, **leaf, *old, **n, *x, *y, *z;
+	void *result;
 	int cmp;
 
-	if (rootp == NULL || (p = *rootp) == NULL)
-		return NULL;
+	/* POSIX requires that tdelete() returns NULL if rootp is NULL. */
+	if (rootp == NULL)
+		return (NULL);
+	root = *rootp;
+
+	/*
+	 * Find the leaf that needs to be removed. Return if we cannot
+	 * find an existing entry. Keep track of the path that is taken
+	 * to get to the node, as we will need it to adjust the
+	 * balances.
+	 */
+	result = (void *)1;
+	path_init(&path);
+	base = &root;
+	leaf = &root;
+	for (;;) {
+		if (*leaf == NULL)
+			return (NULL);
+		cmp = compar(key, (*leaf)->key);
+		if (cmp < 0) {
+			result = &(*leaf)->key;
+			GO_LEFT();
+		} else if (cmp > 0) {
+			result = &(*leaf)->key;
+			GO_RIGHT();
+		} else {
+			break;
+		}
+	}
 
-	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 */
+	/* Found a matching key in the tree. Remove the node. */
+	if ((*leaf)->llink == NULL) {
+		/* Node has no left children. Replace by its right subtree. */
+		old = *leaf;
+		*leaf = old->rlink;
+		free(old);
+	} else {
+		/*
+		 * Node has left children. Replace this node's key by
+		 * its predecessor's and remove that node instead.
+		 */
+		void **keyp = &(*leaf)->key;
+		GO_LEFT();
+		while ((*leaf)->rlink != NULL)
+			GO_RIGHT();
+		old = *leaf;
+		*keyp = old->key;
+		*leaf = old->llink;
+		free(old);
 	}
-	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;
+
+	/*
+	 * Walk along the same path a second time and adjust the
+	 * balances. Though this code looks similar to the rebalancing
+	 * performed in tsearch(), it is not identical. We now also need
+	 * to consider the case of outward imbalance in the right-right
+	 * and left-left case that only exists when deleting. Hence the
+	 * duplication of code.
+	 */
+	for (n = base; n != leaf;) {
+		if (path_took_left(&path)) {
+			x = *n;
+			if (x->balance < 0) {
+				y = x->rlink;
+				if (y->balance > 0) {
+					/* Right-left case. */
+					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;
+				} else {
+					/* Right-right case. */
+					x->rlink = y->llink;
+					y->llink = x;
+					*n = y;
+
+					if (y->balance < 0) {
+						x->balance = 0;
+						y->balance = 0;
+					} else {
+						x->balance = -1;
+						y->balance = 1;
+					}
+				}
+			} else {
+				--x->balance;
+			}
+			n = &x->llink;
+		} else {
+			x = *n;
+			if (x->balance > 0) {
+				y = x->llink;
+				if (y->balance < 0) {
+					/* Left-right case. */
+					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;
+				} else {
+					/* Left-left case. */
+					x->llink = y->rlink;
+					y->rlink = x;
+					*n = y;
+
+					if (y->balance > 0) {
+						x->balance = 0;
+						y->balance = 0;
+					} else {
+						x->balance = 1;
+						y->balance = -1;
+					}
+				}
+			} else {
+				++x->balance;
+			}
+			n = &x->rlink;
 		}
 	}
-	if (p != *rootp)
-		free(*rootp);			/* D4: Free node */
-	*rootp = q;				/* link parent to new node */
-	return p;
+
+	/* Return the parent of the old entry. */
+	*rootp = root;
+	return (result);
 }
diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3
index 7a204d0..2205f7e 100644
--- a/lib/libc/stdlib/tsearch.3
+++ b/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 @@ The
 .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 .
diff --git a/lib/libc/stdlib/tsearch.c b/lib/libc/stdlib/tsearch.c
index 16bbf7c..b96a275 100644
--- a/lib/libc/stdlib/tsearch.c
+++ b/lib/libc/stdlib/tsearch.c
@@ -1,55 +1,200 @@
-/*	$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.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
+/*-
+ * Copyright (c) 2015 Nuxi, https://nuxi.nl/
  *
- * Written by reading the System V Interface Definition, not the code.
+ * 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.
  *
- * 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
+#define	_SEARCH_PRIVATE
 #include <search.h>
 #include <stdlib.h>
 
-/* find or insert datum into search tree */
+#include "tsearch_path.h"
+
 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;
+	struct path path;
+	node_t *root, **base, **leaf, *result, *n, *x, *y, *z;
+	int cmp;
 
+	/* POSIX requires that tsearch() returns NULL if rootp is NULL. */
 	if (rootp == NULL)
-		return NULL;
+	return (NULL);
+		root = *rootp;
 
-	while (*rootp != NULL) {	/* Knuth's T1: */
-		int r;
+	/*
+	 * Find the leaf where the new key needs to be inserted. Return
+	 * if we've found an existing entry. Keep track of the path that
+	 * is taken to get to the node, as we will need it to adjust the
+	 * balances.
+	*/
+	path_init(&path);
+	base = &root;
+	leaf = &root;
+	while (*leaf != NULL) {
+		if ((*leaf)->balance != 0) {
+			/*
+			 * If we reach a node that has a non-zero
+			 * balance on the way, we know that we won't
+			 * need to perform any rotations above this
+			 * point. In this case rotations are always
+			 * capable of keeping the subtree in balance.
+			 * Make this the base node and reset the path.
+			 */
+			base = leaf;
+			path_init(&path);
+		}
+		cmp = compar(key, (*leaf)->key);
+		if (cmp < 0) {
+			path_taking_left(&path);
+			leaf = &(*leaf)->llink;
+		} else if (cmp > 0) {
+			path_taking_right(&path);
+			leaf = &(*leaf)->rlink;
+		} else {
+			return (&(*leaf)->key);
+		}
+	}
 
-		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
-			return *rootp;		/* we found it! */
+	/* Did not find a matching key in the tree. Insert a new node. */
+	result = *leaf = malloc(sizeof(**leaf));
+	if (result == NULL)
+		return (NULL);
+	result->key = (void *)key;
+	result->llink = NULL;
+	result->rlink = NULL;
+	result->balance = 0;
 
-		rootp = (r < 0) ?
-		    &(*rootp)->llink :		/* T3: follow left branch */
-		    &(*rootp)->rlink;		/* T4: follow right branch */
+	/*
+	 * Walk along the same path a second time and adjust the
+	 * balances. Except for the first node, all of these nodes must
+	 * have a balance of zero, meaning that these nodes will not get
+	 * out of balance.
+	*/
+	for (n = *base; n != *leaf;) {
+		if (path_took_left(&path)) {
+			n->balance += 1;
+			n = n->llink;
+		} else {
+			n->balance -= 1;
+			n = n->rlink;
+		}
 	}
 
-	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;
+	/*
+	 * Adjusting the balances may have pushed the balance of the
+	 * base node out of range. Perform a rotation to bring the
+	 * balance back in range.
+	 */
+	x = *base;
+	if (x->balance > 1) {
+		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;
+			*base = z;
+
+			x->balance = z->balance > 0 ? -1 : 0;
+			y->balance = z->balance < 0 ? 1 : 0;
+			z->balance = 0;
+		} else {
+			/*
+			 * Left-left case.
+			 *
+			 *        x           y
+			 *       / \         / \
+			 *      y   C  -->  A   x
+			 *     / \             / \
+			 *    A   B           B   C
+			 */
+			x->llink = y->rlink;
+			y->rlink = x;
+			*base = y;
+
+			x->balance = 0;
+			y->balance = 0;
+		}
+	} else if (x->balance < -1) {
+		y = x->rlink;
+		if (y->balance > 0) {
+			/*
+			 * Right-left case.
+			 *
+			 *       x
+			 *      / \              z
+			 *     A   y            / \
+			 *        / \   -->    x   y
+			 *       z   D        /|   |\
+			 *      / \          A B   C D
+			 *     B   C
+			 */
+			node_t *z = y->llink;
+			x->rlink = z->llink;
+			z->llink = x;
+			y->llink = z->rlink;
+			z->rlink = y;
+			*base = z;
+
+			x->balance = z->balance < 0 ? 1 : 0;
+			y->balance = z->balance > 0 ? -1 : 0;
+			z->balance = 0;
+		} else {
+			/*
+			 * Right-right case.
+			 *
+			 *       x               y
+			 *      / \             / \
+			 *     A   y    -->    x   C
+			 *        / \         / \
+			 *       B   C       A   B
+			 */
+			x->rlink = y->llink;
+			y->llink = x;
+			*base = y;
+
+			x->balance = 0;
+			y->balance = 0;
+		}
 	}
-	return q;
+
+	/* Return the new entry. */
+	*rootp = root;
+	return (&result->key);
 }
diff --git a/lib/libc/stdlib/tsearch_path.h b/lib/libc/stdlib/tsearch_path.h
new file mode 100644
index 0000000..934c91f
--- /dev/null
+++ b/lib/libc/stdlib/tsearch_path.h
@@ -0,0 +1,97 @@
+/*-
+ * 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 TSEARCH_PATH_H
+#define	TSEARCH_PATH_H
+
+#include <limits.h>
+#include <stdbool.h>
+#include <stdint.h>
+
+/*
+ * Bookkeeping for storing a path in a balanced binary search tree from
+ * the root to a leaf node.
+ *
+ * For an AVL tree we know that its maximum height of a tree is bounded
+ * by approximately 1.44 * log2(n) - 0.328. Given that the number of
+ * entries of the tree is constrained by the size of the address space,
+ * two uintptr_t's provide sufficient space to store the path from the
+ * root to any leaf.
+ */
+struct path {
+	uintptr_t steps[2];
+	unsigned int nsteps;
+};
+
+/* Initializes the path structure with a zero-length path. */
+static inline void
+path_init(struct path *p)
+{
+
+	p->nsteps = 0;
+}
+
+#define	STEPS_BIT (sizeof(uintptr_t) * CHAR_BIT)
+
+/* Pushes a step to the left to the end of the path. */
+static inline void
+path_taking_left(struct path *p)
+{
+
+	p->steps[p->nsteps / STEPS_BIT] |=
+	    (uintptr_t)1 << (p->nsteps % STEPS_BIT);
+	++p->nsteps;
+}
+
+/* Pushes a step to the right to the end of the path. */
+static inline void
+path_taking_right(struct path *p)
+{
+
+	p->steps[p->nsteps / STEPS_BIT] &=
+	    ~((uintptr_t)1 << (p->nsteps % STEPS_BIT));
+	++p->nsteps;
+}
+
+/*
+ * Pops the first step from the path and returns whether it was a step
+ * to the left.
+ */
+static inline bool
+path_took_left(struct path *p)
+{
+	bool result;
+
+	result = p->steps[0] & 0x1;
+	p->steps[0] = (p->steps[0] >> 1) | (p->steps[1] << (STEPS_BIT - 1));
+	p->steps[1] >>= 1;
+	return (result);
+}
+
+#undef STEPS_BIT
+
+#endif