1/* @title: Linked list */
2#pragma once
3#include <compiler/core.h>
4#include <container_of.h>
5#include <stdbool.h>
6#include <stddef.h>
7
8/* Circular doubly linked list.
9 *
10 * We use two different types here since a unified list_head proved problematic
11 * for readability and semantics. It's largely symbolic and for type safety.
12 *
13 * struct list_node is the link
14 * struct list_head is the head/anchor of the list.
15 *
16 * list_head_* operations take the list_head,
17 * list_node_* operations a list_node,
18 * list_root_* operations technically take a list_node, but this is meant
19 * to be the list_head's root member, and is used as convenience.
20 *
21 * Thus, swapping arguments like list_add(&parent->node, &child->node); is
22 * not possible and fails to compile. */
23struct list_node {
24 struct list_node *next, *prev;
25};
26
27struct list_head {
28 struct list_node root;
29};
30
31static_assert(sizeof(struct list_head) == sizeof(struct list_node));
32static_assert(offsetof(struct list_head, root) == 0);
33
34#ifdef DEBUG_LIST
35void list_add_check(const struct list_node *new, const struct list_node *prev,
36 const struct list_node *next);
37void list_del_check(const struct list_node *entry);
38void list_splice_check(const struct list_node *list,
39 const struct list_node *prev,
40 const struct list_node *next);
41#else
42static inline void list_add_check(const struct list_node *new,
43 const struct list_node *prev,
44 const struct list_node *next) {
45 cc_ignore(new, prev, next);
46}
47
48static inline void list_del_check(const struct list_node *entry) {
49 cc_ignore(entry);
50}
51
52static inline void list_splice_check(const struct list_node *list,
53 const struct list_node *prev,
54 const struct list_node *next) {
55 cc_ignore(list, prev, next);
56}
57#endif /* DEBUG_LIST */
58
59#define LIST_NODE_INIT(name) {&(name), &(name)}
60
61#define LIST_HEAD_INIT(name) \
62 { \
63 .root = { &(name).root, &(name).root } \
64 }
65
66#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
67
68#define list_root(h) (&(h)->root)
69
70static inline void list_node_init(struct list_node *n) {
71 n->next = n;
72 n->prev = n;
73}
74
75static inline void list_head_init(struct list_head *h) {
76 list_node_init(n: &h->root);
77}
78
79static inline bool list_node_is_linked(const struct list_node *n) {
80 return n->next != NULL && n->next != n;
81}
82
83static inline struct list_node *list_node_next(const struct list_node *n) {
84 return n->next;
85}
86
87static inline struct list_node *list_node_prev(const struct list_node *n) {
88 return n->prev;
89}
90
91static inline struct list_node *list_head_sentinel(struct list_head *h) {
92 return &h->root;
93}
94
95/* Treat a node as if it's the head. Should only be used in headless
96 * lists where one of the middle members is also the anchor */
97static inline struct list_head *list_node_as_head(struct list_node *n) {
98 /* container_of in here in case we want to do more tracking
99 * and debugging in list_head */
100 return container_of(n, struct list_head, root);
101}
102
103static inline void list_node_link_between(struct list_node *new,
104 struct list_node *prev,
105 struct list_node *next) {
106 list_add_check(new, prev, next);
107
108 next->prev = new;
109 new->next = next;
110 new->prev = prev;
111 prev->next = new;
112}
113
114static inline void list_node_unlink_between(struct list_node *prev,
115 struct list_node *next) {
116 next->prev = prev;
117 prev->next = next;
118}
119
120static inline void list_node_insert_after(struct list_node *pos,
121 struct list_node *n) {
122 list_node_link_between(new: n, prev: pos, next: pos->next);
123}
124
125static inline void list_node_insert_before(struct list_node *pos,
126 struct list_node *n) {
127 list_node_link_between(new: n, prev: pos->prev, next: pos);
128}
129
130static inline void list_node_delete(struct list_node *n) {
131 list_del_check(entry: n);
132
133 list_node_unlink_between(prev: n->prev, next: n->next);
134 n->next = NULL;
135 n->prev = NULL;
136}
137
138static inline void list_node_delete_init(struct list_node *n) {
139 list_node_delete(n);
140 list_node_init(n);
141}
142
143static inline bool list_head_empty(const struct list_head *h) {
144 return h->root.next == &h->root;
145}
146
147static inline void list_head_push_front(struct list_head *h,
148 struct list_node *n) {
149 list_node_insert_after(pos: &h->root, n);
150}
151
152static inline void list_head_push_back(struct list_head *h,
153 struct list_node *n) {
154 list_node_insert_before(pos: &h->root, n);
155}
156
157/* root_*, For direct sentinel manipulation */
158static inline struct list_node *list_root_pop_front(struct list_node *root) {
159 if (root->next == root)
160 return NULL;
161
162 struct list_node *n = root->next;
163 list_node_delete(n);
164 return n;
165}
166
167static inline struct list_node *list_root_pop_back(struct list_node *root) {
168 if (root->next == root)
169 return NULL;
170
171 struct list_node *n = root->prev;
172 list_node_delete(n);
173 return n;
174}
175
176static inline struct list_node *list_head_peek_front(struct list_head *h) {
177 return list_head_empty(h) ? NULL : h->root.next;
178}
179
180static inline struct list_node *list_head_peek_back(struct list_head *h) {
181 return list_head_empty(h) ? NULL : h->root.prev;
182}
183
184static inline struct list_node *list_head_pop_front(struct list_head *h) {
185 return list_root_pop_front(root: &h->root);
186}
187
188static inline struct list_node *list_head_pop_back(struct list_head *h) {
189 return list_root_pop_back(root: &h->root);
190}
191
192static inline struct list_node *list_head_pop_front_init(struct list_head *h) {
193 struct list_node *n = list_head_pop_front(h);
194 if (n)
195 list_node_init(n);
196
197 return n;
198}
199
200static inline struct list_node *list_head_pop_back_init(struct list_head *h) {
201 struct list_node *n = list_head_pop_back(h);
202 if (n)
203 list_node_init(n);
204
205 return n;
206}
207
208static inline void list_splice_between(const struct list_node *list,
209 struct list_node *prev,
210 struct list_node *next) {
211 list_splice_check(list, prev, next);
212
213 struct list_node *first = list->next;
214 struct list_node *last = list->prev;
215
216 first->prev = prev;
217 prev->next = first;
218
219 last->next = next;
220 next->prev = last;
221}
222
223/* Move everyone from src to the front of dst */
224static inline void list_head_splice_front_init(struct list_head *dst,
225 struct list_head *src) {
226 if (!list_head_empty(h: src)) {
227 list_splice_between(list: &src->root, prev: &dst->root, next: dst->root.next);
228 list_head_init(h: src);
229 }
230}
231
232/* Move everyone from src to the back of dst */
233static inline void list_head_splice_back_init(struct list_head *dst,
234 struct list_head *src) {
235 if (!list_head_empty(h: src)) {
236 list_splice_between(list: &src->root, prev: dst->root.prev, next: &dst->root);
237 list_head_init(h: src);
238 }
239}
240
241typedef int (*list_cmp_fn)(struct list_node *, struct list_node *);
242
243void list_root_sort(struct list_node *root, list_cmp_fn cmp);
244
245static inline void list_head_sort(struct list_head *h, list_cmp_fn cmp) {
246 list_root_sort(root: &h->root, cmp);
247}
248
249#define list_entry(ptr, type, member) container_of(ptr, type, member)
250
251#define list_entry_safe(ptr, type, member) \
252 ({ \
253 __auto_type __list_ptr = (ptr); \
254 __list_ptr ? list_entry(__list_ptr, type, member) : NULL; \
255 })
256
257#define list_for_each(pos, head) \
258 for (pos = list_root(head)->next; pos != list_root(head); pos = pos->next)
259
260#define list_for_each_rev(pos, head) \
261 for (pos = list_root(head)->prev; pos != list_root(head); pos = pos->prev)
262
263#define list_for_each_safe(pos, n, head) \
264 for (pos = list_root(head)->next, n = pos->next; pos != list_root(head); \
265 pos = n, n = pos->next)
266
267#define list_for_each_rev_safe(pos, n, head) \
268 for (pos = list_root(head)->prev, n = pos->prev; pos != list_root(head); \
269 pos = n, n = pos->prev)
270
271#define list_for_each_entry(pos, head, member) \
272 for (pos = list_entry(list_root(head)->next, typeof(*pos), member); \
273 &pos->member != list_root(head); \
274 pos = list_entry(pos->member.next, typeof(*pos), member))
275
276#define list_for_each_entry_rev(pos, head, member) \
277 for (pos = list_entry(list_root(head)->prev, typeof(*pos), member); \
278 &pos->member != list_root(head); \
279 pos = list_entry(pos->member.prev, typeof(*pos), member))
280
281#define list_first_entry(ptr, type, member) \
282 list_entry(list_root(ptr)->next, type, member)
283
284#define list_last_entry(ptr, type, member) \
285 list_entry(list_root(ptr)->prev, type, member)
286
287#define list_for_each_entry_safe(pos, n, head, member) \
288 for (pos = list_entry(list_root(head)->next, typeof(*pos), member), \
289 n = list_entry(pos->member.next, typeof(*pos), member); \
290 &pos->member != list_root(head); \
291 pos = n, n = list_entry(n->member.next, typeof(*n), member))
292
293#define list_for_each_entry_safe_rev(pos, n, head, member) \
294 for (pos = list_entry(list_root(head)->prev, typeof(*pos), member), \
295 n = list_entry(pos->member.prev, typeof(*pos), member); \
296 &pos->member != list_root(head); \
297 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
298
299#define list_for_each_entry_safe_continue(pos, n, head, member) \
300 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
301 n = list_entry(pos->member.next, typeof(*pos), member); \
302 &pos->member != list_root(head); \
303 pos = n, n = list_entry(n->member.next, typeof(*n), member))
304
305#define list_for_each_entry_safe_continue_rev(pos, n, head, member) \
306 for (pos = list_entry(pos->member.prev, typeof(*pos), member), \
307 n = list_entry(pos->member.prev, typeof(*pos), member); \
308 &pos->member != list_root(head); \
309 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
310
311struct slist_node {
312 struct slist_node *next;
313};
314
315struct slist_head {
316 struct slist_node *first;
317 struct slist_node *last;
318};
319
320static inline void slist_head_init(struct slist_head *h) {
321 h->first = NULL;
322 h->last = NULL;
323}
324
325static inline int slist_empty(const struct slist_head *h) {
326 return h->first == NULL;
327}
328
329static inline void slist_push_head(struct slist_head *h, struct slist_node *n) {
330 n->next = h->first;
331 h->first = n;
332 if (h->last == NULL)
333 h->last = n;
334}
335
336static inline void slist_push_tail(struct slist_head *h, struct slist_node *n) {
337 n->next = NULL;
338
339 if (h->last != NULL) {
340 h->last->next = n;
341 } else {
342 h->first = n;
343 }
344
345 h->last = n;
346}
347
348static inline struct slist_node *slist_pop_head(struct slist_head *h) {
349 struct slist_node *n = h->first;
350 if (!n)
351 return NULL;
352
353 h->first = n->next;
354 if (h->first == NULL)
355 h->last = NULL;
356
357 n->next = NULL;
358 return n;
359}
360
361static inline void slist_remove_node_after(struct slist_head *h,
362 struct slist_node *prev,
363 struct slist_node *target) {
364
365 if (!prev) {
366 if (h->first != target)
367 return;
368
369 slist_pop_head(h);
370 return;
371 }
372
373 if (prev->next != target)
374 return;
375
376 prev->next = target->next;
377
378 if (h->last == target)
379 h->last = prev;
380
381 target->next = NULL;
382}
383