qemu/roms/ipxe/src/tests/list_test.c

   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 */
  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  */
 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_for_each() */
 400         INIT_LIST_HEAD ( list );
 401         list_add_tail ( &list_tests[6].list, list );
 402         list_add_tail ( &list_tests[7].list, list );
 403         list_add_tail ( &list_tests[3].list, list );
 404         list_iterate_ok ( list_for_each, "673", raw_pos, list );
 405
 406         /* Test list_for_each_entry() and list_for_each_entry_reverse() */
 407         INIT_LIST_HEAD ( list );
 408         list_add_tail ( &list_tests[3].list, list );
 409         list_add_tail ( &list_tests[2].list, list );
 410         list_add_tail ( &list_tests[6].list, list );
 411         list_add_tail ( &list_tests[9].list, list );
 412         list_iterate_entry_ok ( list_for_each_entry, "3269",
 413                                 pos, list, list );
 414         list_iterate_entry_ok ( list_for_each_entry_reverse, "9623",
 415                                 pos, list, list );
 416
 417         /* Test list_for_each_entry_safe() */
 418         INIT_LIST_HEAD ( list );
 419         list_add_tail ( &list_tests[2].list, list );
 420         list_add_tail ( &list_tests[4].list, list );
 421         list_add_tail ( &list_tests[1].list, list );
 422         {
 423                 char *expected = "241";
 424                 list_for_each_entry_safe ( pos, tmp, list, list ) {
 425                         list_contents_ok ( list, expected );
 426                         list_del ( &pos->list );
 427                         expected++;
 428                         list_contents_ok ( list, expected );
 429                 }
 430         }
 431         ok ( list_empty ( list ) );
 432
 433         /* Test list_for_each_entry_continue() and
 434          * list_for_each_entry_continue_reverse()
 435          */
 436         INIT_LIST_HEAD ( list );
 437         list_add_tail ( &list_tests[4].list, list );
 438         list_add_tail ( &list_tests[7].list, list );
 439         list_add_tail ( &list_tests[2].list, list );
 440         list_add_tail ( &list_tests[9].list, list );
 441         list_add_tail ( &list_tests[3].list, list );
 442         pos = &list_tests[7];
 443         list_iterate_entry_ok ( list_for_each_entry_continue, "293",
 444                                 pos, list, list );
 445         ok ( pos == list_entry ( list, struct list_test, list ) );
 446         list_iterate_entry_ok ( list_for_each_entry_continue, "47293",
 447                                 pos, list, list );
 448         pos = &list_tests[3];
 449         list_iterate_entry_ok ( list_for_each_entry_continue, "",
 450                                 pos, list, list );
 451         pos = &list_tests[2];
 452         list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "74",
 453                                 pos, list, list );
 454         ok ( pos == list_entry ( list, struct list_test, list ) );
 455         list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "39274",
 456                                 pos, list, list );
 457         pos = &list_tests[4];
 458         list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "",
 459                                 pos, list, list );
 460
 461         /* Test list_contains() and list_contains_entry() */
 462         INIT_LIST_HEAD ( list );
 463         INIT_LIST_HEAD ( &list_tests[3].list );
 464         list_add ( &list_tests[8].list, list );
 465         list_add ( &list_tests[5].list, list );
 466         ok ( list_contains ( &list_tests[8].list, list ) );
 467         ok ( list_contains_entry ( &list_tests[8], list, list ) );
 468         ok ( list_contains ( &list_tests[5].list, list ) );
 469         ok ( list_contains_entry ( &list_tests[5], list, list ) );
 470         ok ( ! list_contains ( &list_tests[3].list, list ) );
 471         ok ( ! list_contains_entry ( &list_tests[3], list, list ) );
 472
 473         /* Test list_check_contains_entry() */
 474         INIT_LIST_HEAD ( list );
 475         list_add ( &list_tests[4].list, list );
 476         list_add ( &list_tests[0].list, list );
 477         list_add ( &list_tests[3].list, list );
 478         list_check_contains_entry ( &list_tests[4], list, list );
 479         list_check_contains_entry ( &list_tests[0], list, list );
 480         list_check_contains_entry ( &list_tests[3], list, list );
 481 }
 482
 483 /** List self-test */
 484 struct self_test list_test __self_test = {
 485         .name = "list",
 486         .exec = list_test_exec,
 487 };