Moved iobuf.h assertions outside the static inline functions, so that
[people/sha0/gpxe.git] / src / include / gpxe / list.h
1 #ifndef _GPXE_LIST_H
2 #define _GPXE_LIST_H
3
4 /** @file
5  *
6  * Linked lists
7  *
8  * This linked list handling code is based on the Linux kernel's
9  * list.h.
10  */
11
12 #include <stddef.h>
13 #include <assert.h>
14
15 /*
16  * Simple doubly linked list implementation.
17  *
18  * Some of the internal functions ("__xxx") are useful when
19  * manipulating whole lists rather than single entries, as
20  * sometimes we already know the next/prev entries and we can
21  * generate better code by using them directly rather than
22  * using the generic single-entry routines.
23  */
24
25 struct list_head {
26         struct list_head *next;
27         struct list_head *prev;
28 };
29
30 #define LIST_HEAD_INIT( name ) { &(name), &(name) }
31
32 #define LIST_HEAD( name ) \
33         struct list_head name = LIST_HEAD_INIT ( name )
34
35 #define INIT_LIST_HEAD( ptr ) do { \
36         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
37 } while ( 0 )
38
39 /*
40  * Insert a new entry between two known consecutive entries.
41  *
42  * This is only for internal list manipulation where we know
43  * the prev/next entries already!
44  */
45 static inline void __list_add ( struct list_head *new,
46                                 struct list_head *prev,
47                                 struct list_head *next ) {
48         next->prev = new;
49         new->next = next;
50         new->prev = prev;
51         prev->next = new;
52 }
53
54 /**
55  * Add a new entry to the head of a list
56  *
57  * @v new       New entry to be added
58  * @v head      List head to add it after
59  *
60  * Insert a new entry after the specified head.  This is good for
61  * implementing stacks.
62  */
63 static inline void list_add ( struct list_head *new, struct list_head *head ) {
64         __list_add ( new, head, head->next );
65 }
66 #define list_add( new, head ) do {                      \
67         assert ( (head)->next->prev == (head) );        \
68         assert ( (head)->prev->next == (head) );        \
69         list_add ( (new), (head) );                     \
70         } while ( 0 )
71
72 /**
73  * Add a new entry to the tail of a list
74  *
75  * @v new       New entry to be added
76  * @v head      List head to add it before
77  *
78  * Insert a new entry before the specified head.  This is useful for
79  * implementing queues.
80  */
81 static inline void list_add_tail ( struct list_head *new,
82                                    struct list_head *head ) {
83         __list_add ( new, head->prev, head );
84 }
85 #define list_add_tail( new, head ) do {                 \
86         assert ( (head)->next->prev == (head) );        \
87         assert ( (head)->prev->next == (head) );        \
88         list_add_tail ( (new), (head) );                \
89         } while ( 0 )
90
91 /*
92  * Delete a list entry by making the prev/next entries
93  * point to each other.
94  *
95  * This is only for internal list manipulation where we know
96  * the prev/next entries already!
97  */
98 static inline void __list_del ( struct list_head * prev,
99                                 struct list_head * next ) {
100         next->prev = prev;
101         prev->next = next;
102 }
103
104 /**
105  * Delete an entry from a list
106  *
107  * @v entry     Element to delete from the list
108  *
109  * Note that list_empty() on entry does not return true after this;
110  * the entry is in an undefined state.
111  */
112 static inline void list_del ( struct list_head *entry ) {
113         __list_del ( entry->prev, entry->next );
114 }
115 #define list_del( entry ) do {                          \
116         assert ( (entry)->prev != NULL );               \
117         assert ( (entry)->next != NULL );               \
118         assert ( (entry)->next->prev == (entry) );      \
119         assert ( (entry)->prev->next == (entry) );      \
120         list_del ( (entry) );                           \
121         } while ( 0 )
122
123 /**
124  * Test whether a list is empty
125  *
126  * @v head      List to test.
127  */
128 static inline int list_empty ( const struct list_head *head ) {
129         return head->next == head;
130 }
131
132 /**
133  * Get the containing struct for this entry
134  *
135  * @v ptr       The struct list_head pointer
136  * @v type      The type of the struct this is embedded in
137  * @v member    The name of the list_struct within the struct
138  */
139 #define list_entry( ptr, type, member ) \
140         container_of ( ptr, type, member )
141
142 /**
143  * Iterate over a list
144  *
145  * @v pos       The &struct list_head to use as a loop counter
146  * @v head      The head for your list
147  */
148 #define list_for_each( pos, head ) \
149         for ( pos = (head)->next; pos != (head); pos = pos->next )
150
151 /**
152  * Iterate over entries in a list
153  *
154  * @v pos       The type * to use as a loop counter
155  * @v head      The head for your list
156  * @v member    The name of the list_struct within the struct
157  */
158 #define list_for_each_entry( pos, head, member )                              \
159         for ( pos = list_entry ( (head)->next, typeof ( *pos ), member );     \
160               &pos->member != (head);                                         \
161               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
162
163 /**
164  * Iterate over entries in a list, safe against deletion of entries
165  *
166  * @v pos       The type * to use as a loop counter
167  * @v tmp       Another type * to use for temporary storage
168  * @v head      The head for your list
169  * @v member    The name of the list_struct within the struct
170  */
171 #define list_for_each_entry_safe( pos, tmp, head, member )                    \
172         for ( pos = list_entry ( (head)->next, typeof ( *pos ), member ),     \
173               tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \
174               &pos->member != (head);                                         \
175               pos = tmp,                                                      \
176               tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) )
177
178 #endif /* _GPXE_LIST_H */