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