1 // Copyright 2016 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #pragma once
6
7 #include <zircon/compiler.h>
8 #include <stdbool.h>
9 #include <stddef.h>
10
11 __BEGIN_CDECLS;
12
13 #define containerof(ptr, type, member) ((type*)((uintptr_t)(ptr)-offsetof(type, member)))
14
15 typedef struct list_node list_node_t;
16
17 struct list_node {
18 list_node_t* prev;
19 list_node_t* next;
20 };
21
22 #define LIST_INITIAL_VALUE(list) \
23 { &(list), &(list) }
24 #define LIST_INITIAL_CLEARED_VALUE \
25 { NULL, NULL }
26
list_initialize(list_node_t * list)27 static inline void list_initialize(list_node_t* list) {
28 list->prev = list->next = list;
29 }
30
list_clear_node(list_node_t * item)31 static inline void list_clear_node(list_node_t* item) {
32 item->prev = item->next = 0;
33 }
34
list_in_list(const list_node_t * item)35 static inline bool list_in_list(const list_node_t* item) {
36 if (item->prev == 0 && item->next == 0)
37 return false;
38 else
39 return true;
40 }
41
list_add_head(list_node_t * list,list_node_t * item)42 static inline void list_add_head(list_node_t* list, list_node_t* item) {
43 item->next = list->next;
44 item->prev = list;
45 list->next->prev = item;
46 list->next = item;
47 }
48
49 #define list_add_after(entry, new_entry) list_add_head(entry, new_entry)
50
list_add_tail(list_node_t * list,list_node_t * item)51 static inline void list_add_tail(list_node_t* list, list_node_t* item) {
52 item->prev = list->prev;
53 item->next = list;
54 list->prev->next = item;
55 list->prev = item;
56 }
57
58 #define list_add_before(entry, new_entry) list_add_tail(entry, new_entry)
59
list_delete(list_node_t * item)60 static inline void list_delete(list_node_t* item) {
61 item->next->prev = item->prev;
62 item->prev->next = item->next;
63 item->prev = item->next = 0;
64 }
65
list_replace_node(list_node_t * old_node,list_node_t * new_node)66 static inline void list_replace_node(list_node_t* old_node, list_node_t* new_node) {
67 // replace a spot in a list with a new node
68 // assumes old_node is part of a list and new_node is not
69 new_node->next = old_node->next;
70 new_node->prev = old_node->prev;
71 old_node->prev = old_node->next = 0;
72
73 new_node->next->prev = new_node;
74 new_node->prev->next = new_node;
75 }
76
list_remove_head(list_node_t * list)77 static inline list_node_t* list_remove_head(list_node_t* list) {
78 if (list->next != list) {
79 list_node_t* item = list->next;
80 list_delete(item);
81 return item;
82 } else {
83 return NULL;
84 }
85 }
86
87 #define list_remove_head_type(list, type, element) \
88 ({ \
89 list_node_t* __nod = list_remove_head(list); \
90 type* __t; \
91 if (__nod) \
92 __t = containerof(__nod, type, element); \
93 else \
94 __t = (type*)0; \
95 __t; \
96 })
97
list_remove_tail(list_node_t * list)98 static inline list_node_t* list_remove_tail(list_node_t* list) {
99 if (list->prev != list) {
100 list_node_t* item = list->prev;
101 list_delete(item);
102 return item;
103 } else {
104 return NULL;
105 }
106 }
107
108 #define list_remove_tail_type(list, type, element) \
109 ({ \
110 list_node_t* __nod = list_remove_tail(list); \
111 type* __t; \
112 if (__nod) \
113 __t = containerof(__nod, type, element); \
114 else \
115 __t = (type*)0; \
116 __t; \
117 })
118
list_peek_head(list_node_t * list)119 static inline list_node_t* list_peek_head(list_node_t* list) {
120 if (list->next != list) {
121 return list->next;
122 } else {
123 return NULL;
124 }
125 }
126
127 #define list_peek_head_type(list, type, element) \
128 ({ \
129 list_node_t* __nod = list_peek_head(list); \
130 type* __t; \
131 if (__nod) \
132 __t = containerof(__nod, type, element); \
133 else \
134 __t = (type*)0; \
135 __t; \
136 })
137
list_peek_tail(list_node_t * list)138 static inline list_node_t* list_peek_tail(list_node_t* list) {
139 if (list->prev != list) {
140 return list->prev;
141 } else {
142 return NULL;
143 }
144 }
145
146 #define list_peek_tail_type(list, type, element) \
147 ({ \
148 list_node_t* __nod = list_peek_tail(list); \
149 type* __t; \
150 if (__nod) \
151 __t = containerof(__nod, type, element); \
152 else \
153 __t = (type*)0; \
154 __t; \
155 })
156
list_prev(list_node_t * list,list_node_t * item)157 static inline list_node_t* list_prev(list_node_t* list, list_node_t* item) {
158 if (item->prev != list)
159 return item->prev;
160 else
161 return NULL;
162 }
163
164 #define list_prev_type(list, item, type, element) \
165 ({ \
166 list_node_t* __nod = list_prev(list, item); \
167 type* __t; \
168 if (__nod) \
169 __t = containerof(__nod, type, element); \
170 else \
171 __t = (type*)0; \
172 __t; \
173 })
174
list_prev_wrap(list_node_t * list,list_node_t * item)175 static inline list_node_t* list_prev_wrap(list_node_t* list, list_node_t* item) {
176 if (item->prev != list)
177 return item->prev;
178 else if (item->prev->prev != list)
179 return item->prev->prev;
180 else
181 return NULL;
182 }
183
184 #define list_prev_wrap_type(list, item, type, element) \
185 ({ \
186 list_node_t* __nod = list_prev_wrap(list, item); \
187 type* __t; \
188 if (__nod) \
189 __t = containerof(__nod, type, element); \
190 else \
191 __t = (type*)0; \
192 __t; \
193 })
194
list_next(list_node_t * list,list_node_t * item)195 static inline list_node_t* list_next(list_node_t* list, list_node_t* item) {
196 if (item->next != list)
197 return item->next;
198 else
199 return NULL;
200 }
201
202 #define list_next_type(list, item, type, element) \
203 ({ \
204 list_node_t* __nod = list_next(list, item); \
205 type* __t; \
206 if (__nod) \
207 __t = containerof(__nod, type, element); \
208 else \
209 __t = (type*)0; \
210 __t; \
211 })
212
list_next_wrap(list_node_t * list,list_node_t * item)213 static inline list_node_t* list_next_wrap(list_node_t* list, list_node_t* item) {
214 if (item->next != list)
215 return item->next;
216 else if (item->next->next != list)
217 return item->next->next;
218 else
219 return NULL;
220 }
221
222 #define list_next_wrap_type(list, item, type, element) \
223 ({ \
224 list_node_t* __nod = list_next_wrap(list, item); \
225 type* __t; \
226 if (__nod) \
227 __t = containerof(__nod, type, element); \
228 else \
229 __t = (type*)0; \
230 __t; \
231 })
232
233 // iterates over the list, node should be list_node_t*
234 #define list_for_every(list, node) for (node = (list)->next; node != (list); node = node->next)
235
236 // iterates over the list in a safe way for deletion of current node
237 // node and temp_node should be list_node_t*
238 #define list_for_every_safe(list, node, temp_node) \
239 for (node = (list)->next, temp_node = (node)->next; node != (list); \
240 node = temp_node, temp_node = (node)->next)
241
242 // iterates over the list, entry should be the container structure type *
243 #define list_for_every_entry(list, entry, type, member) \
244 for ((entry) = containerof((list)->next, type, member); &(entry)->member != (list); \
245 (entry) = containerof((entry)->member.next, type, member))
246
247 // iterates over the list in a safe way for deletion of current node
248 // entry and temp_entry should be the container structure type *
249 #define list_for_every_entry_safe(list, entry, temp_entry, type, member) \
250 for (entry = containerof((list)->next, type, member), \
251 temp_entry = containerof((entry)->member.next, type, member); \
252 &(entry)->member != (list); \
253 entry = temp_entry, temp_entry = containerof((temp_entry)->member.next, type, member))
254
list_is_empty(const list_node_t * list)255 static inline bool list_is_empty(const list_node_t* list) {
256 return (list->next == list) ? true : false;
257 }
258
list_length(const list_node_t * list)259 static inline size_t list_length(const list_node_t* list) {
260 size_t cnt = 0;
261 const list_node_t* node = list;
262 list_for_every(list, node) {
263 cnt++;
264 }
265
266 return cnt;
267 }
268
269 // Splice the contents of splice_from into the list immediately following pos.
list_splice_after(list_node_t * splice_from,list_node_t * pos)270 static inline void list_splice_after(list_node_t* splice_from, list_node_t* pos) {
271 if (list_is_empty(splice_from)) {
272 return;
273 }
274 splice_from->next->prev = pos;
275 splice_from->prev->next = pos->next;
276 pos->next->prev = splice_from->prev;
277 pos->next = splice_from->next;
278 list_initialize(splice_from);
279 }
280
281 // Split the contents of list after (but not including) pos, into split_to
282 // (which should be empty).
list_split_after(list_node_t * list,list_node_t * pos,list_node_t * split_to)283 static inline void list_split_after(list_node_t* list, list_node_t* pos,
284 list_node_t* split_to) {
285 if (pos->next == list) {
286 list_initialize(split_to);
287 return;
288 }
289 split_to->prev = list->prev;
290 split_to->prev->next = split_to;
291 split_to->next = pos->next;
292 split_to->next->prev = split_to;
293 pos->next = list;
294 list->prev = pos;
295 }
296
297 // Moves all the contents of old_list (which may or may not be empty)
298 // to new_list (which should be empty).
list_move(list_node_t * old_list,list_node_t * new_list)299 static inline void list_move(list_node_t* old_list, list_node_t* new_list) {
300 list_initialize(new_list);
301 list_splice_after(old_list, new_list);
302 }
303
304 __END_CDECLS;
305