Commit | Line | Data |
---|---|---|
a09e091a JB |
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 | #ifndef _XORG_LIST_H_ | |
27 | #define _XORG_LIST_H_ | |
28 | ||
29 | #include <stddef.h> /* offsetof() */ | |
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 xorg_list'). | |
47 | * | |
48 | * struct bar { | |
49 | * ... | |
50 | * struct xorg_list list_of_foos; | |
51 | * ... | |
52 | * } | |
53 | * | |
54 | * struct foo { | |
55 | * ... | |
56 | * struct xorg_list entry; | |
57 | * ... | |
58 | * } | |
59 | * | |
60 | * Now we initialize the list head: | |
61 | * | |
62 | * struct bar bar; | |
63 | * ... | |
64 | * xorg_list_init(&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 | * xorg_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 | * xorg_list_del(&foo->entry); | |
75 | * free(foo); | |
76 | * | |
77 | * Note: calling xorg_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 | * xorg_list_for_each_entry(iterator, &bar.list_of_foos, entry) { | |
85 | * if (iterator->something == ...) | |
86 | * ... | |
87 | * } | |
88 | * | |
89 | * Note: You must not call xorg_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 | * xorg_list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) { | |
94 | * if (...) | |
95 | * xorg_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 xorg_list is required for both the head of the | |
103 | * list and for each list node. | |
104 | * | |
105 | * Position and name of the struct xorg_list 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 xorg_list can be a list | |
108 | * head. | |
109 | */ | |
110 | struct xorg_list { | |
111 | struct xorg_list *next, *prev; | |
112 | }; | |
113 | ||
114 | /** | |
115 | * Initialize the list as an empty list. | |
116 | * | |
117 | * Example: | |
118 | * xorg_list_init(&bar->list_of_foos); | |
119 | * | |
120 | * @param The list to initialized. | |
121 | */ | |
122 | static inline void | |
123 | xorg_list_init(struct xorg_list *list) | |
124 | { | |
125 | list->next = list->prev = list; | |
126 | } | |
127 | ||
128 | static inline void | |
129 | __xorg_list_add(struct xorg_list *entry, | |
130 | struct xorg_list *prev, struct xorg_list *next) | |
131 | { | |
132 | next->prev = entry; | |
133 | entry->next = next; | |
134 | entry->prev = prev; | |
135 | prev->next = entry; | |
136 | } | |
137 | ||
138 | /** | |
139 | * Insert a new element after the given list head. The new element does not | |
140 | * need to be initialised as empty list. | |
141 | * The list changes from: | |
142 | * head → some element → ... | |
143 | * to | |
144 | * head → new element → older element → ... | |
145 | * | |
146 | * Example: | |
147 | * struct foo *newfoo = malloc(...); | |
148 | * xorg_list_add(&newfoo->entry, &bar->list_of_foos); | |
149 | * | |
150 | * @param entry The new element to prepend to the list. | |
151 | * @param head The existing list. | |
152 | */ | |
153 | static inline void | |
154 | xorg_list_add(struct xorg_list *entry, struct xorg_list *head) | |
155 | { | |
156 | __xorg_list_add(entry, head, head->next); | |
157 | } | |
158 | ||
159 | /** | |
160 | * Append a new element to the end of the list given with this list head. | |
161 | * | |
162 | * The list changes from: | |
163 | * head → some element → ... → lastelement | |
164 | * to | |
165 | * head → some element → ... → lastelement → new element | |
166 | * | |
167 | * Example: | |
168 | * struct foo *newfoo = malloc(...); | |
169 | * xorg_list_append(&newfoo->entry, &bar->list_of_foos); | |
170 | * | |
171 | * @param entry The new element to prepend to the list. | |
172 | * @param head The existing list. | |
173 | */ | |
174 | static inline void | |
175 | xorg_list_append(struct xorg_list *entry, struct xorg_list *head) | |
176 | { | |
177 | __xorg_list_add(entry, head->prev, head); | |
178 | } | |
179 | ||
180 | static inline void | |
181 | __xorg_list_del(struct xorg_list *prev, struct xorg_list *next) | |
182 | { | |
183 | next->prev = prev; | |
184 | prev->next = next; | |
185 | } | |
186 | ||
187 | /** | |
188 | * Remove the element from the list it is in. Using this function will reset | |
189 | * the pointers to/from this element so it is removed from the list. It does | |
190 | * NOT free the element itself or manipulate it otherwise. | |
191 | * | |
192 | * Using xorg_list_del on a pure list head (like in the example at the top of | |
193 | * this file) will NOT remove the first element from | |
194 | * the list but rather reset the list as empty list. | |
195 | * | |
196 | * Example: | |
197 | * xorg_list_del(&foo->entry); | |
198 | * | |
199 | * @param entry The element to remove. | |
200 | */ | |
201 | static inline void | |
202 | xorg_list_del(struct xorg_list *entry) | |
203 | { | |
204 | __xorg_list_del(entry->prev, entry->next); | |
205 | xorg_list_init(entry); | |
206 | } | |
207 | ||
208 | /** | |
209 | * Check if the list is empty. | |
210 | * | |
211 | * Example: | |
212 | * xorg_list_is_empty(&bar->list_of_foos); | |
213 | * | |
214 | * @return True if the list contains one or more elements or False otherwise. | |
215 | */ | |
216 | static inline int | |
217 | xorg_list_is_empty(struct xorg_list *head) | |
218 | { | |
219 | return head->next == head; | |
220 | } | |
221 | ||
222 | /** | |
223 | * Returns a pointer to the container of this list element. | |
224 | * | |
225 | * Example: | |
226 | * struct foo* f; | |
227 | * f = container_of(&foo->entry, struct foo, entry); | |
228 | * assert(f == foo); | |
229 | * | |
230 | * @param ptr Pointer to the struct xorg_list. | |
231 | * @param type Data type of the list element. | |
232 | * @param member Member name of the struct xorg_list field in the list element. | |
233 | * @return A pointer to the data struct containing the list head. | |
234 | */ | |
235 | #ifndef container_of | |
236 | #define container_of(ptr, type, member) \ | |
237 | (type *)((char *)(ptr) - offsetof(type, member)) | |
238 | #endif | |
239 | ||
240 | /** | |
241 | * Alias of container_of | |
242 | */ | |
243 | #define xorg_list_entry(ptr, type, member) \ | |
244 | container_of(ptr, type, member) | |
245 | ||
246 | /** | |
247 | * Retrieve the first list entry for the given list pointer. | |
248 | * | |
249 | * Example: | |
250 | * struct foo *first; | |
251 | * first = xorg_list_first_entry(&bar->list_of_foos, struct foo, list_of_foos); | |
252 | * | |
253 | * @param ptr The list head | |
254 | * @param type Data type of the list element to retrieve | |
255 | * @param member Member name of the struct xorg_list field in the list element. | |
256 | * @return A pointer to the first list element. | |
257 | */ | |
258 | #define xorg_list_first_entry(ptr, type, member) \ | |
259 | xorg_list_entry((ptr)->next, type, member) | |
260 | ||
261 | /** | |
262 | * Retrieve the last list entry for the given listpointer. | |
263 | * | |
264 | * Example: | |
265 | * struct foo *first; | |
266 | * first = xorg_list_last_entry(&bar->list_of_foos, struct foo, list_of_foos); | |
267 | * | |
268 | * @param ptr The list head | |
269 | * @param type Data type of the list element to retrieve | |
270 | * @param member Member name of the struct xorg_list field in the list element. | |
271 | * @return A pointer to the last list element. | |
272 | */ | |
273 | #define xorg_list_last_entry(ptr, type, member) \ | |
274 | xorg_list_entry((ptr)->prev, type, member) | |
275 | ||
276 | #ifdef HAVE_TYPEOF | |
277 | #define __container_of(ptr, sample, member) \ | |
278 | container_of(ptr, typeof(*sample), member) | |
279 | #else | |
280 | /* This implementation of __container_of has undefined behavior according | |
281 | * to the C standard, but it works in many cases. If your compiler doesn't | |
282 | * support typeof() and fails with this implementation, please try a newer | |
283 | * compiler. | |
284 | */ | |
285 | #define __container_of(ptr, sample, member) \ | |
286 | (void *)((char *)(ptr) \ | |
287 | - ((char *)&(sample)->member - (char *)(sample))) | |
288 | #endif | |
289 | ||
290 | /** | |
291 | * Loop through the list given by head and set pos to struct in the list. | |
292 | * | |
293 | * Example: | |
294 | * struct foo *iterator; | |
295 | * xorg_list_for_each_entry(iterator, &bar->list_of_foos, entry) { | |
296 | * [modify iterator] | |
297 | * } | |
298 | * | |
299 | * This macro is not safe for node deletion. Use xorg_list_for_each_entry_safe | |
300 | * instead. | |
301 | * | |
302 | * @param pos Iterator variable of the type of the list elements. | |
303 | * @param head List head | |
304 | * @param member Member name of the struct xorg_list in the list elements. | |
305 | * | |
306 | */ | |
307 | #define xorg_list_for_each_entry(pos, head, member) \ | |
308 | for (pos = __container_of((head)->next, pos, member); \ | |
309 | &pos->member != (head); \ | |
310 | pos = __container_of(pos->member.next, pos, member)) | |
311 | ||
312 | /** | |
313 | * Loop through the list, keeping a backup pointer to the element. This | |
314 | * macro allows for the deletion of a list element while looping through the | |
315 | * list. | |
316 | * | |
317 | * See xorg_list_for_each_entry for more details. | |
318 | */ | |
319 | #define xorg_list_for_each_entry_safe(pos, tmp, head, member) \ | |
320 | for (pos = __container_of((head)->next, pos, member), \ | |
321 | tmp = __container_of(pos->member.next, pos, member); \ | |
322 | &pos->member != (head); \ | |
323 | pos = tmp, tmp = __container_of(pos->member.next, tmp, member)) | |
324 | ||
325 | /* NULL-Terminated List Interface | |
326 | * | |
327 | * The interface below does _not_ use the struct xorg_list as described above. | |
328 | * It is mainly for legacy structures that cannot easily be switched to | |
329 | * struct xorg_list. | |
330 | * | |
331 | * This interface is for structs like | |
332 | * struct foo { | |
333 | * [...] | |
334 | * struct foo *next; | |
335 | * [...] | |
336 | * }; | |
337 | * | |
338 | * The position and field name of "next" are arbitrary. | |
339 | */ | |
340 | ||
341 | /** | |
342 | * Init the element as null-terminated list. | |
343 | * | |
344 | * Example: | |
345 | * struct foo *list = malloc(); | |
346 | * nt_list_init(list, next); | |
347 | * | |
348 | * @param list The list element that will be the start of the list | |
349 | * @param member Member name of the field pointing to next struct | |
350 | */ | |
351 | #define nt_list_init(_list, _member) \ | |
352 | (_list)->_member = NULL | |
353 | ||
354 | /** | |
355 | * Returns the next element in the list or NULL on termination. | |
356 | * | |
357 | * Example: | |
358 | * struct foo *element = list; | |
359 | * while ((element = nt_list_next(element, next)) { } | |
360 | * | |
361 | * This macro is not safe for node deletion. Use nt_list_for_each_entry_safe | |
362 | * instead. | |
363 | * | |
364 | * @param list The list or current element. | |
365 | * @param member Member name of the field pointing to next struct. | |
366 | */ | |
367 | #define nt_list_next(_list, _member) \ | |
368 | (_list)->_member | |
369 | ||
370 | /** | |
371 | * Iterate through each element in the list. | |
372 | * | |
373 | * Example: | |
374 | * struct foo *iterator; | |
375 | * nt_list_for_each_entry(iterator, list, next) { | |
376 | * [modify iterator] | |
377 | * } | |
378 | * | |
379 | * @param entry Assigned to the current list element | |
380 | * @param list The list to iterate through. | |
381 | * @param member Member name of the field pointing to next struct. | |
382 | */ | |
383 | #define nt_list_for_each_entry(_entry, _list, _member) \ | |
384 | for (_entry = _list; _entry; _entry = (_entry)->_member) | |
385 | ||
386 | /** | |
387 | * Iterate through each element in the list, keeping a backup pointer to the | |
388 | * element. This macro allows for the deletion of a list element while | |
389 | * looping through the list. | |
390 | * | |
391 | * See nt_list_for_each_entry for more details. | |
392 | * | |
393 | * @param entry Assigned to the current list element | |
394 | * @param tmp The pointer to the next element | |
395 | * @param list The list to iterate through. | |
396 | * @param member Member name of the field pointing to next struct. | |
397 | */ | |
398 | #define nt_list_for_each_entry_safe(_entry, _tmp, _list, _member) \ | |
399 | for (_entry = _list, _tmp = (_entry) ? (_entry)->_member : NULL;\ | |
400 | _entry; \ | |
401 | _entry = _tmp, _tmp = (_tmp) ? (_tmp)->_member: NULL) | |
402 | ||
403 | /** | |
404 | * Append the element to the end of the list. This macro may be used to | |
405 | * merge two lists. | |
406 | * | |
407 | * Example: | |
408 | * struct foo *elem = malloc(...); | |
409 | * nt_list_init(elem, next) | |
410 | * nt_list_append(elem, list, struct foo, next); | |
411 | * | |
412 | * Resulting list order: | |
413 | * list_item_0 -> list_item_1 -> ... -> elem_item_0 -> elem_item_1 ... | |
414 | * | |
415 | * @param entry An entry (or list) to append to the list | |
416 | * @param list The list to append to. This list must be a valid list, not | |
417 | * NULL. | |
418 | * @param type The list type | |
419 | * @param member Member name of the field pointing to next struct | |
420 | */ | |
421 | #define nt_list_append(_entry, _list, _type, _member) \ | |
422 | do { \ | |
423 | _type *__iterator = _list; \ | |
424 | while (__iterator->_member) { __iterator = __iterator->_member;}\ | |
425 | __iterator->_member = _entry; \ | |
426 | } while (0) | |
427 | ||
428 | /** | |
429 | * Insert the element at the next position in the list. This macro may be | |
430 | * used to insert a list into a list. | |
431 | * | |
432 | * struct foo *elem = malloc(...); | |
433 | * nt_list_init(elem, next) | |
434 | * nt_list_insert(elem, list, struct foo, next); | |
435 | * | |
436 | * Resulting list order: | |
437 | * list_item_0 -> elem_item_0 -> elem_item_1 ... -> list_item_1 -> ... | |
438 | * | |
439 | * @param entry An entry (or list) to append to the list | |
440 | * @param list The list to insert to. This list must be a valid list, not | |
441 | * NULL. | |
442 | * @param type The list type | |
443 | * @param member Member name of the field pointing to next struct | |
444 | */ | |
445 | #define nt_list_insert(_entry, _list, _type, _member) \ | |
446 | do { \ | |
447 | nt_list_append((_list)->_member, _entry, _type, _member); \ | |
448 | (_list)->_member = _entry; \ | |
449 | } while (0) | |
450 | ||
451 | /** | |
452 | * Delete the entry from the list by iterating through the list and | |
453 | * removing any reference from the list to the entry. | |
454 | * | |
455 | * Example: | |
456 | * struct foo *elem = <assign to right element> | |
457 | * nt_list_del(elem, list, struct foo, next); | |
458 | * | |
459 | * @param entry The entry to delete from the list. entry is always | |
460 | * re-initialized as a null-terminated list. | |
461 | * @param list The list containing the entry, set to the new list without | |
462 | * the removed entry. | |
463 | * @param type The list type | |
464 | * @param member Member name of the field pointing to the next entry | |
465 | */ | |
466 | #define nt_list_del(_entry, _list, _type, _member) \ | |
467 | do { \ | |
468 | _type *__e = _entry; \ | |
469 | if (__e == NULL || _list == NULL) break; \ | |
470 | if ((_list) == __e) { \ | |
471 | _list = __e->_member; \ | |
472 | } else { \ | |
473 | _type *__prev = _list; \ | |
474 | while (__prev->_member && __prev->_member != __e) \ | |
475 | __prev = nt_list_next(__prev, _member); \ | |
476 | if (__prev->_member) \ | |
477 | __prev->_member = __e->_member; \ | |
478 | } \ | |
479 | nt_list_init(__e, _member); \ | |
480 | } while(0) | |
481 | ||
482 | /** | |
483 | * DO NOT USE THIS. | |
484 | * This is a remainder of the xfree86 DDX attempt of having a set of generic | |
485 | * list functions. Unfortunately, the xf86OptionRec uses it and we can't | |
486 | * easily get rid of it. Do not use for new code. | |
487 | */ | |
488 | typedef struct generic_list_rec { | |
489 | void *next; | |
490 | } GenericListRec, *GenericListPtr, *glp; | |
491 | ||
492 | #endif |