Skip to content

Commit

Permalink
[list] Add list functions required by ath9k driver
Browse files Browse the repository at this point in the history 
Originally-implemented-by: Scott K Logan <logans@cottsay.net>
Signed-off-by: Michael Brown <mcb30@ipxe.org>
  • Loading branch information
@mcb30
mcb30 committed Oct 14, 2011
1 parent d40bd11 commit c280530
Show file tree
Hide file tree
Showing 2 changed files with 326 additions and 0 deletions.
154 changes: 154 additions & 0 deletions src/include/ipxe/list.h
View file
Expand Up @@ -145,6 +145,160 @@ static inline int list_empty ( const struct list_head *list ) {
list_check ( (list) ); \
list_empty ( (list) ); } )

/**
* Test whether a list has just one entry
*
* @v list List to test
*/
static inline int list_is_singular ( const struct list_head *list ) {
return ( ( ! list_empty ( list ) ) && ( list->next == list->prev ) );
}
#define list_is_singular( list ) ( { \
list_check ( (list) ); \
list_is_singular ( (list) ); } )

/**
* Test whether an entry is the last entry in list
*
* @v list List entry to test
* @v head List head
*/
static inline int list_is_last ( const struct list_head *list,
const struct list_head *head ) {
return ( list->next == head );
}
#define list_is_last( list, head ) ( { \
list_check ( (list) ); \
list_check ( (head) ); \
list_is_last ( (list), (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.
*/
static inline void 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;
}
}
#define list_cut_position( new, list, entry ) do { \
list_check ( (new) ); \
assert ( list_empty ( (new) ) ); \
list_check ( (list) ); \
list_check ( (entry) ); \
list_cut_position ( (new), (list), (entry) ); \
} while ( 0 )

/**
* 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.
*/
static inline void 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;
}
}
#define list_splice( list, entry ) do { \
list_check ( (list) ); \
list_check ( (entry) ); \
list_splice ( (list), (entry) ); \
} while ( 0 )

/**
* 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.
*/
static inline void 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;
}
}
#define list_splice_tail( list, entry ) do { \
list_check ( (list) ); \
list_check ( (entry) ); \
list_splice_tail ( (list), (entry) ); \
} while ( 0 )

/**
* 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.
*/
static inline void list_splice_init ( struct list_head *list,
struct list_head *entry ) {
list_splice ( list, entry );
INIT_LIST_HEAD ( list );
}
#define list_splice_init( list, entry ) do { \
list_check ( (list) ); \
list_check ( (entry) ); \
list_splice_init ( (list), (entry) ); \
} while ( 0 )

/**
* 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.
*/
static inline void list_splice_tail_init ( struct list_head *list,
struct list_head *entry ) {
list_splice_tail ( list, entry );
INIT_LIST_HEAD ( list );
}
#define list_splice_tail_init( list, entry ) do { \
list_check ( (list) ); \
list_check ( (entry) ); \
list_splice_tail_init ( (list), (entry) ); \
} while ( 0 )

/**
* Get the container of a list entry
*
Expand Down
172 changes: 172 additions & 0 deletions src/tests/list_test.c
View file
Expand Up @@ -124,6 +124,8 @@ static int list_check_contents ( struct list_head *list,
*/
static void list_test_exec ( void ) {
struct list_head *list = &test_list;
struct list_head target_list;
struct list_head *target = &target_list;

/* Test initialiser and list_empty() */
ok ( list_empty ( list ) );
Expand Down Expand Up @@ -153,6 +155,176 @@ static void list_test_exec ( void ) {
list_contents_ok ( list, "" );
ok ( list_empty ( list ) );

/* Test list_is_singular() */
INIT_LIST_HEAD ( list );
ok ( ! list_is_singular ( list ) );
list_add ( &list_tests[1].list, list );
ok ( list_is_singular ( list ) );
list_add ( &list_tests[3].list, list );
ok ( ! list_is_singular ( list ) );
list_del ( &list_tests[1].list );
ok ( list_is_singular ( list ) );

/* Test list_is_last() */
INIT_LIST_HEAD ( list );
list_add_tail ( &list_tests[6].list, list );
ok ( list_is_last ( &list_tests[6].list, list ) );
list_add_tail ( &list_tests[4].list, list );
ok ( list_is_last ( &list_tests[4].list, list ) );
ok ( ! list_is_last ( &list_tests[6].list, list ) );

/* Test list_cut_position() - empty list */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_cut_position ( target, list, list );
list_contents_ok ( list, "" );
list_contents_ok ( target, "" );

/* Test list_cut_position() - singular list, move nothing */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[4].list, list );
list_cut_position ( target, list, list );
list_contents_ok ( list, "4" );
list_contents_ok ( target, "" );

/* Test list_cut_position() - singular list, move singular entry */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[9].list, list );
list_cut_position ( target, list, &list_tests[9].list );
list_contents_ok ( list, "" );
list_contents_ok ( target, "9" );

/* Test list_cut_position() - multi-entry list, move nothing */
INIT_LIST_HEAD ( list );
list_add_tail ( &list_tests[3].list, list );
list_add_tail ( &list_tests[2].list, list );
list_add_tail ( &list_tests[7].list, list );
INIT_LIST_HEAD ( target );
list_cut_position ( target, list, list );
list_contents_ok ( list, "327" );
list_contents_ok ( target, "" );

/* Test list_cut_position() - multi-entry list, move some */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[8].list, list );
list_add_tail ( &list_tests[0].list, list );
list_add_tail ( &list_tests[9].list, list );
list_add_tail ( &list_tests[3].list, list );
list_add_tail ( &list_tests[2].list, list );
list_cut_position ( target, list, &list_tests[0].list );
list_contents_ok ( list, "932" );
list_contents_ok ( target, "80" );

/* Test list_cut_position() - multi-entry list, move everything */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[3].list, list );
list_add_tail ( &list_tests[5].list, list );
list_add_tail ( &list_tests[4].list, list );
list_add_tail ( &list_tests[7].list, list );
list_add_tail ( &list_tests[1].list, list );
list_cut_position ( target, list, &list_tests[1].list );
list_contents_ok ( list, "" );
list_contents_ok ( target, "35471" );

/* Test list_splice() - empty list */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_splice ( list, target );
list_contents_ok ( list, "" );
list_contents_ok ( target, "" );

/* Test list_splice() - both lists empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_splice ( list, target );
list_contents_ok ( target, "" );

/* Test list_splice() - source list empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[1].list, target );
list_add_tail ( &list_tests[3].list, target );
list_splice ( list, &list_tests[1].list );
list_contents_ok ( target, "13" );

/* Test list_splice() - destination list empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[6].list, list );
list_add_tail ( &list_tests[5].list, list );
list_add_tail ( &list_tests[2].list, list );
list_splice ( list, target );
list_contents_ok ( target, "652" );

/* Test list_splice() - both lists non-empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[8].list, list );
list_add_tail ( &list_tests[4].list, list );
list_add_tail ( &list_tests[5].list, list );
list_add_tail ( &list_tests[1].list, target );
list_add_tail ( &list_tests[9].list, target );
list_splice ( list, &list_tests[1].list );
list_contents_ok ( target, "18459" );

/* Test list_splice_tail() - both lists empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_splice_tail ( list, target );
list_contents_ok ( target, "" );

/* Test list_splice_tail() - source list empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[5].list, target );
list_splice_tail ( list, &list_tests[5].list );
list_contents_ok ( target, "5" );

/* Test list_splice_tail() - destination list empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[2].list, list );
list_add_tail ( &list_tests[1].list, list );
list_add_tail ( &list_tests[0].list, list );
list_splice_tail ( list, target );
list_contents_ok ( target, "210" );

/* Test list_splice_tail() - both lists non-empty */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[9].list, list );
list_add_tail ( &list_tests[5].list, list );
list_add_tail ( &list_tests[7].list, list );
list_add_tail ( &list_tests[2].list, target );
list_add_tail ( &list_tests[4].list, target );
list_splice_tail ( list, &list_tests[2].list );
list_contents_ok ( target, "95724" );

/* Test list_splice_init() */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[4].list, list );
list_add_tail ( &list_tests[1].list, target );
list_splice_init ( list, target );
ok ( list_empty ( list ) );
list_contents_ok ( list, "" );
list_contents_ok ( target, "41" );

/* Test list_splice_tail_init() */
INIT_LIST_HEAD ( list );
INIT_LIST_HEAD ( target );
list_add_tail ( &list_tests[3].list, list );
list_add_tail ( &list_tests[2].list, list );
list_add_tail ( &list_tests[5].list, target );
list_splice_tail_init ( list, &list_tests[5].list );
ok ( list_empty ( list ) );
list_contents_ok ( list, "" );
list_contents_ok ( target, "325" );

/* Test list_entry() */
INIT_LIST_HEAD ( &list_tests[3].list ); // for list_check()
ok ( list_entry ( &list_tests[3].list, struct list_test, list )
Expand Down

0 comments on commit c280530

Please sign in to comment.