diff options
author | dormando <dormando@rydia.net> | 2014-04-16 23:13:04 -0700 |
---|---|---|
committer | dormando <dormando@rydia.net> | 2014-04-16 23:20:21 -0700 |
commit | 05ca809cc4bda62f0c778be29bfdf565fa39142d (patch) | |
tree | caaa069af4a731988f0d00cee92c804ce307617d /murmur3_hash.c | |
parent | d5d4c4909f37b9ec157bb418fa821530dfb66c9f (diff) | |
download | memcached-05ca809cc4bda62f0c778be29bfdf565fa39142d.tar.gz |
Make hash table algorithm selectable
jenkins hash is old. Lets try murmur3 to start! Default is the old one, so
people aren't surprised.
Diffstat (limited to 'murmur3_hash.c')
-rw-r--r-- | murmur3_hash.c | 124 |
1 files changed, 124 insertions, 0 deletions
diff --git a/murmur3_hash.c b/murmur3_hash.c new file mode 100644 index 0000000..4aa4f93 --- /dev/null +++ b/murmur3_hash.c @@ -0,0 +1,124 @@ +//----------------------------------------------------------------------------- +// MurmurHash3 was written by Austin Appleby, and is placed in the public +// domain. The author hereby disclaims copyright to this source code. + +// Note - The x86 and x64 versions do _not_ produce the same results, as the +// algorithms are optimized for their respective platforms. You can still +// compile and run any of them on any platform, but your performance with the +// non-native version will be less than optimal. + +#include "murmur3_hash.h" + +//----------------------------------------------------------------------------- +// Platform-specific functions and macros + +// Microsoft Visual Studio + +#if defined(_MSC_VER) + +#define FORCE_INLINE __forceinline + +#include <stdlib.h> + +#define ROTL32(x,y) _rotl(x,y) + +#define BIG_CONSTANT(x) (x) + +// Other compilers + +#else // defined(_MSC_VER) + +#define FORCE_INLINE inline __attribute__((always_inline)) + +static inline uint32_t rotl32 ( uint32_t x, int8_t r ) +{ + return (x << r) | (x >> (32 - r)); +} + +#define ROTL32(x,y) rotl32(x,y) + +#define BIG_CONSTANT(x) (x##LLU) + +#endif // !defined(_MSC_VER) + +//----------------------------------------------------------------------------- +// Block read - if your platform needs to do endian-swapping or can only +// handle aligned reads, do the conversion here + +static FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i ) +{ + return p[i]; +} + +//----------------------------------------------------------------------------- +// Finalization mix - force all bits of a hash block to avalanche + +static FORCE_INLINE uint32_t fmix32 ( uint32_t h ) +{ + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + + return h; +} + +//----------------------------------------------------------------------------- + +/* Defintion modified slightly from the public domain interface (no seed + + * return value */ +uint32_t MurmurHash3_x86_32 ( const void * key, size_t length) +{ + const uint8_t * data = (const uint8_t*)key; + const int nblocks = length / 4; + + uint32_t h1 = 0; + + uint32_t c1 = 0xcc9e2d51; + uint32_t c2 = 0x1b873593; + + //---------- + // body + + const uint32_t * blocks = (const uint32_t *)(data + nblocks*4); + + for(int i = -nblocks; i; i++) + { + uint32_t k1 = getblock32(blocks,i); + + k1 *= c1; + k1 = ROTL32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = ROTL32(h1,13); + h1 = h1*5+0xe6546b64; + } + + //---------- + // tail + + const uint8_t * tail = (const uint8_t*)(data + nblocks*4); + + uint32_t k1 = 0; + + switch(length & 3) + { + case 3: k1 ^= tail[2] << 16; + case 2: k1 ^= tail[1] << 8; + case 1: k1 ^= tail[0]; + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; + }; + + //---------- + // finalization + + h1 ^= length; + + h1 = fmix32(h1); + + //*(uint32_t*)out = h1; + return h1; +} + |