list.h

   1 /*
   2  * Copied from the Linux kernel source tree, version 2.6.13.
   3  *
   4  * Licensed under the GPL v2 as per the whole kernel source tree.
   5  *
   6  */
   7
   8 /** \file list.h doubly linked list implementation */
   9
  10 #include <stddef.h> /* offsetof */
  11
  12 #define container_of(ptr, type, member) ({                      \
  13         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  14         (type *)( (char *)__mptr - offsetof(type,member) );})
  15
  16 /*
  17  * These are non-NULL pointers that will result in page faults
  18  * under normal circumstances, used to verify that nobody uses
  19  * non-initialized list entries.
  20  */
  21 #define LIST_POISON1  ((void *) 0x00100100)
  22 #define LIST_POISON2  ((void *) 0x00200200)
  23
  24 /**
  25  * Simple doubly linked list implementation.
  26  *
  27  * Some of the internal functions ("__xxx") are useful when
  28  * manipulating whole lists rather than single entries, as
  29  * sometimes we already know the next/prev entries and we can
  30  * generate better code by using them directly rather than
  31  * using the generic single-entry routines.
  32  */
  33 struct list_head {
  34         struct list_head *next, *prev;
  35 };
  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 {
  51         next->prev = new;
  52         new->next = next;
  53         new->prev = prev;
  54         prev->next = new;
  55 }
  56
  57 /**
  58  * add a new entry
  59  *
  60  * \param new new entry to be added
  61  * \param head list head to add it after
  62  *
  63  * Insert a new entry after the specified head.
  64  * This is good for implementing stacks.
  65  */
  66 static inline void para_list_add(struct list_head *new, struct list_head *head)
  67 {
  68         __list_add(new, head, head->next);
  69 }
  70
  71 /**
  72  * add a new entry
  73  *
  74  * \param new new entry to be added
  75  * \param head list head to add it before
  76  *
  77  * Insert a new entry before the specified head.
  78  * This is useful for implementing queues.
  79  */
  80 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  81 {
  82         __list_add(new, head->prev, head);
  83 }
  84
  85 /*
  86  * Delete a list entry by making the prev/next entries
  87  * point to each other.
  88  *
  89  * This is only for internal list manipulation where we know
  90  * the prev/next entries already!
  91  */
  92 static inline void __list_del(struct list_head * prev, struct list_head * next)
  93 {
  94         next->prev = prev;
  95         prev->next = next;
  96 }
  97
  98 /**
  99  * Delete entry from list.
 100  *
 101  * \param entry the element to delete from the list.
 102  *
 103  * Note: list_empty on entry does not return true after this, the entry is
 104  * in an undefined state.
 105  */
 106 static inline void list_del(struct list_head *entry)
 107 {
 108         __list_del(entry->prev, entry->next);
 109         entry->next = LIST_POISON1;
 110         entry->prev = LIST_POISON2;
 111 }
 112
 113 /**
 114  * delete from one list and add as another's head
 115  *
 116  * \param list: the entry to move
 117  * \param head: the head that will precede our entry
 118  */
 119 static inline void list_move(struct list_head *list, struct list_head *head)
 120 {
 121         __list_del(list->prev, list->next);
 122         para_list_add(list, head);
 123 }
 124
 125 /**
 126  * test whether a list is empty
 127  *
 128  * \param head the list to test.
 129  */
 130 static inline int list_empty(const struct list_head *head)
 131 {
 132         return head->next == head;
 133 }
 134
 135 /**
 136  * get the struct for this entry
 137  *
 138  * \param ptr the &struct list_head pointer.
 139  * \param type the type of the struct this is embedded in.
 140  * \param member the name of the list_struct within the struct.
 141  */
 142 #define list_entry(ptr, type, member) \
 143         container_of(ptr, type, member)
 144
 145 /**
 146  * iterate over a list safe against removal of list entry
 147  *
 148  * \param pos the &struct list_head to use as a loop counter.
 149  * \param n another &struct list_head to use as temporary storage
 150  * \param head the head for your list.
 151  */
 152 #define list_for_each_safe(pos, n, head) \
 153         for (pos = (head)->next, n = pos->next; pos != (head); \
 154                 pos = n, n = pos->next)
 155
 156 /**
 157  * iterate over list of given type
 158  *
 159  * \param pos the type * to use as a loop counter.
 160  * \param head the head for your list.
 161  * \param member the name of the list_struct within the struct.
 162  */
 163 #define list_for_each_entry(pos, head, member)                          \
 164         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 165              &pos->member != (head);    \
 166              pos = list_entry(pos->member.next, typeof(*pos), member))
 167
 168 /**
 169  * iterate over list of given type safe against removal of list entry
 170  *
 171  * \param pos the type * to use as a loop counter.
 172  * \param n another type * to use as temporary storage
 173  * \param head the head for your list.
 174  * \param member the name of the list_struct within the struct.
 175  */
 176 #define list_for_each_entry_safe(pos, n, head, member)                  \
 177         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 178                 n = list_entry(pos->member.next, typeof(*pos), member); \
 179              &pos->member != (head);                                    \
 180              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 181 /**
 182  * iterate backwards over list of given type safe against removal of list entry
 183  * \param pos the type * to use as a loop counter.
 184  * \param n another type * to use as temporary storage
 185  * \param head the head for your list.
 186  * \param member the name of the list_struct within the struct.
 187  */
 188 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 189         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 190                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 191              &pos->member != (head);                                    \
 192              pos = n, n = list_entry(n->member.prev, typeof(*n), member))