This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9162

revlog: store new index entries as binary
ClosedPublic

Authored by joerg.sonnenberger on Oct 6 2020, 9:26 PM.

Details

Reviewers
durin42
pulkit
Group Reviewers
hg-reviewers
Commits
rHG0ce15a8c7b8b: revlog: store new index entries as binary
Summary

For a pure-Python unbundle of the current NetBSD test repository, this
results in a 10% peak RSS reduction. Using the C revlog index, it shows
25% peak RSS reduction. This is a direct result of avoiding at least
8 objects per new changeset or 200 Bytes+ on AMD64.

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

joerg.sonnenberger retitled this revision from [WIP] revlog: store new index entries as binary to revlog: store new index entries as binary.Oct 14 2020, 4:29 PM
joerg.sonnenberger edited the summary of this revision. (Show Details)
durin42 requested changes to this revision.Oct 30 2020, 5:28 PM
durin42 added a subscriber: durin42.

This flunks tests extensively (sorry, I forgot to copy the output as I've been doing entirely too many things today).

This revision now requires changes to proceed.Oct 30 2020, 5:28 PM
pulkit accepted this revision.Nov 27 2020, 5:39 AM
joerg.sonnenberger added a commit: rHG0ce15a8c7b8b: revlog: store new index entries as binary.Nov 27 2020, 6:34 AM
This revision was not accepted when it landed; it landed in state Needs Revision.
Closed by commit rHG0ce15a8c7b8b: revlog: store new index entries as binary (authored by joerg.sonnenberger). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/revlog.c (272 lines)
Mmercurial/pure/parsers.py (18 lines)

Diff 23711

mercurial/cext/revlog.c

* rev, using a base-16 trie. * rev, using a base-16 trie.
*/ */
struct indexObjectStruct { struct indexObjectStruct {
PyObject_HEAD PyObject_HEAD
/* Type-specific fields go here. */ /* Type-specific fields go here. */
PyObject *data; /* raw bytes of index */ PyObject *data; /* raw bytes of index */
Py_buffer buf; /* buffer of data */ Py_buffer buf; /* buffer of data */
const char **offsets; /* populated on demand */ const char **offsets; /* populated on demand */
Py_ssize_t raw_length; /* original number of elements */ Py_ssize_t length; /* current on-disk number of elements */
Py_ssize_t length; /* current number of elements */ unsigned new_length; /* number of added elements */
PyObject *added; /* populated on demand */ unsigned added_length; /* space reserved for added elements */
char *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 */
int ntinitialized; /* 0 or 1 */ int ntinitialized; /* 0 or 1 */
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;
}; };
static Py_ssize_t index_length(const indexObject *self) static Py_ssize_t index_length(const indexObject *self)
{ {
if (self->added == NULL) return self->length + self->new_length;
return self->length;
return self->length + PyList_GET_SIZE(self->added);
} }
static PyObject *nullentry = NULL; static PyObject *nullentry = NULL;
static const char nullid[20] = {0}; static const char nullid[20] = {0};
static const Py_ssize_t nullrev = -1; static const Py_ssize_t nullrev = -1;
static Py_ssize_t inline_scan(indexObject *self, const char **offsets); static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
Py_XDECREF(mod); Py_XDECREF(mod);
} }
/* /*
* Return a pointer to the beginning of a RevlogNG record. * Return a pointer to the beginning of a RevlogNG record.
*/ */
static const char *index_deref(indexObject *self, Py_ssize_t pos) static const char *index_deref(indexObject *self, Py_ssize_t pos)
{ {
if (pos >= self->length)
return self->added + (pos - self->length) * v1_hdrsize;
if (self->inlined && pos > 0) { if (self->inlined && pos > 0) {
if (self->offsets == NULL) { if (self->offsets == NULL) {
Py_ssize_t ret; Py_ssize_t ret;
self->offsets = PyMem_Malloc(self->raw_length * self->offsets =
sizeof(*self->offsets)); PyMem_Malloc(self->length * sizeof(*self->offsets));
if (self->offsets == NULL) if (self->offsets == NULL)
return (const char *)PyErr_NoMemory(); return (const char *)PyErr_NoMemory();
ret = inline_scan(self, self->offsets); ret = inline_scan(self, self->offsets);
if (ret == -1) { if (ret == -1) {
return NULL; return NULL;
}; };
} }
return self->offsets[pos]; return self->offsets[pos];
} }
return (const char *)(self->buf.buf) + pos * v1_hdrsize; return (const char *)(self->buf.buf) + pos * v1_hdrsize;
} }
/* /*
* Get parents of the given rev. * Get parents of the given rev.
* *
* The specified rev must be valid and must not be nullrev. A returned * The specified rev must be valid and must not be nullrev. A returned
* parent revision may be nullrev, but is guaranteed to be in valid range. * parent revision may be nullrev, but is guaranteed to be in valid range.
*/ */
static inline int index_get_parents(indexObject *self, Py_ssize_t rev, int *ps, static inline int index_get_parents(indexObject *self, Py_ssize_t rev, int *ps,
int maxrev) int maxrev)
{ {
if (rev >= self->length) {
long tmp;
PyObject *tuple =
PyList_GET_ITEM(self->added, rev - self->length);
if (!pylong_to_long(PyTuple_GET_ITEM(tuple, 5), &tmp)) {
return -1;
}
ps[0] = (int)tmp;
if (!pylong_to_long(PyTuple_GET_ITEM(tuple, 6), &tmp)) {
return -1;
}
ps[1] = (int)tmp;
} else {
const char *data = index_deref(self, rev); const char *data = index_deref(self, rev);
ps[0] = getbe32(data + 24); ps[0] = getbe32(data + 24);
ps[1] = getbe32(data + 28); ps[1] = getbe32(data + 28);
}
/* If index file is corrupted, ps[] may point to invalid revisions. So /* If index file is corrupted, ps[] may point to invalid revisions. So
* there is a risk of buffer overflow to trust them unconditionally. */ * there is a risk of buffer overflow to trust them unconditionally. */
if (ps[0] < -1 || ps[0] > maxrev || ps[1] < -1 || ps[1] > maxrev) { if (ps[0] < -1 || ps[0] > maxrev || ps[1] < -1 || ps[1] > maxrev) {
PyErr_SetString(PyExc_ValueError, "parent out of range"); PyErr_SetString(PyExc_ValueError, "parent out of range");
return -1; return -1;
} }
return 0; return 0;
} }
return 0; return 0;
} else { } else {
return index_get_parents((indexObject *)op, rev, ps, tiprev); return index_get_parents((indexObject *)op, rev, ps, tiprev);
} }
} }
static inline int64_t index_get_start(indexObject *self, Py_ssize_t rev) static inline int64_t index_get_start(indexObject *self, Py_ssize_t rev)
{ {
const char *data;
uint64_t offset; uint64_t offset;
if (rev == nullrev) {
if (rev == nullrev)
return 0; return 0;
}
if (rev >= self->length) { data = index_deref(self, rev);
PyObject *tuple;
PyObject *pylong;
PY_LONG_LONG tmp;
tuple = PyList_GET_ITEM(self->added, rev - self->length);
pylong = PyTuple_GET_ITEM(tuple, 0);
tmp = PyLong_AsLongLong(pylong);
if (tmp == -1 && PyErr_Occurred()) {
return -1;
}
if (tmp < 0) {
PyErr_Format(PyExc_OverflowError,
"revlog entry size out of bound (%lld)",
(long long)tmp);
return -1;
}
offset = (uint64_t)tmp;
} else {
const char *data = index_deref(self, rev);
offset = getbe32(data + 4); offset = getbe32(data + 4);
if (rev == 0) { if (rev == 0) {
/* mask out version number for the first entry */ /* mask out version number for the first entry */
offset &= 0xFFFF; offset &= 0xFFFF;
} else { } else {
uint32_t offset_high = getbe32(data); uint32_t offset_high = getbe32(data);
offset |= ((uint64_t)offset_high) << 32; offset |= ((uint64_t)offset_high) << 32;
} }
}
return (int64_t)(offset >> 16); return (int64_t)(offset >> 16);
} }
static inline int index_get_length(indexObject *self, Py_ssize_t rev) static inline int index_get_length(indexObject *self, Py_ssize_t rev)
{ {
if (rev == nullrev) { const char *data;
int tmp;
if (rev == nullrev)
return 0; return 0;
}
if (rev >= self->length) { data = index_deref(self, rev);
PyObject *tuple;
PyObject *pylong; tmp = (int)getbe32(data + 8);
long ret;
tuple = PyList_GET_ITEM(self->added, rev - self->length);
pylong = PyTuple_GET_ITEM(tuple, 1);
ret = PyInt_AsLong(pylong);
if (ret == -1 && PyErr_Occurred()) {
return -1;
}
if (ret < 0 || ret > (long)INT_MAX) {
PyErr_Format(PyExc_OverflowError,
"revlog entry size out of bound (%ld)",
ret);
return -1;
}
return (int)ret;
} else {
const char *data = index_deref(self, rev);
int tmp = (int)getbe32(data + 8);
if (tmp < 0) { if (tmp < 0) {
PyErr_Format(PyExc_OverflowError, PyErr_Format(PyExc_OverflowError,
"revlog entry size out of bound (%d)", "revlog entry size out of bound (%d)", tmp);
tmp);
return -1; return -1;
} }
return tmp; return tmp;
} }
}
/* /*
* RevlogNG format (all in big endian, data may be inlined): * RevlogNG format (all in big endian, data may be inlined):
* 6 bytes: offset * 6 bytes: offset
* 2 bytes: flags * 2 bytes: flags
* 4 bytes: compressed length * 4 bytes: compressed length
* 4 bytes: uncompressed length * 4 bytes: uncompressed length
* 4 bytes: base revision * 4 bytes: base revision
return nullentry; return nullentry;
} }
if (pos < 0 || pos >= length) { if (pos < 0 || pos >= length) {
PyErr_SetString(PyExc_IndexError, "revlog index out of range"); PyErr_SetString(PyExc_IndexError, "revlog index out of range");
return NULL; return NULL;
} }
if (pos >= self->length) {
PyObject *obj;
obj = PyList_GET_ITEM(self->added, pos - self->length);
Py_INCREF(obj);
return obj;
}
data = index_deref(self, pos); data = index_deref(self, pos);
if (data == NULL) if (data == NULL)
return NULL; return NULL;
offset_flags = getbe32(data + 4); offset_flags = getbe32(data + 4);
if (pos == 0) /* mask out version number for the first entry */ /*
* The first entry on-disk needs the version number masked out,
* but this doesn't apply if entries are added to an empty index.
*/
if (self->length && pos == 0)
offset_flags &= 0xFFFF; offset_flags &= 0xFFFF;
else { else {
uint32_t offset_high = getbe32(data); uint32_t offset_high = getbe32(data);
offset_flags |= ((uint64_t)offset_high) << 32; offset_flags |= ((uint64_t)offset_high) << 32;
} }
comp_len = getbe32(data + 8); comp_len = getbe32(data + 8);
uncomp_len = getbe32(data + 12); uncomp_len = getbe32(data + 12);
const char *data; const char *data;
if (pos == nullrev) if (pos == nullrev)
return nullid; return nullid;
if (pos >= length) if (pos >= length)
return NULL; return NULL;
if (pos >= self->length) {
PyObject *tuple, *str;
tuple = PyList_GET_ITEM(self->added, pos - self->length);
str = PyTuple_GetItem(tuple, 7);
return str ? PyBytes_AS_STRING(str) : NULL;
}
data = index_deref(self, pos); data = index_deref(self, pos);
return data ? data + 32 : NULL; return data ? data + 32 : NULL;
} }
/* /*
* Return the 20-byte SHA of the node corresponding to the given rev. The * Return the 20-byte SHA of the node corresponding to the given rev. The
* rev is assumed to be existing. If not, an exception is set. * rev is assumed to be existing. If not, an exception is set.
*/ */
if (nodelen == 20) if (nodelen == 20)
return 0; return 0;
PyErr_SetString(PyExc_ValueError, "20-byte hash required"); PyErr_SetString(PyExc_ValueError, "20-byte hash required");
return -1; return -1;
} }
static PyObject *index_append(indexObject *self, PyObject *obj) static PyObject *index_append(indexObject *self, PyObject *obj)
{ {
char *node; unsigned long offset_flags;
Py_ssize_t len; int rev, comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
Py_ssize_t c_node_id_len;
const char *c_node_id;
char *data;
if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) { if (!PyArg_ParseTuple(obj, tuple_format, &offset_flags, &comp_len,
&uncomp_len, &base_rev, &link_rev, &parent_1,
&parent_2, &c_node_id, &c_node_id_len)) {
PyErr_SetString(PyExc_TypeError, "8-tuple required"); PyErr_SetString(PyExc_TypeError, "8-tuple required");
return NULL; return NULL;
} }
if (c_node_id_len != 20 && c_node_id_len != 32) {
if (node_check(PyTuple_GET_ITEM(obj, 7), &node) == -1) PyErr_SetString(PyExc_TypeError, "invalid node");
return NULL;
len = index_length(self);
if (self->added == NULL) {
self->added = PyList_New(0);
if (self->added == NULL)
return NULL; return NULL;
} }
if (PyList_Append(self->added, obj) == -1) if (self->new_length == self->added_length) {
return NULL; size_t new_added_length =
self->added_length ? self->added_length * 2 : 4096;
void *new_added =
PyMem_Realloc(self->added, new_added_length * v1_hdrsize);
if (!new_added)
return PyErr_NoMemory();
self->added = new_added;
self->added_length = new_added_length;
}
rev = self->length + self->new_length;
data = self->added + v1_hdrsize * self->new_length++;
putbe32(offset_flags >> 32, data);
putbe32(offset_flags & 0xffffffffU, data + 4);
putbe32(comp_len, data + 8);
putbe32(uncomp_len, data + 12);
putbe32(base_rev, data + 16);
putbe32(link_rev, data + 20);
putbe32(parent_1, data + 24);
putbe32(parent_2, data + 28);
memcpy(data + 32, c_node_id, c_node_id_len);
memset(data + 32 + c_node_id_len, 0, 32 - c_node_id_len);
if (self->ntinitialized) if (self->ntinitialized)
nt_insert(&self->nt, node, (int)len); nt_insert(&self->nt, c_node_id, rev);
Py_CLEAR(self->headrevs); Py_CLEAR(self->headrevs);
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 (!s || !t) \ if (!s || !t) \
goto bail; \ goto bail; \
if (PyDict_SetItem(obj, s, t) == -1) \ if (PyDict_SetItem(obj, s, t) == -1) \
goto bail; \ goto bail; \
Py_CLEAR(s); \ Py_CLEAR(s); \
Py_CLEAR(t); \ Py_CLEAR(t); \
} while (0) } while (0)
if (self->added) { if (self->added_length)
Py_ssize_t len = PyList_GET_SIZE(self->added); istat(new_length, "index entries added");
s = PyBytes_FromString("index entries added");
t = PyInt_FromSsize_t(len);
if (!s || !t)
goto bail;
if (PyDict_SetItem(obj, s, t) == -1)
goto bail;
Py_CLEAR(s);
Py_CLEAR(t);
}
if (self->raw_length != self->length)
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->ntinitialized) { if (self->ntinitialized) {
istat(nt.capacity, "node trie capacity"); istat(nt.capacity, "node trie capacity");
istat(nt.depth, "node trie depth"); istat(nt.depth, "node trie depth");
istat(nt.length, "node trie count"); istat(nt.length, "node trie count");
* *
* Callers must ensure that rev >= 0 or illegal memory access may occur. * Callers must ensure that rev >= 0 or illegal memory access may occur.
*/ */
static inline int index_baserev(indexObject *self, int rev) static inline int index_baserev(indexObject *self, int rev)
{ {
const char *data; const char *data;
int result; int result;
if (rev >= self->length) {
PyObject *tuple =
PyList_GET_ITEM(self->added, rev - self->length);
long ret;
if (!pylong_to_long(PyTuple_GET_ITEM(tuple, 3), &ret)) {
return -2;
}
result = (int)ret;
} else {
data = index_deref(self, rev); data = index_deref(self, rev);
if (data == NULL) { if (data == NULL)
return -2; return -2;
}
result = getbe32(data + 16); result = getbe32(data + 16);
}
if (result > rev) { if (result > rev) {
PyErr_Format( PyErr_Format(
PyExc_ValueError, PyExc_ValueError,
"corrupted revlog, revision base above revision: %d, %d", "corrupted revlog, revision base above revision: %d, %d",
rev, result); rev, result);
return -2; return -2;
} }
if (result < -1) { if (result < -1) {
0, /* tp_dictoffset */ 0, /* tp_dictoffset */
(initproc)ntobj_init, /* tp_init */ (initproc)ntobj_init, /* tp_init */
0, /* tp_alloc */ 0, /* tp_alloc */
}; };
static int index_init_nt(indexObject *self) static int index_init_nt(indexObject *self)
{ {
if (!self->ntinitialized) { if (!self->ntinitialized) {
if (nt_init(&self->nt, self, (int)self->raw_length) == -1) { if (nt_init(&self->nt, self, (int)self->length) == -1) {
nt_dealloc(&self->nt); nt_dealloc(&self->nt);
return -1; return -1;
} }
if (nt_insert(&self->nt, nullid, -1) == -1) { if (nt_insert(&self->nt, nullid, -1) == -1) {
nt_dealloc(&self->nt); nt_dealloc(&self->nt);
return -1; return -1;
} }
self->ntinitialized = 1; self->ntinitialized = 1;
return ret; return ret;
} }
/* /*
* Invalidate any trie entries introduced by added revs. * Invalidate any trie entries introduced by added revs.
*/ */
static void index_invalidate_added(indexObject *self, Py_ssize_t start) static void index_invalidate_added(indexObject *self, Py_ssize_t start)
{ {
Py_ssize_t i, len = PyList_GET_SIZE(self->added); Py_ssize_t i, len;
for (i = start; i < len; i++) { len = self->length + self->new_length;
PyObject *tuple = PyList_GET_ITEM(self->added, i); i = start - self->length;
PyObject *node = PyTuple_GET_ITEM(tuple, 7); if (i < 0)
return;
nt_delete_node(&self->nt, PyBytes_AS_STRING(node)); for (i = start; i < len; i++)
} nt_delete_node(&self->nt, index_deref(self, i) + 32);
if (start == 0) self->new_length = start - self->length;
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
* range. * range.
*/ */
static int index_slice_del(indexObject *self, PyObject *item) static int index_slice_del(indexObject *self, PyObject *item)
{ {
for (i = start; i < self->length; i++) { for (i = start; i < self->length; 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->nt, node); nt_delete_node(&self->nt, node);
} }
if (self->added) if (self->new_length)
index_invalidate_added(self, 0); index_invalidate_added(self, self->length);
if (self->ntrev > start) if (self->ntrev > start)
self->ntrev = (int)start; self->ntrev = (int)start;
} else if (self->added) { } else if (self->new_length) {
Py_CLEAR(self->added); self->new_length = 0;
} }
self->length = start; self->length = start;
if (start < self->raw_length)
self->raw_length = start;
goto done; goto done;
} }
if (self->ntinitialized) { if (self->ntinitialized) {
index_invalidate_added(self, start - self->length); index_invalidate_added(self, start);
if (self->ntrev > start) if (self->ntrev > start)
self->ntrev = (int)start; self->ntrev = (int)start;
} else {
self->new_length = start - self->length;
} }
if (self->added)
ret = PyList_SetSlice(self->added, start - self->length,
PyList_GET_SIZE(self->added), NULL);
done: done:
Py_CLEAR(self->headrevs); Py_CLEAR(self->headrevs);
return ret; return ret;
} }
/* /*
* Supported ops: * Supported ops:
* *
static int index_init(indexObject *self, PyObject *args) static int index_init(indexObject *self, PyObject *args)
{ {
PyObject *data_obj, *inlined_obj; PyObject *data_obj, *inlined_obj;
Py_ssize_t size; Py_ssize_t size;
/* Initialize before argument-checking to avoid index_dealloc() crash. /* Initialize before argument-checking to avoid index_dealloc() crash.
*/ */
self->raw_length = 0;
self->added = NULL; self->added = NULL;
self->new_length = 0;
self->added_length = 0;
self->data = NULL; self->data = NULL;
memset(&self->buf, 0, sizeof(self->buf)); memset(&self->buf, 0, sizeof(self->buf));
self->headrevs = NULL; self->headrevs = NULL;
self->filteredrevs = Py_None; self->filteredrevs = Py_None;
Py_INCREF(Py_None); Py_INCREF(Py_None);
self->ntinitialized = 0; self->ntinitialized = 0;
self->offsets = NULL; self->offsets = NULL;
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;
self->raw_length = len;
self->length = len; self->length = len;
} else { } else {
if (size % v1_hdrsize) { if (size % v1_hdrsize) {
PyErr_SetString(PyExc_ValueError, "corrupt index file"); PyErr_SetString(PyExc_ValueError, "corrupt index file");
goto bail; goto bail;
} }
self->raw_length = size / v1_hdrsize; self->length = size / v1_hdrsize;
self->length = self->raw_length;
} }
return 0; return 0;
bail: bail:
return -1; return -1;
} }
static PyObject *index_nodemap(indexObject *self) static PyObject *index_nodemap(indexObject *self)
{ {
_index_clearcaches(self); _index_clearcaches(self);
Py_XDECREF(self->filteredrevs); Py_XDECREF(self->filteredrevs);
if (self->buf.buf) { if (self->buf.buf) {
PyBuffer_Release(&self->buf); PyBuffer_Release(&self->buf);
memset(&self->buf, 0, sizeof(self->buf)); memset(&self->buf, 0, sizeof(self->buf));
} }
Py_XDECREF(self->data); Py_XDECREF(self->data);
Py_XDECREF(self->added); PyMem_Free(self->added);
PyObject_Del(self); PyObject_Del(self);
} }
static PySequenceMethods index_sequence_methods = { static PySequenceMethods index_sequence_methods = {
(lenfunc)index_length, /* sq_length */ (lenfunc)index_length, /* sq_length */
0, /* sq_concat */ 0, /* sq_concat */
0, /* sq_repeat */ 0, /* sq_repeat */
(ssizeargfunc)index_get, /* sq_item */ (ssizeargfunc)index_get, /* sq_item */

mercurial/pure/parsers.py

self.__dict__.pop('_nodemap', None) self.__dict__.pop('_nodemap', None)
def __len__(self): def __len__(self):
return self._lgt + len(self._extra) return self._lgt + len(self._extra)
def append(self, tup): def append(self, tup):
if '_nodemap' in vars(self): if '_nodemap' in vars(self):
self._nodemap[tup[7]] = len(self) self._nodemap[tup[7]] = len(self)
self._extra.append(tup) data = _pack(indexformatng, *tup)
self._extra.append(data)
def _check_index(self, i): def _check_index(self, i):
if not isinstance(i, int): if not isinstance(i, int):
raise TypeError(b"expecting int indexes") raise TypeError(b"expecting int indexes")
if i < 0 or i >= len(self): if i < 0 or i >= len(self):
raise IndexError raise IndexError
def __getitem__(self, i): def __getitem__(self, i):
if i == -1: if i == -1:
return nullitem return nullitem
self._check_index(i) self._check_index(i)
if i >= self._lgt: if i >= self._lgt:
return self._extra[i - self._lgt] data = self._extra[i - self._lgt]
else:
index = self._calculate_index(i) index = self._calculate_index(i)
r = struct.unpack(indexformatng, self._data[index : index + indexsize]) data = self._data[index : index + indexsize]
if i == 0: r = _unpack(indexformatng, data)
e = list(r) if self._lgt and i == 0:
type = gettype(e[0]) r = (offset_type(0, gettype(r[0])),) + r[1:]
e[0] = offset_type(0, type)
return tuple(e)
return r return r
class IndexObject(BaseIndexObject): class IndexObject(BaseIndexObject):
def __init__(self, data): def __init__(self, data):
assert len(data) % indexsize == 0 assert len(data) % indexsize == 0
self._data = data self._data = data
self._lgt = len(data) // indexsize self._lgt = len(data) // indexsize