1 /*
2 * Copyright (c) 2019 Intel Corporation
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 #include <zephyr/ztest.h>
8 #include <zephyr/sys/sflist.h>
9
10 static sys_sflist_t test_list;
11 static sys_sflist_t append_list;
12
13 struct container_node {
14 sys_sfnode_t node;
15 int unused;
16 };
17
18 static struct container_node test_node_1;
19 static struct container_node test_node_2;
20 static struct container_node test_node_3;
21 static struct container_node test_node_4;
22
verify_emptyness(sys_sflist_t * list)23 static inline bool verify_emptyness(sys_sflist_t *list)
24 {
25 sys_sfnode_t *node;
26 sys_sfnode_t *s_node;
27 struct container_node *cnode;
28 struct container_node *s_cnode;
29 int count;
30
31 if (!sys_sflist_is_empty(list)) {
32 return false;
33 }
34
35 if (sys_sflist_peek_head(list)) {
36 return false;
37 }
38
39 if (sys_sflist_peek_tail(list)) {
40 return false;
41 }
42
43 if (sys_sflist_len(list) != 0) {
44 return false;
45 }
46
47 count = 0;
48 SYS_SFLIST_FOR_EACH_NODE(list, node) {
49 count++;
50 }
51
52 if (count) {
53 return false;
54 }
55
56 SYS_SFLIST_FOR_EACH_NODE_SAFE(list, node, s_node) {
57 count++;
58 }
59
60 if (count) {
61 return false;
62 }
63
64 count = 0;
65 SYS_SFLIST_FOR_EACH_CONTAINER(list, cnode, node) {
66 count++;
67 }
68
69 if (count) {
70 return false;
71 }
72
73 count = 0;
74 SYS_SFLIST_FOR_EACH_CONTAINER_SAFE(list, cnode, s_cnode, node) {
75 count++;
76 }
77
78 if (count) {
79 return false;
80 }
81
82 return true;
83 }
84
verify_content_amount(sys_sflist_t * list,int amount)85 static inline bool verify_content_amount(sys_sflist_t *list, int amount)
86 {
87 sys_sfnode_t *node;
88 sys_sfnode_t *s_node;
89 struct container_node *cnode;
90 struct container_node *s_cnode;
91 int count;
92
93 if (sys_sflist_is_empty(list)) {
94 return false;
95 }
96
97 if (!sys_sflist_peek_head(list)) {
98 return false;
99 }
100
101 if (!sys_sflist_peek_tail(list)) {
102 return false;
103 }
104
105 if (sys_sflist_len(list) != amount) {
106 return false;
107 }
108
109 count = 0;
110 SYS_SFLIST_FOR_EACH_NODE(list, node) {
111 count++;
112 }
113
114 if (count != amount) {
115 return false;
116 }
117
118 count = 0;
119 SYS_SFLIST_FOR_EACH_NODE_SAFE(list, node, s_node) {
120 count++;
121 }
122
123 if (count != amount) {
124 return false;
125 }
126
127 count = 0;
128 SYS_SFLIST_FOR_EACH_CONTAINER(list, cnode, node) {
129 count++;
130 }
131
132 if (count != amount) {
133 return false;
134 }
135
136 count = 0;
137 SYS_SFLIST_FOR_EACH_CONTAINER_SAFE(list, cnode, s_cnode, node) {
138 count++;
139 }
140
141 if (count != amount) {
142 return false;
143 }
144
145 return true;
146 }
147
verify_tail_head(sys_sflist_t * list,sys_sfnode_t * head,sys_sfnode_t * tail,bool same)148 static inline bool verify_tail_head(sys_sflist_t *list,
149 sys_sfnode_t *head,
150 sys_sfnode_t *tail,
151 bool same)
152 {
153 if (sys_sflist_peek_head(list) != head) {
154 return false;
155 }
156
157 if (sys_sflist_peek_tail(list) != tail) {
158 return false;
159 }
160
161 if (same) {
162 if (sys_sflist_peek_head(list) != sys_sflist_peek_tail(list)) {
163 return false;
164 }
165 } else {
166 if (sys_sflist_peek_head(list) == sys_sflist_peek_tail(list)) {
167 return false;
168 }
169 }
170
171 return true;
172 }
173 /**
174 * @addtogroup kernel_common_tests
175 * @{
176 */
177
178 /**
179 * @brief Test singly linked list functionalities
180 *
181 * @details Test list initialization, append item to the list,
182 * find and remove item, prepend, append, remove list
183 *
184 * @see sys_sflist_init(), sys_sflist_append(),
185 * sys_sflist_find_and_remove(), sys_sflist_prepend(),
186 * sys_sflist_remove(), sys_sflist_get(), sys_sflist_get_not_empty(),
187 * sys_sflist_append_list(), sys_sflist_merge_list()
188 */
ZTEST(dlist_api,test_sflist)189 ZTEST(dlist_api, test_sflist)
190 {
191 sys_sflist_init(&test_list);
192
193 zassert_true((verify_emptyness(&test_list)),
194 "test_list should be empty");
195
196 /* Appending node 1 */
197 sys_sflist_append(&test_list, &test_node_1.node);
198 zassert_true((verify_content_amount(&test_list, 1)),
199 "test_list has wrong content");
200
201 zassert_true((verify_tail_head(&test_list, &test_node_1.node,
202 &test_node_1.node, true)),
203 "test_list head/tail are wrong");
204
205 /* Finding and removing node 1 */
206 sys_sflist_find_and_remove(&test_list, &test_node_1.node);
207 zassert_true((verify_emptyness(&test_list)),
208 "test_list should be empty");
209
210 /* Prepending node 1 */
211 sys_sflist_prepend(&test_list, &test_node_1.node);
212 zassert_true((verify_content_amount(&test_list, 1)),
213 "test_list has wrong content");
214
215 zassert_true((verify_tail_head(&test_list, &test_node_1.node,
216 &test_node_1.node, true)),
217 "test_list head/tail are wrong");
218
219 /* Removing node 1 */
220 sys_sflist_remove(&test_list, NULL, &test_node_1.node);
221 zassert_true((verify_emptyness(&test_list)),
222 "test_list should be empty");
223
224 /* Appending node 1 */
225 sys_sflist_append(&test_list, &test_node_1.node);
226 /* Prepending node 2 */
227 sys_sflist_prepend(&test_list, &test_node_2.node);
228
229 zassert_true((verify_content_amount(&test_list, 2)),
230 "test_list has wrong content");
231
232 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
233 &test_node_1.node, false)),
234 "test_list head/tail are wrong");
235
236 /* Appending node 3 */
237 sys_sflist_append(&test_list, &test_node_3.node);
238
239 zassert_true((verify_content_amount(&test_list, 3)),
240 "test_list has wrong content");
241
242 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
243 &test_node_3.node, false)),
244 "test_list head/tail are wrong");
245
246 zassert_true((sys_sflist_peek_next(&test_node_2.node) ==
247 &test_node_1.node),
248 "test_list node links are wrong");
249
250 /* Inserting node 4 after node 2, peek with nocheck variant */
251 sys_sflist_insert(&test_list, &test_node_2.node, &test_node_4.node);
252
253 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
254 &test_node_3.node, false)),
255 "test_list head/tail are wrong");
256
257 zassert_true((sys_sflist_peek_next_no_check(&test_node_2.node) ==
258 &test_node_4.node),
259 "test_list node links are wrong");
260
261 /* Finding and removing node 1 */
262 sys_sflist_find_and_remove(&test_list, &test_node_1.node);
263 zassert_true((verify_content_amount(&test_list, 3)),
264 "test_list has wrong content");
265
266 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
267 &test_node_3.node, false)),
268 "test_list head/tail are wrong");
269
270 /* Removing node 3 */
271 sys_sflist_remove(&test_list, &test_node_4.node, &test_node_3.node);
272 zassert_true((verify_content_amount(&test_list, 2)),
273 "test_list has wrong content");
274
275 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
276 &test_node_4.node, false)),
277 "test_list head/tail are wrong");
278
279 /* Removing node 4 */
280 sys_sflist_remove(&test_list, &test_node_2.node, &test_node_4.node);
281 zassert_true((verify_content_amount(&test_list, 1)),
282 "test_list has wrong content");
283
284 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
285 &test_node_2.node, true)),
286 "test_list head/tail are wrong");
287
288 /* Removing node 2 */
289 sys_sflist_remove(&test_list, NULL, &test_node_2.node);
290 zassert_true((verify_emptyness(&test_list)),
291 "test_list should be empty");
292
293 /* test iterator from a node */
294 struct data_node {
295 sys_sfnode_t node;
296 int data;
297 } data_node[6] = {
298 { .data = 0 },
299 { .data = 1 },
300 { .data = 2 },
301 { .data = 3 },
302 { .data = 4 },
303 { .data = 5 },
304 };
305 sys_sfnode_t *node = NULL;
306 int ii;
307
308 sys_sflist_init(&test_list);
309
310 for (ii = 0; ii < 6; ii++) {
311 sys_sflist_append(&test_list, &data_node[ii].node);
312 }
313
314 ii = 0;
315 SYS_SFLIST_ITERATE_FROM_NODE(&test_list, node) {
316 ii++;
317 if (((struct data_node *)node)->data == 2) {
318 break;
319 }
320 }
321 zassert_equal(ii, 3, "");
322
323 ii = 0;
324 SYS_SFLIST_ITERATE_FROM_NODE(&test_list, node) {
325 ii++;
326 if (((struct data_node *)node)->data == 3) {
327 break;
328 }
329 }
330 zassert_equal(ii, 1, "");
331
332 ii = 0;
333 SYS_SFLIST_ITERATE_FROM_NODE(&test_list, node) {
334 ii++;
335 }
336 zassert_equal(ii, 2, "");
337
338 /* test sys_sflist_get_not_empty() and sys_sflist_get() APIs */
339 for (ii = 0; ii < 6; ii++) {
340 node = sys_sflist_get_not_empty(&test_list);
341 zassert_equal(((struct data_node *)node)->data, ii, "");
342 }
343 for (ii = 0; ii < 6; ii++) {
344 /* regenerate test_list since we just emptied it */
345 sys_sflist_append(&test_list, &data_node[ii].node);
346 }
347 for (ii = 0; ii < 6; ii++) {
348 node = sys_sflist_get(&test_list);
349 zassert_equal(((struct data_node *)node)->data, ii, "");
350 }
351 node = sys_sflist_get(&test_list);
352 zassert_equal(node, NULL, "");
353
354 /* test sys_sflist_append_list() */
355 sys_sflist_init(&append_list);
356 struct data_node data_node_append[6] = {
357 { .data = 6 },
358 { .data = 7 },
359 { .data = 8 },
360 { .data = 9 },
361 { .data = 10 },
362 { .data = 11 },
363 };
364 for (ii = 0; ii < 6; ii++) {
365 /* regenerate test_list, which we just emptied */
366 sys_sflist_append(&test_list, &data_node[ii].node);
367 /* Build append_list so that the node pointers are correct */
368 sys_sflist_append(&append_list, &data_node_append[ii].node);
369 }
370 sys_sflist_append_list(&test_list, &data_node_append[0].node,
371 &data_node_append[5].node);
372 for (ii = 0; ii < 12; ii++) {
373 node = sys_sflist_get(&test_list);
374 zassert_equal(((struct data_node *)node)->data, ii,
375 "expected %d got %d", ii,
376 ((struct data_node *)node)->data);
377 }
378
379 /* test sys_sflist_merge_sflist */
380 sys_sflist_init(&test_list);
381 sys_sflist_init(&append_list);
382 for (ii = 0; ii < 6; ii++) {
383 /* regenerate both lists */
384 sys_sflist_append(&test_list, &data_node[ii].node);
385 sys_sflist_append(&append_list, &data_node_append[ii].node);
386 }
387 sys_sflist_merge_sflist(&test_list, &append_list);
388 for (ii = 0; ii < 12; ii++) {
389 node = sys_sflist_get(&test_list);
390 zassert_equal(((struct data_node *)node)->data, ii,
391 "expected %d got %d", ii,
392 ((struct data_node *)node)->data);
393 }
394 zassert_true(sys_sflist_is_empty(&append_list),
395 "merged list is not empty");
396
397 /* tests for sys_sfnode_flags_get(), sys_sfnode_flags_set()
398 * sys_sfnode_init()
399 */
400 sys_sflist_init(&test_list);
401 /* Only iterating 0..3 due to limited range of flag values */
402 for (ii = 0; ii < 4; ii++) {
403 sys_sfnode_init(&data_node[ii].node, ii);
404 sys_sflist_append(&test_list, &data_node[ii].node);
405 }
406 for (ii = 0; ii < 4; ii++) {
407 node = sys_sflist_get(&test_list);
408 zassert_equal(sys_sfnode_flags_get(node), ii,
409 "wrong flags value");
410 /* Place the nodes back on the list with the flags set
411 * in reverse order for the next test
412 */
413 sys_sfnode_flags_set(node, 3 - ii);
414 sys_sflist_append(&test_list, node);
415 }
416 for (ii = 3; ii >= 0; ii--) {
417 node = sys_sflist_get(&test_list);
418 zassert_equal(sys_sfnode_flags_get(node), ii,
419 "wrong flags value");
420 }
421 }
422
423 /**
424 * @}
425 */
426
