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 
82 #ifndef CLIST_H
83 #define CLIST_H
84 
85 #include <stddef.h>
86 #include "list.h"
87 
88 #ifdef __cplusplus
89  extern "C" {
90 #endif
91 
99 
109 static inline void clist_rpush(clist_node_t *list, clist_node_t *new_node)
110 {
111  if (list->next) {
112  new_node->next = list->next->next;
113  list->next->next = new_node;
114  }
115  else {
116  new_node->next = new_node;
117  }
118  list->next = new_node;
119 }
120 
130 static inline void clist_lpush(clist_node_t *list, clist_node_t *new_node)
131 {
132  if (list->next) {
133  new_node->next = list->next->next;
134  list->next->next = new_node;
135  }
136  else {
137  new_node->next = new_node;
138  list->next = new_node;
139  }
140 }
141 
150 static inline clist_node_t *clist_lpop(clist_node_t *list)
151 {
152  if (list->next) {
153  clist_node_t *first = list->next->next;
154  if (list->next == first) {
155  list->next = NULL;
156  }
157  else {
158  list->next->next = first->next;
159  }
160  return first;
161  }
162  else {
163  return NULL;
164  }
165 }
166 
180 static inline void clist_lpoprpush(clist_node_t *list)
181 {
182  if (list->next) {
183  list->next = list->next->next;
184  }
185 }
186 
195 static inline clist_node_t *clist_lpeek(const clist_node_t *list)
196 {
197  if (list->next) {
198  return list->next->next;
199  }
200  return NULL;
201 }
202 
211 static inline clist_node_t *clist_rpeek(const clist_node_t *list)
212 {
213  return list->next;
214 }
215 
224 static inline clist_node_t *clist_rpop(clist_node_t *list)
225 {
226  if (list->next) {
227  list_node_t *last = list->next;
228  while (list->next->next != last) {
229  clist_lpoprpush(list);
230  }
231  return clist_lpop(list);
232  }
233  else {
234  return NULL;
235  }
236 }
237 
250 static inline clist_node_t *clist_find_before(const clist_node_t *list, const clist_node_t *node)
251 {
252  clist_node_t *pos = list->next;
253  if (!pos) {
254  return NULL;
255  }
256  do {
257  pos = pos->next;
258  if (pos->next == node) {
259  return pos;
260  }
261  } while (pos != list->next);
262 
263  return NULL;
264 }
265 
278 static inline clist_node_t *clist_find(const clist_node_t *list, const clist_node_t *node)
279 {
280  clist_node_t *tmp = clist_find_before(list, node);
281  if (tmp) {
282  return tmp->next;
283  }
284  else {
285  return NULL;
286  }
287 }
288 
301 static inline clist_node_t *clist_remove(clist_node_t *list, clist_node_t *node)
302 {
303  if (list->next) {
304  if (list->next->next == node) {
305  return clist_lpop(list);
306  }
307  else {
308  clist_node_t *tmp = clist_find_before(list, node);
309  if (tmp) {
310  tmp->next = tmp->next->next;
311  if (node == list->next) {
312  list->next = tmp;
313  }
314  return node;
315  }
316  }
317  }
318 
319  return NULL;
320 }
321 
334 static inline void clist_foreach(clist_node_t *list, int(*func)(clist_node_t *, void *), void *arg)
335 {
336  clist_node_t *node = list->next;
337  if (! node) {
338  return;
339  }
340  do {
341  node = node->next;
342  if (func(node, arg)) {
343  return;
344  }
345  } while (node != list->next);
346 }
347 
352 typedef int (*clist_cmp_func_t)(clist_node_t *a, clist_node_t *b);
353 
364 clist_node_t *_clist_sort(clist_node_t *list_head, clist_cmp_func_t cmp);
365 
408 static inline void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
409 {
410  if (list->next) {
411  list->next = _clist_sort(list->next->next, cmp);
412  }
413 }
414 
415 #ifdef __cplusplus
416 }
417 #endif
418 
419 #endif /* CLIST_H */
420 
static void clist_foreach(clist_node_t *list, int(*func)(clist_node_t *, void *), void *arg)
Traverse clist, call function for each member.
Definition: clist.h:334
list_node_t clist_node_t
List node structure.
Definition: clist.h:98
static clist_node_t * clist_rpeek(const clist_node_t *list)
Returns last element in list.
Definition: clist.h:211
int(* clist_cmp_func_t)(clist_node_t *a, clist_node_t *b)
Typedef for comparison function used by clist_sort()
Definition: clist.h:352
static void clist_rpush(clist_node_t *list, clist_node_t *new_node)
Appends new_node at the end of *list.
Definition: clist.h:109
static clist_node_t * clist_find(const clist_node_t *list, const clist_node_t *node)
Finds and returns node.
Definition: clist.h:278
static void clist_lpush(clist_node_t *list, clist_node_t *new_node)
Inserts new_node at the beginning of *list.
Definition: clist.h:130
Intrusive linked list.
static clist_node_t * clist_lpop(clist_node_t *list)
Removes and returns first element from list.
Definition: clist.h:150
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:250
static void clist_sort(clist_node_t *list, clist_cmp_func_t cmp)
Sort a list.
Definition: clist.h:408
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:301
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:180
static clist_node_t * clist_lpeek(const clist_node_t *list)
Returns first element in list.
Definition: clist.h:195
static clist_node_t * clist_rpop(clist_node_t *list)
Removes and returns last element from list.
Definition: clist.h:224
clist_node_t * _clist_sort(clist_node_t *list_head, clist_cmp_func_t cmp)
List sorting helper function.