BeRTOS
Data Structures | Defines | Functions
General purpose lists
Embedded optimized general purpose data types

General pourpose double-linked lists. More...

Data Structures

struct  Node
 This structure represents a node for bidirectional lists. More...
struct  List
 Head of a doubly-linked list of Node structs. More...
struct  PriNode
 Extended node for priority queues. More...

Defines

#define DECLARE_NODE_ANON(T)   T *succ; T *pred;
 Template for a naked node in a list of T structures.
#define DECLARE_NODE_TYPE(T)   typedef struct T##Node { T *succ; T *pred; } T##Node
 Declare a typesafe node for structures of type T.
#define DECLARE_LIST_TYPE(T)
 Template for a list of T structures.
#define LIST_HEAD(l)   ((l)->head.succ)
 Get a pointer to the first node in a list.
#define LIST_TAIL(l)   ((l)->tail.pred)
 Get a pointer to the last node in a list.
#define FOREACH_NODE(n, l)
 Iterate over all nodes in a list.
#define REVERSE_FOREACH_NODE(n, l)
 Iterate backwards over all nodes in a list.
#define LIST_INIT(l)
 Initialize a list.
#define LIST_ASSERT_VALID(l)
 Make sure that a list is valid (it was initialized and is not corrupted).
#define LIST_ASSERT_NOT_CONTAINS(list, node)
 Checks that a node isn't part of a given list.
#define LIST_EMPTY(l)   ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
 Tell whether a list is empty.
#define ADDHEAD(l, n)
 Add node to list head.
#define ADDTAIL(l, n)
 Add node to list tail.
#define INSERT_BEFORE(n, ln)
 Insert node n before node ln.
#define REMOVE(n)
 Remove n from whatever list it is in.
#define LIST_ENQUEUE_HEAD(list, node)
 Insert a priority node in a priority queue.
#define LIST_ENQUEUE(list, node)
 Insert a priority node in a priority queue.

Functions

Nodelist_remHead (List *l)
 Unlink a node from the head of the list l.
Nodelist_remTail (List *l)
 Unlink a node from the tail of the list l.

Detailed Description

General pourpose double-linked lists.

Lists contain nodes. You can put any custom struct into any list as long as it has a Node struct inside it. If you make the Node struct the first member of your data type, you can simply cast it to (Node *) when passing it to list functions.

Lists must be initialized before use with LIST_INIT(). You can then add objects using ADDHEAD() and ADDTAIL() macros, and remove them with list_remHead() and list_remTail().

You can create lists with priorities by using PriNode instead of Node as the base member struct. Use LIST_ENQUEUE() and LIST_ENQUEUE_HEAD() to insert a priority node into a list.

To iterate over a list, use the macros FOREACH_NODE() and REVERSE_FOREACH_NODE() in this way:

 struct Foo
 {
     Node n;
     int a;
 }

 int main()
 {
        List foo_list;
        static Foo foo1, foo2;
        Foo *fp;

        LIST_INIT(&foo_list);
        ADDHEAD(&foo_list, (Node *)&foo1);
        INSERT_BEFORE(&foo_list, (Node *)&foo2);
        FOREACH_NODE(fp, &foo_list)
            fp->a = 10;
 }
Author:
Bernie Innocenti <bernie@codewiz.org>

Define Documentation

#define ADDHEAD (   l,
 
)
Value:
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)

Add node to list head.

Definition at line 267 of file list.h.

#define ADDTAIL (   l,
 
)
Value:
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)

Add node to list tail.

Definition at line 277 of file list.h.

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

Template for a list of T structures.

Definition at line 160 of file list.h.

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

Template for a naked node in a list of T structures.

To be used as data member in other structures:

    struct Foo
    {
        DECLARE_NODE_ANON(struct Foo)
        int a;
        float b;
    }

    DECLARE_LIST_TYPE(Foo);

    void foo(void)
    {
        static LIST_TYPE(Foo) foo_list;
        static Foo foo1, foo2;
        Foo *fp;

        LIST_INIT(&foo_list);
        ADDHEAD(&foo_list, &foo1);
        INSERT_BEFORE(&foo_list, &foo2);
        FOREACH_NODE(fp, &foo_list)
            fp->a = 10;
    }

Definition at line 152 of file list.h.

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

Declare a typesafe node for structures of type T.

Definition at line 156 of file list.h.

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

Iterate over all nodes in a list.

This macro generates a "for" statement using the following parameters:

Parameters:
nNode pointer to be used in each iteration.
lPointer to list.

Definition at line 198 of file list.h.

#define INSERT_BEFORE (   n,
  ln 
)
Value:
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)

Insert node n before node ln.

Note:
You can't pass in a list header as ln, but it is safe to pass list->head of an empty list.

Definition at line 292 of file list.h.

#define LIST_ASSERT_VALID (   l)
Value:
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)

Make sure that a list is valid (it was initialized and is not corrupted).

Definition at line 230 of file list.h.

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

Tell whether a list is empty.

Definition at line 264 of file list.h.

#define LIST_ENQUEUE (   list,
  node 
)
Value:
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)

Insert a priority node in a priority queue.

The new node is inserted immediately before the first node with lower priority or appended to the tail if no such node exists.

Definition at line 338 of file list.h.

#define LIST_ENQUEUE_HEAD (   list,
  node 
)
Value:
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)

Insert a priority node in a priority queue.

The new node is inserted immediately before the first node with the same priority or appended to the tail if no such node exists.

Definition at line 322 of file list.h.

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

Get a pointer to the first node in a list.

If l is empty, result points to l->tail.

Definition at line 175 of file list.h.

#define LIST_INIT (   l)
Value:
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)

Initialize a list.

Definition at line 220 of file list.h.

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

Get a pointer to the last node in a list.

If l is empty, result points to l->head.

Definition at line 182 of file list.h.

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

Remove n from whatever list it is in.

Note:
Removing a node that has not previously been inserted into a list invokes undefined behavior.

Definition at line 308 of file list.h.

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

Iterate backwards over all nodes in a list.

This macro generates a "for" statement using the following parameters:

Parameters:
nNode pointer to be used in each iteration.
lPointer to list.

Definition at line 212 of file list.h.


Function Documentation

Node* list_remHead ( List l) [inline]

Unlink a node from the head of the list l.

Returns:
Pointer to node, or NULL if the list was empty.

Definition at line 354 of file list.h.

Node* list_remTail ( List l) [inline]

Unlink a node from the tail of the list l.

Returns:
Pointer to node, or NULL if the list was empty.

Definition at line 376 of file list.h.