From: Jan Klemkow Subject: Re: Diff: add reantrant version for hcreate(3) To: Timo Mirau Cc: tech@openbsd.org Date: Wed, 29 Apr 2026 00:55:46 +0200 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 > +#include > #include > > #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); > }