Download raw body.
Diff: add reantrant version for hcreate(3)
On Fri, Jan 16, 2026 at 05:26:17PM +0100, Timo Mirau wrote:
> I created a reentrant version of hcreate(3), that is hcreate_r(3). The
> function is now able to use mulitple hashtables at the same time.
> Therefore I changed the header-file and manpage. Also I adapted the
> regression test in /regress/lib/libc/hsearch.
>
> I've stayed closely to the code from NetBSD, FreeBSD and Linux.
>
> Please test the diff! I'm looking forward to comments.
The diff looks good and straight forward to me. I also tested it with
the hsearch(3) users usr.bin/bc, usr.bin/rsync and usr.bin/fstat.
ok jan@
> Index: include/search.h
> ===================================================================
> RCS file: /cvs/src/include/search.h,v
> diff -u -p -u -r1.10 search.h
> --- include/search.h 18 Jul 2014 04:16:09 -0000 1.10
> +++ include/search.h 16 Jan 2026 08:20:59 -0000
> @@ -10,6 +10,7 @@
> #define _SEARCH_H_
>
> #include <sys/cdefs.h>
> +#include <sys/queue.h>
> #include <machine/_types.h>
>
> #ifndef _SIZE_T_DEFINED_
> @@ -22,6 +23,11 @@ typedef struct entry {
> void *data;
> } ENTRY;
>
> +struct hsearch_data {
> + struct internal_head *htable;
> + size_t htablesize;
> +};
> +
> typedef enum {
> FIND, ENTER
> } ACTION;
> @@ -37,6 +43,10 @@ __BEGIN_DECLS
> int hcreate(size_t);
> void hdestroy(void);
> ENTRY *hsearch(ENTRY, ACTION);
> +
> +int hcreate_r(size_t, struct hsearch_data *);
> +void hdestroy_r(struct hsearch_data *);
> +int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
>
> void *lfind(const void *, const void *, size_t *, size_t,
> int (*)(const void *, const void *));
> Index: lib/libc/Symbols.list
> ===================================================================
> RCS file: /cvs/src/lib/libc/Symbols.list,v
> diff -u -p -u -r1.95 Symbols.list
> --- lib/libc/Symbols.list 24 Oct 2025 11:30:06 -0000 1.95
> +++ lib/libc/Symbols.list 9 Jan 2026 14:13:59 -0000
> @@ -1530,9 +1530,12 @@ getopt_long_only
> getsubopt
> grantpt
> hcreate
> +hcreate_r
> hdestroy
> +hdestroy_r
> heapsort
> hsearch
> +hsearch_r
> icdb_new
> icdb_open
> icdb_lookup
> Index: lib/libc/stdlib/hcreate.3
> ===================================================================
> RCS file: /cvs/src/lib/libc/stdlib/hcreate.3,v
> diff -u -p -u -r1.8 hcreate.3
> --- lib/libc/stdlib/hcreate.3 30 Jan 2018 11:37:58 -0000 1.8
> +++ lib/libc/stdlib/hcreate.3 16 Jan 2026 15:52:36 -0000
> @@ -40,10 +40,16 @@
> .In search.h
> .Ft int
> .Fn hcreate "size_t nel"
> +.Ft int
> +.Fn hcreate_r "size_t nel" "struct hsearch_data *htab"
> .Ft void
> .Fn hdestroy "void"
> +.Ft void
> +.Fn hdestroy_r "struct hsearch_data *htab"
> .Ft ENTRY *
> .Fn hsearch "ENTRY item" "ACTION action"
> +.Ft int
> +.Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY **itemp" "struct hsearch_data *htab"
> .Sh DESCRIPTION
> The
> .Fn hcreate ,
> @@ -51,6 +57,11 @@ The
> and
> .Fn hsearch
> functions manage hash search tables.
> +.Fn hcreate_r ,
> +.Fn hdestroy_r ,
> +and
> +.Fn hsearch_r
> +are reentrant versions of the functions which can handle multiple hashtables.
> .Pp
> The
> .Fn hcreate
> @@ -67,11 +78,20 @@ Initialization using the
> .Fn hcreate
> function is mandatory prior to any access operations using
> .Fn hsearch .
> +The
> +.Fn hcreate_r
> +operates in the same way but
> +.Fa *htab
> +points to the created hashtable.
> .Pp
> The
> .Fn hdestroy
> function destroys a table previously created using
> .Fn hcreate .
> +The
> +.Fn hdestroy_r
> +acts accordingly for the hashtable
> +.Fa *htab .
> After a call to
> .Fn hdestroy ,
> the data can no longer be accessed.
> @@ -98,8 +118,17 @@ pointer to data associated with
> .Fa key
> .El
> .Pp
> +The function
> +.Fn hsearch_r
> +operates in the same way and searches the hashtables pointed to by
> +.Fa *htab .
> +The pointer to the found entry is returned in
> +.Fa *retval .
> +.Pp
> The key comparison function used by
> .Fn hsearch
> +and
> +.Fn hsearch_r
> is
> .Xr strcmp 3 .
> .Pp
> @@ -154,7 +183,9 @@ is allocated by using
> .Sh RETURN VALUES
> If successful, the
> .Fn hcreate
> -function returns a non-zero value.
> +and
> +.Fn hcreate_r
> +functions returns a non-zero value.
> Otherwise, a value of 0 is returned and
> .Va errno
> is set to indicate the error.
> @@ -176,6 +207,13 @@ If the action is
> .Dv ENTER
> and an entry already existed in the table matching the given
> key, the existing entry is returned and is not replaced.
> +.Pp
> +The function
> +.Fn hsearch_r
> +returns a non-zero value on success.
> +On error 0 is returned and
> +.Va errno
> +is set accordingly.
> .Sh ERRORS
> The
> .Fn hcreate
> @@ -211,7 +249,9 @@ functions first appeared in
> At least the following limitations can be mentioned:
> .Bl -bullet
> .It
> -The interface permits the use of only one hash table at a time.
> +The
> +.Fn hcreate
> +interface permits the use of only one hash table at a time.
> .It
> Individual hash table entries can be added, but not deleted.
> .It
> Index: lib/libc/stdlib/hcreate.c
> ===================================================================
> RCS file: /cvs/src/lib/libc/stdlib/hcreate.c,v
> diff -u -p -u -r1.7 hcreate.c
> --- lib/libc/stdlib/hcreate.c 29 May 2016 20:47:49 -0000 1.7
> +++ lib/libc/stdlib/hcreate.c 16 Jan 2026 15:30:23 -0000
> @@ -81,18 +81,17 @@ SLIST_HEAD(internal_head, internal_entry
> #define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5)
> #define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2)
>
> -static struct internal_head *htable;
> -static size_t htablesize;
> +static struct hsearch_data htab;
>
> int
> -hcreate(size_t nel)
> +hcreate_r(size_t nel, struct hsearch_data *htab)
> {
> size_t idx;
> unsigned int p2;
>
> /* Make sure this isn't called when a table already exists. */
> - _DIAGASSERT(htable == NULL);
> - if (htable != NULL) {
> + _DIAGASSERT(htab->htable == NULL);
> + if (htab->htable != NULL) {
> errno = EINVAL;
> return 0;
> }
> @@ -114,58 +113,70 @@ hcreate(size_t nel)
> }
>
> /* Allocate the table. */
> - htablesize = nel;
> - htable = calloc(htablesize, sizeof htable[0]);
> - if (htable == NULL) {
> + htab->htablesize = nel;
> + htab->htable = calloc(htab->htablesize, sizeof htab->htable[0]);
> + if (htab->htable == NULL) {
> errno = ENOMEM;
> return 0;
> }
>
> /* Initialize it. */
> - for (idx = 0; idx < htablesize; idx++)
> - SLIST_INIT(&htable[idx]);
> + for (idx = 0; idx < htab->htablesize; idx++)
> + SLIST_INIT(&htab->htable[idx]);
>
> return 1;
> }
>
> +int
> +hcreate(size_t nel)
> +{
> + return hcreate_r(nel, &htab);
> +}
> +
> void
> -hdestroy(void)
> +hdestroy_r(struct hsearch_data *htab)
> {
> struct internal_entry *ie;
> size_t idx;
>
> - _DIAGASSERT(htable != NULL);
> - if (htable == NULL)
> + _DIAGASSERT(htab->htable != NULL);
> + if (htab->htable == NULL)
> return;
>
> - for (idx = 0; idx < htablesize; idx++) {
> - while (!SLIST_EMPTY(&htable[idx])) {
> - ie = SLIST_FIRST(&htable[idx]);
> - SLIST_REMOVE_HEAD(&htable[idx], link);
> + for (idx = 0; idx < htab->htablesize; idx++) {
> + while (!SLIST_EMPTY(&htab->htable[idx])) {
> + ie = SLIST_FIRST(&htab->htable[idx]);
> + SLIST_REMOVE_HEAD(&htab->htable[idx], link);
> free(ie->ent.key);
> free(ie);
> }
> }
> - free(htable);
> - htable = NULL;
> + free(htab->htable);
> + htab->htable = NULL;
> }
>
> -ENTRY *
> -hsearch(ENTRY item, ACTION action)
> +void
> +hdestroy(void)
> +{
> + hdestroy_r(&htab);
> +}
> +
> +int
> +hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
> {
> struct internal_head *head;
> struct internal_entry *ie;
> uint32_t hashval;
> size_t len;
>
> - _DIAGASSERT(htable != NULL);
> + _DIAGASSERT(htab->htable != NULL);
> _DIAGASSERT(item.key != NULL);
> _DIAGASSERT(action == ENTER || action == FIND);
>
> len = strlen(item.key);
> hashval = __default_hash(item.key, len);
>
> - head = &htable[hashval & (htablesize - 1)];
> + head = &htab->htable[hashval & (htab->htablesize - 1)];
> ie = SLIST_FIRST(head);
> while (ie != NULL) {
> if (strcmp(ie->ent.key, item.key) == 0)
> @@ -173,17 +184,31 @@ hsearch(ENTRY item, ACTION action)
> ie = SLIST_NEXT(ie, link);
> }
>
> - if (ie != NULL)
> - return &ie->ent;
> - else if (action == FIND)
> - return NULL;
> -
> + if (ie != NULL) {
> + *retval = &ie->ent;
> + return 1;
> + } else if (action == FIND) {
> + *retval = NULL;
> + errno = ESRCH;
> + return 0;
> + }
> ie = malloc(sizeof *ie);
> if (ie == NULL)
> - return NULL;
> + return 0;
> ie->ent.key = item.key;
> ie->ent.data = item.data;
>
> SLIST_INSERT_HEAD(head, ie, link);
> - return &ie->ent;
> + *retval = &ie->ent;
> + return 1;
> +}
> +
> +ENTRY *
> +hsearch(ENTRY item, ACTION action)
> +{
> + ENTRY *retval = NULL;
> +
> + hsearch_r(item, action, &retval, &htab);
> +
> + return retval;
> }
> Index: regress/lib/libc/hsearch/hsearchtest.c
> ===================================================================
> RCS file: /cvs/src/regress/lib/libc/hsearch/hsearchtest.c,v
> diff -u -p -u -r1.2 hsearchtest.c
> --- regress/lib/libc/hsearch/hsearchtest.c 27 Oct 2009 23:59:32 -0000 1.2
> +++ regress/lib/libc/hsearch/hsearchtest.c 16 Jan 2026 16:01:07 -0000
> @@ -62,9 +62,15 @@ main(int argc, char *argv[])
> int created_ok;
> char ch[2];
> int i;
> + struct hsearch_data t_r;
>
> + memset(&t_r, 0, sizeof t_r);
> +
> + /* create hsearch and hsearch_r table */
> created_ok = hcreate(16);
> TEST(created_ok);
> + created_ok = hcreate_r(16, &t_r);
> + TEST(created_ok);
>
> /* ch[1] should be constant from here on down. */
> ch[1] = '\0';
> @@ -79,6 +85,13 @@ main(int argc, char *argv[])
> TEST(ep != NULL);
> TEST(strcmp(ep->key, ch) == 0);
> TEST((long)ep->data == i);
> + /* reentrant with data + 10 */
> + e.key = strdup(ch);
> + e.data = (void *)(long)i+10;
> + hsearch_r(e, ENTER, &ep, &t_r);
> + TEST(ep != NULL);
> + TEST(strcmp(ep->key, ch) == 0);
> + TEST((long)ep->data == i+10);
> }
>
> /* e.key should be constant from here on down. */
> @@ -91,6 +104,11 @@ main(int argc, char *argv[])
> TEST(ep != NULL);
> TEST(strcmp(ep->key, ch) == 0);
> TEST((long)ep->data == i);
> + /* reentrant with data + 10 */
> + hsearch_r(e, FIND, &ep, &t_r);
> + TEST(ep != NULL);
> + TEST(strcmp(ep->key, ch) == 0);
> + TEST((long)ep->data == i+10);
> }
>
> /* Check duplicate entry. Should _not_ overwrite existing data. */
> @@ -100,11 +118,20 @@ main(int argc, char *argv[])
> TEST(ep != NULL);
> TEST(strcmp(ep->key, ch) == 0);
> TEST((long)ep->data == 0);
> + /* reentrant */
> + e.data = (void *)(long)12345;
> + hsearch_r(e, FIND, &ep, &t_r);
> + TEST(ep != NULL);
> + TEST(strcmp(ep->key, ch) == 0);
> + TEST((long)ep->data == 10);
>
> /* Check for something that's not there. */
> ch[0] = 'A';
> ep = hsearch(e, FIND);
> TEST(ep == NULL);
> + /* reentrant */
> + hsearch_r(e, FIND, &ep, &t_r);
> + TEST(ep == NULL);
>
> /* Check two at once. */
> ch[0] = 'a';
> @@ -115,8 +142,18 @@ main(int argc, char *argv[])
> TEST(strcmp(ep->key, "a") == 0 && (long)ep->data == 0);
> TEST(ep2 != NULL);
> TEST(strcmp(ep2->key, "b") == 0 && (long)ep2->data == 1);
> + /* reentrant with data + 10 */
> + ch[0] = 'a';
> + hsearch_r(e, FIND, &ep, &t_r);
> + ch[0] = 'b';
> + hsearch_r(e, FIND, &ep2, &t_r);
> + TEST(ep != NULL);
> + TEST(strcmp(ep->key, "a") == 0 && (long)ep->data == 10);
> + TEST(ep2 != NULL);
> + TEST(strcmp(ep2->key, "b") == 0 && (long)ep2->data == 11);
>
> hdestroy();
> + hdestroy_r(&t_r);
>
> exit(0);
> }
Diff: add reantrant version for hcreate(3)