7 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
9 * http://burtleburtle.net/bob/c/lookup3.c
13 * hash - fast hash of an array for internal use
14 * @p: the array or pointer to first element
15 * @num: the number of elements to hash
16 * @base: the base number to roll into the hash (usually 0)
18 * The memory region pointed to by p is combined with the base to form
21 * This hash will have different results on different machines, so is
22 * only useful for internal hashes (ie. not hashes sent across the
23 * network or saved to disk).
25 * It may also change with future versions: it could even detect at runtime
26 * what the fastest hash to use is.
28 * See also: hash_stable.
31 * #include "hash/hash.h"
35 * // Simple demonstration: idential strings will have the same hash, but
36 * // two different strings will probably not.
37 * int main(int argc, char *argv[])
39 * uint32_t hash1, hash2;
42 * err(1, "Usage: %s <string1> <string2>", argv[0]);
44 * hash1 = hash(argv[1], strlen(argv[1]), 0);
45 * hash2 = hash(argv[2], strlen(argv[2]), 0);
46 * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
50 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
53 * hash_stable - hash of an array for external use
54 * @p: the array or pointer to first element
55 * @num: the number of elements to hash
56 * @base: the base number to roll into the hash (usually 0)
58 * The array of simple integer types pointed to by p is combined with
59 * the base to form a 32-bit hash.
61 * This hash will have the same results on different machines, so can
62 * be used for external hashes (ie. hashes sent across the network or
63 * saved to disk). The results will not change in future versions of
66 * Note that it is only legal to hand an array of simple integer types
67 * to this hash (ie. char, uint16_t, int64_t, etc). In these cases,
68 * the same values will have the same hash result, even though the
69 * memory representations of integers depend on the machine
73 * #include "hash/hash.h"
77 * int main(int argc, char *argv[])
80 * err(1, "Usage: %s <string-to-hash>", argv[0]);
82 * printf("Hash stable result is %u\n",
83 * hash_stable(argv[1], strlen(argv[1]), 0));
87 #define hash_stable(p, num, base) \
88 (sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base)) \
89 : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base)) \
90 : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base)) \
91 : sizeof(*(p)) == 1 ? hash_stable_8((p), (num), (base)) \
92 : hash_stable_fail((p), (num), sizeof(*(p)), (base)))
95 * hash_u32 - fast hash an array of 32-bit values for internal use
96 * @key: the array of uint32_t
97 * @num: the number of elements to hash
98 * @base: the base number to roll into the hash (usually 0)
100 * The array of uint32_t pointed to by @key is combined with the base
101 * to form a 32-bit hash. This is 2-3 times faster than hash() on small
102 * arrays, but the advantage vanishes over large hashes.
104 * This hash will have different results on different machines, so is
105 * only useful for internal hashes (ie. not hashes sent across the
106 * network or saved to disk).
108 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
111 * hash_string - very fast hash of an ascii string
112 * @str: the nul-terminated string
114 * The string is hashed, using a hash function optimized for ASCII and
115 * similar strings. It's weaker than the other hash functions.
117 * This hash may have different results on different machines, so is
118 * only useful for internal hashes (ie. not hashes sent across the
119 * network or saved to disk). The results will be different from the
120 * other hash functions in this module, too.
122 static inline uint32_t hash_string(const char *string)
124 /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
125 * It's a little faster than the (much better) lookup3 hash(): 56ns vs
126 * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
129 for (ret = 0; *string; string++)
130 ret = (ret << 5) - ret + *string;
135 /* Our underlying operations. */
136 uint32_t hash_any(const void *key, size_t length, uint32_t base);
137 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base);
138 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base);
139 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base);
140 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base);
141 uint32_t hash_stable_fail(const void *key, size_t n, size_t len, uint32_t base);
144 * hash_pointer - hash a pointer for internal use
145 * @p: the pointer value to hash
146 * @base: the base number to roll into the hash (usually 0)
148 * The pointer p (not what p points to!) is combined with the base to form
151 * This hash will have different results on different machines, so is
152 * only useful for internal hashes (ie. not hashes sent across the
153 * network or saved to disk).
156 * #include "hash/hash.h"
158 * // Code to keep track of memory regions.
160 * struct region *chain;
164 * // We keep a simple hash table.
165 * static struct region *region_hash[128];
167 * static void add_region(struct region *r)
169 * unsigned int h = hash_pointer(r->start);
171 * r->chain = region_hash[h];
172 * region_hash[h] = r->chain;
175 * static void find_region(const void *start)
179 * for (r = region_hash[hash_pointer(start)]; r; r = r->chain)
180 * if (r->start == start)
185 static inline uint32_t hash_pointer(const void *p, uint32_t base)
187 if (sizeof(p) % sizeof(uint32_t) == 0) {
188 /* This convoluted union is the right way of aliasing. */
190 uint32_t u32[sizeof(p) / sizeof(uint32_t)];
194 return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base);
196 return hash(&p, 1, base);