Commit | Line | Data |
---|---|---|
a04d0423 BS |
1 | /* |
2 | * Copyright © 2010 Intel Corporation | |
3 | * Copyright © 2010 Francisco Jerez <currojerez@riseup.net> | |
4 | * | |
5 | * Permission is hereby granted, free of charge, to any person obtaining a | |
6 | * copy of this software and associated documentation files (the "Software"), | |
7 | * to deal in the Software without restriction, including without limitation | |
8 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, | |
9 | * and/or sell copies of the Software, and to permit persons to whom the | |
10 | * Software is furnished to do so, subject to the following conditions: | |
11 | * | |
12 | * The above copyright notice and this permission notice (including the next | |
13 | * paragraph) shall be included in all copies or substantial portions of the | |
14 | * Software. | |
15 | * | |
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
17 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
18 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
19 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
20 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |
21 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS | |
22 | * IN THE SOFTWARE. | |
23 | * | |
24 | */ | |
25 | ||
26 | /* Modified by Ben Skeggs <bskeggs@redhat.com> to match kernel list APIs */ | |
27 | ||
28 | #ifndef _XORG_LIST_H_ | |
29 | #define _XORG_LIST_H_ | |
30 | ||
31 | /** | |
32 | * @file Classic doubly-link circular list implementation. | |
33 | * For real usage examples of the linked list, see the file test/list.c | |
34 | * | |
35 | * Example: | |
36 | * We need to keep a list of struct foo in the parent struct bar, i.e. what | |
37 | * we want is something like this. | |
38 | * | |
39 | * struct bar { | |
40 | * ... | |
41 | * struct foo *list_of_foos; -----> struct foo {}, struct foo {}, struct foo{} | |
42 | * ... | |
43 | * } | |
44 | * | |
45 | * We need one list head in bar and a list element in all list_of_foos (both are of | |
46 | * data type 'struct list_head'). | |
47 | * | |
48 | * struct bar { | |
49 | * ... | |
50 | * struct list_head list_of_foos; | |
51 | * ... | |
52 | * } | |
53 | * | |
54 | * struct foo { | |
55 | * ... | |
56 | * struct list_head entry; | |
57 | * ... | |
58 | * } | |
59 | * | |
60 | * Now we initialize the list head: | |
61 | * | |
62 | * struct bar bar; | |
63 | * ... | |
64 | * INIT_LIST_HEAD(&bar.list_of_foos); | |
65 | * | |
66 | * Then we create the first element and add it to this list: | |
67 | * | |
68 | * struct foo *foo = malloc(...); | |
69 | * .... | |
70 | * list_add(&foo->entry, &bar.list_of_foos); | |
71 | * | |
72 | * Repeat the above for each element you want to add to the list. Deleting | |
73 | * works with the element itself. | |
74 | * list_del(&foo->entry); | |
75 | * free(foo); | |
76 | * | |
77 | * Note: calling list_del(&bar.list_of_foos) will set bar.list_of_foos to an empty | |
78 | * list again. | |
79 | * | |
80 | * Looping through the list requires a 'struct foo' as iterator and the | |
81 | * name of the field the subnodes use. | |
82 | * | |
83 | * struct foo *iterator; | |
84 | * list_for_each_entry(iterator, &bar.list_of_foos, entry) { | |
85 | * if (iterator->something == ...) | |
86 | * ... | |
87 | * } | |
88 | * | |
89 | * Note: You must not call list_del() on the iterator if you continue the | |
90 | * loop. You need to run the safe for-each loop instead: | |
91 | * | |
92 | * struct foo *iterator, *next; | |
93 | * list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) { | |
94 | * if (...) | |
95 | * list_del(&iterator->entry); | |
96 | * } | |
97 | * | |
98 | */ | |
99 | ||
100 | /** | |
101 | * The linkage struct for list nodes. This struct must be part of your | |
102 | * to-be-linked struct. struct list_head is required for both the head of the | |
103 | * list and for each list node. | |
104 | * | |
105 | * Position and name of the struct list_head field is irrelevant. | |
106 | * There are no requirements that elements of a list are of the same type. | |
107 | * There are no requirements for a list head, any struct list_head can be a list | |
108 | * head. | |
109 | */ | |
110 | struct list_head { | |
111 | struct list_head *next, *prev; | |
112 | }; | |
113 | ||
114 | /** | |
115 | * Initialize the list as an empty list. | |
116 | * | |
117 | * Example: | |
118 | * INIT_LIST_HEAD(&bar->list_of_foos); | |
119 | * | |
120 | * @param The list to initialized. | |
121 | */ | |
122 | #define LIST_HEAD_INIT(name) { &(name), &(name) } | |
123 | ||
124 | #define LIST_HEAD(name) \ | |
125 | struct list_head name = LIST_HEAD_INIT(name) | |
126 | ||
127 | static inline void | |
128 | INIT_LIST_HEAD(struct list_head *list) | |
129 | { | |
130 | list->next = list->prev = list; | |
131 | } | |
132 | ||
133 | static inline void | |
134 | __list_add(struct list_head *entry, | |
135 | struct list_head *prev, struct list_head *next) | |
136 | { | |
137 | next->prev = entry; | |
138 | entry->next = next; | |
139 | entry->prev = prev; | |
140 | prev->next = entry; | |
141 | } | |
142 | ||
143 | /** | |
144 | * Insert a new element after the given list head. The new element does not | |
145 | * need to be initialised as empty list. | |
146 | * The list changes from: | |
147 | * head → some element → ... | |
148 | * to | |
149 | * head → new element → older element → ... | |
150 | * | |
151 | * Example: | |
152 | * struct foo *newfoo = malloc(...); | |
153 | * list_add(&newfoo->entry, &bar->list_of_foos); | |
154 | * | |
155 | * @param entry The new element to prepend to the list. | |
156 | * @param head The existing list. | |
157 | */ | |
158 | static inline void | |
159 | list_add(struct list_head *entry, struct list_head *head) | |
160 | { | |
161 | __list_add(entry, head, head->next); | |
162 | } | |
163 | ||
164 | /** | |
165 | * Append a new element to the end of the list given with this list head. | |
166 | * | |
167 | * The list changes from: | |
168 | * head → some element → ... → lastelement | |
169 | * to | |
170 | * head → some element → ... → lastelement → new element | |
171 | * | |
172 | * Example: | |
173 | * struct foo *newfoo = malloc(...); | |
174 | * list_add_tail(&newfoo->entry, &bar->list_of_foos); | |
175 | * | |
176 | * @param entry The new element to prepend to the list. | |
177 | * @param head The existing list. | |
178 | */ | |
179 | static inline void | |
180 | list_add_tail(struct list_head *entry, struct list_head *head) | |
181 | { | |
182 | __list_add(entry, head->prev, head); | |
183 | } | |
184 | ||
185 | static inline void | |
186 | __list_del(struct list_head *prev, struct list_head *next) | |
187 | { | |
188 | next->prev = prev; | |
189 | prev->next = next; | |
190 | } | |
191 | ||
192 | /** | |
193 | * Remove the element from the list it is in. Using this function will reset | |
194 | * the pointers to/from this element so it is removed from the list. It does | |
195 | * NOT free the element itself or manipulate it otherwise. | |
196 | * | |
197 | * Using list_del on a pure list head (like in the example at the top of | |
198 | * this file) will NOT remove the first element from | |
199 | * the list but rather reset the list as empty list. | |
200 | * | |
201 | * Example: | |
202 | * list_del(&foo->entry); | |
203 | * | |
204 | * @param entry The element to remove. | |
205 | */ | |
206 | static inline void | |
207 | list_del(struct list_head *entry) | |
208 | { | |
209 | __list_del(entry->prev, entry->next); | |
210 | } | |
211 | ||
212 | static inline void | |
213 | list_del_init(struct list_head *entry) | |
214 | { | |
215 | __list_del(entry->prev, entry->next); | |
216 | INIT_LIST_HEAD(entry); | |
217 | } | |
218 | ||
219 | static inline void list_move_tail(struct list_head *list, | |
220 | struct list_head *head) | |
221 | { | |
222 | __list_del(list->prev, list->next); | |
223 | list_add_tail(list, head); | |
224 | } | |
225 | ||
226 | /** | |
227 | * Check if the list is empty. | |
228 | * | |
229 | * Example: | |
230 | * list_empty(&bar->list_of_foos); | |
231 | * | |
232 | * @return True if the list contains one or more elements or False otherwise. | |
233 | */ | |
234 | static inline bool | |
235 | list_empty(struct list_head *head) | |
236 | { | |
237 | return head->next == head; | |
238 | } | |
239 | ||
240 | /** | |
241 | * Returns a pointer to the container of this list element. | |
242 | * | |
243 | * Example: | |
244 | * struct foo* f; | |
245 | * f = container_of(&foo->entry, struct foo, entry); | |
246 | * assert(f == foo); | |
247 | * | |
248 | * @param ptr Pointer to the struct list_head. | |
249 | * @param type Data type of the list element. | |
250 | * @param member Member name of the struct list_head field in the list element. | |
251 | * @return A pointer to the data struct containing the list head. | |
252 | */ | |
253 | #ifndef container_of | |
254 | #define container_of(ptr, type, member) \ | |
255 | (type *)((char *)(ptr) - (char *) &((type *)0)->member) | |
256 | #endif | |
257 | ||
258 | /** | |
259 | * Alias of container_of | |
260 | */ | |
261 | #define list_entry(ptr, type, member) \ | |
262 | container_of(ptr, type, member) | |
263 | ||
264 | /** | |
265 | * Retrieve the first list entry for the given list pointer. | |
266 | * | |
267 | * Example: | |
268 | * struct foo *first; | |
269 | * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos); | |
270 | * | |
271 | * @param ptr The list head | |
272 | * @param type Data type of the list element to retrieve | |
273 | * @param member Member name of the struct list_head field in the list element. | |
274 | * @return A pointer to the first list element. | |
275 | */ | |
276 | #define list_first_entry(ptr, type, member) \ | |
277 | list_entry((ptr)->next, type, member) | |
278 | ||
279 | /** | |
280 | * Retrieve the last list entry for the given listpointer. | |
281 | * | |
282 | * Example: | |
283 | * struct foo *first; | |
284 | * first = list_last_entry(&bar->list_of_foos, struct foo, list_of_foos); | |
285 | * | |
286 | * @param ptr The list head | |
287 | * @param type Data type of the list element to retrieve | |
288 | * @param member Member name of the struct list_head field in the list element. | |
289 | * @return A pointer to the last list element. | |
290 | */ | |
291 | #define list_last_entry(ptr, type, member) \ | |
292 | list_entry((ptr)->prev, type, member) | |
293 | ||
294 | #define __container_of(ptr, sample, member) \ | |
295 | (void *)container_of((ptr), typeof(*(sample)), member) | |
296 | ||
297 | /** | |
298 | * Loop through the list given by head and set pos to struct in the list. | |
299 | * | |
300 | * Example: | |
301 | * struct foo *iterator; | |
302 | * list_for_each_entry(iterator, &bar->list_of_foos, entry) { | |
303 | * [modify iterator] | |
304 | * } | |
305 | * | |
306 | * This macro is not safe for node deletion. Use list_for_each_entry_safe | |
307 | * instead. | |
308 | * | |
309 | * @param pos Iterator variable of the type of the list elements. | |
310 | * @param head List head | |
311 | * @param member Member name of the struct list_head in the list elements. | |
312 | * | |
313 | */ | |
314 | #define list_for_each_entry(pos, head, member) \ | |
315 | for (pos = __container_of((head)->next, pos, member); \ | |
316 | &pos->member != (head); \ | |
317 | pos = __container_of(pos->member.next, pos, member)) | |
318 | ||
319 | /** | |
320 | * Loop through the list, keeping a backup pointer to the element. This | |
321 | * macro allows for the deletion of a list element while looping through the | |
322 | * list. | |
323 | * | |
324 | * See list_for_each_entry for more details. | |
325 | */ | |
326 | #define list_for_each_entry_safe(pos, tmp, head, member) \ | |
327 | for (pos = __container_of((head)->next, pos, member), \ | |
328 | tmp = __container_of(pos->member.next, pos, member); \ | |
329 | &pos->member != (head); \ | |
330 | pos = tmp, tmp = __container_of(pos->member.next, tmp, member)) | |
331 | ||
332 | ||
333 | #define list_for_each_entry_reverse(pos, head, member) \ | |
334 | for (pos = __container_of((head)->prev, pos, member); \ | |
335 | &pos->member != (head); \ | |
336 | pos = __container_of(pos->member.prev, pos, member)) | |
337 | ||
338 | #define list_for_each_entry_continue(pos, head, member) \ | |
339 | for (pos = __container_of(pos->member.next, pos, member); \ | |
340 | &pos->member != (head); \ | |
341 | pos = __container_of(pos->member.next, pos, member)) | |
342 | ||
343 | #define list_for_each_entry_continue_reverse(pos, head, member) \ | |
344 | for (pos = __container_of(pos->member.prev, pos, member); \ | |
345 | &pos->member != (head); \ | |
346 | pos = __container_of(pos->member.prev, pos, member)) | |
347 | ||
348 | #define list_for_each_entry_from(pos, head, member) \ | |
349 | for (; \ | |
350 | &pos->member != (head); \ | |
351 | pos = __container_of(pos->member.next, pos, member)) | |
352 | ||
353 | #endif |