Debian Codegraph @

third_party/c-list/src/c-list.h

raw
1 #pragma once
2
3 /*
4 * Circular Intrusive Double Linked List Collection in ISO-C11
5 *
6 * This implements a generic circular double linked list. List entries must
7 * embed the CList object, which provides pointers to the next and previous
8 * element. Insertion and removal can be done in O(1) due to the double links.
9 * Furthermore, the list is circular, thus allows access to front/tail in O(1)
10 * as well, even if you only have a single head pointer (which is not how the
11 * list is usually operated, though).
12 *
13 * Note that you are free to use the list implementation without a head
14 * pointer. However, usual operation uses a single CList object as head, which
15 * is itself linked in the list and as such must be identified as list head.
16 * This allows very simply list operations and avoids a lot of special cases.
17 * Most importantly, you can unlink entries without requiring a head pointer.
18 */
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24 #include <stddef.h>
25 #include <stdint.h>
26
27 typedef struct CList CList;
28
29 /**
30 * struct CList - Entry of a circular double linked list
31 * @next: next entry
32 * @prev: previous entry
33 *
34 * Each entry in a list must embed a CList object. This object contains
35 * pointers to its next and previous elements, which can be freely accessed by
36 * the API user at any time. Note that the list is circular, and the list head
37 * is linked in the list as well.
38 *
39 * The list head must be initialized via C_LIST_INIT before use. There is no
40 * reason to initialize entry objects before linking them. However, if you need
41 * a boolean state that tells you whether the entry is linked or not, you should
42 * initialize the entry via C_LIST_INIT as well.
43 */
44 struct CList {
45 CList *next;
46 CList *prev;
47 };
48
49 #define C_LIST_INIT(_var) { .next = &(_var), .prev = &(_var) }
50
51 /**
52 * c_list_init() - initialize list entry
53 * @what: list entry to initialize
54 *
55 * Return: @what is returned.
56 */
57 static inline CList *c_list_init(CList *what) {
58 *what = (CList)C_LIST_INIT(*what);
59 return what;
60 }
61
62 /**
63 * c_list_entry_offset() - get parent container of list entry
64 * @what: list entry, or NULL
65 * @offset: offset of the list member in its surrounding type
66 *
67 * If the list entry @what is embedded into a surrounding structure, this will
68 * turn the list entry pointer @what into a pointer to the parent container
69 * (sometimes called container_of(3)). Use the `c_list_entry()` macro for an
70 * easier API.
71 *
72 * If @what is NULL, this will also return NULL.
73 *
74 * Return: Pointer to parent container, or NULL.
75 */
76 static inline void *c_list_entry_offset(const CList *what, size_t offset) {
77 if (what) {
78 /*
79 * We allow calling "c_list_entry()" on the list head, which is
80 * commonly a plain CList struct. The returned entry pointer is
81 * thus invalid. For instance, this is used by the
82 * c_list_for_each_entry*() macros. Gcc correctly warns about that
83 * with "-Warray-bounds". However, as long as the value is never
84 * dereferenced, this is fine. We explicitly use integer arithmetic
85 * to circumvent the Gcc warning.
86 */
87 return (void *)(((uintptr_t)(void *)what) - offset);
88 }
89 return NULL;
90 }
91
92 /**
93 * c_list_entry() - get parent container of list entry
94 * @_what: list entry, or NULL
95 * @_t: type of parent container
96 * @_m: member name of list entry in @_t
97 *
98 * If the list entry @_what is embedded into a surrounding structure, this will
99 * turn the list entry pointer @_what into a pointer to the parent container
100 * (using offsetof(3), or sometimes called container_of(3)).
101 *
102 * If @_what is NULL, this will also return NULL.
103 *
104 * Return: Pointer to parent container, or NULL.
105 */
106 #define c_list_entry(_what, _t, _m) \
107 ((_t *)c_list_entry_offset((_what), offsetof(_t, _m)))
108
109 /**
110 * c_list_is_linked() - check whether an entry is linked
111 * @what: entry to check, or NULL
112 *
113 * Return: True if @what is linked in a list, false if not.
114 */
115 static inline _Bool c_list_is_linked(const CList *what) {
116 return what && what->next != what;
117 }
118
119 /**
120 * c_list_is_empty() - check whether a list is empty
121 * @list: list to check, or NULL
122 *
123 * This is the same as !c_list_is_linked().
124 *
125 * Return: True if @list is empty, false if not.
126 */
127 static inline _Bool c_list_is_empty(const CList *list) {
128 return !c_list_is_linked(list);
129 }
130
131 /**
132 * c_list_link_before() - link entry into list
133 * @where: linked list entry used as anchor
134 * @what: entry to link
135 *
136 * This links @what directly in front of @where. @where can either be a list
137 * head or any entry in the list.
138 *
139 * If @where points to the list head, this effectively links @what as new tail
140 * element. Hence, the macro c_list_link_tail() is an alias to this.
141 *
142 * @what is not inspected prior to being linked. Hence, it better not be linked
143 * into another list, or the other list will be corrupted.
144 */
145 static inline void c_list_link_before(CList *where, CList *what) {
146 CList *prev = where->prev, *next = where;
147
148 next->prev = what;
149 what->next = next;
150 what->prev = prev;
151 prev->next = what;
152 }
153 #define c_list_link_tail(_list, _what) c_list_link_before((_list), (_what))
154
155 /**
156 * c_list_link_after() - link entry into list
157 * @where: linked list entry used as anchor
158 * @what: entry to link
159 *
160 * This links @what directly after @where. @where can either be a list head or
161 * any entry in the list.
162 *
163 * If @where points to the list head, this effectively links @what as new front
164 * element. Hence, the macro c_list_link_front() is an alias to this.
165 *
166 * @what is not inspected prior to being linked. Hence, it better not be linked
167 * into another list, or the other list will be corrupted.
168 */
169 static inline void c_list_link_after(CList *where, CList *what) {
170 CList *prev = where, *next = where->next;
171
172 next->prev = what;
173 what->next = next;
174 what->prev = prev;
175 prev->next = what;
176 }
177 #define c_list_link_front(_list, _what) c_list_link_after((_list), (_what))
178
179 /**
180 * c_list_unlink_stale() - unlink element from list
181 * @what: element to unlink
182 *
183 * This unlinks @what. If @what was initialized via C_LIST_INIT(), it has no
184 * effect. If @what was never linked, nor initialized, behavior is undefined.
185 *
186 * Note that this does not modify @what. It just modifies the previous and next
187 * elements in the list to no longer reference @what. If you want to make sure
188 * @what is re-initialized after removal, use c_list_unlink().
189 */
190 static inline void c_list_unlink_stale(CList *what) {
191 CList *prev = what->prev, *next = what->next;
192
193 next->prev = prev;
194 prev->next = next;
195 }
196
197 /**
198 * c_list_unlink() - unlink element from list and re-initialize
199 * @what: element to unlink
200 *
201 * This is like c_list_unlink_stale() but re-initializes @what after removal.
202 */
203 static inline void c_list_unlink(CList *what) {
204 /* condition is not needed, but avoids STOREs in fast-path */
205 if (c_list_is_linked(what)) {
206 c_list_unlink_stale(what);
207 *what = (CList)C_LIST_INIT(*what);
208 }
209 }
210
211 /**
212 * c_list_swap() - exchange the contents of two lists
213 * @list1: the list to operate on
214 * @list2: the list to operate on
215 *
216 * This replaces the contents of the list @list1 with the contents
217 * of @list2, and vice versa.
218 */
219 static inline void c_list_swap(CList *list1, CList *list2) {
220 CList t;
221
222 /* make neighbors of list1 point to list2, and vice versa */
223 t = *list1;
224 t.next->prev = list2;
225 t.prev->next = list2;
226 t = *list2;
227 t.next->prev = list1;
228 t.prev->next = list1;
229
230 /* swap list1 and list2 now that their neighbors were fixed up */
231 t = *list1;
232 *list1 = *list2;
233 *list2 = t;
234 }
235
236 /**
237 * c_list_splice() - splice one list into another
238 * @target: the list to splice into
239 * @source: the list to splice
240 *
241 * This removes all the entries from @source and splice them into @target.
242 * The order of the two lists is preserved and the source is appended
243 * to the end of target.
244 *
245 * On return, the source list will be empty.
246 */
247 static inline void c_list_splice(CList *target, CList *source) {
248 if (!c_list_is_empty(source)) {
249 /* attach the front of @source to the tail of @target */
250 source->next->prev = target->prev;
251 target->prev->next = source->next;
252
253 /* attach the tail of @source to the front of @target */
254 source->prev->next = target;
255 target->prev = source->prev;
256
257 /* clear source */
258 *source = (CList)C_LIST_INIT(*source);
259 }
260 }
261
262 /**
263 * c_list_split() - split one list in two
264 * @source: the list to split
265 * @where: new starting element of newlist
266 * @target: new list
267 *
268 * This splits @source in two. All elements following @where (including @where)
269 * are moved to @target, replacing any old list. If @where points to @source
270 * (i.e., the end of the list), @target will be empty.
271 */
272 static inline void c_list_split(CList *source, CList *where, CList *target) {
273 if (where == source) {
274 *target = (CList)C_LIST_INIT(*target);
275 } else {
276 target->next = where;
277 target->prev = source->prev;
278
279 where->prev->next = source;
280 source->prev = where->prev;
281
282 where->prev = target;
283 target->prev->next = target;
284 }
285 }
286
287 /**
288 * c_list_first() - return pointer to first element, or NULL if empty
289 * @list: list to operate on, or NULL
290 *
291 * This returns a pointer to the first element, or NULL if empty. This never
292 * returns a pointer to the list head.
293 *
294 * Return: Pointer to first list element, or NULL if empty.
295 */
296 static inline CList *c_list_first(CList *list) {
297 return c_list_is_empty(list) ? NULL : list->next;
298 }
299
300 /**
301 * c_list_last() - return pointer to last element, or NULL if empty
302 * @list: list to operate on, or NULL
303 *
304 * This returns a pointer to the last element, or NULL if empty. This never
305 * returns a pointer to the list head.
306 *
307 * Return: Pointer to last list element, or NULL if empty.
308 */
309 static inline CList *c_list_last(CList *list) {
310 return c_list_is_empty(list) ? NULL : list->prev;
311 }
312
313 /**
314 * c_list_first_entry() - return pointer to first entry, or NULL if empty
315 * @_list: list to operate on, or NULL
316 * @_t: type of list entries
317 * @_m: name of CList member in @_t
318 *
319 * This is like c_list_first(), but also applies c_list_entry() on the result.
320 *
321 * Return: Pointer to first list entry, or NULL if empty.
322 */
323 #define c_list_first_entry(_list, _t, _m) \
324 c_list_entry(c_list_first(_list), _t, _m)
325
326 /**
327 * c_list_last_entry() - return pointer to last entry, or NULL if empty
328 * @_list: list to operate on, or NULL
329 * @_t: type of list entries
330 * @_m: name of CList member in @_t
331 *
332 * This is like c_list_last(), but also applies c_list_entry() on the result.
333 *
334 * Return: Pointer to last list entry, or NULL if empty.
335 */
336 #define c_list_last_entry(_list, _t, _m) \
337 c_list_entry(c_list_last(_list), _t, _m)
338
339 /**
340 * c_list_for_each*() - iterators
341 *
342 * The c_list_for_each*() macros provide simple for-loop wrappers to iterate
343 * a linked list. They come in a set of flavours:
344 *
345 * - "entry": This combines c_list_entry() with the loop iterator, so the
346 * iterator always has the type of the surrounding object, rather
347 * than CList.
348 *
349 * - "safe": The loop iterator always keeps track of the next element to
350 * visit. This means, you can safely modify the current element,
351 * while retaining loop-integrity.
352 * You still must not touch any other entry of the list. Otherwise,
353 * the loop-iterator will be corrupted.
354 *
355 * - "continue": Rather than starting the iteration at the front of the list,
356 * use the current value of the iterator as starting position.
357 * Note that the first loop iteration will be the following
358 * element, not the given element.
359 *
360 * - "unlink": This unlinks the current element from the list before the loop
361 * code is run. Note that this only does a partial unlink, since
362 * it assumes the entire list will be unlinked. You must not
363 * break out of the loop, or the list will be in an inconsistent
364 * state.
365 */
366
367 /* direct/raw iterators */
368
369 #define c_list_for_each(_iter, _list) \
370 for (_iter = (_list)->next; \
371 (_iter) != (_list); \
372 _iter = (_iter)->next)
373
374 #define c_list_for_each_safe(_iter, _safe, _list) \
375 for (_iter = (_list)->next, _safe = (_iter)->next; \
376 (_iter) != (_list); \
377 _iter = (_safe), _safe = (_safe)->next)
378
379 #define c_list_for_each_continue(_iter, _list) \
380 for (_iter = (_iter) ? (_iter)->next : (_list)->next; \
381 (_iter) != (_list); \
382 _iter = (_iter)->next)
383
384 #define c_list_for_each_safe_continue(_iter, _safe, _list) \
385 for (_iter = (_iter) ? (_iter)->next : (_list)->next, \
386 _safe = (_iter)->next; \
387 (_iter) != (_list); \
388 _iter = (_safe), _safe = (_safe)->next)
389
390 #define c_list_for_each_safe_unlink(_iter, _safe, _list) \
391 for (_iter = (_list)->next, _safe = (_iter)->next; \
392 c_list_init(_iter) != (_list); \
393 _iter = (_safe), _safe = (_safe)->next)
394
395 /* c_list_entry() based iterators */
396
397 #define c_list_for_each_entry(_iter, _list, _m) \
398 for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m); \
399 &(_iter)->_m != (_list); \
400 _iter = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m))
401
402 #define c_list_for_each_entry_safe(_iter, _safe, _list, _m) \
403 for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m), \
404 _safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m); \
405 &(_iter)->_m != (_list); \
406 _iter = (_safe), \
407 _safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m))
408
409 #define c_list_for_each_entry_continue(_iter, _list, _m) \
410 for (_iter = c_list_entry((_iter) ? (_iter)->_m.next : (_list)->next, \
411 __typeof__(*_iter), \
412 _m); \
413 &(_iter)->_m != (_list); \
414 _iter = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m))
415
416 #define c_list_for_each_entry_safe_continue(_iter, _safe, _list, _m) \
417 for (_iter = c_list_entry((_iter) ? (_iter)->_m.next : (_list)->next, \
418 __typeof__(*_iter), \
419 _m), \
420 _safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m); \
421 &(_iter)->_m != (_list); \
422 _iter = (_safe), \
423 _safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m))
424
425 #define c_list_for_each_entry_safe_unlink(_iter, _safe, _list, _m) \
426 for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m), \
427 _safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m); \
428 c_list_init(&(_iter)->_m) != (_list); \
429 _iter = (_safe), \
430 _safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m))
431
432 /**
433 * c_list_flush() - flush all entries from a list
434 * @list: list to flush
435 *
436 * This unlinks all entries from the given list @list and reinitializes their
437 * link-nodes via C_LIST_INIT().
438 *
439 * Note that the entries are not modified in any other way, nor is their memory
440 * released. This function just unlinks them and resets all the list nodes. It
441 * is particularly useful with temporary lists on the stack in combination with
442 * the GCC-extension __attribute__((__cleanup__(arg))).
443 */
444 static inline void c_list_flush(CList *list) {
445 CList *iter, *safe;
446
447 c_list_for_each_safe_unlink(iter, safe, list)
448 /* empty */ ;
449 }
450
451 /**
452 * c_list_length() - return number of linked entries, excluding the head
453 * @list: list to operate on
454 *
455 * Returns the number of entries in the list, excluding the list head @list.
456 * That is, for a list that is empty according to c_list_is_empty(), the
457 * returned length is 0. This requires to iterate the list and has thus O(n)
458 * runtime.
459 *
460 * Note that this function is meant for debugging purposes only. If you need
461 * the list size during normal operation, you should maintain a counter
462 * separately.
463 *
464 * Return: Number of items in @list.
465 */
466 static inline size_t c_list_length(const CList *list) {
467 size_t n = 0;
468 const CList *iter;
469
470 c_list_for_each(iter, list)
471 ++n;
472
473 return n;
474 }
475
476 /**
477 * c_list_contains() - check whether an entry is linked in a certain list
478 * @list: list to operate on
479 * @what: entry to look for
480 *
481 * This checks whether @what is linked into @list. This requires a linear
482 * search through the list, as such runs in O(n). Note that the list-head is
483 * considered part of the list, and hence this returns true if @what equals
484 * @list.
485 *
486 * Note that this function is meant for debugging purposes, and consistency
487 * checks. You should always be aware whether your objects are linked in a
488 * specific list.
489 *
490 * Return: True if @what is in @list, false otherwise.
491 */
492 static inline _Bool c_list_contains(const CList *list, const CList *what) {
493 const CList *iter;
494
495 c_list_for_each(iter, list)
496 if (what == iter)
497 return 1;
498
499 return what == list;
500 }
501
502 #ifdef __cplusplus
503 }
504 #endif