( )⚙ D4005 index: store nullrev as -1 in nodetree

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4005

index: store nullrev as -1 in nodetree
ClosedPublic

Authored by martinvonz on Aug 1 2018, 12:43 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGf738c502e43b: index: store nullrev as -1 in nodetree
Summary

Nothing important, it just seems more natural to not map nullrev to
INT_MAX. We just need to change the revision encoding a little to make
space for the -1.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Revision Contents
Changeset List

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

Diff 9789

mercurial/cext/revlog.c

#define PyInt_AS_LONG PyLong_AS_LONG #define PyInt_AS_LONG PyLong_AS_LONG
#define PyInt_AsLong PyLong_AsLong #define PyInt_AsLong PyLong_AsLong
#endif #endif
/* /*
* 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 + 1) * Negative value is a leaf: -(rev + 2)
* Zero is empty * Zero is empty
*/ */
typedef struct { typedef struct {
int children[16]; int children[16];
} nodetree; } nodetree;
/* /*
* This class has two behaviors. * This class has two behaviors.
/* /*
* Return the 20-byte SHA of the node corresponding to the given rev. * Return the 20-byte SHA of the node corresponding to the given rev.
*/ */
static const char *index_node(indexObject *self, Py_ssize_t pos) static const char *index_node(indexObject *self, Py_ssize_t pos)
{ {
Py_ssize_t length = index_length(self); Py_ssize_t length = index_length(self);
const char *data; const char *data;
if (pos == length - 1 || pos == INT_MAX) if (pos == length - 1 || pos == -1)
return nullid; return nullid;
if (pos >= length) if (pos >= length)
return NULL; return NULL;
if (pos >= self->length - 1) { if (pos >= self->length - 1) {
PyObject *tuple, *str; PyObject *tuple, *str;
tuple = PyList_GET_ITEM(self->added, pos - self->length + 1); tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);
int k = getnybble(node, level); int k = getnybble(node, level);
nodetree *n = &self->nt[off]; nodetree *n = &self->nt[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 + 1); v = -(v + 2);
n = index_node(self, v); n = index_node(self, 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;
} }
int k = nt_level(node, level); int k = nt_level(node, level);
nodetree *n; nodetree *n;
int v; int v;
n = &self->nt[off]; n = &self->nt[off];
v = n->children[k]; v = n->children[k];
if (v == 0) { if (v == 0) {
n->children[k] = -rev - 1; n->children[k] = -rev - 2;
return 0; return 0;
} }
if (v < 0) { if (v < 0) {
const char *oldnode = index_node_existing(self, -(v + 1)); const char *oldnode = index_node_existing(self, -(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 - 1; n->children[k] = -rev - 2;
return 0; return 0;
} }
noff = nt_new(self); noff = nt_new(self);
if (noff == -1) if (noff == -1)
return -1; return -1;
/* self->nt may have been changed by realloc */ /* self->nt may have been changed by realloc */
self->nt[off].children[k] = noff; self->nt[off].children[k] = noff;
off = noff; off = noff;
n = &self->nt[off]; n = &self->nt[off];
n->children[nt_level(oldnode, ++level)] = v; n->children[nt_level(oldnode, ++level)] = v;
if (level > self->ntdepth) if (level > self->ntdepth)
self->ntdepth = level; self->ntdepth = level;
self->ntsplits += 1; self->ntsplits += 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(indexObject *self, const char *node)
{ {
/* rev==-1 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, -1); 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) {
if ((size_t)self->raw_length > INT_MAX / sizeof(nodetree)) { if ((size_t)self->raw_length > INT_MAX / sizeof(nodetree)) {
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->ntcapacity = self->raw_length < 4
? 4 : (int)self->raw_length / 2; ? 4 : (int)self->raw_length / 2;
self->nt = calloc(self->ntcapacity, sizeof(nodetree)); self->nt = calloc(self->ntcapacity, sizeof(nodetree));
if (self->nt == NULL) { if (self->nt == NULL) {
PyErr_NoMemory(); PyErr_NoMemory();
return -1; return -1;
} }
self->ntlength = 1; self->ntlength = 1;
self->ntrev = (int)index_length(self) - 1; self->ntrev = (int)index_length(self) - 1;
self->ntlookups = 1; self->ntlookups = 1;
self->ntmisses = 0; self->ntmisses = 0;
if (nt_insert(self, nullid, INT_MAX) == -1) if (nt_insert(self, nullid, -1) == -1)
return -1; return -1;
} }
return 0; return 0;
} }
/* /*
* Return values: * Return values:
* *
for (level = off = 0; level < 40; level++) { for (level = off = 0; level < 40; level++) {
int k, v; int k, v;
nodetree *n = &self->nt[off]; nodetree *n = &self->nt[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 + 1); v = -(v + 2);
n = index_node_existing(self, v); n = index_node_existing(self, 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).