4 * This file is part of BeRTOS.
6 * Bertos is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * As a special exception, you may use this file as part of a free software
21 * library without restriction. Specifically, if other files instantiate
22 * templates or use macros or inline functions from this file, or you compile
23 * this file and link it with other files to produce an executable, this
24 * file does not by itself cause the resulting executable to be covered by
25 * the GNU General Public License. This exception does not however
26 * invalidate any other reasons why the executable file might be covered by
27 * the GNU General Public License.
29 * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
30 * Copyright 2001, 2008 Bernie Innocenti <bernie@codewiz.org>
33 * \defgroup list General purpose lists
37 * \brief General pourpose double-linked lists
39 * Lists contain nodes. You can put any custom struct into any list as long
40 * as it has a Node struct inside it. If you make the Node struct the first
41 * member of your data type, you can simply cast it to (Node *) when passing
42 * it to list functions.
44 * Lists must be initialized before use with LIST_INIT(). You can then add
45 * objects using ADDHEAD() and ADDTAIL() macros, and remove them with
46 * list_remHead() and list_remTail().
48 * You can create lists with priorities by using PriNode instead of Node as
49 * the base member struct.
50 * Use LIST_ENQUEUE() and LIST_ENQUEUE_HEAD() to insert a priority node into
53 * To iterate over a list, use the macros FOREACH_NODE() and REVERSE_FOREACH_NODE()
65 * static Foo foo1, foo2;
68 * LIST_INIT(&foo_list);
69 * ADDHEAD(&foo_list, (Node *)&foo1);
70 * INSERT_BEFORE(&foo_list, (Node *)&foo2);
71 * FOREACH_NODE(fp, &foo_list)
76 * \author Bernie Innocenti <bernie@codewiz.org>
82 #include <cfg/compiler.h> /* INLINE */
83 #include <cfg/debug.h> /* ASSERT_VALID_PTR() */
86 * This structure represents a node for bidirectional lists.
88 * Data is usually appended to nodes by making them the first
89 * field of another struture, as a poor-man's form of inheritance.
98 * Head of a doubly-linked list of \c Node structs.
100 * Lists must be initialized with LIST_INIT() prior to use.
102 * Nodes can be added and removed from either end of the list
103 * with O(1) performance. Iterating over these lists can be
104 * tricky: use the FOREACH_NODE() macro instead.
113 * Extended node for priority queues.
115 typedef struct _PriNode
123 * Template for a naked node in a list of \a T structures.
125 * To be used as data member in other structures:
130 * DECLARE_NODE_ANON(struct Foo)
135 * DECLARE_LIST_TYPE(Foo);
139 * static LIST_TYPE(Foo) foo_list;
140 * static Foo foo1, foo2;
143 * LIST_INIT(&foo_list);
144 * ADDHEAD(&foo_list, &foo1);
145 * INSERT_BEFORE(&foo_list, &foo2);
146 * FOREACH_NODE(fp, &foo_list)
152 #define DECLARE_NODE_ANON(T) \
155 /** Declare a typesafe node for structures of type \a T. */
156 #define DECLARE_NODE_TYPE(T) \
157 typedef struct T##Node { T *succ; T *pred; } T##Node
159 /** Template for a list of \a T structures. */
160 #define DECLARE_LIST_TYPE(T) \
161 DECLARE_NODE_TYPE(T); \
162 typedef struct T##List { \
167 #define NODE_TYPE(T) T##Node
168 #define LIST_TYPE(T) T##List
171 * Get a pointer to the first node in a list.
173 * If \a l is empty, result points to l->tail.
175 #define LIST_HEAD(l) ((l)->head.succ)
178 * Get a pointer to the last node in a list.
180 * If \a l is empty, result points to l->head.
182 #define LIST_TAIL(l) ((l)->tail.pred)
184 // TODO: move in compiler.h
186 #define TYPEOF_OR_VOIDPTR(type) typeof(type)
188 #define TYPEOF_OR_VOIDPTR(type) void *
192 * Iterate over all nodes in a list.
194 * This macro generates a "for" statement using the following parameters:
195 * \param n Node pointer to be used in each iteration.
196 * \param l Pointer to list.
198 #define FOREACH_NODE(n, l) \
200 (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \
201 ((Node *)(n))->succ; \
202 (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
206 * Iterate backwards over all nodes in a list.
208 * This macro generates a "for" statement using the following parameters:
209 * \param n Node pointer to be used in each iteration.
210 * \param l Pointer to list.
212 #define REVERSE_FOREACH_NODE(n, l) \
214 (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \
215 ((Node *)(n))->pred; \
216 (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \
220 * Iterate on the list safely against node removal.
222 * This macro generates a "for" statement using the following parameters:
223 * \param n Node pointer to be used in each iteration.
224 * \param p Temporal storage for the iterator.
225 * \param l Pointer to list.
227 #define FOREACH_NODE_SAFE(n, p, l) \
229 (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l), (p) = ((Node *)(n))->succ; \
230 ((Node *)(n))->succ; \
231 (n) = (p), (p) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
234 /** Initialize a list. */
235 #define LIST_INIT(l) \
237 (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \
238 (l)->head.pred = NULL; \
239 (l)->tail.succ = NULL; \
240 (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \
244 /** Make sure that a list is valid (it was initialized and is not corrupted). */
245 #define LIST_ASSERT_VALID(l) \
248 ASSERT((l)->head.succ != NULL); \
249 ASSERT((l)->head.pred == NULL); \
250 ASSERT((l)->tail.succ == NULL); \
251 ASSERT((l)->tail.pred != NULL); \
255 ASSERT(n->pred == pred); \
258 ASSERT(n == &(l)->tail); \
261 /// Checks that a node isn't part of a given list
262 #define LIST_ASSERT_NOT_CONTAINS(list,node) \
265 ASSERT_VALID_PTR(list); \
266 ASSERT_VALID_PTR(node); \
267 FOREACH_NODE(ln, list) \
268 ASSERT(ln != (Node *)(node)); \
271 #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
273 #define LIST_ASSERT_VALID(l) do {} while (0)
274 #define LIST_ASSERT_NOT_CONTAINS(list,node) do {} while (0)
275 #define INVALIDATE_NODE(n) do {} while (0)
278 /** Tell whether a list is empty. */
279 #define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
281 /** Add node to list head. */
282 #define ADDHEAD(l,n) \
284 LIST_ASSERT_NOT_CONTAINS((l),(n)); \
285 (n)->succ = (l)->head.succ; \
286 (n)->pred = (l)->head.succ->pred; \
287 (n)->succ->pred = (n); \
288 (n)->pred->succ = (n); \
291 /** Add node to list tail. */
292 #define ADDTAIL(l,n) \
294 LIST_ASSERT_NOT_CONTAINS((l),(n)); \
295 (n)->succ = &(l)->tail; \
296 (n)->pred = (l)->tail.pred; \
297 (n)->pred->succ = (n); \
298 (l)->tail.pred = (n); \
302 * Insert node \a n before node \a ln.
304 * \note You can't pass in a list header as \a ln, but
305 * it is safe to pass list-\>head of an empty list.
307 #define INSERT_BEFORE(n,ln) \
309 ASSERT_VALID_PTR(n); \
310 ASSERT_VALID_PTR(ln); \
312 (n)->pred = (ln)->pred; \
313 (ln)->pred->succ = (n); \
318 * Remove \a n from whatever list it is in.
320 * \note Removing a node that has not previously been
321 * inserted into a list invokes undefined behavior.
325 ASSERT_VALID_PTR(n); \
326 (n)->pred->succ = (n)->succ; \
327 (n)->succ->pred = (n)->pred; \
328 INVALIDATE_NODE(n); \
332 * Insert a priority node in a priority queue.
334 * The new node is inserted immediately before the first node with the same
335 * priority or appended to the tail if no such node exists.
337 #define LIST_ENQUEUE_HEAD(list, node) \
340 LIST_ASSERT_NOT_CONTAINS((list),(node)); \
341 FOREACH_NODE(ln, (list)) \
342 if (ln->pri <= (node)->pri) \
344 INSERT_BEFORE(&(node)->link, &ln->link); \
348 * Insert a priority node in a priority queue.
350 * The new node is inserted immediately before the first node with lower
351 * priority or appended to the tail if no such node exists.
353 #define LIST_ENQUEUE(list, node) \
356 LIST_ASSERT_NOT_CONTAINS((list),(node)); \
357 FOREACH_NODE(ln, (list)) \
358 if (ln->pri < (node)->pri) \
360 INSERT_BEFORE(&(node)->link, &ln->link); \
365 * Unlink a node from the head of the list \a l.
367 * \return Pointer to node, or NULL if the list was empty.
369 INLINE Node *list_remHead(List *l)
378 n = l->head.succ; /* Get first node. */
379 l->head.succ = n->succ; /* Link list head to second node. */
380 n->succ->pred = &l->head; /* Link second node to list head. */
387 * Unlink a node from the tail of the list \a l.
389 * \return Pointer to node, or NULL if the list was empty.
391 INLINE Node *list_remTail(List *l)
400 n = l->tail.pred; /* Get last node. */
401 l->tail.pred = n->pred; /* Link list tail to second last node. */
402 n->pred->succ = &l->tail; /* Link second last node to list tail. */
408 /** \} */ //defgroup list
410 #endif /* STRUCT_LIST_H */