Changeset f2d05e9


Ignore:
Timestamp:
May 12, 2020, 7:16:49 PM (16 months ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast, new-ast-unique-expr
Children:
8d462e5
Parents:
70ac8d0
Message:

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

Files:
3 edited

Legend:

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

    r70ac8d0 rf2d05e9  
    301301                $prev_link(list_pos) = (Telem*) 0p;
    302302        }
     303
     304        static inline bool ?`is_empty(dlist(Tnode, Telem) &list) {
     305                assert( &list != 0p );
     306                $dlinks(Telem) *listLinks = & list.$links;
     307                if (listLinks->next.is_terminator) {
     308                        assert(listLinks->prev.is_terminator);
     309                        assert(listLinks->next.terminator);
     310                        assert(listLinks->prev.terminator);
     311                        return true;
     312                } else {
     313                        assert(!listLinks->prev.is_terminator);
     314                        assert(listLinks->next.elem);
     315                        assert(listLinks->prev.elem);
     316                        return false;
     317                }
     318        }
     319
     320        static inline Telem & pop_first(dlist(Tnode, Telem) &list) {
     321                assert( &list != 0p );
     322                assert( !list`is_empty );
     323                $dlinks(Telem) *listLinks = & list.$links;
     324                Telem & first = *listLinks->next.elem;
     325                Tnode & list_pos_first  = $tempcv_e2n( first );
     326                remove(list_pos_first);
     327                return first;
     328        }
     329
     330        static inline Telem & pop_last(dlist(Tnode, Telem) &list) {
     331                assert( &list != 0p );
     332                assert( !list`is_empty );
     333                $dlinks(Telem) *listLinks = & list.$links;
     334                Telem & last = *listLinks->prev.elem;
     335                Tnode & list_pos_last  = $tempcv_e2n( last );
     336                remove(list_pos_last);
     337                return last;
     338        }
     339
    303340}
    304341
  • tests/list/.expect/dlist-insert-remove.txt

    r70ac8d0 rf2d05e9  
    146414640.7
    14651465-
     1466
     1467~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~
     1468
     1469~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1470Test 16-i.  Modifying Freds on MINE
     1471~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1472==== fred by MINE before
     14731.7
     14742.7
     14753.7
     1476-
     14771.7
     1478-
     14793.7
     1480-
     14813.7
     14822.7
     14831.7
     1484-
     1485==== fred by YOURS before
     14861.7
     14872.7
     14883.7
     1489-
     14901.7
     1491-
     14923.7
     1493-
     14943.7
     14952.7
     14961.7
     1497-
     1498==== fred by MINE after
     14992.7
     15003.7
     1501-
     15022.7
     1503-
     15043.7
     1505-
     15063.7
     15072.7
     1508-
     1509==== fred by YOURS after
     15101.7
     15112.7
     15123.7
     1513-
     15141.7
     1515-
     15163.7
     1517-
     15183.7
     15192.7
     15201.7
     1521-
     1522==== fred by MINE after
     15231.7
     1524-
     15251.7
     1526-
     1527-
     1528-
     1529~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1530Test 16-ii.  Modifying Freds on YOURS
     1531~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1532==== fred by MINE before
     15331.7
     15342.7
     15353.7
     1536-
     15371.7
     1538-
     15393.7
     1540-
     15413.7
     15422.7
     15431.7
     1544-
     1545==== fred by YOURS before
     15461.7
     15472.7
     15483.7
     1549-
     15501.7
     1551-
     15523.7
     1553-
     15543.7
     15552.7
     15561.7
     1557-
     1558==== fred by MINE after
     15591.7
     15602.7
     15613.7
     1562-
     15631.7
     1564-
     15653.7
     1566-
     15673.7
     15682.7
     15691.7
     1570-
     1571==== fred by YOURS after
     15722.7
     15733.7
     1574-
     15752.7
     1576-
     15773.7
     1578-
     15793.7
     15802.7
     1581-
     1582==== fred by YOURS after
     15831.7
     1584-
     15851.7
     1586-
     1587-
     1588-
     1589~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1590Test 16-iii.  Modifying Maries
     1591~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1592==== mary before
     15931.7
     15942.7
     15953.7
     1596-
     15971.7
     1598-
     15993.7
     1600-
     16013.7
     16022.7
     16031.7
     1604-
     1605==== mary after
     16062.7
     16073.7
     1608-
     16092.7
     1610-
     16113.7
     1612-
     16133.7
     16142.7
     1615-
     1616==== mary after
     16171.7
     1618-
     16191.7
     1620-
     1621-
     1622-
     1623
     1624~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~
     1625
     1626~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1627Test 17-i.  Modifying Freds on MINE
     1628~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1629==== fred by MINE before
     16301.7
     16312.7
     16323.7
     1633-
     16341.7
     1635-
     16363.7
     1637-
     16383.7
     16392.7
     16401.7
     1641-
     1642==== fred by YOURS before
     16431.7
     16442.7
     16453.7
     1646-
     16471.7
     1648-
     16493.7
     1650-
     16513.7
     16522.7
     16531.7
     1654-
     1655==== fred by MINE after
     16561.7
     16572.7
     1658-
     16591.7
     1660-
     16612.7
     1662-
     16632.7
     16641.7
     1665-
     1666==== fred by YOURS after
     16671.7
     16682.7
     16693.7
     1670-
     16711.7
     1672-
     16733.7
     1674-
     16753.7
     16762.7
     16771.7
     1678-
     1679==== fred by MINE after
     16803.7
     1681-
     16823.7
     1683-
     1684-
     1685-
     1686~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1687Test 17-ii.  Modifying Freds on YOURS
     1688~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1689==== fred by MINE before
     16901.7
     16912.7
     16923.7
     1693-
     16941.7
     1695-
     16963.7
     1697-
     16983.7
     16992.7
     17001.7
     1701-
     1702==== fred by YOURS before
     17031.7
     17042.7
     17053.7
     1706-
     17071.7
     1708-
     17093.7
     1710-
     17113.7
     17122.7
     17131.7
     1714-
     1715==== fred by MINE after
     17161.7
     17172.7
     17183.7
     1719-
     17201.7
     1721-
     17223.7
     1723-
     17243.7
     17252.7
     17261.7
     1727-
     1728==== fred by YOURS after
     17291.7
     17302.7
     1731-
     17321.7
     1733-
     17342.7
     1735-
     17362.7
     17371.7
     1738-
     1739==== fred by YOURS after
     17403.7
     1741-
     17423.7
     1743-
     1744-
     1745-
     1746~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1747Test 17-iii.  Modifying Maries
     1748~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1749==== mary before
     17501.7
     17512.7
     17523.7
     1753-
     17541.7
     1755-
     17563.7
     1757-
     17583.7
     17592.7
     17601.7
     1761-
     1762==== mary after
     17631.7
     17642.7
     1765-
     17661.7
     1767-
     17682.7
     1769-
     17702.7
     17711.7
     1772-
     1773==== mary after
     17743.7
     1775-
     17763.7
     1777-
     1778-
     1779-
  • tests/list/dlist-insert-remove.cfa

    r70ac8d0 rf2d05e9  
    11871187////////////////////////////////////////////////////////////
    11881188//
     1189// Section 4f
     1190//
     1191// Test cases of pop_first, pop_last
     1192//
     1193// Example of call-side user code
     1194//
     1195////////////////////////////////////////////////////////////
     1196
     1197// These cases assume element removal at first-last is correct
     1198
     1199void test__pop_first__fred_mine() {
     1200
     1201        fred f1 = {1.7};
     1202        fred f2 = {2.7};
     1203        fred f3 = {3.7};
     1204
     1205        dlist(fred_in_mine, fred) flm;
     1206        insert_last(flm, f1);
     1207        insert_last(flm, f2);
     1208        insert_last(flm, f3);
     1209
     1210        dlist(fred_in_yours, fred) fly;
     1211        insert_last(fly, f1);
     1212        insert_last(fly, f2);
     1213        insert_last(fly, f3);
     1214
     1215        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1216        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1217
     1218        verify(validate(fly));
     1219        verify(validate(flm));
     1220
     1221        fred & popped = pop_first(flm);
     1222
     1223        verify(validate(fly));
     1224        verify(validate(flm));
     1225
     1226        printMyFreddies(flm`first, flm`last, 0);     // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
     1227        printYourFreddies(fly`first, fly`last, 0);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
     1228
     1229        // observe f1 is now solo in mine; in yours, it was just traversed
     1230        printMyFreddies(f1, *0p, 0);    // 1.7; 1.7; ;
     1231
     1232        assert( &popped == & f1 );
     1233}
     1234
     1235void test__pop_first__fred_yours() {
     1236
     1237        fred f1 = {1.7};
     1238        fred f2 = {2.7};
     1239        fred f3 = {3.7};
     1240
     1241        dlist(fred_in_mine, fred) flm;
     1242        insert_last(flm, f1);
     1243        insert_last(flm, f2);
     1244        insert_last(flm, f3);
     1245
     1246        dlist(fred_in_yours, fred) fly;
     1247        insert_last(fly, f1);
     1248        insert_last(fly, f2);
     1249        insert_last(fly, f3);
     1250
     1251        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1252        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1253
     1254        verify(validate(fly));
     1255        verify(validate(flm));
     1256
     1257        fred & popped = pop_first(fly);
     1258
     1259        verify(validate(fly));
     1260        verify(validate(flm));
     1261
     1262        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
     1263        printYourFreddies(fly`first, fly`last, 0);   // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
     1264
     1265        // observe f1 is now solo in yours; in mine, it was just traversed
     1266        printYourFreddies(f1, *0p, 0);    // 1.7; 1.7; ;
     1267
     1268        assert( &popped == &f1 );
     1269}
     1270
     1271void test__pop_first__maries() {
     1272
     1273        mary m1 = {1.7};
     1274        mary m2 = {2.7};
     1275        mary m3 = {3.7};
     1276
     1277        dlist(mary, mary) ml;
     1278        insert_last(ml, m1);
     1279        insert_last(ml, m2);
     1280        insert_last(ml, m3);
     1281
     1282        printMariatheotokos(ml`first, ml`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1283
     1284        verify(validate(ml));
     1285
     1286        mary & popped = pop_first(ml);
     1287
     1288        verify(validate(ml));
     1289
     1290        printMariatheotokos(ml`first, ml`last, 0);     // 2.7, 3.7;       2.7;  3.7;  3.7, 2.7      (modified)
     1291
     1292        // observe m1 is now solo
     1293        printMariatheotokos(m1, *0p, 0);               // 1.7; 1.7; ;
     1294
     1295        assert( &popped == &m1 );
     1296}
     1297
     1298void test__pop_last__fred_mine() {
     1299
     1300        fred f1 = {1.7};
     1301        fred f2 = {2.7};
     1302        fred f3 = {3.7};
     1303
     1304        dlist(fred_in_mine, fred) flm;
     1305        insert_last(flm, f1);
     1306        insert_last(flm, f2);
     1307        insert_last(flm, f3);
     1308
     1309        dlist(fred_in_yours, fred) fly;
     1310        insert_last(fly, f1);
     1311        insert_last(fly, f2);
     1312        insert_last(fly, f3);
     1313
     1314        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1315        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1316
     1317        verify(validate(fly));
     1318        verify(validate(flm));
     1319
     1320        fred & popped = pop_last(flm);
     1321
     1322        verify(validate(fly));
     1323        verify(validate(flm));
     1324
     1325        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7;       1.7;  2.7;  2.7, 1.7      (modified)
     1326        printYourFreddies(fly`first, fly`last, 0);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
     1327
     1328        // observe f3 is now solo in mine; in yours, it was just traversed
     1329        printMyFreddies(f3, *0p, 0);    // 3.7; 3.7; ;
     1330
     1331        assert( &popped == & f3 );
     1332}
     1333
     1334void test__pop_last__fred_yours() {
     1335
     1336        fred f1 = {1.7};
     1337        fred f2 = {2.7};
     1338        fred f3 = {3.7};
     1339
     1340        dlist(fred_in_mine, fred) flm;
     1341        insert_last(flm, f1);
     1342        insert_last(flm, f2);
     1343        insert_last(flm, f3);
     1344
     1345        dlist(fred_in_yours, fred) fly;
     1346        insert_last(fly, f1);
     1347        insert_last(fly, f2);
     1348        insert_last(fly, f3);
     1349
     1350        printMyFreddies(flm`first, flm`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1351        printYourFreddies(fly`first, fly`last, 1);   // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1352
     1353        verify(validate(fly));
     1354        verify(validate(flm));
     1355
     1356        fred & popped = pop_last(fly);
     1357
     1358        verify(validate(fly));
     1359        verify(validate(flm));
     1360
     1361        printMyFreddies(flm`first, flm`last, 0);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7 (unmodified)
     1362        printYourFreddies(fly`first, fly`last, 0);   // 1.7, 2.7;       1.7;  2.7;  2.7, 1.7      (modified)
     1363
     1364        // observe f3 is now solo in yours; in mine, it was just traversed
     1365        printYourFreddies(f3, *0p, 0);    // 3.7; 3.7; ;
     1366
     1367        assert( &popped == & f3 );
     1368}
     1369
     1370void test__pop_last__maries() {
     1371
     1372        mary m1 = {1.7};
     1373        mary m2 = {2.7};
     1374        mary m3 = {3.7};
     1375
     1376        dlist(mary, mary) ml;
     1377        insert_last(ml, m1);
     1378        insert_last(ml, m2);
     1379        insert_last(ml, m3);
     1380
     1381        printMariatheotokos(ml`first, ml`last, 1);     // 1.7, 2.7, 3.7;  1.7;  3.7;  3.7, 2.7, 1.7
     1382
     1383        verify(validate(ml));
     1384
     1385        mary & popped = pop_last(ml);
     1386
     1387        verify(validate(ml));
     1388
     1389        printMariatheotokos(ml`first, ml`last, 0);     // 1.7, 1.7;       1.7;  2.7;  2.7, 1.7      (modified)
     1390
     1391        // observe m1 is now solo
     1392        printMariatheotokos(m3, *0p, 0);               // 3.7; 3.7; ;
     1393
     1394        assert( &popped == &m3 );
     1395}
     1396
     1397////////////////////////////////////////////////////////////
     1398//
    11891399// Section 5
    11901400//
     
    14221632        test__remove_of_sole__mary();
    14231633
     1634        sout | "";
     1635        sout | "~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~";
     1636        sout | "";
     1637
     1638        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1639        sout | "Test 16-i.  Modifying Freds on MINE";
     1640        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1641        test__pop_first__fred_mine();
     1642
     1643        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1644        sout | "Test 16-ii.  Modifying Freds on YOURS";
     1645        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1646        test__pop_first__fred_yours();
     1647
     1648        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1649        sout | "Test 16-iii.  Modifying Maries";
     1650        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1651        test__pop_first__maries();
     1652
     1653        sout | "";
     1654        sout | "~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~";
     1655        sout | "";
     1656
     1657        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1658        sout | "Test 17-i.  Modifying Freds on MINE";
     1659        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1660        test__pop_last__fred_mine();
     1661
     1662        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1663        sout | "Test 17-ii.  Modifying Freds on YOURS";
     1664        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1665        test__pop_last__fred_yours();
     1666
     1667        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1668        sout | "Test 17-iii.  Modifying Maries";
     1669        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1670        test__pop_last__maries();
     1671
    14241672        return 0;
    14251673}
Note: See TracChangeset for help on using the changeset viewer.