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