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