libhurd-ihash/

2008-01-23  Neal H. Walfield  <neal@gnu.org>

	* ihash.h (hurd_ihash_buffer_size): New declaration.
	(hurd_ihash_init_with_buffer): Likewise.
	(hurd_ihash_init): Add comment that this function is not provided
	if the library is compiled with NO_MALLOC.
	(hurd_ihash_create): Likewise.
	(hurd_ihash_free): Likewise.
	(hurd_ihash_destroy): Update comment.
	* ihash.c (hurd_ihash_init_with_buffer): New function.
	(hurd_ihash_destroy) [NO_MALLOC]: Don't free HT->ITEMS.
	(hurd_ihash_create) [NO_MALLOC]: Just return ENOMEM;
	(hurd_ihash_free) [NO_MALLOC]: Remove function.
	(hurd_ihash_buffer_size): New function.
	(hurd_ihash_replace) [NO_MALLOC]: Don't attempt to expand the hash
	table.
	[! NO_MALLOC]: Use hurd_ihash_buffer_size to calculate an
	appropriate buffer size.
	* Makefile.am (lib_LIBRARIES): Add libhurd-ihash-nomalloc.a.
	(libhurd_ihash_nomalloc_a_CPPFLAGS): New variable.
	(libhurd_ihash_nomalloc_a_SOURCES): Likewise.

	* t-ihash.c (main): Cast locp offset calculation to elide warning.

viengoos/

2008-01-23  Neal H. Walfield  <neal@gnu.org>

	* thread.c: Include "zalloc.h".
	(thread_init): Initialize TID_TO_THREAD hash here.  Allocate using
	zalloc.
	* object.c: Include "zalloc.h".
	(object_init): Allocate hash table and object_descs using zalloc.
	* Makefile.am (viengoos_SOURCES): Remove malloc.h and
	malloc-wrap.c.
	(viengoos_LDADD): Use ../libhurd-ihash/libhurd-ihash-nomalloc.a
	rather than ../libhurd-ihash/libhurd-ihash.a.
	(EXTRA_viengoos_SOURCES): Remove variable.

	* memory.c (memory_grab) [_L4_TEST_ENVIRONMENT]: Don't include
	binary when calculating available memory.

5 files changed, 117 insertions, 20 deletions

diff --git a/libhurd-ihash/ChangeLog b/libhurd-ihash/ChangeLog
index cb8a34b..3a80edf 100644
--- a/libhurd-ihash/ChangeLog
+++ b/libhurd-ihash/ChangeLog
@@ -1,5 +1,29 @@
 2008-01-23  Neal H. Walfield  <neal@gnu.org>
 
+	* ihash.h (hurd_ihash_buffer_size): New declaration.
+	(hurd_ihash_init_with_buffer): Likewise.
+	(hurd_ihash_init): Add comment that this function is not provided
+	if the library is compiled with NO_MALLOC.
+	(hurd_ihash_create): Likewise.
+	(hurd_ihash_free): Likewise.
+	(hurd_ihash_destroy): Update comment.
+	* ihash.c (hurd_ihash_init_with_buffer): New function.
+	(hurd_ihash_destroy) [NO_MALLOC]: Don't free HT->ITEMS.
+	(hurd_ihash_create) [NO_MALLOC]: Just return ENOMEM;
+	(hurd_ihash_free) [NO_MALLOC]: Remove function.
+	(hurd_ihash_buffer_size): New function.
+	(hurd_ihash_replace) [NO_MALLOC]: Don't attempt to expand the hash
+	table.
+	[! NO_MALLOC]: Use hurd_ihash_buffer_size to calculate an
+	appropriate buffer size.
+	* Makefile.am (lib_LIBRARIES): Add libhurd-ihash-nomalloc.a.
+	(libhurd_ihash_nomalloc_a_CPPFLAGS): New variable.
+	(libhurd_ihash_nomalloc_a_SOURCES): Likewise.
+
+	* t-ihash.c (main): Cast locp offset calculation to elide warning.
+
+2008-01-23  Neal H. Walfield  <neal@gnu.org>
+
 	* Makefile.am (AM_CPPFLAGS): Add -I$(LIBC)/include.
 
 2008-01-23  Neal H. Walfield  <neal@gnu.org>
diff --git a/libhurd-ihash/Makefile.am b/libhurd-ihash/Makefile.am
index da7c106..60c09aa 100644
--- a/libhurd-ihash/Makefile.am
+++ b/libhurd-ihash/Makefile.am
@@ -19,7 +19,7 @@
 # Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 # 02111-1307 USA.
 
-lib_LIBRARIES = libhurd-ihash.a
+lib_LIBRARIES = libhurd-ihash.a libhurd-ihash-nomalloc.a
 
 includehurddir = $(includedir)/hurd
 includehurd_HEADERS = ihash.h
@@ -29,8 +29,12 @@ includehurd_HEADERS = ihash.h
 AM_CPPFLAGS = -I$(LIBC)/include -I$(top_builddir)/include	\
 	-I$(top_srcdir)/libc-parts
 AM_CFLAGS = -std=gnu99
+
 libhurd_ihash_a_SOURCES = ihash.h ihash.c
 
+libhurd_ihash_nomalloc_a_CPPFLAGS = $(AM_CPPFLAGS) -DNO_MALLOC
+libhurd_ihash_nomalloc_a_SOURCES = ihash.h ihash.c
+
 TESTS = t-ihash
 
 check_PROGRAMS = t-ihash
diff --git a/libhurd-ihash/ihash.c b/libhurd-ihash/ihash.c
index 9e00b2e..b16632b 100644
--- a/libhurd-ihash/ihash.c
+++ b/libhurd-ihash/ihash.c
@@ -1,5 +1,5 @@
 /* ihash.c - Integer-keyed hash table functions.
-   Copyright (C) 1993-1997, 2001, 2003, 2004, 2007 Free Software Foundation, Inc.
+   Copyright (C) 1993-1997, 2001, 2003, 2004, 2007, 2008 Free Software Foundation, Inc.
    Written by Michael I. Bushnell.
    Revised by Miles Bader <miles@gnu.org>.
    Revised by Marcus Brinkmann <marcus@gnu.org>.
@@ -166,8 +166,8 @@ locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp, bool cleanup)
 /* Construction and destruction of hash tables.  */
 
 /* Initialize the hash table at address HT.  */
-void
-hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
+static void
+hurd_ihash_init_internal (hurd_ihash_t ht, intptr_t locp_offs)
 {
   ht->nr_items = 0;
   ht->size = 0;
@@ -176,6 +176,23 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
   ht->cleanup = 0;
 }
 
+#ifndef NO_MALLOC
+void
+hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
+{
+  hurd_ihash_init_internal (ht, locp_offs);
+}
+#endif
+
+void
+hurd_ihash_init_with_buffer (hurd_ihash_t ht, intptr_t locp_offs,
+			     void *buffer, size_t size)
+{
+  hurd_ihash_init_internal (ht, locp_offs);
+  ht->items = buffer;
+  ht->size = size / sizeof (struct _hurd_ihash_item);
+}
+
 
 /* Destroy the hash table at address HT.  This first removes all
    elements which are still in the hash table, and calling the cleanup
@@ -192,13 +209,16 @@ hurd_ihash_destroy (hurd_ihash_t ht)
 	(*cleanup) (value, cleanup_data);
     }
 
+#ifndef NO_MALLOC
   if (ht->size > 0)
     free (ht->items);
+#endif
 }
 
 
 /* Create a hash table, initialize it and return it in HT.  If a
    memory allocation error occurs, ENOMEM is returned, otherwise 0.  */
+#ifndef NO_MALLOC
 error_t
 hurd_ihash_create (hurd_ihash_t *ht, intptr_t locp_offs)
 {
@@ -210,16 +230,19 @@ hurd_ihash_create (hurd_ihash_t *ht, intptr_t locp_offs)
 
   return 0;
 }
+#endif
 
 
 /* Destroy the hash table HT and release the memory allocated for it
    by hurd_ihash_create().  */
+#ifndef NO_MALLOC
 void
 hurd_ihash_free (hurd_ihash_t ht)
 {
   hurd_ihash_destroy (ht);
   free (ht);
 }
+#endif
 
 
 /* Set the cleanup function for the hash table HT to CLEANUP.  The
@@ -352,7 +375,32 @@ replace_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value,
   return 0;
 }
 
-  
+/* Return the size of a buffer (in bytes) that is appropriate for a
+   hash with COUNT elements and a load factor of LOAD_FACTOR
+   (LOAD_FACTOR must be between 1 and 100, a load factor of 0 implies
+   the default load factor).  */
+size_t
+hurd_ihash_buffer_size (size_t count, int max_load_factor)
+{
+  if (max_load_factor == 0)
+    max_load_factor = HURD_IHASH_MAX_LOAD_DEFAULT;
+  if (max_load_factor > 100)
+    max_load_factor = 100;
+  if (max_load_factor < 0)
+    max_load_factor = 1;
+
+  count = count * 100 / max_load_factor;
+
+  int i;
+  for (i = 0; i < ihash_nsizes; i++)
+    if (ihash_sizes[i] >= count)
+      break;
+  if (i == ihash_nsizes)
+    return SIZE_MAX;		/* Surely will be true momentarily.  */
+
+  return ihash_sizes[i] * sizeof (struct _hurd_ihash_item);
+}
+
 /* Add ITEM to the hash table HT under the key KEY.  If there already
    is an item under this key and OLD_VALUE is not NULL, then stores
    the value in *OLD_VALUE.  If there already is an item under this
@@ -366,28 +414,30 @@ hurd_ihash_replace (hurd_ihash_t ht, hurd_ihash_key_t key,
 		    hurd_ihash_value_t item,
 		    bool *had_value, hurd_ihash_value_t  *old_value)
 {
-  struct hurd_ihash old_ht = *ht;
-  int was_added;
-  int i;
-
   if (ht->size)
     {
       /* Only fill the hash table up to its maximum load factor.  */
+#ifndef NO_MALLOC
       if (ht->nr_items * 100 / ht->size <= ht->max_load)
+#endif
 	if (replace_one (ht, key, item, had_value, old_value))
 	  return 0;
     }
 
+#ifdef NO_MALLOC
+  return ENOMEM;
+#else
+  struct hurd_ihash old_ht = *ht;
+  int was_added;
+  int i;
+
   /* The hash table is too small, and we have to increase it.  */
-  for (i = 0; i < ihash_nsizes; i++)
-    if (ihash_sizes[i] > old_ht.size)
-      break;
-  if (i == ihash_nsizes
-      || ihash_sizes[i] > SIZE_MAX / sizeof (struct _hurd_ihash_item))
+  size_t size = hurd_ihash_buffer_size (old_ht.size + 1, ht->max_load);
+  if (size >= SIZE_MAX)
     return ENOMEM;		/* Surely will be true momentarily.  */
 
   ht->nr_items = 0;
-  ht->size = ihash_sizes[i];
+  ht->size = size / sizeof (struct _hurd_ihash_item);
   /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitely.  */
   ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
 
@@ -418,6 +468,7 @@ hurd_ihash_replace (hurd_ihash_t ht, hurd_ihash_key_t key,
     free (old_ht.items);
 
   return 0;
+#endif
 }
 
 
diff --git a/libhurd-ihash/ihash.h b/libhurd-ihash/ihash.h
index 6a7a809..c2332de 100644
--- a/libhurd-ihash/ihash.h
+++ b/libhurd-ihash/ihash.h
@@ -110,12 +110,28 @@ typedef struct hurd_ihash *hurd_ihash_t;
    HURD_IHASH_NO_LOCP, then this is an offset (in bytes) from the
    address of a hash value where a location pointer can be found.  The
    location pointer must be of type hurd_ihash_locp_t and can be used
-   for fast removal with hurd_ihash_locp_remove().  */
+   for fast removal with hurd_ihash_locp_remove().  This function is
+   not provided if compiled with NO_MALLOC.  */
 void hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs);
 
+/* Return the size of a buffer (in bytes) that is appropriate for a
+   hash with COUNT elements and a load factor of LOAD_FACTOR
+   (LOAD_FACTOR must be between 1 and 100, a load factor of 0 implies
+   the default load factor).  */
+size_t hurd_ihash_buffer_size (size_t count, int max_load_factor);
+
+/* Initialize a hash ala hurd_ihash_init but provide an initial buffer
+   BUFFER of size SIZE bytes.  If not compiled with NO_MALLOC, the
+   memory is assumed to be allocated with malloc and may be freed if
+   the hash must be grown or when hurd_ihash_destroy is called.  */
+void hurd_ihash_init_with_buffer (hurd_ihash_t ht, intptr_t locp_offs,
+				  void *buffer, size_t size);
+
 /* Destroy the hash table at address HT.  This first removes all
    elements which are still in the hash table, and calling the cleanup
-   function for them (if any).  */
+   function for them (if any).  If compiled with NO_MALLOC, it is the
+   caller's responsibility to free the originally provided buffer,
+   otherwise, any buffer in use if freed.  */
 void hurd_ihash_destroy (hurd_ihash_t ht);
 
 /* Create a hash table, initialize it and return it in HT.  If
@@ -124,11 +140,13 @@ void hurd_ihash_destroy (hurd_ihash_t ht);
    can be found.  The location pointer must be of type
    hurd_ihash_locp_t and can be used for fast removal with
    hurd_ihash_locp_remove().  If a memory allocation error occurs,
-   ENOMEM is returned, otherwise 0.  */
+   ENOMEM is returned, otherwise 0.  This function is not provided if
+   compiled with NO_MALLOC.  */
 error_t hurd_ihash_create (hurd_ihash_t *ht, intptr_t locp_offs);
 
 /* Destroy the hash table HT and release the memory allocated for it
-   by hurd_ihash_create().  */
+   by hurd_ihash_create().  This function is not provided if compiled
+   with NO_MALLOC.  */
 void hurd_ihash_free (hurd_ihash_t ht);
 
 
diff --git a/libhurd-ihash/t-ihash.c b/libhurd-ihash/t-ihash.c
index e906da0..316e4d5 100644
--- a/libhurd-ihash/t-ihash.c
+++ b/libhurd-ihash/t-ihash.c
@@ -104,7 +104,7 @@ main (int argc, char *argv[])
     int value;
     hurd_ihash_locp_t locp;
   };
-  hurd_ihash_init (&hash, &(((struct s *)0)->locp));
+  hurd_ihash_init (&hash, (int) &(((struct s *)0)->locp));
 
   if (hurd_ihash_find (&hash, 1))
     F ("Found object with key 1 in otherwise empty hash");