2 * Simple doubly linked list implementation.
4 * Based on list.h in the Linux kernel source tree, licensed under
5 * the GNU GPL version 2.
13 * @ptr: the pointer to the member.
14 * @type: the type of the container struct this is embedded in.
15 * @member: the name of the member within the struct.
17 * cast a member of a structure out to the containing structure
19 #define container_of(ptr, type, member) ({ \
20 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
21 (type *)( (char *)__mptr - offsetof(type,member) );})
24 * These are non-NULL pointers that will result in page faults
25 * under normal circumstances, used to verify that nobody uses
26 * non-initialized list entries.
28 #define LIST_POISON1 ((void *) 0x00100100)
29 #define LIST_POISON2 ((void *) 0x00200200)
32 struct list_head *next, *prev;
35 #define LIST_HEAD_INIT(name) { &(name), &(name) }
37 #define LIST_HEAD(name) \
38 struct list_head name = LIST_HEAD_INIT(name)
40 #define INIT_LIST_HEAD(ptr) do { \
41 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
44 /* Insert a new entry between two known consecutive entries. */
45 static inline void __list_add(struct list_head *new,
46 struct list_head *prev,
47 struct list_head *next)
57 * @new: new entry to be added
58 * @head: list head to add it after
60 * Insert a new entry after the specified head.
61 * This is good for implementing stacks.
63 static inline void list_add(struct list_head *new, struct list_head *head)
65 __list_add(new, head, head->next);
70 * @new: new entry to be added
71 * @head: list head to add it before
73 * Insert a new entry before the specified head.
74 * This is useful for implementing queues.
76 static inline void list_add_tail(struct list_head *new, struct list_head *head)
78 __list_add(new, head->prev, head);
82 * Delete a list entry by making the prev/next entries
83 * point to each other.
85 static inline void __list_del(struct list_head * prev, struct list_head * next)
93 * @entry: the element to delete from the list.
95 * deletes entry from list.
97 * Note: list_empty on entry does not return true after this, the entry is
98 * in an undefined state.
100 static inline void list_del(struct list_head *entry)
102 __list_del(entry->prev, entry->next);
103 entry->next = LIST_POISON1;
104 entry->prev = LIST_POISON2;
109 * @list: the entry to move
110 * @head: the head that will precede our entry
111 * delete from one list and add as another's head
113 static inline void list_move(struct list_head *list, struct list_head *head)
115 __list_del(list->prev, list->next);
116 list_add(list, head);
121 * @list: the entry to move
122 * @head: the head that will follow our entry
124 * delete from one list and add as another's tail
126 static inline void list_move_tail(struct list_head *list,
127 struct list_head *head)
129 __list_del(list->prev, list->next);
130 list_add_tail(list, head);
135 * @head: the list to test.
137 * tests whether a list is empty
139 static inline int list_empty(struct list_head *head)
141 return head->next == head;
146 * @ptr: the &struct list_head pointer.
147 * @type: the type of the struct this is embedded in.
148 * @member: the name of the list_struct within the struct.
150 * get the struct for this entry
152 #define list_entry(ptr, type, member) \
153 container_of(ptr, type, member)
156 * list_for_each_entry:
157 * @pos: the type * to use as a loop counter.
158 * @head: the head for your list.
159 * @member: the name of the list_struct within the struct.
161 * iterate over list of given type
163 #define list_for_each_entry(pos, head, member) \
164 for (pos = list_entry((head)->next, typeof(*pos), member); \
165 &pos->member != (head); \
166 pos = list_entry(pos->member.next, typeof(*pos), member))
169 * list_for_each_entry_safe:
170 * @pos: the type * to use as a loop counter.
171 * @n: another type * to use as temporary storage
172 * @head: the head for your list.
173 * @member: the name of the list_struct within the struct.
175 * iterate over list of given type safe against removal of list entry
177 #define list_for_each_entry_safe(pos, n, head, member) \
178 for (pos = list_entry((head)->next, typeof(*pos), member), \
179 n = list_entry(pos->member.next, typeof(*pos), member); \
180 &pos->member != (head); \
181 pos = n, n = list_entry(n->member.next, typeof(*n), member))