1 /*
2 * Copyright (c) 2008 Travis Geiselbrecht
3 *
4 * Use of this source code is governed by a MIT-style
5 * license that can be found in the LICENSE file or at
6 * https://opensource.org/licenses/MIT
7 */
8 #pragma once
9
10 #include <lk/compiler.h>
11 #include <stdbool.h>
12 #include <stddef.h>
13
14 __BEGIN_CDECLS
15
16 #define containerof(ptr, type, member) \
17 ((type *)((addr_t)(ptr) - offsetof(type, member)))
18
19 struct list_node {
20 struct list_node *prev;
21 struct list_node *next;
22 };
23
24 #define LIST_INITIAL_VALUE(list) { &(list), &(list) }
25 #define LIST_INITIAL_CLEARED_VALUE { NULL, NULL }
26
list_initialize(struct list_node * list)27 static inline void list_initialize(struct list_node *list) {
28 list->prev = list->next = list;
29 }
30
list_clear_node(struct list_node * item)31 static inline void list_clear_node(struct list_node *item) {
32 item->prev = item->next = 0;
33 }
34
list_in_list(struct list_node * item)35 static inline bool list_in_list(struct list_node *item) {
36 if (item->prev == 0 && item->next == 0)
37 return false;
38 else
39 return true;
40 }
41
list_add_head(struct list_node * list,struct list_node * item)42 static inline void list_add_head(struct list_node *list, struct list_node *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(struct list_node * list,struct list_node * item)51 static inline void list_add_tail(struct list_node *list, struct list_node *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(struct list_node * item)60 static inline void list_delete(struct list_node *item) {
61 item->next->prev = item->prev;
62 item->prev->next = item->next;
63 item->prev = item->next = 0;
64 }
65
list_remove_head(struct list_node * list)66 static inline struct list_node *list_remove_head(struct list_node *list) {
67 if (list->next != list) {
68 struct list_node *item = list->next;
69 list_delete(item);
70 return item;
71 } else {
72 return NULL;
73 }
74 }
75
76 #define list_remove_head_type(list, type, element) ({\
77 struct list_node *__nod = list_remove_head(list);\
78 type *__t;\
79 if(__nod)\
80 __t = containerof(__nod, type, element);\
81 else\
82 __t = (type *)0;\
83 __t;\
84 })
85
list_remove_tail(struct list_node * list)86 static inline struct list_node *list_remove_tail(struct list_node *list) {
87 if (list->prev != list) {
88 struct list_node *item = list->prev;
89 list_delete(item);
90 return item;
91 } else {
92 return NULL;
93 }
94 }
95
96 #define list_remove_tail_type(list, type, element) ({\
97 struct list_node *__nod = list_remove_tail(list);\
98 type *__t;\
99 if(__nod)\
100 __t = containerof(__nod, type, element);\
101 else\
102 __t = (type *)0;\
103 __t;\
104 })
105
list_peek_head(struct list_node * list)106 static inline struct list_node *list_peek_head(struct list_node *list) {
107 if (list->next != list) {
108 return list->next;
109 } else {
110 return NULL;
111 }
112 }
113
114 #define list_peek_head_type(list, type, element) ({\
115 struct list_node *__nod = list_peek_head(list);\
116 type *__t;\
117 if(__nod)\
118 __t = containerof(__nod, type, element);\
119 else\
120 __t = (type *)0;\
121 __t;\
122 })
123
list_peek_tail(struct list_node * list)124 static inline struct list_node *list_peek_tail(struct list_node *list) {
125 if (list->prev != list) {
126 return list->prev;
127 } else {
128 return NULL;
129 }
130 }
131
132 #define list_peek_tail_type(list, type, element) ({\
133 struct list_node *__nod = list_peek_tail(list);\
134 type *__t;\
135 if(__nod)\
136 __t = containerof(__nod, type, element);\
137 else\
138 __t = (type *)0;\
139 __t;\
140 })
141
list_prev(struct list_node * list,struct list_node * item)142 static inline struct list_node *list_prev(struct list_node *list, struct list_node *item) {
143 if (item->prev != list)
144 return item->prev;
145 else
146 return NULL;
147 }
148
149 #define list_prev_type(list, item, type, element) ({\
150 struct list_node *__nod = list_prev(list, item);\
151 type *__t;\
152 if(__nod)\
153 __t = containerof(__nod, type, element);\
154 else\
155 __t = (type *)0;\
156 __t;\
157 })
158
list_prev_wrap(struct list_node * list,struct list_node * item)159 static inline struct list_node *list_prev_wrap(struct list_node *list, struct list_node *item) {
160 if (item->prev != list)
161 return item->prev;
162 else if (item->prev->prev != list)
163 return item->prev->prev;
164 else
165 return NULL;
166 }
167
168 #define list_prev_wrap_type(list, item, type, element) ({\
169 struct list_node *__nod = list_prev_wrap(list, item);\
170 type *__t;\
171 if(__nod)\
172 __t = containerof(__nod, type, element);\
173 else\
174 __t = (type *)0;\
175 __t;\
176 })
177
list_next(struct list_node * list,struct list_node * item)178 static inline struct list_node *list_next(struct list_node *list, struct list_node *item) {
179 if (item->next != list)
180 return item->next;
181 else
182 return NULL;
183 }
184
185 #define list_next_type(list, item, type, element) ({\
186 struct list_node *__nod = list_next(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_wrap(struct list_node * list,struct list_node * item)195 static inline struct list_node *list_next_wrap(struct list_node *list, struct list_node *item) {
196 if (item->next != list)
197 return item->next;
198 else if (item->next->next != list)
199 return item->next->next;
200 else
201 return NULL;
202 }
203
204 #define list_next_wrap_type(list, item, type, element) ({\
205 struct list_node *__nod = list_next_wrap(list, item);\
206 type *__t;\
207 if(__nod)\
208 __t = containerof(__nod, type, element);\
209 else\
210 __t = (type *)0;\
211 __t;\
212 })
213
214 // iterates over the list, node should be struct list_node*
215 #define list_for_every(list, node) \
216 for(node = (list)->next; node != (list); node = node->next)
217
218 // iterates over the list in a safe way for deletion of current node
219 // node and temp_node should be struct list_node*
220 #define list_for_every_safe(list, node, temp_node) \
221 for(node = (list)->next, temp_node = (node)->next;\
222 node != (list);\
223 node = temp_node, temp_node = (node)->next)
224
225 // iterates over the list, entry should be the container structure type *
226 #define list_for_every_entry(list, entry, type, member) \
227 for((entry) = containerof((list)->next, type, member);\
228 &(entry)->member != (list);\
229 (entry) = containerof((entry)->member.next, type, member))
230
231 // iterates over the list in a safe way for deletion of current node
232 // entry and temp_entry should be the container structure type *
233 #define list_for_every_entry_safe(list, entry, temp_entry, type, member) \
234 for(entry = containerof((list)->next, type, member),\
235 temp_entry = containerof((entry)->member.next, type, member);\
236 &(entry)->member != (list);\
237 entry = temp_entry, temp_entry = containerof((temp_entry)->member.next, type, member))
238
list_is_empty(struct list_node * list)239 static inline bool list_is_empty(struct list_node *list) {
240 return (list->next == list) ? true : false;
241 }
242
list_length(struct list_node * list)243 static inline size_t list_length(struct list_node *list) {
244 size_t cnt = 0;
245 struct list_node *node = list;
246 list_for_every(list, node) {
247 cnt++;
248 }
249
250 return cnt;
251 }
252
253 __END_CDECLS
254