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);
230 const struct bimap *map,
const void *value);
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_ void bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
Initializes a bidirectional map.
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...
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
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.
This header file is part of the utilities library; it contains the comparison function definitions...
struct binode * bimap_first_by_value(const struct bimap *map)
Returns a pointer to the first (leftmost) node by value in a bidirectional map.
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
struct rbnode key
The node used to lookup values by key.
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 * 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...
This header file is part of the utilities library; it contains the red-black tree declarations...
int cmp_t(const void *p1, const void *p2)
The type of a generic comparison function.
A node in a bidirectional map.
void bimap_insert(struct bimap *map, struct binode *node)
Inserts a node into a bidirectional map.
struct binode * bimap_find_by_value(const struct bimap *map, const void *value)
Finds a node by value in a bidirectional map.
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in 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.
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
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 binode * bimap_last_by_key(const struct bimap *map)
Returns a pointer to the last (rightmost) node by key in a bidirectional map.
struct binode * bimap_last_by_value(const struct bimap *map)
Returns a pointer to the last (rightmost) node by value in a bidirectional map.
#define structof(ptr, type, member)
Obtains the address of a structure from the address of one of its members.
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 * 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...
struct rbtree keys
The red-black tree used to store the keys.
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 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...
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
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.
struct rbtree values
The red-black tree used to store the values.
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
A node in a red-black tree.