xref: /kvmtool/include/linux/list.h (revision fbb8a81d1a37ac9dc43e61ce975a0b27e58b61db)
17e841c88SAndre Przywara #ifndef _LINUX_LIST_H
27e841c88SAndre Przywara #define _LINUX_LIST_H
37e841c88SAndre Przywara 
47e841c88SAndre Przywara #include <linux/types.h>
57e841c88SAndre Przywara #include <linux/stddef.h>
67e841c88SAndre Przywara #include <linux/const.h>
77e841c88SAndre Przywara #include <linux/kernel.h>
87e841c88SAndre Przywara 
97e841c88SAndre Przywara /*
107e841c88SAndre Przywara  * Simple doubly linked list implementation.
117e841c88SAndre Przywara  *
127e841c88SAndre Przywara  * Some of the internal functions ("__xxx") are useful when
137e841c88SAndre Przywara  * manipulating whole lists rather than single entries, as
147e841c88SAndre Przywara  * sometimes we already know the next/prev entries and we can
157e841c88SAndre Przywara  * generate better code by using them directly rather than
167e841c88SAndre Przywara  * using the generic single-entry routines.
177e841c88SAndre Przywara  */
187e841c88SAndre Przywara 
197e841c88SAndre Przywara #define LIST_HEAD_INIT(name) { &(name), &(name) }
207e841c88SAndre Przywara 
217e841c88SAndre Przywara #define LIST_HEAD(name) \
227e841c88SAndre Przywara 	struct list_head name = LIST_HEAD_INIT(name)
237e841c88SAndre Przywara 
INIT_LIST_HEAD(struct list_head * list)247e841c88SAndre Przywara static inline void INIT_LIST_HEAD(struct list_head *list)
257e841c88SAndre Przywara {
267e841c88SAndre Przywara 	list->next = list;
277e841c88SAndre Przywara 	list->prev = list;
287e841c88SAndre Przywara }
297e841c88SAndre Przywara 
307e841c88SAndre Przywara /*
317e841c88SAndre Przywara  * Insert a new entry between two known consecutive entries.
327e841c88SAndre Przywara  *
337e841c88SAndre Przywara  * This is only for internal list manipulation where we know
347e841c88SAndre Przywara  * the prev/next entries already!
357e841c88SAndre Przywara  */
367e841c88SAndre Przywara #ifndef CONFIG_DEBUG_LIST
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)377e841c88SAndre Przywara static inline void __list_add(struct list_head *new,
387e841c88SAndre Przywara 			      struct list_head *prev,
397e841c88SAndre Przywara 			      struct list_head *next)
407e841c88SAndre Przywara {
417e841c88SAndre Przywara 	next->prev = new;
427e841c88SAndre Przywara 	new->next = next;
437e841c88SAndre Przywara 	new->prev = prev;
447e841c88SAndre Przywara 	prev->next = new;
457e841c88SAndre Przywara }
467e841c88SAndre Przywara #else
477e841c88SAndre Przywara extern void __list_add(struct list_head *new,
487e841c88SAndre Przywara 			      struct list_head *prev,
497e841c88SAndre Przywara 			      struct list_head *next);
507e841c88SAndre Przywara #endif
517e841c88SAndre Przywara 
527e841c88SAndre Przywara /**
537e841c88SAndre Przywara  * list_add - add a new entry
547e841c88SAndre Przywara  * @new: new entry to be added
557e841c88SAndre Przywara  * @head: list head to add it after
567e841c88SAndre Przywara  *
577e841c88SAndre Przywara  * Insert a new entry after the specified head.
587e841c88SAndre Przywara  * This is good for implementing stacks.
597e841c88SAndre Przywara  */
list_add(struct list_head * new,struct list_head * head)607e841c88SAndre Przywara static inline void list_add(struct list_head *new, struct list_head *head)
617e841c88SAndre Przywara {
627e841c88SAndre Przywara 	__list_add(new, head, head->next);
637e841c88SAndre Przywara }
647e841c88SAndre Przywara 
657e841c88SAndre Przywara 
667e841c88SAndre Przywara /**
677e841c88SAndre Przywara  * list_add_tail - add a new entry
687e841c88SAndre Przywara  * @new: new entry to be added
697e841c88SAndre Przywara  * @head: list head to add it before
707e841c88SAndre Przywara  *
717e841c88SAndre Przywara  * Insert a new entry before the specified head.
727e841c88SAndre Przywara  * This is useful for implementing queues.
737e841c88SAndre Przywara  */
list_add_tail(struct list_head * new,struct list_head * head)747e841c88SAndre Przywara static inline void list_add_tail(struct list_head *new, struct list_head *head)
757e841c88SAndre Przywara {
767e841c88SAndre Przywara 	__list_add(new, head->prev, head);
777e841c88SAndre Przywara }
787e841c88SAndre Przywara 
797e841c88SAndre Przywara /*
807e841c88SAndre Przywara  * Delete a list entry by making the prev/next entries
817e841c88SAndre Przywara  * point to each other.
827e841c88SAndre Przywara  *
837e841c88SAndre Przywara  * This is only for internal list manipulation where we know
847e841c88SAndre Przywara  * the prev/next entries already!
857e841c88SAndre Przywara  */
__list_del(struct list_head * prev,struct list_head * next)867e841c88SAndre Przywara static inline void __list_del(struct list_head * prev, struct list_head * next)
877e841c88SAndre Przywara {
887e841c88SAndre Przywara 	next->prev = prev;
897e841c88SAndre Przywara 	prev->next = next;
907e841c88SAndre Przywara }
917e841c88SAndre Przywara 
927e841c88SAndre Przywara /**
937e841c88SAndre Przywara  * list_del - deletes entry from list.
947e841c88SAndre Przywara  * @entry: the element to delete from the list.
957e841c88SAndre Przywara  * Note: list_empty() on entry does not return true after this, the entry is
967e841c88SAndre Przywara  * in an undefined state.
977e841c88SAndre Przywara  */
987e841c88SAndre Przywara #ifndef CONFIG_DEBUG_LIST
__list_del_entry(struct list_head * entry)997e841c88SAndre Przywara static inline void __list_del_entry(struct list_head *entry)
1007e841c88SAndre Przywara {
1017e841c88SAndre Przywara 	__list_del(entry->prev, entry->next);
1027e841c88SAndre Przywara }
1037e841c88SAndre Przywara 
list_del(struct list_head * entry)1047e841c88SAndre Przywara static inline void list_del(struct list_head *entry)
1057e841c88SAndre Przywara {
1067e841c88SAndre Przywara 	__list_del(entry->prev, entry->next);
107*fbb8a81dSAndre Przywara 	entry->next = NULL;
108*fbb8a81dSAndre Przywara 	entry->prev = NULL;
1097e841c88SAndre Przywara }
1107e841c88SAndre Przywara #else
1117e841c88SAndre Przywara extern void __list_del_entry(struct list_head *entry);
1127e841c88SAndre Przywara extern void list_del(struct list_head *entry);
1137e841c88SAndre Przywara #endif
1147e841c88SAndre Przywara 
1157e841c88SAndre Przywara /**
1167e841c88SAndre Przywara  * list_replace - replace old entry by new one
1177e841c88SAndre Przywara  * @old : the element to be replaced
1187e841c88SAndre Przywara  * @new : the new element to insert
1197e841c88SAndre Przywara  *
1207e841c88SAndre Przywara  * If @old was empty, it will be overwritten.
1217e841c88SAndre Przywara  */
list_replace(struct list_head * old,struct list_head * new)1227e841c88SAndre Przywara static inline void list_replace(struct list_head *old,
1237e841c88SAndre Przywara 				struct list_head *new)
1247e841c88SAndre Przywara {
1257e841c88SAndre Przywara 	new->next = old->next;
1267e841c88SAndre Przywara 	new->next->prev = new;
1277e841c88SAndre Przywara 	new->prev = old->prev;
1287e841c88SAndre Przywara 	new->prev->next = new;
1297e841c88SAndre Przywara }
1307e841c88SAndre Przywara 
list_replace_init(struct list_head * old,struct list_head * new)1317e841c88SAndre Przywara static inline void list_replace_init(struct list_head *old,
1327e841c88SAndre Przywara 					struct list_head *new)
1337e841c88SAndre Przywara {
1347e841c88SAndre Przywara 	list_replace(old, new);
1357e841c88SAndre Przywara 	INIT_LIST_HEAD(old);
1367e841c88SAndre Przywara }
1377e841c88SAndre Przywara 
1387e841c88SAndre Przywara /**
1397e841c88SAndre Przywara  * list_del_init - deletes entry from list and reinitialize it.
1407e841c88SAndre Przywara  * @entry: the element to delete from the list.
1417e841c88SAndre Przywara  */
list_del_init(struct list_head * entry)1427e841c88SAndre Przywara static inline void list_del_init(struct list_head *entry)
1437e841c88SAndre Przywara {
1447e841c88SAndre Przywara 	__list_del_entry(entry);
1457e841c88SAndre Przywara 	INIT_LIST_HEAD(entry);
1467e841c88SAndre Przywara }
1477e841c88SAndre Przywara 
1487e841c88SAndre Przywara /**
1497e841c88SAndre Przywara  * list_move - delete from one list and add as another's head
1507e841c88SAndre Przywara  * @list: the entry to move
1517e841c88SAndre Przywara  * @head: the head that will precede our entry
1527e841c88SAndre Przywara  */
list_move(struct list_head * list,struct list_head * head)1537e841c88SAndre Przywara static inline void list_move(struct list_head *list, struct list_head *head)
1547e841c88SAndre Przywara {
1557e841c88SAndre Przywara 	__list_del_entry(list);
1567e841c88SAndre Przywara 	list_add(list, head);
1577e841c88SAndre Przywara }
1587e841c88SAndre Przywara 
1597e841c88SAndre Przywara /**
1607e841c88SAndre Przywara  * list_move_tail - delete from one list and add as another's tail
1617e841c88SAndre Przywara  * @list: the entry to move
1627e841c88SAndre Przywara  * @head: the head that will follow our entry
1637e841c88SAndre Przywara  */
list_move_tail(struct list_head * list,struct list_head * head)1647e841c88SAndre Przywara static inline void list_move_tail(struct list_head *list,
1657e841c88SAndre Przywara 				  struct list_head *head)
1667e841c88SAndre Przywara {
1677e841c88SAndre Przywara 	__list_del_entry(list);
1687e841c88SAndre Przywara 	list_add_tail(list, head);
1697e841c88SAndre Przywara }
1707e841c88SAndre Przywara 
1717e841c88SAndre Przywara /**
1727e841c88SAndre Przywara  * list_is_last - tests whether @list is the last entry in list @head
1737e841c88SAndre Przywara  * @list: the entry to test
1747e841c88SAndre Przywara  * @head: the head of the list
1757e841c88SAndre Przywara  */
list_is_last(const struct list_head * list,const struct list_head * head)1767e841c88SAndre Przywara static inline int list_is_last(const struct list_head *list,
1777e841c88SAndre Przywara 				const struct list_head *head)
1787e841c88SAndre Przywara {
1797e841c88SAndre Przywara 	return list->next == head;
1807e841c88SAndre Przywara }
1817e841c88SAndre Przywara 
1827e841c88SAndre Przywara /**
1837e841c88SAndre Przywara  * list_empty - tests whether a list is empty
1847e841c88SAndre Przywara  * @head: the list to test.
1857e841c88SAndre Przywara  */
list_empty(const struct list_head * head)1867e841c88SAndre Przywara static inline int list_empty(const struct list_head *head)
1877e841c88SAndre Przywara {
1887e841c88SAndre Przywara 	return head->next == head;
1897e841c88SAndre Przywara }
1907e841c88SAndre Przywara 
1917e841c88SAndre Przywara /**
1927e841c88SAndre Przywara  * list_empty_careful - tests whether a list is empty and not being modified
1937e841c88SAndre Przywara  * @head: the list to test
1947e841c88SAndre Przywara  *
1957e841c88SAndre Przywara  * Description:
1967e841c88SAndre Przywara  * tests whether a list is empty _and_ checks that no other CPU might be
1977e841c88SAndre Przywara  * in the process of modifying either member (next or prev)
1987e841c88SAndre Przywara  *
1997e841c88SAndre Przywara  * NOTE: using list_empty_careful() without synchronization
2007e841c88SAndre Przywara  * can only be safe if the only activity that can happen
2017e841c88SAndre Przywara  * to the list entry is list_del_init(). Eg. it cannot be used
2027e841c88SAndre Przywara  * if another CPU could re-list_add() it.
2037e841c88SAndre Przywara  */
list_empty_careful(const struct list_head * head)2047e841c88SAndre Przywara static inline int list_empty_careful(const struct list_head *head)
2057e841c88SAndre Przywara {
2067e841c88SAndre Przywara 	struct list_head *next = head->next;
2077e841c88SAndre Przywara 	return (next == head) && (next == head->prev);
2087e841c88SAndre Przywara }
2097e841c88SAndre Przywara 
2107e841c88SAndre Przywara /**
2117e841c88SAndre Przywara  * list_rotate_left - rotate the list to the left
2127e841c88SAndre Przywara  * @head: the head of the list
2137e841c88SAndre Przywara  */
list_rotate_left(struct list_head * head)2147e841c88SAndre Przywara static inline void list_rotate_left(struct list_head *head)
2157e841c88SAndre Przywara {
2167e841c88SAndre Przywara 	struct list_head *first;
2177e841c88SAndre Przywara 
2187e841c88SAndre Przywara 	if (!list_empty(head)) {
2197e841c88SAndre Przywara 		first = head->next;
2207e841c88SAndre Przywara 		list_move_tail(first, head);
2217e841c88SAndre Przywara 	}
2227e841c88SAndre Przywara }
2237e841c88SAndre Przywara 
2247e841c88SAndre Przywara /**
2257e841c88SAndre Przywara  * list_is_singular - tests whether a list has just one entry.
2267e841c88SAndre Przywara  * @head: the list to test.
2277e841c88SAndre Przywara  */
list_is_singular(const struct list_head * head)2287e841c88SAndre Przywara static inline int list_is_singular(const struct list_head *head)
2297e841c88SAndre Przywara {
2307e841c88SAndre Przywara 	return !list_empty(head) && (head->next == head->prev);
2317e841c88SAndre Przywara }
2327e841c88SAndre Przywara 
__list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)2337e841c88SAndre Przywara static inline void __list_cut_position(struct list_head *list,
2347e841c88SAndre Przywara 		struct list_head *head, struct list_head *entry)
2357e841c88SAndre Przywara {
2367e841c88SAndre Przywara 	struct list_head *new_first = entry->next;
2377e841c88SAndre Przywara 	list->next = head->next;
2387e841c88SAndre Przywara 	list->next->prev = list;
2397e841c88SAndre Przywara 	list->prev = entry;
2407e841c88SAndre Przywara 	entry->next = list;
2417e841c88SAndre Przywara 	head->next = new_first;
2427e841c88SAndre Przywara 	new_first->prev = head;
2437e841c88SAndre Przywara }
2447e841c88SAndre Przywara 
2457e841c88SAndre Przywara /**
2467e841c88SAndre Przywara  * list_cut_position - cut a list into two
2477e841c88SAndre Przywara  * @list: a new list to add all removed entries
2487e841c88SAndre Przywara  * @head: a list with entries
2497e841c88SAndre Przywara  * @entry: an entry within head, could be the head itself
2507e841c88SAndre Przywara  *	and if so we won't cut the list
2517e841c88SAndre Przywara  *
2527e841c88SAndre Przywara  * This helper moves the initial part of @head, up to and
2537e841c88SAndre Przywara  * including @entry, from @head to @list. You should
2547e841c88SAndre Przywara  * pass on @entry an element you know is on @head. @list
2557e841c88SAndre Przywara  * should be an empty list or a list you do not care about
2567e841c88SAndre Przywara  * losing its data.
2577e841c88SAndre Przywara  *
2587e841c88SAndre Przywara  */
list_cut_position(struct list_head * list,struct list_head * head,struct list_head * entry)2597e841c88SAndre Przywara static inline void list_cut_position(struct list_head *list,
2607e841c88SAndre Przywara 		struct list_head *head, struct list_head *entry)
2617e841c88SAndre Przywara {
2627e841c88SAndre Przywara 	if (list_empty(head))
2637e841c88SAndre Przywara 		return;
2647e841c88SAndre Przywara 	if (list_is_singular(head) &&
2657e841c88SAndre Przywara 		(head->next != entry && head != entry))
2667e841c88SAndre Przywara 		return;
2677e841c88SAndre Przywara 	if (entry == head)
2687e841c88SAndre Przywara 		INIT_LIST_HEAD(list);
2697e841c88SAndre Przywara 	else
2707e841c88SAndre Przywara 		__list_cut_position(list, head, entry);
2717e841c88SAndre Przywara }
2727e841c88SAndre Przywara 
__list_splice(const struct list_head * list,struct list_head * prev,struct list_head * next)2737e841c88SAndre Przywara static inline void __list_splice(const struct list_head *list,
2747e841c88SAndre Przywara 				 struct list_head *prev,
2757e841c88SAndre Przywara 				 struct list_head *next)
2767e841c88SAndre Przywara {
2777e841c88SAndre Przywara 	struct list_head *first = list->next;
2787e841c88SAndre Przywara 	struct list_head *last = list->prev;
2797e841c88SAndre Przywara 
2807e841c88SAndre Przywara 	first->prev = prev;
2817e841c88SAndre Przywara 	prev->next = first;
2827e841c88SAndre Przywara 
2837e841c88SAndre Przywara 	last->next = next;
2847e841c88SAndre Przywara 	next->prev = last;
2857e841c88SAndre Przywara }
2867e841c88SAndre Przywara 
2877e841c88SAndre Przywara /**
2887e841c88SAndre Przywara  * list_splice - join two lists, this is designed for stacks
2897e841c88SAndre Przywara  * @list: the new list to add.
2907e841c88SAndre Przywara  * @head: the place to add it in the first list.
2917e841c88SAndre Przywara  */
list_splice(const struct list_head * list,struct list_head * head)2927e841c88SAndre Przywara static inline void list_splice(const struct list_head *list,
2937e841c88SAndre Przywara 				struct list_head *head)
2947e841c88SAndre Przywara {
2957e841c88SAndre Przywara 	if (!list_empty(list))
2967e841c88SAndre Przywara 		__list_splice(list, head, head->next);
2977e841c88SAndre Przywara }
2987e841c88SAndre Przywara 
2997e841c88SAndre Przywara /**
3007e841c88SAndre Przywara  * list_splice_tail - join two lists, each list being a queue
3017e841c88SAndre Przywara  * @list: the new list to add.
3027e841c88SAndre Przywara  * @head: the place to add it in the first list.
3037e841c88SAndre Przywara  */
list_splice_tail(struct list_head * list,struct list_head * head)3047e841c88SAndre Przywara static inline void list_splice_tail(struct list_head *list,
3057e841c88SAndre Przywara 				struct list_head *head)
3067e841c88SAndre Przywara {
3077e841c88SAndre Przywara 	if (!list_empty(list))
3087e841c88SAndre Przywara 		__list_splice(list, head->prev, head);
3097e841c88SAndre Przywara }
3107e841c88SAndre Przywara 
3117e841c88SAndre Przywara /**
3127e841c88SAndre Przywara  * list_splice_init - join two lists and reinitialise the emptied list.
3137e841c88SAndre Przywara  * @list: the new list to add.
3147e841c88SAndre Przywara  * @head: the place to add it in the first list.
3157e841c88SAndre Przywara  *
3167e841c88SAndre Przywara  * The list at @list is reinitialised
3177e841c88SAndre Przywara  */
list_splice_init(struct list_head * list,struct list_head * head)3187e841c88SAndre Przywara static inline void list_splice_init(struct list_head *list,
3197e841c88SAndre Przywara 				    struct list_head *head)
3207e841c88SAndre Przywara {
3217e841c88SAndre Przywara 	if (!list_empty(list)) {
3227e841c88SAndre Przywara 		__list_splice(list, head, head->next);
3237e841c88SAndre Przywara 		INIT_LIST_HEAD(list);
3247e841c88SAndre Przywara 	}
3257e841c88SAndre Przywara }
3267e841c88SAndre Przywara 
3277e841c88SAndre Przywara /**
3287e841c88SAndre Przywara  * list_splice_tail_init - join two lists and reinitialise the emptied list
3297e841c88SAndre Przywara  * @list: the new list to add.
3307e841c88SAndre Przywara  * @head: the place to add it in the first list.
3317e841c88SAndre Przywara  *
3327e841c88SAndre Przywara  * Each of the lists is a queue.
3337e841c88SAndre Przywara  * The list at @list is reinitialised
3347e841c88SAndre Przywara  */
list_splice_tail_init(struct list_head * list,struct list_head * head)3357e841c88SAndre Przywara static inline void list_splice_tail_init(struct list_head *list,
3367e841c88SAndre Przywara 					 struct list_head *head)
3377e841c88SAndre Przywara {
3387e841c88SAndre Przywara 	if (!list_empty(list)) {
3397e841c88SAndre Przywara 		__list_splice(list, head->prev, head);
3407e841c88SAndre Przywara 		INIT_LIST_HEAD(list);
3417e841c88SAndre Przywara 	}
3427e841c88SAndre Przywara }
3437e841c88SAndre Przywara 
3447e841c88SAndre Przywara /**
3457e841c88SAndre Przywara  * list_entry - get the struct for this entry
3467e841c88SAndre Przywara  * @ptr:	the &struct list_head pointer.
3477e841c88SAndre Przywara  * @type:	the type of the struct this is embedded in.
3487e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
3497e841c88SAndre Przywara  */
3507e841c88SAndre Przywara #define list_entry(ptr, type, member) \
3517e841c88SAndre Przywara 	container_of(ptr, type, member)
3527e841c88SAndre Przywara 
3537e841c88SAndre Przywara /**
3547e841c88SAndre Przywara  * list_first_entry - get the first element from a list
3557e841c88SAndre Przywara  * @ptr:	the list head to take the element from.
3567e841c88SAndre Przywara  * @type:	the type of the struct this is embedded in.
3577e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
3587e841c88SAndre Przywara  *
3597e841c88SAndre Przywara  * Note, that list is expected to be not empty.
3607e841c88SAndre Przywara  */
3617e841c88SAndre Przywara #define list_first_entry(ptr, type, member) \
3627e841c88SAndre Przywara 	list_entry((ptr)->next, type, member)
3637e841c88SAndre Przywara 
3647e841c88SAndre Przywara /**
3657e841c88SAndre Przywara  * list_last_entry - get the last element from a list
3667e841c88SAndre Przywara  * @ptr:	the list head to take the element from.
3677e841c88SAndre Przywara  * @type:	the type of the struct this is embedded in.
3687e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
3697e841c88SAndre Przywara  *
3707e841c88SAndre Przywara  * Note, that list is expected to be not empty.
3717e841c88SAndre Przywara  */
3727e841c88SAndre Przywara #define list_last_entry(ptr, type, member) \
3737e841c88SAndre Przywara 	list_entry((ptr)->prev, type, member)
3747e841c88SAndre Przywara 
3757e841c88SAndre Przywara /**
3767e841c88SAndre Przywara  * list_first_entry_or_null - get the first element from a list
3777e841c88SAndre Przywara  * @ptr:	the list head to take the element from.
3787e841c88SAndre Przywara  * @type:	the type of the struct this is embedded in.
3797e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
3807e841c88SAndre Przywara  *
3817e841c88SAndre Przywara  * Note that if the list is empty, it returns NULL.
3827e841c88SAndre Przywara  */
3837e841c88SAndre Przywara #define list_first_entry_or_null(ptr, type, member) \
3847e841c88SAndre Przywara 	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
3857e841c88SAndre Przywara 
3867e841c88SAndre Przywara /**
3877e841c88SAndre Przywara  * list_next_entry - get the next element in list
3887e841c88SAndre Przywara  * @pos:	the type * to cursor
3897e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
3907e841c88SAndre Przywara  */
3917e841c88SAndre Przywara #define list_next_entry(pos, member) \
3927e841c88SAndre Przywara 	list_entry((pos)->member.next, typeof(*(pos)), member)
3937e841c88SAndre Przywara 
3947e841c88SAndre Przywara /**
3957e841c88SAndre Przywara  * list_prev_entry - get the prev element in list
3967e841c88SAndre Przywara  * @pos:	the type * to cursor
3977e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
3987e841c88SAndre Przywara  */
3997e841c88SAndre Przywara #define list_prev_entry(pos, member) \
4007e841c88SAndre Przywara 	list_entry((pos)->member.prev, typeof(*(pos)), member)
4017e841c88SAndre Przywara 
4027e841c88SAndre Przywara /**
4037e841c88SAndre Przywara  * list_for_each	-	iterate over a list
4047e841c88SAndre Przywara  * @pos:	the &struct list_head to use as a loop cursor.
4057e841c88SAndre Przywara  * @head:	the head for your list.
4067e841c88SAndre Przywara  */
4077e841c88SAndre Przywara #define list_for_each(pos, head) \
4087e841c88SAndre Przywara 	for (pos = (head)->next; pos != (head); pos = pos->next)
4097e841c88SAndre Przywara 
4107e841c88SAndre Przywara /**
4117e841c88SAndre Przywara  * list_for_each_prev	-	iterate over a list backwards
4127e841c88SAndre Przywara  * @pos:	the &struct list_head to use as a loop cursor.
4137e841c88SAndre Przywara  * @head:	the head for your list.
4147e841c88SAndre Przywara  */
4157e841c88SAndre Przywara #define list_for_each_prev(pos, head) \
4167e841c88SAndre Przywara 	for (pos = (head)->prev; pos != (head); pos = pos->prev)
4177e841c88SAndre Przywara 
4187e841c88SAndre Przywara /**
4197e841c88SAndre Przywara  * list_for_each_safe - iterate over a list safe against removal of list entry
4207e841c88SAndre Przywara  * @pos:	the &struct list_head to use as a loop cursor.
4217e841c88SAndre Przywara  * @n:		another &struct list_head to use as temporary storage
4227e841c88SAndre Przywara  * @head:	the head for your list.
4237e841c88SAndre Przywara  */
4247e841c88SAndre Przywara #define list_for_each_safe(pos, n, head) \
4257e841c88SAndre Przywara 	for (pos = (head)->next, n = pos->next; pos != (head); \
4267e841c88SAndre Przywara 		pos = n, n = pos->next)
4277e841c88SAndre Przywara 
4287e841c88SAndre Przywara /**
4297e841c88SAndre Przywara  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
4307e841c88SAndre Przywara  * @pos:	the &struct list_head to use as a loop cursor.
4317e841c88SAndre Przywara  * @n:		another &struct list_head to use as temporary storage
4327e841c88SAndre Przywara  * @head:	the head for your list.
4337e841c88SAndre Przywara  */
4347e841c88SAndre Przywara #define list_for_each_prev_safe(pos, n, head) \
4357e841c88SAndre Przywara 	for (pos = (head)->prev, n = pos->prev; \
4367e841c88SAndre Przywara 	     pos != (head); \
4377e841c88SAndre Przywara 	     pos = n, n = pos->prev)
4387e841c88SAndre Przywara 
4397e841c88SAndre Przywara /**
4407e841c88SAndre Przywara  * list_for_each_entry	-	iterate over list of given type
4417e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
4427e841c88SAndre Przywara  * @head:	the head for your list.
4437e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
4447e841c88SAndre Przywara  */
4457e841c88SAndre Przywara #define list_for_each_entry(pos, head, member)				\
4467e841c88SAndre Przywara 	for (pos = list_first_entry(head, typeof(*pos), member);	\
4477e841c88SAndre Przywara 	     &pos->member != (head);					\
4487e841c88SAndre Przywara 	     pos = list_next_entry(pos, member))
4497e841c88SAndre Przywara 
4507e841c88SAndre Przywara /**
4517e841c88SAndre Przywara  * list_for_each_entry_reverse - iterate backwards over list of given type.
4527e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
4537e841c88SAndre Przywara  * @head:	the head for your list.
4547e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
4557e841c88SAndre Przywara  */
4567e841c88SAndre Przywara #define list_for_each_entry_reverse(pos, head, member)			\
4577e841c88SAndre Przywara 	for (pos = list_last_entry(head, typeof(*pos), member);		\
4587e841c88SAndre Przywara 	     &pos->member != (head); 					\
4597e841c88SAndre Przywara 	     pos = list_prev_entry(pos, member))
4607e841c88SAndre Przywara 
4617e841c88SAndre Przywara /**
4627e841c88SAndre Przywara  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
4637e841c88SAndre Przywara  * @pos:	the type * to use as a start point
4647e841c88SAndre Przywara  * @head:	the head of the list
4657e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
4667e841c88SAndre Przywara  *
4677e841c88SAndre Przywara  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
4687e841c88SAndre Przywara  */
4697e841c88SAndre Przywara #define list_prepare_entry(pos, head, member) \
4707e841c88SAndre Przywara 	((pos) ? : list_entry(head, typeof(*pos), member))
4717e841c88SAndre Przywara 
4727e841c88SAndre Przywara /**
4737e841c88SAndre Przywara  * list_for_each_entry_continue - continue iteration over list of given type
4747e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
4757e841c88SAndre Przywara  * @head:	the head for your list.
4767e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
4777e841c88SAndre Przywara  *
4787e841c88SAndre Przywara  * Continue to iterate over list of given type, continuing after
4797e841c88SAndre Przywara  * the current position.
4807e841c88SAndre Przywara  */
4817e841c88SAndre Przywara #define list_for_each_entry_continue(pos, head, member) 		\
4827e841c88SAndre Przywara 	for (pos = list_next_entry(pos, member);			\
4837e841c88SAndre Przywara 	     &pos->member != (head);					\
4847e841c88SAndre Przywara 	     pos = list_next_entry(pos, member))
4857e841c88SAndre Przywara 
4867e841c88SAndre Przywara /**
4877e841c88SAndre Przywara  * list_for_each_entry_continue_reverse - iterate backwards from the given point
4887e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
4897e841c88SAndre Przywara  * @head:	the head for your list.
4907e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
4917e841c88SAndre Przywara  *
4927e841c88SAndre Przywara  * Start to iterate over list of given type backwards, continuing after
4937e841c88SAndre Przywara  * the current position.
4947e841c88SAndre Przywara  */
4957e841c88SAndre Przywara #define list_for_each_entry_continue_reverse(pos, head, member)		\
4967e841c88SAndre Przywara 	for (pos = list_prev_entry(pos, member);			\
4977e841c88SAndre Przywara 	     &pos->member != (head);					\
4987e841c88SAndre Przywara 	     pos = list_prev_entry(pos, member))
4997e841c88SAndre Przywara 
5007e841c88SAndre Przywara /**
5017e841c88SAndre Przywara  * list_for_each_entry_from - iterate over list of given type from the current point
5027e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
5037e841c88SAndre Przywara  * @head:	the head for your list.
5047e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
5057e841c88SAndre Przywara  *
5067e841c88SAndre Przywara  * Iterate over list of given type, continuing from current position.
5077e841c88SAndre Przywara  */
5087e841c88SAndre Przywara #define list_for_each_entry_from(pos, head, member) 			\
5097e841c88SAndre Przywara 	for (; &pos->member != (head);					\
5107e841c88SAndre Przywara 	     pos = list_next_entry(pos, member))
5117e841c88SAndre Przywara 
5127e841c88SAndre Przywara /**
5137e841c88SAndre Przywara  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
5147e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
5157e841c88SAndre Przywara  * @n:		another type * to use as temporary storage
5167e841c88SAndre Przywara  * @head:	the head for your list.
5177e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
5187e841c88SAndre Przywara  */
5197e841c88SAndre Przywara #define list_for_each_entry_safe(pos, n, head, member)			\
5207e841c88SAndre Przywara 	for (pos = list_first_entry(head, typeof(*pos), member),	\
5217e841c88SAndre Przywara 		n = list_next_entry(pos, member);			\
5227e841c88SAndre Przywara 	     &pos->member != (head); 					\
5237e841c88SAndre Przywara 	     pos = n, n = list_next_entry(n, member))
5247e841c88SAndre Przywara 
5257e841c88SAndre Przywara /**
5267e841c88SAndre Przywara  * list_for_each_entry_safe_continue - continue list iteration safe against removal
5277e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
5287e841c88SAndre Przywara  * @n:		another type * to use as temporary storage
5297e841c88SAndre Przywara  * @head:	the head for your list.
5307e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
5317e841c88SAndre Przywara  *
5327e841c88SAndre Przywara  * Iterate over list of given type, continuing after current point,
5337e841c88SAndre Przywara  * safe against removal of list entry.
5347e841c88SAndre Przywara  */
5357e841c88SAndre Przywara #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
5367e841c88SAndre Przywara 	for (pos = list_next_entry(pos, member), 				\
5377e841c88SAndre Przywara 		n = list_next_entry(pos, member);				\
5387e841c88SAndre Przywara 	     &pos->member != (head);						\
5397e841c88SAndre Przywara 	     pos = n, n = list_next_entry(n, member))
5407e841c88SAndre Przywara 
5417e841c88SAndre Przywara /**
5427e841c88SAndre Przywara  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
5437e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
5447e841c88SAndre Przywara  * @n:		another type * to use as temporary storage
5457e841c88SAndre Przywara  * @head:	the head for your list.
5467e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
5477e841c88SAndre Przywara  *
5487e841c88SAndre Przywara  * Iterate over list of given type from current point, safe against
5497e841c88SAndre Przywara  * removal of list entry.
5507e841c88SAndre Przywara  */
5517e841c88SAndre Przywara #define list_for_each_entry_safe_from(pos, n, head, member) 			\
5527e841c88SAndre Przywara 	for (n = list_next_entry(pos, member);					\
5537e841c88SAndre Przywara 	     &pos->member != (head);						\
5547e841c88SAndre Przywara 	     pos = n, n = list_next_entry(n, member))
5557e841c88SAndre Przywara 
5567e841c88SAndre Przywara /**
5577e841c88SAndre Przywara  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
5587e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
5597e841c88SAndre Przywara  * @n:		another type * to use as temporary storage
5607e841c88SAndre Przywara  * @head:	the head for your list.
5617e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
5627e841c88SAndre Przywara  *
5637e841c88SAndre Przywara  * Iterate backwards over list of given type, safe against removal
5647e841c88SAndre Przywara  * of list entry.
5657e841c88SAndre Przywara  */
5667e841c88SAndre Przywara #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
5677e841c88SAndre Przywara 	for (pos = list_last_entry(head, typeof(*pos), member),		\
5687e841c88SAndre Przywara 		n = list_prev_entry(pos, member);			\
5697e841c88SAndre Przywara 	     &pos->member != (head); 					\
5707e841c88SAndre Przywara 	     pos = n, n = list_prev_entry(n, member))
5717e841c88SAndre Przywara 
5727e841c88SAndre Przywara /**
5737e841c88SAndre Przywara  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
5747e841c88SAndre Przywara  * @pos:	the loop cursor used in the list_for_each_entry_safe loop
5757e841c88SAndre Przywara  * @n:		temporary storage used in list_for_each_entry_safe
5767e841c88SAndre Przywara  * @member:	the name of the list_head within the struct.
5777e841c88SAndre Przywara  *
5787e841c88SAndre Przywara  * list_safe_reset_next is not safe to use in general if the list may be
5797e841c88SAndre Przywara  * modified concurrently (eg. the lock is dropped in the loop body). An
5807e841c88SAndre Przywara  * exception to this is if the cursor element (pos) is pinned in the list,
5817e841c88SAndre Przywara  * and list_safe_reset_next is called after re-taking the lock and before
5827e841c88SAndre Przywara  * completing the current iteration of the loop body.
5837e841c88SAndre Przywara  */
5847e841c88SAndre Przywara #define list_safe_reset_next(pos, n, member)				\
5857e841c88SAndre Przywara 	n = list_next_entry(pos, member)
5867e841c88SAndre Przywara 
5877e841c88SAndre Przywara /*
5887e841c88SAndre Przywara  * Double linked lists with a single pointer list head.
5897e841c88SAndre Przywara  * Mostly useful for hash tables where the two pointer list head is
5907e841c88SAndre Przywara  * too wasteful.
5917e841c88SAndre Przywara  * You lose the ability to access the tail in O(1).
5927e841c88SAndre Przywara  */
5937e841c88SAndre Przywara 
5947e841c88SAndre Przywara #define HLIST_HEAD_INIT { .first = NULL }
5957e841c88SAndre Przywara #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
5967e841c88SAndre Przywara #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
INIT_HLIST_NODE(struct hlist_node * h)5977e841c88SAndre Przywara static inline void INIT_HLIST_NODE(struct hlist_node *h)
5987e841c88SAndre Przywara {
5997e841c88SAndre Przywara 	h->next = NULL;
6007e841c88SAndre Przywara 	h->pprev = NULL;
6017e841c88SAndre Przywara }
6027e841c88SAndre Przywara 
hlist_unhashed(const struct hlist_node * h)6037e841c88SAndre Przywara static inline int hlist_unhashed(const struct hlist_node *h)
6047e841c88SAndre Przywara {
6057e841c88SAndre Przywara 	return !h->pprev;
6067e841c88SAndre Przywara }
6077e841c88SAndre Przywara 
hlist_empty(const struct hlist_head * h)6087e841c88SAndre Przywara static inline int hlist_empty(const struct hlist_head *h)
6097e841c88SAndre Przywara {
6107e841c88SAndre Przywara 	return !h->first;
6117e841c88SAndre Przywara }
6127e841c88SAndre Przywara 
__hlist_del(struct hlist_node * n)6137e841c88SAndre Przywara static inline void __hlist_del(struct hlist_node *n)
6147e841c88SAndre Przywara {
6157e841c88SAndre Przywara 	struct hlist_node *next = n->next;
6167e841c88SAndre Przywara 	struct hlist_node **pprev = n->pprev;
6177e841c88SAndre Przywara 	*pprev = next;
6187e841c88SAndre Przywara 	if (next)
6197e841c88SAndre Przywara 		next->pprev = pprev;
6207e841c88SAndre Przywara }
6217e841c88SAndre Przywara 
hlist_del(struct hlist_node * n)6227e841c88SAndre Przywara static inline void hlist_del(struct hlist_node *n)
6237e841c88SAndre Przywara {
6247e841c88SAndre Przywara 	__hlist_del(n);
625*fbb8a81dSAndre Przywara 	n->next = NULL;
626*fbb8a81dSAndre Przywara 	n->pprev = NULL;
6277e841c88SAndre Przywara }
6287e841c88SAndre Przywara 
hlist_del_init(struct hlist_node * n)6297e841c88SAndre Przywara static inline void hlist_del_init(struct hlist_node *n)
6307e841c88SAndre Przywara {
6317e841c88SAndre Przywara 	if (!hlist_unhashed(n)) {
6327e841c88SAndre Przywara 		__hlist_del(n);
6337e841c88SAndre Przywara 		INIT_HLIST_NODE(n);
6347e841c88SAndre Przywara 	}
6357e841c88SAndre Przywara }
6367e841c88SAndre Przywara 
hlist_add_head(struct hlist_node * n,struct hlist_head * h)6377e841c88SAndre Przywara static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
6387e841c88SAndre Przywara {
6397e841c88SAndre Przywara 	struct hlist_node *first = h->first;
6407e841c88SAndre Przywara 	n->next = first;
6417e841c88SAndre Przywara 	if (first)
6427e841c88SAndre Przywara 		first->pprev = &n->next;
6437e841c88SAndre Przywara 	h->first = n;
6447e841c88SAndre Przywara 	n->pprev = &h->first;
6457e841c88SAndre Przywara }
6467e841c88SAndre Przywara 
6477e841c88SAndre Przywara /* next must be != NULL */
hlist_add_before(struct hlist_node * n,struct hlist_node * next)6487e841c88SAndre Przywara static inline void hlist_add_before(struct hlist_node *n,
6497e841c88SAndre Przywara 					struct hlist_node *next)
6507e841c88SAndre Przywara {
6517e841c88SAndre Przywara 	n->pprev = next->pprev;
6527e841c88SAndre Przywara 	n->next = next;
6537e841c88SAndre Przywara 	next->pprev = &n->next;
6547e841c88SAndre Przywara 	*(n->pprev) = n;
6557e841c88SAndre Przywara }
6567e841c88SAndre Przywara 
hlist_add_behind(struct hlist_node * n,struct hlist_node * prev)6577e841c88SAndre Przywara static inline void hlist_add_behind(struct hlist_node *n,
6587e841c88SAndre Przywara 				    struct hlist_node *prev)
6597e841c88SAndre Przywara {
6607e841c88SAndre Przywara 	n->next = prev->next;
6617e841c88SAndre Przywara 	prev->next = n;
6627e841c88SAndre Przywara 	n->pprev = &prev->next;
6637e841c88SAndre Przywara 
6647e841c88SAndre Przywara 	if (n->next)
6657e841c88SAndre Przywara 		n->next->pprev  = &n->next;
6667e841c88SAndre Przywara }
6677e841c88SAndre Przywara 
6687e841c88SAndre Przywara /* after that we'll appear to be on some hlist and hlist_del will work */
hlist_add_fake(struct hlist_node * n)6697e841c88SAndre Przywara static inline void hlist_add_fake(struct hlist_node *n)
6707e841c88SAndre Przywara {
6717e841c88SAndre Przywara 	n->pprev = &n->next;
6727e841c88SAndre Przywara }
6737e841c88SAndre Przywara 
6747e841c88SAndre Przywara /*
6757e841c88SAndre Przywara  * Move a list from one list head to another. Fixup the pprev
6767e841c88SAndre Przywara  * reference of the first entry if it exists.
6777e841c88SAndre Przywara  */
hlist_move_list(struct hlist_head * old,struct hlist_head * new)6787e841c88SAndre Przywara static inline void hlist_move_list(struct hlist_head *old,
6797e841c88SAndre Przywara 				   struct hlist_head *new)
6807e841c88SAndre Przywara {
6817e841c88SAndre Przywara 	new->first = old->first;
6827e841c88SAndre Przywara 	if (new->first)
6837e841c88SAndre Przywara 		new->first->pprev = &new->first;
6847e841c88SAndre Przywara 	old->first = NULL;
6857e841c88SAndre Przywara }
6867e841c88SAndre Przywara 
6877e841c88SAndre Przywara #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
6887e841c88SAndre Przywara 
6897e841c88SAndre Przywara #define hlist_for_each(pos, head) \
6907e841c88SAndre Przywara 	for (pos = (head)->first; pos ; pos = pos->next)
6917e841c88SAndre Przywara 
6927e841c88SAndre Przywara #define hlist_for_each_safe(pos, n, head) \
6937e841c88SAndre Przywara 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
6947e841c88SAndre Przywara 	     pos = n)
6957e841c88SAndre Przywara 
6967e841c88SAndre Przywara #define hlist_entry_safe(ptr, type, member) \
6977e841c88SAndre Przywara 	({ typeof(ptr) ____ptr = (ptr); \
6987e841c88SAndre Przywara 	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
6997e841c88SAndre Przywara 	})
7007e841c88SAndre Przywara 
7017e841c88SAndre Przywara /**
7027e841c88SAndre Przywara  * hlist_for_each_entry	- iterate over list of given type
7037e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
7047e841c88SAndre Przywara  * @head:	the head for your list.
7057e841c88SAndre Przywara  * @member:	the name of the hlist_node within the struct.
7067e841c88SAndre Przywara  */
7077e841c88SAndre Przywara #define hlist_for_each_entry(pos, head, member)				\
7087e841c88SAndre Przywara 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
7097e841c88SAndre Przywara 	     pos;							\
7107e841c88SAndre Przywara 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
7117e841c88SAndre Przywara 
7127e841c88SAndre Przywara /**
7137e841c88SAndre Przywara  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
7147e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
7157e841c88SAndre Przywara  * @member:	the name of the hlist_node within the struct.
7167e841c88SAndre Przywara  */
7177e841c88SAndre Przywara #define hlist_for_each_entry_continue(pos, member)			\
7187e841c88SAndre Przywara 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
7197e841c88SAndre Przywara 	     pos;							\
7207e841c88SAndre Przywara 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
7217e841c88SAndre Przywara 
7227e841c88SAndre Przywara /**
7237e841c88SAndre Przywara  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
7247e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
7257e841c88SAndre Przywara  * @member:	the name of the hlist_node within the struct.
7267e841c88SAndre Przywara  */
7277e841c88SAndre Przywara #define hlist_for_each_entry_from(pos, member)				\
7287e841c88SAndre Przywara 	for (; pos;							\
7297e841c88SAndre Przywara 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
7307e841c88SAndre Przywara 
7317e841c88SAndre Przywara /**
7327e841c88SAndre Przywara  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
7337e841c88SAndre Przywara  * @pos:	the type * to use as a loop cursor.
7347e841c88SAndre Przywara  * @n:		another &struct hlist_node to use as temporary storage
7357e841c88SAndre Przywara  * @head:	the head for your list.
7367e841c88SAndre Przywara  * @member:	the name of the hlist_node within the struct.
7377e841c88SAndre Przywara  */
7387e841c88SAndre Przywara #define hlist_for_each_entry_safe(pos, n, head, member) 		\
7397e841c88SAndre Przywara 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
7407e841c88SAndre Przywara 	     pos && ({ n = pos->member.next; 1; });			\
7417e841c88SAndre Przywara 	     pos = hlist_entry_safe(n, typeof(*pos), member))
7427e841c88SAndre Przywara 
7437e841c88SAndre Przywara #endif
744