Lely core libraries
2.2.5
|
Go to the documentation of this file.
29 #ifndef LELY_UTIL_BIMAP_H_
30 #define LELY_UTIL_BIMAP_H_
35 #ifndef LELY_UTIL_BIMAP_INLINE
36 #define LELY_UTIL_BIMAP_INLINE static inline
75 struct binode *node,
const void *key,
const void *value);
84 const struct binode *node);
95 const struct binode *node);
104 const struct binode *node);
115 const struct binode *node);
128 #define binode_foreach_by_key(first, node) \
129 _binode_foreach_by_key(first, node, __COUNTER__)
131 #define binode_foreach_by_key(first, node) \
132 _binode_foreach_by_key(first, node, __LINE__)
134 #define _binode_foreach_by_key(first, node, n) \
135 __binode_foreach_by_key(first, node, n)
137 #define __binode_foreach_by_key(first, node, n) \
138 for (struct binode *node = (first), \
139 *__binode_next_by_key_##n = (node) \
140 ? binode_next_by_key(node) : NULL; \
141 (node); (node) = __binode_next_by_key_##n, \
142 __binode_next_by_key_##n = (node) \
143 ? binode_next_by_key(node) : NULL)
157 #define binode_foreach_by_value(first, node) \
158 _binode_foreach_by_value(first, node, __COUNTER__)
160 #define binode_foreach_by_value(first, node) \
161 _binode_foreach_by_value(first, node, __LINE__)
163 #define _binode_foreach_by_value(first, node, n) \
164 __binode_foreach_by_value(first, node, n)
166 #define __binode_foreach_by_value(first, node, n) \
167 for (struct binode *node = (first), \
168 *__binode_next_by_value_##n = (node) \
169 ? binode_next_by_value(node) : NULL; \
170 (node); (node) = __binode_next_by_value_##n, \
171 __binode_next_by_value_##n = (node) \
172 ? binode_next_by_value(node) : NULL)
220 const struct bimap *map,
const void *
key);
239 const struct bimap *map);
248 const struct bimap *map);
257 const struct bimap *map);
266 const struct bimap *map);
273 #define bimap_foreach_by_key(map, node) \
274 binode_foreach_by_key (bimap_first_by_key(map), node)
281 #define bimap_foreach_by_value(map, node) \
282 binode_foreach_by_value (bimap_first_by_value(map), node)
398 #endif // !LELY_UTIL_BIMAP_H_
struct binode * bimap_last_by_value(const struct bimap *map)
Returns a pointer to the last (rightmost) node by value in a bidirectional map.
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
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.
struct rbnode * rbnode_next(const struct rbnode *node)
Returns a pointer to the next (in-order) node in a red-black tree with respect to node.
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
int cmp_t(const void *p1, const void *p2)
The type of a generic comparison function.
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
struct rbnode key
The node used to lookup values by key.
struct binode * bimap_find_by_value(const struct bimap *map, const void *value)
Finds a node by value in a bidirectional map.
size_t bimap_size(const struct bimap *map)
Returns the size (in number of nodes) of a bidirectional map.
void binode_init(struct binode *node, const void *key, const void *value)
Initializes a node in a bidirectional map.
A node in a bidirectional map.
struct binode * bimap_first_by_value(const struct bimap *map)
Returns a pointer to the first (leftmost) node by value in a bidirectional map.
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 nod...
struct rbtree values
The red-black tree used to store the values.
A node in a red-black tree.
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.
struct binode * bimap_first_by_key(const struct bimap *map)
Returns a pointer to the first (leftmost) node by key in a bidirectional map.
struct binode * bimap_last_by_key(const struct bimap *map)
Returns a pointer to the last (rightmost) node by key in a bidirectional map.
struct rbnode value
The node used to lookup keys by value.
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
struct binode * bimap_find_by_key(const struct bimap *map, const void *key)
Finds a node by key in a bidirectional map.
int bimap_empty(const struct bimap *map)
Returns 1 if the bidirectional map is empty, and 0 if not.
void bimap_remove(struct bimap *map, struct binode *node)
Removes a node from a bidirectional map.
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
#define structof(ptr, type, member)
Obtains the address of a structure from the address of one of its members.
const void * key
A pointer to the key for this node.
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
void bimap_insert(struct bimap *map, struct binode *node)
Inserts a node into a bidirectional map.
struct rbtree keys
The red-black tree used to store the keys.
void bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
Initializes a bidirectional map.
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.
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
struct rbnode * rbnode_prev(const struct rbnode *node)
Returns a pointer to the previous (in-order) node in a red-black tree with respect to node.