Circular linked list. More...
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_is_empty() | O(1) | returns true if the list contains no elements |
| clist_exactly_one() | O(1) | returns true if the list contains one element |
| clist_more_than_one() | O(1) | returns true if the list contains more than one element |
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.
Definition in file clist.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. | |
| typedef int(* | clist_cmp_func_t) (clist_node_t *a, clist_node_t *b) |
| Typedef for comparison function used by clist_sort() | |
| static bool | clist_is_empty (const clist_node_t *list) |
| Checks if *list is empty. | |
| static void | clist_rpush (clist_node_t *list, clist_node_t *new_node) |
| Appends new_node at the end of *list. | |
| static void | clist_lpush (clist_node_t *list, clist_node_t *new_node) |
| Inserts new_node at the beginning of *list. | |
| static clist_node_t * | clist_lpop (clist_node_t *list) |
| Removes and returns first element from list. | |
| static void | clist_lpoprpush (clist_node_t *list) |
| Advances the circle list. | |
| static clist_node_t * | clist_lpeek (const clist_node_t *list) |
| Returns first element in list. | |
| static clist_node_t * | clist_rpeek (const clist_node_t *list) |
| Returns last element in list. | |
| static clist_node_t * | clist_rpop (clist_node_t *list) |
| Removes and returns last element from list. | |
| static clist_node_t * | clist_find_before (const clist_node_t *list, const clist_node_t *node) |
| Finds node and returns its predecessor. | |
| static clist_node_t * | clist_find (const clist_node_t *list, const clist_node_t *node) |
| Finds and returns node. | |
| static clist_node_t * | clist_remove (clist_node_t *list, clist_node_t *node) |
| Finds and removes node. | |
| 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. | |
| 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. | |
| static size_t | clist_count (clist_node_t *list) |
| Count the number of items in the given list. | |
| static bool | clist_exactly_one (clist_node_t *list) |
| Tells if a list has exactly one element. | |
| static bool | clist_more_than_one (clist_node_t *list) |
| Tells if a list has more than one element. | |
| typedef int(* clist_cmp_func_t) (clist_node_t *a, clist_node_t *b) |
Typedef for comparison function used by clist_sort()
| typedef list_node_t clist_node_t |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
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.
| [in] | list | List to traverse. |
| [in] | func | Function to call for each member. |
| [in] | arg | Pointer to pass to every call to func |
func(node, arg) to exit non-zero
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
inlinestatic |
|
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);
| [in,out] | list | List to sort |
| [in] | cmp | Comparison function |
1.12.0