1 // SPDX-License-Identifier: GPL-2.0-or-later
5  * Descending-priority-sorted double-linked list
7  * (C) 2002-2003 Intel Corp
8  * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
10  * 2001-2005 (c) MontaVista Software, Inc.
16  * Oleg Nesterov <oleg@tv-sign.ru>
32 static void plist_check_prev_next(struct list_head *t, struct list_head *p,  in plist_check_prev_next()  argument
35 	WARN(n->prev != p || p->next != n,  in plist_check_prev_next()
39 			 t, t->next, t->prev,  in plist_check_prev_next()
40 			p, p->next, p->prev,  in plist_check_prev_next()
41 			n, n->next, n->prev);  in plist_check_prev_next()
46 	struct list_head *prev = top, *next = top->next;  in plist_check_list()
51 		WRITE_ONCE(next, prev->next);  in plist_check_list()
56 static void plist_check_head(struct plist_head *head)  in plist_check_head()  argument
58 	if (!plist_head_empty(head))  in plist_check_head()
59 		plist_check_list(&plist_first(head)->prio_list);  in plist_check_head()
60 	plist_check_list(&head->node_list);  in plist_check_head()
68  * plist_add - add @node to @head
71  * @head:	&struct plist_head pointer
73 void plist_add(struct plist_node *node, struct plist_head *head)  in plist_add()  argument
76 	struct list_head *node_next = &head->node_list;  in plist_add()
78 	plist_check_head(head);  in plist_add()
80 	WARN_ON(!list_empty(&node->prio_list));  in plist_add()
82 	if (plist_head_empty(head))  in plist_add()
85 	first = iter = plist_first(head);  in plist_add()
86 	last = reverse_iter = list_entry(first->prio_list.prev, struct plist_node, prio_list);  in plist_add()
89 		if (node->prio < iter->prio) {  in plist_add()
90 			node_next = &iter->node_list;  in plist_add()
92 		} else if (node->prio >= reverse_iter->prio) {  in plist_add()
94 			iter = list_entry(reverse_iter->prio_list.next,  in plist_add()
97 				node_next = &iter->node_list;  in plist_add()
102 		iter = list_entry(iter->prio_list.next,  in plist_add()
104 		reverse_iter = list_entry(reverse_iter->prio_list.prev,  in plist_add()
108 	if (!prev || prev->prio != node->prio)  in plist_add()
109 		list_add_tail(&node->prio_list, &iter->prio_list);  in plist_add()
111 	list_add_tail(&node->node_list, node_next);  in plist_add()
113 	plist_check_head(head);  in plist_add()
117  * plist_del - Remove a @node from plist.
119  * @node:	&struct plist_node pointer - entry to be removed
120  * @head:	&struct plist_head pointer - list head
122 void plist_del(struct plist_node *node, struct plist_head *head)  in plist_del()  argument
124 	plist_check_head(head);  in plist_del()
126 	if (!list_empty(&node->prio_list)) {  in plist_del()
127 		if (node->node_list.next != &head->node_list) {  in plist_del()
130 			next = list_entry(node->node_list.next,  in plist_del()
134 			if (list_empty(&next->prio_list))  in plist_del()
135 				list_add(&next->prio_list, &node->prio_list);  in plist_del()
137 		list_del_init(&node->prio_list);  in plist_del()
140 	list_del_init(&node->node_list);  in plist_del()
142 	plist_check_head(head);  in plist_del()
146  * plist_requeue - Requeue @node at end of same-prio entries.
150  * after any other same-priority entries.
152  * @node:	&struct plist_node pointer - entry to be moved
153  * @head:	&struct plist_head pointer - list head
155 void plist_requeue(struct plist_node *node, struct plist_head *head)  in plist_requeue()  argument
158 	struct list_head *node_next = &head->node_list;  in plist_requeue()
160 	plist_check_head(head);  in plist_requeue()
161 	BUG_ON(plist_head_empty(head));  in plist_requeue()
164 	if (node == plist_last(head))  in plist_requeue()
169 	if (node->prio != iter->prio)  in plist_requeue()
172 	plist_del(node, head);  in plist_requeue()
174 	plist_for_each_continue(iter, head) {  in plist_requeue()
175 		if (node->prio != iter->prio) {  in plist_requeue()
176 			node_next = &iter->node_list;  in plist_requeue()
180 	list_add_tail(&node->node_list, node_next);  in plist_requeue()
182 	plist_check_head(head);  in plist_requeue()
204 		if (nr_expect-- < 0)  in plist_test_check()
208 		if (node_pos->prio == prio_pos->prio) {  in plist_test_check()
209 			BUG_ON(!list_empty(&node_pos->prio_list));  in plist_test_check()
213 		BUG_ON(prio_pos->prio > node_pos->prio);  in plist_test_check()
214 		BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);  in plist_test_check()
219 	BUG_ON(prio_pos->prio_list.next != &first->prio_list);  in plist_test_check()
227 		BUG_ON(node->prio == plist_next(node)->prio);  in plist_test_requeue()
250 			nr_expect--;  in plist_test()
263 		nr_expect--;  in plist_test()
289 			time_elapsed += (end - start);  in plist_test()