Left: | ||
Right: |
LEFT | RIGHT |
---|---|
1 /* List object implementation */ | 1 /* List object implementation */ |
2 | 2 |
3 #include "Python.h" | 3 #include "Python.h" |
4 | 4 |
5 #ifdef STDC_HEADERS | 5 #ifdef STDC_HEADERS |
6 #include <stddef.h> | 6 #include <stddef.h> |
7 #else | 7 #else |
8 #include <sys/types.h> /* For size_t */ | 8 #include <sys/types.h> /* For size_t */ |
9 #endif | 9 #endif |
10 | 10 |
(...skipping 1424 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1435 if (ms->a.values != NULL) | 1435 if (ms->a.values != NULL) |
1436 ms->a.values = &ms->a.keys[need]; | 1436 ms->a.values = &ms->a.keys[need]; |
1437 return 0; | 1437 return 0; |
1438 } | 1438 } |
1439 PyErr_NoMemory(); | 1439 PyErr_NoMemory(); |
1440 return -1; | 1440 return -1; |
1441 } | 1441 } |
1442 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ | 1442 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ |
1443 merge_getmem(MS, NEED)) | 1443 merge_getmem(MS, NEED)) |
1444 | 1444 |
1445 /* Merge the na elements starting at pa with the nb elements starting at pb | 1445 /* Merge the na elements starting at ssa with the nb elements starting at |
1446 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | 1446 * ssb = ssa + na in a stable way, in-place. na and nb must be > 0. Must |
1447 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | 1447 * also have that pa[na-1] belongs at the end of the merge, and should have |
Antoine Pitrou
2010/11/23 21:44:06
What is "pa" here?
| |
1448 * merge, and should have na <= nb. See listsort.txt for more info. | 1448 * na <= nb. See listsort.txt for more info. Return 0 if successful, |
1449 * Return 0 if successful, -1 if error. | 1449 * -1 if error. |
1450 */ | 1450 */ |
1451 static Py_ssize_t | 1451 static Py_ssize_t |
1452 merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na, Py_ssize_t nb) | 1452 merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na, Py_ssize_t nb) |
1453 { | 1453 { |
1454 Py_ssize_t k; | 1454 Py_ssize_t k; |
1455 sortslice dest, ssb; | 1455 sortslice dest, ssb; |
1456 int result = -1; /* guilty until proved innocent */ | 1456 int result = -1; /* guilty until proved innocent */ |
1457 Py_ssize_t min_gallop; | 1457 Py_ssize_t min_gallop; |
1458 | 1458 |
1459 assert(ms && ssa.keys && na > 0 && nb > 0); | 1459 assert(ms && ssa.keys && na > 0 && nb > 0); |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1495 } else { | 1495 } else { |
1496 sortslice_copy_incr(&dest, &ssa); | 1496 sortslice_copy_incr(&dest, &ssa); |
1497 if (--na == 1) | 1497 if (--na == 1) |
1498 goto CopyB; | 1498 goto CopyB; |
1499 if (++acount >= min_gallop) | 1499 if (++acount >= min_gallop) |
1500 break; | 1500 break; |
1501 bcount = 0; | 1501 bcount = 0; |
1502 } | 1502 } |
1503 } | 1503 } |
1504 | 1504 |
1505 /* One run is winning so consistently that galloping may | 1505 /* One run is winning so consistently that galloping may be a huge |
1506 * be a huge win. So try that, and continue galloping until | 1506 * win. So try that, and continue galloping until (if ever) neither |
1507 * (if ever) neither run appears to be winning consistently | 1507 * run appears to be winning consistently anymore. |
1508 * anymore. | |
1509 */ | 1508 */ |
1510 ++min_gallop; | 1509 ++min_gallop; |
1511 do { | 1510 do { |
1512 assert(na > 1 && nb > 0); | 1511 assert(na > 1 && nb > 0); |
1513 min_gallop -= min_gallop > 1; | 1512 min_gallop -= min_gallop > 1; |
1514 ms->min_gallop = min_gallop; | 1513 ms->min_gallop = min_gallop; |
1515 k = gallop_right(ssb.keys[0], ssa.keys, na, 0); | 1514 k = gallop_right(ssb.keys[0], ssa.keys, na, 0); |
1516 acount = k; | 1515 acount = k; |
1517 if (k) { | 1516 if (k) { |
1518 if (k < 0) | 1517 if (k < 0) |
1519 goto Fail; | 1518 goto Fail; |
1520 sortslice_memcpy(&dest, 0, &ssa, 0, k); | 1519 sortslice_memcpy(&dest, 0, &ssa, 0, k); |
1521 sortslice_advance(&dest, k); | 1520 sortslice_advance(&dest, k); |
1522 sortslice_advance(&ssa, k); | 1521 sortslice_advance(&ssa, k); |
1523 na -= k; | 1522 na -= k; |
1524 if (na == 1) | 1523 if (na == 1) |
1525 goto CopyB; | 1524 goto CopyB; |
1526 /* na==0 is impossible now if the comparison | 1525 /* na==0 is impossible now if the comparison function is |
1527 * function is consistent, but we can't assume | 1526 * consistent, but we can't assume that it is. |
1528 * that it is. | |
1529 */ | 1527 */ |
1530 if (na == 0) | 1528 if (na == 0) |
1531 goto Succeed; | 1529 goto Succeed; |
1532 } | 1530 } |
1533 sortslice_copy_incr(&dest, &ssb); | 1531 sortslice_copy_incr(&dest, &ssb); |
1534 --nb; | 1532 --nb; |
1535 if (nb == 0) | 1533 if (nb == 0) |
1536 goto Succeed; | 1534 goto Succeed; |
1537 | 1535 |
1538 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0); | 1536 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0); |
(...skipping 17 matching lines...) Expand all Loading... | |
1556 ms->min_gallop = min_gallop; | 1554 ms->min_gallop = min_gallop; |
1557 } | 1555 } |
1558 Succeed: | 1556 Succeed: |
1559 result = 0; | 1557 result = 0; |
1560 Fail: | 1558 Fail: |
1561 if (na) | 1559 if (na) |
1562 sortslice_memcpy(&dest, 0, &ssa, 0, na); | 1560 sortslice_memcpy(&dest, 0, &ssa, 0, na); |
1563 return result; | 1561 return result; |
1564 CopyB: | 1562 CopyB: |
1565 assert(na == 1 && nb > 0); | 1563 assert(na == 1 && nb > 0); |
1566 /* The last element of pa belongs at the end of the merge. */ | 1564 /* The last element of ssa belongs at the end of the merge. */ |
1567 sortslice_memmove(&dest, 0, &ssb, 0, nb); | 1565 sortslice_memmove(&dest, 0, &ssb, 0, nb); |
1568 sortslice_copy(&dest, nb, &ssa, 0); | 1566 sortslice_copy(&dest, nb, &ssa, 0); |
1569 return 0; | 1567 return 0; |
1570 } | 1568 } |
1571 | 1569 |
1572 /* Merge the na elements starting at pa with the nb elements starting at pb | 1570 /* Merge the na elements starting at pa with the nb elements starting at |
1573 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | 1571 * ssb = ssa + na in a stable way, in-place. na and nb must be > 0. |
1574 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | 1572 * Must also have that pa[na-1] belongs at the end of the merge, and |
Antoine Pitrou
2010/11/23 21:44:06
Again, what is "pa"?
| |
1575 * merge, and should have na >= nb. See listsort.txt for more info. | 1573 * should have na >= nb. See listsort.txt for more info. Return 0 if |
1576 * Return 0 if successful, -1 if error. | 1574 * successful, -1 if error. |
1577 */ | 1575 */ |
1578 static Py_ssize_t | 1576 static Py_ssize_t |
1579 merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na, Py_ssize_t nb) | 1577 merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na, Py_ssize_t nb) |
1580 { | 1578 { |
1581 Py_ssize_t k; | 1579 Py_ssize_t k; |
1582 sortslice dest, ssb; | 1580 sortslice dest, ssb; |
1583 int result = -1; /* guilty until proved innocent */ | 1581 int result = -1; /* guilty until proved innocent */ |
1584 Py_ssize_t min_gallop; | 1582 Py_ssize_t min_gallop; |
1585 | 1583 |
1586 assert(ms && ssa.keys && na > 0 && nb > 0); | 1584 assert(ms && ssa.keys && na > 0 && nb > 0); |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1623 } else { | 1621 } else { |
1624 sortslice_copy_decr(&dest, &ssb); | 1622 sortslice_copy_decr(&dest, &ssb); |
1625 if (--nb == 1) | 1623 if (--nb == 1) |
1626 goto CopyA; | 1624 goto CopyA; |
1627 if (++bcount >= min_gallop) | 1625 if (++bcount >= min_gallop) |
1628 break; | 1626 break; |
1629 acount = 0; | 1627 acount = 0; |
1630 } | 1628 } |
1631 } | 1629 } |
1632 | 1630 |
1633 /* One run is winning so consistently that galloping may | 1631 /* One run is winning so consistently that galloping may be a huge |
1634 * be a huge win. So try that, and continue galloping until | 1632 * win. So try that, and continue galloping until (if ever) neither |
1635 * (if ever) neither run appears to be winning consistently | 1633 * run appears to be winning consistently anymore. |
1636 * anymore. | |
1637 */ | 1634 */ |
1638 ++min_gallop; | 1635 ++min_gallop; |
1639 do { | 1636 do { |
1640 assert(na > 0 && nb > 1); | 1637 assert(na > 0 && nb > 1); |
1641 min_gallop -= min_gallop > 1; | 1638 min_gallop -= min_gallop > 1; |
1642 ms->min_gallop = min_gallop; | 1639 ms->min_gallop = min_gallop; |
1643 k = gallop_right(ssb.keys[0], ssa.keys - (na - 1), na, na - 1); | 1640 k = gallop_right(ssb.keys[0], ssa.keys - (na - 1), na, na - 1); |
1644 if (k < 0) | 1641 if (k < 0) |
1645 goto Fail; | 1642 goto Fail; |
1646 k = na - k; | 1643 k = na - k; |
(...skipping 16 matching lines...) Expand all Loading... | |
1663 goto Fail; | 1660 goto Fail; |
1664 k = nb - k; | 1661 k = nb - k; |
1665 bcount = k; | 1662 bcount = k; |
1666 if (k) { | 1663 if (k) { |
1667 sortslice_advance(&dest, -k); | 1664 sortslice_advance(&dest, -k); |
1668 sortslice_advance(&ssb, -k); | 1665 sortslice_advance(&ssb, -k); |
1669 sortslice_memcpy(&dest, 1, &ssb, 1, k); | 1666 sortslice_memcpy(&dest, 1, &ssb, 1, k); |
1670 nb -= k; | 1667 nb -= k; |
1671 if (nb == 1) | 1668 if (nb == 1) |
1672 goto CopyA; | 1669 goto CopyA; |
1673 /* nb==0 is impossible now if the comparison | 1670 /* nb==0 is impossible now if the comparison function is |
1674 * function is consistent, but we can't assume | 1671 * consistent, but we can't assume that it is. |
1675 * that it is. | |
1676 */ | 1672 */ |
1677 if (nb == 0) | 1673 if (nb == 0) |
1678 goto Succeed; | 1674 goto Succeed; |
1679 } | 1675 } |
1680 sortslice_copy_decr(&dest, &ssa); | 1676 sortslice_copy_decr(&dest, &ssa); |
1681 --na; | 1677 --na; |
1682 if (na == 0) | 1678 if (na == 0) |
1683 goto Succeed; | 1679 goto Succeed; |
1684 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | 1680 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
1685 ++min_gallop; /* penalize it for leaving galloping mode */ | 1681 ++min_gallop; /* penalize it for leaving galloping mode */ |
1686 ms->min_gallop = min_gallop; | 1682 ms->min_gallop = min_gallop; |
1687 } | 1683 } |
1688 Succeed: | 1684 Succeed: |
1689 result = 0; | 1685 result = 0; |
1690 Fail: | 1686 Fail: |
1691 if (nb) | 1687 if (nb) |
1692 sortslice_memcpy(&dest, -(nb-1), &ms->a, 0, nb); | 1688 sortslice_memcpy(&dest, -(nb-1), &ms->a, 0, nb); |
1693 return result; | 1689 return result; |
1694 CopyA: | 1690 CopyA: |
1695 assert(nb == 1 && na > 0); | 1691 assert(nb == 1 && na > 0); |
1696 /* The first element of pb belongs at the front of the merge. */ | 1692 /* The first element of ssb belongs at the front of the merge. */ |
1697 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na); | 1693 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na); |
1698 sortslice_advance(&dest, -na); | 1694 sortslice_advance(&dest, -na); |
1699 sortslice_advance(&ssa, -na); | 1695 sortslice_advance(&ssa, -na); |
1700 sortslice_copy(&dest, 0, &ssb, 0); | 1696 sortslice_copy(&dest, 0, &ssb, 0); |
1701 return 0; | 1697 return 0; |
1702 } | 1698 } |
1703 | 1699 |
1704 /* Merge the two runs at stack indices i and i+1. | 1700 /* Merge the two runs at stack indices i and i+1. |
1705 * Returns 0 on success, -1 on error. | 1701 * Returns 0 on success, -1 on error. |
1706 */ | 1702 */ |
(...skipping 1143 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
2850 } | 2846 } |
2851 | 2847 |
2852 static PyObject * | 2848 static PyObject * |
2853 listreviter_len(listreviterobject *it) | 2849 listreviter_len(listreviterobject *it) |
2854 { | 2850 { |
2855 Py_ssize_t len = it->it_index + 1; | 2851 Py_ssize_t len = it->it_index + 1; |
2856 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) | 2852 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) |
2857 len = 0; | 2853 len = 0; |
2858 return PyLong_FromSsize_t(len); | 2854 return PyLong_FromSsize_t(len); |
2859 } | 2855 } |
LEFT | RIGHT |