diff options
Diffstat (limited to 'third_party/python/pyrsistent/pvectorcmodule.c')
| -rw-r--r-- | third_party/python/pyrsistent/pvectorcmodule.c | 1642 |
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 |