1 /*
2 * Copyright (C) 2013 Kim Woelders
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies of the Software, its documentation and marketing & publicity
13 * materials, and acknowledgment shall be given in the documentation, materials
14 * and software packages that this Software was used.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
20 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 */
23 #ifndef LIST_H
24 #define LIST_H
25
26 #include <stddef.h>
27
28 typedef struct _dlist_t dlist_t;
29
30 struct _dlist_t {
31 struct _dlist_t *next, *prev;
32 };
33
34 #define dlist_for_each(head, elem) \
35 for (elem = (head)->next; elem != (head); elem = elem->next)
36
37 #define dlist_for_each_safe(head, elem, temp) \
38 for (elem = (head)->next, temp = elem->next; elem != (head); elem = temp, temp = elem->next)
39
40 static inline void
dlist_init(dlist_t * head)41 dlist_init(dlist_t * head)
42 {
43 head->next = head->prev = head;
44 }
45
46 static inline void
_dlist_insert(dlist_t * elem,dlist_t * prev,dlist_t * next)47 _dlist_insert(dlist_t * elem, dlist_t * prev, dlist_t * next)
48 {
49 next->prev = elem;
50 elem->next = next;
51 elem->prev = prev;
52 prev->next = elem;
53 }
54
55 static inline void
dlist_append(dlist_t * head,dlist_t * elem)56 dlist_append(dlist_t * head, dlist_t * elem)
57 {
58 _dlist_insert(elem, head->prev, head);
59 }
60
61 static inline void
dlist_prepend(dlist_t * head,dlist_t * elem)62 dlist_prepend(dlist_t * head, dlist_t * elem)
63 {
64 _dlist_insert(elem, head, head->next);
65 }
66
67 static inline void
_dlist_remove(dlist_t * prev,dlist_t * next)68 _dlist_remove(dlist_t * prev, dlist_t * next)
69 {
70 next->prev = prev;
71 prev->next = next;
72 }
73
74 static inline dlist_t *
dlist_remove(dlist_t * elem)75 dlist_remove(dlist_t * elem)
76 {
77 if (elem)
78 _dlist_remove(elem->prev, elem->next);
79
80 return elem;
81 }
82
83 static inline int
dlist_is_empty(const dlist_t * head)84 dlist_is_empty(const dlist_t * head)
85 {
86 return head->next == head;
87 }
88
89 static inline unsigned int
dlist_get_count(const dlist_t * head)90 dlist_get_count(const dlist_t * head)
91 {
92 unsigned int count = 0;
93 dlist_t *e;
94
95 dlist_for_each(head, e)
96 {
97 count++;
98 }
99
100 return count;
101 }
102
103 #define LIST_NOINLINE_dlist_find 0
104
105 typedef int (dlist_match_func_t) (const void *elem, const void *prm);
106
107 #if LIST_NOINLINE_dlist_find
108 dlist_t *dlist_find(const dlist_t * head,
109 dlist_match_func_t * match, const void *prm);
110 #else
111 static inline dlist_t *
dlist_find(const dlist_t * head,dlist_match_func_t * match,const void * prm)112 dlist_find(const dlist_t * head, dlist_match_func_t * match, const void *prm)
113 {
114 dlist_t *e;
115
116 dlist_for_each(head, e)
117 {
118 if (match(e, prm) == 0)
119 return e;
120 }
121
122 return NULL;
123 }
124 #endif
125
126 #define LIST_NOINLINE_dlist_for_each_func 0
127
128 typedef void (dlist_foreach_func_t) (void *elem, void *prm);
129
130 #if LIST_NOINLINE_dlist_for_each_func
131 void dlist_for_each_func(dlist_t * head,
132 dlist_foreach_func_t * func, void *prm);
133 #else
134 static inline void
dlist_for_each_func(dlist_t * head,dlist_foreach_func_t * func,void * prm)135 dlist_for_each_func(dlist_t * head, dlist_foreach_func_t * func, void *prm)
136 {
137 dlist_t *e, *tmp;
138
139 dlist_for_each_safe(head, e, tmp)
140 {
141 func(e, prm);
142 }
143 }
144 #endif
145
146 static inline dlist_t *
dlist_check(const dlist_t * head,dlist_t * elem)147 dlist_check(const dlist_t * head, dlist_t * elem)
148 {
149 dlist_t *e;
150
151 dlist_for_each(head, e)
152 {
153 if (e == elem)
154 return e;
155 }
156
157 return NULL;
158 }
159
160 #define LIST_NOINLINE_dlist_get_index 0
161
162 #if LIST_NOINLINE_dlist_get_index
163 int dlist_get_index(const dlist_t * head, dlist_t * elem);
164 #else
165 static inline int
dlist_get_index(const dlist_t * head,dlist_t * elem)166 dlist_get_index(const dlist_t * head, dlist_t * elem)
167 {
168 const dlist_t *e;
169 int i;
170
171 i = 0;
172 dlist_for_each(head, e)
173 {
174 if (e == elem)
175 return i;
176 i++;
177 }
178
179 return -1;
180 }
181 #endif
182
183 #define LIST_NOINLINE_dlist_get_by_index 0
184
185 #if LIST_NOINLINE_dlist_get_by_index
186 dlist_t *dlist_get_by_index(const dlist_t * head, int ix);
187 #else
188 static inline dlist_t *
dlist_get_by_index(const dlist_t * head,int ix)189 dlist_get_by_index(const dlist_t * head, int ix)
190 {
191 dlist_t *etmp;
192 int i;
193
194 i = 0;
195 dlist_for_each(head, etmp)
196 {
197 if (i == ix)
198 return etmp;
199 i++;
200 }
201
202 return NULL;
203 }
204 #endif
205
206 #define LIST_NOINLINE_dlist_get_items 1
207
208 #if LIST_NOINLINE_dlist_get_items
209 dlist_t **dlist_get_items(const dlist_t * head, int *pnum);
210 #else
211 static inline dlist_t **
dlist_get_items(const dlist_t * head,int * pnum)212 dlist_get_items(const dlist_t * head, int *pnum)
213 {
214 dlist_t *etmp;
215 dlist_t **lst;
216 int i, num;
217
218 lst = NULL;
219 num = dlist_get_count(head);
220 if (num <= 0)
221 goto done;
222 lst = (dlist_t **) malloc(num * sizeof(void *));
223
224 i = 0;
225 dlist_for_each(head, etmp)
226 {
227 lst[i++] = etmp;
228 }
229
230 done:
231 *pnum = num;
232 return lst;
233 }
234 #endif
235
236 #define LIST_HEAD(head) \
237 dlist_t head = { &head, &head }
238
239 #define LIST_INIT(type, head) \
240 dlist_init(head)
241
242 #define LIST_APPEND(type, head, elem) \
243 dlist_append(head, &((elem)->list))
244
245 #define LIST_PREPEND(type, head, elem) \
246 dlist_prepend(head, &((elem)->list))
247
248 #define LIST_REMOVE(type, head, elem) \
249 (type*)dlist_remove(&((elem)->list))
250
251 #define LIST_FIND(type, head, func, prm) \
252 (type*)dlist_find(head, func, prm)
253
254 #define LIST_CHECK(type, head, elem) \
255 (type*)dlist_check(head, &((elem)->list))
256
257 #define LIST_GET_INDEX(type, head, elem) \
258 dlist_get_index(head, &((elem)->list))
259
260 #define LIST_GET_BY_INDEX(type, head, ix) \
261 (type*)dlist_get_by_index(head, ix)
262
263 #define LIST_IS_EMPTY(head) \
264 dlist_is_empty(head)
265
266 #define LIST_GET_COUNT(head) \
267 dlist_get_count(head)
268
269 #define LIST_NEXT(type, head, elem) \
270 ((elem->list.next != head) ? (type*)(elem)->list.next : NULL)
271
272 #define LIST_PREV(type, head, elem) \
273 ((elem->list.prev != head) ? (type*)(elem)->list.prev : NULL)
274
275 #define LIST_GET_ITEMS(type, head, pnum) \
276 (type**)dlist_get_items(head, pnum)
277
278 #define LIST_FOR_EACH(type, head, elem) \
279 for (elem = (type*)((head)->next); \
280 &(elem)->list != (head); \
281 elem = (type*)((elem)->list.next))
282
283 #define LIST_FOR_EACH_REV(type, head, elem) \
284 for (elem = (type*)((head)->prev); \
285 &(elem)->list != (head); \
286 elem = (type*)((elem)->list.prev))
287
288 #define LIST_FOR_EACH_SAFE(type, head, elem, temp) \
289 for (elem = (type*)((head)->next), temp = (type*)((elem)->list.next); \
290 &(elem)->list != (head); \
291 elem = temp, temp = (type*)((elem)->list.next))
292
293 #define LIST_FOR_EACH_FUNC(type, head, func, prm) \
294 dlist_for_each_func(head, func, prm)
295
296 #endif /* LIST_H */
297