1 /* $OpenBSD: list.h,v 1.8 2024/01/16 23:38:13 jsg Exp $ */
2 /* drm_linux_list.h -- linux list functions for the BSDs.
3 * Created: Mon Apr 7 14:30:16 1999 by anholt@FreeBSD.org
4 */
5 /*-
6 * Copyright 2003 Eric Anholt
7 * All Rights Reserved.
8 *
9 * Permission is hereby granted, free of charge, to any person obtaining a
10 * copy of this software and associated documentation files (the "Software"),
11 * to deal in the Software without restriction, including without limitation
12 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
13 * and/or sell copies of the Software, and to permit persons to whom the
14 * Software is furnished to do so, subject to the following conditions:
15 *
16 * The above copyright notice and this permission notice (including the next
17 * paragraph) shall be included in all copies or substantial portions of the
18 * Software.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 * VA LINUX SYSTEMS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
24 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
26 * OTHER DEALINGS IN THE SOFTWARE.
27 *
28 * Authors:
29 * Eric Anholt <anholt@FreeBSD.org>
30 *
31 */
32
33 #ifndef _DRM_LINUX_LIST_H_
34 #define _DRM_LINUX_LIST_H_
35
36 #include <sys/param.h>
37 #include <linux/container_of.h>
38 #include <linux/types.h>
39 #include <linux/poison.h>
40
41 #define list_entry(ptr, type, member) container_of(ptr, type, member)
42
43 static inline void
INIT_LIST_HEAD(struct list_head * head)44 INIT_LIST_HEAD(struct list_head *head) {
45 (head)->next = head;
46 (head)->prev = head;
47 }
48
49 #define LIST_HEAD_INIT(name) { &(name), &(name) }
50
51 #define DRM_LIST_HEAD(name) \
52 struct list_head name = LIST_HEAD_INIT(name)
53
54 static inline int
list_empty(const struct list_head * head)55 list_empty(const struct list_head *head) {
56 return (head)->next == head;
57 }
58
59 static inline int
list_is_singular(const struct list_head * head)60 list_is_singular(const struct list_head *head) {
61 return !list_empty(head) && ((head)->next == (head)->prev);
62 }
63
64 static inline int
list_is_first(const struct list_head * list,const struct list_head * head)65 list_is_first(const struct list_head *list,
66 const struct list_head *head)
67 {
68 return list->prev == head;
69 }
70
71 static inline int
list_is_last(const struct list_head * list,const struct list_head * head)72 list_is_last(const struct list_head *list,
73 const struct list_head *head)
74 {
75 return list->next == head;
76 }
77
78 static inline void
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)79 __list_add(struct list_head *new, struct list_head *prev,
80 struct list_head *next)
81 {
82 next->prev = new;
83 new->next = next;
84 new->prev = prev;
85 prev->next = new;
86 }
87
88 static inline void
list_add(struct list_head * new,struct list_head * head)89 list_add(struct list_head *new, struct list_head *head) {
90 (head)->next->prev = new;
91 (new)->next = (head)->next;
92 (new)->prev = head;
93 (head)->next = new;
94 }
95
96 static inline void
list_add_tail(struct list_head * entry,struct list_head * head)97 list_add_tail(struct list_head *entry, struct list_head *head) {
98 (entry)->prev = (head)->prev;
99 (entry)->next = head;
100 (head)->prev->next = entry;
101 (head)->prev = entry;
102 }
103
104 static inline void
list_del(struct list_head * entry)105 list_del(struct list_head *entry) {
106 (entry)->next->prev = (entry)->prev;
107 (entry)->prev->next = (entry)->next;
108 }
109
110 #define __list_del_entry(x) list_del(x)
111
list_replace(struct list_head * old,struct list_head * new)112 static inline void list_replace(struct list_head *old,
113 struct list_head *new)
114 {
115 new->next = old->next;
116 new->next->prev = new;
117 new->prev = old->prev;
118 new->prev->next = new;
119 }
120
list_replace_init(struct list_head * old,struct list_head * new)121 static inline void list_replace_init(struct list_head *old,
122 struct list_head *new)
123 {
124 list_replace(old, new);
125 INIT_LIST_HEAD(old);
126 }
127
list_move(struct list_head * list,struct list_head * head)128 static inline void list_move(struct list_head *list, struct list_head *head)
129 {
130 list_del(list);
131 list_add(list, head);
132 }
133
list_move_tail(struct list_head * list,struct list_head * head)134 static inline void list_move_tail(struct list_head *list,
135 struct list_head *head)
136 {
137 list_del(list);
138 list_add_tail(list, head);
139 }
140
141 static inline void
list_rotate_to_front(struct list_head * list,struct list_head * head)142 list_rotate_to_front(struct list_head *list, struct list_head *head)
143 {
144 list_del(head);
145 list_add_tail(head, list);
146 }
147
148 static inline void
list_bulk_move_tail(struct list_head * head,struct list_head * first,struct list_head * last)149 list_bulk_move_tail(struct list_head *head, struct list_head *first,
150 struct list_head *last)
151 {
152 first->prev->next = last->next;
153 last->next->prev = first->prev;
154 head->prev->next = first;
155 first->prev = head->prev;
156 last->next = head;
157 head->prev = last;
158 }
159
160 static inline void
list_del_init(struct list_head * entry)161 list_del_init(struct list_head *entry) {
162 (entry)->next->prev = (entry)->prev;
163 (entry)->prev->next = (entry)->next;
164 INIT_LIST_HEAD(entry);
165 }
166
167 #define list_next_entry(pos, member) \
168 list_entry(((pos)->member.next), typeof(*(pos)), member)
169
170 #define list_prev_entry(pos, member) \
171 list_entry(((pos)->member.prev), typeof(*(pos)), member)
172
173 #define list_safe_reset_next(pos, n, member) \
174 n = list_next_entry(pos, member)
175
176 #define list_for_each(entry, head) \
177 for (entry = (head)->next; entry != head; entry = (entry)->next)
178
179 #define list_for_each_prev(entry, head) \
180 for (entry = (head)->prev; entry != (head); \
181 entry = entry->prev)
182
183 #define list_for_each_safe(entry, temp, head) \
184 for (entry = (head)->next, temp = (entry)->next; \
185 entry != head; \
186 entry = temp, temp = entry->next)
187
188 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
189 for (pos = list_entry((head)->prev, __typeof(*pos), member), \
190 n = list_entry((pos)->member.prev, __typeof(*pos), member); \
191 &(pos)->member != (head); \
192 pos = n, n = list_entry(n->member.prev, __typeof(*n), member))
193
194 #define list_for_each_entry_safe_from(pos, n, head, member) \
195 for (n = list_entry(pos->member.next, __typeof(*pos), member); \
196 &pos->member != (head); \
197 pos = n, n = list_entry(n->member.next, __typeof(*n), member))
198
199 #define list_for_each_entry(pos, head, member) \
200 for (pos = list_entry((head)->next, __typeof(*pos), member); \
201 &pos->member != (head); \
202 pos = list_entry(pos->member.next, __typeof(*pos), member))
203
204 #define list_for_each_entry_from(pos, head, member) \
205 for (; \
206 &pos->member != (head); \
207 pos = list_entry(pos->member.next, __typeof(*pos), member))
208
209 #define list_for_each_entry_reverse(pos, head, member) \
210 for (pos = list_entry((head)->prev, __typeof(*pos), member); \
211 &pos->member != (head); \
212 pos = list_entry(pos->member.prev, __typeof(*pos), member))
213
214 #define list_for_each_entry_from_reverse(pos, head, member) \
215 for (; \
216 &pos->member != (head); \
217 pos = list_entry(pos->member.prev, __typeof(*pos), member))
218
219 #define list_for_each_entry_continue(pos, head, member) \
220 for (pos = list_entry((pos)->member.next, __typeof(*pos), member); \
221 &pos->member != (head); \
222 pos = list_entry(pos->member.next, __typeof(*pos), member))
223
224 #define list_for_each_entry_continue_reverse(pos, head, member) \
225 for (pos = list_entry(pos->member.prev, __typeof(*pos), member); \
226 &pos->member != (head); \
227 pos = list_entry(pos->member.prev, __typeof(*pos), member))
228
229 /**
230 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
231 * @pos: the type * to use as a loop cursor.
232 * @n: another type * to use as temporary storage
233 * @head: the head for your list.
234 * @member: the name of the list_struct within the struct.
235 */
236 #define list_for_each_entry_safe(pos, n, head, member) \
237 for (pos = list_entry((head)->next, __typeof(*pos), member), \
238 n = list_entry(pos->member.next, __typeof(*pos), member); \
239 &pos->member != (head); \
240 pos = n, n = list_entry(n->member.next, __typeof(*n), member))
241
242 #define list_first_entry(ptr, type, member) \
243 list_entry((ptr)->next, type, member)
244
245 #define list_first_entry_or_null(ptr, type, member) \
246 (list_empty(ptr) ? NULL : list_first_entry(ptr, type, member))
247
248 #define list_last_entry(ptr, type, member) \
249 list_entry((ptr)->prev, type, member)
250
251 static inline void
__list_splice(const struct list_head * list,struct list_head * prev,struct list_head * next)252 __list_splice(const struct list_head *list, struct list_head *prev,
253 struct list_head *next)
254 {
255 struct list_head *first = list->next;
256 struct list_head *last = list->prev;
257
258 first->prev = prev;
259 prev->next = first;
260
261 last->next = next;
262 next->prev = last;
263 }
264
265 static inline void
list_splice(const struct list_head * list,struct list_head * head)266 list_splice(const struct list_head *list, struct list_head *head)
267 {
268 if (list_empty(list))
269 return;
270
271 __list_splice(list, head, head->next);
272 }
273
274 static inline void
list_splice_init(struct list_head * list,struct list_head * head)275 list_splice_init(struct list_head *list, struct list_head *head)
276 {
277 if (list_empty(list))
278 return;
279
280 __list_splice(list, head, head->next);
281 INIT_LIST_HEAD(list);
282 }
283
284 static inline void
list_splice_tail(const struct list_head * list,struct list_head * head)285 list_splice_tail(const struct list_head *list, struct list_head *head)
286 {
287 if (list_empty(list))
288 return;
289
290 __list_splice(list, head->prev, head);
291 }
292
293 static inline void
list_splice_tail_init(struct list_head * list,struct list_head * head)294 list_splice_tail_init(struct list_head *list, struct list_head *head)
295 {
296 if (list_empty(list))
297 return;
298
299 __list_splice(list, head->prev, head);
300 INIT_LIST_HEAD(list);
301 }
302
303 static inline size_t
list_count_nodes(struct list_head * head)304 list_count_nodes(struct list_head *head)
305 {
306 struct list_head *entry;
307 size_t n = 0;
308
309 list_for_each(entry, head)
310 n++;
311
312 return n;
313 }
314
315 void list_sort(void *, struct list_head *,
316 int (*)(void *, const struct list_head *, const struct list_head *));
317
318 #define hlist_entry(ptr, type, member) \
319 ((ptr) ? container_of(ptr, type, member) : NULL)
320
321 static inline void
INIT_HLIST_HEAD(struct hlist_head * head)322 INIT_HLIST_HEAD(struct hlist_head *head) {
323 head->first = NULL;
324 }
325
326 static inline int
hlist_empty(const struct hlist_head * head)327 hlist_empty(const struct hlist_head *head) {
328 return head->first == NULL;
329 }
330
331 static inline void
hlist_add_head(struct hlist_node * new,struct hlist_head * head)332 hlist_add_head(struct hlist_node *new, struct hlist_head *head)
333 {
334 if ((new->next = head->first) != NULL)
335 head->first->prev = &new->next;
336 head->first = new;
337 new->prev = &head->first;
338 }
339
340 static inline void
hlist_del_init(struct hlist_node * node)341 hlist_del_init(struct hlist_node *node)
342 {
343 if (node->next != NULL)
344 node->next->prev = node->prev;
345 *(node->prev) = node->next;
346 node->next = NULL;
347 node->prev = NULL;
348 }
349
350 #define hlist_for_each(pos, head) \
351 for (pos = (head)->first; pos != NULL; pos = pos->next)
352
353 #define hlist_for_each_entry(pos, head, member) \
354 for (pos = hlist_entry((head)->first, __typeof(*pos), member); \
355 pos != NULL; \
356 pos = hlist_entry((pos)->member.next, __typeof(*pos), member))
357
358 #define hlist_for_each_entry_safe(pos, n, head, member) \
359 for (pos = hlist_entry((head)->first, __typeof(*pos), member); \
360 pos != NULL && (n = pos->member.next, 1); \
361 pos = hlist_entry(n, __typeof(*pos), member))
362
363 #endif /* _DRM_LINUX_LIST_H_ */
364