Finish <search.h>.
I'm unable to find a bug, but we've had requests for this internally
once or twice (though I pointed those folks at the STL), and there's
code we build for the host or in our bootloaders that would use this,
and there's reasonable-looking FreeBSD implementation ready and waiting.
Bug: N/A
Test: ran tests
Change-Id: I6ddee4b71bea4c22ed015debd31d3eaac4fcdd35
diff --git a/libc/Android.bp b/libc/Android.bp
index 204ad19..e7a2e09 100644
--- a/libc/Android.bp
+++ b/libc/Android.bp
@@ -218,6 +218,10 @@
"upstream-freebsd/lib/libc/gen/sleep.c",
"upstream-freebsd/lib/libc/gen/usleep.c",
"upstream-freebsd/lib/libc/stdlib/getopt_long.c",
+ "upstream-freebsd/lib/libc/stdlib/hcreate.c",
+ "upstream-freebsd/lib/libc/stdlib/hcreate_r.c",
+ "upstream-freebsd/lib/libc/stdlib/hdestroy_r.c",
+ "upstream-freebsd/lib/libc/stdlib/hsearch_r.c",
"upstream-freebsd/lib/libc/stdlib/qsort.c",
"upstream-freebsd/lib/libc/stdlib/quick_exit.c",
"upstream-freebsd/lib/libc/string/wcpcpy.c",
@@ -282,6 +286,7 @@
cflags: [
"-Wno-sign-compare",
"-Wno-uninitialized",
+ "-Wno-unused-parameter",
"-include freebsd-compat.h",
],
diff --git a/libc/NOTICE b/libc/NOTICE
index 90de7ef..feea29d 100644
--- a/libc/NOTICE
+++ b/libc/NOTICE
@@ -5644,6 +5644,31 @@
-------------------------------------------------------------------
+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.
+
+-------------------------------------------------------------------
+
Copyright (c) 2017 Imagination Technologies.
All rights reserved.
diff --git a/libc/bionic/tdestroy.cpp b/libc/bionic/tdestroy.cpp
index 95c3e64..2968ff9 100644
--- a/libc/bionic/tdestroy.cpp
+++ b/libc/bionic/tdestroy.cpp
@@ -14,10 +14,15 @@
* limitations under the License.
*/
-#define _SEARCH_PRIVATE
#include <search.h>
#include <stdlib.h>
+struct node_t {
+ char* key;
+ struct node* llink;
+ struct node* rlink;
+};
+
// Destroy a tree and free all allocated resources.
// This is a GNU extension, not available from BSD.
void tdestroy(void* root, void (*destroy_func)(void*)) {
diff --git a/libc/include/search.h b/libc/include/search.h
index 0015699..5930bcd 100644
--- a/libc/include/search.h
+++ b/libc/include/search.h
@@ -13,18 +13,26 @@
#include <sys/types.h>
typedef enum {
+ FIND,
+ ENTER
+} ACTION;
+
+typedef struct entry {
+ char* key;
+ void* data;
+} ENTRY;
+
+typedef enum {
preorder,
postorder,
endorder,
leaf
} VISIT;
-#ifdef _SEARCH_PRIVATE
-typedef struct node {
- char* key;
- struct node* llink;
- struct node* rlink;
-} node_t;
+#if defined(__USE_BSD) || defined(__USE_GNU)
+struct hsearch_data {
+ struct __hsearch* __hsearch;
+};
#endif
__BEGIN_DECLS
@@ -32,6 +40,16 @@
void insque(void* __element, void* __previous) __INTRODUCED_IN(21);
void remque(void* __element) __INTRODUCED_IN(21);
+int hcreate(size_t) __INTRODUCED_IN_FUTURE;
+void hdestroy(void) __INTRODUCED_IN_FUTURE;
+ENTRY* hsearch(ENTRY, ACTION) __INTRODUCED_IN_FUTURE;
+
+#if defined(__USE_BSD) || defined(__USE_GNU)
+int hcreate_r(size_t, struct hsearch_data*) __INTRODUCED_IN_FUTURE;
+void hdestroy_r(struct hsearch_data*) __INTRODUCED_IN_FUTURE;
+int hsearch_r(ENTRY, ACTION, ENTRY**, struct hsearch_data*) __INTRODUCED_IN_FUTURE;
+#endif
+
void* lfind(const void* __key, const void* __base, size_t* __count, size_t __size, int (*__comparator)(const void*, const void*))
__INTRODUCED_IN(21);
void* lsearch(const void* __key, void* __base, size_t* __count, size_t __size, int (*__comparator)(const void*, const void*))
diff --git a/libc/libc.arm.map b/libc/libc.arm.map
index 31c2a53..5018951 100644
--- a/libc/libc.arm.map
+++ b/libc/libc.arm.map
@@ -1323,6 +1323,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/libc.arm64.map b/libc/libc.arm64.map
index 6cc6d64..4ea5896 100644
--- a/libc/libc.arm64.map
+++ b/libc/libc.arm64.map
@@ -1243,6 +1243,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/libc.map.txt b/libc/libc.map.txt
index 5cbfaeb..a0ac50a 100644
--- a/libc/libc.map.txt
+++ b/libc/libc.map.txt
@@ -1348,6 +1348,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/libc.mips.map b/libc/libc.mips.map
index 34369ba..8970549 100644
--- a/libc/libc.mips.map
+++ b/libc/libc.mips.map
@@ -1307,6 +1307,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/libc.mips64.map b/libc/libc.mips64.map
index 6cc6d64..4ea5896 100644
--- a/libc/libc.mips64.map
+++ b/libc/libc.mips64.map
@@ -1243,6 +1243,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/libc.x86.map b/libc/libc.x86.map
index 76dffa5..5439852 100644
--- a/libc/libc.x86.map
+++ b/libc/libc.x86.map
@@ -1305,6 +1305,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/libc.x86_64.map b/libc/libc.x86_64.map
index 6cc6d64..4ea5896 100644
--- a/libc/libc.x86_64.map
+++ b/libc/libc.x86_64.map
@@ -1243,6 +1243,12 @@
__freading; # future
__fwriting; # future
getlogin_r; # future
+ hcreate; # future
+ hcreate_r; # future
+ hdestroy; # future
+ hdestroy_r; # future
+ hsearch; # future
+ hsearch_r; # future
iconv; # future
iconv_close; # future
iconv_open; # future
diff --git a/libc/upstream-freebsd/lib/libc/stdlib/hcreate.c b/libc/upstream-freebsd/lib/libc/stdlib/hcreate.c
new file mode 100644
index 0000000..d512857
--- /dev/null
+++ b/libc/upstream-freebsd/lib/libc/stdlib/hcreate.c
@@ -0,0 +1,73 @@
+/*-
+ * 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: head/lib/libc/stdlib/hcreate.c 292767 2015-12-27 07:50:11Z ed $");
+
+#include <search.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+/*
+ * Thread unsafe interface: use a single process-wide hash table and
+ * forward calls to *_r() functions.
+ */
+
+static struct hsearch_data global_hashtable;
+static bool global_hashtable_initialized = false;
+
+int
+hcreate(size_t nel)
+{
+
+ return (1);
+}
+
+void
+hdestroy(void)
+{
+
+ /* Destroy global hash table if present. */
+ if (global_hashtable_initialized) {
+ hdestroy_r(&global_hashtable);
+ global_hashtable_initialized = false;
+ }
+}
+
+ENTRY *
+hsearch(ENTRY item, ACTION action)
+{
+ ENTRY *retval;
+
+ /* Create global hash table if needed. */
+ if (!global_hashtable_initialized) {
+ if (hcreate_r(0, &global_hashtable) == 0)
+ return (NULL);
+ global_hashtable_initialized = true;
+ }
+ if (hsearch_r(item, action, &retval, &global_hashtable) == 0)
+ return (NULL);
+ return (retval);
+}
diff --git a/libc/upstream-freebsd/lib/libc/stdlib/hcreate_r.c b/libc/upstream-freebsd/lib/libc/stdlib/hcreate_r.c
new file mode 100644
index 0000000..34db88e
--- /dev/null
+++ b/libc/upstream-freebsd/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: head/lib/libc/stdlib/hcreate_r.c 292767 2015-12-27 07:50:11Z ed $");
+
+#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/libc/upstream-freebsd/lib/libc/stdlib/hdestroy_r.c b/libc/upstream-freebsd/lib/libc/stdlib/hdestroy_r.c
new file mode 100644
index 0000000..76d8a42
--- /dev/null
+++ b/libc/upstream-freebsd/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: head/lib/libc/stdlib/hdestroy_r.c 292767 2015-12-27 07:50:11Z ed $");
+
+#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/libc/upstream-freebsd/lib/libc/stdlib/hsearch.h b/libc/upstream-freebsd/lib/libc/stdlib/hsearch.h
new file mode 100644
index 0000000..a0542b5
--- /dev/null
+++ b/libc/upstream-freebsd/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: head/lib/libc/stdlib/hsearch.h 292767 2015-12-27 07:50:11Z ed $
+ */
+
+#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/libc/upstream-freebsd/lib/libc/stdlib/hsearch_r.c b/libc/upstream-freebsd/lib/libc/stdlib/hsearch_r.c
new file mode 100644
index 0000000..9a859d3
--- /dev/null
+++ b/libc/upstream-freebsd/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: head/lib/libc/stdlib/hsearch_r.c 292767 2015-12-27 07:50:11Z ed $");
+
+#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);
+}