# hash.inl ## Overview
`hash.inl` implements typed hash tables and sets in C. Example: ~~~c struct TM_HASH_T(key_t, value_t) hash = {.allocator = a}; tm_hash_add(&hash, key, val); value_t val = tm_hash_get(&hash, key); ~~~ The hashes in this file map from an arbitrary 64-bit key type `K` (e.g. `uint64_t`, `T *`, `tm_tt_id_t`, `tm_entity_t`, ...) to an arbitrary value type `V`. Only 64-bit key types are supported. If your hash key is smaller, extend it to 64 bits. If your hash key is bigger (such as a string), pre-hash it to a 64-bit value and use *that* as your key. If you use a pre-hash, note that the hash table implementation here doesn't provide any protection against collisions in the *pre-hash*. Instead, we just rely on the fact that such collisions are statistically improbable. !!! NOTE If such collisions become a problem in the future, we might add support for 128-bit keys to reduce their probability further. The hash table uses two sentinel key values to mark unused and deleted keys in the hash table: `TM_HASH_UNUSED = 0xffffffffffffffff` and `TM_HASH_TOMBSTONE = 0xfffffffffffffffe`. Note that these values can't be used as keys for the hash table. If you are using a hash function to generate the key, we again rely on the statistical improbability that it would produce either of these values. (You could also modify your hash function so that these values are never produced.) !!! WARNING: Rvalues Since we take the address of the key passed to `tm_hash_get()` you can't use an rvalue for the key: ~~~c // Instead of: tm_hash_get(&h, 3); // Write: tm_hash_get(&h, (uint64_t){3}); // Or: tm_hash_get_rv(&h, 3); ~~~ ### Implementation notes `hash.inl` uses a macro (`TM_TT_HASH_T`) to define a struct with `keys` and `values` arrays as well as some additional helper fields. Macros (`tm_hash_get()`, etc) are used to provide type safety. By doing things like: ~~~c h->values[i] = value ~~~ in the macro, the compiler will ensure that `value` matches the type of `h->values`. Sometimes we do this *just* as a type check, i.e. no code will actually execute, with a construct such as: ~~~c 0 && (h->keys[0] = key, 0) ~~~ For more advanced operations, the macros call out to C functions. Note that when we do this, all the type information is erased, as C doesn't support generics. I.e., all data is passed as `void *` with additional information to specify the size (in bytes) of the data. The keys are required to be unique 64-bit values. !!! TIP: Use a separate array for large values We allocate the `values` array to the same size as the `keys` array, so if the `keys` array has 50 % fillrate, the `values` array will too. This will waste space if the value type is large. If you want to use large values, we suggest you store them in a separate, dense array and just store indices into that array in the hash table. The `keys` array is always a power-of-two in size. This is important, because it means we can map the `key` to an index with a bit shift, which is significantly cheaper than a modulus operation. Bit shifts can have bad patterns with certain input keys, such as not using the full key entropy. We try to address this with a pre-mix of the key, but it's a bit tricky because doing too much pre-mixing will hurt performance. Still trying to find a good balance. We use linear probing to find they key (or an unused slot in case of an `add`). Removed items are marked with a `TOMBSTONE`. Both the `TOMBSTONE` and the `UNUSED` marker are actual keys (with the patterns `0xfffffffffffffffe` and `0xffffffffffffffff` respectively). It's illegal to use these keys in the hash table. Currently, the hash table will grow (by doubling in size) when it's 75 % full. This gives an average fill rate of (75 + 75/2)/2 = 56 %. A default value is stored in the struct. This is returned when the key is not found and is by default zero-initialized with the rest of the struct. The defalut value is also stored in the slot `values[-1]`. This allows us to implement `tm_hash_get()` with just one lookup of the hash index `h->values[tm_hash_index(h,key)]` where `tm_hash_index()` has been implemented to return `-1` for missing keys. Note that this means that if you want to change the default value of a non-empty hash (not recommended), you must also change `values[-1]`. Rvalue issue : To pass the key to the C functions, we have to take its address with `&key`. Unfortunately, this means that we can't use rvalues for keys. If all our target compiler versions supported the `typeof()` operator, we could fix this in the future by using a temp array for the key: ~~~c (typeof(key)[1]){key} ~~~ Default value at `values[-1]` : Having the default value at `values[-1]` has the drawback of requiring an extra memory slot and making the values array not power-of-two sized. We could fix this by using either the [GNU extension that allows for local macro variables](https://gcc.gnu.org/onlinedocs/cpp/Duplication-of-Side-Effects.html) or the [typeof()](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) extension. Unfortunately, neither of these are available in Visual Studio (and we want to keep compatibility with the Visual Studio compiler). To do : Should we support other key widths? 32-bit? 128-bit? ### Possible improvements Robin Hood hashing : We could use Robin Hood hashing to shorten searches in the case of collisions. The main benefit of this is to be able to tolerate a higher fill-rate. (With Robin Hood hashing, fill-rates of up to 90 % are possible.) However, since our hash table is always a power of two in size, our average fill rate can theoretically never be higher than 75 % anyway. Adding Robin Hood hashing and growing at 90 % would only up our average fill rate from 56 % to 68 %. Doesn't seem like the added complexity is worth that minor improvement. Add a control word array : We could add a control word array with 1 byte per element containing tombstone/unused flags as well as 7 bits of the hash value, as described in [Designing a Fast, Efficient, Cache-friendly Hash Table](https://www.youtube.com/watch?v=ncHmEUmJZf4&3342). This would bring several advantages: * It allows us to to search 16 elements at a time using AVX. (For a match against the stored 7 hash bits.) * Since we are always searching 16 elements at a time, tombstones can be reused unless the whole 16-element group is full. This makes the hash behave better when there are lots of remove operations. * With tombstones and unused elements marked in the control word, we no longer need special key values for them which makes our hashes more universal. However, it seems like the control word *mainly* speeds things up when there are collisions. Is the extra overhead worth it when we don't have a lot of collisions? Would need some testing to find out. Reduce clustering : Linear probing is fast and cache friendly but prone to clustering. Maybe a compromise is to use groups for this too? I.e. search the group (16 elements) linearly and then use a non-linear probe to find the next group to search.
## Index



Standard hash and set types

Rvalue macros
## API
Sentinel key value that represents a removed key. Note that this value can never be used as an actual key, or there will be trouble. ~~~c static const uint64_t TM_HASH_TOMBSTONE = 0xfffffffffffffffeULL; ~~~
Sentinel key value that represents an unused key. Note that this value can never be used as an actual key, or there will be trouble. ~~~c static const uint64_t TM_HASH_UNUSED = 0xffffffffffffffffULL; ~~~


Macros for manipulating hashes. ### `TM_HASH_T()`
~~~c #define TM_HASH_T(K, V) {...} ~~~ Macro that defines a struct representing a hash from type `K` keys to type `V` values. You can either use the macro directly to declare a variable or use it to create a typedef. ~~~c struct TM_HASH_T(uint64_t, const char *) my_hash; typedef struct TM_HASH_T(void *, void *) ptr_lookup; ~~~ The macro expands to the following struct: ~~~c struct { // Number of items in the `keys` and `values` arrays. Note that this is not the same as // the number of valid items in the hash table, because some items will be `UNUSED`, or // used for `TOMBSTONE`s. You can use `num_buckets` to loop over the `keys` and `values` // arrays to iterate over all hash table items. uint32_t num_buckets; // Number of items in the `keys` array used either for real values or `TOMBSTONE`s. (This // is used to determine fill rate.) uint32_t num_used; // Temp storage for an index value. int32_t temp; // Arrays of hash table keys and values. // // Note that these arrays are actually allocated together using a single allocation and // thus will be sequential in memory. K *keys; V *values; // Allocator used to grow the hash table. // // You can create a statically allocated hash table by statically allocating the `keys` // and `values` arrays and using `NULL` for the `allocator`. A statically allocated hash // table cannot grow beyond the initial `num_buckets` value. Note that you must take care // to use a power-of-two value for `num_buckets` if you set it yourself. struct tm_allocator_i *allocator; // Default value of the hash table. This will be returned if you call `tm_hash_get()` with a missing // key. The default value should be set when you initialize the hash struct. If you change the // default value of a non-empty hash (not recommended), you must also change `values[-1]` // because it caches a copy of the default value. V default_value; } ~~~
### `tm_hash_skip_key()`
~~~c #define tm_hash_skip_key(h, keyptr) {...} ~~~ Returns *true* if `keyptr` should be skipped when iterating over `h` (i.e., `*keyptr` is a `TOMBSTONE` or `UNUSED` value): ~~~c for (const K* k = ht.keys; k < ht.keys + ht.num_buckets; ++k) { if (tm_hash_skip_key(&ht, k)) continue; .... } ~~~
### `tm_hash_use_key()`
~~~c #define tm_hash_use_key(h, keyptr) {...} ~~~ The opposite of `tm_hash_skip_key()`.
### `tm_hash_skip_index()`
~~~c #define tm_hash_skip_index(h, index) {...} ~~~ Returns *true* if index should be skipped when iterating over the hash table (i.e. if it contains a `TOMBSTONE` or `UNUSED` value). ~~~c for (uint32_t i = 0; i < ht.num_buckets; ++i) { if (tm_hash_skip_index(&ht, i)) continue; .... } ~~~
### `tm_hash_use_index()`
~~~c #define tm_hash_use_index(h, index) {...} ~~~ The opposite of `tm_hash_skip_index()`.
### `tm_hash_index()`
~~~c #define tm_hash_index(h, key) {...} ~~~ Returns the index in the hash table where the `key` is stored, or `-1` if `key` is not in the hash table.
### `tm_hash_has()`
~~~c #define tm_hash_has(h, key) (tm_hash_index(h, key) != -1) ~~~ Returns *true* if the hash table contains `key`.
### `tm_hash_count()`
~~~c #define tm_hash_count(h) (tm_hash__num_real_keys((const uint64_t *)(h)->keys, (h)->num_buckets)) ~~~ Counts the number of real keys is the hash table.
### `tm_hash_get()`
~~~c #define tm_hash_get(h, key) {...} ~~~ Returns the value stored for `key` in the hash table. If the key has not been stored, the `default_value` of the hash table is returned.
### `tm_hash_get_default()`
~~~c #define tm_hash_get_default(h, key, default_value, temp) {...} ~~~ As `tm_hash_get()`, but uses the explicitly passed `default_value`, instead of the default value set in the hash table. `temp` should be an `int32_t`. It is used to cache the index lookup so it doesn't have to be made twice.
### `tm_hash_add()`
~~~c #define tm_hash_add(h, key, value) {...} ~~~ Adds the pair `(key, value)` to the hash table.
### `tm_hash_add_reference()`
~~~c #define tm_hash_add_reference(h, key) {...} ~~~ As `tm_hash_add()` but returns a pointer to the value. The returned pointer is valid until the hash table is modified. If the key was added to the hash table by this operation, the value is set to the default value. If the key already existed, the value remains unchanged.
### `tm_hash_update()`
~~~c #define tm_hash_update(h, key, value) {...} ~~~ If `key` exists, sets the corresponding `value`, otherwise does nothing. Note that unlike `tm_hash_add()`, `tm_hash_update()` will never allocate memory.
### `tm_hash_remove()`
~~~c #define tm_hash_remove(h, key) {...} ~~~ Removes the value with the specified `key`. Removing a value never reallocates the hash table.
### `tm_hash_clear()`
~~~c #define tm_hash_clear(h) (((h)->keys ? memset((h)->keys, 0xff, (h)->num_buckets * sizeof(*(h)->keys)) : (h)->keys), (h)->num_used = 0) ~~~ Clears the hash table. This does not free any memory. The array will keep the same number of buckets, but all the keys and values will be erased.
### `tm_hash_free()`
~~~c #define tm_hash_free(h) (tm_hash__free((uint64_t **)&(h)->keys, &(h)->num_used, &(h)->num_buckets, (void **)&(h)->values, sizeof(*(h)->values), (h)->allocator, __FILE__, __LINE__)) ~~~ Frees the hash table.
### `tm_hash_copy()`
~~~c #define tm_hash_copy(h, from) {...} ~~~ Copies the hash table `from` to `h`.
### `tm_hash_reserve()`
~~~c #define tm_hash_reserve(h, num_elements) {...} ~~~ Reserves space in the hash table for `num_elements` new elements. The hash table will be resized so that its size is a power-of-two and adding `num_elements` elements will keep it below the target fillrate (currently 70 %). If the hash table already has room for `num_elements` new elements, this function is a NOP.


Macros for set manipulation. ### `TM_SET_T()`
~~~c #define TM_SET_T(K) {...} ~~~ Macro that defines a struct representing a set of `K` keys. The set implementation is identical to the hash table implementation, except it doesn't have a `values` array.
### `tm_set_index()`
~~~c #define tm_set_index(h, key) tm_set_index(h, key) ~~~ Returns the index in the set where the `key` is stored, or `-1` if `key` is not in the set.
### `tm_set_has()`
~~~c #define tm_set_has(h, key) tm_hash_has(h, key) ~~~ Returns *true* if the set contains `key`.
### `tm_set_count()`
~~~c #define tm_set_count(h) tm_hash_count(h) ~~~ Counts the number of real keys is the set.
### `tm_set_add()`
~~~c #define tm_set_add(h, key) (tm_hash__add((uint64_t **)&(h)->keys, &(h)->num_used, &(h)->num_buckets, *(uint64_t *)&key, NULL, 0, (h)->allocator, __FILE__, __LINE__, NULL)[(h)->keys] = key, 0) ~~~ Adds the `key` to the set. Note that this might reallocate the set.
### `tm_set_remove()`
~~~c #define tm_set_remove(h, key) tm_hash_remove(h, key) ~~~ Removes the value with the specified `key`. Removing a value never reallocates set.
### `tm_set_clear()`
~~~c #define tm_set_clear(h) tm_hash_clear(h) ~~~ Clears the set. This does not free any memory.
### `tm_set_free()`
~~~c #define tm_set_free(h) (tm_hash__free((uint64_t **)&(h)->keys, &(h)->num_used, &(h)->num_buckets, NULL, 0, (h)->allocator, __FILE__, __LINE__)) ~~~ Frees the set.
### `tm_set_copy()`
~~~c #define tm_set_copy(h, from) {...} ~~~ Copies the set `from` to `h`.
### `tm_set_reserve()`
~~~c #define tm_set_reserve(h, num_elements) {...} ~~~ Reserves space in the set for `num_elements` new elements.
### `tm_set_skip_key()`
~~~c #define tm_set_skip_key(s, keyptr) tm_hash_skip_key(s, keyptr) ~~~ Identical to `tm_hash_skip_key()`.
### `tm_set_use_key()`
~~~c #define tm_set_use_key(s, keyptr) tm_hash_use_key(s, keyptr) ~~~ Identical to `tm_hash_use_key()`.
### `tm_set_skip_index()`
~~~c #define tm_set_skip_index(s, index) tm_hash_skip_index(s, index) ~~~ Identical to `tm_hash_skip_index()`.
### `tm_set_use_index()`
~~~c #define tm_set_use_index(s, index) tm_hash_use_index(s, index) ~~~ Identical to `tm_hash_use_index()`.

Standard hash and set types

Defines some commonly used set and hash types. ### `tm_hash64_t`
~~~c typedef struct tm_hash64_t TM_HASH_T(uint64_t, uint64_t) tm_hash64_t; ~~~ Maps from an `uint64_t` key to an `uint64_t` value.
### `tm_hash32_t`
~~~c typedef struct tm_hash32_t TM_HASH_T(uint64_t, uint32_t) tm_hash32_t; ~~~ Maps from an `uint64_t` key to a `uint32_t` value.
### `tm_hash64_float_t`
~~~c typedef struct tm_hash64_float_t TM_HASH_T(uint64_t, float) tm_hash64_float_t; ~~~ Maps from an `uint64_t` key to a `float` value.
### `tm_hash_id_to_id_t`
~~~c typedef struct tm_hash_id_to_id_t TM_HASH_T(tm_tt_id_t, tm_tt_id_t) tm_hash_id_to_id_t; ~~~ Maps from an `tm_tt_id_t` key to a `tm_tt_id_t` value.
### `tm_set_t`
~~~c typedef struct tm_set_t TM_SET_T(uint64_t) tm_set_t; ~~~ Represents a set of `uint64_t` keys.
### `tm_set_id_t`
~~~c typedef struct tm_set_id_t TM_SET_T(tm_tt_id_t) tm_set_id_t; ~~~ Represents a set of `tm_tt_id_t` keys.
### `tm_set_strhash_t`
~~~c typedef struct tm_set_strhash_t TM_SET_T(tm_strhash_t) tm_set_strhash_t; ~~~ Represents a set of hashed strings.

Rvalue macros

These macros can be used when you have an `uint64_t` rvalue that you want to use as the key. They automatically wrap the key in `(uint64_t){ key }`. Note that if the key type of your hash is something other than an `uint64_t`, these macros won't work. ### `tm_hash_has_rv()`
~~~c #define tm_hash_has_rv(h, key) tm_hash_has(h, (uint64_t){ key }) ~~~
### `tm_hash_get_rv()`
~~~c #define tm_hash_get_rv(h, key) tm_hash_get(h, (uint64_t){ key }) ~~~
### `tm_hash_add_rv()`
~~~c #define tm_hash_add_rv(h, key, value) tm_hash_add(h, (uint64_t){ key }, value) ~~~
### `tm_hash_add_reference_rv()`
~~~c #define tm_hash_add_reference_rv(h, key) tm_hash_add_reference(h, (uint64_t){ key }) ~~~
### `tm_hash_update_rv()`
~~~c #define tm_hash_update_rv(h, key, value) tm_hash_update(h, (uint64_t){ key }, value) ~~~
### `tm_hash_remove_rv()`
~~~c #define tm_hash_remove_rv(h, key) tm_hash_remove(h, (uint64_t){ key }) ~~~
### `tm_set_has_rv()`
~~~c #define tm_set_has_rv(h, key) tm_set_has(h, (uint64_t){ key }) ~~~
### `tm_set_add_rv()`
~~~c #define tm_set_add_rv(h, key) tm_set_add(h, (uint64_t){ key }) ~~~
### `tm_set_remove_rv()`
~~~c #define tm_set_remove_rv(h, key) tm_set_remove(h, (uint64_t){ key }) ~~~