[svn] Allow NULL/0 as hash table keys.

[wget] / src / hash.c

diff --git a/src/hash.c b/src/hash.c
index 91abee481eb9d74c1b609f3f9673da9d99870bc7..ed8cac1e3c3f086c1eb09271a11af7e5b3027ca7 100644 (file)
--- a/src/hash.c
+++ b/src/hash.c
@@ -145,12 +145,13 @@ so, delete this exception statement from your version.  */
    hash_table_remove is careful to rehash the mappings that follow the
    deleted one.  */
 
-/* When hash table's fullness exceeds this threshold, the hash table
-   is resized.  */
-#define HASH_FULLNESS_THRESHOLD 0.75
+/* Maximum allowed fullness: when hash table's fullness exceeds this
+   value, the table is resized.  */
+#define HASH_MAX_FULLNESS 0.75
 
-/* The hash table size is multiplied by this factor with each resize.
-   This guarantees infrequent resizes.  */
+/* The hash table size is multiplied by this factor (and then rounded
+   to the next prime) with each resize.  This guarantees infrequent
+   resizes.  */
 #define HASH_RESIZE_FACTOR 2
 
 struct mapping {
@@ -174,9 +175,10 @@ struct hash_table {
   struct mapping *mappings;    /* the array of mapping pairs. */
 };
 
-/* We use NULL key to mark a mapping as empty.  It is consequently
-   illegal to store NULL keys.  */
-#define NON_EMPTY(mp) (mp->key != NULL)
+/* We use all-bit-set marker to mean that a mapping is empty.  It is
+   (hopefully) illegal as a pointer, and it allows the users to use
+   NULL (as well as any non-negative integer) as key.  */
+#define NON_EMPTY(mp) (mp->key != (void *)~(unsigned long)0)
 
 /* "Next" mapping is the mapping after MP, but wrapping back to
    MAPPINGS when MP would reach MAPPINGS+SIZE.  */
@@ -237,6 +239,9 @@ prime_size (int size, int *prime_offset)
   return 0;
 }
 
+static unsigned long ptrhash PARAMS ((const void *));
+static int ptrcmp PARAMS ((const void *, const void *));
+
 /* Create a hash table with hash function HASH_FUNCTION and test
    function TEST_FUNCTION.  The table is empty (its count is 0), but
    pre-allocated to store at least ITEMS items.
@@ -263,24 +268,27 @@ hash_table_new (int items,
                int (*test_function) (const void *, const void *))
 {
   int size;
-  struct hash_table *ht
-    = (struct hash_table *)xmalloc (sizeof (struct hash_table));
+  struct hash_table *ht = xnew (struct hash_table);
 
   ht->hash_function = hash_function ? hash_function : ptrhash;
   ht->test_function = test_function ? test_function : ptrcmp;
 
+  /* If the size of struct hash_table ever becomes a concern, this
+     field can go.  (Wget doesn't create many hashes.)  */
   ht->prime_offset = 0;
 
   /* Calculate the size that ensures that the table will store at
      least ITEMS keys without the need to resize.  */
-  size = 1 + items / HASH_FULLNESS_THRESHOLD;
+  size = 1 + items / HASH_MAX_FULLNESS;
   size = prime_size (size, &ht->prime_offset);
   ht->size = size;
-  ht->resize_threshold = size * HASH_FULLNESS_THRESHOLD;
+  ht->resize_threshold = size * HASH_MAX_FULLNESS;
   /*assert (ht->resize_threshold >= items);*/
 
-  ht->mappings = xmalloc (ht->size * sizeof (struct mapping));
-  memset (ht->mappings, '\0', ht->size * sizeof (struct mapping));
+  ht->mappings = xnew_array (struct mapping, ht->size);
+  /* Mark mappings as empty.  We use 0xff rather than 0 to mark empty
+     keys because it allows us to store NULL keys to the table.  */
+  memset (ht->mappings, 255, size * sizeof (struct mapping));
 
   ht->count = 0;
 
@@ -380,19 +388,19 @@ grow_hash_table (struct hash_table *ht)
 #endif
 
   ht->size = newsize;
-  ht->resize_threshold = newsize * HASH_FULLNESS_THRESHOLD;
+  ht->resize_threshold = newsize * HASH_MAX_FULLNESS;
 
-  mappings = xmalloc (ht->size * sizeof (struct mapping));
-  memset (mappings, '\0', ht->size * sizeof (struct mapping));
+  mappings = xnew_array (struct mapping, newsize);
+  memset (mappings, 255, newsize * sizeof (struct mapping));
   ht->mappings = mappings;
 
   for (mp = old_mappings; mp < old_end; mp++)
     if (NON_EMPTY (mp))
       {
        struct mapping *new_mp = mappings + HASH_POSITION (ht, mp->key);
-       /* We don't need to test for uniqueness of keys because all
-          the keys come from the hash table and are therefore known
-          to be unique.  */
+       /* We don't need to test for uniqueness of keys because they
+          come from the hash table and are therefore known to be
+          unique.  */
        LOOP_NON_EMPTY (new_mp, mappings, newsize)
          ;
        *new_mp = *mp;
@@ -615,7 +623,7 @@ make_nocase_string_hash_table (int items)
    pointer identity.  (Common Lisp calls them EQ hash tables, and Java
    calls them IdentityHashMaps.)  */
 
-unsigned long
+static unsigned long
 ptrhash (const void *ptr)
 {
   unsigned long key = (unsigned long)ptr;
@@ -640,29 +648,11 @@ ptrhash (const void *ptr)
   return key;
 }
 
-int
+static int
 ptrcmp (const void *ptr1, const void *ptr2)
 {
   return ptr1 == ptr2;
 }
-
-#if 0
-/* Currently unused: hashing of integers. */
-
-unsigned long
-inthash (unsigned int key)
-{
-  key += (key << 12);
-  key ^= (key >> 22);
-  key += (key << 4);
-  key ^= (key >> 9);
-  key += (key << 10);
-  key ^= (key >> 2);
-  key += (key << 7);
-  key ^= (key >> 12);
-  return key;
-}
-#endif
 \f
 #ifdef STANDALONE