dllist.h

Go to the documentation of this file.

 
#ifndef LELY_UTIL_DLLIST_H_
#define LELY_UTIL_DLLIST_H_
 
#include <lely/features.h>
 
#include <stddef.h>
 
#ifndef LELY_UTIL_DLLIST_INLINE
#define LELY_UTIL_DLLIST_INLINE static inline
#endif
 
struct dlnode {
        struct dlnode *prev;
        struct dlnode *next;
};
 
#define DLNODE_INIT \
        { \
                NULL, NULL \
        }
 
struct dllist {
        struct dlnode *first;
        struct dlnode *last;
};
 
#define DLLIST_INIT \
        { \
                NULL, NULL \
        }
 
#ifdef __cplusplus
extern "C" {
#endif
 
LELY_UTIL_DLLIST_INLINE void dlnode_init(struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE int dlnode_insert_after(
                struct dlnode *prev, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE int dlnode_insert_before(
                struct dlnode *next, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE void dlnode_remove(struct dlnode *node);
 
#ifdef __COUNTER__
#define dlnode_foreach(first, node) dlnode_foreach_(__COUNTER__, first, node)
#else
#define dlnode_foreach(first, node) dlnode_foreach_(__LINE__, first, node)
#endif
#define dlnode_foreach_(n, first, node) dlnode_foreach__(n, first, node)
// clang-format off
#define dlnode_foreach__(n, first, node) \
        for (struct dlnode *node = (first), \
                        *_dlnode_next_##n = (node) ? (node)->next : NULL; \
                        (node); (node) = _dlnode_next_##n, \
                        _dlnode_next_##n = (node) ? (node)->next : NULL)
// clang-format on
 
LELY_UTIL_DLLIST_INLINE void dllist_init(struct dllist *list);
 
LELY_UTIL_DLLIST_INLINE int dllist_empty(const struct dllist *list);
 
LELY_UTIL_DLLIST_INLINE size_t dllist_size(const struct dllist *list);
 
LELY_UTIL_DLLIST_INLINE void dllist_push_front(
                struct dllist *list, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE void dllist_push_back(
                struct dllist *list, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_front(struct dllist *list);
 
LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_back(struct dllist *list);
 
LELY_UTIL_DLLIST_INLINE void dllist_insert_after(
                struct dllist *list, struct dlnode *prev, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE void dllist_insert_before(
                struct dllist *list, struct dlnode *next, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE void dllist_remove(
                struct dllist *list, struct dlnode *node);
 
LELY_UTIL_DLLIST_INLINE struct dllist *dllist_append(
                struct dllist *dst, struct dllist *src);
 
LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_first(const struct dllist *list);
 
LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_last(const struct dllist *list);
 
#define dllist_foreach(list, node) dlnode_foreach (dllist_first(list), node)
 
inline void
dlnode_init(struct dlnode *node)
{
        node->prev = NULL;
        node->next = NULL;
}
 
inline int
dlnode_insert_after(struct dlnode *prev, struct dlnode *node)
{
        node->prev = prev;
        if ((node->next = prev->next) != NULL)
                node->next->prev = node;
        prev->next = node;
        return !node->next;
}
 
inline int
dlnode_insert_before(struct dlnode *next, struct dlnode *node)
{
        node->next = next;
        if ((node->prev = next->prev) != NULL)
                node->prev->next = node;
        next->prev = node;
        return !node->prev;
}
 
inline void
dlnode_remove(struct dlnode *node)
{
        if (node->prev)
                node->prev->next = node->next;
        if (node->next)
                node->next->prev = node->prev;
}
 
inline void
dllist_init(struct dllist *list)
{
        list->first = NULL;
        list->last = NULL;
}
 
inline int
dllist_empty(const struct dllist *list)
{
        return !list->first;
}
 
inline size_t
dllist_size(const struct dllist *list)
{
        size_t size = 0;
        dllist_foreach (list, node)
                size++;
        return size;
}
 
inline void
dllist_push_front(struct dllist *list, struct dlnode *node)
{
        node->prev = NULL;
        if ((node->next = list->first))
                node->next->prev = node;
        else
                list->last = node;
        list->first = node;
}
 
inline void
dllist_push_back(struct dllist *list, struct dlnode *node)
{
        node->next = NULL;
        if ((node->prev = list->last))
                node->prev->next = node;
        else
                list->first = node;
        list->last = node;
}
 
inline struct dlnode *
dllist_pop_front(struct dllist *list)
{
        struct dlnode *node = list->first;
        if (list->first) {
                if ((list->first = list->first->next))
                        list->first->prev = NULL;
                else
                        list->last = NULL;
        }
        return node;
}
 
inline struct dlnode *
dllist_pop_back(struct dllist *list)
{
        struct dlnode *node = list->last;
        if (list->last) {
                if ((list->last = list->last->prev))
                        list->last->next = NULL;
                else
                        list->first = NULL;
        }
        return node;
}
 
inline void
dllist_insert_after(
                struct dllist *list, struct dlnode *prev, struct dlnode *node)
{
        if (dlnode_insert_after(prev, node))
                list->last = node;
}
 
inline void
dllist_insert_before(
                struct dllist *list, struct dlnode *next, struct dlnode *node)
{
        if (dlnode_insert_before(next, node))
                list->first = node;
}
 
inline void
dllist_remove(struct dllist *list, struct dlnode *node)
{
        if (!node->prev)
                list->first = node->next;
        if (!node->next)
                list->last = node->prev;
        dlnode_remove(node);
}
 
inline struct dllist *
dllist_append(struct dllist *dst, struct dllist *src)
{
        if (src->first) {
                if (dst->first) {
                        src->first->prev = dst->last;
                        dst->last->next = src->first;
                        dst->last = src->last;
                } else {
                        dst->first = src->first;
                        dst->last = src->last;
                }
                dllist_init(src);
        }
        return dst;
}
 
inline struct dlnode *
dllist_first(const struct dllist *list)
{
        return list->first;
}
 
inline struct dlnode *
dllist_last(const struct dllist *list)
{
        return list->last;
}
 
#ifdef __cplusplus
}
#endif
 
#endif // !LELY_UTIL_DLLIST_H_