[PATCH 03 of 22] radixlink: add C implementation

Jun Wu quark at fb.com
Sun Jun 4 19:59:15 EDT 2017


# 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

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);
+	if (!pyvalues)
+		goto bail;
+
+	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;
+	}
+}
+
+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))
+		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;
+	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);
+}
+
+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 */
+	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;
+	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
@@ -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']),


More information about the Mercurial-devel mailing list