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.
12 /*#ifndef container_of
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
;
191 * @head: the list to test.
193 static inline int list_count(const struct list_head
*head
)
196 const struct list_head
*p
= head
->next
;
206 * list_empty_careful - tests whether a list is empty and not being modified
207 * @head: the list to test
210 * tests whether a list is empty _and_ checks that no other CPU might be
211 * in the process of modifying either member (next or prev)
213 * NOTE: using list_empty_careful() without synchronization
214 * can only be safe if the only activity that can happen
215 * to the list entry is list_del_init(). Eg. it cannot be used
216 * if another CPU could re-list_add() it.
218 static inline int list_empty_careful(const struct list_head
*head
)
220 struct list_head
*next
= head
->next
;
221 return (next
== head
) && (next
== head
->prev
);
224 static inline void __list_splice(struct list_head
*list
,
225 struct list_head
*head
)
227 struct list_head
*first
= list
->next
;
228 struct list_head
*last
= list
->prev
;
229 struct list_head
*at
= head
->next
;
239 * list_splice - join two lists
240 * @list: the new list to add.
241 * @head: the place to add it in the first list.
243 static inline void list_splice(struct list_head
*list
, struct list_head
*head
)
245 if (!list_empty(list
))
246 __list_splice(list
, head
);
250 * list_splice_init - join two lists and reinitialise the emptied list.
251 * @list: the new list to add.
252 * @head: the place to add it in the first list.
254 * The list at @list is reinitialised
256 static inline void list_splice_init(struct list_head
*list
,
257 struct list_head
*head
)
259 if (!list_empty(list
)) {
260 __list_splice(list
, head
);
261 INIT_LIST_HEAD(list
);
266 * list_entry - get the struct for this entry
267 * @ptr: the &struct list_head pointer.
268 * @type: the type of the struct this is embedded in.
269 * @member: the name of the list_struct within the struct.
271 #define list_entry(ptr, type, member) \
272 container_of(ptr, type, member)
275 * list_first_entry - get the first element from a list
276 * @ptr: the list head to take the element from.
277 * @type: the type of the struct this is embedded in.
278 * @member: the name of the list_struct within the struct.
280 * Note, that list is expected to be not empty.
282 #define list_first_entry(ptr, type, member) \
283 list_entry((ptr)->next, type, member)
286 * list_for_each - iterate over a list
287 * @pos: the &struct list_head to use as a loop cursor.
288 * @head: the head for your list.
290 #define list_for_each(pos, head) \
291 for (pos = (head)->next; pos != (head); \
295 * __list_for_each - iterate over a list
296 * @pos: the &struct list_head to use as a loop cursor.
297 * @head: the head for your list.
299 * This variant differs from list_for_each() in that it's the
300 * simplest possible list iteration code, no prefetching is done.
301 * Use this for code that knows the list to be very short (empty
302 * or 1 entry) most of the time.
304 #define __list_for_each(pos, head) \
305 for (pos = (head)->next; pos != (head); pos = pos->next)
308 * list_for_each_prev - iterate over a list backwards
309 * @pos: the &struct list_head to use as a loop cursor.
310 * @head: the head for your list.
312 #define list_for_each_prev(pos, head) \
313 for (pos = (head)->prev; pos != (head); \
317 * list_for_each_safe - iterate over a list safe against removal of list entry
318 * @pos: the &struct list_head to use as a loop cursor.
319 * @n: another &struct list_head to use as temporary storage
320 * @head: the head for your list.
322 #define list_for_each_safe(pos, n, head) \
323 for (pos = (head)->next, n = pos->next; pos != (head); \
324 pos = n, n = pos->next)
327 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
328 * @pos: the &struct list_head to use as a loop cursor.
329 * @n: another &struct list_head to use as temporary storage
330 * @head: the head for your list.
332 #define list_for_each_prev_safe(pos, n, head) \
333 for (pos = (head)->prev, n = pos->prev; \
335 pos = n, n = pos->prev)
338 * list_for_each_entry - iterate over list of given type
339 * @pos: the type * to use as a loop cursor.
340 * @head: the head for your list.
341 * @member: the name of the list_struct within the struct.
343 #define list_for_each_entry(pos, head, member) \
344 for (pos = list_entry((head)->next, typeof(*pos), member); \
345 &pos->member != (head); \
346 pos = list_entry(pos->member.next, typeof(*pos), member))
349 * list_for_each_entry_reverse - iterate backwards over list of given type.
350 * @pos: the type * to use as a loop cursor.
351 * @head: the head for your list.
352 * @member: the name of the list_struct within the struct.
354 #define list_for_each_entry_reverse(pos, head, member) \
355 for (pos = list_entry((head)->prev, typeof(*pos), member); \
356 &pos->member != (head); \
357 pos = list_entry(pos->member.prev, typeof(*pos), member))
360 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
361 * @pos: the type * to use as a start point
362 * @head: the head of the list
363 * @member: the name of the list_struct within the struct.
365 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
367 #define list_prepare_entry(pos, head, member) \
368 ((pos) ? : list_entry(head, typeof(*pos), member))
371 * list_for_each_entry_continue - continue iteration over list of given type
372 * @pos: the type * to use as a loop cursor.
373 * @head: the head for your list.
374 * @member: the name of the list_struct within the struct.
376 * Continue to iterate over list of given type, continuing after
377 * the current position.
379 #define list_for_each_entry_continue(pos, head, member) \
380 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
381 &pos->member != (head); \
382 pos = list_entry(pos->member.next, typeof(*pos), member))
385 * list_for_each_entry_continue_reverse - iterate backwards from the given point
386 * @pos: the type * to use as a loop cursor.
387 * @head: the head for your list.
388 * @member: the name of the list_struct within the struct.
390 * Start to iterate over list of given type backwards, continuing after
391 * the current position.
393 #define list_for_each_entry_continue_reverse(pos, head, member) \
394 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
395 &pos->member != (head); \
396 pos = list_entry(pos->member.prev, typeof(*pos), member))
399 * list_for_each_entry_from - iterate over list of given type from the current point
400 * @pos: the type * to use as a loop cursor.
401 * @head: the head for your list.
402 * @member: the name of the list_struct within the struct.
404 * Iterate over list of given type, continuing from current position.
406 #define list_for_each_entry_from(pos, head, member) \
407 for (; &pos->member != (head); \
408 pos = list_entry(pos->member.next, typeof(*pos), member))
411 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
412 * @pos: the type * to use as a loop cursor.
413 * @n: another type * to use as temporary storage
414 * @head: the head for your list.
415 * @member: the name of the list_struct within the struct.
417 #define list_for_each_entry_safe(pos, n, head, member) \
418 for (pos = list_entry((head)->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_continue
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, continuing after current point,
431 * safe against removal of list entry.
433 #define list_for_each_entry_safe_continue(pos, n, head, member) \
434 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
435 n = list_entry(pos->member.next, typeof(*pos), member); \
436 &pos->member != (head); \
437 pos = n, n = list_entry(n->member.next, typeof(*n), member))
440 * list_for_each_entry_safe_from
441 * @pos: the type * to use as a loop cursor.
442 * @n: another type * to use as temporary storage
443 * @head: the head for your list.
444 * @member: the name of the list_struct within the struct.
446 * Iterate over list of given type from current point, safe against
447 * removal of list entry.
449 #define list_for_each_entry_safe_from(pos, n, head, member) \
450 for (n = list_entry(pos->member.next, typeof(*pos), member); \
451 &pos->member != (head); \
452 pos = n, n = list_entry(n->member.next, typeof(*n), member))
455 * list_for_each_entry_safe_reverse
456 * @pos: the type * to use as a loop cursor.
457 * @n: another type * to use as temporary storage
458 * @head: the head for your list.
459 * @member: the name of the list_struct within the struct.
461 * Iterate backwards over list of given type, safe against removal
464 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
465 for (pos = list_entry((head)->prev, typeof(*pos), member), \
466 n = list_entry(pos->member.prev, typeof(*pos), member); \
467 &pos->member != (head); \
468 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
471 * Double linked lists with a single pointer list head.
472 * Mostly useful for hash tables where the two pointer list head is
474 * You lose the ability to access the tail in O(1).
478 struct hlist_node
*first
;
482 struct hlist_node
*next
, **pprev
;
485 #define HLIST_HEAD_INIT { .first = NULL }
486 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
487 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
488 static inline void INIT_HLIST_NODE(struct hlist_node
*h
)
494 static inline int hlist_unhashed(const struct hlist_node
*h
)
499 static inline int hlist_empty(const struct hlist_head
*h
)
504 static inline void __hlist_del(struct hlist_node
*n
)
506 struct hlist_node
*next
= n
->next
;
507 struct hlist_node
**pprev
= n
->pprev
;
513 static inline void hlist_del(struct hlist_node
*n
)
520 static inline void hlist_del_init(struct hlist_node
*n
)
522 if (!hlist_unhashed(n
)) {
529 static inline void hlist_add_head(struct hlist_node
*n
, struct hlist_head
*h
)
531 struct hlist_node
*first
= h
->first
;
534 first
->pprev
= &n
->next
;
536 n
->pprev
= &h
->first
;
540 /* next must be != NULL */
541 static inline void hlist_add_before(struct hlist_node
*n
,
542 struct hlist_node
*next
)
544 n
->pprev
= next
->pprev
;
546 next
->pprev
= &n
->next
;
550 static inline void hlist_add_after(struct hlist_node
*n
,
551 struct hlist_node
*next
)
553 next
->next
= n
->next
;
555 next
->pprev
= &n
->next
;
558 next
->next
->pprev
= &next
->next
;
561 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
563 #define hlist_for_each(pos, head) \
564 for (pos = (head)->first; pos; pos = pos->next)
566 #define hlist_for_each_safe(pos, n, head) \
567 for (pos = (head)->first; pos; pos = n)
570 * hlist_for_each_entry - iterate over list of given type
571 * @tpos: the type * to use as a loop cursor.
572 * @pos: the &struct hlist_node to use as a loop cursor.
573 * @head: the head for your list.
574 * @member: the name of the hlist_node within the struct.
576 #define hlist_for_each_entry(tpos, pos, head, member) \
577 for (pos = (head)->first; pos && \
578 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
582 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
583 * @tpos: the type * to use as a loop cursor.
584 * @pos: the &struct hlist_node to use as a loop cursor.
585 * @member: the name of the hlist_node within the struct.
587 #define hlist_for_each_entry_continue(tpos, pos, member) \
588 for (pos = (pos)->next; pos && \
589 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
593 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
594 * @tpos: the type * to use as a loop cursor.
595 * @pos: the &struct hlist_node to use as a loop cursor.
596 * @member: the name of the hlist_node within the struct.
598 #define hlist_for_each_entry_from(tpos, pos, member) \
600 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
604 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
605 * @tpos: the type * to use as a loop cursor.
606 * @pos: the &struct hlist_node to use as a loop cursor.
607 * @n: another &struct hlist_node to use as temporary storage
608 * @head: the head for your list.
609 * @member: the name of the hlist_node within the struct.
611 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
612 for (pos = (head)->first; \
613 pos && ({ n = pos->next; 1; }) && \
614 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \