list.h File Reference
General pourpose double-linked lists. More...
#include <cfg/compiler.h>
#include <cfg/debug.h>
Go to the source code of this file.
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(list, node) |
| Insert a priority node in a priority queue. | |
Typedefs | |
| typedef struct _Node | Node |
| This structure represents a node for bidirectional lists. | |
| typedef struct _List | List |
Head of a doubly-linked list of Node structs. | |
| typedef struct _PriNode | PriNode |
| Extended node for priority queues. | |
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. | |
Detailed Description
General pourpose double-linked lists.
- Version:
- Id
- list.h 2751 2009-07-08 13:13:35Z lottaviano
Definition in file list.h.
Define Documentation
| #define ADDHEAD | ( | l, | |||
| n | ) |
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)
| #define ADDTAIL | ( | l, | |||
| n | ) |
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)
| #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 | ) |
Value:
for( \ (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \ ((Node *)(n))->succ; \ (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \ )
This macro generates a "for" statement using the following parameters:
- Parameters:
-
n Node pointer to be used in each iteration. l Pointer to list.
| #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)
- Note:
- You can't pass in a list header as ln, but it is safe to pass list->head of an empty list.
| #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)
| #define LIST_EMPTY | ( | l | ) | ( (void *)((l)->head.succ) == (void *)(&(l)->tail) ) |
| #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)
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_HEAD | ( | l | ) | ((l)->head.succ) |
| #define LIST_INIT | ( | l | ) |
| #define LIST_TAIL | ( | l | ) | ((l)->tail.pred) |
| #define REMOVE | ( | n | ) |
Value:
do { \ ASSERT_VALID_PTR(n); \ (n)->pred->succ = (n)->succ; \ (n)->succ->pred = (n)->pred; \ INVALIDATE_NODE(n); \ } while (0)
- Note:
- Removing a node that has not previously been inserted into a list invokes undefined behavior.
| #define REVERSE_FOREACH_NODE | ( | n, | |||
| l | ) |
Value:
for( \ (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \ ((Node *)(n))->pred; \ (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \ )
This macro generates a "for" statement using the following parameters:
- Parameters:
-
n Node pointer to be used in each iteration. l Pointer to list.
Typedef Documentation
Head of a doubly-linked list of Node structs.
Lists must be initialized with LIST_INIT() prior to use.
Nodes can be added and removed from either end of the list with O(1) performance. Iterating over these lists can be tricky: use the FOREACH_NODE() macro instead.
This structure represents a node for bidirectional lists.
Data is usually appended to nodes by making them the first field of another struture, as a poor-man's form of inheritance.
Function Documentation
Join us on Facebook —
Follow us on Twitter
