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