Associative fields to map and resolve key entries to values. More...

#include "gate/gate_core_api.h"
#include "gate/memalloc.h"
#include "gate/comparers.h"
#include "gate/enumerators.h"

Data Structures
struct	gate_mapping_class
	mapping entry base class More...
struct	gate_treenode
struct	gate_map_class
	A `gate_map_t` structure contains is a sorted tree of key/value pairs. More...
struct	gate_flatmap_class
	A flat map stores an array of key/value pair, the key needs to be unique. More...

Macros
#define	GATE_MAP_FOREACH(iterator_var, ptr_map)
	for-each macro to iterate over elements of a map
#define	GATE_MAP_ITER_KEY(type, iter)
	Typed key accessor for iterators.
#define	GATE_MAP_ITER_VALUE(type, iter)
	Typed value accessor for iterators.
#define	gate_set_create(s, comparer, key_size, key_ctor, key_dtor)
	Creates a set of unique keys.
#define	gate_set_copy(dst, src)
	Creates a set by copying the contents of another set.
#define	gate_set_destroy(s)
	Releases all allocated resources of a set.
#define	gate_set_count(s)
	Returns the amount of elements in a set.
#define	gate_set_add(s, key)
	Adds an element to the set (or replaces an existing one)
#define	gate_set_remove(s, key)
	Removes an element from the set.
#define	gate_set_is_empty(s)
	Determines if the set is currently empty.
#define	gate_set_clear(s)
	Removes all elements from the set.
#define	gate_set_get(s, key)
	Returns an iterator to the set element matching the key.
#define	gate_set_first(s)
	Returns an iterator to the first element in the set (smallest in search order)
#define	gate_set_last(s)
	Returns an iterator to the last element in the set (greatest in search order)
#define	gate_set_end(s)
	Returns an iterator to the virtual end (NULL element) of a set.
#define	gate_set_iterator_next(s)
	Returns an iterator to the next following element relative to the given iterator.
#define	gate_set_iterator_prev(s)
	Returns an iterator to the previous element relative to the given iterator.
#define	gate_set_iterator_equals(i1, i2)
	Determines if two iterators are pointing to the same element.
#define	gate_set_iterator_valid(s)
	Determines if an iterator is pointing to a valid element.
#define	gate_set_remove_keys(s, keys)
	Removes all elements in set that are also contained in another key set.
#define	gate_set_merge(s, with)
	Imports all elements of a set into a target set.

Typedefs
typedef struct gate_mapping_class	gate_mapping_t
	mapping entry base class
typedef struct gate_treenode	gate_treenode_t
typedef struct gate_map_class	gate_map_t
	A `gate_map_t` structure contains is a sorted tree of key/value pairs.
typedef gate_treenode_t *	gate_map_iterator_t
	Iterator pointing to an element within a map.
typedef struct gate_flatmap_class	gate_flatmap_t
	A flat map stores an array of key/value pair, the key needs to be unique.
typedef gate_mapping_t const const	gate_flatmap_iterator_t
	Iterator pointing to mapping-item in flat map.

Functions
GATE_CORE_API gate_treenode_t *	gate_treenode_find (gate_treenode_t root, gate_comparer_t comparer, void const key, gate_treenode_t **ptr_last_parent)
	Finds a node in a tree of nodes by the given comparer and key.
GATE_CORE_API void	gate_treenode_insert_repair_tree (gate_treenode_t *root, gate_treenode_t node)
	Rebalances the tree after a node was inserted.
GATE_CORE_API void	gate_treenode_remove_repair_tree (gate_treenode_t *root, gate_treenode_t node)
	Removes a node from the tree and rebalances the tree structure param[in] root Pointer to root-node-pointer param[in] node Node to be removed.
GATE_CORE_API gate_treenode_t *	gate_treenode_minimum (gate_treenode_t *node)
	Returns the left-most side of a tree-node.
GATE_CORE_API gate_treenode_t *	gate_treenode_maximum (gate_treenode_t *node)
	Returns the right-most side of a tree-node.
GATE_CORE_API gate_treenode_t *	gate_treenode_next (gate_treenode_t *node)
	Returns the next node in the sorting order of a specific node.
GATE_CORE_API gate_treenode_t *	gate_treenode_prev (gate_treenode_t *node)
	Returns the previous node in the sorting order of a specific node.
GATE_CORE_API gate_map_t *	gate_map_create (gate_map_t *m, gate_comparer_t key_comparer, gate_size_t key_size, gate_mem_copyctor_t key_ctor, gate_mem_dtor_t key_dtor, gate_size_t value_size, gate_mem_copyctor_t value_ctor, gate_mem_dtor_t value_dtor)
	Creates a new mapping table structure.
GATE_CORE_API gate_map_t *	gate_map_copy (gate_map_t dst, gate_map_t const src)
	Creates a new mapping table structure by copying content from another map.
GATE_CORE_API void	gate_map_destroy (gate_map_t *m)
	Destroys the map and its allocated contents.
GATE_CORE_API gate_size_t	gate_map_count (gate_map_t const *m)
	Returns the amount of nodes in a map.
GATE_CORE_API gate_map_iterator_t	gate_map_add (gate_map_t m, void const key, void const *value)
	Adds a new key/value pair to the map or replaces an existing node if key already exists)
GATE_CORE_API gate_bool_t	gate_map_remove (gate_map_t m, void const key)
	Removes a key/value pair from the map.
GATE_CORE_API gate_bool_t	gate_map_is_empty (gate_map_t const *m)
	Checks if no content is in a map.
GATE_CORE_API void	gate_map_clear (gate_map_t *m)
	Removes all contents from the map.
GATE_CORE_API gate_size_t	gate_map_merge (gate_map_t m, gate_map_t const with)
	Imports all contents from one map into target map.
GATE_CORE_API gate_size_t	gate_map_remove_keys (gate_map_t m, gate_map_t const keys)
	Removes all nodes in a target map, that are part of another map.
GATE_CORE_API gate_map_iterator_t	gate_map_get (gate_map_t const m, void const key)
	Searches a key and returns an iterator to its entry.
GATE_CORE_API gate_map_iterator_t	gate_map_first (gate_map_t const *m)
	Returns an iterator to the first element in the map (smallest in search order)
GATE_CORE_API gate_map_iterator_t	gate_map_last (gate_map_t const *m)
	Returns an iterator to the last element in the map (greatest in search order)
GATE_CORE_API gate_map_iterator_t	gate_map_end (gate_map_t const *m)
	Returns an iterator to a not existing element (NULL)
GATE_CORE_API gate_map_iterator_t	gate_map_iterator_next (gate_map_iterator_t iterator)
	Retrieves the next following element of an iterator.
GATE_CORE_API gate_map_iterator_t	gate_map_iterator_prev (gate_map_iterator_t iterator)
	Retrieves the previous element of an iterator.
GATE_CORE_API gate_bool_t	gate_map_iterator_equals (gate_map_iterator_t iter1, gate_map_iterator_t iter2)
	Compares two iterators for equality.
GATE_CORE_API gate_bool_t	gate_map_iterator_valid (gate_map_iterator_t iterator)
	Evaluates if an iterator points to a valid element.
GATE_CORE_API gate_enumerator_t *	gate_map_enumerate (gate_map_t const m, gate_enumerator_t enumerator)
	Initializes an enumerator structure to walk through all map elements.
GATE_CORE_API void *	gate_map_get_value (gate_map_t const m, void const key)
	Returns a pointer to value addressed by a key.
GATE_CORE_API void const *	gate_map_iterator_key (gate_map_iterator_t iterator)
	Returns a pointer to the key of an element an iterator is pointing to.
GATE_CORE_API void *	gate_map_iterator_value (gate_map_iterator_t iterator)
	Returns a pointer to the value of an element an iterator is pointing to.
GATE_CORE_API gate_result_t	gate_map_copy_constructor (void dest, void const src)
	Copy constructor function for map types.
GATE_CORE_API void	gate_map_destructor (void *dest)
	Destructor function for map types.

Detailed Description

Associative fields to map and resolve key entries to values.

Macro Definition Documentation

◆ GATE_MAP_FOREACH

#define GATE_MAP_FOREACH	(		iterator_var,
			ptr_map )

Value:

for(iterator_var = gate_map_first(ptr_map); gate_map_iterator_valid(iterator_var); iterator_var = gate_map_iterator_next(iterator_var))

for-each macro to iterate over elements of a map

Parameters

iterator_var	name of iterator variable to be used
ptr_map	Pointer to map to be accessed

◆ GATE_MAP_ITER_KEY

#define GATE_MAP_ITER_KEY	(		type,
			iter )

Value:

(*((type const*)iter->mapping.key))

Typed key accessor for iterators.

Parameters

type	data-type of key (e.g. `int` or `gate_string_t`
iter	Iterator to valid element

Returns: Reference to key using data-type of type

◆ GATE_MAP_ITER_VALUE

#define GATE_MAP_ITER_VALUE	(		type,
			iter )

Value:

(*((type*)iter->mapping.value))

Typed value accessor for iterators.

Parameters

type	data-type of value (e.g. `int` or `gate_string_t`
iter	Iterator to valid element

Returns: Reference to value using data-type of type

◆ gate_set_create

#define gate_set_create	(	s,
		comparer,
		key_size,
		key_ctor,
		key_dtor )

Value:

gate_map_create(s, comparer, key_size, key_ctor, key_dtor, 0, NULL, NULL)

Creates a set of unique keys.

Parameters

[in]	s	Pointer to set to be initialized
[in]	comparer	Pointer to key comparer function
[in]	key_size	Size of one key element
[in]	key_ctor	Optional copy constructor function for key types
[in]	key_dtor	Optional destructor function for key types

Typedef Documentation

◆ gate_mapping_t

typedef struct gate_mapping_class gate_mapping_t

mapping entry base class

Implementations may allocate a block of memory containing key and value content gate_mapping_t is a generic header that prepends the content

◆ gate_treenode_t

typedef struct gate_treenode gate_treenode_t

@ brief Represents a single node in a sorted R-B-tree

◆ gate_map_t

typedef struct gate_map_class gate_map_t

A gate_map_t structure contains is a sorted tree of key/value pairs.

Elements are inserted by comparing their key-part. A key is unique in the map, if the same key is inserted again, it overwrites the content of previous key/value pair. Key searches have a complexity of "O(log(n))"

◆ gate_flatmap_t

typedef struct gate_flatmap_class gate_flatmap_t

A flat map stores an array of key/value pair, the key needs to be unique.

This map type preserves the order in which items were added at its end. Key searchs have complexity of "O(n)".

Function Documentation

◆ gate_treenode_find()

GATE_CORE_API gate_treenode_t * gate_treenode_find	(	gate_treenode_t *	root,
		gate_comparer_t	comparer,
		void const *	key,
		gate_treenode_t **	ptr_last_parent )

Finds a node in a tree of nodes by the given comparer and key.

Parameters

[in]	root	Pointer to root node
[in]	comparer	Compare function to evalute key
[in]	key	Pointer to key content to be found
[out]	ptr_last_parent	Optional pointer to tree-node-pointer to be filled with last accessed parent node

Returns: Pointer to found tree node in tree, or NULL if no key did match

◆ gate_treenode_insert_repair_tree()

GATE_CORE_API void gate_treenode_insert_repair_tree	(	gate_treenode_t **	root,
		gate_treenode_t *	node )

Rebalances the tree after a node was inserted.

Parameters

[in]	root	Root of the tree to be balanced
[in]	node	Inserted node

◆ gate_treenode_minimum()

GATE_CORE_API gate_treenode_t * gate_treenode_minimum ( gate_treenode_t * node )

Returns the left-most side of a tree-node.

Parameters

[in] node Pointer to node to start search

Returns: Returns the left-most node relative to start node

◆ gate_treenode_maximum()

GATE_CORE_API gate_treenode_t * gate_treenode_maximum ( gate_treenode_t * node )

Returns the right-most side of a tree-node.

Parameters

[in] node Pointer to node to start search

Returns: Returns the right-most node relative to start node

◆ gate_treenode_next()

GATE_CORE_API gate_treenode_t * gate_treenode_next ( gate_treenode_t * node )

Returns the next node in the sorting order of a specific node.

Parameters

[in] node Pointer to source node

Returns: Pointer to next following node in sorting order, or NULL if no next node is available

◆ gate_treenode_prev()

GATE_CORE_API gate_treenode_t * gate_treenode_prev ( gate_treenode_t * node )

Returns the previous node in the sorting order of a specific node.

Parameters

[in] node Pointer to source node

Returns: Pointer to previous node in sorting order, or NULL if no next node is available

◆ gate_map_create()

GATE_CORE_API gate_map_t * gate_map_create	(	gate_map_t *	m,
		gate_comparer_t	key_comparer,
		gate_size_t	key_size,
		gate_mem_copyctor_t	key_ctor,
		gate_mem_dtor_t	key_dtor,
		gate_size_t	value_size,
		gate_mem_copyctor_t	value_ctor,
		gate_mem_dtor_t	value_dtor )

Creates a new mapping table structure.

Parameters

[out]	m	Pointer to map structure to be initialized
[in]	key_comparer	Pointer to compare function for key searches
[in]	key_size	Size of key element type
[in]	key_ctor	Optional constructor function for key elements
[in]	key_dtor	Optional destructor function for key elements
[in]	value_size	Size of value element type
[in]	value_ctor	Optional constructor function for value elements
[in]	value_dtor	Optional destructor function for value elements

Returns: Returns pointer to map m or NULL in case of failure

◆ gate_map_copy()

GATE_CORE_API gate_map_t * gate_map_copy	(	gate_map_t *	dst,
		gate_map_t const *	src )

Creates a new mapping table structure by copying content from another map.

Parameters

[out]	dst	Pointer to map structure to be initialized
[in]	src	Pointer to source map thats content and types are copied

Returns: Returns a pointer to map m or NULL in case of allocation/copy failure

◆ gate_map_destroy()

GATE_CORE_API void gate_map_destroy ( gate_map_t * m )

Destroys the map and its allocated contents.

Parameters

[in] m Pointer to map to be destroyed

◆ gate_map_count()

GATE_CORE_API gate_size_t gate_map_count ( gate_map_t const * m )

Returns the amount of nodes in a map.

Parameters

[in] m Pointer to map to be accessed

Returns: Count of contained nodes in map

◆ gate_map_add()

GATE_CORE_API gate_map_iterator_t gate_map_add	(	gate_map_t *	m,
		void const *	key,
		void const *	value )

Adds a new key/value pair to the map or replaces an existing node if key already exists)

Parameters

[in]	m	Pointer to map to be accessed
[in]	key	Pointer to key content to be added/replaced
[in]	value	Pointer to value content to be added/replaced

Returns: Iterator to new/updated node, or NULL if map update failed

◆ gate_map_remove()

GATE_CORE_API gate_bool_t gate_map_remove	(	gate_map_t *	m,
		void const *	key )

Removes a key/value pair from the map.

Parameters

[in]	m	Pointer to map to be accessed
[in]	key	Pointer to key content to be removed

Returns: true if key was found and removed, otherwise false

◆ gate_map_is_empty()

GATE_CORE_API gate_bool_t gate_map_is_empty ( gate_map_t const * m )

Checks if no content is in a map.

Parameters

[in] m Pointer to map to be accessed

Returns: true if map has no content, otherwise false

◆ gate_map_clear()

GATE_CORE_API void gate_map_clear ( gate_map_t * m )

Removes all contents from the map.

Parameters

[in] m Pointer to map to be accessed

◆ gate_map_merge()

GATE_CORE_API gate_size_t gate_map_merge	(	gate_map_t *	m,
		gate_map_t const *	with )

Imports all contents from one map into target map.

Parameters

[in]	m	Pointer to target map to be updated
[in]	with	Pointer to source map thats content is imported

Returns: Amount of key/value pairs that where imported

◆ gate_map_remove_keys()

GATE_CORE_API gate_size_t gate_map_remove_keys	(	gate_map_t *	m,
		gate_map_t const *	keys )

Removes all nodes in a target map, that are part of another map.

Parameters

[in]	m	Pointer to target map to be updated
[in]	keys	Pointer to source map with keys to be removed from `m`

Returns: Amount of entries that where removed

◆ gate_map_get()

GATE_CORE_API gate_map_iterator_t gate_map_get	(	gate_map_t const *	m,
		void const *	key )

Searches a key and returns an iterator to its entry.

Parameters

[in]	m	Pointer to map to be accessed
[in]	key	Pointer to key to be searched

Returns: Iterator to found entry, or NULL if key was not in map

◆ gate_map_first()

GATE_CORE_API gate_map_iterator_t gate_map_first ( gate_map_t const * m )

Returns an iterator to the first element in the map (smallest in search order)

Parameters

[in] m Pointer to map to be accessed

Returns: Iterator to first element in map, or NULL if map is empty

◆ gate_map_last()

GATE_CORE_API gate_map_iterator_t gate_map_last ( gate_map_t const * m )

Returns an iterator to the last element in the map (greatest in search order)

Parameters

[in] m Pointer to map to be accessed

Returns: Iterator to last element in map, or NULL if map is empty

◆ gate_map_end()

GATE_CORE_API gate_map_iterator_t gate_map_end ( gate_map_t const * m )

Returns an iterator to a not existing element (NULL)

Used for iterator comparison, e.g. for(i = first, i != end; i = next(i))

Parameters

[in] m Pointer to map to be accessed

Returns: Iterator to virtual end element (NULL)

◆ gate_map_iterator_next()

GATE_CORE_API gate_map_iterator_t gate_map_iterator_next ( gate_map_iterator_t iterator )

Retrieves the next following element of an iterator.

Parameters

[in] iterator Source iterator

Returns: Iterator to following element of iterator

◆ gate_map_iterator_prev()

GATE_CORE_API gate_map_iterator_t gate_map_iterator_prev ( gate_map_iterator_t iterator )

Retrieves the previous element of an iterator.

Parameters

[in] iterator Source iterator

Returns: Iterator to previous element of iterator

◆ gate_map_iterator_equals()

GATE_CORE_API gate_bool_t gate_map_iterator_equals	(	gate_map_iterator_t	iter1,
		gate_map_iterator_t	iter2 )

Compares two iterators for equality.

Parameters

[in]	iter1	First iterator to be compared
[in]	iter2	Second iterator to be compared

Returns: true if both iterators are pointing to the same element, otherwise false

◆ gate_map_iterator_valid()

GATE_CORE_API gate_bool_t gate_map_iterator_valid ( gate_map_iterator_t iterator )

Evaluates if an iterator points to a valid element.

Parameters

[in] iterator Iterator to be evaluated

Returns: true if iterator is valid, otherwise false (e.g. when NULL)

◆ gate_map_enumerate()

GATE_CORE_API gate_enumerator_t * gate_map_enumerate	(	gate_map_t const *	m,
		gate_enumerator_t *	enumerator )

Initializes an enumerator structure to walk through all map elements.

Parameters

[in]	m	Pointer to source map to be enumerated
[out]	enumerator	Pointer to enumerator to be initialized

Returns: Pointer to enumerator, or NULL if initialization failed

◆ gate_map_get_value()

GATE_CORE_API void * gate_map_get_value	(	gate_map_t const *	m,
		void const *	key )

Returns a pointer to value addressed by a key.

Parameters

[in]	m	Pointer to map to be accessed
[in]	key	Pointer to key to be searched

Returns: Pointer to associated value, or NULL if key was not found

◆ gate_map_iterator_key()

GATE_CORE_API void const * gate_map_iterator_key ( gate_map_iterator_t iterator )

Returns a pointer to the key of an element an iterator is pointing to.

Parameters

[in] iterator Iterator pointing to a valid entry

Returns: Pointer to key

◆ gate_map_iterator_value()

GATE_CORE_API void * gate_map_iterator_value ( gate_map_iterator_t iterator )

Returns a pointer to the value of an element an iterator is pointing to.

Parameters

[in] iterator Iterator pointing the a valid entry

Returns: Pointer to value

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ GATE_MAP_FOREACH

◆ GATE_MAP_ITER_KEY

◆ GATE_MAP_ITER_VALUE

◆ gate_set_create

Typedef Documentation

◆ gate_mapping_t

◆ gate_treenode_t

◆ gate_map_t

◆ gate_flatmap_t

Function Documentation

◆ gate_treenode_find()

◆ gate_treenode_insert_repair_tree()

◆ gate_treenode_minimum()

◆ gate_treenode_maximum()

◆ gate_treenode_next()

◆ gate_treenode_prev()

◆ gate_map_create()

◆ gate_map_copy()

◆ gate_map_destroy()

◆ gate_map_count()

◆ gate_map_add()

◆ gate_map_remove()

◆ gate_map_is_empty()

◆ gate_map_clear()

◆ gate_map_merge()

◆ gate_map_remove_keys()

◆ gate_map_get()

◆ gate_map_first()

◆ gate_map_last()

◆ gate_map_end()

◆ gate_map_iterator_next()

◆ gate_map_iterator_prev()

◆ gate_map_iterator_equals()

◆ gate_map_iterator_valid()

◆ gate_map_enumerate()

◆ gate_map_get_value()

◆ gate_map_iterator_key()

◆ gate_map_iterator_value()