Line data Source code
1 : /*
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:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
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.
14 : */
15 : #include <vppinfra/llist.h>
16 : #include <vlib/vlib.h>
17 :
18 : #define LLIST_TEST_I(_cond, _comment, _args...) \
19 : ({ \
20 : int _evald = (_cond); \
21 : if (!(_evald)) { \
22 : fformat(stderr, "FAIL:%d: " _comment "\n", \
23 : __LINE__, ##_args); \
24 : } else { \
25 : fformat(stderr, "PASS:%d: " _comment "\n", \
26 : __LINE__, ##_args); \
27 : } \
28 : _evald; \
29 : })
30 :
31 : #define LLIST_TEST(_cond, _comment, _args...) \
32 : { \
33 : if (!LLIST_TEST_I(_cond, _comment, ##_args)) { \
34 : return 1; \
35 : } \
36 : }
37 :
38 : typedef struct list_elt
39 : {
40 : clib_llist_anchor_t ll_test;
41 : clib_llist_anchor_t ll_test2;
42 : u32 data;
43 : } list_elt_t;
44 :
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)
50 :
51 : #define list_test_is_sane(pl,name,h) \
52 : do { \
53 : typeof (pl) e; \
54 : int rv; \
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)); \
59 : if (!rv) \
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); \
63 : })); \
64 : } while (0)
65 :
66 : static int
67 0 : llist_test_basic (vlib_main_t * vm, unformat_input_t * input)
68 : {
69 0 : 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;
72 : u32 old_tail;
73 :
74 0 : while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
75 : {
76 0 : if (unformat (input, "verbose"))
77 0 : verbose = 1;
78 : else
79 : {
80 0 : vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
81 : input);
82 0 : return -1;
83 : }
84 : }
85 :
86 0 : head = clib_llist_make_head (pelts, ll_test);
87 0 : he = clib_llist_elt (pelts, head);
88 :
89 0 : LLIST_TEST (he->ll_test.next == head, "head next points to itself");
90 0 : LLIST_TEST (he->ll_test.prev == head, "head prev points to itself");
91 0 : LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
92 : "should be the same");
93 0 : LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
94 : "should be the same");
95 :
96 : /*
97 : * Add and remove one element
98 : */
99 0 : clib_llist_get (pelts, e);
100 0 : e->data = 1;
101 0 : he = clib_llist_elt (pelts, head);
102 0 : clib_llist_add (pelts, ll_test, e, he);
103 :
104 0 : LLIST_TEST (e->ll_test.next == head, "next should be head");
105 0 : LLIST_TEST (e->ll_test.prev == head, "prev should be head");
106 0 : LLIST_TEST (he->ll_test.prev == e - pelts, "prev should be new");
107 0 : LLIST_TEST (he->ll_test.next == e - pelts, "prev should be new");
108 :
109 0 : clib_llist_remove (pelts, ll_test, e);
110 0 : clib_llist_put (pelts, e);
111 0 : LLIST_TEST (he->ll_test.prev == head, "prev should be head");
112 0 : LLIST_TEST (he->ll_test.prev == head, "next should be head");
113 0 : LLIST_TEST (he == clib_llist_next (pelts, ll_test, he),
114 : "should be the same");
115 0 : LLIST_TEST (he == clib_llist_prev (pelts, ll_test, he),
116 : "should be the same");
117 :
118 : /*
119 : * Add multiple head elements and test insertion
120 : */
121 0 : for (i = 0; i < 100; i++)
122 : {
123 0 : clib_llist_get (pelts, e);
124 0 : e->data = i;
125 0 : he = clib_llist_elt (pelts, head);
126 0 : clib_llist_add (pelts, ll_test, e, he);
127 : }
128 :
129 0 : he = clib_llist_elt (pelts, head);
130 0 : LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
131 : "shoud not be empty");
132 0 : list_test_is_sane (pelts, ll_test, he);
133 :
134 0 : i--;
135 : /* *INDENT-OFF* */
136 0 : clib_llist_foreach (pelts, ll_test, he, e, ({
137 : if (i != e->data)
138 : LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
139 : i--;
140 : }));
141 : /* *INDENT-ON* */
142 :
143 0 : LLIST_TEST (i == -1, "head insertion works i = %d", i);
144 :
145 : /*
146 : * Remove elements from head
147 : */
148 0 : i = 99;
149 0 : e = clib_llist_next (pelts, ll_test, he);
150 0 : while (e != he)
151 : {
152 0 : next = clib_llist_next (pelts, ll_test, e);
153 0 : clib_llist_remove (pelts, ll_test, e);
154 0 : clib_llist_put (pelts, e);
155 0 : i--;
156 0 : e = next;
157 : }
158 :
159 0 : he = clib_llist_elt (pelts, head);
160 0 : list_test_is_sane (pelts, ll_test, he);
161 0 : LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he),
162 : "list should be empty");
163 0 : LLIST_TEST (clib_llist_elts (pelts) == 1, "pool should have only 1 element");
164 :
165 : /*
166 : * Add tail elements to ll_test2 and test
167 : */
168 0 : head2 = clib_llist_make_head (pelts, ll_test2);
169 0 : for (i = 0; i < 100; i++)
170 : {
171 0 : clib_llist_get (pelts, e);
172 0 : e->data = i;
173 0 : he2 = clib_llist_elt (pelts, head2);
174 0 : clib_llist_add_tail (pelts, ll_test2, e, he2);
175 : }
176 :
177 0 : he2 = clib_llist_elt (pelts, head2);
178 0 : list_test_is_sane (pelts, ll_test2, he2);
179 0 : LLIST_TEST (!clib_llist_is_empty (pelts, ll_test2, he2),
180 : "list should not be empty");
181 :
182 0 : i--;
183 : /* *INDENT-OFF* */
184 0 : clib_llist_foreach_reverse (pelts, ll_test2, he2, e, ({
185 : if (i != e->data)
186 : LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
187 : i--;
188 : }));
189 : /* *INDENT-ON* */
190 0 : LLIST_TEST (i == -1, "tail insertion works");
191 :
192 : /*
193 : * Remove in from ll_test2 and add to ll_test
194 : */
195 0 : i = 0;
196 0 : he = clib_llist_elt (pelts, head);
197 0 : e = clib_llist_next (pelts, ll_test2, he2);
198 0 : while (e != he2)
199 : {
200 0 : next = clib_llist_next (pelts, ll_test2, e);
201 :
202 0 : if (e->data != i)
203 0 : LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
204 :
205 0 : clib_llist_remove (pelts, ll_test2, e);
206 0 : clib_llist_add_tail (pelts, ll_test, e, he);
207 0 : i++;
208 0 : e = next;
209 : }
210 :
211 0 : he = clib_llist_elt (pelts, head);
212 0 : he2 = clib_llist_elt (pelts, head2);
213 0 : list_test_is_sane (pelts, ll_test, he);
214 0 : LLIST_TEST (!clib_llist_is_empty (pelts, ll_test, he),
215 : "shoud not be empty");
216 0 : LLIST_TEST (clib_llist_is_empty (pelts, ll_test2, he2), "shoud be empty");
217 :
218 0 : i = 0;
219 :
220 : /* *INDENT-OFF* */
221 0 : clib_llist_foreach (pelts, ll_test, he, e, ({
222 : if (i != e->data)
223 : LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
224 : i++;
225 : }));
226 : /* *INDENT-ON* */
227 :
228 0 : LLIST_TEST (i == 100, "move from ll_test2 to ll_test worked i %u", i);
229 :
230 : /*
231 : * Delete and insert at random position
232 : */
233 0 : e = clib_llist_elt (pelts, head);
234 0 : for (i = 0; i < 10; i++)
235 0 : e = clib_llist_next (pelts, ll_test, e);
236 :
237 0 : next = clib_llist_next (pelts, ll_test, e);
238 0 : nnext = clib_llist_next (pelts, ll_test, next);
239 :
240 0 : LLIST_TEST (e->data == 9, "data should be 9 is %u", e->data);
241 0 : LLIST_TEST (next->data == 10, "data should be 10");
242 0 : LLIST_TEST (nnext->data == 11, "data should be 11");
243 :
244 0 : clib_llist_remove (pelts, ll_test, next);
245 0 : clib_llist_put (pelts, next);
246 0 : memset (next, 0xfc, sizeof (*next));
247 :
248 0 : next = clib_llist_next (pelts, ll_test, e);
249 0 : LLIST_TEST (next->data == 11, "data should be 11");
250 0 : LLIST_TEST (next == nnext, "should be nnext");
251 :
252 0 : clib_llist_get (pelts, next);
253 0 : next->data = 10;
254 0 : clib_llist_insert (pelts, ll_test, next, e);
255 :
256 0 : next = clib_llist_next (pelts, ll_test, e);
257 0 : LLIST_TEST (next->data == 10, "new next data should be 10");
258 0 : next = clib_llist_next (pelts, ll_test, next);
259 0 : LLIST_TEST (nnext == next, "next should be linked to old nnext");
260 :
261 0 : he = clib_llist_elt (pelts, head);
262 0 : list_test_is_sane (pelts, ll_test, he);
263 :
264 : /*
265 : * Make a new list that uses ll_test anchor
266 : */
267 :
268 0 : head3 = clib_llist_make_head (pelts, ll_test);
269 0 : for (i = 0; i < 10; i++)
270 : {
271 0 : clib_llist_get (pelts, e);
272 0 : e->data = 300 + i;
273 0 : he3 = clib_llist_elt (pelts, head3);
274 0 : clib_llist_add (pelts, ll_test, e, he3);
275 : }
276 :
277 0 : he = clib_llist_elt (pelts, head);
278 0 : he3 = clib_llist_elt (pelts, head3);
279 0 : list_test_is_sane (pelts, ll_test, he3);
280 0 : e = clib_llist_prev (pelts, ll_test, he);
281 0 : old_tail = e->data;
282 :
283 : /*
284 : * Splice third list into the tail of the first
285 : */
286 0 : clib_llist_splice (pelts, ll_test, e, he3);
287 :
288 0 : list_test_is_sane (pelts, ll_test, he);
289 0 : LLIST_TEST (clib_llist_is_empty (pelts, ll_test, he3), "should be empty");
290 :
291 0 : e = clib_llist_prev (pelts, ll_test, he);
292 0 : LLIST_TEST (e->data == 300, "data for last spliced should be 300 is %u",
293 : e->data);
294 0 : for (i = 0; i < 10; i++)
295 : {
296 0 : if (e->data != 300 + i)
297 0 : LLIST_TEST (0, "incorrect element i = %u data = %u", i, e->data);
298 0 : e = clib_llist_prev (pelts, ll_test, e);
299 : }
300 :
301 0 : LLIST_TEST (e->data == old_tail, "data should be old tail %u is %u",
302 : old_tail, e->data);
303 :
304 : /*
305 : * Cleanup
306 : */
307 0 : clib_llist_free (pelts);
308 0 : return 0;
309 : }
310 :
311 : static clib_error_t *
312 0 : llist_test (vlib_main_t * vm,
313 : unformat_input_t * input, vlib_cli_command_t * cmd_arg)
314 : {
315 0 : int res = 0;
316 :
317 0 : while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
318 : {
319 0 : if (unformat (input, "basic"))
320 : {
321 0 : res = llist_test_basic (vm, input);
322 : }
323 0 : else if (unformat (input, "all"))
324 : {
325 0 : if ((res = llist_test_basic (vm, input)))
326 0 : goto done;
327 : }
328 : else
329 0 : break;
330 : }
331 :
332 0 : done:
333 0 : if (res)
334 0 : return clib_error_return (0, "llist unit test failed");
335 0 : return 0;
336 : }
337 :
338 : /* *INDENT-OFF* */
339 16239 : VLIB_CLI_COMMAND (llist_test_command, static) =
340 : {
341 : .path = "test llist",
342 : .short_help = "internal llist unit tests",
343 : .function = llist_test,
344 : };
345 : /* *INDENT-ON* */
346 :
347 : /*
348 : * fd.io coding-style-patch-verification: ON
349 : *
350 : * Local Variables:
351 : * eval: (c-set-style "gnu")
352 : * End:
353 : */
|
