1 /* SPDX-License-Identifier: GPL-2.0 */
17  * using the generic single-entry routines.
27 	list->next = list;  in INIT_LIST_HEAD()
28 	list->prev = list;  in INIT_LIST_HEAD()
42 	next->prev = new;  in __list_add()
43 	new->next = next;  in __list_add()
44 	new->prev = prev;  in __list_add()
45 	prev->next = new;  in __list_add()
54  * list_add - add a new entry
63 	__list_add(new, head, head->next);  in list_add()
68  * list_add_tail - add a new entry
77 	__list_add(new, head->prev, head);  in list_add_tail()
89 	next->prev = prev;  in __list_del()
90 	WRITE_ONCE(prev->next, next);  in __list_del()
94  * list_del - deletes entry from list.
102 	__list_del(entry->prev, entry->next);  in __list_del_entry()
107 	__list_del(entry->prev, entry->next);  in list_del()
108 	entry->next = LIST_POISON1;  in list_del()
109 	entry->prev = LIST_POISON2;  in list_del()
117  * list_replace - replace old entry by new one
126 	new->next = old->next;  in list_replace()
127 	new->next->prev = new;  in list_replace()
128 	new->prev = old->prev;  in list_replace()
129 	new->prev->next = new;  in list_replace()
140  * list_del_init - deletes entry from list and reinitialize it.
150  * list_move - delete from one list and add as another's head
161  * list_move_tail - delete from one list and add as another's tail
173  * list_is_last - tests whether @list is the last entry in list @head
180 	return list->next == head;  in list_is_last()
184  * list_empty - tests whether a list is empty
189 	return head->next == head;  in list_empty()
193  * list_empty_careful - tests whether a list is empty and not being modified
203  * if another CPU could re-list_add() it.
207 	struct list_head *next = head->next;  in list_empty_careful()
208 	return (next == head) && (next == head->prev);  in list_empty_careful()
212  * list_rotate_left - rotate the list to the left
220 		first = head->next;  in list_rotate_left()
226  * list_is_singular - tests whether a list has just one entry.
231 	return !list_empty(head) && (head->next == head->prev);  in list_is_singular()
237 	struct list_head *new_first = entry->next;  in __list_cut_position()
238 	list->next = head->next;  in __list_cut_position()
239 	list->next->prev = list;  in __list_cut_position()
240 	list->prev = entry;  in __list_cut_position()
241 	entry->next = list;  in __list_cut_position()
242 	head->next = new_first;  in __list_cut_position()
243 	new_first->prev = head;  in __list_cut_position()
247  * list_cut_position - cut a list into two
266 		(head->next != entry && head != entry))  in list_cut_position()
278 	struct list_head *first = list->next;  in __list_splice()
279 	struct list_head *last = list->prev;  in __list_splice()
281 	first->prev = prev;  in __list_splice()
282 	prev->next = first;  in __list_splice()
284 	last->next = next;  in __list_splice()
285 	next->prev = last;  in __list_splice()
289  * list_splice - join two lists, this is designed for stacks
297 		__list_splice(list, head, head->next);  in list_splice()
301  * list_splice_tail - join two lists, each list being a queue
309 		__list_splice(list, head->prev, head);  in list_splice_tail()
313  * list_splice_init - join two lists and reinitialise the emptied list.
323 		__list_splice(list, head, head->next);  in list_splice_init()
329  * list_splice_tail_init - join two lists and reinitialise the emptied list
340 		__list_splice(list, head->prev, head);  in list_splice_tail_init()
346  * list_entry - get the struct for this entry
355  * list_first_entry - get the first element from a list
363 	list_entry((ptr)->next, type, member)
366  * list_last_entry - get the last element from a list
374 	list_entry((ptr)->prev, type, member)
377  * list_first_entry_or_null - get the first element from a list
388  * list_last_entry_or_null - get the last element from a list
399  * list_next_entry - get the next element in list
404 	list_entry((pos)->member.next, typeof(*(pos)), member)
407  * list_prev_entry - get the prev element in list
412 	list_entry((pos)->member.prev, typeof(*(pos)), member)
415  * list_for_each	-	iterate over a list
420 	for (pos = (head)->next; pos != (head); pos = pos->next)
423  * list_for_each_prev	-	iterate over a list backwards
428 	for (pos = (head)->prev; pos != (head); pos = pos->prev)
431  * list_for_each_safe - iterate over a list safe against removal of list entry
437 	for (pos = (head)->next, n = pos->next; pos != (head); \
438 		pos = n, n = pos->next)
441  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
447 	for (pos = (head)->prev, n = pos->prev; \
449 	     pos = n, n = pos->prev)
452  * list_for_each_entry	-	iterate over list of given type
459 	     &pos->member != (head);					\
463  * list_for_each_entry_reverse - iterate backwards over list of given type.
470 	     &pos->member != (head); 					\
474  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
485  * list_for_each_entry_continue - continue iteration over list of given type
490  * Continue to iterate over list of given type, continuing after
491  * the current position.
495 	     &pos->member != (head);					\
499  * list_for_each_entry_continue_reverse - iterate backwards from the given point
504  * Start to iterate over list of given type backwards, continuing after
505  * the current position.
509 	     &pos->member != (head);					\
513  * list_for_each_entry_from - iterate over list of given type from the current point
518  * Iterate over list of given type, continuing from current position.
521 	for (; &pos->member != (head);					\
525  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
534 	     &pos->member != (head); 					\
538  * list_for_each_entry_safe_continue - continue list iteration safe against removal
544  * Iterate over list of given type, continuing after current point,
550 	     &pos->member != (head);						\
554  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
560  * Iterate over list of given type from current point, safe against
565 	     &pos->member != (head);						\
569  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
575  * Iterate backwards over list of given type, safe against removal
581 	     &pos->member != (head); 					\
585  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
593  * and list_safe_reset_next is called after re-taking the lock and before
594  * completing the current iteration of the loop body.
608 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
611 	h->next = NULL;  in INIT_HLIST_NODE()
612 	h->pprev = NULL;  in INIT_HLIST_NODE()
617 	return !h->pprev;  in hlist_unhashed()
622 	return !h->first;  in hlist_empty()
627 	struct hlist_node *next = n->next;  in __hlist_del()
628 	struct hlist_node **pprev = n->pprev;  in __hlist_del()
632 		next->pprev = pprev;  in __hlist_del()
638 	n->next = LIST_POISON1;  in hlist_del()
639 	n->pprev = LIST_POISON2;  in hlist_del()
652 	struct hlist_node *first = h->first;  in hlist_add_head()
653 	n->next = first;  in hlist_add_head()
655 		first->pprev = &n->next;  in hlist_add_head()
656 	h->first = n;  in hlist_add_head()
657 	n->pprev = &h->first;  in hlist_add_head()
664 	n->pprev = next->pprev;  in hlist_add_before()
665 	n->next = next;  in hlist_add_before()
666 	next->pprev = &n->next;  in hlist_add_before()
667 	*(n->pprev) = n;  in hlist_add_before()
673 	n->next = prev->next;  in hlist_add_behind()
674 	prev->next = n;  in hlist_add_behind()
675 	n->pprev = &prev->next;  in hlist_add_behind()
677 	if (n->next)  in hlist_add_behind()
678 		n->next->pprev  = &n->next;  in hlist_add_behind()
684 	n->pprev = &n->next;  in hlist_add_fake()
689 	return h->pprev == &h->next;  in hlist_fake()
699 	new->first = old->first;  in hlist_move_list()
700 	if (new->first)  in hlist_move_list()
701 		new->first->pprev = &new->first;  in hlist_move_list()
702 	old->first = NULL;  in hlist_move_list()
708 	for (pos = (head)->first; pos ; pos = pos->next)
711 	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
720  * hlist_for_each_entry	- iterate over list of given type
726 	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
728 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
731  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
736 	for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
738 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
741  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
747 	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
750  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
757 	for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
758 	     pos && ({ n = pos->member.next; 1; });			\
762  * list_del_range - deletes range of entries from list.
771 	begin->prev->next = end->next;  in list_del_range()
772 	end->next->prev = begin->prev;  in list_del_range()
776  * list_for_each_from	-	iterate over a list from one of its nodes
781 	for (; pos != (head); pos = pos->next)