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