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  * Insert a new entry after the specified head.
  34  *
  35  * \param new The new entry to add.
  36  * \param head The list head to add it after.
  37  *
  38  * This is good for implementing stacks.
  39  */
  40 static inline void para_list_add(struct list_head *new, struct list_head *head)
  41 {
  42         new->prev = head;
  43         new->next = head->next;
  44         head->next->prev = new;
  45         head->next = new;
  46 }
  47
  48 /**
  49  * Insert a new entry before the specified head.
  50  *
  51  * \param new The new entry to add.
  52  * \param head list head to add it before.
  53  *
  54  * This is useful for implementing queues.
  55  */
  56 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  57 {
  58         new->prev = head->prev;
  59         new->next = head;
  60         head->prev->next = new;
  61         head->prev = new;
  62 }
  63
  64 /*
  65  * These non-NULL pointers result in page faults when dereferenced. This helps
  66  * to catch bugs resulting from using deleted list heads.
  67  */
  68
  69 /** Used for poisoning the next pointer. */
  70 #define LIST_POISON1 ((void *)0x00100100)
  71
  72 /** Used for poisoning the prev pointer. */
  73 #define LIST_POISON2 ((void *)0x00200200)
  74
  75 /**
  76  * Delete an entry from a list.
  77  *
  78  * \param entry The element to delete.
  79  *
  80  * The list entry is in an undefined state after this and \ref list_empty()
  81  * does not return true.
  82  */
  83 static inline void list_del(struct list_head *entry)
  84 {
  85         entry->prev->next = entry->next;
  86         entry->next->prev = entry->prev;
  87         entry->next = LIST_POISON1;
  88         entry->prev = LIST_POISON2;
  89 }
  90
  91 /**
  92  * Delete an entry from one list and add it as another list's head.
  93  *
  94  * \param list The entry to move.
  95  * \param head The head that will precede our entry.
  96  */
  97 static inline void list_move(struct list_head *list, struct list_head *head)
  98 {
  99         list_del(list);
 100         para_list_add(list, head);
 101 }
 102
 103 /**
 104  * Test whether a list contains no entries.
 105  *
 106  * \param head The list to test.
 107  */
 108 static inline int list_empty(const struct list_head *head)
 109 {
 110         return head->next == head;
 111 }
 112
 113 /**
 114  * Get the struct in which this entry is embedded in.
 115  *
 116  * \param ptr The list head pointer.
 117  * \param type The type of containing structure.
 118  * \param member The name of the list head member within the structure.
 119  */
 120 #define list_entry(ptr, type, member) container_of(ptr, type, member)
 121
 122 /**
 123  * Iterate over a list.
 124  *
 125  * \param pos A list head pointer which serves as the iterator.
 126  * \param head The head of the list.
 127  * \param member The name of the list head member within the structure.
 128  */
 129 #define list_for_each_entry(pos, head, member)                          \
 130         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 131              &pos->member != (head);    \
 132              pos = list_entry(pos->member.next, typeof(*pos), member))
 133
 134 /**
 135  * Iterate over list, safe against removal of list entry.
 136  *
 137  * \param pos The iterator.
 138  * \param n A list head pointer which is used as temporary storage.
 139  * \param head The head of the list.
 140  * \param member The name of the list head member within the structure.
 141  */
 142 #define list_for_each_entry_safe(pos, n, head, member)                  \
 143         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 144                 n = list_entry(pos->member.next, typeof(*pos), member); \
 145              &pos->member != (head);                                    \
 146              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 147
 148 /**
 149  * Get the first element of a list.
 150  *
 151  * \param ptr The list head to take the element from.
 152  * \param type The type of the struct this is embedded in.
 153  * \param member The name of the list_struct within the struct.
 154  *
 155  * Note that the list is expected to be non-empty.
 156  */
 157 #define list_first_entry(ptr, type, member) \
 158         list_entry((ptr)->next, type, member)
 159
 160 /**
 161  * Test whether a list has just one entry.
 162  *
 163  * \param head The list to test.
 164  */
 165 static inline int list_is_singular(const struct list_head *head)
 166 {
 167         return !list_empty(head) && (head->next == head->prev);
 168 }