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
12FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
13FILE_SECBOOT ( PERMITTED );
14
15#include <stddef.h>
16#include <assert.h>
17
18/** A doubly-linked list entry (or list head) */
19struct 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 )
76static 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}
85extern 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 )
100static 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}
109extern 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 )
124static 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}
130extern 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) ); } )
140static inline int inline_list_empty ( const struct list_head *list ) {
141 return ( list->next == list );
142}
143extern 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) ); } )
153static inline int inline_list_is_singular ( const struct list_head *list ) {
154 return ( ( ! list_empty ( list ) ) && ( list->next == list->prev ) );
155}
156extern 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) ); } )
168static inline int inline_list_is_last ( const struct list_head *list,
169 const struct list_head *head ) {
170 return ( list->next == head );
171}
172extern 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 )
193static 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}
207extern 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 )
226static 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}
238extern 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 )
256static 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}
268extern 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 )
284static 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}
289extern 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
306static 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}
311extern 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) ); } )
520static 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}
530extern 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 */
assert.h
Assertions.
next
uint32_t next
Next descriptor address.
Definition dwmac.h:11
head
uint8_t head
Head number.
Definition int13.h:23
FILE_LICENCE
#define FILE_LICENCE(_licence)
Declare a particular licence as applying to a file.
Definition compiler.h:896
FILE_SECBOOT
#define FILE_SECBOOT(_status)
Declare a file's UEFI Secure Boot permission status.
Definition compiler.h:926
tmp
unsigned long tmp
Definition linux_pci.h:65
extern_list_is_last
int extern_list_is_last(const struct list_head *list, const struct list_head *head)
Definition list.c:55
extern_list_splice
void extern_list_splice(const struct list_head *list, struct list_head *entry)
Definition list.c:66
extern_list_empty
int extern_list_empty(const struct list_head *list)
Definition list.c:47
extern_list_contains
int extern_list_contains(struct list_head *entry, struct list_head *head)
Definition list.c:86
inline_list_splice_tail
static void inline_list_splice_tail(const struct list_head *list, struct list_head *entry)
Definition list.h:256
list_splice
#define list_splice(list, entry)
Move all entries from one list into another list.
Definition list.h:221
list_splice_tail
#define list_splice_tail(list, entry)
Move all entries from one list into another list.
Definition list.h:251
extern_list_add
void extern_list_add(struct list_head *new, struct list_head *head)
Definition list.c:35
extern_list_splice_init
void extern_list_splice_init(struct list_head *list, struct list_head *entry)
Definition list.c:76
extern_list_is_singular
int extern_list_is_singular(const struct list_head *list)
Definition list.c:51
extern_list_del
void extern_list_del(struct list_head *list)
Definition list.c:43
inline_list_add
static void inline_list_add(struct list_head *new, struct list_head *head)
Definition list.h:76
inline_list_splice_init
static void inline_list_splice_init(struct list_head *list, struct list_head *entry)
Definition list.h:284
inline_list_del
static void inline_list_del(struct list_head *list)
Definition list.h:124
extern_list_splice_tail_init
void extern_list_splice_tail_init(struct list_head *list, struct list_head *entry)
Definition list.c:81
INIT_LIST_HEAD
#define INIT_LIST_HEAD(list)
Initialise a list head.
Definition list.h:46
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_contains
static int inline_list_contains(struct list_head *entry, struct list_head *head)
Definition list.h:520
list_for_each
#define list_for_each(pos, head)
Iterate over a list.
Definition list.h:419
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
list_empty
#define list_empty(list)
Test whether a list is empty.
Definition list.h:137
extern_list_splice_tail
void extern_list_splice_tail(const struct list_head *list, struct list_head *entry)
Definition list.c:71
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_add_tail
static void inline_list_add_tail(struct list_head *new, struct list_head *head)
Definition list.h:100
inline_list_splice
static void inline_list_splice(const struct list_head *list, struct list_head *entry)
Definition list.h:226
extern_list_add_tail
void extern_list_add_tail(struct list_head *new, struct list_head *head)
Definition list.c:39
inline_list_is_last
static int inline_list_is_last(const struct list_head *list, const struct list_head *head)
Definition list.h:168
inline_list_empty
static int inline_list_empty(const struct list_head *list)
Definition list.h:140
inline_list_is_singular
static int inline_list_is_singular(const struct list_head *list)
Definition list.h:153
first
uint32_t first
First block in range.
Definition pccrr.h:1
list_head
A doubly-linked list entry (or list head)
Definition list.h:19
list_head::next
struct list_head * next
Next list entry.
Definition list.h:21
list_head::prev
struct list_head * prev
Previous list entry.
Definition list.h:23
Generated by doxygen 1.14.0