1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#pragma once
4
5#include <mos/types.hpp>
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 = this;
29 list_node_t *next = this;
30
31 list_node()
32 {
33 prev = this;
34 next = this;
35 }
36};
37
38/**
39 * @brief Embed a list node into a struct
40 */
41#define as_linked_list list_node_t list_node
42
43// clang-format off
44#define LIST_HEAD_INIT(container) { .prev = &(container), .next = &(container) }
45// clang-format on
46
47#define LIST_NODE_INIT(container) LIST_HEAD_INIT(container.list_node)
48
49/**
50 * @brief Get the container struct of a list node
51 */
52#define list_entry(node, type) container_of((node), type, list_node)
53
54/**
55 * @brief Get the next element in a list
56 */
57#define list_prev_entry(item, type) list_entry(list_node(item)->prev, type)
58
59/**
60 * @brief Get the next element in a list
61 */
62#define list_next_entry(item, type) list_entry(list_node(item)->next, type)
63
64/**
65 * @brief Get the next list node
66 *
67 */
68#define list_node_next_entry(node, type) container_of((node)->next, type, list_node)
69
70/**
71 * @brief Get the `list_node' of a list element.
72 * This is exactly the reverse of `list_entry' above.
73 */
74#define list_node(element) (&((element)->list_node))
75
76#define list_prepend(element, item) list_node_prepend(list_node(element), list_node(item))
77#define list_append(element, item) list_node_append(list_node(element), list_node(item))
78#define list_insert_before(element, item) list_node_insert_before(list_node(element), list_node(item))
79#define list_insert_after(element, item) list_node_insert_after(list_node(element), list_node(item))
80#define list_remove(element) list_node_remove(list_node(element))
81
82/**
83 * @brief Iterate over a list
84 *
85 * @param t Type of the list elements (e.g. `struct foo')
86 * @param v Name of the variable to use for the current element (e.g. `item')
87 * @param h List Head (e.g. `consoles')
88 */
89#define list_foreach(t, v, h) for (auto v = list_entry((h).next, t), __next = list_next_entry(v, t); list_node(v) != &(h); v = __next, __next = list_next_entry(v, t))
90
91#define list_foreach_reverse(t, v, h) \
92 for (auto v = list_entry((h).prev, t), __next = list_prev_entry(v, t); list_node(v) != &(h); v = __next, __next = list_prev_entry(v, t))
93
94#define list_node_foreach(v, h) for (list_node_t *v = (h)->next, *__next = v->next; v != (h); v = __next, __next = v->next)
95#define list_node_foreach_reverse(v, h) for (list_node_t *v = (h)->prev, *__next = v->prev; v != (h); v = __next, __next = v->prev)
96
97#define list_headless_foreach(t, v, h) \
98 for (t *v = &(h), *__next = list_next_entry(v, t), *__head = nullptr; (v) != __head; \
99 v = __next, __next = list_next_entry(v, t), __head = __head == nullptr ? &(h) : __head)
100
101#define list_headless_foreach_reverse(t, v, h) \
102 for (t *v = &(h), *__next = list_prev_entry(v, t), *__head = nullptr; (v) != __head; \
103 v = __next, __next = list_prev_entry(v, t), __head = __head == nullptr ? &(h) : __head)
104
105MOSAPI void linked_list_init(list_node_t *head_node);
106MOSAPI bool list_is_empty(const list_node_t *head);
107MOSAPI void list_node_remove(list_node_t *link);
108
109MOSAPI list_node_t *list_node_pop(list_node_t *head);
110MOSAPI void list_node_prepend(list_node_t *head, list_node_t *item);
111MOSAPI void list_node_append(list_node_t *head, list_node_t *item);
112MOSAPI void list_node_insert_before(list_node_t *element, list_node_t *item);
113MOSAPI void list_node_insert_after(list_node_t *element, list_node_t *item);
114
115/** @} */
116