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