6 #include <ccan/build_assert/build_assert.h>
8 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
10 * http://burtleburtle.net/bob/c/lookup3.c
14 * hash - fast hash of an array for internal use
15 * @p: the array or pointer to first element
16 * @num: the number of elements to hash
17 * @base: the base number to roll into the hash (usually 0)
19 * The memory region pointed to by p is combined with the base to form
22 * This hash will have different results on different machines, so is
23 * only useful for internal hashes (ie. not hashes sent across the
24 * network or saved to disk).
26 * It may also change with future versions: it could even detect at runtime
27 * what the fastest hash to use is.
29 * See also: hash64, hash_stable.
32 * #include "hash/hash.h"
36 * // Simple demonstration: idential strings will have the same hash, but
37 * // two different strings will probably not.
38 * int main(int argc, char *argv[])
40 * uint32_t hash1, hash2;
43 * err(1, "Usage: %s <string1> <string2>", argv[0]);
45 * hash1 = hash(argv[1], strlen(argv[1]), 0);
46 * hash2 = hash(argv[2], strlen(argv[2]), 0);
47 * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
51 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
54 * hash_stable - hash of an array for external use
55 * @p: the array or pointer to first element
56 * @num: the number of elements to hash
57 * @base: the base number to roll into the hash (usually 0)
59 * The array of simple integer types pointed to by p is combined with
60 * the base to form a 32-bit hash.
62 * This hash will have the same results on different machines, so can
63 * be used for external hashes (ie. hashes sent across the network or
64 * saved to disk). The results will not change in future versions of
67 * Note that it is only legal to hand an array of simple integer types
68 * to this hash (ie. char, uint16_t, int64_t, etc). In these cases,
69 * the same values will have the same hash result, even though the
70 * memory representations of integers depend on the machine
77 * #include "hash/hash.h"
81 * int main(int argc, char *argv[])
84 * err(1, "Usage: %s <string-to-hash>", argv[0]);
86 * printf("Hash stable result is %u\n",
87 * hash_stable(argv[1], strlen(argv[1]), 0));
91 #define hash_stable(p, num, base) \
92 (EXPR_BUILD_ASSERT(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \
93 || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
94 sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base)) \
95 : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base)) \
96 : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base)) \
97 : hash_stable_8((p), (num), (base)))
100 * hash_u32 - fast hash an array of 32-bit values for internal use
101 * @key: the array of uint32_t
102 * @num: the number of elements to hash
103 * @base: the base number to roll into the hash (usually 0)
105 * The array of uint32_t pointed to by @key is combined with the base
106 * to form a 32-bit hash. This is 2-3 times faster than hash() on small
107 * arrays, but the advantage vanishes over large hashes.
109 * This hash will have different results on different machines, so is
110 * only useful for internal hashes (ie. not hashes sent across the
111 * network or saved to disk).
113 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
115 /* Our underlying operations. */
116 uint32_t hash_any(const void *key, size_t length, uint32_t base);
117 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base);
118 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base);
119 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base);
120 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base);
121 uint64_t hash64_any(const void *key, size_t length, uint32_t base);
122 uint64_t hash64_stable_64(const void *key, size_t n, uint32_t base);
123 uint64_t hash64_stable_32(const void *key, size_t n, uint32_t base);
124 uint64_t hash64_stable_16(const void *key, size_t n, uint32_t base);
125 uint64_t hash64_stable_8(const void *key, size_t n, uint32_t base);
128 * hash_string - very fast hash of an ascii string
129 * @str: the nul-terminated string
131 * The string is hashed, using a hash function optimized for ASCII and
132 * similar strings. It's weaker than the other hash functions.
134 * This hash may have different results on different machines, so is
135 * only useful for internal hashes (ie. not hashes sent across the
136 * network or saved to disk). The results will be different from the
137 * other hash functions in this module, too.
139 static inline uint32_t hash_string(const char *string)
141 /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
142 * It's a little faster than the (much better) lookup3 hash(): 56ns vs
143 * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
146 for (ret = 0; *string; string++)
147 ret = (ret << 5) - ret + *string;
153 * hash_pointer - hash a pointer for internal use
154 * @p: the pointer value to hash
155 * @base: the base number to roll into the hash (usually 0)
157 * The pointer p (not what p points to!) is combined with the base to form
160 * This hash will have different results on different machines, so is
161 * only useful for internal hashes (ie. not hashes sent across the
162 * network or saved to disk).
165 * #include "hash/hash.h"
167 * // Code to keep track of memory regions.
169 * struct region *chain;
173 * // We keep a simple hash table.
174 * static struct region *region_hash[128];
176 * static void add_region(struct region *r)
178 * unsigned int h = hash_pointer(r->start);
180 * r->chain = region_hash[h];
181 * region_hash[h] = r->chain;
184 * static void find_region(const void *start)
188 * for (r = region_hash[hash_pointer(start)]; r; r = r->chain)
189 * if (r->start == start)
194 static inline uint32_t hash_pointer(const void *p, uint32_t base)
196 if (sizeof(p) % sizeof(uint32_t) == 0) {
197 /* This convoluted union is the right way of aliasing. */
199 uint32_t u32[sizeof(p) / sizeof(uint32_t)];
203 return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base);
205 return hash(&p, 1, base);
209 * hash64 - fast 64-bit hash of an array for internal use
210 * @p: the array or pointer to first element
211 * @num: the number of elements to hash
212 * @base: the base number to roll into the hash (usually 0)
214 * The memory region pointed to by p is combined with the base to form
217 * This hash will have different results on different machines, so is
218 * only useful for internal hashes (ie. not hashes sent across the
219 * network or saved to disk).
221 * It may also change with future versions: it could even detect at runtime
222 * what the fastest hash to use is.
227 * #include <ccan/hash/hash.h>
231 * // Simple demonstration: idential strings will have the same hash, but
232 * // two different strings will probably not.
233 * int main(int argc, char *argv[])
235 * uint64_t hash1, hash2;
238 * err(1, "Usage: %s <string1> <string2>", argv[0]);
240 * hash1 = hash64(argv[1], strlen(argv[1]), 0);
241 * hash2 = hash64(argv[2], strlen(argv[2]), 0);
242 * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
246 #define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base))
249 * hash64_stable - 64 bit hash of an array for external use
250 * @p: the array or pointer to first element
251 * @num: the number of elements to hash
252 * @base: the base number to roll into the hash (usually 0)
254 * The array of simple integer types pointed to by p is combined with
255 * the base to form a 64-bit hash.
257 * This hash will have the same results on different machines, so can
258 * be used for external hashes (ie. hashes sent across the network or
259 * saved to disk). The results will not change in future versions of
262 * Note that it is only legal to hand an array of simple integer types
263 * to this hash (ie. char, uint16_t, int64_t, etc). In these cases,
264 * the same values will have the same hash result, even though the
265 * memory representations of integers depend on the machine
272 * #include <ccan/hash/hash.h>
276 * int main(int argc, char *argv[])
279 * err(1, "Usage: %s <string-to-hash>", argv[0]);
281 * printf("Hash stable result is %llu\n",
282 * (long long)hash64_stable(argv[1], strlen(argv[1]), 0));
286 #define hash64_stable(p, num, base) \
287 (EXPR_BUILD_ASSERT(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \
288 || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
289 sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base)) \
290 : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base)) \
291 : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base)) \
292 : hash64_stable_8((p), (num), (base)))
296 * hashl - fast 32/64-bit hash of an array for internal use
297 * @p: the array or pointer to first element
298 * @num: the number of elements to hash
299 * @base: the base number to roll into the hash (usually 0)
301 * This is either hash() or hash64(), on 32/64 bit long machines.
303 #define hashl(p, num, base) \
304 (EXPR_BUILD_ASSERT(sizeof(long) == sizeof(uint32_t) \
305 || sizeof(long) == sizeof(uint64_t)) + \
306 (sizeof(long) == sizeof(uint64_t) \
307 ? hash64((p), (num), (base)) : hash((p), (num), (base))))