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
21struct 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
30static 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
43static 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
53extern 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
67static inline void list_add(struct list_head *new, struct list_head *head)
68{
69	__list_add(new, head, head->next);
70}
71#else
72extern 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 */
84static 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 */
95static 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 */
121static 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 */
142static 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 */
155static 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
168static 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
175extern 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 */
202static 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 */
215static 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
224static 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 */
239static 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 */
254static 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 */
265static 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 */
276static 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 */
288static 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 */
298static 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 */
316static 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
322static 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 */
341static 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 */
354static 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 */
380static 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_entry	-	iterate over list of given type
482 * @pos:	the type * to use as a loop cursor.
483 * @head:	the head for your list.
484 * @member:	the name of the list_struct within the struct.
485 */
486#define list_for_each_entry(pos, head, member)				\
487	for (pos = list_entry((head)->next, typeof(*pos), member);	\
488	     prefetch(pos->member.next), &pos->member != (head); 	\
489	     pos = list_entry(pos->member.next, typeof(*pos), member))
490
491/**
492 * list_for_each_entry_reverse - iterate backwards 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_reverse(pos, head, member)			\
498	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
499	     prefetch(pos->member.prev), &pos->member != (head); 	\
500	     pos = list_entry(pos->member.prev, typeof(*pos), member))
501
502/**
503 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
504 * @pos:	the type * to use as a start point
505 * @head:	the head of the list
506 * @member:	the name of the list_struct within the struct.
507 *
508 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
509 */
510#define list_prepare_entry(pos, head, member) \
511	((pos) ? : list_entry(head, typeof(*pos), member))
512
513/**
514 * list_for_each_entry_continue - continue iteration over list of given type
515 * @pos:	the type * to use as a loop cursor.
516 * @head:	the head for your list.
517 * @member:	the name of the list_struct within the struct.
518 *
519 * Continue to iterate over list of given type, continuing after
520 * the current position.
521 */
522#define list_for_each_entry_continue(pos, head, member) 		\
523	for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
524	     prefetch(pos->member.next), &pos->member != (head);	\
525	     pos = list_entry(pos->member.next, typeof(*pos), member))
526
527/**
528 * list_for_each_entry_from - iterate over list of given type from the current point
529 * @pos:	the type * to use as a loop cursor.
530 * @head:	the head for your list.
531 * @member:	the name of the list_struct within the struct.
532 *
533 * Iterate over list of given type, continuing from current position.
534 */
535#define list_for_each_entry_from(pos, head, member) 			\
536	for (; prefetch(pos->member.next), &pos->member != (head);	\
537	     pos = list_entry(pos->member.next, typeof(*pos), member))
538
539/**
540 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
541 * @pos:	the type * to use as a loop cursor.
542 * @n:		another type * to use as temporary storage
543 * @head:	the head for your list.
544 * @member:	the name of the list_struct within the struct.
545 */
546#define list_for_each_entry_safe(pos, n, head, member)			\
547	for (pos = list_entry((head)->next, typeof(*pos), member),	\
548		n = list_entry(pos->member.next, typeof(*pos), member);	\
549	     &pos->member != (head); 					\
550	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
551
552/**
553 * list_for_each_entry_safe_continue
554 * @pos:	the type * to use as a loop cursor.
555 * @n:		another type * to use as temporary storage
556 * @head:	the head for your list.
557 * @member:	the name of the list_struct within the struct.
558 *
559 * Iterate over list of given type, continuing after current point,
560 * safe against removal of list entry.
561 */
562#define list_for_each_entry_safe_continue(pos, n, head, member) 		\
563	for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
564		n = list_entry(pos->member.next, typeof(*pos), member);		\
565	     &pos->member != (head);						\
566	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
567
568/**
569 * list_for_each_entry_safe_from
570 * @pos:	the type * to use as a loop cursor.
571 * @n:		another type * to use as temporary storage
572 * @head:	the head for your list.
573 * @member:	the name of the list_struct within the struct.
574 *
575 * Iterate over list of given type from current point, safe against
576 * removal of list entry.
577 */
578#define list_for_each_entry_safe_from(pos, n, head, member) 			\
579	for (n = list_entry(pos->member.next, typeof(*pos), member);		\
580	     &pos->member != (head);						\
581	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
582
583/**
584 * list_for_each_entry_safe_reverse
585 * @pos:	the type * to use as a loop cursor.
586 * @n:		another type * to use as temporary storage
587 * @head:	the head for your list.
588 * @member:	the name of the list_struct within the struct.
589 *
590 * Iterate backwards over list of given type, safe against removal
591 * of list entry.
592 */
593#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
594	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
595		n = list_entry(pos->member.prev, typeof(*pos), member);	\
596	     &pos->member != (head); 					\
597	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))
598
599/**
600 * list_for_each_rcu	-	iterate over an rcu-protected list
601 * @pos:	the &struct list_head to use as a loop cursor.
602 * @head:	the head for your list.
603 *
604 * This list-traversal primitive may safely run concurrently with
605 * the _rcu list-mutation primitives such as list_add_rcu()
606 * as long as the traversal is guarded by rcu_read_lock().
607 */
608#define list_for_each_rcu(pos, head) \
609	for (pos = (head)->next; \
610		prefetch(rcu_dereference(pos)->next), pos != (head); \
611        	pos = pos->next)
612
613#define __list_for_each_rcu(pos, head) \
614	for (pos = (head)->next; \
615		rcu_dereference(pos) != (head); \
616        	pos = pos->next)
617
618/**
619 * list_for_each_safe_rcu
620 * @pos:	the &struct list_head to use as a loop cursor.
621 * @n:		another &struct list_head to use as temporary storage
622 * @head:	the head for your list.
623 *
624 * Iterate over an rcu-protected list, safe against removal of list entry.
625 *
626 * This list-traversal primitive may safely run concurrently with
627 * the _rcu list-mutation primitives such as list_add_rcu()
628 * as long as the traversal is guarded by rcu_read_lock().
629 */
630#define list_for_each_safe_rcu(pos, n, head) \
631	for (pos = (head)->next; \
632		n = rcu_dereference(pos)->next, pos != (head); \
633		pos = n)
634
635/**
636 * list_for_each_entry_rcu	-	iterate over rcu list of given type
637 * @pos:	the type * to use as a loop cursor.
638 * @head:	the head for your list.
639 * @member:	the name of the list_struct within the struct.
640 *
641 * This list-traversal primitive may safely run concurrently with
642 * the _rcu list-mutation primitives such as list_add_rcu()
643 * as long as the traversal is guarded by rcu_read_lock().
644 */
645#define list_for_each_entry_rcu(pos, head, member) \
646	for (pos = list_entry((head)->next, typeof(*pos), member); \
647		prefetch(rcu_dereference(pos)->member.next), \
648			&pos->member != (head); \
649		pos = list_entry(pos->member.next, typeof(*pos), member))
650
651
652/**
653 * list_for_each_continue_rcu
654 * @pos:	the &struct list_head to use as a loop cursor.
655 * @head:	the head for your list.
656 *
657 * Iterate over an rcu-protected list, continuing after current point.
658 *
659 * This list-traversal primitive may safely run concurrently with
660 * the _rcu list-mutation primitives such as list_add_rcu()
661 * as long as the traversal is guarded by rcu_read_lock().
662 */
663#define list_for_each_continue_rcu(pos, head) \
664	for ((pos) = (pos)->next; \
665		prefetch(rcu_dereference((pos))->next), (pos) != (head); \
666        	(pos) = (pos)->next)
667
668/*
669 * Double linked lists with a single pointer list head.
670 * Mostly useful for hash tables where the two pointer list head is
671 * too wasteful.
672 * You lose the ability to access the tail in O(1).
673 */
674
675struct hlist_head {
676	struct hlist_node *first;
677};
678
679struct hlist_node {
680	struct hlist_node *next, **pprev;
681};
682
683#define HLIST_HEAD_INIT { .first = NULL }
684#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
685#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
686static inline void INIT_HLIST_NODE(struct hlist_node *h)
687{
688	h->next = NULL;
689	h->pprev = NULL;
690}
691
692static inline int hlist_unhashed(const struct hlist_node *h)
693{
694	return !h->pprev;
695}
696
697static inline int hlist_empty(const struct hlist_head *h)
698{
699	return !h->first;
700}
701
702static inline void __hlist_del(struct hlist_node *n)
703{
704	struct hlist_node *next = n->next;
705	struct hlist_node **pprev = n->pprev;
706	*pprev = next;
707	if (next)
708		next->pprev = pprev;
709}
710
711static inline void hlist_del(struct hlist_node *n)
712{
713	__hlist_del(n);
714	n->next = LIST_POISON1;
715	n->pprev = LIST_POISON2;
716}
717
718/**
719 * hlist_del_rcu - deletes entry from hash list without re-initialization
720 * @n: the element to delete from the hash list.
721 *
722 * Note: list_unhashed() on entry does not return true after this,
723 * the entry is in an undefined state. It is useful for RCU based
724 * lockfree traversal.
725 *
726 * In particular, it means that we can not poison the forward
727 * pointers that may still be used for walking the hash list.
728 *
729 * The caller must take whatever precautions are necessary
730 * (such as holding appropriate locks) to avoid racing
731 * with another list-mutation primitive, such as hlist_add_head_rcu()
732 * or hlist_del_rcu(), running on this same list.
733 * However, it is perfectly legal to run concurrently with
734 * the _rcu list-traversal primitives, such as
735 * hlist_for_each_entry().
736 */
737static inline void hlist_del_rcu(struct hlist_node *n)
738{
739	__hlist_del(n);
740	n->pprev = LIST_POISON2;
741}
742
743static inline void hlist_del_init(struct hlist_node *n)
744{
745	if (!hlist_unhashed(n)) {
746		__hlist_del(n);
747		INIT_HLIST_NODE(n);
748	}
749}
750
751/**
752 * hlist_replace_rcu - replace old entry by new one
753 * @old : the element to be replaced
754 * @new : the new element to insert
755 *
756 * The @old entry will be replaced with the @new entry atomically.
757 */
758static inline void hlist_replace_rcu(struct hlist_node *old,
759					struct hlist_node *new)
760{
761	struct hlist_node *next = old->next;
762
763	new->next = next;
764	new->pprev = old->pprev;
765	smp_wmb();
766	if (next)
767		new->next->pprev = &new->next;
768	*new->pprev = new;
769	old->pprev = LIST_POISON2;
770}
771
772static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
773{
774	struct hlist_node *first = h->first;
775	n->next = first;
776	if (first)
777		first->pprev = &n->next;
778	h->first = n;
779	n->pprev = &h->first;
780}
781
782
783/**
784 * hlist_add_head_rcu
785 * @n: the element to add to the hash list.
786 * @h: the list to add to.
787 *
788 * Description:
789 * Adds the specified element to the specified hlist,
790 * while permitting racing traversals.
791 *
792 * The caller must take whatever precautions are necessary
793 * (such as holding appropriate locks) to avoid racing
794 * with another list-mutation primitive, such as hlist_add_head_rcu()
795 * or hlist_del_rcu(), running on this same list.
796 * However, it is perfectly legal to run concurrently with
797 * the _rcu list-traversal primitives, such as
798 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
799 * problems on Alpha CPUs.  Regardless of the type of CPU, the
800 * list-traversal primitive must be guarded by rcu_read_lock().
801 */
802static inline void hlist_add_head_rcu(struct hlist_node *n,
803					struct hlist_head *h)
804{
805	struct hlist_node *first = h->first;
806	n->next = first;
807	n->pprev = &h->first;
808	smp_wmb();
809	if (first)
810		first->pprev = &n->next;
811	h->first = n;
812}
813
814/* next must be != NULL */
815static inline void hlist_add_before(struct hlist_node *n,
816					struct hlist_node *next)
817{
818	n->pprev = next->pprev;
819	n->next = next;
820	next->pprev = &n->next;
821	*(n->pprev) = n;
822}
823
824static inline void hlist_add_after(struct hlist_node *n,
825					struct hlist_node *next)
826{
827	next->next = n->next;
828	n->next = next;
829	next->pprev = &n->next;
830
831	if(next->next)
832		next->next->pprev  = &next->next;
833}
834
835/**
836 * hlist_add_before_rcu
837 * @n: the new element to add to the hash list.
838 * @next: the existing element to add the new element before.
839 *
840 * Description:
841 * Adds the specified element to the specified hlist
842 * before the specified node while permitting racing traversals.
843 *
844 * The caller must take whatever precautions are necessary
845 * (such as holding appropriate locks) to avoid racing
846 * with another list-mutation primitive, such as hlist_add_head_rcu()
847 * or hlist_del_rcu(), running on this same list.
848 * However, it is perfectly legal to run concurrently with
849 * the _rcu list-traversal primitives, such as
850 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
851 * problems on Alpha CPUs.
852 */
853static inline void hlist_add_before_rcu(struct hlist_node *n,
854					struct hlist_node *next)
855{
856	n->pprev = next->pprev;
857	n->next = next;
858	smp_wmb();
859	next->pprev = &n->next;
860	*(n->pprev) = n;
861}
862
863/**
864 * hlist_add_after_rcu
865 * @prev: the existing element to add the new element after.
866 * @n: the new element to add to the hash list.
867 *
868 * Description:
869 * Adds the specified element to the specified hlist
870 * after the specified node while permitting racing traversals.
871 *
872 * The caller must take whatever precautions are necessary
873 * (such as holding appropriate locks) to avoid racing
874 * with another list-mutation primitive, such as hlist_add_head_rcu()
875 * or hlist_del_rcu(), running on this same list.
876 * However, it is perfectly legal to run concurrently with
877 * the _rcu list-traversal primitives, such as
878 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
879 * problems on Alpha CPUs.
880 */
881static inline void hlist_add_after_rcu(struct hlist_node *prev,
882				       struct hlist_node *n)
883{
884	n->next = prev->next;
885	n->pprev = &prev->next;
886	smp_wmb();
887	prev->next = n;
888	if (n->next)
889		n->next->pprev = &n->next;
890}
891
892#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
893
894#define hlist_for_each(pos, head) \
895	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
896	     pos = pos->next)
897
898#define hlist_for_each_safe(pos, n, head) \
899	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
900	     pos = n)
901
902/**
903 * hlist_for_each_entry	- iterate over list of given type
904 * @tpos:	the type * to use as a loop cursor.
905 * @pos:	the &struct hlist_node to use as a loop cursor.
906 * @head:	the head for your list.
907 * @member:	the name of the hlist_node within the struct.
908 */
909#define hlist_for_each_entry(tpos, pos, head, member)			 \
910	for (pos = (head)->first;					 \
911	     pos && ({ prefetch(pos->next); 1;}) &&			 \
912		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
913	     pos = pos->next)
914
915/**
916 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
917 * @tpos:	the type * to use as a loop cursor.
918 * @pos:	the &struct hlist_node to use as a loop cursor.
919 * @member:	the name of the hlist_node within the struct.
920 */
921#define hlist_for_each_entry_continue(tpos, pos, member)		 \
922	for (pos = (pos)->next;						 \
923	     pos && ({ prefetch(pos->next); 1;}) &&			 \
924		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
925	     pos = pos->next)
926
927/**
928 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
929 * @tpos:	the type * to use as a loop cursor.
930 * @pos:	the &struct hlist_node to use as a loop cursor.
931 * @member:	the name of the hlist_node within the struct.
932 */
933#define hlist_for_each_entry_from(tpos, pos, member)			 \
934	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
935		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
936	     pos = pos->next)
937
938/**
939 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
940 * @tpos:	the type * to use as a loop cursor.
941 * @pos:	the &struct hlist_node to use as a loop cursor.
942 * @n:		another &struct hlist_node to use as temporary storage
943 * @head:	the head for your list.
944 * @member:	the name of the hlist_node within the struct.
945 */
946#define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
947	for (pos = (head)->first;					 \
948	     pos && ({ n = pos->next; 1; }) && 				 \
949		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
950	     pos = n)
951
952/**
953 * hlist_for_each_entry_rcu - iterate over rcu list of given type
954 * @tpos:	the type * to use as a loop cursor.
955 * @pos:	the &struct hlist_node to use as a loop cursor.
956 * @head:	the head for your list.
957 * @member:	the name of the hlist_node within the struct.
958 *
959 * This list-traversal primitive may safely run concurrently with
960 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
961 * as long as the traversal is guarded by rcu_read_lock().
962 */
963#define hlist_for_each_entry_rcu(tpos, pos, head, member)		 \
964	for (pos = (head)->first;					 \
965	     rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&	 \
966		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
967	     pos = pos->next)
968
969#else
970#warning "don't include kernel headers in userspace"
971#endif /* __KERNEL__ */
972#endif
973