map.h File Reference

Implementation of a map container. More...

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include "cmagic/memory.h"
#include "cmagic/utils.h"

Go to the source code of this file.

Classes
struct	cmagic_map_iterator_t
struct	cmagic_map_insert_result_t
	Map insertion result. More...

Macros
#define	CMAGIC_MAP(key_type)   key_type*
	Convenient alias for type*. Returned type of CMAGIC_MAP_NEW. More...
#define	CMAGIC_MAP_NEW(key_type, value_type, key_comparator, alloc_packet)
	Allocates and returns an address of a newly created empty map. More...
#define	CMAGIC_MAP_FREE(cmagic_map)   cmagic_map_free((void*)(cmagic_map))
	Frees the resources allocated by the map before. More...
#define	CMAGIC_MAP_ALLOCATE(cmagic_map, key)
	Allocates space for a new element (key-value pair) but does not initialize it. More...
#define	CMAGIC_MAP_INSERT(cmagic_map, key, value)
	Allocates space for a new element and initializes it with data under key and value. More...
#define	CMAGIC_MAP_ERASE_EXT(cmagic_map, key, destructor)
	Extended version of CMAGIC_MAP_ERASE. More...
#define	CMAGIC_MAP_ERASE(cmagic_map, key)   CMAGIC_MAP_ERASE_EXT(cmagic_map, key, NULL)
	Removes a single element (key-value pair) from the map. More...
#define	CMAGIC_MAP_CLEAR(cmagic_map)   cmagic_map_clear((void*)(cmagic_map))
	Removes all elements from the map. More...
#define	CMAGIC_MAP_SIZE(cmagic_map)   cmagic_map_size((void*)(cmagic_map))
	Returns the number of elements in the map. More...
#define	CMAGIC_MAP_FIRST(cmagic_map)   cmagic_map_first((void*)(cmagic_map))
	Return iterator to the first element in map. More...
#define	CMAGIC_MAP_LAST(cmagic_map)   cmagic_map_last((void*)(cmagic_map))
	Return iterator to the last element in map. More...
#define	CMAGIC_MAP_ITERATOR_NEXT(iterator)   cmagic_map_iterator_next(iterator)
	Returns iterator to the next element in container. More...
#define	CMAGIC_MAP_ITERATOR_PREV(iterator)   cmagic_map_iterator_prev(iterator)
	Returns iterator to the previous element in container. More...
#define	CMAGIC_MAP_FIND(cmagic_map, key)
	Searches the container for an element with a key equivalent to key and returns an iterator to it if found, otherwise it returns NULL. More...
#define	CMAGIC_MAP_GET_KEY(key_type, iterator)   (assert(iterator), assert((iterator)->key), *((const key_type*)(iterator)->key))
	Helper macro for retrieving the key from the iterator. More...
#define	CMAGIC_MAP_GET_VALUE(value_type, iterator)   (assert(iterator), assert((iterator)->value), *((value_type*)(iterator)->value))
	Helper macro for retrieving the value from the iterator. More...
#define	CMAGIC_MAP_GET_ALLOC_PACKET(cmagic_map)   cmagic_map_get_alloc_packet((void*)(cmagic_map))
	Retrieves cmagic_memory_alloc_packet_t associated with the map. More...

Typedefs
typedef int(*	cmagic_map_key_comparator_t) (const void *key1, const void *key2)
	Pointer to a function that compares two keys. More...
typedef void(*	cmagic_map_erase_destructor_t) (void *key, void *value)
	User defined additional tasks to be executed right before map element deletion. More...

Detailed Description

Implementation of a map container.

Please use provided macros instead of raw functions to gain additional type checks.

Macro Definition Documentation

CMAGIC_MAP

#define CMAGIC_MAP

(

key_type

)

key_type*

Convenient alias for type*. Returned type of CMAGIC_MAP_NEW.

Warning

Because of C language limitations all type checks are performed only for map keys. User has to be careful while passing map values to macros from this file. Their types must match to the type of map values but this is not checked at compile time.

Parameters

type	type of map keys

CMAGIC_MAP_ALLOCATE

#define CMAGIC_MAP_ALLOCATE	(		cmagic_map,
			key
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_map), *(key)), \
    cmagic_map_allocate((void*)(cmagic_map), (key)))

Allocates space for a new element (key-value pair) but does not initialize it.

New element is allocated only if key doesn't already exist in the map.

Warning

The new element must be initialized right after calling this function. Especially it must be ready then to call cmagic_map_key_comparator_t on it and return the same value as for key. Otherwise the map will be in an undefined state.

Parameters

cmagic_map	a map allocated before with CMAGIC_MAP_NEW
key	pointer to the key value, needed to place a new element in the right place in the internal binary tree

Returns

cmagic_map_insert_result_t pointing to the new or already existing element

CMAGIC_MAP_CLEAR

#define CMAGIC_MAP_CLEAR

(

cmagic_map

)

cmagic_map_clear((void*)(cmagic_map))

Removes all elements from the map.

Parameters

cmagic_map

a map allocated before with CMAGIC_MAP_NEW

CMAGIC_MAP_ERASE

#define CMAGIC_MAP_ERASE	(		cmagic_map,
			key
	)		CMAGIC_MAP_ERASE_EXT(cmagic_map, key, NULL)

Removes a single element (key-value pair) from the map.

Parameters

cmagic_map	a map allocated before with CMAGIC_MAP_NEW
key	pointer to a key to be removed from the map. This function compares by a value, the key doesn't have to be an address of the original key. Does nothing if the element doesn't exist in the map.

CMAGIC_MAP_ERASE_EXT

#define CMAGIC_MAP_ERASE_EXT	(		cmagic_map,
			key,
			destructor
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_map), *(key)), \
    cmagic_map_erase((void*)(cmagic_map), (key), (destructor)))

Extended version of CMAGIC_MAP_ERASE.

Parameters

cmagic_map	a map allocated before with CMAGIC_MAP_NEW
key	pointer to a key to be removed from the map. This function compares by a value, the key doesn't have to be an address of the original key. Does nothing if the element doesn't exist in the map.
destructor	function of type cmagic_map_erase_destructor_t to be called on the key and value right before deleting them

CMAGIC_MAP_FIND

#define CMAGIC_MAP_FIND	(		cmagic_map,
			key
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_map), *(key)), \
    cmagic_map_find((void*)(cmagic_map), (key)))

Searches the container for an element with a key equivalent to key and returns an iterator to it if found, otherwise it returns NULL.

Parameters

key	pointer to a key to be searched for

Returns

an iterator to the element, if key is found, or NULL otherwise

CMAGIC_MAP_FIRST

#define CMAGIC_MAP_FIRST

(

cmagic_map

)

cmagic_map_first((void*)(cmagic_map))

Return iterator to the first element in map.

Returns an iterator pointing to the first element in the map according to the order defined by cmagic_map_key_comparator_t.

Parameters

cmagic_map

a map allocated before with CMAGIC_MAP_NEW

Returns

an iterator to the first element or NULL if the map is empty

CMAGIC_MAP_FREE

#define CMAGIC_MAP_FREE

(

cmagic_map

)

cmagic_map_free((void*)(cmagic_map))

Frees the resources allocated by the map before.

Must not use cmagic_map after free.

Parameters

cmagic_map

a map allocated before with CMAGIC_MAP_NEW

CMAGIC_MAP_GET_ALLOC_PACKET

#define CMAGIC_MAP_GET_ALLOC_PACKET

(

cmagic_map

)

cmagic_map_get_alloc_packet((void*)(cmagic_map))

Retrieves cmagic_memory_alloc_packet_t associated with the map.

Parameters

cmagic_map

a map allocated before with CMAGIC_MAP_NEW

Returns

cmagic_memory_alloc_packet_t associated with the map

CMAGIC_MAP_GET_KEY

#define CMAGIC_MAP_GET_KEY	(		key_type,
			iterator
	)		(assert(iterator), assert((iterator)->key), *((const key_type*)(iterator)->key))

Helper macro for retrieving the key from the iterator.

Warning

iterator must not be NULL

Parameters

key_type	type of the keys of the map which the iterator is associated with
iterator	cmagic_map_iterator_t object

Returns

map key

CMAGIC_MAP_GET_VALUE

#define CMAGIC_MAP_GET_VALUE	(		value_type,
			iterator
	)		(assert(iterator), assert((iterator)->value), *((value_type*)(iterator)->value))

Helper macro for retrieving the value from the iterator.

Warning

iterator must not be NULL

Parameters

value_type	type of the values of the map which the iterator is associated with
iterator	cmagic_map_iterator_t object

Returns

map value

CMAGIC_MAP_INSERT

#define CMAGIC_MAP_INSERT	(		cmagic_map,
			key,
			value
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_map), *(key)), \
    cmagic_map_insert((void*)(cmagic_map), (key), (value)))

Allocates space for a new element and initializes it with data under key and value.

Parameters

cmagic_map	a map allocated before with CMAGIC_MAP_NEW
key	pointer to the key value
value	pointer to the value value

Returns

cmagic_map_insert_result_t pointing to the new or already existing element

CMAGIC_MAP_ITERATOR_NEXT

#define CMAGIC_MAP_ITERATOR_NEXT

(

iterator

)

cmagic_map_iterator_next(iterator)

Returns iterator to the next element in container.

Parameters

iterator

cmagic_map_iterator_t object

Returns

iterator to the next element or NULL if iterator was the last element in container

CMAGIC_MAP_ITERATOR_PREV

#define CMAGIC_MAP_ITERATOR_PREV

(

iterator

)

cmagic_map_iterator_prev(iterator)

Returns iterator to the previous element in container.

Parameters

iterator

cmagic_map_iterator_t object

Returns

iterator to the previous element or NULL if iterator was the first element in container

CMAGIC_MAP_LAST

#define CMAGIC_MAP_LAST

(

cmagic_map

)

cmagic_map_last((void*)(cmagic_map))

Return iterator to the last element in map.

Returns an iterator pointing to the last element in the map according to the order defined by cmagic_map_key_comparator_t.

Parameters

cmagic_map

a map allocated before with CMAGIC_MAP_NEW

Returns

an iterator to the last element or NULL if the map is empty

CMAGIC_MAP_NEW

#define CMAGIC_MAP_NEW	(		key_type,
			value_type,
			key_comparator,
			alloc_packet
	)

Value:

((CMAGIC_MAP(key_type)) \
    cmagic_map_new(sizeof(key_type), sizeof(value_type), (key_comparator), (alloc_packet)))

Allocates and returns an address of a newly created empty map.

Parameters

key_type	type of map elements
value_type	type of map values
key_comparator	function of type cmagic_map_key_comparator_t determining the order of the elements
alloc_packet	cmagic_memory_alloc_packet_t suite of dynamic memory managing functions

Returns

a new empty map

CMAGIC_MAP_SIZE

#define CMAGIC_MAP_SIZE

(

cmagic_map

)

cmagic_map_size((void*)(cmagic_map))

Returns the number of elements in the map.

Parameters

cmagic_map

a map allocated before with CMAGIC_MAP_NEW

Returns

number of elements in the map

Typedef Documentation

cmagic_map_erase_destructor_t

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

User defined additional tasks to be executed right before map element deletion.

Warning

Do not call free function on the key or value. It's called later internally by map implementation

Parameters

key	pointer to key to be deleted
value	pointer to the value to be deleted

cmagic_map_key_comparator_t

typedef int(* cmagic_map_key_comparator_t) (const void *key1, const void *key2)

Pointer to a function that compares two keys.

This function is called by the map implementation to compare two kes, which is necessary to properly construct and move inside its internal binary tree. Both arguments must be manually casted to a type corresponding to the type of the map key. This function defines the order of the elements.

Parameters

key1	pointer to the first key value
key2	pointer to the second first key value

Returns

value	meaning
<0	The element pointed to by key1 goes before the element pointed to by key2
0	The element pointed to by key1 is equivalent to the element pointed to by key2
>0	The element pointed to by key1 goes after the element pointed to by key2