From af254bfe03b99e242c8b12e8c76a76df1a1805cf Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Thu, 18 Jun 2009 07:11:39 -0600 Subject: [PATCH] hash: provide default callback functions * lib/hash.c (raw_hasher, raw_comparator): New functions. (hash_initialize): Use them as defaults. * tests/test-hash.c (main): Test this. Signed-off-by: Eric Blake --- ChangeLog | 5 +++++ lib/hash.c | 32 ++++++++++++++++++++++++++++---- tests/test-hash.c | 12 ++++++++++++ 3 files changed, 45 insertions(+), 4 deletions(-) diff --git a/ChangeLog b/ChangeLog index 09cc027ab..6861f6b19 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,10 @@ 2009-06-18 Eric Blake + hash: provide default callback functions + * lib/hash.c (raw_hasher, raw_comparator): New functions. + (hash_initialize): Use them as defaults. + * tests/test-hash.c (main): Test this. + hash: minor optimization * lib/hash.c (hash_lookup, hash_find_entry): Avoid function call when possible. diff --git a/lib/hash.c b/lib/hash.c index e464ce390..59f1ff0d0 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -479,6 +479,28 @@ hash_reset_tuning (Hash_tuning *tuning) *tuning = default_tuning; } +/* If the user passes a NULL hasher, we hash the raw pointer. */ +static size_t +raw_hasher (const void *data, size_t n) +{ + /* When hashing unique pointers, it is often the case that they were + generated by malloc and thus have the property that the low-order + bits are 0. As this tends to give poorer performance with small + tables, we rotate the pointer value before performing division, + in an attempt to improve hash quality. */ + size_t val = (size_t) data; + val = ((val >> 3) | (val << (CHAR_BIT * sizeof val - 3))) & SIZE_MAX; + return val % n; +} + +/* If the user passes a NULL comparator, we use pointer comparison. */ +static bool +raw_comparator (const void *a, const void *b) +{ + return a == b; +} + + /* For the given hash TABLE, check the user supplied tuning structure for reasonable values, and return true if there is no gross error with it. Otherwise, definitively reset the TUNING field to some acceptable default @@ -527,12 +549,12 @@ check_tuning (Hash_table *table) provided but the values requested are out of bounds or might cause rounding errors, return NULL. - The user-supplied HASHER function should be provided. It accepts two + The user-supplied HASHER function, when not NULL, accepts two arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a slot number for that entry which should be in the range 0..TABLE_SIZE-1. This slot number is then returned. - The user-supplied COMPARATOR function should be provided. It accepts two + The user-supplied COMPARATOR function, when not NULL, accepts two arguments pointing to user data, it then returns true for a pair of entries that compare equal, or false otherwise. This function is internally called on entries which are already known to hash to the same bucket index, @@ -553,8 +575,10 @@ hash_initialize (size_t candidate, const Hash_tuning *tuning, { Hash_table *table; - if (hasher == NULL || comparator == NULL) - return NULL; + if (hasher == NULL) + hasher = raw_hasher; + if (comparator == NULL) + comparator = raw_comparator; table = malloc (sizeof *table); if (table == NULL) diff --git a/tests/test-hash.c b/tests/test-hash.c index 73a351206..6bb965298 100644 --- a/tests/test-hash.c +++ b/tests/test-hash.c @@ -135,6 +135,18 @@ main (void) hash_clear (ht); ASSERT (hash_get_n_entries (ht) == 0); hash_free (ht); + + /* Test pointer hashing. */ + ht = hash_initialize (sz, NULL, NULL, NULL, NULL); + ASSERT (ht); + { + char *str = xstrdup ("a"); + insert_new (ht, "a"); + insert_new (ht, str); + ASSERT (hash_lookup (ht, str) == str); + free (str); + } + hash_free (ht); } /* Now, each entry is malloc'd. */ -- 2.11.0