]>
Commit | Line | Data |
---|---|---|
6a364ced KB |
1 | /* |
2 | * Generic implementation of hash-based key value mappings. | |
3 | */ | |
4 | #include "cache.h" | |
5 | #include "hashmap.h" | |
6 | ||
7 | #define FNV32_BASE ((unsigned int) 0x811c9dc5) | |
8 | #define FNV32_PRIME ((unsigned int) 0x01000193) | |
9 | ||
10 | unsigned int strhash(const char *str) | |
11 | { | |
12 | unsigned int c, hash = FNV32_BASE; | |
13 | while ((c = (unsigned char) *str++)) | |
14 | hash = (hash * FNV32_PRIME) ^ c; | |
15 | return hash; | |
16 | } | |
17 | ||
18 | unsigned int strihash(const char *str) | |
19 | { | |
20 | unsigned int c, hash = FNV32_BASE; | |
21 | while ((c = (unsigned char) *str++)) { | |
22 | if (c >= 'a' && c <= 'z') | |
23 | c -= 'a' - 'A'; | |
24 | hash = (hash * FNV32_PRIME) ^ c; | |
25 | } | |
26 | return hash; | |
27 | } | |
28 | ||
29 | unsigned int memhash(const void *buf, size_t len) | |
30 | { | |
31 | unsigned int hash = FNV32_BASE; | |
32 | unsigned char *ucbuf = (unsigned char *) buf; | |
33 | while (len--) { | |
34 | unsigned int c = *ucbuf++; | |
35 | hash = (hash * FNV32_PRIME) ^ c; | |
36 | } | |
37 | return hash; | |
38 | } | |
39 | ||
40 | unsigned int memihash(const void *buf, size_t len) | |
41 | { | |
42 | unsigned int hash = FNV32_BASE; | |
43 | unsigned char *ucbuf = (unsigned char *) buf; | |
44 | while (len--) { | |
45 | unsigned int c = *ucbuf++; | |
46 | if (c >= 'a' && c <= 'z') | |
47 | c -= 'a' - 'A'; | |
48 | hash = (hash * FNV32_PRIME) ^ c; | |
49 | } | |
50 | return hash; | |
51 | } | |
52 | ||
f75619bd | 53 | /* |
15beaaa3 | 54 | * Incorporate another chunk of data into a memihash |
f75619bd JH |
55 | * computation. |
56 | */ | |
57 | unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len) | |
58 | { | |
59 | unsigned int hash = hash_seed; | |
60 | unsigned char *ucbuf = (unsigned char *) buf; | |
61 | while (len--) { | |
62 | unsigned int c = *ucbuf++; | |
63 | if (c >= 'a' && c <= 'z') | |
64 | c -= 'a' - 'A'; | |
65 | hash = (hash * FNV32_PRIME) ^ c; | |
66 | } | |
67 | return hash; | |
68 | } | |
69 | ||
6a364ced KB |
70 | #define HASHMAP_INITIAL_SIZE 64 |
71 | /* grow / shrink by 2^2 */ | |
72 | #define HASHMAP_RESIZE_BITS 2 | |
73 | /* load factor in percent */ | |
74 | #define HASHMAP_LOAD_FACTOR 80 | |
75 | ||
76 | static void alloc_table(struct hashmap *map, unsigned int size) | |
77 | { | |
78 | map->tablesize = size; | |
79 | map->table = xcalloc(size, sizeof(struct hashmap_entry *)); | |
80 | ||
81 | /* calculate resize thresholds for new size */ | |
82 | map->grow_at = (unsigned int) ((uint64_t) size * HASHMAP_LOAD_FACTOR / 100); | |
83 | if (size <= HASHMAP_INITIAL_SIZE) | |
84 | map->shrink_at = 0; | |
85 | else | |
86 | /* | |
87 | * The shrink-threshold must be slightly smaller than | |
88 | * (grow-threshold / resize-factor) to prevent erratic resizing, | |
89 | * thus we divide by (resize-factor + 1). | |
90 | */ | |
91 | map->shrink_at = map->grow_at / ((1 << HASHMAP_RESIZE_BITS) + 1); | |
92 | } | |
93 | ||
94 | static inline int entry_equals(const struct hashmap *map, | |
97a39a4a EN |
95 | const struct hashmap_entry *e1, |
96 | const struct hashmap_entry *e2, | |
97 | const void *keydata) | |
6a364ced | 98 | { |
7663cdc8 SB |
99 | return (e1 == e2) || |
100 | (e1->hash == e2->hash && | |
101 | !map->cmpfn(map->cmpfn_data, e1, e2, keydata)); | |
6a364ced KB |
102 | } |
103 | ||
104 | static inline unsigned int bucket(const struct hashmap *map, | |
97a39a4a | 105 | const struct hashmap_entry *key) |
6a364ced KB |
106 | { |
107 | return key->hash & (map->tablesize - 1); | |
108 | } | |
109 | ||
0607e100 JH |
110 | int hashmap_bucket(const struct hashmap *map, unsigned int hash) |
111 | { | |
112 | return hash & (map->tablesize - 1); | |
113 | } | |
114 | ||
6a364ced KB |
115 | static void rehash(struct hashmap *map, unsigned int newsize) |
116 | { | |
b7879b0b | 117 | /* map->table MUST NOT be NULL when this function is called */ |
6a364ced KB |
118 | unsigned int i, oldsize = map->tablesize; |
119 | struct hashmap_entry **oldtable = map->table; | |
120 | ||
121 | alloc_table(map, newsize); | |
122 | for (i = 0; i < oldsize; i++) { | |
123 | struct hashmap_entry *e = oldtable[i]; | |
124 | while (e) { | |
125 | struct hashmap_entry *next = e->next; | |
126 | unsigned int b = bucket(map, e); | |
127 | e->next = map->table[b]; | |
128 | map->table[b] = e; | |
129 | e = next; | |
130 | } | |
131 | } | |
132 | free(oldtable); | |
133 | } | |
134 | ||
135 | static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map, | |
136 | const struct hashmap_entry *key, const void *keydata) | |
137 | { | |
b7879b0b | 138 | /* map->table MUST NOT be NULL when this function is called */ |
6a364ced KB |
139 | struct hashmap_entry **e = &map->table[bucket(map, key)]; |
140 | while (*e && !entry_equals(map, *e, key, keydata)) | |
141 | e = &(*e)->next; | |
142 | return e; | |
143 | } | |
144 | ||
7663cdc8 | 145 | static int always_equal(const void *unused_cmp_data, |
939af16e EW |
146 | const struct hashmap_entry *unused1, |
147 | const struct hashmap_entry *unused2, | |
7663cdc8 | 148 | const void *unused_keydata) |
6a364ced KB |
149 | { |
150 | return 0; | |
151 | } | |
152 | ||
153 | void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, | |
97a39a4a | 154 | const void *cmpfn_data, size_t initial_size) |
6a364ced KB |
155 | { |
156 | unsigned int size = HASHMAP_INITIAL_SIZE; | |
0607e100 JH |
157 | |
158 | memset(map, 0, sizeof(*map)); | |
159 | ||
6a364ced | 160 | map->cmpfn = equals_function ? equals_function : always_equal; |
7663cdc8 | 161 | map->cmpfn_data = cmpfn_data; |
6a364ced KB |
162 | |
163 | /* calculate initial table size and allocate the table */ | |
164 | initial_size = (unsigned int) ((uint64_t) initial_size * 100 | |
165 | / HASHMAP_LOAD_FACTOR); | |
166 | while (initial_size > size) | |
167 | size <<= HASHMAP_RESIZE_BITS; | |
168 | alloc_table(map, size); | |
8b604d19 JH |
169 | |
170 | /* | |
171 | * Keep track of the number of items in the map and | |
172 | * allow the map to automatically grow as necessary. | |
173 | */ | |
174 | map->do_count_items = 1; | |
6a364ced KB |
175 | } |
176 | ||
33f20d82 EN |
177 | static void free_individual_entries(struct hashmap *map, ssize_t entry_offset) |
178 | { | |
179 | struct hashmap_iter iter; | |
180 | struct hashmap_entry *e; | |
181 | ||
182 | hashmap_iter_init(map, &iter); | |
183 | while ((e = hashmap_iter_next(&iter))) | |
184 | /* | |
185 | * like container_of, but using caller-calculated | |
6da1a258 | 186 | * offset (caller being hashmap_clear_and_free) |
33f20d82 EN |
187 | */ |
188 | free((char *)e - entry_offset); | |
189 | } | |
190 | ||
191 | void hashmap_partial_clear_(struct hashmap *map, ssize_t entry_offset) | |
192 | { | |
193 | if (!map || !map->table) | |
194 | return; | |
195 | if (entry_offset >= 0) /* called by hashmap_clear_entries */ | |
196 | free_individual_entries(map, entry_offset); | |
197 | memset(map->table, 0, map->tablesize * sizeof(struct hashmap_entry *)); | |
198 | map->shrink_at = 0; | |
199 | map->private_size = 0; | |
200 | } | |
201 | ||
6da1a258 | 202 | void hashmap_clear_(struct hashmap *map, ssize_t entry_offset) |
6a364ced KB |
203 | { |
204 | if (!map || !map->table) | |
205 | return; | |
6da1a258 | 206 | if (entry_offset >= 0) /* called by hashmap_clear_and_free */ |
33f20d82 | 207 | free_individual_entries(map, entry_offset); |
6a364ced KB |
208 | free(map->table); |
209 | memset(map, 0, sizeof(*map)); | |
210 | } | |
211 | ||
f23a4651 EW |
212 | struct hashmap_entry *hashmap_get(const struct hashmap *map, |
213 | const struct hashmap_entry *key, | |
214 | const void *keydata) | |
6a364ced | 215 | { |
b7879b0b EN |
216 | if (!map->table) |
217 | return NULL; | |
6a364ced KB |
218 | return *find_entry_ptr(map, key, keydata); |
219 | } | |
220 | ||
6bcbdfb2 | 221 | struct hashmap_entry *hashmap_get_next(const struct hashmap *map, |
97a39a4a | 222 | const struct hashmap_entry *entry) |
6a364ced | 223 | { |
f6eb6bdc | 224 | struct hashmap_entry *e = entry->next; |
6a364ced KB |
225 | for (; e; e = e->next) |
226 | if (entry_equals(map, entry, e, NULL)) | |
227 | return e; | |
228 | return NULL; | |
229 | } | |
230 | ||
b94e5c1d | 231 | void hashmap_add(struct hashmap *map, struct hashmap_entry *entry) |
6a364ced | 232 | { |
b7879b0b | 233 | unsigned int b; |
6a364ced | 234 | |
b7879b0b EN |
235 | if (!map->table) |
236 | alloc_table(map, HASHMAP_INITIAL_SIZE); | |
237 | ||
238 | b = bucket(map, entry); | |
6a364ced | 239 | /* add entry */ |
b94e5c1d | 240 | entry->next = map->table[b]; |
6a364ced KB |
241 | map->table[b] = entry; |
242 | ||
243 | /* fix size and rehash if appropriate */ | |
8b604d19 JH |
244 | if (map->do_count_items) { |
245 | map->private_size++; | |
246 | if (map->private_size > map->grow_at) | |
247 | rehash(map, map->tablesize << HASHMAP_RESIZE_BITS); | |
248 | } | |
6a364ced KB |
249 | } |
250 | ||
8a973d0b | 251 | struct hashmap_entry *hashmap_remove(struct hashmap *map, |
97a39a4a EN |
252 | const struct hashmap_entry *key, |
253 | const void *keydata) | |
6a364ced KB |
254 | { |
255 | struct hashmap_entry *old; | |
b7879b0b EN |
256 | struct hashmap_entry **e; |
257 | ||
258 | if (!map->table) | |
259 | return NULL; | |
260 | e = find_entry_ptr(map, key, keydata); | |
6a364ced KB |
261 | if (!*e) |
262 | return NULL; | |
263 | ||
264 | /* remove existing entry */ | |
265 | old = *e; | |
266 | *e = old->next; | |
267 | old->next = NULL; | |
268 | ||
269 | /* fix size and rehash if appropriate */ | |
8b604d19 JH |
270 | if (map->do_count_items) { |
271 | map->private_size--; | |
272 | if (map->private_size < map->shrink_at) | |
273 | rehash(map, map->tablesize >> HASHMAP_RESIZE_BITS); | |
274 | } | |
275 | ||
6a364ced KB |
276 | return old; |
277 | } | |
278 | ||
8a973d0b | 279 | struct hashmap_entry *hashmap_put(struct hashmap *map, |
97a39a4a | 280 | struct hashmap_entry *entry) |
6a364ced KB |
281 | { |
282 | struct hashmap_entry *old = hashmap_remove(map, entry, NULL); | |
283 | hashmap_add(map, entry); | |
284 | return old; | |
285 | } | |
286 | ||
287 | void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter) | |
288 | { | |
289 | iter->map = map; | |
290 | iter->tablepos = 0; | |
291 | iter->next = NULL; | |
292 | } | |
293 | ||
87571c3f | 294 | struct hashmap_entry *hashmap_iter_next(struct hashmap_iter *iter) |
6a364ced KB |
295 | { |
296 | struct hashmap_entry *current = iter->next; | |
297 | for (;;) { | |
298 | if (current) { | |
299 | iter->next = current->next; | |
300 | return current; | |
301 | } | |
302 | ||
303 | if (iter->tablepos >= iter->map->tablesize) | |
304 | return NULL; | |
305 | ||
306 | current = iter->map->table[iter->tablepos++]; | |
307 | } | |
308 | } | |
7b64d42d KB |
309 | |
310 | struct pool_entry { | |
311 | struct hashmap_entry ent; | |
312 | size_t len; | |
313 | unsigned char data[FLEX_ARRAY]; | |
314 | }; | |
315 | ||
7663cdc8 | 316 | static int pool_entry_cmp(const void *unused_cmp_data, |
939af16e EW |
317 | const struct hashmap_entry *eptr, |
318 | const struct hashmap_entry *entry_or_key, | |
319 | const void *keydata) | |
7b64d42d | 320 | { |
939af16e EW |
321 | const struct pool_entry *e1, *e2; |
322 | ||
323 | e1 = container_of(eptr, const struct pool_entry, ent); | |
324 | e2 = container_of(entry_or_key, const struct pool_entry, ent); | |
325 | ||
7b64d42d KB |
326 | return e1->data != keydata && |
327 | (e1->len != e2->len || memcmp(e1->data, keydata, e1->len)); | |
328 | } | |
329 | ||
330 | const void *memintern(const void *data, size_t len) | |
331 | { | |
332 | static struct hashmap map; | |
333 | struct pool_entry key, *e; | |
334 | ||
335 | /* initialize string pool hashmap */ | |
336 | if (!map.tablesize) | |
939af16e | 337 | hashmap_init(&map, pool_entry_cmp, NULL, 0); |
7b64d42d KB |
338 | |
339 | /* lookup interned string in pool */ | |
d22245a2 | 340 | hashmap_entry_init(&key.ent, memhash(data, len)); |
7b64d42d | 341 | key.len = len; |
404ab78e | 342 | e = hashmap_get_entry(&map, &key, ent, data); |
7b64d42d KB |
343 | if (!e) { |
344 | /* not found: create it */ | |
96ffc06f | 345 | FLEX_ALLOC_MEM(e, data, data, len); |
d22245a2 | 346 | hashmap_entry_init(&e->ent, key.ent.hash); |
7b64d42d | 347 | e->len = len; |
b94e5c1d | 348 | hashmap_add(&map, &e->ent); |
7b64d42d KB |
349 | } |
350 | return e->data; | |
351 | } |