1 /*
2 * Copyright (c) 2017 Intel Corporation
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 #include <zephyr/ztest.h>
8 #include <zephyr/sys/dlist.h>
9
10 static sys_dlist_t test_list;
11
12 struct container_node {
13 sys_dnode_t node;
14 int unused;
15 };
16
17 static struct container_node test_node_1;
18 static struct container_node test_node_2;
19 static struct container_node test_node_3;
20 static struct container_node test_node_4;
21
verify_emptyness(sys_dlist_t * list)22 static inline bool verify_emptyness(sys_dlist_t *list)
23 {
24 sys_dnode_t *node;
25 sys_dnode_t *s_node;
26 struct container_node *cnode;
27 struct container_node *s_cnode;
28 int count;
29
30 if (!sys_dlist_is_empty(list)) {
31 return false;
32 }
33
34 if (sys_dlist_peek_head(list)) {
35 return false;
36 }
37
38 if (sys_dlist_peek_tail(list)) {
39 return false;
40 }
41
42 if (sys_dlist_len(list) != 0) {
43 return false;
44 }
45
46 count = 0;
47 SYS_DLIST_FOR_EACH_NODE(list, node) {
48 count++;
49 }
50
51 if (count) {
52 return false;
53 }
54
55 SYS_DLIST_FOR_EACH_NODE_SAFE(list, node, s_node) {
56 count++;
57 }
58
59 if (count) {
60 return false;
61 }
62
63 count = 0;
64 SYS_DLIST_FOR_EACH_CONTAINER(list, cnode, node) {
65 count++;
66 }
67
68 if (count) {
69 return false;
70 }
71
72 count = 0;
73 SYS_DLIST_FOR_EACH_CONTAINER_SAFE(list, cnode, s_cnode, node) {
74 count++;
75 }
76
77 if (count) {
78 return false;
79 }
80
81 return true;
82 }
83
verify_content_amount(sys_dlist_t * list,int amount)84 static inline bool verify_content_amount(sys_dlist_t *list, int amount)
85 {
86 sys_dnode_t *node;
87 sys_dnode_t *s_node;
88 struct container_node *cnode;
89 struct container_node *s_cnode;
90 int count;
91
92 if (sys_dlist_is_empty(list)) {
93 return false;
94 }
95
96 if (!sys_dlist_peek_head(list)) {
97 return false;
98 }
99
100 if (!sys_dlist_peek_tail(list)) {
101 return false;
102 }
103
104 if (sys_dlist_len(list) != amount) {
105 return false;
106 }
107
108 count = 0;
109 SYS_DLIST_FOR_EACH_NODE(list, node) {
110 count++;
111 }
112
113 if (count != amount) {
114 return false;
115 }
116
117 count = 0;
118 SYS_DLIST_FOR_EACH_NODE_SAFE(list, node, s_node) {
119 count++;
120 }
121
122 if (count != amount) {
123 return false;
124 }
125
126 count = 0;
127 SYS_DLIST_FOR_EACH_CONTAINER(list, cnode, node) {
128 count++;
129 }
130
131 if (count != amount) {
132 return false;
133 }
134
135 count = 0;
136 SYS_DLIST_FOR_EACH_CONTAINER_SAFE(list, cnode, s_cnode, node) {
137 count++;
138 }
139
140 if (count != amount) {
141 return false;
142 }
143
144 return true;
145 }
146
verify_tail_head(sys_dlist_t * list,sys_dnode_t * head,sys_dnode_t * tail,bool same)147 static inline bool verify_tail_head(sys_dlist_t *list,
148 sys_dnode_t *head,
149 sys_dnode_t *tail,
150 bool same)
151 {
152 if (sys_dlist_peek_head(list) != head) {
153 return false;
154 }
155
156 if (sys_dlist_peek_tail(list) != tail) {
157 return false;
158 }
159
160 if (same) {
161 if (sys_dlist_peek_head(list) != sys_dlist_peek_tail(list)) {
162 return false;
163 }
164 } else {
165 if (sys_dlist_peek_head(list) == sys_dlist_peek_tail(list)) {
166 return false;
167 }
168 }
169
170 return true;
171 }
172 /**
173 * @addtogroup unit_tests
174 * @{
175 */
176
177 /**
178 * @brief Verify doubly linked list functionalities
179 *
180 * @see sys_dlist_append(), sys_dlist_remove(), sys_dlist_prepend(),
181 * sys_dlist_remove(), sys_dlist_insert(), sys_dlist_peek_next()
182 * SYS_DLIST_ITERATE_FROM_NODE()
183 */
ZTEST(dlist_api,test_dlist)184 ZTEST(dlist_api, test_dlist)
185 {
186 sys_dlist_init(&test_list);
187
188 zassert_true((verify_emptyness(&test_list)),
189 "test_list should be empty");
190
191 /* Appending node 1 */
192 sys_dlist_append(&test_list, &test_node_1.node);
193 zassert_true((verify_content_amount(&test_list, 1)),
194 "test_list has wrong content");
195
196 zassert_true((verify_tail_head(&test_list, &test_node_1.node,
197 &test_node_1.node, true)),
198 "test_list head/tail are wrong");
199
200 /* Finding and removing node 1 */
201 zassert_true(sys_dnode_is_linked(&test_node_1.node),
202 "node1 is not linked");
203 sys_dlist_remove(&test_node_1.node);
204 zassert_true((verify_emptyness(&test_list)),
205 "test_list should be empty");
206 zassert_false(sys_dnode_is_linked(&test_node_1.node),
207 "node1 is still linked");
208
209 /* Prepending node 1 */
210 sys_dlist_prepend(&test_list, &test_node_1.node);
211 zassert_true((verify_content_amount(&test_list, 1)),
212 "test_list has wrong content");
213
214 zassert_true((verify_tail_head(&test_list, &test_node_1.node,
215 &test_node_1.node, true)),
216 "test_list head/tail are wrong");
217
218 /* Removing node 1 */
219 sys_dlist_remove(&test_node_1.node);
220 zassert_true((verify_emptyness(&test_list)),
221 "test_list should be empty");
222
223 /* Appending node 1 */
224 sys_dlist_append(&test_list, &test_node_1.node);
225 /* Prepending node 2 */
226 sys_dlist_prepend(&test_list, &test_node_2.node);
227
228 zassert_true((verify_content_amount(&test_list, 2)),
229 "test_list has wrong content");
230
231 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
232 &test_node_1.node, false)),
233 "test_list head/tail are wrong");
234
235 /* Appending node 3 */
236 sys_dlist_append(&test_list, &test_node_3.node);
237
238 zassert_true((verify_content_amount(&test_list, 3)),
239 "test_list has wrong content");
240
241 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
242 &test_node_3.node, false)),
243 "test_list head/tail are wrong");
244
245 zassert_true((sys_dlist_peek_next(&test_list, &test_node_2.node) ==
246 &test_node_1.node),
247 "test_list node links are wrong");
248
249 /* Inserting node 4 after node 2 */
250 sys_dlist_insert(test_node_2.node.next, &test_node_4.node);
251
252 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
253 &test_node_3.node, false)),
254 "test_list head/tail are wrong");
255
256 zassert_true((sys_dlist_peek_next(&test_list, &test_node_2.node) ==
257 &test_node_4.node),
258 "test_list node links are wrong");
259
260 /* Finding and removing node 1 */
261 sys_dlist_remove(&test_node_1.node);
262 zassert_true((verify_content_amount(&test_list, 3)),
263 "test_list has wrong content");
264
265 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
266 &test_node_3.node, false)),
267 "test_list head/tail are wrong");
268
269 /* Removing node 3 */
270 sys_dlist_remove(&test_node_3.node);
271 zassert_true((verify_content_amount(&test_list, 2)),
272 "test_list has wrong content");
273
274 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
275 &test_node_4.node, false)),
276 "test_list head/tail are wrong");
277
278 /* Removing node 4 */
279 sys_dlist_remove(&test_node_4.node);
280 zassert_true((verify_content_amount(&test_list, 1)),
281 "test_list has wrong content");
282
283 zassert_true((verify_tail_head(&test_list, &test_node_2.node,
284 &test_node_2.node, true)),
285 "test_list head/tail are wrong");
286
287 /* Removing node 2 */
288 sys_dlist_remove(&test_node_2.node);
289 zassert_true((verify_emptyness(&test_list)),
290 "test_list should be empty");
291
292 /* test iterator from a node */
293 struct data_node {
294 sys_dnode_t node;
295 int data;
296 } data_node[6] = {
297 { .data = 0 },
298 { .data = 1 },
299 { .data = 2 },
300 { .data = 3 },
301 { .data = 4 },
302 { .data = 5 },
303 };
304 sys_dnode_t *node = NULL;
305 int ii;
306
307 sys_dlist_init(&test_list);
308
309 for (ii = 0; ii < 6; ii++) {
310 sys_dlist_append(&test_list, &data_node[ii].node);
311 }
312
313 ii = 0;
314 SYS_DLIST_ITERATE_FROM_NODE(&test_list, node) {
315 ii++;
316 if (((struct data_node *)node)->data == 2) {
317 break;
318 }
319 }
320 zassert_equal(ii, 3, "");
321
322 ii = 0;
323 SYS_DLIST_ITERATE_FROM_NODE(&test_list, node) {
324 ii++;
325 if (((struct data_node *)node)->data == 3) {
326 break;
327 }
328 }
329 zassert_equal(ii, 1, "");
330
331 ii = 0;
332 SYS_DLIST_ITERATE_FROM_NODE(&test_list, node) {
333 ii++;
334 }
335 zassert_equal(ii, 2, "");
336 }
337
cond(sys_dnode_t * node,void * data)338 int cond(sys_dnode_t *node, void *data)
339 {
340 return (node == data) ? 1 : 0;
341 }
342 /**
343 * @brief Verify doubly linked list functionalities
344 *
345 * @see sys_dlist_is_head(),sys_dlist_is_tail(),
346 * sys_dlist_has_multiple_nodes(),sys_dlist_get()
347 * sys_dlist_peek_head_not_empty(),sys_dlist_insert_at(),
348 * sys_dlist_peek_prev(),
349 */
ZTEST(dlist_api,test_dlist2)350 ZTEST(dlist_api, test_dlist2)
351 {
352 struct container_node test_node[6];
353 struct container_node insert_node;
354 struct container_node insert_node2;
355
356 /* Initialize */
357 memset(test_node, 0, sizeof(test_node));
358 memset(&insert_node, 0, sizeof(insert_node));
359 memset(&insert_node2, 0, sizeof(insert_node2));
360 sys_dlist_init(&test_list);
361
362 /* Check if the dlist is empty */
363 zassert_true(sys_dlist_get(&test_list) == NULL,
364 "Get a empty dilst, NULL will be returned");
365
366 /* Check if a node can append as head if dlist is empty */
367 sys_dlist_insert_at(&test_list, &insert_node.node,
368 cond, &test_node[2].node);
369 zassert_true(test_list.head == &insert_node.node, "");
370 zassert_true(test_list.tail == &insert_node.node, "");
371
372 /* Re-initialize and insert nodes */
373 sys_dlist_init(&test_list);
374
375 for (int i = 0; i < 5; i++) {
376 sys_dlist_append(&test_list, &test_node[i].node);
377 }
378
379 zassert_true(sys_dlist_peek_head_not_empty(&test_list) != NULL,
380 "dlist appended incorrectly");
381
382 zassert_true(sys_dlist_is_head(&test_list,
383 &test_node[0].node),
384 "dlist appended incorrectly");
385
386 zassert_true(sys_dlist_is_tail(&test_list,
387 &test_node[4].node),
388 "dlist appended incorrectly");
389
390 zassert_true(sys_dlist_has_multiple_nodes(&test_list),
391 "dlist appended incorrectly");
392
393 zassert_true(sys_dlist_peek_prev(&test_list,
394 &test_node[2].node) == &test_node[1].node,
395 "dlist appended incorrectly");
396
397 zassert_true(sys_dlist_peek_prev(&test_list,
398 &test_node[0].node) == NULL,
399 "dlist appended incorrectly");
400
401 zassert_true(sys_dlist_peek_prev(&test_list,
402 NULL) == NULL,
403 "dlist appended incorrectly");
404
405 zassert_true(sys_dlist_get(&test_list) ==
406 &test_node[0].node,
407 "Get a dilst, head will be returned");
408
409 /* Check if a node can insert in front of known nodes */
410 sys_dlist_insert_at(&test_list, &insert_node.node,
411 cond, &test_node[2].node);
412 zassert_true(sys_dlist_peek_next(&test_list,
413 &test_node[1].node) == &insert_node.node, " ");
414
415 /* Check if a node can append if the node is unknown */
416 sys_dlist_insert_at(&test_list, &insert_node2.node,
417 cond, &test_node[5].node);
418 zassert_true(sys_dlist_peek_next(&test_list,
419 &test_node[4].node) == &insert_node2.node, " ");
420 }
421
422 /**
423 * @}
424 */
425
