# HG changeset patch
# User Jun Wu <qu...@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']),
_______________________________________________
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
