Ignore:
Timestamp:
May 4, 2020, 8:45:20 PM (19 months ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast, new-ast-unique-expr
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.

File:
1 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;
Note: See TracChangeset for help on using the changeset viewer.