This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4109

index: move more fields onto nodetree type
ClosedPublic

Authored by martinvonz on Aug 5 2018, 3:58 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGc2c253558e3c: index: move more fields onto nodetree type
Summary

The fields moves are the ones that are not related to how the nodetree
is used in the index and that will make sense for the new nodetree
instance for a subset of the index that I'll add later.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

martinvonz created this revision.Aug 5 2018, 3:58 AM
Closed by commit rHGc2c253558e3c: index: move more fields onto nodetree type (authored by martinvonz). · Explain WhyAug 6 2018, 9:13 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/revlog.c (55 lines)

Diff 9973

mercurial/cext/revlog.c

* A base-16 trie for fast node->rev mapping. * A base-16 trie for fast node->rev mapping.
* *
* Positive value is index of the next node in the trie * Positive value is index of the next node in the trie
* Negative value is a leaf: -(rev + 2) * Negative value is a leaf: -(rev + 2)
* Zero is empty * Zero is empty
*/ */
typedef struct { typedef struct {
nodetreenode *nodes; nodetreenode *nodes;
unsigned ntlength; /* # nodes in use */
unsigned ntcapacity; /* # nodes allocated */
int ntdepth; /* maximum depth of tree */
int ntsplits; /* # splits performed */
} nodetree; } nodetree;
/* /*
* This class has two behaviors. * This class has two behaviors.
* *
* When used in a list-like way (with integer keys), we decode an * When used in a list-like way (with integer keys), we decode an
* entry in a RevlogNG index file on demand. Our last entry is a * entry in a RevlogNG index file on demand. Our last entry is a
* sentinel, always a nullid. We have limited support for * sentinel, always a nullid. We have limited support for
PyObject **cache; /* cached tuples */ PyObject **cache; /* cached tuples */
const char **offsets; /* populated on demand */ const char **offsets; /* populated on demand */
Py_ssize_t raw_length; /* original number of elements */ Py_ssize_t raw_length; /* original number of elements */
Py_ssize_t length; /* current number of elements */ Py_ssize_t length; /* current number of elements */
PyObject *added; /* populated on demand */ PyObject *added; /* populated on demand */
PyObject *headrevs; /* cache, invalidated on changes */ PyObject *headrevs; /* cache, invalidated on changes */
PyObject *filteredrevs;/* filtered revs set */ PyObject *filteredrevs;/* filtered revs set */
nodetree *nt; /* base-16 trie */ nodetree *nt; /* base-16 trie */
unsigned ntlength; /* # nodes in use */
unsigned ntcapacity; /* # nodes allocated */
int ntdepth; /* maximum depth of tree */
int ntsplits; /* # splits performed */
int ntrev; /* last rev scanned */ int ntrev; /* last rev scanned */
int ntlookups; /* # lookups */ int ntlookups; /* # lookups */
int ntmisses; /* # lookups that miss the cache */ int ntmisses; /* # lookups that miss the cache */
int inlined; int inlined;
} indexObject; } indexObject;
static Py_ssize_t index_length(const indexObject *self) static Py_ssize_t index_length(const indexObject *self)
{ {
} }
self->nt = NULL; self->nt = NULL;
Py_CLEAR(self->headrevs); Py_CLEAR(self->headrevs);
} }
static PyObject *index_clearcaches(indexObject *self) static PyObject *index_clearcaches(indexObject *self)
{ {
_index_clearcaches(self); _index_clearcaches(self);
self->ntlength = self->ntcapacity = 0;
self->ntdepth = self->ntsplits = 0;
self->ntrev = -1; self->ntrev = -1;
self->ntlookups = self->ntmisses = 0; self->ntlookups = self->ntmisses = 0;
Py_RETURN_NONE; Py_RETURN_NONE;
} }
static PyObject *index_stats(indexObject *self) static PyObject *index_stats(indexObject *self)
{ {
PyObject *obj = PyDict_New(); PyObject *obj = PyDict_New();
if (PyDict_SetItemString(obj, "index entries added", t) == -1) if (PyDict_SetItemString(obj, "index entries added", t) == -1)
goto bail; goto bail;
Py_DECREF(t); Py_DECREF(t);
} }
if (self->raw_length != self->length - 1) if (self->raw_length != self->length - 1)
istat(raw_length, "revs on disk"); istat(raw_length, "revs on disk");
istat(length, "revs in memory"); istat(length, "revs in memory");
istat(ntcapacity, "node trie capacity");
istat(ntdepth, "node trie depth");
istat(ntlength, "node trie count");
istat(ntlookups, "node trie lookups"); istat(ntlookups, "node trie lookups");
istat(ntmisses, "node trie misses"); istat(ntmisses, "node trie misses");
istat(ntrev, "node trie last rev scanned"); istat(ntrev, "node trie last rev scanned");
istat(ntsplits, "node trie splits"); if (self->nt) {
istat(nt->ntcapacity, "node trie capacity");
istat(nt->ntdepth, "node trie depth");
istat(nt->ntlength, "node trie count");
istat(nt->ntsplits, "node trie splits");
}
#undef istat #undef istat
return obj; return obj;
bail: bail:
Py_XDECREF(obj); Py_XDECREF(obj);
Py_XDECREF(t); Py_XDECREF(t);
off = v; off = v;
} }
/* multiple matches against an ambiguous prefix */ /* multiple matches against an ambiguous prefix */
return -4; return -4;
} }
static int nt_new(indexObject *self) static int nt_new(indexObject *self)
{ {
if (self->ntlength == self->ntcapacity) { nodetree *nt = self->nt;
if (self->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) { if (nt->ntlength == nt->ntcapacity) {
if (nt->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {
PyErr_SetString(PyExc_MemoryError, PyErr_SetString(PyExc_MemoryError,
"overflow in nt_new"); "overflow in nt_new");
return -1; return -1;
} }
self->ntcapacity *= 2; nt->ntcapacity *= 2;
self->nt->nodes = realloc(self->nt->nodes, nt->nodes = realloc(nt->nodes,
self->ntcapacity * sizeof(nodetreenode)); nt->ntcapacity * sizeof(nodetreenode));
if (self->nt->nodes == NULL) { if (nt->nodes == NULL) {
PyErr_SetString(PyExc_MemoryError, "out of memory"); PyErr_SetString(PyExc_MemoryError, "out of memory");
return -1; return -1;
} }
memset(&self->nt->nodes[self->ntlength], 0, memset(&nt->nodes[nt->ntlength], 0,
sizeof(nodetreenode) * (self->ntcapacity - self->ntlength)); sizeof(nodetreenode) * (nt->ntcapacity - nt->ntlength));
} }
return self->ntlength++; return nt->ntlength++;
} }
static int nt_insert(indexObject *self, const char *node, int rev) static int nt_insert(indexObject *self, const char *node, int rev)
{ {
int level = 0; int level = 0;
int off = 0; int off = 0;
while (level < 40) { while (level < 40) {
noff = nt_new(self); noff = nt_new(self);
if (noff == -1) if (noff == -1)
return -1; return -1;
/* self->nt->nodes may have been changed by realloc */ /* self->nt->nodes may have been changed by realloc */
self->nt->nodes[off].children[k] = noff; self->nt->nodes[off].children[k] = noff;
off = noff; off = noff;
n = &self->nt->nodes[off]; n = &self->nt->nodes[off];
n->children[nt_level(oldnode, ++level)] = v; n->children[nt_level(oldnode, ++level)] = v;
if (level > self->ntdepth) if (level > self->nt->ntdepth)
self->ntdepth = level; self->nt->ntdepth = level;
self->ntsplits += 1; self->nt->ntsplits += 1;
} else { } else {
level += 1; level += 1;
off = v; off = v;
} }
} }
return -1; return -1;
} }
if (self->nt == NULL) { if (self->nt == NULL) {
PyErr_NoMemory(); PyErr_NoMemory();
return -1; return -1;
} }
if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) { if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) {
PyErr_SetString(PyExc_ValueError, "overflow in nt_init"); PyErr_SetString(PyExc_ValueError, "overflow in nt_init");
return -1; return -1;
} }
self->ntcapacity = self->raw_length < 4 self->nt->ntcapacity = self->raw_length < 4
? 4 : (int)self->raw_length / 2; ? 4 : (int)self->raw_length / 2;
self->nt->nodes = calloc(self->ntcapacity, sizeof(nodetreenode)); self->nt->nodes = calloc(self->nt->ntcapacity, sizeof(nodetreenode));
if (self->nt->nodes == NULL) { if (self->nt->nodes == NULL) {
free(self->nt); free(self->nt);
self->nt = NULL; self->nt = NULL;
PyErr_NoMemory(); PyErr_NoMemory();
return -1; return -1;
} }
self->ntlength = 1;
self->ntrev = (int)index_length(self); self->ntrev = (int)index_length(self);
self->ntlookups = 1; self->ntlookups = 1;
self->ntmisses = 0; self->ntmisses = 0;
self->nt->ntdepth = 0;
self->nt->ntsplits = 0;
self->nt->ntlength = 1;
if (nt_insert(self, nullid, -1) == -1) { if (nt_insert(self, nullid, -1) == -1) {
free(self->nt->nodes); free(self->nt->nodes);
free(self->nt); free(self->nt);
self->nt = NULL; self->nt = NULL;
return -1; return -1;
} }
} }
return 0; return 0;
if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1) if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1)
return -1; return -1;
size = self->buf.len; size = self->buf.len;
self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj); self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
self->data = data_obj; self->data = data_obj;
self->ntlength = self->ntcapacity = 0;
self->ntdepth = self->ntsplits = 0;
self->ntlookups = self->ntmisses = 0; self->ntlookups = self->ntmisses = 0;
self->ntrev = -1; self->ntrev = -1;
Py_INCREF(self->data); Py_INCREF(self->data);
if (self->inlined) { if (self->inlined) {
Py_ssize_t len = inline_scan(self, NULL); Py_ssize_t len = inline_scan(self, NULL);
if (len == -1) if (len == -1)
goto bail; goto bail;