2007-10-06 Neal H. Walfield <neal@gnu.org>

	* ihash.h (hurd_ihash_replace): New prototype.
	(hurd_ihash_add): Replace prototype with a static inline
	implementation that calls hurd_ihash_replace with the right
	parameters.
	* ihash.c (locp_remove): Take additional argument, cleanup.  Only
	call the cleanup function if CLEANUP is true.  Update callers.
	(add_one): Rename from this...
	(replace_one): ... to this.  Add two parameters, had_value and
	old_value.  If the key has a value and OLD_VALUE is not NULL, then
	do not call the cleanup function but save the old value in
	*OLD_VALUE.  If the key had a value and HAD_VALUE is not NULL,
	then store true in *HAD_VALUE, otherwise, false.  Update callers.

	* Makefile.am (TESTS): Set to t-ihash.
	(check_PROGRAMS): Set to t-ihash.
	(t_ihash_SOURCES): Set to t-ihash.c and ihash.h.
	(t_ihash_LDADD): Set to libhurd-ihash.a.
	* t-ihash.c: New file.

5 files changed, 199 insertions, 21 deletions

diff --git a/libhurd-ihash/ChangeLog b/libhurd-ihash/ChangeLog
index 93ffb9d..16d9034 100644
--- a/libhurd-ihash/ChangeLog
+++ b/libhurd-ihash/ChangeLog
@@ -1,3 +1,37 @@
+2007-10-06  Neal H. Walfield  <neal@gnu.org>
+
+	* ihash.h (hurd_ihash_replace): New prototype.
+	(hurd_ihash_add): Replace prototype with a static inline
+	implementation that calls hurd_ihash_replace with the right
+	parameters.
+	* ihash.c (locp_remove): Take additional argument, cleanup.  Only
+	call the cleanup function if CLEANUP is true.  Update callers.
+	(add_one): Rename from this...
+	(replace_one): ... to this.  Add two parameters, had_value and
+	old_value.  If the key has a value and OLD_VALUE is not NULL, then
+	do not call the cleanup function but save the old value in
+	*OLD_VALUE.  If the key had a value and HAD_VALUE is not NULL,
+	then store true in *HAD_VALUE, otherwise, false.  Update callers.
+	
+	* Makefile.am (TESTS): Set to t-ihash.
+	(check_PROGRAMS): Set to t-ihash.
+	(t_ihash_SOURCES): Set to t-ihash.c and ihash.h.
+	(t_ihash_LDADD): Set to libhurd-ihash.a.
+	* t-ihash.c: New file.
+
+2007-08-23  Neal H. Walfield  <neal@gnu.org>
+
+	* ihash.h (hurd_ihash_replace): New declaration.
+	(hurd_ihash_add): Replace declaration with a static inline stub
+	that calls hurd_ihash_replace.
+	* ihash.c (add_one): Rename from this...
+	(replace_one): ... to this.  Add two parameters.  Save the old key
+	value in *OLD_VALUE.  Save whether there was an old value in
+	*HAD_VALUE.  Update callers.
+	(hurd_ihash_add): Rename from this...
+	(hurd_ihash_replace): ... to this.  Add two parameters.  Pass them
+	in calls to replace_one.
+
 2004-04-21  Marcus Brinkmann  <marcus@gnu.org>
 
 	* ihash.h (HURD_IHASH_ITERATE): Don't use increment operator in
diff --git a/libhurd-ihash/Makefile.am b/libhurd-ihash/Makefile.am
index 4a4e4fa..1752bad 100644
--- a/libhurd-ihash/Makefile.am
+++ b/libhurd-ihash/Makefile.am
@@ -1,5 +1,5 @@
 # Makefile.am - Makefile template for libhurd-ihash.
-# Copyright (C) 2003 Free Software Foundation, Inc.
+# Copyright (C) 2003, 2007 Free Software Foundation, Inc.
 # Written by Marcus Brinkmann.
 #
 # This file is part of the GNU Hurd.
@@ -29,3 +29,9 @@ includehurd_HEADERS = ihash.h
 AM_CPPFLAGS = -I$(top_builddir)/include -I$(top_srcdir)/libc-parts
 AM_CFLAGS = -std=gnu99
 libhurd_ihash_a_SOURCES = ihash.h ihash.c
+
+TESTS = t-ihash
+
+check_PROGRAMS = t-ihash
+t_ihash_SOURCES = t-ihash.c ihash.h
+t_ihash_LDADD = libhurd-ihash.a
diff --git a/libhurd-ihash/ihash.c b/libhurd-ihash/ihash.c
index 8fa9d51..9e00b2e 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 Free Software Foundation, Inc.
+   Copyright (C) 1993-1997, 2001, 2003, 2004, 2007 Free Software Foundation, Inc.
    Written by Michael I. Bushnell.
    Revised by Miles Bader <miles@gnu.org>.
    Revised by Marcus Brinkmann <marcus@gnu.org>.
@@ -151,11 +151,12 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
 
 /* Remove the entry pointed to by the location pointer LOCP from the
    hashtable HT.  LOCP is the location pointer of which the address
-   was provided to hurd_ihash_add().  */
+   was provided to hurd_ihash_add().  If CLEANUP is true, call the
+   cleanup handler, if any.  */
 static inline void
-locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
+locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp, bool cleanup)
 {
-  if (ht->cleanup)
+  if (cleanup && ht->cleanup)
     (*ht->cleanup) (*locp, ht->cleanup_data);
   *locp = _HURD_IHASH_DELETED;
   ht->nr_items--;
@@ -252,15 +253,16 @@ hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load)
 }
 
 
-/* Helper function for hurd_ihash_add.  Return 1 if the item was
+/* Helper function for hurd_ihash_replace.  Return 1 if the item was
    added, and 0 if it could not be added because no empty slot was
-   found.  The arguments are identical to hurd_ihash_add.
+   found.  The arguments are identical to hurd_ihash_replace.
 
    We are using open address hashing.  As the hash function we use the
    division method with quadratic probe.  This is guaranteed to try
    all slots in the hash table if the prime number is 3 mod 4.  */
 static inline int
-add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
+replace_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value,
+	     bool *had_value, hurd_ihash_value_t *old_value)
 {
   unsigned int idx;
   unsigned int first_free;
@@ -315,7 +317,19 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
 
   /* Remove the old entry for this key if necessary.  */
   if (index_valid (ht, idx, key))
-    locp_remove (ht, &ht->items[idx].value);
+    {
+      if (had_value)
+	*had_value = true;
+
+      if (old_value)
+	*old_value = ht->items[idx].value;
+      locp_remove (ht, &ht->items[idx].value, !! old_value);
+    }
+  else
+    {
+      if (had_value)
+	*had_value = false;
+    }
 
   /* If we have not found an empty slot, maybe the last one we
      looked at was empty (or just got deleted).  */
@@ -340,11 +354,17 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
 
   
 /* Add ITEM to the hash table HT under the key KEY.  If there already
-   is an item under this key, call the cleanup function (if any) for
-   it before overriding the value.  If a memory allocation error
-   occurs, ENOMEM is returned, otherwise 0.  */
+   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
+   key and OLD_VALUE is NULL, then calls the cleanup function (if any)
+   for it before overriding the value.  If HAD_VALUE is not NULL, then
+   stores whether there was already an item under this key in
+   *HAD_VALUE.  If a memory allocation error occurs, ENOMEM is
+   returned, otherwise 0.  */
 error_t
-hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
+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;
@@ -354,7 +374,7 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
     {
       /* Only fill the hash table up to its maximum load factor.  */
       if (ht->nr_items * 100 / ht->size <= ht->max_load)
-	if (add_one (ht, key, item))
+	if (replace_one (ht, key, item, had_value, old_value))
 	  return 0;
     }
 
@@ -384,12 +404,14 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item)
   for (i = 0; i < old_ht.size; i++)
     if (!index_empty (&old_ht, i))
       {
-	was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value);
+	was_added = replace_one (ht, old_ht.items[i].key,
+				 old_ht.items[i].value,
+				 had_value, old_value);
 	assert (was_added);
       }
 
   /* Finally add the new element!  */
-  was_added = add_one (ht, key, item);
+  was_added = replace_one (ht, key, item, had_value, old_value);
   assert (was_added);
 
   if (old_ht.size > 0)
@@ -425,7 +447,7 @@ hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key)
       
       if (index_valid (ht, idx, key))
 	{
-	  locp_remove (ht, &ht->items[idx].value);
+	  locp_remove (ht, &ht->items[idx].value, true);
 	  return 1;
 	}
     }
@@ -441,5 +463,5 @@ hurd_ihash_remove (hurd_ihash_t ht, hurd_ihash_key_t key)
 void
 hurd_ihash_locp_remove (hurd_ihash_t ht, hurd_ihash_locp_t locp)
 {
-  locp_remove (ht, locp);
+  locp_remove (ht, locp, true);
 }
diff --git a/libhurd-ihash/ihash.h b/libhurd-ihash/ihash.h
index a4e76dc..822455f 100644
--- a/libhurd-ihash/ihash.h
+++ b/libhurd-ihash/ihash.h
@@ -1,5 +1,5 @@
 /* ihash.h - Integer keyed hash table interface.
-   Copyright (C) 1995, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 1995, 2003, 2004, 2007 Free Software Foundation, Inc.
    Written by Miles Bader <miles@gnu.org>.
    Revised by Marcus Brinkmann <marcus@gnu.org>.
 
@@ -155,11 +155,28 @@ void hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load);
 
 
 /* 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
+   key and OLD_VALUE is NULL, then calls the cleanup function (if any)
+   for it before overriding the value.  If HAD_VALUE is not NULL, then
+   stores whether there was already an item under this key in
+   *HAD_VALUE.  If a memory allocation error occurs, ENOMEM is
+   returned, otherwise 0.  */
+error_t
+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);
+
+/* Add ITEM to the hash table HT under the key KEY.  If there already
    is an item under this key, call the cleanup function (if any) for
    it before overriding the value.  If a memory allocation error
    occurs, ENOMEM is returned, otherwise 0.  */
-error_t hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
-			hurd_ihash_value_t item);
+static inline error_t
+hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
+		hurd_ihash_value_t item)
+{
+  return hurd_ihash_replace (ht, key, item, NULL, NULL);
+}
 
 /* Find and return the item in the hash table HT with key KEY, or NULL
    if it doesn't exist.  */
diff --git a/libhurd-ihash/t-ihash.c b/libhurd-ihash/t-ihash.c
new file mode 100644
index 0000000..c0124f5
--- /dev/null
+++ b/libhurd-ihash/t-ihash.c
@@ -0,0 +1,99 @@
+/* t-ihash.c - Integer-keyed hash table function unit-tests.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+   Written by Neal H. Walfield <neal@gnu.org>.
+   
+   This file is part of the GNU Hurd.
+
+   The GNU Hurd is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   The GNU Hurd is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with the GNU Hurd; see the file COPYING.  If not, write to
+   the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
+
+#define _GNU_SOURCE
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <errno.h>
+#include <stdio.h>
+
+#include "ihash.h"
+
+#define F(format, args...) \
+  ({ \
+    printf ("fail: line %d ", __LINE__); \
+    printf (format "... ", ##args); \
+    return 1; \
+  })
+
+int
+main (int argc, char *argv[])
+{
+  struct hurd_ihash hash;
+
+  hurd_ihash_init (&hash, HURD_IHASH_NO_LOCP);
+
+  printf ("Testing hurd_ihash_add... ");
+
+  int k;
+  hurd_ihash_value_t v;
+  for (k = 1; k < 100; k ++)
+    if (hurd_ihash_add (&hash, (hurd_ihash_key_t) k,
+			(hurd_ihash_value_t) k) != 0)
+      F ("failed to insert %d\n", k);
+  for (k = 1; k < 100; k ++)
+    {
+      v = hurd_ihash_find (&hash, (hurd_ihash_key_t) k);
+      if (v != (hurd_ihash_value_t) k)
+	F ("unexpected value %d for key %d\n", (int) v, k);
+    }
+
+  printf ("ok\n");
+
+  printf ("Testing hurd_ihash_replace... ");
+
+  bool had_value;
+  for (k = 1; k < 100; k ++)
+    if (hurd_ihash_replace (&hash,
+			    (hurd_ihash_key_t) k,
+			    (hurd_ihash_value_t) k + 1,
+			    &had_value, &v) != 0)
+      F ("failed to replace key %d\n", k);
+    else if (! had_value)
+      F ("No value for key %d\n", k);
+    else if ((int) v != k)
+      F ("Value for key %d is %d, not %d\n", k, (int) v, k);
+
+  for (k = 100; k < 200; k ++)
+    if (hurd_ihash_replace (&hash,
+			    (hurd_ihash_key_t) k,
+			    (hurd_ihash_value_t) (k + 1),
+			    &had_value, &v) != 0)
+      F ("failed to replace value of key %d\n", k);
+    else if (had_value)
+      F ("key %d had the unexpected value %d!\n", k, (int) v);
+
+  for (k = 1; k < 100; k ++)
+    if (hurd_ihash_replace (&hash, (hurd_ihash_key_t) k,
+			    (hurd_ihash_value_t) k,
+			    &had_value, &v) != 0)
+      F ("failed to replace the value of key %d\n", k);
+    else if (! had_value)
+      F ("No value for key %d\n", k);
+    else if ((int) v != k + 1)
+      F ("Value for key %d is %d, not %d\n", k, (int) v, k + 1);
+
+  printf ("ok\n");
+
+  return 0;
+}