[PATCH] Add hash_contains function

[Colin Watson]

I looked at converting man-db to use Gnulib's hash implementation rather
than its own.  One obstacle seems to be that there is one place where
man-db cares about the difference between a key not being in the hash at
all, and a key being in the hash but with a NULL value (in Perl syntax,
the difference between 'not exists $hash{$key}' and 'not defined
$hash{$key}').  I haven't spent much time looking at the relevant code
and so it may well be that it can be rewritten to avoid relying on this
distinction, but in general it does seem like a useful distinction to
draw; most high-level languages' built-in hash implementations allow you
to ask whether a key exists without testing the truth of its value.

The attached patch adds this feature.

Thanks,

-- 
Colin Watson                                       [cjwat...@debian.org]

diff --git a/ChangeLog b/ChangeLog
index c382d58..2f32364 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2010-02-14  Colin Watson  <cjwat...@debian.org>
+
+	* lib/hash.c (hash_contains): New function (trivial modification of
+	hash_lookup).
+	* lib/hash.h (hash_contains): New declaration.
+	* tests/test-hash.c (main): Test hash_contains.
+
 2010-02-10  Jim Meyering  <meyer...@redhat.com>
 
 	maint.mk: prohibit inclusion of "ignore-value.h" without_use
diff --git a/lib/hash.c b/lib/hash.c
index f9abb9f..de8b778 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -243,6 +243,28 @@ hash_print_statistics (const Hash_table *table, FILE *stream)
            (unsigned long int) max_bucket_length);
 }
 
+/* Return true if ENTRY matches an entry already in the hash table.  */
+
+bool
+hash_contains (const Hash_table *table, const void *entry)
+{
+  struct hash_entry const *bucket
+    = table->bucket + table->hasher (entry, table->n_buckets);
+  struct hash_entry const *cursor;
+
+  if (! (bucket < table->bucket_limit))
+    abort ();
+
+  if (bucket->data == NULL)
+    return false;
+
+  for (cursor = bucket; cursor; cursor = cursor->next)
+    if (entry == cursor->data || table->comparator (entry, cursor->data))
+      return true;
+
+  return false;
+}
+
 /* If ENTRY matches an entry already in the hash table, return the
    entry from the table.  Otherwise, return NULL.  */
 
diff --git a/lib/hash.h b/lib/hash.h
index e795cdc..00e2e1a 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -68,6 +68,7 @@ size_t hash_get_n_entries (const Hash_table *);
 size_t hash_get_max_bucket_length (const Hash_table *);
 bool hash_table_ok (const Hash_table *);
 void hash_print_statistics (const Hash_table *, FILE *);
+bool hash_contains (const Hash_table *, const void *);
 void *hash_lookup (const Hash_table *, const void *);
 
 /* Walking.  */
diff --git a/tests/test-hash.c b/tests/test-hash.c
index 1715033..756f0ae 100644
--- a/tests/test-hash.c
+++ b/tests/test-hash.c
@@ -164,7 +164,9 @@ main (int argc, char **argv)
         char *str = xstrdup ("a");
         insert_new (ht, "a");
         insert_new (ht, str);
+        ASSERT (hash_contains (ht, str));
         ASSERT (hash_lookup (ht, str) == str);
+        ASSERT (!hash_contains (ht, "b"));
         free (str);
       }
       hash_free (ht);