Mercurial > hg > octave-kai > gnulib-hg
changeset 11637:0b026e877c96
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 <ebb9@byu.net>
author | Eric Blake <ebb9@byu.net> |
---|---|
date | Thu, 18 Jun 2009 07:11:39 -0600 |
parents | 95fd221d763c |
children | bddc78d1a1c2 |
files | ChangeLog lib/hash.c tests/test-hash.c |
diffstat | 3 files changed, 45 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,10 @@ 2009-06-18 Eric Blake <ebb9@byu.net> + 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.
--- a/lib/hash.c +++ b/lib/hash.c @@ -479,6 +479,28 @@ *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 @@ 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_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)
--- a/tests/test-hash.c +++ b/tests/test-hash.c @@ -135,6 +135,18 @@ 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. */