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