All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Loading...
Searching...
No Matches
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
11#pragma once
12
92#include <stdbool.h>
93#include <stddef.h>
94#include "list.h"
95
96#ifdef __cplusplus
97extern "C" {
98#endif
99
107
117static inline bool clist_is_empty(const clist_node_t *list)
118{
119 return list->next == NULL;
120}
121
131static inline void clist_rpush(clist_node_t *list, clist_node_t *new_node)
132{
133 if (list->next) {
134 new_node->next = list->next->next;
135 list->next->next = new_node;
136 }
137 else {
138 new_node->next = new_node;
139 }
140 list->next = new_node;
141}
142
152static inline void clist_lpush(clist_node_t *list, clist_node_t *new_node)
153{
154 if (list->next) {
155 new_node->next = list->next->next;
156 list->next->next = new_node;
157 }
158 else {
159 new_node->next = new_node;
160 list->next = new_node;
161 }
162}
163
173{
174 if (list->next) {
175 clist_node_t *first = list->next->next;
176 if (list->next == first) {
177 list->next = NULL;
178 }
179 else {
180 list->next->next = first->next;
181 }
182 return first;
183 }
184 else {
185 return NULL;
186 }
187}
188
202static inline void clist_lpoprpush(clist_node_t *list)
203{
204 if (list->next) {
205 list->next = list->next->next;
206 }
207}
208
217static inline clist_node_t *clist_lpeek(const clist_node_t *list)
218{
219 if (list->next) {
220 return list->next->next;
221 }
222 return NULL;
223}
224
233static inline clist_node_t *clist_rpeek(const clist_node_t *list)
234{
235 return list->next;
236}
237
247{
248 if (list->next) {
249 list_node_t *last = list->next;
250 while (list->next->next != last) {
251 clist_lpoprpush(list);
252 }
253 return clist_lpop(list);
254 }
255 else {
256 return NULL;
257 }
258}
259
272static inline clist_node_t *clist_find_before(const clist_node_t *list,
273 const clist_node_t *node)
274{
275 clist_node_t *pos = list->next;
276
277 if (!pos) {
278 return NULL;
279 }
280 do {
281 pos = pos->next;
282 if (pos->next == node) {
283 return pos;
284 }
285 } while (pos != list->next);
286
287 return NULL;
288}
289
302static inline clist_node_t *clist_find(const clist_node_t *list,
303 const clist_node_t *node)
304{
305 clist_node_t *tmp = clist_find_before(list, node);
306
307 if (tmp) {
308 return tmp->next;
309 }
310 else {
311 return NULL;
312 }
313}
314
328{
329 if (list->next) {
330 if (list->next->next == node) {
331 return clist_lpop(list);
332 }
333 else {
334 clist_node_t *tmp = clist_find_before(list, node);
335 if (tmp) {
336 tmp->next = tmp->next->next;
337 if (node == list->next) {
338 list->next = tmp;
339 }
340 return node;
341 }
342 }
343 }
344
345 return NULL;
346}
347
363static inline clist_node_t *clist_foreach(clist_node_t *list, int (*func)(
364 clist_node_t *,
365 void *), void *arg)
366{
367 clist_node_t *node = list->next;
368
369 if (node) {
370 do {
371 node = node->next;
372 if (func(node, arg)) {
373 return node;
374 }
375 } while (node != list->next);
376 }
377
378 return NULL;
379}
380
386
398
441static inline void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
442{
443 if (list->next) {
444 list->next = _clist_sort(list->next->next, cmp);
445 }
446}
447
455static inline size_t clist_count(clist_node_t *list)
456{
457 clist_node_t *node = list->next;
458 size_t cnt = 0;
459
460 if (node) {
461 do {
462 node = node->next;
463 ++cnt;
464 } while (node != list->next);
465 }
466
467 return cnt;
468}
469
479static inline bool clist_exactly_one(clist_node_t *list)
480{
481 return !clist_is_empty(list) && (list->next == list->next->next);
482}
483
493static inline bool clist_more_than_one(clist_node_t *list)
494{
495 return !clist_is_empty(list) && (list->next != list->next->next);
496}
497
498#ifdef __cplusplus
499}
500#endif
501
static size_t clist_count(clist_node_t *list)
Count the number of items in the given list.
Definition clist.h:455
static clist_node_t * clist_lpeek(const clist_node_t *list)
Returns first element in list.
Definition clist.h:217
static bool clist_more_than_one(clist_node_t *list)
Tells if a list has more than one element.
Definition clist.h:493
static void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
Sort a list.
Definition clist.h:441
static clist_node_t * clist_lpop(clist_node_t *list)
Removes and returns first element from list.
Definition clist.h:172
static void clist_rpush(clist_node_t *list, clist_node_t *new_node)
Appends new_node at the end of *list.
Definition clist.h:131
list_node_t clist_node_t
List node structure.
Definition clist.h:106
static bool clist_is_empty(const clist_node_t *list)
Checks if *list is empty.
Definition clist.h:117
static clist_node_t * clist_rpeek(const clist_node_t *list)
Returns last element in list.
Definition clist.h:233
static clist_node_t * clist_find(const clist_node_t *list, const clist_node_t *node)
Finds and returns node.
Definition clist.h:302
static void clist_lpush(clist_node_t *list, clist_node_t *new_node)
Inserts new_node at the beginning of *list.
Definition clist.h:152
static clist_node_t * clist_remove(clist_node_t *list, clist_node_t *node)
Finds and removes node.
Definition clist.h:327
clist_node_t * _clist_sort(clist_node_t *list_head, clist_cmp_func_t cmp)
List sorting helper function.
static void clist_lpoprpush(clist_node_t *list)
Advances the circle list.
Definition clist.h:202
int(* clist_cmp_func_t)(clist_node_t *a, clist_node_t *b)
Typedef for comparison function used by clist_sort()
Definition clist.h:385
static bool clist_exactly_one(clist_node_t *list)
Tells if a list has exactly one element.
Definition clist.h:479
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:363
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:272
static clist_node_t * clist_rpop(clist_node_t *list)
Removes and returns last element from list.
Definition clist.h:246
Intrusive linked list.
List node structure.
Definition list.h:39
struct list_node * next
pointer to next list entry
Definition list.h:40