4 * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
5 * Copyright 2001 Bernardo Innocenti <bernie@develer.com>
6 * This file is part of DevLib - See devlib/README for information.
11 * \author Bernardo Innocenti <bernie@develer.com>
13 * \brief General pourpose double-linked lists
18 *#* Revision 1.9 2004/10/21 09:37:55 bernie
19 *#* Revamp documentation.
21 *#* Revision 1.8 2004/10/19 08:46:34 bernie
24 *#* Revision 1.7 2004/08/25 14:12:09 rasky
25 *#* Aggiornato il comment block dei log RCS
27 *#* Revision 1.6 2004/07/30 14:34:10 rasky
28 *#* Vari fix per documentazione e commenti
29 *#* Aggiunte PP_CATn e STATIC_ASSERT
31 *#* Revision 1.5 2004/07/20 23:45:01 bernie
32 *#* Finally remove redundant protos.
34 *#* Revision 1.4 2004/07/18 22:12:53 bernie
35 *#* Fix warnings with GCC 3.3.2.
37 *#* Revision 1.3 2004/07/18 22:01:43 bernie
38 *#* REMHEAD(), REMTAIL(): Move to list.h as inline functions.
40 *#* Revision 1.2 2004/06/03 11:27:09 bernie
41 *#* Add dual-license information.
43 *#* Revision 1.1 2004/05/23 15:43:16 bernie
44 *#* Import mware modules.
51 * This structure represents a node for bidirectional lists.
53 * Data is usually appended to nodes by making them the first
54 * field of another struture, as a poor-man's form of inheritance.
63 * Head of a doubly-linked list of \c Node structs.
65 * Lists must be initialized with LIST_INIT() prior to use.
67 * Nodes can be added and removed from either end of the list
68 * with O(1) performance. Iterating over these lists can be
69 * tricky: use the FOREACHNODE() macro instead.
79 /*! Template for a list of \a T structures. */
80 #define DECLARE_LIST(T) \
81 struct { T *head; T *null; T *tail; }
83 /*! Template for a node in a list of \a T structures. */
84 #define DECLARE_NODE(T) \
85 struct { T *succ; T *pred; }
87 /*! Template for a node in a list of \a T structures. */
88 #define DECLARE_NODE_ANON(T) \
92 * Iterate over all nodes in a list.
94 * This macro generates a "for" statement using the following parameters:
95 * \param n Node pointer to be used in each iteration.
96 * \param l Pointer to list.
98 #define FOREACHNODE(n,l) \
100 (n) = (typeof(n))((l)->head); \
101 ((Node *)(n))->succ; \
102 (n) = (typeof(n))(((Node *)(n))->succ) \
105 /*! Initialize a list. */
106 #define LIST_INIT(l) \
108 (l)->head = (Node *)(&(l)->null); \
110 (l)->tail = (Node *)(&(l)->head); \
114 #define INITLIST(l) LIST_INIT(l)
116 /*! Add node to list head. */
117 #define ADDHEAD(l,n) \
119 (n)->succ = (l)->head; \
120 (n)->pred = (Node *)&(l)->head; \
121 (n)->succ->pred = (n); \
125 /*! Add node to list tail. */
126 #define ADDTAIL(l,n) \
128 (n)->succ = (Node *)(&(l)->null); \
129 (n)->pred = (l)->tail; \
130 (n)->pred->succ = (n); \
135 * Insert node \a n before node \a ln.
137 * \note You can't pass in a list header as \a ln, but
138 * it is safe to pass list-\>head of an empty list.
140 #define INSERTBEFORE(n,ln) \
143 (n)->pred = (ln)->pred; \
144 (ln)->pred->succ = (n); \
149 * Remove \a n from whatever list it is in.
151 * \note Removing a node that has not previously been
152 * inserted into a list invokes undefined behavior.
156 (n)->pred->succ = (n)->succ; \
157 (n)->succ->pred = (n)->pred; \
160 /*! Tell whether a list is empty. */
161 #define ISLISTEMPTY(l) ( (l)->head == (Node *)(&(l)->null) )
164 * Unlink a node from the head of the list \a l.
166 * \return Pointer to node, or NULL if the list was empty.
168 INLINE Node *REMHEAD(List *l)
177 n->succ->pred = (Node *)l;
182 * Unlink a node from the tail of the list \a l.
184 * \return Pointer to node, or NULL if the list was empty.
186 INLINE Node *REMTAIL(List *l)
195 n->pred->succ = (Node *)&l->null;
199 #endif /* MWARE_LIST_H */