list.h

Go to the documentation of this file.

#ifndef STRUCT_LIST_H
#define STRUCT_LIST_H

#include <cfg/compiler.h> /* INLINE */
#include <cfg/debug.h> /* ASSERT_VALID_PTR() */

typedef struct _Node
{
    struct _Node *succ;
    struct _Node *pred;
} Node;

typedef struct _List
{
    Node head;
    Node tail;
} List;

typedef struct _PriNode
{
    Node link;
    int  pri;
} PriNode;


#define DECLARE_NODE_ANON(T) \
    T *succ; T *pred;

#define DECLARE_NODE_TYPE(T) \
    typedef struct T##Node { T *succ; T *pred; } T##Node

#define DECLARE_LIST_TYPE(T) \
    DECLARE_NODE_TYPE(T); \
    typedef struct T##List { \
         T##Node head; \
         T##Node tail; \
    } T##List

#define NODE_TYPE(T) T##Node
#define LIST_TYPE(T) T##List

#define LIST_HEAD(l) ((l)->head.succ)

#define LIST_TAIL(l) ((l)->tail.pred)

// TODO: move in compiler.h
#if COMPILER_TYPEOF
    #define TYPEOF_OR_VOIDPTR(type) typeof(type)
#else
    #define TYPEOF_OR_VOIDPTR(type) void *
#endif

#define FOREACH_NODE(n, l) \
    for( \
        (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \
        ((Node *)(n))->succ; \
        (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
    )

#define REVERSE_FOREACH_NODE(n, l) \
    for( \
        (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \
        ((Node *)(n))->pred; \
        (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \
    )

#define LIST_INIT(l) \
    do { \
        (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \
        (l)->head.pred = NULL; \
        (l)->tail.succ = NULL; \
        (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \
    } while (0)

#ifdef _DEBUG

    #define LIST_ASSERT_VALID(l) \
        do { \
            Node *n, *pred; \
            ASSERT((l)->head.succ != NULL); \
            ASSERT((l)->head.pred == NULL); \
            ASSERT((l)->tail.succ == NULL); \
            ASSERT((l)->tail.pred != NULL); \
            pred = &(l)->head; \
            FOREACH_NODE(n, l) \
            { \
                ASSERT(n->pred == pred); \
                pred = n; \
            } \
            ASSERT(n == &(l)->tail); \
        } while (0)

    #define LIST_ASSERT_NOT_CONTAINS(list,node) \
        do { \
            Node *ln; \
            ASSERT_VALID_PTR(list); \
            ASSERT_VALID_PTR(node); \
            FOREACH_NODE(ln, list) \
                ASSERT(ln != (Node *)(node)); \
        } while (0)

    #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
#else
    #define LIST_ASSERT_VALID(l) do {} while (0)
    #define INVALIDATE_NODE(n) do {} while (0)
#endif

#define LIST_EMPTY(l)  ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )

#define ADDHEAD(l,n) \
    do { \
        LIST_ASSERT_NOT_CONTAINS((l),(n)); \
        (n)->succ = (l)->head.succ; \
        (n)->pred = (l)->head.succ->pred; \
        (n)->succ->pred = (n); \
        (n)->pred->succ = (n); \
    } while (0)

#define ADDTAIL(l,n) \
    do { \
        LIST_ASSERT_NOT_CONTAINS((l),(n)); \
        (n)->succ = &(l)->tail; \
        (n)->pred = (l)->tail.pred; \
        (n)->pred->succ = (n); \
        (l)->tail.pred = (n); \
    } while (0)

#define INSERT_BEFORE(n,ln) \
    do { \
        ASSERT_VALID_PTR(n); \
        ASSERT_VALID_PTR(ln); \
        (n)->succ = (ln); \
        (n)->pred = (ln)->pred; \
        (ln)->pred->succ = (n); \
        (ln)->pred = (n); \
    } while (0)

#define REMOVE(n) \
    do { \
        ASSERT_VALID_PTR(n); \
        (n)->pred->succ = (n)->succ; \
        (n)->succ->pred = (n)->pred; \
        INVALIDATE_NODE(n); \
    } while (0)

#define LIST_ENQUEUE(list, node) \
    do { \
        PriNode *ln; \
        LIST_ASSERT_NOT_CONTAINS((list),(node)); \
        FOREACH_NODE(ln, (list)) \
            if (ln->pri < (node)->pri) \
                break; \
        INSERT_BEFORE(&(node)->link, &ln->link); \
    } while (0)


INLINE Node *list_remHead(List *l)
{
    Node *n;

    ASSERT_VALID_PTR(l);

    if (LIST_EMPTY(l))
        return (Node *)0;

    n = l->head.succ; /* Get first node. */
    l->head.succ = n->succ; /* Link list head to second node. */
    n->succ->pred = &l->head; /* Link second node to list head. */

    INVALIDATE_NODE(n);
    return n;
}

INLINE Node *list_remTail(List *l)
{
    Node *n;

    ASSERT_VALID_PTR(l);

    if (LIST_EMPTY(l))
        return NULL;

    n = l->tail.pred; /* Get last node. */
    l->tail.pred = n->pred; /* Link list tail to second last node. */
    n->pred->succ = &l->tail; /* Link second last node to list tail. */

    INVALIDATE_NODE(n);
    return n;
}

#endif /* STRUCT_LIST_H */