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  *
5  * This file is subject to the terms and conditions of the GNU Lesser
6  * General Public License v2.1. See the file LICENSE in the top level
7  * directory for more details.
8  */
9 
85 #ifndef CLIST_H
86 #define CLIST_H
87 
88 #include <stddef.h>
89 #include "list.h"
90 
91 #ifdef __cplusplus
92  extern "C" {
93 #endif
94 
102 
112 static inline void clist_rpush(clist_node_t *list, clist_node_t *new_node)
113 {
114  if (list->next) {
115  new_node->next = list->next->next;
116  list->next->next = new_node;
117  }
118  else {
119  new_node->next = new_node;
120  }
121  list->next = new_node;
122 }
123 
133 static inline void clist_lpush(clist_node_t *list, clist_node_t *new_node)
134 {
135  if (list->next) {
136  new_node->next = list->next->next;
137  list->next->next = new_node;
138  }
139  else {
140  new_node->next = new_node;
141  list->next = new_node;
142  }
143 }
144 
153 static inline clist_node_t *clist_lpop(clist_node_t *list)
154 {
155  if (list->next) {
156  clist_node_t *first = list->next->next;
157  if (list->next == first) {
158  list->next = NULL;
159  }
160  else {
161  list->next->next = first->next;
162  }
163  return first;
164  }
165  else {
166  return NULL;
167  }
168 }
169 
183 static inline void clist_lpoprpush(clist_node_t *list)
184 {
185  if (list->next) {
186  list->next = list->next->next;
187  }
188 }
189 
198 static inline clist_node_t *clist_lpeek(const clist_node_t *list)
199 {
200  if (list->next) {
201  return list->next->next;
202  }
203  return NULL;
204 }
205 
214 static inline clist_node_t *clist_rpeek(const clist_node_t *list)
215 {
216  return list->next;
217 }
218 
227 static inline clist_node_t *clist_rpop(clist_node_t *list)
228 {
229  if (list->next) {
230  list_node_t *last = list->next;
231  while (list->next->next != last) {
232  clist_lpoprpush(list);
233  }
234  return clist_lpop(list);
235  }
236  else {
237  return NULL;
238  }
239 }
240 
253 static inline clist_node_t *clist_find_before(const clist_node_t *list, const clist_node_t *node)
254 {
255  clist_node_t *pos = list->next;
256  if (!pos) {
257  return NULL;
258  }
259  do {
260  pos = pos->next;
261  if (pos->next == node) {
262  return pos;
263  }
264  } while (pos != list->next);
265 
266  return NULL;
267 }
268 
281 static inline clist_node_t *clist_find(const clist_node_t *list, const clist_node_t *node)
282 {
283  clist_node_t *tmp = clist_find_before(list, node);
284  if (tmp) {
285  return tmp->next;
286  }
287  else {
288  return NULL;
289  }
290 }
291 
304 static inline clist_node_t *clist_remove(clist_node_t *list, clist_node_t *node)
305 {
306  if (list->next) {
307  if (list->next->next == node) {
308  return clist_lpop(list);
309  }
310  else {
311  clist_node_t *tmp = clist_find_before(list, node);
312  if (tmp) {
313  tmp->next = tmp->next->next;
314  if (node == list->next) {
315  list->next = tmp;
316  }
317  return node;
318  }
319  }
320  }
321 
322  return NULL;
323 }
324 
340 static inline clist_node_t *clist_foreach(clist_node_t *list, int(*func)(clist_node_t *, void *), void *arg)
341 {
342  clist_node_t *node = list->next;
343  if (node) {
344  do {
345  node = node->next;
346  if (func(node, arg)) {
347  return node;
348  }
349  } while (node != list->next);
350  }
351 
352  return NULL;
353 }
354 
359 typedef int (*clist_cmp_func_t)(clist_node_t *a, clist_node_t *b);
360 
371 clist_node_t *_clist_sort(clist_node_t *list_head, clist_cmp_func_t cmp);
372 
415 static inline void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
416 {
417  if (list->next) {
418  list->next = _clist_sort(list->next->next, cmp);
419  }
420 }
421 
422 #ifdef __cplusplus
423 }
424 #endif
425 
426 #endif /* CLIST_H */
427 
list_node_t clist_node_t
List node structure.
Definition: clist.h:101
static clist_node_t * clist_rpeek(const clist_node_t *list)
Returns last element in list.
Definition: clist.h:214
int(* clist_cmp_func_t)(clist_node_t *a, clist_node_t *b)
Typedef for comparison function used by clist_sort()
Definition: clist.h:359
static void clist_rpush(clist_node_t *list, clist_node_t *new_node)
Appends new_node at the end of *list.
Definition: clist.h:112
static clist_node_t * clist_find(const clist_node_t *list, const clist_node_t *node)
Finds and returns node.
Definition: clist.h:281
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:340
static void clist_lpush(clist_node_t *list, clist_node_t *new_node)
Inserts new_node at the beginning of *list.
Definition: clist.h:133
Intrusive linked list.
static clist_node_t * clist_lpop(clist_node_t *list)
Removes and returns first element from list.
Definition: clist.h:153
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:253
static void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
Sort a list.
Definition: clist.h:415
List node structure.
Definition: list.h:40
static clist_node_t * clist_remove(clist_node_t *list, clist_node_t *node)
Finds and removes node.
Definition: clist.h:304
struct list_node * next
pointer to next list entry
Definition: list.h:41
static void clist_lpoprpush(clist_node_t *list)
Advances the circle list.
Definition: clist.h:183
static clist_node_t * clist_lpeek(const clist_node_t *list)
Returns first element in list.
Definition: clist.h:198
static clist_node_t * clist_rpop(clist_node_t *list)
Removes and returns last element from list.
Definition: clist.h:227
clist_node_t * _clist_sort(clist_node_t *list_head, clist_cmp_func_t cmp)
List sorting helper function.