hash: Improve double hashing
authorAndrea Canciani <ranma42@gmail.com>
Mon, 14 Nov 2011 09:24:47 +0000 (10:24 +0100)
committerKristian Høgsberg <krh@bitplanet.net>
Tue, 15 Nov 2011 15:15:48 +0000 (10:15 -0500)
commit3175e91efa4d4cb1847044f9ea4a8ef57fd6f39c
tree48bbb695557597835abb9c861b85e347af65a2bb
parente742dcc9ed4b22eb5191f7e8d2b7cd8011ed5893
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