#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_ONLY );
#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) ); \
} )
/**
* Insert a list entry between two known consecutive entries
*
* @v new New list entry
* @v prev Previous list entry
* @v next Next list entry
*/
static inline void __list_add ( struct list_head *new,
struct list_head *prev,
struct list_head *next ) {
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* 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
*/
static inline void list_add ( struct list_head *new, struct list_head *head ) {
__list_add ( new, head, head->next );
}
#define list_add( new, head ) do { \
list_check ( (head) ); \
list_add ( (new), (head) ); \
} while ( 0 )
/**
* 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
*/
static inline void list_add_tail ( struct list_head *new,
struct list_head *head ) {
__list_add ( new, head->prev, head );
}
#define list_add_tail( new, head ) do { \
list_check ( (head) ); \
list_add_tail ( (new), (head) ); \
} while ( 0 )
/**
* Delete a list entry between two known consecutive entries
*
* @v prev Previous list entry
* @v next Next list entry
*/
static inline void __list_del ( struct list_head *prev,
struct list_head *next ) {
next->prev = prev;
prev->next = next;
}
/**
* 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.
*/
static inline void list_del ( struct list_head *list ) {
__list_del ( list->prev, list->next );
}
#define list_del( list ) do { \
list_check ( (list) ); \
list_del ( (list) ); \
} while ( 0 )
/**
* Test whether a list is empty
*
* @v list List head
*/
static inline int list_empty ( const struct list_head *list ) {
return ( list->next == list );
}
#define list_empty( list ) ( { \
list_check ( (list) ); \
list_empty ( (list) ); } )
/**
* 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 ) )
/**
* 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 ) )
/**
* 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, head, member ) do { \
if ( ASSERTING ) { \
typeof ( entry ) tmp; \
int found = 0; \
list_for_each_entry ( tmp, head, member ) { \
if ( tmp == entry ) \
found = 1; \
} \
assert ( found ); \
} \
} while ( 0 )
#endif /* _IPXE_LIST_H */
