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 
40 struct dlnode {
42  struct dlnode *prev;
44  struct dlnode *next;
45 };
46 
48 #define DLNODE_INIT \
49  { \
50  NULL, NULL \
51  }
52 
54 struct dllist {
56  struct dlnode *first;
58  struct dlnode *last;
59 };
60 
62 #define DLLIST_INIT \
63  { \
64  NULL, NULL \
65  }
66 
67 #ifdef __cplusplus
68 extern "C" {
69 #endif
70 
72 LELY_UTIL_DLLIST_INLINE void dlnode_init(struct dlnode *node);
73 
79 LELY_UTIL_DLLIST_INLINE int dlnode_insert_after(
80  struct dlnode *prev, struct dlnode *node);
81 
87 LELY_UTIL_DLLIST_INLINE int dlnode_insert_before(
88  struct dlnode *next, struct dlnode *node);
89 
94 LELY_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 
119 LELY_UTIL_DLLIST_INLINE void dllist_init(struct dllist *list);
120 
125 LELY_UTIL_DLLIST_INLINE int dllist_empty(const struct dllist *list);
126 
131 LELY_UTIL_DLLIST_INLINE size_t dllist_size(const struct dllist *list);
132 
139 LELY_UTIL_DLLIST_INLINE void dllist_push_front(
140  struct dllist *list, struct dlnode *node);
141 
147 LELY_UTIL_DLLIST_INLINE void dllist_push_back(
148  struct dllist *list, struct dlnode *node);
149 
156 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_front(struct dllist *list);
157 
163 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_pop_back(struct dllist *list);
164 
171 LELY_UTIL_DLLIST_INLINE void dllist_insert_after(
172  struct dllist *list, struct dlnode *prev, struct dlnode *node);
173 
180 LELY_UTIL_DLLIST_INLINE void dllist_insert_before(
181  struct dllist *list, struct dlnode *next, struct dlnode *node);
182 
189 LELY_UTIL_DLLIST_INLINE void dllist_remove(
190  struct dllist *list, struct dlnode *node);
191 
197 int dllist_contains(const struct dllist *list, const struct dlnode *node);
198 
205 LELY_UTIL_DLLIST_INLINE struct dllist *dllist_append(
206  struct dllist *dst, struct dllist *src);
207 
214 LELY_UTIL_DLLIST_INLINE struct dlnode *dllist_first(const struct dllist *list);
215 
222 LELY_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 
234 LELY_UTIL_DLLIST_INLINE void
235 dlnode_init(struct dlnode *node)
236 {
237  assert(node);
238 
239  node->prev = NULL;
240  node->next = NULL;
241 }
242 
243 LELY_UTIL_DLLIST_INLINE int
244 dlnode_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 
256 LELY_UTIL_DLLIST_INLINE int
257 dlnode_insert_before(struct dlnode *next, struct dlnode *node)
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 
269 LELY_UTIL_DLLIST_INLINE void
270 dlnode_remove(struct dlnode *node)
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 
280 LELY_UTIL_DLLIST_INLINE void
281 dllist_init(struct dllist *list)
282 {
283  assert(list);
284 
285  list->first = NULL;
286  list->last = NULL;
287 }
288 
289 LELY_UTIL_DLLIST_INLINE int
290 dllist_empty(const struct dllist *list)
291 {
292  assert(list);
293 
294  return !list->first;
295 }
296 
297 LELY_UTIL_DLLIST_INLINE size_t
298 dllist_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 
308 LELY_UTIL_DLLIST_INLINE void
309 dllist_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 
322 LELY_UTIL_DLLIST_INLINE void
323 dllist_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 
336 LELY_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 
351 LELY_UTIL_DLLIST_INLINE struct dlnode *
352 dllist_pop_back(struct dllist *list)
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 
366 LELY_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 
376 LELY_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 
386 LELY_UTIL_DLLIST_INLINE void
387 dllist_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 
399 LELY_UTIL_DLLIST_INLINE struct dllist *
400 dllist_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 
419 LELY_UTIL_DLLIST_INLINE struct dlnode *
420 dllist_first(const struct dllist *list)
421 {
422  assert(list);
423 
424  return list->first;
425 }
426 
427 LELY_UTIL_DLLIST_INLINE struct dlnode *
428 dllist_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_
dllist_init
void dllist_init(struct dllist *list)
Initializes a doubly-linked list.
Definition: dllist.h:281
dllist_push_front
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
features.h
dllist_contains
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
dllist::first
struct dlnode * first
A pointer to the first node in the list.
Definition: dllist.h:56
dllist_remove
void dllist_remove(struct dllist *list, struct dlnode *node)
Removes a node from a doubly-linked list.
Definition: dllist.h:387
dllist
A doubly-linked list.
Definition: dllist.h:54
dllist::last
struct dlnode * last
A pointer to the last node in the list.
Definition: dllist.h:58
dlnode::next
struct dlnode * next
A pointer to the next node in the list.
Definition: dllist.h:44
dllist_size
size_t dllist_size(const struct dllist *list)
Returns the size (in number of nodes) of a doubly-linked list.
Definition: dllist.h:298
dllist_foreach
#define dllist_foreach(list, node)
Iterates in order over each node in a doubly-linked list.
Definition: dllist.h:232
dllist_append
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
dllist_first
struct dlnode * dllist_first(const struct dllist *list)
Returns a pointer to the first node in a doubly-linked list.
Definition: dllist.h:420
dlnode_init
void dlnode_init(struct dlnode *node)
Initializes a node in a doubly-linked list.
Definition: dllist.h:235
dllist_push_back
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
dlnode_insert_before
int dlnode_insert_before(struct dlnode *next, struct dlnode *node)
Inserts node before next.
Definition: dllist.h:257
dlnode_remove
void dlnode_remove(struct dlnode *node)
Removes node from a doubly-list.
Definition: dllist.h:270
dlnode_insert_after
int dlnode_insert_after(struct dlnode *prev, struct dlnode *node)
Inserts node after prev.
Definition: dllist.h:244
dlnode::prev
struct dlnode * prev
A pointer to the previous node in the list.
Definition: dllist.h:42
dllist_last
struct dlnode * dllist_last(const struct dllist *list)
Returns a pointer to the last node in a doubly-linked list.
Definition: dllist.h:428
dllist_pop_back
struct dlnode * dllist_pop_back(struct dllist *list)
Pops a node from the back of a doubly-linked list.
Definition: dllist.h:352
dllist_pop_front
struct dlnode * dllist_pop_front(struct dllist *list)
Pops a node from the front of a doubly-linked list.
Definition: dllist.h:337
dllist_empty
int dllist_empty(const struct dllist *list)
Returns 1 if the doubly-linked list is empty, and 0 if not.
Definition: dllist.h:290
dlnode
A node in a doubly-linked list.
Definition: dllist.h:40
stddef.h
dllist_insert_before
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
dllist_insert_after
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