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