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