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