Lely core libraries
2.3.4
|
Go to the documentation of this file.
29 #ifndef LELY_UTIL_BIMAP_H_
30 #define LELY_UTIL_BIMAP_H_
37 #ifndef LELY_UTIL_BIMAP_INLINE
38 #define LELY_UTIL_BIMAP_INLINE static inline
77 struct binode *node,
const void *key,
const void *value);
86 const struct binode *node);
97 const struct binode *node);
106 const struct binode *node);
117 const struct binode *node);
130 #define binode_foreach_by_key(first, node) \
131 _binode_foreach_by_key(first, node, __COUNTER__)
133 #define binode_foreach_by_key(first, node) \
134 _binode_foreach_by_key(first, node, __LINE__)
136 #define _binode_foreach_by_key(first, node, n) \
137 __binode_foreach_by_key(first, node, n)
139 #define __binode_foreach_by_key(first, node, n) \
140 for (struct binode *node = (first), \
141 *__binode_next_by_key_##n = (node) \
142 ? binode_next_by_key(node) : NULL; \
143 (node); (node) = __binode_next_by_key_##n, \
144 __binode_next_by_key_##n = (node) \
145 ? binode_next_by_key(node) : NULL)
159 #define binode_foreach_by_value(first, node) \
160 _binode_foreach_by_value(first, node, __COUNTER__)
162 #define binode_foreach_by_value(first, node) \
163 _binode_foreach_by_value(first, node, __LINE__)
165 #define _binode_foreach_by_value(first, node, n) \
166 __binode_foreach_by_value(first, node, n)
168 #define __binode_foreach_by_value(first, node, n) \
169 for (struct binode *node = (first), \
170 *__binode_next_by_value_##n = (node) \
171 ? binode_next_by_value(node) : NULL; \
172 (node); (node) = __binode_next_by_value_##n, \
173 __binode_next_by_value_##n = (node) \
174 ? binode_next_by_value(node) : NULL)
222 const struct bimap *map,
const void *
key);
241 const struct bimap *map);
250 const struct bimap *map);
259 const struct bimap *map);
268 const struct bimap *map);
275 #define bimap_foreach_by_key(map, node) \
276 binode_foreach_by_key (bimap_first_by_key(map), node)
283 #define bimap_foreach_by_value(map, node) \
284 binode_foreach_by_value (bimap_first_by_value(map), node)
286 LELY_UTIL_BIMAP_INLINE
void
295 LELY_UTIL_BIMAP_INLINE
struct binode *
304 LELY_UTIL_BIMAP_INLINE
struct binode *
313 LELY_UTIL_BIMAP_INLINE
struct binode *
322 LELY_UTIL_BIMAP_INLINE
struct binode *
331 LELY_UTIL_BIMAP_INLINE
void
342 LELY_UTIL_BIMAP_INLINE
int
348 LELY_UTIL_BIMAP_INLINE
size_t
356 LELY_UTIL_BIMAP_INLINE
void
366 LELY_UTIL_BIMAP_INLINE
void
376 LELY_UTIL_BIMAP_INLINE
struct binode *
386 LELY_UTIL_BIMAP_INLINE
struct binode *
396 LELY_UTIL_BIMAP_INLINE
struct binode *
405 LELY_UTIL_BIMAP_INLINE
struct binode *
414 LELY_UTIL_BIMAP_INLINE
struct binode *
423 LELY_UTIL_BIMAP_INLINE
struct binode *
436 #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.