BeRTOS
|
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 | |
Node * | list_remHead (List *l) |
Unlink a node from the head of the list l. | |
Node * | list_remTail (List *l) |
Unlink a node from the tail of the list l. |
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; }
#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)
Add node to list head.
#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)
Add node to list tail.
#define DECLARE_LIST_TYPE | ( | T | ) |
#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; }
#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) \ )
Iterate over all nodes in a list.
This macro generates a "for" statement using the following parameters:
n | Node pointer to be used in each iteration. |
l | Pointer to list. |
#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)
Insert node n before node ln.
#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)
Make sure that a list is valid (it was initialized and is not corrupted).
#define LIST_EMPTY | ( | l | ) | ( (void *)((l)->head.succ) == (void *)(&(l)->tail) ) |
#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)
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.
#define LIST_ENQUEUE_HEAD | ( | 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)
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.
#define LIST_HEAD | ( | l | ) | ((l)->head.succ) |
#define LIST_INIT | ( | l | ) |
#define LIST_TAIL | ( | l | ) | ((l)->tail.pred) |
#define REMOVE | ( | n | ) |
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.
#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) \ )
Iterate backwards over all nodes in a list.
This macro generates a "for" statement using the following parameters:
n | Node pointer to be used in each iteration. |
l | Pointer to list. |