From 3175e91efa4d4cb1847044f9ea4a8ef57fd6f39c Mon Sep 17 00:00:00 2001 From: Andrea Canciani Date: Mon, 14 Nov 2011 10:24:47 +0100 Subject: 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]. --- src/wayland-hash.c | 8 ++------ 1 file 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); -- cgit v1.2.3