Make tokenizer throw error on empty char literal, along with some slight cleanups...
[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
7 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
8  * 
9  * http://burtleburtle.net/bob/c/lookup3.c
10  */
11
12 /**
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)
17  *
18  * The memory region pointed to by p is combined with the base to form
19  * a 32-bit hash.
20  *
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).
24  *
25  * It may also change with future versions: it could even detect at runtime
26  * what the fastest hash to use is.
27  *
28  * See also: hash_stable.
29  *
30  * Example:
31  *      #include "hash/hash.h"
32  *      #include <err.h>
33  *      #include <stdio.h>
34  *
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[])
38  *      {
39  *              uint32_t hash1, hash2;
40  *
41  *              if (argc != 3)
42  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
43  *
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");
47  *              return 0;
48  *      }
49  */
50 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
51
52 /**
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)
57  *
58  * The array of simple integer types pointed to by p is combined with
59  * the base to form a 32-bit hash.
60  *
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
64  * this module.
65  *
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
70  * endianness.
71  *
72  * Example:
73  *      #include "hash/hash.h"
74  *      #include <err.h>
75  *      #include <stdio.h>
76  *
77  *      int main(int argc, char *argv[])
78  *      {
79  *              if (argc != 2)
80  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
81  *
82  *              printf("Hash stable result is %u\n",
83  *                     hash_stable(argv[1], strlen(argv[1]), 0));
84  *              return 0;
85  *      }
86  */
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)))
93
94 /**
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)
99  *
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.
103  *
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).
107  */
108 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
109
110 /**
111  * hash_string - very fast hash of an ascii string
112  * @str: the nul-terminated string
113  *
114  * The string is hashed, using a hash function optimized for ASCII and
115  * similar strings.  It's weaker than the other hash functions.
116  *
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.
121  */
122 static inline uint32_t hash_string(const char *string)
123 {
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. */
127         uint32_t ret;
128
129         for (ret = 0; *string; string++)
130                 ret = (ret << 5) - ret + *string;
131
132         return ret;
133 }
134
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);
142
143 /**
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)
147  *
148  * The pointer p (not what p points to!) is combined with the base to form
149  * a 32-bit hash.
150  *
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).
154  *
155  * Example:
156  *      #include "hash/hash.h"
157  *
158  *      // Code to keep track of memory regions.
159  *      struct region {
160  *              struct region *chain;
161  *              void *start;
162  *              unsigned int size;
163  *      };
164  *      // We keep a simple hash table.
165  *      static struct region *region_hash[128];
166  *
167  *      static void add_region(struct region *r)
168  *      {
169  *              unsigned int h = hash_pointer(r->start);
170  *
171  *              r->chain = region_hash[h];
172  *              region_hash[h] = r->chain;
173  *      }
174  *
175  *      static void find_region(const void *start)
176  *      {
177  *              struct region *r;
178  *
179  *              for (r = region_hash[hash_pointer(start)]; r; r = r->chain)
180  *                      if (r->start == start)
181  *                              return r;
182  *              return NULL;
183  *      }
184  */
185 static inline uint32_t hash_pointer(const void *p, uint32_t base)
186 {
187         if (sizeof(p) % sizeof(uint32_t) == 0) {
188                 /* This convoluted union is the right way of aliasing. */
189                 union {
190                         uint32_t u32[sizeof(p) / sizeof(uint32_t)];
191                         const void *p;
192                 } u;
193                 u.p = p;
194                 return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base);
195         } else
196                 return hash(&p, 1, base);
197 }
198 #endif /* HASH_H */