+struct ordered_hashmap_entry {
+ struct plain_hashmap_entry p;
+ unsigned iterate_next, iterate_previous;
+};
+
+struct set_entry {
+ struct hashmap_base_entry b;
+};
+
+/* In several functions it is advantageous to have the hash table extended
+ * virtually by a couple of additional buckets. We reserve special index values
+ * for these "swap" buckets. */
+#define _IDX_SWAP_BEGIN (UINT_MAX - 3)
+#define IDX_PUT (_IDX_SWAP_BEGIN + 0)
+#define IDX_TMP (_IDX_SWAP_BEGIN + 1)
+#define _IDX_SWAP_END (_IDX_SWAP_BEGIN + 2)
+
+#define IDX_FIRST (UINT_MAX - 1) /* special index for freshly initialized iterators */
+#define IDX_NIL UINT_MAX /* special index value meaning "none" or "end" */
+
+assert_cc(IDX_FIRST == _IDX_SWAP_END);
+assert_cc(IDX_FIRST == _IDX_ITERATOR_FIRST);
+
+/* Storage space for the "swap" buckets.
+ * All entry types can fit into a ordered_hashmap_entry. */
+struct swap_entries {
+ struct ordered_hashmap_entry e[_IDX_SWAP_END - _IDX_SWAP_BEGIN];
+};
+
+/* Distance from Initial Bucket */
+typedef uint8_t dib_raw_t;
+#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
+#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
+#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
+#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
+
+#define DIB_FREE UINT_MAX
+
+#ifdef ENABLE_HASHMAP_DEBUG
+struct hashmap_debug_info {
+ LIST_FIELDS(struct hashmap_debug_info, debug_list);
+ unsigned max_entries; /* high watermark of n_entries */
+
+ /* who allocated this hashmap */
+ int line;
+ const char *file;
+ const char *func;
+
+ /* fields to detect modification while iterating */
+ unsigned put_count; /* counts puts into the hashmap */
+ unsigned rem_count; /* counts removals from hashmap */
+ unsigned last_rem_idx; /* remembers last removal index */
+};
+
+/* Tracks all existing hashmaps. Get at it from gdb. See sd_dump_hashmaps.py */
+static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);
+
+#define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
+
+#else /* !ENABLE_HASHMAP_DEBUG */
+#define HASHMAP_DEBUG_FIELDS
+#endif /* ENABLE_HASHMAP_DEBUG */
+
+enum HashmapType {
+ HASHMAP_TYPE_PLAIN,
+ HASHMAP_TYPE_ORDERED,
+ HASHMAP_TYPE_SET,
+ _HASHMAP_TYPE_MAX
+};
+
+struct _packed_ indirect_storage {
+ char *storage; /* where buckets and DIBs are stored */
+ uint8_t hash_key[HASH_KEY_SIZE]; /* hash key; changes during resize */
+
+ unsigned n_entries; /* number of stored entries */
+ unsigned n_buckets; /* number of buckets */
+
+ unsigned idx_lowest_entry; /* Index below which all buckets are free.
+ Makes "while(hashmap_steal_first())" loops
+ O(n) instead of O(n^2) for unordered hashmaps. */
+ uint8_t _pad[3]; /* padding for the whole HashmapBase */
+ /* The bitfields in HashmapBase complete the alignment of the whole thing. */
+};
+
+struct direct_storage {
+ /* This gives us 39 bytes on 64bit, or 35 bytes on 32bit.
+ * That's room for 4 set_entries + 4 DIB bytes + 3 unused bytes on 64bit,
+ * or 7 set_entries + 7 DIB bytes + 0 unused bytes on 32bit. */
+ char storage[sizeof(struct indirect_storage)];
+};
+
+#define DIRECT_BUCKETS(entry_t) \
+ (sizeof(struct direct_storage) / (sizeof(entry_t) + sizeof(dib_raw_t)))
+
+/* We should be able to store at least one entry directly. */
+assert_cc(DIRECT_BUCKETS(struct ordered_hashmap_entry) >= 1);
+
+/* We have 3 bits for n_direct_entries. */
+assert_cc(DIRECT_BUCKETS(struct set_entry) < (1 << 3));
+
+/* Hashmaps with directly stored entries all use this shared hash key.
+ * It's no big deal if the key is guessed, because there can be only
+ * a handful of directly stored entries in a hashmap. When a hashmap
+ * outgrows direct storage, it gets its own key for indirect storage. */
+static uint8_t shared_hash_key[HASH_KEY_SIZE];
+static bool shared_hash_key_initialized;
+
+/* Fields that all hashmap/set types must have */
+struct HashmapBase {
+ const struct hash_ops *hash_ops; /* hash and compare ops to use */
+
+ union _packed_ {
+ struct indirect_storage indirect; /* if has_indirect */
+ struct direct_storage direct; /* if !has_indirect */
+ };
+
+ enum HashmapType type:2; /* HASHMAP_TYPE_* */
+ bool has_indirect:1; /* whether indirect storage is used */
+ unsigned n_direct_entries:3; /* Number of entries in direct storage.
+ * Only valid if !has_indirect. */
+ bool from_pool:1; /* whether was allocated from mempool */
+ HASHMAP_DEBUG_FIELDS /* optional hashmap_debug_info */
+};
+
+/* Specific hash types
+ * HashmapBase must be at the beginning of each hashmap struct. */
+