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 )
inline_list_add(struct list_head * new,struct list_head * head)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 )
inline_list_add_tail(struct list_head * new,struct list_head * head)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 )
inline_list_del(struct list_head * list)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) ); } )
inline_list_empty(const struct list_head * 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) ); } )
inline_list_is_singular(const struct list_head * 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) ); } )
inline_list_is_last(const struct list_head * list,const struct list_head * 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 )
inline_list_cut_position(struct list_head * new,struct list_head * list,struct list_head * entry)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 )
inline_list_splice(const struct list_head * list,struct list_head * entry)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 )
inline_list_splice_tail(const struct list_head * list,struct list_head * entry)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 )
inline_list_splice_init(struct list_head * list,struct list_head * entry)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
inline_list_splice_tail_init(struct list_head * list,struct list_head * entry)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) ); } )
inline_list_contains(struct list_head * entry,struct list_head * 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 */
527