iPXE
list.h
Go to the documentation of this file.
00001 #ifndef _IPXE_LIST_H
00002 #define _IPXE_LIST_H
00003 
00004 /** @file
00005  *
00006  * Linked lists
00007  *
00008  * This linked list handling code is based on the Linux kernel's
00009  * list.h.
00010  */
00011 
00012 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00013 
00014 #include <stddef.h>
00015 #include <assert.h>
00016 
00017 /** A doubly-linked list entry (or list head) */
00018 struct list_head {
00019         /** Next list entry */
00020         struct list_head *next;
00021         /** Previous list entry */
00022         struct list_head *prev;
00023 };
00024 
00025 /**
00026  * Initialise a static list head
00027  *
00028  * @v list              List head
00029  */
00030 #define LIST_HEAD_INIT( list ) { &(list), &(list) }
00031 
00032 /**
00033  * Declare a static list head
00034  *
00035  * @v list              List head
00036  */
00037 #define LIST_HEAD( list ) \
00038         struct list_head list = LIST_HEAD_INIT ( list )
00039 
00040 /**
00041  * Initialise a list head
00042  *
00043  * @v list              List head
00044  */
00045 #define INIT_LIST_HEAD( list ) do {                             \
00046         (list)->next = (list);                                  \
00047         (list)->prev = (list);                                  \
00048         } while ( 0 )
00049 
00050 /**
00051  * Check a list entry or list head is valid
00052  *
00053  * @v list              List entry or head
00054  */
00055 #define list_check( list ) ( {                                  \
00056         assert ( (list) != NULL );                              \
00057         assert ( (list)->prev != NULL );                        \
00058         assert ( (list)->next != NULL );                        \
00059         assert ( (list)->next->prev == (list) );                \
00060         assert ( (list)->prev->next == (list) );                \
00061         } )
00062 
00063 /**
00064  * Add a new entry to the head of a list
00065  *
00066  * @v new               New entry to be added
00067  * @v head              List head, or entry after which to add the new entry
00068  */
00069 #define list_add( new, head ) do {                              \
00070         list_check ( (head) );                                  \
00071         extern_list_add ( (new), (head) );                      \
00072         list_check ( (head) );                                  \
00073         list_check ( (new) );                                   \
00074         } while ( 0 )
00075 static inline void inline_list_add ( struct list_head *new,
00076                                      struct list_head *head ) {
00077         struct list_head *prev = head;
00078         struct list_head *next = head->next;
00079         next->prev = (new);
00080         (new)->next = next;
00081         (new)->prev = prev;
00082         prev->next = (new);
00083 }
00084 extern void extern_list_add ( struct list_head *new,
00085                               struct list_head *head );
00086 
00087 /**
00088  * Add a new entry to the tail of a list
00089  *
00090  * @v new               New entry to be added
00091  * @v head              List head, or entry before which to add the new entry
00092  */
00093 #define list_add_tail( new, head ) do {                         \
00094         list_check ( (head) );                                  \
00095         extern_list_add_tail ( (new), (head) );                 \
00096         list_check ( (head) );                                  \
00097         list_check ( (new) );                                   \
00098         } while ( 0 )
00099 static inline void inline_list_add_tail ( struct list_head *new,
00100                                           struct list_head *head ) {
00101         struct list_head *prev = head->prev;
00102         struct list_head *next = head;
00103         next->prev = (new);
00104         (new)->next = next;
00105         (new)->prev = prev;
00106         prev->next = (new);
00107 }
00108 extern void extern_list_add_tail ( struct list_head *new,
00109                                    struct list_head *head );
00110 
00111 /**
00112  * Delete an entry from a list
00113  *
00114  * @v list              List entry
00115  *
00116  * Note that list_empty() on entry does not return true after this;
00117  * the entry is in an undefined state.
00118  */
00119 #define list_del( list ) do {                                   \
00120         list_check ( (list) );                                  \
00121         inline_list_del ( (list) );                             \
00122         } while ( 0 )
00123 static inline void inline_list_del ( struct list_head *list ) {
00124         struct list_head *next = (list)->next;
00125         struct list_head *prev = (list)->prev;
00126         next->prev = prev;
00127         prev->next = next;
00128 }
00129 extern void extern_list_del ( struct list_head *list );
00130 
00131 /**
00132  * Test whether a list is empty
00133  *
00134  * @v list              List head
00135  */
00136 #define list_empty( list ) ( {                                  \
00137         list_check ( (list) );                                  \
00138         inline_list_empty ( (list) ); } )
00139 static inline int inline_list_empty ( const struct list_head *list ) {
00140         return ( list->next == list );
00141 }
00142 extern int extern_list_empty ( const struct list_head *list );
00143 
00144 /**
00145  * Test whether a list has just one entry
00146  *
00147  * @v list              List to test
00148  */
00149 #define list_is_singular( list ) ( {                            \
00150         list_check ( (list) );                                  \
00151         inline_list_is_singular ( (list) ); } )
00152 static inline int inline_list_is_singular ( const struct list_head *list ) {
00153         return ( ( ! list_empty ( list ) ) && ( list->next == list->prev ) );
00154 }
00155 extern int extern_list_is_singular ( const struct list_head *list );
00156 
00157 /**
00158  * Test whether an entry is the last entry in list
00159  *
00160  * @v list              List entry to test
00161  * @v head              List head
00162  */
00163 #define list_is_last( list, head ) ( {                          \
00164         list_check ( (list) );                                  \
00165         list_check ( (head) );                                  \
00166         inline_list_is_last ( (list), (head) ); } )
00167 static inline int inline_list_is_last ( const struct list_head *list,
00168                                         const struct list_head *head ) {
00169         return ( list->next == head );
00170 }
00171 extern int extern_list_is_last ( const struct list_head *list,
00172                                  const struct list_head *head );
00173 
00174 /**
00175  * Cut a list into two
00176  *
00177  * @v new               A new list to contain all removed entries
00178  * @v list              An existing list
00179  * @v entry             An entry within the existing list
00180  *
00181  * All entries from @c list up to and including @c entry are moved to
00182  * @c new, which should be an empty list.  @c entry may be equal to @c
00183  * list, in which case no entries are moved.
00184  */
00185 #define list_cut_position( new, list, entry ) do {              \
00186         list_check ( (new) );                                   \
00187         assert ( list_empty ( (new) ) );                        \
00188         list_check ( (list) );                                  \
00189         list_check ( (entry) );                                 \
00190         extern_list_cut_position ( (new), (list), (entry) );    \
00191         } while ( 0 )
00192 static inline void inline_list_cut_position ( struct list_head *new,
00193                                               struct list_head *list,
00194                                               struct list_head *entry ) {
00195         struct list_head *first = entry->next;
00196 
00197         if ( list != entry ) {
00198                 new->next = list->next;
00199                 new->next->prev = new;
00200                 new->prev = entry;
00201                 new->prev->next = new;
00202                 list->next = first;
00203                 list->next->prev = list;
00204         }
00205 }
00206 extern void extern_list_cut_position ( struct list_head *new,
00207                                        struct list_head *list,
00208                                        struct list_head *entry );
00209 
00210 /**
00211  * Move all entries from one list into another list
00212  *
00213  * @v list              List of entries to add
00214  * @v entry             Entry after which to add the new entries
00215  *
00216  * All entries from @c list are inserted after @c entry.  Note that @c
00217  * list is left in an undefined state; use @c list_splice_init() if
00218  * you want @c list to become an empty list.
00219  */
00220 #define list_splice( list, entry ) do {                         \
00221         list_check ( (list) );                                  \
00222         list_check ( (entry) );                                 \
00223         extern_list_splice ( (list), (entry) );                 \
00224         } while ( 0 )
00225 static inline void inline_list_splice ( const struct list_head *list,
00226                                         struct list_head *entry ) {
00227         struct list_head *first = list->next;
00228         struct list_head *last = list->prev;
00229 
00230         if ( ! list_empty ( list ) ) {
00231                 last->next = entry->next;
00232                 last->next->prev = last;
00233                 first->prev = entry;
00234                 first->prev->next = first;
00235         }
00236 }
00237 extern void extern_list_splice ( const struct list_head *list,
00238                                  struct list_head *entry );
00239 
00240 /**
00241  * Move all entries from one list into another list
00242  *
00243  * @v list              List of entries to add
00244  * @v entry             Entry before which to add the new entries
00245  *
00246  * All entries from @c list are inserted before @c entry.  Note that @c
00247  * list is left in an undefined state; use @c list_splice_tail_init() if
00248  * you want @c list to become an empty list.
00249  */
00250 #define list_splice_tail( list, entry ) do {                    \
00251         list_check ( (list) );                                  \
00252         list_check ( (entry) );                                 \
00253         extern_list_splice_tail ( (list), (entry) );            \
00254         } while ( 0 )
00255 static inline void inline_list_splice_tail ( const struct list_head *list,
00256                                              struct list_head *entry ) {
00257         struct list_head *first = list->next;
00258         struct list_head *last = list->prev;
00259 
00260         if ( ! list_empty ( list ) ) {
00261                 first->prev = entry->prev;
00262                 first->prev->next = first;
00263                 last->next = entry;
00264                 last->next->prev = last;
00265         }
00266 }
00267 extern void extern_list_splice_tail ( const struct list_head *list,
00268                                       struct list_head *entry );
00269 
00270 /**
00271  * Move all entries from one list into another list and reinitialise empty list
00272  *
00273  * @v list              List of entries to add
00274  * @v entry             Entry after which to add the new entries
00275  *
00276  * All entries from @c list are inserted after @c entry.
00277  */
00278 #define list_splice_init( list, entry ) do {                    \
00279         list_check ( (list) );                                  \
00280         list_check ( (entry) );                                 \
00281         extern_list_splice_init ( (list), (entry) );            \
00282         } while ( 0 )
00283 static inline void inline_list_splice_init ( struct list_head *list,
00284                                              struct list_head *entry ) {
00285         list_splice ( list, entry );
00286         INIT_LIST_HEAD ( list );
00287 }
00288 extern void extern_list_splice_init ( struct list_head *list,
00289                                       struct list_head *entry );
00290 
00291 /**
00292  * Move all entries from one list into another list and reinitialise empty list
00293  *
00294  * @v list              List of entries to add
00295  * @v entry             Entry before which to add the new entries
00296  *
00297  * All entries from @c list are inserted before @c entry.
00298  */
00299 #define list_splice_tail_init( list, entry ) do {               \
00300         list_check ( (list) );                                  \
00301         list_check ( (entry) );                                 \
00302         extern_list_splice_tail_init ( (list), (entry) );       \
00303         } while ( 0 )
00304 
00305 static inline void inline_list_splice_tail_init ( struct list_head *list,
00306                                                   struct list_head *entry ) {
00307         list_splice_tail ( list, entry );
00308         INIT_LIST_HEAD ( list );
00309 }
00310 extern void extern_list_splice_tail_init ( struct list_head *list,
00311                                            struct list_head *entry );
00312 
00313 /**
00314  * Get the container of a list entry
00315  *
00316  * @v list              List entry
00317  * @v type              Containing type
00318  * @v member            Name of list field within containing type
00319  * @ret container       Containing object
00320  */
00321 #define list_entry( list, type, member ) ( {                    \
00322         list_check ( (list) );                                  \
00323         container_of ( list, type, member ); } )
00324 
00325 /**
00326  * Get the container of the first entry in a list
00327  *
00328  * @v list              List head
00329  * @v type              Containing type
00330  * @v member            Name of list field within containing type
00331  * @ret first           First list entry, or NULL
00332  */
00333 #define list_first_entry( list, type, member )                  \
00334         ( list_empty ( (list) ) ?                               \
00335           ( type * ) NULL :                                     \
00336           list_entry ( (list)->next, type, member ) )
00337 
00338 /**
00339  * Get the container of the last entry in a list
00340  *
00341  * @v list              List head
00342  * @v type              Containing type
00343  * @v member            Name of list field within containing type
00344  * @ret first           First list entry, or NULL
00345  */
00346 #define list_last_entry( list, type, member )                   \
00347         ( list_empty ( (list) ) ?                               \
00348           ( type * ) NULL :                                     \
00349           list_entry ( (list)->prev, type, member ) )
00350 
00351 /**
00352  * Get the container of the next entry in a list
00353  *
00354  * @v pos               Current list entry
00355  * @v head              List head
00356  * @v member            Name of list field within iterator's type
00357  * @ret next            Next list entry, or NULL at end of list
00358  */
00359 #define list_next_entry( pos, head, member ) ( {                \
00360         typeof (pos) next = list_entry ( (pos)->member.next,    \
00361                                          typeof ( *(pos) ),     \
00362                                          member );              \
00363         ( ( &next->member == (head) ) ? NULL : next ); } )
00364 
00365 /**
00366  * Get the container of the previous entry in a list
00367  *
00368  * @v pos               Current list entry
00369  * @v head              List head
00370  * @v member            Name of list field within iterator's type
00371  * @ret next            Next list entry, or NULL at end of list
00372  */
00373 #define list_prev_entry( pos, head, member ) ( {                \
00374         typeof (pos) prev = list_entry ( (pos)->member.prev,    \
00375                                          typeof ( *(pos) ),     \
00376                                          member );              \
00377         ( ( &prev->member == (head) ) ? NULL : prev ); } )
00378 
00379 /**
00380  * Test if entry is first in a list
00381  *
00382  * @v entry             List entry
00383  * @v head              List head
00384  * @v member            Name of list field within iterator's type
00385  * @ret is_first        Entry is first in the list
00386  */
00387 #define list_is_first_entry( entry, head, member )              \
00388         ( (head)->next == &(entry)->member )
00389 
00390 /**
00391  * Test if entry is last in a list
00392  *
00393  * @v entry             List entry
00394  * @v head              List head
00395  * @v member            Name of list field within iterator's type
00396  * @ret is_last         Entry is last in the list
00397  */
00398 #define list_is_last_entry( entry, head, member )               \
00399         ( (head)->prev == &(entry)->member )
00400 
00401 /**
00402  * Iterate over a list
00403  *
00404  * @v pos               Iterator
00405  * @v head              List head
00406  */
00407 #define list_for_each( pos, head )                                            \
00408         for ( list_check ( (head) ),                                          \
00409               pos = (head)->next;                                             \
00410               pos != (head);                                                  \
00411               pos = (pos)->next )
00412 
00413 /**
00414  * Iterate over entries in a list
00415  *
00416  * @v pos               Iterator
00417  * @v head              List head
00418  * @v member            Name of list field within iterator's type
00419  */
00420 #define list_for_each_entry( pos, head, member )                              \
00421         for ( list_check ( (head) ),                                          \
00422               pos = list_entry ( (head)->next, typeof ( *pos ), member );     \
00423               &pos->member != (head);                                         \
00424               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
00425 
00426 /**
00427  * Iterate over entries in a list in reverse order
00428  *
00429  * @v pos               Iterator
00430  * @v head              List head
00431  * @v member            Name of list field within iterator's type
00432  */
00433 #define list_for_each_entry_reverse( pos, head, member )                      \
00434         for ( list_check ( (head) ),                                          \
00435               pos = list_entry ( (head)->prev, typeof ( *pos ), member );     \
00436               &pos->member != (head);                                         \
00437               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
00438 
00439 /**
00440  * Iterate over entries in a list, safe against deletion of the current entry
00441  *
00442  * @v pos               Iterator
00443  * @v tmp               Temporary value (of same type as iterator)
00444  * @v head              List head
00445  * @v member            Name of list field within iterator's type
00446  */
00447 #define list_for_each_entry_safe( pos, tmp, head, member )                    \
00448         for ( list_check ( (head) ),                                          \
00449               pos = list_entry ( (head)->next, typeof ( *pos ), member ),     \
00450               tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \
00451               &pos->member != (head);                                         \
00452               pos = tmp,                                                      \
00453               tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) )
00454 
00455 /**
00456  * Iterate over entries in a list, starting after current position
00457  *
00458  * @v pos               Iterator
00459  * @v head              List head
00460  * @v member            Name of list field within iterator's type
00461  */
00462 #define list_for_each_entry_continue( pos, head, member )                     \
00463         for ( list_check ( (head) ),                                          \
00464               pos = list_entry ( pos->member.next, typeof ( *pos ), member ); \
00465               &pos->member != (head);                                         \
00466               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
00467 
00468 /**
00469  * Iterate over entries in a list in reverse, starting after current position
00470  *
00471  * @v pos               Iterator
00472  * @v head              List head
00473  * @v member            Name of list field within iterator's type
00474  */
00475 #define list_for_each_entry_continue_reverse( pos, head, member )             \
00476         for ( list_check ( (head) ),                                          \
00477               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ); \
00478               &pos->member != (head);                                         \
00479               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
00480 
00481 /**
00482  * Test if list contains a specified entry
00483  *
00484  * @v entry             Entry
00485  * @v head              List head
00486  * @ret present         List contains specified entry
00487  */
00488 #define list_contains( entry, head ) ( {                        \
00489         list_check ( (head) );                                  \
00490         list_check ( (entry) );                                 \
00491         extern_list_contains ( (entry), (head) ); } )
00492 static inline int inline_list_contains ( struct list_head *entry,
00493                                          struct list_head *head ) {
00494         struct list_head *tmp;
00495 
00496         list_for_each ( tmp, head ) {
00497                 if ( tmp == entry )
00498                         return 1;
00499         }
00500         return 0;
00501 }
00502 extern int extern_list_contains ( struct list_head *entry,
00503                                   struct list_head *head );
00504 
00505 /**
00506  * Test if list contains a specified entry
00507  *
00508  * @v entry             Entry
00509  * @v head              List head
00510  * @ret present         List contains specified entry
00511  */
00512 #define list_contains_entry( entry, head, member )              \
00513         list_contains ( &(entry)->member, (head) )
00514 
00515 /**
00516  * Check list contains a specified entry
00517  *
00518  * @v entry             Entry
00519  * @v head              List head
00520  * @v member            Name of list field within iterator's type
00521  */
00522 #define list_check_contains_entry( entry, head, member ) do {                 \
00523         assert ( list_contains_entry ( (entry), (head), member ) );           \
00524         } while ( 0 )
00525 
00526 #endif /* _IPXE_LIST_H */