1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
2 | /* |
3 | * Descending-priority-sorted double-linked list |
4 | * |
5 | * (C) 2002-2003 Intel Corp |
6 | * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>. |
7 | * |
8 | * 2001-2005 (c) MontaVista Software, Inc. |
9 | * Daniel Walker <dwalker@mvista.com> |
10 | * |
11 | * (C) 2005 Thomas Gleixner <tglx@linutronix.de> |
12 | * |
13 | * Simplifications of the original code by |
14 | * Oleg Nesterov <oleg@tv-sign.ru> |
15 | * |
16 | * Based on simple lists (include/linux/list.h). |
17 | * |
18 | * This is a priority-sorted list of nodes; each node has a |
19 | * priority from INT_MIN (highest) to INT_MAX (lowest). |
20 | * |
21 | * Addition is O(K), removal is O(1), change of priority of a node is |
22 | * O(K) and K is the number of RT priority levels used in the system. |
23 | * (1 <= K <= 99) |
24 | * |
25 | * This list is really a list of lists: |
26 | * |
27 | * - The tier 1 list is the prio_list, different priority nodes. |
28 | * |
29 | * - The tier 2 list is the node_list, serialized nodes. |
30 | * |
31 | * Simple ASCII art explanation: |
32 | * |
33 | * pl:prio_list (only for plist_node) |
34 | * nl:node_list |
35 | * HEAD| NODE(S) |
36 | * | |
37 | * ||------------------------------------| |
38 | * ||->|pl|<->|pl|<--------------->|pl|<-| |
39 | * | |10| |21| |21| |21| |40| (prio) |
40 | * | | | | | | | | | | | |
41 | * | | | | | | | | | | | |
42 | * |->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-| |
43 | * |-------------------------------------------| |
44 | * |
45 | * The nodes on the prio_list list are sorted by priority to simplify |
46 | * the insertion of new nodes. There are no nodes with duplicate |
47 | * priorites on the list. |
48 | * |
49 | * The nodes on the node_list are ordered by priority and can contain |
50 | * entries which have the same priority. Those entries are ordered |
51 | * FIFO |
52 | * |
53 | * Addition means: look for the prio_list node in the prio_list |
54 | * for the priority of the node and insert it before the node_list |
55 | * entry of the next prio_list node. If it is the first node of |
56 | * that priority, add it to the prio_list in the right position and |
57 | * insert it into the serialized node_list list |
58 | * |
59 | * Removal means remove it from the node_list and remove it from |
60 | * the prio_list if the node_list list_head is non empty. In case |
61 | * of removal from the prio_list it must be checked whether other |
62 | * entries of the same priority are on the list or not. If there |
63 | * is another entry of the same priority then this entry has to |
64 | * replace the removed entry on the prio_list. If the entry which |
65 | * is removed is the only entry of this priority then a simple |
66 | * remove from both list is sufficient. |
67 | * |
68 | * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX |
69 | * is lowest priority. |
70 | * |
71 | * No locking is done, up to the caller. |
72 | */ |
73 | #ifndef _LINUX_PLIST_H_ |
74 | #define _LINUX_PLIST_H_ |
75 | |
76 | #include <linux/container_of.h> |
77 | #include <linux/list.h> |
78 | #include <linux/plist_types.h> |
79 | |
80 | #include <asm/bug.h> |
81 | |
82 | /** |
83 | * PLIST_HEAD_INIT - static struct plist_head initializer |
84 | * @head: struct plist_head variable name |
85 | */ |
86 | #define PLIST_HEAD_INIT(head) \ |
87 | { \ |
88 | .node_list = LIST_HEAD_INIT((head).node_list) \ |
89 | } |
90 | |
91 | /** |
92 | * PLIST_HEAD - declare and init plist_head |
93 | * @head: name for struct plist_head variable |
94 | */ |
95 | #define PLIST_HEAD(head) \ |
96 | struct plist_head head = PLIST_HEAD_INIT(head) |
97 | |
98 | /** |
99 | * PLIST_NODE_INIT - static struct plist_node initializer |
100 | * @node: struct plist_node variable name |
101 | * @__prio: initial node priority |
102 | */ |
103 | #define PLIST_NODE_INIT(node, __prio) \ |
104 | { \ |
105 | .prio = (__prio), \ |
106 | .prio_list = LIST_HEAD_INIT((node).prio_list), \ |
107 | .node_list = LIST_HEAD_INIT((node).node_list), \ |
108 | } |
109 | |
110 | /** |
111 | * plist_head_init - dynamic struct plist_head initializer |
112 | * @head: &struct plist_head pointer |
113 | */ |
114 | static inline void |
115 | plist_head_init(struct plist_head *head) |
116 | { |
117 | INIT_LIST_HEAD(list: &head->node_list); |
118 | } |
119 | |
120 | /** |
121 | * plist_node_init - Dynamic struct plist_node initializer |
122 | * @node: &struct plist_node pointer |
123 | * @prio: initial node priority |
124 | */ |
125 | static inline void plist_node_init(struct plist_node *node, int prio) |
126 | { |
127 | node->prio = prio; |
128 | INIT_LIST_HEAD(list: &node->prio_list); |
129 | INIT_LIST_HEAD(list: &node->node_list); |
130 | } |
131 | |
132 | extern void plist_add(struct plist_node *node, struct plist_head *head); |
133 | extern void plist_del(struct plist_node *node, struct plist_head *head); |
134 | |
135 | extern void plist_requeue(struct plist_node *node, struct plist_head *head); |
136 | |
137 | /** |
138 | * plist_for_each - iterate over the plist |
139 | * @pos: the type * to use as a loop counter |
140 | * @head: the head for your list |
141 | */ |
142 | #define plist_for_each(pos, head) \ |
143 | list_for_each_entry(pos, &(head)->node_list, node_list) |
144 | |
145 | /** |
146 | * plist_for_each_continue - continue iteration over the plist |
147 | * @pos: the type * to use as a loop cursor |
148 | * @head: the head for your list |
149 | * |
150 | * Continue to iterate over plist, continuing after the current position. |
151 | */ |
152 | #define plist_for_each_continue(pos, head) \ |
153 | list_for_each_entry_continue(pos, &(head)->node_list, node_list) |
154 | |
155 | /** |
156 | * plist_for_each_safe - iterate safely over a plist of given type |
157 | * @pos: the type * to use as a loop counter |
158 | * @n: another type * to use as temporary storage |
159 | * @head: the head for your list |
160 | * |
161 | * Iterate over a plist of given type, safe against removal of list entry. |
162 | */ |
163 | #define plist_for_each_safe(pos, n, head) \ |
164 | list_for_each_entry_safe(pos, n, &(head)->node_list, node_list) |
165 | |
166 | /** |
167 | * plist_for_each_entry - iterate over list of given type |
168 | * @pos: the type * to use as a loop counter |
169 | * @head: the head for your list |
170 | * @mem: the name of the list_head within the struct |
171 | */ |
172 | #define plist_for_each_entry(pos, head, mem) \ |
173 | list_for_each_entry(pos, &(head)->node_list, mem.node_list) |
174 | |
175 | /** |
176 | * plist_for_each_entry_continue - continue iteration over list of given type |
177 | * @pos: the type * to use as a loop cursor |
178 | * @head: the head for your list |
179 | * @m: the name of the list_head within the struct |
180 | * |
181 | * Continue to iterate over list of given type, continuing after |
182 | * the current position. |
183 | */ |
184 | #define plist_for_each_entry_continue(pos, head, m) \ |
185 | list_for_each_entry_continue(pos, &(head)->node_list, m.node_list) |
186 | |
187 | /** |
188 | * plist_for_each_entry_safe - iterate safely over list of given type |
189 | * @pos: the type * to use as a loop counter |
190 | * @n: another type * to use as temporary storage |
191 | * @head: the head for your list |
192 | * @m: the name of the list_head within the struct |
193 | * |
194 | * Iterate over list of given type, safe against removal of list entry. |
195 | */ |
196 | #define plist_for_each_entry_safe(pos, n, head, m) \ |
197 | list_for_each_entry_safe(pos, n, &(head)->node_list, m.node_list) |
198 | |
199 | /** |
200 | * plist_head_empty - return !0 if a plist_head is empty |
201 | * @head: &struct plist_head pointer |
202 | */ |
203 | static inline int plist_head_empty(const struct plist_head *head) |
204 | { |
205 | return list_empty(head: &head->node_list); |
206 | } |
207 | |
208 | /** |
209 | * plist_node_empty - return !0 if plist_node is not on a list |
210 | * @node: &struct plist_node pointer |
211 | */ |
212 | static inline int plist_node_empty(const struct plist_node *node) |
213 | { |
214 | return list_empty(head: &node->node_list); |
215 | } |
216 | |
217 | /* All functions below assume the plist_head is not empty. */ |
218 | |
219 | /** |
220 | * plist_first_entry - get the struct for the first entry |
221 | * @head: the &struct plist_head pointer |
222 | * @type: the type of the struct this is embedded in |
223 | * @member: the name of the list_head within the struct |
224 | */ |
225 | #ifdef CONFIG_DEBUG_PLIST |
226 | # define plist_first_entry(head, type, member) \ |
227 | ({ \ |
228 | WARN_ON(plist_head_empty(head)); \ |
229 | container_of(plist_first(head), type, member); \ |
230 | }) |
231 | #else |
232 | # define plist_first_entry(head, type, member) \ |
233 | container_of(plist_first(head), type, member) |
234 | #endif |
235 | |
236 | /** |
237 | * plist_last_entry - get the struct for the last entry |
238 | * @head: the &struct plist_head pointer |
239 | * @type: the type of the struct this is embedded in |
240 | * @member: the name of the list_head within the struct |
241 | */ |
242 | #ifdef CONFIG_DEBUG_PLIST |
243 | # define plist_last_entry(head, type, member) \ |
244 | ({ \ |
245 | WARN_ON(plist_head_empty(head)); \ |
246 | container_of(plist_last(head), type, member); \ |
247 | }) |
248 | #else |
249 | # define plist_last_entry(head, type, member) \ |
250 | container_of(plist_last(head), type, member) |
251 | #endif |
252 | |
253 | /** |
254 | * plist_next - get the next entry in list |
255 | * @pos: the type * to cursor |
256 | */ |
257 | #define plist_next(pos) \ |
258 | list_next_entry(pos, node_list) |
259 | |
260 | /** |
261 | * plist_prev - get the prev entry in list |
262 | * @pos: the type * to cursor |
263 | */ |
264 | #define plist_prev(pos) \ |
265 | list_prev_entry(pos, node_list) |
266 | |
267 | /** |
268 | * plist_first - return the first node (and thus, highest priority) |
269 | * @head: the &struct plist_head pointer |
270 | * |
271 | * Assumes the plist is _not_ empty. |
272 | */ |
273 | static inline struct plist_node *plist_first(const struct plist_head *head) |
274 | { |
275 | return list_entry(head->node_list.next, |
276 | struct plist_node, node_list); |
277 | } |
278 | |
279 | /** |
280 | * plist_last - return the last node (and thus, lowest priority) |
281 | * @head: the &struct plist_head pointer |
282 | * |
283 | * Assumes the plist is _not_ empty. |
284 | */ |
285 | static inline struct plist_node *plist_last(const struct plist_head *head) |
286 | { |
287 | return list_entry(head->node_list.prev, |
288 | struct plist_node, node_list); |
289 | } |
290 | |
291 | #endif |
292 | |