bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: hash resizing bug


From: Jim Meyering
Subject: Re: hash resizing bug
Date: Thu, 18 Jun 2009 09:14:34 +0200

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 <address@hidden>
> 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 <address@hidden>
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  <address@hidden>
+
+       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  <address@hidden>

        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);




reply via email to

[Prev in Thread] Current Thread [Next in Thread]