git.m6w6.name Git - awesomized/libmemcached/blob - libmemcached/murmur_hash.c

   1 #include "common.h"
   2
   3 /*
   4   "Murmur"hash provided by Austin, tanjent@gmail.com
   5 */
   6
   7 #define MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
   8
   9 uint32_t murmur_hash(char *key, size_t length)
  10 {
  11   const uint32_t m= 0x5bd1e995;
  12   const int r= 16;
  13   uint32_t h= length * m;
  14
  15   while(length >= 4)
  16   {
  17     uint32_t k = *(uint32_t*)key;
  18     MIX(h,k,m);
  19
  20     key += 4;
  21     length -= 4;
  22   }
  23
  24   if (length)
  25   {
  26     uint32_t k= 0;
  27
  28     switch(length)
  29     {
  30     case 3: k += key[2] << 16;
  31     case 2: k += key[1] << 8;
  32     case 1: k += key[0];
  33     };
  34     MIX(h,k,m);
  35   }
  36
  37   h *= m;
  38   h ^= h >> 10;
  39   h *= m;
  40   h ^= h >> 17;
  41
  42   return h;
  43 }