bimap.h

Go to the documentation of this file.

 
#ifndef LELY_UTIL_BIMAP_H_
#define LELY_UTIL_BIMAP_H_
 
#include <lely/util/cmp.h>
#include <lely/util/rbtree.h>
 
#ifndef LELY_UTIL_BIMAP_INLINE
#define LELY_UTIL_BIMAP_INLINE static inline
#endif
 
struct binode {
        struct rbnode key;
        struct rbnode value;
};
 
struct bimap {
        struct rbtree keys;
        struct rbtree values;
};
 
#ifdef __cplusplus
extern "C" {
#endif
 
LELY_UTIL_BIMAP_INLINE void binode_init(
                struct binode *node, const void *key, const void *value);
 
LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_key(
                const struct binode *node);
 
LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_key(
                const struct binode *node);
 
LELY_UTIL_BIMAP_INLINE struct binode *binode_prev_by_value(
                const struct binode *node);
 
LELY_UTIL_BIMAP_INLINE struct binode *binode_next_by_value(
                const struct binode *node);
 
#ifdef __COUNTER__
#define binode_foreach_by_key(first, node) \
        _binode_foreach_by_key(first, node, __COUNTER__)
#else
#define binode_foreach_by_key(first, node) \
        _binode_foreach_by_key(first, node, __LINE__)
#endif
#define _binode_foreach_by_key(first, node, n) \
        __binode_foreach_by_key(first, node, n)
// clang-format off
#define __binode_foreach_by_key(first, node, n) \
        for (struct binode *node = (first), \
                        *__binode_next_by_key_##n = (node) \
                        ? binode_next_by_key(node) : NULL; \
                        (node); (node) = __binode_next_by_key_##n, \
                        __binode_next_by_key_##n = (node) \
                        ? binode_next_by_key(node) : NULL)
// clang-format on
 
#ifdef __COUNTER__
#define binode_foreach_by_value(first, node) \
        _binode_foreach_by_value(first, node, __COUNTER__)
#else
#define binode_foreach_by_value(first, node) \
        _binode_foreach_by_value(first, node, __LINE__)
#endif
#define _binode_foreach_by_value(first, node, n) \
        __binode_foreach_by_value(first, node, n)
// clang-format off
#define __binode_foreach_by_value(first, node, n) \
        for (struct binode *node = (first), \
                        *__binode_next_by_value_##n = (node) \
                        ? binode_next_by_value(node) : NULL; \
                        (node); (node) = __binode_next_by_value_##n, \
                        __binode_next_by_value_##n = (node) \
                        ? binode_next_by_value(node) : NULL)
// clang-format on
 
LELY_UTIL_BIMAP_INLINE void bimap_init(
                struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp);
 
LELY_UTIL_BIMAP_INLINE int bimap_empty(const struct bimap *map);
 
LELY_UTIL_BIMAP_INLINE size_t bimap_size(const struct bimap *map);
 
LELY_UTIL_BIMAP_INLINE void bimap_insert(
                struct bimap *map, struct binode *node);
 
LELY_UTIL_BIMAP_INLINE void bimap_remove(
                struct bimap *map, struct binode *node);
 
LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_key(
                const struct bimap *map, const void *key);
 
LELY_UTIL_BIMAP_INLINE struct binode *bimap_find_by_value(
                const struct bimap *map, const void *value);
 
LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_key(
                const struct bimap *map);
 
LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_key(
                const struct bimap *map);
 
LELY_UTIL_BIMAP_INLINE struct binode *bimap_first_by_value(
                const struct bimap *map);
 
LELY_UTIL_BIMAP_INLINE struct binode *bimap_last_by_value(
                const struct bimap *map);
 
#define bimap_foreach_by_key(map, node) \
        binode_foreach_by_key (bimap_first_by_key(map), node)
 
#define bimap_foreach_by_value(map, node) \
        binode_foreach_by_value (bimap_first_by_value(map), node)
 
inline void
binode_init(struct binode *node, const void *key, const void *value)
{
        rbnode_init(&node->key, key);
        rbnode_init(&node->value, value);
}
 
inline struct binode *
binode_prev_by_key(const struct binode *node)
{
        struct rbnode *prev = rbnode_prev(&node->key);
        return prev ? structof(prev, struct binode, key) : NULL;
}
 
inline struct binode *
binode_next_by_key(const struct binode *node)
{
        struct rbnode *next = rbnode_next(&node->key);
        return next ? structof(next, struct binode, key) : NULL;
}
 
inline struct binode *
binode_prev_by_value(const struct binode *node)
{
        struct rbnode *prev = rbnode_prev(&node->value);
        return prev ? structof(prev, struct binode, value) : NULL;
}
 
inline struct binode *
binode_next_by_value(const struct binode *node)
{
        struct rbnode *next = rbnode_next(&node->value);
        return next ? structof(next, struct binode, value) : NULL;
}
 
inline void
bimap_init(struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
{
        rbtree_init(&map->keys, key_cmp);
        rbtree_init(&map->values, value_cmp);
}
 
inline int
bimap_empty(const struct bimap *map)
{
        return !bimap_size(map);
}
 
inline size_t
bimap_size(const struct bimap *map)
{
        return rbtree_size(&map->keys);
}
 
inline void
bimap_insert(struct bimap *map, struct binode *node)
{
        rbtree_insert(&map->keys, &node->key);
        rbtree_insert(&map->values, &node->value);
}
 
inline void
bimap_remove(struct bimap *map, struct binode *node)
{
        rbtree_remove(&map->keys, &node->key);
        rbtree_remove(&map->values, &node->value);
}
 
inline struct binode *
bimap_find_by_key(const struct bimap *map, const void *key)
{
        struct rbnode *node = rbtree_find(&map->keys, key);
        return node ? structof(node, struct binode, key) : NULL;
}
 
inline struct binode *
bimap_find_by_value(const struct bimap *map, const void *value)
{
        struct rbnode *node = rbtree_find(&map->values, value);
        return node ? structof(node, struct binode, value) : NULL;
}
 
inline struct binode *
bimap_first_by_key(const struct bimap *map)
{
        struct rbnode *node = rbtree_first(&map->keys);
        return node ? structof(node, struct binode, key) : NULL;
}
 
inline struct binode *
bimap_last_by_key(const struct bimap *map)
{
        struct rbnode *node = rbtree_last(&map->keys);
        return node ? structof(node, struct binode, key) : NULL;
}
 
inline struct binode *
bimap_first_by_value(const struct bimap *map)
{
        struct rbnode *node = rbtree_first(&map->values);
        return node ? structof(node, struct binode, value) : NULL;
}
 
inline struct binode *
bimap_last_by_value(const struct bimap *map)
{
        struct rbnode *node = rbtree_last(&map->values);
        return node ? structof(node, struct binode, value) : NULL;
}
 
#ifdef __cplusplus
}
#endif
 
#endif // !LELY_UTIL_BIMAP_H_