map.h File Reference

Interface for map implementations. More...

#include "common.h"
#include "collection.h"
#include "string.h"
#include "hash_key.h"

Go to the source code of this file.

Data Structures
struct	cx_map_s
	Structure for the UCX map. More...
struct	cx_map_entry_s
	A map entry. More...
struct	cx_map_iterator_s
	Internal iterator struct - use CxMapIterator. More...
struct	cx_map_class_s
	The class definition for arbitrary maps. More...

Macros
#define	cxMapPut(map, key, value)
	Puts a key/value-pair into the map.
#define	cxMapEmplace(map, key)
	Allocates memory for a value in the map associated with the specified key.
#define	cxMapGet(map, key)
	Retrieves a value by using a key.
#define	cxMapContains(map, key)
	Checks if a map contains a specific key.
#define	cxMapRemove(map, key)
	Removes a key/value-pair from the map by using the key.
#define	cxMapRemoveAndGet(map, key, targetbuf)
	Removes a key/value-pair from the map by using the key.

Typedefs
typedef struct cx_map_s	CxMap
	Type for the UCX map.
typedef struct cx_map_entry_s	CxMapEntry
	Type for a map entry.
typedef struct cx_map_iterator_s	CxMapIterator
	Type for a map iterator.
typedef struct cx_map_class_s	cx_map_class
	Type for map class definitions.

Enumerations
enum	cx_map_iterator_type { CX_MAP_ITERATOR_PAIRS , CX_MAP_ITERATOR_KEYS , CX_MAP_ITERATOR_VALUES }
	The type of iterator for a map. More...

Functions
void	cxMapFree (CxMap *map)
	Deallocates the memory of the specified map.
void	cxMapClear (CxMap *map)
	Clears a map by removing all elements.
size_t	cxMapSize (const CxMap *map)
	Returns the number of elements in this map.
CxMapIterator	cxMapIteratorValues (const CxMap *map)
	Creates a value iterator for a map.
CxMapIterator	cxMapIteratorKeys (const CxMap *map)
	Creates a key iterator for a map.
CxMapIterator	cxMapIterator (const CxMap *map)
	Creates an iterator for a map.
int	cx_map_put (CxMap *map, CxHashKey key, void *value)
	Puts a key/value-pair into the map.
void *	cx_map_emplace (CxMap *map, CxHashKey key)
	Allocates memory for a value in the map associated with the specified key.
void *	cx_map_get (const CxMap *map, CxHashKey key)
	Retrieves a value by using a key.
int	cx_map_remove (CxMap *map, CxHashKey key, void *targetbuf)
	Removes a key/value-pair from the map by using the key.
int	cxMapClone (CxMap *dst, const CxMap *src, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data)
	Performs a deep clone of one map into another.
int	cxMapDifference (CxMap *dst, const CxMap *minuend, const CxMap *subtrahend, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data)
	Clones entries of a map if their key is not present in another map.
int	cxMapListDifference (CxMap *dst, const CxMap *src, const CxList *keys, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data)
	Clones entries of a map if their key is not present in a list.
int	cxMapIntersection (CxMap *dst, const CxMap *src, const CxMap *other, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data)
	Clones entries of a map only if their key is present in another map.
int	cxMapListIntersection (CxMap *dst, const CxMap *src, const CxList *keys, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data)
	Clones entries of a map only if their key is present in a list.
int	cxMapUnion (CxMap *dst, const CxMap *src, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data)
	Clones entries into a map if their key does not exist yet.
int	cxMapCloneSimple (CxMap *dst, const CxMap *src)
	Performs a shallow clone of one map into another.
int	cxMapDifferenceSimple (CxMap *dst, const CxMap *minuend, const CxMap *subtrahend)
	Clones entries of a map if their key is not present in another map.
int	cxMapListDifferenceSimple (CxMap *dst, const CxMap *src, const CxList *keys)
	Clones entries of a map if their key is not present in a list.
int	cxMapIntersectionSimple (CxMap *dst, const CxMap *src, const CxMap *other)
	Clones entries of a map only if their key is present in another map.
int	cxMapListIntersectionSimple (CxMap *dst, const CxMap *src, const CxList *keys)
	Clones entries of a map only if their key is present in a list.
int	cxMapUnionSimple (CxMap *dst, const CxMap *src)
	Clones entries into a map if their key does not exist yet.

Variables
CxMap *const	cxEmptyMap
	A shared instance of an empty map.

Detailed Description

Interface for map implementations.

Author

Mike Becker

Olaf Wintermann

Copyright

2-Clause BSD License

Macro Definition Documentation

cxMapContains

#define cxMapContains	(		map,
			key )

Value:

(cxMapGet(map, key) != NULL)

Checks if a map contains a specific key.

Parameters

map	(CxMap*) the map
key	(any supported key type) the key

Return values

true	if the key exists in the map
false	if the key does not exist in the map

See also

CX_HASH_KEY()

cxMapEmplace

#define cxMapEmplace	(		map,
			key )

Value:

cx_map_emplace(map, CX_HASH_KEY(key))

Allocates memory for a value in the map associated with the specified key.

A possible existing value will be overwritten. If destructor functions are specified, they are called for the overwritten element.

If the map is storing pointers, this function returns a void** pointer, meaning a pointer to that pointer.

The key is always copied.

Parameters

map	(CxMap*) the map
key	(any supported key type) the key

Returns

the pointer to the allocated memory or NULL if allocation fails

Return values

zero	success
non-zero	value on memory allocation failure

See also

CX_HASH_KEY()

cxMapGet

#define cxMapGet	(		map,
			key )

Value:

cx_map_get(map, CX_HASH_KEY(key))

Retrieves a value by using a key.

If this map is storing pointers, the stored pointer is returned. Otherwise, a pointer to the element within the map's memory is returned (which is valid as long as the element stays in the map).

Parameters

map	(CxMap*) the map
key	(any supported key type) the key

Returns

(void*) the value or NULL when no value with that key exists

See also

CX_HASH_KEY()

cxMapPut

#define cxMapPut	(		map,
			key,
			value )

Value:

cx_map_put(map, CX_HASH_KEY(key), value)

Puts a key/value-pair into the map.

A possible existing value will be overwritten. If destructor functions are specified, they are called for the overwritten element.

If this map is storing pointers, the value pointer is written to the map. Otherwise, the memory is copied from value with memcpy().

The key is always copied.

Parameters

map	(CxMap*) the map
key	(any supported key type) the key
value	(void*) the value

Return values

zero	success
non-zero	value on memory allocation failure

See also

CX_HASH_KEY()

cxMapRemove

#define cxMapRemove	(		map,
			key )

Value:

cx_map_remove(map, CX_HASH_KEY(key), NULL)

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

Always invokes the destructor functions, if any, on the removed element.

Parameters

map	(CxMap*) the map
key	(any supported key type) the key

Return values

zero	success
non-zero	the key was not found

See also

cxMapRemoveAndGet()

CX_HASH_KEY()

cxMapRemoveAndGet

#define cxMapRemoveAndGet	(		map,
			key,
			targetbuf )

Value:

cx_map_remove(map, CX_HASH_KEY(key), targetbuf)

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

This function will copy the contents of the removed element to the target buffer, which must be guaranteed to be large enough to hold the element (the map's element size). The destructor functions, if any, will not be called.

If this map is storing pointers, the element is the pointer itself and not the object it points to.

Parameters

map	(CxMap*) the map
key	(any supported key type) the key
targetbuf	(void*) the buffer where the element shall be copied to

Return values

zero	success
non-zero	the key was not found

See also

cxMapRemove()

CX_HASH_KEY()

Enumeration Type Documentation

cx_map_iterator_type

enum cx_map_iterator_type

The type of iterator for a map.

Enumerator
CX_MAP_ITERATOR_PAIRS	Iterates over key/value pairs.
CX_MAP_ITERATOR_KEYS	Iterates over keys only.
CX_MAP_ITERATOR_VALUES	Iterates over values only.

Function Documentation

cx_map_emplace()

void * cx_map_emplace	(	CxMap *	map,
		CxHashKey	key )

Allocates memory for a value in the map associated with the specified key.

A possible existing value will be overwritten. If destructor functions are specified, they are called for the overwritten element.

If the map is storing pointers, this function returns a void** pointer, meaning a pointer to that pointer.

The key is always copied.

Parameters

map	the map
key	the key

Returns

the pointer to the allocated memory or NULL if allocation fails

Return values

zero	success
non-zero	value on memory allocation failure

See also

cxMapEmplace()

cx_map_get()

void * cx_map_get	(	const CxMap *	map,
		CxHashKey	key )

Retrieves a value by using a key.

If this map is storing pointers, the stored pointer is returned. Otherwise, a pointer to the element within the map's memory is returned (which is valid as long as the element stays in the map).

Parameters

map	the map
key	the key

Returns

the value

See also

cxMapGet()

cx_map_put()

int cx_map_put	(	CxMap *	map,
		CxHashKey	key,
		void *	value )

Puts a key/value-pair into the map.

A possible existing value will be overwritten. If destructor functions are specified, they are called for the overwritten element.

If this map is storing pointers, the value pointer is written to the map. Otherwise, the memory is copied from value with memcpy().

The key is always copied.

Parameters

map	the map
key	the key
value	the value

Return values

zero	success
non-zero	value on memory allocation failure

See also

cxMapPut()

cx_map_remove()

int cx_map_remove	(	CxMap *	map,
		CxHashKey	key,
		void *	targetbuf )

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

Invokes the destructor functions, if any, on the removed element if and only if the targetbuf is NULL.

Parameters

map	the map
key	the key
targetbuf	the optional buffer where the removed element shall be copied to

Return values

zero	success
non-zero	the key was not found

See also

cxMapRemove()

cxMapRemoveAndGet()

cxMapClear()

void cxMapClear

(

CxMap *

map

)

Clears a map by removing all elements.

Also calls the content destructor functions for each element, if specified.

Parameters

map	the map to be cleared

cxMapClone()

int cxMapClone	(	CxMap *	dst,
		const CxMap *	src,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Performs a deep clone of one map into another.

If the destination map already contains entries, the cloned entries are added to that map, possibly overwriting existing elements when the keys already exist.

When elements in the destination map need to be replaced, any destructor function is called on the replaced elements before replacing them.

Attention

If the cloned elements need to be destroyed by a destructor function, you must make sure that the destination map also uses this destructor function.

Parameters

dst	the destination map
src	the source map
clone_func	the clone function for the values
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when all elements were successfully cloned
non-zero	when an allocation error occurred

cxMapCloneSimple()

int cxMapCloneSimple	(	CxMap *	dst,
		const CxMap *	src )

Performs a shallow clone of one map into another.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

If the destination map already contains entries, the cloned entries are added to that map, possibly overwriting existing elements when the keys already exist.

When elements in the destination map need to be replaced, any destructor function is called on the replaced elements before replacing them.

Attention

If the cloned elements need to be destroyed by a destructor function, you must make sure that the destination map also uses this destructor function.

Parameters

dst	the destination map
src	the source map

Return values

zero	when all elements were successfully cloned
non-zero	when an allocation error occurred

See also

cxMapClone()

cxMapDifference()

int cxMapDifference	(	CxMap *	dst,
		const CxMap *	minuend,
		const CxMap *	subtrahend,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones entries of a map if their key is not present in another map.

Parameters

dst	the destination map
minuend	the map to subtract the entries from
subtrahend	the map containing the elements to be subtracted
clone_func	the clone function for the values
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapDifferenceSimple()

int cxMapDifferenceSimple	(	CxMap *	dst,
		const CxMap *	minuend,
		const CxMap *	subtrahend )

Clones entries of a map if their key is not present in another map.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

Parameters

dst	the destination map
minuend	the map to subtract the entries from
subtrahend	the map containing the elements to be subtracted

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapFree()

void cxMapFree

(

CxMap *

map

)

Deallocates the memory of the specified map.

Also calls the content destructor functions for each element, if specified.

Parameters

map	the map to be freed

cxMapIntersection()

int cxMapIntersection	(	CxMap *	dst,
		const CxMap *	src,
		const CxMap *	other,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones entries of a map only if their key is present in another map.

Parameters

dst	the destination map
src	the map to clone the entries from
other	the map to check for existence of the keys
clone_func	the clone function for the values
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapIntersectionSimple()

int cxMapIntersectionSimple	(	CxMap *	dst,
		const CxMap *	src,
		const CxMap *	other )

Clones entries of a map only if their key is present in another map.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

Parameters

dst	the destination map
src	the map to clone the entries from
other	the map to check for existence of the keys

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapIterator()

CxMapIterator cxMapIterator

(

const CxMap *

map

)

Creates an iterator for a map.

The elements of the iterator are key/value pairs of type CxMapEntry, and the pointer returned during iterator shall be treated as const CxMapEntry* .

Note

An iterator iterates over all elements successively. Therefore, the order highly depends on the map implementation and may change arbitrarily when the contents change.

Parameters

map	the map to create the iterator for (can be NULL)

Returns

an iterator for the currently stored entries

See also

cxMapIteratorKeys()

cxMapIteratorValues()

cxMapIteratorKeys()

CxMapIterator cxMapIteratorKeys

(

const CxMap *

map

)

Creates a key iterator for a map.

The elements of the iterator are keys of type CxHashKey, and the pointer returned during iterator shall be treated as const CxHashKey* .

Note

An iterator iterates over all elements successively. Therefore, the order highly depends on the map implementation and may change arbitrarily when the contents change.

Parameters

map	the map to create the iterator for (can be NULL)

Returns

an iterator for the currently stored keys

cxMapIteratorValues()

CxMapIterator cxMapIteratorValues

(

const CxMap *

map

)

Creates a value iterator for a map.

When the map is storing pointers, those pointers are returned. Otherwise, the iterator iterates over pointers to the memory within the map where the respective elements are stored.

Note

An iterator iterates over all elements successively. Therefore, the order highly depends on the map implementation and may change arbitrarily when the contents change.

Parameters

map	the map to create the iterator for (can be NULL)

Returns

an iterator for the currently stored values

cxMapListDifference()

int cxMapListDifference	(	CxMap *	dst,
		const CxMap *	src,
		const CxList *	keys,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones entries of a map if their key is not present in a list.

Note that the list must contain keys of type CxKey (or pointers to such keys) and must use cx_hash_key_cmp as the compare function. Generic key types cannot be processed in this case.

Parameters

dst	the destination map
src	the source map
keys	the list of CxKey items
clone_func	the clone function for the values
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapListDifferenceSimple()

int cxMapListDifferenceSimple	(	CxMap *	dst,
		const CxMap *	src,
		const CxList *	keys )

Clones entries of a map if their key is not present in a list.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

Note that the list must contain keys of type CxKey (or pointers to such keys) and must use cx_hash_key_cmp as the compare function. Generic key types cannot be processed in this case.

Parameters

dst	the destination map
src	the source map
keys	the list of CxKey items

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also

cxMapListDifference()

cxMapListIntersection()

int cxMapListIntersection	(	CxMap *	dst,
		const CxMap *	src,
		const CxList *	keys,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones entries of a map only if their key is present in a list.

Note that the list must contain keys of type CxKey (or pointers to such keys) and must use cx_hash_key_cmp as the compare function. Generic key types cannot be processed in this case.

Parameters

dst	the destination map
src	the source map
keys	the list of CxKey items
clone_func	the clone function for the values
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapListIntersectionSimple()

int cxMapListIntersectionSimple	(	CxMap *	dst,
		const CxMap *	src,
		const CxList *	keys )

Clones entries of a map only if their key is present in a list.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

Note that the list must contain keys of type CxKey (or pointers to such keys) and must use cx_hash_key_cmp as the compare function. Generic key types cannot be processed in this case.

Parameters

dst	the destination map
src	the source map
keys	the list of CxKey items

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapSize()

size_t cxMapSize

(

const CxMap *

map

)

Returns the number of elements in this map.

Parameters

map

the map

Returns

the number of stored elements

cxMapUnion()

int cxMapUnion	(	CxMap *	dst,
		const CxMap *	src,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones entries into a map if their key does not exist yet.

If you want to calculate the union of two maps into a fresh new map, you can proceed as follows:

1. Clone the first map into a fresh, empty map.
2. Use this function to clone the second map into the result from step 1.

Parameters

dst	the destination map
src	the map to clone the entries from
clone_func	the clone function for the values
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

cxMapUnionSimple()

int cxMapUnionSimple	(	CxMap *	dst,
		const CxMap *	src )

Clones entries into a map if their key does not exist yet.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

If you want to calculate the union of two maps into a fresh new map, you can proceed as follows:

1. Clone the first map into a fresh, empty map.
2. Use this function to clone the second map into the result from step 1.

Parameters

dst	the destination map
src	the map to clone the entries from

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

Variable Documentation

cxEmptyMap

CxMap* const cxEmptyMap

extern

A shared instance of an empty map.

Writing to that map is not allowed.

You can use this as a placeholder for initializing CxMap pointers for which you do not want to reserve memory right from the beginning.