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 = clib_llist_elt (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
99 clib_llist_get (pelts, e);
101 he = clib_llist_elt (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);
110 clib_llist_put (pelts, 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++)
123 clib_llist_get (pelts, e);
125 he = clib_llist_elt (pelts, head);
126 clib_llist_add (pelts, ll_test, e, he);
129 he = clib_llist_elt (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);
135 clib_llist_foreach (pelts, ll_test, he, e, ({
137 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
141 LLIST_TEST (i == -1, "head insertion works i = %d", i);
144 * Remove elements from head
147 e = clib_llist_next (pelts, ll_test, he);
150 next = clib_llist_next (pelts, ll_test, e);
151 clib_llist_remove (pelts, ll_test, e);
152 clib_llist_put (pelts, e);
157 he = clib_llist_elt (pelts, head);
158 list_test_is_sane (pelts, ll_test, he);
159 LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he),
160 "list should be empty");
161 LLIST_TEST (clib_llist_elts (pelts) == 1, "pool should have only 1 element");
164 * Add tail elements to ll_test2 and test
166 head2 = clib_llist_make_head (pelts, ll_test2);
167 for (i = 0; i < 100; i++)
169 clib_llist_get (pelts, e);
171 he2 = clib_llist_elt (pelts, head2);
172 clib_llist_add_tail (pelts, ll_test2, e, he2);
175 he2 = clib_llist_elt (pelts, head2);
176 list_test_is_sane (pelts, ll_test2, he2);
177 LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2),
178 "list should not be empty");
181 clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({
183 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
186 LLIST_TEST (i == -1, "tail insertion works");
189 * Remove in from ll_test2 and add to ll_test
192 he = clib_llist_elt (pelts, head);
193 e = clib_llist_next (pelts, ll_test2, he2);
196 next = clib_llist_next (pelts, ll_test2, e);
199 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
201 clib_llist_remove (pelts, ll_test2, e);
202 clib_llist_add_tail (pelts, ll_test, e, he);
207 he = clib_llist_elt (pelts, head);
208 he2 = clib_llist_elt (pelts, head2);
209 list_test_is_sane (pelts, ll_test, he);
210 LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
211 "shoud not be empty");
212 LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty");
216 clib_llist_foreach (pelts, ll_test, he, e, ({
218 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
222 LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i);
225 * Delete and insert at random position
227 e = clib_llist_elt (pelts, head);
228 for (i = 0; i < 10; i++)
229 e = clib_llist_next (pelts, ll_test, e);
231 next = clib_llist_next (pelts, ll_test, e);
232 nnext = clib_llist_next (pelts, ll_test, next);
234 LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data);
235 LLIST_TEST (next->data == 10, "data should be 10");
236 LLIST_TEST (nnext->data == 11, "data should be 11");
238 clib_llist_remove (pelts, ll_test, next);
239 clib_llist_put (pelts, next);
240 memset (next, 0xfc, sizeof (*next));
242 next = clib_llist_next (pelts, ll_test, e);
243 LLIST_TEST (next->data == 11, "data should be 11");
244 LLIST_TEST (next == nnext, "should be nnext");
246 clib_llist_get (pelts, next);
248 clib_llist_insert (pelts, ll_test, next, e);
250 next = clib_llist_next (pelts, ll_test, e);
251 LLIST_TEST (next->data == 10, "new next data should be 10");
252 next = clib_llist_next (pelts, ll_test, next);
253 LLIST_TEST (nnext == next, "next should be linked to old nnext");
255 he = clib_llist_elt (pelts, head);
256 list_test_is_sane (pelts, ll_test, he);
259 * Make a new list that uses ll_test anchor
262 head3 = clib_llist_make_head (pelts, ll_test);
263 for (i = 0; i < 10; i++)
265 clib_llist_get (pelts, e);
267 he3 = clib_llist_elt (pelts, head3);
268 clib_llist_add (pelts, ll_test, e, he3);
271 he = clib_llist_elt (pelts, head);
272 he3 = clib_llist_elt (pelts, head3);
273 list_test_is_sane (pelts, ll_test, he3);
274 e = clib_llist_prev (pelts, ll_test, he);
278 * Splice third list into the tail of the first
280 clib_llist_splice (pelts, ll_test, e, he3);
282 list_test_is_sane (pelts, ll_test, he);
283 LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty");
285 e = clib_llist_prev (pelts, ll_test, he);
286 LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u",
288 for (i = 0; i < 10; i++)
290 if (e->data != 300 + i)
291 LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
292 e = clib_llist_prev (pelts, ll_test, e);
295 LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u",
301 clib_llist_free (pelts);
305 static clib_error_t *
306 llist_test (vlib_main_t * vm,
307 unformat_input_t * input, vlib_cli_command_t * cmd_arg)
311 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
313 if (unformat (input, "basic"))
315 res = llist_test_basic (vm, input);
317 else if (unformat (input, "all"))
319 if ((res = llist_test_basic (vm, input)))
328 return clib_error_return (0, "llist unit test failed");
332 VLIB_CLI_COMMAND (llist_test_command, static) =
334 .path = "test llist",
335 .short_help = "internal llist unit tests",
336 .function = llist_test,
340 * fd.io coding-style-patch-verification: ON
343 * eval: (c-set-style "gnu")