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