How do I create a fixed-length, mutable array of Python objects in Cython?

Question

I need to have an array of python objects to be used in creating a trie datastructure. I need a structure that will be fixed-length like a tuple and mutable like a list. I don't want to use a list because I want to be able to ensure that the list is exactly the right size (if it starts allocating extra elements, the memory overhead could add up very quickly as the trie grows larger). Is there a way to do this? I tried creating an array of objects:

cdef class TrieNode:
    cdef object members[32]

...but that gave an error:

Error compiling Cython file:
------------------------------------------------------------
...
cdef class TrieNode:
    cdef object members[32]
                      ^
------------------------------------------------------------

/Users/jason/src/pysistence/source/pysistence/trie.pyx:2:23: Array element cannot be a Python object

What is the best way to do what I'm trying to do?

Answer 1

I don't know about the best solution, but here's a solution:

from cpython.ref cimport PyObject, Py_XINCREF, Py_XDECREF

DEF SIZE = 32

cdef class TrieNode:
    cdef PyObject *members[SIZE]

    def __cinit__(self):
        cdef object temp_object
        for i in range(SIZE):
            temp_object = int(i)
            # increment its refcount so it's not gc'd.
            # We hold a reference to the object and are responsible for
            # decref-ing it in __dealloc__.
            Py_XINCREF(<PyObject*>temp_object)
            self.members[i] = <PyObject*>temp_object

    def __init__(self):
        # just to show that it works...
        for i in range(SIZE):
            print <object>self.members[i]

    def __dealloc__(self):
        # make sure we decref the members elements.
        for i in range(SIZE):
            Py_XDECREF(self.members[i])
            self.members[i] = NULL

A Cython object is an automatically refcounted PyObject *. You can always roll your own arrays of PyObject *'s as long as you take responsibility for refcounting the little buggers. This can be a major headache for non-trivial cases.

Answer 2

If you only need few fixed sizes of such a structure, I'd look at making classes with uniformly named __slots__, including one size slot to store the size. You'll need to declare a separate class for each size (number of slots). Define a cdecl function to access slots by index. Access performance will probably be not as great as with plain address arithmetics of a C array, but you'll be sure that there's only so many slots and none more.