1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#pragma once
4
5#include <mos/types.h>
6
7/**
8 * @defgroup linked_list libs.LinkedList
9 * @ingroup libs
10 * @brief A circular, doubly-linked list.
11 * @{
12 */
13
14typedef struct list_node list_node_t;
15
16/**
17 * @brief A linked list head.
18 *
19 * @note The list head should be placed in the heap, not on the stack.
20 * This is because the list head is a circular list, and the
21 * `prev' and `next' pointers of the list head point to itself.
22 */
23typedef list_node_t list_head;
24
25/** @brief A node in a linked list. */
26struct list_node
27{
28 list_node_t *prev;
29 list_node_t *next;
30};
31
32/**
33 * @brief Embed a list node into a struct
34 */
35#define as_linked_list list_node_t list_node
36
37// clang-format off
38#define LIST_HEAD_INIT(container) { .prev = &(container), .next = &(container) }
39// clang-format on
40
41#define LIST_NODE_INIT(container) LIST_HEAD_INIT(container.list_node)
42
43/**
44 * @brief Get the container struct of a list node
45 */
46#define list_entry(node, type) container_of((node), type, list_node)
47
48/**
49 * @brief Get the next element in a list
50 */
51#define list_prev_entry(item, type) list_entry(list_node(item)->prev, type)
52
53/**
54 * @brief Get the next element in a list
55 */
56#define list_next_entry(item, type) list_entry(list_node(item)->next, type)
57
58/**
59 * @brief Get the next list node
60 *
61 */
62#define list_node_next_entry(node, type) container_of((node)->next, type, list_node)
63
64/**
65 * @brief Get the `list_node' of a list element.
66 * This is exactly the reverse of `list_entry' above.
67 */
68#define list_node(element) (&((element)->list_node))
69
70#define list_prepend(element, item) list_node_prepend(list_node(element), list_node(item))
71#define list_append(element, item) list_node_append(list_node(element), list_node(item))
72#define list_insert_before(element, item) list_node_insert_before(list_node(element), list_node(item))
73#define list_insert_after(element, item) list_node_insert_after(list_node(element), list_node(item))
74#define list_remove(element) list_node_remove(list_node(element))
75
76/**
77 * @brief Iterate over a list
78 *
79 * @param t Type of the list elements (e.g. `struct foo')
80 * @param v Name of the variable to use for the current element (e.g. `item')
81 * @param h List Head (e.g. `consoles')
82 */
83#define list_foreach(t, v, h) \
84 for (__typeof(list_entry(&(h), t)) v = list_entry((h).next, t), __next = list_next_entry(v, t); list_node(v) != &(h); v = __next, __next = list_next_entry(v, t))
85
86#define list_foreach_reverse(t, v, h) \
87 for (__typeof(list_entry(&(h), t)) v = list_entry((h).prev, t), __next = list_prev_entry(v, t); list_node(v) != &(h); v = __next, __next = list_prev_entry(v, t))
88
89#define list_node_foreach(v, h) for (list_node_t *v = (h)->next, *__next = v->next; v != (h); v = __next, __next = v->next)
90#define list_node_foreach_reverse(v, h) for (list_node_t *v = (h)->prev, *__next = v->prev; v != (h); v = __next, __next = v->prev)
91
92#define list_headless_foreach(t, v, h) \
93 for (__typeof(&(h)) v = &(h), __next = list_next_entry(v, t), __head = NULL; (v) != __head; \
94 v = __next, __next = list_next_entry(v, t), __head = __head == NULL ? &(h) : __head)
95
96#define list_headless_foreach_reverse(t, v, h) \
97 for (__typeof(h) v = (h), __next = list_prev_entry(v, t), __head = NULL; (v) != __head; \
98 v = __next, __next = list_prev_entry(v, t), __head = __head == NULL ? (h) : __head)
99
100MOSAPI void linked_list_init(list_node_t *head_node);
101MOSAPI bool list_is_empty(const list_node_t *head);
102MOSAPI void list_node_remove(list_node_t *link);
103
104MOSAPI list_node_t *list_node_pop(list_node_t *head);
105MOSAPI void list_node_prepend(list_node_t *head, list_node_t *item);
106MOSAPI void list_node_append(list_node_t *head, list_node_t *item);
107MOSAPI void list_node_insert_before(list_node_t *element, list_node_t *item);
108MOSAPI void list_node_insert_after(list_node_t *element, list_node_t *item);
109
110/** @} */
111