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_safe(pos, n, head) \
150 for (pos = (head)->next, n = pos->next; pos != (head); \
151 pos = n, n = pos->next)
152
153#define list_for_each_entry(pos, head, member) \
154 for (pos = list_entry((head)->next, typeof(*pos), member); \
155 &pos->member != (head); \
156 pos = list_entry(pos->member.next, typeof(*pos), member))
157
158#define list_first_entry(ptr, type, member) \
159 list_entry((ptr)->next, type, member)
160
161#define list_for_each_entry_safe(pos, n, head, member) \
162 for (pos = list_entry((head)->next, typeof(*pos), member), \
163 n = list_entry(pos->member.next, typeof(*pos), member); \
164 &pos->member != (head); \
165 pos = n, n = list_entry(n->member.next, typeof(*n), member))
166
167#define list_for_each_entry_safe_continue(pos, n, head, member) \
168 for (pos = list_entry(pos->member.next, typeof(*pos), member), \
169 n = list_entry(pos->member.next, typeof(*pos), member); \
170 &pos->member != (head); \
171 pos = n, n = list_entry(n->member.next, typeof(*n), member))
172
173void list_sort(struct list_head *head,
174 int (*cmp)(struct list_head *, struct list_head *));
175
176struct slist_node {
177 struct slist_node *next;
178};
179
180struct slist_head {
181 struct slist_node *first;
182 struct slist_node *last;
183};
184
185static inline void slist_head_init(struct slist_head *h) {
186 h->first = NULL;
187 h->last = NULL;
188}
189
190static inline int slist_empty(const struct slist_head *h) {
191 return h->first == NULL;
192}
193
194static inline void slist_push_head(struct slist_head *h, struct slist_node *n) {
195 n->next = h->first;
196 h->first = n;
197 if (h->last == NULL)
198 h->last = n;
199}
200
201static inline void slist_push_tail(struct slist_head *h, struct slist_node *n) {
202 n->next = NULL;
203
204 if (h->last != NULL) {
205 h->last->next = n;
206 } else {
207 h->first = n;
208 }
209
210 h->last = n;
211}
212
213static inline struct slist_node *slist_pop_head(struct slist_head *h) {
214 struct slist_node *n = h->first;
215 if (!n)
216 return NULL;
217
218 h->first = n->next;
219 if (h->first == NULL)
220 h->last = NULL;
221
222 n->next = NULL;
223 return n;
224}
225
226static inline void slist_remove_node_after(struct slist_head *h,
227 struct slist_node *prev,
228 struct slist_node *target) {
229
230 if (!prev) {
231 if (h->first != target)
232 return;
233
234 slist_pop_head(h);
235 return;
236 }
237
238 if (prev->next != target)
239 return;
240
241 prev->next = target->next;
242
243 if (h->last == target)
244 h->last = prev;
245
246 target->next = NULL;
247}
248