-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
}
}
-/* 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); )
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)
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
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)
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);
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);
key += (key << 39);
key ^= (key >> 44);
#endif
- return key;
+ return (unsigned long) key;
}
static int