1 /*
2 * Copyright (c) 2016 Intel Corporation
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 #include <zephyr/ztest.h>
8 #include <zephyr/sys/slist.h>
9
10 static sys_slist_t test_list;
11 static sys_slist_t append_list;
12
13 struct container_node {
14 sys_snode_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_slist_t * list)23 static inline bool verify_emptyness(sys_slist_t *list)
24 {
25 sys_snode_t *node;
26 sys_snode_t *s_node;
27 struct container_node *cnode;
28 struct container_node *s_cnode;
29 int count;
30
31 if (!sys_slist_is_empty(list)) {
32 return false;
33 }
34
35 if (sys_slist_peek_head(list)) {
36 return false;
37 }
38
39 if (sys_slist_peek_tail(list)) {
40 return false;
41 }
42
43 if (sys_slist_len(list) != 0) {
44 return false;
45 }
46
47 count = 0;
48 SYS_SLIST_FOR_EACH_NODE(list, node) {
49 count++;
50 }
51
52 if (count) {
53 return false;
54 }
55
56 SYS_SLIST_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_SLIST_FOR_EACH_CONTAINER(list, cnode, node) {
66 count++;
67 }
68
69 if (count) {
70 return false;
71 }
72
73 count = 0;
74 SYS_SLIST_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_slist_t * list,int amount)85 static inline bool verify_content_amount(sys_slist_t *list, int amount)
86 {
87 sys_snode_t *node;
88 sys_snode_t *s_node;
89 struct container_node *cnode;
90 struct container_node *s_cnode;
91 int count;
92
93 if (sys_slist_is_empty(list)) {
94 return false;
95 }
96
97 if (!sys_slist_peek_head(list)) {
98 return false;
99 }
100
101 if (!sys_slist_peek_tail(list)) {
102 return false;
103 }
104
105 if (sys_slist_len(list) != amount) {
106 return false;
107 }
108
109 count = 0;
110 SYS_SLIST_FOR_EACH_NODE(list, node) {
111 count++;
112 }
113
114 if (count != amount) {
115 return false;
116 }
117
118 count = 0;
119 SYS_SLIST_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_SLIST_FOR_EACH_CONTAINER(list, cnode, node) {
129 count++;
130 }
131
132 if (count != amount) {
133 return false;
134 }
135
136 count = 0;
137 SYS_SLIST_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_slist_t * list,sys_snode_t * head,sys_snode_t * tail,bool same)148 static inline bool verify_tail_head(sys_slist_t *list,
149 sys_snode_t *head,
150 sys_snode_t *tail,
151 bool same)
152 {
153 if (sys_slist_peek_head(list) != head) {
154 return false;
155 }
156
157 if (sys_slist_peek_tail(list) != tail) {
158 return false;
159 }
160
161 if (same) {
162 if (sys_slist_peek_head(list) != sys_slist_peek_tail(list)) {
163 return false;
164 }
165 } else {
166 if (sys_slist_peek_head(list) == sys_slist_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_slist_init(), sys_slist_append(),
185 * sys_slist_find_and_remove(), sys_slist_prepend(),
186 * sys_slist_remove(), sys_slist_get(), sys_slist_get_not_empty(),
187 * sys_slist_append_list(), sys_slist_merge_list(), sys_slist_find()
188 */
ZTEST(dlist_api,test_slist)189 ZTEST(dlist_api, test_slist)
190 {
191 sys_slist_init(&test_list);
192
193 zassert_true((verify_emptyness(&test_list)),
194 "test_list should be empty");
195
196 /* Appending node 1 */
197 sys_slist_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 /* Find the node 1, previous node should be null */
206 sys_snode_t *test_node_1_prev = &test_node_1.node;
207
208 zassert_true(sys_slist_find(&test_list, &test_node_1.node, &test_node_1_prev),
209 "test_list did not find node ");
210 zassert_is_null(test_node_1_prev, "test_list previous node not null ");
211
212 /* Finding and removing node 1 */
213 sys_slist_find_and_remove(&test_list, &test_node_1.node);
214 zassert_true((verify_emptyness(&test_list)),
215 "test_list should be empty");
216
217 /* Prepending node 1 */
218 sys_slist_prepend(&test_list, &test_node_1.node);
219 zassert_true((verify_content_amount(&test_list, 1)),
220 "test_list has wrong content");
221
222 zassert_true((verify_tail_head(&test_list, &test_node_1.node,
223 &test_node_1.node, true)),
224 "test_list head/tail are wrong");
225
226 /* Removing node 1 */
227 sys_slist_remove(&test_list, NULL, &test_node_1.node);
228 zassert_true((verify_emptyness(&test_list)),
229 "test_list should be empty");
230
231 /* Appending node 1 */
232 sys_slist_append(&test_list, &test_node_1.node);
233 /* Prepending node 2 */
234 sys_slist_prepend(&test_list, &test_node_2.node);
235
236 zassert_true((verify_content_amount(&test_list, 2)),
237 "test_list has wrong content");
238
239 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
240 &test_node_1.node, false)),
241 "test_list head/tail are wrong");
242
243 /* Appending node 3 */
244 sys_slist_append(&test_list, &test_node_3.node);
245
246 zassert_true((verify_content_amount(&test_list, 3)),
247 "test_list has wrong content");
248
249 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
250 &test_node_3.node, false)),
251 "test_list head/tail are wrong");
252
253 zassert_true((sys_slist_peek_next(&test_node_2.node) ==
254 &test_node_1.node),
255 "test_list node links are wrong");
256
257 /* Inserting node 4 after node 2, peek with nocheck variant */
258 sys_slist_insert(&test_list, &test_node_2.node, &test_node_4.node);
259
260 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
261 &test_node_3.node, false)),
262 "test_list head/tail are wrong");
263
264 zassert_true((sys_slist_peek_next_no_check(&test_node_2.node) ==
265 &test_node_4.node),
266 "test_list node links are wrong");
267
268 /* Find the node 4 and get the previous node*/
269 sys_snode_t *test_node_4_prev = NULL;
270
271 zassert_true(sys_slist_find(&test_list, &test_node_4.node, &test_node_4_prev),
272 "test_list did not find node");
273 zassert_equal(&test_node_2.node, test_node_4_prev,
274 "test_list previous node wrong ");
275
276 /* Finding and removing node 1 */
277 sys_slist_find_and_remove(&test_list, &test_node_1.node);
278 zassert_true((verify_content_amount(&test_list, 3)),
279 "test_list has wrong content");
280
281 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
282 &test_node_3.node, false)),
283 "test_list head/tail are wrong");
284
285 /* Removing node 3 */
286 sys_slist_remove(&test_list, &test_node_4.node, &test_node_3.node);
287 zassert_true((verify_content_amount(&test_list, 2)),
288 "test_list has wrong content");
289
290 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
291 &test_node_4.node, false)),
292 "test_list head/tail are wrong");
293
294 /* Removing node 4 */
295 sys_slist_remove(&test_list, &test_node_2.node, &test_node_4.node);
296 zassert_true((verify_content_amount(&test_list, 1)),
297 "test_list has wrong content");
298
299 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
300 &test_node_2.node, true)),
301 "test_list head/tail are wrong");
302
303 /* Removing node 2 */
304 sys_slist_remove(&test_list, NULL, &test_node_2.node);
305 zassert_true((verify_emptyness(&test_list)),
306 "test_list should be empty");
307
308 /* test iterator from a node */
309 struct data_node {
310 sys_snode_t node;
311 int data;
312 } data_node[6] = {
313 { .data = 0 },
314 { .data = 1 },
315 { .data = 2 },
316 { .data = 3 },
317 { .data = 4 },
318 { .data = 5 },
319 };
320 sys_snode_t *node = NULL;
321 int ii;
322
323 sys_slist_init(&test_list);
324
325 for (ii = 0; ii < 6; ii++) {
326 sys_slist_append(&test_list, &data_node[ii].node);
327 }
328
329 ii = 0;
330 SYS_SLIST_ITERATE_FROM_NODE(&test_list, node) {
331 ii++;
332 if (((struct data_node *)node)->data == 2) {
333 break;
334 }
335 }
336 zassert_equal(ii, 3, "");
337
338 ii = 0;
339 SYS_SLIST_ITERATE_FROM_NODE(&test_list, node) {
340 ii++;
341 if (((struct data_node *)node)->data == 3) {
342 break;
343 }
344 }
345 zassert_equal(ii, 1, "");
346
347 ii = 0;
348 SYS_SLIST_ITERATE_FROM_NODE(&test_list, node) {
349 ii++;
350 }
351 zassert_equal(ii, 2, "");
352
353 /* test sys_slist_remove and sys_slist_append inside safe node iteration */
354 sys_snode_t *s_node, *prev, *removed;
355 sys_snode_t append;
356
357 removed = NULL;
358 SYS_SLIST_FOR_EACH_NODE_SAFE(&test_list, node, s_node) {
359 /* Remove first node under iteration */
360 if (removed == NULL) {
361 sys_slist_remove(&test_list, NULL, node);
362 removed = node;
363 }
364 }
365 zassert_not_null(removed);
366 zassert_true((verify_content_amount(&test_list, 5)), "test_list has wrong content");
367 sys_slist_prepend(&test_list, removed);
368
369 removed = NULL;
370 SYS_SLIST_FOR_EACH_NODE_SAFE(&test_list, node, s_node) {
371 /* Remove last node under iteration */
372 if (node->next == NULL) {
373 sys_slist_remove(&test_list, prev, node);
374 removed = node;
375 }
376 prev = node;
377 }
378 zassert_not_null(removed);
379 zassert_true((verify_content_amount(&test_list, 5)), "test_list has wrong content");
380 sys_slist_append(&test_list, removed);
381
382 SYS_SLIST_FOR_EACH_NODE_SAFE(&test_list, node, s_node) {
383 /* Append on first iteration */
384 if (test_list.head == node) {
385 sys_slist_append(&test_list, &append);
386 }
387 }
388 zassert_true((verify_content_amount(&test_list, 7)), "test_list has wrong content");
389 sys_slist_find_and_remove(&test_list, &append);
390
391 SYS_SLIST_FOR_EACH_NODE_SAFE(&test_list, node, s_node) {
392 /* Append on last iteration */
393 if (node->next == NULL) {
394 sys_slist_append(&test_list, &append);
395 }
396 }
397 zassert_true((verify_content_amount(&test_list, 7)), "test_list has wrong content");
398 sys_slist_find_and_remove(&test_list, &append);
399
400 /* test sys_slist_remove and sys_slist_append inside safe container iteration */
401 struct container_node *cnode, *s_cnode, *cprev, *cremoved;
402 struct container_node cappend;
403
404 cremoved = NULL;
405 SYS_SLIST_FOR_EACH_CONTAINER_SAFE(&test_list, cnode, s_cnode, node) {
406 /* Remove on first iteration */
407 if (cremoved == NULL) {
408 sys_slist_remove(&test_list, NULL, &cnode->node);
409 cremoved = cnode;
410 }
411 }
412 zassert_not_null(cremoved);
413 zassert_true((verify_content_amount(&test_list, 5)), "test_list has wrong content");
414 sys_slist_prepend(&test_list, &cremoved->node);
415
416 cremoved = NULL;
417 SYS_SLIST_FOR_EACH_CONTAINER_SAFE(&test_list, cnode, s_cnode, node) {
418 /* Remove on last iteration */
419 if (cnode->node.next == NULL) {
420 sys_slist_remove(&test_list, &cprev->node, &cnode->node);
421 cremoved = cnode;
422 }
423 cprev = cnode;
424 }
425 zassert_not_null(cremoved);
426 zassert_true((verify_content_amount(&test_list, 5)), "test_list has wrong content");
427 sys_slist_append(&test_list, &cremoved->node);
428
429 SYS_SLIST_FOR_EACH_CONTAINER_SAFE(&test_list, cnode, s_cnode, node) {
430 /* Append on first iteration */
431 if (test_list.head == &cnode->node) {
432 sys_slist_append(&test_list, &cappend.node);
433 }
434 }
435 zassert_true((verify_content_amount(&test_list, 7)), "test_list has wrong content");
436 sys_slist_find_and_remove(&test_list, &cappend.node);
437
438 SYS_SLIST_FOR_EACH_CONTAINER_SAFE(&test_list, cnode, s_cnode, node) {
439 /* Append on last iteration */
440 if (cnode->node.next == NULL) {
441 sys_slist_append(&test_list, &cappend.node);
442 }
443 }
444 zassert_true((verify_content_amount(&test_list, 7)), "test_list has wrong content");
445 sys_slist_find_and_remove(&test_list, &cappend.node);
446
447 /* test sys_slist_get_not_empty() and sys_slist_get() APIs */
448 for (ii = 0; ii < 6; ii++) {
449 node = sys_slist_get_not_empty(&test_list);
450 zassert_equal(((struct data_node *)node)->data, ii, "");
451 }
452 for (ii = 0; ii < 6; ii++) {
453 /* regenerate test_list since we just emptied it */
454 sys_slist_append(&test_list, &data_node[ii].node);
455 }
456 for (ii = 0; ii < 6; ii++) {
457 node = sys_slist_get(&test_list);
458 zassert_equal(((struct data_node *)node)->data, ii, "");
459 }
460 node = sys_slist_get(&test_list);
461 zassert_equal(node, NULL, "");
462
463 /* test sys_slist_append_list() */
464 sys_slist_init(&append_list);
465 struct data_node data_node_append[6] = {
466 { .data = 6 },
467 { .data = 7 },
468 { .data = 8 },
469 { .data = 9 },
470 { .data = 10 },
471 { .data = 11 },
472 };
473 for (ii = 0; ii < 6; ii++) {
474 /* regenerate test_list, which we just emptied */
475 sys_slist_append(&test_list, &data_node[ii].node);
476 /* Build append_list so that the node pointers are correct */
477 sys_slist_append(&append_list, &data_node_append[ii].node);
478 }
479 sys_slist_append_list(&test_list, &data_node_append[0].node,
480 &data_node_append[5].node);
481 for (ii = 0; ii < 12; ii++) {
482 node = sys_slist_get(&test_list);
483 zassert_equal(((struct data_node *)node)->data, ii,
484 "expected %d got %d", ii,
485 ((struct data_node *)node)->data);
486 }
487
488 /* test sys_slist_append_list with empty list */
489 sys_slist_init(&test_list);
490 sys_slist_init(&append_list);
491 for (ii = 0; ii < 6; ii++) {
492 /* regenerate test_list only */
493 sys_slist_append(&test_list, &data_node[ii].node);
494 }
495 sys_slist_append_list(&test_list, append_list.head, append_list.tail);
496 node = sys_slist_peek_tail(&test_list);
497 zassert_equal(((struct data_node *)node)->data, data_node[5].data, "expected %d got %d",
498 data_node[5].data, ((struct data_node *)node)->data);
499
500 /* test sys_slist_merge_slist */
501 sys_slist_init(&test_list);
502 sys_slist_init(&append_list);
503 for (ii = 0; ii < 6; ii++) {
504 /* regenerate both lists */
505 sys_slist_append(&test_list, &data_node[ii].node);
506 sys_slist_append(&append_list, &data_node_append[ii].node);
507 }
508 sys_slist_merge_slist(&test_list, &append_list);
509 for (ii = 0; ii < 12; ii++) {
510 node = sys_slist_get(&test_list);
511 zassert_equal(((struct data_node *)node)->data, ii,
512 "expected %d got %d", ii,
513 ((struct data_node *)node)->data);
514 }
515 zassert_true(sys_slist_is_empty(&append_list),
516 "merged list is not empty");
517
518 /* test sys_slist_merge_slist with empty list */
519 sys_slist_init(&test_list);
520 sys_slist_init(&append_list);
521 for (ii = 0; ii < 6; ii++) {
522 /* regenerate test_list only */
523 sys_slist_append(&test_list, &data_node[ii].node);
524 }
525
526 sys_slist_merge_slist(&test_list, &append_list);
527 node = sys_slist_peek_tail(&test_list);
528 zassert_equal(((struct data_node *)node)->data, data_node[5].data, "expected %d got %d",
529 data_node[5].data, ((struct data_node *)node)->data);
530 }
531
532 /**
533 * @}
534 */
535
