diff options
| author | Andrea Canciani <ranma42@gmail.com> | 2011-11-14 10:24:47 +0100 |
|---|---|---|
| committer | Kristian Høgsberg <krh@bitplanet.net> | 2011-11-15 10:15:48 -0500 |
| commit | 3175e91efa4d4cb1847044f9ea4a8ef57fd6f39c (patch) | |
| tree | 48bbb695557597835abb9c861b85e347af65a2bb | |
| parent | e742dcc9ed4b22eb5191f7e8d2b7cd8011ed5893 (diff) | |
hash: Improve double hashing
Instead of artificially introducing collisions in the step value by
replacing 0 with 1 (which causes the value 1 to have twice the
frequency of any other value), the step value can simply be computed
as an uniformly distributed value in the range [1, rehash], extremes
included.
This is safe because any step value smaller than the hash modulus is
co-prime with it, hence induces an orbit which includes every integer
in [0, size - 1].
| -rw-r--r-- | src/wayland-hash.c | 8 |
1 files changed, 2 insertions, 6 deletions
diff --git a/src/wayland-hash.c b/src/wayland-hash.c index 1ec6be4..01ccd7c 100644 --- a/src/wayland-hash.c +++ b/src/wayland-hash.c @@ -176,9 +176,7 @@ hash_table_search(struct wl_hash_table *ht, uint32_t hash) return entry; } - double_hash = hash % ht->rehash; - if (double_hash == 0) - double_hash = 1; + double_hash = 1 + hash % ht->rehash; hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != hash % ht->size); @@ -277,9 +275,7 @@ wl_hash_table_insert(struct wl_hash_table *ht, uint32_t hash, void *data) return 0; } - double_hash = hash % ht->rehash; - if (double_hash == 0) - double_hash = 1; + double_hash = 1 + hash % ht->rehash; hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != hash % ht->size); |