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