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