[PATCH 03 of 22] radixlink: add C implementation
Gregory Szorc
gregory.szorc at gmail.com
Tue Jun 6 01:58:49 EDT 2017
On Sun, Jun 4, 2017 at 4:59 PM, Jun Wu <quark at fb.com> wrote:
> # HG changeset patch
> # User Jun Wu <quark at fb.com>
> # Date 1496550656 25200
> # Sat Jun 03 21:30:56 2017 -0700
> # Node ID d492628229c58f8417a8b5925a614e26a16465af
> # Parent e8e8d713e4b774f6894ee65723e7fdc12bf8a101
> # Available At https://bitbucket.org/quark-zju/hg-draft
> # hg pull https://bitbucket.org/quark-zju/hg-draft -r
> d492628229c5
> radixlink: add C implementation
>
Only a very quick review. Nothing glaringly wrong from a CPython
perspective. Although a more thorough examination is needed.
On reading this code, I was once again reminded of Mercurial's style of
omitting braces from one-line conditional blocks. I detest this style. See
Apple's "goto fail" bug for why. I would prefer we not continue that
practice in new code.
It is somewhat weird seeing the C implementation so early in the series.
I'd favor deferring this patch then landing the C implementation after the
feature is implemented. That way we can introduce the C code along with
perf numbers and more robust test coverage. But if it's ready, it's ready:
I don't want to cause too much work for you to refactor.
>
> This patch implements the radixlink class in C.
>
> The core algorithm and data structure was written in a separated pure C
> file
> so it could be reused outside Python environment.
>
> Partial examples of reading and writing in pure C:
>
> radixlink_buffer_t index = readfile("prefix");
> radixlink_buffer_t link = readfile("prefix.l");
>
> /* read */
> uint32_t loff, v;
> radixlink_buffer_t key = { "key", 3 };
> if (radixlink_index_find(&index, &key, &loff) != 0)
> abort();
> while (loff) {
> if (radixlink_link_read(&link, &loff, &v) != 0)
> abort();
> printf(" value: %u\n", (unsigned) v);
> }
>
> /* insert (key, value) */
> static void resize(radixlink_buffer_t *buf, uint32_t newsize) {
> void *p = realloc(buf->buf, newsize);
> if (p) { buf->buf = p; buf->size = newsize; }
> }
> uint32_t loff, ioff;
> if (radixlink_index_findorcreate(index, key, &loff, &ioff, resize) !=
> 0)
> abort();
> if (radixlink_link_append(link, &loff, value, resize) != 0)
> abort();
> if (radixlink_index_writelink(index, ioff, loff) != 0)
> abort();
>
> "valgrind --tool=memcheck --leak-check=yes python2 test-radixlink.py" does
> not report any possible leak with stack containing radixlink.c [1].
>
> [1]: python2 was a debug build of 2.7.13: --with-pydebug --without-pymalloc
> --with-valgrind
>
> diff --git a/mercurial/cext/radixlink.c b/mercurial/cext/radixlink.c
> new file mode 100644
> --- /dev/null
> +++ b/mercurial/cext/radixlink.c
> @@ -0,0 +1,314 @@
> +/* radixlink.c - Python wrapper for C radixlink implementation
> + *
> + * Copyright 2017 Facebook, Inc.
> + *
> + * This software may be used and distributed according to the terms of the
> + * GNU General Public License version 2 or any later version. */
> +
> +#include <Python.h>
> +#include <stdio.h>
> +
> +#include "radixlink.h"
> +
> +typedef struct {
> + PyObject_HEAD
> + radixlink_buffer_t data;
> +} radixlinkObject;
> +
> +static const uint32_t MIN_DATA_SIZE = 76; /* header (4B) + radix-entry
> (72B) */
> +
> +static int radixlink_contains(radixlinkObject *self, PyObject *keyobj)
> +{
> + radixlink_buffer_t k;
> + Py_ssize_t klen = 0;
> + uint32_t loff = 0;
> +
> + if (PyBytes_AsStringAndSize(keyobj, (char **)&k.buf, &klen) == -1)
> + return -1;
> + k.size = (uint32_t)klen;
> + if (radixlink_index_find(&self->data, &k, &loff) == -1)
> + return -1;
> + return loff > 0;
> +}
> +
> +static PyObject *radixlink_getitem(radixlinkObject *self, PyObject
> *keyobj)
> +{
> + radixlink_buffer_t k;
> + Py_ssize_t klen = 0;
> + PyObject *pyvalues = NULL;
> + uint32_t loff = 0;
> +
> + if (PyBytes_AsStringAndSize(keyobj, (char **)&k.buf, &klen) == -1)
> + return NULL;
> + k.size = (uint32_t)klen;
> + if (radixlink_index_find(&self->data, &k, &loff) == -1)
> + return NULL;
> + if (loff == 0)
> + return PyErr_Format(PyExc_KeyError, "No such entry");
> +
> + pyvalues = PyList_New(0);
>
Appending lists can be relatively expensive. Do you think it is worth
scanning the linked list so we can pre-allocate enough slots in the PyList?
> + if (!pyvalues)
> + goto bail;
>
This can just return NULL. Then you can change bail to Py_DECREF since
pyvalues is guaranteed to be !NULL.
> +
> + while (loff) {
> + PyObject *pyvalue;
> + uint32_t value;
> + int r;
> + if (radixlink_link_read(&self->data, &loff, &value) != 0)
> + goto bail;
> + pyvalue = PyInt_FromLong((long)value);
> + if (!pyvalue)
> + goto bail;
> + r = PyList_Append(pyvalues, pyvalue);
> + Py_DECREF(pyvalue);
> + if (r == -1)
> + goto bail;
> + }
> + return pyvalues;
> +bail:
> + Py_XDECREF(pyvalues);
> + return NULL;
> +}
> +
> +static void resize(radixlink_buffer_t *buf, uint32_t newsize) {
> + void *p = PyMem_Realloc(buf->buf, (size_t)newsize);
> + if (p) {
> + buf->buf = p;
> + buf->size = newsize;
> + }
>
This function nor callers appear to handle the case where PyMem_Realloc
fails.
> +}
> +
> +static PyObject *radixlink_insert(radixlinkObject *self, PyObject *args)
> +{
> + radixlink_buffer_t k;
> + Py_ssize_t klen = 0;
> + unsigned int v;
> + uint32_t loff, ioff;
> +
> + if (!PyArg_ParseTuple(args, "s#I", &k.buf, &klen, &v))
>
You'll want to conditionalize this to use y# on Python 3 to limit to bytes
types.
> + return NULL;
> + k.size = (uint32_t)klen;
> +
> + if (radixlink_index_findorcreate(&self->data, &k, &loff, &ioff,
> resize)
> + != 0)
> + return NULL;
> + if (radixlink_link_append(&self->data, &loff, (uint32_t)v,
> resize) != 0)
> + return NULL;
> + if (radixlink_index_writelink(&self->data, ioff, loff) != 0)
> + return NULL;
> + Py_RETURN_NONE;
> +}
> +
> +static PyObject *radixlink_getsourceoftruthsize(radixlinkObject *self,
> + void *context)
> +{
> + uint32_t v;
> + (void)context;
>
What's this argument for? Future patch?
> + if (self->data.size < 4)
> + return NULL;
> + v = getbe32((const char *)self->data.buf);
> + return PyInt_FromLong((long)v);
> +}
> +
> +static int radixlink_setsourceoftruthsize(radixlinkObject *self,
> + PyObject *value, void *context)
> +{
> + uint32_t origv;
> + long v;
> + (void)context;
> + v = PyInt_AsLong(value);
> + if (self->data.size < 4 || v < 0)
> + return -1;
> + origv = getbe32((const char *)self->data.buf);
> + if (origv != (uint32_t)v)
> + putbe32((uint32_t)v, (char *)self->data.buf);
> + return 0;
> +}
> +
> +static PyObject *radixlink_getdata(radixlinkObject *self, void *context)
> +{
> + (void)context;
> + return PyBytes_FromStringAndSize((const char *)self->data.buf,
> + (Py_ssize_t)self->data.size);
> +}
> +static int radixlink_setdata(radixlinkObject *self, PyObject *value,
> + void *context)
> +{
> + radixlink_buffer_t buf = { NULL, 0 };
> + Py_buffer view = { NULL };
> + (void)context;
> + if (value == NULL || PyObject_Not(value)) {
> + /* minimal empty buffer */
> + view.len = MIN_DATA_SIZE;
> + view.buf = NULL;
> + } else {
> + /* copy from a buffer object */
> + if (!PyObject_CheckBuffer(value)) {
> + PyErr_SetString(PyExc_TypeError, "need a buffer");
> + goto bail;
> + }
> + if (PyObject_GetBuffer(value, &view, PyBUF_SIMPLE) != 0)
> + goto bail;
> + }
> + buf.buf = PyMem_Malloc((size_t)view.len);
> + if (!buf.buf) {
> + PyErr_SetNone(PyExc_MemoryError);
> + goto bail;
> + }
> + if (view.buf) {
> + memcpy(buf.buf, view.buf, (size_t)view.len);
> + PyBuffer_Release(&view);
> + } else {
> + memset(buf.buf, 0, (size_t)view.len);
> + }
> + buf.size = (uint32_t)view.len;
> + PyMem_Free(self->data.buf);
> + self->data = buf;
> + return 0;
> +bail:
> + if (view.buf)
> + PyBuffer_Release(&view);
> + return -1;
> +
> +}
> +
> +static Py_ssize_t radixlink_length(radixlinkObject *self)
> +{
> + return (Py_ssize_t)self->data.size;
> +}
> +
> +static int radixlink_init(radixlinkObject *self, PyObject *args)
> +{
> + PyObject *data = NULL;
> + self->data.buf = NULL;
> + self->data.size = 0;
> +
> + if (!PyArg_ParseTuple(args, "|O", &data))
> + return -1;
> +
> + return radixlink_setdata(self, data, NULL);
> +}
> +
> +static void radixlink_dealloc(radixlinkObject *self)
> +{
> + PyMem_Free(self->data.buf);
> + self->ob_type->tp_free((PyObject *)self);
>
Does Py_TPFLAGS_BASETYPE need to be set? If not, don't bother and call
PyObject_Del() instead.
> +}
> +
> +static PySequenceMethods radixlink_sequence_methods = {
> + (lenfunc)radixlink_length, /* sq_length */
> + 0, /* sq_concat */
> + 0, /* sq_repeat */
> + 0, /* sq_item */
> + 0, /* sq_slice */
> + 0, /* sq_ass_item */
> + 0, /* sq_ass_slice */
> + (objobjproc)radixlink_contains, /* sq_contains */
> + 0, /* sq_inplace_concat */
> + 0, /* sq_inplace_repeat */
> +};
> +
> +static PyMappingMethods radixlink_mapping_methods = {
> + (lenfunc)radixlink_length, /* mp_length */
> + (binaryfunc)radixlink_getitem, /* mp_subscript */
> + NULL, /* mp_ass_subscript */
> +};
> +
> +static PyMethodDef radixlink_methods[] = {
> + {"insert", (PyCFunction)radixlink_insert, METH_VARARGS,
> + "insert value (uint32) at the beginning of the list for given
> key\n"},
> + {NULL},
> +};
> +
> +static PyGetSetDef radixlink_getset[] = {
> + {"sourceoftruthsize", (getter)radixlink_getsourceoftruthsize,
> + (setter)radixlink_setsourceoftruthsize, "sourceoftruthsize",
> NULL},
> + {"data", (getter)radixlink_getdata, (setter)radixlink_setdata,
> "data",
> + NULL},
> + {NULL},
> +};
> +
> +static PyTypeObject radixlinkType = {
> + PyObject_HEAD_INIT(NULL)
> + 0, /* ob_size */
> + "radixlink.radixlink", /* tp_name */
>
"mercurial.radixlink.radixlink" (yes, we make this mistake elsewhere).
> + sizeof(radixlinkObject), /* tp_basicsize */
> + 0, /* tp_itemsize */
> + (destructor)radixlink_dealloc, /* tp_dealloc */
> + 0, /* tp_print */
> + 0, /* tp_getattr */
> + 0, /* tp_setattr */
> + 0, /* tp_compare */
> + 0, /* tp_repr */
> + 0, /* tp_as_number */
> + &radixlink_sequence_methods, /* tp_as_sequence */
> + &radixlink_mapping_methods, /* tp_as_mapping */
> + 0, /* tp_hash */
> + 0, /* tp_call */
> + 0, /* tp_str */
> + 0, /* tp_getattro */
> + 0, /* tp_setattro */
> + 0, /* tp_as_buffer */
> + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /* tp_flags */
> + "A radixlink object", /* tp_doc */
> + 0, /* tp_traverse */
> + 0, /* tp_clear */
> + 0, /* tp_richcompare */
> + 0, /* tp_weaklistoffset */
> + 0, /* tp_iter */
> + 0, /* tp_iternext */
> + radixlink_methods, /* tp_methods */
> + 0, /* tp_members */
> + radixlink_getset, /* tp_getset */
> + 0, /* tp_base */
> + 0, /* tp_dict */
> + 0, /* tp_descr_get */
> + 0, /* tp_descr_set */
> + 0, /* tp_dictoffset */
> + (initproc)radixlink_init, /* tp_init */
> + 0, /* tp_alloc */
> +};
> +
> +static PyMethodDef methods[] = {{NULL}};
> +
> +static char radixlink_doc[] = ("multimap<bytes, uint32> based on radix
> tree "
> + "and linked list\n");
> +
> +static const int version = 1;
> +
> +static int postinit(PyObject *m)
> +{
> + Py_INCREF(&radixlinkType);
> + radixlinkType.tp_new = PyType_GenericNew;
>
Pretty sure you can assign this directly in PyTypeObject. The tp_new slot
is immediately after tp_alloc. I'm not sure why you would defer doing this,
but CPython itself is inconsistent. So maybe I'm missing something.
> + if (PyType_Ready(&radixlinkType) < 0)
> + return -1;
> + if (PyModule_AddObject(m, "radixlink", (PyObject *)&radixlinkType)
> != 0)
> + return -1;
> + if (PyModule_AddIntConstant(m, "version", version) != 0)
> + return -1;
> + return 0;
> +}
> +
> +#ifdef IS_PY3K
> +static struct PyModuleDef radixlink_module = {
> + PyModuleDef_HEAD_INIT,
> + "radixlink",
> + radixlink_doc,
> + -1,
> + methods,
> +};
> +
> +PyMODINIT_FUNC PyInit_radixlink(void)
> +{
> + PyObject *m = PyModule_Create(&radixlink_module);
> + if (postinit(m) != 0)
> + return NULL;
> + return m;
> +}
> +#else
> +PyMODINIT_FUNC initradixlink(void)
> +{
> + PyObject *m = Py_InitModule3("radixlink", methods, radixlink_doc);
> + (void)postinit(m);
> +}
> +#endif
> diff --git a/mercurial/policy.py b/mercurial/policy.py
> --- a/mercurial/policy.py
> +++ b/mercurial/policy.py
> @@ -77,4 +77,5 @@ def _importfrom(pkgname, modname):
> (r'cext', r'osutil'): 1,
> (r'cext', r'parsers'): 1,
> + (r'cext', r'radixlink'): 1,
> }
>
> diff --git a/mercurial/radixlink.c b/mercurial/radixlink.c
> new file mode 100644
> --- /dev/null
> +++ b/mercurial/radixlink.c
>
I suspect we'll want to put all C code in mercurial/cext. Althought I'm not
100% sure if we want to put a wall between pure C and Python C or what.
> @@ -0,0 +1,270 @@
> +/* radixlink.c - on-disk radixtree index pointing to linked list data
> + *
> + * Copyright 2017 Facebook, Inc.
> + *
> + * This software may be used and distributed according to the terms of the
> + * GNU General Public License version 2 or any later version. */
> +
> +#include <assert.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include "radixlink.h"
> +
> +static const uint32_t INDEX_HEADER_SIZE = 4;
> +static const uint32_t INDEX_KEY_SIZE = 4;
> +static const uint32_t INDEX_OFFSET_SIZE = 4;
> +static const uint32_t LINK_OFFSET_SIZE = 4;
> +static const uint32_t LINK_VALUE_SIZE = 4;
> +
> +/* INDEX_KEY_SIZE + LINK_OFFSET_SIZE + INDEX_OFFSET_SIZE * 16 */
> +static const uint32_t INDEX_RADIX_ENTRY_SIZE = 72;
> +
> +/* Return -1 on buffer overflow, or write *pvalue (if not NULL) and
> return 0 */
> +static inline int safereadu32(radixlink_buffer_t *buf, uint32_t offset,
> + uint32_t *pvalue)
> +{
> + assert(buf);
> + if (pvalue == NULL)
> + return 0;
> + if (buf->size < offset + 4)
> + return -1;
> + *pvalue = getbe32((const char *)(buf->buf + offset));
> + return 0;
> +}
> +
> +/* Return -1 on buffer overflow, or write *buf and return 0 */
> +static inline int safewriteu32(radixlink_buffer_t *buf, uint32_t offset,
> + uint32_t value)
> +{
> + assert(buf);
> + if (buf->size < offset + 4)
> + return -1;
> + putbe32(value, (char *)(buf->buf + offset));
> + return 0;
> +}
> +
> +/* Get base16 from a base256 key. Caller responsible for memory safety. */
> +static inline uint8_t getb16(uint8_t b256[], uint32_t index)
> +{
> + uint8_t v = b256[index / 2];
> + return index & 1 ? (v & 0xf) : (v >> 4);
> +}
> +
> +/* Compare base256 and base16 buffer. Return 0 on equal, -1 otherwise.
> + * Caller responsible for memory boundary check. */
> +static inline int b16cmp(radixlink_buffer_t *b256, uint32_t b256offset,
> + radixlink_buffer_t *b16)
> +{
> + uint32_t i;
> + assert(b256 && b16);
> + if (b256->size * 2 != b16->size + b256offset)
> + return -1;
> + for (i = 0; i < b16->size; ++i) {
> + uint8_t v = getb16(b256->buf, i + b256offset);
> + if (v != b16->buf[i])
> + return -1;
> + }
> + return 0;
> +}
> +
> +static inline int readindexentry(radixlink_buffer_t *index, uint32_t
> offset,
> + uint32_t *pklen, uint32_t *plinkoffset, uint32_t
> *pindexoffset)
> +{
> + uint32_t poff = offset + INDEX_KEY_SIZE;
> + /* index-entry := radix-entry | leaf-entry
> + radix-entry := '\0' * 4 + link-offset + index-offset (4B) * 16
> + leaf-entry := key-length (4B, > 0) + link-offset + key */
> + if (safereadu32(index, offset, pklen) != 0)
> + return -1;
> + if (safereadu32(index, poff, plinkoffset) != 0)
> + return -1;
> + if (pindexoffset != NULL)
> + *pindexoffset = poff;
> + return 0;
> +}
> +
> +static inline int splitleaf(radixlink_buffer_t *index,
> + uint32_t ioff, uint32_t klen, uint32_t loff,
> + radixlink_resize_func resize)
> +{
> + uint32_t noff, size, koff;
> + uint8_t b16;
> +
> + /* require klen, loff to avoid reading from index again */
> + assert(klen > 0);
> + koff = ioff + INDEX_KEY_SIZE + LINK_OFFSET_SIZE;
> + noff = index->size; /* new leaf entry offset */
> + size = INDEX_KEY_SIZE + LINK_OFFSET_SIZE + klen - 1; /* entry size
> */
> + if (size < INDEX_RADIX_ENTRY_SIZE)
> + size = INDEX_RADIX_ENTRY_SIZE;
> +
> + resize(index, noff + size);
> + if (index->size < noff + size)
> + return -1;
> + memset(index->buf + noff, 0, size);
> +
> + /* copy remaining key to new location */
> + putbe32(klen - 1, (char *)(index->buf + noff));
> + putbe32(loff, (char *)(index->buf + noff + INDEX_KEY_SIZE));
> + memcpy(index->buf + noff + INDEX_KEY_SIZE + LINK_OFFSET_SIZE,
> + index->buf + koff + 1, klen - 1);
> + b16 = index->buf[koff];
> +
> + /* convert entry at ioff to a radix entry */
> + memset(index->buf + ioff, 0, INDEX_RADIX_ENTRY_SIZE);
> + putbe32(noff, (char *)(index->buf + koff + INDEX_OFFSET_SIZE *
> b16));
> + return 0;
> +}
> +
> +static inline int appendleaf(radixlink_buffer_t *index,
> + radixlink_buffer_t *key, uint32_t kidx, uint32_t *poffset,
> + radixlink_resize_func resize)
> +{
> + uint32_t noff, koff, size, ksize, klen, i;
> + assert(index && key && poffset && resize);
> + noff = index->size;
> + ksize = key->size * 2; /* size if represented in base16 */
> + assert(ksize >= kidx);
> + klen = ksize - kidx;
> + size = INDEX_KEY_SIZE + LINK_OFFSET_SIZE + klen;
> + if (size < INDEX_RADIX_ENTRY_SIZE)
> + size = INDEX_RADIX_ENTRY_SIZE;
> + resize(index, noff + size);
> + if (index->size < noff + size)
> + return -1;
> + memset(index->buf + noff, 0, size);
> + putbe32(klen, (char *)(index->buf + noff));
> + koff = noff + INDEX_KEY_SIZE + LINK_OFFSET_SIZE;
> + for (i = kidx; i < ksize; ++i) {
> + uint32_t b = getb16(key->buf, i);
> + index->buf[koff] = b;
> + ++koff;
> + }
> + *poffset = noff;
> + return 0;
> +}
> +
> +static inline int followindex(radixlink_buffer_t *index,
> + radixlink_buffer_t *key, uint32_t *pkidx, uint32_t *pioff,
> + uint32_t *ppoff, radixlink_resize_func *presize)
> +{
> + uint32_t ioff, loff, kidx, klen, koff, poff;
> + uint8_t b16;
> + assert(index && key && pkidx && pioff);
> + ioff = *pioff;
> + kidx = *pkidx;
> + if (readindexentry(index, ioff, &klen, &loff, NULL) != 0)
> + return -1;
> + koff = ioff + INDEX_KEY_SIZE + LINK_OFFSET_SIZE;
> + /* leaf entry */
> + if (klen > 0) {
> + radixlink_buffer_t b16;
> + if (index->size < koff + klen)
> + return -1; /* overflow */
> + b16.buf = index->buf + koff;
> + b16.size = klen;
> + if (b16cmp(key, kidx, &b16) == 0) {
> + *pkidx = key->size * 2 + 1;
> + return 0;
> + }
> + if (presize == NULL) {
> + *pioff = 0;
> + return 0;
> + }
> + /* if presize is provided, split the leaf entry */
> + splitleaf(index, ioff, klen, loff, *presize);
> + }
> + /* radix entry */
> + *pkidx = kidx + 1;
> + if (kidx >= key->size * 2)
> + return 0;
> + b16 = getb16(key->buf, kidx);
> + poff = koff + (uint32_t)b16 * INDEX_OFFSET_SIZE;
> + if (safereadu32(index, poff, pioff) != 0)
> + return -1;
> + if (ppoff != NULL)
> + *ppoff = poff;
> + return 0;
> +}
> +
> +int radixlink_index_find(radixlink_buffer_t *index, radixlink_buffer_t
> *key,
> + uint32_t *plinkoffset)
> +{
> + uint32_t ioff, ksize, kidx;
> + assert(index && key && plinkoffset);
> + ioff = INDEX_HEADER_SIZE;
> + ksize = key->size * 2;
> + for (kidx = 0; kidx <= ksize;) {
> + if (followindex(index, key, &kidx, &ioff, NULL, NULL) != 0)
> + return -1;
> + if (ioff == 0) {
> + *plinkoffset = 0;
> + return 0;
> + }
> + }
> + if (readindexentry(index, ioff, NULL, plinkoffset, NULL) != 0)
> + return -1;
> + return 0;
> +}
> +
> +int radixlink_index_findorcreate(radixlink_buffer_t *index,
> + radixlink_buffer_t *key, uint32_t *plinkoffset,
> + uint32_t *pindexoffset, radixlink_resize_func resize)
> +{
> + uint32_t ioff, ksize, kidx;
> + assert(index && key && plinkoffset && pindexoffset && resize);
> + ioff = INDEX_HEADER_SIZE;
> + ksize = key->size * 2;
> + for (kidx = 0; kidx <= ksize;) {
> + uint32_t poff = 0;
> + if (followindex(index, key, &kidx, &ioff, &poff, resize)
> != 0)
> + return -1;
> + if (ioff == 0) {
> + /* create new leaf */
> + assert(poff != 0);
> + if (appendleaf(index, key, kidx, &ioff, resize) !=
> 0)
> + return -1;
> + if (safewriteu32(index, poff, ioff) != 0)
> + return -1;
> + break;
> + }
> + }
> + if (readindexentry(index, ioff, NULL, plinkoffset, pindexoffset)
> != 0)
> + return -1;
> + return 0;
> +}
> +
> +int radixlink_index_writelink(radixlink_buffer_t *index, uint32_t
> indexoffset,
> + uint32_t linkoffset)
> +{
> + return safewriteu32(index, indexoffset, linkoffset);
> +}
> +
> +int radixlink_link_read(radixlink_buffer_t *link, uint32_t *plinkoffset,
> + uint32_t *pvalue)
> +{
> + uint32_t nextoffset;
> + assert(link && plinkoffset && pvalue);
> + if (safereadu32(link, *plinkoffset + 4, pvalue) != 0)
> + return -1;
> + if (safereadu32(link, *plinkoffset, &nextoffset) != 0)
> + return -1;
> + *plinkoffset = nextoffset;
> + return 0;
> +}
> +
> +int radixlink_link_append(radixlink_buffer_t *link, uint32_t
> *plinkoffset,
> + uint32_t value, radixlink_resize_func resize)
> +{
> + uint32_t offset, size;
> + assert(link && plinkoffset);
> + offset = link->size;
> + size = LINK_OFFSET_SIZE + LINK_VALUE_SIZE;
> + resize(link, offset + size);
> + if (safewriteu32(link, offset + LINK_OFFSET_SIZE, value) != 0)
> + return -1;
> + if (safewriteu32(link, offset, *plinkoffset) != 0)
> + return -1;
> + *plinkoffset = offset;
> + return 0;
> +}
> diff --git a/mercurial/radixlink.h b/mercurial/radixlink.h
> new file mode 100644
> --- /dev/null
> +++ b/mercurial/radixlink.h
> @@ -0,0 +1,57 @@
> +#ifndef _HG_RADIXLINK_H_
> +#define _HG_RADIXLINK_H_
> +
> +/* See radixlink.py for the radixlink file format. In short, "index" is a
> radix
> + * tree with pointing to "link" entries. "link" consists of linked lists.
> + * "index" and "link" could be separate buffers or a mixed buffer. */
> +
> +#include "bitmanipulation.h"
> +
> +/* A customized buffer struct allows us to dynamically resize the buffer
> and be
> + * able to do boundary check at all time. */
> +typedef struct {
> + uint8_t *buf;
> + /* not size_t because offset (could be size) is u32 in file format
> */
> + uint32_t size;
> +} radixlink_buffer_t;
> +
> +/* Function signature to resize a buffer. radixlink does not care about
> how to
> + * resize a buffer. The underlying implementation could be realloc or
> mremap or
> + * something else. It must update "buf->size" to "newsize" on success. If
> the
> + * underlying implementation needs to store extra information like
> "capacity"
> + * to make resize more efficiently, it might use "((uint32_t *)(buf) -
> 4)" or
> + * elsewhere to do the trick. */
> +typedef void radixlink_resize_func(radixlink_buffer_t *buf, uint32_t
> newsize);
> +
> +/* Given the index buffer, and a key, lookup the offset in link buffer.
> + * On success, return 0 and store the offset to *plinkoffset. *plinkoffset
> + * could be 0 which means "not found". On error, return -1 and index
> buffer
> + * should be considered as corrupted. */
> +int radixlink_index_find(radixlink_buffer_t *index,
> + radixlink_buffer_t *key, uint32_t *plinkoffset);
> +
> +/* Like radixlink_index_find, but create the entry on demand */
> +int radixlink_index_findorcreate(radixlink_buffer_t *index,
> + radixlink_buffer_t *key, uint32_t *plinkoffset,
> + uint32_t *pindexoffset, radixlink_resize_func resize);
> +
> +/* Update index at given offset to point to given link offset.
> indexoffset and
> + * linkoffset must be values returned by radixlink_index_findorcreate or
> + * radixlink_link_append. */
> +int radixlink_index_writelink(radixlink_buffer_t *index, uint32_t
> indexoffset,
> + uint32_t linkoffset);
> +
> +/* Given the link buffer and the offset (*ploffset), read an uint32 value
> and
> + * the next offset in the linked list.
> + * On success, return 0 and *ploffset will be the next offset and *pvalue
> will
> + * be the value. If *ploffset is 0, the list should be considered as
> "ended".
> + * On error, return -1 and link buffer should be considered corrupted. */
> +int radixlink_link_read(radixlink_buffer_t *link, uint32_t *plinkoffset,
> + uint32_t *pvalue);
> +
> +/* Append an entry (nextlinkoffset, value) to link buffer. *plinkoffset
> is used
> + * as both input (nextlinkoffset) and output (offset of the new entry) */
> +int radixlink_link_append(radixlink_buffer_t *link, uint32_t
> *plinkoffset,
> + uint32_t value, radixlink_resize_func resize);
> +
> +#endif
> diff --git a/setup.py b/setup.py
> --- a/setup.py
> +++ b/setup.py
> @@ -660,4 +660,8 @@ extmodules = [
> extra_link_args=osutil_ldflags,
> depends=common_depends),
> + Extension('mercurial.cext.radixlink', ['mercurial/radixlink.c',
> + 'mercurial/cext/radixlink.c'],
> + include_dirs=common_include_dirs,
> + depends=common_depends + ['mercurial/radixlink.h']),
> Extension('hgext.fsmonitor.pywatchman.bser',
> ['hgext/fsmonitor/pywatchman/bser.c']),
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mercurial-scm.org/pipermail/mercurial-devel/attachments/20170605/4439d111/attachment.html>
More information about the Mercurial-devel
mailing list