Lely core libraries  2.2.5
bimap.h
Go to the documentation of this file.
1 
29 #ifndef LELY_UTIL_BIMAP_H_
30 #define LELY_UTIL_BIMAP_H_
31 
32 #include <lely/util/cmp.h>
33 #include <lely/util/rbtree.h>
34 
35 #ifndef LELY_UTIL_BIMAP_INLINE
36 #define LELY_UTIL_BIMAP_INLINE static inline
37 #endif
38 
46 struct binode {
48  struct rbnode key;
50  struct rbnode value;
51 };
52 
54 struct bimap {
56  struct rbtree keys;
58  struct rbtree values;
59 };
60 
61 #ifdef __cplusplus
62 extern "C" {
63 #endif
64 
74 LELY_UTIL_BIMAP_INLINE void binode_init(
75  struct binode *node, const void *key, const void *value);
76 
83 LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_key(
84  const struct binode *node);
85 
94 LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_key(
95  const struct binode *node);
96 
103 LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_value(
104  const struct binode *node);
105 
114 LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_value(
115  const struct binode *node);
116 
127 #ifdef __COUNTER__
128 #define binode_foreach_by_key(first, node) \
129  _binode_foreach_by_key(first, node, __COUNTER__)
130 #else
131 #define binode_foreach_by_key(first, node) \
132  _binode_foreach_by_key(first, node, __LINE__)
133 #endif
134 #define _binode_foreach_by_key(first, node, n) \
135  __binode_foreach_by_key(first, node, n)
136 // clang-format off
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)
144 // clang-format on
145 
156 #ifdef __COUNTER__
157 #define binode_foreach_by_value(first, node) \
158  _binode_foreach_by_value(first, node, __COUNTER__)
159 #else
160 #define binode_foreach_by_value(first, node) \
161  _binode_foreach_by_value(first, node, __LINE__)
162 #endif
163 #define _binode_foreach_by_value(first, node, n) \
164  __binode_foreach_by_value(first, node, n)
165 // clang-format off
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)
173 // clang-format on
174 
182 LELY_UTIL_BIMAP_INLINE void bimap_init(
183  struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp);
184 
186 LELY_UTIL_BIMAP_INLINE int bimap_empty(const struct bimap *map);
187 
192 LELY_UTIL_BIMAP_INLINE size_t bimap_size(const struct bimap *map);
193 
201 LELY_UTIL_BIMAP_INLINE void bimap_insert(
202  struct bimap *map, struct binode *node);
203 
209 LELY_UTIL_BIMAP_INLINE void bimap_remove(
210  struct bimap *map, struct binode *node);
211 
219 LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_key(
220  const struct bimap *map, const void *key);
221 
229 LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_value(
230  const struct bimap *map, const void *value);
231 
238 LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_key(
239  const struct bimap *map);
240 
247 LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_key(
248  const struct bimap *map);
249 
256 LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_value(
257  const struct bimap *map);
258 
265 LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_value(
266  const struct bimap *map);
267 
273 #define bimap_foreach_by_key(map, node) \
274  binode_foreach_by_key (bimap_first_by_key(map), node)
275 
281 #define bimap_foreach_by_value(map, node) \
282  binode_foreach_by_value (bimap_first_by_value(map), node)
283 
284 inline void
285 binode_init(struct binode *node, const void *key, const void *value)
286 {
287  rbnode_init(&node->key, key);
288  rbnode_init(&node->value, value);
289 }
290 
291 inline struct binode *
292 binode_prev_by_key(const struct binode *node)
293 {
294  struct rbnode *prev = rbnode_prev(&node->key);
295  return prev ? structof(prev, struct binode, key) : NULL;
296 }
297 
298 inline struct binode *
299 binode_next_by_key(const struct binode *node)
300 {
301  struct rbnode *next = rbnode_next(&node->key);
302  return next ? structof(next, struct binode, key) : NULL;
303 }
304 
305 inline struct binode *
306 binode_prev_by_value(const struct binode *node)
307 {
308  struct rbnode *prev = rbnode_prev(&node->value);
309  return prev ? structof(prev, struct binode, value) : NULL;
310 }
311 
312 inline struct binode *
313 binode_next_by_value(const struct binode *node)
314 {
315  struct rbnode *next = rbnode_next(&node->value);
316  return next ? structof(next, struct binode, value) : NULL;
317 }
318 
319 inline void
320 bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
321 {
322  rbtree_init(&map->keys, key_cmp);
323  rbtree_init(&map->values, value_cmp);
324 }
325 
326 inline int
327 bimap_empty(const struct bimap *map)
328 {
329  return !bimap_size(map);
330 }
331 
332 inline size_t
333 bimap_size(const struct bimap *map)
334 {
335  return rbtree_size(&map->keys);
336 }
337 
338 inline void
339 bimap_insert(struct bimap *map, struct binode *node)
340 {
341  rbtree_insert(&map->keys, &node->key);
342  rbtree_insert(&map->values, &node->value);
343 }
344 
345 inline void
346 bimap_remove(struct bimap *map, struct binode *node)
347 {
348  rbtree_remove(&map->keys, &node->key);
349  rbtree_remove(&map->values, &node->value);
350 }
351 
352 inline struct binode *
353 bimap_find_by_key(const struct bimap *map, const void *key)
354 {
355  struct rbnode *node = rbtree_find(&map->keys, key);
356  return node ? structof(node, struct binode, key) : NULL;
357 }
358 
359 inline struct binode *
360 bimap_find_by_value(const struct bimap *map, const void *value)
361 {
362  struct rbnode *node = rbtree_find(&map->values, value);
363  return node ? structof(node, struct binode, value) : NULL;
364 }
365 
366 inline struct binode *
367 bimap_first_by_key(const struct bimap *map)
368 {
369  struct rbnode *node = rbtree_first(&map->keys);
370  return node ? structof(node, struct binode, key) : NULL;
371 }
372 
373 inline struct binode *
374 bimap_last_by_key(const struct bimap *map)
375 {
376  struct rbnode *node = rbtree_last(&map->keys);
377  return node ? structof(node, struct binode, key) : NULL;
378 }
379 
380 inline struct binode *
381 bimap_first_by_value(const struct bimap *map)
382 {
383  struct rbnode *node = rbtree_first(&map->values);
384  return node ? structof(node, struct binode, value) : NULL;
385 }
386 
387 inline struct binode *
388 bimap_last_by_value(const struct bimap *map)
389 {
390  struct rbnode *node = rbtree_last(&map->values);
391  return node ? structof(node, struct binode, value) : NULL;
392 }
393 
394 #ifdef __cplusplus
395 }
396 #endif
397 
398 #endif // !LELY_UTIL_BIMAP_H_
bimap_last_by_value
struct binode * bimap_last_by_value(const struct bimap *map)
Returns a pointer to the last (rightmost) node by value in a bidirectional map.
Definition: bimap.h:388
rbtree_insert
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
binode_next_by_value
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.
Definition: bimap.h:313
rbnode_next
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.
Definition: rbtree.c:91
rbtree
A red-black tree.
Definition: rbtree.h:90
bimap
A bidirectional map.
Definition: bimap.h:54
cmp.h
rbtree_first
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
Definition: rbtree.c:322
rbtree_find
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
Definition: rbtree.c:306
cmp_t
int cmp_t(const void *p1, const void *p2)
The type of a generic comparison function.
Definition: cmp.h:50
rbtree_last
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
Definition: rbtree.c:330
binode::key
struct rbnode key
The node used to lookup values by key.
Definition: bimap.h:48
bimap_find_by_value
struct binode * bimap_find_by_value(const struct bimap *map, const void *value)
Finds a node by value in a bidirectional map.
Definition: bimap.h:360
bimap_size
size_t bimap_size(const struct bimap *map)
Returns the size (in number of nodes) of a bidirectional map.
Definition: bimap.h:333
binode_init
void binode_init(struct binode *node, const void *key, const void *value)
Initializes a node in a bidirectional map.
Definition: bimap.h:285
binode
A node in a bidirectional map.
Definition: bimap.h:46
rbtree.h
bimap_first_by_value
struct binode * bimap_first_by_value(const struct bimap *map)
Returns a pointer to the first (leftmost) node by value in a bidirectional map.
Definition: bimap.h:381
binode_prev_by_value
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...
Definition: bimap.h:306
bimap::values
struct rbtree values
The red-black tree used to store the values.
Definition: bimap.h:58
rbnode
A node in a red-black tree.
Definition: rbtree.h:52
binode_next_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.
Definition: bimap.h:299
bimap_first_by_key
struct binode * bimap_first_by_key(const struct bimap *map)
Returns a pointer to the first (leftmost) node by key in a bidirectional map.
Definition: bimap.h:367
bimap_last_by_key
struct binode * bimap_last_by_key(const struct bimap *map)
Returns a pointer to the last (rightmost) node by key in a bidirectional map.
Definition: bimap.h:374
binode::value
struct rbnode value
The node used to lookup keys by value.
Definition: bimap.h:50
rbtree_init
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
Definition: rbtree.h:238
bimap_find_by_key
struct binode * bimap_find_by_key(const struct bimap *map, const void *key)
Finds a node by key in a bidirectional map.
Definition: bimap.h:353
bimap_empty
int bimap_empty(const struct bimap *map)
Returns 1 if the bidirectional map is empty, and 0 if not.
Definition: bimap.h:327
bimap_remove
void bimap_remove(struct bimap *map, struct binode *node)
Removes a node from a bidirectional map.
Definition: bimap.h:346
rbtree_remove
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
Definition: rbtree.c:187
structof
#define structof(ptr, type, member)
Obtains the address of a structure from the address of one of its members.
Definition: util.h:93
rbnode::key
const void * key
A pointer to the key for this node.
Definition: rbtree.h:58
rbtree_size
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
Definition: rbtree.h:252
bimap_insert
void bimap_insert(struct bimap *map, struct binode *node)
Inserts a node into a bidirectional map.
Definition: bimap.h:339
bimap::keys
struct rbtree keys
The red-black tree used to store the keys.
Definition: bimap.h:56
bimap_init
void bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
Initializes a bidirectional map.
Definition: bimap.h:320
binode_prev_by_key
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.
Definition: bimap.h:292
rbnode_init
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
Definition: rbtree.h:229
rbnode_prev
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.
Definition: rbtree.c:74