GATE
C/C++ Framework
|
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. |
Associative fields to map and resolve key entries to values.
#define GATE_MAP_FOREACH | ( | iterator_var, | |
ptr_map ) |
for-each macro to iterate over elements of a map
iterator_var | name of iterator variable to be used |
ptr_map | Pointer to map to be accessed |
#define GATE_MAP_ITER_KEY | ( | type, | |
iter ) |
Typed key accessor for iterators.
type | data-type of key (e.g. int or gate_string_t |
iter | Iterator to valid element |
type
#define GATE_MAP_ITER_VALUE | ( | type, | |
iter ) |
Typed value accessor for iterators.
type | data-type of value (e.g. int or gate_string_t |
iter | Iterator to valid element |
type
#define gate_set_create | ( | s, | |
comparer, | |||
key_size, | |||
key_ctor, | |||
key_dtor ) |
Creates a set of unique keys.
[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 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
typedef struct gate_treenode gate_treenode_t |
@ brief Represents a single node in a sorted R-B-tree
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))"
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)".
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.
[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 |
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.
[in] | root | Root of the tree to be balanced |
[in] | node | Inserted node |
GATE_CORE_API gate_treenode_t * gate_treenode_minimum | ( | gate_treenode_t * | node | ) |
Returns the left-most side of a tree-node.
[in] | node | Pointer to node to start search |
GATE_CORE_API gate_treenode_t * gate_treenode_maximum | ( | gate_treenode_t * | node | ) |
Returns the right-most side of a tree-node.
[in] | node | Pointer to node to start search |
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.
[in] | node | Pointer to source 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.
[in] | node | Pointer to source 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.
[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 |
m
or NULL in case of failure 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.
[out] | dst | Pointer to map structure to be initialized |
[in] | src | Pointer to source map thats content and types are copied |
m
or NULL in case of allocation/copy failure GATE_CORE_API void gate_map_destroy | ( | gate_map_t * | m | ) |
Destroys the map and its allocated contents.
[in] | m | Pointer to map to be destroyed |
GATE_CORE_API gate_size_t gate_map_count | ( | gate_map_t const * | m | ) |
Returns the amount of nodes in a map.
[in] | m | Pointer to map to be accessed |
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)
[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 |
GATE_CORE_API gate_bool_t gate_map_remove | ( | gate_map_t * | m, |
void const * | key ) |
Removes a key/value pair from the map.
[in] | m | Pointer to map to be accessed |
[in] | key | Pointer to key content to be removed |
true
if key was found and removed, otherwise false
GATE_CORE_API gate_bool_t gate_map_is_empty | ( | gate_map_t const * | m | ) |
Checks if no content is in a map.
[in] | m | Pointer to map to be accessed |
true
if map has no content, otherwise false
GATE_CORE_API void gate_map_clear | ( | gate_map_t * | m | ) |
Removes all contents from the map.
[in] | m | Pointer to map to be accessed |
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.
[in] | m | Pointer to target map to be updated |
[in] | with | Pointer to source map thats content is imported |
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.
[in] | m | Pointer to target map to be updated |
[in] | keys | Pointer to source map with keys to be removed from m |
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.
[in] | m | Pointer to map to be accessed |
[in] | key | Pointer to key to be searched |
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)
[in] | m | Pointer to map to be accessed |
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)
[in] | m | Pointer to map to be accessed |
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))
[in] | m | Pointer to map to be accessed |
GATE_CORE_API gate_map_iterator_t gate_map_iterator_next | ( | gate_map_iterator_t | iterator | ) |
Retrieves the next following element of an iterator.
[in] | iterator | Source iterator |
iterator
GATE_CORE_API gate_map_iterator_t gate_map_iterator_prev | ( | gate_map_iterator_t | iterator | ) |
Retrieves the previous element of an iterator.
[in] | iterator | Source iterator |
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.
[in] | iter1 | First iterator to be compared |
[in] | iter2 | Second iterator to be compared |
true
if both iterators are pointing to the same element, otherwise false
GATE_CORE_API gate_bool_t gate_map_iterator_valid | ( | gate_map_iterator_t | iterator | ) |
Evaluates if an iterator points to a valid element.
[in] | iterator | Iterator to be evaluated |
true
if iterator is valid, otherwise false
(e.g. when NULL) 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.
[in] | m | Pointer to source map to be enumerated |
[out] | enumerator | Pointer to enumerator to be initialized |
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.
[in] | m | Pointer to map to be accessed |
[in] | key | Pointer to key to be searched |
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.
[in] | iterator | Iterator pointing to a valid entry |
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.
[in] | iterator | Iterator pointing the a valid entry |