Fixed-size open-adressing hashtable (robin hood hashing)
More...
#include "fnvhash.h"
#include "is_pow2.h"
#include "murmurhash.h"
#include "paste.h"
#include "round_up_pow2.h"
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
Go to the source code of this file.
|
struct | fhashtable_slot |
| Generated hashtable slot struct type for a given KEY_TYPE and VALUE_TYPE . More...
|
|
struct | fhashtable |
| Generated hashtable struct type for a given KEY_TYPE and VALUE_TYPE . More...
|
|
|
#define | FHASHTABLE_EMPTY_SLOT_OFFSET (UINT32_MAX) |
| Offset constant used to flag empty slots.
|
|
#define | fhashtable_for_each(self, index, key_, value_) |
| Iterate over the non-empty slots in the hashtable in arbitary order.
|
|
#define | fhashtable_calc_sizeof(fhashtable_name, capacity) |
| Calculate the size of the hashtable struct. No overflow checks.
|
|
#define | fhashtable_calc_sizeof_overflows(fhashtable_name, capacity) |
| Check for a given capacity, if the equivalent size of the hashtable struct overflows.
|
|
#define | NAME fhashtable |
| Prefix to hashtable types and operations. This must be manually defined before including this header file.
|
|
#define | KEY_TYPE int |
| The key type. This must be manually defined before including this header file.
|
|
#define | VALUE_TYPE int |
| The value type. This must be manually defined before including this header file.
|
|
#define | KEY_IS_EQUAL(a, b) |
| Used to compare two keys This must be manually defined before including this header file.
|
|
#define | HASH_FUNCTION(key) |
| Used to compute indicies of keys. This must be manually defined before including this header file.
|
|
|
static fhashtable_type * | fhashtable_init (fhashtable_type *self, const uint32_t pow2_capacity) |
| Initialize a hashtable struct, given a (power-of-2) capacity.
|
|
static fhashtable_type * | fhashtable_create (const uint32_t min_capacity) |
| Create an hashtable with a given capacity with malloc().
|
|
static void | fhashtable_destroy (fhashtable_type *self) |
| Destroy an hashtable struct and free the underlying memory with free().
|
|
static bool | fhashtable_is_empty (const fhashtable_type *self) |
| Return whether the hashtable is empty.
|
|
static bool | fhashtable_is_full (const fhashtable_type *self) |
| Return whether the hashtable is full.
|
|
static bool | fhashtable_contains_key (const fhashtable_type *self, const KEY_TYPE key) |
| Check if hashtable contains a key.
|
|
static VALUE_TYPE * | fhashtable_get_value_mut (fhashtable_type *self, const KEY_TYPE key) |
| From a given key, get the pointer to the corresponding value in the hashtable.
|
|
static VALUE_TYPE | fhashtable_get_value (const fhashtable_type *self, const KEY_TYPE key, VALUE_TYPE default_value) |
| From a given key, get the copy of the corresponding value in the hashtable.
|
|
static VALUE_TYPE * | fhashtable_search (fhashtable_type *self, const KEY_TYPE key) |
| Search a given key in the hashtable and get the pointer to the corresponding value.
|
|
static void | fhashtable_insert (fhashtable_type *self, KEY_TYPE key, VALUE_TYPE value) |
| Insert a non-duplicate key and it's corresponding value inside the hashtable.
|
|
static void | fhashtable_update (fhashtable_type *self, KEY_TYPE key, VALUE_TYPE value) |
| Update a key's corresponding value inside the hashtable. Allows duplicates.
|
|
static bool | fhashtable_delete (fhashtable_type *self, const KEY_TYPE key) |
| Delete a key and it's corresponding value from the hashtable.
|
|
static void | fhashtable_clear (fhashtable_type *self) |
| Clear an existing hashtable and flag all slots as empty.
|
|
static void | fhashtable_copy (fhashtable_type *restrict dest_ptr, const fhashtable_type *restrict src_ptr) |
| Copy the values from a source hashtable to a destination hashtable.
|
|
Fixed-size open-adressing hashtable (robin hood hashing)
Ensure the capacity rounded up to the power of 2 is 75% of the expected numbers of values to be stored to keep load factor low and the hash table performant.
Prefer to use scalar types (int/uint/pointers) or strings as key/value pairs. Structs can be used with elementwise equality check but will not make use the cache and hardware prefetching as well. Keep the structs in a seperate buffer and use their pointers preferably.
A static / heap-allocated buffer should be used, should the key/values's lifetime extend beyond the scope the arguments are provided. This applies to strings. See example.
The following macros must be defined:
Source(s) used:
◆ fhashtable_calc_sizeof
#define fhashtable_calc_sizeof |
( |
| fhashtable_name, |
|
|
| capacity ) |
Value: (uint32_t)(offsetof(struct fhashtable_name, slots) + capacity * sizeof(((struct fhashtable_name *)0)->slots[0]))
Calculate the size of the hashtable struct. No overflow checks.
- Parameters
-
[in] | fhashtable_name | Defined hashtable NAME. |
[in] | capacity | Capacity input. |
- Returns
- The equivalent size.
◆ fhashtable_calc_sizeof_overflows
#define fhashtable_calc_sizeof_overflows |
( |
| fhashtable_name, |
|
|
| capacity ) |
Value: (capacity \
> (UINT32_MAX - offsetof(struct fhashtable_name, slots)) / sizeof(((struct fhashtable_name *)0)->slots[0]))
Check for a given capacity, if the equivalent size of the hashtable struct overflows.
- Parameters
-
[in] | fhashtable_name | Defined hashtable NAME. |
[in] | capacity | Capacity input. |
- Returns
- Whether the equivalent size overflows.
◆ fhashtable_for_each
#define fhashtable_for_each |
( |
| self, |
|
|
| index, |
|
|
| key_, |
|
|
| value_ ) |
Value: for ((index) = 0; (index) < (self)->capacity; (index)++) \
&& ((key_) = (self)->slots[(index)].key, (value_) = (self)->slots[(index)].value, true))
#define FHASHTABLE_EMPTY_SLOT_OFFSET
Offset constant used to flag empty slots.
Definition fhashtable.h:61
Iterate over the non-empty slots in the hashtable in arbitary order.
- Warning
- Modifying the hashtable under the iteration may result in errors.
- Parameters
-
[in] | self | Hashtable pointer. |
[in] | index | Temporary indexing variable. Should be uint32_t . |
[out] | key_ | Current key. Should be KEY_TYPE . |
[out] | value_ | Current value. Should be VALUE_TYPE . |
◆ HASH_FUNCTION
#define HASH_FUNCTION |
( |
| key | ) |
|
Value:
#define KEY_TYPE
The key type. This must be manually defined before including this header file.
Definition fhashtable.h:132
static uint32_t murmur3_32(const uint8_t *key_ptr, const uint32_t len, const uint32_t seed)
Get the Murmur3 (32-bit) hash of a string of bytes.
Definition murmurhash.h:54
Used to compute indicies of keys. This must be manually defined before including this header file.
Is undefined once header is included.
- Parameters
-
- Returns
- The hash of the key as
uint32_t
.
◆ KEY_IS_EQUAL
#define KEY_IS_EQUAL |
( |
| a, |
|
|
| b ) |
Value:
Used to compare two keys This must be manually defined before including this header file.
Is undefined once header is included.
- Attention
- If comparing two scalar values, set this macro to ((a) == (b)).
- If comparing two strings, set this macro to strcmp() or strncmp() appropiately.
- If comparing two structs, set this macro to a function that does element-wise comparison between the structs.
- Return values
-
true | If the two keys are equal. Equivalent to a non-zero int. |
false | If the two key are not equal. Equivalent to the int 0. |
◆ KEY_TYPE
The key type. This must be manually defined before including this header file.
Is undefined once header is included.
◆ NAME
Prefix to hashtable types and operations. This must be manually defined before including this header file.
Is undefined after header is included.
◆ VALUE_TYPE
The value type. This must be manually defined before including this header file.
Is undefined once header is included.
◆ fhashtable_clear()
static void fhashtable_clear |
( |
fhashtable_type * | self | ) |
|
|
inlinestatic |
Clear an existing hashtable and flag all slots as empty.
- Parameters
-
[in] | self | The pointer of the hashtable to clear. |
◆ fhashtable_contains_key()
static bool fhashtable_contains_key |
( |
const fhashtable_type * | self, |
|
|
const KEY_TYPE | key ) |
|
inlinestatic |
Check if hashtable contains a key.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key. |
- Returns
- A boolean indicating whether the hashtable contains the given key.
◆ fhashtable_copy()
static void fhashtable_copy |
( |
fhashtable_type *restrict | dest_ptr, |
|
|
const fhashtable_type *restrict | src_ptr ) |
|
inlinestatic |
Copy the values from a source hashtable to a destination hashtable.
- Parameters
-
[out] | dest_ptr | The destination hashtable. |
[in] | src_ptr | The source hashtable. |
◆ fhashtable_create()
static fhashtable_type * fhashtable_create |
( |
const uint32_t | min_capacity | ) |
|
|
inlinestatic |
Create an hashtable with a given capacity with malloc().
- Parameters
-
[in] | min_capacity | Maximum number of elements to be stored. |
- Returns
- A pointer to the queue.
- Return values
-
NULL |
- If malloc fails.
- If capacity is equal to 0 or larger than UINT32_MAX / 2 + 1 or the equivalent size overflows.
|
◆ fhashtable_delete()
static bool fhashtable_delete |
( |
fhashtable_type * | self, |
|
|
const KEY_TYPE | key ) |
|
inlinestatic |
Delete a key and it's corresponding value from the hashtable.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key. |
- Returns
- A boolean indicating whether the key was previously contained in the hashtable.
◆ fhashtable_destroy()
static void fhashtable_destroy |
( |
fhashtable_type * | self | ) |
|
|
inlinestatic |
Destroy an hashtable struct and free the underlying memory with free().
- Warning
- May not be called twice in a row on the same object.
- Parameters
-
[in] | self | The hashtable pointer. |
◆ fhashtable_get_value()
From a given key, get the copy of the corresponding value in the hashtable.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key to search for. |
[in] | default_value | The default value returned if the hashtable did not contain the key. |
- Returns
- The corresponding key.
- Return values
-
`default_value` | If the hashtable did not contain the key. |
◆ fhashtable_get_value_mut()
static VALUE_TYPE * fhashtable_get_value_mut |
( |
fhashtable_type * | self, |
|
|
const KEY_TYPE | key ) |
|
inlinestatic |
From a given key, get the pointer to the corresponding value in the hashtable.
- Note
- The returned pointer is not garanteed to point to the same value if the hashtable is modified.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key to search for. |
- Returns
- A pointer to the corresponding key.
- Return values
-
NULL | If the hashtable did not contain the key. |
◆ fhashtable_init()
static fhashtable_type * fhashtable_init |
( |
fhashtable_type * | self, |
|
|
const uint32_t | pow2_capacity ) |
|
inlinestatic |
Initialize a hashtable struct, given a (power-of-2) capacity.
- Parameters
-
[in] | self | Hashtable pointer |
[in] | pow2_capacity | Power of 2 capacity. |
◆ fhashtable_insert()
Insert a non-duplicate key and it's corresponding value inside the hashtable.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key. |
[in] | value | The value. |
◆ fhashtable_is_empty()
static bool fhashtable_is_empty |
( |
const fhashtable_type * | self | ) |
|
|
inlinestatic |
Return whether the hashtable is empty.
- Parameters
-
[in] | self | The hashtable pointer. |
- Returns
- Whether the hashtable is empty.
◆ fhashtable_is_full()
static bool fhashtable_is_full |
( |
const fhashtable_type * | self | ) |
|
|
inlinestatic |
Return whether the hashtable is full.
- Parameters
-
[in] | self | The hashtable pointer. |
- Returns
- Whether the hashtable is full.
◆ fhashtable_search()
Search a given key in the hashtable and get the pointer to the corresponding value.
- Note
- The returned pointer is not garanteed to point to the same value if the hashtable is modified.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key to search for. |
- Returns
- A pointer to the corresponding key.
- Return values
-
NULL | If the hashtable did not contain the key. |
◆ fhashtable_update()
Update a key's corresponding value inside the hashtable. Allows duplicates.
- Parameters
-
[in] | self | The hashtable pointer. |
[in] | key | The key. |
[in] | value | The value. |