diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c
--- a/mercurial/cext/revlog.c
+++ b/mercurial/cext/revlog.c
@@ -2837,6 +2837,127 @@
return NULL;
}
+typedef struct {
+ PyObject_HEAD
+ indexObject *idx;
+ int with_buffer;
+ Py_buffer buf;
+ uint32_t m, n, seed;
+} phashObject;
+
+static int phash_init(phashObject *self, PyObject *args)
+{
+ if (!PyArg_ParseTuple(args, "y*O!", &self->buf, &HgRevlogIndex_Type, &self->idx))
+ return -1;
+ self->with_buffer = 1;
+ if (!PyBuffer_IsContiguous(&self->buf, 'C') || self->buf.ndim > 1 || self->buf.len < 12)
+ return -1;
+ self->seed = getbe32(self->buf.buf + 0);
+ self->m = getbe32(self->buf.buf + 4);
+ self->n = getbe32(self->buf.buf + 8);
+ if (self->m == 0 || self->buf.len % 4 != 0 || (self->buf.len - 12) / 4 < self->m)
+ return -1;
+ return 0;
+}
+
+static void phash_dealloc(phashObject *self)
+{
+ if (self->with_buffer)
+ PyBuffer_Release(&self->buf);
+}
+
+static PyObject *phash_get(phashObject *self, PyObject *args)
+{
+ const char *node, *nodedata;
+ Py_ssize_t nodelen;
+ uint32_t h0, h1, h2, rev;
+ if (!PyArg_ParseTuple(args, "y#", &node, &nodelen))
+ Py_RETURN_NONE;
+ if (self->n == 0 || nodelen < 12 || nodelen != self->idx->nodelen)
+ Py_RETURN_NONE;
+
+ if (!memcmp(node, nullid, nodelen))
+ return PyLong_FromLong(-1);
+
+ if (self->seed + 12 > nodelen)
+ Py_RETURN_NONE;
+
+ h0 = getbe32(node + self->seed);
+ h1 = getbe32(node + self->seed + 4);
+ h2 = getbe32(node + self->seed + 8);
+
+ h0 %= self->m;
+ h1 %= self->m;
+ h2 %= self->m;
+
+ h1 ^= (h0 == h1);
+ h2 ^= (h0 == h2 || h1 == h2);
+ h2 ^= 2 * (h0 == h2 || h1 == h2);
+
+ h0 = getbe32(self->buf.buf + 12 + 4 * h0);
+ h1 = getbe32(self->buf.buf + 12 + 4 * h1);
+ h2 = getbe32(self->buf.buf + 12 + 4 * h2);
+
+ rev = (h0 + h1 + h2) % self->n;
+ if (rev >= self->idx->length)
+ Py_RETURN_NONE;
+
+ nodedata = index_deref(self->idx, rev);
+ if (!nodedata)
+ Py_RETURN_NONE;
+
+ if (memcmp(nodedata + 32, node, nodelen))
+ Py_RETURN_NONE;
+
+ return PyLong_FromUnsignedLong(rev);
+}
+
+static PyMethodDef phash_methods[] = {
+ {"get", (PyCFunction)phash_get, METH_VARARGS,
+ "find candidate revision for given node"},
+ {NULL}
+};
+
+static PyTypeObject phashType = {
+ PyVarObject_HEAD_INIT(NULL, 0) /* header */
+ "parsers.phash", /* tp_name */
+ sizeof(phashObject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)phash_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
+ "phash", /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ phash_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ (initproc)phash_init, /* tp_init */
+ 0, /* tp_alloc */
+};
+
static Revlog_CAPI CAPI = {
/* increment the abi_version field upon each change in the Revlog_CAPI
struct or in the ABI of the listed functions */
@@ -2861,6 +2982,12 @@
Py_INCREF(&nodetreeType);
PyModule_AddObject(mod, "nodetree", (PyObject *)&nodetreeType);
+ phashType.tp_new = PyType_GenericNew;
+ if (PyType_Ready(&phashType) < 0)
+ return;
+ Py_INCREF(&phashType);
+ PyModule_AddObject(mod, "phash", (PyObject *)&phashType);
+
caps = PyCapsule_New(&CAPI, "mercurial.cext.parsers.revlog_CAPI", NULL);
if (caps != NULL)
PyModule_AddObject(mod, "revlog_CAPI", caps);
diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -12,6 +12,7 @@
bin,
hex,
nullid,
+ nullrev,
)
from .thirdparty import attr
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -2699,12 +2699,12 @@
self.filtered(b'served').branchmap()
self.filtered(b'served.hidden').branchmap()
+ self.changelog.update_caches(transaction=tr)
+ self.manifestlog.update_caches(transaction=tr)
+
if full:
unfi = self.unfiltered()
- self.changelog.update_caches(transaction=tr)
- self.manifestlog.update_caches(transaction=tr)
-
rbc = unfi.revbranchcache()
for r in unfi.changelog:
rbc.branchinfo(r)
diff --git a/mercurial/pure/parsers.py b/mercurial/pure/parsers.py
--- a/mercurial/pure/parsers.py
+++ b/mercurial/pure/parsers.py
@@ -284,3 +284,24 @@
write(e)
write(f)
return cs.getvalue()
+
+
+from ..node import nullid, nullrev
+from ..utils import phash_reader
+
+be32 = struct.Struct('>I')
+
+
+class phash:
+ def __init__(self, data, revlogindex):
+ self.hashtable = phash_reader.hashtable(data)
+ self.revlogindex = revlogindex
+
+ def get(self, node):
+ if node == nullid:
+ return nullrev
+
+ rev = self.hashtable.get(node)
+ if self.revlogindex[rev][7] == node:
+ return rev
+ return None
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -227,6 +227,61 @@
indexformatv0_unpack = indexformatv0.unpack
+class WrapperIndex(object):
+ def __init__(self, real_index, pphash, sphash):
+ self.__real_index = real_index
+ self.__pphash = pphash
+ self.__sphash = sphash
+
+ def has_node(self, node):
+ if self.__pphash and self.__pphash.get(node) is not None:
+ return True
+ if self.__sphash and self.__sphash.get(node) is not None:
+ return True
+ return self.__real_index.has_node(node)
+
+ def rev(self, node):
+ if self.__pphash:
+ rev = self.__pphash.get(node)
+ if rev is not None:
+ return rev
+ if self.__sphash:
+ rev = self.__sphash.get(node)
+ if rev is not None:
+ return rev
+ return self.__real_index.rev(node)
+
+ def get_rev(self, node):
+ if self.__pphash:
+ rev = self.__pphash.get(node)
+ if rev is not None:
+ return rev
+ if self.__sphash:
+ rev = self.__sphash.get(node)
+ if rev is not None:
+ return rev
+ return self.__real_index.get_rev(node)
+
+ def _stripnodes(self, start):
+ return self.__real_index.stripnodes(start)
+
+ def clearcaches(self):
+ return self.__real_index.clearcaches()
+
+ def __len__(self):
+ return self.__real_index.__len__()
+ return self._lgt + len(self._extra)
+
+ def append(self, tup):
+ return self.__real_index.append(tup)
+
+ def _check_index(self, i):
+ return self.__real_index._check_index(i)
+
+ def __getitem__(self, i):
+ return self.__real_index.__getitem__(i)
+
+
class revlogoldindex(list):
@property
def nodemap(self):
@@ -385,6 +440,15 @@
return rustrevlog.MixedIndex(index), cache
+def indexfile_sibling(opener, path, ext):
+ if not path.endswith(b".a"):
+ return path[:-2] + ext
+ pending_path = path[:-4] + ext + b".a"
+ if opener.exists(pending_path):
+ return pending_path
+ return path[:-4] + ext
+
+
class revlog(object):
"""
the underlying revision storage object
@@ -448,14 +512,12 @@
self.datafile = datafile or (indexfile[:-2] + b".d")
self.nodemap_file = None
if persistentnodemap:
- if indexfile.endswith(b'.a'):
- pending_path = indexfile[:-4] + b".n.a"
- if opener.exists(pending_path):
- self.nodemap_file = pending_path
- else:
- self.nodemap_file = indexfile[:-4] + b".n"
- else:
- self.nodemap_file = indexfile[:-2] + b".n"
+ self.nodemap_file = indexfile_sibling(opener, indexfile, b".n")
+
+ self._pphash_file = indexfile_sibling(opener, indexfile, b".pphf")
+ self._pphash = None
+ self._sphash_file = indexfile_sibling(opener, indexfile, b".sphf")
+ self._sphash = None
self.opener = opener
# When True, indexfile is opened with checkambig=True at writing, to
@@ -670,6 +732,18 @@
# no changelog tampering
self._nodemap_docket = docket
index.update_nodemap_data(*nodemap_data)
+ if not self._inline:
+ if self.opener.exists(self._pphash_file):
+ f = self.opener.open(self._pphash_file)
+ data = util.mmapread(f)
+ self._pphash = parsers.phash(data, d[0])
+ if self.opener.exists(self._sphash_file):
+ f = self.opener.open(self._sphash_file)
+ data = util.mmapread(f)
+ self._sphash = parsers.phash(data, d[0])
+ if self._pphash or self._sphash:
+ d = WrapperIndex(d[0], self._pphash, self._sphash), d[1]
+
except (ValueError, IndexError):
raise error.RevlogError(
_(b"index %s is corrupted") % self.indexfile
@@ -780,12 +854,52 @@
return False
return True
+ phash_update_delta = 1000
+
+ def _update_pphash(self, transaction):
+ if self._pphash and transaction:
+ if (
+ transaction.changes[b'origrepolen'] // self.phash_update_delta
+ == len(self) // self.phash_update_delta
+ ):
+ return
+ elif len(self) < self.phash_update_delta:
+ return
+ from .utils import phash_writer
+
+ writer = phash_writer.hashtable()
+ for rev in pycompat.xrange(
+ len(self) // self.phash_update_delta * self.phash_update_delta
+ ):
+ writer.insert(self.node(rev))
+ data = writer.write()
+ f = self.opener(self._pphash_file, atomictemp=True, mode=b'wb')
+ f.write(data)
+ f.close()
+
+ def _update_sphash(self, transaction):
+ from .utils import phash_writer
+
+ writer = phash_writer.hashtable()
+ for rev in pycompat.xrange(
+ len(self) // self.phash_update_delta * self.phash_update_delta,
+ len(self),
+ ):
+ writer.insert(self.node(rev))
+ data = writer.write()
+ f = self.opener(self._sphash_file, atomictemp=True, mode=b'wb')
+ f.write(data)
+ f.close()
+
def update_caches(self, transaction):
if self.nodemap_file is not None:
if transaction is None:
nodemaputil.update_persistent_nodemap(self)
else:
nodemaputil.setup_persistent_nodemap(transaction, self)
+ if self._pphash_file and not self._inline:
+ self._update_pphash(transaction)
+ self._update_sphash(transaction)
def clearcaches(self):
self._revisioncache = None
diff --git a/mercurial/utils/phash_reader.py b/mercurial/utils/phash_reader.py
new file mode 100644
--- /dev/null
+++ b/mercurial/utils/phash_reader.py
@@ -0,0 +1,39 @@
+import struct
+
+be32 = struct.Struct('>I')
+
+
+def default_hash(key, seed):
+ base = seed * 4
+ return [
+ be32.unpack(key[base : base + 4])[0],
+ be32.unpack(key[base + 4 : base + 8])[0],
+ be32.unpack(key[base + 8 : base + 12])[0],
+ ]
+
+
+class hashtable:
+ def __init__(self, data, hash=default_hash):
+ self.data = data
+ (self.seed,) = be32.unpack(data[0:4])
+ (self.m,) = be32.unpack(data[4:8])
+ (self.n,) = be32.unpack(data[8:12])
+
+ def get(self, node):
+ base = self.seed * 4
+ h0 = be32.unpack(node[base : base + 4])[0] % self.m
+ h1 = be32.unpack(node[base + 4 : base + 8])[0] % self.m
+ h2 = be32.unpack(node[base + 8 : base + 12])[0] % self.m
+
+ if h0 == h1:
+ h1 ^= 1
+ if h0 == h2 or h1 == h2:
+ h2 ^= 1
+ if h0 == h2 or h1 == h2:
+ h2 ^= 2
+
+ def g(idx):
+ idx = 12 + 4 * idx
+ return be32.unpack(self.data[idx : idx + 4])[0]
+
+ return (g(h0 % self.m) + g(h1 % self.m) + g(h2 % self.m)) % self.n
diff --git a/mercurial/utils/phash_writer.py b/mercurial/utils/phash_writer.py
new file mode 100644
--- /dev/null
+++ b/mercurial/utils/phash_writer.py
@@ -0,0 +1,104 @@
+import struct
+
+be32 = struct.Struct('>I')
+
+
+def default_hash(key, seed):
+ base = seed * 4
+ return [
+ be32.unpack(key[base : base + 4])[0],
+ be32.unpack(key[base + 4 : base + 8])[0],
+ be32.unpack(key[base + 8 : base + 12])[0],
+ ]
+
+
+class hashtable:
+ def __init__(self, hash=default_hash):
+ self.entries = []
+ self.hash = hash
+
+ def insert(self, key):
+ self.entries.append(key)
+
+ def _hash_entry(self, nv, seed, entry):
+ hash = [x % nv for x in self.hash(entry, seed)]
+ if hash[0] == hash[1]:
+ hash[1] ^= 1
+ if hash[0] == hash[2] or hash[1] == hash[2]:
+ hash[2] ^= 1
+ if hash[0] == hash[2] or hash[1] == hash[2]:
+ hash[2] ^= 2
+
+ return hash
+
+ def _compute_graph(self, ne, nv, seed):
+ edges = []
+ vertices_edges = [0] * nv
+ vertices_degrees = [0] * nv
+
+ for i in range(ne):
+ e = self._hash_entry(nv, seed, self.entries[i])
+ edges.append(e)
+ for v in e:
+ vertices_edges[v] ^= i
+ vertices_degrees[v] += 1
+
+ output_order = []
+
+ def remove_vertex(v):
+ if vertices_degrees[v] != 1:
+ return
+ e = vertices_edges[v]
+ output_order.append(e)
+ for v in edges[e]:
+ vertices_edges[v] ^= e
+ vertices_degrees[v] -= 1
+
+ for v in range(nv):
+ remove_vertex(v)
+ oi = 0
+ while oi < len(output_order):
+ for v in edges[output_order[oi]]:
+ remove_vertex(v)
+ oi += 1
+
+ if len(output_order) == ne:
+ return edges, output_order
+ else:
+ return None
+
+ def write(self):
+ seed = 0
+ ne = len(self.entries)
+ nv = max(128, ne * 124 // 100)
+ nv = (nv | 3) + 1
+
+ rv = None
+ seed = -1
+ while rv is None:
+ seed += 1
+ rv = self._compute_graph(ne, nv, seed)
+ edges, output_order = rv
+
+ g = [0] * nv
+ visited = [False] * nv
+ for idx in reversed(output_order):
+ edge = edges[idx]
+ if not visited[edge[0]]:
+ g[edge[0]] = (idx - g[edge[1]] - g[edge[2]]) % ne
+ elif not visited[edge[1]]:
+ g[edge[1]] = (idx - g[edge[0]] - g[edge[2]]) % ne
+ else:
+ g[edge[2]] = (idx - g[edge[1]] - g[edge[0]]) % ne
+ for v in edge:
+ visited[v] = True
+
+ output = bytearray(12 + 4 * len(g))
+ be32.pack_into(output, 0, seed)
+ be32.pack_into(output, 4, nv)
+ be32.pack_into(output, 8, ne)
+ pos = 12
+ for v in g:
+ be32.pack_into(output, pos, v)
+ pos += 4
+ return output