blob: dac16f99c70115ba4e4f1cee8b18f5f1b0f050c8 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001#ifndef _LINUX_LIST_H
2#define _LINUX_LIST_H
3
4#ifdef __KERNEL__
5
6#include <linux/stddef.h>
Randy Dunlapc9cf5522006-06-27 02:53:52 -07007#include <linux/poison.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -07008#include <linux/prefetch.h>
9#include <asm/system.h>
10
11/*
Linus Torvalds1da177e2005-04-16 15:20:36 -070012 * Simple doubly linked list implementation.
13 *
14 * Some of the internal functions ("__xxx") are useful when
15 * manipulating whole lists rather than single entries, as
16 * sometimes we already know the next/prev entries and we can
17 * generate better code by using them directly rather than
18 * using the generic single-entry routines.
19 */
20
21struct list_head {
22 struct list_head *next, *prev;
23};
24
25#define LIST_HEAD_INIT(name) { &(name), &(name) }
26
27#define LIST_HEAD(name) \
28 struct list_head name = LIST_HEAD_INIT(name)
29
Zach Brown490d6ab2006-02-03 03:03:56 -080030static inline void INIT_LIST_HEAD(struct list_head *list)
31{
32 list->next = list;
33 list->prev = list;
34}
Linus Torvalds1da177e2005-04-16 15:20:36 -070035
36/*
37 * Insert a new entry between two known consecutive entries.
38 *
39 * This is only for internal list manipulation where we know
40 * the prev/next entries already!
41 */
Dave Jones199a9af2006-09-29 01:59:00 -070042#ifndef CONFIG_DEBUG_LIST
Linus Torvalds1da177e2005-04-16 15:20:36 -070043static inline void __list_add(struct list_head *new,
44 struct list_head *prev,
45 struct list_head *next)
46{
47 next->prev = new;
48 new->next = next;
49 new->prev = prev;
50 prev->next = new;
51}
Dave Jones199a9af2006-09-29 01:59:00 -070052#else
53extern void __list_add(struct list_head *new,
54 struct list_head *prev,
55 struct list_head *next);
56#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070057
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 */
Dave Jones199a9af2006-09-29 01:59:00 -070066#ifndef CONFIG_DEBUG_LIST
Linus Torvalds1da177e2005-04-16 15:20:36 -070067static inline void list_add(struct list_head *new, struct list_head *head)
68{
69 __list_add(new, head, head->next);
70}
Dave Jones199a9af2006-09-29 01:59:00 -070071#else
72extern void list_add(struct list_head *new, struct list_head *head);
73#endif
74
Linus Torvalds1da177e2005-04-16 15:20:36 -070075
76/**
77 * list_add_tail - add a new entry
78 * @new: new entry to be added
79 * @head: list head to add it before
80 *
81 * Insert a new entry before the specified head.
82 * This is useful for implementing queues.
83 */
84static inline void list_add_tail(struct list_head *new, struct list_head *head)
85{
86 __list_add(new, head->prev, head);
87}
88
89/*
90 * Insert a new entry between two known consecutive entries.
91 *
92 * This is only for internal list manipulation where we know
93 * the prev/next entries already!
94 */
95static inline void __list_add_rcu(struct list_head * new,
96 struct list_head * prev, struct list_head * next)
97{
98 new->next = next;
99 new->prev = prev;
100 smp_wmb();
101 next->prev = new;
102 prev->next = new;
103}
104
105/**
106 * list_add_rcu - add a new entry to rcu-protected list
107 * @new: new entry to be added
108 * @head: list head to add it after
109 *
110 * Insert a new entry after the specified head.
111 * This is good for implementing stacks.
112 *
113 * The caller must take whatever precautions are necessary
114 * (such as holding appropriate locks) to avoid racing
115 * with another list-mutation primitive, such as list_add_rcu()
116 * or list_del_rcu(), running on this same list.
117 * However, it is perfectly legal to run concurrently with
118 * the _rcu list-traversal primitives, such as
119 * list_for_each_entry_rcu().
120 */
121static inline void list_add_rcu(struct list_head *new, struct list_head *head)
122{
123 __list_add_rcu(new, head, head->next);
124}
125
126/**
127 * list_add_tail_rcu - add a new entry to rcu-protected list
128 * @new: new entry to be added
129 * @head: list head to add it before
130 *
131 * Insert a new entry before the specified head.
132 * This is useful for implementing queues.
133 *
134 * The caller must take whatever precautions are necessary
135 * (such as holding appropriate locks) to avoid racing
136 * with another list-mutation primitive, such as list_add_tail_rcu()
137 * or list_del_rcu(), running on this same list.
138 * However, it is perfectly legal to run concurrently with
139 * the _rcu list-traversal primitives, such as
140 * list_for_each_entry_rcu().
141 */
142static inline void list_add_tail_rcu(struct list_head *new,
143 struct list_head *head)
144{
145 __list_add_rcu(new, head->prev, head);
146}
147
148/*
149 * Delete a list entry by making the prev/next entries
150 * point to each other.
151 *
152 * This is only for internal list manipulation where we know
153 * the prev/next entries already!
154 */
155static inline void __list_del(struct list_head * prev, struct list_head * next)
156{
157 next->prev = prev;
158 prev->next = next;
159}
160
161/**
162 * list_del - deletes entry from list.
163 * @entry: the element to delete from the list.
Robert P. J. Day72fd4a32007-02-10 01:45:59 -0800164 * Note: list_empty() on entry does not return true after this, the entry is
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165 * in an undefined state.
166 */
Dave Jones199a9af2006-09-29 01:59:00 -0700167#ifndef CONFIG_DEBUG_LIST
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168static inline void list_del(struct list_head *entry)
169{
170 __list_del(entry->prev, entry->next);
171 entry->next = LIST_POISON1;
172 entry->prev = LIST_POISON2;
173}
Dave Jones199a9af2006-09-29 01:59:00 -0700174#else
175extern void list_del(struct list_head *entry);
176#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700177
178/**
179 * list_del_rcu - deletes entry from list without re-initialization
180 * @entry: the element to delete from the list.
181 *
Robert P. J. Day72fd4a32007-02-10 01:45:59 -0800182 * Note: list_empty() on entry does not return true after this,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700183 * the entry is in an undefined state. It is useful for RCU based
184 * lockfree traversal.
185 *
186 * In particular, it means that we can not poison the forward
187 * pointers that may still be used for walking the list.
188 *
189 * The caller must take whatever precautions are necessary
190 * (such as holding appropriate locks) to avoid racing
191 * with another list-mutation primitive, such as list_del_rcu()
192 * or list_add_rcu(), running on this same list.
193 * However, it is perfectly legal to run concurrently with
194 * the _rcu list-traversal primitives, such as
195 * list_for_each_entry_rcu().
196 *
197 * Note that the caller is not permitted to immediately free
Paul E. McKenneyb2b18662005-06-25 14:55:38 -0700198 * the newly deleted entry. Instead, either synchronize_rcu()
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 * or call_rcu() must be used to defer freeing until an RCU
200 * grace period has elapsed.
201 */
202static inline void list_del_rcu(struct list_head *entry)
203{
204 __list_del(entry->prev, entry->next);
205 entry->prev = LIST_POISON2;
206}
207
Oleg Nesterov54e73772006-06-23 02:05:54 -0700208/**
209 * list_replace - replace old entry by new one
210 * @old : the element to be replaced
211 * @new : the new element to insert
Robert P. J. Day72fd4a32007-02-10 01:45:59 -0800212 *
213 * If @old was empty, it will be overwritten.
Oleg Nesterov54e73772006-06-23 02:05:54 -0700214 */
215static inline void list_replace(struct list_head *old,
216 struct list_head *new)
217{
218 new->next = old->next;
219 new->next->prev = new;
220 new->prev = old->prev;
221 new->prev->next = new;
222}
223
224static inline void list_replace_init(struct list_head *old,
225 struct list_head *new)
226{
227 list_replace(old, new);
228 INIT_LIST_HEAD(old);
229}
230
Robert P. J. Day45f8bde2007-01-26 00:57:09 -0800231/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232 * list_replace_rcu - replace old entry by new one
233 * @old : the element to be replaced
234 * @new : the new element to insert
235 *
Robert P. J. Day45f8bde2007-01-26 00:57:09 -0800236 * The @old entry will be replaced with the @new entry atomically.
237 * Note: @old should not be empty.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238 */
Ingo Molnarb88cb422005-12-12 00:37:11 -0800239static inline void list_replace_rcu(struct list_head *old,
240 struct list_head *new)
241{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700242 new->next = old->next;
243 new->prev = old->prev;
244 smp_wmb();
245 new->next->prev = new;
246 new->prev->next = new;
Ingo Molnarb88cb422005-12-12 00:37:11 -0800247 old->prev = LIST_POISON2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248}
249
250/**
251 * list_del_init - deletes entry from list and reinitialize it.
252 * @entry: the element to delete from the list.
253 */
254static inline void list_del_init(struct list_head *entry)
255{
256 __list_del(entry->prev, entry->next);
257 INIT_LIST_HEAD(entry);
258}
259
260/**
261 * list_move - delete from one list and add as another's head
262 * @list: the entry to move
263 * @head: the head that will precede our entry
264 */
265static inline void list_move(struct list_head *list, struct list_head *head)
266{
Daniel Walker78db2ad2007-05-12 16:28:35 -0700267 __list_del(list->prev, list->next);
268 list_add(list, head);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269}
270
271/**
272 * list_move_tail - delete from one list and add as another's tail
273 * @list: the entry to move
274 * @head: the head that will follow our entry
275 */
276static inline void list_move_tail(struct list_head *list,
277 struct list_head *head)
278{
Daniel Walker78db2ad2007-05-12 16:28:35 -0700279 __list_del(list->prev, list->next);
280 list_add_tail(list, head);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281}
282
283/**
Shailabh Nagare8f4d972006-07-14 00:24:35 -0700284 * list_is_last - tests whether @list is the last entry in list @head
285 * @list: the entry to test
286 * @head: the head of the list
287 */
288static inline int list_is_last(const struct list_head *list,
289 const struct list_head *head)
290{
291 return list->next == head;
292}
293
294/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295 * list_empty - tests whether a list is empty
296 * @head: the list to test.
297 */
298static inline int list_empty(const struct list_head *head)
299{
300 return head->next == head;
301}
302
303/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700304 * list_empty_careful - tests whether a list is empty and not being modified
305 * @head: the list to test
306 *
307 * Description:
308 * tests whether a list is empty _and_ checks that no other CPU might be
309 * in the process of modifying either member (next or prev)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310 *
311 * NOTE: using list_empty_careful() without synchronization
312 * can only be safe if the only activity that can happen
313 * to the list entry is list_del_init(). Eg. it cannot be used
314 * if another CPU could re-list_add() it.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 */
316static inline int list_empty_careful(const struct list_head *head)
317{
318 struct list_head *next = head->next;
319 return (next == head) && (next == head->prev);
320}
321
322static inline void __list_splice(struct list_head *list,
323 struct list_head *head)
324{
325 struct list_head *first = list->next;
326 struct list_head *last = list->prev;
327 struct list_head *at = head->next;
328
329 first->prev = head;
330 head->next = first;
331
332 last->next = at;
333 at->prev = last;
334}
335
336/**
337 * list_splice - join two lists
338 * @list: the new list to add.
339 * @head: the place to add it in the first list.
340 */
341static inline void list_splice(struct list_head *list, struct list_head *head)
342{
343 if (!list_empty(list))
344 __list_splice(list, head);
345}
346
347/**
348 * list_splice_init - join two lists and reinitialise the emptied list.
349 * @list: the new list to add.
350 * @head: the place to add it in the first list.
351 *
352 * The list at @list is reinitialised
353 */
354static inline void list_splice_init(struct list_head *list,
355 struct list_head *head)
356{
357 if (!list_empty(list)) {
358 __list_splice(list, head);
359 INIT_LIST_HEAD(list);
360 }
361}
362
363/**
Corey Minyard3678d622007-02-10 01:45:42 -0800364 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
365 * @list: the RCU-protected list to splice
366 * @head: the place in the list to splice the first list into
367 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
368 *
369 * @head can be RCU-read traversed concurrently with this function.
370 *
371 * Note that this function blocks.
372 *
373 * Important note: the caller must take whatever action is necessary to
374 * prevent any other updates to @head. In principle, it is possible
375 * to modify the list as soon as sync() begins execution.
376 * If this sort of thing becomes necessary, an alternative version
377 * based on call_rcu() could be created. But only if -really-
378 * needed -- there is no shortage of RCU API members.
379 */
380static inline void list_splice_init_rcu(struct list_head *list,
381 struct list_head *head,
382 void (*sync)(void))
383{
384 struct list_head *first = list->next;
385 struct list_head *last = list->prev;
386 struct list_head *at = head->next;
387
388 if (list_empty(head))
389 return;
390
391 /* "first" and "last" tracking list, so initialize it. */
392
393 INIT_LIST_HEAD(list);
394
395 /*
396 * At this point, the list body still points to the source list.
397 * Wait for any readers to finish using the list before splicing
398 * the list body into the new list. Any new readers will see
399 * an empty list.
400 */
401
402 sync();
403
404 /*
405 * Readers are finished with the source list, so perform splice.
406 * The order is important if the new list is global and accessible
407 * to concurrent RCU readers. Note that RCU readers are not
408 * permitted to traverse the prev pointers without excluding
409 * this function.
410 */
411
412 last->next = at;
413 smp_wmb();
414 head->next = first;
415 first->prev = head;
416 at->prev = last;
417}
418
419/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700420 * list_entry - get the struct for this entry
421 * @ptr: the &struct list_head pointer.
422 * @type: the type of the struct this is embedded in.
423 * @member: the name of the list_struct within the struct.
424 */
425#define list_entry(ptr, type, member) \
426 container_of(ptr, type, member)
427
428/**
Pavel Emelianovb5e61812007-05-08 00:30:19 -0700429 * list_first_entry - get the first element from a list
430 * @ptr: the list head to take the element from.
431 * @type: the type of the struct this is embedded in.
432 * @member: the name of the list_struct within the struct.
433 *
434 * Note, that list is expected to be not empty.
435 */
436#define list_first_entry(ptr, type, member) \
437 list_entry((ptr)->next, type, member)
438
439/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700440 * list_for_each - iterate over a list
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700441 * @pos: the &struct list_head to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442 * @head: the head for your list.
443 */
444#define list_for_each(pos, head) \
445 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
446 pos = pos->next)
447
448/**
449 * __list_for_each - iterate over a list
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700450 * @pos: the &struct list_head to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700451 * @head: the head for your list.
452 *
453 * This variant differs from list_for_each() in that it's the
454 * simplest possible list iteration code, no prefetching is done.
455 * Use this for code that knows the list to be very short (empty
456 * or 1 entry) most of the time.
457 */
458#define __list_for_each(pos, head) \
459 for (pos = (head)->next; pos != (head); pos = pos->next)
460
461/**
462 * list_for_each_prev - iterate over a list backwards
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700463 * @pos: the &struct list_head to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 * @head: the head for your list.
465 */
466#define list_for_each_prev(pos, head) \
467 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
468 pos = pos->prev)
469
470/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700471 * list_for_each_safe - iterate over a list safe against removal of list entry
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700472 * @pos: the &struct list_head to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700473 * @n: another &struct list_head to use as temporary storage
474 * @head: the head for your list.
475 */
476#define list_for_each_safe(pos, n, head) \
477 for (pos = (head)->next, n = pos->next; pos != (head); \
478 pos = n, n = pos->next)
479
480/**
Randy Dunlap8f731f72007-10-18 23:39:28 -0700481 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
Denis V. Lunev37c42522007-10-16 23:29:53 -0700482 * @pos: the &struct list_head to use as a loop cursor.
483 * @n: another &struct list_head to use as temporary storage
484 * @head: the head for your list.
485 */
486#define list_for_each_prev_safe(pos, n, head) \
487 for (pos = (head)->prev, n = pos->prev; \
488 prefetch(pos->prev), pos != (head); \
489 pos = n, n = pos->prev)
490
491/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 * list_for_each_entry - iterate over list of given type
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700493 * @pos: the type * to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700494 * @head: the head for your list.
495 * @member: the name of the list_struct within the struct.
496 */
497#define list_for_each_entry(pos, head, member) \
498 for (pos = list_entry((head)->next, typeof(*pos), member); \
499 prefetch(pos->member.next), &pos->member != (head); \
500 pos = list_entry(pos->member.next, typeof(*pos), member))
501
502/**
503 * list_for_each_entry_reverse - iterate backwards over list of given type.
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700504 * @pos: the type * to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 * @head: the head for your list.
506 * @member: the name of the list_struct within the struct.
507 */
508#define list_for_each_entry_reverse(pos, head, member) \
509 for (pos = list_entry((head)->prev, typeof(*pos), member); \
510 prefetch(pos->member.prev), &pos->member != (head); \
511 pos = list_entry(pos->member.prev, typeof(*pos), member))
512
513/**
Robert P. J. Day72fd4a32007-02-10 01:45:59 -0800514 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
Linus Torvalds1da177e2005-04-16 15:20:36 -0700515 * @pos: the type * to use as a start point
516 * @head: the head of the list
517 * @member: the name of the list_struct within the struct.
Randy Dunlapfe96e572006-06-25 05:47:42 -0700518 *
Robert P. J. Day72fd4a32007-02-10 01:45:59 -0800519 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
Linus Torvalds1da177e2005-04-16 15:20:36 -0700520 */
521#define list_prepare_entry(pos, head, member) \
522 ((pos) ? : list_entry(head, typeof(*pos), member))
523
524/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700525 * list_for_each_entry_continue - continue iteration over list of given type
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700526 * @pos: the type * to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527 * @head: the head for your list.
528 * @member: the name of the list_struct within the struct.
Randy Dunlapfe96e572006-06-25 05:47:42 -0700529 *
530 * Continue to iterate over list of given type, continuing after
531 * the current position.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532 */
533#define list_for_each_entry_continue(pos, head, member) \
534 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
535 prefetch(pos->member.next), &pos->member != (head); \
536 pos = list_entry(pos->member.next, typeof(*pos), member))
537
538/**
Pavel Emelyanov768f35912007-09-18 13:20:41 -0700539 * list_for_each_entry_continue_reverse - iterate backwards from the given point
540 * @pos: the type * to use as a loop cursor.
541 * @head: the head for your list.
542 * @member: the name of the list_struct within the struct.
543 *
544 * Start to iterate over list of given type backwards, continuing after
545 * the current position.
546 */
547#define list_for_each_entry_continue_reverse(pos, head, member) \
548 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \
549 prefetch(pos->member.prev), &pos->member != (head); \
550 pos = list_entry(pos->member.prev, typeof(*pos), member))
551
552/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700553 * list_for_each_entry_from - iterate over list of given type from the current point
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700554 * @pos: the type * to use as a loop cursor.
Arnaldo Carvalho de Meloe229c2f2006-03-20 17:19:17 -0800555 * @head: the head for your list.
556 * @member: the name of the list_struct within the struct.
Randy Dunlapfe96e572006-06-25 05:47:42 -0700557 *
558 * Iterate over list of given type, continuing from current position.
Arnaldo Carvalho de Meloe229c2f2006-03-20 17:19:17 -0800559 */
560#define list_for_each_entry_from(pos, head, member) \
561 for (; prefetch(pos->member.next), &pos->member != (head); \
562 pos = list_entry(pos->member.next, typeof(*pos), member))
563
564/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700565 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700566 * @pos: the type * to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567 * @n: another type * to use as temporary storage
568 * @head: the head for your list.
569 * @member: the name of the list_struct within the struct.
570 */
571#define list_for_each_entry_safe(pos, n, head, member) \
572 for (pos = list_entry((head)->next, typeof(*pos), member), \
573 n = list_entry(pos->member.next, typeof(*pos), member); \
574 &pos->member != (head); \
575 pos = n, n = list_entry(n->member.next, typeof(*n), member))
576
577/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700578 * list_for_each_entry_safe_continue
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700579 * @pos: the type * to use as a loop cursor.
Arnaldo Carvalho de Melo74459dc2005-08-09 20:15:51 -0700580 * @n: another type * to use as temporary storage
581 * @head: the head for your list.
582 * @member: the name of the list_struct within the struct.
Randy Dunlapfe96e572006-06-25 05:47:42 -0700583 *
584 * Iterate over list of given type, continuing after current point,
585 * safe against removal of list entry.
Arnaldo Carvalho de Melo74459dc2005-08-09 20:15:51 -0700586 */
587#define list_for_each_entry_safe_continue(pos, n, head, member) \
Arnaldo Carvalho de Melo8c60f3f2005-08-10 12:59:38 -0300588 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
589 n = list_entry(pos->member.next, typeof(*pos), member); \
Arnaldo Carvalho de Melo74459dc2005-08-09 20:15:51 -0700590 &pos->member != (head); \
591 pos = n, n = list_entry(n->member.next, typeof(*n), member))
592
593/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700594 * list_for_each_entry_safe_from
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700595 * @pos: the type * to use as a loop cursor.
Arnaldo Carvalho de Melod8dcffe2006-03-20 17:18:05 -0800596 * @n: another type * to use as temporary storage
597 * @head: the head for your list.
598 * @member: the name of the list_struct within the struct.
Randy Dunlapfe96e572006-06-25 05:47:42 -0700599 *
600 * Iterate over list of given type from current point, safe against
601 * removal of list entry.
Arnaldo Carvalho de Melod8dcffe2006-03-20 17:18:05 -0800602 */
603#define list_for_each_entry_safe_from(pos, n, head, member) \
604 for (n = list_entry(pos->member.next, typeof(*pos), member); \
605 &pos->member != (head); \
606 pos = n, n = list_entry(n->member.next, typeof(*n), member))
607
608/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700609 * list_for_each_entry_safe_reverse
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700610 * @pos: the type * to use as a loop cursor.
David Howells0ad42352006-01-09 20:51:31 -0800611 * @n: another type * to use as temporary storage
612 * @head: the head for your list.
613 * @member: the name of the list_struct within the struct.
Randy Dunlapfe96e572006-06-25 05:47:42 -0700614 *
615 * Iterate backwards over list of given type, safe against removal
616 * of list entry.
David Howells0ad42352006-01-09 20:51:31 -0800617 */
618#define list_for_each_entry_safe_reverse(pos, n, head, member) \
619 for (pos = list_entry((head)->prev, typeof(*pos), member), \
620 n = list_entry(pos->member.prev, typeof(*pos), member); \
621 &pos->member != (head); \
622 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
623
624/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625 * list_for_each_rcu - iterate over an rcu-protected list
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700626 * @pos: the &struct list_head to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627 * @head: the head for your list.
628 *
629 * This list-traversal primitive may safely run concurrently with
630 * the _rcu list-mutation primitives such as list_add_rcu()
631 * as long as the traversal is guarded by rcu_read_lock().
632 */
633#define list_for_each_rcu(pos, head) \
Linus Torvaldscc216c52008-04-20 21:59:13 -0700634 for (pos = rcu_dereference((head)->next); \
635 prefetch(pos->next), pos != (head); \
636 pos = rcu_dereference(pos->next))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637
638#define __list_for_each_rcu(pos, head) \
Linus Torvaldscc216c52008-04-20 21:59:13 -0700639 for (pos = rcu_dereference((head)->next); \
640 pos != (head); \
641 pos = rcu_dereference(pos->next))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642
643/**
644 * list_for_each_entry_rcu - iterate over rcu list of given type
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700645 * @pos: the type * to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700646 * @head: the head for your list.
647 * @member: the name of the list_struct within the struct.
648 *
649 * This list-traversal primitive may safely run concurrently with
650 * the _rcu list-mutation primitives such as list_add_rcu()
651 * as long as the traversal is guarded by rcu_read_lock().
652 */
Herbert Xub24d18a2005-10-16 20:29:20 -0700653#define list_for_each_entry_rcu(pos, head, member) \
Linus Torvaldscc216c52008-04-20 21:59:13 -0700654 for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), member); \
655 prefetch(pos->member.next), &pos->member != (head); \
656 pos = list_entry(rcu_dereference(pos->member.next), typeof(*pos), member))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657
658
659/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700660 * list_for_each_continue_rcu
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700661 * @pos: the &struct list_head to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 * @head: the head for your list.
663 *
Randy Dunlapfe96e572006-06-25 05:47:42 -0700664 * Iterate over an rcu-protected list, continuing after current point.
665 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666 * This list-traversal primitive may safely run concurrently with
667 * the _rcu list-mutation primitives such as list_add_rcu()
668 * as long as the traversal is guarded by rcu_read_lock().
669 */
670#define list_for_each_continue_rcu(pos, head) \
Linus Torvaldscc216c52008-04-20 21:59:13 -0700671 for ((pos) = rcu_dereference((pos)->next); \
672 prefetch((pos)->next), (pos) != (head); \
673 (pos) = rcu_dereference((pos)->next))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700674
675/*
676 * Double linked lists with a single pointer list head.
677 * Mostly useful for hash tables where the two pointer list head is
678 * too wasteful.
679 * You lose the ability to access the tail in O(1).
680 */
681
682struct hlist_head {
683 struct hlist_node *first;
684};
685
686struct hlist_node {
687 struct hlist_node *next, **pprev;
688};
689
690#define HLIST_HEAD_INIT { .first = NULL }
691#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
692#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
Zach Brown490d6ab2006-02-03 03:03:56 -0800693static inline void INIT_HLIST_NODE(struct hlist_node *h)
694{
695 h->next = NULL;
696 h->pprev = NULL;
697}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700698
699static inline int hlist_unhashed(const struct hlist_node *h)
700{
701 return !h->pprev;
702}
703
704static inline int hlist_empty(const struct hlist_head *h)
705{
706 return !h->first;
707}
708
709static inline void __hlist_del(struct hlist_node *n)
710{
711 struct hlist_node *next = n->next;
712 struct hlist_node **pprev = n->pprev;
713 *pprev = next;
714 if (next)
715 next->pprev = pprev;
716}
717
718static inline void hlist_del(struct hlist_node *n)
719{
720 __hlist_del(n);
721 n->next = LIST_POISON1;
722 n->pprev = LIST_POISON2;
723}
724
725/**
726 * hlist_del_rcu - deletes entry from hash list without re-initialization
727 * @n: the element to delete from the hash list.
728 *
729 * Note: list_unhashed() on entry does not return true after this,
730 * the entry is in an undefined state. It is useful for RCU based
731 * lockfree traversal.
732 *
733 * In particular, it means that we can not poison the forward
734 * pointers that may still be used for walking the hash list.
735 *
736 * The caller must take whatever precautions are necessary
737 * (such as holding appropriate locks) to avoid racing
738 * with another list-mutation primitive, such as hlist_add_head_rcu()
739 * or hlist_del_rcu(), running on this same list.
740 * However, it is perfectly legal to run concurrently with
741 * the _rcu list-traversal primitives, such as
742 * hlist_for_each_entry().
743 */
744static inline void hlist_del_rcu(struct hlist_node *n)
745{
746 __hlist_del(n);
747 n->pprev = LIST_POISON2;
748}
749
750static inline void hlist_del_init(struct hlist_node *n)
751{
Akinobu Mitada753be2006-04-28 15:21:23 -0700752 if (!hlist_unhashed(n)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700753 __hlist_del(n);
754 INIT_HLIST_NODE(n);
755 }
756}
757
Robert P. J. Day45f8bde2007-01-26 00:57:09 -0800758/**
Ingo Molnarb88cb422005-12-12 00:37:11 -0800759 * hlist_replace_rcu - replace old entry by new one
760 * @old : the element to be replaced
761 * @new : the new element to insert
762 *
Robert P. J. Day45f8bde2007-01-26 00:57:09 -0800763 * The @old entry will be replaced with the @new entry atomically.
Ingo Molnarb88cb422005-12-12 00:37:11 -0800764 */
765static inline void hlist_replace_rcu(struct hlist_node *old,
766 struct hlist_node *new)
767{
768 struct hlist_node *next = old->next;
769
770 new->next = next;
771 new->pprev = old->pprev;
772 smp_wmb();
773 if (next)
774 new->next->pprev = &new->next;
775 *new->pprev = new;
776 old->pprev = LIST_POISON2;
777}
778
Linus Torvalds1da177e2005-04-16 15:20:36 -0700779static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
780{
781 struct hlist_node *first = h->first;
782 n->next = first;
783 if (first)
784 first->pprev = &n->next;
785 h->first = n;
786 n->pprev = &h->first;
787}
788
789
790/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700791 * hlist_add_head_rcu
Linus Torvalds1da177e2005-04-16 15:20:36 -0700792 * @n: the element to add to the hash list.
793 * @h: the list to add to.
794 *
Randy Dunlapfe96e572006-06-25 05:47:42 -0700795 * Description:
796 * Adds the specified element to the specified hlist,
797 * while permitting racing traversals.
798 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700799 * The caller must take whatever precautions are necessary
800 * (such as holding appropriate locks) to avoid racing
801 * with another list-mutation primitive, such as hlist_add_head_rcu()
802 * or hlist_del_rcu(), running on this same list.
803 * However, it is perfectly legal to run concurrently with
804 * the _rcu list-traversal primitives, such as
Paul E. McKenney665a7582005-11-07 00:59:17 -0800805 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806 * problems on Alpha CPUs. Regardless of the type of CPU, the
807 * list-traversal primitive must be guarded by rcu_read_lock().
808 */
809static inline void hlist_add_head_rcu(struct hlist_node *n,
810 struct hlist_head *h)
811{
812 struct hlist_node *first = h->first;
813 n->next = first;
814 n->pprev = &h->first;
815 smp_wmb();
816 if (first)
817 first->pprev = &n->next;
818 h->first = n;
819}
820
821/* next must be != NULL */
822static inline void hlist_add_before(struct hlist_node *n,
823 struct hlist_node *next)
824{
825 n->pprev = next->pprev;
826 n->next = next;
827 next->pprev = &n->next;
828 *(n->pprev) = n;
829}
830
831static inline void hlist_add_after(struct hlist_node *n,
832 struct hlist_node *next)
833{
834 next->next = n->next;
835 n->next = next;
836 next->pprev = &n->next;
837
838 if(next->next)
839 next->next->pprev = &next->next;
840}
841
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700842/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700843 * hlist_add_before_rcu
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700844 * @n: the new element to add to the hash list.
845 * @next: the existing element to add the new element before.
846 *
Randy Dunlapfe96e572006-06-25 05:47:42 -0700847 * Description:
848 * Adds the specified element to the specified hlist
849 * before the specified node while permitting racing traversals.
850 *
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700851 * The caller must take whatever precautions are necessary
852 * (such as holding appropriate locks) to avoid racing
853 * with another list-mutation primitive, such as hlist_add_head_rcu()
854 * or hlist_del_rcu(), running on this same list.
855 * However, it is perfectly legal to run concurrently with
856 * the _rcu list-traversal primitives, such as
Paul E. McKenney665a7582005-11-07 00:59:17 -0800857 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700858 * problems on Alpha CPUs.
859 */
Robert Olssone5b43762005-08-25 13:01:03 -0700860static inline void hlist_add_before_rcu(struct hlist_node *n,
861 struct hlist_node *next)
862{
863 n->pprev = next->pprev;
864 n->next = next;
865 smp_wmb();
866 next->pprev = &n->next;
867 *(n->pprev) = n;
868}
869
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700870/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700871 * hlist_add_after_rcu
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700872 * @prev: the existing element to add the new element after.
873 * @n: the new element to add to the hash list.
874 *
Randy Dunlapfe96e572006-06-25 05:47:42 -0700875 * Description:
876 * Adds the specified element to the specified hlist
877 * after the specified node while permitting racing traversals.
878 *
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700879 * The caller must take whatever precautions are necessary
880 * (such as holding appropriate locks) to avoid racing
881 * with another list-mutation primitive, such as hlist_add_head_rcu()
882 * or hlist_del_rcu(), running on this same list.
883 * However, it is perfectly legal to run concurrently with
884 * the _rcu list-traversal primitives, such as
Paul E. McKenney665a7582005-11-07 00:59:17 -0800885 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700886 * problems on Alpha CPUs.
887 */
Robert Olssone5b43762005-08-25 13:01:03 -0700888static inline void hlist_add_after_rcu(struct hlist_node *prev,
889 struct hlist_node *n)
890{
891 n->next = prev->next;
892 n->pprev = &prev->next;
893 smp_wmb();
894 prev->next = n;
895 if (n->next)
896 n->next->pprev = &n->next;
897}
898
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
900
901#define hlist_for_each(pos, head) \
902 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
903 pos = pos->next)
904
905#define hlist_for_each_safe(pos, n, head) \
906 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
907 pos = n)
908
Linus Torvalds1da177e2005-04-16 15:20:36 -0700909/**
910 * hlist_for_each_entry - iterate over list of given type
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700911 * @tpos: the type * to use as a loop cursor.
912 * @pos: the &struct hlist_node to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913 * @head: the head for your list.
914 * @member: the name of the hlist_node within the struct.
915 */
916#define hlist_for_each_entry(tpos, pos, head, member) \
917 for (pos = (head)->first; \
918 pos && ({ prefetch(pos->next); 1;}) && \
919 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
920 pos = pos->next)
921
922/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700923 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700924 * @tpos: the type * to use as a loop cursor.
925 * @pos: the &struct hlist_node to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 * @member: the name of the hlist_node within the struct.
927 */
928#define hlist_for_each_entry_continue(tpos, pos, member) \
929 for (pos = (pos)->next; \
930 pos && ({ prefetch(pos->next); 1;}) && \
931 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
932 pos = pos->next)
933
934/**
Randy Dunlapfe96e572006-06-25 05:47:42 -0700935 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700936 * @tpos: the type * to use as a loop cursor.
937 * @pos: the &struct hlist_node to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700938 * @member: the name of the hlist_node within the struct.
939 */
940#define hlist_for_each_entry_from(tpos, pos, member) \
941 for (; pos && ({ prefetch(pos->next); 1;}) && \
942 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
943 pos = pos->next)
944
945/**
946 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700947 * @tpos: the type * to use as a loop cursor.
948 * @pos: the &struct hlist_node to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700949 * @n: another &struct hlist_node to use as temporary storage
950 * @head: the head for your list.
951 * @member: the name of the hlist_node within the struct.
952 */
953#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
954 for (pos = (head)->first; \
955 pos && ({ n = pos->next; 1; }) && \
956 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
957 pos = n)
958
959/**
960 * hlist_for_each_entry_rcu - iterate over rcu list of given type
Randy Dunlap8e3a67a2006-06-25 05:47:43 -0700961 * @tpos: the type * to use as a loop cursor.
962 * @pos: the &struct hlist_node to use as a loop cursor.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700963 * @head: the head for your list.
964 * @member: the name of the hlist_node within the struct.
965 *
966 * This list-traversal primitive may safely run concurrently with
Paul E. McKenneye1ba0da2005-04-16 15:25:51 -0700967 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 * as long as the traversal is guarded by rcu_read_lock().
969 */
970#define hlist_for_each_entry_rcu(tpos, pos, head, member) \
Linus Torvaldscc216c52008-04-20 21:59:13 -0700971 for (pos = rcu_dereference((head)->first); \
972 pos && ({ prefetch(pos->next); 1;}) && \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
Linus Torvaldscc216c52008-04-20 21:59:13 -0700974 pos = rcu_dereference(pos->next))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975
976#else
977#warning "don't include kernel headers in userspace"
978#endif /* __KERNEL__ */
979#endif