[PATCH] hash: Improve double hashing

[Kristian Høgsberg]

On Mon, Nov 14, 2011 at 4:24 AM, Andrea Canciani <ranma42 at gmail.com> wrote:
> 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].

Right, I see, that's better.  And we're hashing against ht->size to
get the new hash_address, so we're still within the allocated table.

On a side note, I'm no longer using the hash table in core Wayland, so
I'll probably move it to wayland-demos where it's currently used.

thanks,
Kristian

> ---
>  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);
> --
> 1.7.5.4
>
> _______________________________________________
> wayland-devel mailing list
> wayland-devel at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/wayland-devel
>