Changeset 8d1ad36

Timestamp:

May 11, 2021, 9:14:26 PM (4 years ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

7d51ef8

Parents:

4ab767a

Message:

Adding linked-list convenience functions and testing a corner case.

New API: isEmpty, hasPrev, `hasNext, try_pop_front, try_pop_back

Corner case: modifications near `elems (inserting in all n+1 interator states)

Files:

• libcfa/src/containers/list2.hfa (modified) (5 diffs)
• tests/list/.expect/dlist-insert-remove-2.txt (modified) (1 diff)
• tests/list/dlist-insert-remove-2.cfa (modified) (2 diffs)

libcfa/src/containers/list2.hfa

@@ -17 +17 @@
 
 #include <assert.h>
-
-forall( T & ) struct tag {};
-#define ttag(T) ((tag(T)){})
-#define ztag(n) ttag(Z(n))
 
 extern "C" {
@@ -191 +187 @@
     }
 
+    static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
+        tE * firstPtr = lst.next;
+        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
+        return firstPtr == 0p;
+    }
+
     static inline int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) {
         tE & list_pos_elem = list_pos;
@@ -229 +231 @@
     }
 
+    static inline bool ?`hasNext( diref(tE, tLinks) refx ) {
+        return refx`moveNext;
+    }
+
+    static inline bool ?`hasPrev( diref(tE, tLinks) refx ) {
+        return refx`movePrev;
+    }
+
+    static inline diref(tE, tLinks) ?`next( diref(tE, tLinks) refx ) {
+        if( refx`moveNext ) return refx;
+        tE && ref_inner = refx;
+        & ref_inner = 0p;
+        return refx;
+    }
+
+    static inline diref(tE, tLinks) ?`prev( diref(tE, tLinks) refx ) {
+        if( refx`movePrev ) return refx;
+        tE && ref_inner = refx;
+        & ref_inner = 0p;
+        return refx;
+    }
+
     static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
         insert_after(lst`elems, e);
@@ -235 +259 @@
     static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
         insert_before(lst`elems, e);
+    }
+
+    static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
+        diref(tE, tLinks) first_inlist = lst`first;
+        tE & first_item = first_inlist;
+        if (&first_item) remove(first_inlist);
+        return first_item;
+    }
+
+    static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
+        diref(tE, tLinks) last_inlist = lst`last;
+        tE & last_item = last_inlist;
+        if (&last_item) remove(last_inlist);
+        return last_item;
     }
 
@@ -297 +335 @@
         return ref_dird`movePrev;
     }
-
+    static inline bool ?`hasNext( tE & ref ) {
+        diref(tE, tE) ref_dird = { ref };
+        return ref_dird`hasNext;
+    }
+    static inline bool ?`hasPrev( tE & ref ) {
+        diref(tE, tE) ref_dird = { ref };
+        return ref_dird`hasPrev;
+    }
+    static inline tE & ?`next( tE & ref ) {
+        diref(tE, tE) ref_dird = { ref };
+        diref(tE, tE) rslt = ref_dird`next;
+        return rslt;
+    }
+    static inline tE & ?`prev( tE & ref ) {
+        diref(tE, tE) ref_dird = { ref };
+        diref(tE, tE) rslt = ref_dird`prev;
+        return rslt;
+    }
 }

tests/list/.expect/dlist-insert-remove-2.txt

@@ -1092 +1092 @@
 -
 -
+
+~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~
+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 18-i.  Modifying Freds on MINE
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Not implmented
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 18-ii.  Modifying Freds on YOURS
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Not implmented
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 18-iii.  Modifying Maries
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+accessor_cases done
+try_pop cases done
+origin_mutation cases done

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

@@ -1432 +1432 @@
 }
 
+
+////////////////////////////////////////////////////////////
+//
+// Section 4g
+//
+// Test cases of `isEmpty, `hasPrev, `hasNext,
+// try_pop_front, try_pop_back, modifications via `elems
+//
+// Example of call-side user code
+//
+////////////////////////////////////////////////////////////
+
+void test__accessor_cases__mary() {
+
+        mary m1 = {1.7};
+        mary m2 = {2.7};
+        mary m3 = {3.7};
+
+        dlist(mary, mary) ml;   assert( ml`isEmpty);
+
+        insert_last(ml, m1);    assert(!ml`isEmpty);
+        insert_last(ml, m2);    assert(!ml`isEmpty);
+        insert_last(ml, m3);    assert(!ml`isEmpty);
+
+        mary & m1prev = m1`prev;
+        mary & m1next = m1`next;
+        mary & m2prev = m2`prev;
+        mary & m2next = m2`next;
+        mary & m3prev = m3`prev;
+        mary & m3next = m3`next;
+
+        assert (&m1prev == 0p);
+        assert (&m1next == &m2);
+        assert (&m2prev == &m1);
+        assert (&m2next == &m3);
+        assert (&m3prev == &m2);
+        assert (&m3next == 0p);
+
+        assert(!m1`hasPrev);
+        assert( m1`hasNext);
+        assert( m2`hasPrev);
+        assert( m2`hasNext);
+        assert( m3`hasPrev);
+        assert(!m3`hasNext);
+
+        printf("accessor_cases done\n");
+}
+
+void test__try_pop__mary() {
+
+        mary m1 = {1.7};
+        mary m2 = {2.7};
+        mary m3 = {3.7};
+
+        dlist(mary, mary) ml;
+
+        mary &m1r = *0p;
+        mary &m2r = *0p;
+        mary &m3r = *0p;
+        mary &mxr = *0p;
+
+        // queue, back to front
+
+        assert( ml`isEmpty);
+
+        insert_last(ml, m1);
+        insert_last(ml, m2);
+        insert_last(ml, m3);
+
+        &m1r = & try_pop_front(ml);     assert(!ml`isEmpty);
+        &m2r = & try_pop_front(ml);     assert(!ml`isEmpty);
+        &m3r = & try_pop_front(ml);     assert( ml`isEmpty);
+        &mxr = & try_pop_front(ml);     assert( ml`isEmpty);
+
+        assert( &m1r == &m1 );
+        assert( &m2r == &m2 );
+        assert( &m3r == &m3 );
+        assert( &mxr == 0p  );
+
+        &m1r = 0p;
+        &m2r = 0p;
+        &m3r = 0p;
+
+        // queue, front to back
+
+        assert( ml`isEmpty);
+
+        insert_first(ml, m1);
+        insert_first(ml, m2);
+        insert_first(ml, m3);
+
+        &m1r = & try_pop_back(ml);      assert(!ml`isEmpty);
+        &m2r = & try_pop_back(ml);      assert(!ml`isEmpty);
+        &m3r = & try_pop_back(ml);      assert( ml`isEmpty);
+        &mxr = & try_pop_back(ml);      assert( ml`isEmpty);
+
+        assert( &m1r == &m1 );
+        assert( &m2r == &m2 );
+        assert( &m3r == &m3 );
+        assert( &mxr == 0p  );
+
+        &m1r = 0p;
+        &m2r = 0p;
+        &m3r = 0p;
+
+        // stack at front
+
+        assert( ml`isEmpty);
+
+        insert_first(ml, m1);
+        insert_first(ml, m2);
+        insert_first(ml, m3);
+
+        &m3r = & try_pop_front(ml);     assert(!ml`isEmpty);
+        &m2r = & try_pop_front(ml);     assert(!ml`isEmpty);
+        &m1r = & try_pop_front(ml);     assert( ml`isEmpty);
+        &mxr = & try_pop_front(ml);     assert( ml`isEmpty);
+
+        assert( &m1r == &m1 );
+        assert( &m2r == &m2 );
+        assert( &m3r == &m3 );
+        assert( &mxr == 0p  );
+
+        &m1r = 0p;
+        &m2r = 0p;
+        &m3r = 0p;
+
+        // stack at back
+
+        assert( ml`isEmpty);
+
+        insert_last(ml, m1);
+        insert_last(ml, m2);
+        insert_last(ml, m3);
+
+        &m3r = & try_pop_back(ml);      assert(!ml`isEmpty);
+        &m2r = & try_pop_back(ml);      assert(!ml`isEmpty);
+        &m1r = & try_pop_back(ml);      assert( ml`isEmpty);
+        &mxr = & try_pop_back(ml);      assert( ml`isEmpty);
+
+        assert( &m1r == &m1 );
+        assert( &m2r == &m2 );
+        assert( &m3r == &m3 );
+        assert( &mxr == 0p  );
+
+        &m1r = 0p;
+        &m2r = 0p;
+        &m3r = 0p;
+
+        printf("try_pop cases done\n");
+}
+
+void test__origin_mutation__mary() {
+
+        mary m1 = {1.7};
+
+        dlist(mary, mary) ml;
+        mary & mlorigin = ml`elems;
+
+        // insert before the origin
+
+        insert_before( ml`elems, m1 );
+        assert( ! ml`isEmpty );
+
+        mary & mlfirst = ml`first;
+        mary & mllast = ml`last;
+
+        assert( &m1 == & mlfirst );
+        assert( &m1 == & mllast );
+
+        // moveNext after last goes back to origin, &vv
+
+        bool canMoveNext = mllast`moveNext;
+        bool canMovePrev = mlfirst`movePrev;
+
+        assert( ! canMoveNext );
+        assert( ! canMovePrev );
+
+        assert( &mlorigin == & mlfirst );
+        assert( &mlorigin == & mllast );
+
+        printf("origin_mutation cases done\n");
+}
+
 ////////////////////////////////////////////////////////////
 //
@@ -1708 +1892 @@
         test__pop_last__maries();
 
+        sout | "";
+        sout | "~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~";
+        sout | "";
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 18-i.  Modifying Freds on MINE";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Not implmented";
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 18-ii.  Modifying Freds on YOURS";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Not implmented";
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 18-iii.  Modifying Maries";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+
+        test__accessor_cases__mary();
+        test__try_pop__mary();
+        test__origin_mutation__mary();
+
         return 0;
 }