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
48struct binode {
50 struct rbnode key;
52 struct rbnode value;
53};
54
56struct bimap {
58 struct rbtree keys;
60 struct rbtree values;
61};
62
63#ifdef __cplusplus
64extern "C" {
65#endif
66
76LELY_UTIL_BIMAP_INLINE void binode_init(
77 struct binode *node, const void *key, const void *value);
78
85LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_key(
86 const struct binode *node);
87
96LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_key(
97 const struct binode *node);
98
105LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_value(
106 const struct binode *node);
107
116LELY_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
184LELY_UTIL_BIMAP_INLINE void bimap_init(
185 struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp);
186
188LELY_UTIL_BIMAP_INLINE int bimap_empty(const struct bimap *map);
189
194LELY_UTIL_BIMAP_INLINE size_t bimap_size(const struct bimap *map);
195
203LELY_UTIL_BIMAP_INLINE void bimap_insert(
204 struct bimap *map, struct binode *node);
205
211LELY_UTIL_BIMAP_INLINE void bimap_remove(
212 struct bimap *map, struct binode *node);
213
221LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_key(
222 const struct bimap *map, const void *key);
223
231LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_value(
232 const struct bimap *map, const void *value);
233
240LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_key(
241 const struct bimap *map);
242
249LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_key(
250 const struct bimap *map);
251
258LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_value(
259 const struct bimap *map);
260
267LELY_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
286LELY_UTIL_BIMAP_INLINE void
287binode_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
295LELY_UTIL_BIMAP_INLINE struct binode *
296binode_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
304LELY_UTIL_BIMAP_INLINE struct binode *
305binode_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
313LELY_UTIL_BIMAP_INLINE struct binode *
314binode_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
322LELY_UTIL_BIMAP_INLINE struct binode *
323binode_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
331LELY_UTIL_BIMAP_INLINE void
332bimap_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
342LELY_UTIL_BIMAP_INLINE int
343bimap_empty(const struct bimap *map)
344{
345 return !bimap_size(map);
346}
347
348LELY_UTIL_BIMAP_INLINE size_t
349bimap_size(const struct bimap *map)
350{
351 assert(map);
352
353 return rbtree_size(&map->keys);
354}
355
356LELY_UTIL_BIMAP_INLINE void
357bimap_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
366LELY_UTIL_BIMAP_INLINE void
367bimap_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
376LELY_UTIL_BIMAP_INLINE struct binode *
377bimap_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
386LELY_UTIL_BIMAP_INLINE struct binode *
387bimap_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
396LELY_UTIL_BIMAP_INLINE struct binode *
397bimap_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
405LELY_UTIL_BIMAP_INLINE struct binode *
406bimap_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
414LELY_UTIL_BIMAP_INLINE struct binode *
415bimap_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
423LELY_UTIL_BIMAP_INLINE struct binode *
424bimap_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 * 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_insert(struct rbtree *tree, struct rbnode *node)
Inserts a node into a red-black tree.
Definition rbtree.c:108
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 * 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 * 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
void rbtree_init(struct rbtree *tree, rbtree_cmp_t *cmp)
Initializes a red-black tree.
Definition rbtree.h:248
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
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
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