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