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 		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()
88 		if (node->prio < iter->prio) {  in plist_add()
89 			node_next = &iter->node_list;  in plist_add()
94 		iter = list_entry(iter->prio_list.next,  in plist_add()
98 	if (!prev || prev->prio != node->prio)  in plist_add()
99 		list_add_tail(&node->prio_list, &iter->prio_list);  in plist_add()
101 	list_add_tail(&node->node_list, node_next);  in plist_add()
103 	plist_check_head(head);  in plist_add()
107  * plist_del - Remove a @node from plist.
109  * @node:	&struct plist_node pointer - entry to be removed
110  * @head:	&struct plist_head pointer - list head
112 void plist_del(struct plist_node *node, struct plist_head *head)  in plist_del()  argument
114 	plist_check_head(head);  in plist_del()
116 	if (!list_empty(&node->prio_list)) {  in plist_del()
117 		if (node->node_list.next != &head->node_list) {  in plist_del()
120 			next = list_entry(node->node_list.next,  in plist_del()
124 			if (list_empty(&next->prio_list))  in plist_del()
125 				list_add(&next->prio_list, &node->prio_list);  in plist_del()
127 		list_del_init(&node->prio_list);  in plist_del()
130 	list_del_init(&node->node_list);  in plist_del()
132 	plist_check_head(head);  in plist_del()
136  * plist_requeue - Requeue @node at end of same-prio entries.
140  * after any other same-priority entries.
142  * @node:	&struct plist_node pointer - entry to be moved
143  * @head:	&struct plist_head pointer - list head
145 void plist_requeue(struct plist_node *node, struct plist_head *head)  in plist_requeue()  argument
148 	struct list_head *node_next = &head->node_list;  in plist_requeue()
150 	plist_check_head(head);  in plist_requeue()
151 	BUG_ON(plist_head_empty(head));  in plist_requeue()
154 	if (node == plist_last(head))  in plist_requeue()
159 	if (node->prio != iter->prio)  in plist_requeue()
162 	plist_del(node, head);  in plist_requeue()
164 	plist_for_each_continue(iter, head) {  in plist_requeue()
165 		if (node->prio != iter->prio) {  in plist_requeue()
166 			node_next = &iter->node_list;  in plist_requeue()
170 	list_add_tail(&node->node_list, node_next);  in plist_requeue()
172 	plist_check_head(head);  in plist_requeue()
194 		if (nr_expect-- < 0)  in plist_test_check()
198 		if (node_pos->prio == prio_pos->prio) {  in plist_test_check()
199 			BUG_ON(!list_empty(&node_pos->prio_list));  in plist_test_check()
203 		BUG_ON(prio_pos->prio > node_pos->prio);  in plist_test_check()
204 		BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);  in plist_test_check()
209 	BUG_ON(prio_pos->prio_list.next != &first->prio_list);  in plist_test_check()
217 		BUG_ON(node->prio == plist_next(node)->prio);  in plist_test_requeue()
240 			nr_expect--;  in plist_test()
253 		nr_expect--;  in plist_test()