Circular linked list.
This file contains a circularly and singly linked list implementation.
Its operations are:
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.
| 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_t * | clist_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_t * | clist_lpeek (const clist_node_t *list) |
| | Returns first element in list. More...
|
| |
| static clist_node_t * | clist_rpeek (const clist_node_t *list) |
| | Returns last element in list. More...
|
| |
| static clist_node_t * | clist_rpop (clist_node_t *list) |
| | Removes and returns last element from list. More...
|
| |
| static clist_node_t * | clist_find_before (const clist_node_t *list, const clist_node_t *node) |
| | Finds node and returns its predecessor. More...
|
| |
| static clist_node_t * | clist_find (const clist_node_t *list, const clist_node_t *node) |
| | Finds and returns node. More...
|
| |
| static clist_node_t * | clist_remove (clist_node_t *list, clist_node_t *node) |
| | Finds and removes node. More...
|
| |
| 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. 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...
|
| |
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] | list | List to sort |
| [in] | cmp | Comparison function |
Definition at line 424 of file clist.h.
Include dependency graph for clist.h: