1 /*
2  * Copyright (C) 2011 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17  * 02110-1301, USA.
18  *
19  * You can also choose to distribute this program under the terms of
20  * the Unmodified Binary Distribution Licence (as given in the file
21  * COPYING.UBDL), provided that you have satisfied its requirements.
22  */
23 
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25 
26 /** @file
27  *
28  * List function tests
29  *
30  */
31 
32 /* Forcibly enable assertions for list_check() */
33 #undef NDEBUG
34 
35 #include <assert.h>
36 #include <string.h>
37 #include <stdio.h>
38 #include <ipxe/list.h>
39 #include <ipxe/test.h>
40 
41 /** A list test structure */
42 struct list_test {
43 	/** List element */
44 	struct list_head list;
45 	/** Label */
46 	char label;
47 };
48 
49 /** List test elements */
50 static struct list_test list_tests[] = {
51 	{ .label = '0' },
52 	{ .label = '1' },
53 	{ .label = '2' },
54 	{ .label = '3' },
55 	{ .label = '4' },
56 	{ .label = '5' },
57 	{ .label = '6' },
58 	{ .label = '7' },
59 	{ .label = '8' },
60 	{ .label = '9' },
61 };
62 
63 /** Test list */
64 static LIST_HEAD ( test_list );
65 
66 /**
67  * Check list contents are as expected
68  *
69  * @v list		Test list
70  * @v expected		Expected contents
71  * @v ok		List contents are as expected
72  */
list_check_contents(struct list_head * list,const char * expected)73 static int list_check_contents ( struct list_head *list,
74 				 const char *expected ) {
75 	struct list_test *entry;
76 	size_t num_entries = 0;
77 
78 	/* Determine size of list */
79 	list_for_each_entry ( entry, list, list )
80 		num_entries++;
81 
82 	{
83 		char found[ num_entries + 1 ];
84 		char found_rev[ num_entries + 1 ];
85 		char *tmp;
86 
87 		/* Build up list content string */
88 		tmp = found;
89 		list_for_each_entry ( entry, list, list )
90 			*(tmp++) = entry->label;
91 		*tmp = '\0';
92 
93 		/* Sanity check reversed list */
94 		tmp = &found_rev[ sizeof ( found_rev ) - 1 ];
95 		*tmp = '\0';
96 		list_for_each_entry_reverse ( entry, list, list )
97 			*(--tmp) = entry->label;
98 		if ( strcmp ( found, found_rev ) != 0 ) {
99 			printf ( "FAILURE: list reversal mismatch (forward "
100 				 "\"%s\", reverse \"%s\")\n",
101 				 found, found_rev  );
102 			return 0;
103 		}
104 
105 		/* Compare against expected content */
106 		if ( strcmp ( found, expected ) == 0 ) {
107 			return 1;
108 		} else {
109 			printf ( "FAILURE: expected \"%s\", got \"%s\"\n",
110 			 expected, found );
111 			return 0;
112 		}
113 	}
114 }
115 
116 /**
117  * Report list test result
118  *
119  * @v list		Test list
120  * @v expected		Expected contents
121  */
122 #define list_contents_ok( list, expected ) do {			\
123 	ok ( list_check_contents ( (list), (expected) ) );	\
124 	} while ( 0 )
125 
126 /**
127  * Report list iteration test result
128  *
129  * @v macro		Iterator macro
130  * @v expected		Expected contents
131  * @v pos		Iterator
132  * @v ...		Arguments to iterator macro
133  */
134 #define list_iterate_ok( macro, expected, pos, ... ) do {	\
135 	const char *check = expected;				\
136 	macro ( pos, __VA_ARGS__ ) {				\
137 		struct list_test *entry =			\
138 			list_entry ( pos, struct list_test,	\
139 				     list );			\
140 		ok ( entry->label == *(check++) );		\
141 	}							\
142 	ok ( *check == '\0' );					\
143 	} while ( 0 )
144 
145 /**
146  * Report list entry iteration test result
147  *
148  * @v macro		Iterator macro
149  * @v expected		Expected contents
150  * @v pos		Iterator
151  * @v ...		Arguments to iterator macro
152  */
153 #define list_iterate_entry_ok( macro, expected, pos, ... ) do {	\
154 	const char *check = expected;				\
155 	macro ( pos, __VA_ARGS__ ) {				\
156 		ok ( (pos)->label == *(check++) );		\
157 	}							\
158 	ok ( *check == '\0' );					\
159 	} while ( 0 )
160 
161 /**
162  * Perform list self-test
163  *
164  */
list_test_exec(void)165 static void list_test_exec ( void ) {
166 	struct list_head *list = &test_list;
167 	struct list_head target_list;
168 	struct list_head *target = &target_list;
169 	struct list_head *raw_pos;
170 	struct list_test *pos;
171 	struct list_test *tmp;
172 
173 	/* Test initialiser and list_empty() */
174 	ok ( list_empty ( list ) );
175 	list_contents_ok ( list, "" );
176 
177 	/* Test list_add(), list_add_tail() and list_del() */
178 	INIT_LIST_HEAD ( list );
179 	list_contents_ok ( list, "" );
180 	list_add ( &list_tests[4].list, list ); /* prepend */
181 	list_contents_ok ( list, "4" );
182 	list_add ( &list_tests[2].list, list ); /* prepend */
183 	list_contents_ok ( list, "24" );
184 	list_add_tail ( &list_tests[7].list, list ); /* append */
185 	list_contents_ok ( list, "247" );
186 	list_add ( &list_tests[1].list, &list_tests[4].list ); /* after */
187 	list_contents_ok ( list, "2417" );
188 	list_add_tail ( &list_tests[8].list, &list_tests[7].list ); /* before */
189 	list_contents_ok ( list, "24187" );
190 	list_del ( &list_tests[4].list ); /* delete middle */
191 	list_contents_ok ( list, "2187" );
192 	list_del ( &list_tests[2].list ); /* delete first */
193 	list_contents_ok ( list, "187" );
194 	list_del ( &list_tests[7].list ); /* delete last */
195 	list_contents_ok ( list, "18" );
196 	list_del ( &list_tests[1].list ); /* delete all */
197 	list_del ( &list_tests[8].list ); /* delete all */
198 	list_contents_ok ( list, "" );
199 	ok ( list_empty ( list ) );
200 
201 	/* Test list_is_singular() */
202 	INIT_LIST_HEAD ( list );
203 	ok ( ! list_is_singular ( list ) );
204 	list_add ( &list_tests[1].list, list );
205 	ok ( list_is_singular ( list ) );
206 	list_add ( &list_tests[3].list, list );
207 	ok ( ! list_is_singular ( list ) );
208 	list_del ( &list_tests[1].list );
209 	ok ( list_is_singular ( list ) );
210 
211 	/* Test list_is_last() */
212 	INIT_LIST_HEAD ( list );
213 	list_add_tail ( &list_tests[6].list, list );
214 	ok ( list_is_last ( &list_tests[6].list, list ) );
215 	list_add_tail ( &list_tests[4].list, list );
216 	ok ( list_is_last ( &list_tests[4].list, list ) );
217 	ok ( ! list_is_last ( &list_tests[6].list, list ) );
218 
219 	/* Test list_cut_position() - empty list */
220 	INIT_LIST_HEAD ( list );
221 	INIT_LIST_HEAD ( target );
222 	list_cut_position ( target, list, list );
223 	list_contents_ok ( list, "" );
224 	list_contents_ok ( target, "" );
225 
226 	/* Test list_cut_position() - singular list, move nothing */
227 	INIT_LIST_HEAD ( list );
228 	INIT_LIST_HEAD ( target );
229 	list_add_tail ( &list_tests[4].list, list );
230 	list_cut_position ( target, list, list );
231 	list_contents_ok ( list, "4" );
232 	list_contents_ok ( target, "" );
233 
234 	/* Test list_cut_position() - singular list, move singular entry */
235 	INIT_LIST_HEAD ( list );
236 	INIT_LIST_HEAD ( target );
237 	list_add_tail ( &list_tests[9].list, list );
238 	list_cut_position ( target, list, &list_tests[9].list );
239 	list_contents_ok ( list, "" );
240 	list_contents_ok ( target, "9" );
241 
242 	/* Test list_cut_position() - multi-entry list, move nothing */
243 	INIT_LIST_HEAD ( list );
244 	list_add_tail ( &list_tests[3].list, list );
245 	list_add_tail ( &list_tests[2].list, list );
246 	list_add_tail ( &list_tests[7].list, list );
247 	INIT_LIST_HEAD ( target );
248 	list_cut_position ( target, list, list );
249 	list_contents_ok ( list, "327" );
250 	list_contents_ok ( target, "" );
251 
252 	/* Test list_cut_position() - multi-entry list, move some */
253 	INIT_LIST_HEAD ( list );
254 	INIT_LIST_HEAD ( target );
255 	list_add_tail ( &list_tests[8].list, list );
256 	list_add_tail ( &list_tests[0].list, list );
257 	list_add_tail ( &list_tests[9].list, list );
258 	list_add_tail ( &list_tests[3].list, list );
259 	list_add_tail ( &list_tests[2].list, list );
260 	list_cut_position ( target, list, &list_tests[0].list );
261 	list_contents_ok ( list, "932" );
262 	list_contents_ok ( target, "80" );
263 
264 	/* Test list_cut_position() - multi-entry list, move everything */
265 	INIT_LIST_HEAD ( list );
266 	INIT_LIST_HEAD ( target );
267 	list_add_tail ( &list_tests[3].list, list );
268 	list_add_tail ( &list_tests[5].list, list );
269 	list_add_tail ( &list_tests[4].list, list );
270 	list_add_tail ( &list_tests[7].list, list );
271 	list_add_tail ( &list_tests[1].list, list );
272 	list_cut_position ( target, list, &list_tests[1].list );
273 	list_contents_ok ( list, "" );
274 	list_contents_ok ( target, "35471" );
275 
276 	/* Test list_splice() - empty list */
277 	INIT_LIST_HEAD ( list );
278 	INIT_LIST_HEAD ( target );
279 	list_splice ( list, target );
280 	list_contents_ok ( list, "" );
281 	list_contents_ok ( target, "" );
282 
283 	/* Test list_splice() - both lists empty */
284 	INIT_LIST_HEAD ( list );
285 	INIT_LIST_HEAD ( target );
286 	list_splice ( list, target );
287 	list_contents_ok ( target, "" );
288 
289 	/* Test list_splice() - source list empty */
290 	INIT_LIST_HEAD ( list );
291 	INIT_LIST_HEAD ( target );
292 	list_add_tail ( &list_tests[1].list, target );
293 	list_add_tail ( &list_tests[3].list, target );
294 	list_splice ( list, &list_tests[1].list );
295 	list_contents_ok ( target, "13" );
296 
297 	/* Test list_splice() - destination list empty */
298 	INIT_LIST_HEAD ( list );
299 	INIT_LIST_HEAD ( target );
300 	list_add_tail ( &list_tests[6].list, list );
301 	list_add_tail ( &list_tests[5].list, list );
302 	list_add_tail ( &list_tests[2].list, list );
303 	list_splice ( list, target );
304 	list_contents_ok ( target, "652" );
305 
306 	/* Test list_splice() - both lists non-empty */
307 	INIT_LIST_HEAD ( list );
308 	INIT_LIST_HEAD ( target );
309 	list_add_tail ( &list_tests[8].list, list );
310 	list_add_tail ( &list_tests[4].list, list );
311 	list_add_tail ( &list_tests[5].list, list );
312 	list_add_tail ( &list_tests[1].list, target );
313 	list_add_tail ( &list_tests[9].list, target );
314 	list_splice ( list, &list_tests[1].list );
315 	list_contents_ok ( target, "18459" );
316 
317 	/* Test list_splice_tail() - both lists empty */
318 	INIT_LIST_HEAD ( list );
319 	INIT_LIST_HEAD ( target );
320 	list_splice_tail ( list, target );
321 	list_contents_ok ( target, "" );
322 
323 	/* Test list_splice_tail() - source list empty */
324 	INIT_LIST_HEAD ( list );
325 	INIT_LIST_HEAD ( target );
326 	list_add_tail ( &list_tests[5].list, target );
327 	list_splice_tail ( list, &list_tests[5].list );
328 	list_contents_ok ( target, "5" );
329 
330 	/* Test list_splice_tail() - destination list empty */
331 	INIT_LIST_HEAD ( list );
332 	INIT_LIST_HEAD ( target );
333 	list_add_tail ( &list_tests[2].list, list );
334 	list_add_tail ( &list_tests[1].list, list );
335 	list_add_tail ( &list_tests[0].list, list );
336 	list_splice_tail ( list, target );
337 	list_contents_ok ( target, "210" );
338 
339 	/* Test list_splice_tail() - both lists non-empty */
340 	INIT_LIST_HEAD ( list );
341 	INIT_LIST_HEAD ( target );
342 	list_add_tail ( &list_tests[9].list, list );
343 	list_add_tail ( &list_tests[5].list, list );
344 	list_add_tail ( &list_tests[7].list, list );
345 	list_add_tail ( &list_tests[2].list, target );
346 	list_add_tail ( &list_tests[4].list, target );
347 	list_splice_tail ( list, &list_tests[2].list );
348 	list_contents_ok ( target, "95724" );
349 
350 	/* Test list_splice_init() */
351 	INIT_LIST_HEAD ( list );
352 	INIT_LIST_HEAD ( target );
353 	list_add_tail ( &list_tests[4].list, list );
354 	list_add_tail ( &list_tests[1].list, target );
355 	list_splice_init ( list, target );
356 	ok ( list_empty ( list ) );
357 	list_contents_ok ( list, "" );
358 	list_contents_ok ( target, "41" );
359 
360 	/* Test list_splice_tail_init() */
361 	INIT_LIST_HEAD ( list );
362 	INIT_LIST_HEAD ( target );
363 	list_add_tail ( &list_tests[3].list, list );
364 	list_add_tail ( &list_tests[2].list, list );
365 	list_add_tail ( &list_tests[5].list, target );
366 	list_splice_tail_init ( list, &list_tests[5].list );
367 	ok ( list_empty ( list ) );
368 	list_contents_ok ( list, "" );
369 	list_contents_ok ( target, "325" );
370 
371 	/* Test list_entry() */
372 	INIT_LIST_HEAD ( &list_tests[3].list );  // for list_check()
373 	ok ( list_entry ( &list_tests[3].list, struct list_test, list )
374 	     == &list_tests[3] );
375 
376 	/* Test list_first_entry() and list_last_entry() */
377 	INIT_LIST_HEAD ( list );
378 	list_add_tail ( &list_tests[9].list, list );
379 	list_add_tail ( &list_tests[5].list, list );
380 	list_add_tail ( &list_tests[6].list, list );
381 	ok ( list_first_entry ( list, struct list_test, list )
382 	     == &list_tests[9] );
383 	ok ( list_last_entry ( list, struct list_test, list )
384 	     == &list_tests[6] );
385 	list_del ( &list_tests[9].list );
386 	ok ( list_first_entry ( list, struct list_test, list )
387 	     == &list_tests[5] );
388 	ok ( list_last_entry ( list, struct list_test, list )
389 	     == &list_tests[6] );
390 	list_del ( &list_tests[6].list );
391 	ok ( list_first_entry ( list, struct list_test, list )
392 	     == &list_tests[5] );
393 	ok ( list_last_entry ( list, struct list_test, list )
394 	     == &list_tests[5] );
395 	list_del ( &list_tests[5].list );
396 	ok ( list_first_entry ( list, struct list_test, list ) == NULL );
397 	ok ( list_last_entry ( list, struct list_test, list ) == NULL );
398 
399 	/* Test list_next_entry() and list_prev_entry() */
400 	INIT_LIST_HEAD ( list );
401 	list_add_tail ( &list_tests[5].list, list );
402 	list_add_tail ( &list_tests[3].list, list );
403 	list_add_tail ( &list_tests[1].list, list );
404 	list_add_tail ( &list_tests[7].list, list );
405 	ok ( list_prev_entry ( &list_tests[5], list, list ) == NULL );
406 	ok ( list_next_entry ( &list_tests[5], list, list ) == &list_tests[3] );
407 	ok ( list_prev_entry ( &list_tests[3], list, list ) == &list_tests[5] );
408 	ok ( list_next_entry ( &list_tests[3], list, list ) == &list_tests[1] );
409 	ok ( list_prev_entry ( &list_tests[1], list, list ) == &list_tests[3] );
410 	ok ( list_next_entry ( &list_tests[1], list, list ) == &list_tests[7] );
411 	ok ( list_prev_entry ( &list_tests[7], list, list ) == &list_tests[1] );
412 	ok ( list_next_entry ( &list_tests[7], list, list ) == NULL );
413 	list_del ( &list_tests[7].list );
414 	ok ( list_prev_entry ( &list_tests[1], list, list ) == &list_tests[3] );
415 	ok ( list_next_entry ( &list_tests[1], list, list ) == NULL );
416 	list_del ( &list_tests[3].list );
417 	ok ( list_prev_entry ( &list_tests[5], list, list ) == NULL );
418 	ok ( list_next_entry ( &list_tests[5], list, list ) == &list_tests[1] );
419 	ok ( list_prev_entry ( &list_tests[1], list, list ) == &list_tests[5] );
420 	ok ( list_next_entry ( &list_tests[1], list, list ) == NULL );
421 
422 	/* Test list_is_first_entry() and list_is_last_entry() */
423 	INIT_LIST_HEAD ( list );
424 	list_add_tail ( &list_tests[4].list, list );
425 	list_add_tail ( &list_tests[8].list, list );
426 	list_add_tail ( &list_tests[3].list, list );
427 	list_add_tail ( &list_tests[6].list, list );
428 	ok ( list_is_first_entry ( &list_tests[4], list, list ) );
429 	ok ( ! list_is_first_entry ( &list_tests[8], list, list ) );
430 	ok ( ! list_is_first_entry ( &list_tests[3], list, list ) );
431 	ok ( ! list_is_first_entry ( &list_tests[6], list, list ) );
432 	ok ( ! list_is_last_entry ( &list_tests[4], list, list ) );
433 	ok ( ! list_is_last_entry ( &list_tests[8], list, list ) );
434 	ok ( ! list_is_last_entry ( &list_tests[3], list, list ) );
435 	ok ( list_is_last_entry ( &list_tests[6], list, list ) );
436 	list_del ( &list_tests[4].list );
437 	ok ( list_is_first_entry ( &list_tests[8], list, list ) );
438 	list_del ( &list_tests[8].list );
439 	list_del ( &list_tests[6].list );
440 	ok ( list_is_first_entry ( &list_tests[3], list, list ) );
441 	ok ( list_is_last_entry ( &list_tests[3], list, list ) );
442 
443 	/* Test list_for_each() */
444 	INIT_LIST_HEAD ( list );
445 	list_add_tail ( &list_tests[6].list, list );
446 	list_add_tail ( &list_tests[7].list, list );
447 	list_add_tail ( &list_tests[3].list, list );
448 	list_iterate_ok ( list_for_each, "673", raw_pos, list );
449 
450 	/* Test list_for_each_entry() and list_for_each_entry_reverse() */
451 	INIT_LIST_HEAD ( list );
452 	list_add_tail ( &list_tests[3].list, list );
453 	list_add_tail ( &list_tests[2].list, list );
454 	list_add_tail ( &list_tests[6].list, list );
455 	list_add_tail ( &list_tests[9].list, list );
456 	list_iterate_entry_ok ( list_for_each_entry, "3269",
457 				pos, list, list );
458 	list_iterate_entry_ok ( list_for_each_entry_reverse, "9623",
459 				pos, list, list );
460 
461 	/* Test list_for_each_entry_safe() */
462 	INIT_LIST_HEAD ( list );
463 	list_add_tail ( &list_tests[2].list, list );
464 	list_add_tail ( &list_tests[4].list, list );
465 	list_add_tail ( &list_tests[1].list, list );
466 	{
467 		char *expected = "241";
468 		list_for_each_entry_safe ( pos, tmp, list, list ) {
469 			list_contents_ok ( list, expected );
470 			list_del ( &pos->list );
471 			expected++;
472 			list_contents_ok ( list, expected );
473 		}
474 	}
475 	ok ( list_empty ( list ) );
476 
477 	/* Test list_for_each_entry_continue() and
478 	 * list_for_each_entry_continue_reverse()
479 	 */
480 	INIT_LIST_HEAD ( list );
481 	list_add_tail ( &list_tests[4].list, list );
482 	list_add_tail ( &list_tests[7].list, list );
483 	list_add_tail ( &list_tests[2].list, list );
484 	list_add_tail ( &list_tests[9].list, list );
485 	list_add_tail ( &list_tests[3].list, list );
486 	pos = &list_tests[7];
487 	list_iterate_entry_ok ( list_for_each_entry_continue, "293",
488 				pos, list, list );
489 	ok ( pos == list_entry ( list, struct list_test, list ) );
490 	list_iterate_entry_ok ( list_for_each_entry_continue, "47293",
491 				pos, list, list );
492 	pos = &list_tests[3];
493 	list_iterate_entry_ok ( list_for_each_entry_continue, "",
494 				pos, list, list );
495 	pos = &list_tests[2];
496 	list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "74",
497 				pos, list, list );
498 	ok ( pos == list_entry ( list, struct list_test, list ) );
499 	list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "39274",
500 				pos, list, list );
501 	pos = &list_tests[4];
502 	list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "",
503 				pos, list, list );
504 
505 	/* Test list_contains() and list_contains_entry() */
506 	INIT_LIST_HEAD ( list );
507 	INIT_LIST_HEAD ( &list_tests[3].list );
508 	list_add ( &list_tests[8].list, list );
509 	list_add ( &list_tests[5].list, list );
510 	ok ( list_contains ( &list_tests[8].list, list ) );
511 	ok ( list_contains_entry ( &list_tests[8], list, list ) );
512 	ok ( list_contains ( &list_tests[5].list, list ) );
513 	ok ( list_contains_entry ( &list_tests[5], list, list ) );
514 	ok ( ! list_contains ( &list_tests[3].list, list ) );
515 	ok ( ! list_contains_entry ( &list_tests[3], list, list ) );
516 
517 	/* Test list_check_contains_entry() */
518 	INIT_LIST_HEAD ( list );
519 	list_add ( &list_tests[4].list, list );
520 	list_add ( &list_tests[0].list, list );
521 	list_add ( &list_tests[3].list, list );
522 	list_check_contains_entry ( &list_tests[4], list, list );
523 	list_check_contains_entry ( &list_tests[0], list, list );
524 	list_check_contains_entry ( &list_tests[3], list, list );
525 }
526 
527 /** List self-test */
528 struct self_test list_test __self_test = {
529 	.name = "list",
530 	.exec = list_test_exec,
531 };
532