[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:1.8.1.21) Gecko/20090302 Thunderbird/2.0.0.21 Mnenhy/0.7.6.666 |
-----BEGIN PGP SIGNED MESSAGE-----
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
-----BEGIN PGP SIGNATURE-----
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
iEYEARECAAYFAko6kzAACgkQ84KuGfSFAYCGfQCguTMBtGbMsCupmBXJLi8bxXGv
yKIAoLjfju/52Xz0FNF+CuhjEw7ph/ds
=XTpQ
-----END PGP SIGNATURE-----
>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. */
#if USE_OBSTACK
--
1.6.3.rc3.2.g4b51
- Re: hash resizing bug, (continued)
- Re: hash resizing bug, Jim Meyering, 2009/06/18
- Re: hash resizing bug, Eric Blake, 2009/06/18
- Re: hash resizing bug, Jim Meyering, 2009/06/18
- Re: hash resizing bug, Eric Blake, 2009/06/18
- hash and bitrotate (was: hash resizing bug), Eric Blake, 2009/06/18
- Re: hash and bitrotate, Eric Blake, 2009/06/18
- Re: hash and bitrotate, Jim Meyering, 2009/06/18
- Re: hash and bitrotate, Simon Josefsson, 2009/06/18
- Re: hash resizing bug, Jim Meyering, 2009/06/18
- Re: hash resizing bug, Ben Pfaff, 2009/06/18
- another hash cleanup (was: hash resizing bug),
Eric Blake <=
- Re: another hash cleanup, Jim Meyering, 2009/06/18
- Re: another hash cleanup, Eric Blake, 2009/06/18
- Re: another hash cleanup, Jim Meyering, 2009/06/18
- Re: another hash cleanup, Eric Blake, 2009/06/18
- Re: another hash cleanup, Jim Meyering, 2009/06/19
- Re: another hash cleanup, Eric Blake, 2009/06/19
- Re: another hash cleanup, Jim Meyering, 2009/06/19
- Re: another hash cleanup, Eric Blake, 2009/06/19
- Re: another hash cleanup, Jim Meyering, 2009/06/19
- Re: another hash cleanup, Eric Blake, 2009/06/19