blob: 945daa1f13dd05d6a7ad95e6022108a824d6a3dd [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>
7#include <linux/prefetch.h>
8#include <asm/system.h>
9
10/*
11 * These are non-NULL pointers that will result in page faults
12 * under normal circumstances, used to verify that nobody uses
13 * non-initialized list entries.
14 */
15#define LIST_POISON1 ((void *) 0x00100100)
16#define LIST_POISON2 ((void *) 0x00200200)
17
18/*
19 * Simple doubly linked list implementation.
20 *
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.
26 */
27
28struct list_head {
29 struct list_head *next, *prev;
30};
31
32#define LIST_HEAD_INIT(name) { &(name), &(name) }
33
34#define LIST_HEAD(name) \
35 struct list_head name = LIST_HEAD_INIT(name)
36
37#define INIT_LIST_HEAD(ptr) do { \
38 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
39} while (0)
40
41/*
42 * Insert a new entry between two known consecutive entries.
43 *
44 * This is only for internal list manipulation where we know
45 * the prev/next entries already!
46 */
47static inline void __list_add(struct list_head *new,
48 struct list_head *prev,
49 struct list_head *next)
50{
51 next->prev = new;
52 new->next = next;
53 new->prev = prev;
54 prev->next = new;
55}
56
57/**
58 * list_add - add a new entry
59 * @new: new entry to be added
60 * @head: list head to add it after
61 *
62 * Insert a new entry after the specified head.
63 * This is good for implementing stacks.
64 */
65static inline void list_add(struct list_head *new, struct list_head *head)
66{
67 __list_add(new, head, head->next);
68}
69
70/**
71 * list_add_tail - add a new entry
72 * @new: new entry to be added
73 * @head: list head to add it before
74 *
75 * Insert a new entry before the specified head.
76 * This is useful for implementing queues.
77 */
78static inline void list_add_tail(struct list_head *new, struct list_head *head)
79{
80 __list_add(new, head->prev, head);
81}
82
83/*
84 * Insert a new entry between two known consecutive entries.
85 *
86 * This is only for internal list manipulation where we know
87 * the prev/next entries already!
88 */
89static inline void __list_add_rcu(struct list_head * new,
90 struct list_head * prev, struct list_head * next)
91{
92 new->next = next;
93 new->prev = prev;
94 smp_wmb();
95 next->prev = new;
96 prev->next = new;
97}
98
99/**
100 * list_add_rcu - add a new entry to rcu-protected list
101 * @new: new entry to be added
102 * @head: list head to add it after
103 *
104 * Insert a new entry after the specified head.
105 * This is good for implementing stacks.
106 *
107 * The caller must take whatever precautions are necessary
108 * (such as holding appropriate locks) to avoid racing
109 * with another list-mutation primitive, such as list_add_rcu()
110 * or list_del_rcu(), running on this same list.
111 * However, it is perfectly legal to run concurrently with
112 * the _rcu list-traversal primitives, such as
113 * list_for_each_entry_rcu().
114 */
115static inline void list_add_rcu(struct list_head *new, struct list_head *head)
116{
117 __list_add_rcu(new, head, head->next);
118}
119
120/**
121 * list_add_tail_rcu - add a new entry to rcu-protected list
122 * @new: new entry to be added
123 * @head: list head to add it before
124 *
125 * Insert a new entry before the specified head.
126 * This is useful for implementing queues.
127 *
128 * The caller must take whatever precautions are necessary
129 * (such as holding appropriate locks) to avoid racing
130 * with another list-mutation primitive, such as list_add_tail_rcu()
131 * or list_del_rcu(), running on this same list.
132 * However, it is perfectly legal to run concurrently with
133 * the _rcu list-traversal primitives, such as
134 * list_for_each_entry_rcu().
135 */
136static inline void list_add_tail_rcu(struct list_head *new,
137 struct list_head *head)
138{
139 __list_add_rcu(new, head->prev, head);
140}
141
142/*
143 * Delete a list entry by making the prev/next entries
144 * point to each other.
145 *
146 * This is only for internal list manipulation where we know
147 * the prev/next entries already!
148 */
149static inline void __list_del(struct list_head * prev, struct list_head * next)
150{
151 next->prev = prev;
152 prev->next = next;
153}
154
155/**
156 * list_del - deletes entry from list.
157 * @entry: the element to delete from the list.
158 * Note: list_empty on entry does not return true after this, the entry is
159 * in an undefined state.
160 */
161static inline void list_del(struct list_head *entry)
162{
163 __list_del(entry->prev, entry->next);
164 entry->next = LIST_POISON1;
165 entry->prev = LIST_POISON2;
166}
167
168/**
169 * list_del_rcu - deletes entry from list without re-initialization
170 * @entry: the element to delete from the list.
171 *
172 * Note: list_empty on entry does not return true after this,
173 * the entry is in an undefined state. It is useful for RCU based
174 * lockfree traversal.
175 *
176 * In particular, it means that we can not poison the forward
177 * pointers that may still be used for walking the list.
178 *
179 * The caller must take whatever precautions are necessary
180 * (such as holding appropriate locks) to avoid racing
181 * with another list-mutation primitive, such as list_del_rcu()
182 * or list_add_rcu(), running on this same list.
183 * However, it is perfectly legal to run concurrently with
184 * the _rcu list-traversal primitives, such as
185 * list_for_each_entry_rcu().
186 *
187 * Note that the caller is not permitted to immediately free
Paul E. McKenneyb2b18662005-06-25 14:55:38 -0700188 * the newly deleted entry. Instead, either synchronize_rcu()
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189 * or call_rcu() must be used to defer freeing until an RCU
190 * grace period has elapsed.
191 */
192static inline void list_del_rcu(struct list_head *entry)
193{
194 __list_del(entry->prev, entry->next);
195 entry->prev = LIST_POISON2;
196}
197
198/*
199 * list_replace_rcu - replace old entry by new one
200 * @old : the element to be replaced
201 * @new : the new element to insert
202 *
203 * The old entry will be replaced with the new entry atomically.
204 */
Ingo Molnarb88cb422005-12-12 00:37:11 -0800205static inline void list_replace_rcu(struct list_head *old,
206 struct list_head *new)
207{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 new->next = old->next;
209 new->prev = old->prev;
210 smp_wmb();
211 new->next->prev = new;
212 new->prev->next = new;
Ingo Molnarb88cb422005-12-12 00:37:11 -0800213 old->prev = LIST_POISON2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700214}
215
216/**
217 * list_del_init - deletes entry from list and reinitialize it.
218 * @entry: the element to delete from the list.
219 */
220static inline void list_del_init(struct list_head *entry)
221{
222 __list_del(entry->prev, entry->next);
223 INIT_LIST_HEAD(entry);
224}
225
226/**
227 * list_move - delete from one list and add as another's head
228 * @list: the entry to move
229 * @head: the head that will precede our entry
230 */
231static inline void list_move(struct list_head *list, struct list_head *head)
232{
233 __list_del(list->prev, list->next);
234 list_add(list, head);
235}
236
237/**
238 * list_move_tail - delete from one list and add as another's tail
239 * @list: the entry to move
240 * @head: the head that will follow our entry
241 */
242static inline void list_move_tail(struct list_head *list,
243 struct list_head *head)
244{
245 __list_del(list->prev, list->next);
246 list_add_tail(list, head);
247}
248
249/**
250 * list_empty - tests whether a list is empty
251 * @head: the list to test.
252 */
253static inline int list_empty(const struct list_head *head)
254{
255 return head->next == head;
256}
257
258/**
259 * list_empty_careful - tests whether a list is
260 * empty _and_ checks that no other CPU might be
261 * in the process of still modifying either member
262 *
263 * NOTE: using list_empty_careful() without synchronization
264 * can only be safe if the only activity that can happen
265 * to the list entry is list_del_init(). Eg. it cannot be used
266 * if another CPU could re-list_add() it.
267 *
268 * @head: the list to test.
269 */
270static inline int list_empty_careful(const struct list_head *head)
271{
272 struct list_head *next = head->next;
273 return (next == head) && (next == head->prev);
274}
275
276static inline void __list_splice(struct list_head *list,
277 struct list_head *head)
278{
279 struct list_head *first = list->next;
280 struct list_head *last = list->prev;
281 struct list_head *at = head->next;
282
283 first->prev = head;
284 head->next = first;
285
286 last->next = at;
287 at->prev = last;
288}
289
290/**
291 * list_splice - join two lists
292 * @list: the new list to add.
293 * @head: the place to add it in the first list.
294 */
295static inline void list_splice(struct list_head *list, struct list_head *head)
296{
297 if (!list_empty(list))
298 __list_splice(list, head);
299}
300
301/**
302 * list_splice_init - join two lists and reinitialise the emptied list.
303 * @list: the new list to add.
304 * @head: the place to add it in the first list.
305 *
306 * The list at @list is reinitialised
307 */
308static inline void list_splice_init(struct list_head *list,
309 struct list_head *head)
310{
311 if (!list_empty(list)) {
312 __list_splice(list, head);
313 INIT_LIST_HEAD(list);
314 }
315}
316
317/**
318 * list_entry - get the struct for this entry
319 * @ptr: the &struct list_head pointer.
320 * @type: the type of the struct this is embedded in.
321 * @member: the name of the list_struct within the struct.
322 */
323#define list_entry(ptr, type, member) \
324 container_of(ptr, type, member)
325
326/**
327 * list_for_each - iterate over a list
328 * @pos: the &struct list_head to use as a loop counter.
329 * @head: the head for your list.
330 */
331#define list_for_each(pos, head) \
332 for (pos = (head)->next; prefetch(pos->next), pos != (head); \
333 pos = pos->next)
334
335/**
336 * __list_for_each - iterate over a list
337 * @pos: the &struct list_head to use as a loop counter.
338 * @head: the head for your list.
339 *
340 * This variant differs from list_for_each() in that it's the
341 * simplest possible list iteration code, no prefetching is done.
342 * Use this for code that knows the list to be very short (empty
343 * or 1 entry) most of the time.
344 */
345#define __list_for_each(pos, head) \
346 for (pos = (head)->next; pos != (head); pos = pos->next)
347
348/**
349 * list_for_each_prev - iterate over a list backwards
350 * @pos: the &struct list_head to use as a loop counter.
351 * @head: the head for your list.
352 */
353#define list_for_each_prev(pos, head) \
354 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
355 pos = pos->prev)
356
357/**
358 * list_for_each_safe - iterate over a list safe against removal of list entry
359 * @pos: the &struct list_head to use as a loop counter.
360 * @n: another &struct list_head to use as temporary storage
361 * @head: the head for your list.
362 */
363#define list_for_each_safe(pos, n, head) \
364 for (pos = (head)->next, n = pos->next; pos != (head); \
365 pos = n, n = pos->next)
366
367/**
368 * list_for_each_entry - iterate over list of given type
369 * @pos: the type * to use as a loop counter.
370 * @head: the head for your list.
371 * @member: the name of the list_struct within the struct.
372 */
373#define list_for_each_entry(pos, head, member) \
374 for (pos = list_entry((head)->next, typeof(*pos), member); \
375 prefetch(pos->member.next), &pos->member != (head); \
376 pos = list_entry(pos->member.next, typeof(*pos), member))
377
378/**
379 * list_for_each_entry_reverse - iterate backwards over list of given type.
380 * @pos: the type * to use as a loop counter.
381 * @head: the head for your list.
382 * @member: the name of the list_struct within the struct.
383 */
384#define list_for_each_entry_reverse(pos, head, member) \
385 for (pos = list_entry((head)->prev, typeof(*pos), member); \
386 prefetch(pos->member.prev), &pos->member != (head); \
387 pos = list_entry(pos->member.prev, typeof(*pos), member))
388
389/**
390 * list_prepare_entry - prepare a pos entry for use as a start point in
391 * list_for_each_entry_continue
392 * @pos: the type * to use as a start point
393 * @head: the head of the list
394 * @member: the name of the list_struct within the struct.
395 */
396#define list_prepare_entry(pos, head, member) \
397 ((pos) ? : list_entry(head, typeof(*pos), member))
398
399/**
400 * list_for_each_entry_continue - iterate over list of given type
401 * continuing after existing point
402 * @pos: the type * to use as a loop counter.
403 * @head: the head for your list.
404 * @member: the name of the list_struct within the struct.
405 */
406#define list_for_each_entry_continue(pos, head, member) \
407 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
408 prefetch(pos->member.next), &pos->member != (head); \
409 pos = list_entry(pos->member.next, typeof(*pos), member))
410
411/**
412 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
413 * @pos: the type * to use as a loop counter.
414 * @n: another type * to use as temporary storage
415 * @head: the head for your list.
416 * @member: the name of the list_struct within the struct.
417 */
418#define list_for_each_entry_safe(pos, n, head, member) \
419 for (pos = list_entry((head)->next, typeof(*pos), member), \
420 n = list_entry(pos->member.next, typeof(*pos), member); \
421 &pos->member != (head); \
422 pos = n, n = list_entry(n->member.next, typeof(*n), member))
423
424/**
Arnaldo Carvalho de Melo74459dc2005-08-09 20:15:51 -0700425 * list_for_each_entry_safe_continue - iterate over list of given type
426 * continuing after existing point safe against removal of list entry
427 * @pos: the type * to use as a loop counter.
428 * @n: another type * to use as temporary storage
429 * @head: the head for your list.
430 * @member: the name of the list_struct within the struct.
431 */
432#define list_for_each_entry_safe_continue(pos, n, head, member) \
Arnaldo Carvalho de Melo8c60f3f2005-08-10 12:59:38 -0300433 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
434 n = list_entry(pos->member.next, typeof(*pos), member); \
Arnaldo Carvalho de Melo74459dc2005-08-09 20:15:51 -0700435 &pos->member != (head); \
436 pos = n, n = list_entry(n->member.next, typeof(*n), member))
437
438/**
David Howells0ad42352006-01-09 20:51:31 -0800439 * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
440 * removal of list entry
441 * @pos: the type * to use as a loop counter.
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.
445 */
446#define list_for_each_entry_safe_reverse(pos, n, head, member) \
447 for (pos = list_entry((head)->prev, typeof(*pos), member), \
448 n = list_entry(pos->member.prev, typeof(*pos), member); \
449 &pos->member != (head); \
450 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
451
452/**
Linus Torvalds1da177e2005-04-16 15:20:36 -0700453 * list_for_each_rcu - iterate over an rcu-protected list
454 * @pos: the &struct list_head to use as a loop counter.
455 * @head: the head for your list.
456 *
457 * This list-traversal primitive may safely run concurrently with
458 * the _rcu list-mutation primitives such as list_add_rcu()
459 * as long as the traversal is guarded by rcu_read_lock().
460 */
461#define list_for_each_rcu(pos, head) \
Herbert Xub24d18a2005-10-16 20:29:20 -0700462 for (pos = (head)->next; \
463 prefetch(rcu_dereference(pos)->next), pos != (head); \
464 pos = pos->next)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465
466#define __list_for_each_rcu(pos, head) \
Herbert Xub24d18a2005-10-16 20:29:20 -0700467 for (pos = (head)->next; \
468 rcu_dereference(pos) != (head); \
469 pos = pos->next)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700470
471/**
472 * list_for_each_safe_rcu - iterate over an rcu-protected list safe
473 * against removal of list entry
474 * @pos: the &struct list_head to use as a loop counter.
475 * @n: another &struct list_head to use as temporary storage
476 * @head: the head for your list.
477 *
478 * This list-traversal primitive may safely run concurrently with
479 * the _rcu list-mutation primitives such as list_add_rcu()
480 * as long as the traversal is guarded by rcu_read_lock().
481 */
482#define list_for_each_safe_rcu(pos, n, head) \
Herbert Xub24d18a2005-10-16 20:29:20 -0700483 for (pos = (head)->next; \
484 n = rcu_dereference(pos)->next, pos != (head); \
485 pos = n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486
487/**
488 * list_for_each_entry_rcu - iterate over rcu list of given type
489 * @pos: the type * to use as a loop counter.
490 * @head: the head for your list.
491 * @member: the name of the list_struct within the struct.
492 *
493 * This list-traversal primitive may safely run concurrently with
494 * the _rcu list-mutation primitives such as list_add_rcu()
495 * as long as the traversal is guarded by rcu_read_lock().
496 */
Herbert Xub24d18a2005-10-16 20:29:20 -0700497#define list_for_each_entry_rcu(pos, head, member) \
498 for (pos = list_entry((head)->next, typeof(*pos), member); \
499 prefetch(rcu_dereference(pos)->member.next), \
500 &pos->member != (head); \
501 pos = list_entry(pos->member.next, typeof(*pos), member))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502
503
504/**
505 * list_for_each_continue_rcu - iterate over an rcu-protected list
506 * continuing after existing point.
507 * @pos: the &struct list_head to use as a loop counter.
508 * @head: the head for your list.
509 *
510 * This list-traversal primitive may safely run concurrently with
511 * the _rcu list-mutation primitives such as list_add_rcu()
512 * as long as the traversal is guarded by rcu_read_lock().
513 */
514#define list_for_each_continue_rcu(pos, head) \
Herbert Xub24d18a2005-10-16 20:29:20 -0700515 for ((pos) = (pos)->next; \
516 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
517 (pos) = (pos)->next)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518
519/*
520 * Double linked lists with a single pointer list head.
521 * Mostly useful for hash tables where the two pointer list head is
522 * too wasteful.
523 * You lose the ability to access the tail in O(1).
524 */
525
526struct hlist_head {
527 struct hlist_node *first;
528};
529
530struct hlist_node {
531 struct hlist_node *next, **pprev;
532};
533
534#define HLIST_HEAD_INIT { .first = NULL }
535#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
536#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
537#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
538
539static inline int hlist_unhashed(const struct hlist_node *h)
540{
541 return !h->pprev;
542}
543
544static inline int hlist_empty(const struct hlist_head *h)
545{
546 return !h->first;
547}
548
549static inline void __hlist_del(struct hlist_node *n)
550{
551 struct hlist_node *next = n->next;
552 struct hlist_node **pprev = n->pprev;
553 *pprev = next;
554 if (next)
555 next->pprev = pprev;
556}
557
558static inline void hlist_del(struct hlist_node *n)
559{
560 __hlist_del(n);
561 n->next = LIST_POISON1;
562 n->pprev = LIST_POISON2;
563}
564
565/**
566 * hlist_del_rcu - deletes entry from hash list without re-initialization
567 * @n: the element to delete from the hash list.
568 *
569 * Note: list_unhashed() on entry does not return true after this,
570 * the entry is in an undefined state. It is useful for RCU based
571 * lockfree traversal.
572 *
573 * In particular, it means that we can not poison the forward
574 * pointers that may still be used for walking the hash list.
575 *
576 * The caller must take whatever precautions are necessary
577 * (such as holding appropriate locks) to avoid racing
578 * with another list-mutation primitive, such as hlist_add_head_rcu()
579 * or hlist_del_rcu(), running on this same list.
580 * However, it is perfectly legal to run concurrently with
581 * the _rcu list-traversal primitives, such as
582 * hlist_for_each_entry().
583 */
584static inline void hlist_del_rcu(struct hlist_node *n)
585{
586 __hlist_del(n);
587 n->pprev = LIST_POISON2;
588}
589
590static inline void hlist_del_init(struct hlist_node *n)
591{
592 if (n->pprev) {
593 __hlist_del(n);
594 INIT_HLIST_NODE(n);
595 }
596}
597
Ingo Molnarb88cb422005-12-12 00:37:11 -0800598/*
599 * hlist_replace_rcu - replace old entry by new one
600 * @old : the element to be replaced
601 * @new : the new element to insert
602 *
603 * The old entry will be replaced with the new entry atomically.
604 */
605static inline void hlist_replace_rcu(struct hlist_node *old,
606 struct hlist_node *new)
607{
608 struct hlist_node *next = old->next;
609
610 new->next = next;
611 new->pprev = old->pprev;
612 smp_wmb();
613 if (next)
614 new->next->pprev = &new->next;
615 *new->pprev = new;
616 old->pprev = LIST_POISON2;
617}
618
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
620{
621 struct hlist_node *first = h->first;
622 n->next = first;
623 if (first)
624 first->pprev = &n->next;
625 h->first = n;
626 n->pprev = &h->first;
627}
628
629
630/**
631 * hlist_add_head_rcu - adds the specified element to the specified hlist,
632 * while permitting racing traversals.
633 * @n: the element to add to the hash list.
634 * @h: the list to add to.
635 *
636 * The caller must take whatever precautions are necessary
637 * (such as holding appropriate locks) to avoid racing
638 * with another list-mutation primitive, such as hlist_add_head_rcu()
639 * or hlist_del_rcu(), running on this same list.
640 * However, it is perfectly legal to run concurrently with
641 * the _rcu list-traversal primitives, such as
Paul E. McKenney665a7582005-11-07 00:59:17 -0800642 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
Linus Torvalds1da177e2005-04-16 15:20:36 -0700643 * problems on Alpha CPUs. Regardless of the type of CPU, the
644 * list-traversal primitive must be guarded by rcu_read_lock().
645 */
646static inline void hlist_add_head_rcu(struct hlist_node *n,
647 struct hlist_head *h)
648{
649 struct hlist_node *first = h->first;
650 n->next = first;
651 n->pprev = &h->first;
652 smp_wmb();
653 if (first)
654 first->pprev = &n->next;
655 h->first = n;
656}
657
658/* next must be != NULL */
659static inline void hlist_add_before(struct hlist_node *n,
660 struct hlist_node *next)
661{
662 n->pprev = next->pprev;
663 n->next = next;
664 next->pprev = &n->next;
665 *(n->pprev) = n;
666}
667
668static inline void hlist_add_after(struct hlist_node *n,
669 struct hlist_node *next)
670{
671 next->next = n->next;
672 n->next = next;
673 next->pprev = &n->next;
674
675 if(next->next)
676 next->next->pprev = &next->next;
677}
678
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700679/**
680 * hlist_add_before_rcu - adds the specified element to the specified hlist
681 * before the specified node while permitting racing traversals.
682 * @n: the new element to add to the hash list.
683 * @next: the existing element to add the new element before.
684 *
685 * The caller must take whatever precautions are necessary
686 * (such as holding appropriate locks) to avoid racing
687 * with another list-mutation primitive, such as hlist_add_head_rcu()
688 * or hlist_del_rcu(), running on this same list.
689 * However, it is perfectly legal to run concurrently with
690 * the _rcu list-traversal primitives, such as
Paul E. McKenney665a7582005-11-07 00:59:17 -0800691 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700692 * problems on Alpha CPUs.
693 */
Robert Olssone5b43762005-08-25 13:01:03 -0700694static inline void hlist_add_before_rcu(struct hlist_node *n,
695 struct hlist_node *next)
696{
697 n->pprev = next->pprev;
698 n->next = next;
699 smp_wmb();
700 next->pprev = &n->next;
701 *(n->pprev) = n;
702}
703
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700704/**
705 * hlist_add_after_rcu - adds the specified element to the specified hlist
706 * after the specified node while permitting racing traversals.
707 * @prev: the existing element to add the new element after.
708 * @n: the new element to add to the hash list.
709 *
710 * The caller must take whatever precautions are necessary
711 * (such as holding appropriate locks) to avoid racing
712 * with another list-mutation primitive, such as hlist_add_head_rcu()
713 * or hlist_del_rcu(), running on this same list.
714 * However, it is perfectly legal to run concurrently with
715 * the _rcu list-traversal primitives, such as
Paul E. McKenney665a7582005-11-07 00:59:17 -0800716 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
Paul E. McKenneycf4ef012005-08-25 16:08:37 -0700717 * problems on Alpha CPUs.
718 */
Robert Olssone5b43762005-08-25 13:01:03 -0700719static inline void hlist_add_after_rcu(struct hlist_node *prev,
720 struct hlist_node *n)
721{
722 n->next = prev->next;
723 n->pprev = &prev->next;
724 smp_wmb();
725 prev->next = n;
726 if (n->next)
727 n->next->pprev = &n->next;
728}
729
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
731
732#define hlist_for_each(pos, head) \
733 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
734 pos = pos->next)
735
736#define hlist_for_each_safe(pos, n, head) \
737 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
738 pos = n)
739
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740/**
741 * hlist_for_each_entry - iterate over list of given type
742 * @tpos: the type * to use as a loop counter.
743 * @pos: the &struct hlist_node to use as a loop counter.
744 * @head: the head for your list.
745 * @member: the name of the hlist_node within the struct.
746 */
747#define hlist_for_each_entry(tpos, pos, head, member) \
748 for (pos = (head)->first; \
749 pos && ({ prefetch(pos->next); 1;}) && \
750 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
751 pos = pos->next)
752
753/**
754 * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
755 * @tpos: the type * to use as a loop counter.
756 * @pos: the &struct hlist_node to use as a loop counter.
757 * @member: the name of the hlist_node within the struct.
758 */
759#define hlist_for_each_entry_continue(tpos, pos, member) \
760 for (pos = (pos)->next; \
761 pos && ({ prefetch(pos->next); 1;}) && \
762 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
763 pos = pos->next)
764
765/**
766 * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
767 * @tpos: the type * to use as a loop counter.
768 * @pos: the &struct hlist_node to use as a loop counter.
769 * @member: the name of the hlist_node within the struct.
770 */
771#define hlist_for_each_entry_from(tpos, pos, member) \
772 for (; pos && ({ prefetch(pos->next); 1;}) && \
773 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
774 pos = pos->next)
775
776/**
777 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
778 * @tpos: the type * to use as a loop counter.
779 * @pos: the &struct hlist_node to use as a loop counter.
780 * @n: another &struct hlist_node to use as temporary storage
781 * @head: the head for your list.
782 * @member: the name of the hlist_node within the struct.
783 */
784#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
785 for (pos = (head)->first; \
786 pos && ({ n = pos->next; 1; }) && \
787 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
788 pos = n)
789
790/**
791 * hlist_for_each_entry_rcu - iterate over rcu list of given type
Paul E. McKenney665a7582005-11-07 00:59:17 -0800792 * @tpos: the type * to use as a loop counter.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700793 * @pos: the &struct hlist_node to use as a loop counter.
794 * @head: the head for your list.
795 * @member: the name of the hlist_node within the struct.
796 *
797 * This list-traversal primitive may safely run concurrently with
Paul E. McKenneye1ba0da2005-04-16 15:25:51 -0700798 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
Linus Torvalds1da177e2005-04-16 15:20:36 -0700799 * as long as the traversal is guarded by rcu_read_lock().
800 */
801#define hlist_for_each_entry_rcu(tpos, pos, head, member) \
802 for (pos = (head)->first; \
Herbert Xub24d18a2005-10-16 20:29:20 -0700803 rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) && \
Linus Torvalds1da177e2005-04-16 15:20:36 -0700804 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
Herbert Xub24d18a2005-10-16 20:29:20 -0700805 pos = pos->next)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806
807#else
808#warning "don't include kernel headers in userspace"
809#endif /* __KERNEL__ */
810#endif