Changeset 4d741e9 for libcfa/src/containers/list.hfa

Timestamp:

May 4, 2020, 8:45:20 PM (3 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

ADT, arm-eh, 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.

File:

• libcfa/src/containers/list.hfa (modified) (6 diffs)

libcfa/src/containers/list.hfa

@@ -71 +71 @@
                 // will collapse to single pointer with tag bit
         };
-        inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
+        static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
                 (this.elem){ elem };
                 (this.terminator){ 0p };
                 (this.is_terminator){ 0 };
         }
-        inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
+        static inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
                 (this.elem){ 0p };
                 (this.terminator){ terminator };
@@ -82 +82 @@
         }
         forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
-        void ?=?( $mgd_link(tE) &this, tInit i ) {
+        static inline void ?=?( $mgd_link(tE) &this, tInit i ) {
                 ^?{}( this );
                 ?{}( this, i );
@@ -93 +93 @@
                 $mgd_link(tE) prev;
         };
-        inline void ?{}( $dlinks(tE) &this ) {
+        static inline void ?{}( $dlinks(tE) &this ) {
                 (this.next){ (tE *)0p };
                 (this.prev){ (tE *)0p };
@@ -132 +132 @@
         // an empty dlist
         // links refer to self, making a tight circle
-        void ?{}( dlist(Tnode, Telem) & this ) {
+        static inline void ?{}( dlist(Tnode, Telem) & this ) {
                 $mgd_link(Telem) selfRef = (void *) &this;
                 ( this.$links ) { selfRef, selfRef };
         }
 
-        Telem & ?`first( dlist(Tnode, Telem) &l ) {
+        static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
                 return * l.$links.next.elem;
         }
 
-        Telem & ?`last( dlist(Tnode, Telem) &l ) {
+        static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
                 return * l.$links.prev.elem;
         }
+
+        #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
+        static bool $validate_fwd( dlist(Tnode, Telem) & this ) {
+                Tnode * it = & $tempcv_e2n( this`first );
+                if (!it) return (& this`last == 0p);
+
+                while( $next_link(*it).elem ) {
+                        it = & $tempcv_e2n( * $next_link(*it).elem );
+                }
+
+                return ( it == & $tempcv_e2n( this`last ) ) &&
+                           ( $next_link(*it).is_terminator ) &&
+                           ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this );
+        }
+        static bool $validate_rev( dlist(Tnode, Telem) & this ) {
+                Tnode * it = & $tempcv_e2n( this`last );
+                if (!it) return (& this`first == 0p);
+
+                while( $prev_link(*it).elem ) {
+                        it = & $tempcv_e2n( * $prev_link(*it).elem );
+                }
+
+                return ( it == & $tempcv_e2n( this`first ) ) &&
+                           ( $prev_link(*it).is_terminator ) &&
+                           ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this );
+        }
+        static bool validate( dlist(Tnode, Telem) & this ) {
+                return $validate_fwd(this) && $validate_rev(this);
+        }
+        #endif
 
         static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
@@ -152 +182 @@
                 assert($next_link(singleton_to_insert).elem == 0p);
                 $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
-                $next_link(singleton_to_insert) = $next_link(list_pos).elem;
+                $next_link(singleton_to_insert) = $next_link(list_pos);
                 if ($next_link(list_pos).is_terminator) {
                         dlist(Tnode, Telem) *list = $next_link(list_pos).terminator;
@@ -175 +205 @@
                 assert($next_link(singleton_to_insert).elem == 0p);
                 $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
-                $prev_link(singleton_to_insert) = $prev_link(list_pos).elem;
+                $prev_link(singleton_to_insert) = $prev_link(list_pos);
                 if ($prev_link(list_pos).is_terminator) {
                         dlist(Tnode, Telem) *list = $prev_link(list_pos).terminator;