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