This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4110

index: drop now-redundant "nt" prefix of fields in nodetree struct
ClosedPublic

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

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGf28e64bbdd29: index: drop now-redundant "nt" prefix of fields in nodetree struct
Summary

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 rHGf28e64bbdd29: index: drop now-redundant "nt" prefix of fields in nodetree struct (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 (46 lines)

Diff 9974

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 length; /* # nodes in use */
unsigned ntcapacity; /* # nodes allocated */ unsigned capacity; /* # nodes allocated */
int ntdepth; /* maximum depth of tree */ int depth; /* maximum depth of tree */
int ntsplits; /* # splits performed */ int splits; /* # 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
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(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");
if (self->nt) { if (self->nt) {
istat(nt->ntcapacity, "node trie capacity"); istat(nt->capacity, "node trie capacity");
istat(nt->ntdepth, "node trie depth"); istat(nt->depth, "node trie depth");
istat(nt->ntlength, "node trie count"); istat(nt->length, "node trie count");
istat(nt->ntsplits, "node trie splits"); istat(nt->splits, "node trie splits");
} }
#undef istat #undef istat
return obj; return obj;
bail: bail:
Py_XDECREF(obj); Py_XDECREF(obj);
} }
/* 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)
{ {
nodetree *nt = self->nt; nodetree *nt = self->nt;
if (nt->ntlength == nt->ntcapacity) { if (nt->length == nt->capacity) {
if (nt->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) { if (nt->capacity >= 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;
} }
nt->ntcapacity *= 2; nt->capacity *= 2;
nt->nodes = realloc(nt->nodes, nt->nodes = realloc(nt->nodes,
nt->ntcapacity * sizeof(nodetreenode)); nt->capacity * sizeof(nodetreenode));
if (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(&nt->nodes[nt->ntlength], 0, memset(&nt->nodes[nt->length], 0,
sizeof(nodetreenode) * (nt->ntcapacity - nt->ntlength)); sizeof(nodetreenode) * (nt->capacity - nt->length));
} }
return nt->ntlength++; return nt->length++;
} }
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->nt->ntdepth) if (level > self->nt->depth)
self->nt->ntdepth = level; self->nt->depth = level;
self->nt->ntsplits += 1; self->nt->splits += 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->nt->ntcapacity = self->raw_length < 4 self->nt->capacity = self->raw_length < 4
? 4 : (int)self->raw_length / 2; ? 4 : (int)self->raw_length / 2;
self->nt->nodes = calloc(self->nt->ntcapacity, sizeof(nodetreenode)); self->nt->nodes = calloc(self->nt->capacity, 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->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->depth = 0;
self->nt->ntsplits = 0; self->nt->splits = 0;
self->nt->ntlength = 1; self->nt->length = 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;