src/include/gpxe/list.h

   1 #ifndef _GPXE_LIST_H
   2 #define _GPXE_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 /*
  18  * Simple doubly linked list implementation.
  19  *
  20  * Some of the internal functions ("__xxx") are useful when
  21  * manipulating whole lists rather than single entries, as
  22  * sometimes we already know the next/prev entries and we can
  23  * generate better code by using them directly rather than
  24  * using the generic single-entry routines.
  25  */
  26
  27 struct list_head {
  28         struct list_head *next;
  29         struct list_head *prev;
  30 };
  31
  32 #define LIST_HEAD_INIT( name ) { &(name), &(name) }
  33
  34 #define LIST_HEAD( name ) \
  35         struct list_head name = LIST_HEAD_INIT ( name )
  36
  37 #define INIT_LIST_HEAD( ptr ) do { \
  38         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  39 } while ( 0 )
  40
  41 /*
  42  * Insert a new entry between two known consecutive entries.
  43  *
  44  * This is only for internal list manipulation where we know
  45  * the prev/next entries already!
  46  */
  47 static inline void __list_add ( struct list_head *new,
  48                                 struct list_head *prev,
  49                                 struct list_head *next ) {
  50         next->prev = new;
  51         new->next = next;
  52         new->prev = prev;
  53         prev->next = new;
  54 }
  55
  56 /**
  57  * Add a new entry to the head of a list
  58  *
  59  * @v new       New entry to be added
  60  * @v head      List head to add it after
  61  *
  62  * Insert a new entry after the specified head.  This is good for
  63  * implementing stacks.
  64  */
  65 static inline void list_add ( struct list_head *new, struct list_head *head ) {
  66         __list_add ( new, head, head->next );
  67 }
  68 #define list_add( new, head ) do {                      \
  69         assert ( (head)->next->prev == (head) );        \
  70         assert ( (head)->prev->next == (head) );        \
  71         list_add ( (new), (head) );                     \
  72         } while ( 0 )
  73
  74 /**
  75  * Add a new entry to the tail of a list
  76  *
  77  * @v new       New entry to be added
  78  * @v head      List head to add it before
  79  *
  80  * Insert a new entry before the specified head.  This is useful for
  81  * implementing queues.
  82  */
  83 static inline void list_add_tail ( struct list_head *new,
  84                                    struct list_head *head ) {
  85         __list_add ( new, head->prev, head );
  86 }
  87 #define list_add_tail( new, head ) do {                 \
  88         assert ( (head)->next->prev == (head) );        \
  89         assert ( (head)->prev->next == (head) );        \
  90         list_add_tail ( (new), (head) );                \
  91         } while ( 0 )
  92
  93 /*
  94  * Delete a list entry by making the prev/next entries
  95  * point to each other.
  96  *
  97  * This is only for internal list manipulation where we know
  98  * the prev/next entries already!
  99  */
 100 static inline void __list_del ( struct list_head * prev,
 101                                 struct list_head * next ) {
 102         next->prev = prev;
 103         prev->next = next;
 104 }
 105
 106 /**
 107  * Delete an entry from a list
 108  *
 109  * @v entry     Element to delete from the list
 110  *
 111  * Note that list_empty() on entry does not return true after this;
 112  * the entry is in an undefined state.
 113  */
 114 static inline void list_del ( struct list_head *entry ) {
 115         __list_del ( entry->prev, entry->next );
 116 }
 117 #define list_del( entry ) do {                          \
 118         assert ( (entry)->prev != NULL );               \
 119         assert ( (entry)->next != NULL );               \
 120         assert ( (entry)->next->prev == (entry) );      \
 121         assert ( (entry)->prev->next == (entry) );      \
 122         list_del ( (entry) );                           \
 123         } while ( 0 )
 124
 125 /**
 126  * Test whether a list is empty
 127  *
 128  * @v head      List to test.
 129  */
 130 static inline int list_empty ( const struct list_head *head ) {
 131         return head->next == head;
 132 }
 133
 134 /**
 135  * Get the containing struct for this entry
 136  *
 137  * @v ptr       The struct list_head pointer
 138  * @v type      The type of the struct this is embedded in
 139  * @v member    The name of the list_struct within the struct
 140  */
 141 #define list_entry( ptr, type, member ) \
 142         container_of ( ptr, type, member )
 143
 144 /**
 145  * Iterate over a list
 146  *
 147  * @v pos       The &struct list_head to use as a loop counter
 148  * @v head      The head for your list
 149  */
 150 #define list_for_each( pos, head ) \
 151         for ( pos = (head)->next; pos != (head); pos = pos->next )
 152
 153 /**
 154  * Iterate over entries in a list
 155  *
 156  * @v pos       The type * to use as a loop counter
 157  * @v head      The head for your list
 158  * @v member    The name of the list_struct within the struct
 159  */
 160 #define list_for_each_entry( pos, head, member )                              \
 161         for ( pos = list_entry ( (head)->next, typeof ( *pos ), member );     \
 162               &pos->member != (head);                                         \
 163               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
 164
 165 /**
 166  * Iterate over entries in a list in reverse order
 167  *
 168  * @v pos       The type * to use as a loop counter
 169  * @v head      The head for your list
 170  * @v member    The name of the list_struct within the struct
 171  */
 172 #define list_for_each_entry_reverse( pos, head, member )                      \
 173         for ( pos = list_entry ( (head)->prev, typeof ( *pos ), member );     \
 174               &pos->member != (head);                                         \
 175               pos = list_entry ( pos->member.prev, typeof ( *pos ), member ) )
 176
 177 /**
 178  * Iterate over entries in a list, safe against deletion of entries
 179  *
 180  * @v pos       The type * to use as a loop counter
 181  * @v tmp       Another type * to use for temporary storage
 182  * @v head      The head for your list
 183  * @v member    The name of the list_struct within the struct
 184  */
 185 #define list_for_each_entry_safe( pos, tmp, head, member )                    \
 186         for ( pos = list_entry ( (head)->next, typeof ( *pos ), member ),     \
 187               tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \
 188               &pos->member != (head);                                         \
 189               pos = tmp,                                                      \
 190               tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) )
 191
 192 #endif /* _GPXE_LIST_H */