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 Bernardo Innocenti <bernie@develer.com>
36 * \author Bernardo Innocenti <bernie@develer.com>
38 * \brief General pourpose double-linked lists
44 #include <cfg/compiler.h> /* INLINE */
45 #include <cfg/debug.h> /* ASSERT() */
48 * This structure represents a node for bidirectional lists.
50 * Data is usually appended to nodes by making them the first
51 * field of another struture, as a poor-man's form of inheritance.
60 * Head of a doubly-linked list of \c Node structs.
62 * Lists must be initialized with LIST_INIT() prior to use.
64 * Nodes can be added and removed from either end of the list
65 * with O(1) performance. Iterating over these lists can be
66 * tricky: use the FOREACH_NODE() macro instead.
75 * Extended node for priority queues.
77 typedef struct _PriNode
85 * Template for a naked node in a list of \a T structures.
87 * To be used as data member in other structures:
92 * DECLARE_NODE_ANON(struct Foo)
97 * DECLARE_LIST_TYPE(Foo);
101 * static LIST_TYPE(Foo) foo_list;
102 * static Foo foo1, foo2;
105 * LIST_INIT(&foo_list);
106 * ADDHEAD(&foo_list, &foo1);
107 * INSERT_BEFORE(&foo_list, &foo2);
108 * FOREACH_NODE(fp, &foo_list)
114 #define DECLARE_NODE_ANON(T) \
117 /** Declare a typesafe node for structures of type \a T. */
118 #define DECLARE_NODE_TYPE(T) \
119 typedef struct T##Node { T *succ; T *pred; } T##Node
121 /** Template for a list of \a T structures. */
122 #define DECLARE_LIST_TYPE(T) \
123 DECLARE_NODE_TYPE(T); \
124 typedef struct T##List { \
129 #define NODE_TYPE(T) T##Node
130 #define LIST_TYPE(T) T##List
133 * Get a pointer to the first node in a list.
135 * If \a l is empty, result points to l->tail.
137 #define LIST_HEAD(l) ((l)->head.succ)
140 * Get a pointer to the last node in a list.
142 * If \a l is empty, result points to l->head.
144 #define LIST_TAIL(l) ((l)->tail.pred)
146 // TODO: move in compiler.h
148 #define TYPEOF_OR_VOIDPTR(type) typeof(type)
150 #define TYPEOF_OR_VOIDPTR(type) void *
154 * Iterate over all nodes in a list.
156 * This macro generates a "for" statement using the following parameters:
157 * \param n Node pointer to be used in each iteration.
158 * \param l Pointer to list.
160 #define FOREACH_NODE(n, l) \
162 (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l); \
163 ((Node *)(n))->succ; \
164 (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
168 * Iterate backwards over all nodes in a list.
170 * This macro generates a "for" statement using the following parameters:
171 * \param n Node pointer to be used in each iteration.
172 * \param l Pointer to list.
174 #define REVERSE_FOREACH_NODE(n, l) \
176 (n) = (TYPEOF_OR_VOIDPTR(n))LIST_TAIL(l); \
177 ((Node *)(n))->pred; \
178 (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \
181 /** Initialize a list. */
182 #define LIST_INIT(l) \
184 (l)->head.succ = (TYPEOF_OR_VOIDPTR((l)->head.succ)) &(l)->tail; \
185 (l)->head.pred = NULL; \
186 (l)->tail.succ = NULL; \
187 (l)->tail.pred = (TYPEOF_OR_VOIDPTR((l)->tail.pred)) &(l)->head; \
191 /** Make sure that a list is valid (it was initialized and is not corrupted). */
192 #define LIST_ASSERT_VALID(l) \
195 ASSERT((l)->head.succ != NULL); \
196 ASSERT((l)->head.pred == NULL); \
197 ASSERT((l)->tail.succ == NULL); \
198 ASSERT((l)->tail.pred != NULL); \
202 ASSERT(n->pred == pred); \
205 ASSERT(n == &(l)->tail); \
208 #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
210 #define LIST_ASSERT_VALID(l) do {} while (0)
211 #define INVALIDATE_NODE(n) do {} while (0)
214 /** Add node to list head. */
215 #define ADDHEAD(l,n) \
219 (n)->succ = (l)->head.succ; \
220 (n)->pred = (l)->head.succ->pred; \
221 (n)->succ->pred = (n); \
222 (n)->pred->succ = (n); \
225 /** Add node to list tail. */
226 #define ADDTAIL(l,n) \
230 (n)->succ = &(l)->tail; \
231 (n)->pred = (l)->tail.pred; \
232 (n)->pred->succ = (n); \
233 (l)->tail.pred = (n); \
237 * Insert node \a n before node \a ln.
239 * \note You can't pass in a list header as \a ln, but
240 * it is safe to pass list-\>head of an empty list.
242 #define INSERT_BEFORE(n,ln) \
245 (n)->pred = (ln)->pred; \
246 (ln)->pred->succ = (n); \
251 * Remove \a n from whatever list it is in.
253 * \note Removing a node that has not previously been
254 * inserted into a list invokes undefined behavior.
258 (n)->pred->succ = (n)->succ; \
259 (n)->succ->pred = (n)->pred; \
260 INVALIDATE_NODE(n); \
263 /** Tell whether a list is empty. */
264 #define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
267 * Insert a priority node in a priority queue.
269 * The new node is inserted immediately before the
270 * first node with lower priority or appended to
271 * the tail if no such node exists.
273 #define LIST_ENQUEUE(list, node) \
276 FOREACH_NODE(ln, (list)) \
277 if (ln->pri < (node)->pri) \
279 INSERT_BEFORE(&(node)->link, &ln->link); \
284 * Unlink a node from the head of the list \a l.
286 * \return Pointer to node, or NULL if the list was empty.
288 INLINE Node *list_remHead(List *l)
295 n = l->head.succ; /* Get first node. */
296 l->head.succ = n->succ; /* Link list head to second node. */
297 n->succ->pred = &l->head; /* Link second node to list head. */
304 * Unlink a node from the tail of the list \a l.
306 * \return Pointer to node, or NULL if the list was empty.
308 INLINE Node *list_remTail(List *l)
315 n = l->tail.pred; /* Get last node. */
316 l->tail.pred = n->pred; /* Link list tail to second last node. */
317 n->pred->succ = &l->tail; /* Link second last node to list tail. */
323 #endif /* MWARE_LIST_H */