1f8ccbf06212e3b3b7b98ce32ee07659c717a8df
[ccan] / ccan / hash / hash.h
1 #ifndef CCAN_HASH_H
2 #define CCAN_HASH_H
3 #include <stdint.h>
4 #include <stdlib.h>
5 #include "config.h"
6 #include <ccan/build_assert/build_assert.h>
7
8 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
9  * 
10  * http://burtleburtle.net/bob/c/lookup3.c
11  */
12
13 /**
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)
18  *
19  * The memory region pointed to by p is combined with the base to form
20  * a 32-bit hash.
21  *
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).
25  *
26  * It may also change with future versions: it could even detect at runtime
27  * what the fastest hash to use is.
28  *
29  * See also: hash64, hash_stable.
30  *
31  * Example:
32  *      #include "hash/hash.h"
33  *      #include <err.h>
34  *      #include <stdio.h>
35  *
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[])
39  *      {
40  *              uint32_t hash1, hash2;
41  *
42  *              if (argc != 3)
43  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
44  *
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");
48  *              return 0;
49  *      }
50  */
51 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
52
53 /**
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)
58  *
59  * The array of simple integer types pointed to by p is combined with
60  * the base to form a 32-bit hash.
61  *
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
65  * this module.
66  *
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
71  * endianness.
72  *
73  * See also:
74  *      hash64_stable
75  *
76  * Example:
77  *      #include "hash/hash.h"
78  *      #include <err.h>
79  *      #include <stdio.h>
80  *
81  *      int main(int argc, char *argv[])
82  *      {
83  *              if (argc != 2)
84  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
85  *
86  *              printf("Hash stable result is %u\n",
87  *                     hash_stable(argv[1], strlen(argv[1]), 0));
88  *              return 0;
89  *      }
90  */
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)))
98
99 /**
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)
104  *
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.
108  *
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).
112  */
113 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
114
115 /**
116  * hash_string - very fast hash of an ascii string
117  * @str: the nul-terminated string
118  *
119  * The string is hashed, using a hash function optimized for ASCII and
120  * similar strings.  It's weaker than the other hash functions.
121  *
122  * This hash may have different results on different machines, so is
123  * only useful for internal hashes (ie. not hashes sent across the
124  * network or saved to disk).  The results will be different from the
125  * other hash functions in this module, too.
126  */
127 static inline uint32_t hash_string(const char *string)
128 {
129         /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
130          * It's a little faster than the (much better) lookup3 hash(): 56ns vs
131          * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
132         uint32_t ret;
133
134         for (ret = 0; *string; string++)
135                 ret = (ret << 5) - ret + *string;
136
137         return ret;
138 }
139
140 /**
141  * hash64 - fast 64-bit hash of an array for internal use
142  * @p: the array or pointer to first element
143  * @num: the number of elements to hash
144  * @base: the 64-bit base number to roll into the hash (usually 0)
145  *
146  * The memory region pointed to by p is combined with the base to form
147  * a 64-bit hash.
148  *
149  * This hash will have different results on different machines, so is
150  * only useful for internal hashes (ie. not hashes sent across the
151  * network or saved to disk).
152  *
153  * It may also change with future versions: it could even detect at runtime
154  * what the fastest hash to use is.
155  *
156  * See also: hash.
157  *
158  * Example:
159  *      #include <ccan/hash/hash.h>
160  *      #include <err.h>
161  *      #include <stdio.h>
162  *
163  *      // Simple demonstration: idential strings will have the same hash, but
164  *      // two different strings will probably not.
165  *      int main(int argc, char *argv[])
166  *      {
167  *              uint64_t hash1, hash2;
168  *
169  *              if (argc != 3)
170  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
171  *
172  *              hash1 = hash64(argv[1], strlen(argv[1]), 0);
173  *              hash2 = hash64(argv[2], strlen(argv[2]), 0);
174  *              printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
175  *              return 0;
176  *      }
177  */
178 #define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base))
179
180 /**
181  * hash64_stable - 64 bit hash of an array for external use
182  * @p: the array or pointer to first element
183  * @num: the number of elements to hash
184  * @base: the base number to roll into the hash (usually 0)
185  *
186  * The array of simple integer types pointed to by p is combined with
187  * the base to form a 64-bit hash.
188  *
189  * This hash will have the same results on different machines, so can
190  * be used for external hashes (ie. hashes sent across the network or
191  * saved to disk).  The results will not change in future versions of
192  * this module.
193  *
194  * Note that it is only legal to hand an array of simple integer types
195  * to this hash (ie. char, uint16_t, int64_t, etc).  In these cases,
196  * the same values will have the same hash result, even though the
197  * memory representations of integers depend on the machine
198  * endianness.
199  *
200  * See also:
201  *      hash_stable
202  *
203  * Example:
204  *      #include <ccan/hash/hash.h>
205  *      #include <err.h>
206  *      #include <stdio.h>
207  *
208  *      int main(int argc, char *argv[])
209  *      {
210  *              if (argc != 2)
211  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
212  *
213  *              printf("Hash stable result is %llu\n",
214  *                     (long long)hash64_stable(argv[1], strlen(argv[1]), 0));
215  *              return 0;
216  *      }
217  */
218 #define hash64_stable(p, num, base)                                     \
219         (EXPR_BUILD_ASSERT(sizeof(*(p)) == 8 || sizeof(*(p)) == 4       \
220                            || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
221          sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base))       \
222          : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base))     \
223          : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base))     \
224          : hash64_stable_8((p), (num), (base)))
225
226
227 /**
228  * hashl - fast 32/64-bit hash of an array for internal use
229  * @p: the array or pointer to first element
230  * @num: the number of elements to hash
231  * @base: the base number to roll into the hash (usually 0)
232  *
233  * This is either hash() or hash64(), on 32/64 bit long machines.
234  */
235 #define hashl(p, num, base)                                             \
236         (EXPR_BUILD_ASSERT(sizeof(long) == sizeof(uint32_t)             \
237                            || sizeof(long) == sizeof(uint64_t)) +       \
238         (sizeof(long) == sizeof(uint64_t)                               \
239          ? hash64((p), (num), (base)) : hash((p), (num), (base))))
240
241 /* Our underlying operations. */
242 uint32_t hash_any(const void *key, size_t length, uint32_t base);
243 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base);
244 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base);
245 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base);
246 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base);
247 uint64_t hash64_any(const void *key, size_t length, uint64_t base);
248 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base);
249 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base);
250 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base);
251 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base);
252
253 /**
254  * hash_pointer - hash a pointer for internal use
255  * @p: the pointer value to hash
256  * @base: the base number to roll into the hash (usually 0)
257  *
258  * The pointer p (not what p points to!) is combined with the base to form
259  * a 32-bit hash.
260  *
261  * This hash will have different results on different machines, so is
262  * only useful for internal hashes (ie. not hashes sent across the
263  * network or saved to disk).
264  *
265  * Example:
266  *      #include "hash/hash.h"
267  *
268  *      // Code to keep track of memory regions.
269  *      struct region {
270  *              struct region *chain;
271  *              void *start;
272  *              unsigned int size;
273  *      };
274  *      // We keep a simple hash table.
275  *      static struct region *region_hash[128];
276  *
277  *      static void add_region(struct region *r)
278  *      {
279  *              unsigned int h = hash_pointer(r->start);
280  *
281  *              r->chain = region_hash[h];
282  *              region_hash[h] = r->chain;
283  *      }
284  *
285  *      static void find_region(const void *start)
286  *      {
287  *              struct region *r;
288  *
289  *              for (r = region_hash[hash_pointer(start)]; r; r = r->chain)
290  *                      if (r->start == start)
291  *                              return r;
292  *              return NULL;
293  *      }
294  */
295 static inline uint32_t hash_pointer(const void *p, uint32_t base)
296 {
297         if (sizeof(p) % sizeof(uint32_t) == 0) {
298                 /* This convoluted union is the right way of aliasing. */
299                 union {
300                         uint32_t u32[sizeof(p) / sizeof(uint32_t)];
301                         const void *p;
302                 } u;
303                 u.p = p;
304                 return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base);
305         } else
306                 return hash(&p, 1, base);
307 }
308 #endif /* HASH_H */