Lely core libraries  2.3.4
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 #include <assert.h>
36 
37 #ifndef LELY_UTIL_BIMAP_INLINE
38 #define LELY_UTIL_BIMAP_INLINE static inline
39 #endif
40 
48 struct binode {
50  struct rbnode key;
52  struct rbnode value;
53 };
54 
56 struct bimap {
58  struct rbtree keys;
60  struct rbtree values;
61 };
62 
63 #ifdef __cplusplus
64 extern "C" {
65 #endif
66 
76 LELY_UTIL_BIMAP_INLINE void binode_init(
77  struct binode *node, const void *key, const void *value);
78 
85 LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_key(
86  const struct binode *node);
87 
96 LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_key(
97  const struct binode *node);
98 
105 LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_value(
106  const struct binode *node);
107 
116 LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_value(
117  const struct binode *node);
118 
129 #ifdef __COUNTER__
130 #define binode_foreach_by_key(first, node) \
131  _binode_foreach_by_key(first, node, __COUNTER__)
132 #else
133 #define binode_foreach_by_key(first, node) \
134  _binode_foreach_by_key(first, node, __LINE__)
135 #endif
136 #define _binode_foreach_by_key(first, node, n) \
137  __binode_foreach_by_key(first, node, n)
138 // clang-format off
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)
146 // clang-format on
147 
158 #ifdef __COUNTER__
159 #define binode_foreach_by_value(first, node) \
160  _binode_foreach_by_value(first, node, __COUNTER__)
161 #else
162 #define binode_foreach_by_value(first, node) \
163  _binode_foreach_by_value(first, node, __LINE__)
164 #endif
165 #define _binode_foreach_by_value(first, node, n) \
166  __binode_foreach_by_value(first, node, n)
167 // clang-format off
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)
175 // clang-format on
176 
184 LELY_UTIL_BIMAP_INLINE void bimap_init(
185  struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp);
186 
188 LELY_UTIL_BIMAP_INLINE int bimap_empty(const struct bimap *map);
189 
194 LELY_UTIL_BIMAP_INLINE size_t bimap_size(const struct bimap *map);
195 
203 LELY_UTIL_BIMAP_INLINE void bimap_insert(
204  struct bimap *map, struct binode *node);
205 
211 LELY_UTIL_BIMAP_INLINE void bimap_remove(
212  struct bimap *map, struct binode *node);
213 
221 LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_key(
222  const struct bimap *map, const void *key);
223 
231 LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_value(
232  const struct bimap *map, const void *value);
233 
240 LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_key(
241  const struct bimap *map);
242 
249 LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_key(
250  const struct bimap *map);
251 
258 LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_value(
259  const struct bimap *map);
260 
267 LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_value(
268  const struct bimap *map);
269 
275 #define bimap_foreach_by_key(map, node) \
276  binode_foreach_by_key (bimap_first_by_key(map), node)
277 
283 #define bimap_foreach_by_value(map, node) \
284  binode_foreach_by_value (bimap_first_by_value(map), node)
285 
286 LELY_UTIL_BIMAP_INLINE void
287 binode_init(struct binode *node, const void *key, const void *value)
288 {
289  assert(node);
290 
291  rbnode_init(&node->key, key);
292  rbnode_init(&node->value, value);
293 }
294 
295 LELY_UTIL_BIMAP_INLINE struct binode *
296 binode_prev_by_key(const struct binode *node)
297 {
298  assert(node);
299 
300  struct rbnode *prev = rbnode_prev(&node->key);
301  return prev ? structof(prev, struct binode, key) : NULL;
302 }
303 
304 LELY_UTIL_BIMAP_INLINE struct binode *
305 binode_next_by_key(const struct binode *node)
306 {
307  assert(node);
308 
309  struct rbnode *next = rbnode_next(&node->key);
310  return next ? structof(next, struct binode, key) : NULL;
311 }
312 
313 LELY_UTIL_BIMAP_INLINE struct binode *
314 binode_prev_by_value(const struct binode *node)
315 {
316  assert(node);
317 
318  struct rbnode *prev = rbnode_prev(&node->value);
319  return prev ? structof(prev, struct binode, value) : NULL;
320 }
321 
322 LELY_UTIL_BIMAP_INLINE struct binode *
323 binode_next_by_value(const struct binode *node)
324 {
325  assert(node);
326 
327  struct rbnode *next = rbnode_next(&node->value);
328  return next ? structof(next, struct binode, value) : NULL;
329 }
330 
331 LELY_UTIL_BIMAP_INLINE void
332 bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
333 {
334  assert(map);
335  assert(key_cmp);
336  assert(value_cmp);
337 
338  rbtree_init(&map->keys, key_cmp);
339  rbtree_init(&map->values, value_cmp);
340 }
341 
342 LELY_UTIL_BIMAP_INLINE int
343 bimap_empty(const struct bimap *map)
344 {
345  return !bimap_size(map);
346 }
347 
348 LELY_UTIL_BIMAP_INLINE size_t
349 bimap_size(const struct bimap *map)
350 {
351  assert(map);
352 
353  return rbtree_size(&map->keys);
354 }
355 
356 LELY_UTIL_BIMAP_INLINE void
357 bimap_insert(struct bimap *map, struct binode *node)
358 {
359  assert(map);
360  assert(node);
361 
362  rbtree_insert(&map->keys, &node->key);
363  rbtree_insert(&map->values, &node->value);
364 }
365 
366 LELY_UTIL_BIMAP_INLINE void
367 bimap_remove(struct bimap *map, struct binode *node)
368 {
369  assert(map);
370  assert(node);
371 
372  rbtree_remove(&map->keys, &node->key);
373  rbtree_remove(&map->values, &node->value);
374 }
375 
376 LELY_UTIL_BIMAP_INLINE struct binode *
377 bimap_find_by_key(const struct bimap *map, const void *key)
378 {
379  assert(map);
380  assert(key);
381 
382  struct rbnode *node = rbtree_find(&map->keys, key);
383  return node ? structof(node, struct binode, key) : NULL;
384 }
385 
386 LELY_UTIL_BIMAP_INLINE struct binode *
387 bimap_find_by_value(const struct bimap *map, const void *value)
388 {
389  assert(map);
390  assert(value);
391 
392  struct rbnode *node = rbtree_find(&map->values, value);
393  return node ? structof(node, struct binode, value) : NULL;
394 }
395 
396 LELY_UTIL_BIMAP_INLINE struct binode *
397 bimap_first_by_key(const struct bimap *map)
398 {
399  assert(map);
400 
401  struct rbnode *node = rbtree_first(&map->keys);
402  return node ? structof(node, struct binode, key) : NULL;
403 }
404 
405 LELY_UTIL_BIMAP_INLINE struct binode *
406 bimap_last_by_key(const struct bimap *map)
407 {
408  assert(map);
409 
410  struct rbnode *node = rbtree_last(&map->keys);
411  return node ? structof(node, struct binode, key) : NULL;
412 }
413 
414 LELY_UTIL_BIMAP_INLINE struct binode *
415 bimap_first_by_value(const struct bimap *map)
416 {
417  assert(map);
418 
419  struct rbnode *node = rbtree_first(&map->values);
420  return node ? structof(node, struct binode, value) : NULL;
421 }
422 
423 LELY_UTIL_BIMAP_INLINE struct binode *
424 bimap_last_by_value(const struct bimap *map)
425 {
426  assert(map);
427 
428  struct rbnode *node = rbtree_last(&map->values);
429  return node ? structof(node, struct binode, value) : NULL;
430 }
431 
432 #ifdef __cplusplus
433 }
434 #endif
435 
436 #endif // !LELY_UTIL_BIMAP_H_
void binode_init(struct binode *node, const void *key, const void *value)
Initializes a node in a bidirectional map.
Definition: bimap.h:287
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:406
void bimap_remove(struct bimap *map, struct binode *node)
Removes a node from a bidirectional map.
Definition: bimap.h:367
size_t bimap_size(const struct bimap *map)
Returns the size (in number of nodes) of a bidirectional map.
Definition: bimap.h:349
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:377
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:415
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:424
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:305
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:314
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:323
int bimap_empty(const struct bimap *map)
Returns 1 if the bidirectional map is empty, and 0 if not.
Definition: bimap.h:343
void bimap_insert(struct bimap *map, struct binode *node)
Inserts a node into a bidirectional map.
Definition: bimap.h:357
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:387
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:296
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:397
void bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
Initializes a bidirectional map.
Definition: bimap.h:332
This header file is part of the utilities library; it contains the comparison function definitions.
int cmp_t(const void *p1, const void *p2)
The type of a generic comparison function.
Definition: cmp.h:50
#define structof(ptr, type, member)
Obtains the address of a structure from the address of one of its members.
Definition: util.h:93
This header file is part of the utilities library; it contains the red-black tree declarations.
void rbnode_init(struct rbnode *node, const void *key)
Initializes a node in a red-black tree.
Definition: rbtree.h:237
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
void rbtree_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition: rbtree.c:108
struct rbnode * rbtree_last(const struct rbtree *tree)
Returns a pointer to the last (rightmost) node in a red-black tree.
Definition: rbtree.c:343
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
Definition: rbtree.h:248
size_t rbtree_size(const struct rbtree *tree)
Returns the size (in number of nodes) of a red-black tree.
Definition: rbtree.h:265
void rbtree_remove(struct rbtree *tree, struct rbnode *node)
Removes a node from a red-black tree.
Definition: rbtree.c:187
struct rbnode * rbtree_first(const struct rbtree *tree)
Returns a pointer to the first (leftmost) node in a red-black tree.
Definition: rbtree.c:335
struct rbnode * rbtree_find(const struct rbtree *tree, const void *key)
Finds a node in a red-black tree.
Definition: rbtree.c:306
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
A bidirectional map.
Definition: bimap.h:56
struct rbtree keys
The red-black tree used to store the keys.
Definition: bimap.h:58
struct rbtree values
The red-black tree used to store the values.
Definition: bimap.h:60
A node in a bidirectional map.
Definition: bimap.h:48
struct rbnode key
The node used to lookup values by key.
Definition: bimap.h:50
struct rbnode value
The node used to lookup keys by value.
Definition: bimap.h:52
A node in a red-black tree.
Definition: rbtree.h:53
const void * key
A pointer to the key for this node.
Definition: rbtree.h:59
A red-black tree.
Definition: rbtree.h:91