universe@390: universe@390:

Hash map implementation. universe@390: More...

universe@390:

#include "ucx.h"
universe@390: #include "string.h"
universe@390: #include "allocator.h"
universe@390: #include <stdio.h>
universe@390:

universe@390:

Go to the source code of this file.

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: 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...

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: 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...

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: 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...

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: 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...

universe@390:

Detailed Description

universe@390:

Hash map implementation.

universe@390:

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

universe@390:

Author: Mike Becker; universe@390: Olaf Wintermann

universe@390:

Macro Definition Documentation

universe@390: universe@390:

◆ ucx_map_cstr_get

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the value

universe@390:

See also: ucx_map_get()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_cstr_put

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key
value	the value

universe@390:

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

universe@390:

See also: ucx_map_put()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_cstr_remove

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the removed value

universe@390:

See also: ucx_map_remove()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ UCX_MAP_FOREACH

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Loop statement for UCX maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

See also: ucx_map_iterator()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_int_get

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the value

universe@390:

See also: ucx_map_get()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_int_put

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key
value	the value

universe@390:

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

universe@390:

See also: ucx_map_put()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_int_remove

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the removed value

universe@390:

See also: ucx_map_remove()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_sstr_get

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the value

universe@390:

See also: ucx_map_get()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_sstr_put

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key
value	the value

universe@390:

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

universe@390:

See also: ucx_map_put()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_sstr_remove

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the removed value

universe@390:

See also: ucx_map_remove()

universe@390: universe@390:

universe@390:

Typedef Documentation

universe@390: universe@390:

◆ UcxKey

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390:

typedef struct UcxKey UcxKey

universe@390:

universe@390: universe@390:

Type for a key of a UcxMap.

universe@390:

See also: UcxKey

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ UcxMap

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390:

typedef struct UcxMap UcxMap

universe@390:

universe@390: universe@390:

Type for the UCX map.

universe@390:

See also: UcxMap

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ UcxMapElement

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390:

typedef struct UcxMapElement UcxMapElement

universe@390:

universe@390: universe@390:

Type for an element of a UcxMap.

universe@390:

See also: UcxMapElement

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ UcxMapIterator

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390:

typedef struct UcxMapIterator UcxMapIterator

universe@390:

universe@390: universe@390:

Type for an iterator over a UcxMap.

universe@390:

See also: UcxMapIterator

universe@390: universe@390:

universe@390:

Function Documentation

universe@390: universe@390:

◆ ucx_hash()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_hash	(	const char *	data,
		size_t	len
	)

universe@390:

universe@390: universe@390:

Computes a murmur hash-2.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

data	the data to hash
len	the length of the data

universe@390:

Returns: the murmur hash-2 of the data

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_key()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxKey ucx_key	(	const void *	data,
		size_t	len
	)

universe@390:

universe@390: universe@390:

Creates a UcxKey based on the given data.

universe@390:

This function implicitly computes the hash.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a UcxKey with implicitly computed hash

universe@390:

See also: ucx_hash()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_clear()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void ucx_map_clear ( UcxMap * map )

universe@390:

universe@390: universe@390:

Clears a hash map.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390:

map	the map to be cleared

universe@390:

See also: ucx_map_free_content()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_clone()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Clones the map and rehashes if necessary.

universe@390:

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.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: the cloned map

universe@390:

See also: ucx_map_copy()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_clone_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Clones the map and rehashes if necessary.

universe@390:

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.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: the cloned map

universe@390:

See also: ucx_map_copy()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_copy()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

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.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

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

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_difference()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Returns the difference of two maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a new list containing the difference

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_difference_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Returns the difference of two maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a new list containing the difference

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_free()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void ucx_map_free ( UcxMap * map )

universe@390:

universe@390: universe@390:

Frees a hash map.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390:

map	the map to be freed

universe@390:

See also: ucx_map_free_content()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_free_content()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void ucx_map_free_content	(	UcxMap *	map,
		ucx_destructor	destr
	)

universe@390:

universe@390: universe@390:

Frees the contents of a hash map.

universe@390:

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

universe@390:

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

universe@390:

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

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

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

universe@390:

See also: ucx_map_free(); universe@390: ucx_map_clear()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_get()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Retrieves a value by using a key.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the value

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_intersection()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Returns the intersection of two maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a new map containing the intersection

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_intersection_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Returns the intersection of two maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a new map containing the intersection

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_iter_next()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

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

universe@390:

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.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

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

universe@390:

See also: ucx_map_iterator()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_iterator()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxMapIterator ucx_map_iterator ( UcxMap const * map )

universe@390:

universe@390: universe@390:

Creates an iterator for a map.

universe@390:

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.

universe@390:

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.

universe@390:

Parameters

universe@390: universe@390: universe@390:

map	the map to create the iterator for

universe@390:

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

universe@390:

See also: ucx_map_iter_next()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_new()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxMap* ucx_map_new ( size_t size )

universe@390:

universe@390: universe@390:

Creates a new hash map with the specified size.

universe@390:

Parameters

universe@390: universe@390: universe@390:

size	the size of the hash map

universe@390:

Returns: a pointer to the new hash map

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_new_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxMap* ucx_map_new_a	(	UcxAllocator *	allocator,
		size_t	size
	)

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a pointer to the new hash map

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_put()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Puts a key/value-pair into the map.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key
value	the value

universe@390:

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

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_rehash()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_map_rehash ( UcxMap * map )

universe@390:

universe@390: universe@390:

Increases size of the hash map, if necessary.

universe@390:

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.

universe@390:

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.

universe@390:

You can use this function to dramatically increase access performance.

universe@390:

Parameters

universe@390: universe@390: universe@390:

map	the map to rehash

universe@390:

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

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_remove()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void* ucx_map_remove	(	UcxMap *	map,
		UcxKey	key
	)

universe@390:

universe@390: universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

map	the map
key	the key

universe@390:

Returns: the removed value

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_union()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Returns the union of two maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a new map containing the union

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_map_union_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

universe@390: universe@390:

Returns the union of two maps.

universe@390:

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

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

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

universe@390:

Returns: a new map containing the union

universe@390: universe@390:

universe@390:

universe@390: Data Structures

universe@390: Macros

universe@390: Typedefs

universe@390: 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()