3 * This file is based on include/linux/list.h in the Linux kernel source code.
12 * container_of - cast a member of a structure out to the containing structure
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.
19 #define container_of(ptr, type, member) ({ \
20 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
21 (type *)( (char *)__mptr - offsetof(type,member) );})
26 struct list_head *next, *prev;
29 struct hlist_node *first;
33 struct hlist_node *next, **pprev;
37 * Simple doubly linked list implementation.
39 * Some of the internal functions ("__xxx") are useful when
40 * manipulating whole lists rather than single entries, as
41 * sometimes we already know the next/prev entries and we can
42 * generate better code by using them directly rather than
43 * using the generic single-entry routines.
46 #define LIST_HEAD_INIT(name) { &(name), &(name) }
48 #ifdef LIST_HEAD /* BSD sys/queue.h defines this... */
52 #define LIST_HEAD(name) \
53 struct list_head name = LIST_HEAD_INIT(name)
55 static inline void INIT_LIST_HEAD(struct list_head *list)
62 * Insert a new entry between two known consecutive entries.
64 * This is only for internal list manipulation where we know
65 * the prev/next entries already!
67 static inline void __list_add(struct list_head *new,
68 struct list_head *prev,
69 struct list_head *next)
78 * list_add - add a new entry
79 * @new: new entry to be added
80 * @head: list head to add it after
82 * Insert a new entry after the specified head.
83 * This is good for implementing stacks.
85 static inline void list_add(struct list_head *new, struct list_head *head)
87 __list_add(new, head, head->next);
91 * list_add_tail - add a new entry
92 * @new: new entry to be added
93 * @head: list head to add it before
95 * Insert a new entry before the specified head.
96 * This is useful for implementing queues.
98 static inline void list_add_tail(struct list_head *new, struct list_head *head)
100 __list_add(new, head->prev, head);
104 * Delete a list entry by making the prev/next entries
105 * point to each other.
107 * This is only for internal list manipulation where we know
108 * the prev/next entries already!
110 static inline void __list_del(struct list_head * prev, struct list_head * next)
117 * list_del - deletes entry from list.
118 * @entry: the element to delete from the list.
119 * Note: list_empty() on entry does not return true after this, the entry is
120 * in an undefined state.
122 static inline void list_del(struct list_head *entry)
124 __list_del(entry->prev, entry->next);
128 * list_empty - tests whether a list is empty
129 * @head: the list to test.
131 static inline int list_empty(const struct list_head *head)
133 return head->next == head;
137 * list_entry - get the struct for this entry
138 * @ptr: the &struct list_head pointer.
139 * @type: the type of the struct this is embedded in.
140 * @member: the name of the list_struct within the struct.
142 #define list_entry(ptr, type, member) \
143 container_of(ptr, type, member)
146 * list_for_each - iterate over a list
147 * @pos: the &struct list_head to use as a loop cursor.
148 * @head: the head for your list.
150 #define list_for_each(pos, head) \
151 for (pos = (head)->next; pos != (head); pos = pos->next)
154 * list_for_each_safe - iterate over a list safe against removal of list entry
155 * @pos: the &struct list_head to use as a loop cursor.
156 * @n: another &struct list_head to use as temporary storage
157 * @head: the head for your list.
159 #define list_for_each_safe(pos, n, head) \
160 for (pos = (head)->next, n = pos->next; pos != (head); \
161 pos = n, n = pos->next)
164 * list_for_each_entry - iterate over list of given type
165 * @pos: the type * to use as a loop cursor.
166 * @head: the head for your list.
167 * @member: the name of the list_struct within the struct.
169 #define list_for_each_entry(pos, head, member) \
170 for (pos = list_entry((head)->next, typeof(*pos), member); \
171 &pos->member != (head); \
172 pos = list_entry(pos->member.next, typeof(*pos), member))
175 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
176 * @pos: the type * to use as a loop cursor.
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.
181 #define list_for_each_entry_safe(pos, n, head, member) \
182 for (pos = list_entry((head)->next, typeof(*pos), member), \
183 n = list_entry(pos->member.next, typeof(*pos), member); \
184 &pos->member != (head); \
185 pos = n, n = list_entry(n->member.next, typeof(*n), member))
188 * Double linked lists with a single pointer list head.
189 * Mostly useful for hash tables where the two pointer list head is
191 * You lose the ability to access the tail in O(1).
194 #define HLIST_HEAD_INIT { .first = NULL }
195 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
196 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
197 static inline void INIT_HLIST_NODE(struct hlist_node *h)
203 static inline void hlist_del(struct hlist_node *n)
205 struct hlist_node *next = n->next;
206 struct hlist_node **pprev = n->pprev;
212 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
214 struct hlist_node *first = h->first;
217 first->pprev = &n->next;
219 n->pprev = &h->first;
222 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
224 #define hlist_for_each(pos, head) \
225 for (pos = (head)->first; pos ; pos = pos->next)
227 #define hlist_for_each_safe(pos, n, head) \
228 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
232 * hlist_for_each_entry - iterate over list of given type
233 * @tpos: the type * to use as a loop cursor.
234 * @pos: the &struct hlist_node to use as a loop cursor.
235 * @head: the head for your list.
236 * @member: the name of the hlist_node within the struct.
238 #define hlist_for_each_entry(tpos, pos, head, member) \
239 for (pos = (head)->first; \
241 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
245 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
246 * @tpos: the type * to use as a loop cursor.
247 * @pos: the &struct hlist_node to use as a loop cursor.
248 * @n: another &struct hlist_node to use as temporary storage
249 * @head: the head for your list.
250 * @member: the name of the hlist_node within the struct.
252 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
253 for (pos = (head)->first; \
254 pos && ({ n = pos->next; 1; }) && \
255 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \