summaryrefslogtreecommitdiffstats
path: root/third_party/python/pyrsistent/pvectorcmodule.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 19:33:14 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 19:33:14 +0000
commit36d22d82aa202bb199967e9512281e9a53db42c9 (patch)
tree105e8c98ddea1c1e4784a60a5a6410fa416be2de /third_party/python/pyrsistent/pvectorcmodule.c
parentInitial commit. (diff)
downloadfirefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz
firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/python/pyrsistent/pvectorcmodule.c')
-rw-r--r--third_party/python/pyrsistent/pvectorcmodule.c1642
1 files changed, 1642 insertions, 0 deletions
diff --git a/third_party/python/pyrsistent/pvectorcmodule.c b/third_party/python/pyrsistent/pvectorcmodule.c
new file mode 100644
index 0000000000..11a5bd6411
--- /dev/null
+++ b/third_party/python/pyrsistent/pvectorcmodule.c
@@ -0,0 +1,1642 @@
+#include <Python.h>
+#include <structmember.h>
+
+/*
+Persistent/Immutable/Functional vector and helper types.
+
+Please note that they are anything but immutable at this level since
+there is a whole lot of reference counting going on. That's the way
+CPython works though and the GIL makes them appear immutable.
+
+To the programmer using them from Python they appear immutable and
+behave immutably at least.
+
+Naming conventions
+------------------
+initpyrsistentc - This is the method that initializes the whole module
+pyrsistent_* - Methods part of the interface
+<typename>_* - Instance methods of types. For examle PVector_append(...)
+
+All other methods are camel cased without prefix. All methods are static, none should
+require to be exposed outside of this module.
+*/
+
+#define SHIFT 5
+#define BRANCH_FACTOR (1 << SHIFT)
+#define BIT_MASK (BRANCH_FACTOR - 1)
+
+static PyTypeObject PVectorType;
+static PyTypeObject PVectorEvolverType;
+
+typedef struct {
+ void *items[BRANCH_FACTOR];
+ unsigned int refCount;
+} VNode;
+
+#define NODE_CACHE_MAX_SIZE 1024
+
+typedef struct {
+ unsigned int size;
+ VNode* nodes[NODE_CACHE_MAX_SIZE];
+} vNodeCache;
+
+static vNodeCache nodeCache;
+
+typedef struct {
+ PyObject_HEAD
+ unsigned int count; // Perhaps ditch this one in favor of ob_size/Py_SIZE()
+ unsigned int shift;
+ VNode *root;
+ VNode *tail;
+ PyObject *in_weakreflist; /* List of weak references */
+} PVector;
+
+typedef struct {
+ PyObject_HEAD
+ PVector* originalVector;
+ PVector* newVector;
+ PyObject* appendList;
+} PVectorEvolver;
+
+
+static PVector* EMPTY_VECTOR = NULL;
+static PyObject* transform_fn = NULL;
+
+static PyObject* transform(PVector* self, PyObject* args) {
+ if(transform_fn == NULL) {
+ // transform to avoid circular import problems
+ transform_fn = PyObject_GetAttrString(PyImport_ImportModule("pyrsistent._transformations"), "transform");
+ }
+
+ return PyObject_CallFunctionObjArgs(transform_fn, self, args, NULL);
+}
+
+
+// No access to internal members
+static PyMemberDef PVector_members[] = {
+ {NULL} /* Sentinel */
+};
+
+#define debug(...)
+// #define debug printf
+
+#define NODE_REF_COUNT(n) ((n)->refCount)
+#define SET_NODE_REF_COUNT(n, c) (NODE_REF_COUNT(n) = (c))
+#define INC_NODE_REF_COUNT(n) (NODE_REF_COUNT(n)++)
+#define DEC_NODE_REF_COUNT(n) (NODE_REF_COUNT(n)--)
+
+static VNode* allocNode(void) {
+ if(nodeCache.size > 0) {
+ nodeCache.size--;
+ return nodeCache.nodes[nodeCache.size];
+ }
+
+ return PyMem_Malloc(sizeof(VNode));
+}
+
+static void freeNode(VNode *node) {
+ if(nodeCache.size < NODE_CACHE_MAX_SIZE) {
+ nodeCache.nodes[nodeCache.size] = node;
+ nodeCache.size++;
+ } else {
+ PyMem_Free(node);
+ }
+}
+
+static VNode* newNode(void) {
+ VNode* result = allocNode();
+ memset(result, 0x0, sizeof(VNode));
+ SET_NODE_REF_COUNT(result, 1);
+ debug("newNode() %p\n", result);
+ return result;
+}
+
+static VNode* copyNode(VNode* source) {
+ /* NB: Only to be used for internal nodes, eg. nodes that do not
+ hold direct references to python objects but only to other nodes. */
+ int i;
+ VNode* result = allocNode();
+ debug("copyNode() %p\n", result);
+ memcpy(result->items, source->items, sizeof(source->items));
+
+ for(i = 0; i < BRANCH_FACTOR; i++) {
+ // TODO-OPT: Any need to go on when the first NULL has been found?
+ if(result->items[i] != NULL) {
+ INC_NODE_REF_COUNT((VNode*)result->items[i]);
+ }
+ }
+
+ SET_NODE_REF_COUNT(result, 1);
+ return result;
+}
+
+static PVector* emptyNewPvec(void);
+static PVector* copyPVector(PVector *original);
+static void extendWithItem(PVector *newVec, PyObject *item);
+
+static PyObject *PVectorEvolver_persistent(PVectorEvolver *);
+static int PVectorEvolver_set_item(PVectorEvolver *, PyObject*, PyObject*);
+
+static Py_ssize_t PVector_len(PVector *self) {
+ return self->count;
+}
+
+/* Convenience macros */
+#define ROOT_NODE_FULL(vec) ((vec->count >> SHIFT) > (1 << vec->shift))
+#define TAIL_OFF(vec) ((vec->count < BRANCH_FACTOR) ? 0 : (((vec->count - 1) >> SHIFT) << SHIFT))
+#define TAIL_SIZE(vec) (vec->count - TAIL_OFF(vec))
+#define PVector_CheckExact(op) (Py_TYPE(op) == &PVectorType)
+
+static VNode* nodeFor(PVector *self, int i){
+ int level;
+ if((i >= 0) && (i < self->count)) {
+ if(i >= TAIL_OFF(self)) {
+ return self->tail;
+ }
+
+ VNode* node = self->root;
+ for(level = self->shift; level > 0; level -= SHIFT) {
+ node = (VNode*) node->items[(i >> level) & BIT_MASK];
+ }
+
+ return node;
+ }
+
+ PyErr_Format(PyExc_IndexError, "Index out of range: %i", i);
+ return NULL;
+}
+
+static PyObject* _get_item(PVector *self, Py_ssize_t pos) {
+ VNode* node = nodeFor((PVector*)self, pos);
+ PyObject *result = NULL;
+ if(node != NULL) {
+ result = node->items[pos & BIT_MASK];
+ }
+ return result;
+}
+
+/*
+ Returns a new reference as specified by the PySequence_GetItem function.
+*/
+static PyObject* PVector_get_item(PVector *self, Py_ssize_t pos) {
+ if (pos < 0) {
+ pos += self->count;
+ }
+
+ PyObject* obj = _get_item(self, pos);
+ Py_XINCREF(obj);
+ return obj;
+}
+
+static void releaseNode(int level, VNode *node) {
+ if(node == NULL) {
+ return;
+ }
+
+ debug("releaseNode(): node=%p, level=%i, refCount=%i\n", node, level, NODE_REF_COUNT(node));
+
+ int i;
+
+ DEC_NODE_REF_COUNT(node);
+ debug("Refcount when trying to release: %u\n", NODE_REF_COUNT(node));
+ if(NODE_REF_COUNT(node) == 0) {
+ if(level > 0) {
+ for(i = 0; i < BRANCH_FACTOR; i++) {
+ if(node->items[i] != NULL) {
+ releaseNode(level - SHIFT, node->items[i]);
+ }
+ }
+ freeNode(node);
+ } else {
+ for(i = 0; i < BRANCH_FACTOR; i++) {
+ Py_XDECREF(node->items[i]);
+ }
+ freeNode(node);
+ }
+ }
+
+ debug("releaseNode(): Done! node=%p!\n", node);
+}
+
+/*
+ Returns all references to PyObjects that have been stolen. Also decrements
+ the internal reference counts used for shared memory structures and deallocates
+ those if needed.
+*/
+static void PVector_dealloc(PVector *self) {
+ debug("Dealloc(): self=%p, self->count=%u, tail->refCount=%u, root->refCount=%u, self->shift=%u, self->tail=%p, self->root=%p\n",
+ self, self->count, NODE_REF_COUNT(self->tail), NODE_REF_COUNT(self->root), self->shift, self->tail, self->root);
+
+ if (self->in_weakreflist != NULL) {
+ PyObject_ClearWeakRefs((PyObject *) self);
+ }
+
+ PyObject_GC_UnTrack((PyObject*)self);
+ Py_TRASHCAN_SAFE_BEGIN(self);
+
+ releaseNode(0, self->tail);
+ releaseNode(self->shift, self->root);
+
+ PyObject_GC_Del(self);
+ Py_TRASHCAN_SAFE_END(self);
+}
+
+static PyObject *PVector_toList(PVector *self) {
+ Py_ssize_t i;
+ PyObject *list = PyList_New(self->count);
+ for (i = 0; i < self->count; ++i) {
+ PyObject *o = _get_item(self, i);
+ Py_INCREF(o);
+ PyList_SET_ITEM(list, i, o);
+ }
+
+ return list;
+}
+
+
+static PyObject *PVector_repr(PVector *self) {
+ // Reuse the list repr code, a bit less efficient but saves some code
+ PyObject *list = PVector_toList(self);
+ PyObject *list_repr = PyObject_Repr(list);
+ Py_DECREF(list);
+
+ if(list_repr == NULL) {
+ // Exception raised during call to repr
+ return NULL;
+ }
+
+ // Repr for list implemented differently in python 2 and 3. Need to
+ // handle this or core dump will occur.
+#if PY_MAJOR_VERSION >= 3
+ PyObject *s = PyUnicode_FromFormat("%s%U%s", "pvector(", list_repr, ")");
+ Py_DECREF(list_repr);
+#else
+ PyObject *s = PyString_FromString("pvector(");
+ PyString_ConcatAndDel(&s, list_repr);
+ PyString_ConcatAndDel(&s, PyString_FromString(")"));
+#endif
+
+ return s;
+}
+
+
+static long PVector_hash(PVector *self) {
+ // Follows the pattern of the tuple hash
+ long x, y;
+ Py_ssize_t i;
+ long mult = 1000003L;
+ x = 0x456789L;
+ for(i=0; i<self->count; i++) {
+ y = PyObject_Hash(_get_item(self, i));
+ if (y == -1) {
+ return -1;
+ }
+ x = (x ^ y) * mult;
+ mult += (long)(82520L + i + i);
+ }
+
+ x += 97531L;
+ if(x == -1) {
+ x = -2;
+ }
+
+ return x;
+}
+
+static PyObject* compareSizes(long vlen, long wlen, int op) {
+ int cmp;
+ PyObject *res;
+ switch (op) {
+ case Py_LT: cmp = vlen < wlen; break;
+ case Py_LE: cmp = vlen <= wlen; break;
+ case Py_EQ: cmp = vlen == wlen; break;
+ case Py_NE: cmp = vlen != wlen; break;
+ case Py_GT: cmp = vlen > wlen; break;
+ case Py_GE: cmp = vlen >= wlen; break;
+ default: return NULL; /* cannot happen */
+ }
+
+ if (cmp) {
+ res = Py_True;
+ } else {
+ res = Py_False;
+ }
+
+ Py_INCREF(res);
+ return res;
+}
+
+static PyObject* PVector_richcompare(PyObject *v, PyObject *w, int op) {
+ // Follows the principles of the tuple comparison
+ PVector *vt, *wt;
+ Py_ssize_t i;
+ Py_ssize_t vlen, wlen;
+ PyObject *list;
+ PyObject *result;
+
+ if(!PVector_CheckExact(v) || !PVector_CheckExact(w)) {
+ if(PVector_CheckExact(v)) {
+ list = PVector_toList((PVector*)v);
+ result = PyObject_RichCompare(list , w, op);
+ Py_DECREF(list);
+ return result;
+ }
+
+ if(PVector_CheckExact(w)) {
+ list = PVector_toList((PVector*)w);
+ result = PyObject_RichCompare(v, list, op);
+ Py_DECREF(list);
+ return result;
+ }
+
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+
+ if((op == Py_EQ) && (v == w)) {
+ Py_INCREF(Py_True);
+ return Py_True;
+ }
+
+ vt = (PVector *)v;
+ wt = (PVector *)w;
+
+ vlen = vt->count;
+ wlen = wt->count;
+
+ if (vlen != wlen) {
+ if (op == Py_EQ) {
+ Py_INCREF(Py_False);
+ return Py_False;
+ } else if (op == Py_NE) {
+ Py_INCREF(Py_True);
+ return Py_True;
+ }
+ }
+
+ /* Search for the first index where items are different. */
+ PyObject *left = NULL;
+ PyObject *right = NULL;
+ for (i = 0; i < vlen && i < wlen; i++) {
+ left = _get_item(vt, i);
+ right = _get_item(wt, i);
+ int k = PyObject_RichCompareBool(left, right, Py_EQ);
+ if (k < 0) {
+ return NULL;
+ }
+ if (!k) {
+ break;
+ }
+ }
+
+ if (i >= vlen || i >= wlen) {
+ /* No more items to compare -- compare sizes */
+ return compareSizes(vlen, wlen, op);
+ }
+
+ /* We have an item that differs -- shortcuts for EQ/NE */
+ if (op == Py_EQ) {
+ Py_INCREF(Py_False);
+ return Py_False;
+ } else if (op == Py_NE) {
+ Py_INCREF(Py_True);
+ return Py_True;
+ } else {
+ /* Compare the final item again using the proper operator */
+ return PyObject_RichCompare(left, right, op);
+ }
+}
+
+
+static PyObject* PVector_repeat(PVector *self, Py_ssize_t n) {
+ if (n < 0) {
+ n = 0;
+ }
+
+ if ((n == 0) || (self->count == 0)) {
+ Py_INCREF(EMPTY_VECTOR);
+ return (PyObject *)EMPTY_VECTOR;
+ } else if (n == 1) {
+ Py_INCREF(self);
+ return (PyObject *)self;
+ } else if ((self->count * n)/self->count != n) {
+ return PyErr_NoMemory();
+ } else {
+ int i, j;
+ PVector *newVec = copyPVector(self);
+ for(i=0; i<(n-1); i++) {
+ for(j=0; j<self->count; j++) {
+ extendWithItem(newVec, PVector_get_item(self, j));
+ }
+ }
+ return (PyObject*)newVec;
+ }
+}
+
+static int PVector_traverse(PVector *o, visitproc visit, void *arg) {
+ // Naive traverse
+ Py_ssize_t i;
+ for (i = o->count; --i >= 0; ) {
+ Py_VISIT(_get_item(o, i));
+ }
+
+ return 0;
+}
+
+
+static PyObject* PVector_index(PVector *self, PyObject *args) {
+ // A direct rip-off of the tuple version
+ Py_ssize_t i, start=0, stop=self->count;
+ PyObject *value;
+
+ if (!PyArg_ParseTuple(args, "O|O&O&:index", &value,
+ _PyEval_SliceIndex, &start,
+ _PyEval_SliceIndex, &stop)) {
+ return NULL;
+ }
+
+ if (start < 0) {
+ start += self->count;
+ if (start < 0) {
+ start = 0;
+ }
+ }
+
+ if (stop < 0) {
+ stop += self->count;
+ if (stop < 0) {
+ stop = 0;
+ }
+ }
+
+ for (i = start; i < stop && i < self->count; i++) {
+ int cmp = PyObject_RichCompareBool(_get_item(self, i), value, Py_EQ);
+ if (cmp > 0) {
+#if PY_MAJOR_VERSION >= 3
+ return PyLong_FromSsize_t(i);
+#else
+ return PyInt_FromSsize_t(i);
+#endif
+ } else if (cmp < 0) {
+ return NULL;
+ }
+ }
+
+ PyErr_SetString(PyExc_ValueError, "PVector.index(x): x not in vector");
+ return NULL;
+}
+
+static PyObject* PVector_count(PVector *self, PyObject *value) {
+ Py_ssize_t count = 0;
+ Py_ssize_t i;
+
+ for (i = 0; i < self->count; i++) {
+ int cmp = PyObject_RichCompareBool(_get_item(self, i), value, Py_EQ);
+ if (cmp > 0) {
+ count++;
+ } else if (cmp < 0) {
+ return NULL;
+ }
+ }
+
+#if PY_MAJOR_VERSION >= 3
+ return PyLong_FromSsize_t(count);
+#else
+ return PyInt_FromSsize_t(count);
+#endif
+}
+
+static PyObject* PVector_pickle_reduce(PVector *self) {
+
+ PyObject* module = PyImport_ImportModule("pvectorc");
+ PyObject* pvector_fn = PyObject_GetAttrString(module, "pvector");
+ Py_DECREF(module);
+
+ PyObject *list = PVector_toList(self);
+ PyObject *arg_tuple = PyTuple_New(1);
+ PyTuple_SET_ITEM(arg_tuple, 0, list);
+
+ PyObject *result_tuple = PyTuple_New(2);
+ PyTuple_SET_ITEM(result_tuple, 0, pvector_fn);
+ PyTuple_SET_ITEM(result_tuple, 1, arg_tuple);
+
+ return result_tuple;
+}
+
+static PVector* rawCopyPVector(PVector* vector) {
+ PVector* newVector = PyObject_GC_New(PVector, &PVectorType);
+ newVector->count = vector->count;
+ newVector->shift = vector->shift;
+ newVector->root = vector->root;
+ newVector->tail = vector->tail;
+ newVector->in_weakreflist = NULL;
+ PyObject_GC_Track((PyObject*)newVector);
+ return newVector;
+}
+
+static void initializeEvolver(PVectorEvolver* evolver, PVector* vector, PyObject* appendList) {
+ // Need to hold a reference to the underlying vector to manage
+ // the ref counting properly.
+ evolver->originalVector = vector;
+ evolver->newVector = vector;
+
+ if(appendList == NULL) {
+ evolver->appendList = PyList_New(0);
+ } else {
+ evolver->appendList = appendList;
+ }
+}
+
+static PyObject * PVector_evolver(PVector *self) {
+ PVectorEvolver *evolver = PyObject_GC_New(PVectorEvolver, &PVectorEvolverType);
+ if (evolver == NULL) {
+ return NULL;
+ }
+ initializeEvolver(evolver, self, NULL);
+ PyObject_GC_Track(evolver);
+ Py_INCREF(self);
+ return (PyObject *)evolver;
+}
+
+
+static void copyInsert(void** dest, void** src, Py_ssize_t pos, void *obj) {
+ memcpy(dest, src, BRANCH_FACTOR * sizeof(void*));
+ dest[pos] = obj;
+}
+
+static PyObject* PVector_append(PVector *self, PyObject *obj);
+
+static PyObject* PVector_transform(PVector *self, PyObject *obj);
+
+static PyObject* PVector_set(PVector *self, PyObject *obj);
+
+static PyObject* PVector_mset(PVector *self, PyObject *args);
+
+static PyObject* PVector_subscript(PVector* self, PyObject* item);
+
+static PyObject* PVector_extend(PVector *self, PyObject *args);
+
+static PyObject* PVector_delete(PVector *self, PyObject *args);
+
+static PyObject* PVector_remove(PVector *self, PyObject *args);
+
+static PySequenceMethods PVector_sequence_methods = {
+ (lenfunc)PVector_len, /* sq_length */
+ (binaryfunc)PVector_extend, /* sq_concat */
+ (ssizeargfunc)PVector_repeat, /* sq_repeat */
+ (ssizeargfunc)PVector_get_item, /* sq_item */
+ // TODO might want to move the slice function to here
+ NULL, /* sq_slice */
+ NULL, /* sq_ass_item */
+ NULL, /* sq_ass_slice */
+ NULL, /* sq_contains */
+ NULL, /* sq_inplace_concat */
+ NULL, /* sq_inplace_repeat */
+};
+
+static PyMappingMethods PVector_mapping_methods = {
+ (lenfunc)PVector_len,
+ (binaryfunc)PVector_subscript,
+ NULL
+};
+
+
+static PyMethodDef PVector_methods[] = {
+ {"append", (PyCFunction)PVector_append, METH_O, "Appends an element"},
+ {"set", (PyCFunction)PVector_set, METH_VARARGS, "Inserts an element at the specified position"},
+ {"extend", (PyCFunction)PVector_extend, METH_O|METH_COEXIST, "Extend"},
+ {"transform", (PyCFunction)PVector_transform, METH_VARARGS, "Apply one or more transformations"},
+ {"index", (PyCFunction)PVector_index, METH_VARARGS, "Return first index of value"},
+ {"count", (PyCFunction)PVector_count, METH_O, "Return number of occurrences of value"},
+ {"__reduce__", (PyCFunction)PVector_pickle_reduce, METH_NOARGS, "Pickle support method"},
+ {"evolver", (PyCFunction)PVector_evolver, METH_NOARGS, "Return new evolver for pvector"},
+ {"mset", (PyCFunction)PVector_mset, METH_VARARGS, "Inserts multiple elements at the specified positions"},
+ {"tolist", (PyCFunction)PVector_toList, METH_NOARGS, "Convert to list"},
+ {"delete", (PyCFunction)PVector_delete, METH_VARARGS, "Delete element(s) by index"},
+ {"remove", (PyCFunction)PVector_remove, METH_VARARGS, "Remove element(s) by equality"},
+ {NULL}
+};
+
+static PyObject * PVectorIter_iter(PyObject *seq);
+
+static PyTypeObject PVectorType = {
+ PyVarObject_HEAD_INIT(NULL, 0)
+ "pvectorc.PVector", /* tp_name */
+ sizeof(PVector), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)PVector_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ (reprfunc)PVector_repr, /* tp_repr */
+ 0, /* tp_as_number */
+ &PVector_sequence_methods, /* tp_as_sequence */
+ &PVector_mapping_methods, /* tp_as_mapping */
+ (hashfunc)PVector_hash, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
+ "Persistent vector", /* tp_doc */
+ (traverseproc)PVector_traverse, /* tp_traverse */
+ 0, /* tp_clear */
+ PVector_richcompare, /* tp_richcompare */
+ offsetof(PVector, in_weakreflist), /* tp_weaklistoffset */
+ PVectorIter_iter, /* tp_iter */
+ 0, /* tp_iternext */
+ PVector_methods, /* tp_methods */
+ PVector_members, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+};
+
+static PyObject* pyrsistent_pvec(PyObject *self, PyObject *args) {
+ debug("pyrsistent_pvec(): %x\n", args);
+
+ PyObject *argObj = NULL; /* list of arguments */
+
+ if(!PyArg_ParseTuple(args, "|O", &argObj)) {
+ return NULL;
+ }
+
+ if(argObj == NULL) {
+ Py_INCREF(EMPTY_VECTOR);
+ return (PyObject*)EMPTY_VECTOR;
+ }
+
+ return PVector_extend(EMPTY_VECTOR, argObj);
+}
+
+static PVector* emptyNewPvec(void) {
+ PVector *pvec = PyObject_GC_New(PVector, &PVectorType);
+ debug("pymem alloc_new %x, ref cnt: %u\n", pvec, pvec->ob_refcnt);
+ pvec->count = (Py_ssize_t)0;
+ pvec->shift = SHIFT;
+ pvec->root = newNode();
+ pvec->tail = newNode();
+ pvec->in_weakreflist = NULL;
+ PyObject_GC_Track((PyObject*)pvec);
+ return pvec;
+}
+
+static void incRefs(PyObject **obj) {
+ // TODO-OPT: Would it be OK to exit on first NULL? Should not be any
+ // non NULLs beyond a NULL.
+ int i;
+ for(i = 0; i < BRANCH_FACTOR; i++) {
+ Py_XINCREF(obj[i]);
+ }
+}
+
+
+static PVector* newPvec(unsigned int count, unsigned int shift, VNode *root) {
+ // TODO-OPT: Introduce object cache
+ PVector *pvec = PyObject_GC_New(PVector, &PVectorType);
+ debug("pymem alloc_copy %x, ref cnt: %u\n", pvec, pvec->ob_refcnt);
+ pvec->count = count;
+ pvec->shift = shift;
+ pvec->root = root;
+ pvec->tail = newNode();
+ pvec->in_weakreflist = NULL;
+ PyObject_GC_Track((PyObject*)pvec);
+ return pvec;
+}
+
+static VNode* newPath(unsigned int level, VNode* node){
+ if(level == 0) {
+ INC_NODE_REF_COUNT(node);
+ return node;
+ }
+
+ VNode* result = newNode();
+ result->items[0] = newPath(level - SHIFT, node);
+ return result;
+}
+
+static VNode* pushTail(unsigned int level, unsigned int count, VNode* parent, VNode* tail) {
+ int subIndex = ((count - 1) >> level) & BIT_MASK;
+ VNode* result = copyNode(parent);
+ VNode* nodeToInsert;
+ VNode* child;
+ debug("pushTail(): count = %i, subIndex = %i\n", count, subIndex);
+
+ if(level == SHIFT) {
+ // We're at the bottom
+ INC_NODE_REF_COUNT(tail);
+ nodeToInsert = tail;
+ } else {
+ // More levels available in the tree
+ child = parent->items[subIndex];
+
+ if(child != NULL) {
+ nodeToInsert = pushTail(level - SHIFT, count, child, tail);
+
+ // Need to make an adjustment of the ref COUNT for the child node here since
+ // it was incremented in an earlier stage when the node was copied. Now the child
+ // node will be part of the path copy so the number of references to the original
+ // child will not increase at all.
+ DEC_NODE_REF_COUNT(child);
+ } else {
+ nodeToInsert = newPath(level - SHIFT, tail);
+ }
+ }
+
+ result->items[subIndex] = nodeToInsert;
+ return result;
+}
+
+static PVector* copyPVector(PVector *original) {
+ PVector *newVec = newPvec(original->count, original->shift, original->root);
+ INC_NODE_REF_COUNT(original->root);
+ memcpy(newVec->tail->items, original->tail->items, TAIL_SIZE(original) * sizeof(void*));
+ incRefs((PyObject**)newVec->tail->items);
+ return newVec;
+}
+
+/* Does not steal a reference, this must be managed outside of this function */
+static void extendWithItem(PVector *newVec, PyObject *item) {
+ unsigned int tail_size = TAIL_SIZE(newVec);
+
+ if(tail_size >= BRANCH_FACTOR) {
+ VNode* new_root;
+ if(ROOT_NODE_FULL(newVec)) {
+ new_root = newNode();
+ new_root->items[0] = newVec->root;
+ new_root->items[1] = newPath(newVec->shift, newVec->tail);
+ newVec->shift += SHIFT;
+ } else {
+ new_root = pushTail(newVec->shift, newVec->count, newVec->root, newVec->tail);
+ releaseNode(newVec->shift, newVec->root);
+ }
+
+ newVec->root = new_root;
+
+ // Need to adjust the ref count of the old tail here since no new references were
+ // actually created, we just moved the tail.
+ DEC_NODE_REF_COUNT(newVec->tail);
+ newVec->tail = newNode();
+ tail_size = 0;
+ }
+
+ newVec->tail->items[tail_size] = item;
+ newVec->count++;
+}
+
+
+#if PY_MAJOR_VERSION >= 3
+// This was changed in 3.2 but we do not claim compatibility with any older version of python 3.
+#define SLICE_CAST
+#else
+#define SLICE_CAST (PySliceObject *)
+#endif
+
+static PyObject *PVector_subscript(PVector* self, PyObject* item) {
+ if (PyIndex_Check(item)) {
+ Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
+ if (i == -1 && PyErr_Occurred()) {
+ return NULL;
+ }
+
+ return PVector_get_item(self, i);
+ } else if (PySlice_Check(item)) {
+ Py_ssize_t start, stop, step, slicelength, cur, i;
+ if (PySlice_GetIndicesEx(SLICE_CAST item, self->count,
+ &start, &stop, &step, &slicelength) < 0) {
+ return NULL;
+ }
+
+ debug("start=%i, stop=%i, step=%i\n", start, stop, step);
+
+ if (slicelength <= 0) {
+ Py_INCREF(EMPTY_VECTOR);
+ return (PyObject*)EMPTY_VECTOR;
+ } else if((slicelength == self->count) && (step > 0)) {
+ Py_INCREF(self);
+ return (PyObject*)self;
+ } else {
+ PVector *newVec = copyPVector(EMPTY_VECTOR);
+ for (cur=start, i=0; i<slicelength; cur += (size_t)step, i++) {
+ extendWithItem(newVec, PVector_get_item(self, cur));
+ }
+
+ return (PyObject*)newVec;
+ }
+ } else {
+ PyErr_Format(PyExc_TypeError, "pvector indices must be integers, not %.200s", Py_TYPE(item)->tp_name);
+ return NULL;
+ }
+}
+
+/* A hack to get some of the error handling code away from the function
+ doing the actual work */
+#define HANDLE_ITERATION_ERROR() \
+ if (PyErr_Occurred()) { \
+ if (PyErr_ExceptionMatches(PyExc_StopIteration)) { \
+ PyErr_Clear(); \
+ } else { \
+ return NULL; \
+ } \
+ }
+
+
+/* Returns a new vector that is extended with the iterable b.
+ Takes a copy of the original vector and performs the extension in place on this
+ one for efficiency.
+
+ These are some optimizations that could be done to this function,
+ these are not considered important enough yet though.
+ - Use the PySequence_Fast ops if the iterable is a list or a tuple (which it
+ whould probably often be)
+ - Only copy the original tail if it is not full
+ - No need to try to increment ref count in tail for the whole tail
+*/
+static PyObject* PVector_extend(PVector *self, PyObject *iterable) {
+ PyObject *it;
+ PyObject *(*iternext)(PyObject *);
+
+ it = PyObject_GetIter(iterable);
+ if (it == NULL) {
+ return NULL;
+ }
+
+ // TODO-OPT: Use special fast iterator if available
+ iternext = *Py_TYPE(it)->tp_iternext;
+ PyObject *item = iternext(it);
+ if (item == NULL) {
+ Py_DECREF(it);
+ HANDLE_ITERATION_ERROR()
+ Py_INCREF(self);
+ return (PyObject *)self;
+ } else {
+ PVector *newVec = copyPVector(self);
+ // TODO-OPT test using special case code here for extension to
+ // avoid recalculating tail length all the time.
+ while(item != NULL) {
+ extendWithItem(newVec, item);
+ item = iternext(it);
+ }
+
+ Py_DECREF(it);
+ HANDLE_ITERATION_ERROR()
+ return (PyObject*)newVec;
+ }
+}
+
+/*
+ Steals a reference to the object that is appended to the list.
+*/
+static PyObject* PVector_append(PVector *self, PyObject *obj) {
+ assert (obj != NULL);
+
+ unsigned int tail_size = TAIL_SIZE(self);
+ debug("append(): count = %u, tail_size = %u\n", self->count, tail_size);
+
+ // Does the new object fit in the tail? If so, take a copy of the tail and
+ // insert the new element in that.
+ if(tail_size < BRANCH_FACTOR) {
+ INC_NODE_REF_COUNT(self->root);
+ PVector *new_pvec = newPvec(self->count + 1, self->shift, self->root);
+ // TODO-OPT No need to copy more than the current tail length
+ // TODO-OPT No need to incRefs for all elements all the time
+ copyInsert(new_pvec->tail->items, self->tail->items, tail_size, obj);
+ incRefs((PyObject**)new_pvec->tail->items);
+ debug("append(): new_pvec=%p, new_pvec->tail=%p, new_pvec->root=%p\n",
+ new_pvec, new_pvec->tail, new_pvec->root);
+
+ return (PyObject*)new_pvec;
+ }
+
+ // Tail is full, need to push it into the tree
+ VNode* new_root;
+ unsigned int new_shift;
+ if(ROOT_NODE_FULL(self)) {
+ new_root = newNode();
+ new_root->items[0] = self->root;
+ INC_NODE_REF_COUNT(self->root);
+ new_root->items[1] = newPath(self->shift, self->tail);
+ new_shift = self->shift + SHIFT;
+ } else {
+ new_root = pushTail(self->shift, self->count, self->root, self->tail);
+ new_shift = self->shift;
+ }
+
+ PVector* pvec = newPvec(self->count + 1, new_shift, new_root);
+ pvec->tail->items[0] = obj;
+ Py_XINCREF(obj);
+ debug("append_push(): pvec=%p, pvec->tail=%p, pvec->root=%p\n", pvec, pvec->tail, pvec->root);
+ return (PyObject*)pvec;
+}
+
+static VNode* doSet(VNode* node, unsigned int level, unsigned int position, PyObject* value) {
+ debug("doSet(): level == %i\n", level);
+ if(level == 0) {
+ // TODO-OPT: Perhaps an alloc followed by a reset of reference
+ // count is enough here since we overwrite all subnodes below.
+ VNode* theNewNode = newNode();
+ copyInsert(theNewNode->items, node->items, position & BIT_MASK, value);
+ incRefs((PyObject**)theNewNode->items);
+ return theNewNode;
+ } else {
+ VNode* theNewNode = copyNode(node);
+ Py_ssize_t index = (position >> level) & BIT_MASK;
+
+ // Drop reference to this node since we're about to replace it
+ DEC_NODE_REF_COUNT((VNode*)theNewNode->items[index]);
+ theNewNode->items[index] = doSet(node->items[index], level - SHIFT, position, value);
+ return theNewNode;
+ }
+}
+
+
+static PyObject* internalSet(PVector *self, Py_ssize_t position, PyObject *argObj) {
+ if(position < 0) {
+ position += self->count;
+ }
+
+ if((0 <= position) && (position < self->count)) {
+ if(position >= TAIL_OFF(self)) {
+ // Reuse the root, replace the tail
+ INC_NODE_REF_COUNT(self->root);
+ PVector *new_pvec = newPvec(self->count, self->shift, self->root);
+ copyInsert(new_pvec->tail->items, self->tail->items, position & BIT_MASK, argObj);
+ incRefs((PyObject**)new_pvec->tail->items);
+ return (PyObject*)new_pvec;
+ } else {
+ // Keep the tail, replace the root
+ VNode *newRoot = doSet(self->root, self->shift, position, argObj);
+ PVector *new_pvec = newPvec(self->count, self->shift, newRoot);
+
+ // Free the tail and replace it with a reference to the tail of the original vector
+ freeNode(new_pvec->tail);
+ new_pvec->tail = self->tail;
+ INC_NODE_REF_COUNT(self->tail);
+ return (PyObject*)new_pvec;
+ }
+ } else if (position == self->count) {
+ // TODO Remove this case?
+ return PVector_append(self, argObj);
+ } else {
+ PyErr_Format(PyExc_IndexError, "Index out of range: %zd", position);
+ return NULL;
+ }
+}
+
+static PyObject* PVector_transform(PVector *self, PyObject *obj) {
+ return transform(self, obj);
+}
+
+/*
+ Steals a reference to the object that is inserted in the vector.
+*/
+static PyObject* PVector_set(PVector *self, PyObject *args) {
+ PyObject *argObj = NULL; /* argument to insert */
+ Py_ssize_t position;
+
+ /* The n parses for size, the O parses for a Python object */
+ if(!PyArg_ParseTuple(args, "nO", &position, &argObj)) {
+ return NULL;
+ }
+
+ return internalSet(self, position, argObj);
+}
+
+
+static PyObject* PVector_mset(PVector *self, PyObject *args) {
+ Py_ssize_t size = PyTuple_Size(args);
+ if(size % 2) {
+ PyErr_SetString(PyExc_TypeError, "mset expected an even number of arguments");
+ return NULL;
+ }
+
+ PVectorEvolver* evolver = (PVectorEvolver*)PVector_evolver(self);
+ Py_ssize_t i;
+ for(i=0; i<size; i+=2) {
+ if(PVectorEvolver_set_item(evolver, PyTuple_GetItem(args, i), PyTuple_GetItem(args, i + 1)) < 0) {
+ Py_DECREF(evolver);
+ return NULL;
+ }
+ }
+
+ PyObject* vector = PVectorEvolver_persistent(evolver);
+ Py_DECREF(evolver);
+ return vector;
+}
+
+
+static PyObject* internalDelete(PVector *self, Py_ssize_t index, PyObject *stop_obj) {
+ Py_ssize_t stop;
+ PyObject *list;
+ PyObject *result;
+
+ if (index < 0) {
+ index += self->count;
+ }
+
+ if (stop_obj != NULL) {
+ if (PyIndex_Check(stop_obj)) {
+ stop = PyNumber_AsSsize_t(stop_obj, PyExc_IndexError);
+ if (stop == -1 && PyErr_Occurred()) {
+ return NULL;
+ }
+ } else {
+ PyErr_Format(PyExc_TypeError, "Stop index must be integer, not %.200s", Py_TYPE(stop_obj)->tp_name);
+ return NULL;
+ }
+
+ if (stop < 0) {
+ stop += self->count;
+ }
+ } else {
+ if (index < 0 || index >= self->count) {
+ PyErr_SetString(PyExc_IndexError, "delete index out of range");
+ return NULL;
+ }
+
+ stop = index + 1;
+ }
+
+ list = PVector_toList(self);
+ if(PyList_SetSlice(list, index, stop, NULL) < 0) {
+ return NULL;
+ }
+
+ result = PVector_extend(EMPTY_VECTOR, list);
+ Py_DECREF(list);
+ return result;
+}
+
+static PyObject* PVector_delete(PVector *self, PyObject *args) {
+ Py_ssize_t index;
+ PyObject *stop_obj = NULL;
+
+ if(!PyArg_ParseTuple(args, "n|O:delete", &index, &stop_obj)) {
+ return NULL;
+ }
+
+ return internalDelete(self, index, stop_obj);
+}
+
+static PyObject* PVector_remove(PVector *self, PyObject *args) {
+ Py_ssize_t index;
+ PyObject* py_index = PVector_index(self, args);
+
+ if(py_index != NULL) {
+#if PY_MAJOR_VERSION >= 3
+ index = PyLong_AsSsize_t(py_index);
+#else
+ index = PyInt_AsSsize_t(py_index);
+#endif
+ Py_DECREF(py_index);
+ return internalDelete(self, index, NULL);
+ }
+
+ PyErr_SetString(PyExc_ValueError, "PVector.remove(x): x not in vector");
+ return NULL;
+}
+
+
+/*********************** PVector Iterator **************************/
+
+/*
+The Sequence class provides us with a default iterator but the runtime
+overhead of using that compared to the iterator below is huge.
+*/
+
+typedef struct {
+ PyObject_HEAD
+ Py_ssize_t it_index;
+ PVector *it_seq; /* Set to NULL when iterator is exhausted */
+} PVectorIter;
+
+static void PVectorIter_dealloc(PVectorIter *);
+static int PVectorIter_traverse(PVectorIter *, visitproc, void *);
+static PyObject *PVectorIter_next(PVectorIter *);
+
+static PyMethodDef PVectorIter_methods[] = {
+ {NULL, NULL} /* sentinel */
+};
+
+static PyTypeObject PVectorIterType = {
+ PyVarObject_HEAD_INIT(NULL, 0)
+ "pvector_iterator", /* tp_name */
+ sizeof(PVectorIter), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)PVectorIter_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)PVectorIter_traverse, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)PVectorIter_next, /* tp_iternext */
+ PVectorIter_methods, /* tp_methods */
+ 0, /* tp_members */
+};
+
+static PyObject *PVectorIter_iter(PyObject *seq) {
+ PVectorIter *it = PyObject_GC_New(PVectorIter, &PVectorIterType);
+ if (it == NULL) {
+ return NULL;
+ }
+
+ it->it_index = 0;
+ Py_INCREF(seq);
+ it->it_seq = (PVector *)seq;
+ PyObject_GC_Track(it);
+ return (PyObject *)it;
+}
+
+static void PVectorIter_dealloc(PVectorIter *it) {
+ PyObject_GC_UnTrack(it);
+ Py_XDECREF(it->it_seq);
+ PyObject_GC_Del(it);
+}
+
+static int PVectorIter_traverse(PVectorIter *it, visitproc visit, void *arg) {
+ Py_VISIT(it->it_seq);
+ return 0;
+}
+
+static PyObject *PVectorIter_next(PVectorIter *it) {
+ assert(it != NULL);
+ PVector *seq = it->it_seq;
+ if (seq == NULL) {
+ return NULL;
+ }
+
+ if (it->it_index < seq->count) {
+ PyObject *item = _get_item(seq, it->it_index);
+ ++it->it_index;
+ Py_INCREF(item);
+ return item;
+ }
+
+ Py_DECREF(seq);
+ it->it_seq = NULL;
+ return NULL;
+}
+
+
+/*********************** PVector Evolver **************************/
+
+/*
+Evolver to make multi updates easier to work with and more efficient.
+*/
+
+static void PVectorEvolver_dealloc(PVectorEvolver *);
+static PyObject *PVectorEvolver_append(PVectorEvolver *, PyObject *);
+static PyObject *PVectorEvolver_extend(PVectorEvolver *, PyObject *);
+static PyObject *PVectorEvolver_set(PVectorEvolver *, PyObject *);
+static PyObject *PVectorEvolver_delete(PVectorEvolver *self, PyObject *args);
+static PyObject *PVectorEvolver_subscript(PVectorEvolver *, PyObject *);
+static PyObject *PVectorEvolver_persistent(PVectorEvolver *);
+static Py_ssize_t PVectorEvolver_len(PVectorEvolver *);
+static PyObject *PVectorEvolver_is_dirty(PVectorEvolver *);
+static int PVectorEvolver_traverse(PVectorEvolver *self, visitproc visit, void *arg);
+
+static PyMappingMethods PVectorEvolver_mapping_methods = {
+ (lenfunc)PVectorEvolver_len,
+ (binaryfunc)PVectorEvolver_subscript,
+ (objobjargproc)PVectorEvolver_set_item,
+};
+
+
+static PyMethodDef PVectorEvolver_methods[] = {
+ {"append", (PyCFunction)PVectorEvolver_append, METH_O, "Appends an element"},
+ {"extend", (PyCFunction)PVectorEvolver_extend, METH_O|METH_COEXIST, "Extend"},
+ {"set", (PyCFunction)PVectorEvolver_set, METH_VARARGS, "Set item"},
+ {"delete", (PyCFunction)PVectorEvolver_delete, METH_VARARGS, "Delete item"},
+ {"persistent", (PyCFunction)PVectorEvolver_persistent, METH_NOARGS, "Create PVector from evolver"},
+ {"is_dirty", (PyCFunction)PVectorEvolver_is_dirty, METH_NOARGS, "Check if evolver contains modifications"},
+ {NULL, NULL} /* sentinel */
+};
+
+static PyTypeObject PVectorEvolverType = {
+ PyVarObject_HEAD_INIT(NULL, 0)
+ "pvector_evolver", /* tp_name */
+ sizeof(PVectorEvolver), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)PVectorEvolver_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ &PVectorEvolver_mapping_methods, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
+ 0, /* tp_doc */
+ (traverseproc)PVectorEvolver_traverse, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ PVectorEvolver_methods, /* tp_methods */
+ 0, /* tp_members */
+};
+
+
+// Indicate that a node is "dirty" (has been updated by the evolver)
+// by setting the MSB of the refCount. This will be cleared when
+// creating a pvector from the evolver (cleaning it).
+#define DIRTY_BIT 0x80000000
+#define REF_COUNT_MASK (~DIRTY_BIT)
+#define IS_DIRTY(node) ((node)->refCount & DIRTY_BIT)
+#define SET_DIRTY(node) ((node)->refCount |= DIRTY_BIT)
+#define CLEAR_DIRTY(node) ((node)->refCount &= REF_COUNT_MASK)
+
+
+static void cleanNodeRecursively(VNode *node, int level) {
+ debug("Cleaning recursively node=%p, level=%u\n", node, level);
+
+ int i;
+ CLEAR_DIRTY(node);
+ SET_NODE_REF_COUNT(node, 1);
+ if(level > 0) {
+ for(i = 0; i < BRANCH_FACTOR; i++) {
+ VNode *nextNode = (VNode*)node->items[i];
+ if((nextNode != NULL) && IS_DIRTY(nextNode)) {
+ cleanNodeRecursively(nextNode, level - SHIFT);
+ }
+ }
+ }
+}
+
+static void cleanVector(PVector *vector) {
+ // Cleaning the vector means that all dirty indications are cleared
+ // and that the nodes that were dirty get a ref count of 1 since
+ // they are brand new. Once cleaned the vector can be released into
+ // the wild.
+ if(IS_DIRTY(vector->tail)) {
+ cleanNodeRecursively(vector->tail, 0);
+ } else {
+ INC_NODE_REF_COUNT(vector->tail);
+ }
+
+ if(IS_DIRTY(vector->root)) {
+ cleanNodeRecursively(vector->root, vector->shift);
+ } else {
+ INC_NODE_REF_COUNT(vector->root);
+ }
+}
+
+static void PVectorEvolver_dealloc(PVectorEvolver *self) {
+ PyObject_GC_UnTrack(self);
+ Py_TRASHCAN_SAFE_BEGIN(self);
+
+ if(self->originalVector != self->newVector) {
+ cleanVector(self->newVector);
+ Py_DECREF(self->newVector);
+ }
+
+ Py_DECREF(self->originalVector);
+ Py_DECREF(self->appendList);
+
+ PyObject_GC_Del(self);
+ Py_TRASHCAN_SAFE_END(self);
+}
+
+static PyObject *PVectorEvolver_append(PVectorEvolver *self, PyObject *args) {
+ if (PyList_Append(self->appendList, args) == 0) {
+ Py_INCREF(self);
+ return (PyObject*)self;
+ }
+
+ return NULL;
+}
+
+static PyObject *PVectorEvolver_extend(PVectorEvolver *self, PyObject *args) {
+ PyObject *retVal = _PyList_Extend((PyListObject *)self->appendList, args);
+ if (retVal == NULL) {
+ return NULL;
+ }
+
+ Py_DECREF(retVal);
+ Py_INCREF(self);
+ return (PyObject*)self;
+}
+
+static PyObject *PVectorEvolver_subscript(PVectorEvolver *self, PyObject *item) {
+ if (PyIndex_Check(item)) {
+ Py_ssize_t position = PyNumber_AsSsize_t(item, PyExc_IndexError);
+ if (position == -1 && PyErr_Occurred()) {
+ return NULL;
+ }
+
+ if (position < 0) {
+ position += self->newVector->count + PyList_GET_SIZE(self->appendList);
+ }
+
+ if(0 <= position && position < self->newVector->count) {
+ PyObject *result = _get_item(self->newVector, position);
+ Py_XINCREF(result);
+ return result;
+ } else if (0 <= position && position < (self->newVector->count + PyList_GET_SIZE(self->appendList))) {
+ PyObject *result = PyList_GetItem(self->appendList, position - self->newVector->count);
+ Py_INCREF(result);
+ return result;
+ } else {
+ PyErr_SetString(PyExc_IndexError, "Index out of range");
+ }
+ } else {
+ PyErr_Format(PyExc_TypeError, "Indices must be integers, not %.200s", item->ob_type->tp_name);
+ }
+
+ return NULL;
+}
+
+static VNode* doSetWithDirty(VNode* node, unsigned int level, unsigned int position, PyObject* value) {
+ VNode* resultNode;
+ debug("doSetWithDirty(): level == %i\n", level);
+ if(level == 0) {
+ if(!IS_DIRTY(node)) {
+ resultNode = allocNode();
+ copyInsert(resultNode->items, node->items, position & BIT_MASK, value);
+ incRefs((PyObject**)resultNode->items);
+ SET_DIRTY(resultNode);
+ } else {
+ resultNode = node;
+ Py_INCREF(value);
+ Py_DECREF(resultNode->items[position & BIT_MASK]);
+ resultNode->items[position & BIT_MASK] = value;
+ }
+ } else {
+ if(!IS_DIRTY(node)) {
+ resultNode = copyNode(node);
+ SET_DIRTY(resultNode);
+ } else {
+ resultNode = node;
+ }
+
+ Py_ssize_t index = (position >> level) & BIT_MASK;
+ VNode* oldNode = (VNode*)resultNode->items[index];
+ resultNode->items[index] = doSetWithDirty(resultNode->items[index], level - SHIFT, position, value);
+
+ if(resultNode->items[index] != oldNode) {
+ // Node replaced, drop references to old node
+ DEC_NODE_REF_COUNT(oldNode);
+ }
+ }
+
+ return resultNode;
+}
+
+/*
+ Steals a reference to the object that is inserted in the vector.
+*/
+static PyObject *PVectorEvolver_set(PVectorEvolver *self, PyObject *args) {
+ PyObject *argObj = NULL; /* argument to insert */
+ PyObject *position = NULL;
+
+ /* The n parses for size, the O parses for a Python object */
+ if(!PyArg_ParseTuple(args, "OO", &position, &argObj)) {
+ return NULL;
+ }
+
+ if(PVectorEvolver_set_item(self, position, argObj) < 0) {
+ return NULL;
+ }
+
+ Py_INCREF(self);
+ return (PyObject*)self;
+}
+
+static PyObject *PVectorEvolver_delete(PVectorEvolver *self, PyObject *args) {
+ PyObject *position = NULL;
+
+ /* The n parses for size, the O parses for a Python object */
+ if(!PyArg_ParseTuple(args, "O", &position)) {
+ return NULL;
+ }
+
+ if(PVectorEvolver_set_item(self, position, NULL) < 0) {
+ return NULL;
+ }
+
+ Py_INCREF(self);
+ return (PyObject*)self;
+}
+
+
+static int internalPVectorDelete(PVectorEvolver *self, Py_ssize_t position) {
+ // Delete element. Should be unusual. Simple but expensive operation
+ // that reuses the delete code for the vector. Realize the vector, delete on it and
+ // then reset the evolver to work on the new vector.
+ PVector *temp = (PVector*)PVectorEvolver_persistent(self);
+ PVector *temp2 = (PVector*)internalDelete(temp, position, NULL);
+ Py_DECREF(temp);
+
+ if(temp2 == NULL) {
+ return -1;
+ }
+
+ Py_DECREF(self->originalVector);
+ self->originalVector = temp2;
+ self->newVector = self->originalVector;
+ return 0;
+}
+
+static int PVectorEvolver_set_item(PVectorEvolver *self, PyObject* item, PyObject* value) {
+ if (PyIndex_Check(item)) {
+ Py_ssize_t position = PyNumber_AsSsize_t(item, PyExc_IndexError);
+ if (position == -1 && PyErr_Occurred()) {
+ return -1;
+ }
+
+ if (position < 0) {
+ position += self->newVector->count + PyList_GET_SIZE(self->appendList);
+ }
+
+ if((0 <= position) && (position < self->newVector->count)) {
+ if(self->originalVector == self->newVector) {
+ // Create new vector since we're about to modify the original
+ self->newVector = rawCopyPVector(self->originalVector);
+ }
+
+ if(value != NULL) {
+ if(position < TAIL_OFF(self->newVector)) {
+ self->newVector->root = doSetWithDirty(self->newVector->root, self->newVector->shift, position, value);
+ } else {
+ self->newVector->tail = doSetWithDirty(self->newVector->tail, 0, position, value);
+ }
+
+ return 0;
+ }
+
+ return internalPVectorDelete(self, position);
+ } else if((0 <= position) && (position < (self->newVector->count + PyList_GET_SIZE(self->appendList)))) {
+ if (value != NULL) {
+ int result = PyList_SetItem(self->appendList, position - self->newVector->count, value);
+ if(result == 0) {
+ Py_INCREF(value);
+ }
+ return result;
+ }
+
+ return internalPVectorDelete(self, position);
+ } else if((0 <= position)
+ && (position < (self->newVector->count + PyList_GET_SIZE(self->appendList) + 1))
+ && (value != NULL)) {
+ return PyList_Append(self->appendList, value);
+ } else {
+ PyErr_Format(PyExc_IndexError, "Index out of range: %zd", position);
+ }
+ } else {
+ PyErr_Format(PyExc_TypeError, "Indices must be integers, not %.200s", item->ob_type->tp_name);
+ }
+ return -1;
+}
+
+static PyObject *PVectorEvolver_persistent(PVectorEvolver *self) {
+ PVector *resultVector;
+ if(self->newVector != self->originalVector) {
+ cleanVector(self->newVector);
+ Py_DECREF(self->originalVector);
+ }
+
+ resultVector = self->newVector;
+
+ if(PyList_GET_SIZE(self->appendList)) {
+ PVector *oldVector = resultVector;
+ resultVector = (PVector*)PVector_extend(resultVector, self->appendList);
+ Py_DECREF(oldVector);
+ Py_DECREF(self->appendList);
+ self->appendList = NULL;
+ }
+
+ initializeEvolver(self, resultVector, self->appendList);
+ Py_INCREF(resultVector);
+ return (PyObject*)resultVector;
+}
+
+static Py_ssize_t PVectorEvolver_len(PVectorEvolver *self) {
+ return self->newVector->count + PyList_GET_SIZE(self->appendList);
+}
+
+static PyObject* PVectorEvolver_is_dirty(PVectorEvolver *self) {
+ if((self->newVector != self->originalVector) || (PyList_GET_SIZE(self->appendList) > 0)) {
+ Py_INCREF(Py_True);
+ return Py_True;
+ }
+
+ Py_INCREF(Py_False);
+ return Py_False;
+}
+
+static int PVectorEvolver_traverse(PVectorEvolver *self, visitproc visit, void *arg) {
+ Py_VISIT(self->newVector);
+ if (self->newVector != self->originalVector) {
+ Py_VISIT(self->originalVector);
+ }
+ Py_VISIT(self->appendList);
+ return 0;
+}
+
+static PyMethodDef PyrsistentMethods[] = {
+ {"pvector", pyrsistent_pvec, METH_VARARGS,
+ "pvector([iterable])\n"
+ "Create a new persistent vector containing the elements in iterable.\n\n"
+ ">>> v1 = pvector([1, 2, 3])\n"
+ ">>> v1\n"
+ "pvector([1, 2, 3])"},
+ {NULL, NULL, 0, NULL}
+};
+
+
+/********************* Python module initialization ************************/
+
+#if PY_MAJOR_VERSION >= 3
+ static struct PyModuleDef moduledef = {
+ PyModuleDef_HEAD_INIT,
+ "pvectorc", /* m_name */
+ "Persistent vector", /* m_doc */
+ -1, /* m_size */
+ PyrsistentMethods, /* m_methods */
+ NULL, /* m_reload */
+ NULL, /* m_traverse */
+ NULL, /* m_clear */
+ NULL, /* m_free */
+ };
+#endif
+
+static PyObject* pyrsistent_pvectorc_moduleinit(void) {
+ PyObject* m;
+
+ // Only allow creation/initialization through factory method pvec
+ PVectorType.tp_init = NULL;
+ PVectorType.tp_new = NULL;
+
+ if (PyType_Ready(&PVectorType) < 0) {
+ return NULL;
+ }
+ if (PyType_Ready(&PVectorIterType) < 0) {
+ return NULL;
+ }
+ if (PyType_Ready(&PVectorEvolverType) < 0) {
+ return NULL;
+ }
+
+
+#if PY_MAJOR_VERSION >= 3
+ m = PyModule_Create(&moduledef);
+#else
+ m = Py_InitModule3("pvectorc", PyrsistentMethods, "Persistent vector");
+#endif
+
+ if (m == NULL) {
+ return NULL;
+ }
+
+ if(EMPTY_VECTOR == NULL) {
+ EMPTY_VECTOR = emptyNewPvec();
+ }
+
+ nodeCache.size = 0;
+
+ Py_INCREF(&PVectorType);
+ PyModule_AddObject(m, "PVector", (PyObject *)&PVectorType);
+
+ return m;
+}
+
+#if PY_MAJOR_VERSION >= 3
+PyMODINIT_FUNC PyInit_pvectorc(void) {
+ return pyrsistent_pvectorc_moduleinit();
+}
+#else
+PyMODINIT_FUNC initpvectorc(void) {
+ pyrsistent_pvectorc_moduleinit();
+}
+#endif