( )⚙ D4113 index: make most "nt_*" functions take a nodetree

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4113

index: make most "nt_*" functions take a nodetree
ClosedPublic

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

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGb6fb71a0a005: index: make most "nt_*" functions take a nodetree
Summary

Now that the nodetree has a pointer to the index, we can pass the
nodtree instead of the index. There are few "nt_*" functions left
after this. I'll deal with them soon.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Revision Contents
Changeset List

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

Diff 10037

mercurial/cext/revlog.c

const char *node = index_node(self, pos); const char *node = index_node(self, pos);
if (node == NULL) { if (node == NULL) {
PyErr_Format(PyExc_IndexError, "could not access rev %d", PyErr_Format(PyExc_IndexError, "could not access rev %d",
(int)pos); (int)pos);
} }
return node; return node;
} }
static int nt_insert(indexObject *self, const char *node, int rev); static int nt_insert(nodetree *self, const char *node, int rev);
static int node_check(PyObject *obj, char **node) static int node_check(PyObject *obj, char **node)
{ {
Py_ssize_t nodelen; Py_ssize_t nodelen;
if (PyBytes_AsStringAndSize(obj, node, &nodelen) == -1) if (PyBytes_AsStringAndSize(obj, node, &nodelen) == -1)
return -1; return -1;
if (nodelen == 20) if (nodelen == 20)
return 0; return 0;
if (self->added == NULL) if (self->added == NULL)
return NULL; return NULL;
} }
if (PyList_Append(self->added, obj) == -1) if (PyList_Append(self->added, obj) == -1)
return NULL; return NULL;
if (self->nt) if (self->nt)
nt_insert(self, node, len); nt_insert(self->nt, node, len);
Py_CLEAR(self->headrevs); Py_CLEAR(self->headrevs);
Py_RETURN_NONE; Py_RETURN_NONE;
} }
static void _index_clearcaches(indexObject *self) static void _index_clearcaches(indexObject *self)
{ {
if (self->cache) { if (self->cache) {
/* /*
* Return values: * Return values:
* *
* -4: match is ambiguous (multiple candidates) * -4: match is ambiguous (multiple candidates)
* -2: not found * -2: not found
* rest: valid rev * rest: valid rev
*/ */
static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen, static int nt_find(nodetree *self, const char *node, Py_ssize_t nodelen,
int hex) int hex)
{ {
int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level; int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
int level, maxlevel, off; int level, maxlevel, off;
if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0) if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
return -1; return -1;
if (hex) if (hex)
maxlevel = nodelen > 40 ? 40 : (int)nodelen; maxlevel = nodelen > 40 ? 40 : (int)nodelen;
else else
maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2); maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2);
for (level = off = 0; level < maxlevel; level++) { for (level = off = 0; level < maxlevel; level++) {
int k = getnybble(node, level); int k = getnybble(node, level);
nodetreenode *n = &self->nt->nodes[off]; nodetreenode *n = &self->nodes[off];
int v = n->children[k]; int v = n->children[k];
if (v < 0) { if (v < 0) {
const char *n; const char *n;
Py_ssize_t i; Py_ssize_t i;
v = -(v + 2); v = -(v + 2);
n = index_node(self, v); n = index_node(self->index, v);
if (n == NULL) if (n == NULL)
return -2; return -2;
for (i = level; i < maxlevel; i++) for (i = level; i < maxlevel; i++)
if (getnybble(node, i) != nt_level(n, i)) if (getnybble(node, i) != nt_level(n, i))
return -2; return -2;
return v; return v;
} }
if (v == 0) if (v == 0)
self->capacity = newcapacity; self->capacity = newcapacity;
self->nodes = newnodes; self->nodes = newnodes;
memset(&self->nodes[self->length], 0, memset(&self->nodes[self->length], 0,
sizeof(nodetreenode) * (self->capacity - self->length)); sizeof(nodetreenode) * (self->capacity - self->length));
} }
return self->length++; return self->length++;
} }
static int nt_insert(indexObject *self, const char *node, int rev) static int nt_insert(nodetree *self, const char *node, int rev)
{ {
int level = 0; int level = 0;
int off = 0; int off = 0;
while (level < 40) { while (level < 40) {
int k = nt_level(node, level); int k = nt_level(node, level);
nodetreenode *n; nodetreenode *n;
int v; int v;
n = &self->nt->nodes[off]; n = &self->nodes[off];
v = n->children[k]; v = n->children[k];
if (v == 0) { if (v == 0) {
n->children[k] = -rev - 2; n->children[k] = -rev - 2;
return 0; return 0;
} }
if (v < 0) { if (v < 0) {
const char *oldnode = index_node_existing(self, -(v + 2)); const char *oldnode = index_node_existing(self->index, -(v + 2));
int noff; int noff;
if (oldnode == NULL) if (oldnode == NULL)
return -1; return -1;
if (!memcmp(oldnode, node, 20)) { if (!memcmp(oldnode, node, 20)) {
n->children[k] = -rev - 2; n->children[k] = -rev - 2;
return 0; return 0;
} }
noff = nt_new(self->nt); noff = nt_new(self);
if (noff == -1) if (noff == -1)
return -1; return -1;
/* self->nt->nodes may have been changed by realloc */ /* self->nodes may have been changed by realloc */
self->nt->nodes[off].children[k] = noff; self->nodes[off].children[k] = noff;
off = noff; off = noff;
n = &self->nt->nodes[off]; n = &self->nodes[off];
n->children[nt_level(oldnode, ++level)] = v; n->children[nt_level(oldnode, ++level)] = v;
if (level > self->nt->depth) if (level > self->depth)
self->nt->depth = level; self->depth = level;
self->nt->splits += 1; self->splits += 1;
} else { } else {
level += 1; level += 1;
off = v; off = v;
} }
} }
return -1; return -1;
} }
static int nt_delete_node(indexObject *self, const char *node) static int nt_delete_node(nodetree *self, const char *node)
{ {
/* rev==-2 happens to get encoded as 0, which is interpreted as not set */ /* rev==-2 happens to get encoded as 0, which is interpreted as not set */
return nt_insert(self, node, -2); return nt_insert(self, node, -2);
} }
static int nt_init(indexObject *self) static int nt_init(indexObject *self)
{ {
if (self->nt == NULL) { if (self->nt == NULL) {
} }
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->depth = 0; self->nt->depth = 0;
self->nt->splits = 0; self->nt->splits = 0;
self->nt->length = 1; self->nt->length = 1;
self->nt->index = self; self->nt->index = self;
if (nt_insert(self, nullid, -1) == -1) { if (nt_insert(self->nt, nullid, -1) == -1) {
free(self->nt->nodes); free(self->nt->nodes);
PyMem_Free(self->nt); PyMem_Free(self->nt);
self->nt = NULL; self->nt = NULL;
return -1; return -1;
} }
} }
return 0; return 0;
} }
const char *node, Py_ssize_t nodelen) const char *node, Py_ssize_t nodelen)
{ {
int rev; int rev;
if (nt_init(self) == -1) if (nt_init(self) == -1)
return -3; return -3;
self->ntlookups++; self->ntlookups++;
rev = nt_find(self, node, nodelen, 0); rev = nt_find(self->nt, node, nodelen, 0);
if (rev >= -1) if (rev >= -1)
return rev; return rev;
/* /*
* For the first handful of lookups, we scan the entire index, * For the first handful of lookups, we scan the entire index,
* and cache only the matching nodes. This optimizes for cases * and cache only the matching nodes. This optimizes for cases
* like "hg tip", where only a few nodes are accessed. * like "hg tip", where only a few nodes are accessed.
* *
* After that, we cache every node we visit, using a single * After that, we cache every node we visit, using a single
* scan amortized over multiple lookups. This gives the best * scan amortized over multiple lookups. This gives the best
* bulk performance, e.g. for "hg log". * bulk performance, e.g. for "hg log".
*/ */
if (self->ntmisses++ < 4) { if (self->ntmisses++ < 4) {
for (rev = self->ntrev - 1; rev >= 0; rev--) { for (rev = self->ntrev - 1; rev >= 0; rev--) {
const char *n = index_node_existing(self, rev); const char *n = index_node_existing(self, rev);
if (n == NULL) if (n == NULL)
return -3; return -3;
if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) { if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
if (nt_insert(self, n, rev) == -1) if (nt_insert(self->nt, n, rev) == -1)
return -3; return -3;
break; break;
} }
} }
} else { } else {
for (rev = self->ntrev - 1; rev >= 0; rev--) { for (rev = self->ntrev - 1; rev >= 0; rev--) {
const char *n = index_node_existing(self, rev); const char *n = index_node_existing(self, rev);
if (n == NULL) if (n == NULL)
return -3; return -3;
if (nt_insert(self, n, rev) == -1) { if (nt_insert(self->nt, n, rev) == -1) {
self->ntrev = rev + 1; self->ntrev = rev + 1;
return -3; return -3;
} }
if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) { if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
break; break;
} }
} }
self->ntrev = rev; self->ntrev = rev;
*/ */
static int nt_populate(indexObject *self) { static int nt_populate(indexObject *self) {
int rev; int rev;
if (self->ntrev > 0) { if (self->ntrev > 0) {
for (rev = self->ntrev - 1; rev >= 0; rev--) { for (rev = self->ntrev - 1; rev >= 0; rev--) {
const char *n = index_node_existing(self, rev); const char *n = index_node_existing(self, rev);
if (n == NULL) if (n == NULL)
return -1; return -1;
if (nt_insert(self, n, rev) == -1) if (nt_insert(self->nt, n, rev) == -1)
return -1; return -1;
} }
self->ntrev = -1; self->ntrev = -1;
} }
return 0; return 0;
} }
static int nt_partialmatch(indexObject *self, const char *node, static int nt_partialmatch(nodetree *self, const char *node,
Py_ssize_t nodelen) Py_ssize_t nodelen)
{ {
return nt_find(self, node, nodelen, 1); return nt_find(self, node, nodelen, 1);
} }
/* /*
* Find the length of the shortest unique prefix of node. * Find the length of the shortest unique prefix of node.
* *
* Return values: * Return values:
* *
* -3: error (exception set) * -3: error (exception set)
* -2: not found (no exception set) * -2: not found (no exception set)
* rest: length of shortest prefix * rest: length of shortest prefix
*/ */
static int nt_shortest(indexObject *self, const char *node) static int nt_shortest(nodetree *self, const char *node)
{ {
int level, off; int level, off;
for (level = off = 0; level < 40; level++) { for (level = off = 0; level < 40; level++) {
int k, v; int k, v;
nodetreenode *n = &self->nt->nodes[off]; nodetreenode *n = &self->nodes[off];
k = nt_level(node, level); k = nt_level(node, level);
v = n->children[k]; v = n->children[k];
if (v < 0) { if (v < 0) {
const char *n; const char *n;
v = -(v + 2); v = -(v + 2);
n = index_node_existing(self, v); n = index_node_existing(self->index, v);
if (n == NULL) if (n == NULL)
return -3; return -3;
if (memcmp(node, n, 20) != 0) if (memcmp(node, n, 20) != 0)
/* /*
* Found a unique prefix, but it wasn't for the * Found a unique prefix, but it wasn't for the
* requested node (i.e the requested node does * requested node (i.e the requested node does
* not exist). * not exist).
*/ */
PyErr_Clear(); PyErr_Clear();
Py_RETURN_NONE; Py_RETURN_NONE;
} }
if (nt_init(self) == -1) if (nt_init(self) == -1)
return NULL; return NULL;
if (nt_populate(self) == -1) if (nt_populate(self) == -1)
return NULL; return NULL;
rev = nt_partialmatch(self, node, nodelen); rev = nt_partialmatch(self->nt, node, nodelen);
switch (rev) { switch (rev) {
case -4: case -4:
raise_revlog_error(); raise_revlog_error();
return NULL; return NULL;
case -2: case -2:
Py_RETURN_NONE; Py_RETURN_NONE;
case -1: case -1:
if (node_check(val, &node) == -1) if (node_check(val, &node) == -1)
return NULL; return NULL;
self->ntlookups++; self->ntlookups++;
if (nt_init(self) == -1) if (nt_init(self) == -1)
return NULL; return NULL;
if (nt_populate(self) == -1) if (nt_populate(self) == -1)
return NULL; return NULL;
length = nt_shortest(self, node); length = nt_shortest(self->nt, node);
if (length == -3) if (length == -3)
return NULL; return NULL;
if (length == -2) { if (length == -2) {
raise_revlog_error(); raise_revlog_error();
return NULL; return NULL;
} }
return PyInt_FromLong(length); return PyInt_FromLong(length);
} }
static void nt_invalidate_added(indexObject *self, Py_ssize_t start) static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
{ {
Py_ssize_t i, len = PyList_GET_SIZE(self->added); Py_ssize_t i, len = PyList_GET_SIZE(self->added);
for (i = start; i < len; i++) { for (i = start; i < len; i++) {
PyObject *tuple = PyList_GET_ITEM(self->added, i); PyObject *tuple = PyList_GET_ITEM(self->added, i);
PyObject *node = PyTuple_GET_ITEM(tuple, 7); PyObject *node = PyTuple_GET_ITEM(tuple, 7);
nt_delete_node(self, PyBytes_AS_STRING(node)); nt_delete_node(self->nt, PyBytes_AS_STRING(node));
} }
if (start == 0) if (start == 0)
Py_CLEAR(self->added); Py_CLEAR(self->added);
} }
/* /*
* Delete a numeric range of revs, which must be at the end of the * Delete a numeric range of revs, which must be at the end of the
if (self->nt) { if (self->nt) {
Py_ssize_t i; Py_ssize_t i;
for (i = start + 1; i < self->length - 1; i++) { for (i = start + 1; i < self->length - 1; i++) {
const char *node = index_node_existing(self, i); const char *node = index_node_existing(self, i);
if (node == NULL) if (node == NULL)
return -1; return -1;
nt_delete_node(self, node); nt_delete_node(self->nt, node);
} }
if (self->added) if (self->added)
nt_invalidate_added(self, 0); nt_invalidate_added(self, 0);
if (self->ntrev > start) if (self->ntrev > start)
self->ntrev = (int)start; self->ntrev = (int)start;
} }
self->length = start + 1; self->length = start + 1;
if (start < self->raw_length) { if (start < self->raw_length) {
if (PySlice_Check(item) && value == NULL) if (PySlice_Check(item) && value == NULL)
return index_slice_del(self, item); return index_slice_del(self, item);
if (node_check(item, &node) == -1) if (node_check(item, &node) == -1)
return -1; return -1;
if (value == NULL) if (value == NULL)
return self->nt ? nt_delete_node(self, node) : 0; return self->nt ? nt_delete_node(self->nt, node) : 0;
rev = PyInt_AsLong(value); rev = PyInt_AsLong(value);
if (rev > INT_MAX || rev < 0) { if (rev > INT_MAX || rev < 0) {
if (!PyErr_Occurred()) if (!PyErr_Occurred())
PyErr_SetString(PyExc_ValueError, "rev out of range"); PyErr_SetString(PyExc_ValueError, "rev out of range");
return -1; return -1;
} }
if (nt_init(self) == -1) if (nt_init(self) == -1)
return -1; return -1;
return nt_insert(self, node, (int)rev); return nt_insert(self->nt, node, (int)rev);
} }
/* /*
* Find all RevlogNG entries in an index that has inline data. Update * Find all RevlogNG entries in an index that has inline data. Update
* the optional "offsets" table with those entries. * the optional "offsets" table with those entries.
*/ */
static Py_ssize_t inline_scan(indexObject *self, const char **offsets) static Py_ssize_t inline_scan(indexObject *self, const char **offsets)
{ {