src/ceph/src/include/hash.h

   1 #ifndef CEPH_HASH_H
   2 #define CEPH_HASH_H
   3
   4 #include "acconfig.h"
   5
   6 // Robert Jenkins' function for mixing 32-bit values
   7 // http://burtleburtle.net/bob/hash/evahash.html
   8 // a, b = random bits, c = input and output
   9
  10 #define hashmix(a,b,c) \
  11         a=a-b;  a=a-c;  a=a^(c>>13); \
  12         b=b-c;  b=b-a;  b=b^(a<<8);  \
  13         c=c-a;  c=c-b;  c=c^(b>>13); \
  14         a=a-b;  a=a-c;  a=a^(c>>12); \
  15         b=b-c;  b=b-a;  b=b^(a<<16); \
  16         c=c-a;  c=c-b;  c=c^(b>>5);  \
  17         a=a-b;  a=a-c;  a=a^(c>>3); \
  18         b=b-c;  b=b-a;  b=b^(a<<10); \
  19         c=c-a;  c=c-b;  c=c^(b>>15);
  20
  21
  22 //namespace ceph {
  23
  24 template <class _Key> struct rjhash { };
  25
  26 inline uint64_t rjhash64(uint64_t key) {
  27   key = (~key) + (key << 21); // key = (key << 21) - key - 1;
  28   key = key ^ (key >> 24);
  29   key = (key + (key << 3)) + (key << 8); // key * 265
  30   key = key ^ (key >> 14);
  31   key = (key + (key << 2)) + (key << 4); // key * 21
  32   key = key ^ (key >> 28);
  33   key = key + (key << 31);
  34   return key;
  35 }
  36
  37 inline uint32_t rjhash32(uint32_t a) {
  38   a = (a+0x7ed55d16) + (a<<12);
  39   a = (a^0xc761c23c) ^ (a>>19);
  40   a = (a+0x165667b1) + (a<<5);
  41   a = (a+0xd3a2646c) ^ (a<<9);
  42   a = (a+0xfd7046c5) + (a<<3);
  43   a = (a^0xb55a4f09) ^ (a>>16);
  44   return a;
  45 }
  46
  47
  48 template<> struct rjhash<uint32_t> {
  49   inline size_t operator()(const uint32_t x) const {
  50     return rjhash32(x);
  51   }
  52 };
  53
  54 template<> struct rjhash<uint64_t> {
  55   inline size_t operator()(const uint64_t x) const {
  56     return rjhash64(x);
  57   }
  58 };
  59
  60 //}
  61
  62
  63
  64 #endif