Changeset f2d05e9

Timestamp:

May 12, 2020, 7:16:49 PM (4 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:

8d462e5

Parents:

70ac8d0

Message:

Dlist API getting pop_first, pop_last, ?`is_empty on the list head.

Files:

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

libcfa/src/containers/list.hfa

@@ -301 +301 @@
                 $prev_link(list_pos) = (Telem*) 0p;
         }
+
+        static inline bool ?`is_empty(dlist(Tnode, Telem) &list) {
+                assert( &list != 0p );
+                $dlinks(Telem) *listLinks = & list.$links;
+                if (listLinks->next.is_terminator) {
+                        assert(listLinks->prev.is_terminator);
+                        assert(listLinks->next.terminator);
+                        assert(listLinks->prev.terminator);
+                        return true;
+                } else {
+                        assert(!listLinks->prev.is_terminator);
+                        assert(listLinks->next.elem);
+                        assert(listLinks->prev.elem);
+                        return false;
+                }
+        }
+
+        static inline Telem & pop_first(dlist(Tnode, Telem) &list) {
+                assert( &list != 0p );
+                assert( !list`is_empty );
+                $dlinks(Telem) *listLinks = & list.$links;
+                Telem & first = *listLinks->next.elem;
+                Tnode & list_pos_first  = $tempcv_e2n( first );
+                remove(list_pos_first);
+                return first;
+        }
+
+        static inline Telem & pop_last(dlist(Tnode, Telem) &list) {
+                assert( &list != 0p );
+                assert( !list`is_empty );
+                $dlinks(Telem) *listLinks = & list.$links;
+                Telem & last = *listLinks->prev.elem;
+                Tnode & list_pos_last  = $tempcv_e2n( last );
+                remove(list_pos_last);
+                return last;
+        }
+
 }
 

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

@@ -1464 +1464 @@
 0.7
 -
+
+~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~
+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 16-i.  Modifying Freds on MINE
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+==== fred by MINE before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by YOURS before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by MINE after 
+2.7
+3.7
+-
+2.7
+-
+3.7
+-
+3.7
+2.7
+-
+==== fred by YOURS after 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by MINE after 
+1.7
+-
+1.7
+-
+-
+-
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 16-ii.  Modifying Freds on YOURS
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+==== fred by MINE before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by YOURS before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by MINE after 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by YOURS after 
+2.7
+3.7
+-
+2.7
+-
+3.7
+-
+3.7
+2.7
+-
+==== fred by YOURS after 
+1.7
+-
+1.7
+-
+-
+-
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 16-iii.  Modifying Maries
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+==== mary before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== mary after 
+2.7
+3.7
+-
+2.7
+-
+3.7
+-
+3.7
+2.7
+-
+==== mary after 
+1.7
+-
+1.7
+-
+-
+-
+
+~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~
+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 17-i.  Modifying Freds on MINE
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+==== fred by MINE before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by YOURS before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by MINE after 
+1.7
+2.7
+-
+1.7
+-
+2.7
+-
+2.7
+1.7
+-
+==== fred by YOURS after 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by MINE after 
+3.7
+-
+3.7
+-
+-
+-
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 17-ii.  Modifying Freds on YOURS
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+==== fred by MINE before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by YOURS before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by MINE after 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== fred by YOURS after 
+1.7
+2.7
+-
+1.7
+-
+2.7
+-
+2.7
+1.7
+-
+==== fred by YOURS after 
+3.7
+-
+3.7
+-
+-
+-
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Test 17-iii.  Modifying Maries
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+==== mary before 
+1.7
+2.7
+3.7
+-
+1.7
+-
+3.7
+-
+3.7
+2.7
+1.7
+-
+==== mary after 
+1.7
+2.7
+-
+1.7
+-
+2.7
+-
+2.7
+1.7
+-
+==== mary after 
+3.7
+-
+3.7
+-
+-
+-

tests/list/dlist-insert-remove.cfa

@@ -1187 +1187 @@
 ////////////////////////////////////////////////////////////
 //
+// Section 4f
+//
+// Test cases of pop_first, pop_last
+//
+// Example of call-side user code
+//
+////////////////////////////////////////////////////////////
+
+// These cases assume element removal at first-last is correct
+
+void test__pop_first__fred_mine() {
+
+        fred f1 = {1.7};
+        fred f2 = {2.7};
+        fred f3 = {3.7};
+
+        dlist(fred_in_mine, fred) flm;
+        insert_last(flm, f1);
+        insert_last(flm, f2);
+        insert_last(flm, f3);
+
+        dlist(fred_in_yours, fred) fly;
+        insert_last(fly, f1);
+        insert_last(fly, f2);
+        insert_last(fly, f3);
+
+        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        fred & popped = pop_first(flm);
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        printMyFreddies(flm`first, flm`last, 0);     // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
+        printYourFreddies(fly`first, fly`last, 0);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
+
+        // observe f1 is now solo in mine; in yours, it was just traversed
+        printMyFreddies(f1, *0p, 0);    // 1.7; 1.7; ;
+
+        assert( &popped == & f1 );
+}
+
+void test__pop_first__fred_yours() {
+
+        fred f1 = {1.7};
+        fred f2 = {2.7};
+        fred f3 = {3.7};
+
+        dlist(fred_in_mine, fred) flm;
+        insert_last(flm, f1);
+        insert_last(flm, f2);
+        insert_last(flm, f3);
+
+        dlist(fred_in_yours, fred) fly;
+        insert_last(fly, f1);
+        insert_last(fly, f2);
+        insert_last(fly, f3);
+
+        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        fred & popped = pop_first(fly);
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
+        printYourFreddies(fly`first, fly`last, 0);   // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
+
+        // observe f1 is now solo in yours; in mine, it was just traversed
+        printYourFreddies(f1, *0p, 0);    // 1.7; 1.7; ;
+
+        assert( &popped == &f1 );
+}
+
+void test__pop_first__maries() {
+
+        mary m1 = {1.7};
+        mary m2 = {2.7};
+        mary m3 = {3.7};
+
+        dlist(mary, mary) ml;
+        insert_last(ml, m1);
+        insert_last(ml, m2);
+        insert_last(ml, m3);
+
+        printMariatheotokos(ml`first, ml`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+
+        verify(validate(ml));
+
+        mary & popped = pop_first(ml);
+
+        verify(validate(ml));
+
+        printMariatheotokos(ml`first, ml`last, 0);     // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
+
+        // observe m1 is now solo
+        printMariatheotokos(m1, *0p, 0);               // 1.7; 1.7; ;
+
+        assert( &popped == &m1 );
+}
+
+void test__pop_last__fred_mine() {
+
+        fred f1 = {1.7};
+        fred f2 = {2.7};
+        fred f3 = {3.7};
+
+        dlist(fred_in_mine, fred) flm;
+        insert_last(flm, f1);
+        insert_last(flm, f2);
+        insert_last(flm, f3);
+
+        dlist(fred_in_yours, fred) fly;
+        insert_last(fly, f1);
+        insert_last(fly, f2);
+        insert_last(fly, f3);
+
+        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        fred & popped = pop_last(flm);
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7;       1.7;  2.7;  2.7, 1.7      (modified)
+        printYourFreddies(fly`first, fly`last, 0);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
+
+        // observe f3 is now solo in mine; in yours, it was just traversed
+        printMyFreddies(f3, *0p, 0);    // 3.7; 3.7; ;
+
+        assert( &popped == & f3 );
+}
+
+void test__pop_last__fred_yours() {
+
+        fred f1 = {1.7};
+        fred f2 = {2.7};
+        fred f3 = {3.7};
+
+        dlist(fred_in_mine, fred) flm;
+        insert_last(flm, f1);
+        insert_last(flm, f2);
+        insert_last(flm, f3);
+
+        dlist(fred_in_yours, fred) fly;
+        insert_last(fly, f1);
+        insert_last(fly, f2);
+        insert_last(fly, f3);
+
+        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        fred & popped = pop_last(fly);
+
+        verify(validate(fly));
+        verify(validate(flm));
+
+        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
+        printYourFreddies(fly`first, fly`last, 0);   // 1.7, 2.7;       1.7;  2.7;  2.7, 1.7      (modified)
+
+        // observe f3 is now solo in yours; in mine, it was just traversed
+        printYourFreddies(f3, *0p, 0);    // 3.7; 3.7; ;
+
+        assert( &popped == & f3 );
+}
+
+void test__pop_last__maries() {
+
+        mary m1 = {1.7};
+        mary m2 = {2.7};
+        mary m3 = {3.7};
+
+        dlist(mary, mary) ml;
+        insert_last(ml, m1);
+        insert_last(ml, m2);
+        insert_last(ml, m3);
+
+        printMariatheotokos(ml`first, ml`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 
+
+        verify(validate(ml));
+
+        mary & popped = pop_last(ml);
+
+        verify(validate(ml));
+
+        printMariatheotokos(ml`first, ml`last, 0);     // 1.7, 1.7;       1.7;  2.7;  2.7, 1.7      (modified)
+
+        // observe m1 is now solo
+        printMariatheotokos(m3, *0p, 0);               // 3.7; 3.7; ;
+
+        assert( &popped == &m3 );
+}
+
+////////////////////////////////////////////////////////////
+//
 // Section 5
 //
@@ -1422 +1632 @@
         test__remove_of_sole__mary();
 
+        sout | "";
+        sout | "~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~";
+        sout | "";
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 16-i.  Modifying Freds on MINE";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        test__pop_first__fred_mine();
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 16-ii.  Modifying Freds on YOURS";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        test__pop_first__fred_yours();
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 16-iii.  Modifying Maries";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        test__pop_first__maries();
+
+        sout | "";
+        sout | "~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~";
+        sout | "";
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 17-i.  Modifying Freds on MINE";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        test__pop_last__fred_mine();
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 17-ii.  Modifying Freds on YOURS";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        test__pop_last__fred_yours();
+
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        sout | "Test 17-iii.  Modifying Maries";
+        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
+        test__pop_last__maries();
+
         return 0;
 }