Mercurial > hg
comparison mercurial/parsers.c @ 24004:8a5267cd5286
parsers: rewrite index_ancestors() in terms of index_commonancestorsheads()
The first 80% of index_ancestors() is identical to
index_commonancestorsheads(), so just call that function instead.
author | Martin von Zweigbergk <martinvonz@google.com> |
---|---|
date | Fri, 23 Jan 2015 14:09:49 -0800 |
parents | bd307b462ce2 |
children | 72c9b5ae7278 |
comparison
equal
deleted
inserted
replaced
24003:b95a5bb58653 | 24004:8a5267cd5286 |
---|---|
1674 | 1674 |
1675 return keys; | 1675 return keys; |
1676 } | 1676 } |
1677 | 1677 |
1678 /* | 1678 /* |
1679 * Given a (possibly overlapping) set of revs, return the greatest | 1679 * Given a (possibly overlapping) set of revs, return all the |
1680 * common ancestors: those with the longest path to the root. | 1680 * common ancestors heads: heads(::args[0] and ::a[1] and ...) |
1681 */ | 1681 */ |
1682 static PyObject *index_ancestors(indexObject *self, PyObject *args) | 1682 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args) |
1683 { | 1683 { |
1684 PyObject *ret = NULL, *gca = NULL; | 1684 PyObject *ret = NULL; |
1685 Py_ssize_t argcount, i, len; | 1685 Py_ssize_t argcount, i, len; |
1686 bitmask repeat = 0; | 1686 bitmask repeat = 0; |
1687 int revcount = 0; | 1687 int revcount = 0; |
1688 int *revs; | 1688 int *revs; |
1689 | 1689 |
1752 goto bail; | 1752 goto bail; |
1753 PyList_SET_ITEM(ret, 0, obj); | 1753 PyList_SET_ITEM(ret, 0, obj); |
1754 goto done; | 1754 goto done; |
1755 } | 1755 } |
1756 | 1756 |
1757 gca = find_gca_candidates(self, revs, revcount); | |
1758 if (gca == NULL) | |
1759 goto bail; | |
1760 | |
1761 if (PyList_GET_SIZE(gca) <= 1) { | |
1762 ret = gca; | |
1763 Py_INCREF(gca); | |
1764 } | |
1765 else ret = find_deepest(self, gca); | |
1766 | |
1767 done: | |
1768 free(revs); | |
1769 Py_XDECREF(gca); | |
1770 | |
1771 return ret; | |
1772 | |
1773 bail: | |
1774 free(revs); | |
1775 Py_XDECREF(gca); | |
1776 Py_XDECREF(ret); | |
1777 return NULL; | |
1778 } | |
1779 | |
1780 /* | |
1781 * Given a (possibly overlapping) set of revs, return all the | |
1782 * common ancestors heads: heads(::args[0] and ::a[1] and ...) | |
1783 */ | |
1784 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args) | |
1785 { | |
1786 PyObject *ret = NULL; | |
1787 Py_ssize_t argcount, i, len; | |
1788 bitmask repeat = 0; | |
1789 int revcount = 0; | |
1790 int *revs; | |
1791 | |
1792 argcount = PySequence_Length(args); | |
1793 revs = malloc(argcount * sizeof(*revs)); | |
1794 if (argcount > 0 && revs == NULL) | |
1795 return PyErr_NoMemory(); | |
1796 len = index_length(self) - 1; | |
1797 | |
1798 for (i = 0; i < argcount; i++) { | |
1799 static const int capacity = 24; | |
1800 PyObject *obj = PySequence_GetItem(args, i); | |
1801 bitmask x; | |
1802 long val; | |
1803 | |
1804 if (!PyInt_Check(obj)) { | |
1805 PyErr_SetString(PyExc_TypeError, | |
1806 "arguments must all be ints"); | |
1807 Py_DECREF(obj); | |
1808 goto bail; | |
1809 } | |
1810 val = PyInt_AsLong(obj); | |
1811 Py_DECREF(obj); | |
1812 if (val == -1) { | |
1813 ret = PyList_New(0); | |
1814 goto done; | |
1815 } | |
1816 if (val < 0 || val >= len) { | |
1817 PyErr_SetString(PyExc_IndexError, | |
1818 "index out of range"); | |
1819 goto bail; | |
1820 } | |
1821 /* this cheesy bloom filter lets us avoid some more | |
1822 * expensive duplicate checks in the common set-is-disjoint | |
1823 * case */ | |
1824 x = 1ull << (val & 0x3f); | |
1825 if (repeat & x) { | |
1826 int k; | |
1827 for (k = 0; k < revcount; k++) { | |
1828 if (val == revs[k]) | |
1829 goto duplicate; | |
1830 } | |
1831 } | |
1832 else repeat |= x; | |
1833 if (revcount >= capacity) { | |
1834 PyErr_Format(PyExc_OverflowError, | |
1835 "bitset size (%d) > capacity (%d)", | |
1836 revcount, capacity); | |
1837 goto bail; | |
1838 } | |
1839 revs[revcount++] = (int)val; | |
1840 duplicate:; | |
1841 } | |
1842 | |
1843 if (revcount == 0) { | |
1844 ret = PyList_New(0); | |
1845 goto done; | |
1846 } | |
1847 if (revcount == 1) { | |
1848 PyObject *obj; | |
1849 ret = PyList_New(1); | |
1850 if (ret == NULL) | |
1851 goto bail; | |
1852 obj = PyInt_FromLong(revs[0]); | |
1853 if (obj == NULL) | |
1854 goto bail; | |
1855 PyList_SET_ITEM(ret, 0, obj); | |
1856 goto done; | |
1857 } | |
1858 | |
1859 ret = find_gca_candidates(self, revs, revcount); | 1757 ret = find_gca_candidates(self, revs, revcount); |
1860 if (ret == NULL) | 1758 if (ret == NULL) |
1861 goto bail; | 1759 goto bail; |
1862 | 1760 |
1863 done: | 1761 done: |
1866 | 1764 |
1867 bail: | 1765 bail: |
1868 free(revs); | 1766 free(revs); |
1869 Py_XDECREF(ret); | 1767 Py_XDECREF(ret); |
1870 return NULL; | 1768 return NULL; |
1769 } | |
1770 | |
1771 /* | |
1772 * Given a (possibly overlapping) set of revs, return the greatest | |
1773 * common ancestors: those with the longest path to the root. | |
1774 */ | |
1775 static PyObject *index_ancestors(indexObject *self, PyObject *args) | |
1776 { | |
1777 PyObject *gca = index_commonancestorsheads(self, args); | |
1778 if (gca == NULL) | |
1779 return NULL; | |
1780 | |
1781 if (PyList_GET_SIZE(gca) <= 1) { | |
1782 Py_INCREF(gca); | |
1783 return gca; | |
1784 } | |
1785 | |
1786 return find_deepest(self, gca); | |
1871 } | 1787 } |
1872 | 1788 |
1873 /* | 1789 /* |
1874 * Invalidate any trie entries introduced by added revs. | 1790 * Invalidate any trie entries introduced by added revs. |
1875 */ | 1791 */ |