Index: include/search.h =================================================================== --- include/search.h +++ include/search.h @@ -46,11 +46,8 @@ #endif #if __BSD_VISIBLE -struct _ENTRY; struct hsearch_data { - struct _ENTRY *table; - size_t size; - size_t filled; + struct __hsearch *__hsearch; }; #endif Index: lib/libc/stdlib/Makefile.inc =================================================================== --- lib/libc/stdlib/Makefile.inc +++ 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 \ Index: lib/libc/stdlib/hcreate.3 =================================================================== --- lib/libc/stdlib/hcreate.3 +++ lib/libc/stdlib/hcreate.3 @@ -28,7 +28,7 @@ .\" .\" $FreeBSD$ .\" -.Dd July 21, 2014 +.Dd December 18, 2015 .Dt HCREATE 3 .Os .Sh NAME @@ -76,8 +76,8 @@ .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 @@ .Bl -tag -width Er .It Bq Er ENOMEM Insufficient memory is available. -.It Bq Er EINVAL -A table already exists. .El .Pp The Index: lib/libc/stdlib/hcreate.c =================================================================== --- lib/libc/stdlib/hcreate.c +++ 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. - * - * <> - */ - -/* - * 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 -#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 -#include -#include #include -#include -#include +#include +#include /* - * 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) +static struct hsearch_data global_hashtable; +static bool global_hashtable_initialized = false; -/* - * 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; - 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); + return (1); } -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; -} - 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; -} + ENTRY *retval; -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; - - 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); + /* Create global hash table if needed. */ + if (!global_hashtable_initialized) { + if (hcreate_r(0, &global_hashtable) == 0) + return (NULL); + global_hashtable_initialized = true; } - - if (ie != NULL) { - *itemp = &ie->ent; - return 1; - } else if (action == FIND) { - *itemp = NULL; - errno = ESRCH; - return 1; - } - - 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); } Index: lib/libc/stdlib/hcreate_r.c =================================================================== --- lib/libc/stdlib/hcreate_r.c +++ 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 +__FBSDID("$FreeBSD$"); + +#include +#include + +#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; +} Index: lib/libc/stdlib/hdestroy_r.c =================================================================== --- lib/libc/stdlib/hdestroy_r.c +++ 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 +__FBSDID("$FreeBSD$"); + +#include +#include + +#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); +} Index: lib/libc/stdlib/hsearch.h =================================================================== --- lib/libc/stdlib/hsearch.h +++ 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 + +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 Index: lib/libc/stdlib/hsearch_r.c =================================================================== --- lib/libc/stdlib/hsearch_r.c +++ 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 +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include +#include +#include + +#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); +}