clist.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2016 Kaspar Schleiser <kaspar@schleiser.de>
3  * 2013 Freie Universit├Ąt Berlin
4  * 2017 Inria
5  *
6  * This file is subject to the terms and conditions of the GNU Lesser
7  * General Public License v2.1. See the file LICENSE in the top level
8  * directory for more details.
9  */
10 
90 #ifndef CLIST_H
91 #define CLIST_H
92 
93 #include <stdbool.h>
94 #include <stddef.h>
95 #include "list.h"
96 
97 #ifdef __cplusplus
98 extern "C" {
99 #endif
100 
108 
118 static inline bool clist_is_empty(const clist_node_t *list)
119 {
120  return list->next == NULL;
121 }
122 
132 static inline void clist_rpush(clist_node_t *list, clist_node_t *new_node)
133 {
134  if (list->next) {
135  new_node->next = list->next->next;
136  list->next->next = new_node;
137  }
138  else {
139  new_node->next = new_node;
140  }
141  list->next = new_node;
142 }
143 
153 static inline void clist_lpush(clist_node_t *list, clist_node_t *new_node)
154 {
155  if (list->next) {
156  new_node->next = list->next->next;
157  list->next->next = new_node;
158  }
159  else {
160  new_node->next = new_node;
161  list->next = new_node;
162  }
163 }
164 
173 static inline clist_node_t *clist_lpop(clist_node_t *list)
174 {
175  if (list->next) {
176  clist_node_t *first = list->next->next;
177  if (list->next == first) {
178  list->next = NULL;
179  }
180  else {
181  list->next->next = first->next;
182  }
183  return first;
184  }
185  else {
186  return NULL;
187  }
188 }
189 
203 static inline void clist_lpoprpush(clist_node_t *list)
204 {
205  if (list->next) {
206  list->next = list->next->next;
207  }
208 }
209 
218 static inline clist_node_t *clist_lpeek(const clist_node_t *list)
219 {
220  if (list->next) {
221  return list->next->next;
222  }
223  return NULL;
224 }
225 
234 static inline clist_node_t *clist_rpeek(const clist_node_t *list)
235 {
236  return list->next;
237 }
238 
247 static inline clist_node_t *clist_rpop(clist_node_t *list)
248 {
249  if (list->next) {
250  list_node_t *last = list->next;
251  while (list->next->next != last) {
252  clist_lpoprpush(list);
253  }
254  return clist_lpop(list);
255  }
256  else {
257  return NULL;
258  }
259 }
260 
273 static inline clist_node_t *clist_find_before(const clist_node_t *list,
274  const clist_node_t *node)
275 {
276  clist_node_t *pos = list->next;
277 
278  if (!pos) {
279  return NULL;
280  }
281  do {
282  pos = pos->next;
283  if (pos->next == node) {
284  return pos;
285  }
286  } while (pos != list->next);
287 
288  return NULL;
289 }
290 
303 static inline clist_node_t *clist_find(const clist_node_t *list,
304  const clist_node_t *node)
305 {
306  clist_node_t *tmp = clist_find_before(list, node);
307 
308  if (tmp) {
309  return tmp->next;
310  }
311  else {
312  return NULL;
313  }
314 }
315 
329 {
330  if (list->next) {
331  if (list->next->next == node) {
332  return clist_lpop(list);
333  }
334  else {
335  clist_node_t *tmp = clist_find_before(list, node);
336  if (tmp) {
337  tmp->next = tmp->next->next;
338  if (node == list->next) {
339  list->next = tmp;
340  }
341  return node;
342  }
343  }
344  }
345 
346  return NULL;
347 }
348 
364 static inline clist_node_t *clist_foreach(clist_node_t *list, int (*func)(
365  clist_node_t *,
366  void *), void *arg)
367 {
368  clist_node_t *node = list->next;
369 
370  if (node) {
371  do {
372  node = node->next;
373  if (func(node, arg)) {
374  return node;
375  }
376  } while (node != list->next);
377  }
378 
379  return NULL;
380 }
381 
387 
399 
442 static inline void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
443 {
444  if (list->next) {
445  list->next = _clist_sort(list->next->next, cmp);
446  }
447 }
448 
456 static inline size_t clist_count(clist_node_t *list)
457 {
458  clist_node_t *node = list->next;
459  size_t cnt = 0;
460 
461  if (node) {
462  do {
463  node = node->next;
464  ++cnt;
465  } while (node != list->next);
466  }
467 
468  return cnt;
469 }
470 
480 static inline bool clist_exactly_one(clist_node_t *list)
481 {
482  return !clist_is_empty(list) && (list->next == list->next->next);
483 }
484 
494 static inline bool clist_more_than_one(clist_node_t *list)
495 {
496  return !clist_is_empty(list) && (list->next != list->next->next);
497 }
498 
499 #ifdef __cplusplus
500 }
501 #endif
502 
503 #endif /* CLIST_H */
static size_t clist_count(clist_node_t *list)
Count the number of items in the given list.
Definition: clist.h:456
static bool clist_more_than_one(clist_node_t *list)
Tells if a list has more than one element.
Definition: clist.h:494
static clist_node_t * clist_remove(clist_node_t *list, clist_node_t *node)
Finds and removes node.
Definition: clist.h:328
static void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
Sort a list.
Definition: clist.h:442
static clist_node_t * clist_rpeek(const clist_node_t *list)
Returns last element in list.
Definition: clist.h:234
clist_node_t * _clist_sort(clist_node_t *list_head, clist_cmp_func_t cmp)
List sorting helper function.
static void clist_rpush(clist_node_t *list, clist_node_t *new_node)
Appends new_node at the end of *list.
Definition: clist.h:132
list_node_t clist_node_t
List node structure.
Definition: clist.h:107
static bool clist_is_empty(const clist_node_t *list)
Checks if *list is empty.
Definition: clist.h:118
static void clist_lpush(clist_node_t *list, clist_node_t *new_node)
Inserts new_node at the beginning of *list.
Definition: clist.h:153
static clist_node_t * clist_lpeek(const clist_node_t *list)
Returns first element in list.
Definition: clist.h:218
static clist_node_t * clist_rpop(clist_node_t *list)
Removes and returns last element from list.
Definition: clist.h:247
static void clist_lpoprpush(clist_node_t *list)
Advances the circle list.
Definition: clist.h:203
int(* clist_cmp_func_t)(clist_node_t *a, clist_node_t *b)
Typedef for comparison function used by clist_sort()
Definition: clist.h:386
static bool clist_exactly_one(clist_node_t *list)
Tells if a list has exactly one element.
Definition: clist.h:480
static clist_node_t * clist_find_before(const clist_node_t *list, const clist_node_t *node)
Finds node and returns its predecessor.
Definition: clist.h:273
static clist_node_t * clist_find(const clist_node_t *list, const clist_node_t *node)
Finds and returns node.
Definition: clist.h:303
static clist_node_t * clist_foreach(clist_node_t *list, int(*func)(clist_node_t *, void *), void *arg)
Traverse clist, call function for each member.
Definition: clist.h:364
static clist_node_t * clist_lpop(clist_node_t *list)
Removes and returns first element from list.
Definition: clist.h:173
Intrusive linked list.
List node structure.
Definition: list.h:40
struct list_node * next
pointer to next list entry
Definition: list.h:41