1/* @title: Linked list */
2#pragma once
3#include <compiler.h>
4#include <container_of.h>
5#include <stddef.h>
6
7struct list_head {
8 struct list_head *next, *prev;
9};
10
11#define LIST_HEAD_INIT(name) {&(name), &(name)}
12
13#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
14
15static inline void INIT_LIST_HEAD(struct list_head *list) {
16 list->next = list;
17 list->prev = list;
18}
19
20static inline void __list_add(struct list_head *new, struct list_head *prev,
21 struct list_head *next) {
22 next->prev = new;
23 new->next = next;
24 new->prev = prev;
25 prev->next = new;
26}
27
28static inline void list_add(struct list_head *new, struct list_head *head) {
29 __list_add(new, prev: head, next: head->next);
30}
31
32static inline void list_add_tail(struct list_head *new,
33 struct list_head *head) {
34 __list_add(new, prev: head->prev, next: head);
35}
36
37static inline void __list_del(struct list_head *prev, struct list_head *next) {
38 next->prev = prev;
39 prev->next = next;
40}
41
42static inline void list_del(struct list_head *entry) {
43 __list_del(prev: entry->prev, next: entry->next);
44 entry->next = NULL;
45 entry->prev = NULL;
46}
47
48static inline void list_del_init(struct list_head *entry) {
49 list_del(entry);
50 INIT_LIST_HEAD(list: entry);
51}
52
53static inline int list_empty(const struct list_head *head) {
54 return head->next == head;
55}
56
57static inline struct list_head *list_peek_front(struct list_head *head) {
58 if (list_empty(head))
59 return NULL;
60
61 return head->next;
62}
63
64static inline struct list_head *list_peek_tail(struct list_head *head) {
65 if (list_empty(head))
66 return NULL;
67
68 return head->prev;
69}
70
71static inline struct list_head *list_pop_front(struct list_head *head) {
72 if (list_empty(head))
73 return NULL;
74
75 struct list_head *entry = head->next;
76 list_del(entry);
77 return entry;
78}
79
80static inline struct list_head *list_pop_front_init(struct list_head *head) {
81 struct list_head *ret = list_pop_front(head);
82 if (ret)
83 INIT_LIST_HEAD(list: ret);
84
85 return ret;
86}
87
88static inline struct list_head *list_pop_tail(struct list_head *head) {
89 if (list_empty(head))
90 return NULL;
91
92 struct list_head *entry = head->prev;
93 list_del(entry);
94 return entry;
95}
96
97static inline struct list_head *list_pop_tail_init(struct list_head *head) {
98 struct list_head *ret = list_pop_tail(head);
99 if (ret)
100 INIT_LIST_HEAD(list: ret);
101
102 return ret;
103}
104
105static inline void __list_splice(const struct list_head *list,
106 struct list_head *prev,
107 struct list_head *next) {
108 struct list_head *first = list->next;
109 struct list_head *last = list->prev;
110
111 first->prev = prev;
112 prev->next = first;
113
114 last->next = next;
115 next->prev = last;
116}
117
118static inline void list_splice_init(struct list_head *src,
119 struct list_head *dst) {
120 if (!list_empty(head: src)) {
121 struct list_head *first = src->next;
122 struct list_head *last = src->prev;
123 struct list_head *at = dst;
124
125 first->prev = at->prev;
126 at->prev->next = first;
127
128 last->next = at;
129 at->prev = last;
130
131 INIT_LIST_HEAD(list: src);
132 }
133}
134
135static inline void list_splice_tail_init(struct list_head *list,
136 struct list_head *head) {
137 if (!list_empty(head: list)) {
138 __list_splice(list, prev: head->prev, next: head);
139 INIT_LIST_HEAD(list);
140 }
141}
142
143#define list_entry(ptr, type, member) \
144 ((type *) ((char *) (ptr) - (offsetof(type, member))))
145
146#define list_for_each(pos, head) \
147 for (pos = (head)->next; pos != (head); pos = pos->next)
148
149#define list_for_each_rev(pos, head) \
150 for (pos = (head)->prev; pos != (head); pos = pos->prev)
151
152#define list_for_each_safe(pos, n, head) \
153 for (pos = (head)->next, n = pos->next; pos != (head); \
154 pos = n, n = pos->next)
155
156#define list_for_each_rev_safe(pos, n, head) \
157 for (pos = (head)->prev, n = pos->prev; pos != (head); \
158 pos = n, n = pos->prev)
159
160#define list_for_each_entry(pos, head, member) \
161 for (pos = list_entry((head)->next, typeof(*pos), member); \
162 &pos->member != (head); \
163 pos = list_entry(pos->member.next, typeof(*pos), member))
164
165#define list_for_each_entry_rev(pos, head, member) \
166 for (pos = list_entry((head)->prev, typeof(*pos), member); \
167 &pos->member != (head); \
168 pos = list_entry(pos->member.prev, typeof(*pos), member))
169
170#define list_first_entry(ptr, type, member) \
171 list_entry((ptr)->next, type, member)
172
173#define list_last_entry(ptr, type, member) list_entry((ptr)->prev, type, member)
174
175#define list_for_each_entry_safe(pos, n, head, member) \
176 for (pos = list_entry((head)->next, typeof(*pos), member), \
177 n = list_entry(pos->member.next, typeof(*pos), member); \
178 &pos->member != (head); \
179 pos = n, n = list_entry(n->member.next, typeof(*n), member))
180
181#define list_for_each_entry_safe_rev(pos, n, head, member) \
182 for (pos = list_entry((head)->prev, typeof(*pos), member), \
183 n = list_entry(pos->member.prev, typeof(*pos), member); \
184 &pos->member != (head); \
185 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
186
187#define list_for_each_entry_safe_continue(pos, n, head, member) \
188 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
189 n = list_entry(pos->member.next, typeof(*pos), member); \
190 &pos->member != (head); \
191 pos = n, n = list_entry(n->member.next, typeof(*n), member))
192
193#define list_for_each_entry_safe_continue_rev(pos, n, head, member) \
194 for (pos = list_entry(pos->member.prev, typeof(*pos), member), \
195 n = list_entry(pos->member.prev, typeof(*pos), member); \
196 &pos->member != (head); \
197 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
198
199void list_sort(struct list_head *head,
200 int (*cmp)(struct list_head *, struct list_head *));
201
202struct slist_node {
203 struct slist_node *next;
204};
205
206struct slist_head {
207 struct slist_node *first;
208 struct slist_node *last;
209};
210
211static inline void slist_head_init(struct slist_head *h) {
212 h->first = NULL;
213 h->last = NULL;
214}
215
216static inline int slist_empty(const struct slist_head *h) {
217 return h->first == NULL;
218}
219
220static inline void slist_push_head(struct slist_head *h, struct slist_node *n) {
221 n->next = h->first;
222 h->first = n;
223 if (h->last == NULL)
224 h->last = n;
225}
226
227static inline void slist_push_tail(struct slist_head *h, struct slist_node *n) {
228 n->next = NULL;
229
230 if (h->last != NULL) {
231 h->last->next = n;
232 } else {
233 h->first = n;
234 }
235
236 h->last = n;
237}
238
239static inline struct slist_node *slist_pop_head(struct slist_head *h) {
240 struct slist_node *n = h->first;
241 if (!n)
242 return NULL;
243
244 h->first = n->next;
245 if (h->first == NULL)
246 h->last = NULL;
247
248 n->next = NULL;
249 return n;
250}
251
252static inline void slist_remove_node_after(struct slist_head *h,
253 struct slist_node *prev,
254 struct slist_node *target) {
255
256 if (!prev) {
257 if (h->first != target)
258 return;
259
260 slist_pop_head(h);
261 return;
262 }
263
264 if (prev->next != target)
265 return;
266
267 prev->next = target->next;
268
269 if (h->last == target)
270 h->last = prev;
271
272 target->next = NULL;
273}
274