Comments
Patch
@@ -11,8 +11,8 @@ from node import nullrev
def ancestors(pfunc, *orignodes):
"""
- Returns the common ancestors of a and b that are furthest from a
- root (as measured by longest path).
+ Returns a set with the heads of all common ancestors of all orignodes,
+ heads(::orignodes[0] and ::orignodes[1] and ...) .
pfunc must return a list of parent vertices for a given vertex.
"""
@@ -67,67 +67,9 @@ def ancestors(pfunc, *orignodes):
seen[p] = sv
return gca
- def deepest(nodes):
- interesting = {}
- count = max(nodes) + 1
- depth = [0] * count
- seen = [0] * count
- mapping = []
- for (i, n) in enumerate(sorted(nodes)):
- depth[n] = 1
- b = 1 << i
- seen[n] = b
- interesting[b] = 1
- mapping.append((b, n))
- nv = count - 1
- while nv >= 0 and len(interesting) > 1:
- v = nv
- nv -= 1
- dv = depth[v]
- if dv == 0:
- continue
- sv = seen[v]
- for p in pfunc(v):
- if p == nullrev:
- continue
- dp = depth[p]
- nsp = sp = seen[p]
- if dp <= dv:
- depth[p] = dv + 1
- if sp != sv:
- interesting[sv] += 1
- nsp = seen[p] = sv
- if sp:
- interesting[sp] -= 1
- if interesting[sp] == 0:
- del interesting[sp]
- elif dv == dp - 1:
- nsp = sp | sv
- if nsp == sp:
- continue
- seen[p] = nsp
- interesting.setdefault(nsp, 0)
- interesting[nsp] += 1
- interesting[sp] -= 1
- if interesting[sp] == 0:
- del interesting[sp]
- interesting[sv] -= 1
- if interesting[sv] == 0:
- del interesting[sv]
-
- if len(interesting) != 1:
- return []
-
- k = 0
- for i in interesting:
- k |= i
- return set(n for (i, n) in mapping if k & i)
-
gca = candidates(orignodes)
- if len(gca) <= 1:
- return gca
- return deepest(gca)
+ return gca
def genericancestor(a, b, pfunc):
"""
@@ -1288,162 +1288,8 @@ bail:
}
/*
- * Given a disjoint set of revs, return the subset with the longest
- * path to the root.
- */
-static PyObject *find_deepest(indexObject *self, PyObject *revs)
-{
- const Py_ssize_t revcount = PyList_GET_SIZE(revs);
- static const Py_ssize_t capacity = 24;
- int *depth, *interesting = NULL;
- int i, j, v, ninteresting;
- PyObject *dict = NULL, *keys;
- long *seen = NULL;
- int maxrev = -1;
- long final;
-
- if (revcount > capacity) {
- PyErr_Format(PyExc_OverflowError,
- "bitset size (%ld) > capacity (%ld)",
- (long)revcount, (long)capacity);
- return NULL;
- }
-
- for (i = 0; i < revcount; i++) {
- int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
- if (n > maxrev)
- maxrev = n;
- }
-
- depth = calloc(sizeof(*depth), maxrev + 1);
- if (depth == NULL)
- return PyErr_NoMemory();
-
- seen = calloc(sizeof(*seen), maxrev + 1);
- if (seen == NULL) {
- PyErr_NoMemory();
- goto bail;
- }
-
- interesting = calloc(sizeof(*interesting), 2 << revcount);
- if (interesting == NULL) {
- PyErr_NoMemory();
- goto bail;
- }
-
- if (PyList_Sort(revs) == -1)
- goto bail;
-
- for (i = 0; i < revcount; i++) {
- int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
- long b = 1l << i;
- depth[n] = 1;
- seen[n] = b;
- interesting[b] = 1;
- }
-
- ninteresting = (int)revcount;
-
- for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
- int dv = depth[v];
- int parents[2];
- long sv;
-
- if (dv == 0)
- continue;
-
- sv = seen[v];
- index_get_parents(self, v, parents);
-
- for (i = 0; i < 2; i++) {
- int p = parents[i];
- long nsp, sp;
- int dp;
-
- if (p == -1)
- continue;
-
- dp = depth[p];
- nsp = sp = seen[p];
- if (dp <= dv) {
- depth[p] = dv + 1;
- if (sp != sv) {
- interesting[sv] += 1;
- nsp = seen[p] = sv;
- if (sp) {
- interesting[sp] -= 1;
- if (interesting[sp] == 0)
- ninteresting -= 1;
- }
- }
- }
- else if (dv == dp - 1) {
- nsp = sp | sv;
- if (nsp == sp)
- continue;
- seen[p] = nsp;
- interesting[sp] -= 1;
- if (interesting[sp] == 0 && interesting[nsp] > 0)
- ninteresting -= 1;
- interesting[nsp] += 1;
- }
- }
- interesting[sv] -= 1;
- if (interesting[sv] == 0)
- ninteresting -= 1;
- }
-
- final = 0;
- j = ninteresting;
- for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
- if (interesting[i] == 0)
- continue;
- final |= i;
- j -= 1;
- }
- if (final == 0)
- return PyList_New(0);
-
- dict = PyDict_New();
- if (dict == NULL)
- goto bail;
-
- for (i = 0; i < revcount; i++) {
- PyObject *key;
-
- if ((final & (1 << i)) == 0)
- continue;
-
- key = PyList_GET_ITEM(revs, i);
- Py_INCREF(key);
- Py_INCREF(Py_None);
- if (PyDict_SetItem(dict, key, Py_None) == -1) {
- Py_DECREF(key);
- Py_DECREF(Py_None);
- goto bail;
- }
- }
-
- keys = PyDict_Keys(dict);
-
- free(depth);
- free(seen);
- free(interesting);
- Py_DECREF(dict);
-
- return keys;
-bail:
- free(depth);
- free(seen);
- free(interesting);
- Py_XDECREF(dict);
-
- return NULL;
-}
-
-/*
- * Given a (possibly overlapping) set of revs, return the greatest
- * common ancestors: those with the longest path to the root.
+ * Given a (possibly overlapping) set of revs, return all the greatest
+ * common ancestors: heads(::a and ::b and ...)
*/
static PyObject *index_ancestors(indexObject *self, PyObject *args)
{
@@ -1522,11 +1368,8 @@ static PyObject *index_ancestors(indexOb
if (gca == NULL)
goto bail;
- if (PyList_GET_SIZE(gca) <= 1) {
- ret = gca;
- Py_INCREF(gca);
- }
- else ret = find_deepest(self, gca);
+ ret = gca;
+ Py_INCREF(gca);
done:
free(revs);