gen-uni-tables: Say "gen-uni-tables.c" consistently.

[gnulib.git] / lib / hash.c

diff --git a/lib/hash.c b/lib/hash.c
index 4c359a4..4d76f76 100644 (file)
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -1,6 +1,6 @@
 /* hash - hashing table processing.
 
-   Copyright (C) 1998-2004, 2006-2007, 2009-2010 Free Software Foundation, Inc.
+   Copyright (C) 1998-2004, 2006-2007, 2009-2011 Free Software Foundation, Inc.
 
    Written by Jim Meyering, 1992.
 
@@ -27,7 +27,7 @@
 #include "hash.h"
 
 #include "bitrotate.h"
-#include "xalloc.h"
+#include "xalloc-oversized.h"
 
 #include <stdint.h>
 #include <stdio.h>
@@ -243,19 +243,26 @@ hash_print_statistics (const Hash_table *table, FILE *stream)
            (unsigned long int) max_bucket_length);
 }
 
+/* Hash KEY and return a pointer to the selected bucket.
+   If TABLE->hasher misbehaves, abort.  */
+static struct hash_entry *
+safe_hasher (const Hash_table *table, const void *key)
+{
+  size_t n = table->hasher (key, table->n_buckets);
+  if (! (n < table->n_buckets))
+    abort ();
+  return table->bucket + n;
+}
+
 /* If ENTRY matches an entry already in the hash table, return the
    entry from the table.  Otherwise, return NULL.  */
 
 void *
 hash_lookup (const Hash_table *table, const void *entry)
 {
-  struct hash_entry const *bucket
-    = table->bucket + table->hasher (entry, table->n_buckets);
+  struct hash_entry const *bucket = safe_hasher (table, entry);
   struct hash_entry const *cursor;
 
-  if (! (bucket < table->bucket_limit))
-    abort ();
-
   if (bucket->data == NULL)
     return NULL;
 
@@ -299,17 +306,18 @@ hash_get_first (const Hash_table *table)
 void *
 hash_get_next (const Hash_table *table, const void *entry)
 {
-  struct hash_entry const *bucket
-    = table->bucket + table->hasher (entry, table->n_buckets);
+  struct hash_entry const *bucket = safe_hasher (table, entry);
   struct hash_entry const *cursor;
 
-  if (! (bucket < table->bucket_limit))
-    abort ();
-
   /* Find next entry in the same bucket.  */
-  for (cursor = bucket; cursor; cursor = cursor->next)
-    if (cursor->data == entry && cursor->next)
-      return cursor->next->data;
+  cursor = bucket;
+  do
+    {
+      if (cursor->data == entry && cursor->next)
+        return cursor->next->data;
+      cursor = cursor->next;
+    }
+  while (cursor != NULL);
 
   /* Find first entry in any subsequent bucket.  */
   while (++bucket < table->bucket_limit)
@@ -782,13 +790,9 @@ static void *
 hash_find_entry (Hash_table *table, const void *entry,
                  struct hash_entry **bucket_head, bool delete)
 {
-  struct hash_entry *bucket
-    = table->bucket + table->hasher (entry, table->n_buckets);
+  struct hash_entry *bucket = safe_hasher (table, entry);
   struct hash_entry *cursor;
 
-  if (! (bucket < table->bucket_limit))
-    abort ();
-
   *bucket_head = bucket;
 
   /* Test for empty bucket.  */
@@ -873,10 +877,7 @@ transfer_entries (Hash_table *dst, Hash_table *src, bool safe)
         for (cursor = bucket->next; cursor; cursor = next)
           {
             data = cursor->data;
-            new_bucket = (dst->bucket + dst->hasher (data, dst->n_buckets));
-
-            if (! (new_bucket < dst->bucket_limit))
-              abort ();
+            new_bucket = safe_hasher (dst, data);
 
             next = cursor->next;
 
@@ -903,10 +904,7 @@ transfer_entries (Hash_table *dst, Hash_table *src, bool safe)
         bucket->next = NULL;
         if (safe)
           continue;
-        new_bucket = (dst->bucket + dst->hasher (data, dst->n_buckets));
-
-        if (! (new_bucket < dst->bucket_limit))
-          abort ();
+        new_bucket = safe_hasher (dst, data);
 
         if (new_bucket->data)
           {
@@ -1032,13 +1030,20 @@ hash_rehash (Hash_table *table, size_t candidate)
    hash_insert, the only way to distinguish those cases is to compare
    the return value and ENTRY.  That works only when you can have two
    different ENTRY values that point to data that compares "equal".  Thus,
-   when the ENTRY value is a simple scalar, you must use hash_insert0.  */
+   when the ENTRY value is a simple scalar, you must use hash_insert0.
+   ENTRY must not be NULL.  */
 int
 hash_insert0 (Hash_table *table, void const *entry, void const **matched_ent)
 {
   void *data;
   struct hash_entry *bucket;
 
+  /* The caller cannot insert a NULL entry, since hash_lookup returns NULL
+     to indicate "not found", and hash_find_entry uses "bucket->data == NULL"
+     to indicate an empty bucket.  */
+  if (! entry)
+    abort ();
+
   /* If there's a matching entry already in the table, return that.  */
   if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
     {