2 * Copyright (c) 2019 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
15 #include <vppinfra/llist.h>
16 #include <vlib/vlib.h>
18 #define LLIST_TEST_I(_cond, _comment, _args...) \
20 int _evald = (_cond); \
22 fformat(stderr, "FAIL:%d: " _comment "\n", \
25 fformat(stderr, "PASS:%d: " _comment "\n", \
31 #define LLIST_TEST(_cond, _comment, _args...) \
33 if (!LLIST_TEST_I(_cond, _comment, ##_args)) { \
38 typedef struct list_elt
40 clib_llist_anchor_t ll_test;
41 clib_llist_anchor_t ll_test2;
45 #define list_elt_is_sane(pl,name,E,P,N) \
46 (E->name.next == (N) - pl \
47 && E->name.prev == (P) - pl \
48 && P->name.next == (E) - pl \
49 && N->name.prev == (E) - pl)
51 #define list_test_is_sane(pl,name,h) \
55 clib_llist_foreach (pl, name, h, e, ({ \
56 rv = list_elt_is_sane ((pl), name, (e), \
57 clib_llist_prev (pl,name,e), \
58 clib_llist_next (pl,name,e)); \
60 LLIST_TEST (0, "invalid elt %u prev %u/%u next %u/%u", e - pl, \
61 e->name.prev, clib_llist_prev (pl,name,e) - pl, \
62 e->name.next, clib_llist_next (pl,name,e) - pl); \
67 llist_test_basic (vlib_main_t * vm, unformat_input_t * input)
69 list_elt_t *pelts = 0, *he, *he2, *he3, *e, *next, *nnext;
70 int __clib_unused verbose, i, rv;
71 clib_llist_index_t head, head2, head3;
74 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
76 if (unformat (input, "verbose"))
80 vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
86 head = clib_llist_make_head (pelts, ll_test);
87 he = pool_elt_at_index (pelts, head);
89 LLIST_TEST (he->ll_test.next == head, "head next points to itself");
90 LLIST_TEST (he->ll_test.prev == head, "head prev points to itself");
91 LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
92 "should be the same");
93 LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
94 "should be the same");
97 * Add and remove one element
101 he = pool_elt_at_index (pelts, head);
102 clib_llist_add (pelts, ll_test, e, he);
104 LLIST_TEST (e->ll_test.next == head, "next should be head");
105 LLIST_TEST (e->ll_test.prev == head, "prev should be head");
106 LLIST_TEST (he->ll_test.prev == e - pelts, "prev should be new");
107 LLIST_TEST (he->ll_test.next == e - pelts, "prev should be new");
109 clib_llist_remove (pelts, ll_test, e);
111 LLIST_TEST (he->ll_test.prev == head, "prev should be head");
112 LLIST_TEST (he->ll_test.prev == head, "next should be head");
113 LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
114 "should be the same");
115 LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
116 "should be the same");
119 * Add multiple head elements and test insertion
121 for (i = 0; i < 100; i++)
125 he = pool_elt_at_index (pelts, head);
126 clib_llist_add (pelts, ll_test, e, he);
129 he = pool_elt_at_index (pelts, head);
130 LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
131 "shoud not be empty");
132 list_test_is_sane (pelts, ll_test, he);
136 clib_llist_foreach (pelts, ll_test, he, e, ({
138 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
143 LLIST_TEST (i == -1, "head insertion works i = %d", i);
146 * Remove elements from head
149 e = clib_llist_next (pelts, ll_test, he);
152 next = clib_llist_next (pelts, ll_test, e);
153 clib_llist_remove (pelts, ll_test, e);
159 he = pool_elt_at_index (pelts, head);
160 list_test_is_sane (pelts, ll_test, he);
161 LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he),
162 "list should be empty");
163 LLIST_TEST (pool_elts (pelts) == 1, "pool should have only 1 element");
166 * Add tail elements to ll_test2 and test
168 head2 = clib_llist_make_head (pelts, ll_test2);
169 for (i = 0; i < 100; i++)
173 he2 = pool_elt_at_index (pelts, head2);
174 clib_llist_add_tail (pelts, ll_test2, e, he2);
177 he2 = pool_elt_at_index (pelts, head2);
178 list_test_is_sane (pelts, ll_test2, he2);
179 LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2),
180 "list should not be empty");
184 clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({
186 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
190 LLIST_TEST (i == -1, "tail insertion works");
193 * Remove in from ll_test2 and add to ll_test
196 he = pool_elt_at_index (pelts, head);
197 e = clib_llist_next (pelts, ll_test2, he2);
200 next = clib_llist_next (pelts, ll_test2, e);
203 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
205 clib_llist_remove (pelts, ll_test2, e);
206 clib_llist_add_tail (pelts, ll_test, e, he);
211 he = pool_elt_at_index (pelts, head);
212 he2 = pool_elt_at_index (pelts, head2);
213 list_test_is_sane (pelts, ll_test, he);
214 LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
215 "shoud not be empty");
216 LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty");
221 clib_llist_foreach (pelts, ll_test, he, e, ({
223 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
228 LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i);
231 * Delete and insert at random position
233 e = pool_elt_at_index (pelts, head);
234 for (i = 0; i < 10; i++)
235 e = clib_llist_next (pelts, ll_test, e);
237 next = clib_llist_next (pelts, ll_test, e);
238 nnext = clib_llist_next (pelts, ll_test, next);
240 LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data);
241 LLIST_TEST (next->data == 10, "data should be 10");
242 LLIST_TEST (nnext->data == 11, "data should be 11");
244 clib_llist_remove (pelts, ll_test, next);
245 pool_put (pelts, next);
246 memset (next, 0xfc, sizeof (*next));
248 next = clib_llist_next (pelts, ll_test, e);
249 LLIST_TEST (next->data == 11, "data should be 11");
250 LLIST_TEST (next == nnext, "should be nnext");
252 pool_get (pelts, next);
254 clib_llist_insert (pelts, ll_test, next, e);
256 next = clib_llist_next (pelts, ll_test, e);
257 LLIST_TEST (next->data == 10, "new next data should be 10");
258 next = clib_llist_next (pelts, ll_test, next);
259 LLIST_TEST (nnext == next, "next should be linked to old nnext");
261 he = pool_elt_at_index (pelts, head);
262 list_test_is_sane (pelts, ll_test, he);
265 * Make a new list that uses ll_test anchor
268 head3 = clib_llist_make_head (pelts, ll_test);
269 for (i = 0; i < 10; i++)
273 he3 = pool_elt_at_index (pelts, head3);
274 clib_llist_add (pelts, ll_test, e, he3);
277 he = pool_elt_at_index (pelts, head);
278 he3 = pool_elt_at_index (pelts, head3);
279 list_test_is_sane (pelts, ll_test, he3);
280 e = clib_llist_prev (pelts, ll_test, he);
284 * Splice third list into the tail of the first
286 clib_llist_splice (pelts, ll_test, e, he3);
288 list_test_is_sane (pelts, ll_test, he);
289 LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty");
291 e = clib_llist_prev (pelts, ll_test, he);
292 LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u",
294 for (i = 0; i < 10; i++)
296 if (e->data != 300 + i)
297 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
298 e = clib_llist_prev (pelts, ll_test, e);
301 LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u",
311 static clib_error_t *
312 llist_test (vlib_main_t * vm,
313 unformat_input_t * input, vlib_cli_command_t * cmd_arg)
317 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
319 if (unformat (input, "basic"))
321 res = llist_test_basic (vm, input);
323 else if (unformat (input, "all"))
325 if ((res = llist_test_basic (vm, input)))
334 return clib_error_return (0, "llist unit test failed");
339 VLIB_CLI_COMMAND (llist_test_command, static) =
341 .path = "test llist",
342 .short_help = "internal llist unit tests",
343 .function = llist_test,
348 * fd.io coding-style-patch-verification: ON
351 * eval: (c-set-style "gnu")