iPXE
list.h
Go to the documentation of this file.
1 #ifndef _IPXE_LIST_H
2 #define _IPXE_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_OR_LATER_OR_UBDL );
13 
14 #include <stddef.h>
15 #include <assert.h>
16 
17 /** A doubly-linked list entry (or list head) */
18 struct list_head {
19  /** Next list entry */
20  struct list_head *next;
21  /** Previous list entry */
22  struct list_head *prev;
23 };
24 
25 /**
26  * Initialise a static list head
27  *
28  * @v list List head
29  */
30 #define LIST_HEAD_INIT( list ) { &(list), &(list) }
31 
32 /**
33  * Declare a static list head
34  *
35  * @v list List head
36  */
37 #define LIST_HEAD( list ) \
38  struct list_head list = LIST_HEAD_INIT ( list )
39 
40 /**
41  * Initialise a list head
42  *
43  * @v list List head
44  */
45 #define INIT_LIST_HEAD( list ) do { \
46  (list)->next = (list); \
47  (list)->prev = (list); \
48  } while ( 0 )
49 
50 /**
51  * Check a list entry or list head is valid
52  *
53  * @v list List entry or head
54  */
55 #define list_check( list ) ( { \
56  assert ( (list) != NULL ); \
57  assert ( (list)->prev != NULL ); \
58  assert ( (list)->next != NULL ); \
59  assert ( (list)->next->prev == (list) ); \
60  assert ( (list)->prev->next == (list) ); \
61  } )
62 
63 /**
64  * Add a new entry to the head of a list
65  *
66  * @v new New entry to be added
67  * @v head List head, or entry after which to add the new entry
68  */
69 #define list_add( new, head ) do { \
70  list_check ( (head) ); \
71  extern_list_add ( (new), (head) ); \
72  list_check ( (head) ); \
73  list_check ( (new) ); \
74  } while ( 0 )
75 static inline void inline_list_add ( struct list_head *new,
76  struct list_head *head ) {
77  struct list_head *prev = head;
78  struct list_head *next = head->next;
79  next->prev = (new);
80  (new)->next = next;
81  (new)->prev = prev;
82  prev->next = (new);
83 }
84 extern void extern_list_add ( struct list_head *new,
85  struct list_head *head );
86 
87 /**
88  * Add a new entry to the tail of a list
89  *
90  * @v new New entry to be added
91  * @v head List head, or entry before which to add the new entry
92  */
93 #define list_add_tail( new, head ) do { \
94  list_check ( (head) ); \
95  extern_list_add_tail ( (new), (head) ); \
96  list_check ( (head) ); \
97  list_check ( (new) ); \
98  } while ( 0 )
99 static inline void inline_list_add_tail ( struct list_head *new,
100  struct list_head *head ) {
101  struct list_head *prev = head->prev;
102  struct list_head *next = head;
103  next->prev = (new);
104  (new)->next = next;
105  (new)->prev = prev;
106  prev->next = (new);
107 }
108 extern void extern_list_add_tail ( struct list_head *new,
109  struct list_head *head );
110 
111 /**
112  * Delete an entry from a list
113  *
114  * @v list List entry
115  *
116  * Note that list_empty() on entry does not return true after this;
117  * the entry is in an undefined state.
118  */
119 #define list_del( list ) do { \
120  list_check ( (list) ); \
121  inline_list_del ( (list) ); \
122  } while ( 0 )
123 static inline void inline_list_del ( struct list_head *list ) {
124  struct list_head *next = (list)->next;
125  struct list_head *prev = (list)->prev;
126  next->prev = prev;
127  prev->next = next;
128 }
129 extern void extern_list_del ( struct list_head *list );
130 
131 /**
132  * Test whether a list is empty
133  *
134  * @v list List head
135  */
136 #define list_empty( list ) ( { \
137  list_check ( (list) ); \
138  inline_list_empty ( (list) ); } )
139 static inline int inline_list_empty ( const struct list_head *list ) {
140  return ( list->next == list );
141 }
142 extern int extern_list_empty ( const struct list_head *list );
143 
144 /**
145  * Test whether a list has just one entry
146  *
147  * @v list List to test
148  */
149 #define list_is_singular( list ) ( { \
150  list_check ( (list) ); \
151  inline_list_is_singular ( (list) ); } )
152 static inline int inline_list_is_singular ( const struct list_head *list ) {
153  return ( ( ! list_empty ( list ) ) && ( list->next == list->prev ) );
154 }
155 extern int extern_list_is_singular ( const struct list_head *list );
156 
157 /**
158  * Test whether an entry is the last entry in list
159  *
160  * @v list List entry to test
161  * @v head List head
162  */
163 #define list_is_last( list, head ) ( { \
164  list_check ( (list) ); \
165  list_check ( (head) ); \
166  inline_list_is_last ( (list), (head) ); } )
167 static inline int inline_list_is_last ( const struct list_head *list,
168  const struct list_head *head ) {
169  return ( list->next == head );
170 }
171 extern int extern_list_is_last ( const struct list_head *list,
172  const struct list_head *head );
173 
174 /**
175  * Cut a list into two
176  *
177  * @v new A new list to contain all removed entries
178  * @v list An existing list
179  * @v entry An entry within the existing list
180  *
181  * All entries from @c list up to and including @c entry are moved to
182  * @c new, which should be an empty list. @c entry may be equal to @c
183  * list, in which case no entries are moved.
184  */
185 #define list_cut_position( new, list, entry ) do { \
186  list_check ( (new) ); \
187  assert ( list_empty ( (new) ) ); \
188  list_check ( (list) ); \
189  list_check ( (entry) ); \
190  extern_list_cut_position ( (new), (list), (entry) ); \
191  } while ( 0 )
192 static inline void inline_list_cut_position ( struct list_head *new,
193  struct list_head *list,
194  struct list_head *entry ) {
195  struct list_head *first = entry->next;
196 
197  if ( list != entry ) {
198  new->next = list->next;
199  new->next->prev = new;
200  new->prev = entry;
201  new->prev->next = new;
202  list->next = first;
203  list->next->prev = list;
204  }
205 }
206 extern void extern_list_cut_position ( struct list_head *new,
207  struct list_head *list,
208  struct list_head *entry );
209 
210 /**
211  * Move all entries from one list into another list
212  *
213  * @v list List of entries to add
214  * @v entry Entry after which to add the new entries
215  *
216  * All entries from @c list are inserted after @c entry. Note that @c
217  * list is left in an undefined state; use @c list_splice_init() if
218  * you want @c list to become an empty list.
219  */
220 #define list_splice( list, entry ) do { \
221  list_check ( (list) ); \
222  list_check ( (entry) ); \
223  extern_list_splice ( (list), (entry) ); \
224  } while ( 0 )
225 static inline void inline_list_splice ( const struct list_head *list,
226  struct list_head *entry ) {
227  struct list_head *first = list->next;
228  struct list_head *last = list->prev;
229 
230  if ( ! list_empty ( list ) ) {
231  last->next = entry->next;
232  last->next->prev = last;
233  first->prev = entry;
234  first->prev->next = first;
235  }
236 }
237 extern void extern_list_splice ( const struct list_head *list,
238  struct list_head *entry );
239 
240 /**
241  * Move all entries from one list into another list
242  *
243  * @v list List of entries to add
244  * @v entry Entry before which to add the new entries
245  *
246  * All entries from @c list are inserted before @c entry. Note that @c
247  * list is left in an undefined state; use @c list_splice_tail_init() if
248  * you want @c list to become an empty list.
249  */
250 #define list_splice_tail( list, entry ) do { \
251  list_check ( (list) ); \
252  list_check ( (entry) ); \
253  extern_list_splice_tail ( (list), (entry) ); \
254  } while ( 0 )
255 static inline void inline_list_splice_tail ( const struct list_head *list,
256  struct list_head *entry ) {
257  struct list_head *first = list->next;
258  struct list_head *last = list->prev;
259 
260  if ( ! list_empty ( list ) ) {
261  first->prev = entry->prev;
262  first->prev->next = first;
263  last->next = entry;
264  last->next->prev = last;
265  }
266 }
267 extern void extern_list_splice_tail ( const struct list_head *list,
268  struct list_head *entry );
269 
270 /**
271  * Move all entries from one list into another list and reinitialise empty list
272  *
273  * @v list List of entries to add
274  * @v entry Entry after which to add the new entries
275  *
276  * All entries from @c list are inserted after @c entry.
277  */
278 #define list_splice_init( list, entry ) do { \
279  list_check ( (list) ); \
280  list_check ( (entry) ); \
281  extern_list_splice_init ( (list), (entry) ); \
282  } while ( 0 )
283 static inline void inline_list_splice_init ( struct list_head *list,
284  struct list_head *entry ) {
285  list_splice ( list, entry );
286  INIT_LIST_HEAD ( list );
287 }
288 extern void extern_list_splice_init ( struct list_head *list,
289  struct list_head *entry );
290 
291 /**
292  * Move all entries from one list into another list and reinitialise empty list
293  *
294  * @v list List of entries to add
295  * @v entry Entry before which to add the new entries
296  *
297  * All entries from @c list are inserted before @c entry.
298  */
299 #define list_splice_tail_init( list, entry ) do { \
300  list_check ( (list) ); \
301  list_check ( (entry) ); \
302  extern_list_splice_tail_init ( (list), (entry) ); \
303  } while ( 0 )
304 
305 static inline void inline_list_splice_tail_init ( struct list_head *list,
306  struct list_head *entry ) {
307  list_splice_tail ( list, entry );
308  INIT_LIST_HEAD ( list );
309 }
310 extern void extern_list_splice_tail_init ( struct list_head *list,
311  struct list_head *entry );
312 
313 /**
314  * Get the container of a list entry
315  *
316  * @v list List entry
317  * @v type Containing type
318  * @v member Name of list field within containing type
319  * @ret container Containing object
320  */
321 #define list_entry( list, type, member ) ( { \
322  list_check ( (list) ); \
323  container_of ( list, type, member ); } )
324 
325 /**
326  * Get the container of the first entry in a list
327  *
328  * @v list List head
329  * @v type Containing type
330  * @v member Name of list field within containing type
331  * @ret first First list entry, or NULL
332  */
333 #define list_first_entry( list, type, member ) \
334  ( list_empty ( (list) ) ? \
335  ( type * ) NULL : \
336  list_entry ( (list)->next, type, member ) )
337 
338 /**
339  * Get the container of the last entry in a list
340  *
341  * @v list List head
342  * @v type Containing type
343  * @v member Name of list field within containing type
344  * @ret first First list entry, or NULL
345  */
346 #define list_last_entry( list, type, member ) \
347  ( list_empty ( (list) ) ? \
348  ( type * ) NULL : \
349  list_entry ( (list)->prev, type, member ) )
350 
351 /**
352  * Get the container of the next entry in a list
353  *
354  * @v pos Current list entry
355  * @v head List head
356  * @v member Name of list field within iterator's type
357  * @ret next Next list entry, or NULL at end of list
358  */
359 #define list_next_entry( pos, head, member ) ( { \
360  typeof (pos) next = list_entry ( (pos)->member.next, \
361  typeof ( *(pos) ), \
362  member ); \
363  ( ( &next->member == (head) ) ? NULL : next ); } )
364 
365 /**
366  * Get the container of the previous entry in a list
367  *
368  * @v pos Current list entry
369  * @v head List head
370  * @v member Name of list field within iterator's type
371  * @ret next Next list entry, or NULL at end of list
372  */
373 #define list_prev_entry( pos, head, member ) ( { \
374  typeof (pos) prev = list_entry ( (pos)->member.prev, \
375  typeof ( *(pos) ), \
376  member ); \
377  ( ( &prev->member == (head) ) ? NULL : prev ); } )
378 
379 /**
380  * Test if entry is first in a list
381  *
382  * @v entry List entry
383  * @v head List head
384  * @v member Name of list field within iterator's type
385  * @ret is_first Entry is first in the list
386  */
387 #define list_is_first_entry( entry, head, member ) \
388  ( (head)->next == &(entry)->member )
389 
390 /**
391  * Test if entry is last in a list
392  *
393  * @v entry List entry
394  * @v head List head
395  * @v member Name of list field within iterator's type
396  * @ret is_last Entry is last in the list
397  */
398 #define list_is_last_entry( entry, head, member ) \
399  ( (head)->prev == &(entry)->member )
400 
401 /**
402  * Iterate over a list
403  *
404  * @v pos Iterator
405  * @v head List head
406  */
407 #define list_for_each( pos, head ) \
408  for ( list_check ( (head) ), \
409  pos = (head)->next; \
410  pos != (head); \
411  pos = (pos)->next )
412 
413 /**
414  * Iterate over entries in a list
415  *
416  * @v pos Iterator
417  * @v head List head
418  * @v member Name of list field within iterator's type
419  */
420 #define list_for_each_entry( pos, head, member ) \
421  for ( list_check ( (head) ), \
422  pos = list_entry ( (head)->next, typeof ( *pos ), member ); \
423  &pos->member != (head); \
424  pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
425 
426 /**
427  * Iterate over entries in a list in reverse order
428  *
429  * @v pos Iterator
430  * @v head List head
431  * @v member Name of list field within iterator's type
432  */
433 #define list_for_each_entry_reverse( pos, head, member ) \
434  for ( list_check ( (head) ), \
435  pos = list_entry ( (head)->prev, typeof ( *pos ), member ); \
436  &pos->member != (head); \
437  pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
438 
439 /**
440  * Iterate over entries in a list, safe against deletion of the current entry
441  *
442  * @v pos Iterator
443  * @v tmp Temporary value (of same type as iterator)
444  * @v head List head
445  * @v member Name of list field within iterator's type
446  */
447 #define list_for_each_entry_safe( pos, tmp, head, member ) \
448  for ( list_check ( (head) ), \
449  pos = list_entry ( (head)->next, typeof ( *pos ), member ), \
450  tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \
451  &pos->member != (head); \
452  pos = tmp, \
453  tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) )
454 
455 /**
456  * Iterate over entries in a list, starting after current position
457  *
458  * @v pos Iterator
459  * @v head List head
460  * @v member Name of list field within iterator's type
461  */
462 #define list_for_each_entry_continue( pos, head, member ) \
463  for ( list_check ( (head) ), \
464  pos = list_entry ( pos->member.next, typeof ( *pos ), member ); \
465  &pos->member != (head); \
466  pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
467 
468 /**
469  * Iterate over entries in a list in reverse, starting after current position
470  *
471  * @v pos Iterator
472  * @v head List head
473  * @v member Name of list field within iterator's type
474  */
475 #define list_for_each_entry_continue_reverse( pos, head, member ) \
476  for ( list_check ( (head) ), \
477  pos = list_entry ( pos->member.prev, typeof ( *pos ), member ); \
478  &pos->member != (head); \
479  pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
480 
481 /**
482  * Test if list contains a specified entry
483  *
484  * @v entry Entry
485  * @v head List head
486  * @ret present List contains specified entry
487  */
488 #define list_contains( entry, head ) ( { \
489  list_check ( (head) ); \
490  list_check ( (entry) ); \
491  extern_list_contains ( (entry), (head) ); } )
492 static inline int inline_list_contains ( struct list_head *entry,
493  struct list_head *head ) {
494  struct list_head *tmp;
495 
496  list_for_each ( tmp, head ) {
497  if ( tmp == entry )
498  return 1;
499  }
500  return 0;
501 }
502 extern int extern_list_contains ( struct list_head *entry,
503  struct list_head *head );
504 
505 /**
506  * Test if list contains a specified entry
507  *
508  * @v entry Entry
509  * @v head List head
510  * @ret present List contains specified entry
511  */
512 #define list_contains_entry( entry, head, member ) \
513  list_contains ( &(entry)->member, (head) )
514 
515 /**
516  * Check list contains a specified entry
517  *
518  * @v entry Entry
519  * @v head List head
520  * @v member Name of list field within iterator's type
521  */
522 #define list_check_contains_entry( entry, head, member ) do { \
523  assert ( list_contains_entry ( (entry), (head), member ) ); \
524  } while ( 0 )
525 
526 #endif /* _IPXE_LIST_H */
static int inline_list_empty(const struct list_head *list)
Definition: list.h:139
static void inline_list_splice_init(struct list_head *list, struct list_head *entry)
Definition: list.h:283
static void inline_list_add(struct list_head *new, struct list_head *head)
Definition: list.h:75
static void inline_list_splice(const struct list_head *list, struct list_head *entry)
Definition: list.h:225
void extern_list_splice(const struct list_head *list, struct list_head *entry)
Definition: list.c:65
uint32_t next
Next descriptor address.
Definition: myson.h:18
struct list_head * next
Next list entry.
Definition: list.h:20
static void inline_list_splice_tail(const struct list_head *list, struct list_head *entry)
Definition: list.h:255
int extern_list_is_last(const struct list_head *list, const struct list_head *head)
Definition: list.c:54
#define list_for_each(pos, head)
Iterate over a list.
Definition: list.h:407
uint8_t head
Head number.
Definition: int13.h:34
A doubly-linked list entry (or list head)
Definition: list.h:18
#define list_empty(list)
Test whether a list is empty.
Definition: list.h:136
static int inline_list_contains(struct list_head *entry, struct list_head *head)
Definition: list.h:492
Assertions.
static void inline_list_cut_position(struct list_head *new, struct list_head *list, struct list_head *entry)
Definition: list.h:192
static void inline_list_del(struct list_head *list)
Definition: list.h:123
void extern_list_del(struct list_head *list)
Definition: list.c:42
union aes_table_entry entry[256]
Table entries, indexed by S(N)
Definition: aes.c:26
void extern_list_splice_tail(const struct list_head *list, struct list_head *entry)
Definition: list.c:70
#define list_splice_tail(list, entry)
Move all entries from one list into another list.
Definition: list.h:250
int extern_list_is_singular(const struct list_head *list)
Definition: list.c:50
uint8_t * tmp
Definition: entropy.h:156
int extern_list_empty(const struct list_head *list)
Definition: list.c:46
uint32_t last
Length to read in last segment, or zero.
Definition: pccrc.h:30
void extern_list_add(struct list_head *new, struct list_head *head)
Definition: list.c:34
#define INIT_LIST_HEAD(list)
Initialise a list head.
Definition: list.h:45
struct list_head * prev
Previous list entry.
Definition: list.h:22
void extern_list_splice_tail_init(struct list_head *list, struct list_head *entry)
Definition: list.c:80
static int inline_list_is_singular(const struct list_head *list)
Definition: list.h:152
#define list_splice(list, entry)
Move all entries from one list into another list.
Definition: list.h:220
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
void extern_list_splice_init(struct list_head *list, struct list_head *entry)
Definition: list.c:75
static void inline_list_splice_tail_init(struct list_head *list, struct list_head *entry)
Definition: list.h:305
static int inline_list_is_last(const struct list_head *list, const struct list_head *head)
Definition: list.h:167
int extern_list_contains(struct list_head *entry, struct list_head *head)
Definition: list.c:85
uint32_t first
Length to skip in first segment.
Definition: pccrc.h:23
void extern_list_cut_position(struct list_head *new, struct list_head *list, struct list_head *entry)
Definition: list.c:59
static void inline_list_add_tail(struct list_head *new, struct list_head *head)
Definition: list.h:99
void extern_list_add_tail(struct list_head *new, struct list_head *head)
Definition: list.c:38