1 #ifndef FIRM_ADT_LIST_H
2 #define FIRM_ADT_LIST_H
10 * @defgroup lists Linked Lists
11 * @brief Doubly linked lists.
13 * Simple doubly linked list implementation.
15 * Some of the internal functions ("__xxx") are useful when
16 * manipulating whole lists rather than single entries, as
17 * sometimes we already know the next/prev entries and we can
18 * generate better code by using them directly rather than
19 * using the generic single-entry routines.
25 * Put this into all list elements and at the place where you want to keep
26 * references to the list. */
27 typedef struct list_head list_head;
29 /** Static initializer for a list header */
30 #define LIST_HEAD_INIT(name) { &(name), &(name) }
32 /** Defines a (static) list reference */
33 #define LIST_HEAD(name) \
34 struct list_head name = LIST_HEAD_INIT(name)
36 /** Initializes a list header */
37 #define INIT_LIST_HEAD(ptr) do { \
38 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
43 struct list_head *next, *prev;
46 #define _list_offsetof(type,member) \
47 ((char *) &(((type *) 0)->member) - (char *) 0)
49 #define _list_container_of(ptr, type, member) \
50 ((type *) ((char *) (ptr) - _list_offsetof(type, member)))
54 * Inserts a new entry between two known consecutive entries.
56 * This is only for internal list manipulation where we know
57 * the prev/next entries already!
59 static inline void __list_add(struct list_head *new_node,
60 struct list_head *prev,
61 struct list_head *next)
63 next->prev = new_node;
64 new_node->next = next;
65 new_node->prev = prev;
66 prev->next = new_node;
71 * @param new_node new entry to be added
72 * @param head list head to add it after
74 * Insert a new entry after the specified head.
75 * This is good for implementing stacks.
77 static inline void list_add(struct list_head *new_node, struct list_head *head)
79 __list_add(new_node, head, head->next);
84 * @param new_node new entry to be added
85 * @param head list head to add it before
87 * Insert a new entry before the specified head.
88 * This is useful for implementing queues.
90 static inline void list_add_tail(struct list_head *new_node, struct list_head *head)
92 __list_add(new_node, head->prev, head);
96 * Deletes a list entry by making the prev/next entries
97 * point to each other.
99 * This is only for internal list manipulation where we know
100 * the prev/next entries already!
102 static inline void __list_del(struct list_head * prev, struct list_head * next)
109 * Deletes entry from list.
110 * @param entry the element to delete from the list.
113 * list_empty on entry does not return true after this, the entry is
114 * in an undefined state.
116 static inline void list_del(struct list_head *entry)
118 __list_del(entry->prev, entry->next);
125 * Deletes entry from list and reinitialize it.
126 * @param entry the element to delete from the list.
128 static inline void list_del_init(struct list_head *entry)
130 __list_del(entry->prev, entry->next);
131 INIT_LIST_HEAD(entry);
135 * Deletes from one list and add as another's head
136 * @param list the entry to move
137 * @param head the head that will precede our entry
139 static inline void list_move(struct list_head *list, struct list_head *head)
141 __list_del(list->prev, list->next);
142 list_add(list, head);
146 * Deletes from one list and add as another's tail
147 * @param list the entry to move
148 * @param head the head that will follow our entry
150 static inline void list_move_tail(struct list_head *list,
151 struct list_head *head)
153 __list_del(list->prev, list->next);
154 list_add_tail(list, head);
158 * Tests whether a list is empty
159 * @param head the list to test.
161 static inline int list_empty(const struct list_head *head)
163 return head->next == head;
167 * Join two nonempty lists.
169 * @note Use list_splice() if @p list is possibly empty.
170 * @param list the new list to add.
171 * @param head the place to add it in the first list.
173 static inline void __list_splice(struct list_head *list,
174 struct list_head *head)
176 struct list_head *first = list->next;
177 struct list_head *last = list->prev;
178 struct list_head *at = head->next;
188 * list_splice - join two lists
189 * @param list the new list to add.
190 * @param head the place to add it in the first list.
192 static inline void list_splice(struct list_head *list, struct list_head *head)
194 if (!list_empty(list))
195 __list_splice(list, head);
199 * list_splice_init - join two lists and reinitialize the emptied list.
200 * @param list the new list to add.
201 * @param head the place to add it in the first list.
203 * The list at list is reinitialized
205 static inline void list_splice_init(struct list_head *list,
206 struct list_head *head)
208 if (!list_empty(list)) {
209 __list_splice(list, head);
210 INIT_LIST_HEAD(list);
215 * list_entry - get the struct for this entry
216 * @param ptr the &struct list_head pointer.
217 * @param type the type of the struct this is embedded in.
218 * @param member the name of the list_struct within the struct.
220 #define list_entry(ptr, type, member) \
221 _list_container_of(ptr, type, member)
224 * list_for_each - iterate over a list
225 * @param pos the &struct list_head to use as a loop counter.
226 * @param head the head for your list.
228 #define list_for_each(pos, head) \
229 for (pos = (head)->next; pos != (head); pos = pos->next)
232 * __list_for_each - iterate over a list
233 * @param pos the &struct list_head to use as a loop counter.
234 * @param head the head for your list.
236 * This variant differs from list_for_each() in that it's the
237 * simplest possible list iteration code, no ing is done.
238 * Use this for code that knows the list to be very short (empty
239 * or 1 entry) most of the time.
241 #define __list_for_each(pos, head) \
242 for (pos = (head)->next; pos != (head); pos = pos->next)
245 * list_for_each_prev - iterate over a list backwards
246 * @param pos the &struct list_head to use as a loop counter.
247 * @param head the head for your list.
249 #define list_for_each_prev(pos, head) \
250 for (pos = (head)->prev; pos != (head); pos = pos->prev)
253 * list_for_each_safe - iterate over a list safe against removal of list entry
254 * @param pos the &struct list_head to use as a loop counter.
255 * @param n another &struct list_head to use as temporary storage
256 * @param head the head for your list.
258 #define list_for_each_safe(pos, n, head) \
259 for (pos = (head)->next, n = pos->next; pos != (head); \
260 pos = n, n = pos->next)
263 * list_for_each_entry - iterate over list of given type
264 * @param type the type of the struct where the listhead is embedded in
265 * @param pos the type * to use as a loop counter.
266 * @param head the head for your list.
267 * @param member the name of the list_struct within the struct.
269 #define list_for_each_entry(type, pos, head, member) \
270 for (pos = list_entry((head)->next, type, member); \
271 &pos->member != (head); \
272 pos = list_entry(pos->member.next, type, member))
275 * list_for_each_entry_reverse - iterate backwards over list of given type.
276 * @param type the type of the struct where the listhead is embedded in
277 * @param pos the type * to use as a loop counter.
278 * @param head the head for your list.
279 * @param member the name of the list_struct within the struct.
281 #define list_for_each_entry_reverse(type, pos, head, member) \
282 for (pos = list_entry((head)->prev, type, member); \
283 &pos->member != (head); \
284 pos = list_entry(pos->member.prev, type, member))
288 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
289 * @param type the type of the struct where the listhead is embedded in
290 * @param pos the type * to use as a loop counter.
291 * @param n another type * to use as temporary storage
292 * @param head the head for your list.
293 * @param member the name of the list_struct within the struct.
295 #define list_for_each_entry_safe(type, pos, n, head, member) \
296 for (pos = list_entry((head)->next, type, member), \
297 n = list_entry(pos->member.next, type, member); \
298 &pos->member != (head); \
299 pos = n, n = list_entry(n->member.next, type, member))