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 entry 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 *entry, struct list_head *head)
  41 {
  42         entry->prev = head;
  43         entry->next = head->next;
  44         head->next->prev = entry;
  45         head->next = entry;
  46 }
  47
  48 /**
  49  * Insert a new entry before the specified head.
  50  *
  51  * \param entry 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 *entry, struct list_head *head)
  57 {
  58         entry->prev = head->prev;
  59         entry->next = head;
  60         head->prev->next = entry;
  61         head->prev = entry;
  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 entry The entry to move.
  88  * \param head The head that will precede our entry.
  89  */
  90 static inline void list_move(struct list_head *entry, struct list_head *head)
  91 {
  92         list_del(entry);
  93         para_list_add(entry, 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  * Test whether a list has just one entry.
 108  *
 109  * \param head The list to test.
 110  */
 111 static inline int list_is_singular(const struct list_head *head)
 112 {
 113         return !list_empty(head) && (head->next == head->prev);
 114 }
 115
 116 /**
 117  * Get the struct in which this entry is embedded in.
 118  *
 119  * \param ptr The list head pointer.
 120  * \param type The type of containing structure.
 121  * \param member The name of the list head member within the structure.
 122  */
 123 #define list_entry(ptr, type, member) container_of(ptr, type, member)
 124
 125 /**
 126  * Iterate over a list.
 127  *
 128  * \param pos A struct pointer which serves as the iterator.
 129  * \param head The head of the list.
 130  * \param member The name of the list head member within the structure.
 131  */
 132 #define list_for_each_entry(pos, head, member)                          \
 133         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 134              &pos->member != (head);    \
 135              pos = list_entry(pos->member.next, typeof(*pos), member))
 136
 137 /**
 138  * Iterate over list, safe against removal of list entry.
 139  *
 140  * \param pos The iterator struct pointer.
 141  * \param n A second struct pointer which is used as temporary storage.
 142  * \param head The head of the list.
 143  * \param member The name of the list head member within the structure.
 144  */
 145 #define list_for_each_entry_safe(pos, n, head, member)                  \
 146         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 147                 n = list_entry(pos->member.next, typeof(*pos), member); \
 148              &pos->member != (head);                                    \
 149              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 150
 151 /**
 152  * Get the first element of a list.
 153  *
 154  * \param ptr The list head to take the element from.
 155  * \param type The type of the struct this is embedded in.
 156  * \param member The name of the list_struct within the struct.
 157  *
 158  * Note that the list is expected to be non-empty.
 159  */
 160 #define list_first_entry(ptr, type, member) \
 161         list_entry((ptr)->next, type, member)