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  * list_add - add a new entry
  60  * @new: new entry to be added
  61  * @head: list head to add it after
  62  *
  63  * Insert a new entry after the specified head.
  64  * This is good for implementing stacks.
  65  */
  66 static inline void list_add(struct list_head *new, struct list_head *head)
  67 {
  68         __list_add(new, head, head->next);
  69 }
  70
  71 /**
  72  * list_add_tail - add a new entry
  73  * @new: new entry to be added
  74  * @head: list head to add it before
  75  *
  76  * Insert a new entry before the specified head.
  77  * This is useful for implementing queues.
  78  */
  79 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  80 {
  81         __list_add(new, head->prev, head);
  82 }
  83
  84 /*
  85  * Delete a list entry by making the prev/next entries
  86  * point to each other.
  87  *
  88  * This is only for internal list manipulation where we know
  89  * the prev/next entries already!
  90  */
  91 static inline void __list_del(struct list_head * prev, struct list_head * next)
  92 {
  93         next->prev = prev;
  94         prev->next = next;
  95 }
  96
  97 /**
  98  * list_del - deletes entry from list.
  99  * @entry: the element to delete from the list.
 100  * Note: list_empty on entry does not return true after this, the entry is
 101  * in an undefined state.
 102  */
 103 static inline void list_del(struct list_head *entry)
 104 {
 105         __list_del(entry->prev, entry->next);
 106         entry->next = LIST_POISON1;
 107         entry->prev = LIST_POISON2;
 108 }
 109
 110 /**
 111  * list_move - delete from one list and add as another's head
 112  * @list: the entry to move
 113  * @head: the head that will precede our entry
 114  */
 115 static inline void list_move(struct list_head *list, struct list_head *head)
 116 {
 117         __list_del(list->prev, list->next);
 118         list_add(list, head);
 119 }
 120
 121 /**
 122  * list_empty - tests whether a list is empty
 123  * @head: the list to test.
 124  */
 125 static inline int list_empty(const struct list_head *head)
 126 {
 127         return head->next == head;
 128 }
 129
 130 /**
 131  * list_entry - get the struct for this entry
 132  * @ptr:        the &struct list_head pointer.
 133  * @type:       the type of the struct this is embedded in.
 134  * @member:     the name of the list_struct within the struct.
 135  */
 136 #define list_entry(ptr, type, member) \
 137         container_of(ptr, type, member)
 138
 139 /**
 140  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 141  * @pos:        the &struct list_head to use as a loop counter.
 142  * @n:          another &struct list_head to use as temporary storage
 143  * @head:       the head for your list.
 144  */
 145 #define list_for_each_safe(pos, n, head) \
 146         for (pos = (head)->next, n = pos->next; pos != (head); \
 147                 pos = n, n = pos->next)
 148
 149 /**
 150  * list_for_each_entry  -       iterate over list of given type
 151  * @pos:        the type * to use as a loop counter.
 152  * @head:       the head for your list.
 153  * @member:     the name of the list_struct within the struct.
 154  */
 155 #define list_for_each_entry(pos, head, member)                          \
 156         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 157              &pos->member != (head);    \
 158              pos = list_entry(pos->member.next, typeof(*pos), member))
 159
 160 /**
 161  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 162  * @pos:        the type * to use as a loop counter.
 163  * @n:          another type * to use as temporary storage
 164  * @head:       the head for your list.
 165  * @member:     the name of the list_struct within the struct.
 166  */
 167 #define list_for_each_entry_safe(pos, n, head, member)                  \
 168         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 169                 n = list_entry(pos->member.next, typeof(*pos), member); \
 170              &pos->member != (head);                                    \
 171              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 172 /**
 173  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 174  *                                    removal of list entry
 175  * @pos:        the type * to use as a loop counter.
 176  * @n:          another type * to use as temporary storage
 177  * @head:       the head for your list.
 178  * @member:     the name of the list_struct within the struct.
 179  */
 180 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 181         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 182                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 183              &pos->member != (head);                                    \
 184              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 185
 186 #endif /* _LIST_H */