1#ifndef _LINUX_LIST_H
2#define _LINUX_LIST_H
3
4#include "poison.h"
5
6#define LIST_HEAD_INIT(name) { &(name), &(name) }
7
8#define LIST_HEAD(name) \
9	struct list_head name = LIST_HEAD_INIT(name)
10
11static inline void INIT_LIST_HEAD(struct list_head *list)
12{
13	list->next = list;
14	list->prev = list;
15}
16
17/*
18 * Insert a new entry between two known consecutive entries.
19 *
20 * This is only for internal list manipulation where we know
21 * the prev/next entries already!
22 */
23#ifndef CONFIG_DEBUG_LIST
24static inline void __list_add(struct list_head *new,
25			      struct list_head *prev,
26			      struct list_head *next)
27{
28	next->prev = new;
29	new->next = next;
30	new->prev = prev;
31	prev->next = new;
32}
33#else
34extern void __list_add(struct list_head *new,
35			      struct list_head *prev,
36			      struct list_head *next);
37#endif
38
39/**
40 * list_add - add a new entry
41 * @new: new entry to be added
42 * @head: list head to add it after
43 *
44 * Insert a new entry after the specified head.
45 * This is good for implementing stacks.
46 */
47static inline void list_add(struct list_head *new, struct list_head *head)
48{
49	__list_add(new, head, head->next);
50}
51
52
53/**
54 * list_add_tail - add a new entry
55 * @new: new entry to be added
56 * @head: list head to add it before
57 *
58 * Insert a new entry before the specified head.
59 * This is useful for implementing queues.
60 */
61static inline void list_add_tail(struct list_head *new, struct list_head *head)
62{
63	__list_add(new, head->prev, head);
64}
65
66/*
67 * Delete a list entry by making the prev/next entries
68 * point to each other.
69 *
70 * This is only for internal list manipulation where we know
71 * the prev/next entries already!
72 */
73static inline void __list_del(struct list_head * prev, struct list_head * next)
74{
75	next->prev = prev;
76	prev->next = next;
77}
78
79/**
80 * list_del - deletes entry from list.
81 * @entry: the element to delete from the list.
82 * Note: list_empty() on entry does not return true after this, the entry is
83 * in an undefined state.
84 */
85#ifndef CONFIG_DEBUG_LIST
86static inline void list_del(struct list_head *entry)
87{
88	__list_del(entry->prev, entry->next);
89	entry->next = LIST_POISON1;
90	entry->prev = LIST_POISON2;
91}
92#else
93extern void list_del(struct list_head *entry);
94#endif
95
96/**
97 * list_replace - replace old entry by new one
98 * @old : the element to be replaced
99 * @new : the new element to insert
100 *
101 * If @old was empty, it will be overwritten.
102 */
103static inline void list_replace(struct list_head *old,
104				struct list_head *new)
105{
106	new->next = old->next;
107	new->next->prev = new;
108	new->prev = old->prev;
109	new->prev->next = new;
110}
111
112static inline void list_replace_init(struct list_head *old,
113					struct list_head *new)
114{
115	list_replace(old, new);
116	INIT_LIST_HEAD(old);
117}
118
119/**
120 * list_del_init - deletes entry from list and reinitialize it.
121 * @entry: the element to delete from the list.
122 */
123static inline void list_del_init(struct list_head *entry)
124{
125	__list_del(entry->prev, entry->next);
126	INIT_LIST_HEAD(entry);
127}
128
129/**
130 * list_move - delete from one list and add as another's head
131 * @list: the entry to move
132 * @head: the head that will precede our entry
133 */
134static inline void list_move(struct list_head *list, struct list_head *head)
135{
136	__list_del(list->prev, list->next);
137	list_add(list, head);
138}
139
140/**
141 * list_move_tail - delete from one list and add as another's tail
142 * @list: the entry to move
143 * @head: the head that will follow our entry
144 */
145static inline void list_move_tail(struct list_head *list,
146				  struct list_head *head)
147{
148	__list_del(list->prev, list->next);
149	list_add_tail(list, head);
150}
151
152/**
153 * list_is_last - tests whether @list is the last entry in list @head
154 * @list: the entry to test
155 * @head: the head of the list
156 */
157static inline int list_is_last(const struct list_head *list,
158				const struct list_head *head)
159{
160	return list->next == head;
161}
162
163/**
164 * list_empty - tests whether a list is empty
165 * @head: the list to test.
166 */
167static inline int list_empty(const struct list_head *head)
168{
169	return head->next == head;
170}
171
172/**
173 * list_empty_careful - tests whether a list is empty and not being modified
174 * @head: the list to test
175 *
176 * Description:
177 * tests whether a list is empty _and_ checks that no other CPU might be
178 * in the process of modifying either member (next or prev)
179 *
180 * NOTE: using list_empty_careful() without synchronization
181 * can only be safe if the only activity that can happen
182 * to the list entry is list_del_init(). Eg. it cannot be used
183 * if another CPU could re-list_add() it.
184 */
185static inline int list_empty_careful(const struct list_head *head)
186{
187	struct list_head *next = head->next;
188	return (next == head) && (next == head->prev);
189}
190
191/**
192 * list_rotate_left - rotate the list to the left
193 * @head: the head of the list
194 */
195static inline void list_rotate_left(struct list_head *head)
196{
197	struct list_head *first;
198
199	if (!list_empty(head)) {
200		first = head->next;
201		list_move_tail(first, head);
202	}
203}
204
205/**
206 * list_is_singular - tests whether a list has just one entry.
207 * @head: the list to test.
208 */
209static inline int list_is_singular(const struct list_head *head)
210{
211	return !list_empty(head) && (head->next == head->prev);
212}
213
214static inline void __list_cut_position(struct list_head *list,
215		struct list_head *head, struct list_head *entry)
216{
217	struct list_head *new_first = entry->next;
218	list->next = head->next;
219	list->next->prev = list;
220	list->prev = entry;
221	entry->next = list;
222	head->next = new_first;
223	new_first->prev = head;
224}
225
226/**
227 * list_cut_position - cut a list into two
228 * @list: a new list to add all removed entries
229 * @head: a list with entries
230 * @entry: an entry within head, could be the head itself
231 *	and if so we won't cut the list
232 *
233 * This helper moves the initial part of @head, up to and
234 * including @entry, from @head to @list. You should
235 * pass on @entry an element you know is on @head. @list
236 * should be an empty list or a list you do not care about
237 * losing its data.
238 *
239 */
240static inline void list_cut_position(struct list_head *list,
241		struct list_head *head, struct list_head *entry)
242{
243	if (list_empty(head))
244		return;
245	if (list_is_singular(head) &&
246		(head->next != entry && head != entry))
247		return;
248	if (entry == head)
249		INIT_LIST_HEAD(list);
250	else
251		__list_cut_position(list, head, entry);
252}
253
254static inline void __list_splice(const struct list_head *list,
255				 struct list_head *prev,
256				 struct list_head *next)
257{
258	struct list_head *first = list->next;
259	struct list_head *last = list->prev;
260
261	first->prev = prev;
262	prev->next = first;
263
264	last->next = next;
265	next->prev = last;
266}
267
268/**
269 * list_splice - join two lists, this is designed for stacks
270 * @list: the new list to add.
271 * @head: the place to add it in the first list.
272 */
273static inline void list_splice(const struct list_head *list,
274				struct list_head *head)
275{
276	if (!list_empty(list))
277		__list_splice(list, head, head->next);
278}
279
280/**
281 * list_splice_tail - join two lists, each list being a queue
282 * @list: the new list to add.
283 * @head: the place to add it in the first list.
284 */
285static inline void list_splice_tail(struct list_head *list,
286				struct list_head *head)
287{
288	if (!list_empty(list))
289		__list_splice(list, head->prev, head);
290}
291
292/**
293 * list_splice_init - join two lists and reinitialise the emptied list.
294 * @list: the new list to add.
295 * @head: the place to add it in the first list.
296 *
297 * The list at @list is reinitialised
298 */
299static inline void list_splice_init(struct list_head *list,
300				    struct list_head *head)
301{
302	if (!list_empty(list)) {
303		__list_splice(list, head, head->next);
304		INIT_LIST_HEAD(list);
305	}
306}
307
308/**
309 * list_splice_tail_init - join two lists and reinitialise the emptied list
310 * @list: the new list to add.
311 * @head: the place to add it in the first list.
312 *
313 * Each of the lists is a queue.
314 * The list at @list is reinitialised
315 */
316static inline void list_splice_tail_init(struct list_head *list,
317					 struct list_head *head)
318{
319	if (!list_empty(list)) {
320		__list_splice(list, head->prev, head);
321		INIT_LIST_HEAD(list);
322	}
323}
324
325/**
326 * list_entry - get the struct for this entry
327 * @ptr:	the &struct list_head pointer.
328 * @type:	the type of the struct this is embedded in.
329 * @member:	the name of the list_struct within the struct.
330 */
331#define list_entry(ptr, type, member) \
332	container_of(ptr, type, member)
333
334/**
335 * list_first_entry - get the first element from a list
336 * @ptr:	the list head to take the element from.
337 * @type:	the type of the struct this is embedded in.
338 * @member:	the name of the list_struct within the struct.
339 *
340 * Note, that list is expected to be not empty.
341 */
342#define list_first_entry(ptr, type, member) \
343	list_entry((ptr)->next, type, member)
344
345/**
346 * list_for_each	-	iterate over a list
347 * @pos:	the &struct list_head to use as a loop cursor.
348 * @head:	the head for your list.
349 */
350#define list_for_each(pos, head) \
351	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
352        	pos = pos->next)
353
354/**
355 * __list_for_each	-	iterate over a list
356 * @pos:	the &struct list_head to use as a loop cursor.
357 * @head:	the head for your list.
358 *
359 * This variant differs from list_for_each() in that it's the
360 * simplest possible list iteration code, no prefetching is done.
361 * Use this for code that knows the list to be very short (empty
362 * or 1 entry) most of the time.
363 */
364#define __list_for_each(pos, head) \
365	for (pos = (head)->next; pos != (head); pos = pos->next)
366
367/**
368 * list_for_each_prev	-	iterate over a list backwards
369 * @pos:	the &struct list_head to use as a loop cursor.
370 * @head:	the head for your list.
371 */
372#define list_for_each_prev(pos, head) \
373	for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
374        	pos = pos->prev)
375
376/**
377 * list_for_each_safe - iterate over a list safe against removal of list entry
378 * @pos:	the &struct list_head to use as a loop cursor.
379 * @n:		another &struct list_head to use as temporary storage
380 * @head:	the head for your list.
381 */
382#define list_for_each_safe(pos, n, head) \
383	for (pos = (head)->next, n = pos->next; pos != (head); \
384		pos = n, n = pos->next)
385
386/**
387 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
388 * @pos:	the &struct list_head to use as a loop cursor.
389 * @n:		another &struct list_head to use as temporary storage
390 * @head:	the head for your list.
391 */
392#define list_for_each_prev_safe(pos, n, head) \
393	for (pos = (head)->prev, n = pos->prev; \
394	     prefetch(pos->prev), pos != (head); \
395	     pos = n, n = pos->prev)
396
397/**
398 * list_for_each_entry	-	iterate over list of given type
399 * @pos:	the type * to use as a loop cursor.
400 * @head:	the head for your list.
401 * @member:	the name of the list_struct within the struct.
402 */
403#define list_for_each_entry(pos, head, member)				\
404	for (pos = list_entry((head)->next, typeof(*pos), member);	\
405	     prefetch(pos->member.next), &pos->member != (head); 	\
406	     pos = list_entry(pos->member.next, typeof(*pos), member))
407
408/**
409 * list_for_each_entry_reverse - iterate backwards over list of given type.
410 * @pos:	the type * to use as a loop cursor.
411 * @head:	the head for your list.
412 * @member:	the name of the list_struct within the struct.
413 */
414#define list_for_each_entry_reverse(pos, head, member)			\
415	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
416	     prefetch(pos->member.prev), &pos->member != (head); 	\
417	     pos = list_entry(pos->member.prev, typeof(*pos), member))
418
419/**
420 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
421 * @pos:	the type * to use as a start point
422 * @head:	the head of the list
423 * @member:	the name of the list_struct within the struct.
424 *
425 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
426 */
427#define list_prepare_entry(pos, head, member) \
428	((pos) ? : list_entry(head, typeof(*pos), member))
429
430/**
431 * list_for_each_entry_continue - continue iteration over list of given type
432 * @pos:	the type * to use as a loop cursor.
433 * @head:	the head for your list.
434 * @member:	the name of the list_struct within the struct.
435 *
436 * Continue to iterate over list of given type, continuing after
437 * the current position.
438 */
439#define list_for_each_entry_continue(pos, head, member) 		\
440	for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
441	     prefetch(pos->member.next), &pos->member != (head);	\
442	     pos = list_entry(pos->member.next, typeof(*pos), member))
443
444/**
445 * list_for_each_entry_continue_reverse - iterate backwards from the given point
446 * @pos:	the type * to use as a loop cursor.
447 * @head:	the head for your list.
448 * @member:	the name of the list_struct within the struct.
449 *
450 * Start to iterate over list of given type backwards, continuing after
451 * the current position.
452 */
453#define list_for_each_entry_continue_reverse(pos, head, member)		\
454	for (pos = list_entry(pos->member.prev, typeof(*pos), member);	\
455	     prefetch(pos->member.prev), &pos->member != (head);	\
456	     pos = list_entry(pos->member.prev, typeof(*pos), member))
457
458/**
459 * list_for_each_entry_from - iterate over list of given type from the current point
460 * @pos:	the type * to use as a loop cursor.
461 * @head:	the head for your list.
462 * @member:	the name of the list_struct within the struct.
463 *
464 * Iterate over list of given type, continuing from current position.
465 */
466#define list_for_each_entry_from(pos, head, member) 			\
467	for (; prefetch(pos->member.next), &pos->member != (head);	\
468	     pos = list_entry(pos->member.next, typeof(*pos), member))
469
470/**
471 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
472 * @pos:	the type * to use as a loop cursor.
473 * @n:		another type * to use as temporary storage
474 * @head:	the head for your list.
475 * @member:	the name of the list_struct within the struct.
476 */
477#define list_for_each_entry_safe(pos, n, head, member)			\
478	for (pos = list_entry((head)->next, typeof(*pos), member),	\
479		n = list_entry(pos->member.next, typeof(*pos), member);	\
480	     &pos->member != (head); 					\
481	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
482
483/**
484 * list_for_each_entry_safe_continue - continue list iteration safe against removal
485 * @pos:	the type * to use as a loop cursor.
486 * @n:		another type * to use as temporary storage
487 * @head:	the head for your list.
488 * @member:	the name of the list_struct within the struct.
489 *
490 * Iterate over list of given type, continuing after current point,
491 * safe against removal of list entry.
492 */
493#define list_for_each_entry_safe_continue(pos, n, head, member) 		\
494	for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
495		n = list_entry(pos->member.next, typeof(*pos), member);		\
496	     &pos->member != (head);						\
497	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
498
499/**
500 * list_for_each_entry_safe_from - iterate over list from current point safe against removal
501 * @pos:	the type * to use as a loop cursor.
502 * @n:		another type * to use as temporary storage
503 * @head:	the head for your list.
504 * @member:	the name of the list_struct within the struct.
505 *
506 * Iterate over list of given type from current point, safe against
507 * removal of list entry.
508 */
509#define list_for_each_entry_safe_from(pos, n, head, member) 			\
510	for (n = list_entry(pos->member.next, typeof(*pos), member);		\
511	     &pos->member != (head);						\
512	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
513
514/**
515 * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
516 * @pos:	the type * to use as a loop cursor.
517 * @n:		another type * to use as temporary storage
518 * @head:	the head for your list.
519 * @member:	the name of the list_struct within the struct.
520 *
521 * Iterate backwards over list of given type, safe against removal
522 * of list entry.
523 */
524#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
525	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
526		n = list_entry(pos->member.prev, typeof(*pos), member);	\
527	     &pos->member != (head); 					\
528	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))
529
530/**
531 * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
532 * @pos:	the loop cursor used in the list_for_each_entry_safe loop
533 * @n:		temporary storage used in list_for_each_entry_safe
534 * @member:	the name of the list_struct within the struct.
535 *
536 * list_safe_reset_next is not safe to use in general if the list may be
537 * modified concurrently (eg. the lock is dropped in the loop body). An
538 * exception to this is if the cursor element (pos) is pinned in the list,
539 * and list_safe_reset_next is called after re-taking the lock and before
540 * completing the current iteration of the loop body.
541 */
542#define list_safe_reset_next(pos, n, member)				\
543	n = list_entry(pos->member.next, typeof(*pos), member)
544
545#define HLIST_HEAD_INIT { .first = NULL }
546#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
547#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
548static inline void INIT_HLIST_NODE(struct hlist_node *h)
549{
550	h->next = NULL;
551	h->pprev = NULL;
552}
553
554static inline int hlist_unhashed(const struct hlist_node *h)
555{
556	return !h->pprev;
557}
558
559static inline int hlist_empty(const struct hlist_head *h)
560{
561	return !h->first;
562}
563
564static inline void __hlist_del(struct hlist_node *n)
565{
566	struct hlist_node *next = n->next;
567	struct hlist_node **pprev = n->pprev;
568	*pprev = next;
569	if (next)
570		next->pprev = pprev;
571}
572
573static inline void hlist_del(struct hlist_node *n)
574{
575	__hlist_del(n);
576	n->next = LIST_POISON1;
577	n->pprev = LIST_POISON2;
578}
579
580static inline void hlist_del_init(struct hlist_node *n)
581{
582	if (!hlist_unhashed(n)) {
583		__hlist_del(n);
584		INIT_HLIST_NODE(n);
585	}
586}
587
588static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
589{
590	struct hlist_node *first = h->first;
591	n->next = first;
592	if (first)
593		first->pprev = &n->next;
594	h->first = n;
595	n->pprev = &h->first;
596}
597
598/* next must be != NULL */
599static inline void hlist_add_before(struct hlist_node *n,
600					struct hlist_node *next)
601{
602	n->pprev = next->pprev;
603	n->next = next;
604	next->pprev = &n->next;
605	*(n->pprev) = n;
606}
607
608static inline void hlist_add_after(struct hlist_node *n,
609					struct hlist_node *next)
610{
611	next->next = n->next;
612	n->next = next;
613	next->pprev = &n->next;
614
615	if(next->next)
616		next->next->pprev  = &next->next;
617}
618
619/*
620 * Move a list from one list head to another. Fixup the pprev
621 * reference of the first entry if it exists.
622 */
623static inline void hlist_move_list(struct hlist_head *old,
624				   struct hlist_head *new)
625{
626	new->first = old->first;
627	if (new->first)
628		new->first->pprev = &new->first;
629	old->first = NULL;
630}
631
632#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
633
634#define hlist_for_each(pos, head) \
635	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
636	     pos = pos->next)
637
638#define hlist_for_each_safe(pos, n, head) \
639	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
640	     pos = n)
641
642/**
643 * hlist_for_each_entry	- iterate over list of given type
644 * @tpos:	the type * to use as a loop cursor.
645 * @pos:	the &struct hlist_node to use as a loop cursor.
646 * @head:	the head for your list.
647 * @member:	the name of the hlist_node within the struct.
648 */
649#define hlist_for_each_entry(tpos, pos, head, member)			 \
650	for (pos = (head)->first;					 \
651	     pos && ({ prefetch(pos->next); 1;}) &&			 \
652		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
653	     pos = pos->next)
654
655/**
656 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
657 * @tpos:	the type * to use as a loop cursor.
658 * @pos:	the &struct hlist_node to use as a loop cursor.
659 * @member:	the name of the hlist_node within the struct.
660 */
661#define hlist_for_each_entry_continue(tpos, pos, member)		 \
662	for (pos = (pos)->next;						 \
663	     pos && ({ prefetch(pos->next); 1;}) &&			 \
664		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
665	     pos = pos->next)
666
667/**
668 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
669 * @tpos:	the type * to use as a loop cursor.
670 * @pos:	the &struct hlist_node to use as a loop cursor.
671 * @member:	the name of the hlist_node within the struct.
672 */
673#define hlist_for_each_entry_from(tpos, pos, member)			 \
674	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
675		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
676	     pos = pos->next)
677
678/**
679 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
680 * @tpos:	the type * to use as a loop cursor.
681 * @pos:	the &struct hlist_node to use as a loop cursor.
682 * @n:		another &struct hlist_node to use as temporary storage
683 * @head:	the head for your list.
684 * @member:	the name of the hlist_node within the struct.
685 */
686#define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
687	for (pos = (head)->first;					 \
688	     pos && ({ n = pos->next; 1; }) && 				 \
689		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
690	     pos = n)
691
692#endif
693