Index: head/include/search.h =================================================================== --- head/include/search.h (revision 292766) +++ head/include/search.h (revision 292767) @@ -1,83 +1,80 @@ /*- * Written by J.T. Conklin * Public domain. * * $NetBSD: search.h,v 1.16 2005/02/03 04:39:32 perry Exp $ * $FreeBSD$ */ #ifndef _SEARCH_H_ #define _SEARCH_H_ #include #include #ifndef _SIZE_T_DECLARED typedef __size_t size_t; #define _SIZE_T_DECLARED #endif typedef struct entry { char *key; void *data; } ENTRY; typedef enum { FIND, ENTER } ACTION; typedef enum { preorder, postorder, endorder, leaf } VISIT; #ifdef _SEARCH_PRIVATE typedef struct node { void *key; struct node *llink, *rlink; signed char balance; } node_t; struct que_elem { struct que_elem *next; struct que_elem *prev; }; #endif #if __BSD_VISIBLE -struct _ENTRY; struct hsearch_data { - struct _ENTRY *table; - size_t size; - size_t filled; + struct __hsearch *__hsearch; }; #endif __BEGIN_DECLS int hcreate(size_t); void hdestroy(void); ENTRY *hsearch(ENTRY, ACTION); void insque(void *, void *); void *lfind(const void *, const void *, size_t *, size_t, int (*)(const void *, const void *)); void *lsearch(const void *, void *, size_t *, size_t, int (*)(const void *, const void *)); void remque(void *); void *tdelete(const void * __restrict, void ** __restrict, int (*)(const void *, const void *)); void *tfind(const void *, void * const *, int (*)(const void *, const void *)); void *tsearch(const void *, void **, int (*)(const void *, const void *)); void twalk(const void *, void (*)(const void *, VISIT, int)); #if __BSD_VISIBLE int hcreate_r(size_t, struct hsearch_data *); void hdestroy_r(struct hsearch_data *); int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); #endif __END_DECLS #endif /* !_SEARCH_H_ */ Index: head/lib/libc/stdlib/Makefile.inc =================================================================== --- head/lib/libc/stdlib/Makefile.inc (revision 292766) +++ head/lib/libc/stdlib/Makefile.inc (revision 292767) @@ -1,52 +1,53 @@ # from @(#)Makefile.inc 8.3 (Berkeley) 2/4/95 # $FreeBSD$ # machine-independent stdlib sources .PATH: ${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib ${LIBC_SRCTOP}/stdlib 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 \ random.c reallocarray.c reallocf.c realpath.c remque.c strfmon.c \ strtoimax.c \ strtol.c strtoll.c strtoq.c strtoul.c strtonum.c strtoull.c \ strtoumax.c strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c SYM_MAPS+= ${LIBC_SRCTOP}/stdlib/Symbol.map # machine-dependent stdlib sources .sinclude "${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib/Makefile.inc" MAN+= a64l.3 abort.3 abs.3 alloca.3 atexit.3 atof.3 \ atoi.3 atol.3 at_quick_exit.3 bsearch.3 \ div.3 exit.3 getenv.3 getopt.3 getopt_long.3 getsubopt.3 \ hcreate.3 imaxabs.3 imaxdiv.3 insque.3 labs.3 ldiv.3 llabs.3 lldiv.3 \ lsearch.3 memory.3 ptsname.3 qsort.3 \ quick_exit.3 \ radixsort.3 rand.3 random.3 reallocarray.3 reallocf.3 \ realpath.3 strfmon.3 strtod.3 strtol.3 strtonum.3 strtoul.3 system.3 \ tsearch.3 MLINKS+=a64l.3 l64a.3 a64l.3 l64a_r.3 MLINKS+=atol.3 atoll.3 MLINKS+=exit.3 _Exit.3 MLINKS+=getenv.3 putenv.3 getenv.3 setenv.3 getenv.3 unsetenv.3 MLINKS+=getopt_long.3 getopt_long_only.3 MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3 MLINKS+=hcreate.3 hcreate_r.3 hcreate.3 hdestroy_r.3 hcreate.3 hsearch_r.3 MLINKS+=insque.3 remque.3 MLINKS+=lsearch.3 lfind.3 MLINKS+=ptsname.3 grantpt.3 ptsname.3 unlockpt.3 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3 MLINKS+=rand.3 rand_r.3 rand.3 srand.3 rand.3 sranddev.3 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 \ random.3 srandomdev.3 MLINKS+=radixsort.3 sradixsort.3 MLINKS+=strfmon.3 strfmon_l.3 MLINKS+=strtod.3 strtof.3 strtod.3 strtold.3 MLINKS+=strtol.3 strtoll.3 strtol.3 strtoq.3 strtol.3 strtoimax.3 MLINKS+=strtoul.3 strtoull.3 strtoul.3 strtouq.3 strtoul.3 strtoumax.3 MLINKS+=tsearch.3 tdelete.3 tsearch.3 tfind.3 tsearch.3 twalk.3 Index: head/lib/libc/stdlib/hcreate.3 =================================================================== --- head/lib/libc/stdlib/hcreate.3 (revision 292766) +++ head/lib/libc/stdlib/hcreate.3 (revision 292767) @@ -1,327 +1,325 @@ .\"- .\" Copyright (c) 1999 The NetBSD Foundation, Inc. .\" All rights reserved. .\" .\" This code is derived from software contributed to The NetBSD Foundation .\" by Klaus Klein. .\" .\" 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 NETBSD FOUNDATION, INC. 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 FOUNDATION 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$ .\" -.Dd July 21, 2014 +.Dd December 26, 2015 .Dt HCREATE 3 .Os .Sh NAME .Nm hcreate , .Nm hcreate_r , .Nm hdestroy , .Nm hdestroy_r , .Nm hsearch , .Nm hsearch_r .Nd manage hash search table .Sh LIBRARY .Lb libc .Sh SYNOPSIS .In search.h .Ft int .Fn hcreate "size_t nel" .Ft int .Fn hcreate_r "size_t nel" "struct hsearch_data *table" .Ft void .Fn hdestroy "void" .Ft void .Fn hdestroy_r "struct hsearch_data *table" .Ft ENTRY * .Fn hsearch "ENTRY item" "ACTION action" .Ft int .Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table" .Sh DESCRIPTION The .Fn hcreate , .Fn hcreate_r , .Fn hdestroy , .Fn hdestroy_r .Fn hsearch , and .Fn hsearch_r functions manage hash search tables. .Pp The .Fn hcreate function allocates sufficient space for the table, and the application should ensure it is called before .Fn hsearch is used. 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 function disposes of the search table, and may be followed by another call to .Fn hcreate . After the call to .Fn hdestroy , the data can no longer be considered accessible. The .Fn hdestroy function calls .Xr free 3 for each comparison key in the search table but not the data item associated with the key. .Pp The .Fn hsearch function is a hash-table search routine. It returns a pointer into a hash table indicating the location at which an entry can be found. The .Fa item argument is a structure of type .Vt ENTRY (defined in the .In search.h header) that contains two pointers: .Fa item.key points to the comparison key (a .Vt "char *" ) , and .Fa item.data (a .Vt "void *" ) points to any other data to be associated with that key. The comparison function used by .Fn hsearch is .Xr strcmp 3 . The .Fa action argument is a member of an enumeration type .Vt ACTION indicating the disposition of the entry if it cannot be found in the table. .Dv ENTER indicates that the .Fa item should be inserted in the table at an appropriate point. .Dv FIND indicates that no entry should be made. Unsuccessful resolution is indicated by the return of a .Dv NULL pointer. .Pp The comparison key (passed to .Fn hsearch as .Fa item.key ) must be allocated using .Xr malloc 3 if .Fa action is .Dv ENTER and .Fn hdestroy is called. .Pp The .Fn hcreate_r , .Fn hdestroy_r , and .Fn hsearch_r functions are re-entrant versions of the above functions that can operate on a table supplied by the user. The .Fn hsearch_r function returns .Dv 0 if the action is .Dv ENTER and the element cannot be created, .Dv 1 otherwise. If the element exists or can be created, it will be placed in .Fa itemp , otherwise .Fa itemp will be set to .Dv NULL . .Sh RETURN VALUES The .Fn hcreate and .Fn hcreate_r functions return 0 if the table creation failed and the global variable .Va errno is set to indicate the error; otherwise, a non-zero value is returned. .Pp The .Fn hdestroy and .Fn hdestroy_r functions return no value. .Pp The .Fn hsearch and .Fn hsearch_r functions return a .Dv NULL pointer if either the .Fa action is .Dv FIND and the .Fa item could not be found or the .Fa action is .Dv ENTER and the table is full. .Sh EXAMPLES The following example reads in strings followed by two numbers and stores them in a hash table, discarding duplicates. It then reads in strings and finds the matching entry in the hash table and prints it out. .Bd -literal #include #include #include #include struct info { /* This is the info stored in the table */ int age, room; /* other than the key. */ }; #define NUM_EMPL 5000 /* # of elements in search table. */ int main(void) { char str[BUFSIZ]; /* Space to read string */ struct info info_space[NUM_EMPL]; /* Space to store employee info. */ struct info *info_ptr = info_space; /* Next space in info_space. */ ENTRY item; ENTRY *found_item; /* Name to look for in table. */ char name_to_find[30]; int i = 0; /* Create table; no error checking is performed. */ (void) hcreate(NUM_EMPL); while (scanf("%s%d%d", str, &info_ptr->age, &info_ptr->room) != EOF && i++ < NUM_EMPL) { /* Put information in structure, and structure in item. */ item.key = strdup(str); item.data = info_ptr; info_ptr++; /* Put item into table. */ (void) hsearch(item, ENTER); } /* Access table. */ item.key = name_to_find; while (scanf("%s", item.key) != EOF) { if ((found_item = hsearch(item, FIND)) != NULL) { /* If item is in the table. */ (void)printf("found %s, age = %d, room = %d\en", found_item->key, ((struct info *)found_item->data)->age, ((struct info *)found_item->data)->room); } else (void)printf("no such employee %s\en", name_to_find); } hdestroy(); return 0; } .Ed .Sh ERRORS The .Fn hcreate .Fn hcreate_r , .Fn hsearch and .Fn hsearch_r 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 .Fn hsearch and .Fn hsearch_r functions will also fail if the action is .Dv SEARCH and the element is not found: .Bl -tag -width Er .It Bq Er ESRCH The .Fa item given is not found. .El .Sh SEE ALSO .Xr bsearch 3 , .Xr lsearch 3 , .Xr malloc 3 , .Xr strcmp 3 , .Xr tsearch 3 .Sh STANDARDS The .Fn hcreate , .Fn hdestroy , and .Fn hsearch functions conform to .St -xpg4.2 . .Sh HISTORY The .Fn hcreate , .Fn hdestroy , and .Fn hsearch functions first appeared in .At V . The .Fn hcreate_r , .Fn hdestroy_r and .Fn hsearch_r functions are .Tn GNU extensions. .Sh BUGS The original, .Pf non- Tn GNU interface permits the use of only one hash table at a time. Index: head/lib/libc/stdlib/hcreate.c =================================================================== --- head/lib/libc/stdlib/hcreate.c (revision 292766) +++ head/lib/libc/stdlib/hcreate.c (revision 292767) @@ -1,218 +1,73 @@ -/* $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: * 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. - * 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); } Property changes on: head/lib/libc/stdlib/hcreate.c ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property Index: head/lib/libc/stdlib/hcreate_r.c =================================================================== --- head/lib/libc/stdlib/hcreate_r.c (nonexistent) +++ head/lib/libc/stdlib/hcreate_r.c (revision 292767) @@ -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; +} Property changes on: head/lib/libc/stdlib/hcreate_r.c ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property Index: head/lib/libc/stdlib/hdestroy_r.c =================================================================== --- head/lib/libc/stdlib/hdestroy_r.c (nonexistent) +++ head/lib/libc/stdlib/hdestroy_r.c (revision 292767) @@ -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); +} Property changes on: head/lib/libc/stdlib/hdestroy_r.c ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property Index: head/lib/libc/stdlib/hsearch.h =================================================================== --- head/lib/libc/stdlib/hsearch.h (nonexistent) +++ head/lib/libc/stdlib/hsearch.h (revision 292767) @@ -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 Property changes on: head/lib/libc/stdlib/hsearch.h ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property Index: head/lib/libc/stdlib/hsearch_r.c =================================================================== --- head/lib/libc/stdlib/hsearch_r.c (nonexistent) +++ head/lib/libc/stdlib/hsearch_r.c (revision 292767) @@ -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); +} Property changes on: head/lib/libc/stdlib/hsearch_r.c ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Added: svn:keywords ## -0,0 +1 ## +FreeBSD=%H \ No newline at end of property Added: svn:mime-type ## -0,0 +1 ## +text/plain \ No newline at end of property