1 /* SPDX-License-Identifier: GPL-2.0 */
18  * using the generic single-entry routines.
21 #define LIST_HEAD_INIT(name) { &(name), &(name) }  argument
23 #define LIST_HEAD(name) \  argument
24 	struct list_head name = LIST_HEAD_INIT(name)
27  * INIT_LIST_HEAD - Initialize a list_head structure
35 	WRITE_ONCE(list->next, list);  in INIT_LIST_HEAD()
36 	list->prev = list;  in INIT_LIST_HEAD()
43 extern bool __list_del_entry_valid(struct list_head *entry);
51 static inline bool __list_del_entry_valid(struct list_head *entry)  in __list_del_entry_valid()  argument
58  * Insert a new entry between two known consecutive entries.
70 	next->prev = new;  in __list_add()
71 	new->next = next;  in __list_add()
72 	new->prev = prev;  in __list_add()
73 	WRITE_ONCE(prev->next, new);  in __list_add()
77  * list_add - add a new entry
78  * @new: new entry to be added
81  * Insert a new entry after the specified head.
86 	__list_add(new, head, head->next);  in list_add()
91  * list_add_tail - add a new entry
92  * @new: new entry to be added
95  * Insert a new entry before the specified head.
100 	__list_add(new, head->prev, head);  in list_add_tail()
104  * Delete a list entry by making the prev/next entries
112 	next->prev = prev;  in __list_del()
113 	WRITE_ONCE(prev->next, next);  in __list_del()
117  * Delete a list entry and clear the 'prev' pointer.
119  * This is a special-purpose list clearing method used in the networking code
120  * for lists allocated as per-cpu, where we don't want to incur the extra
124 static inline void __list_del_clearprev(struct list_head *entry)  in __list_del_clearprev()  argument
126 	__list_del(entry->prev, entry->next);  in __list_del_clearprev()
127 	entry->prev = NULL;  in __list_del_clearprev()
130 static inline void __list_del_entry(struct list_head *entry)  in __list_del_entry()  argument
132 	if (!__list_del_entry_valid(entry))  in __list_del_entry()
135 	__list_del(entry->prev, entry->next);  in __list_del_entry()
139  * list_del - deletes entry from list.
140  * @entry: the element to delete from the list.
141  * Note: list_empty() on entry does not return true after this, the entry is
144 static inline void list_del(struct list_head *entry)  in list_del()  argument
146 	__list_del_entry(entry);  in list_del()
147 	entry->next = LIST_POISON1;  in list_del()
148 	entry->prev = LIST_POISON2;  in list_del()
152  * list_replace - replace old entry by new one
161 	new->next = old->next;  in list_replace()
162 	new->next->prev = new;  in list_replace()
163 	new->prev = old->prev;  in list_replace()
164 	new->prev->next = new;  in list_replace()
168  * list_replace_init - replace old entry by new one and initialize the old one
182  * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
189 	struct list_head *pos = entry2->prev;  in list_swap()
199  * list_del_init - deletes entry from list and reinitialize it.
200  * @entry: the element to delete from the list.
202 static inline void list_del_init(struct list_head *entry)  in list_del_init()  argument
204 	__list_del_entry(entry);  in list_del_init()
205 	INIT_LIST_HEAD(entry);  in list_del_init()
209  * list_move - delete from one list and add as another's head
210  * @list: the entry to move
211  * @head: the head that will precede our entry
220  * list_move_tail - delete from one list and add as another's tail
221  * @list: the entry to move
222  * @head: the head that will follow our entry
232  * list_bulk_move_tail - move a subsection of a list to its tail
233  * @head: the head that will follow our entry
234  * @first: first entry to move
235  * @last: last entry to move, can be the same as first
244 	first->prev->next = last->next;  in list_bulk_move_tail()
245 	last->next->prev = first->prev;  in list_bulk_move_tail()
247 	head->prev->next = first;  in list_bulk_move_tail()
248 	first->prev = head->prev;  in list_bulk_move_tail()
250 	last->next = head;  in list_bulk_move_tail()
251 	head->prev = last;  in list_bulk_move_tail()
255  * list_is_first -- tests whether @list is the first entry in list @head
256  * @list: the entry to test
262 	return list->prev == head;  in list_is_first()
266  * list_is_last - tests whether @list is the last entry in list @head
267  * @list: the entry to test
273 	return list->next == head;  in list_is_last()
277  * list_empty - tests whether a list is empty
282 	return READ_ONCE(head->next) == head;  in list_empty()
286  * list_del_init_careful - deletes entry from list and reinitialize it.
287  * @entry: the element to delete from the list.
296 static inline void list_del_init_careful(struct list_head *entry)  in list_del_init_careful()  argument
298 	__list_del_entry(entry);  in list_del_init_careful()
299 	entry->prev = entry;  in list_del_init_careful()
300 	smp_store_release(&entry->next, entry);  in list_del_init_careful()
304  * list_empty_careful - tests whether a list is empty and not being modified
313  * to the list entry is list_del_init(). Eg. it cannot be used
314  * if another CPU could re-list_add() it.
318 	struct list_head *next = smp_load_acquire(&head->next);  in list_empty_careful()
319 	return (next == head) && (next == head->prev);  in list_empty_careful()
323  * list_rotate_left - rotate the list to the left
331 		first = head->next;  in list_rotate_left()
337  * list_rotate_to_front() - Rotate list to specific item.
355  * list_is_singular - tests whether a list has just one entry.
360 	return !list_empty(head) && (head->next == head->prev);  in list_is_singular()
364 		struct list_head *head, struct list_head *entry)  in __list_cut_position()  argument
366 	struct list_head *new_first = entry->next;  in __list_cut_position()
367 	list->next = head->next;  in __list_cut_position()
368 	list->next->prev = list;  in __list_cut_position()
369 	list->prev = entry;  in __list_cut_position()
370 	entry->next = list;  in __list_cut_position()
371 	head->next = new_first;  in __list_cut_position()
372 	new_first->prev = head;  in __list_cut_position()
376  * list_cut_position - cut a list into two
379  * @entry: an entry within head, could be the head itself
383  * including @entry, from @head to @list. You should
384  * pass on @entry an element you know is on @head. @list
390 		struct list_head *head, struct list_head *entry)  in list_cut_position()  argument
395 		(head->next != entry && head != entry))  in list_cut_position()
397 	if (entry == head)  in list_cut_position()
400 		__list_cut_position(list, head, entry);  in list_cut_position()
404  * list_cut_before - cut a list into two, before given entry
407  * @entry: an entry within head, could be the head itself
410  * excluding @entry, from @head to @list.  You should pass
411  * in @entry an element you know is on @head.  @list should
414  * If @entry == @head, all entries on @head are moved to
419 				   struct list_head *entry)  in list_cut_before()  argument
421 	if (head->next == entry) {  in list_cut_before()
425 	list->next = head->next;  in list_cut_before()
426 	list->next->prev = list;  in list_cut_before()
427 	list->prev = entry->prev;  in list_cut_before()
428 	list->prev->next = list;  in list_cut_before()
429 	head->next = entry;  in list_cut_before()
430 	entry->prev = head;  in list_cut_before()
437 	struct list_head *first = list->next;  in __list_splice()
438 	struct list_head *last = list->prev;  in __list_splice()
440 	first->prev = prev;  in __list_splice()
441 	prev->next = first;  in __list_splice()
443 	last->next = next;  in __list_splice()
444 	next->prev = last;  in __list_splice()
448  * list_splice - join two lists, this is designed for stacks
456 		__list_splice(list, head, head->next);  in list_splice()
460  * list_splice_tail - join two lists, each list being a queue
468 		__list_splice(list, head->prev, head);  in list_splice_tail()
472  * list_splice_init - join two lists and reinitialise the emptied list.
482 		__list_splice(list, head, head->next);  in list_splice_init()
488  * list_splice_tail_init - join two lists and reinitialise the emptied list
499 		__list_splice(list, head->prev, head);  in list_splice_tail_init()
505  * list_entry - get the struct for this entry
508  * @member:	the name of the list_head within the struct.
514  * list_first_entry - get the first element from a list
517  * @member:	the name of the list_head within the struct.
522 	list_entry((ptr)->next, type, member)
525  * list_last_entry - get the last element from a list
528  * @member:	the name of the list_head within the struct.
533 	list_entry((ptr)->prev, type, member)
536  * list_first_entry_or_null - get the first element from a list
539  * @member:	the name of the list_head within the struct.
545 	struct list_head *pos__ = READ_ONCE(head__->next); \
550  * list_next_entry - get the next element in list
552  * @member:	the name of the list_head within the struct.
555 	list_entry((pos)->member.next, typeof(*(pos)), member)
558  * list_prev_entry - get the prev element in list
560  * @member:	the name of the list_head within the struct.
563 	list_entry((pos)->member.prev, typeof(*(pos)), member)
566  * list_for_each	-	iterate over a list
571 	for (pos = (head)->next; pos != (head); pos = pos->next)
574  * list_for_each_continue - continue iteration over a list
581 	for (pos = pos->next; pos != (head); pos = pos->next)
584  * list_for_each_prev	-	iterate over a list backwards
589 	for (pos = (head)->prev; pos != (head); pos = pos->prev)
592  * list_for_each_safe - iterate over a list safe against removal of list entry
598 	for (pos = (head)->next, n = pos->next; pos != (head); \
599 		pos = n, n = pos->next)
602  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
608 	for (pos = (head)->prev, n = pos->prev; \
610 	     pos = n, n = pos->prev)
613  * list_entry_is_head - test if the entry points to the head of the list
616  * @member:	the name of the list_head within the struct.
619 	(&pos->member == (head))
622  * list_for_each_entry	-	iterate over list of given type
625  * @member:	the name of the list_head within the struct.
633  * list_for_each_entry_reverse - iterate backwards over list of given type.
636  * @member:	the name of the list_head within the struct.
644  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
647  * @member:	the name of the list_head within the struct.
649  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
655  * list_for_each_entry_continue - continue iteration over list of given type
658  * @member:	the name of the list_head within the struct.
669  * list_for_each_entry_continue_reverse - iterate backwards from the given point
672  * @member:	the name of the list_head within the struct.
683  * list_for_each_entry_from - iterate over list of given type from the current point
686  * @member:	the name of the list_head within the struct.
695  * list_for_each_entry_from_reverse - iterate backwards over list of given type
699  * @member:	the name of the list_head within the struct.
708  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
712  * @member:	the name of the list_head within the struct.
721  * list_for_each_entry_safe_continue - continue list iteration safe against removal
725  * @member:	the name of the list_head within the struct.
728  * safe against removal of list entry.
737  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
741  * @member:	the name of the list_head within the struct.
744  * removal of list entry.
752  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
756  * @member:	the name of the list_head within the struct.
759  * of list entry.
768  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
771  * @member:	the name of the list_head within the struct.
776  * and list_safe_reset_next is called after re-taking the lock and before
790 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }  argument
791 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
794 	h->next = NULL;  in INIT_HLIST_NODE()
795 	h->pprev = NULL;  in INIT_HLIST_NODE()
799  * hlist_unhashed - Has node been removed from list and reinitialized?
808 	return !h->pprev;  in hlist_unhashed()
812  * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
816  * to avoid potential load-tearing.  The READ_ONCE() is paired with the
821 	return !READ_ONCE(h->pprev);  in hlist_unhashed_lockless()
825  * hlist_empty - Is the specified hlist_head structure an empty hlist?
830 	return !READ_ONCE(h->first);  in hlist_empty()
835 	struct hlist_node *next = n->next;  in __hlist_del()
836 	struct hlist_node **pprev = n->pprev;  in __hlist_del()
840 		WRITE_ONCE(next->pprev, pprev);  in __hlist_del()
844  * hlist_del - Delete the specified hlist_node from its list
853 	n->next = LIST_POISON1;  in hlist_del()
854 	n->pprev = LIST_POISON2;  in hlist_del()
858  * hlist_del_init - Delete the specified hlist_node from its list and initialize
872  * hlist_add_head - add a new entry at the beginning of the hlist
873  * @n: new entry to be added
876  * Insert a new entry after the specified head.
881 	struct hlist_node *first = h->first;  in hlist_add_head()
882 	WRITE_ONCE(n->next, first);  in hlist_add_head()
884 		WRITE_ONCE(first->pprev, &n->next);  in hlist_add_head()
885 	WRITE_ONCE(h->first, n);  in hlist_add_head()
886 	WRITE_ONCE(n->pprev, &h->first);  in hlist_add_head()
890  * hlist_add_before - add a new entry before the one specified
891  * @n: new entry to be added
892  * @next: hlist node to add it before, which must be non-NULL
897 	WRITE_ONCE(n->pprev, next->pprev);  in hlist_add_before()
898 	WRITE_ONCE(n->next, next);  in hlist_add_before()
899 	WRITE_ONCE(next->pprev, &n->next);  in hlist_add_before()
900 	WRITE_ONCE(*(n->pprev), n);  in hlist_add_before()
904  * hlist_add_behing - add a new entry after the one specified
905  * @n: new entry to be added
906  * @prev: hlist node to add it after, which must be non-NULL
911 	WRITE_ONCE(n->next, prev->next);  in hlist_add_behind()
912 	WRITE_ONCE(prev->next, n);  in hlist_add_behind()
913 	WRITE_ONCE(n->pprev, &prev->next);  in hlist_add_behind()
915 	if (n->next)  in hlist_add_behind()
916 		WRITE_ONCE(n->next->pprev, &n->next);  in hlist_add_behind()
920  * hlist_add_fake - create a fake hlist consisting of a single headless node
929 	n->pprev = &n->next;  in hlist_add_fake()
934  * @h: Node to check for being a self-referential fake hlist.
938 	return h->pprev == &h->next;  in hlist_fake()
942  * hlist_is_singular_node - is node the only element of the specified hlist?
952 	return !n->next && n->pprev == &h->first;  in hlist_is_singular_node()
956  * hlist_move_list - Move an hlist
961  * reference of the first entry if it exists.
966 	new->first = old->first;  in hlist_move_list()
967 	if (new->first)  in hlist_move_list()
968 		new->first->pprev = &new->first;  in hlist_move_list()
969 	old->first = NULL;  in hlist_move_list()
975 	for (pos = (head)->first; pos ; pos = pos->next)
978 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
987  * hlist_for_each_entry	- iterate over list of given type
990  * @member:	the name of the hlist_node within the struct.
993 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
995 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
998  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1000  * @member:	the name of the hlist_node within the struct.
1003 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1005 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1008  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1010  * @member:	the name of the hlist_node within the struct.
1014 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1017  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1021  * @member:	the name of the hlist_node within the struct.
1024 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1025 	     pos && ({ n = pos->member.next; 1; });			\