Lely core libraries  2.2.5
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 <stddef.h>
29 
30 #ifndef LELY_UTIL_DLLIST_INLINE
31 #define LELY_UTIL_DLLIST_INLINE static inline
32 #endif
33 
39 struct dlnode {
41  struct dlnode *prev;
43  struct dlnode *next;
44 };
45 
47 #define DLNODE_INIT \
48  { \
49  NULL, NULL \
50  }
51 
53 struct dllist {
55  struct dlnode *first;
57  struct dlnode *last;
58 };
59 
61 #define DLLIST_INIT \
62  { \
63  NULL, NULL \
64  }
65 
66 #ifdef __cplusplus
67 extern "C" {
68 #endif
69 
71 LELY_UTIL_DLLIST_INLINE void dlnode_init(struct dlnode *node);
72 
78 LELY_UTIL_DLLIST_INLINE int dlnode_insert_after(
79  struct dlnode *prev, struct dlnode *node);
80 
86 LELY_UTIL_DLLIST_INLINE int dlnode_insert_before(
87  struct dlnode *next, struct dlnode *node);
88 
93 LELY_UTIL_DLLIST_INLINE void dlnode_remove(struct dlnode *node);
94 
103 #ifdef __COUNTER__
104 #define dlnode_foreach(first, node) dlnode_foreach_(__COUNTER__, first, node)
105 #else
106 #define dlnode_foreach(first, node) dlnode_foreach_(__LINE__, first, node)
107 #endif
108 #define dlnode_foreach_(n, first, node) dlnode_foreach__(n, first, node)
109 // clang-format off
110 #define dlnode_foreach__(n, first, node) \
111  for (struct dlnode *node = (first), \
112  *_dlnode_next_##n = (node) ? (node)->next : NULL; \
113  (node); (node) = _dlnode_next_##n, \
114  _dlnode_next_##n = (node) ? (node)->next : NULL)
115 // clang-format on
116 
118 LELY_UTIL_DLLIST_INLINE void dllist_init(struct dllist *list);
119 
124 LELY_UTIL_DLLIST_INLINE int dllist_empty(const struct dllist *list);
125 
130 LELY_UTIL_DLLIST_INLINE size_t dllist_size(const struct dllist *list);
131 
138 LELY_UTIL_DLLIST_INLINE void dllist_push_front(
139  struct dllist *list, struct dlnode *node);
140 
146 LELY_UTIL_DLLIST_INLINE void dllist_push_back(
147  struct dllist *list, struct dlnode *node);
148 
155 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_front(struct dllist *list);
156 
162 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_back(struct dllist *list);
163 
170 LELY_UTIL_DLLIST_INLINE void dllist_insert_after(
171  struct dllist *list, struct dlnode *prev, struct dlnode *node);
172 
179 LELY_UTIL_DLLIST_INLINE void dllist_insert_before(
180  struct dllist *list, struct dlnode *next, struct dlnode *node);
181 
188 LELY_UTIL_DLLIST_INLINE void dllist_remove(
189  struct dllist *list, struct dlnode *node);
190 
197 LELY_UTIL_DLLIST_INLINE struct dllist *dllist_append(
198  struct dllist *dst, struct dllist *src);
199 
206 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_first(const struct dllist *list);
207 
214 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_last(const struct dllist *list);
215 
224 #define dllist_foreach(list, node) dlnode_foreach (dllist_first(list), node)
225 
226 inline void
227 dlnode_init(struct dlnode *node)
228 {
229  node->prev = NULL;
230  node->next = NULL;
231 }
232 
233 inline int
234 dlnode_insert_after(struct dlnode *prev, struct dlnode *node)
235 {
236  node->prev = prev;
237  if ((node->next = prev->next) != NULL)
238  node->next->prev = node;
239  prev->next = node;
240  return !node->next;
241 }
242 
243 inline int
244 dlnode_insert_before(struct dlnode *next, struct dlnode *node)
245 {
246  node->next = next;
247  if ((node->prev = next->prev) != NULL)
248  node->prev->next = node;
249  next->prev = node;
250  return !node->prev;
251 }
252 
253 inline void
254 dlnode_remove(struct dlnode *node)
255 {
256  if (node->prev)
257  node->prev->next = node->next;
258  if (node->next)
259  node->next->prev = node->prev;
260 }
261 
262 inline void
263 dllist_init(struct dllist *list)
264 {
265  list->first = NULL;
266  list->last = NULL;
267 }
268 
269 inline int
270 dllist_empty(const struct dllist *list)
271 {
272  return !list->first;
273 }
274 
275 inline size_t
276 dllist_size(const struct dllist *list)
277 {
278  size_t size = 0;
279  dllist_foreach (list, node)
280  size++;
281  return size;
282 }
283 
284 inline void
285 dllist_push_front(struct dllist *list, struct dlnode *node)
286 {
287  node->prev = NULL;
288  if ((node->next = list->first))
289  node->next->prev = node;
290  else
291  list->last = node;
292  list->first = node;
293 }
294 
295 inline void
296 dllist_push_back(struct dllist *list, struct dlnode *node)
297 {
298  node->next = NULL;
299  if ((node->prev = list->last))
300  node->prev->next = node;
301  else
302  list->first = node;
303  list->last = node;
304 }
305 
306 inline struct dlnode *
308 {
309  struct dlnode *node = list->first;
310  if (list->first) {
311  if ((list->first = list->first->next))
312  list->first->prev = NULL;
313  else
314  list->last = NULL;
315  }
316  return node;
317 }
318 
319 inline struct dlnode *
320 dllist_pop_back(struct dllist *list)
321 {
322  struct dlnode *node = list->last;
323  if (list->last) {
324  if ((list->last = list->last->prev))
325  list->last->next = NULL;
326  else
327  list->first = NULL;
328  }
329  return node;
330 }
331 
332 inline void
334  struct dllist *list, struct dlnode *prev, struct dlnode *node)
335 {
336  if (dlnode_insert_after(prev, node))
337  list->last = node;
338 }
339 
340 inline void
342  struct dllist *list, struct dlnode *next, struct dlnode *node)
343 {
344  if (dlnode_insert_before(next, node))
345  list->first = node;
346 }
347 
348 inline void
349 dllist_remove(struct dllist *list, struct dlnode *node)
350 {
351  if (!node->prev)
352  list->first = node->next;
353  if (!node->next)
354  list->last = node->prev;
355  dlnode_remove(node);
356 }
357 
358 inline struct dllist *
359 dllist_append(struct dllist *dst, struct dllist *src)
360 {
361  if (src->first) {
362  if (dst->first) {
363  src->first->prev = dst->last;
364  dst->last->next = src->first;
365  dst->last = src->last;
366  } else {
367  dst->first = src->first;
368  dst->last = src->last;
369  }
370  dllist_init(src);
371  }
372  return dst;
373 }
374 
375 inline struct dlnode *
376 dllist_first(const struct dllist *list)
377 {
378  return list->first;
379 }
380 
381 inline struct dlnode *
382 dllist_last(const struct dllist *list)
383 {
384  return list->last;
385 }
386 
387 #ifdef __cplusplus
388 }
389 #endif
390 
391 #endif // !LELY_UTIL_DLLIST_H_
void dlnode_remove(struct dlnode *node)
Removes node from a doubly-list.
Definition: dllist.h:254
void dllist_push_back(struct dllist *list, struct dlnode *node)
Pushes a node to the back of a doubly-linked list.
Definition: dllist.h:296
int dlnode_insert_before(struct dlnode *next, struct dlnode *node)
Inserts node before next.
Definition: dllist.h:244
struct dlnode * dllist_pop_back(struct dllist *list)
Pops a node from the back of a doubly-linked list.
Definition: dllist.h:320
void dllist_init(struct dllist *list)
Initializes a doubly-linked list.
Definition: dllist.h:263
void dllist_insert_after(struct dllist *list, struct dlnode *prev, struct dlnode *node)
Inserts a node into a doubly-linked list.
Definition: dllist.h:333
int dlnode_insert_after(struct dlnode *prev, struct dlnode *node)
Inserts node after prev.
Definition: dllist.h:234
int dllist_empty(const struct dllist *list)
Returns 1 if the doubly-linked list is empty, and 0 if not.
Definition: dllist.h:270
#define dllist_foreach(list, node)
Iterates in order over each node in a doubly-linked list.
Definition: dllist.h:224
size_t dllist_size(const struct dllist *list)
Returns the size (in number of nodes) of a doubly-linked list.
Definition: dllist.h:276
void dllist_push_front(struct dllist *list, struct dlnode *node)
Pushes a node to the front of a doubly-linked list.
Definition: dllist.h:285
struct dlnode * dllist_last(const struct dllist *list)
Returns a pointer to the last node in a doubly-linked list.
Definition: dllist.h:382
void dllist_insert_before(struct dllist *list, struct dlnode *next, struct dlnode *node)
Inserts a node into a doubly-linked list.
Definition: dllist.h:341
struct dlnode * dllist_first(const struct dllist *list)
Returns a pointer to the first node in a doubly-linked list.
Definition: dllist.h:376
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:359
struct dlnode * dllist_pop_front(struct dllist *list)
Pops a node from the front of a doubly-linked list.
Definition: dllist.h:307
void dlnode_init(struct dlnode *node)
Initializes a node in a doubly-linked list.
Definition: dllist.h:227
void dllist_remove(struct dllist *list, struct dlnode *node)
Removes a node from a doubly-linked list.
Definition: dllist.h:349
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:53
struct dlnode * last
A pointer to the last node in the list.
Definition: dllist.h:57
struct dlnode * first
A pointer to the first node in the list.
Definition: dllist.h:55
A node in a doubly-linked list.
Definition: dllist.h:39
struct dlnode * next
A pointer to the next node in the list.
Definition: dllist.h:43
struct dlnode * prev
A pointer to the previous node in the list.
Definition: dllist.h:41