1 | // SPDX-License-Identifier: GPL-3.0-or-later |
2 | |
3 | #include <mos/lib/structures/list.h> |
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 | */ |
15 | void linked_list_init(list_node_t *node) |
16 | { |
17 | node->prev = node; |
18 | node->next = node; |
19 | } |
20 | |
21 | bool list_is_empty(const list_node_t *head) |
22 | { |
23 | return head->next == head; |
24 | } |
25 | |
26 | void 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 | */ |
48 | static 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 | |
56 | list_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 | |
63 | void 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 | |
68 | void 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 | |
74 | void 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 | |
79 | void 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 | |