6c8008a06fcf7fb1426ca85b13f5986fab62e52d
2 * SPDX-License-Identifier: LGPL-2.1-only
4 * Copyright (C) 2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
6 * LTTng hash table helpers.
9 #ifndef _LTTNG_HASH_HELPER_H
10 #define _LTTNG_HASH_HELPER_H
15 #include <urcu/compiler.h>
19 * Source: http://burtleburtle.net/bob/c/lookup3.c
20 * Originally Public Domain
23 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
25 #define mix(a, b, c) \
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; \
35 #define final(a, b, c) \
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); \
46 static inline __attribute__((unused
))
47 uint32_t lttng_hash_u32(
48 const uint32_t *k
, /* the key, an array of uint32_t values */
49 size_t length
, /* the length of the key, in uint32_ts */
50 uint32_t initval
) /* the previous hash, or an arbitrary value */
54 /* Set up the internal state */
55 a
= b
= c
= 0xdeadbeef + (((uint32_t) length
) << 2) + initval
;
57 /*----------------------------------------- handle most of the key */
67 /*----------------------------------- handle the last 3 uint32_t's */
68 switch (length
) { /* all the case statements fall through */
73 case 0: /* case 0: nothing left to add */
76 /*---------------------------------------------- report the result */
82 const uint32_t *k
, /* the key, an array of uint32_t values */
83 size_t length
, /* the length of the key, in uint32_ts */
84 uint32_t *pc
, /* IN: seed OUT: primary hash value */
85 uint32_t *pb
) /* IN: more seed OUT: secondary hash value */
89 /* Set up the internal state */
90 a
= b
= c
= 0xdeadbeef + ((uint32_t) (length
<< 2)) + *pc
;
93 /*----------------------------------------- handle most of the key */
103 /*----------------------------------- handle the last 3 uint32_t's */
104 switch (length
) { /* all the case statements fall through */
109 case 0: /* case 0: nothing left to add */
112 /*---------------------------------------------- report the result */
117 #if (CAA_BITS_PER_LONG == 32)
119 unsigned long lttng_hash_mix(const void *_key
, size_t length
, unsigned long seed
)
121 unsigned int key
= (unsigned int) _key
;
123 assert(length
== sizeof(unsigned int));
124 return lttng_hash_u32(&key
, 1, seed
);
128 unsigned long lttng_hash_mix(const void *_key
, size_t length
, unsigned long seed
)
139 assert(length
== sizeof(unsigned long));
140 v
.v64
= (uint64_t) seed
;
141 key
.v64
= (uint64_t) _key
;
142 lttng_hashword2(key
.v32
, 2, &v
.v32
[0], &v
.v32
[1]);
147 #endif /* _LTTNG_HASH_HELPER_H */
This page took 0.055277 seconds and 3 git commands to generate.