[svn] Merge of fix for bugs 20341 and 20410.

[wget] / src / hash.c

diff --git a/src/hash.c b/src/hash.c
index 36a90be82c9cffcc408f5a2846f4b775a12f7954..1ef11525d893cdabd6b7180fac3cd225647b9d3e 100644 (file)
--- a/src/hash.c
+++ b/src/hash.c
@@ -1,11 +1,11 @@
 /* Hash tables.
-   Copyright (C) 2000-2005 Free Software Foundation, Inc.
+   Copyright (C) 2000-2006 Free Software Foundation, Inc.
 
 This file is part of GNU Wget.
 
 GNU Wget 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 of the License, or (at
+the Free Software Foundation; either version 3 of the License, or (at
 your option) any later version.
 
 GNU Wget is distributed in the hope that it will be useful,
@@ -14,8 +14,7 @@ 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 Wget; if not, write to the Free Software Foundation, Inc.,
-51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+along with Wget.  If not, see <http://www.gnu.org/licenses/>.
 
 In addition, as a special exception, the Free Software Foundation
 gives permission to link the code of its release of Wget with the
@@ -50,8 +49,16 @@ so, delete this exception statement from your version.  */
 # define xnew_array(type, x) xmalloc (sizeof (type) * (x))
 # define xmalloc malloc
 # define xfree free
-# define countof(x) (sizeof (x) / sizeof ((x)[0]))
-# define TOLOWER(x) ('A' <= (x) && (x) <= 'Z' ? (x) - 32 : (x))
+# ifndef countof
+#  define countof(x) (sizeof (x) / sizeof ((x)[0]))
+# endif
+# include <ctype.h>
+# define TOLOWER(x) tolower ((unsigned char) (x))
+# if __STDC_VERSION__ >= 199901L
+#  include <stdint.h>  /* for uintptr_t */
+# else
+   typedef unsigned long uintptr_t;
+# endif
 #endif
 
 #include "hash.h"
@@ -170,7 +177,7 @@ struct hash_table {
    -1.  This is acceptable because it still allows the use of
    nonnegative integer keys.  */
 
-#define INVALID_PTR ((void *) ~0UL)
+#define INVALID_PTR ((void *) ~(uintptr_t) 0)
 #ifndef UCHAR_MAX
 # define UCHAR_MAX 0xff
 #endif
@@ -530,8 +537,8 @@ hash_table_for_each (struct hash_table *ht,
       }
 }
 
-/* Initiate iteration over HT.  Get the next entry using
-   hash_table_iter_next.  The typical loop looks like this:
+/* Initiate iteration over HT.  Entries are obtained with
+   hash_table_iter_next, a typical iteration loop looking like this:
 
        hash_table_iterator iter;
        for (hash_table_iterate (ht, &iter); hash_table_iter_next (&iter); )
@@ -553,8 +560,8 @@ hash_table_iterate (struct hash_table *ht, hash_table_iterator *iter)
    ITER->value respectively and 1 is returned.  When there are no more
    entries, 0 is returned.
 
-   The hash table must not be modified between calls to this
-   function.  */
+   If the hash table is modified between calls to this function, the
+   result is undefined.  */
 
 int
 hash_table_iter_next (hash_table_iterator *iter)
@@ -602,7 +609,7 @@ hash_table_count (const struct hash_table *ht)
      a hash function that returns 0 for any given object is a
      perfectly valid (albeit extremely bad) hash function.  A hash
      function that hashes a string by adding up all its characters is
-     another example of a valid (but quite bad) hash function.
+     another example of a valid (but still quite bad) hash function.
 
      It is not hard to make hash and test functions agree about
      equality.  For example, if the test function compares strings
@@ -610,24 +617,25 @@ hash_table_count (const struct hash_table *ht)
      characters when calculating the hash value.  That ensures that
      two strings differing only in case will hash the same.
 
-   - If you care about performance, choose a hash function with as
-     good "spreading" as possible.  A good hash function will use all
-     the bits of the input when calculating the hash, and will react
-     to even small changes in input with a completely different
-     output.  Finally, don't make the hash function itself overly
-     slow, because you'll be incurring a non-negligible overhead to
-     all hash table operations.  */
+   - To prevent performance degradation, choose a hash function with
+     as good "spreading" as possible.  A good hash function will use
+     all the bits of the input when calculating the hash, and will
+     react to even small changes in input with a completely different
+     output.  But don't make the hash function itself overly slow,
+     because you'll be incurring a non-negligible overhead to all hash
+     table operations.  */
 
 /*
  * Support for hash tables whose keys are strings.
  *
  */
    
-/* 31 bit hash function.  Taken from Gnome's glib, modified to use
+/* Base 31 hash function.  Taken from Gnome's glib, modified to use
    standard C types.
 
    We used to use the popular hash function from the Dragon Book, but
-   this one seems to perform much better.  */
+   this one seems to perform much better, both by being faster and by
+   generating less collisions.  */
 
 static unsigned long
 hash_string (const void *key)
@@ -708,7 +716,7 @@ make_nocase_string_hash_table (int items)
 unsigned long
 hash_pointer (const void *ptr)
 {
-  unsigned long key = (unsigned long) ptr;
+  uintptr_t key = (uintptr_t) ptr;
   key += (key << 12);
   key ^= (key >> 22);
   key += (key << 4);
@@ -717,7 +725,7 @@ hash_pointer (const void *ptr)
   key ^= (key >> 2);
   key += (key << 7);
   key ^= (key >> 12);
-#if SIZEOF_LONG > 4
+#if SIZEOF_VOID_P > 4
   key += (key << 44);
   key ^= (key >> 54);
   key += (key << 36);
@@ -727,7 +735,7 @@ hash_pointer (const void *ptr)
   key += (key << 39);
   key ^= (key >> 44);
 #endif
-  return key;
+  return (unsigned long) key;
 }
 
 static int