clist.h File Reference

Circular linked list. More...

Detailed Description

Circular linked list.

This file contains a circularly and singly linked list implementation.

Its operations are:

operation runtime description
clist_lpush() O(1) insert as head (leftmost node)
clist_lpop() O(1) remove and return head (leftmost node)
clist_rpush() O(1) append as tail (rightmost node)
clist_rpop() O(n) remove and return tail (rightmost node)
clist_find() O(n) find and return node
clist_find_before() O(n) find node return node pointing to node
clist_remove() O(n) remove and return node
clist_sort() O(NlogN)sort list (stable)

clist can be used as a traditional list, a queue (FIFO) and a stack (LIFO) using fast O(1) operations.

When used as traditional list, in order to traverse, make sure every element is only visited once.


void clist_traverse(clist_node_t *list) {
    clist_node_t *node = list->next;
    if (! node) {
        puts("list empty");

    do {
        node = node->next;
        // do something with node
    } while (node != list->next);

Or use the clist_foreach() helper function, e.g.,:

static int _print_node(clist_node_t *node) { printf("0x%08x ", (unsigned)node); return 0; }

[...] clist_foreach(&list, _print_node);

To use clist as a queue, use clist_rpush() for adding elements and clist_lpop() for removal. Using clist_lpush() and clist_rpop() is inefficient due to clist_rpop()'s O(n) runtime.

To use clist as stack, use clist_lpush()/clist_lpop().

Implementation details:

Each list is represented as a "clist_node_t". Its only member, the "next" pointer, points to the last entry in the list, whose "next" pointer points to the first entry. Actual list objects should have a clist_node_t as member and then use the container_of() macro in list operations. See thread_add_to_list() as example.

Kaspar Schleiser

Definition in file clist.h.

#include <stddef.h>
#include "list.h"
+ Include dependency graph for clist.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.


typedef list_node_t clist_node_t
 List node structure. More...
typedef int(* clist_cmp_func_t) (clist_node_t *a, clist_node_t *b)
 Typedef for comparison function used by clist_sort() More...


static void clist_rpush (clist_node_t *list, clist_node_t *new_node)
 Appends new_node at the end of *list. More...
static void clist_lpush (clist_node_t *list, clist_node_t *new_node)
 Inserts new_node at the beginning of *list. More...
static clist_node_tclist_lpop (clist_node_t *list)
 Removes and returns first element from list. More...
static void clist_lpoprpush (clist_node_t *list)
 Advances the circle list. More...
static clist_node_tclist_lpeek (const clist_node_t *list)
 Returns first element in list. More...
static clist_node_tclist_rpeek (const clist_node_t *list)
 Returns last element in list. More...
static clist_node_tclist_rpop (clist_node_t *list)
 Removes and returns last element from list. More...
static clist_node_tclist_find_before (const clist_node_t *list, const clist_node_t *node)
 Finds node and returns its predecessor. More...
static clist_node_tclist_find (const clist_node_t *list, const clist_node_t *node)
 Finds and returns node. More...
static clist_node_tclist_remove (clist_node_t *list, clist_node_t *node)
 Finds and removes node. More...
static clist_node_tclist_foreach (clist_node_t *list, int(*func)(clist_node_t *, void *), void *arg)
 Traverse clist, call function for each member. More...
clist_node_t_clist_sort (clist_node_t *list_head, clist_cmp_func_t cmp)
 List sorting helper function.
static void clist_sort (clist_node_t *list, clist_cmp_func_t cmp)
 Sort a list. More...