Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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