14  * Circular doubly linked list implementation.
30  * @list: list_head structure to be initialized.
32  * Initializes the list_head to point to itself.  If it is a list header,
33  * the result is an empty list.
35 static inline void INIT_LIST_HEAD(struct list_head *list)  in INIT_LIST_HEAD()  argument
37 	WRITE_ONCE(list->next, list);  in INIT_LIST_HEAD()
38 	WRITE_ONCE(list->prev, list);  in INIT_LIST_HEAD()
62  * This is only for internal list manipulation where we know
81  * @head: list head to add it after
95  * @head: list head to add it before
106  * Delete a list entry by making the prev/next entries
109  * This is only for internal list manipulation where we know
119  * Delete a list entry and clear the 'prev' pointer.
121  * This is a special-purpose list clearing method used in the networking code
141  * list_del - deletes entry from list.
142  * @entry: the element to delete from the list.
201  * list_del_init - deletes entry from list and reinitialize it.
202  * @entry: the element to delete from the list.
211  * list_move - delete from one list and add as another's head
212  * @list: the entry to move
215 static inline void list_move(struct list_head *list, struct list_head *head)  in list_move()  argument
217 	__list_del_entry(list);  in list_move()
218 	list_add(list, head);  in list_move()
222  * list_move_tail - delete from one list and add as another's tail
223  * @list: the entry to move
226 static inline void list_move_tail(struct list_head *list,  in list_move_tail()  argument
229 	__list_del_entry(list);  in list_move_tail()
230 	list_add_tail(list, head);  in list_move_tail()
234  * list_bulk_move_tail - move a subsection of a list to its tail
240  * All three entries must belong to the same linked list.
257  * list_is_first -- tests whether @list is the first entry in list @head
258  * @list: the entry to test
259  * @head: the head of the list
261 static inline int list_is_first(const struct list_head *list, const struct list_head *head)  in list_is_first()  argument
263 	return list->prev == head;  in list_is_first()
267  * list_is_last - tests whether @list is the last entry in list @head
268  * @list: the entry to test
269  * @head: the head of the list
271 static inline int list_is_last(const struct list_head *list, const struct list_head *head)  in list_is_last()  argument
273 	return list->next == head;  in list_is_last()
277  * list_is_head - tests whether @list is the list @head
278  * @list: the entry to test
279  * @head: the head of the list
281 static inline int list_is_head(const struct list_head *list, const struct list_head *head)  in list_is_head()  argument
283 	return list == head;  in list_is_head()
287  * list_empty - tests whether a list is empty
288  * @head: the list to test.
296  * list_del_init_careful - deletes entry from list and reinitialize it.
297  * @entry: the element to delete from the list.
314  * list_empty_careful - tests whether a list is empty and not being modified
315  * @head: the list to test
318  * tests whether a list is empty _and_ checks that no other CPU might be
323  * to the list entry is list_del_init(). Eg. it cannot be used
333  * list_rotate_left - rotate the list to the left
334  * @head: the head of the list
347  * list_rotate_to_front() - Rotate list to specific item.
348  * @list: The desired new front of the list.
349  * @head: The head of the list.
351  * Rotates list so that @list becomes the new front of the list.
353 static inline void list_rotate_to_front(struct list_head *list,  in list_rotate_to_front()  argument
357 	 * Deletes the list head from the list denoted by @head and  in list_rotate_to_front()
358 	 * places it as the tail of @list, this effectively rotates the  in list_rotate_to_front()
359 	 * list so that @list is at the front.  in list_rotate_to_front()
361 	list_move_tail(head, list);  in list_rotate_to_front()
365  * list_is_singular - tests whether a list has just one entry.
366  * @head: the list to test.
373 static inline void __list_cut_position(struct list_head *list,  in __list_cut_position()  argument
377 	list->next = head->next;  in __list_cut_position()
378 	list->next->prev = list;  in __list_cut_position()
379 	list->prev = entry;  in __list_cut_position()
380 	entry->next = list;  in __list_cut_position()
386  * list_cut_position - cut a list into two
387  * @list: a new list to add all removed entries
388  * @head: a list with entries
390  *	and if so we won't cut the list
393  * including @entry, from @head to @list. You should
394  * pass on @entry an element you know is on @head. @list
395  * should be an empty list or a list you do not care about
399 static inline void list_cut_position(struct list_head *list,  in list_cut_position()  argument
407 		INIT_LIST_HEAD(list);  in list_cut_position()
409 		__list_cut_position(list, head, entry);  in list_cut_position()
413  * list_cut_before - cut a list into two, before given entry
414  * @list: a new list to add all removed entries
415  * @head: a list with entries
419  * excluding @entry, from @head to @list.  You should pass
420  * in @entry an element you know is on @head.  @list should
421  * be an empty list or a list you do not care about losing
424  * @list.
426 static inline void list_cut_before(struct list_head *list,  in list_cut_before()  argument
431 		INIT_LIST_HEAD(list);  in list_cut_before()
434 	list->next = head->next;  in list_cut_before()
435 	list->next->prev = list;  in list_cut_before()
436 	list->prev = entry->prev;  in list_cut_before()
437 	list->prev->next = list;  in list_cut_before()
442 static inline void __list_splice(const struct list_head *list,  in __list_splice()  argument
446 	struct list_head *first = list->next;  in __list_splice()
447 	struct list_head *last = list->prev;  in __list_splice()
458  * @list: the new list to add.
459  * @head: the place to add it in the first list.
461 static inline void list_splice(const struct list_head *list,  in list_splice()  argument
464 	if (!list_empty(list))  in list_splice()
465 		__list_splice(list, head, head->next);  in list_splice()
469  * list_splice_tail - join two lists, each list being a queue
470  * @list: the new list to add.
471  * @head: the place to add it in the first list.
473 static inline void list_splice_tail(struct list_head *list,  in list_splice_tail()  argument
476 	if (!list_empty(list))  in list_splice_tail()
477 		__list_splice(list, head->prev, head);  in list_splice_tail()
481  * list_splice_init - join two lists and reinitialise the emptied list.
482  * @list: the new list to add.
483  * @head: the place to add it in the first list.
485  * The list at @list is reinitialised
487 static inline void list_splice_init(struct list_head *list,  in list_splice_init()  argument
490 	if (!list_empty(list)) {  in list_splice_init()
491 		__list_splice(list, head, head->next);  in list_splice_init()
492 		INIT_LIST_HEAD(list);  in list_splice_init()
497  * list_splice_tail_init - join two lists and reinitialise the emptied list
498  * @list: the new list to add.
499  * @head: the place to add it in the first list.
502  * The list at @list is reinitialised
504 static inline void list_splice_tail_init(struct list_head *list,  in list_splice_tail_init()  argument
507 	if (!list_empty(list)) {  in list_splice_tail_init()
508 		__list_splice(list, head->prev, head);  in list_splice_tail_init()
509 		INIT_LIST_HEAD(list);  in list_splice_tail_init()
523  * list_first_entry - get the first element from a list
524  * @ptr:	the list head to take the element from.
528  * Note, that list is expected to be not empty.
534  * list_last_entry - get the last element from a list
535  * @ptr:	the list head to take the element from.
539  * Note, that list is expected to be not empty.
545  * list_first_entry_or_null - get the first element from a list
546  * @ptr:	the list head to take the element from.
550  * Note that if the list is empty, it returns NULL.
559  * list_next_entry - get the next element in list
567  * list_next_entry_circular - get the next element in list
569  * @head:	the list head to take the element from.
573  * Note, that list is expected to be not empty.
580  * list_prev_entry - get the prev element in list
588  * list_prev_entry_circular - get the prev element in list
590  * @head:	the list head to take the element from.
594  * Note, that list is expected to be not empty.
601  * list_for_each	-	iterate over a list
603  * @head:	the head for your list.
609  * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
611  * @head:	the head for your list.
619  * list_for_each_continue - continue iteration over a list
621  * @head:	the head for your list.
623  * Continue to iterate over a list, continuing after the current position.
629  * list_for_each_prev	-	iterate over a list backwards
631  * @head:	the head for your list.
637  * list_for_each_safe - iterate over a list safe against removal of list entry
640  * @head:	the head for your list.
648  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
651  * @head:	the head for your list.
659  * list_entry_is_head - test if the entry points to the head of the list
661  * @head:	the head for your list.
668  * list_for_each_entry	-	iterate over list of given type
670  * @head:	the head for your list.
679  * list_for_each_entry_reverse - iterate backwards over list of given type.
681  * @head:	the head for your list.
692  * @head:	the head of the list
701  * list_for_each_entry_continue - continue iteration over list of given type
703  * @head:	the head for your list.
706  * Continue to iterate over list of given type, continuing after
717  * @head:	the head for your list.
720  * Start to iterate over list of given type backwards, continuing after
729  * list_for_each_entry_from - iterate over list of given type from the current point
731  * @head:	the head for your list.
734  * Iterate over list of given type, continuing from current position.
741  * list_for_each_entry_from_reverse - iterate backwards over list of given type
744  * @head:	the head for your list.
747  * Iterate backwards over list of given type, continuing from current position.
754  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
757  * @head:	the head for your list.
767  * list_for_each_entry_safe_continue - continue list iteration safe against removal
770  * @head:	the head for your list.
773  * Iterate over list of given type, continuing after current point,
774  * safe against removal of list entry.
783  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
786  * @head:	the head for your list.
789  * Iterate over list of given type from current point, safe against
790  * removal of list entry.
798  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
801  * @head:	the head for your list.
804  * Iterate backwards over list of given type, safe against removal
805  * of list entry.
819  * list_safe_reset_next is not safe to use in general if the list may be
821  * exception to this is if the cursor element (pos) is pinned in the list,
829  * Double linked lists with a single pointer list head.
830  * Mostly useful for hash tables where the two pointer list head is
845  * hlist_unhashed - Has node been removed from list and reinitialized?
890  * hlist_del - Delete the specified hlist_node from its list
904  * hlist_del_init - Delete the specified hlist_node from its list and initialize
967  * @n: Node to make a fake list out of
971  * in cases where there is no list.
990  * @h: Header for potentially singular list.
1003  * @old: hlist_head for old list.
1004  * @new: hlist_head for new list.
1006  * Move a list from one list head to another. Fixup the pprev
1033  * hlist_for_each_entry	- iterate over list of given type
1035  * @head:	the head for your list.
1063  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1066  * @head:	the head for your list.