Eric Blake wrote:
> Jim Meyering <jim <at> meyering.net> writes:
>
>> > /* If the growth threshold of the buckets in use has been reached,
> increase
>> > the table size and rehash. There's no point in checking the number
>> > of
>> > entries: if the hashing function is ill-conditioned, rehashing is
>> > not
>> > @@ -1057,6 +1031,32 @@ hash_insert (Hash_table *table, const void *entry)
>> > }
>> > }
>>
>> You can't use a pre-rehash "bucket" here (after rehash),
>> since it is no longer valid.
>>
>> Considering the cost of rehashing (and its relative infrequency),
>> one more hash_find_entry won't even show up on the radar.
>
> Good catch. So the simple code motion was a bit too simple; here's the
> updated
> patch (and I've now run it through the same m4 test that found the original
> problem):
>
>
> From: Eric Blake <e...@byu.net>
> Date: Wed, 17 Jun 2009 13:01:41 -0600
> Subject: [PATCH] hash: check for resize before insertion
>
> * lib/hash.c (hash_insert): Check whether bucket usage exceeds
> threshold before insertion, so that a pathological hash_rehash
> that fills every bucket can still trigger another rehash.
Thanks.
I've pushed that after a small change to the testing code
(this diff is ignoring the indentation changes):
commit ae156c0bf8058d3c1568c1ed573a1319a451ac7e
Author: Jim Meyering <meyer...@redhat.com>
Date: Thu Jun 18 07:36:54 2009 +0200
hash-tests: add a loop around the small tests
* tests/test-hash.c (main): Repeat small tests with selected
small initial table sizes.
diff --git a/ChangeLog b/ChangeLog
index e695428..1d69f22 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2009-06-18 Jim Meyering <meyer...@redhat.com>
+
+ hash-tests: add a loop around the small tests
+ * tests/test-hash.c (main): Repeat small tests with selected
+ small initial table sizes.
+
2009-06-17 Eric Blake <e...@byu.net>
hash: minor cleanups
diff --git a/tests/test-hash.c b/tests/test-hash.c
index e7066c0..2266545 100644
--- a/tests/test-hash.c
+++ b/tests/test-hash.c
@@ -29,6 +29,7 @@
#include <unistd.h>
#define STREQ(a, b) (strcmp (a, b) == 0)
+#define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
#define ASSERT(expr) \
do \
@@ -80,10 +81,14 @@ int
main (void)
{
unsigned int i;
- Hash_table *ht = hash_initialize (53, NULL, hash_pjw,
- hash_compare_strings, NULL);
+ unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
+ Hash_table *ht;
Hash_tuning tuning;
+ for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
+ {
+ size_t sz = table_size[i];
+ ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
ASSERT (ht);
insert_new (ht, "a");
{
@@ -116,7 +121,7 @@ main (void)
hash_clear (ht);
hash_free (ht);
- ht = hash_initialize (53, NULL, hash_pjw, hash_compare_strings, NULL);
+ ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
ASSERT (ht);
insert_new (ht, "z");
@@ -129,6 +134,7 @@ main (void)
hash_clear (ht);
ASSERT (hash_get_n_entries (ht) == 0);
hash_free (ht);
+ }
/* Now, each entry is malloc'd. */
ht = hash_initialize (4651, NULL, hash_pjw, hash_compare_strings,
hash_freer);
