1 | // SPDX-License-Identifier: GPL-2.0-or-later |
2 | /* |
3 | * lib/plist.c |
4 | * |
5 | * Descending-priority-sorted double-linked list |
6 | * |
7 | * (C) 2002-2003 Intel Corp |
8 | * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>. |
9 | * |
10 | * 2001-2005 (c) MontaVista Software, Inc. |
11 | * Daniel Walker <dwalker@mvista.com> |
12 | * |
13 | * (C) 2005 Thomas Gleixner <tglx@linutronix.de> |
14 | * |
15 | * Simplifications of the original code by |
16 | * Oleg Nesterov <oleg@tv-sign.ru> |
17 | * |
18 | * Based on simple lists (include/linux/list.h). |
19 | * |
20 | * This file contains the add / del functions which are considered to |
21 | * be too large to inline. See include/linux/plist.h for further |
22 | * information. |
23 | */ |
24 | |
25 | #include <linux/bug.h> |
26 | #include <linux/plist.h> |
27 | |
28 | #ifdef CONFIG_DEBUG_PLIST |
29 | |
30 | static struct plist_head test_head; |
31 | |
32 | static void plist_check_prev_next(struct list_head *t, struct list_head *p, |
33 | struct list_head *n) |
34 | { |
35 | WARN(n->prev != p || p->next != n, |
36 | "top: %p, n: %p, p: %p\n" |
37 | "prev: %p, n: %p, p: %p\n" |
38 | "next: %p, n: %p, p: %p\n" , |
39 | t, t->next, t->prev, |
40 | p, p->next, p->prev, |
41 | n, n->next, n->prev); |
42 | } |
43 | |
44 | static void plist_check_list(struct list_head *top) |
45 | { |
46 | struct list_head *prev = top, *next = top->next; |
47 | |
48 | plist_check_prev_next(t: top, p: prev, n: next); |
49 | while (next != top) { |
50 | prev = next; |
51 | next = prev->next; |
52 | plist_check_prev_next(t: top, p: prev, n: next); |
53 | } |
54 | } |
55 | |
56 | static void plist_check_head(struct plist_head *head) |
57 | { |
58 | if (!plist_head_empty(head)) |
59 | plist_check_list(top: &plist_first(head)->prio_list); |
60 | plist_check_list(top: &head->node_list); |
61 | } |
62 | |
63 | #else |
64 | # define plist_check_head(h) do { } while (0) |
65 | #endif |
66 | |
67 | /** |
68 | * plist_add - add @node to @head |
69 | * |
70 | * @node: &struct plist_node pointer |
71 | * @head: &struct plist_head pointer |
72 | */ |
73 | void plist_add(struct plist_node *node, struct plist_head *head) |
74 | { |
75 | struct plist_node *first, *iter, *prev = NULL; |
76 | struct list_head *node_next = &head->node_list; |
77 | |
78 | plist_check_head(head); |
79 | WARN_ON(!plist_node_empty(node)); |
80 | WARN_ON(!list_empty(&node->prio_list)); |
81 | |
82 | if (plist_head_empty(head)) |
83 | goto ins_node; |
84 | |
85 | first = iter = plist_first(head); |
86 | |
87 | do { |
88 | if (node->prio < iter->prio) { |
89 | node_next = &iter->node_list; |
90 | break; |
91 | } |
92 | |
93 | prev = iter; |
94 | iter = list_entry(iter->prio_list.next, |
95 | struct plist_node, prio_list); |
96 | } while (iter != first); |
97 | |
98 | if (!prev || prev->prio != node->prio) |
99 | list_add_tail(new: &node->prio_list, head: &iter->prio_list); |
100 | ins_node: |
101 | list_add_tail(new: &node->node_list, head: node_next); |
102 | |
103 | plist_check_head(head); |
104 | } |
105 | |
106 | /** |
107 | * plist_del - Remove a @node from plist. |
108 | * |
109 | * @node: &struct plist_node pointer - entry to be removed |
110 | * @head: &struct plist_head pointer - list head |
111 | */ |
112 | void plist_del(struct plist_node *node, struct plist_head *head) |
113 | { |
114 | plist_check_head(head); |
115 | |
116 | if (!list_empty(head: &node->prio_list)) { |
117 | if (node->node_list.next != &head->node_list) { |
118 | struct plist_node *next; |
119 | |
120 | next = list_entry(node->node_list.next, |
121 | struct plist_node, node_list); |
122 | |
123 | /* add the next plist_node into prio_list */ |
124 | if (list_empty(head: &next->prio_list)) |
125 | list_add(new: &next->prio_list, head: &node->prio_list); |
126 | } |
127 | list_del_init(entry: &node->prio_list); |
128 | } |
129 | |
130 | list_del_init(entry: &node->node_list); |
131 | |
132 | plist_check_head(head); |
133 | } |
134 | |
135 | /** |
136 | * plist_requeue - Requeue @node at end of same-prio entries. |
137 | * |
138 | * This is essentially an optimized plist_del() followed by |
139 | * plist_add(). It moves an entry already in the plist to |
140 | * after any other same-priority entries. |
141 | * |
142 | * @node: &struct plist_node pointer - entry to be moved |
143 | * @head: &struct plist_head pointer - list head |
144 | */ |
145 | void plist_requeue(struct plist_node *node, struct plist_head *head) |
146 | { |
147 | struct plist_node *iter; |
148 | struct list_head *node_next = &head->node_list; |
149 | |
150 | plist_check_head(head); |
151 | BUG_ON(plist_head_empty(head)); |
152 | BUG_ON(plist_node_empty(node)); |
153 | |
154 | if (node == plist_last(head)) |
155 | return; |
156 | |
157 | iter = plist_next(node); |
158 | |
159 | if (node->prio != iter->prio) |
160 | return; |
161 | |
162 | plist_del(node, head); |
163 | |
164 | plist_for_each_continue(iter, head) { |
165 | if (node->prio != iter->prio) { |
166 | node_next = &iter->node_list; |
167 | break; |
168 | } |
169 | } |
170 | list_add_tail(new: &node->node_list, head: node_next); |
171 | |
172 | plist_check_head(head); |
173 | } |
174 | |
175 | #ifdef CONFIG_DEBUG_PLIST |
176 | #include <linux/sched.h> |
177 | #include <linux/sched/clock.h> |
178 | #include <linux/module.h> |
179 | #include <linux/init.h> |
180 | |
181 | static struct plist_node __initdata test_node[241]; |
182 | |
183 | static void __init plist_test_check(int nr_expect) |
184 | { |
185 | struct plist_node *first, *prio_pos, *node_pos; |
186 | |
187 | if (plist_head_empty(head: &test_head)) { |
188 | BUG_ON(nr_expect != 0); |
189 | return; |
190 | } |
191 | |
192 | prio_pos = first = plist_first(head: &test_head); |
193 | plist_for_each(node_pos, &test_head) { |
194 | if (nr_expect-- < 0) |
195 | break; |
196 | if (node_pos == first) |
197 | continue; |
198 | if (node_pos->prio == prio_pos->prio) { |
199 | BUG_ON(!list_empty(&node_pos->prio_list)); |
200 | continue; |
201 | } |
202 | |
203 | BUG_ON(prio_pos->prio > node_pos->prio); |
204 | BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list); |
205 | prio_pos = node_pos; |
206 | } |
207 | |
208 | BUG_ON(nr_expect != 0); |
209 | BUG_ON(prio_pos->prio_list.next != &first->prio_list); |
210 | } |
211 | |
212 | static void __init plist_test_requeue(struct plist_node *node) |
213 | { |
214 | plist_requeue(node, head: &test_head); |
215 | |
216 | if (node != plist_last(head: &test_head)) |
217 | BUG_ON(node->prio == plist_next(node)->prio); |
218 | } |
219 | |
220 | static int __init plist_test(void) |
221 | { |
222 | int nr_expect = 0, i, loop; |
223 | unsigned int r = local_clock(); |
224 | |
225 | printk(KERN_DEBUG "start plist test\n" ); |
226 | plist_head_init(head: &test_head); |
227 | for (i = 0; i < ARRAY_SIZE(test_node); i++) |
228 | plist_node_init(node: test_node + i, prio: 0); |
229 | |
230 | for (loop = 0; loop < 1000; loop++) { |
231 | r = r * 193939 % 47629; |
232 | i = r % ARRAY_SIZE(test_node); |
233 | if (plist_node_empty(node: test_node + i)) { |
234 | r = r * 193939 % 47629; |
235 | test_node[i].prio = r % 99; |
236 | plist_add(node: test_node + i, head: &test_head); |
237 | nr_expect++; |
238 | } else { |
239 | plist_del(node: test_node + i, head: &test_head); |
240 | nr_expect--; |
241 | } |
242 | plist_test_check(nr_expect); |
243 | if (!plist_node_empty(node: test_node + i)) { |
244 | plist_test_requeue(node: test_node + i); |
245 | plist_test_check(nr_expect); |
246 | } |
247 | } |
248 | |
249 | for (i = 0; i < ARRAY_SIZE(test_node); i++) { |
250 | if (plist_node_empty(node: test_node + i)) |
251 | continue; |
252 | plist_del(node: test_node + i, head: &test_head); |
253 | nr_expect--; |
254 | plist_test_check(nr_expect); |
255 | } |
256 | |
257 | printk(KERN_DEBUG "end plist test\n" ); |
258 | return 0; |
259 | } |
260 | |
261 | module_init(plist_test); |
262 | |
263 | #endif |
264 | |