Page MenuHomeFreeBSD
Files F131702220

D4644.diff
No OneTemporary
Actions

D4644.diff
View Options

Index: head/include/search.h
===================================================================
--- head/include/search.h
+++ head/include/search.h
@@ -47,11 +47,8 @@
#endif
#if __BSD_VISIBLE
-struct _ENTRY;
struct hsearch_data {
- struct _ENTRY *table;
- size_t size;
- size_t filled;
+ struct __hsearch *__hsearch;
};
#endif
Index: head/lib/libc/stdlib/Makefile.inc
===================================================================
--- head/lib/libc/stdlib/Makefile.inc
+++ head/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: head/lib/libc/stdlib/hcreate.3
===================================================================
--- head/lib/libc/stdlib/hcreate.3
+++ head/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 @@
.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: head/lib/libc/stdlib/hcreate.c
===================================================================
--- head/lib/libc/stdlib/hcreate.c
+++ head/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;
-
- 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;
- }
+ ENTRY *retval;
- 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;
+ /* 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);
}
Index: head/lib/libc/stdlib/hcreate_r.c
===================================================================
--- head/lib/libc/stdlib/hcreate_r.c
+++ head/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;
+}
Index: head/lib/libc/stdlib/hdestroy_r.c
===================================================================
--- head/lib/libc/stdlib/hdestroy_r.c
+++ head/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);
+}
Index: head/lib/libc/stdlib/hsearch.h
===================================================================
--- head/lib/libc/stdlib/hsearch.h
+++ head/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
Index: head/lib/libc/stdlib/hsearch_r.c
===================================================================
--- head/lib/libc/stdlib/hsearch_r.c
+++ head/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);
+}

File Metadata

Mime Type
text/plain
Expires
Sat, Oct 11, 11:39 AM (19 h, 52 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
23575464
Default Alt Text
D4644.diff (19 KB)

Event Timeline