1 #ifndef _LTTNG_HASH_HELPER_H
2 #define _LTTNG_HASH_HELPER_H
7 * LTTng hash table helpers.
9 * Copyright (C) 2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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.
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.
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
28 #include <urcu/compiler.h>
32 * Source: http://burtleburtle.net/bob/c/lookup3.c
33 * Originally Public Domain
36 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
38 #define mix(a, b, c) \
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; \
48 #define final(a, b, c) \
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); \
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 */
67 /* Set up the internal state */
68 a
= b
= c
= 0xdeadbeef + (((uint32_t) length
) << 2) + initval
;
70 /*----------------------------------------- handle most of the key */
80 /*----------------------------------- handle the last 3 uint32_t's */
81 switch (length
) { /* all the case statements fall through */
86 case 0: /* case 0: nothing left to add */
89 /*---------------------------------------------- report the result */
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 */
102 /* Set up the internal state */
103 a
= b
= c
= 0xdeadbeef + ((uint32_t) (length
<< 2)) + *pc
;
106 /*----------------------------------------- handle most of the key */
116 /*----------------------------------- handle the last 3 uint32_t's */
117 switch (length
) { /* all the case statements fall through */
122 case 0: /* case 0: nothing left to add */
125 /*---------------------------------------------- report the result */
130 #if (CAA_BITS_PER_LONG == 32)
132 unsigned long lttng_hash_mix(const void *_key
, size_t length
, unsigned long seed
)
134 unsigned int key
= (unsigned int) _key
;
136 assert(length
== sizeof(unsigned int));
137 return lttng_hash_u32(&key
, 1, seed
);
141 unsigned long lttng_hash_mix(const void *_key
, size_t length
, unsigned long seed
)
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]);
160 #endif /* _LTTNG_HASH_HELPER_H */
This page took 0.041608 seconds and 4 git commands to generate.