6 * container_of - cast a member of a structure out to the containing structure
7 * @ptr: the pointer to the member.
8 * @type: the type of the container struct this is embedded in.
9 * @member: the name of the member within the struct.
13 #define container_of(ptr, type, member) ( \
14 (type *)( (char *)ptr - offsetof(type,member) ))
19 * Simple doubly linked list implementation.
21 * Some of the internal functions ("__xxx") are useful when
22 * manipulating whole lists rather than single entries, as
23 * sometimes we already know the next/prev entries and we can
24 * generate better code by using them directly rather than
25 * using the generic single-entry routines.
29 struct list_head
*next
, *prev
;
32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
34 #define LIST_HEAD(name) \
35 struct list_head name = LIST_HEAD_INIT(name)
37 static inline void INIT_LIST_HEAD(struct list_head
*list
)
44 * Insert a new entry between two known consecutive entries.
46 * This is only for internal list manipulation where we know
47 * the prev/next entries already!
49 static inline void __list_add(struct list_head
*new,
50 struct list_head
*prev
,
51 struct list_head
*next
)
60 * list_add - add a new entry
61 * @new: new entry to be added
62 * @head: list head to add it after
64 * Insert a new entry after the specified head.
65 * This is good for implementing stacks.
67 static inline void list_add(struct list_head
*new, struct list_head
*head
)
69 __list_add(new, head
, head
->next
);
74 * list_add_tail - add a new entry
75 * @new: new entry to be added
76 * @head: list head to add it before
78 * Insert a new entry before the specified head.
79 * This is useful for implementing queues.
81 static inline void list_add_tail(struct list_head
*new, struct list_head
*head
)
83 __list_add(new, head
->prev
, head
);
88 * Delete a list entry by making the prev/next entries
89 * point to each other.
91 * This is only for internal list manipulation where we know
92 * the prev/next entries already!
94 static inline void __list_del(struct list_head
* prev
, struct list_head
* next
)
101 * list_del - deletes entry from list.
102 * @entry: the element to delete from the list.
103 * Note: list_empty() on entry does not return true after this, the entry is
104 * in an undefined state.
106 static inline void list_del(struct list_head
*entry
)
108 __list_del(entry
->prev
, entry
->next
);
114 * list_replace - replace old entry by new one
115 * @old : the element to be replaced
116 * @new : the new element to insert
118 * If @old was empty, it will be overwritten.
120 static inline void list_replace(struct list_head
*old
,
121 struct list_head
*new)
123 new->next
= old
->next
;
124 new->next
->prev
= new;
125 new->prev
= old
->prev
;
126 new->prev
->next
= new;
129 static inline void list_replace_init(struct list_head
*old
,
130 struct list_head
*new)
132 list_replace(old
, new);
137 * list_del_init - deletes entry from list and reinitialize it.
138 * @entry: the element to delete from the list.
140 static inline void list_del_init(struct list_head
*entry
)
142 __list_del(entry
->prev
, entry
->next
);
143 INIT_LIST_HEAD(entry
);
147 * list_move - delete from one list and add as another's head
148 * @list: the entry to move
149 * @head: the head that will precede our entry
151 static inline void list_move(struct list_head
*list
, struct list_head
*head
)
153 __list_del(list
->prev
, list
->next
);
154 list_add(list
, head
);
158 * list_move_tail - delete from one list and add as another's tail
159 * @list: the entry to move
160 * @head: the head that will follow our entry
162 static inline void list_move_tail(struct list_head
*list
,
163 struct list_head
*head
)
165 __list_del(list
->prev
, list
->next
);
166 list_add_tail(list
, head
);
170 * list_is_last - tests whether @list is the last entry in list @head
171 * @list: the entry to test
172 * @head: the head of the list
174 static inline int list_is_last(const struct list_head
*list
,
175 const struct list_head
*head
)
177 return list
->next
== head
;
181 * list_empty - tests whether a list is empty
182 * @head: the list to test.
184 static inline int list_empty(const struct list_head
*head
)
186 return head
->next
== head
;
190 * list_empty_careful - tests whether a list is empty and not being modified
191 * @head: the list to test
194 * tests whether a list is empty _and_ checks that no other CPU might be
195 * in the process of modifying either member (next or prev)
197 * NOTE: using list_empty_careful() without synchronization
198 * can only be safe if the only activity that can happen
199 * to the list entry is list_del_init(). Eg. it cannot be used
200 * if another CPU could re-list_add() it.
202 static inline int list_empty_careful(const struct list_head
*head
)
204 struct list_head
*next
= head
->next
;
205 return (next
== head
) && (next
== head
->prev
);
208 static inline void __list_splice(struct list_head
*list
,
209 struct list_head
*head
)
211 struct list_head
*first
= list
->next
;
212 struct list_head
*last
= list
->prev
;
213 struct list_head
*at
= head
->next
;
223 * list_splice - join two lists
224 * @list: the new list to add.
225 * @head: the place to add it in the first list.
227 static inline void list_splice(struct list_head
*list
, struct list_head
*head
)
229 if (!list_empty(list
))
230 __list_splice(list
, head
);
234 * list_splice_init - join two lists and reinitialise the emptied list.
235 * @list: the new list to add.
236 * @head: the place to add it in the first list.
238 * The list at @list is reinitialised
240 static inline void list_splice_init(struct list_head
*list
,
241 struct list_head
*head
)
243 if (!list_empty(list
)) {
244 __list_splice(list
, head
);
245 INIT_LIST_HEAD(list
);
250 * list_entry - get the struct for this entry
251 * @ptr: the &struct list_head pointer.
252 * @type: the type of the struct this is embedded in.
253 * @member: the name of the list_struct within the struct.
255 #define list_entry(ptr, type, member) \
256 container_of(ptr, type, member)
259 * list_first_entry - get the first element from a list
260 * @ptr: the list head to take the element from.
261 * @type: the type of the struct this is embedded in.
262 * @member: the name of the list_struct within the struct.
264 * Note, that list is expected to be not empty.
266 #define list_first_entry(ptr, type, member) \
267 list_entry((ptr)->next, type, member)
270 * list_for_each - iterate over a list
271 * @pos: the &struct list_head to use as a loop cursor.
272 * @head: the head for your list.
274 #define list_for_each(pos, head) \
275 for (pos = (head)->next; pos != (head); \
279 * __list_for_each - iterate over a list
280 * @pos: the &struct list_head to use as a loop cursor.
281 * @head: the head for your list.
283 * This variant differs from list_for_each() in that it's the
284 * simplest possible list iteration code, no prefetching is done.
285 * Use this for code that knows the list to be very short (empty
286 * or 1 entry) most of the time.
288 #define __list_for_each(pos, head) \
289 for (pos = (head)->next; pos != (head); pos = pos->next)
292 * list_for_each_prev - iterate over a list backwards
293 * @pos: the &struct list_head to use as a loop cursor.
294 * @head: the head for your list.
296 #define list_for_each_prev(pos, head) \
297 for (pos = (head)->prev; pos != (head); \
301 * list_for_each_safe - iterate over a list safe against removal of list entry
302 * @pos: the &struct list_head to use as a loop cursor.
303 * @n: another &struct list_head to use as temporary storage
304 * @head: the head for your list.
306 #define list_for_each_safe(pos, n, head) \
307 for (pos = (head)->next, n = pos->next; pos != (head); \
308 pos = n, n = pos->next)
311 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
312 * @pos: the &struct list_head to use as a loop cursor.
313 * @n: another &struct list_head to use as temporary storage
314 * @head: the head for your list.
316 #define list_for_each_prev_safe(pos, n, head) \
317 for (pos = (head)->prev, n = pos->prev; \
319 pos = n, n = pos->prev)
322 * list_for_each_entry - iterate over list of given type
323 * @pos: the type * to use as a loop cursor.
324 * @head: the head for your list.
325 * @member: the name of the list_struct within the struct.
327 #define list_for_each_entry(pos, head, member) \
328 for (pos = list_entry((head)->next, typeof(*pos), member); \
329 &pos->member != (head); \
330 pos = list_entry(pos->member.next, typeof(*pos), member))
333 * list_for_each_entry_reverse - iterate backwards over list of given type.
334 * @pos: the type * to use as a loop cursor.
335 * @head: the head for your list.
336 * @member: the name of the list_struct within the struct.
338 #define list_for_each_entry_reverse(pos, head, member) \
339 for (pos = list_entry((head)->prev, typeof(*pos), member); \
340 &pos->member != (head); \
341 pos = list_entry(pos->member.prev, typeof(*pos), member))
344 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
345 * @pos: the type * to use as a start point
346 * @head: the head of the list
347 * @member: the name of the list_struct within the struct.
349 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
351 #define list_prepare_entry(pos, head, member) \
352 ((pos) ? : list_entry(head, typeof(*pos), member))
355 * list_for_each_entry_continue - continue iteration over list of given type
356 * @pos: the type * to use as a loop cursor.
357 * @head: the head for your list.
358 * @member: the name of the list_struct within the struct.
360 * Continue to iterate over list of given type, continuing after
361 * the current position.
363 #define list_for_each_entry_continue(pos, head, member) \
364 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
365 &pos->member != (head); \
366 pos = list_entry(pos->member.next, typeof(*pos), member))
369 * list_for_each_entry_continue_reverse - iterate backwards from the given point
370 * @pos: the type * to use as a loop cursor.
371 * @head: the head for your list.
372 * @member: the name of the list_struct within the struct.
374 * Start to iterate over list of given type backwards, continuing after
375 * the current position.
377 #define list_for_each_entry_continue_reverse(pos, head, member) \
378 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
379 &pos->member != (head); \
380 pos = list_entry(pos->member.prev, typeof(*pos), member))
383 * list_for_each_entry_from - iterate over list of given type from the current point
384 * @pos: the type * to use as a loop cursor.
385 * @head: the head for your list.
386 * @member: the name of the list_struct within the struct.
388 * Iterate over list of given type, continuing from current position.
390 #define list_for_each_entry_from(pos, head, member) \
391 for (; &pos->member != (head); \
392 pos = list_entry(pos->member.next, typeof(*pos), member))
395 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
396 * @pos: the type * to use as a loop cursor.
397 * @n: another type * to use as temporary storage
398 * @head: the head for your list.
399 * @member: the name of the list_struct within the struct.
401 #define list_for_each_entry_safe(pos, n, head, member) \
402 for (pos = list_entry((head)->next, typeof(*pos), member), \
403 n = list_entry(pos->member.next, typeof(*pos), member); \
404 &pos->member != (head); \
405 pos = n, n = list_entry(n->member.next, typeof(*n), member))
408 * list_for_each_entry_safe_continue
409 * @pos: the type * to use as a loop cursor.
410 * @n: another type * to use as temporary storage
411 * @head: the head for your list.
412 * @member: the name of the list_struct within the struct.
414 * Iterate over list of given type, continuing after current point,
415 * safe against removal of list entry.
417 #define list_for_each_entry_safe_continue(pos, n, head, member) \
418 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
419 n = list_entry(pos->member.next, typeof(*pos), member); \
420 &pos->member != (head); \
421 pos = n, n = list_entry(n->member.next, typeof(*n), member))
424 * list_for_each_entry_safe_from
425 * @pos: the type * to use as a loop cursor.
426 * @n: another type * to use as temporary storage
427 * @head: the head for your list.
428 * @member: the name of the list_struct within the struct.
430 * Iterate over list of given type from current point, safe against
431 * removal of list entry.
433 #define list_for_each_entry_safe_from(pos, n, head, member) \
434 for (n = list_entry(pos->member.next, typeof(*pos), member); \
435 &pos->member != (head); \
436 pos = n, n = list_entry(n->member.next, typeof(*n), member))
439 * list_for_each_entry_safe_reverse
440 * @pos: the type * to use as a loop cursor.
441 * @n: another type * to use as temporary storage
442 * @head: the head for your list.
443 * @member: the name of the list_struct within the struct.
445 * Iterate backwards over list of given type, safe against removal
448 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
449 for (pos = list_entry((head)->prev, typeof(*pos), member), \
450 n = list_entry(pos->member.prev, typeof(*pos), member); \
451 &pos->member != (head); \
452 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
455 * Double linked lists with a single pointer list head.
456 * Mostly useful for hash tables where the two pointer list head is
458 * You lose the ability to access the tail in O(1).
462 struct hlist_node
*first
;
466 struct hlist_node
*next
, **pprev
;
469 #define HLIST_HEAD_INIT { .first = NULL }
470 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
471 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
472 static inline void INIT_HLIST_NODE(struct hlist_node
*h
)
478 static inline int hlist_unhashed(const struct hlist_node
*h
)
483 static inline int hlist_empty(const struct hlist_head
*h
)
488 static inline void __hlist_del(struct hlist_node
*n
)
490 struct hlist_node
*next
= n
->next
;
491 struct hlist_node
**pprev
= n
->pprev
;
497 static inline void hlist_del(struct hlist_node
*n
)
504 static inline void hlist_del_init(struct hlist_node
*n
)
506 if (!hlist_unhashed(n
)) {
513 static inline void hlist_add_head(struct hlist_node
*n
, struct hlist_head
*h
)
515 struct hlist_node
*first
= h
->first
;
518 first
->pprev
= &n
->next
;
520 n
->pprev
= &h
->first
;
524 /* next must be != NULL */
525 static inline void hlist_add_before(struct hlist_node
*n
,
526 struct hlist_node
*next
)
528 n
->pprev
= next
->pprev
;
530 next
->pprev
= &n
->next
;
534 static inline void hlist_add_after(struct hlist_node
*n
,
535 struct hlist_node
*next
)
537 next
->next
= n
->next
;
539 next
->pprev
= &n
->next
;
542 next
->next
->pprev
= &next
->next
;
545 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
547 #define hlist_for_each(pos, head) \
548 for (pos = (head)->first; pos; pos = pos->next)
550 #define hlist_for_each_safe(pos, n, head) \
551 for (pos = (head)->first; pos; pos = n)
554 * hlist_for_each_entry - iterate over list of given type
555 * @tpos: the type * to use as a loop cursor.
556 * @pos: the &struct hlist_node to use as a loop cursor.
557 * @head: the head for your list.
558 * @member: the name of the hlist_node within the struct.
560 #define hlist_for_each_entry(tpos, pos, head, member) \
561 for (pos = (head)->first; pos && \
562 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
566 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
567 * @tpos: the type * to use as a loop cursor.
568 * @pos: the &struct hlist_node to use as a loop cursor.
569 * @member: the name of the hlist_node within the struct.
571 #define hlist_for_each_entry_continue(tpos, pos, member) \
572 for (pos = (pos)->next; pos && \
573 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
577 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
578 * @tpos: the type * to use as a loop cursor.
579 * @pos: the &struct hlist_node to use as a loop cursor.
580 * @member: the name of the hlist_node within the struct.
582 #define hlist_for_each_entry_from(tpos, pos, member) \
584 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
588 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
589 * @tpos: the type * to use as a loop cursor.
590 * @pos: the &struct hlist_node to use as a loop cursor.
591 * @n: another &struct hlist_node to use as temporary storage
592 * @head: the head for your list.
593 * @member: the name of the hlist_node within the struct.
595 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
596 for (pos = (head)->first; \
597 pos && ({ n = pos->next; 1; }) && \
598 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
This page took 0.07584 seconds and 5 git commands to generate.