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
   8 #include <stddef.h> /* offsetof */
   9 #ifndef _LINUX_LIST_H
  10 #define _LINUX_LIST_H
  11
  12 #define container_of(ptr, type, member) ({                      \
  13         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  14         (type *)( (char *)__mptr - offsetof(type,member) );})
  15
  16 /*
  17  * These are non-NULL pointers that will result in page faults
  18  * under normal circumstances, used to verify that nobody uses
  19  * non-initialized list entries.
  20  */
  21 #define LIST_POISON1  ((void *) 0x00100100)
  22 #define LIST_POISON2  ((void *) 0x00200200)
  23
  24 /*
  25  * Simple doubly linked list implementation.
  26  *
  27  * Some of the internal functions ("__xxx") are useful when
  28  * manipulating whole lists rather than single entries, as
  29  * sometimes we already know the next/prev entries and we can
  30  * generate better code by using them directly rather than
  31  * using the generic single-entry routines.
  32  */
  33
  34 struct list_head {
  35         struct list_head *next, *prev;
  36 };
  37
  38 #define INIT_LIST_HEAD(ptr) do { \
  39         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  40 } while (0)
  41
  42 /*
  43  * Insert a new entry between two known consecutive entries.
  44  *
  45  * This is only for internal list manipulation where we know
  46  * the prev/next entries already!
  47  */
  48 static inline void __list_add(struct list_head *new,
  49                               struct list_head *prev,
  50                               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  * add a new entry
  60  *
  61  * \param new: new entry to be added
  62  * \param head: list head to add it after
  63  *
  64  * Insert a new entry after the specified head.
  65  * This is good for implementing stacks.
  66  */
  67 static inline void para_list_add(struct list_head *new, struct list_head *head)
  68 {
  69         __list_add(new, head, head->next);
  70 }
  71
  72 /**
  73  * list_add_tail - add a new entry
  74  * @new: new entry to be added
  75  * @head: list head to add it before
  76  *
  77  * Insert a new entry before the specified head.
  78  * This is useful for implementing queues.
  79  */
  80 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  81 {
  82         __list_add(new, head->prev, head);
  83 }
  84
  85 /*
  86  * Delete a list entry by making the prev/next entries
  87  * point to each other.
  88  *
  89  * This is only for internal list manipulation where we know
  90  * the prev/next entries already!
  91  */
  92 static inline void __list_del(struct list_head * prev, struct list_head * next)
  93 {
  94         next->prev = prev;
  95         prev->next = next;
  96 }
  97
  98 /**
  99  * list_del - deletes entry from list.
 100  * @entry: the element to delete from the list.
 101  * Note: list_empty on entry does not return true after this, the entry is
 102  * in an undefined state.
 103  */
 104 static inline void list_del(struct list_head *entry)
 105 {
 106         __list_del(entry->prev, entry->next);
 107         entry->next = LIST_POISON1;
 108         entry->prev = LIST_POISON2;
 109 }
 110
 111 /**
 112  * list_move - delete from one list and add as another's head
 113  * @list: the entry to move
 114  * @head: the head that will precede our entry
 115  */
 116 static inline void list_move(struct list_head *list, struct list_head *head)
 117 {
 118         __list_del(list->prev, list->next);
 119         para_list_add(list, head);
 120 }
 121
 122 /**
 123  * list_empty - tests whether a list is empty
 124  * @head: the list to test.
 125  */
 126 static inline int list_empty(const struct list_head *head)
 127 {
 128         return head->next == head;
 129 }
 130
 131 /**
 132  * list_entry - get the struct for this entry
 133  * @ptr:        the &struct list_head pointer.
 134  * @type:       the type of the struct this is embedded in.
 135  * @member:     the name of the list_struct within the struct.
 136  */
 137 #define list_entry(ptr, type, member) \
 138         container_of(ptr, type, member)
 139
 140 /**
 141  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 142  * @pos:        the &struct list_head to use as a loop counter.
 143  * @n:          another &struct list_head to use as temporary storage
 144  * @head:       the head for your list.
 145  */
 146 #define list_for_each_safe(pos, n, head) \
 147         for (pos = (head)->next, n = pos->next; pos != (head); \
 148                 pos = n, n = pos->next)
 149
 150 /**
 151  * list_for_each_entry  -       iterate over list of given type
 152  * @pos:        the type * to use as a loop counter.
 153  * @head:       the head for your list.
 154  * @member:     the name of the list_struct within the struct.
 155  */
 156 #define list_for_each_entry(pos, head, member)                          \
 157         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 158              &pos->member != (head);    \
 159              pos = list_entry(pos->member.next, typeof(*pos), member))
 160
 161 /**
 162  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 163  * @pos:        the type * to use as a loop counter.
 164  * @n:          another type * to use as temporary storage
 165  * @head:       the head for your list.
 166  * @member:     the name of the list_struct within the struct.
 167  */
 168 #define list_for_each_entry_safe(pos, n, head, member)                  \
 169         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 170                 n = list_entry(pos->member.next, typeof(*pos), member); \
 171              &pos->member != (head);                                    \
 172              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 173 /**
 174  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 175  *                                    removal of list entry
 176  * @pos:        the type * to use as a loop counter.
 177  * @n:          another type * to use as temporary storage
 178  * @head:       the head for your list.
 179  * @member:     the name of the list_struct within the struct.
 180  */
 181 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 182         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 183                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 184              &pos->member != (head);                                    \
 185              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 186
 187 #endif /* _LIST_H */