[Mesa-dev] [PATCH 3/3] util: Use 32 bit integer hash function for pointers

[Jordan Justen]

On 2015-03-29 11:05:40, Thomas Helland wrote:
> Since a pointer is basically just an int we can use integer hashing.
> This one is taken from https://gist.github.com/badboy/6267743

There doesn't seem to be a license associated with this code, nor is
it indicated that it is public domain code.

-Jordan

> A google search seems to suggest this is a common and good algorithm.
> Since it operates 32 bits at a time it is really effective.
> assert that we are hashing 32bit aligned pointers.
> 
> Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
> ---
>  src/util/hash_table.c | 24 ++++++++++++++++++++++--
>  1 file changed, 22 insertions(+), 2 deletions(-)
> 
> diff --git a/src/util/hash_table.c b/src/util/hash_table.c
> index 24184c0..54d04ef 100644
> --- a/src/util/hash_table.c
> +++ b/src/util/hash_table.c
> @@ -393,6 +393,15 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
>     return NULL;
>  }
>  
> +static inline uint32_t
> +hash_32bit_int(uint32_t a) {
> +   a = (a ^ 61) ^ (a >> 16);
> +   a = a + (a << 3);
> +   a = a ^ (a >> 4);
> +   a = a * 0x27d4eb2d;
> +   a = a ^ (a >> 15);
> +   return a;
> +}
>  
>  /**
>   * Quick FNV-1a hash implementation based on:
> @@ -406,8 +415,19 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
>  uint32_t
>  _mesa_hash_data(const void *data, size_t size)
>  {
> -   return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
> -                                          data, size);
> +   uint32_t hash = _mesa_fnv32_1a_offset_bias;
> +   const uint32_t *ints = (const uint32_t *) data;
> +
> +   assert((size % 4) == 0);
> +
> +   uint32_t i = size / 4;
> +
> +   while (i-- != 0) {
> +      hash ^= hash_32bit_int(*ints);
> +      ints++;
> +   }
> +
> +   return hash;
>  }
>  
>  /** FNV-1a string hash implementation */
> -- 
> 2.3.4
> 
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev