[src/trunk]: src/lib/libc/stdlib add re-entrant versions of the hash function...

[christos <christos%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/ed1c32dd4cbc
branches:  trunk
changeset: 769573:ed1c32dd4cbc
user:      christos <christos%NetBSD.org@localhost>
date:      Wed Sep 14 23:33:51 2011 +0000

description:
add re-entrant versions of the hash functions based on the GNU api.

diffstat:

 lib/libc/stdlib/Makefile.inc |    3 +-
 lib/libc/stdlib/hcreate.3    |  103 +++++++++++++++++++++++++++++++++++++-----
 lib/libc/stdlib/hcreate.c    |  103 +++++++++++++++++++++++++++++-------------
 3 files changed, 164 insertions(+), 45 deletions(-)

diffs (truncated from 381 to 300 lines):

diff -r f67b4ccd7417 -r ed1c32dd4cbc lib/libc/stdlib/Makefile.inc
--- a/lib/libc/stdlib/Makefile.inc      Wed Sep 14 19:45:27 2011 +0000
+++ b/lib/libc/stdlib/Makefile.inc      Wed Sep 14 23:33:51 2011 +0000
@@ -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
diff -r f67b4ccd7417 -r ed1c32dd4cbc lib/libc/stdlib/hcreate.3
--- a/lib/libc/stdlib/hcreate.3 Wed Sep 14 19:45:27 2011 +0000
+++ b/lib/libc/stdlib/hcreate.3 Wed Sep 14 23:33:51 2011 +0000
@@ -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
+.Fn hcreate ,
+.Fn hcreate_r ,
+.Fn hsearch
 and
-.Fn hsearch
+.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
diff -r f67b4ccd7417 -r ed1c32dd4cbc lib/libc/stdlib/hcreate.c
--- a/lib/libc/stdlib/hcreate.c Wed Sep 14 19:45:27 2011 +0000
+++ b/lib/libc/stdlib/hcreate.c Wed Sep 14 23:33:51 2011 +0000
@@ -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;