0df5f288b584882663c15530704af34c2d96c40c
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
29 #include <urcu/compiler.h>
33 * Source: http://burtleburtle.net/bob/c/lookup3.c
34 * Originally Public Domain
37 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
39 #define mix(a, b, c) \
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; \
49 #define final(a, b, c) \
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); \
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 */
68 /* Set up the internal state */
69 a
= b
= c
= 0xdeadbeef + (((uint32_t) length
) << 2) + initval
;
71 /*----------------------------------------- handle most of the key */
81 /*----------------------------------- handle the last 3 uint32_t's */
82 switch (length
) { /* all the case statements fall through */
87 case 0: /* case 0: nothing left to add */
90 /*---------------------------------------------- report the result */
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 */
103 /* Set up the internal state */
104 a
= b
= c
= 0xdeadbeef + ((uint32_t) (length
<< 2)) + *pc
;
107 /*----------------------------------------- handle most of the key */
117 /*----------------------------------- handle the last 3 uint32_t's */
118 switch (length
) { /* all the case statements fall through */
123 case 0: /* case 0: nothing left to add */
126 /*---------------------------------------------- report the result */
131 #if (CAA_BITS_PER_LONG == 32)
133 unsigned long lttng_hash_mix(const void *_key
, size_t length
, unsigned long seed
)
135 unsigned int key
= (unsigned int) _key
;
137 assert(length
== sizeof(unsigned int));
138 return lttng_hash_u32(&key
, 1, seed
);
142 unsigned long lttng_hash_mix(const void *_key
, size_t length
, unsigned long seed
)
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]);
161 #endif /* _LTTNG_HASH_HELPER_H */
This page took 0.046462 seconds and 3 git commands to generate.