Lely core libraries 2.3.4
dllist.h
Go to the documentation of this file.
1
23#ifndef LELY_UTIL_DLLIST_H_
24#define LELY_UTIL_DLLIST_H_
25
26#include <lely/features.h>
27
28#include <assert.h>
29#include <stddef.h>
30
31#ifndef LELY_UTIL_DLLIST_INLINE
32#define LELY_UTIL_DLLIST_INLINE static inline
33#endif
34
40struct dlnode {
42 struct dlnode *prev;
44 struct dlnode *next;
45};
46
48#define DLNODE_INIT \
49 { \
50 NULL, NULL \
51 }
52
54struct dllist {
56 struct dlnode *first;
58 struct dlnode *last;
59};
60
62#define DLLIST_INIT \
63 { \
64 NULL, NULL \
65 }
66
67#ifdef __cplusplus
68extern "C" {
69#endif
70
72LELY_UTIL_DLLIST_INLINE void dlnode_init(struct dlnode *node);
73
79LELY_UTIL_DLLIST_INLINE int dlnode_insert_after(
80 struct dlnode *prev, struct dlnode *node);
81
87LELY_UTIL_DLLIST_INLINE int dlnode_insert_before(
88 struct dlnode *next, struct dlnode *node);
89
94LELY_UTIL_DLLIST_INLINE void dlnode_remove(struct dlnode *node);
95
104#ifdef __COUNTER__
105#define dlnode_foreach(first, node) dlnode_foreach_(__COUNTER__, first, node)
106#else
107#define dlnode_foreach(first, node) dlnode_foreach_(__LINE__, first, node)
108#endif
109#define dlnode_foreach_(n, first, node) dlnode_foreach__(n, first, node)
110// clang-format off
111#define dlnode_foreach__(n, first, node) \
112 for (struct dlnode *node = (first), \
113 *_dlnode_next_##n = (node) ? (node)->next : NULL; \
114 (node); (node) = _dlnode_next_##n, \
115 _dlnode_next_##n = (node) ? (node)->next : NULL)
116// clang-format on
117
119LELY_UTIL_DLLIST_INLINE void dllist_init(struct dllist *list);
120
125LELY_UTIL_DLLIST_INLINE int dllist_empty(const struct dllist *list);
126
131LELY_UTIL_DLLIST_INLINE size_t dllist_size(const struct dllist *list);
132
139LELY_UTIL_DLLIST_INLINE void dllist_push_front(
140 struct dllist *list, struct dlnode *node);
141
147LELY_UTIL_DLLIST_INLINE void dllist_push_back(
148 struct dllist *list, struct dlnode *node);
149
156LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_front(struct dllist *list);
157
163LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_back(struct dllist *list);
164
171LELY_UTIL_DLLIST_INLINE void dllist_insert_after(
172 struct dllist *list, struct dlnode *prev, struct dlnode *node);
173
180LELY_UTIL_DLLIST_INLINE void dllist_insert_before(
181 struct dllist *list, struct dlnode *next, struct dlnode *node);
182
189LELY_UTIL_DLLIST_INLINE void dllist_remove(
190 struct dllist *list, struct dlnode *node);
191
197int dllist_contains(const struct dllist *list, const struct dlnode *node);
198
205LELY_UTIL_DLLIST_INLINE struct dllist *dllist_append(
206 struct dllist *dst, struct dllist *src);
207
214LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_first(const struct dllist *list);
215
222LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_last(const struct dllist *list);
223
232#define dllist_foreach(list, node) dlnode_foreach (dllist_first(list), node)
233
234LELY_UTIL_DLLIST_INLINE void
235dlnode_init(struct dlnode *node)
236{
237 assert(node);
238
239 node->prev = NULL;
240 node->next = NULL;
241}
242
243LELY_UTIL_DLLIST_INLINE int
244dlnode_insert_after(struct dlnode *prev, struct dlnode *node)
245{
246 assert(prev);
247 assert(node);
248
249 node->prev = prev;
250 if ((node->next = prev->next) != NULL)
251 node->next->prev = node;
252 prev->next = node;
253 return !node->next;
254}
255
256LELY_UTIL_DLLIST_INLINE int
258{
259 assert(next);
260 assert(node);
261
262 node->next = next;
263 if ((node->prev = next->prev) != NULL)
264 node->prev->next = node;
265 next->prev = node;
266 return !node->prev;
267}
268
269LELY_UTIL_DLLIST_INLINE void
271{
272 assert(node);
273
274 if (node->prev)
275 node->prev->next = node->next;
276 if (node->next)
277 node->next->prev = node->prev;
278}
279
280LELY_UTIL_DLLIST_INLINE void
281dllist_init(struct dllist *list)
282{
283 assert(list);
284
285 list->first = NULL;
286 list->last = NULL;
287}
288
289LELY_UTIL_DLLIST_INLINE int
290dllist_empty(const struct dllist *list)
291{
292 assert(list);
293
294 return !list->first;
295}
296
297LELY_UTIL_DLLIST_INLINE size_t
298dllist_size(const struct dllist *list)
299{
300 assert(list);
301
302 size_t size = 0;
303 dllist_foreach (list, node)
304 size++;
305 return size;
306}
307
308LELY_UTIL_DLLIST_INLINE void
309dllist_push_front(struct dllist *list, struct dlnode *node)
310{
311 assert(list);
312 assert(node);
313
314 node->prev = NULL;
315 if ((node->next = list->first))
316 node->next->prev = node;
317 else
318 list->last = node;
319 list->first = node;
320}
321
322LELY_UTIL_DLLIST_INLINE void
323dllist_push_back(struct dllist *list, struct dlnode *node)
324{
325 assert(list);
326 assert(node);
327
328 node->next = NULL;
329 if ((node->prev = list->last))
330 node->prev->next = node;
331 else
332 list->first = node;
333 list->last = node;
334}
335
336LELY_UTIL_DLLIST_INLINE struct dlnode *
338{
339 assert(list);
340
341 struct dlnode *node = list->first;
342 if (list->first) {
343 if ((list->first = list->first->next))
344 list->first->prev = NULL;
345 else
346 list->last = NULL;
347 }
348 return node;
349}
350
351LELY_UTIL_DLLIST_INLINE struct dlnode *
353{
354 assert(list);
355
356 struct dlnode *node = list->last;
357 if (list->last) {
358 if ((list->last = list->last->prev))
359 list->last->next = NULL;
360 else
361 list->first = NULL;
362 }
363 return node;
364}
365
366LELY_UTIL_DLLIST_INLINE void
368 struct dllist *list, struct dlnode *prev, struct dlnode *node)
369{
370 assert(list);
371
372 if (dlnode_insert_after(prev, node))
373 list->last = node;
374}
375
376LELY_UTIL_DLLIST_INLINE void
378 struct dllist *list, struct dlnode *next, struct dlnode *node)
379{
380 assert(list);
381
382 if (dlnode_insert_before(next, node))
383 list->first = node;
384}
385
386LELY_UTIL_DLLIST_INLINE void
387dllist_remove(struct dllist *list, struct dlnode *node)
388{
389 assert(list);
390 assert(node);
391
392 if (!node->prev)
393 list->first = node->next;
394 if (!node->next)
395 list->last = node->prev;
396 dlnode_remove(node);
397}
398
399LELY_UTIL_DLLIST_INLINE struct dllist *
400dllist_append(struct dllist *dst, struct dllist *src)
401{
402 assert(dst);
403 assert(src);
404
405 if (src->first) {
406 if (dst->first) {
407 src->first->prev = dst->last;
408 dst->last->next = src->first;
409 dst->last = src->last;
410 } else {
411 dst->first = src->first;
412 dst->last = src->last;
413 }
414 dllist_init(src);
415 }
416 return dst;
417}
418
419LELY_UTIL_DLLIST_INLINE struct dlnode *
420dllist_first(const struct dllist *list)
421{
422 assert(list);
423
424 return list->first;
425}
426
427LELY_UTIL_DLLIST_INLINE struct dlnode *
428dllist_last(const struct dllist *list)
429{
430 assert(list);
431
432 return list->last;
433}
434
435#ifdef __cplusplus
436}
437#endif
438
439#endif // !LELY_UTIL_DLLIST_H_
void dlnode_remove(struct dlnode *node)
Removes node from a doubly-list.
Definition: dllist.h:270
void dllist_push_back(struct dllist *list, struct dlnode *node)
Pushes a node to the back of a doubly-linked list.
Definition: dllist.h:323
int dlnode_insert_before(struct dlnode *next, struct dlnode *node)
Inserts node before next.
Definition: dllist.h:257
struct dlnode * dllist_pop_back(struct dllist *list)
Pops a node from the back of a doubly-linked list.
Definition: dllist.h:352
void dllist_init(struct dllist *list)
Initializes a doubly-linked list.
Definition: dllist.h:281
void dllist_insert_after(struct dllist *list, struct dlnode *prev, struct dlnode *node)
Inserts a node into a doubly-linked list.
Definition: dllist.h:367
int dlnode_insert_after(struct dlnode *prev, struct dlnode *node)
Inserts node after prev.
Definition: dllist.h:244
int dllist_empty(const struct dllist *list)
Returns 1 if the doubly-linked list is empty, and 0 if not.
Definition: dllist.h:290
#define dllist_foreach(list, node)
Iterates in order over each node in a doubly-linked list.
Definition: dllist.h:232
size_t dllist_size(const struct dllist *list)
Returns the size (in number of nodes) of a doubly-linked list.
Definition: dllist.h:298
void dllist_push_front(struct dllist *list, struct dlnode *node)
Pushes a node to the front of a doubly-linked list.
Definition: dllist.h:309
int dllist_contains(const struct dllist *list, const struct dlnode *node)
Checks if a node is part of a doubly-linked list.
Definition: dllist.c:31
struct dlnode * dllist_last(const struct dllist *list)
Returns a pointer to the last node in a doubly-linked list.
Definition: dllist.h:428
void dllist_insert_before(struct dllist *list, struct dlnode *next, struct dlnode *node)
Inserts a node into a doubly-linked list.
Definition: dllist.h:377
struct dlnode * dllist_first(const struct dllist *list)
Returns a pointer to the first node in a doubly-linked list.
Definition: dllist.h:420
struct dllist * dllist_append(struct dllist *dst, struct dllist *src)
Appends the doubly-linked list at src to the one at dst.
Definition: dllist.h:400
struct dlnode * dllist_pop_front(struct dllist *list)
Pops a node from the front of a doubly-linked list.
Definition: dllist.h:337
void dlnode_init(struct dlnode *node)
Initializes a node in a doubly-linked list.
Definition: dllist.h:235
void dllist_remove(struct dllist *list, struct dlnode *node)
Removes a node from a doubly-linked list.
Definition: dllist.h:387
This header file is part of the Lely libraries; it contains the compiler feature definitions.
This header file is part of the C11 and POSIX compatibility library; it includes <stddef....
A doubly-linked list.
Definition: dllist.h:54
struct dlnode * last
A pointer to the last node in the list.
Definition: dllist.h:58
struct dlnode * first
A pointer to the first node in the list.
Definition: dllist.h:56
A node in a doubly-linked list.
Definition: dllist.h:40
struct dlnode * next
A pointer to the next node in the list.
Definition: dllist.h:44
struct dlnode * prev
A pointer to the previous node in the list.
Definition: dllist.h:42