1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#include <mos/lib/structures/list.hpp>
4
5// Note: The nullability of each parameter is not checked, because results will be the same no matter what.
6// (i.e. kernel panic / process termination)
7
8/**
9 * @brief Initialise a circular double linked list
10 * @post head_node->next == head_node
11 * @post head_node->prev == head_node
12 *
13 * @param node The list head node (and thus, the only element in the newly created list)
14 */
15void linked_list_init(list_node_t *node)
16{
17 node->prev = node;
18 node->next = node;
19}
20
21bool list_is_empty(const list_node_t *head)
22{
23 return head->next == head;
24}
25
26void list_node_remove(list_node_t *node)
27{
28 node->prev->next = node->next;
29 node->next->prev = node->prev;
30
31 // detach the node from the list
32 node->next = node;
33 node->prev = node;
34}
35
36// ! Internal API
37/**
38 * @brief Insert a node into a list
39 * @post node->next == next
40 * @post node->prev == prev
41 * @post prev->next == node
42 * @post next->prev == node
43 *
44 * @param prev The node before the insertion point
45 * @param new_node The node to insert
46 * @param next The node after the insertion point
47 */
48static void list_node_insert(list_node_t *prev, list_node_t *new_node, list_node_t *next)
49{
50 new_node->prev = prev;
51 new_node->next = next;
52 prev->next = new_node;
53 next->prev = new_node;
54}
55
56list_node_t *list_node_pop(list_node_t *head)
57{
58 list_node_t *node = head->next;
59 list_node_remove(node);
60 return node;
61}
62
63void list_node_prepend(list_node_t *head, list_node_t *item)
64{
65 list_node_insert(prev: head, new_node: item, next: head->next);
66}
67
68void list_node_append(list_node_t *head, list_node_t *item)
69{
70 // The list is circular, so accessing the list tail is like the prev of its head.
71 list_node_insert(prev: head->prev, new_node: item, next: head);
72}
73
74void list_node_insert_before(list_node_t *element, list_node_t *item)
75{
76 list_node_insert(prev: element->prev, new_node: item, next: element);
77}
78
79void list_node_insert_after(list_node_t *element, list_node_t *item)
80{
81 list_node_insert(prev: element, new_node: item, next: element->next);
82}
83