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_lpeek() O(1) get the head without removing it
clist_lpop() O(1) remove and return head (leftmost node)
clist_rpush() O(1) append as tail (rightmost node)
clist_rpeek() O(1) get the tail without removing it
clist_rpop() O(n) remove and return tail (rightmost node)
clist_lpoprpush() O(1) move first element to the end of the list
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_count() O(n) count the number of elements in a list

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.

Example:

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

    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.

Author
Kaspar Schleiser kaspa.nosp@m.r@sc.nosp@m.hleis.nosp@m.er.d.nosp@m.e

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...
 
static size_t clist_count (clist_node_t *list)
 Count the number of items in the given list. More...
 

Typedef Documentation

◆ clist_cmp_func_t

typedef int(* clist_cmp_func_t) (clist_node_t *a, clist_node_t *b)

Typedef for comparison function used by clist_sort()

Definition at line 361 of file clist.h.

◆ clist_node_t

List node structure.

Used as is as reference to a list.

Definition at line 103 of file clist.h.

Function Documentation

◆ clist_count()

static size_t clist_count ( clist_node_t list)
inlinestatic

Count the number of items in the given list.

Parameters
[in]listptr to the first element of the list
Returns
the number of elements in the given list

Definition at line 431 of file clist.h.

◆ clist_find()

static clist_node_t* clist_find ( const clist_node_t list,
const clist_node_t node 
)
inlinestatic

Finds and returns node.

Note
Complexity: O(n)
Parameters
[in]listpointer to clist
[in,out]nodeNode to look for Must not be NULL.
Returns
node if found
NULL if node is not a list member

Definition at line 283 of file clist.h.

◆ clist_find_before()

static clist_node_t* clist_find_before ( const clist_node_t list,
const clist_node_t node 
)
inlinestatic

Finds node and returns its predecessor.

Note
Complexity: O(n)
Parameters
[in]listpointer to clist
[in,out]nodeNode to look for Must not be NULL.
Returns
predecessor of node if found
NULL if node is not a list member

Definition at line 255 of file clist.h.

◆ clist_foreach()

static clist_node_t* clist_foreach ( clist_node_t list,
int(*)(clist_node_t *, void *)  func,
void *  arg 
)
inlinestatic

Traverse clist, call function for each member.

The pointer supplied by arg will be passed to every call to func.

If func returns non-zero, traversal will be aborted like when calling break within a for loop, returning the corresponding node.

Parameters
[in]listList to traverse.
[in]funcFunction to call for each member.
[in]argPointer to pass to every call to func
Returns
NULL on empty list or full traversal
node that caused func(node, arg) to exit non-zero

Definition at line 342 of file clist.h.

◆ clist_lpeek()

static clist_node_t* clist_lpeek ( const clist_node_t list)
inlinestatic

Returns first element in list.

Note
: Complexity: O(1)
Parameters
[in]listThe list to work upon.
Returns
first (leftmost) list element, or NULL if list is empty

Definition at line 200 of file clist.h.

◆ clist_lpop()

static clist_node_t* clist_lpop ( clist_node_t list)
inlinestatic

Removes and returns first element from list.

Note
Complexity: O(1)
Parameters
[in,out]listPointer to the list to remove first element from.

Definition at line 155 of file clist.h.

◆ clist_lpoprpush()

static void clist_lpoprpush ( clist_node_t list)
inlinestatic

Advances the circle list.

The result of this function is will be a list with nodes shifted by one. So second list entry will be first, first is last.

[ A, B, C ] becomes [ B, C, A ]

Note
Complexity: O(1)
Parameters
[in,out]listThe list to work upon.

Definition at line 185 of file clist.h.

◆ clist_lpush()

static void clist_lpush ( clist_node_t list,
clist_node_t new_node 
)
inlinestatic

Inserts new_node at the beginning of *list.

Note
Complexity: O(1)
Parameters
[in,out]listPointer to clist
[in,out]new_nodeNode which gets inserted. Must not be NULL.

Definition at line 135 of file clist.h.

◆ clist_remove()

static clist_node_t* clist_remove ( clist_node_t list,
clist_node_t node 
)
inlinestatic

Finds and removes node.

Note
Complexity: O(n)
Parameters
[in]listpointer to clist
[in,out]nodeNode to remove for Must not be NULL.
Returns
node if found and removed
NULL if node is not a list member

Definition at line 306 of file clist.h.

◆ clist_rpeek()

static clist_node_t* clist_rpeek ( const clist_node_t list)
inlinestatic

Returns last element in list.

Note
: Complexity: O(1)
Parameters
[in]listThe list to work upon.
Returns
last (rightmost) list element, or NULL if list is empty

Definition at line 216 of file clist.h.

◆ clist_rpop()

static clist_node_t* clist_rpop ( clist_node_t list)
inlinestatic

Removes and returns last element from list.

Note
Complexity: O(n) with n being the number of elements in the list.
Parameters
[in,out]listPointer to the list to remove last element from.

Definition at line 229 of file clist.h.

◆ clist_rpush()

static void clist_rpush ( clist_node_t list,
clist_node_t new_node 
)
inlinestatic

Appends new_node at the end of *list.

Note
Complexity: O(1)
Parameters
[in,out]listPointer to clist
[in,out]new_nodeNode which gets inserted. Must not be NULL.

Definition at line 114 of file clist.h.

◆ clist_sort()

static void clist_sort ( clist_node_t list,
clist_cmp_func_t  cmp 
)
inlinestatic

Sort a list.

This function will sort list using merge sort. The sorting algorithm runs in O(N log N) time. It is also stable.

Apart from the to-be-sorted list, the function needs a comparison function. That function will be called by the sorting implementation for every comparison. It gets two pointers a, b of type "clist_node_t" as parameters and must return <0, 0 or >0 if a is lesser, equal or larger than b.

Example:

typedef struct {
    clist_node_t next;
    uint32_t value;
} mylist_node_t;

int _cmp(clist_node_t *a, clist_node_t *b)
{
    uint32_t a_val = ((mylist_node_t *)a)->value;
    uint32_t b_val = ((mylist_node_t *)b)->value;

    if (a_val < b_val) {
        return -1;
    }
    else if (a_val > b_val) {
        return 1;
    }
    else {
        return 0;
    }
}

...

clist_sort(list, _cmp);
Parameters
[in,out]listList to sort
[in]cmpComparison function

Definition at line 417 of file clist.h.