deps/jemalloc/include/jemalloc/internal/hash.h

   1 /******************************************************************************/
   2 #ifdef JEMALLOC_H_TYPES
   3
   4 #endif /* JEMALLOC_H_TYPES */
   5 /******************************************************************************/
   6 #ifdef JEMALLOC_H_STRUCTS
   7
   8 #endif /* JEMALLOC_H_STRUCTS */
   9 /******************************************************************************/
  10 #ifdef JEMALLOC_H_EXTERNS
  11
  12 #endif /* JEMALLOC_H_EXTERNS */
  13 /******************************************************************************/
  14 #ifdef JEMALLOC_H_INLINES
  15
  16 #ifndef JEMALLOC_ENABLE_INLINE
  17 uint64_t        hash(const void *key, size_t len, uint64_t seed);
  18 #endif
  19
  20 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_HASH_C_))
  21 /*
  22  * The following hash function is based on MurmurHash64A(), placed into the
  23  * public domain by Austin Appleby.  See http://murmurhash.googlepages.com/ for
  24  * details.
  25  */
  26 JEMALLOC_INLINE uint64_t
  27 hash(const void *key, size_t len, uint64_t seed)
  28 {
  29         const uint64_t m = 0xc6a4a7935bd1e995LLU;
  30         const int r = 47;
  31         uint64_t h = seed ^ (len * m);
  32         const uint64_t *data = (const uint64_t *)key;
  33         const uint64_t *end = data + (len/8);
  34         const unsigned char *data2;
  35
  36         assert(((uintptr_t)key & 0x7) == 0);
  37
  38         while(data != end) {
  39                 uint64_t k = *data++;
  40
  41                 k *= m;
  42                 k ^= k >> r;
  43                 k *= m;
  44
  45                 h ^= k;
  46                 h *= m;
  47         }
  48
  49         data2 = (const unsigned char *)data;
  50         switch(len & 7) {
  51                 case 7: h ^= ((uint64_t)(data2[6])) << 48;
  52                 case 6: h ^= ((uint64_t)(data2[5])) << 40;
  53                 case 5: h ^= ((uint64_t)(data2[4])) << 32;
  54                 case 4: h ^= ((uint64_t)(data2[3])) << 24;
  55                 case 3: h ^= ((uint64_t)(data2[2])) << 16;
  56                 case 2: h ^= ((uint64_t)(data2[1])) << 8;
  57                 case 1: h ^= ((uint64_t)(data2[0]));
  58                         h *= m;
  59         }
  60
  61         h ^= h >> r;
  62         h *= m;
  63         h ^= h >> r;
  64
  65         return (h);
  66 }
  67 #endif
  68
  69 #endif /* JEMALLOC_H_INLINES */
  70 /******************************************************************************/