[PATCH] Add list_for_each_entry_safe_reverse()
[linux-2.6.git] / include / linux / list.h
1 #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
28 struct 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  */
47 static 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  */
65 static 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  */
78 static 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  */
89 static 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  */
115 static 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  */
136 static 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  */
149 static 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  */
161 static 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
188  * the newly deleted entry.  Instead, either synchronize_rcu()
189  * or call_rcu() must be used to defer freeing until an RCU
190  * grace period has elapsed.
191  */
192 static 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  */
205 static inline void list_replace_rcu(struct list_head *old,
206                                 struct list_head *new)
207 {
208         new->next = old->next;
209         new->prev = old->prev;
210         smp_wmb();
211         new->next->prev = new;
212         new->prev->next = new;
213         old->prev = LIST_POISON2;
214 }
215
216 /**
217  * list_del_init - deletes entry from list and reinitialize it.
218  * @entry: the element to delete from the list.
219  */
220 static 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  */
231 static 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  */
242 static 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  */
253 static 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  */
270 static 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
276 static 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  */
295 static 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  */
308 static 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 /**
425  * 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)                 \
433         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
434                 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))
437
438 /**
439  * 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 /**
453  * 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) \
462         for (pos = (head)->next; \
463                 prefetch(rcu_dereference(pos)->next), pos != (head); \
464                 pos = pos->next)
465
466 #define __list_for_each_rcu(pos, head) \
467         for (pos = (head)->next; \
468                 rcu_dereference(pos) != (head); \
469                 pos = pos->next)
470
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) \
483         for (pos = (head)->next; \
484                 n = rcu_dereference(pos)->next, pos != (head); \
485                 pos = n)
486
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  */
497 #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))
502
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) \
515         for ((pos) = (pos)->next; \
516                 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
517                 (pos) = (pos)->next)
518
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
526 struct hlist_head {
527         struct hlist_node *first;
528 };
529
530 struct 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
539 static inline int hlist_unhashed(const struct hlist_node *h)
540 {
541         return !h->pprev;
542 }
543
544 static inline int hlist_empty(const struct hlist_head *h)
545 {
546         return !h->first;
547 }
548
549 static 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
558 static 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  */
584 static inline void hlist_del_rcu(struct hlist_node *n)
585 {
586         __hlist_del(n);
587         n->pprev = LIST_POISON2;
588 }
589
590 static 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
598 /*
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  */
605 static 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
619 static 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
642  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
643  * problems on Alpha CPUs.  Regardless of the type of CPU, the
644  * list-traversal primitive must be guarded by rcu_read_lock().
645  */
646 static 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 */
659 static 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
668 static 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
679 /**
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
691  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
692  * problems on Alpha CPUs.
693  */
694 static 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
704 /**
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
716  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
717  * problems on Alpha CPUs.
718  */
719 static 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
730 #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
740 /**
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
792  * @tpos:       the type * to use as a loop counter.
793  * @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
798  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
799  * 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;                                        \
803              rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&     \
804                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
805              pos = pos->next)
806
807 #else
808 #warning "don't include kernel headers in userspace"
809 #endif /* __KERNEL__ */
810 #endif