rhhashmap.h File Reference

A generally useful Robin Hood hash map implementation. More...

Typedefs
typedef struct rh_hashmap_t	rh_hashmap_t
typedef uintptr_t()	rh_hash_fn(intptr_t key, size_t mapsize, void *data)
	Type of a function to return the hash value for a key. More...
typedef int()	rh_key_equal_fn(intptr_t key1, intptr_t key2)
	Type of a function to compare two hash map keys for equality. More...
typedef void()	rh_resize_fn(size_t size, size_t *shrinkto, size_t *expandto, void *data)
	Type of a function called to determine the hash map's expansion and shrinkage policy. More...
typedef void *()	rh_alloc_fn(size_t size, void *data)
	Type of a function to allocate a block of memory. More...
typedef void()	rh_free_fn(void *ptr, size_t size, void *data)
	Type of a function to free a block of memory previously allocated using the rh_alloc_fn() callback. More...
typedef void()	rh_release_key_fn(intptr_t key, void *data)
	Type of a function to release a key when removed from the hash map. More...
typedef void()	rh_release_value_fn(intptr_t value, void *data)
	Type of a function to release a value when removed from the hash map. More...
typedef int()	rh_iterate_fn(intptr_t key, intptr_t value, void *data, void *iterate_data)
	Type of a function called when iterating over a hash map. More...

Functions
rh_hashmap_t *	rh_hashmap_create (size_t initsize, intptr_t invalid_value, rh_hash_fn *hash_fn, rh_key_equal_fn *equals_fn, rh_resize_fn *resize_fn, rh_alloc_fn *alloc_fn, rh_free_fn *free_fn, rh_release_key_fn *release_key_fn, rh_release_value_fn *release_value_fn, void *data)
	Create a Robin Hood hash map. More...
void	rh_hashmap_destroy (rh_hashmap_t **map)
	Destroy a hash map. More...
intptr_t	rh_hashmap_search (rh_hashmap_t *map, intptr_t key)
	Search for key in a hash map, and return its value if found. More...
intptr_t	rh_hashmap_replace (rh_hashmap_t *map, intptr_t key, intptr_t value)
	Insert, delete, or replace the value of a key in a hash map. More...
int	rh_hashmap_iterate (rh_hashmap_t *map, rh_iterate_fn *iterate_fn, void *iterate_data)
	Iterate over a hash map. More...
void	rh_resize_power_2 (size_t size, size_t *shrinkto, size_t *expandto, void *data)
	A power-of-two resize function, for use with user hash maps. More...

Detailed Description

A generally useful Robin Hood hash map implementation.

Copyright (C) 2023 Global Graphics Software Ltd. All rights reserved. This source code contains the confidential and trade secret information of Global Graphics Software Ltd. It may not be used, copied or distributed for any reason except as set forth in the applicable Global Graphics license agreement.

Typedef Documentation

rh_alloc_fn

typedef void*() rh_alloc_fn(size_t size, void *data)

Type of a function to allocate a block of memory.

Parameters

[in]	size	The size in bytes of the block of memory to allocate.
[in]	data	The data pointer provided to rh_hashmap_create().

Returns

A pointer to the allocated memory block, or NULL if the memory block cannot be allocated.

rh_free_fn

typedef void() rh_free_fn(void *ptr, size_t size, void *data)

Type of a function to free a block of memory previously allocated using the rh_alloc_fn() callback.

Parameters

[in]	ptr	The block of memory to free.
[in]	size	The size in bytes of the block of memory to free.
[in]	data	The data pointer provided to rh_hashmap_create().

rh_hash_fn

typedef uintptr_t() rh_hash_fn(intptr_t key, size_t mapsize, void *data)

Type of a function to return the hash value for a key.

Parameters

[in]	key	The key to be hashed.
[in]	mapsize	The size of the hash map. This is provided to enable universal hash function optimisations such as multiply-shift to be used. The return value should be the full hash value, not reduced to the map size.
[in]	data	The data pointer provided to rh_hashmap_create().

Returns

A hash value, not reduced to the hash map size. The top 7 bits of the hash value may be discarded; the hash function chosen should NOT put all its entropy into these bits.

Note

The performance of Robin Hood hashing (as with all hashing) is dependent on choosing a good hash function, with a uniform distribution.

rh_hashmap_t

typedef struct rh_hashmap_t rh_hashmap_t

Opaque reference to a Robin Hood hash map.

rh_iterate_fn

typedef int() rh_iterate_fn(intptr_t key, intptr_t value, void *data, void *iterate_data)

Type of a function called when iterating over a hash map.

Parameters

[in]	key	The key for an entry in the hash map.
[in]	value	The value for an entry in the hash map.
[in]	data	The data pointer provided to rh_hashmap_create().
[in]	iterate_data	The iteration-specific data pointer passed to rh_hashmap_iterate().

Returns

Non-zero if the iteration should terminate immediately. The termination value will be returned from rh_hashmap_iterate(). Zero if the iteration should continue.

rh_key_equal_fn

typedef int() rh_key_equal_fn(intptr_t key1, intptr_t key2)

Type of a function to compare two hash map keys for equality.

Parameters

[in]	key1	The first key to compare.
[in]	key2	The second key to compare.

Return values

TRUE	if the keys are equal.
FALSE	if the keys are not equal.

rh_release_key_fn

typedef void() rh_release_key_fn(intptr_t key, void *data)

Type of a function to release a key when removed from the hash map.

Parameters

[in]	key	The key removed from the map.
[in]	data	The data pointer provided to rh_hashmap_create().

This function may be used to reference count or track complex keys inserted into a hash map. If reference counting, the caller passes responsibility for the key to the hash map when inserting or replacing with rh_hashmap_replace().

rh_release_value_fn

typedef void() rh_release_value_fn(intptr_t value, void *data)

Type of a function to release a value when removed from the hash map.

Parameters

[in]	value	The value removed from the map.
[in]	data	The data pointer provided to rh_hashmap_create().

This function may be used to reference count or track complex values inserted into a hash map. If reference counting, the caller passes responsibility for the value to the hash map when inserting or replacing with rh_hashmap_replace(). Ownership of the return value of rh_hashmap_replace() is transferred from the hash map to the caller.

rh_resize_fn

typedef void() rh_resize_fn(size_t size, size_t *shrinkto, size_t *expandto, void *data)

Type of a function called to determine the hash map's expansion and shrinkage policy.

Parameters

[in]	size	The current size of the hash map.
[out]	shrinkto	A location to store the size to reduce the hash map to if shrunk. If this is greater than or equal to the current size, the hash map will never be shrunk.
[out]	expandto	A location to store the size to increase the hash map to if expanded. If this is less than or equal to the current size, the hash map will never be expanded.
[in]	data	The data pointer provided to rh_hashmap_create().

This function is called at hash map creation, and whenever the hash map is shrunk or expanded. It sets the new target sizes for shrinking and expanding the hash map. This can be used to enforce a minimum size or maximum size for the hash map, or to force the number of entries in the hash map to particular boundaries (such as powers of two, or cache line size multiples). The hash map implementation quietly enforces a minimum shrink size.

The hash map will be expanded when the load factor at the current size is too high. The hash map will not be shrunk if the load factor at the new size is too high. There is hysteresis in the load factors using for shrinking and expanding.

If the expandto value is larger than the current size, the hash map implementation always guarantees that it will request expansion (by calling the rh_alloc_fn() callback) before the hash map is completely full. In this case, at least one insertion will succeed, regardless whether the expansion allocation fails.

Function Documentation

rh_hashmap_create()

rh_hashmap_t* rh_hashmap_create	(	size_t	initsize,
		intptr_t	invalid_value,
		rh_hash_fn *	hash_fn,
		rh_key_equal_fn *	equals_fn,
		rh_resize_fn *	resize_fn,
		rh_alloc_fn *	alloc_fn,
		rh_free_fn *	free_fn,
		rh_release_key_fn *	release_key_fn,
		rh_release_value_fn *	release_value_fn,
		void *	data
	)

Create a Robin Hood hash map.

Parameters

initsize	The initial size of the hash map. The hash map is only shrunk on deletions, so the initial size can be set to a suitable size to allow loading an expected number of entries without re-allocation. The hash map implementation quietly enforces a minimum size.
invalid_value	An invalid value for the hash map entries. Entries cannot be inserted with this value. Returning this value from rh_hashmap_find() signifies a failure to find the hash key in the map.
hash_fn	A function to return the hash of a key.
equals_fn	An optional function to compare two keys for equality. If this function pointer is NULL, then equality is determined by key identity.
resize_fn	An optional function to set the next smaller and larger sizes for the hash map. This function can be used to enforce minimum or maximum sizes for the hash map, or enforce a policy on the number of entries in a hash map (e.g., powers of two or multiples of cache line sizes). If this function pointer is NULL, the hash map is not resizable.
alloc_fn	A function to allocate memory when creating or expanding the hash map. The hash map implementation will attempt to expand the map when it reaches a high load factor, but before it is full. If the caller is in a critical section and cannot take a memory allocation lock when an insertion happens, it can return NULL for the allocation. The hash value will be inserted into the map. The caller can then arrange to pre-allocate the requested memory outside of the critical section, ready for the next insertion.
free_fn	A function to free memory when shrinking or destroying the hash map.
release_key_fn	An optional function called when a key is removed from a hash map, either when replacing an existing key or when destroying the hash map. If present, this function may be used to reference count complex keys.
release_value_fn	An optional function called when the hash map is destroyed with values still present. If present, this function may be used to reference count complex values.
data	An opaque pointer supplied by the user of the hash map, passed through to the hashing and memory allocation functions.

Returns

A pointer to the new hash map, or NULL if the map could not be created.

The hash_fn(), alloc_fn(), and free_fn() callback function pointers are required. All other function pointers are optional. If the user is storing complex keys or values in the hash map, the release_key_fn() and release_value_fn() can be supplied to reference count the keys or values. In this case, ownership of the key and value supplied to rh_hashmap_replace() are passed to the hash map. Ownership of the value returned by rh_hashmap_replace() is passed back to the caller. The release_key_fn() callback will be called while replacing an existing value using rh_hashmap_replace(), on either the new or the old key. It will also be called during rh_hashmap_destroy() when releasing non-empty entries in the hash map. The release_value_fn() callback will be called only during rh_hashmap_destroy() when releasing non-empty entries in the hash map.

If storing complex keys, it is likely that the user will want to supply the equals_fn() pointer. If not supplied, the default comparison is key identity, which may not be correct for complex key types.

If the resize_fn() pointer is not supplied, the hash map will not be resizable from its initial size.

rh_hashmap_destroy()

void rh_hashmap_destroy

(

rh_hashmap_t **

map

)

Destroy a hash map.

Parameters

[in,out]

map

A location where the hash map to destroy will be found. This function is safe to use when *map is NULL. On exit, *map will be set to NULL.

All operations on the hash map will fail during destruction.

If the release_key_fn() or release_value_fn() were supplied to rh_hashmap_create(), they will be called for each entry destroyed.

rh_hashmap_iterate()

int rh_hashmap_iterate	(	rh_hashmap_t *	map,
		rh_iterate_fn *	iterate_fn,
		void *	iterate_data
	)

Iterate over a hash map.

Parameters

[in]	map	The hash map to iterate.
[in]	iterate_fn	A function to callback for each hash key and value in the map.
[in]	iterate_data	An opaque pointer that will be passed through to iterate_fn().

Returns

Zero if the iteration was not stopped early. If stopped early, the return value of iterate_fn().

Note

Insertions and deletions may be made during an iteration, but may cause key-value entries to be duplicated or omitted from the iteration.

rh_hashmap_replace()

intptr_t rh_hashmap_replace	(	rh_hashmap_t *	map,
		intptr_t	key,
		intptr_t	value
	)

Insert, delete, or replace the value of a key in a hash map.

Parameters

[in]	map	The hash map to replace key in.
[in]	key	The key to replace in map.
[in]	value	The value to associate with key in map. If this value is the invalid value originally provided to rh_hashmap_create(), then the key is being deleted from the hash map.

Returns

The previous value of key in map. If there was no previous value associated with key, the invalid value initially passed to rh_hashmap_create(). If an attempt is made to insert a new value, but the hash map is completely full, then the value that was attempted to be inserted will be returned. The implementation will try to expand the hash map before it is completely full, so this will only happen if the allocations for the hash map expansion failed, and the caller took no action to allow them to proceed.

Ownership of the key and value are transferred to the hash map. Ownership of the return value is transferred from the hash map to the caller. If the hash map is entirely full and cannot be expanded, this is equivalent to not transferring ownership of the value, and release_key_fn() will be called on the new key, if a callback was supplied to rh_hashmap_create().

rh_hashmap_search()

intptr_t rh_hashmap_search	(	rh_hashmap_t *	map,
		intptr_t	key
	)

Search for key in a hash map, and return its value if found.

Parameters

[in]	map	The hash map to find key in.
[in]	key	The key to find in map.

Returns

If a key was found, the value associated with it. If the key was not found, the invalid value passed to rh_hashmap_create().

The return value is still owned by the hash map implementation.

rh_resize_power_2()

void rh_resize_power_2	(	size_t	size,
		size_t *	shrinkto,
		size_t *	expandto,
		void *	data
	)

A power-of-two resize function, for use with user hash maps.

This function can be used as the rh_resize_fn() callback when creating hash maps that should store a power of two entries. The implementation will enforce a minimum size of the hash map. There is no maximum size for the hash map, it is limited only by memory.

Parameters

[in]	size	The current size of the hash map.
[out]	shrinkto	A location to store the size to reduce the hash map to if shrunk. If this is greater than or equal to the current size, the hash map will never be shrunk.
[out]	expandto	A location to store the size to increase the hash map to if expanded. If this is less than or equal to the current size, the hash map will never be expanded.
[in]	data	The data pointer provided to rh_hashmap_create().

This function is called at hash map creation, and whenever the hash map is shrunk or expanded. It sets the new target sizes for shrinking and expanding the hash map. This can be used to enforce a minimum size or maximum size for the hash map, or to force the number of entries in the hash map to particular boundaries (such as powers of two, or cache line size multiples). The hash map implementation quietly enforces a minimum shrink size.

The hash map will be expanded when the load factor at the current size is too high. The hash map will not be shrunk if the load factor at the new size is too high. There is hysteresis in the load factors using for shrinking and expanding.

If the expandto value is larger than the current size, the hash map implementation always guarantees that it will request expansion (by calling the rh_alloc_fn() callback) before the hash map is completely full. In this case, at least one insertion will succeed, regardless whether the expansion allocation fails.