qemu/roms/ipxe/src/include/ipxe/list.h

   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_ONLY );
  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 )
  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 )
  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 )
 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) ); } )
 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) ); } )
 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) ); } )
 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 )
 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 )
 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 )
 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 )
 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
 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  * Iterate over a list
 353  *
 354  * @v pos               Iterator
 355  * @v head              List head
 356  */
 357 #define list_for_each( pos, head )                                            \
 358         for ( list_check ( (head) ),                                          \
 359               pos = (head)->next;                                             \
 360               pos != (head);                                                  \
 361               pos = (pos)->next )
 362
 363 /**
 364  * Iterate over entries in a list
 365  *
 366  * @v pos               Iterator
 367  * @v head              List head
 368  * @v member            Name of list field within iterator's type
 369  */
 370 #define list_for_each_entry( pos, head, member )                              \
 371         for ( list_check ( (head) ),                                          \
 372               pos = list_entry ( (head)->next, typeof ( *pos ), member );     \
 373               &pos->member != (head);                                         \
 374               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
 375
 376 /**
 377  * Iterate over entries in a list in reverse order
 378  *
 379  * @v pos               Iterator
 380  * @v head              List head
 381  * @v member            Name of list field within iterator's type
 382  */
 383 #define list_for_each_entry_reverse( pos, head, member )                      \
 384         for ( list_check ( (head) ),                                          \
 385               pos = list_entry ( (head)->prev, typeof ( *pos ), member );     \
 386               &pos->member != (head);                                         \
 387               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
 388
 389 /**
 390  * Iterate over entries in a list, safe against deletion of the current entry
 391  *
 392  * @v pos               Iterator
 393  * @v tmp               Temporary value (of same type as iterator)
 394  * @v head              List head
 395  * @v member            Name of list field within iterator's type
 396  */
 397 #define list_for_each_entry_safe( pos, tmp, head, member )                    \
 398         for ( list_check ( (head) ),                                          \
 399               pos = list_entry ( (head)->next, typeof ( *pos ), member ),     \
 400               tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \
 401               &pos->member != (head);                                         \
 402               pos = tmp,                                                      \
 403               tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) )
 404
 405 /**
 406  * Iterate over entries in a list, starting after current position
 407  *
 408  * @v pos               Iterator
 409  * @v head              List head
 410  * @v member            Name of list field within iterator's type
 411  */
 412 #define list_for_each_entry_continue( pos, head, member )                     \
 413         for ( list_check ( (head) ),                                          \
 414               pos = list_entry ( pos->member.next, typeof ( *pos ), member ); \
 415               &pos->member != (head);                                         \
 416               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
 417
 418 /**
 419  * Iterate over entries in a list in reverse, starting after current position
 420  *
 421  * @v pos               Iterator
 422  * @v head              List head
 423  * @v member            Name of list field within iterator's type
 424  */
 425 #define list_for_each_entry_continue_reverse( pos, head, member )             \
 426         for ( list_check ( (head) ),                                          \
 427               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ); \
 428               &pos->member != (head);                                         \
 429               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
 430
 431 /**
 432  * Test if list contains a specified entry
 433  *
 434  * @v entry             Entry
 435  * @v head              List head
 436  * @ret present         List contains specified entry
 437  */
 438 #define list_contains( entry, head ) ( {                        \
 439         list_check ( (head) );                                  \
 440         list_check ( (entry) );                                 \
 441         extern_list_contains ( (entry), (head) ); } )
 442 static inline int inline_list_contains ( struct list_head *entry,
 443                                          struct list_head *head ) {
 444         struct list_head *tmp;
 445
 446         list_for_each ( tmp, head ) {
 447                 if ( tmp == entry )
 448                         return 1;
 449         }
 450         return 0;
 451 }
 452 extern int extern_list_contains ( struct list_head *entry,
 453                                   struct list_head *head );
 454
 455 /**
 456  * Test if list contains a specified entry
 457  *
 458  * @v entry             Entry
 459  * @v head              List head
 460  * @ret present         List contains specified entry
 461  */
 462 #define list_contains_entry( entry, head, member )              \
 463         list_contains ( &(entry)->member, (head) )
 464
 465 /**
 466  * Check list contains a specified entry
 467  *
 468  * @v entry             Entry
 469  * @v head              List head
 470  * @v member            Name of list field within iterator's type
 471  */
 472 #define list_check_contains_entry( entry, head, member ) do {                 \
 473         assert ( list_contains_entry ( (entry), (head), member ) );           \
 474         } while ( 0 )
 475
 476 #endif /* _IPXE_LIST_H */