[Top][All Lists]

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

another hash cleanup (was: hash resizing bug)

From: Eric Blake
Subject: another hash cleanup (was: hash resizing bug)
Date: Thu, 18 Jun 2009 13:19:12 -0600
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv: Gecko/20090302 Thunderbird/ Mnenhy/

Hash: SHA1

According to Eric Blake on 6/18/2009 7:29 AM:
> Here's two simple patches.  I'm committing the first, as there should be
> enough cases where you end up searching for an element already known to be
> hashed, where making an indirect function call is needless overhead
> (particularly if the comparator function is expensive, and neglected to do
> the pointer comparison filter itself).  And by documenting this behavior,
> the user's comparator functions can now be safely rewritten to avoid the
> pointer comparison filter.

How about this simple patch - since the user can request hash_rehash with
any size, it is possible to call hash_rehash when it is otherwise a no-op.
 This could also happen, for example, with custom tuning parameters that
shrink the table; eventually, the shrink will pick a value that gets
rounded back up to the same prime number as the current size.

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

>From 86514ea5ebf71c35726c21ae077f2a3a10e196e2 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Thu, 18 Jun 2009 13:18:34 -0600
Subject: [PATCH] hash: avoid no-op rehashing

* lib/hash.c (hash_rehash): Recognize useless rehash attempts.

Signed-off-by: Eric Blake <address@hidden>
 ChangeLog  |    3 +++
 lib/hash.c |    2 ++
 2 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 6861f6b..e7698b7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,8 @@
 2009-06-18  Eric Blake  <address@hidden>

+       hash: avoid no-op rehashing
+       * lib/hash.c (hash_rehash): Recognize useless rehash attempts.
        hash: provide default callback functions
        * lib/hash.c (raw_hasher, raw_comparator): New functions.
        (hash_initialize): Use them as defaults.
diff --git a/lib/hash.c b/lib/hash.c
index 59f1ff0..f2123b4 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -862,6 +862,8 @@ hash_rehash (Hash_table *table, size_t candidate)
                               table->comparator, table->data_freer);
   if (new_table == NULL)
     return false;
+  if (new_table->n_buckets == table->n_buckets)
+    return true;

   /* Merely reuse the extra old space into the new table.  */

reply via email to

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