Fixed-size open-adressing hashtable (robin hood hashing) More...

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "round_up_pow2_32.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	PASTE(a, b)
	Paste two tokens together.

#define	XPASTE(a, b)
	First expand tokens, then paste them together.

#define	JOIN(a, b)
	First expand tokens, then paste them together with a _ in between.

#define	IS_POW2(X)
	Macro to check if a number is a power of two.

#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	KEY_TYPE int
	The key type. This must be manually defined before including this header file.

#define	FUNCTION_DEFINITIONS
	Define the functions.

#define	TYPE_DEFINITIONS
	Define the types.

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

#define	FUNCTION_LINKAGE
	Specify function linkage e.g. static inline.

Functions
fhashtable_type *	fhashtable_init (fhashtable_type *self, const uint32_t pow2_capacity)
	Initialize a hashtable struct, given a (power-of-2) capacity.

fhashtable_type *	fhashtable_create (const uint32_t min_capacity)
	Create an hashtable with a given capacity with malloc().

void	fhashtable_destroy (fhashtable_type *self)
	Destroy an hashtable struct and free the underlying memory with free().

bool	fhashtable_is_empty (const fhashtable_type *self)
	Return whether the hashtable is empty.

bool	fhashtable_is_full (const fhashtable_type *self)
	Return whether the hashtable is full.

bool	fhashtable_contains_key (const fhashtable_type *self, const KEY_TYPE key)
	Check if hashtable contains a key.

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.

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.

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.

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.

void	fhashtable_update (fhashtable_type *self, KEY_TYPE key, VALUE_TYPE value)
	Update a key's corresponding value inside the hashtable. Allows duplicates.

bool	fhashtable_delete (fhashtable_type *self, const KEY_TYPE key)
	Delete a key and it's corresponding value from the hashtable.

void	fhashtable_clear (fhashtable_type *self)
	Clear an existing hashtable and flag all slots as empty.

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

Examples: fhashtable_example.c.

◆ HASH_FUNCTION

#define HASH_FUNCTION ( key )

Value:

(0)

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.

◆ IS_POW2

#define IS_POW2 ( X )

Value:

((X) != 0 && ((X) & ((X) - 1)) == 0)

Macro to check if a number is a power of two.

Parameters

[in] X The number at hand.

Returns: A boolean value indicating whether the number is a power of two.

◆ JOIN

#define JOIN	(		a,
			b )

Value:

XPASTE(a, XPASTE(_, b))

XPASTE

#define XPASTE(a, b)

First expand tokens, then paste them together.

Definition fstack_template.h:42

First expand tokens, then paste them together with a _ in between.

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

◆ PASTE

#define PASTE	(		a,
			b )

Value:

a##b

Paste two tokens together.

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

◆ XPASTE

#define XPASTE	(		a,
			b )

Value:

PASTE(a, b)

PASTE

#define PASTE(a, b)

Paste two tokens together.

Definition fstack_template.h:34

First expand tokens, then paste them together.

Function Documentation

◆ fhashtable_clear()

void fhashtable_clear ( fhashtable_type * self )

Clear an existing hashtable and flag all slots as empty.

Parameters

[in] self The pointer of the hashtable to clear.

◆ fhashtable_contains_key()

bool fhashtable_contains_key	(	const fhashtable_type *	self,
		const KEY_TYPE	key )

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

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.

Parameters

[out]	dest_ptr	The destination hashtable.
[in]	src_ptr	The source hashtable.

◆ fhashtable_create()

fhashtable_type * fhashtable_create ( const uint32_t min_capacity )

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

bool fhashtable_delete	(	fhashtable_type *	self,
		const KEY_TYPE	key )

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

void fhashtable_destroy ( fhashtable_type * self )

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

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.

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

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.

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

fhashtable_type * fhashtable_init	(	fhashtable_type *	self,
		const uint32_t	pow2_capacity )

Initialize a hashtable struct, given a (power-of-2) capacity.

Parameters

[in]	self	Hashtable pointer
[in]	pow2_capacity	Power of 2 capacity.

◆ fhashtable_insert()

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.

Parameters

[in]	self	The hashtable pointer.
[in]	key	The key.
[in]	value	The value.

◆ fhashtable_is_empty()

bool fhashtable_is_empty ( const fhashtable_type * self )

Return whether the hashtable is empty.

Parameters

[in] self The hashtable pointer.

Returns: Whether the hashtable is empty.

◆ fhashtable_is_full()

bool fhashtable_is_full ( const fhashtable_type * self )

Return whether the hashtable is full.

Parameters

[in] self The hashtable pointer.

Returns: Whether the hashtable is full.

◆ fhashtable_search()

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.

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

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

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

◆ IS_POW2

◆ JOIN

◆ KEY_IS_EQUAL

◆ KEY_TYPE

◆ PASTE

◆ VALUE_TYPE

◆ XPASTE

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