iPXE
list_test.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2011 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 /** @file
00027  *
00028  * List function tests
00029  *
00030  */
00031 
00032 /* Forcibly enable assertions for list_check() */
00033 #undef NDEBUG
00034 
00035 #include <assert.h>
00036 #include <string.h>
00037 #include <stdio.h>
00038 #include <ipxe/list.h>
00039 #include <ipxe/test.h>
00040 
00041 /** A list test structure */
00042 struct list_test {
00043         /** List element */
00044         struct list_head list;
00045         /** Label */
00046         char label;
00047 };
00048 
00049 /** List test elements */
00050 static struct list_test list_tests[] = {
00051         { .label = '0' },
00052         { .label = '1' },
00053         { .label = '2' },
00054         { .label = '3' },
00055         { .label = '4' },
00056         { .label = '5' },
00057         { .label = '6' },
00058         { .label = '7' },
00059         { .label = '8' },
00060         { .label = '9' },
00061 };
00062 
00063 /** Test list */
00064 static LIST_HEAD ( test_list );
00065 
00066 /**
00067  * Check list contents are as expected
00068  *
00069  * @v list              Test list
00070  * @v expected          Expected contents
00071  * @v ok                List contents are as expected
00072  */
00073 static int list_check_contents ( struct list_head *list,
00074                                  const char *expected ) {
00075         struct list_test *entry;
00076         size_t num_entries = 0;
00077 
00078         /* Determine size of list */
00079         list_for_each_entry ( entry, list, list )
00080                 num_entries++;
00081 
00082         {
00083                 char found[ num_entries + 1 ];
00084                 char found_rev[ num_entries + 1 ];
00085                 char *tmp;
00086 
00087                 /* Build up list content string */
00088                 tmp = found;
00089                 list_for_each_entry ( entry, list, list )
00090                         *(tmp++) = entry->label;
00091                 *tmp = '\0';
00092 
00093                 /* Sanity check reversed list */
00094                 tmp = &found_rev[ sizeof ( found_rev ) - 1 ];
00095                 *tmp = '\0';
00096                 list_for_each_entry_reverse ( entry, list, list )
00097                         *(--tmp) = entry->label;
00098                 if ( strcmp ( found, found_rev ) != 0 ) {
00099                         printf ( "FAILURE: list reversal mismatch (forward "
00100                                  "\"%s\", reverse \"%s\")\n",
00101                                  found, found_rev  );
00102                         return 0;
00103                 }
00104 
00105                 /* Compare against expected content */
00106                 if ( strcmp ( found, expected ) == 0 ) {
00107                         return 1;
00108                 } else {
00109                         printf ( "FAILURE: expected \"%s\", got \"%s\"\n",
00110                          expected, found );
00111                         return 0;
00112                 }
00113         }
00114 }
00115 
00116 /**
00117  * Report list test result
00118  *
00119  * @v list              Test list
00120  * @v expected          Expected contents
00121  */
00122 #define list_contents_ok( list, expected ) do {                 \
00123         ok ( list_check_contents ( (list), (expected) ) );      \
00124         } while ( 0 )
00125 
00126 /**
00127  * Report list iteration test result
00128  *
00129  * @v macro             Iterator macro
00130  * @v expected          Expected contents
00131  * @v pos               Iterator
00132  * @v ...               Arguments to iterator macro
00133  */
00134 #define list_iterate_ok( macro, expected, pos, ... ) do {       \
00135         const char *check = expected;                           \
00136         macro ( pos, __VA_ARGS__ ) {                            \
00137                 struct list_test *entry =                       \
00138                         list_entry ( pos, struct list_test,     \
00139                                      list );                    \
00140                 ok ( entry->label == *(check++) );              \
00141         }                                                       \
00142         ok ( *check == '\0' );                                  \
00143         } while ( 0 )
00144 
00145 /**
00146  * Report list entry iteration test result
00147  *
00148  * @v macro             Iterator macro
00149  * @v expected          Expected contents
00150  * @v pos               Iterator
00151  * @v ...               Arguments to iterator macro
00152  */
00153 #define list_iterate_entry_ok( macro, expected, pos, ... ) do { \
00154         const char *check = expected;                           \
00155         macro ( pos, __VA_ARGS__ ) {                            \
00156                 ok ( (pos)->label == *(check++) );              \
00157         }                                                       \
00158         ok ( *check == '\0' );                                  \
00159         } while ( 0 )
00160 
00161 /**
00162  * Perform list self-test
00163  *
00164  */
00165 static void list_test_exec ( void ) {
00166         struct list_head *list = &test_list;
00167         struct list_head target_list;
00168         struct list_head *target = &target_list;
00169         struct list_head *raw_pos;
00170         struct list_test *pos;
00171         struct list_test *tmp;
00172 
00173         /* Test initialiser and list_empty() */
00174         ok ( list_empty ( list ) );
00175         list_contents_ok ( list, "" );
00176 
00177         /* Test list_add(), list_add_tail() and list_del() */
00178         INIT_LIST_HEAD ( list );
00179         list_contents_ok ( list, "" );
00180         list_add ( &list_tests[4].list, list ); /* prepend */
00181         list_contents_ok ( list, "4" );
00182         list_add ( &list_tests[2].list, list ); /* prepend */
00183         list_contents_ok ( list, "24" );
00184         list_add_tail ( &list_tests[7].list, list ); /* append */
00185         list_contents_ok ( list, "247" );
00186         list_add ( &list_tests[1].list, &list_tests[4].list ); /* after */
00187         list_contents_ok ( list, "2417" );
00188         list_add_tail ( &list_tests[8].list, &list_tests[7].list ); /* before */
00189         list_contents_ok ( list, "24187" );
00190         list_del ( &list_tests[4].list ); /* delete middle */
00191         list_contents_ok ( list, "2187" );
00192         list_del ( &list_tests[2].list ); /* delete first */
00193         list_contents_ok ( list, "187" );
00194         list_del ( &list_tests[7].list ); /* delete last */
00195         list_contents_ok ( list, "18" );
00196         list_del ( &list_tests[1].list ); /* delete all */
00197         list_del ( &list_tests[8].list ); /* delete all */
00198         list_contents_ok ( list, "" );
00199         ok ( list_empty ( list ) );
00200 
00201         /* Test list_is_singular() */
00202         INIT_LIST_HEAD ( list );
00203         ok ( ! list_is_singular ( list ) );
00204         list_add ( &list_tests[1].list, list );
00205         ok ( list_is_singular ( list ) );
00206         list_add ( &list_tests[3].list, list );
00207         ok ( ! list_is_singular ( list ) );
00208         list_del ( &list_tests[1].list );
00209         ok ( list_is_singular ( list ) );
00210 
00211         /* Test list_is_last() */
00212         INIT_LIST_HEAD ( list );
00213         list_add_tail ( &list_tests[6].list, list );
00214         ok ( list_is_last ( &list_tests[6].list, list ) );
00215         list_add_tail ( &list_tests[4].list, list );
00216         ok ( list_is_last ( &list_tests[4].list, list ) );
00217         ok ( ! list_is_last ( &list_tests[6].list, list ) );
00218 
00219         /* Test list_cut_position() - empty list */
00220         INIT_LIST_HEAD ( list );
00221         INIT_LIST_HEAD ( target );
00222         list_cut_position ( target, list, list );
00223         list_contents_ok ( list, "" );
00224         list_contents_ok ( target, "" );
00225 
00226         /* Test list_cut_position() - singular list, move nothing */
00227         INIT_LIST_HEAD ( list );
00228         INIT_LIST_HEAD ( target );
00229         list_add_tail ( &list_tests[4].list, list );
00230         list_cut_position ( target, list, list );
00231         list_contents_ok ( list, "4" );
00232         list_contents_ok ( target, "" );
00233 
00234         /* Test list_cut_position() - singular list, move singular entry */
00235         INIT_LIST_HEAD ( list );
00236         INIT_LIST_HEAD ( target );
00237         list_add_tail ( &list_tests[9].list, list );
00238         list_cut_position ( target, list, &list_tests[9].list );
00239         list_contents_ok ( list, "" );
00240         list_contents_ok ( target, "9" );
00241 
00242         /* Test list_cut_position() - multi-entry list, move nothing */
00243         INIT_LIST_HEAD ( list );
00244         list_add_tail ( &list_tests[3].list, list );
00245         list_add_tail ( &list_tests[2].list, list );
00246         list_add_tail ( &list_tests[7].list, list );
00247         INIT_LIST_HEAD ( target );
00248         list_cut_position ( target, list, list );
00249         list_contents_ok ( list, "327" );
00250         list_contents_ok ( target, "" );
00251 
00252         /* Test list_cut_position() - multi-entry list, move some */
00253         INIT_LIST_HEAD ( list );
00254         INIT_LIST_HEAD ( target );
00255         list_add_tail ( &list_tests[8].list, list );
00256         list_add_tail ( &list_tests[0].list, list );
00257         list_add_tail ( &list_tests[9].list, list );
00258         list_add_tail ( &list_tests[3].list, list );
00259         list_add_tail ( &list_tests[2].list, list );
00260         list_cut_position ( target, list, &list_tests[0].list );
00261         list_contents_ok ( list, "932" );
00262         list_contents_ok ( target, "80" );
00263 
00264         /* Test list_cut_position() - multi-entry list, move everything */
00265         INIT_LIST_HEAD ( list );
00266         INIT_LIST_HEAD ( target );
00267         list_add_tail ( &list_tests[3].list, list );
00268         list_add_tail ( &list_tests[5].list, list );
00269         list_add_tail ( &list_tests[4].list, list );
00270         list_add_tail ( &list_tests[7].list, list );
00271         list_add_tail ( &list_tests[1].list, list );
00272         list_cut_position ( target, list, &list_tests[1].list );
00273         list_contents_ok ( list, "" );
00274         list_contents_ok ( target, "35471" );
00275 
00276         /* Test list_splice() - empty list */
00277         INIT_LIST_HEAD ( list );
00278         INIT_LIST_HEAD ( target );
00279         list_splice ( list, target );
00280         list_contents_ok ( list, "" );
00281         list_contents_ok ( target, "" );
00282 
00283         /* Test list_splice() - both lists empty */
00284         INIT_LIST_HEAD ( list );
00285         INIT_LIST_HEAD ( target );
00286         list_splice ( list, target );
00287         list_contents_ok ( target, "" );
00288 
00289         /* Test list_splice() - source list empty */
00290         INIT_LIST_HEAD ( list );
00291         INIT_LIST_HEAD ( target );
00292         list_add_tail ( &list_tests[1].list, target );
00293         list_add_tail ( &list_tests[3].list, target );
00294         list_splice ( list, &list_tests[1].list );
00295         list_contents_ok ( target, "13" );
00296 
00297         /* Test list_splice() - destination list empty */
00298         INIT_LIST_HEAD ( list );
00299         INIT_LIST_HEAD ( target );
00300         list_add_tail ( &list_tests[6].list, list );
00301         list_add_tail ( &list_tests[5].list, list );
00302         list_add_tail ( &list_tests[2].list, list );
00303         list_splice ( list, target );
00304         list_contents_ok ( target, "652" );
00305 
00306         /* Test list_splice() - both lists non-empty */
00307         INIT_LIST_HEAD ( list );
00308         INIT_LIST_HEAD ( target );
00309         list_add_tail ( &list_tests[8].list, list );
00310         list_add_tail ( &list_tests[4].list, list );
00311         list_add_tail ( &list_tests[5].list, list );
00312         list_add_tail ( &list_tests[1].list, target );
00313         list_add_tail ( &list_tests[9].list, target );
00314         list_splice ( list, &list_tests[1].list );
00315         list_contents_ok ( target, "18459" );
00316 
00317         /* Test list_splice_tail() - both lists empty */
00318         INIT_LIST_HEAD ( list );
00319         INIT_LIST_HEAD ( target );
00320         list_splice_tail ( list, target );
00321         list_contents_ok ( target, "" );
00322 
00323         /* Test list_splice_tail() - source list empty */
00324         INIT_LIST_HEAD ( list );
00325         INIT_LIST_HEAD ( target );
00326         list_add_tail ( &list_tests[5].list, target );
00327         list_splice_tail ( list, &list_tests[5].list );
00328         list_contents_ok ( target, "5" );
00329 
00330         /* Test list_splice_tail() - destination list empty */
00331         INIT_LIST_HEAD ( list );
00332         INIT_LIST_HEAD ( target );
00333         list_add_tail ( &list_tests[2].list, list );
00334         list_add_tail ( &list_tests[1].list, list );
00335         list_add_tail ( &list_tests[0].list, list );
00336         list_splice_tail ( list, target );
00337         list_contents_ok ( target, "210" );
00338 
00339         /* Test list_splice_tail() - both lists non-empty */
00340         INIT_LIST_HEAD ( list );
00341         INIT_LIST_HEAD ( target );
00342         list_add_tail ( &list_tests[9].list, list );
00343         list_add_tail ( &list_tests[5].list, list );
00344         list_add_tail ( &list_tests[7].list, list );
00345         list_add_tail ( &list_tests[2].list, target );
00346         list_add_tail ( &list_tests[4].list, target );
00347         list_splice_tail ( list, &list_tests[2].list );
00348         list_contents_ok ( target, "95724" );
00349 
00350         /* Test list_splice_init() */
00351         INIT_LIST_HEAD ( list );
00352         INIT_LIST_HEAD ( target );
00353         list_add_tail ( &list_tests[4].list, list );
00354         list_add_tail ( &list_tests[1].list, target );
00355         list_splice_init ( list, target );
00356         ok ( list_empty ( list ) );
00357         list_contents_ok ( list, "" );
00358         list_contents_ok ( target, "41" );
00359 
00360         /* Test list_splice_tail_init() */
00361         INIT_LIST_HEAD ( list );
00362         INIT_LIST_HEAD ( target );
00363         list_add_tail ( &list_tests[3].list, list );
00364         list_add_tail ( &list_tests[2].list, list );
00365         list_add_tail ( &list_tests[5].list, target );
00366         list_splice_tail_init ( list, &list_tests[5].list );
00367         ok ( list_empty ( list ) );
00368         list_contents_ok ( list, "" );
00369         list_contents_ok ( target, "325" );
00370 
00371         /* Test list_entry() */
00372         INIT_LIST_HEAD ( &list_tests[3].list );  // for list_check()
00373         ok ( list_entry ( &list_tests[3].list, struct list_test, list )
00374              == &list_tests[3] );
00375 
00376         /* Test list_first_entry() and list_last_entry() */
00377         INIT_LIST_HEAD ( list );
00378         list_add_tail ( &list_tests[9].list, list );
00379         list_add_tail ( &list_tests[5].list, list );
00380         list_add_tail ( &list_tests[6].list, list );
00381         ok ( list_first_entry ( list, struct list_test, list )
00382              == &list_tests[9] );
00383         ok ( list_last_entry ( list, struct list_test, list )
00384              == &list_tests[6] );
00385         list_del ( &list_tests[9].list );
00386         ok ( list_first_entry ( list, struct list_test, list )
00387              == &list_tests[5] );
00388         ok ( list_last_entry ( list, struct list_test, list )
00389              == &list_tests[6] );
00390         list_del ( &list_tests[6].list );
00391         ok ( list_first_entry ( list, struct list_test, list )
00392              == &list_tests[5] );
00393         ok ( list_last_entry ( list, struct list_test, list )
00394              == &list_tests[5] );
00395         list_del ( &list_tests[5].list );
00396         ok ( list_first_entry ( list, struct list_test, list ) == NULL );
00397         ok ( list_last_entry ( list, struct list_test, list ) == NULL );
00398 
00399         /* Test list_next_entry() and list_prev_entry() */
00400         INIT_LIST_HEAD ( list );
00401         list_add_tail ( &list_tests[5].list, list );
00402         list_add_tail ( &list_tests[3].list, list );
00403         list_add_tail ( &list_tests[1].list, list );
00404         list_add_tail ( &list_tests[7].list, list );
00405         ok ( list_prev_entry ( &list_tests[5], list, list ) == NULL );
00406         ok ( list_next_entry ( &list_tests[5], list, list ) == &list_tests[3] );
00407         ok ( list_prev_entry ( &list_tests[3], list, list ) == &list_tests[5] );
00408         ok ( list_next_entry ( &list_tests[3], list, list ) == &list_tests[1] );
00409         ok ( list_prev_entry ( &list_tests[1], list, list ) == &list_tests[3] );
00410         ok ( list_next_entry ( &list_tests[1], list, list ) == &list_tests[7] );
00411         ok ( list_prev_entry ( &list_tests[7], list, list ) == &list_tests[1] );
00412         ok ( list_next_entry ( &list_tests[7], list, list ) == NULL );
00413         list_del ( &list_tests[7].list );
00414         ok ( list_prev_entry ( &list_tests[1], list, list ) == &list_tests[3] );
00415         ok ( list_next_entry ( &list_tests[1], list, list ) == NULL );
00416         list_del ( &list_tests[3].list );
00417         ok ( list_prev_entry ( &list_tests[5], list, list ) == NULL );
00418         ok ( list_next_entry ( &list_tests[5], list, list ) == &list_tests[1] );
00419         ok ( list_prev_entry ( &list_tests[1], list, list ) == &list_tests[5] );
00420         ok ( list_next_entry ( &list_tests[1], list, list ) == NULL );
00421 
00422         /* Test list_is_first_entry() and list_is_last_entry() */
00423         INIT_LIST_HEAD ( list );
00424         list_add_tail ( &list_tests[4].list, list );
00425         list_add_tail ( &list_tests[8].list, list );
00426         list_add_tail ( &list_tests[3].list, list );
00427         list_add_tail ( &list_tests[6].list, list );
00428         ok ( list_is_first_entry ( &list_tests[4], list, list ) );
00429         ok ( ! list_is_first_entry ( &list_tests[8], list, list ) );
00430         ok ( ! list_is_first_entry ( &list_tests[3], list, list ) );
00431         ok ( ! list_is_first_entry ( &list_tests[6], list, list ) );
00432         ok ( ! list_is_last_entry ( &list_tests[4], list, list ) );
00433         ok ( ! list_is_last_entry ( &list_tests[8], list, list ) );
00434         ok ( ! list_is_last_entry ( &list_tests[3], list, list ) );
00435         ok ( list_is_last_entry ( &list_tests[6], list, list ) );
00436         list_del ( &list_tests[4].list );
00437         ok ( list_is_first_entry ( &list_tests[8], list, list ) );
00438         list_del ( &list_tests[8].list );
00439         list_del ( &list_tests[6].list );
00440         ok ( list_is_first_entry ( &list_tests[3], list, list ) );
00441         ok ( list_is_last_entry ( &list_tests[3], list, list ) );
00442 
00443         /* Test list_for_each() */
00444         INIT_LIST_HEAD ( list );
00445         list_add_tail ( &list_tests[6].list, list );
00446         list_add_tail ( &list_tests[7].list, list );
00447         list_add_tail ( &list_tests[3].list, list );
00448         list_iterate_ok ( list_for_each, "673", raw_pos, list );
00449 
00450         /* Test list_for_each_entry() and list_for_each_entry_reverse() */
00451         INIT_LIST_HEAD ( list );
00452         list_add_tail ( &list_tests[3].list, list );
00453         list_add_tail ( &list_tests[2].list, list );
00454         list_add_tail ( &list_tests[6].list, list );
00455         list_add_tail ( &list_tests[9].list, list );
00456         list_iterate_entry_ok ( list_for_each_entry, "3269",
00457                                 pos, list, list );
00458         list_iterate_entry_ok ( list_for_each_entry_reverse, "9623",
00459                                 pos, list, list );
00460 
00461         /* Test list_for_each_entry_safe() */
00462         INIT_LIST_HEAD ( list );
00463         list_add_tail ( &list_tests[2].list, list );
00464         list_add_tail ( &list_tests[4].list, list );
00465         list_add_tail ( &list_tests[1].list, list );
00466         {
00467                 char *expected = "241";
00468                 list_for_each_entry_safe ( pos, tmp, list, list ) {
00469                         list_contents_ok ( list, expected );
00470                         list_del ( &pos->list );
00471                         expected++;
00472                         list_contents_ok ( list, expected );
00473                 }
00474         }
00475         ok ( list_empty ( list ) );
00476 
00477         /* Test list_for_each_entry_continue() and
00478          * list_for_each_entry_continue_reverse()
00479          */
00480         INIT_LIST_HEAD ( list );
00481         list_add_tail ( &list_tests[4].list, list );
00482         list_add_tail ( &list_tests[7].list, list );
00483         list_add_tail ( &list_tests[2].list, list );
00484         list_add_tail ( &list_tests[9].list, list );
00485         list_add_tail ( &list_tests[3].list, list );
00486         pos = &list_tests[7];
00487         list_iterate_entry_ok ( list_for_each_entry_continue, "293",
00488                                 pos, list, list );
00489         ok ( pos == list_entry ( list, struct list_test, list ) );
00490         list_iterate_entry_ok ( list_for_each_entry_continue, "47293",
00491                                 pos, list, list );
00492         pos = &list_tests[3];
00493         list_iterate_entry_ok ( list_for_each_entry_continue, "",
00494                                 pos, list, list );
00495         pos = &list_tests[2];
00496         list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "74",
00497                                 pos, list, list );
00498         ok ( pos == list_entry ( list, struct list_test, list ) );
00499         list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "39274",
00500                                 pos, list, list );
00501         pos = &list_tests[4];
00502         list_iterate_entry_ok ( list_for_each_entry_continue_reverse, "",
00503                                 pos, list, list );
00504 
00505         /* Test list_contains() and list_contains_entry() */
00506         INIT_LIST_HEAD ( list );
00507         INIT_LIST_HEAD ( &list_tests[3].list );
00508         list_add ( &list_tests[8].list, list );
00509         list_add ( &list_tests[5].list, list );
00510         ok ( list_contains ( &list_tests[8].list, list ) );
00511         ok ( list_contains_entry ( &list_tests[8], list, list ) );
00512         ok ( list_contains ( &list_tests[5].list, list ) );
00513         ok ( list_contains_entry ( &list_tests[5], list, list ) );
00514         ok ( ! list_contains ( &list_tests[3].list, list ) );
00515         ok ( ! list_contains_entry ( &list_tests[3], list, list ) );
00516 
00517         /* Test list_check_contains_entry() */
00518         INIT_LIST_HEAD ( list );
00519         list_add ( &list_tests[4].list, list );
00520         list_add ( &list_tests[0].list, list );
00521         list_add ( &list_tests[3].list, list );
00522         list_check_contains_entry ( &list_tests[4], list, list );
00523         list_check_contains_entry ( &list_tests[0], list, list );
00524         list_check_contains_entry ( &list_tests[3], list, list );
00525 }
00526 
00527 /** List self-test */
00528 struct self_test list_test __self_test = {
00529         .name = "list",
00530         .exec = list_test_exec,
00531 };