Debian Codegraph @

libdrgn/hash_table.h

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 /**
5 * @file
6 *
7 * High performance generic hash tables.
8 *
9 * See @ref HashTables.
10 */
11
12 #ifndef DRGN_HASH_TABLE_H
13 #define DRGN_HASH_TABLE_H
14
15 #ifdef __SSE2__
16 #include <emmintrin.h> // IWYU pragma: keep
17 #endif
18 #ifdef __SSE4_2__
19 #include <nmmintrin.h>
20 #endif
21 #ifdef __BMI2__
22 #include <immintrin.h>
23 #endif
24 #include <stdalign.h>
25 #include <stdbool.h>
26 #include <stddef.h>
27 #include <stdint.h>
28 #include <string.h>
29
30 #include "bitops.h"
31 #include "cityhash.h"
32 #include "generics.h"
33 #include "minmax.h"
34 #include "nstring.h" // IWYU pragma: export
35 #include "util.h"
36
37 /**
38 * @ingroup Internals
39 *
40 * @defgroup HashTables Hash tables
41 *
42 * High performance generic hash tables.
43 *
44 * This is an implementation of Facebook's <a
45 * href="https://github.com/facebook/folly/blob/master/folly/container/F14.md">
46 * F14</a>, which provides both high performance and good memory efficiency by
47 * using SIMD instructions to allow for a high load factor.
48 *
49 * These hash tables are generic, strongly typed (i.e., keys and values have
50 * static types rather than <tt>void *</tt>), and don't have any function
51 * pointer overhead.
52 *
53 * On non-x86 platforms, this falls back to a slower implementation that doesn't
54 * use SIMD.
55 *
56 * Abstractly, a hash table stores @em entries which can be looked up by @em
57 * key. A hash table is defined with @ref DEFINE_HASH_TABLE() (or the
58 * higher-level wrappers, @ref DEFINE_HASH_MAP() and @ref DEFINE_HASH_SET()).
59 * Each generated hash table interface is prefixed with a given name; the
60 * interface documented here uses the example name @c hash_table, which could be
61 * generated with this example code:
62 *
63 * @code{.c}
64 * key_type entry_to_key(const entry_type *entry);
65 * struct hash_pair hash_func(const key_type *key);
66 * bool eq_func(const key_type *a, const key_type *b);
67 * DEFINE_HASH_TABLE(hash_table, entry_type, entry_to_key, hash_func, eq_func);
68 * @endcode
69 *
70 * @sa BinarySearchTrees
71 *
72 * @{
73 */
74
75 /**
76 * Double hash.
77 *
78 * @sa HashTableHelpers
79 */
80 struct hash_pair {
81 /**
82 * First hash.
83 *
84 * F14 uses this to select the chunk.
85 */
86 size_t first;
87 /**
88 * Second hash.
89 *
90 * F14 uses this as the tag within the chunk and as the probe stride
91 * when a chunk overflows.
92 *
93 * Only the 8 least-significant bits of this are used; the rest are zero
94 * (the folly implementation insists that storing this as @c size_t
95 * generates better code). The 8th bit is always set. This is derived
96 * from @ref hash_pair::first; see @ref
97 * hash_pair_from_avalanching_hash() and @ref
98 * hash_pair_from_non_avalanching_hash().
99 */
100 size_t second;
101 };
102
103 #ifdef DOXYGEN
104 /**
105 * @struct hash_table
106 *
107 * Hash table instance.
108 *
109 * There are no requirements on how this is allocated; it may be global, on the
110 * stack, allocated by @c malloc(), embedded in another structure, etc.
111 */
112 struct hash_table;
113
114 /**
115 * Hash table iterator.
116 *
117 * Several functions return an iterator or take one as an argument. This
118 * iterator has a reference to an entry, which can be @c NULL to indicate that
119 * there is no such entry. It also contains private bookkeeping which should not
120 * be used.
121 *
122 * An iterator remains valid until the table is rehashed or the entry or one
123 * before it is deleted.
124 */
125 struct hash_table_iterator {
126 /** Pointer to the entry in the hash table. */
127 entry_type *entry;
128 };
129
130 /**
131 * Compute the hash for a given key.
132 *
133 * Note that this function is simply a wrapper around the hash function that was
134 * passed when defining the hash table. It is provided for convenience.
135 */
136 struct hash_pair hash_table_hash(const key_type *key);
137
138 /**
139 * Initialize a @ref hash_table.
140 *
141 * The new hash table is empty. It must be deinitialized with @ref
142 * hash_table_deinit().
143 *
144 * @sa HASH_TABLE_INIT
145 */
146 void hash_table_init(struct hash_table *table);
147
148 /**
149 * Free memory allocated by a @ref hash_table.
150 *
151 * After this is called, the hash table must not be used unless it is
152 * reinitialized with @ref hash_table_init(). Note that this only frees memory
153 * allocated by the hash table implementation; if the keys, values, or the hash
154 * table structure itself are dynamically allocated, those must be freed
155 * separately.
156 */
157 void hash_table_deinit(struct hash_table *table);
158
159 /**
160 * Return whether a @ref hash_table has no entries.
161 *
162 * This is O(1).
163 */
164 bool hash_table_empty(struct hash_table *table);
165
166 /**
167 * Return the number of entries in a @ref hash_table.
168 *
169 * This is O(1).
170 */
171 size_t hash_table_size(struct hash_table *table);
172
173 /**
174 * Maximum possible number of entries in a @ref hash_table.
175 *
176 * Attempts to increase the size or capacity beyond this will fail.
177 */
178 const size_t hash_table_max_size;
179
180 /**
181 * Delete all entries in a @ref hash_table.
182 *
183 * This does not necessarily free memory used by the hash table.
184 */
185 void hash_table_clear(struct hash_table *table);
186
187 /**
188 * Reserve entries in a @ref hash_table.
189 *
190 * This allocates space up front and rehashes the table to ensure that it will
191 * not be rehashed until it contains the given number of entries.
192 *
193 * @return @c true on success, @c false on failure.
194 */
195 bool hash_table_reserve(struct hash_table *table, size_t capacity);
196
197 /**
198 * Insert an entry in a @ref hash_table.
199 *
200 * If an entry with the same key is already in the hash table, the entry is @em
201 * not inserted.
202 *
203 * @param[out] it_ret If not @c NULL, a returned iterator pointing to the newly
204 * inserted entry or the existing entry with the same key.
205 * @return 1 if the entry was inserted, 0 if the key already existed, -1 if
206 * allocating memory for a rehash failed.
207 */
208 int hash_table_insert(struct hash_table *table, const entry_type *entry,
209 struct hash_table_iterator *it_ret);
210
211 /**
212 * Insert an entry in a @ref hash_table with a precomputed hash.
213 *
214 * Like @ref hash_table_insert(), but the hash was already computed. This saves
215 * recomputing the hash when doing multiple operations with the same key.
216 */
217 int hash_table_insert_hashed(struct hash_table *table, const entry_type *entry,
218 struct hash_pair hp,
219 struct hash_table_iterator *it_ret);
220
221 /**
222 * Insert an entry in a @ref hash_table which is not in the table.
223 *
224 * Like @ref hash_table_insert_hashed(), but a search was previously done and
225 * the key is not already in the table. This saves doing a redundant search in
226 * that case but is unsafe otherwise.
227 */
228 int hash_table_insert_searched(struct hash_table *table,
229 const entry_type *entry, struct hash_pair hp,
230 struct hash_table_iterator *it_ret);
231
232 /**
233 * Search for an entry in a @ref hash_table.
234 *
235 * @return An iterator pointing to the entry with the given key, or an iterator
236 * with <tt>entry == NULL</tt> if the key was not found.
237 */
238 struct hash_table_iterator hash_table_search(struct hash_table *table,
239 const key_type *key);
240
241 /**
242 * Search for an entry in a @ref hash_table with a precomputed hash.
243 *
244 * Like @ref hash_table_search(), but the hash was already computed. This saves
245 * recomputing the hash when doing multiple operations with the same key.
246 */
247 struct hash_table_iterator hash_table_search_hashed(struct hash_table *table,
248 const key_type *key,
249 struct hash_pair hp);
250
251 /**
252 * Delete an entry in a @ref hash_table.
253 *
254 * This deletes the entry with the given key. It will never rehash the table.
255 *
256 * @return @c true if the entry was found and deleted, @c false if not.
257 */
258 bool hash_table_delete(struct hash_table *table, const key_type *key);
259
260 /**
261 * Delete an entry in a @ref hash_table with a precomputed hash.
262 *
263 * Like @ref hash_table_delete(), but the hash was already computed. This saves
264 * recomputing the hash when doing multiple operations with the same key.
265 */
266 bool hash_table_delete_hashed(struct hash_table *table, struct hash_pair hp);
267
268 /**
269 * Delete an entry given by an iterator in a @ref hash_table.
270 *
271 * This deletes the entry pointed to by the iterator. It will never rehash the
272 * table.
273 *
274 * @return An iterator pointing to the next entry in the table. See @ref
275 * hash_table_next().
276 */
277 struct hash_table_iterator
278 hash_table_delete_iterator(struct hash_table *table,
279 struct hash_table_iterator it);
280
281 /**
282 * Delete an entry given by an iterator in a @ref hash_table with a precomputed
283 * hash.
284 *
285 * Like @ref hash_table_delete_iterator(), but the hash was already computed.
286 * This saves recomputing the hash when doing multiple operations with the same
287 * key.
288 */
289 struct hash_table_iterator
290 hash_table_delete_iterator_hashed(struct hash_table *table,
291 struct hash_table_iterator it,
292 struct hash_pair hp);
293
294 /**
295 * Delete an entry in a @ref hash_table.
296 *
297 * @return An iterator pointing to the next entry in the table. See @ref
298 * hash_table_next().
299 */
300 bool hash_table_delete_entry(struct hash_table *table, const entry_type *entry);
301
302 /**
303 * Get an iterator pointing to the first entry in a @ref hash_table.
304 *
305 * The first entry is arbitrary.
306 *
307 * @return An iterator pointing to the first entry, or an iterator with
308 * <tt>entry == NULL</tt> if the table is empty.
309 */
310 struct hash_table_iterator hash_table_first(struct hash_table *table);
311
312 /**
313 * Get an iterator pointing to the next entry in a @ref hash_table.
314 *
315 * The order of entries is arbitrary.
316 *
317 * @return An iterator pointing to the next entry, or an iterator with <tt>entry
318 * == NULL</tt> if there are no more entries.
319 */
320 struct hash_table_iterator hash_table_next(struct hash_table_iterator it);
321 #endif
322
323 enum { hash_table_chunk_alignment = max_iconst(alignof(max_align_t), 16) };
324
325 static inline size_t hash_table_probe_delta(struct hash_pair hp)
326 {
327 return 2 * hp.second + 1;
328 }
329
330 static const uint8_t hosted_overflow_count_inc = 0x10;
331 static const uint8_t hosted_overflow_count_dec = -0x10;
332
333 #if SIZE_MAX == 0xffffffffffffffff
334 _Static_assert(sizeof(size_t) == sizeof(uint64_t),
335 "size_t/SIZE_MAX doesn't make sense");
336
337 struct hash_table_size_and_chunk_shift {
338 uint64_t packed;
339 };
340
341 static inline void
342 hash_table_size_and_chunk_shift_init(struct hash_table_size_and_chunk_shift *scs)
343 {
344 scs->packed = 0;
345 }
346
347 enum { hash_table_size_shift = 8 };
348 static const size_t hash_table_max_size = SIZE_MAX >> hash_table_size_shift;
349
350 static inline size_t
351 hash_table_size(struct hash_table_size_and_chunk_shift *scs)
352 {
353 return scs->packed >> hash_table_size_shift;
354 }
355
356 static inline uint8_t
357 hash_table_chunk_shift(struct hash_table_size_and_chunk_shift *scs)
358 {
359 return scs->packed;
360 }
361
362 static inline void
363 hash_table_set_size(struct hash_table_size_and_chunk_shift *scs, size_t size)
364 {
365 scs->packed = (size << hash_table_size_shift)
366 | hash_table_chunk_shift(scs);
367 }
368
369 static inline void
370 hash_table_increment_size(struct hash_table_size_and_chunk_shift *scs)
371 {
372 scs->packed += UINT64_C(1) << hash_table_size_shift;
373 }
374
375 static inline void
376 hash_table_decrement_size(struct hash_table_size_and_chunk_shift *scs)
377 {
378 scs->packed -= UINT64_C(1) << hash_table_size_shift;
379 }
380
381 static inline void
382 hash_table_set_chunk_count(struct hash_table_size_and_chunk_shift *scs,
383 size_t chunk_count)
384 {
385 scs->packed = (hash_table_size(scs) << hash_table_size_shift)
386 | ilog2(chunk_count);
387 }
388 #elif SIZE_MAX == 0xffffffff
389 _Static_assert(sizeof(size_t) == sizeof(uint32_t),
390 "size_t/SIZE_MAX doesn't make sense");
391
392 struct hash_table_size_and_chunk_shift {
393 size_t size;
394 uint32_t chunk_shift;
395 };
396
397 static inline void
398 hash_table_size_and_chunk_shift_init(struct hash_table_size_and_chunk_shift *scs)
399 {
400 scs->size = 0;
401 scs->chunk_shift = 0;
402 }
403
404 static const size_t hash_table_max_size = SIZE_MAX;
405
406 static inline size_t
407 hash_table_size(struct hash_table_size_and_chunk_shift *scs)
408 {
409 return scs->size;
410 }
411
412 static inline uint8_t
413 hash_table_chunk_shift(struct hash_table_size_and_chunk_shift *scs)
414 {
415 return scs->chunk_shift;
416 }
417
418 static inline void
419 hash_table_set_size(struct hash_table_size_and_chunk_shift *scs, size_t size)
420 {
421 scs->size = size;
422 }
423
424 static inline void
425 hash_table_increment_size(struct hash_table_size_and_chunk_shift *scs)
426 {
427 scs->size++;
428 }
429
430 static inline void
431 hash_table_decrement_size(struct hash_table_size_and_chunk_shift *scs)
432 {
433 scs->size--;
434 }
435
436 static inline void
437 hash_table_set_chunk_count(struct hash_table_size_and_chunk_shift *scs,
438 size_t chunk_count)
439 {
440 scs->chunk_shift = ilog2(chunk_count);
441 }
442 #else
443 #error "unsupported SIZE_MAX"
444 #endif
445
446 static inline size_t
447 hash_table_chunk_count(struct hash_table_size_and_chunk_shift *scs)
448 {
449 return (size_t)1 << hash_table_chunk_shift(scs);
450 }
451
452 static inline size_t
453 hash_table_modulo_by_chunk_count(struct hash_table_size_and_chunk_shift *scs,
454 size_t index)
455 {
456 // The folly implementation resorts to an instrinsic because BZHI wasn't
457 // generated reliably by the compiler.
458 #ifdef __BMI2__
459 return _bzhi_u64(index, hash_table_chunk_shift(scs));
460 #else
461 return index & (((size_t)1 << hash_table_chunk_shift(scs)) - 1);
462 #endif
463 }
464
465 /*
466 * We could represent an empty hash table with chunks set to NULL. However, then
467 * we would need a branch to check for this in insert, search, and delete. We
468 * could avoid this by allocating an empty chunk, but that is wasteful since it
469 * will never actually be used. Instead, we have a special empty chunk which is
470 * used by all tables.
471 */
472 extern const uint8_t hash_table_empty_chunk_header[];
473 #define hash_table_empty_chunk (void *)hash_table_empty_chunk_header
474
475 #ifdef __SSE2__
476 #define HASH_TABLE_CHUNK_MATCH(table) \
477 static inline unsigned int table##_chunk_match(struct table##_chunk *chunk, \
478 size_t needle) \
479 { \
480 __m128i tag_vec = _mm_load_si128((__m128i *)chunk); \
481 __m128i needle_vec = _mm_set1_epi8((uint8_t)needle); \
482 __m128i eq_vec = _mm_cmpeq_epi8(tag_vec, needle_vec); \
483 return _mm_movemask_epi8(eq_vec) & table##_chunk_full_mask; \
484 }
485
486 #define HASH_TABLE_CHUNK_OCCUPIED(table) \
487 static inline unsigned int table##_chunk_occupied(struct table##_chunk *chunk) \
488 { \
489 __m128i tag_vec = _mm_load_si128((__m128i *)chunk); \
490 return _mm_movemask_epi8(tag_vec) & table##_chunk_full_mask; \
491 }
492 #else
493 #define HASH_TABLE_CHUNK_MATCH(table) \
494 static inline unsigned int table##_chunk_match(struct table##_chunk *chunk, \
495 size_t needle) \
496 { \
497 unsigned int mask, i; \
498 for (mask = 0, i = 0; i < table##_chunk_capacity; i++) { \
499 if (chunk->tags[i] == needle) \
500 mask |= 1U << i; \
501 } \
502 return mask; \
503 }
504
505 #define HASH_TABLE_CHUNK_OCCUPIED(table) \
506 static inline unsigned int table##_chunk_occupied(struct table##_chunk *chunk) \
507 { \
508 unsigned int mask, i; \
509 for (mask = 0, i = 0; i < table##_chunk_capacity; i++) { \
510 if (chunk->tags[i]) \
511 mask |= 1U << i; \
512 } \
513 return mask; \
514 }
515 #endif
516
517 /**
518 * Define a hash table type without defining its functions.
519 *
520 * This is useful when the hash table type must be defined in one place (e.g., a
521 * header) but the interface is defined elsewhere (e.g., a source file) with
522 * @ref DEFINE_HASH_TABLE_FUNCTIONS(). Otherwise, just use @ref
523 * DEFINE_HASH_TABLE().
524 *
525 * @sa DEFINE_HASH_TABLE()
526 */
527 #define DEFINE_HASH_TABLE_TYPE(table, entry_type) \
528 typedef typeof(entry_type) table##_entry_type; \
529 \
530 enum { \
531 /* \
532 * Whether this table uses the vector storage policy. \
533 * \
534 * The vector policy provides the best performance and memory \
535 * efficiency for medium and large entries. \
536 */ \
537 table##_vector_policy = sizeof(table##_entry_type) >= 24, \
538 }; \
539 \
540 /* \
541 * The vector storage policy stores 32-bit indices, so it only needs 32-bit \
542 * sizes. \
543 */ \
544 typedef_if(table##_size_type, table##_vector_policy, uint32_t, size_t); \
545 \
546 struct table { \
547 struct table##_chunk *chunks; \
548 struct hash_table_size_and_chunk_shift size_and_chunk_shift; \
549 union { \
550 /* Allocated together with chunks. */ \
551 table##_entry_type *vector; \
552 uintptr_t first_packed; \
553 }; \
554 }; \
555 struct DEFINE_HASH_TABLE_needs_semicolon
556
557 /*
558 * Common search function implementation returning an item iterator. This is
559 * shared by key lookups and index lookups.
560 */
561 #define HASH_TABLE_SEARCH_IMPL(table, func, key_type, item_to_key, eq_func) \
562 static struct table##_iterator table##_##func(struct table *table, \
563 const key_type *key, \
564 struct hash_pair hp) \
565 { \
566 const size_t delta = hash_table_probe_delta(hp); \
567 size_t index = hp.first; \
568 for (size_t tries = 0; tries >> table##_chunk_shift(table) == 0; \
569 tries++) { \
570 struct table##_chunk *chunk = \
571 &table->chunks[table##_modulo_by_chunk_count(table, index)]; \
572 if (sizeof(*chunk) > 64) \
573 __builtin_prefetch(&chunk->items[8]); \
574 unsigned int mask = table##_chunk_match(chunk, hp.second), i; \
575 for_each_bit(i, mask) { \
576 table##_item_type *item = &chunk->items[i]; \
577 key_type item_key = item_to_key(table, item); \
578 if (likely(eq_func(key, &item_key))) { \
579 return (struct table##_iterator){ \
580 .item = item, \
581 .index = i, \
582 }; \
583 } \
584 } \
585 if (likely(chunk->outbound_overflow_count == 0)) \
586 break; \
587 index += delta; \
588 } \
589 return (struct table##_iterator){}; \
590 }
591
592 #define HASH_TABLE_SEARCH_BY_INDEX_ITEM_TO_KEY(table, item) (*(uint32_t *)item)
593
594 /**
595 * Define the functions for a hash table.
596 *
597 * The hash table type must have already been defined with @ref
598 * DEFINE_HASH_TABLE_TYPE().
599 *
600 * Unless the type and function definitions must be in separate places, use @ref
601 * DEFINE_HASH_TABLE() instead.
602 */
603 #define DEFINE_HASH_TABLE_FUNCTIONS(table, entry_to_key, hash_func, eq_func) \
604 typedef typeof(entry_to_key((table##_entry_type *)0)) table##_key_type; \
605 \
606 static inline table##_key_type \
607 table##_entry_to_key(const table##_entry_type *entry) \
608 { \
609 return entry_to_key(entry); \
610 } \
611 \
612 /* \
613 * Item stored in a chunk. \
614 * \
615 * When using the basic policy, the entry is stored directly in the item. When \
616 * using the vector policy, the item is an index to an out-of-band vector of \
617 * entries. \
618 */ \
619 typedef_if(table##_item_type, table##_vector_policy, uint32_t, \
620 table##_entry_type); \
621 \
622 static inline uint32_t *table##_vector_item(table##_item_type *item) \
623 { \
624 return (uint32_t *)item; \
625 } \
626 \
627 enum { \
628 /* \
629 * The number of items per chunk. 14 is the most space efficient, but \
630 * if an item is 4 bytes, 12 items makes a chunk exactly one cache \
631 * line. \
632 */ \
633 table##_chunk_capacity = sizeof(table##_item_type) == 4 ? 12 : 14, \
634 /* The maximum load factor in terms of items per chunk. */ \
635 table##_chunk_desired_capacity = table##_chunk_capacity - 2, \
636 /* \
637 * If an item is 16 bytes, add an extra 16 bytes of padding to make a \
638 * chunk exactly four cache lines. \
639 */ \
640 table##_chunk_allocated_capacity = \
641 (table##_chunk_capacity + \
642 (sizeof(table##_item_type) == 16 ? 1 : 0)), \
643 /* \
644 * If the chunk capacity is 12, we can use tags 12 and 13 for 16 bits. \
645 * Otherwise, we only get 4 from control. \
646 */ \
647 table##_capacity_scale_bits = table##_chunk_capacity == 12 ? 16 : 4, \
648 table##_capacity_scale_shift = table##_capacity_scale_bits - 4, \
649 table##_chunk_full_mask = (1 << table##_chunk_capacity) - 1, \
650 }; \
651 \
652 struct table##_chunk { \
653 uint8_t tags[14]; \
654 /* \
655 * The lower 4 bits are capacity_scale: for the first chunk, this is \
656 * the scaling factor between the chunk count and the capacity; for \
657 * other chunks, this is zero. \
658 * \
659 * The upper 4 bits are hosted_overflow_count: the number of entries in \
660 * this chunk that overflowed their desired chunk. \
661 */ \
662 uint8_t control; \
663 /* \
664 * The number of entries that would have been in this chunk if it were \
665 * not full. This value saturates if it hits 255, after which it will \
666 * not be updated. \
667 */ \
668 uint8_t outbound_overflow_count; \
669 table##_item_type items[table##_chunk_allocated_capacity]; \
670 } __attribute__((__aligned__(hash_table_chunk_alignment))); \
671 \
672 /* \
673 * This may be a "public iterator" (used by the public interface to refer to an \
674 * entry) or an "item iterator" (used by certain internal functions to refer to \
675 * an item regardless of the storage policy). \
676 */ \
677 struct table##_iterator { \
678 union { \
679 /* Entry if public iterator. */ \
680 table##_entry_type *entry; \
681 /* \
682 * Item if item iterator. Interchangable with entry when using \
683 * the basic storage policy. \
684 */ \
685 table##_item_type *item; \
686 }; \
687 union { \
688 /* \
689 * Lowest entry if public iterator and using the vector storage \
690 * policy (i.e., table->vector). \
691 */ \
692 table##_entry_type *lowest; \
693 /* \
694 * Index of item in its containing chunk if item iterator or \
695 * using the basic storage policy. \
696 */ \
697 size_t index; \
698 }; \
699 }; \
700 \
701 static inline struct hash_pair table##_hash(const table##_key_type *key) \
702 { \
703 return hash_func(key); \
704 } \
705 \
706 static inline table##_entry_type * \
707 table##_item_to_entry(struct table *table, table##_item_type *item) \
708 { \
709 if (table##_vector_policy) \
710 return &table->vector[*table##_vector_item(item)]; \
711 else \
712 return (table##_entry_type *)item; \
713 } \
714 \
715 static inline table##_key_type \
716 table##_item_to_key(struct table *table, table##_item_type *item) \
717 { \
718 return table##_entry_to_key(table##_item_to_entry(table, item)); \
719 } \
720 \
721 /* \
722 * We cache the first position in the table as a tagged pointer: we steal the \
723 * bottom bits of the chunk pointer for the entry index. We can do this because \
724 * chunks are aligned to 16 bytes and the index is always less than 16. \
725 * \
726 * The folly implementation mentions this strategy but uses a more complicated \
727 * scheme in order to avoid computing the chunk pointer from an entry pointer. \
728 * We always have the chunk pointer readily available when we want to pack an \
729 * entry, so we can use this much simpler scheme. \
730 */ \
731 static inline uintptr_t table##_pack_iterator(struct table##_chunk *chunk, \
732 size_t index) \
733 { \
734 return (uintptr_t)chunk | (uintptr_t)index; \
735 } \
736 \
737 static inline struct table##_chunk *table##_unpack_chunk(uintptr_t packed) \
738 { \
739 return (struct table##_chunk *)(packed & ~(uintptr_t)0xf); \
740 } \
741 \
742 static inline size_t table##_unpack_index(uintptr_t packed) \
743 { \
744 return packed & 0xf; \
745 } \
746 \
747 static inline struct table##_iterator table##_unpack_iterator(uintptr_t packed) \
748 { \
749 struct table##_chunk *chunk = table##_unpack_chunk(packed); \
750 size_t index = table##_unpack_index(packed); \
751 return (struct table##_iterator) { \
752 .item = chunk ? &chunk->items[index] : NULL, \
753 .index = index, \
754 }; \
755 } \
756 \
757 static inline struct table##_chunk * \
758 table##_iterator_chunk(struct table##_iterator it) \
759 { \
760 return container_of(it.item - it.index, struct table##_chunk, items[0]);\
761 } \
762 \
763 HASH_TABLE_CHUNK_MATCH(table) \
764 HASH_TABLE_CHUNK_OCCUPIED(table) \
765 \
766 static inline unsigned int \
767 table##_chunk_first_empty(struct table##_chunk *chunk) \
768 { \
769 unsigned int mask = \
770 table##_chunk_occupied(chunk) ^ table##_chunk_full_mask; \
771 return mask ? ctz(mask) : (unsigned int)-1; \
772 } \
773 \
774 static inline unsigned int \
775 table##_chunk_last_occupied(struct table##_chunk *chunk) \
776 { \
777 unsigned int mask = table##_chunk_occupied(chunk); \
778 return mask ? fls(mask) - 1 : (unsigned int)-1; \
779 } \
780 \
781 static inline size_t \
782 table##_chunk_hosted_overflow_count(struct table##_chunk *chunk) \
783 { \
784 return chunk->control >> 4; \
785 } \
786 \
787 static inline void \
788 table##_chunk_adjust_hosted_overflow_count(struct table##_chunk *chunk, \
789 size_t op) \
790 { \
791 chunk->control += op; \
792 } \
793 \
794 static inline size_t table##_chunk_capacity_scale(struct table##_chunk *chunk) \
795 { \
796 if (table##_capacity_scale_bits == 4) { \
797 return chunk->control & 0xf; \
798 } else { \
799 uint16_t val; \
800 memcpy(&val, &chunk->tags[12], 2); \
801 return val; \
802 } \
803 } \
804 \
805 static inline bool table##_chunk_eof(struct table##_chunk *chunk) \
806 { \
807 return table##_chunk_capacity_scale(chunk) != 0; \
808 } \
809 \
810 static inline void table##_chunk_mark_eof(struct table##_chunk *chunk, \
811 size_t capacity_scale) \
812 { \
813 if (table##_capacity_scale_bits == 4) { \
814 chunk->control = capacity_scale; \
815 } else { \
816 uint16_t val = capacity_scale; \
817 memcpy(&chunk->tags[12], &val, 2); \
818 } \
819 } \
820 \
821 static inline void \
822 table##_chunk_inc_outbound_overflow_count(struct table##_chunk *chunk) \
823 { \
824 if (chunk->outbound_overflow_count != UINT8_MAX) \
825 chunk->outbound_overflow_count++; \
826 } \
827 \
828 static inline void \
829 table##_chunk_dec_outbound_overflow_count(struct table##_chunk *chunk) \
830 { \
831 if (chunk->outbound_overflow_count != UINT8_MAX) \
832 chunk->outbound_overflow_count--; \
833 } \
834 \
835 __attribute__((__unused__)) \
836 static void table##_init(struct table *table) \
837 { \
838 table->chunks = hash_table_empty_chunk; \
839 hash_table_size_and_chunk_shift_init(&table->size_and_chunk_shift); \
840 if (table##_vector_policy) \
841 table->vector = NULL; \
842 else \
843 table->first_packed = 0; \
844 } \
845 \
846 __attribute__((__unused__)) \
847 static void table##_deinit(struct table *table) \
848 { \
849 if (table->chunks != hash_table_empty_chunk) \
850 free(table->chunks); \
851 } \
852 \
853 static inline size_t table##_size(struct table *table) \
854 { \
855 return hash_table_size(&table->size_and_chunk_shift); \
856 } \
857 \
858 static inline uint8_t table##_chunk_shift(struct table *table) \
859 { \
860 return hash_table_chunk_shift(&table->size_and_chunk_shift); \
861 } \
862 \
863 static inline size_t table##_chunk_count(struct table *table) \
864 { \
865 return hash_table_chunk_count(&table->size_and_chunk_shift); \
866 } \
867 \
868 static inline size_t table##_modulo_by_chunk_count(struct table *table, \
869 size_t i) \
870 { \
871 return hash_table_modulo_by_chunk_count(&table->size_and_chunk_shift, \
872 i); \
873 } \
874 \
875 static inline void table##_set_size(struct table *table, size_t size) \
876 { \
877 hash_table_set_size(&table->size_and_chunk_shift, size); \
878 } \
879 \
880 static inline void table##_increment_size(struct table *table) \
881 { \
882 hash_table_increment_size(&table->size_and_chunk_shift); \
883 } \
884 \
885 static inline void table##_decrement_size(struct table *table) \
886 { \
887 hash_table_decrement_size(&table->size_and_chunk_shift); \
888 } \
889 \
890 static inline void table##_set_chunk_count(struct table *table, \
891 size_t chunk_count) \
892 { \
893 hash_table_set_chunk_count(&table->size_and_chunk_shift, chunk_count); \
894 } \
895 \
896 __attribute__((__unused__)) \
897 static inline bool table##_empty(struct table *table) \
898 { \
899 return table##_size(table) == 0; \
900 } \
901 \
902 static const size_t table##_max_size = \
903 min_iconst(min_iconst(PTRDIFF_MAX / sizeof(table##_entry_type), \
904 table##_vector_policy ? UINT32_MAX : SIZE_MAX), \
905 (table##_size_type)-1); \
906 \
907 static table##_item_type *table##_allocate_tag(struct table *table, \
908 uint8_t *fullness, \
909 struct hash_pair hp) \
910 { \
911 const size_t delta = hash_table_probe_delta(hp); \
912 size_t index = hp.first; \
913 struct table##_chunk *chunk; \
914 uint8_t hosted_op = 0; \
915 for (;;) { \
916 index = table##_modulo_by_chunk_count(table, index); \
917 chunk = &table->chunks[index]; \
918 if (likely(fullness[index] < table##_chunk_capacity)) \
919 break; \
920 table##_chunk_inc_outbound_overflow_count(chunk); \
921 hosted_op = hosted_overflow_count_inc; \
922 index += delta; \
923 } \
924 size_t item_index = fullness[index]++; \
925 chunk->tags[item_index] = hp.second; \
926 table##_chunk_adjust_hosted_overflow_count(chunk, hosted_op); \
927 return &chunk->items[item_index]; \
928 } \
929 \
930 static size_t table##_compute_capacity(size_t chunk_count, size_t scale) \
931 { \
932 return (((chunk_count - 1) >> table##_capacity_scale_shift) + 1) * scale;\
933 } \
934 \
935 static bool \
936 table##_compute_chunk_count_and_scale(size_t capacity, \
937 bool continuous_single_chunk_capacity, \
938 bool continuous_multi_chunk_capacity, \
939 size_t *chunk_count_ret, \
940 size_t *scale_ret) \
941 { \
942 if (capacity <= table##_chunk_capacity) { \
943 if (!continuous_single_chunk_capacity) { \
944 if (capacity <= 2) \
945 capacity = 2; \
946 else if (capacity <= 6) \
947 capacity = 6; \
948 else \
949 capacity = table##_chunk_capacity; \
950 } \
951 *chunk_count_ret = 1; \
952 *scale_ret = capacity; \
953 } else { \
954 size_t min_chunks = \
955 (capacity - 1) / table##_chunk_desired_capacity + 1; \
956 size_t chunk_pow = fls(min_chunks - 1); \
957 if (chunk_pow == 8 * sizeof(size_t)) \
958 return false; \
959 size_t chunk_count = (size_t)1 << chunk_pow; \
960 size_t ss = (chunk_pow >= table##_capacity_scale_shift ? \
961 chunk_pow - table##_capacity_scale_shift : 0); \
962 size_t scale = \
963 continuous_multi_chunk_capacity ? \
964 ((capacity - 1) >> ss) + 1 : \
965 table##_chunk_desired_capacity << (chunk_pow - ss); \
966 if (table##_compute_capacity(chunk_count, scale) \
967 > table##_max_size) \
968 return false; \
969 *chunk_count_ret = chunk_count; \
970 *scale_ret = scale; \
971 } \
972 return true; \
973 } \
974 \
975 static inline size_t table##_chunk_alloc_size(size_t chunk_count, \
976 size_t capacity_scale) \
977 { \
978 /* \
979 * Small hash tables are common, so for capacities of less than a full \
980 * chunk, we only allocate the required items. \
981 */ \
982 if (chunk_count == 1) { \
983 return (offsetof(struct table##_chunk, items) + \
984 table##_compute_capacity(1, capacity_scale) * \
985 sizeof(table##_item_type)); \
986 } else { \
987 return chunk_count * sizeof(struct table##_chunk); \
988 } \
989 } \
990 \
991 static bool table##_rehash(struct table *table, size_t orig_chunk_count, \
992 size_t orig_capacity_scale, size_t new_chunk_count, \
993 size_t new_capacity_scale) \
994 { \
995 size_t chunk_alloc_size = table##_chunk_alloc_size(new_chunk_count, \
996 new_capacity_scale); \
997 size_t alloc_size, entries_offset; \
998 if (table##_vector_policy) { \
999 entries_offset = chunk_alloc_size; \
1000 if (alignof(table##_entry_type) > alignof(table##_item_type)) { \
1001 entries_offset = -(-entries_offset & \
1002 ~(alignof(table##_entry_type) - 1)); \
1003 } \
1004 size_t new_capacity = \
1005 table##_compute_capacity(new_chunk_count, \
1006 new_capacity_scale); \
1007 alloc_size = (entries_offset + \
1008 new_capacity * sizeof(table##_entry_type)); \
1009 } else { \
1010 alloc_size = chunk_alloc_size; \
1011 } \
1012 \
1013 void *new_chunks; \
1014 if (posix_memalign(&new_chunks, hash_table_chunk_alignment, alloc_size))\
1015 return false; \
1016 \
1017 struct table##_chunk *orig_chunks = table->chunks; \
1018 table->chunks = new_chunks; \
1019 table##_entry_type *orig_entries; \
1020 if (table##_vector_policy) { \
1021 orig_entries = table->vector; \
1022 table->vector = (void *)((char *)new_chunks + entries_offset); \
1023 if (table##_size(table) > 0) { \
1024 memcpy(table->vector, orig_entries, \
1025 table##_size(table) * \
1026 sizeof(table##_entry_type)); \
1027 } \
1028 } \
1029 \
1030 memset(table->chunks, 0, chunk_alloc_size); \
1031 table##_chunk_mark_eof(table->chunks, new_capacity_scale); \
1032 table##_set_chunk_count(table, new_chunk_count); \
1033 \
1034 if (table##_size(table) == 0) { \
1035 /* Nothing to do. */ \
1036 } else if (orig_chunk_count == 1 && new_chunk_count == 1) { \
1037 struct table##_chunk *src = orig_chunks; \
1038 struct table##_chunk *dst = table->chunks; \
1039 size_t src_i = 0, dst_i = 0; \
1040 while (dst_i < table##_size(table)) { \
1041 if (likely(src->tags[src_i])) { \
1042 dst->tags[dst_i] = src->tags[src_i]; \
1043 memcpy(&dst->items[dst_i], &src->items[src_i], \
1044 sizeof(dst->items[dst_i])); \
1045 dst_i++; \
1046 } \
1047 src_i++; \
1048 } \
1049 if (!table##_vector_policy) { \
1050 table->first_packed = \
1051 table##_pack_iterator(dst, dst_i - 1); \
1052 } \
1053 } else { \
1054 uint8_t stack_fullness[256]; \
1055 uint8_t *fullness; \
1056 if (new_chunk_count <= sizeof(stack_fullness)) { \
1057 memset(stack_fullness, 0, sizeof(stack_fullness)); \
1058 fullness = stack_fullness; \
1059 } else { \
1060 fullness = calloc(new_chunk_count, 1); \
1061 if (!fullness) \
1062 goto err; \
1063 } \
1064 \
1065 struct table##_chunk *src = &orig_chunks[orig_chunk_count - 1]; \
1066 size_t remaining = table##_size(table); \
1067 while (remaining) { \
1068 unsigned int mask = table##_chunk_occupied(src), i; \
1069 if (table##_vector_policy) { \
1070 unsigned int pmask = mask; \
1071 for_each_bit(i, pmask) { \
1072 table##_item_type *item = \
1073 &src->items[i]; \
1074 table##_entry_type *entry = \
1075 table##_item_to_entry(table, \
1076 item); \
1077 __builtin_prefetch(entry); \
1078 } \
1079 } \
1080 for_each_bit(i, mask) { \
1081 remaining--; \
1082 \
1083 table##_item_type *src_item = &src->items[i]; \
1084 table##_key_type key = \
1085 table##_item_to_key(table, src_item); \
1086 struct hash_pair hp = table##_hash(&key); \
1087 table##_item_type *dst_item = \
1088 table##_allocate_tag(table, fullness, \
1089 hp); \
1090 memcpy(dst_item, src_item, sizeof(*dst_item)); \
1091 } \
1092 src--; \
1093 } \
1094 \
1095 if (!table##_vector_policy) { \
1096 size_t i = table##_chunk_count(table) - 1; \
1097 while (fullness[i] == 0) \
1098 i--; \
1099 table->first_packed = \
1100 table##_pack_iterator(&table->chunks[i], \
1101 fullness[i] - 1); \
1102 } \
1103 \
1104 if (fullness != stack_fullness) \
1105 free(fullness); \
1106 } \
1107 \
1108 if (orig_chunks != hash_table_empty_chunk) \
1109 free(orig_chunks); \
1110 return true; \
1111 \
1112 err: \
1113 free(table->chunks); \
1114 table->chunks = orig_chunks; \
1115 table##_set_chunk_count(table, orig_chunk_count); \
1116 if (table##_vector_policy) \
1117 table->vector = orig_entries; \
1118 return false; \
1119 } \
1120 \
1121 static void table##_do_clear(struct table *table, bool reset) \
1122 { \
1123 if (table->chunks == hash_table_empty_chunk) \
1124 return; \
1125 \
1126 size_t chunk_count = table##_chunk_count(table); \
1127 /* Always reset large tables. */ \
1128 if (chunk_count >= 16) \
1129 reset = true; \
1130 if (!table##_empty(table)) { \
1131 if (!reset) { \
1132 size_t capacity_scale = \
1133 table##_chunk_capacity_scale(table->chunks); \
1134 memset(table->chunks, 0, \
1135 table##_chunk_alloc_size(chunk_count, \
1136 capacity_scale)); \
1137 table##_chunk_mark_eof(table->chunks, capacity_scale); \
1138 } \
1139 if (!table##_vector_policy) \
1140 table->first_packed = 0; \
1141 table##_set_size(table, 0); \
1142 } \
1143 if (reset) { \
1144 free(table->chunks); \
1145 table->chunks = hash_table_empty_chunk; \
1146 table##_set_chunk_count(table, 1); \
1147 if (table##_vector_policy) \
1148 table->vector = NULL; \
1149 } \
1150 } \
1151 \
1152 __attribute__((__unused__)) \
1153 static bool table##_reserve(struct table *table, size_t capacity) \
1154 { \
1155 capacity = max(capacity, table##_size(table)); \
1156 if (!capacity) { \
1157 table##_do_clear(table, true); \
1158 return true; \
1159 } \
1160 \
1161 size_t orig_chunk_count = table##_chunk_count(table); \
1162 size_t orig_capacity_scale = table##_chunk_capacity_scale(table->chunks);\
1163 size_t orig_capacity = table##_compute_capacity(orig_chunk_count, \
1164 orig_capacity_scale); \
1165 \
1166 /* \
1167 * To avoid pathological behavior, ignore decreases that aren't at \
1168 * least a 1/8 decrease, and double for increases that aren't at least \
1169 * a 1/8 increase. \
1170 */ \
1171 if (capacity <= orig_capacity && \
1172 capacity >= orig_capacity - orig_capacity / 8) \
1173 return true; \
1174 bool attempt_exact = !(capacity > orig_capacity && \
1175 capacity < orig_capacity + orig_capacity / 8); \
1176 \
1177 size_t new_chunk_count; \
1178 size_t new_capacity_scale; \
1179 if (!table##_compute_chunk_count_and_scale(capacity, attempt_exact, \
1180 table##_vector_policy && \
1181 attempt_exact, \
1182 &new_chunk_count, \
1183 &new_capacity_scale)) \
1184 return false; \
1185 size_t new_capacity = table##_compute_capacity(new_chunk_count, \
1186 new_capacity_scale); \
1187 if (new_capacity == orig_capacity) \
1188 return true; \
1189 return table##_rehash(table, orig_chunk_count, orig_capacity_scale, \
1190 new_chunk_count, new_capacity_scale); \
1191 } \
1192 \
1193 __attribute__((__unused__)) \
1194 static void table##_clear(struct table *table) \
1195 { \
1196 table##_do_clear(table, false); \
1197 } \
1198 \
1199 \
1200 HASH_TABLE_SEARCH_IMPL(table, search_by_key, table##_key_type, \
1201 table##_item_to_key, eq_func) \
1202 HASH_TABLE_SEARCH_IMPL(table, search_by_index, uint32_t, \
1203 HASH_TABLE_SEARCH_BY_INDEX_ITEM_TO_KEY, scalar_key_eq) \
1204 \
1205 \
1206 static struct table##_iterator \
1207 table##_search_hashed(struct table *table, const table##_key_type *key, \
1208 struct hash_pair hp) \
1209 { \
1210 struct table##_iterator it = table##_search_by_key(table, key, hp); \
1211 /* Convert the item iterator to a public iterator. */ \
1212 if (table##_vector_policy && it.item) { \
1213 it.entry = table##_item_to_entry(table, it.item); \
1214 it.lowest = table->vector; \
1215 } \
1216 return it; \
1217 } \
1218 \
1219 __attribute__((__unused__)) \
1220 static struct table##_iterator \
1221 table##_search(struct table *table, const table##_key_type *key) \
1222 { \
1223 return table##_search_hashed(table, key, table##_hash(key)); \
1224 } \
1225 \
1226 static bool table##_reserve_for_insert(struct table *table) \
1227 { \
1228 size_t orig_chunk_count = table##_chunk_count(table); \
1229 size_t orig_capacity_scale = table##_chunk_capacity_scale(table->chunks);\
1230 size_t orig_capacity = table##_compute_capacity(orig_chunk_count, \
1231 orig_capacity_scale); \
1232 size_t capacity = table##_size(table) + 1; \
1233 if (capacity <= orig_capacity) \
1234 return true; \
1235 /* Grow by at least orig_capacity * 2^0.5. */ \
1236 size_t min_growth = (orig_capacity + \
1237 (orig_capacity >> 2) + \
1238 (orig_capacity >> 3) + \
1239 (orig_capacity >> 5)); \
1240 capacity = max(capacity, min_growth); \
1241 size_t new_chunk_count, new_capacity_scale; \
1242 if (!table##_compute_chunk_count_and_scale(capacity, false, false, \
1243 &new_chunk_count, \
1244 &new_capacity_scale)) \
1245 return false; \
1246 return table##_rehash(table, orig_chunk_count, orig_capacity_scale, \
1247 new_chunk_count, new_capacity_scale); \
1248 } \
1249 \
1250 static void \
1251 table##_adjust_size_and_first_after_insert(struct table *table, \
1252 struct table##_chunk *chunk, \
1253 size_t index) \
1254 { \
1255 if (!table##_vector_policy) { \
1256 uintptr_t first_packed = table##_pack_iterator(chunk, index); \
1257 if (first_packed > table->first_packed) \
1258 table->first_packed = first_packed; \
1259 } \
1260 table##_increment_size(table); \
1261 } \
1262 \
1263 static int table##_insert_searched(struct table *table, \
1264 const table##_entry_type *entry, \
1265 struct hash_pair hp, \
1266 struct table##_iterator *it_ret) \
1267 { \
1268 if (!table##_reserve_for_insert(table)) \
1269 return -1; \
1270 \
1271 size_t index = hp.first; \
1272 struct table##_chunk *chunk = \
1273 &table->chunks[table##_modulo_by_chunk_count(table, index)]; \
1274 unsigned int first_empty = table##_chunk_first_empty(chunk); \
1275 if (first_empty == (unsigned int)-1) { \
1276 size_t delta = hash_table_probe_delta(hp); \
1277 do { \
1278 table##_chunk_inc_outbound_overflow_count(chunk); \
1279 index += delta; \
1280 chunk = &table->chunks[table##_modulo_by_chunk_count(table, index)];\
1281 first_empty = table##_chunk_first_empty(chunk); \
1282 } while (first_empty == (unsigned int)-1); \
1283 table##_chunk_adjust_hosted_overflow_count(chunk, \
1284 hosted_overflow_count_inc);\
1285 } \
1286 chunk->tags[first_empty] = hp.second; \
1287 if (table##_vector_policy) { \
1288 *table##_vector_item(&chunk->items[first_empty]) = \
1289 table##_size(table); \
1290 memcpy(&table->vector[table##_size(table)], entry, \
1291 sizeof(*entry)); \
1292 } else { \
1293 memcpy(&chunk->items[first_empty], entry, sizeof(*entry)); \
1294 } \
1295 table##_adjust_size_and_first_after_insert(table, chunk, first_empty); \
1296 if (it_ret) { \
1297 if (table##_vector_policy) { \
1298 it_ret->entry = \
1299 &table->vector[table##_size(table) - 1]; \
1300 it_ret->lowest = table->vector; \
1301 } else { \
1302 it_ret->item = &chunk->items[first_empty]; \
1303 it_ret->index = first_empty; \
1304 } \
1305 } \
1306 return 1; \
1307 } \
1308 \
1309 static int table##_insert_hashed(struct table *table, \
1310 const table##_entry_type *entry, \
1311 struct hash_pair hp, \
1312 struct table##_iterator *it_ret) \
1313 { \
1314 table##_key_type key = table##_entry_to_key(entry); \
1315 struct table##_iterator it = table##_search_hashed(table, &key, hp); \
1316 if (it.entry) { \
1317 if (it_ret) \
1318 *it_ret = it; \
1319 return 0; \
1320 } else { \
1321 return table##_insert_searched(table, entry, hp, it_ret); \
1322 } \
1323 } \
1324 \
1325 __attribute__((__unused__)) \
1326 static int table##_insert(struct table *table, \
1327 const table##_entry_type *entry, \
1328 struct table##_iterator *it_ret) \
1329 { \
1330 table##_key_type key = table##_entry_to_key(entry); \
1331 return table##_insert_hashed(table, entry, table##_hash(&key), it_ret); \
1332 } \
1333 \
1334 /* Similar to table##_next_impl() but for the cached first position. */ \
1335 static void table##_advance_first_packed(struct table *table) \
1336 { \
1337 uintptr_t packed = table->first_packed; \
1338 struct table##_chunk *chunk = table##_unpack_chunk(packed); \
1339 size_t index = table##_unpack_index(packed); \
1340 while (index > 0) { \
1341 index--; \
1342 if (chunk->tags[index]) { \
1343 table->first_packed = \
1344 table##_pack_iterator(chunk, index); \
1345 return; \
1346 } \
1347 } \
1348 \
1349 /* \
1350 * This is only called when there is another entry in the table, so we \
1351 * don't need to check if we hit the end. \
1352 */ \
1353 for (;;) { \
1354 chunk--; \
1355 unsigned int last = table##_chunk_last_occupied(chunk); \
1356 if (last != (unsigned int)-1) { \
1357 table->first_packed = \
1358 table##_pack_iterator(chunk, last); \
1359 return; \
1360 } \
1361 } \
1362 } \
1363 \
1364 static void \
1365 table##_adjust_size_and_first_before_delete(struct table *table, \
1366 struct table##_chunk *chunk, \
1367 size_t index) \
1368 { \
1369 table##_decrement_size(table); \
1370 if (!table##_vector_policy && \
1371 table##_pack_iterator(chunk, index) == table->first_packed) { \
1372 if (table##_empty(table)) \
1373 table->first_packed = 0; \
1374 else \
1375 table##_advance_first_packed(table); \
1376 } \
1377 } \
1378 \
1379 /* \
1380 * We want this inlined so that the whole function call can be optimized away \
1381 * in the likely_dead case, and so that the counter can be optimized away in \
1382 * the not likely_dead case. \
1383 */ \
1384 __attribute__((__always_inline__)) \
1385 static inline struct table##_iterator \
1386 table##_next_impl(struct table##_iterator it, bool likely_dead) \
1387 { \
1388 struct table##_chunk *chunk = table##_iterator_chunk(it); \
1389 while (it.index > 0) { \
1390 it.index--; \
1391 it.entry--; \
1392 if (likely(chunk->tags[it.index])) \
1393 return it; \
1394 } \
1395 \
1396 /* \
1397 * This hack is copied from the folly implementation: this is dead code \
1398 * if the return value is not used (e.g., the return value of \
1399 * table##_delete_iterator() is often ignored), but the compiler needs \
1400 * some help proving that the following loop terminates. \
1401 */ \
1402 for (size_t i = 1; !likely_dead || i != 0; i++) { \
1403 if (unlikely(table##_chunk_eof(chunk))) \
1404 break; \
1405 \
1406 chunk--; \
1407 unsigned int last = table##_chunk_last_occupied(chunk); \
1408 if (!likely_dead) \
1409 __builtin_prefetch(chunk - 1); \
1410 if (likely(last != (unsigned int)-1)) { \
1411 it.index = last; \
1412 it.item = &chunk->items[last]; \
1413 return it; \
1414 } \
1415 } \
1416 return (struct table##_iterator){}; \
1417 } \
1418 \
1419 static void table##_delete_impl(struct table *table, \
1420 struct table##_iterator item_it, \
1421 struct hash_pair hp) \
1422 { \
1423 struct table##_chunk *it_chunk = table##_iterator_chunk(item_it); \
1424 it_chunk->tags[item_it.index] = 0; \
1425 \
1426 table##_adjust_size_and_first_before_delete(table, it_chunk, \
1427 item_it.index); \
1428 \
1429 if (table##_chunk_hosted_overflow_count(it_chunk)) { \
1430 const size_t delta = hash_table_probe_delta(hp); \
1431 size_t index = hp.first; \
1432 uint8_t hosted_op = 0; \
1433 for (;;) { \
1434 struct table##_chunk *chunk = \
1435 &table->chunks[table##_modulo_by_chunk_count(table, index)];\
1436 if (chunk == it_chunk) { \
1437 table##_chunk_adjust_hosted_overflow_count(chunk,\
1438 hosted_op);\
1439 break; \
1440 } \
1441 table##_chunk_dec_outbound_overflow_count(chunk); \
1442 hosted_op = hosted_overflow_count_dec; \
1443 index += delta; \
1444 } \
1445 } \
1446 } \
1447 \
1448 static void table##_vector_delete_impl(struct table *table, \
1449 struct table##_iterator item_it, \
1450 struct hash_pair hp) \
1451 { \
1452 /* Delete the index from the table. */ \
1453 uint32_t index = *table##_vector_item(item_it.item); \
1454 table##_delete_impl(table, item_it, hp); \
1455 \
1456 /* Replace it with the last entry and update its index in the table. */ \
1457 uint32_t tail_index = table##_size(table); \
1458 if (tail_index != index) { \
1459 table##_entry_type *tail = \
1460 &table->vector[tail_index]; \
1461 table##_key_type tail_key = table##_entry_to_key(tail); \
1462 item_it = table##_search_by_index(table, &tail_index, \
1463 table##_hash(&tail_key)); \
1464 *table##_vector_item(item_it.item) = index; \
1465 memcpy(&table->vector[index], tail, sizeof(*tail)); \
1466 } \
1467 } \
1468 \
1469 /* \
1470 * We want this inlined so that the call to table##_next_impl() can be \
1471 * optimized away. \
1472 */ \
1473 __attribute__((__always_inline__)) \
1474 static inline struct table##_iterator \
1475 table##_delete_iterator_hashed(struct table *table, struct table##_iterator it, \
1476 struct hash_pair hp) \
1477 { \
1478 if (table##_vector_policy) { \
1479 uint32_t index = it.entry - it.lowest; \
1480 struct table##_iterator item_it = \
1481 table##_search_by_index(table, &index, hp); \
1482 table##_vector_delete_impl(table, item_it, hp); \
1483 if (index == 0) { \
1484 return (struct table##_iterator){}; \
1485 } else { \
1486 it.entry--; \
1487 return it; \
1488 } \
1489 } else { \
1490 table##_delete_impl(table, it, hp); \
1491 return table##_next_impl(it, true); \
1492 } \
1493 } \
1494 \
1495 __attribute__((__always_inline__, __unused__)) \
1496 static inline struct table##_iterator \
1497 table##_delete_iterator(struct table *table, struct table##_iterator it) \
1498 { \
1499 struct hash_pair hp = {}; \
1500 /* \
1501 * The basic policy only needs the hash if the chunk hosts an \
1502 * overflowed entry. \
1503 */ \
1504 if (table##_vector_policy || \
1505 table##_chunk_hosted_overflow_count(table##_iterator_chunk(it))) { \
1506 table##_key_type key = table##_entry_to_key(it.entry); \
1507 hp = table##_hash(&key); \
1508 } \
1509 return table##_delete_iterator_hashed(table, it, hp); \
1510 } \
1511 \
1512 static bool table##_delete_hashed(struct table *table, \
1513 const table##_key_type *key, \
1514 struct hash_pair hp) \
1515 { \
1516 struct table##_iterator item_it = table##_search_by_key(table, key, hp);\
1517 if (!item_it.item) \
1518 return false; \
1519 if (table##_vector_policy) \
1520 table##_vector_delete_impl(table, item_it, hp); \
1521 else \
1522 table##_delete_impl(table, item_it, hp); \
1523 return true; \
1524 } \
1525 \
1526 static bool table##_delete(struct table *table, const table##_key_type *key) \
1527 { \
1528 return table##_delete_hashed(table, key, table##_hash(key)); \
1529 } \
1530 \
1531 __attribute__((__unused__)) \
1532 static inline bool table##_delete_entry(struct table *table, \
1533 const table##_entry_type *entry) \
1534 { \
1535 const table##_key_type key = table##_entry_to_key(entry); \
1536 return table##_delete(table, &key); \
1537 } \
1538 \
1539 __attribute__((__unused__)) \
1540 static struct table##_iterator table##_first(struct table *table) \
1541 { \
1542 if (table##_vector_policy) { \
1543 table##_entry_type *entry; \
1544 if (table##_empty(table)) \
1545 entry = NULL; \
1546 else \
1547 entry = &table->vector[table##_size(table) - 1]; \
1548 return (struct table##_iterator){ \
1549 .entry = entry, \
1550 .lowest = table->vector, \
1551 }; \
1552 } else { \
1553 return table##_unpack_iterator(table->first_packed); \
1554 } \
1555 } \
1556 \
1557 __attribute__((__unused__)) \
1558 static struct table##_iterator table##_next(struct table##_iterator it) \
1559 { \
1560 if (table##_vector_policy) { \
1561 if (it.entry == it.lowest) { \
1562 return (struct table##_iterator){}; \
1563 } else { \
1564 it.entry--; \
1565 return it; \
1566 } \
1567 } else { \
1568 return table##_next_impl(it, false); \
1569 } \
1570 } \
1571 struct DEFINE_HASH_TABLE_needs_semicolon
1572
1573 /**
1574 * Define a hash table interface.
1575 *
1576 * This macro defines a hash table type along with its functions.
1577 *
1578 * @param[in] table Name of the type to define. This is prefixed to all of the
1579 * types and functions defined for that type.
1580 * @param[in] entry_type Type of entries in the table.
1581 * @param[in] entry_to_key Name of function or macro which is passed a <tt>const
1582 * entry_type *</tt> and returns the key for that entry. The return type is the
1583 * @c key_type of the hash table. The passed entry is never @c NULL.
1584 * @param[in] hash_func Hash function which takes a <tt>const key_type *</tt>
1585 * and returns a @ref hash_pair.
1586 * @param[in] eq_func Comparison function which takes two <tt>const key_type
1587 * *</tt> and returns a @c bool.
1588 */
1589 #define DEFINE_HASH_TABLE(table, entry_type, entry_to_key, hash_func, eq_func) \
1590 DEFINE_HASH_TABLE_TYPE(table, entry_type); \
1591 DEFINE_HASH_TABLE_FUNCTIONS(table, entry_to_key, hash_func, eq_func)
1592
1593 /**
1594 * Define a hash map type without defining its functions.
1595 *
1596 * The functions are defined with @ref DEFINE_HASH_MAP_FUNCTIONS().
1597 *
1598 * @sa DEFINE_HASH_MAP(), DEFINE_HASH_TABLE_TYPE()
1599 */
1600 #define DEFINE_HASH_MAP_TYPE(table, key_type, value_type) \
1601 struct table##_entry { \
1602 typeof(key_type) key; \
1603 typeof(value_type) value; \
1604 }; \
1605 DEFINE_HASH_TABLE_TYPE(table, struct table##_entry)
1606
1607 #define HASH_MAP_ENTRY_TO_KEY(entry) ((entry)->key)
1608
1609 /**
1610 * Define the functions for a hash map.
1611 *
1612 * The hash map type must have already been defined with @ref
1613 * DEFINE_HASH_MAP_TYPE().
1614 *
1615 * Unless the type and function definitions must be in separate places, use @ref
1616 * DEFINE_HASH_MAP() instead.
1617 *
1618 * @sa DEFINE_HASH_TABLE_FUNCTIONS
1619 */
1620 #define DEFINE_HASH_MAP_FUNCTIONS(table, hash_func, eq_func) \
1621 DEFINE_HASH_TABLE_FUNCTIONS(table, HASH_MAP_ENTRY_TO_KEY, hash_func, eq_func)
1622
1623 /**
1624 * Define a hash map interface.
1625 *
1626 * This is a higher-level wrapper for @ref DEFINE_HASH_TABLE() with entries of
1627 * the following type (with the example name @c hash_map):
1628 *
1629 * @code{.c}
1630 * struct hash_map_entry {
1631 * key_type key;
1632 * value_type value;
1633 * };
1634 * @endcode
1635 *
1636 * @param[in] table Name of the map type to define. This is prefixed to all of
1637 * the types and functions defined for that type.
1638 * @param[in] key_type Type of keys in the map.
1639 * @param[in] value_type Type of values in the map.
1640 * @param[in] hash_func See @ref DEFINE_HASH_TABLE().
1641 * @param[in] eq_func See @ref DEFINE_HASH_TABLE().
1642 */
1643 #define DEFINE_HASH_MAP(table, key_type, value_type, hash_func, eq_func) \
1644 DEFINE_HASH_MAP_TYPE(table, key_type, value_type); \
1645 DEFINE_HASH_MAP_FUNCTIONS(table, hash_func, eq_func)
1646
1647 /**
1648 * Define a hash set type without defining its functions.
1649 *
1650 * The functions are defined with @ref DEFINE_HASH_SET_FUNCTIONS().
1651 *
1652 * @sa DEFINE_HASH_SET(), DEFINE_HASH_TABLE_TYPE()
1653 */
1654 #define DEFINE_HASH_SET_TYPE DEFINE_HASH_TABLE_TYPE
1655
1656 #define HASH_SET_ENTRY_TO_KEY(entry) (*(entry))
1657
1658 /**
1659 * Define the functions for a hash set.
1660 *
1661 * The hash set type must have already been defined with @ref
1662 * DEFINE_HASH_SET_TYPE().
1663 *
1664 * Unless the type and function definitions must be in separate places, use @ref
1665 * DEFINE_HASH_SET() instead.
1666 *
1667 * @sa DEFINE_HASH_TABLE_FUNCTIONS
1668 */
1669 #define DEFINE_HASH_SET_FUNCTIONS(table, hash_func, eq_func) \
1670 DEFINE_HASH_TABLE_FUNCTIONS(table, HASH_SET_ENTRY_TO_KEY, hash_func, eq_func)
1671
1672 /**
1673 * Define a hash set interface.
1674 *
1675 * This is a higher-level wrapper for @ref DEFINE_HASH_TABLE() where @p
1676 * entry_type is the same as @p key_type.
1677 *
1678 * @param[in] table Name of the set type to define. This is prefixed to all of
1679 * the types and functions defined for that type.
1680 * @param[in] key_type Type of keys in the set.
1681 * @param[in] hash_func See @ref DEFINE_HASH_TABLE().
1682 * @param[in] eq_func See @ref DEFINE_HASH_TABLE().
1683 */
1684 #define DEFINE_HASH_SET(table, key_type, hash_func, eq_func) \
1685 DEFINE_HASH_SET_TYPE(table, key_type); \
1686 DEFINE_HASH_SET_FUNCTIONS(table, hash_func, eq_func)
1687
1688 /**
1689 * Empty hash table initializer.
1690 *
1691 * This can be used to initialize a hash table when declaring it.
1692 *
1693 * @sa hash_table_init()
1694 */
1695 #define HASH_TABLE_INIT { hash_table_empty_chunk }
1696
1697 /**
1698 * Define and initialize an empty @ref hash_table of type @p table_type named @p
1699 * table that is automatically deinitialized when it goes out of scope.
1700 */
1701 #define HASH_TABLE(table_type, table) \
1702 __attribute__((__cleanup__(table_type##_deinit))) \
1703 struct table_type table = HASH_TABLE_INIT
1704
1705 /**
1706 * Iterate over every entry in a @ref hash_table.
1707 *
1708 * @param[in] table_type Name of hash table type.
1709 * @param[out] it Name of iterator variable.
1710 * @param[in] table Hash table to iterate over.
1711 */
1712 #define hash_table_for_each(table_type, it, table) \
1713 for (struct table_type##_iterator it = table_type##_first(table); \
1714 it.entry; it = table_type##_next(it))
1715
1716 /**
1717 * @defgroup HashTableHelpers Hash table helpers
1718 *
1719 * Hash functions and comparators for use with @ref HashTables.
1720 *
1721 * F14 resolves collisions by double hashing. Rather than using two independent
1722 * hash functions, this provides two options for efficiently deriving a pair of
1723 * hashes from a single input hash function depending on whether the hash
1724 * function is _avalanching_. See @ref hash_pair_from_avalanching_hash() and
1725 * @ref hash_pair_from_non_avalanching_hash().
1726 *
1727 * This provides:
1728 * * Functions for double hashing common key types: `*_hash_pair()`.
1729 * * Primitives for double hashing more complicated key types.
1730 * * Equality functions for common key types: `*_eq()`.
1731 *
1732 * @{
1733 */
1734
1735 /**
1736 * Split an avalanching hash into a @ref hash_pair.
1737 *
1738 * A hash function is avalanching if each bit of the hash value has a 50% chance
1739 * of being the same for different inputs. This is true for cryptographic hash
1740 * functions as well as certain non-cryptographic hash functions including
1741 * CityHash, MurmurHash, SipHash, and xxHash. Simple hashes like DJBX33A, ad-hoc
1742 * combinations like `53 * x + y`, and the identity function are not
1743 * avalanching.
1744 *
1745 * We use the input hash value as the first hash and the upper bits of the input
1746 * hash value as the second hash (which would otherwise be discarded when
1747 * masking to select the bucket).
1748 */
1749 static inline struct hash_pair hash_pair_from_avalanching_hash(size_t hash)
1750 {
1751 return (struct hash_pair){
1752 .first = hash,
1753 .second = (hash >> (8 * sizeof(hash) - 8)) | 0x80,
1754 };
1755 }
1756
1757 /**
1758 * Mix a non-avalanching hash and split it into a @ref hash_pair.
1759 *
1760 * This is architecture-dependent.
1761 */
1762 static inline struct hash_pair hash_pair_from_non_avalanching_hash(size_t hash)
1763 {
1764 #if SIZE_MAX == 0xffffffffffffffff
1765 #ifdef __SSE4_2__
1766 /* 64-bit with SSE4.2 uses CRC32 */
1767 size_t c = _mm_crc32_u64(0, hash);
1768 return (struct hash_pair){
1769 .first = hash + c,
1770 .second = (c >> 24) | 0x80,
1771 };
1772 #else
1773 /* 64-bit without SSE4.2 uses a 128-bit multiplication-based mixer */
1774 static const uint64_t multiplier = UINT64_C(0xc4ceb9fe1a85ec53);
1775 uint64_t hi = ((unsigned __int128)hash * multiplier) >> 64;
1776 uint64_t lo = hash * multiplier;
1777 hash = hi ^ lo;
1778 hash *= multiplier;
1779 return (struct hash_pair){
1780 .first = hash >> 22,
1781 .second = ((hash >> 15) & 0x7f) | 0x80,
1782 };
1783 #endif
1784 #else
1785 #ifdef __SSE4_2__
1786 /* 32-bit with SSE4.2 uses CRC32 */
1787 size_t c = _mm_crc32_u32(0, hash);
1788 return (struct hash_pair){
1789 .first = hash + c,
1790 .second = (uint8_t)(~(c >> 25)),
1791 };
1792 #else
1793 /* 32-bit without SSE4.2 uses the 32-bit Murmur2 finalizer */
1794 hash ^= hash >> 13;
1795 hash *= 0x5bd1e995;
1796 hash ^= hash >> 15;
1797 return (struct hash_pair){
1798 .first = hash,
1799 .second = (uint8_t)(~(hash >> 25)),
1800 };
1801 #endif
1802 #endif
1803 }
1804
1805 #ifdef DOXYGEN
1806 /**
1807 * Double hash an integral key.
1808 *
1809 * This can be used for any integer key type.
1810 */
1811 struct hash_pair int_key_hash_pair(const T *key);
1812 #else
1813 #if SIZE_MAX == 0xffffffffffffffff
1814 static inline uint64_t hash_128_to_64(unsigned __int128 hash)
1815 {
1816 return cityhash_128_to_64(hash, hash >> 64);
1817 }
1818
1819 #define int_key_hash_pair(key) ({ \
1820 __auto_type _key = *(key); \
1821 _Static_assert(sizeof(_key) <= sizeof(unsigned __int128), \
1822 "unsupported integer size"); \
1823 sizeof(_key) > sizeof(size_t) ? \
1824 hash_pair_from_avalanching_hash(hash_128_to_64(_key)) : \
1825 hash_pair_from_non_avalanching_hash(_key); \
1826 })
1827 #else
1828 /* Thomas Wang downscaling hash function. */
1829 static inline uint32_t hash_64_to_32(uint64_t hash)
1830 {
1831 hash = (~hash) + (hash << 18);
1832 hash = hash ^ (hash >> 31);
1833 hash = hash * 21;
1834 hash = hash ^ (hash >> 11);
1835 hash = hash + (hash << 6);
1836 hash = hash ^ (hash >> 22);
1837 return hash;
1838 }
1839
1840 #define int_key_hash_pair(key) ({ \
1841 __auto_type _key = *(key); \
1842 _Static_assert(sizeof(_key) <= sizeof(uint64_t), \
1843 "unsupported integer size"); \
1844 sizeof(_key) > sizeof(size_t) ? \
1845 hash_pair_from_avalanching_hash(hash_64_to_32(_key)) : \
1846 hash_pair_from_non_avalanching_hash(_key); \
1847 })
1848 #endif
1849 #endif
1850
1851 #ifdef DOXYGEN
1852 /**
1853 * Double hash a pointer key.
1854 *
1855 * This can be used when the key is a pointer value (rather than the
1856 * dereferenced value).
1857 */
1858 struct hash_pair ptr_key_hash_pair(T * const *key);
1859 #else
1860 #define ptr_key_hash_pair(key) ({ \
1861 uintptr_t _ptr = (uintptr_t)*(key); \
1862 int_key_hash_pair(&_ptr); \
1863 })
1864 #endif
1865
1866 #ifdef DOXYGEN
1867 /**
1868 * Return whether two scalar keys are equal.
1869 *
1870 * This can be used as the key comparison function for any scalar key type
1871 * (e.g., integers, floating-point numbers, pointers).
1872 */
1873 bool scalar_key_eq(const T *a, const T *b);
1874 #else
1875 #define scalar_key_eq(a, b) ((bool)(*(a) == *(b)))
1876 #endif
1877
1878 /**
1879 * Hash two integers.
1880 *
1881 * This is an avalanching hash function. It can be used for any integer types.
1882 * The two integers can have different types.
1883 *
1884 * This can be used to combine input hash functions in order to hash records
1885 * with multiple fields (e.g., structures or arrays). For example:
1886 *
1887 * ```
1888 * struct point3d {
1889 * int x, y, z;
1890 * };
1891 *
1892 * static struct hash_pair point3d_key_hash_pair(const struct point3d *key)
1893 * {
1894 * return hash_pair_from_avalanching_hash(hash_combine(hash_combine(key->x, key->y), key->z));
1895 * }
1896 * ```
1897 *
1898 * Note that the input hash functions need not be avalanching; the output will
1899 * be avalanching regardless.
1900 */
1901 #ifdef DOXYGEN
1902 size_t hash_combine(T1 a, T2 b);
1903 #else
1904 #if SIZE_MAX == 0xffffffffffffffff
1905 #define hash_combine(a, b) ({ \
1906 _Static_assert(sizeof(a) <= sizeof(unsigned __int128) && \
1907 sizeof(b) <= sizeof(unsigned __int128), \
1908 "unsupported integer size"); \
1909 size_t _a = sizeof(a) > sizeof(size_t) ? hash_128_to_64(a) : (a); \
1910 size_t _b = sizeof(b) > sizeof(size_t) ? hash_128_to_64(b) : (b); \
1911 cityhash_128_to_64(_b, _a); \
1912 })
1913 #else
1914 #define hash_combine(a, b) ({ \
1915 _Static_assert(sizeof(a) <= sizeof(uint64_t) && \
1916 sizeof(b) <= sizeof(uint64_t), \
1917 "unsupported integer size"); \
1918 size_t _a = sizeof(a) > sizeof(size_t) ? hash_64_to_32(a) : (a); \
1919 size_t _b = sizeof(b) > sizeof(size_t) ? hash_64_to_32(b) : (b); \
1920 hash_64_to_32(((uint64_t)_a << 32) | _b); \
1921 })
1922 #endif
1923 #endif
1924
1925 /**
1926 * Hash a byte buffer.
1927 *
1928 * This is an avalanching hash function.
1929 */
1930 static inline size_t hash_bytes(const void *data, size_t len)
1931 {
1932 return cityhash_size_t(data, len);
1933 }
1934
1935 /**
1936 * Hash a null-terminated string.
1937 *
1938 * This is an avalanching hash function.
1939 */
1940 static inline size_t hash_c_string(const char *s)
1941 {
1942 return hash_bytes(s, strlen(s));
1943 }
1944
1945 #ifdef DOXYGEN
1946 /** Double hash a null-terminated string key. */
1947 struct hash_pair c_string_key_hash_pair(const char * const *key);
1948 #else
1949 /* This is a macro so that it works with char * and const char * keys. */
1950 #define c_string_key_hash_pair(key) \
1951 hash_pair_from_avalanching_hash(hash_c_string(*(key)))
1952 #endif
1953
1954 #ifdef DOXYGEN
1955 /** Compare two null-terminated string keys for equality. */
1956 bool c_string_key_eq(const char * const *a, const char * const *b);
1957 #else
1958 #define c_string_key_eq(a, b) ((bool)(strcmp(*(a), *(b)) == 0))
1959 #endif
1960
1961 /** Double hash a @ref nstring. */
1962 static inline struct hash_pair nstring_hash_pair(const struct nstring *key)
1963 {
1964 return hash_pair_from_avalanching_hash(hash_bytes(key->str, key->len));
1965 }
1966
1967 /** @} */
1968
1969 /** @} */
1970
1971 #endif /* DRGN_HASH_TABLE_H */