Mercurial > hg
comparison mercurial/parsers.c @ 21102:4eb6553789e1
parsers: introduce index_commonancestorsheads
This is an exact copy of index_ancestors but without the final "deepest"
pruning.
author | Mads Kiilerich <madski@unity3d.com> |
---|---|
date | Mon, 24 Feb 2014 22:42:14 +0100 |
parents | e286ab22e461 |
children | 628c16489d1c |
comparison
equal
deleted
inserted
replaced
21101:64911a12dc28 | 21102:4eb6553789e1 |
---|---|
1542 Py_XDECREF(ret); | 1542 Py_XDECREF(ret); |
1543 return NULL; | 1543 return NULL; |
1544 } | 1544 } |
1545 | 1545 |
1546 /* | 1546 /* |
1547 * Given a (possibly overlapping) set of revs, return all the | |
1548 * common ancestors heads: heads(::args[0] and ::a[1] and ...) | |
1549 */ | |
1550 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args) | |
1551 { | |
1552 PyObject *ret = NULL, *gca = NULL; | |
1553 Py_ssize_t argcount, i, len; | |
1554 bitmask repeat = 0; | |
1555 int revcount = 0; | |
1556 int *revs; | |
1557 | |
1558 argcount = PySequence_Length(args); | |
1559 revs = malloc(argcount * sizeof(*revs)); | |
1560 if (argcount > 0 && revs == NULL) | |
1561 return PyErr_NoMemory(); | |
1562 len = index_length(self) - 1; | |
1563 | |
1564 for (i = 0; i < argcount; i++) { | |
1565 static const int capacity = 24; | |
1566 PyObject *obj = PySequence_GetItem(args, i); | |
1567 bitmask x; | |
1568 long val; | |
1569 | |
1570 if (!PyInt_Check(obj)) { | |
1571 PyErr_SetString(PyExc_TypeError, | |
1572 "arguments must all be ints"); | |
1573 goto bail; | |
1574 } | |
1575 val = PyInt_AsLong(obj); | |
1576 if (val == -1) { | |
1577 ret = PyList_New(0); | |
1578 goto done; | |
1579 } | |
1580 if (val < 0 || val >= len) { | |
1581 PyErr_SetString(PyExc_IndexError, | |
1582 "index out of range"); | |
1583 goto bail; | |
1584 } | |
1585 /* this cheesy bloom filter lets us avoid some more | |
1586 * expensive duplicate checks in the common set-is-disjoint | |
1587 * case */ | |
1588 x = 1ull << (val & 0x3f); | |
1589 if (repeat & x) { | |
1590 int k; | |
1591 for (k = 0; k < revcount; k++) { | |
1592 if (val == revs[k]) | |
1593 goto duplicate; | |
1594 } | |
1595 } | |
1596 else repeat |= x; | |
1597 if (revcount >= capacity) { | |
1598 PyErr_Format(PyExc_OverflowError, | |
1599 "bitset size (%d) > capacity (%d)", | |
1600 revcount, capacity); | |
1601 goto bail; | |
1602 } | |
1603 revs[revcount++] = (int)val; | |
1604 duplicate:; | |
1605 } | |
1606 | |
1607 if (revcount == 0) { | |
1608 ret = PyList_New(0); | |
1609 goto done; | |
1610 } | |
1611 if (revcount == 1) { | |
1612 PyObject *obj; | |
1613 ret = PyList_New(1); | |
1614 if (ret == NULL) | |
1615 goto bail; | |
1616 obj = PyInt_FromLong(revs[0]); | |
1617 if (obj == NULL) | |
1618 goto bail; | |
1619 PyList_SET_ITEM(ret, 0, obj); | |
1620 goto done; | |
1621 } | |
1622 | |
1623 gca = find_gca_candidates(self, revs, revcount); | |
1624 if (gca == NULL) | |
1625 goto bail; | |
1626 | |
1627 ret = gca; | |
1628 Py_INCREF(gca); | |
1629 | |
1630 done: | |
1631 free(revs); | |
1632 Py_XDECREF(gca); | |
1633 | |
1634 return ret; | |
1635 | |
1636 bail: | |
1637 free(revs); | |
1638 Py_XDECREF(gca); | |
1639 Py_XDECREF(ret); | |
1640 return NULL; | |
1641 } | |
1642 | |
1643 /* | |
1547 * Invalidate any trie entries introduced by added revs. | 1644 * Invalidate any trie entries introduced by added revs. |
1548 */ | 1645 */ |
1549 static void nt_invalidate_added(indexObject *self, Py_ssize_t start) | 1646 static void nt_invalidate_added(indexObject *self, Py_ssize_t start) |
1550 { | 1647 { |
1551 Py_ssize_t i, len = PyList_GET_SIZE(self->added); | 1648 Py_ssize_t i, len = PyList_GET_SIZE(self->added); |
1785 }; | 1882 }; |
1786 | 1883 |
1787 static PyMethodDef index_methods[] = { | 1884 static PyMethodDef index_methods[] = { |
1788 {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS, | 1885 {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS, |
1789 "return the gca set of the given revs"}, | 1886 "return the gca set of the given revs"}, |
1887 {"commonancestorsheads", (PyCFunction)index_commonancestorsheads, | |
1888 METH_VARARGS, | |
1889 "return the heads of the common ancestors of the given revs"}, | |
1790 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS, | 1890 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS, |
1791 "clear the index caches"}, | 1891 "clear the index caches"}, |
1792 {"get", (PyCFunction)index_m_get, METH_VARARGS, | 1892 {"get", (PyCFunction)index_m_get, METH_VARARGS, |
1793 "get an index entry"}, | 1893 "get an index entry"}, |
1794 {"headrevs", (PyCFunction)index_headrevs, METH_NOARGS, | 1894 {"headrevs", (PyCFunction)index_headrevs, METH_NOARGS, |