src/common/hash.h

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