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