Changeset 8d1ad36


Ignore:
Timestamp:
May 11, 2021, 9:14:26 PM (17 months ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
arm-eh, 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:
3 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/containers/list2.hfa

    r4ab767a r8d1ad36  
    1717
    1818#include <assert.h>
    19 
    20 forall( T & ) struct tag {};
    21 #define ttag(T) ((tag(T)){})
    22 #define ztag(n) ttag(Z(n))
    2319
    2420extern "C" {
     
    191187    }
    192188
     189    static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
     190        tE * firstPtr = lst.next;
     191        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     192        return firstPtr == 0p;
     193    }
     194
    193195    static inline int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) {
    194196        tE & list_pos_elem = list_pos;
     
    229231    }
    230232
     233    static inline bool ?`hasNext( diref(tE, tLinks) refx ) {
     234        return refx`moveNext;
     235    }
     236
     237    static inline bool ?`hasPrev( diref(tE, tLinks) refx ) {
     238        return refx`movePrev;
     239    }
     240
     241    static inline diref(tE, tLinks) ?`next( diref(tE, tLinks) refx ) {
     242        if( refx`moveNext ) return refx;
     243        tE && ref_inner = refx;
     244        & ref_inner = 0p;
     245        return refx;
     246    }
     247
     248    static inline diref(tE, tLinks) ?`prev( diref(tE, tLinks) refx ) {
     249        if( refx`movePrev ) return refx;
     250        tE && ref_inner = refx;
     251        & ref_inner = 0p;
     252        return refx;
     253    }
     254
    231255    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    232256        insert_after(lst`elems, e);
     
    235259    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    236260        insert_before(lst`elems, e);
     261    }
     262
     263    static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
     264        diref(tE, tLinks) first_inlist = lst`first;
     265        tE & first_item = first_inlist;
     266        if (&first_item) remove(first_inlist);
     267        return first_item;
     268    }
     269
     270    static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
     271        diref(tE, tLinks) last_inlist = lst`last;
     272        tE & last_item = last_inlist;
     273        if (&last_item) remove(last_inlist);
     274        return last_item;
    237275    }
    238276
     
    297335        return ref_dird`movePrev;
    298336    }
    299 
     337    static inline bool ?`hasNext( tE & ref ) {
     338        diref(tE, tE) ref_dird = { ref };
     339        return ref_dird`hasNext;
     340    }
     341    static inline bool ?`hasPrev( tE & ref ) {
     342        diref(tE, tE) ref_dird = { ref };
     343        return ref_dird`hasPrev;
     344    }
     345    static inline tE & ?`next( tE & ref ) {
     346        diref(tE, tE) ref_dird = { ref };
     347        diref(tE, tE) rslt = ref_dird`next;
     348        return rslt;
     349    }
     350    static inline tE & ?`prev( tE & ref ) {
     351        diref(tE, tE) ref_dird = { ref };
     352        diref(tE, tE) rslt = ref_dird`prev;
     353        return rslt;
     354    }
    300355}
  • tests/list/.expect/dlist-insert-remove-2.txt

    r4ab767a r8d1ad36  
    10921092-
    10931093-
     1094
     1095~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~
     1096
     1097~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1098Test 18-i.  Modifying Freds on MINE
     1099~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1100Not implmented
     1101~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1102Test 18-ii.  Modifying Freds on YOURS
     1103~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1104Not implmented
     1105~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1106Test 18-iii.  Modifying Maries
     1107~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1108accessor_cases done
     1109try_pop cases done
     1110origin_mutation cases done
  • tests/list/dlist-insert-remove-2.cfa

    r4ab767a r8d1ad36  
    14321432}
    14331433
     1434
     1435////////////////////////////////////////////////////////////
     1436//
     1437// Section 4g
     1438//
     1439// Test cases of `isEmpty, `hasPrev, `hasNext,
     1440// try_pop_front, try_pop_back, modifications via `elems
     1441//
     1442// Example of call-side user code
     1443//
     1444////////////////////////////////////////////////////////////
     1445
     1446void test__accessor_cases__mary() {
     1447
     1448        mary m1 = {1.7};
     1449        mary m2 = {2.7};
     1450        mary m3 = {3.7};
     1451
     1452        dlist(mary, mary) ml;   assert( ml`isEmpty);
     1453
     1454        insert_last(ml, m1);    assert(!ml`isEmpty);
     1455        insert_last(ml, m2);    assert(!ml`isEmpty);
     1456        insert_last(ml, m3);    assert(!ml`isEmpty);
     1457
     1458        mary & m1prev = m1`prev;
     1459        mary & m1next = m1`next;
     1460        mary & m2prev = m2`prev;
     1461        mary & m2next = m2`next;
     1462        mary & m3prev = m3`prev;
     1463        mary & m3next = m3`next;
     1464
     1465        assert (&m1prev == 0p);
     1466        assert (&m1next == &m2);
     1467        assert (&m2prev == &m1);
     1468        assert (&m2next == &m3);
     1469        assert (&m3prev == &m2);
     1470        assert (&m3next == 0p);
     1471
     1472        assert(!m1`hasPrev);
     1473        assert( m1`hasNext);
     1474        assert( m2`hasPrev);
     1475        assert( m2`hasNext);
     1476        assert( m3`hasPrev);
     1477        assert(!m3`hasNext);
     1478
     1479        printf("accessor_cases done\n");
     1480}
     1481
     1482void test__try_pop__mary() {
     1483
     1484        mary m1 = {1.7};
     1485        mary m2 = {2.7};
     1486        mary m3 = {3.7};
     1487
     1488        dlist(mary, mary) ml;
     1489
     1490        mary &m1r = *0p;
     1491        mary &m2r = *0p;
     1492        mary &m3r = *0p;
     1493        mary &mxr = *0p;
     1494
     1495        // queue, back to front
     1496
     1497        assert( ml`isEmpty);
     1498
     1499        insert_last(ml, m1);
     1500        insert_last(ml, m2);
     1501        insert_last(ml, m3);
     1502
     1503        &m1r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1504        &m2r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1505        &m3r = & try_pop_front(ml);     assert( ml`isEmpty);
     1506        &mxr = & try_pop_front(ml);     assert( ml`isEmpty);
     1507
     1508        assert( &m1r == &m1 );
     1509        assert( &m2r == &m2 );
     1510        assert( &m3r == &m3 );
     1511        assert( &mxr == 0p  );
     1512
     1513        &m1r = 0p;
     1514        &m2r = 0p;
     1515        &m3r = 0p;
     1516
     1517        // queue, front to back
     1518
     1519        assert( ml`isEmpty);
     1520
     1521        insert_first(ml, m1);
     1522        insert_first(ml, m2);
     1523        insert_first(ml, m3);
     1524
     1525        &m1r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1526        &m2r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1527        &m3r = & try_pop_back(ml);      assert( ml`isEmpty);
     1528        &mxr = & try_pop_back(ml);      assert( ml`isEmpty);
     1529
     1530        assert( &m1r == &m1 );
     1531        assert( &m2r == &m2 );
     1532        assert( &m3r == &m3 );
     1533        assert( &mxr == 0p  );
     1534
     1535        &m1r = 0p;
     1536        &m2r = 0p;
     1537        &m3r = 0p;
     1538
     1539        // stack at front
     1540
     1541        assert( ml`isEmpty);
     1542
     1543        insert_first(ml, m1);
     1544        insert_first(ml, m2);
     1545        insert_first(ml, m3);
     1546
     1547        &m3r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1548        &m2r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1549        &m1r = & try_pop_front(ml);     assert( ml`isEmpty);
     1550        &mxr = & try_pop_front(ml);     assert( ml`isEmpty);
     1551
     1552        assert( &m1r == &m1 );
     1553        assert( &m2r == &m2 );
     1554        assert( &m3r == &m3 );
     1555        assert( &mxr == 0p  );
     1556
     1557        &m1r = 0p;
     1558        &m2r = 0p;
     1559        &m3r = 0p;
     1560
     1561        // stack at back
     1562
     1563        assert( ml`isEmpty);
     1564
     1565        insert_last(ml, m1);
     1566        insert_last(ml, m2);
     1567        insert_last(ml, m3);
     1568
     1569        &m3r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1570        &m2r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1571        &m1r = & try_pop_back(ml);      assert( ml`isEmpty);
     1572        &mxr = & try_pop_back(ml);      assert( ml`isEmpty);
     1573
     1574        assert( &m1r == &m1 );
     1575        assert( &m2r == &m2 );
     1576        assert( &m3r == &m3 );
     1577        assert( &mxr == 0p  );
     1578
     1579        &m1r = 0p;
     1580        &m2r = 0p;
     1581        &m3r = 0p;
     1582
     1583        printf("try_pop cases done\n");
     1584}
     1585
     1586void test__origin_mutation__mary() {
     1587
     1588        mary m1 = {1.7};
     1589
     1590        dlist(mary, mary) ml;
     1591        mary & mlorigin = ml`elems;
     1592
     1593        // insert before the origin
     1594
     1595        insert_before( ml`elems, m1 );
     1596        assert( ! ml`isEmpty );
     1597
     1598        mary & mlfirst = ml`first;
     1599        mary & mllast = ml`last;
     1600
     1601        assert( &m1 == & mlfirst );
     1602        assert( &m1 == & mllast );
     1603
     1604        // moveNext after last goes back to origin, &vv
     1605
     1606        bool canMoveNext = mllast`moveNext;
     1607        bool canMovePrev = mlfirst`movePrev;
     1608
     1609        assert( ! canMoveNext );
     1610        assert( ! canMovePrev );
     1611
     1612        assert( &mlorigin == & mlfirst );
     1613        assert( &mlorigin == & mllast );
     1614
     1615        printf("origin_mutation cases done\n");
     1616}
     1617
    14341618////////////////////////////////////////////////////////////
    14351619//
     
    17081892        test__pop_last__maries();
    17091893
     1894        sout | "";
     1895        sout | "~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~";
     1896        sout | "";
     1897
     1898        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1899        sout | "Test 18-i.  Modifying Freds on MINE";
     1900        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1901        sout | "Not implmented";
     1902
     1903        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1904        sout | "Test 18-ii.  Modifying Freds on YOURS";
     1905        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1906        sout | "Not implmented";
     1907
     1908        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1909        sout | "Test 18-iii.  Modifying Maries";
     1910        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1911
     1912        test__accessor_cases__mary();
     1913        test__try_pop__mary();
     1914        test__origin_mutation__mary();
     1915
    17101916        return 0;
    17111917}
Note: See TracChangeset for help on using the changeset viewer.