Date: Mon, 21 Jul 2014 15:22:49 +0000 (UTC) From: "Pedro F. Giffuni" <pfg@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r268943 - in head: include lib/libc/stdlib Message-ID: <201407211522.s6LFMnQo084633@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: pfg Date: Mon Jul 21 15:22:48 2014 New Revision: 268943 URL: http://svnweb.freebsd.org/changeset/base/268943 Log: Add re-entrant versions of the hash functions based on the GNU api. While testing this I found a conformance issue in hdestroy() that will be fixed in a subsequent commit. Obtained from: NetBSD (hcreate.c, CVS Rev. 1.7) Modified: head/include/search.h head/lib/libc/stdlib/Makefile.inc head/lib/libc/stdlib/Symbol.map head/lib/libc/stdlib/hcreate.3 head/lib/libc/stdlib/hcreate.c Modified: head/include/search.h ============================================================================== --- head/include/search.h Mon Jul 21 14:36:35 2014 (r268942) +++ head/include/search.h Mon Jul 21 15:22:48 2014 (r268943) @@ -1,8 +1,8 @@ /*- - * Written by J.T. Conklin <jtc@netbsd.org> + * Written by J.T. Conklin <jtc@NetBSD.org> * Public domain. * - * $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ + * $NetBSD: search.h,v 1.16 2005/02/03 04:39:32 perry Exp $ * $FreeBSD$ */ @@ -45,6 +45,15 @@ struct que_elem { }; #endif +#if __BSD_VISIBLE +struct _ENTRY; +struct hsearch_data { + struct _ENTRY *table; + size_t size; + size_t filled; +}; +#endif + __BEGIN_DECLS int hcreate(size_t); void hdestroy(void); @@ -61,6 +70,13 @@ 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_ */ Modified: head/lib/libc/stdlib/Makefile.inc ============================================================================== --- head/lib/libc/stdlib/Makefile.inc Mon Jul 21 14:36:35 2014 (r268942) +++ head/lib/libc/stdlib/Makefile.inc Mon Jul 21 15:22:48 2014 (r268943) @@ -35,6 +35,7 @@ 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 Modified: head/lib/libc/stdlib/Symbol.map ============================================================================== --- head/lib/libc/stdlib/Symbol.map Mon Jul 21 14:36:35 2014 (r268942) +++ head/lib/libc/stdlib/Symbol.map Mon Jul 21 15:22:48 2014 (r268943) @@ -109,6 +109,9 @@ FBSD_1.4 { heapsort_b; mergesort_b; qsort_b; + hcreate_r; + hdestroy_r; + hsearch_r; }; FBSDprivate_1.0 { Modified: head/lib/libc/stdlib/hcreate.3 ============================================================================== --- head/lib/libc/stdlib/hcreate.3 Mon Jul 21 14:36:35 2014 (r268942) +++ head/lib/libc/stdlib/hcreate.3 Mon Jul 21 15:22:48 2014 (r268943) @@ -28,11 +28,16 @@ .\" .\" $FreeBSD$ .\" -.Dd July 6, 2008 +.Dd July 21, 2014 .Dt HCREATE 3 .Os .Sh NAME -.Nm hcreate , hdestroy , hsearch +.Nm hcreate , +.Nm hcreate_r , +.Nm hdestroy , +.Nm hdestroy_r , +.Nm hsearch , +.Nm hsearch_r .Nd manage hash search table .Sh LIBRARY .Lb libc @@ -40,16 +45,25 @@ .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 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 +.Fn hsearch_r functions manage hash search tables. .Pp The @@ -90,7 +104,7 @@ argument is a structure of type .Vt ENTRY (defined in the .In search.h -header) containing two pointers: +header) that contains two pointers: .Fa item.key points to the comparison key (a .Vt "char *" ) , @@ -136,21 +150,50 @@ is 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 -function returns 0 if the table creation failed and the global variable +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 -function does not return a value. +and +.Fn hdestroy_r +functions return no value. .Pp The .Fn hsearch -function returns a +and +.Fn hsearch_r +functions return a .Dv NULL pointer if either the .Fa action @@ -223,15 +266,31 @@ main(void) .Sh ERRORS The .Fn hcreate -and +.Fn hcreate_r , .Fn hsearch -functions may fail if: +and +.Fn hsearch_r +functions will fail if: .Bl -tag -width Er .It Bq Er ENOMEM -Insufficient storage space is available. +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 , @@ -254,5 +313,15 @@ 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 interface permits the use of only one hash table at a time. +The original, +.Pf non- Tn GNU +interface permits the use of only one hash table at a time. Modified: head/lib/libc/stdlib/hcreate.c ============================================================================== --- head/lib/libc/stdlib/hcreate.c Mon Jul 21 14:36:35 2014 (r268942) +++ head/lib/libc/stdlib/hcreate.c Mon Jul 21 15:22:48 2014 (r268943) @@ -1,4 +1,4 @@ -/* $NetBSD: hcreate.c,v 1.6 2008/07/21 12:05:43 lukem Exp $ */ +/* $NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 christos Exp $ */ /* * Copyright (c) 2001 Christopher G. Demetriou @@ -49,7 +49,7 @@ #include <sys/cdefs.h> #if 0 #if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: hcreate.c,v 1.6 2008/07/21 12:05:43 lukem Exp $"); +__RCSID("$NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 christos Exp $"); #endif /* LIBC_SCCS and not lint */ #endif __FBSDID("$FreeBSD$"); @@ -84,20 +84,27 @@ SLIST_HEAD(internal_head, internal_entry /* Default hash function, from db/hash/hash_func.c */ extern u_int32_t (*__default_hash)(const void *, size_t); -static struct internal_head *htable; -static size_t htablesize; +static struct hsearch_data htable; int hcreate(size_t nel) { - size_t idx; - unsigned int p2; /* Make sure this is not called when a table already exists. */ - if (htable != NULL) { + 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) @@ -115,16 +122,19 @@ hcreate(size_t nel) } /* Allocate the table. */ - htablesize = nel; - htable = malloc(htablesize * sizeof htable[0]); - if (htable == NULL) { + 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 < htablesize; idx++) - SLIST_INIT(&htable[idx]); + for (idx = 0; idx < nel; idx++) + SLIST_INIT(&table[idx]); return 1; } @@ -132,54 +142,83 @@ hcreate(size_t nel) 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 (htable == NULL) + if (head == NULL) return; - for (idx = 0; idx < htablesize; idx++) { - while (!SLIST_EMPTY(&htable[idx])) { - ie = SLIST_FIRST(&htable[idx]); - SLIST_REMOVE_HEAD(&htable[idx], link); + 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->ent.key); free(ie); } } - free(htable); - htable = NULL; + free(table); } ENTRY * hsearch(ENTRY item, ACTION action) { - struct internal_head *head; + 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); - head = &htable[hashval & (htablesize - 1)]; - ie = SLIST_FIRST(head); + 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) - return &ie->ent; - else if (action == FIND) - return NULL; + 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 NULL; + return 0; ie->ent.key = item.key; ie->ent.data = item.data; - SLIST_INSERT_HEAD(head, ie, link); - return &ie->ent; + SLIST_INSERT_HEAD(chain, ie, link); + *itemp = &ie->ent; + head->filled++; + return 1; }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201407211522.s6LFMnQo084633>