Provides a dictionary which is based on a sorted list. More...

Data Structures
struct	util_map
	Structure for a map, see also map. More...

Macros
#define	UTIL_MAP_NIL -1
	Identifier for an invalid index.

#define	util_map_foreach(i, map) for (i = util_map_first(map); i != UTIL_MAP_NIL; i = util_map_next(map, i))
	Foreach loop for iterating over a map.

Typedefs
typedef int(*	util_map_compar )(const void a, const void b)
	Compare function for keys stored in the map. More...

typedef void(*	util_map_delete )(void key, void value)
	Delete function for the keys/values store in the map. More...

typedef int	util_map_iterator
	Iterator for the map.

Functions
int	util_map_size (int num_elements)
	Computes the size in bytes for `num_elements` map entries. More...

void	util_map_init (struct util_map m, util_map_compar comp, void data, int size)
	Initializes the given map. More...

void *	util_map_clear (struct util_map *m)
	Clear a map `m`. More...

int	util_map_count (const struct util_map *m)
	Returns the number of elements in the map. More...

int	util_map_maxcount (const struct util_map *m)
	Returns the size of the map in number of entries. More...

int	util_map_insert (struct util_map m, void key, void newval, void *oldval)
	Inserts a new item with the key `key` and a value of `newval`. More...

int	util_map_replace (struct util_map m, void key, void newval, void *oldval)
	Replaces the value identified by `key` with the value `newval`. More...

void *	util_map_remove (struct util_map m, const void key)
	Removes the item with the given `key` and returns its value. More...

void *	util_map_lookup (const struct util_map m, const void key)
	Returns the value identified by `key`. More...

util_map_iterator	util_map_find (const struct util_map m, const void key)
	Find a given key in the map `m`. More...

util_map_iterator	util_map_first (const struct util_map *m)
	Returns an iterator to the first element in the map. More...

util_map_iterator	util_map_next (const struct util_map *m, util_map_iterator it)
	Returns an iterator for the next element. More...

void *	util_map_value (const struct util_map *m, util_map_iterator it)
	Returns the value for the given iterator `it`. More...

void *	util_map_key (const struct util_map *m, util_map_iterator it)
	Returns the key for the given iterator `it`. More...

void	util_map_delete_all (struct util_map *m, util_map_delete del)
	Removes all elements from the map and calls `del` for each element. More...

Detailed Description

Provides a dictionary which is based on a sorted list.

Lookup is implemented using a binary search and operates in O(log n). Insert and remove operations have a complexity of O(n). This implementation should be used for mid-sized amount of data (100-10000 elements), where a list would be too slow. For bigger data the util_hash_map should be used. The advantage of util_map over util_hash_map is, that util_map applies an order on the elements. When iterating over util_map the elements are sorted by key, whereas with util_hash_map the elements are arbitrarily ordered.

Typedef Documentation

typedef int(* util_map_compar)(const void *a, const void *b)

Compare function for keys stored in the map.

Must return zero if elements are equal and negative/positive value if one element is smaller/bigger than the other.

typedef void(* util_map_delete)(void *key, void *value)

Delete function for the keys/values store in the map.

Must delete all resources connected to the key/value.

Function Documentation

void* util_map_clear ( struct util_map * m )

Clear a map m.

No furhter operations may be performed on this map after clearing.

Returns: The data pointer that was given in util_map_init(), as it might need to be freed.

int util_map_count ( const struct util_map * m )

Returns the number of elements in the map.

void util_map_delete_all	(	struct util_map *	m,
		util_map_delete	del
	)

Removes all elements from the map and calls del for each element.

You can use del to cleanup memory references by each element.

util_map_iterator util_map_find	(	const struct util_map *	m,
		const void *	key
	)

Find a given key in the map m.

Returns an iterator, that can be used to retrieve the key: util_map_key or the value: util_map_value.

util_map_iterator util_map_first ( const struct util_map * m )

Returns an iterator to the first element in the map.

This is use for iteration over all elements. It is recommended to use util_map_forach for iterating over all map elements.

Parameters

m	Pointer map.

Returns: Valid iterator or UTIL_MAP_NIL if the map is empty.

void util_map_init	(	struct util_map *	m,
		util_map_compar	comp,
		void *	data,
		int	size
	)

Initializes the given map.

Parameters

m	Pointer to map.
comp	compare functions which is used to apply an order on the items.
data	Pointer to preallocated memory to use for the map.
size	Size of the internal map array. This is the maximum number of items you can store in a map.

int util_map_insert	(	struct util_map *	m,
		void *	key,
		void *	newval,
		void **	oldval
	)

Inserts a new item with the key key and a value of newval.

Parameters

m	Pointer to map.
key	key used to identify the value.
newval	Value to store in the map.
oldval	Returns the existing value if there is one.

Returns: If the key already exists this function returns -2. If the map is full the function returns -1. If the function succeeds the function returns 0.

void* util_map_key	(	const struct util_map *	m,
		util_map_iterator	it
	)

Returns the key for the given iterator it.

Returns: Value of NULL if the iterator is invalid.

void* util_map_lookup	(	const struct util_map *	m,
		const void *	key
	)

Returns the value identified by key.

Parameters

m	Pointer to map.
key	key used to identify the value.

Returns: The found value or NULL if not found.

int util_map_maxcount ( const struct util_map * m )

Returns the size of the map in number of entries.

util_map_iterator util_map_next	(	const struct util_map *	m,
		util_map_iterator	it
	)

Returns an iterator for the next element.

It is recommended to us util_map_forach for iterating over all map elements.

Parameters

m	Pointer map.
it	iterator of current element.

Returns: Valid iterator for next element or UTIL_MAP_NIL if no more items are left.

void* util_map_remove	(	struct util_map *	m,
		const void *	key
	)

Removes the item with the given key and returns its value.

Parameters

m	Pointer to map.
key	key use for lookup.

Returns: The value added in util_map_insert or NULL if the key does not exist.

int util_map_replace	(	struct util_map *	m,
		void *	key,
		void *	newval,
		void **	oldval
	)

Replaces the value identified by key with the value newval.

If the key does not exists this function inserts it as new item.

Parameters

m	Pointer to map.
key	key used to identify the value.
newval	Value to store in the map.
oldval	Returns the existing value if there is one. If there is already an item with the key `key`, that item's value is replaced with `x`.

int util_map_size ( int num_elements )

Computes the size in bytes for num_elements map entries.

This can be used by the called to allocate the correct amount of memory for util_map_init.

void* util_map_value	(	const struct util_map *	m,
		util_map_iterator	it
	)

Returns the value for the given iterator it.

Returns: Value of NULL if the iterator is invalid.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation