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