1#include <enforce.h>
2#include <math/align.h>
3#include <mem/address_range.h>
4#include <structures/list.h>
5
6#ifdef DEBUG_LIST
7
8static bool list_link_is_plausible(const struct list_node *n) {
9 uintptr_t v = (uintptr_t) n;
10
11 return v >= ADDRESS_RANGE_KERNEL_START && IS_ALIGNED(v, sizeof(void *));
12}
13
14static bool list_node_looks_linked(const struct list_node *n) {
15 if (n->next == NULL || n->prev == NULL)
16 return false;
17
18 if (n->next == n || n->prev == n)
19 return false;
20
21 if (!list_link_is_plausible(n->next) || !list_link_is_plausible(n->prev))
22 return false;
23
24 return n->next->prev == n && n->prev->next == n;
25}
26
27void list_add_check(const struct list_node *new, const struct list_node *prev,
28 const struct list_node *next) {
29 if (cc_unlikely(new == NULL || prev == NULL || next == NULL))
30 panic("list_add: NULL operand (new %p, prev %p, next %p)", new, prev,
31 next);
32
33 if (cc_unlikely(prev->next != next))
34 panic(CORRUPTION, "list_add: prev %p ->next should be next %p, was %p",
35 prev, next, prev->next);
36
37 if (cc_unlikely(next->prev != prev))
38 panic(CORRUPTION, "list_add: next %p ->prev should be prev %p, was %p",
39 next, prev, next->prev);
40
41 if (cc_unlikely(new == prev || new == next))
42 panic(DUPLICATE, "list_add: double add of %p (prev %p, next %p)", new,
43 prev, next);
44
45 if (cc_unlikely(list_node_looks_linked(new)))
46 panic(DUPLICATE,
47 "list_add: %p is already linked (next %p, prev %p) -- adding it "
48 "to %p would unlink it; swapped arguments?",
49 new, new->next, new->prev, next);
50}
51
52void list_del_check(const struct list_node *entry) {
53 if (cc_unlikely(entry == NULL))
54 panic("list_del: NULL entry");
55
56 if (cc_unlikely(entry->next == NULL || entry->prev == NULL))
57 panic("list_del: %p already removed (next %p, prev %p)", entry,
58 entry->next, entry->prev);
59
60 if (cc_unlikely(entry->prev->next != entry))
61 panic(CORRUPTION, "list_del: %p ->prev %p ->next should be %p, was %p",
62 entry, entry->prev, entry, entry->prev->next);
63
64 if (cc_unlikely(entry->next->prev != entry))
65 panic(CORRUPTION, "list_del: %p ->next %p ->prev should be %p, was %p",
66 entry, entry->next, entry, entry->next->prev);
67}
68
69void list_splice_check(const struct list_node *list,
70 const struct list_node *prev,
71 const struct list_node *next) {
72 if (cc_unlikely(list == NULL || prev == NULL || next == NULL))
73 panic("list_splice: NULL operand (list %p, prev %p, next %p)", list,
74 prev, next);
75
76 if (cc_unlikely(prev->next != next || next->prev != prev))
77 panic(CORRUPTION,
78 "list_splice: destination prev %p ->next %p, next %p ->prev %p",
79 prev, prev->next, next, next->prev);
80
81 const struct list_node *first = list->next;
82 const struct list_node *last = list->prev;
83
84 if (cc_unlikely(first == NULL || last == NULL))
85 panic(UNINITIALIZED,
86 "list_splice: source %p is not initialised (next %p, prev %p)",
87 list, first, last);
88
89 if (cc_unlikely(first->prev != list || last->next != list))
90 panic(CORRUPTION,
91 "list_splice: source %p first %p ->prev %p, last %p ->next %p",
92 list, first, first->prev, last, last->next);
93}
94#endif /* DEBUG_LIST */
95
96void list_root_sort(struct list_node *head, list_cmp_fn cmp) {
97 if (head->next == head || head->next->next == head)
98 return;
99
100 struct list_node *list = head->next;
101 head->prev->next = NULL;
102 list->prev = NULL;
103
104 int insize = 1;
105
106 while (true) {
107 struct list_node *p = list;
108 list = NULL;
109 struct list_node *tail = NULL;
110 int nmerges = 0;
111
112 while (p) {
113 nmerges++;
114 struct list_node *q = p;
115 int psize = 0;
116 for (int i = 0; i < insize; i++) {
117 psize++;
118 q = q->next;
119 if (!q)
120 break;
121 }
122
123 int qsize = insize;
124
125 /* Merge the two lists */
126 while (psize > 0 || (qsize > 0 && q)) {
127 struct list_node *e;
128
129 if (psize == 0) {
130 e = q;
131 q = q->next;
132 qsize--;
133 } else if (qsize == 0 || !q) {
134 e = p;
135 p = p->next;
136 psize--;
137 } else if (cmp(p, q) <= 0) {
138 e = p;
139 p = p->next;
140 psize--;
141 } else {
142 e = q;
143 q = q->next;
144 qsize--;
145 }
146
147 if (tail)
148 tail->next = e;
149 else
150 list = e;
151
152 e->prev = tail;
153 tail = e;
154 }
155
156 p = q;
157 }
158
159 tail->next = NULL;
160
161 if (nmerges <= 1)
162 break;
163
164 insize *= 2;
165 }
166
167 struct list_node *prev = head;
168 struct list_node *curr = list;
169 while (curr) {
170 curr->prev = prev;
171 prev->next = curr;
172 prev = curr;
173 curr = curr->next;
174 }
175
176 prev->next = head;
177 head->prev = prev;
178}
179
180/* Example:
181 *
182 * int node_cmp(struct list_node *a, struct list_node *b) {
183 * struct node *na = list_entry(a, struct node, list);
184 * struct node *nb = list_entry(b, struct node, list);
185 * return (na->value > nb->value) - (na->value < nb->value);
186 * }
187 */
188