1 /* SPDX-License-Identifier: GPL-2.0 */
20  * using the generic single-entry routines.
29  * INIT_LIST_HEAD - Initialize a list_head structure
37 	WRITE_ONCE(list->next, list);  in INIT_LIST_HEAD()
38 	WRITE_ONCE(list->prev, list);  in INIT_LIST_HEAD()
62  * inline to catch non-faulting corruptions, and only if a corruption is
79 		 * of them completely if they can be proven at compile-time. If  in __list_add_valid()
80 		 * one of the pre-conditions does not hold, the slow-path will  in __list_add_valid()
81 		 * show a report which pre-condition failed.  in __list_add_valid()
83 		if (likely(next->prev == prev && prev->next == next && new != prev && new != next))  in __list_add_valid()
103  * inline to catch non-faulting corruptions, and only if a corruption is
111 		struct list_head *prev = entry->prev;  in __list_del_entry_valid()
112 		struct list_head *next = entry->next;  in __list_del_entry_valid()
119 		if (likely(prev->next == entry && next->prev == entry))  in __list_del_entry_valid()
153 	next->prev = new;  in __list_add()
154 	new->next = next;  in __list_add()
155 	new->prev = prev;  in __list_add()
156 	WRITE_ONCE(prev->next, new);  in __list_add()
160  * list_add - add a new entry
169 	__list_add(new, head, head->next);  in list_add()
174  * list_add_tail - add a new entry
183 	__list_add(new, head->prev, head);  in list_add_tail()
195 	next->prev = prev;  in __list_del()
196 	WRITE_ONCE(prev->next, next);  in __list_del()
202  * This is a special-purpose list clearing method used in the networking code
203  * for lists allocated as per-cpu, where we don't want to incur the extra
209 	__list_del(entry->prev, entry->next);  in __list_del_clearprev()
210 	entry->prev = NULL;  in __list_del_clearprev()
218 	__list_del(entry->prev, entry->next);  in __list_del_entry()
222  * list_del - deletes entry from list.
230 	entry->next = LIST_POISON1;  in list_del()
231 	entry->prev = LIST_POISON2;  in list_del()
235  * list_replace - replace old entry by new one
244 	new->next = old->next;  in list_replace()
245 	new->next->prev = new;  in list_replace()
246 	new->prev = old->prev;  in list_replace()
247 	new->prev->next = new;  in list_replace()
251  * list_replace_init - replace old entry by new one and initialize the old one
265  * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
272 	struct list_head *pos = entry2->prev;  in list_swap()
282  * list_del_init - deletes entry from list and reinitialize it.
292  * list_move - delete from one list and add as another's head
303  * list_move_tail - delete from one list and add as another's tail
315  * list_bulk_move_tail - move a subsection of a list to its tail
327 	first->prev->next = last->next;  in list_bulk_move_tail()
328 	last->next->prev = first->prev;  in list_bulk_move_tail()
330 	head->prev->next = first;  in list_bulk_move_tail()
331 	first->prev = head->prev;  in list_bulk_move_tail()
333 	last->next = head;  in list_bulk_move_tail()
334 	head->prev = last;  in list_bulk_move_tail()
338  * list_is_first -- tests whether @list is the first entry in list @head
344 	return list->prev == head;  in list_is_first()
348  * list_is_last - tests whether @list is the last entry in list @head
354 	return list->next == head;  in list_is_last()
358  * list_is_head - tests whether @list is the list @head
368  * list_empty - tests whether a list is empty
373 	return READ_ONCE(head->next) == head;  in list_empty()
377  * list_del_init_careful - deletes entry from list and reinitialize it.
390 	WRITE_ONCE(entry->prev, entry);  in list_del_init_careful()
391 	smp_store_release(&entry->next, entry);  in list_del_init_careful()
395  * list_empty_careful - tests whether a list is empty and not being modified
405  * if another CPU could re-list_add() it.
409 	struct list_head *next = smp_load_acquire(&head->next);  in list_empty_careful()
410 	return list_is_head(next, head) && (next == READ_ONCE(head->prev));  in list_empty_careful()
414  * list_rotate_left - rotate the list to the left
422 		first = head->next;  in list_rotate_left()
428  * list_rotate_to_front() - Rotate list to specific item.
446  * list_is_singular - tests whether a list has just one entry.
451 	return !list_empty(head) && (head->next == head->prev);  in list_is_singular()
457 	struct list_head *new_first = entry->next;  in __list_cut_position()
458 	list->next = head->next;  in __list_cut_position()
459 	list->next->prev = list;  in __list_cut_position()
460 	list->prev = entry;  in __list_cut_position()
461 	entry->next = list;  in __list_cut_position()
462 	head->next = new_first;  in __list_cut_position()
463 	new_first->prev = head;  in __list_cut_position()
467  * list_cut_position - cut a list into two
485 	if (list_is_singular(head) && !list_is_head(entry, head) && (entry != head->next))  in list_cut_position()
494  * list_cut_before - cut a list into two, before given entry
511 	if (head->next == entry) {  in list_cut_before()
515 	list->next = head->next;  in list_cut_before()
516 	list->next->prev = list;  in list_cut_before()
517 	list->prev = entry->prev;  in list_cut_before()
518 	list->prev->next = list;  in list_cut_before()
519 	head->next = entry;  in list_cut_before()
520 	entry->prev = head;  in list_cut_before()
527 	struct list_head *first = list->next;  in __list_splice()
528 	struct list_head *last = list->prev;  in __list_splice()
530 	first->prev = prev;  in __list_splice()
531 	prev->next = first;  in __list_splice()
533 	last->next = next;  in __list_splice()
534 	next->prev = last;  in __list_splice()
538  * list_splice - join two lists, this is designed for stacks
546 		__list_splice(list, head, head->next);  in list_splice()
550  * list_splice_tail - join two lists, each list being a queue
558 		__list_splice(list, head->prev, head);  in list_splice_tail()
562  * list_splice_init - join two lists and reinitialise the emptied list.
572 		__list_splice(list, head, head->next);  in list_splice_init()
578  * list_splice_tail_init - join two lists and reinitialise the emptied list
589 		__list_splice(list, head->prev, head);  in list_splice_tail_init()
595  * list_entry - get the struct for this entry
604  * list_first_entry - get the first element from a list
612 	list_entry((ptr)->next, type, member)
615  * list_last_entry - get the last element from a list
623 	list_entry((ptr)->prev, type, member)
626  * list_first_entry_or_null - get the first element from a list
635 	struct list_head *pos__ = READ_ONCE(head__->next); \
640  * list_next_entry - get the next element in list
645 	list_entry((pos)->member.next, typeof(*(pos)), member)
648  * list_next_entry_circular - get the next element in list
657 	(list_is_last(&(pos)->member, head) ? \
661  * list_prev_entry - get the prev element in list
666 	list_entry((pos)->member.prev, typeof(*(pos)), member)
669  * list_prev_entry_circular - get the prev element in list
678 	(list_is_first(&(pos)->member, head) ? \
682  * list_for_each	-	iterate over a list
687 	for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
690  * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
695 	for (pos = rcu_dereference((head)->next); \
697 	     pos = rcu_dereference(pos->next))
700  * list_for_each_continue - continue iteration over a list
704  * Continue to iterate over a list, continuing after the current position.
707 	for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
710  * list_for_each_prev	-	iterate over a list backwards
715 	for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
718  * list_for_each_safe - iterate over a list safe against removal of list entry
724 	for (pos = (head)->next, n = pos->next; \
726 	     pos = n, n = pos->next)
729  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
735 	for (pos = (head)->prev, n = pos->prev; \
737 	     pos = n, n = pos->prev)
740  * list_count_nodes - count nodes in the list
755  * list_entry_is_head - test if the entry points to the head of the list
761 	list_is_head(&pos->member, (head))
764  * list_for_each_entry	-	iterate over list of given type
775  * list_for_each_entry_reverse - iterate backwards over list of given type.
786  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
797  * list_for_each_entry_continue - continue iteration over list of given type
802  * Continue to iterate over list of given type, continuing after
803  * the current position.
811  * list_for_each_entry_continue_reverse - iterate backwards from the given point
816  * Start to iterate over list of given type backwards, continuing after
817  * the current position.
825  * list_for_each_entry_from - iterate over list of given type from the current point
830  * Iterate over list of given type, continuing from current position.
837  * list_for_each_entry_from_reverse - iterate backwards over list of given type
838  *                                    from the current point
843  * Iterate backwards over list of given type, continuing from current position.
850  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
863  * list_for_each_entry_safe_continue - continue list iteration safe against removal
869  * Iterate over list of given type, continuing after current point,
879  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
885  * Iterate over list of given type from current point, safe against
894  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
900  * Iterate backwards over list of given type, safe against removal
910  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
918  * and list_safe_reset_next is called after re-taking the lock and before
919  * completing the current iteration of the loop body.
933 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
936 	h->next = NULL;  in INIT_HLIST_NODE()
937 	h->pprev = NULL;  in INIT_HLIST_NODE()
941  * hlist_unhashed - Has node been removed from list and reinitialized?
950 	return !h->pprev;  in hlist_unhashed()
954  * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
958  * to avoid potential load-tearing.  The READ_ONCE() is paired with the
963 	return !READ_ONCE(h->pprev);  in hlist_unhashed_lockless()
967  * hlist_empty - Is the specified hlist_head structure an empty hlist?
972 	return !READ_ONCE(h->first);  in hlist_empty()
977 	struct hlist_node *next = n->next;  in __hlist_del()
978 	struct hlist_node **pprev = n->pprev;  in __hlist_del()
982 		WRITE_ONCE(next->pprev, pprev);  in __hlist_del()
986  * hlist_del - Delete the specified hlist_node from its list
995 	n->next = LIST_POISON1;  in hlist_del()
996 	n->pprev = LIST_POISON2;  in hlist_del()
1000  * hlist_del_init - Delete the specified hlist_node from its list and initialize
1014  * hlist_add_head - add a new entry at the beginning of the hlist
1023 	struct hlist_node *first = h->first;  in hlist_add_head()
1024 	WRITE_ONCE(n->next, first);  in hlist_add_head()
1026 		WRITE_ONCE(first->pprev, &n->next);  in hlist_add_head()
1027 	WRITE_ONCE(h->first, n);  in hlist_add_head()
1028 	WRITE_ONCE(n->pprev, &h->first);  in hlist_add_head()
1032  * hlist_add_before - add a new entry before the one specified
1034  * @next: hlist node to add it before, which must be non-NULL
1039 	WRITE_ONCE(n->pprev, next->pprev);  in hlist_add_before()
1040 	WRITE_ONCE(n->next, next);  in hlist_add_before()
1041 	WRITE_ONCE(next->pprev, &n->next);  in hlist_add_before()
1042 	WRITE_ONCE(*(n->pprev), n);  in hlist_add_before()
1046  * hlist_add_behind - add a new entry after the one specified
1048  * @prev: hlist node to add it after, which must be non-NULL
1053 	WRITE_ONCE(n->next, prev->next);  in hlist_add_behind()
1054 	WRITE_ONCE(prev->next, n);  in hlist_add_behind()
1055 	WRITE_ONCE(n->pprev, &prev->next);  in hlist_add_behind()
1057 	if (n->next)  in hlist_add_behind()
1058 		WRITE_ONCE(n->next->pprev, &n->next);  in hlist_add_behind()
1062  * hlist_add_fake - create a fake hlist consisting of a single headless node
1071 	n->pprev = &n->next;  in hlist_add_fake()
1076  * @h: Node to check for being a self-referential fake hlist.
1080 	return h->pprev == &h->next;  in hlist_fake()
1084  * hlist_is_singular_node - is node the only element of the specified hlist?
1094 	return !n->next && n->pprev == &h->first;  in hlist_is_singular_node()
1098  * hlist_move_list - Move an hlist
1108 	new->first = old->first;  in hlist_move_list()
1109 	if (new->first)  in hlist_move_list()
1110 		new->first->pprev = &new->first;  in hlist_move_list()
1111 	old->first = NULL;  in hlist_move_list()
1115  * hlist_splice_init() - move all entries from one list to another
1126 	if (to->first)  in hlist_splice_init()
1127 		to->first->pprev = &last->next;  in hlist_splice_init()
1128 	last->next = to->first;  in hlist_splice_init()
1129 	to->first = from->first;  in hlist_splice_init()
1130 	from->first->pprev = &to->first;  in hlist_splice_init()
1131 	from->first = NULL;  in hlist_splice_init()
1137 	for (pos = (head)->first; pos ; pos = pos->next)
1140 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1149  * hlist_for_each_entry	- iterate over list of given type
1155 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1157 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1160  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1165 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1167 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1170  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1176 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1179  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1186 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1187 	     pos && ({ n = pos->member.next; 1; });			\
1191  * hlist_count_nodes - count nodes in the hlist