Lely core libraries 2.3.4
|
This header file is part of the utilities library; it contains the bidirectional map declarations. More...
Go to the source code of this file.
Data Structures | |
struct | binode |
A node in a bidirectional map. More... | |
struct | bimap |
A bidirectional map. More... | |
Macros | |
#define | binode_foreach_by_key(first, node) _binode_foreach_by_key(first, node, __LINE__) |
Iterates over each node in a bidirectional map in ascending order by key. More... | |
#define | binode_foreach_by_value(first, node) _binode_foreach_by_value(first, node, __LINE__) |
Iterates over each node in a bidirectional map in ascending order by value. More... | |
#define | bimap_foreach_by_key(map, node) binode_foreach_by_key (bimap_first_by_key(map), node) |
Iterates over each node in a bidirectional map in ascending order by key. More... | |
#define | bimap_foreach_by_value(map, node) binode_foreach_by_value (bimap_first_by_value(map), node) |
Iterates over each node in a bidirectional map in ascending order by value. More... | |
Functions | |
void | binode_init (struct binode *node, const void *key, const void *value) |
Initializes a node in a bidirectional map. More... | |
struct binode * | binode_prev_by_key (const struct binode *node) |
Returns a pointer to the previous (in-order) node by key in a bidirectional map with respect to node. More... | |
struct binode * | binode_next_by_key (const struct binode *node) |
Returns a pointer to the next (in-order) node by key in a bidirectional map with respect to node. More... | |
struct binode * | binode_prev_by_value (const struct binode *node) |
Returns a pointer to the previous (in-order) node by value in a bidirectional map with respect to node. More... | |
struct binode * | binode_next_by_value (const struct binode *node) |
Returns a pointer to the next (in-order) node by value in a bidirectional map with respect to node. More... | |
void | bimap_init (struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp) |
Initializes a bidirectional map. More... | |
int | bimap_empty (const struct bimap *map) |
Returns 1 if the bidirectional map is empty, and 0 if not. | |
size_t | bimap_size (const struct bimap *map) |
Returns the size (in number of nodes) of a bidirectional map. More... | |
void | bimap_insert (struct bimap *map, struct binode *node) |
Inserts a node into a bidirectional map. More... | |
void | bimap_remove (struct bimap *map, struct binode *node) |
Removes a node from a bidirectional map. More... | |
struct binode * | bimap_find_by_key (const struct bimap *map, const void *key) |
Finds a node by key in a bidirectional map. More... | |
struct binode * | bimap_find_by_value (const struct bimap *map, const void *value) |
Finds a node by value in a bidirectional map. More... | |
struct binode * | bimap_first_by_key (const struct bimap *map) |
Returns a pointer to the first (leftmost) node by key in a bidirectional map. More... | |
struct binode * | bimap_last_by_key (const struct bimap *map) |
Returns a pointer to the last (rightmost) node by key in a bidirectional map. More... | |
struct binode * | bimap_first_by_value (const struct bimap *map) |
Returns a pointer to the first (leftmost) node by value in a bidirectional map. More... | |
struct binode * | bimap_last_by_value (const struct bimap *map) |
Returns a pointer to the last (rightmost) node by value in a bidirectional map. More... | |
This header file is part of the utilities library; it contains the bidirectional map declarations.
The bidirectional map is implemented as a pair of red-black trees, one for lookups by key, the other for lookups by value. The implementation is generic and can be used for any kind of key-value pair. Only (void) pointers to keys and values are stored. Upon initialization of the map, the user is responsible for providing suitable comparison functions (cmp_t).
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Definition in file bimap.h.
#define binode_foreach_by_key | ( | first, | |
node | |||
) | _binode_foreach_by_key(first, node, __LINE__) |
Iterates over each node in a bidirectional map in ascending order by key.
It is safe to remove the current node during the iteration.
first | a pointer to the first node. |
node | the name of the pointer to the nodes. This variable is declared in the scope of the loop. |
#define binode_foreach_by_value | ( | first, | |
node | |||
) | _binode_foreach_by_value(first, node, __LINE__) |
Iterates over each node in a bidirectional map in ascending order by value.
It is safe to remove the current node during the iteration.
first | a pointer to the first node. |
node | the name of the pointer to the nodes. This variable is declared in the scope of the loop. |
#define bimap_foreach_by_key | ( | map, | |
node | |||
) | binode_foreach_by_key (bimap_first_by_key(map), node) |
Iterates over each node in a bidirectional map in ascending order by key.
#define bimap_foreach_by_value | ( | map, | |
node | |||
) | binode_foreach_by_value (bimap_first_by_value(map), node) |
Iterates over each node in a bidirectional map in ascending order by value.
|
inline |
Initializes a node in a bidirectional map.
node | a pointer to the node to be initialized. |
key | a pointer to the key of the node. The key MUST NOT be modified while the node is part of a map. |
value | a pointer to the value of the node. The value MUST NOT be modified while the node is part of a map. |
Returns a pointer to the previous (in-order) node by key in a bidirectional map with respect to node.
This is, at worst, an O(log(n)) operation.
Returns a pointer to the next (in-order) node by key in a bidirectional map with respect to node.
This is, at worst, an O(log(n)) operation. However, visiting all nodes in order is an O(n) operation, and therefore, on average, O(1) for each node.
Returns a pointer to the previous (in-order) node by value in a bidirectional map with respect to node.
This is, at worst, an O(log(n)) operation.
Returns a pointer to the next (in-order) node by value in a bidirectional map with respect to node.
This is, at worst, an O(log(n)) operation. However, visiting all nodes in order is an O(n) operation, and therefore, on average, O(1) for each node.
|
inline |
Inserts a node into a bidirectional map.
This is an O(log(n)) operation. This function does not check whether a node with the same key or value already exists, or whether the node is already part of another map.
Finds a node by key in a bidirectional map.
This is an O(log(n)) operation.
Finds a node by value in a bidirectional map.
This is an O(log(n)) operation.
Returns a pointer to the first (leftmost) node by key in a bidirectional map.
This is an O(log(n)) operation.
Returns a pointer to the last (rightmost) node by key in a bidirectional map.
This is an O(log(n)) operation.
Returns a pointer to the first (leftmost) node by value in a bidirectional map.
This is an O(log(n)) operation.
Returns a pointer to the last (rightmost) node by value in a bidirectional map.
This is an O(log(n)) operation.