iPXE
list_test.c
Go to the documentation of this file.
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  */
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 */
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;
90  *(tmp++) = entry->label;
91  *tmp = '\0';
92 
93  /* Sanity check reversed list */
94  tmp = &found_rev[ sizeof ( found_rev ) - 1 ];
95  *tmp = '\0';
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  */
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 );
214  ok ( list_is_last ( &list_tests[6].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 );
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 );
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 );
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 );
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 );
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 );
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 );
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 );
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 );
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 );
345  list_add_tail ( &list_tests[2].list, target );
346  list_add_tail ( &list_tests[4].list, target );
348  list_contents_ok ( target, "95724" );
349 
350  /* Test list_splice_init() */
351  INIT_LIST_HEAD ( list );
352  INIT_LIST_HEAD ( target );
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 );
365  list_add_tail ( &list_tests[5].list, target );
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 );
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 );
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 );
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 );
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 );
457  pos, list, list );
459  pos, list, list );
460 
461  /* Test list_for_each_entry_safe() */
462  INIT_LIST_HEAD ( list );
466  {
467  char *expected = "241";
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 );
486  pos = &list_tests[7];
488  pos, list, list );
489  ok ( pos == list_entry ( list, struct list_test, list ) );
491  pos, list, list );
492  pos = &list_tests[3];
494  pos, list, list );
495  pos = &list_tests[2];
497  pos, list, list );
498  ok ( pos == list_entry ( list, struct list_test, list ) );
500  pos, list, list );
501  pos = &list_tests[4];
503  pos, list, list );
504 
505  /* Test list_contains() and list_contains_entry() */
506  INIT_LIST_HEAD ( 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 );
525 }
526 
527 /** List self-test */
529  .name = "list",
530  .exec = list_test_exec,
531 };
static struct list_test list_tests[]
List test elements.
Definition: list_test.c:50
int printf(const char *fmt,...)
Write a formatted string to the console.
Definition: vsprintf.c:464
#define list_add(new, head)
Add a new entry to the head of a list.
Definition: list.h:69
static LIST_HEAD(test_list)
Test list.
#define list_for_each_entry_continue(pos, head, member)
Iterate over entries in a list, starting after current position.
Definition: list.h:462
#define list_iterate_entry_ok(macro, expected, pos,...)
Report list entry iteration test result.
Definition: list_test.c:153
A list test structure.
Definition: list_test.c:42
#define list_contents_ok(list, expected)
Report list test result.
Definition: list_test.c:122
#define list_next_entry(pos, head, member)
Get the container of the next entry in a list.
Definition: list.h:359
Self-test infrastructure.
#define list_for_each(pos, head)
Iterate over a list.
Definition: list.h:407
const char * name
Test set name.
Definition: test.h:17
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
A self-test set.
Definition: test.h:15
#define list_last_entry(list, type, member)
Get the container of the last entry in a list.
Definition: list.h:346
A doubly-linked list entry (or list head)
Definition: list.h:18
char label
Label.
Definition: list_test.c:46
#define list_empty(list)
Test whether a list is empty.
Definition: list.h:136
#define list_first_entry(list, type, member)
Get the container of the first entry in a list.
Definition: list.h:333
static void list_test_exec(void)
Perform list self-test.
Definition: list_test.c:165
#define list_del(list)
Delete an entry from a list.
Definition: list.h:119
Assertions.
#define list_for_each_entry(pos, head, member)
Iterate over entries in a list.
Definition: list.h:420
#define list_add_tail(new, head)
Add a new entry to the tail of a list.
Definition: list.h:93
#define list_for_each_entry_reverse(pos, head, member)
Iterate over entries in a list in reverse order.
Definition: list.h:433
static int list_check_contents(struct list_head *list, const char *expected)
Check list contents are as expected.
Definition: list_test.c:73
#define list_splice_init(list, entry)
Move all entries from one list into another list and reinitialise empty list.
Definition: list.h:278
#define list_contains_entry(entry, head, member)
Test if list contains a specified entry.
Definition: list.h:512
#define list_iterate_ok(macro, expected, pos,...)
Report list iteration test result.
Definition: list_test.c:134
#define list_for_each_entry_safe(pos, tmp, head, member)
Iterate over entries in a list, safe against deletion of the current entry.
Definition: list.h:447
Linked lists.
#define list_is_last_entry(entry, head, member)
Test if entry is last in a list.
Definition: list.h:398
#define list_splice_tail_init(list, entry)
Move all entries from one list into another list and reinitialise empty list.
Definition: list.h:299
union aes_table_entry entry[256]
Table entries, indexed by S(N)
Definition: aes.c:26
#define list_prev_entry(pos, head, member)
Get the container of the previous entry in a list.
Definition: list.h:373
#define list_splice_tail(list, entry)
Move all entries from one list into another list.
Definition: list.h:250
uint8_t * tmp
Definition: entropy.h:156
#define list_is_first_entry(entry, head, member)
Test if entry is first in a list.
Definition: list.h:387
#define list_cut_position(new, list, entry)
Cut a list into two.
Definition: list.h:185
struct self_test list_test __self_test
List self-test.
Definition: list_test.c:528
#define list_for_each_entry_continue_reverse(pos, head, member)
Iterate over entries in a list in reverse, starting after current position.
Definition: list.h:475
#define INIT_LIST_HEAD(list)
Initialise a list head.
Definition: list.h:45
#define list_is_singular(list)
Test whether a list has just one entry.
Definition: list.h:149
struct list_head list
List element.
Definition: list_test.c:44
int strcmp(const char *first, const char *second)
Compare strings.
Definition: string.c:157
#define list_splice(list, entry)
Move all entries from one list into another list.
Definition: list.h:220
#define list_contains(entry, head)
Test if list contains a specified entry.
Definition: list.h:488
__be32 num_entries
Definition: CIB_PRM.h:31
#define list_check_contains_entry(entry, head, member)
Check list contains a specified entry.
Definition: list.h:522
#define ok(success)
Definition: test.h:46
#define list_entry(list, type, member)
Get the container of a list entry.
Definition: list.h:321
#define list_is_last(list, head)
Test whether an entry is the last entry in list.
Definition: list.h:163
#define NULL
NULL pointer (VOID *)
Definition: Base.h:362
String functions.
if(natsemi->flags &NATSEMI_64BIT) return 1