| #ifndef _IPXE_LIST_H |
| #define _IPXE_LIST_H |
| |
| /** @file |
| * |
| * Linked lists |
| * |
| * This linked list handling code is based on the Linux kernel's |
| * list.h. |
| */ |
| |
| FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); |
| |
| #include <stddef.h> |
| #include <assert.h> |
| |
| /** A doubly-linked list entry (or list head) */ |
| struct list_head { |
| /** Next list entry */ |
| struct list_head *next; |
| /** Previous list entry */ |
| struct list_head *prev; |
| }; |
| |
| /** |
| * Initialise a static list head |
| * |
| * @v list List head |
| */ |
| #define LIST_HEAD_INIT( list ) { &(list), &(list) } |
| |
| /** |
| * Declare a static list head |
| * |
| * @v list List head |
| */ |
| #define LIST_HEAD( list ) \ |
| struct list_head list = LIST_HEAD_INIT ( list ) |
| |
| /** |
| * Initialise a list head |
| * |
| * @v list List head |
| */ |
| #define INIT_LIST_HEAD( list ) do { \ |
| (list)->next = (list); \ |
| (list)->prev = (list); \ |
| } while ( 0 ) |
| |
| /** |
| * Check a list entry or list head is valid |
| * |
| * @v list List entry or head |
| */ |
| #define list_check( list ) ( { \ |
| assert ( (list) != NULL ); \ |
| assert ( (list)->prev != NULL ); \ |
| assert ( (list)->next != NULL ); \ |
| assert ( (list)->next->prev == (list) ); \ |
| assert ( (list)->prev->next == (list) ); \ |
| } ) |
| |
| /** |
| * Add a new entry to the head of a list |
| * |
| * @v new New entry to be added |
| * @v head List head, or entry after which to add the new entry |
| */ |
| #define list_add( new, head ) do { \ |
| list_check ( (head) ); \ |
| extern_list_add ( (new), (head) ); \ |
| list_check ( (head) ); \ |
| list_check ( (new) ); \ |
| } while ( 0 ) |
| static inline void inline_list_add ( struct list_head *new, |
| struct list_head *head ) { |
| struct list_head *prev = head; |
| struct list_head *next = head->next; |
| next->prev = (new); |
| (new)->next = next; |
| (new)->prev = prev; |
| prev->next = (new); |
| } |
| extern void extern_list_add ( struct list_head *new, |
| struct list_head *head ); |
| |
| /** |
| * Add a new entry to the tail of a list |
| * |
| * @v new New entry to be added |
| * @v head List head, or entry before which to add the new entry |
| */ |
| #define list_add_tail( new, head ) do { \ |
| list_check ( (head) ); \ |
| extern_list_add_tail ( (new), (head) ); \ |
| list_check ( (head) ); \ |
| list_check ( (new) ); \ |
| } while ( 0 ) |
| static inline void inline_list_add_tail ( struct list_head *new, |
| struct list_head *head ) { |
| struct list_head *prev = head->prev; |
| struct list_head *next = head; |
| next->prev = (new); |
| (new)->next = next; |
| (new)->prev = prev; |
| prev->next = (new); |
| } |
| extern void extern_list_add_tail ( struct list_head *new, |
| struct list_head *head ); |
| |
| /** |
| * Delete an entry from a list |
| * |
| * @v list List entry |
| * |
| * Note that list_empty() on entry does not return true after this; |
| * the entry is in an undefined state. |
| */ |
| #define list_del( list ) do { \ |
| list_check ( (list) ); \ |
| inline_list_del ( (list) ); \ |
| } while ( 0 ) |
| static inline void inline_list_del ( struct list_head *list ) { |
| struct list_head *next = (list)->next; |
| struct list_head *prev = (list)->prev; |
| next->prev = prev; |
| prev->next = next; |
| } |
| extern void extern_list_del ( struct list_head *list ); |
| |
| /** |
| * Test whether a list is empty |
| * |
| * @v list List head |
| */ |
| #define list_empty( list ) ( { \ |
| list_check ( (list) ); \ |
| inline_list_empty ( (list) ); } ) |
| static inline int inline_list_empty ( const struct list_head *list ) { |
| return ( list->next == list ); |
| } |
| extern int extern_list_empty ( const struct list_head *list ); |
| |
| /** |
| * Test whether a list has just one entry |
| * |
| * @v list List to test |
| */ |
| #define list_is_singular( list ) ( { \ |
| list_check ( (list) ); \ |
| inline_list_is_singular ( (list) ); } ) |
| static inline int inline_list_is_singular ( const struct list_head *list ) { |
| return ( ( ! list_empty ( list ) ) && ( list->next == list->prev ) ); |
| } |
| extern int extern_list_is_singular ( const struct list_head *list ); |
| |
| /** |
| * Test whether an entry is the last entry in list |
| * |
| * @v list List entry to test |
| * @v head List head |
| */ |
| #define list_is_last( list, head ) ( { \ |
| list_check ( (list) ); \ |
| list_check ( (head) ); \ |
| inline_list_is_last ( (list), (head) ); } ) |
| static inline int inline_list_is_last ( const struct list_head *list, |
| const struct list_head *head ) { |
| return ( list->next == head ); |
| } |
| extern int extern_list_is_last ( const struct list_head *list, |
| const struct list_head *head ); |
| |
| /** |
| * Cut a list into two |
| * |
| * @v new A new list to contain all removed entries |
| * @v list An existing list |
| * @v entry An entry within the existing list |
| * |
| * All entries from @c list up to and including @c entry are moved to |
| * @c new, which should be an empty list. @c entry may be equal to @c |
| * list, in which case no entries are moved. |
| */ |
| #define list_cut_position( new, list, entry ) do { \ |
| list_check ( (new) ); \ |
| assert ( list_empty ( (new) ) ); \ |
| list_check ( (list) ); \ |
| list_check ( (entry) ); \ |
| extern_list_cut_position ( (new), (list), (entry) ); \ |
| } while ( 0 ) |
| static inline void inline_list_cut_position ( struct list_head *new, |
| struct list_head *list, |
| struct list_head *entry ) { |
| struct list_head *first = entry->next; |
| |
| if ( list != entry ) { |
| new->next = list->next; |
| new->next->prev = new; |
| new->prev = entry; |
| new->prev->next = new; |
| list->next = first; |
| list->next->prev = list; |
| } |
| } |
| extern void extern_list_cut_position ( struct list_head *new, |
| struct list_head *list, |
| struct list_head *entry ); |
| |
| /** |
| * Move all entries from one list into another list |
| * |
| * @v list List of entries to add |
| * @v entry Entry after which to add the new entries |
| * |
| * All entries from @c list are inserted after @c entry. Note that @c |
| * list is left in an undefined state; use @c list_splice_init() if |
| * you want @c list to become an empty list. |
| */ |
| #define list_splice( list, entry ) do { \ |
| list_check ( (list) ); \ |
| list_check ( (entry) ); \ |
| extern_list_splice ( (list), (entry) ); \ |
| } while ( 0 ) |
| static inline void inline_list_splice ( const struct list_head *list, |
| struct list_head *entry ) { |
| struct list_head *first = list->next; |
| struct list_head *last = list->prev; |
| |
| if ( ! list_empty ( list ) ) { |
| last->next = entry->next; |
| last->next->prev = last; |
| first->prev = entry; |
| first->prev->next = first; |
| } |
| } |
| extern void extern_list_splice ( const struct list_head *list, |
| struct list_head *entry ); |
| |
| /** |
| * Move all entries from one list into another list |
| * |
| * @v list List of entries to add |
| * @v entry Entry before which to add the new entries |
| * |
| * All entries from @c list are inserted before @c entry. Note that @c |
| * list is left in an undefined state; use @c list_splice_tail_init() if |
| * you want @c list to become an empty list. |
| */ |
| #define list_splice_tail( list, entry ) do { \ |
| list_check ( (list) ); \ |
| list_check ( (entry) ); \ |
| extern_list_splice_tail ( (list), (entry) ); \ |
| } while ( 0 ) |
| static inline void inline_list_splice_tail ( const struct list_head *list, |
| struct list_head *entry ) { |
| struct list_head *first = list->next; |
| struct list_head *last = list->prev; |
| |
| if ( ! list_empty ( list ) ) { |
| first->prev = entry->prev; |
| first->prev->next = first; |
| last->next = entry; |
| last->next->prev = last; |
| } |
| } |
| extern void extern_list_splice_tail ( const struct list_head *list, |
| struct list_head *entry ); |
| |
| /** |
| * Move all entries from one list into another list and reinitialise empty list |
| * |
| * @v list List of entries to add |
| * @v entry Entry after which to add the new entries |
| * |
| * All entries from @c list are inserted after @c entry. |
| */ |
| #define list_splice_init( list, entry ) do { \ |
| list_check ( (list) ); \ |
| list_check ( (entry) ); \ |
| extern_list_splice_init ( (list), (entry) ); \ |
| } while ( 0 ) |
| static inline void inline_list_splice_init ( struct list_head *list, |
| struct list_head *entry ) { |
| list_splice ( list, entry ); |
| INIT_LIST_HEAD ( list ); |
| } |
| extern void extern_list_splice_init ( struct list_head *list, |
| struct list_head *entry ); |
| |
| /** |
| * Move all entries from one list into another list and reinitialise empty list |
| * |
| * @v list List of entries to add |
| * @v entry Entry before which to add the new entries |
| * |
| * All entries from @c list are inserted before @c entry. |
| */ |
| #define list_splice_tail_init( list, entry ) do { \ |
| list_check ( (list) ); \ |
| list_check ( (entry) ); \ |
| extern_list_splice_tail_init ( (list), (entry) ); \ |
| } while ( 0 ) |
| |
| static inline void inline_list_splice_tail_init ( struct list_head *list, |
| struct list_head *entry ) { |
| list_splice_tail ( list, entry ); |
| INIT_LIST_HEAD ( list ); |
| } |
| extern void extern_list_splice_tail_init ( struct list_head *list, |
| struct list_head *entry ); |
| |
| /** |
| * Get the container of a list entry |
| * |
| * @v list List entry |
| * @v type Containing type |
| * @v member Name of list field within containing type |
| * @ret container Containing object |
| */ |
| #define list_entry( list, type, member ) ( { \ |
| list_check ( (list) ); \ |
| container_of ( list, type, member ); } ) |
| |
| /** |
| * Get the container of the first entry in a list |
| * |
| * @v list List head |
| * @v type Containing type |
| * @v member Name of list field within containing type |
| * @ret first First list entry, or NULL |
| */ |
| #define list_first_entry( list, type, member ) \ |
| ( list_empty ( (list) ) ? \ |
| ( type * ) NULL : \ |
| list_entry ( (list)->next, type, member ) ) |
| |
| /** |
| * Get the container of the last entry in a list |
| * |
| * @v list List head |
| * @v type Containing type |
| * @v member Name of list field within containing type |
| * @ret first First list entry, or NULL |
| */ |
| #define list_last_entry( list, type, member ) \ |
| ( list_empty ( (list) ) ? \ |
| ( type * ) NULL : \ |
| list_entry ( (list)->prev, type, member ) ) |
| |
| /** |
| * Get the container of the next entry in a list |
| * |
| * @v pos Current list entry |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| * @ret next Next list entry, or NULL at end of list |
| */ |
| #define list_next_entry( pos, head, member ) ( { \ |
| typeof (pos) next = list_entry ( (pos)->member.next, \ |
| typeof ( *(pos) ), \ |
| member ); \ |
| ( ( &next->member == (head) ) ? NULL : next ); } ) |
| |
| /** |
| * Get the container of the previous entry in a list |
| * |
| * @v pos Current list entry |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| * @ret next Next list entry, or NULL at end of list |
| */ |
| #define list_prev_entry( pos, head, member ) ( { \ |
| typeof (pos) prev = list_entry ( (pos)->member.prev, \ |
| typeof ( *(pos) ), \ |
| member ); \ |
| ( ( &prev->member == (head) ) ? NULL : prev ); } ) |
| |
| /** |
| * Test if entry is first in a list |
| * |
| * @v entry List entry |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| * @ret is_first Entry is first in the list |
| */ |
| #define list_is_first_entry( entry, head, member ) \ |
| ( (head)->next == &(entry)->member ) |
| |
| /** |
| * Test if entry is last in a list |
| * |
| * @v entry List entry |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| * @ret is_last Entry is last in the list |
| */ |
| #define list_is_last_entry( entry, head, member ) \ |
| ( (head)->prev == &(entry)->member ) |
| |
| /** |
| * Iterate over a list |
| * |
| * @v pos Iterator |
| * @v head List head |
| */ |
| #define list_for_each( pos, head ) \ |
| for ( list_check ( (head) ), \ |
| pos = (head)->next; \ |
| pos != (head); \ |
| pos = (pos)->next ) |
| |
| /** |
| * Iterate over entries in a list |
| * |
| * @v pos Iterator |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| */ |
| #define list_for_each_entry( pos, head, member ) \ |
| for ( list_check ( (head) ), \ |
| pos = list_entry ( (head)->next, typeof ( *pos ), member ); \ |
| &pos->member != (head); \ |
| pos = list_entry ( pos->member.next, typeof ( *pos ), member ) ) |
| |
| /** |
| * Iterate over entries in a list in reverse order |
| * |
| * @v pos Iterator |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| */ |
| #define list_for_each_entry_reverse( pos, head, member ) \ |
| for ( list_check ( (head) ), \ |
| pos = list_entry ( (head)->prev, typeof ( *pos ), member ); \ |
| &pos->member != (head); \ |
| pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) ) |
| |
| /** |
| * Iterate over entries in a list, safe against deletion of the current entry |
| * |
| * @v pos Iterator |
| * @v tmp Temporary value (of same type as iterator) |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| */ |
| #define list_for_each_entry_safe( pos, tmp, head, member ) \ |
| for ( list_check ( (head) ), \ |
| pos = list_entry ( (head)->next, typeof ( *pos ), member ), \ |
| tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \ |
| &pos->member != (head); \ |
| pos = tmp, \ |
| tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) ) |
| |
| /** |
| * Iterate over entries in a list, starting after current position |
| * |
| * @v pos Iterator |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| */ |
| #define list_for_each_entry_continue( pos, head, member ) \ |
| for ( list_check ( (head) ), \ |
| pos = list_entry ( pos->member.next, typeof ( *pos ), member ); \ |
| &pos->member != (head); \ |
| pos = list_entry ( pos->member.next, typeof ( *pos ), member ) ) |
| |
| /** |
| * Iterate over entries in a list in reverse, starting after current position |
| * |
| * @v pos Iterator |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| */ |
| #define list_for_each_entry_continue_reverse( pos, head, member ) \ |
| for ( list_check ( (head) ), \ |
| pos = list_entry ( pos->member.prev, typeof ( *pos ), member ); \ |
| &pos->member != (head); \ |
| pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) ) |
| |
| /** |
| * Test if list contains a specified entry |
| * |
| * @v entry Entry |
| * @v head List head |
| * @ret present List contains specified entry |
| */ |
| #define list_contains( entry, head ) ( { \ |
| list_check ( (head) ); \ |
| list_check ( (entry) ); \ |
| extern_list_contains ( (entry), (head) ); } ) |
| static inline int inline_list_contains ( struct list_head *entry, |
| struct list_head *head ) { |
| struct list_head *tmp; |
| |
| list_for_each ( tmp, head ) { |
| if ( tmp == entry ) |
| return 1; |
| } |
| return 0; |
| } |
| extern int extern_list_contains ( struct list_head *entry, |
| struct list_head *head ); |
| |
| /** |
| * Test if list contains a specified entry |
| * |
| * @v entry Entry |
| * @v head List head |
| * @ret present List contains specified entry |
| */ |
| #define list_contains_entry( entry, head, member ) \ |
| list_contains ( &(entry)->member, (head) ) |
| |
| /** |
| * Check list contains a specified entry |
| * |
| * @v entry Entry |
| * @v head List head |
| * @v member Name of list field within iterator's type |
| */ |
| #define list_check_contains_entry( entry, head, member ) do { \ |
| assert ( list_contains_entry ( (entry), (head), member ) ); \ |
| } while ( 0 ) |
| |
| #endif /* _IPXE_LIST_H */ |