1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#include "test_engine_impl.h"
4
5#include <mos/lib/structures/list.h>
6
7typedef struct
8{
9 int value_before;
10 as_linked_list;
11 int value_after;
12} test_structure;
13
14MOS_TEST_CASE(test_list_init)
15{
16 test_structure pp = { 0, LIST_NODE_INIT(pp), 1 };
17
18 MOS_TEST_CHECK(pp.value_before, 0);
19 MOS_TEST_CHECK(pp.value_after, 1);
20
21 MOS_TEST_CHECK(pp.list_node.prev, &pp.list_node);
22 MOS_TEST_CHECK(pp.list_node.next, &pp.list_node);
23
24 list_node_t head = LIST_HEAD_INIT(head);
25 MOS_TEST_CHECK(head.next, &head);
26 MOS_TEST_CHECK(head.prev, &head);
27
28 // Check is_empty() on an empty list
29 bool is_empty = list_is_empty(head: &head);
30 MOS_TEST_CHECK(is_empty, true);
31
32 // Check is_empty() on a non-empty list
33 test_structure p1 = { 0, LIST_NODE_INIT(p1), 1 };
34 list_node_append(head: &head, item: &p1.list_node);
35 is_empty = list_is_empty(head: &head);
36 MOS_TEST_CHECK(is_empty, false);
37}
38
39MOS_TEST_CASE(test_list_node_append)
40{
41 list_node_t list_head = LIST_HEAD_INIT(list_head);
42 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
43 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
44 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
45 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
46 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
47 list_node_append(head: &list_head, item: &s1.list_node); // list_head -> s1
48 list_node_append(head: &list_head, item: &s2.list_node); // list_head -> s1 -> s2
49 list_node_append(head: &list_head, item: &s3.list_node); // list_head -> s1 -> s2 -> s3
50 list_node_append(head: &list_head, item: &s4.list_node); // list_head -> s1 -> s2 -> s3 -> s4
51 list_node_append(head: &list_head, item: &s5.list_node); // list_head -> s1 -> s2 -> s3 -> s4 -> s5
52
53 // next pointer
54 MOS_TEST_CHECK(list_head.next, &s1.list_node);
55 MOS_TEST_CHECK(s1.list_node.next, &s2.list_node);
56 MOS_TEST_CHECK(s2.list_node.next, &s3.list_node);
57 MOS_TEST_CHECK(s3.list_node.next, &s4.list_node);
58 MOS_TEST_CHECK(s4.list_node.next, &s5.list_node);
59 MOS_TEST_CHECK(s5.list_node.next, &list_head);
60
61 // prev pointer
62 MOS_TEST_CHECK(list_head.prev, &s5.list_node);
63 MOS_TEST_CHECK(s5.list_node.prev, &s4.list_node);
64 MOS_TEST_CHECK(s4.list_node.prev, &s3.list_node);
65 MOS_TEST_CHECK(s3.list_node.prev, &s2.list_node);
66 MOS_TEST_CHECK(s2.list_node.prev, &s1.list_node);
67 MOS_TEST_CHECK(s1.list_node.prev, &list_head);
68}
69
70// prepending is really the same as appending to the head.
71MOS_TEST_CASE(test_list_node_prepend)
72{
73 list_node_t list_head = LIST_HEAD_INIT(list_head);
74 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
75 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
76 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
77 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
78 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
79 list_node_prepend(head: &list_head, item: &s5.list_node); // s5 -> list_head
80 list_node_prepend(head: &list_head, item: &s4.list_node); // s4 -> s5 -> list_head
81 list_node_prepend(head: &list_head, item: &s3.list_node); // s3 -> s4 -> s5 -> list_head
82 list_node_prepend(head: &list_head, item: &s2.list_node); // s2 -> s3 -> s4 -> s5 -> list_head
83 list_node_prepend(head: &list_head, item: &s1.list_node); // s1 -> s2 -> s3 -> s4 -> s5 -> list_head
84
85 // next pointer
86 MOS_TEST_CHECK(list_head.next, &s1.list_node);
87 MOS_TEST_CHECK(s1.list_node.next, &s2.list_node);
88 MOS_TEST_CHECK(s2.list_node.next, &s3.list_node);
89 MOS_TEST_CHECK(s3.list_node.next, &s4.list_node);
90 MOS_TEST_CHECK(s4.list_node.next, &s5.list_node);
91 MOS_TEST_CHECK(s5.list_node.next, &list_head);
92
93 // prev pointer
94 MOS_TEST_CHECK(list_head.prev, &s5.list_node);
95 MOS_TEST_CHECK(s5.list_node.prev, &s4.list_node);
96 MOS_TEST_CHECK(s4.list_node.prev, &s3.list_node);
97 MOS_TEST_CHECK(s3.list_node.prev, &s2.list_node);
98 MOS_TEST_CHECK(s2.list_node.prev, &s1.list_node);
99 MOS_TEST_CHECK(s1.list_node.prev, &list_head);
100}
101
102MOS_TEST_CASE(test_list_node_insert)
103{
104 list_node_t list_head = LIST_HEAD_INIT(list_head);
105 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
106 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
107 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
108 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
109 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
110
111 test_structure new_s = { 11, LIST_NODE_INIT(new_s), 12 };
112 test_structure new_s2 = { 13, LIST_NODE_INIT(new_s2), 14 };
113
114 // Connect the list.
115 list_node_append(head: &list_head, item: &s1.list_node); // list_head -> s1
116 list_node_append(head: &list_head, item: &s2.list_node); // list_head -> s1 -> s2
117 list_node_append(head: &list_head, item: &s3.list_node); // list_head -> s1 -> s2 -> s3
118 list_node_append(head: &list_head, item: &s4.list_node); // list_head -> s1 -> s2 -> s3 -> s4
119 list_node_append(head: &list_head, item: &s5.list_node); // list_head -> s1 -> s2 -> s3 -> s4 -> s5
120
121 // Insert a new node before s3.
122 list_node_insert_before(element: &s3.list_node, item: &new_s.list_node); // s1 -> s2 -> new_s -> s3 -> s4 -> s5 -> list_head
123 MOS_TEST_CHECK(new_s.list_node.next, &s3.list_node);
124 MOS_TEST_CHECK(new_s.list_node.prev, &s2.list_node);
125 MOS_TEST_CHECK(s2.list_node.next, &new_s.list_node);
126 MOS_TEST_CHECK(s3.list_node.prev, &new_s.list_node);
127
128 // original parts of the list should be unchanged.
129 MOS_TEST_CHECK(s2.list_node.prev, &s1.list_node);
130 MOS_TEST_CHECK(s3.list_node.next, &s4.list_node);
131
132 // Insert a new node after s4
133 list_node_insert_after(element: &s4.list_node, item: &new_s2.list_node); // s1 -> s2 -> new_s -> s3 -> s4 -> new_s2 -> s5 -> list_head
134 MOS_TEST_CHECK(new_s2.list_node.next, &s5.list_node);
135 MOS_TEST_CHECK(new_s2.list_node.prev, &s4.list_node);
136 MOS_TEST_CHECK(s4.list_node.next, &new_s2.list_node);
137 MOS_TEST_CHECK(s5.list_node.prev, &new_s2.list_node);
138
139 // original parts of the list should be unchanged.
140 MOS_TEST_CHECK(s4.list_node.prev, &s3.list_node);
141 MOS_TEST_CHECK(s5.list_node.next, &list_head);
142}
143
144MOS_TEST_CASE(test_list_remove)
145{
146 list_node_t list_head = LIST_HEAD_INIT(list_head);
147 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
148 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
149 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
150 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
151 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
152 list_node_append(head: &list_head, item: &s1.list_node); // list_head -> s1
153 list_node_append(head: &list_head, item: &s2.list_node); // list_head -> s1 -> s2
154 list_node_append(head: &list_head, item: &s3.list_node); // list_head -> s1 -> s2 -> s3
155 list_node_append(head: &list_head, item: &s4.list_node); // list_head -> s1 -> s2 -> s3 -> s4
156 list_node_append(head: &list_head, item: &s5.list_node); // list_head -> s1 -> s2 -> s3 -> s4 -> s5
157
158 // Remove s3.
159 list_node_remove(link: &s3.list_node); // list_head -> s1 -> s2 -> s4 -> s5
160 MOS_TEST_CHECK(s1.list_node.next, &s2.list_node);
161 MOS_TEST_CHECK(s2.list_node.next, &s4.list_node);
162 MOS_TEST_CHECK(s4.list_node.next, &s5.list_node);
163 MOS_TEST_CHECK(s5.list_node.next, &list_head);
164 MOS_TEST_CHECK(list_head.prev, &s5.list_node);
165
166 MOS_TEST_CHECK(s1.list_node.prev, &list_head);
167 MOS_TEST_CHECK(s2.list_node.prev, &s1.list_node);
168 MOS_TEST_CHECK(s4.list_node.prev, &s2.list_node);
169 MOS_TEST_CHECK(s5.list_node.prev, &s4.list_node);
170 MOS_TEST_CHECK(list_head.next, &s1.list_node);
171}
172
173MOS_TEST_CASE(test_list_macros)
174{
175 list_node_t list_head = LIST_HEAD_INIT(list_head);
176 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
177 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
178
179 MOS_TEST_CHECK(list_entry(&s1.list_node, test_structure), &s1);
180 MOS_TEST_CHECK(list_entry(&s2.list_node, test_structure)->value_before, s2.value_before);
181 MOS_TEST_CHECK(list_entry(&s2.list_node, test_structure)->value_after, s2.value_after);
182
183 MOS_TEST_CHECK(list_node(&s1), &s1.list_node);
184}
185
186MOS_TEST_CASE(test_list_foreach)
187{
188 list_node_t list_head = LIST_HEAD_INIT(list_head);
189 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
190 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
191 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
192 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
193 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
194 list_node_append(head: &list_head, item: &s1.list_node); // list_head -> s1
195 list_node_append(head: &list_head, item: &s2.list_node); // list_head -> s1 -> s2
196 list_node_append(head: &list_head, item: &s3.list_node); // list_head -> s1 -> s2 -> s3
197 list_node_append(head: &list_head, item: &s4.list_node); // list_head -> s1 -> s2 -> s3 -> s4
198 list_node_append(head: &list_head, item: &s5.list_node); // list_head -> s1 -> s2 -> s3 -> s4 -> s5
199 int i = 0;
200 list_node_t *node = list_head.next;
201 while (node != &list_head)
202 {
203 i++;
204 node = node->next;
205 }
206 MOS_TEST_CHECK(i, 5);
207
208 // sum the list.
209 int sum_before = 0;
210 int sum_after = 0;
211 list_foreach(test_structure, node, list_head)
212 {
213 sum_before += node->value_before;
214 sum_after += node->value_after;
215 }
216 MOS_TEST_CHECK(sum_before, 25);
217 MOS_TEST_CHECK(sum_after, 30);
218}
219
220MOS_TEST_CASE(test_list_headless_foreach)
221{
222 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
223 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
224 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
225 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
226 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
227 list_append(&s1, &s2); // s1 -> s2
228 list_append(&s1, &s3); // s1 -> s2 -> s3
229 list_append(&s1, &s4); // s1 -> s2 -> s3 -> s4
230 list_append(&s1, &s5); // s1 -> s2 -> s3 -> s4 -> s5
231 int i = 0;
232 test_structure *this = &s1;
233 do
234 {
235 i++;
236 this = list_next_entry(this, test_structure);
237 } while (this != &s1);
238 MOS_TEST_CHECK(i, 5);
239
240 // sum the list.
241 int sum_before = 0;
242 int sum_after = 0;
243 list_headless_foreach(test_structure, node, s1)
244 {
245 sum_before += node->value_before;
246 sum_after += node->value_after;
247 }
248 MOS_TEST_CHECK(sum_before, 25);
249 MOS_TEST_CHECK(sum_after, 30);
250
251 // sum the list, starting from s3.
252 sum_before = 0;
253 sum_after = 0;
254 list_headless_foreach(test_structure, node, s3)
255 {
256 sum_before += node->value_before;
257 sum_after += node->value_after;
258 }
259 MOS_TEST_CHECK(sum_before, 25);
260 MOS_TEST_CHECK(sum_after, 30);
261
262 // sum the list, starting from s5.
263 sum_before = 0;
264 sum_after = 0;
265 list_headless_foreach(test_structure, node, s5)
266 {
267 sum_before += node->value_before;
268 sum_after += node->value_after;
269 }
270 MOS_TEST_CHECK(sum_before, 25);
271 MOS_TEST_CHECK(sum_after, 30);
272
273 // reverse sum the list.
274 sum_before = 0;
275 sum_after = 0;
276 list_headless_foreach_reverse(test_structure, node, &s1)
277 {
278 sum_before += node->value_before;
279 sum_after += node->value_after;
280 }
281 MOS_TEST_CHECK(sum_before, 25);
282 MOS_TEST_CHECK(sum_after, 30);
283
284 // reverse sum the list, starting from s3.
285 sum_before = 0;
286 sum_after = 0;
287 list_headless_foreach_reverse(test_structure, node, &s3)
288 {
289 sum_before += node->value_before;
290 sum_after += node->value_after;
291 }
292 MOS_TEST_CHECK(sum_before, 25);
293 MOS_TEST_CHECK(sum_after, 30);
294}
295
296MOS_TEST_CASE(test_list_safe_foreach)
297{
298 list_node_t list_head = LIST_HEAD_INIT(list_head);
299 test_structure s1 = { 1, LIST_NODE_INIT(s1), 2 };
300 test_structure s2 = { 3, LIST_NODE_INIT(s2), 4 };
301 test_structure s3 = { 5, LIST_NODE_INIT(s3), 6 };
302 test_structure s4 = { 7, LIST_NODE_INIT(s4), 8 };
303 test_structure s5 = { 9, LIST_NODE_INIT(s5), 10 };
304 list_node_append(head: &list_head, item: &s1.list_node); // list_head -> s1
305 list_node_append(head: &list_head, item: &s2.list_node); // list_head -> s1 -> s2
306 list_node_append(head: &list_head, item: &s3.list_node); // list_head -> s1 -> s2 -> s3
307 list_node_append(head: &list_head, item: &s4.list_node); // list_head -> s1 -> s2 -> s3 -> s4
308 list_node_append(head: &list_head, item: &s5.list_node); // list_head -> s1 -> s2 -> s3 -> s4 -> s5
309
310 // count the list.
311 size_t count = 0;
312 list_node_t *node = list_head.next;
313 while (node != &list_head)
314 {
315 count++;
316 node = node->next;
317 }
318 MOS_TEST_CHECK(count, 5);
319
320 // sum the list.
321 int sum_before = 0;
322 int sum_after = 0;
323 list_foreach(test_structure, node, list_head)
324 {
325 sum_before += node->value_before;
326 sum_after += node->value_after;
327 }
328 MOS_TEST_CHECK(sum_before, 25);
329 MOS_TEST_CHECK(sum_after, 30);
330
331 // sum the list, and in the loop, remove s3.
332 sum_before = 0;
333 sum_after = 0;
334 list_foreach(test_structure, node, list_head)
335 {
336 sum_before += node->value_before;
337 sum_after += node->value_after;
338 if (node == &s3)
339 {
340 list_node_remove(link: &s3.list_node);
341 }
342 }
343 MOS_TEST_CHECK(sum_before, 25);
344 MOS_TEST_CHECK(sum_after, 30);
345
346 // count the list.
347 count = 0;
348 list_foreach(test_structure, node, list_head)
349 {
350 count++;
351 }
352 MOS_TEST_CHECK(count, 4);
353}
354