liblttng-ust/lttng-hash-helper.h

   1 #ifndef _LTTNG_HASH_HELPER_H
   2 #define _LTTNG_HASH_HELPER_H
   3
   4 /*
   5  * lttng-hash-helper.h
   6  *
   7  * LTTng hash table helpers.
   8  *
   9  * Copyright (C) 2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; only
  14  * version 2.1 of the License.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  24  */
  25
  26 #include <assert.h>
  27 #include <stdint.h>
  28 #include <urcu/compiler.h>
  29
  30 /*
  31  * Hash function
  32  * Source: http://burtleburtle.net/bob/c/lookup3.c
  33  * Originally Public Domain
  34  */
  35
  36 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
  37
  38 #define mix(a, b, c) \
  39 do { \
  40         a -= c; a ^= rot(c,  4); c += b; \
  41         b -= a; b ^= rot(a,  6); a += c; \
  42         c -= b; c ^= rot(b,  8); b += a; \
  43         a -= c; a ^= rot(c, 16); c += b; \
  44         b -= a; b ^= rot(a, 19); a += c; \
  45         c -= b; c ^= rot(b,  4); b += a; \
  46 } while (0)
  47
  48 #define final(a, b, c) \
  49 { \
  50         c ^= b; c -= rot(b, 14); \
  51         a ^= c; a -= rot(c, 11); \
  52         b ^= a; b -= rot(a, 25); \
  53         c ^= b; c -= rot(b, 16); \
  54         a ^= c; a -= rot(c,  4);\
  55         b ^= a; b -= rot(a, 14); \
  56         c ^= b; c -= rot(b, 24); \
  57 }
  58
  59 static inline __attribute__((unused))
  60 uint32_t lttng_hash_u32(
  61         const uint32_t *k,      /* the key, an array of uint32_t values */
  62         size_t length,          /* the length of the key, in uint32_ts */
  63         uint32_t initval)       /* the previous hash, or an arbitrary value */
  64 {
  65         uint32_t a, b, c;
  66
  67         /* Set up the internal state */
  68         a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
  69
  70         /*----------------------------------------- handle most of the key */
  71         while (length > 3) {
  72                 a += k[0];
  73                 b += k[1];
  74                 c += k[2];
  75                 mix(a, b, c);
  76                 length -= 3;
  77                 k += 3;
  78         }
  79
  80         /*----------------------------------- handle the last 3 uint32_t's */
  81         switch (length) {       /* all the case statements fall through */
  82         case 3: c += k[2];
  83         case 2: b += k[1];
  84         case 1: a += k[0];
  85                 final(a, b, c);
  86         case 0:                 /* case 0: nothing left to add */
  87                 break;
  88         }
  89         /*---------------------------------------------- report the result */
  90         return c;
  91 }
  92
  93 static inline
  94 void lttng_hashword2(
  95         const uint32_t *k,      /* the key, an array of uint32_t values */
  96         size_t length,          /* the length of the key, in uint32_ts */
  97         uint32_t *pc,           /* IN: seed OUT: primary hash value */
  98         uint32_t *pb)           /* IN: more seed OUT: secondary hash value */
  99 {
 100         uint32_t a, b, c;
 101
 102         /* Set up the internal state */
 103         a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
 104         c += *pb;
 105
 106         /*----------------------------------------- handle most of the key */
 107         while (length > 3) {
 108                 a += k[0];
 109                 b += k[1];
 110                 c += k[2];
 111                 mix(a, b, c);
 112                 length -= 3;
 113                 k += 3;
 114         }
 115
 116         /*----------------------------------- handle the last 3 uint32_t's */
 117         switch (length) {       /* all the case statements fall through */
 118         case 3: c += k[2];
 119         case 2: b += k[1];
 120         case 1: a += k[0];
 121                 final(a, b, c);
 122         case 0:                 /* case 0: nothing left to add */
 123                 break;
 124         }
 125         /*---------------------------------------------- report the result */
 126         *pc = c;
 127         *pb = b;
 128 }
 129
 130 #if (CAA_BITS_PER_LONG == 32)
 131 static inline
 132 unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed)
 133 {
 134         unsigned int key = (unsigned int) _key;
 135
 136         assert(length == sizeof(unsigned int));
 137         return lttng_hash_u32(&key, 1, seed);
 138 }
 139 #else
 140 static inline
 141 unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed)
 142 {
 143         union {
 144                 uint64_t v64;
 145                 uint32_t v32[2];
 146         } v;
 147         union {
 148                 uint64_t v64;
 149                 uint32_t v32[2];
 150         } key;
 151
 152         assert(length == sizeof(unsigned long));
 153         v.v64 = (uint64_t) seed;
 154         key.v64 = (uint64_t) _key;
 155         lttng_hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
 156         return v.v64;
 157 }
 158 #endif
 159
 160 #endif /* _LTTNG_HASH_HELPER_H */