Hash map implementation. More...

#include "ucx.h"
#include "string.h"
#include "allocator.h"
#include <stdio.h>

Data Structures
struct	UcxMap
	Structure for the UCX map. More...

struct	UcxKey
	Structure to publicly denote a key of a UcxMap. More...

struct	UcxMapKey
	Internal structure for a key of a UcxMap. More...

struct	UcxMapElement
	Structure for an element of a UcxMap. More...

struct	UcxMapIterator
	Structure for an iterator over a UcxMap. More...

Macros
#define	UCX_MAP_FOREACH(key, value, iter) for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)
	Loop statement for UCX maps. More...

#define	ucx_map_sstr_put(map, key, value) ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)
	Shorthand for putting data with a sstr_t key into the map. More...

#define	ucx_map_cstr_put(map, key, value) ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value)
	Shorthand for putting data with a C string key into the map. More...

#define	ucx_map_int_put(map, key, value) ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value)
	Shorthand for putting data with an integer key into the map. More...

#define	ucx_map_sstr_get(map, key) ucx_map_get(map, ucx_key(key.ptr, key.length))
	Shorthand for getting data from the map with a sstr_t key. More...

#define	ucx_map_cstr_get(map, key) ucx_map_get(map, ucx_key(key, strlen(key)))
	Shorthand for getting data from the map with a C string key. More...

#define	ucx_map_int_get(map, key) ucx_map_get(map, ucx_key(&key, sizeof(int)))
	Shorthand for getting data from the map with an integer key. More...

#define	ucx_map_sstr_remove(map, key) ucx_map_remove(map, ucx_key(key.ptr, key.length))
	Shorthand for removing data from the map with a sstr_t key. More...

#define	ucx_map_cstr_remove(map, key) ucx_map_remove(map, ucx_key(key, strlen(key)))
	Shorthand for removing data from the map with a C string key. More...

#define	ucx_map_int_remove(map, key) ucx_map_remove(map, ucx_key(&key, sizeof(key)))
	Shorthand for removing data from the map with an integer key. More...

Typedefs
typedef struct UcxMap	UcxMap
	Type for the UCX map. More...

typedef struct UcxKey	UcxKey
	Type for a key of a UcxMap. More...

typedef struct UcxMapElement	UcxMapElement
	Type for an element of a UcxMap. More...

typedef struct UcxMapIterator	UcxMapIterator
	Type for an iterator over a UcxMap. More...

Functions
UcxMap *	ucx_map_new (size_t size)
	Creates a new hash map with the specified size. More...

UcxMap *	ucx_map_new_a (UcxAllocator *allocator, size_t size)
	Creates a new hash map with the specified size using a UcxAllocator. More...

void	ucx_map_free (UcxMap *map)
	Frees a hash map. More...

void	ucx_map_free_content (UcxMap *map, ucx_destructor destr)
	Frees the contents of a hash map. More...

void	ucx_map_clear (UcxMap *map)
	Clears a hash map. More...

int	ucx_map_copy (UcxMap const from, UcxMap to, copy_func fnc, void *data)
	Copies contents from a map to another map using a copy function. More...

UcxMap *	ucx_map_clone (UcxMap const map, copy_func fnc, void data)
	Clones the map and rehashes if necessary. More...

UcxMap *	ucx_map_clone_a (UcxAllocator allocator, UcxMap const map, copy_func fnc, void *data)
	Clones the map and rehashes if necessary. More...

int	ucx_map_rehash (UcxMap *map)
	Increases size of the hash map, if necessary. More...

int	ucx_map_put (UcxMap map, UcxKey key, void value)
	Puts a key/value-pair into the map. More...

void *	ucx_map_get (UcxMap const *map, UcxKey key)
	Retrieves a value by using a key. More...

void *	ucx_map_remove (UcxMap *map, UcxKey key)
	Removes a key/value-pair from the map by using the key. More...

UcxKey	ucx_key (const void *data, size_t len)
	Creates a UcxKey based on the given data. More...

int	ucx_hash (const char *data, size_t len)
	Computes a murmur hash-2. More...

UcxMapIterator	ucx_map_iterator (UcxMap const *map)
	Creates an iterator for a map. More...

int	ucx_map_iter_next (UcxMapIterator iterator, UcxKey key, void **value)
	Proceeds to the next element of the map (if any). More...

UcxMap *	ucx_map_union (const UcxMap first, const UcxMap second, copy_func cpfnc, void *cpdata)
	Returns the union of two maps. More...

UcxMap *	ucx_map_union_a (UcxAllocator allocator, const UcxMap first, const UcxMap second, copy_func cpfnc, void cpdata)
	Returns the union of two maps. More...

UcxMap *	ucx_map_intersection (const UcxMap first, const UcxMap second, copy_func cpfnc, void *cpdata)
	Returns the intersection of two maps. More...

UcxMap *	ucx_map_intersection_a (UcxAllocator allocator, const UcxMap first, const UcxMap second, copy_func cpfnc, void cpdata)
	Returns the intersection of two maps. More...

UcxMap *	ucx_map_difference (const UcxMap first, const UcxMap second, copy_func cpfnc, void *cpdata)
	Returns the difference of two maps. More...

UcxMap *	ucx_map_difference_a (UcxAllocator allocator, const UcxMap first, const UcxMap second, copy_func cpfnc, void cpdata)
	Returns the difference of two maps. More...

Detailed Description

Hash map implementation.

This implementation uses murmur hash 2 and separate chaining with linked lists.

Author: Mike Becker; Olaf Wintermann

Macro Definition Documentation

◆ ucx_map_cstr_get

#define ucx_map_cstr_get	(	map,
		key
	)	ucx_map_get(map, ucx_key(key, strlen(key)))

Shorthand for getting data from the map with a C string key.

Parameters

map	the map
key	the key

Returns: the value

See also: ucx_map_get()

◆ ucx_map_cstr_put

#define ucx_map_cstr_put	(	map,
		key,
		value
	)	ucx_map_put(map, ucx_key(key, strlen(key)), (void*)value)

Shorthand for putting data with a C string key into the map.

Parameters

map	the map
key	the key
value	the value

Returns: 0 on success, non-zero value on failure

See also: ucx_map_put()

◆ ucx_map_cstr_remove

#define ucx_map_cstr_remove	(	map,
		key
	)	ucx_map_remove(map, ucx_key(key, strlen(key)))

Shorthand for removing data from the map with a C string key.

Parameters

map	the map
key	the key

Returns: the removed value

See also: ucx_map_remove()

◆ UCX_MAP_FOREACH

#define UCX_MAP_FOREACH	(	key,
		value,
		iter
	)	for(UcxKey key;ucx_map_iter_next(&iter,&key, (void**)&value);)

Loop statement for UCX maps.

The key variable is implicitly defined, but the value variable must be already declared as type information cannot be inferred.

Parameters

key	the variable name for the key
value	the variable name for the value
iter	a UcxMapIterator

See also: ucx_map_iterator()

◆ ucx_map_int_get

#define ucx_map_int_get	(	map,
		key
	)	ucx_map_get(map, ucx_key(&key, sizeof(int)))

Shorthand for getting data from the map with an integer key.

Parameters

map	the map
key	the key

Returns: the value

See also: ucx_map_get()

◆ ucx_map_int_put

#define ucx_map_int_put	(	map,
		key,
		value
	)	ucx_map_put(map, ucx_key(&key, sizeof(key)), (void*)value)

Shorthand for putting data with an integer key into the map.

Parameters

map	the map
key	the key
value	the value

Returns: 0 on success, non-zero value on failure

See also: ucx_map_put()

◆ ucx_map_int_remove

#define ucx_map_int_remove	(	map,
		key
	)	ucx_map_remove(map, ucx_key(&key, sizeof(key)))

Shorthand for removing data from the map with an integer key.

Parameters

map	the map
key	the key

Returns: the removed value

See also: ucx_map_remove()

◆ ucx_map_sstr_get

#define ucx_map_sstr_get	(	map,
		key
	)	ucx_map_get(map, ucx_key(key.ptr, key.length))

Shorthand for getting data from the map with a sstr_t key.

Parameters

map	the map
key	the key

Returns: the value

See also: ucx_map_get()

◆ ucx_map_sstr_put

#define ucx_map_sstr_put	(	map,
		key,
		value
	)	ucx_map_put(map, ucx_key(key.ptr, key.length), (void*)value)

Shorthand for putting data with a sstr_t key into the map.

Parameters

map	the map
key	the key
value	the value

Returns: 0 on success, non-zero value on failure

See also: ucx_map_put()

◆ ucx_map_sstr_remove

#define ucx_map_sstr_remove	(	map,
		key
	)	ucx_map_remove(map, ucx_key(key.ptr, key.length))

Shorthand for removing data from the map with a sstr_t key.

Parameters

map	the map
key	the key

Returns: the removed value

See also: ucx_map_remove()

Typedef Documentation

◆ UcxKey

typedef struct UcxKey UcxKey

Type for a key of a UcxMap.

See also: UcxKey

◆ UcxMap

typedef struct UcxMap UcxMap

Type for the UCX map.

See also: UcxMap

◆ UcxMapElement

typedef struct UcxMapElement UcxMapElement

Type for an element of a UcxMap.

See also: UcxMapElement

◆ UcxMapIterator

typedef struct UcxMapIterator UcxMapIterator

Type for an iterator over a UcxMap.

See also: UcxMapIterator

Function Documentation

◆ ucx_hash()

int ucx_hash	(	const char *	data,
		size_t	len
	)

Computes a murmur hash-2.

Parameters

data	the data to hash
len	the length of the data

Returns: the murmur hash-2 of the data

◆ ucx_key()

UcxKey ucx_key	(	const void *	data,
		size_t	len
	)

Creates a UcxKey based on the given data.

This function implicitly computes the hash.

Parameters

data	the data for the key
len	the length of the data

Returns: a UcxKey with implicitly computed hash

See also: ucx_hash()

◆ ucx_map_clear()

void ucx_map_clear ( UcxMap * map )

Clears a hash map.

Note: the contents are not freed, use ucx_map_free_content() before calling this function to achieve that.

Parameters

map	the map to be cleared

See also: ucx_map_free_content()

◆ ucx_map_clone()

UcxMap* ucx_map_clone	(	UcxMap const *	map,
		copy_func	fnc,
		void *	data
	)

Clones the map and rehashes if necessary.

Note: In contrast to ucx_map_rehash() the load factor is irrelevant. This function always ensures a new UcxMap.size of at least 2.5*UcxMap.count.

Parameters

map	the map to clone
fnc	the copy function to use or `NULL` if the new and the old map shall share the data pointers
data	additional data for the copy function

Returns: the cloned map

See also: ucx_map_copy()

◆ ucx_map_clone_a()

UcxMap* ucx_map_clone_a	(	UcxAllocator *	allocator,
		UcxMap const *	map,
		copy_func	fnc,
		void *	data
	)

Clones the map and rehashes if necessary.

Note: In contrast to ucx_map_rehash() the load factor is irrelevant. This function always ensures a new UcxMap.size of at least 2.5*UcxMap.count.

Parameters

allocator	the allocator to use for the cloned map
map	the map to clone
fnc	the copy function to use or `NULL` if the new and the old map shall share the data pointers
data	additional data for the copy function

Returns: the cloned map

See also: ucx_map_copy()

◆ ucx_map_copy()

int ucx_map_copy	(	UcxMap const *	from,
		UcxMap *	to,
		copy_func	fnc,
		void *	data
	)

Copies contents from a map to another map using a copy function.

Note: The destination map does not need to be empty. However, if it contains data with keys that are also present in the source map, the contents are overwritten.

Parameters

from	the source map
to	the destination map
fnc	the copy function or `NULL` if the pointer address shall be copied
data	additional data for the copy function

Returns: 0 on success or a non-zero value on memory allocation errors

◆ ucx_map_difference()

UcxMap* ucx_map_difference	(	const UcxMap *	first,
		const UcxMap *	second,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the difference of two maps.

The difference contains a copy of all elements of the first map for which the corresponding keys cannot be found in the second map.

Parameters

first	the first source map
second	the second source map
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the difference

◆ ucx_map_difference_a()

UcxMap* ucx_map_difference_a	(	UcxAllocator *	allocator,
		const UcxMap *	first,
		const UcxMap *	second,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the difference of two maps.

The difference contains a copy of all elements of the first map for which the corresponding keys cannot be found in the second map.

Parameters

allocator	the allocator that shall be used by the new map
first	the first source map
second	the second source map
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the difference

◆ ucx_map_free()

void ucx_map_free ( UcxMap * map )

Frees a hash map.

Note: the contents are not freed, use ucx_map_free_content() before calling this function to achieve that.

Parameters

map	the map to be freed

See also: ucx_map_free_content()

◆ ucx_map_free_content()

void ucx_map_free_content	(	UcxMap *	map,
		ucx_destructor	destr
	)

Frees the contents of a hash map.

This is a convenience function that iterates over the map and passes all values to the specified destructor function.

If no destructor is specified (NULL), the free() function of the map's own allocator is used.

You must ensure, that it is valid to pass each value in the map to the same destructor function.

You should free or clear the map afterwards, as the contents will be invalid.

Parameters

map	for which the contents shall be freed
destr	optional pointer to a destructor function

See also: ucx_map_free(); ucx_map_clear()

◆ ucx_map_get()

void* ucx_map_get	(	UcxMap const *	map,
		UcxKey	key
	)

Retrieves a value by using a key.

Parameters

map	the map
key	the key

Returns: the value

◆ ucx_map_intersection()

UcxMap* ucx_map_intersection	(	const UcxMap *	first,
		const UcxMap *	second,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the intersection of two maps.

The intersection is defined as a copy of the first map with every element removed that has no valid key in the second map.

Parameters

first	the first source map
second	the second source map
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new map containing the intersection

◆ ucx_map_intersection_a()

UcxMap* ucx_map_intersection_a	(	UcxAllocator *	allocator,
		const UcxMap *	first,
		const UcxMap *	second,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the intersection of two maps.

The intersection is defined as a copy of the first map with every element removed that has no valid key in the second map.

Parameters

allocator	the allocator that shall be used by the new map
first	the first source map
second	the second source map
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new map containing the intersection

◆ ucx_map_iter_next()

int ucx_map_iter_next	(	UcxMapIterator *	iterator,
		UcxKey *	key,
		void **	value
	)

Proceeds to the next element of the map (if any).

Subsequent calls on the same iterator proceed to the next element and store the key/value-pair into the memory specified as arguments of this function.

If no further elements are found, this function returns zero and leaves the last found key/value-pair in memory.

Parameters

iterator	the iterator to use
key	a pointer to the memory where to store the key
value	a pointer to the memory where to store the value

Returns: 1, if another element was found, 0 if all elements has been processed

See also: ucx_map_iterator()

◆ ucx_map_iterator()

UcxMapIterator ucx_map_iterator ( UcxMap const * map )

Creates an iterator for a map.

Note: A UcxMapIterator iterates over all elements in all element lists successively. Therefore the order highly depends on the key hashes and may vary under different map sizes. So generally you may NOT rely on the iteration order.

Note: The iterator is NOT initialized. You need to call ucx_map_iter_next() at least once before accessing any information. However, it is not recommended to access the fields of a UcxMapIterator directly.

Parameters

map	the map to create the iterator for

Returns: an iterator initialized on the first element of the first element list

See also: ucx_map_iter_next()

◆ ucx_map_new()

UcxMap* ucx_map_new ( size_t size )

Creates a new hash map with the specified size.

Parameters

size	the size of the hash map

Returns: a pointer to the new hash map

◆ ucx_map_new_a()

UcxMap* ucx_map_new_a	(	UcxAllocator *	allocator,
		size_t	size
	)

Creates a new hash map with the specified size using a UcxAllocator.

Parameters

allocator	the allocator to use
size	the size of the hash map

Returns: a pointer to the new hash map

◆ ucx_map_put()

int ucx_map_put	(	UcxMap *	map,
		UcxKey	key,
		void *	value
	)

Puts a key/value-pair into the map.

Parameters

map	the map
key	the key
value	the value

Returns: 0 on success, non-zero value on failure

◆ ucx_map_rehash()

int ucx_map_rehash ( UcxMap * map )

Increases size of the hash map, if necessary.

The load value is 0.75*UcxMap.size. If the element count exceeds the load value, the map needs to be rehashed. Otherwise no action is performed and this function simply returns 0.

The rehashing process ensures, that the UcxMap.size is at least 2.5*UcxMap.count. So there is enough room for additional elements without the need of another soon rehashing.

You can use this function to dramatically increase access performance.

Parameters

map	the map to rehash

Returns: 1, if a memory allocation error occurred, 0 otherwise

◆ ucx_map_remove()

void* ucx_map_remove	(	UcxMap *	map,
		UcxKey	key
	)

Removes a key/value-pair from the map by using the key.

Parameters

map	the map
key	the key

Returns: the removed value

◆ ucx_map_union()

UcxMap* ucx_map_union	(	const UcxMap *	first,
		const UcxMap *	second,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the union of two maps.

The union is a fresh map which is filled by two successive calls of ucx_map_copy() on the two input maps.

Parameters

first	the first source map
second	the second source map
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new map containing the union

◆ ucx_map_union_a()

UcxMap* ucx_map_union_a	(	UcxAllocator *	allocator,
		const UcxMap *	first,
		const UcxMap *	second,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the union of two maps.

The union is a fresh map which is filled by two successive calls of ucx_map_copy() on the two input maps.

Parameters

allocator	the allocator that shall be used by the new map
first	the first source map
second	the second source map
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new map containing the union

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ ucx_map_cstr_get

◆ ucx_map_cstr_put

◆ ucx_map_cstr_remove

◆ UCX_MAP_FOREACH

◆ ucx_map_int_get

◆ ucx_map_int_put

◆ ucx_map_int_remove

◆ ucx_map_sstr_get

◆ ucx_map_sstr_put

◆ ucx_map_sstr_remove

Typedef Documentation

◆ UcxKey

◆ UcxMap

◆ UcxMapElement

◆ UcxMapIterator

Function Documentation

◆ ucx_hash()

◆ ucx_key()

◆ ucx_map_clear()

◆ ucx_map_clone()

◆ ucx_map_clone_a()

◆ ucx_map_copy()

◆ ucx_map_difference()

◆ ucx_map_difference_a()

◆ ucx_map_free()

◆ ucx_map_free_content()

◆ ucx_map_get()

◆ ucx_map_intersection()

◆ ucx_map_intersection_a()

◆ ucx_map_iter_next()

◆ ucx_map_iterator()

◆ ucx_map_new()

◆ ucx_map_new_a()

◆ ucx_map_put()

◆ ucx_map_rehash()

◆ ucx_map_remove()

◆ ucx_map_union()

◆ ucx_map_union_a()