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) \
219 /** Initialize a list. */
220 #define LIST_INIT(l) \
222 (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \
223 (l)->head.pred = NULL; \
224 (l)->tail.succ = NULL; \
225 (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \
229 /** Make sure that a list is valid (it was initialized and is not corrupted). */
230 #define LIST_ASSERT_VALID(l) \
233 ASSERT((l)->head.succ != NULL); \
234 ASSERT((l)->head.pred == NULL); \
235 ASSERT((l)->tail.succ == NULL); \
236 ASSERT((l)->tail.pred != NULL); \
240 ASSERT(n->pred == pred); \
243 ASSERT(n == &(l)->tail); \
246 /// Checks that a node isn't part of a given list
247 #define LIST_ASSERT_NOT_CONTAINS(list,node) \
250 ASSERT_VALID_PTR(list); \
251 ASSERT_VALID_PTR(node); \
252 FOREACH_NODE(ln, list) \
253 ASSERT(ln != (Node *)(node)); \
256 #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
258 #define LIST_ASSERT_VALID(l) do {} while (0)
259 #define LIST_ASSERT_NOT_CONTAINS(list,node) do {} while (0)
260 #define INVALIDATE_NODE(n) do {} while (0)
263 /** Tell whether a list is empty. */
264 #define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
266 /** Add node to list head. */
267 #define ADDHEAD(l,n) \
269 LIST_ASSERT_NOT_CONTAINS((l),(n)); \
270 (n)->succ = (l)->head.succ; \
271 (n)->pred = (l)->head.succ->pred; \
272 (n)->succ->pred = (n); \
273 (n)->pred->succ = (n); \
276 /** Add node to list tail. */
277 #define ADDTAIL(l,n) \
279 LIST_ASSERT_NOT_CONTAINS((l),(n)); \
280 (n)->succ = &(l)->tail; \
281 (n)->pred = (l)->tail.pred; \
282 (n)->pred->succ = (n); \
283 (l)->tail.pred = (n); \
287 * Insert node \a n before node \a ln.
289 * \note You can't pass in a list header as \a ln, but
290 * it is safe to pass list-\>head of an empty list.
292 #define INSERT_BEFORE(n,ln) \
294 ASSERT_VALID_PTR(n); \
295 ASSERT_VALID_PTR(ln); \
297 (n)->pred = (ln)->pred; \
298 (ln)->pred->succ = (n); \
303 * Remove \a n from whatever list it is in.
305 * \note Removing a node that has not previously been
306 * inserted into a list invokes undefined behavior.
310 ASSERT_VALID_PTR(n); \
311 (n)->pred->succ = (n)->succ; \
312 (n)->succ->pred = (n)->pred; \
313 INVALIDATE_NODE(n); \
317 * Insert a priority node in a priority queue.
319 * The new node is inserted immediately before the first node with the same
320 * priority or appended to the tail if no such node exists.
322 #define LIST_ENQUEUE_HEAD(list, node) \
325 LIST_ASSERT_NOT_CONTAINS((list),(node)); \
326 FOREACH_NODE(ln, (list)) \
327 if (ln->pri <= (node)->pri) \
329 INSERT_BEFORE(&(node)->link, &ln->link); \
333 * Insert a priority node in a priority queue.
335 * The new node is inserted immediately before the first node with lower
336 * priority or appended to the tail if no such node exists.
338 #define LIST_ENQUEUE(list, node) \
341 LIST_ASSERT_NOT_CONTAINS((list),(node)); \
342 FOREACH_NODE(ln, (list)) \
343 if (ln->pri < (node)->pri) \
345 INSERT_BEFORE(&(node)->link, &ln->link); \
350 * Unlink a node from the head of the list \a l.
352 * \return Pointer to node, or NULL if the list was empty.
354 INLINE Node *list_remHead(List *l)
363 n = l->head.succ; /* Get first node. */
364 l->head.succ = n->succ; /* Link list head to second node. */
365 n->succ->pred = &l->head; /* Link second node to list head. */
372 * Unlink a node from the tail of the list \a l.
374 * \return Pointer to node, or NULL if the list was empty.
376 INLINE Node *list_remTail(List *l)
385 n = l->tail.pred; /* Get last node. */
386 l->tail.pred = n->pred; /* Link list tail to second last node. */
387 n->pred->succ = &l->tail; /* Link second last node to list tail. */
393 /** \} */ //defgroup list
395 #endif /* STRUCT_LIST_H */