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 <j...@netbsd.org>
+ * Written by J.T. Conklin <j...@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;
}
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
