clist.h

Circular linked list.

This file contains a circularly and singly linked list implementation.

Its operations are:

operation runtime description
clist.h::clist_lpush() O(1) insert as head (leftmost node)
clist.h::clist_lpop() O(1) remove and return head (leftmost node)
clist.h::clist_rpush() O(1) append as tail (rightmost node)
clist.h::clist_rpop() O(n) remove and return tail (rightmost node)
clist.h::clist_find() O(n) find and return node
clist.h::clist_find_before() O(n) find node return node pointing to node
clist.h::clist_remove() O(n) remove and return node
clist.h::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.

Example:

Or use the clist.h::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.h::clist_rpush() for adding elements and clist.h::clist_lpop() for removal. Using clist.h::clist_lpush() and clist.h::clist_rpop() is inefficient due to clist.h::clist_rpop()’s O(n) runtime.

To use clist as stack, use clist.h::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 kernel_defines.h::container_of macro in list operations. See thread.h::thread_add_to_list() as example.

list.h::list_node_t clist_node_t

List node structure.

Used as is as reference to a list.

int(* clist_cmp_func_t()

Typedef for comparison function used by clist.h::clist_sort()

void clist_rpush(clist.h::clist_node_t * list, clist.h::clist_node_t * new_node)

Appends new_node at the end of *list.

Note

Complexity: O(1)

Parameters

list:Pointer to clist
new_node:Node which gets inserted. Must not be NULL.

void clist_lpush(clist.h::clist_node_t * list, clist.h::clist_node_t * new_node)

Inserts new_node at the beginning of *list.

Note

Complexity: O(1)

Parameters

list:Pointer to clist
new_node:Node which gets inserted. Must not be NULL.

clist.h::clist_node_t * clist_lpop(clist.h::clist_node_t * list)

Removes and returns first element from list.

Note

Complexity: O(1)

Parameters

list:Pointer to the list to remove first element from.

void clist_lpoprpush(clist.h::clist_node_t * list)

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

list:The list to work upon.

clist.h::clist_node_t * clist_lpeek(const clist.h::clist_node_t * list)

Returns first element in list.

Note

: Complexity: O(1)

Parameters

list:The list to work upon.

Return values

  • first (leftmost) list element, or NULL if list is empty
clist.h::clist_node_t * clist_rpeek(const clist.h::clist_node_t * list)

Returns last element in list.

Note

: Complexity: O(1)

Parameters

list:The list to work upon.

Return values

  • last (rightmost) list element, or NULL if list is empty
clist.h::clist_node_t * clist_rpop(clist.h::clist_node_t * list)

Removes and returns last element from list.

Note

Complexity: O(n) with n being the number of elements in the list.

Parameters

list:Pointer to the list to remove last element from.

clist.h::clist_node_t * clist_find_before(const clist.h::clist_node_t * list, const clist.h::clist_node_t * node)

Finds node and returns its predecessor.

Note

Complexity: O(n)

Parameters

list:pointer to clist
node:Node to look for Must not be NULL.

Return values

  • predecessor of node if found
  • NULL if node is not a list member
clist.h::clist_node_t * clist_find(const clist.h::clist_node_t * list, const clist.h::clist_node_t * node)

Finds and returns node.

Note

Complexity: O(n)

Parameters

list:pointer to clist
node:Node to look for Must not be NULL.

Return values

  • node if found
  • NULL if node is not a list member
clist.h::clist_node_t * clist_remove(clist.h::clist_node_t * list, clist.h::clist_node_t * node)

Finds and removes node.

Note

Complexity: O(n)

Parameters

list:pointer to clist
node:Node to remove for Must not be NULL.

Return values

  • node if found and removed
  • NULL if node is not a list member
clist.h::clist_node_t * clist_foreach(clist.h::clist_node_t * list, int(*)(clist.h::clist_node_t *, void *) func, void * arg)

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

list:List to traverse.
func:Function to call for each member.
arg:Pointer to pass to every call to func

Return values

  • NULL on empty list or full traversal
  • node that caused func(node, arg) to exit non-zero
clist.h::clist_node_t * _clist_sort(clist.h::clist_node_t * list_head, clist.h::clist_cmp_func_t cmp)

List sorting helper function.

void clist_sort(clist.h::clist_node_t * list, clist.h::clist_cmp_func_t cmp)

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:

Parameters

list:List to sort
cmp:Comparison function