Changeset 4d741e9


Ignore:
Timestamp:
May 4, 2020, 8:45:20 PM (5 years ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
d3ab183
Parents:
3f7d0b4
Message:

Strengthened test and fixed a bug on dlist.

The test acceptance criteria are now stricter with white- and black-box checks added. New white-box checking, borrowed from alarm's linked-list verify ensures that headed lists reach last when traversed starting from first, and vice-versa. New black-box checking ensures the link from an ending element to the head sentinel is intact.

The bug was that element insertion at an end of a headed list broke the new black-box criterion. The new white-box criterion was never violated in the current test cases, but early work at integrating this list with the alarm system exercised such a break.

Both checks behind the new test criteria are packaged as a verify routine for user code to invoke.

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/containers/list.hfa

    r3f7d0b4 r4d741e9  
    7171                // will collapse to single pointer with tag bit
    7272        };
    73         inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
     73        static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
    7474                (this.elem){ elem };
    7575                (this.terminator){ 0p };
    7676                (this.is_terminator){ 0 };
    7777        }
    78         inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
     78        static inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
    7979                (this.elem){ 0p };
    8080                (this.terminator){ terminator };
    … …  
    8282        }
    8383        forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
    84         void ?=?( $mgd_link(tE) &this, tInit i ) {
     84        static inline void ?=?( $mgd_link(tE) &this, tInit i ) {
    8585                ^?{}( this );
    8686                ?{}( this, i );
    … …  
    9393                $mgd_link(tE) prev;
    9494        };
    95         inline void ?{}( $dlinks(tE) &this ) {
     95        static inline void ?{}( $dlinks(tE) &this ) {
    9696                (this.next){ (tE *)0p };
    9797                (this.prev){ (tE *)0p };
    … …  
    132132        // an empty dlist
    133133        // links refer to self, making a tight circle
    134         void ?{}( dlist(Tnode, Telem) & this ) {
     134        static inline void ?{}( dlist(Tnode, Telem) & this ) {
    135135                $mgd_link(Telem) selfRef = (void *) &this;
    136136                ( this.$links ) { selfRef, selfRef };
    137137        }
    138138
    139         Telem & ?`first( dlist(Tnode, Telem) &l ) {
     139        static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
    140140                return * l.$links.next.elem;
    141141        }
    142142
    143         Telem & ?`last( dlist(Tnode, Telem) &l ) {
     143        static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
    144144                return * l.$links.prev.elem;
    145145        }
     146
     147        #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
     148        static bool $validate_fwd( dlist(Tnode, Telem) & this ) {
     149                Tnode * it = & $tempcv_e2n( this`first );
     150                if (!it) return (& this`last == 0p);
     151
     152                while( $next_link(*it).elem ) {
     153                        it = & $tempcv_e2n( * $next_link(*it).elem );
     154                }
     155
     156                return ( it == & $tempcv_e2n( this`last ) ) &&
     157                           ( $next_link(*it).is_terminator ) &&
     158                           ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this );
     159        }
     160        static bool $validate_rev( dlist(Tnode, Telem) & this ) {
     161                Tnode * it = & $tempcv_e2n( this`last );
     162                if (!it) return (& this`first == 0p);
     163
     164                while( $prev_link(*it).elem ) {
     165                        it = & $tempcv_e2n( * $prev_link(*it).elem );
     166                }
     167
     168                return ( it == & $tempcv_e2n( this`first ) ) &&
     169                           ( $prev_link(*it).is_terminator ) &&
     170                           ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this );
     171        }
     172        static bool validate( dlist(Tnode, Telem) & this ) {
     173                return $validate_fwd(this) && $validate_rev(this);
     174        }
     175        #endif
    146176
    147177        static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
    … …  
    152182                assert($next_link(singleton_to_insert).elem == 0p);
    153183                $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
    154                 $next_link(singleton_to_insert) = $next_link(list_pos).elem;
     184                $next_link(singleton_to_insert) = $next_link(list_pos);
    155185                if ($next_link(list_pos).is_terminator) {
    156186                        dlist(Tnode, Telem) *list = $next_link(list_pos).terminator;
    … …  
    175205                assert($next_link(singleton_to_insert).elem == 0p);
    176206                $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
    177                 $prev_link(singleton_to_insert) = $prev_link(list_pos).elem;
     207                $prev_link(singleton_to_insert) = $prev_link(list_pos);
    178208                if ($prev_link(list_pos).is_terminator) {
    179209                        dlist(Tnode, Telem) *list = $prev_link(list_pos).terminator;

  • tests/list/dlist-insert-remove.cfa

    r3f7d0b4 r4d741e9  
    258258        dlist(fred_in_mine, fred) lf;
    259259
     260        verify(validate(lf));
     261
    260262        printMyFreddies(f1, f2, 1);     // 3.14; 3.14; 0.5; 0.5
    261263        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    … …  
    264266        insert_first(lf, f1);
    265267
     268        verify(validate(lf));
     269
    266270        printMyFreddies(f1, f2, 0);     // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    267271        printYourFreddies(f1, f2, 0);   // 3.14; 3.14; 0.5; 0.5 (unmodified)
    … …  
    275279        dlist(fred_in_yours, fred) lf;
    276280
     281        verify(validate(lf));
     282
    277283        printMyFreddies(f1, f2, 1);     // 3.14; 3.14; 0.5; 0.5
    278284        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    … …  
    281287        insert_first(lf, f1);
    282288
     289        verify(validate(lf));
     290
    283291        printMyFreddies(f1, f2, 0);     // 3.14; 3.14; 0.5; 0.5 (unmodified)
    284292        printYourFreddies(f1, f2, 0);   // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    292300        dlist(mary, mary) lm;
    293301
     302        verify(validate(lm));
    294303        printMariatheotokos(m1, m2, 1); // 3.14; 3.14; 0.5; 0.5
    295304
    … …  
    298307
    299308        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
     309        verify(validate(lm));
    300310}
    301311
    … …  
    317327        dlist(fred_in_mine, fred) lf;
    318328
     329        verify(validate(lf));
     330
    319331        printMyFreddies(f1, f2, 1);     // 3.14; 3.14; 0.5; 0.5
    320332        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    … …  
    323335        insert_last(lf, f2);
    324336
     337        verify(validate(lf));
     338
    325339        printMyFreddies(f1, f2, 0);     // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    326340        printYourFreddies(f1, f2, 0);   // 3.14; 3.14; 0.5; 0.5 (unmodified)
    … …  
    334348        dlist(fred_in_yours, fred) lf;
    335349
     350        verify(validate(lf));
     351
    336352        printMyFreddies(f1, f2, 1);     // 3.14; 3.14; 0.5; 0.5
    337353        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    … …  
    340356        insert_last(lf, f2);
    341357
     358        verify(validate(lf));
     359
    342360        printMyFreddies(f1, f2, 0);     // 3.14; 3.14; 0.5; 0.5 (unmodified)
    343361        printYourFreddies(f1, f2, 0);   // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    351369        dlist(mary, mary) lm;
    352370
     371        verify(validate(lm));
    353372        printMariatheotokos(m1, m2, 1); // 3.14; 3.14; 0.5; 0.5
    354373
    … …  
    356375        insert_last(lm, m2);
    357376
     377        verify(validate(lm));
    358378        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    359379}
    … …  
    384404        assert(& lf`last == & f1);
    385405
     406        verify(validate(lf));
     407
    386408        insert_after(f1`in_mine, f2);
     409
     410        verify(validate(lf));
    387411
    388412        printMyFreddies(f1, f2, 0);     // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    408432        assert(& lf`last == & f1);
    409433
     434        verify(validate(lf));
     435
    410436        insert_after(f1`in_yours, f2);
     437
     438        verify(validate(lf));
    411439
    412440        printMyFreddies(f1, f2, 0);     // 3.14; 3.14; 0.5; 0.5 (unmodified)
    … …  
    432460        assert(& lm`last == & m1);
    433461
     462        verify(validate(lm));
     463
    434464        insert_after(m1, m2);
     465
     466        verify(validate(lm));
    435467
    436468        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    465497        assert(& lf`last == & f2);
    466498
     499        verify(validate(lf));
     500
    467501        insert_before(f2`in_mine, f1);
     502
     503        verify(validate(lf));
    468504
    469505        printMyFreddies(f1, f2, 0);     // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    489525        assert(& lf`last == & f2);
    490526
     527        verify(validate(lf));
     528
    491529        insert_before(f2`in_yours, f1);
     530
     531        verify(validate(lf));
    492532
    493533        printMyFreddies(f1, f2, 0);     // 3.14; 3.14; 0.5; 0.5 (unmodified)
    … …  
    513553        assert(& lm`last == & m2);
    514554
     555        verify(validate(lm));
     556
    515557        insert_before(m2, m1);
     558
     559        verify(validate(lm));
    516560
    517561        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    822866        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
    823867
     868        verify(validate(fly));
     869        verify(validate(flm));
     870
    824871        remove(f1`in_mine);
     872
     873        verify(validate(fly));
     874        verify(validate(flm));
    825875
    826876        printMyFreddies(flm`first, flm`last, 0);     // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
    … …  
    854904        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
    855905
     906        verify(validate(fly));
     907        verify(validate(flm));
     908
    856909        remove(f1`in_yours);
     910
     911        verify(validate(fly));
     912        verify(validate(flm));
    857913
    858914        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
    … …  
    880936        printMariatheotokos(ml`first, ml`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
    881937
     938        verify(validate(ml));
     939
    882940        remove(m1);
     941
     942        verify(validate(ml));
    883943
    884944        printMariatheotokos(ml`first, ml`last, 0);     // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
    … …  
    921981        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
    922982
     983        verify(validate(fly));
     984        verify(validate(flm));
     985
    923986        remove(f3`in_mine);
     987
     988        verify(validate(fly));
     989        verify(validate(flm));
    924990
    925991        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7;       1.7;  2.7;  2.7, 1.7      (modified)
    … …  
    9531019        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
    9541020
     1021        verify(validate(fly));
     1022        verify(validate(flm));
     1023
    9551024        remove(f3`in_yours);
     1025
     1026        verify(validate(fly));
     1027        verify(validate(flm));
    9561028
    9571029        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
    … …  
    9791051        printMariatheotokos(ml`first, ml`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
    9801052
     1053        verify(validate(ml));
     1054
    9811055        remove(m3);
     1056
     1057        verify(validate(ml));
    9821058
    9831059        printMariatheotokos(ml`first, ml`last, 0);     // 1.7, 2.7;       1.7;  2.7;  2.7, 1.7      (modified)
    … …  
    10141090        printYourFreddies(fly`first, fly`last, 1);   // 0.7; 0.7; 0.7; 0.7
    10151091
     1092        verify(validate(fly));
     1093        verify(validate(flm));
     1094
    10161095        remove(f`in_mine);
     1096
     1097        verify(validate(fly));
     1098        verify(validate(flm));
    10171099
    10181100        assert(& flm`first == 0p);
    … …  
    10291111
    10301112        insert_last(flm, f);
     1113        verify(validate(fly));
     1114        verify(validate(flm));
    10311115        printMyFreddies(flm`first, flm`last, 0);     // 0.7; 0.7; 0.7; 0.7
    10321116}
    … …  
    10451129        printYourFreddies(fly`first, fly`last, 1);   // 0.7; 0.7; 0.7; 0.7
    10461130
     1131        verify(validate(fly));
     1132        verify(validate(flm));
     1133
    10471134        remove(f`in_yours);
     1135
     1136        verify(validate(fly));
     1137        verify(validate(flm));
    10481138
    10491139        assert(& fly`first == 0p);
    … …  
    10601150
    10611151        insert_last(fly, f);
     1152        verify(validate(fly));
     1153        verify(validate(flm));
    10621154        printYourFreddies(fly`first, fly`last, 0);     // 0.7; 0.7; 0.7; 0.7
    10631155}
    … …  
    10721164        printMariatheotokos(ml`first, ml`last, 1);     // 0.7; 0.7; 0.7; 0.7
    10731165
     1166        verify(validate(ml));
     1167
    10741168        remove(m);
     1169
     1170        verify(validate(ml));
    10751171
    10761172        assert(& ml`first == 0p);
    … …  
    10851181
    10861182        insert_last(ml, m);
     1183        verify(validate(ml));
    10871184        printMariatheotokos(ml`first, ml`last, 0);     // 0.7; 0.7; 0.7; 0.7
    10881185}
Note: See TracChangeset for help on using the changeset viewer.