diff options
Diffstat (limited to 'include/linux/plist.h')
-rw-r--r-- | include/linux/plist.h | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/include/linux/plist.h b/include/linux/plist.h new file mode 100644 index 000000000000..b95818a037ad --- /dev/null +++ b/include/linux/plist.h | |||
@@ -0,0 +1,248 @@ | |||
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 | * |HEAD | | ||
35 | * | | | ||
36 | * |prio_list.prev|<------------------------------------| | ||
37 | * |prio_list.next|<->|pl|<->|pl|<--------------->|pl|<-| | ||
38 | * |10 | |10| |21| |21| |21| |40| (prio) | ||
39 | * | | | | | | | | | | | | | ||
40 | * | | | | | | | | | | | | | ||
41 | * |node_list.next|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-| | ||
42 | * |node_list.prev|<------------------------------------| | ||
43 | * | ||
44 | * The nodes on the prio_list list are sorted by priority to simplify | ||
45 | * the insertion of new nodes. There are no nodes with duplicate | ||
46 | * priorites on the list. | ||
47 | * | ||
48 | * The nodes on the node_list is ordered by priority and can contain | ||
49 | * entries which have the same priority. Those entries are ordered | ||
50 | * FIFO | ||
51 | * | ||
52 | * Addition means: look for the prio_list node in the prio_list | ||
53 | * for the priority of the node and insert it before the node_list | ||
54 | * entry of the next prio_list node. If it is the first node of | ||
55 | * that priority, add it to the prio_list in the right position and | ||
56 | * insert it into the serialized node_list list | ||
57 | * | ||
58 | * Removal means remove it from the node_list and remove it from | ||
59 | * the prio_list if the node_list list_head is non empty. In case | ||
60 | * of removal from the prio_list it must be checked whether other | ||
61 | * entries of the same priority are on the list or not. If there | ||
62 | * is another entry of the same priority then this entry has to | ||
63 | * replace the removed entry on the prio_list. If the entry which | ||
64 | * is removed is the only entry of this priority then a simple | ||
65 | * remove from both list is sufficient. | ||
66 | * | ||
67 | * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX | ||
68 | * is lowest priority. | ||
69 | * | ||
70 | * No locking is done, up to the caller. | ||
71 | * | ||
72 | */ | ||
73 | #ifndef _LINUX_PLIST_H_ | ||
74 | #define _LINUX_PLIST_H_ | ||
75 | |||
76 | #include <linux/kernel.h> | ||
77 | #include <linux/list.h> | ||
78 | #include <linux/spinlock_types.h> | ||
79 | |||
80 | struct plist_head { | ||
81 | struct list_head prio_list; | ||
82 | struct list_head node_list; | ||
83 | #ifdef CONFIG_DEBUG_PI_LIST | ||
84 | spinlock_t *lock; | ||
85 | #endif | ||
86 | }; | ||
87 | |||
88 | struct plist_node { | ||
89 | int prio; | ||
90 | struct plist_head plist; | ||
91 | }; | ||
92 | |||
93 | #ifdef CONFIG_DEBUG_PI_LIST | ||
94 | # define PLIST_HEAD_LOCK_INIT(_lock) .lock = _lock | ||
95 | #else | ||
96 | # define PLIST_HEAD_LOCK_INIT(_lock) | ||
97 | #endif | ||
98 | |||
99 | /** | ||
100 | * #PLIST_HEAD_INIT - static struct plist_head initializer | ||
101 | * | ||
102 | * @head: struct plist_head variable name | ||
103 | */ | ||
104 | #define PLIST_HEAD_INIT(head, _lock) \ | ||
105 | { \ | ||
106 | .prio_list = LIST_HEAD_INIT((head).prio_list), \ | ||
107 | .node_list = LIST_HEAD_INIT((head).node_list), \ | ||
108 | PLIST_HEAD_LOCK_INIT(&(_lock)) \ | ||
109 | } | ||
110 | |||
111 | /** | ||
112 | * #PLIST_NODE_INIT - static struct plist_node initializer | ||
113 | * | ||
114 | * @node: struct plist_node variable name | ||
115 | * @__prio: initial node priority | ||
116 | */ | ||
117 | #define PLIST_NODE_INIT(node, __prio) \ | ||
118 | { \ | ||
119 | .prio = (__prio), \ | ||
120 | .plist = PLIST_HEAD_INIT((node).plist, NULL), \ | ||
121 | } | ||
122 | |||
123 | /** | ||
124 | * plist_head_init - dynamic struct plist_head initializer | ||
125 | * | ||
126 | * @head: &struct plist_head pointer | ||
127 | */ | ||
128 | static inline void | ||
129 | plist_head_init(struct plist_head *head, spinlock_t *lock) | ||
130 | { | ||
131 | INIT_LIST_HEAD(&head->prio_list); | ||
132 | INIT_LIST_HEAD(&head->node_list); | ||
133 | #ifdef CONFIG_DEBUG_PI_LIST | ||
134 | head->lock = lock; | ||
135 | #endif | ||
136 | } | ||
137 | |||
138 | /** | ||
139 | * plist_node_init - Dynamic struct plist_node initializer | ||
140 | * | ||
141 | * @node: &struct plist_node pointer | ||
142 | * @prio: initial node priority | ||
143 | */ | ||
144 | static inline void plist_node_init(struct plist_node *node, int prio) | ||
145 | { | ||
146 | node->prio = prio; | ||
147 | plist_head_init(&node->plist, NULL); | ||
148 | } | ||
149 | |||
150 | extern void plist_add(struct plist_node *node, struct plist_head *head); | ||
151 | extern void plist_del(struct plist_node *node, struct plist_head *head); | ||
152 | |||
153 | /** | ||
154 | * plist_for_each - iterate over the plist | ||
155 | * | ||
156 | * @pos1: the type * to use as a loop counter. | ||
157 | * @head: the head for your list. | ||
158 | */ | ||
159 | #define plist_for_each(pos, head) \ | ||
160 | list_for_each_entry(pos, &(head)->node_list, plist.node_list) | ||
161 | |||
162 | /** | ||
163 | * plist_for_each_entry_safe - iterate over a plist of given type safe | ||
164 | * against removal of list entry | ||
165 | * | ||
166 | * @pos1: the type * to use as a loop counter. | ||
167 | * @n1: another type * to use as temporary storage | ||
168 | * @head: the head for your list. | ||
169 | */ | ||
170 | #define plist_for_each_safe(pos, n, head) \ | ||
171 | list_for_each_entry_safe(pos, n, &(head)->node_list, plist.node_list) | ||
172 | |||
173 | /** | ||
174 | * plist_for_each_entry - iterate over list of given type | ||
175 | * | ||
176 | * @pos: the type * to use as a loop counter. | ||
177 | * @head: the head for your list. | ||
178 | * @member: the name of the list_struct within the struct. | ||
179 | */ | ||
180 | #define plist_for_each_entry(pos, head, mem) \ | ||
181 | list_for_each_entry(pos, &(head)->node_list, mem.plist.node_list) | ||
182 | |||
183 | /** | ||
184 | * plist_for_each_entry_safe - iterate over list of given type safe against | ||
185 | * removal of list entry | ||
186 | * | ||
187 | * @pos: the type * to use as a loop counter. | ||
188 | * @n: another type * to use as temporary storage | ||
189 | * @head: the head for your list. | ||
190 | * @m: the name of the list_struct within the struct. | ||
191 | */ | ||
192 | #define plist_for_each_entry_safe(pos, n, head, m) \ | ||
193 | list_for_each_entry_safe(pos, n, &(head)->node_list, m.plist.node_list) | ||
194 | |||
195 | /** | ||
196 | * plist_head_empty - return !0 if a plist_head is empty | ||
197 | * | ||
198 | * @head: &struct plist_head pointer | ||
199 | */ | ||
200 | static inline int plist_head_empty(const struct plist_head *head) | ||
201 | { | ||
202 | return list_empty(&head->node_list); | ||
203 | } | ||
204 | |||
205 | /** | ||
206 | * plist_node_empty - return !0 if plist_node is not on a list | ||
207 | * | ||
208 | * @node: &struct plist_node pointer | ||
209 | */ | ||
210 | static inline int plist_node_empty(const struct plist_node *node) | ||
211 | { | ||
212 | return plist_head_empty(&node->plist); | ||
213 | } | ||
214 | |||
215 | /* All functions below assume the plist_head is not empty. */ | ||
216 | |||
217 | /** | ||
218 | * plist_first_entry - get the struct for the first entry | ||
219 | * | ||
220 | * @ptr: the &struct plist_head pointer. | ||
221 | * @type: the type of the struct this is embedded in. | ||
222 | * @member: the name of the list_struct within the struct. | ||
223 | */ | ||
224 | #ifdef CONFIG_DEBUG_PI_LIST | ||
225 | # define plist_first_entry(head, type, member) \ | ||
226 | ({ \ | ||
227 | WARN_ON(plist_head_empty(head)); \ | ||
228 | container_of(plist_first(head), type, member); \ | ||
229 | }) | ||
230 | #else | ||
231 | # define plist_first_entry(head, type, member) \ | ||
232 | container_of(plist_first(head), type, member) | ||
233 | #endif | ||
234 | |||
235 | /** | ||
236 | * plist_first - return the first node (and thus, highest priority) | ||
237 | * | ||
238 | * @head: the &struct plist_head pointer | ||
239 | * | ||
240 | * Assumes the plist is _not_ empty. | ||
241 | */ | ||
242 | static inline struct plist_node* plist_first(const struct plist_head *head) | ||
243 | { | ||
244 | return list_entry(head->node_list.next, | ||
245 | struct plist_node, plist.node_list); | ||
246 | } | ||
247 | |||
248 | #endif | ||