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 <stddef.h>
  28 #include <stdint.h>
  29 #include <urcu/compiler.h>
  30
  31 /*
  32  * Hash function
  33  * Source: http://burtleburtle.net/bob/c/lookup3.c
  34  * Originally Public Domain
  35  */
  36
  37 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
  38
  39 #define mix(a, b, c) \
  40 do { \
  41         a -= c; a ^= rot(c,  4); c += b; \
  42         b -= a; b ^= rot(a,  6); a += c; \
  43         c -= b; c ^= rot(b,  8); b += a; \
  44         a -= c; a ^= rot(c, 16); c += b; \
  45         b -= a; b ^= rot(a, 19); a += c; \
  46         c -= b; c ^= rot(b,  4); b += a; \
  47 } while (0)
  48
  49 #define final(a, b, c) \
  50 { \
  51         c ^= b; c -= rot(b, 14); \
  52         a ^= c; a -= rot(c, 11); \
  53         b ^= a; b -= rot(a, 25); \
  54         c ^= b; c -= rot(b, 16); \
  55         a ^= c; a -= rot(c,  4);\
  56         b ^= a; b -= rot(a, 14); \
  57         c ^= b; c -= rot(b, 24); \
  58 }
  59
  60 static inline __attribute__((unused))
  61 uint32_t lttng_hash_u32(
  62         const uint32_t *k,      /* the key, an array of uint32_t values */
  63         size_t length,          /* the length of the key, in uint32_ts */
  64         uint32_t initval)       /* the previous hash, or an arbitrary value */
  65 {
  66         uint32_t a, b, c;
  67
  68         /* Set up the internal state */
  69         a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval;
  70
  71         /*----------------------------------------- handle most of the key */
  72         while (length > 3) {
  73                 a += k[0];
  74                 b += k[1];
  75                 c += k[2];
  76                 mix(a, b, c);
  77                 length -= 3;
  78                 k += 3;
  79         }
  80
  81         /*----------------------------------- handle the last 3 uint32_t's */
  82         switch (length) {       /* all the case statements fall through */
  83         case 3: c += k[2];
  84         case 2: b += k[1];
  85         case 1: a += k[0];
  86                 final(a, b, c);
  87         case 0:                 /* case 0: nothing left to add */
  88                 break;
  89         }
  90         /*---------------------------------------------- report the result */
  91         return c;
  92 }
  93
  94 static inline
  95 void lttng_hashword2(
  96         const uint32_t *k,      /* the key, an array of uint32_t values */
  97         size_t length,          /* the length of the key, in uint32_ts */
  98         uint32_t *pc,           /* IN: seed OUT: primary hash value */
  99         uint32_t *pb)           /* IN: more seed OUT: secondary hash value */
 100 {
 101         uint32_t a, b, c;
 102
 103         /* Set up the internal state */
 104         a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc;
 105         c += *pb;
 106
 107         /*----------------------------------------- handle most of the key */
 108         while (length > 3) {
 109                 a += k[0];
 110                 b += k[1];
 111                 c += k[2];
 112                 mix(a, b, c);
 113                 length -= 3;
 114                 k += 3;
 115         }
 116
 117         /*----------------------------------- handle the last 3 uint32_t's */
 118         switch (length) {       /* all the case statements fall through */
 119         case 3: c += k[2];
 120         case 2: b += k[1];
 121         case 1: a += k[0];
 122                 final(a, b, c);
 123         case 0:                 /* case 0: nothing left to add */
 124                 break;
 125         }
 126         /*---------------------------------------------- report the result */
 127         *pc = c;
 128         *pb = b;
 129 }
 130
 131 #if (CAA_BITS_PER_LONG == 32)
 132 static inline
 133 unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed)
 134 {
 135         unsigned int key = (unsigned int) _key;
 136
 137         assert(length == sizeof(unsigned int));
 138         return lttng_hash_u32(&key, 1, seed);
 139 }
 140 #else
 141 static inline
 142 unsigned long lttng_hash_mix(const void *_key, size_t length, unsigned long seed)
 143 {
 144         union {
 145                 uint64_t v64;
 146                 uint32_t v32[2];
 147         } v;
 148         union {
 149                 uint64_t v64;
 150                 uint32_t v32[2];
 151         } key;
 152
 153         assert(length == sizeof(unsigned long));
 154         v.v64 = (uint64_t) seed;
 155         key.v64 = (uint64_t) _key;
 156         lttng_hashword2(key.v32, 2, &v.v32[0], &v.v32[1]);
 157         return v.v64;
 158 }
 159 #endif
 160
 161 #endif /* _LTTNG_HASH_HELPER_H */