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>

Classes
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...

Macros
#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.

Functions
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.

Detailed Description

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:

NAME
KEY_TYPE
VALUE_TYPE
KEY_IS_EQUAL(a,b)
HASH_FUNCTION(key)

Source(s) used:

Macro Definition Documentation

◆ 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)++)              \
        if ((self)->slots[(index)].offset != FHASHTABLE_EMPTY_SLOT_OFFSET \
            && ((key_) = (self)->slots[(index)].key, (value_) = (self)->slots[(index)].value, true))

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:

(murmur3_32((uint8_t *)&(key), sizeof(KEY_TYPE), 0))

KEY_TYPE

#define KEY_TYPE

The key type. This must be manually defined before including this header file.

Definition fhashtable.h:132

murmur3_32

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

key The key.

Returns: The hash of the key as uint32_t.

◆ KEY_IS_EQUAL

#define KEY_IS_EQUAL	(		a,
			b )

Value:

((a) == (b))

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

#define KEY_TYPE int

The key type. This must be manually defined before including this header file.

Is undefined once header is included.

◆ NAME

#define NAME fhashtable

Prefix to hashtable types and operations. This must be manually defined before including this header file.

Is undefined after header is included.

◆ VALUE_TYPE

#define VALUE_TYPE int

The value type. This must be manually defined before including this header file.

Is undefined once header is included.

Function Documentation

◆ 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()

static VALUE_TYPE fhashtable_get_value	(	const fhashtable_type *	self,
		const KEY_TYPE	key,
		VALUE_TYPE	default_value )

inlinestatic

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()

static void fhashtable_insert	(	fhashtable_type *	self,
		KEY_TYPE	key,
		VALUE_TYPE	value )

inlinestatic

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()

static VALUE_TYPE * fhashtable_search	(	fhashtable_type *	self,
		const KEY_TYPE	key )

inlinestatic

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()

static void fhashtable_update	(	fhashtable_type *	self,
		KEY_TYPE	key,
		VALUE_TYPE	value )

inlinestatic

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.

Classes

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ fhashtable_calc_sizeof

◆ fhashtable_calc_sizeof_overflows

◆ fhashtable_for_each

◆ HASH_FUNCTION

◆ KEY_IS_EQUAL

◆ KEY_TYPE

◆ NAME

◆ VALUE_TYPE

Function Documentation

◆ fhashtable_clear()

◆ fhashtable_contains_key()

◆ fhashtable_copy()

◆ fhashtable_create()

◆ fhashtable_delete()

◆ fhashtable_destroy()

◆ fhashtable_get_value()

◆ fhashtable_get_value_mut()

◆ fhashtable_init()

◆ fhashtable_insert()

◆ fhashtable_is_empty()

◆ fhashtable_is_full()

◆ fhashtable_search()

◆ fhashtable_update()