Module Name: src
Committed By: christos
Date: Wed Sep 14 23:33:51 UTC 2011
Modified Files:
src/lib/libc/stdlib: Makefile.inc hcreate.3 hcreate.c
Log Message:
add re-entrant versions of the hash functions based on the GNU api.
To generate a diff of this commit:
cvs rdiff -u -r1.77 -r1.78 src/lib/libc/stdlib/Makefile.inc
cvs rdiff -u -r1.8 -r1.9 src/lib/libc/stdlib/hcreate.3
cvs rdiff -u -r1.6 -r1.7 src/lib/libc/stdlib/hcreate.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/lib/libc/stdlib/Makefile.inc
diff -u src/lib/libc/stdlib/Makefile.inc:1.77 src/lib/libc/stdlib/Makefile.inc:1.78
--- src/lib/libc/stdlib/Makefile.inc:1.77 Wed Apr 13 03:12:52 2011
+++ src/lib/libc/stdlib/Makefile.inc Wed Sep 14 19:33:51 2011
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.77 2011/04/13 07:12:52 jruoho Exp $
+# $NetBSD: Makefile.inc,v 1.78 2011/09/14 23:33:51 christos Exp $
# from: @(#)Makefile.inc 8.3 (Berkeley) 2/4/95
# stdlib sources
@@ -65,6 +65,7 @@
MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3
MLINKS+=getenv.3 getenv_r.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+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3
Index: src/lib/libc/stdlib/hcreate.3
diff -u src/lib/libc/stdlib/hcreate.3:1.8 src/lib/libc/stdlib/hcreate.3:1.9
--- src/lib/libc/stdlib/hcreate.3:1.8 Sat May 1 02:18:03 2010
+++ src/lib/libc/stdlib/hcreate.3 Wed Sep 14 19:33:51 2011
@@ -1,4 +1,4 @@
-.\" $NetBSD: hcreate.3,v 1.8 2010/05/01 06:18:03 jruoho Exp $
+.\" $NetBSD: hcreate.3,v 1.9 2011/09/14 23:33:51 christos Exp $
.\"
.\" Copyright (c) 1999 The NetBSD Foundation, Inc.
.\" All rights reserved.
@@ -27,13 +27,16 @@
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
-.Dd May 1, 2010
+.Dd September 14, 2011
.Dt HCREATE 3
.Os
.Sh NAME
.Nm hcreate ,
+.Nm hcreate_r ,
.Nm hdestroy ,
-.Nm hsearch
+.Nm hdestroy_r ,
+.Nm hsearch ,
+.Nm hsearch_r
.Nd manage hash search table
.Sh LIBRARY
.Lb libc
@@ -41,16 +44,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_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 hdestroy
+.Fn hcreate_r ,
+.Fn hdestroy ,
+.Fn hdestroy_r
and
-.Fn hsearch
+.Fn hsearch ,
+.Fn hsearch_r
functions manage hash search tables.
.Pp
The
@@ -152,18 +164,46 @@
.Fa key
is allocated by using
.Xr strdup 3 .
+.Pp
+The
+.Fn hcreate_r ,
+.Fn hdestroy_r ,
+and
+.Fn hsearch_r
+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
If successful, the
.Fn hcreate
-function returns a non-zero value.
-Otherwise, a value of 0 is returned and
+and
+.Fn hcreate_r
+function return a non-zero value.
+Otherwise, a value of
+.Dv 0
+is returned and
.Va errno
is set to indicate the error.
.Pp
The
.Fn hdestroy
-functions
-returns no value.
+and
+.Fn hdestroy_r
+functions return no value.
.Pp
If successful, the
.Fn hsearch
@@ -182,16 +222,45 @@
.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
+.Fn hsearch_r
+function returns
+.Dv 1
+unless the table is full, when it returns
+.Dv 0 .
+If the
+.Fn hsearch
+returns
+.Dv 0
+or the element is not found,
+.Va errno
+is set to indicate the error.
.Sh ERRORS
The
-.Fn hcreate
-and
+.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.
.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 ,
@@ -213,11 +282,21 @@
.Fn hsearch
functions first appeared in
.At V .
+The
+.Fn hcreate_r ,
+.Fn hdestroy_r
+and
+.Fn hsearch_r
+are
+.Tn GNU
+extensions.
.Sh CAVEATS
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 original, non-
+.Tn GNU
+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: src/lib/libc/stdlib/hcreate.c
diff -u src/lib/libc/stdlib/hcreate.c:1.6 src/lib/libc/stdlib/hcreate.c:1.7
--- src/lib/libc/stdlib/hcreate.c:1.6 Mon Jul 21 08:05:43 2008
+++ src/lib/libc/stdlib/hcreate.c Wed Sep 14 19:33:51 2011
@@ -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
@@ -48,7 +48,7 @@
#include <sys/cdefs.h>
#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 */
#if !defined(lint)
@@ -88,21 +88,28 @@
/* 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;
+ _DIAGASSERT(htable.table == NULL);
/* Make sure this isn't called when a table already exists. */
- _DIAGASSERT(htable == NULL);
- 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)
@@ -121,16 +128,19 @@
}
/* 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;
}
@@ -138,59 +148,88 @@
void
hdestroy(void)
{
+ _DIAGASSERT(htable.table != NULL);
+ hdestroy_r(&htable);
+}
+
+void
+hdestroy_r(struct hsearch_data *head)
+{
struct internal_entry *ie;
size_t idx;
+ void *p;
+ struct internal_head *table;
- _DIAGASSERT(htable != NULL);
- 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;
+ _DIAGASSERT(htable.table != NULL);
+ (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;
- _DIAGASSERT(htable != NULL);
_DIAGASSERT(item.key != NULL);
_DIAGASSERT(action == ENTER || action == FIND);
+ 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;
}
