path: root/shared/c-list/src/c-list.h

#pragma once

/*
 * Circular Intrusive Double Linked List Collection in ISO-C11
 *
 * This implements a generic circular double linked list. List entries must
 * embed the CList object, which provides pointers to the next and previous
 * element. Insertion and removal can be done in O(1) due to the double links.
 * Furthermore, the list is circular, thus allows access to front/tail in O(1)
 * as well, even if you only have a single head pointer (which is not how the
 * list is usually operated, though).
 *
 * Note that you are free to use the list implementation without a head
 * pointer. However, usual operation uses a single CList object as head, which
 * is itself linked in the list and as such must be identified as list head.
 * This allows very simply list operations and avoids a lot of special cases.
 * Most importantly, you can unlink entries without requiring a head pointer.
 */

#ifdef __cplusplus
extern "C" {
#endif

#include <stddef.h>

typedef struct CList CList;

/**
 * struct CList - Entry of a circular double linked list
 * @next:               next entry
 * @prev:               previous entry
 *
 * Each entry in a list must embed a CList object. This object contains
 * pointers to its next and previous elements, which can be freely accessed by
 * the API user at any time. Note that the list is circular, and the list head
 * is linked in the list as well.
 *
 * The list head must be initialized via C_LIST_INIT before use. There is no
 * reason to initialize entry objects before linking them. However, if you need
 * a boolean state that tells you whether the entry is linked or not, you should
 * initialize the entry via C_LIST_INIT as well.
 */
struct CList {
        CList *next;
        CList *prev;
};

#define C_LIST_INIT(_var) { .next = &(_var), .prev = &(_var) }

/**
 * c_list_init() - initialize list entry
 * @what:               list entry to initialize
 */
static inline void c_list_init(CList *what) {
        *what = (CList)C_LIST_INIT(*what);
}

/**
 * c_list_entry() - get parent container of list entry
 * @_what:              list entry, or NULL
 * @_t:                 type of parent container
 * @_m:                 member name of list entry in @_t
 *
 * If the list entry @_what is embedded into a surrounding structure, this will
 * turn the list entry pointer @_what into a pointer to the parent container
 * (using offsetof(3), or sometimes called container_of(3)).
 *
 * If @_what is NULL, this will also return NULL.
 *
 * Return: Pointer to parent container, or NULL.
 */
#define c_list_entry(_what, _t, _m) \
        ((_t *)(void *)(((unsigned long)(void *)(_what) ?: \
                         offsetof(_t, _m)) - offsetof(_t, _m)))

/**
 * c_list_is_linked() - check whether an entry is linked
 * @what:               entry to check, or NULL
 *
 * Return: True if @what is linked in a list, false if not.
 */
static inline _Bool c_list_is_linked(const CList *what) {
        return what && what->next != what;
}

/**
 * c_list_is_empty() - check whether a list is empty
 * @list:               list to check, or NULL
 *
 * This is the same as !c_list_is_linked().
 *
 * Return: True if @list is empty, false if not.
 */
static inline _Bool c_list_is_empty(const CList *list) {
        return !c_list_is_linked(list);
}

/**
 * c_list_link_before() - link entry into list
 * @where:              linked list entry used as anchor
 * @what:               entry to link
 *
 * This links @what directly in front of @where. @where can either be a list
 * head or any entry in the list.
 *
 * If @where points to the list head, this effectively links @what as new tail
 * element. Hence, the macro c_list_link_tail() is an alias to this.
 *
 * @what is not inspected prior to being linked. Hence, it better not be linked
 * into another list, or the other list will be corrupted.
 */
static inline void c_list_link_before(CList *where, CList *what) {
        CList *prev = where->prev, *next = where;

        next->prev = what;
        what->next = next;
        what->prev = prev;
        prev->next = what;
}
#define c_list_link_tail(_list, _what) c_list_link_before((_list), (_what))

/**
 * c_list_link_after() - link entry into list
 * @where:              linked list entry used as anchor
 * @what:               entry to link
 *
 * This links @what directly after @where. @where can either be a list head or
 * any entry in the list.
 *
 * If @where points to the list head, this effectively links @what as new front
 * element. Hence, the macro c_list_link_front() is an alias to this.
 *
 * @what is not inspected prior to being linked. Hence, it better not be linked
 * into another list, or the other list will be corrupted.
 */
static inline void c_list_link_after(CList *where, CList *what) {
        CList *prev = where, *next = where->next;

        next->prev = what;
        what->next = next;
        what->prev = prev;
        prev->next = what;
}
#define c_list_link_front(_list, _what) c_list_link_after((_list), (_what))

/**
 * c_list_unlink_stale() - unlink element from list
 * @what:               element to unlink
 *
 * This unlinks @what. If @what was initialized via C_LIST_INIT(), it has no
 * effect. If @what was never linked, nor initialized, behavior is undefined.
 *
 * Note that this does not modify @what. It just modifies the previous and next
 * elements in the list to no longer reference @what. If you want to make sure
 * @what is re-initialized after removal, use c_list_unlink().
 */
static inline void c_list_unlink_stale(CList *what) {
        CList *prev = what->prev, *next = what->next;

        next->prev = prev;
        prev->next = next;
}

/**
 * c_list_unlink() - unlink element from list and re-initialize
 * @what:               element to unlink
 *
 * This is like c_list_unlink_stale() but re-initializes @what after removal.
 */
static inline void c_list_unlink(CList *what) {
        /* condition is not needed, but avoids STOREs in fast-path */
        if (c_list_is_linked(what)) {
                c_list_unlink_stale(what);
                *what = (CList)C_LIST_INIT(*what);
        }
}

/**
 * c_list_swap() - exchange the contents of two lists
 * @list1:      the list to operate on
 * @list2:      the list to operate on
 *
 * This replaces the contents of the list @list1 with the contents
 * of @list2, and vice versa.
 */
static inline void c_list_swap(CList *list1, CList *list2) {
        CList t;

        /* make neighbors of list1 point to list2, and vice versa */
        t = *list1;
        t.next->prev = list2;
        t.prev->next = list2;
        t = *list2;
        t.next->prev = list1;
        t.prev->next = list1;

        /* swap list1 and list2 now that their neighbors were fixed up */
        t = *list1;
        *list1 = *list2;
        *list2 = t;
}

/**
 * c_list_splice() - splice one list into another
 * @target:     the list to splice into
 * @source:     the list to splice
 *
 * This removes all the entries from @source and splice them into @target.
 * The order of the two lists is preserved and the source is appended
 * to the end of target.
 *
 * On return, the source list will be empty.
 */
static inline void c_list_splice(CList *target, CList *source) {
        if (!c_list_is_empty(source)) {
                /* attach the front of @source to the tail of @target */
                source->next->prev = target->prev;
                target->prev->next = source->next;

                /* attach the tail of @source to the front of @target */
                source->prev->next = target;
                target->prev = source->prev;

                /* clear source */
                *source = (CList)C_LIST_INIT(*source);
        }
}

/**
 * c_list_first() - return pointer to first element, or NULL if empty
 * @list:               list to operate on, or NULL
 *
 * This returns a pointer to the first element, or NULL if empty. This never
 * returns a pointer to the list head.
 *
 * Return: Pointer to first list element, or NULL if empty.
 */
static inline CList *c_list_first(CList *list) {
        return c_list_is_empty(list) ? NULL : list->next;
}

/**
 * c_list_last() - return pointer to last element, or NULL if empty
 * @list:               list to operate on, or NULL
 *
 * This returns a pointer to the last element, or NULL if empty. This never
 * returns a pointer to the list head.
 *
 * Return: Pointer to last list element, or NULL if empty.
 */
static inline CList *c_list_last(CList *list) {
        return c_list_is_empty(list) ? NULL : list->prev;
}

/**
 * c_list_first_entry() - return pointer to first entry, or NULL if empty
 * @_list:              list to operate on, or NULL
 * @_t:                 type of list entries
 * @_m:                 name of CList member in @_t
 *
 * This is like c_list_first(), but also applies c_list_entry() on the result.
 *
 * Return: Pointer to first list entry, or NULL if empty.
 */
#define c_list_first_entry(_list, _t, _m) \
        c_list_entry(c_list_first(_list), _t, _m)

/**
 * c_list_last_entry() - return pointer to last entry, or NULL if empty
 * @_list:              list to operate on, or NULL
 * @_t:                 type of list entries
 * @_m:                 name of CList member in @_t
 *
 * This is like c_list_last(), but also applies c_list_entry() on the result.
 *
 * Return: Pointer to last list entry, or NULL if empty.
 */
#define c_list_last_entry(_list, _t, _m) \
        c_list_entry(c_list_last(_list), _t, _m)

/**
 * c_list_for_each*() - iterators
 *
 * The c_list_for_each*() macros provide simple for-loop wrappers to iterate
 * a linked list. They come in a set of flavours:
 *
 *   - "entry": This combines c_list_entry() with the loop iterator, so the
 *              iterator always has the type of the surrounding object, rather
 *              than CList.
 *
 *   - "safe": The loop iterator always keeps track of the next element to
 *             visit. This means, you can safely modify the current element,
 *             while retaining loop-integrity.
 *             You still must not touch any other entry of the list. Otherwise,
 *             the loop-iterator will be corrupted.
 *
 *   - "continue": Rather than starting the iteration at the front of the list,
 *                 use the current value of the iterator as starting position.
 *                 Note that the first loop iteration will be the following
 *                 element, not the given element.
 *
 *   - "unlink": This unlinks the current element from the list before the loop
 *               code is run. Note that this only does a partial unlink, since
 *               it assumes the entire list will be unlinked. You must not
 *               break out of the loop, or the list will be in an inconsistent
 *               state.
 */

#define c_list_for_each(_iter, _list)                                           \
        for (_iter = (_list)->next;                                             \
             (_iter) != (_list);                                                \
             _iter = (_iter)->next)

#define c_list_for_each_entry(_iter, _list, _m)                                 \
        for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m);       \
             &(_iter)->_m != (_list);                                           \
             _iter = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m))

#define c_list_for_each_safe(_iter, _safe, _list)                               \
        for (_iter = (_list)->next, _safe = (_iter)->next;                      \
             (_iter) != (_list);                                                \
             _iter = (_safe), _safe = (_safe)->next)

#define c_list_for_each_entry_safe(_iter, _safe, _list, _m)                     \
        for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m),       \
             _safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m);    \
             &(_iter)->_m != (_list);                                           \
             _iter = (_safe),                                                   \
             _safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m))    \

#define c_list_for_each_continue(_iter, _list)                                  \
        for (_iter = (_iter) ? (_iter)->next : (_list)->next;                   \
             (_iter) != (_list);                                                \
             _iter = (_iter)->next)

#define c_list_for_each_entry_continue(_iter, _list, _m)                        \
        for (_iter = c_list_entry((_iter) ? (_iter)->_m.next : (_list)->next,   \
                                  __typeof__(*_iter),                           \
                                  _m);                                          \
             &(_iter)->_m != (_list);                                           \
             _iter = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m))

#define c_list_for_each_safe_continue(_iter, _safe, _list)                      \
        for (_iter = (_iter) ? (_iter)->next : (_list)->next,                   \
             _safe = (_iter)->next;                                             \
             (_iter) != (_list);                                                \
             _iter = (_safe), _safe = (_safe)->next)

#define c_list_for_each_entry_safe_continue(_iter, _safe, _list, _m)            \
        for (_iter = c_list_entry((_iter) ? (_iter)->_m.next : (_list)->next,   \
                                  __typeof__(*_iter),                           \
                                  _m),                                          \
             _safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m);    \
             &(_iter)->_m != (_list);                                           \
             _iter = (_safe),                                                   \
             _safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m))    \

#define c_list_for_each_safe_unlink(_iter, _safe, _list)                        \
        for (_iter = (_list)->next, _safe = (_iter)->next;                      \
             ((*_iter = (CList)C_LIST_INIT(*_iter)), (_iter) != (_list));       \
             _iter = (_safe), _safe = (_safe)->next)

#define c_list_for_each_entry_safe_unlink(_iter, _safe, _list, _m)              \
        for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m),       \
             _safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m);    \
             (((_iter)->_m = (CList)C_LIST_INIT((_iter)->_m)),                  \
              &(_iter)->_m != (_list));                                         \
             _iter = (_safe),                                                   \
             _safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m))    \

/**
 * c_list_flush() - flush all entries from a list
 * @list:               list to flush
 *
 * This unlinks all entries from the given list @list and reinitializes their
 * link-nodes via C_LIST_INIT().
 *
 * Note that the entries are not modified in any other way, nor is their memory
 * released. This function just unlinks them and resets all the list nodes. It
 * is particularly useful with temporary lists on the stack in combination with
 * the GCC-extension __attribute__((__cleanup__(arg))).
 */
static inline void c_list_flush(CList *list) {
        CList *iter, *safe;

        c_list_for_each_safe_unlink(iter, safe, list)
                /* empty */ ;
}

/**
 * c_list_length() - return number of linked entries, excluding the head
 * @list:               list to operate on
 *
 * Returns the number of entries in the list, excluding the list head @list.
 * That is, for a list that is empty according to c_list_is_empty(), the
 * returned length is 0. This requires to iterate the list and has thus O(n)
 * runtime.
 *
 * Note that this function is meant for debugging purposes only. If you need
 * the list size during normal operation, you should maintain a counter
 * separately.
 *
 * Return: Number of items in @list.
 */
static inline unsigned long c_list_length(const CList *list) {
        unsigned long n = 0;
        const CList *iter;

        c_list_for_each(iter, list)
                ++n;

        return n;
}

/**
 * c_list_contains() - check whether an entry is linked in a certain list
 * @list:               list to operate on
 * @what:               entry to look for
 *
 * This checks whether @what is linked into @list. This requires a linear
 * search through the list, as such runs in O(n). Note that the list-head is
 * considered part of the list, and hence this returns true if @what equals
 * @list.
 *
 * Note that this function is meant for debugging purposes, and consistency
 * checks. You should always be aware whether your objects are linked in a
 * specific list.
 *
 * Return: True if @what is in @list, false otherwise.
 */
static inline _Bool c_list_contains(const CList *list, const CList *what) {
        const CList *iter;

        c_list_for_each(iter, list)
                if (what == iter)
                        return 1;

        return what == list;
}

#ifdef __cplusplus
}
#endif