arraymodule.c

/* Array object implementation */

/* An array is a uniform list -- all items have the same type.
   The item type is restricted to simple C types like int or float */

#ifndef Py_BUILD_CORE_BUILTIN
#  define Py_BUILD_CORE_MODULE 1
#endif

#include "Python.h"
#include "pycore_bytesobject.h"   // _PyBytes_RepeatBuffer
#include "pycore_call.h"          // _PyObject_CallMethod()
#include "pycore_ceval.h"         // _PyEval_GetBuiltin()
#include "pycore_floatobject.h"   // _PY_FLOAT_BIG_ENDIAN
#include "pycore_modsupport.h"    // _PyArg_NoKeywords()
#include "pycore_moduleobject.h"  // _PyModule_GetState()
#include "pycore_tuple.h"         // _PyTuple_FromPairSteal
#include "pycore_weakref.h"       // FT_CLEAR_WEAKREFS()

#include <stddef.h>               // offsetof()
#include <stdbool.h>

/*[clinic input]
module array
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=7d1b8d7f5958fd83]*/

struct arrayobject; /* Forward */
static struct PyModuleDef arraymodule;

/* All possible arraydescr values are defined in the vector "descriptors"
 * below.  That's defined later because the appropriate get and set
 * functions aren't visible yet.
 */
struct arraydescr {
    char typecode[3];  // big enough to store "Zd\0"
    int itemsize;
    PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
    int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
    int (*compareitems)(const void *, const void *, Py_ssize_t);
    int is_integer_type;
    int is_signed;
};

typedef struct arrayobject {
    PyObject_VAR_HEAD
    char *ob_item;
    Py_ssize_t allocated;
    const struct arraydescr *ob_descr;
    PyObject *weakreflist; /* List of weak references */
    Py_ssize_t ob_exports;  /* Number of exported buffers */
} arrayobject;

typedef struct {
    PyObject_HEAD
    Py_ssize_t index;
    arrayobject *ao;
    PyObject* (*getitem)(struct arrayobject *, Py_ssize_t);
} arrayiterobject;

typedef struct {
    PyTypeObject *ArrayType;
    PyTypeObject *ArrayIterType;

    PyObject *array_reconstructor;

    PyObject *str_read;
    PyObject *str_write;
    PyObject *str___dict__;
    PyObject *str_iter;
} array_state;

static array_state *
get_array_state(PyObject *module)
{
    return (array_state *)_PyModule_GetState(module);
}

#define find_array_state_by_type(tp) \
    (get_array_state(PyType_GetModuleByDef(tp, &arraymodule)))
#define get_array_state_by_class(cls) \
    (get_array_state(PyType_GetModule(cls)))

#define arrayobject_CAST(op)        ((arrayobject *)(op))
#define arrayiterobject_CAST(op)    ((arrayiterobject *)(op))

enum machine_format_code {
    UNKNOWN_FORMAT = -1,
    /* UNKNOWN_FORMAT is used to indicate that the machine format for an
     * array type code cannot be interpreted. When this occurs, a list of
     * Python objects is used to represent the content of the array
     * instead of using the memory content of the array directly. In that
     * case, the array_reconstructor mechanism is bypassed completely, and
     * the standard array constructor is used instead.
     */

    UNSIGNED_INT8 = 0,
    SIGNED_INT8 = 1,
    UNSIGNED_INT16_LE = 2,
    UNSIGNED_INT16_BE = 3,
    SIGNED_INT16_LE = 4,
    SIGNED_INT16_BE = 5,
    UNSIGNED_INT32_LE = 6,
    UNSIGNED_INT32_BE = 7,
    SIGNED_INT32_LE = 8,
    SIGNED_INT32_BE = 9,
    UNSIGNED_INT64_LE = 10,
    UNSIGNED_INT64_BE = 11,
    SIGNED_INT64_LE = 12,
    SIGNED_INT64_BE = 13,
    IEEE_754_FLOAT_LE = 14,
    IEEE_754_FLOAT_BE = 15,
    IEEE_754_DOUBLE_LE = 16,
    IEEE_754_DOUBLE_BE = 17,
    UTF16_LE = 18,
    UTF16_BE = 19,
    UTF32_LE = 20,
    UTF32_BE = 21,
    IEEE_754_FLOAT_COMPLEX_LE = 22,
    IEEE_754_FLOAT_COMPLEX_BE = 23,
    IEEE_754_DOUBLE_COMPLEX_LE = 24,
    IEEE_754_DOUBLE_COMPLEX_BE = 25,
    IEEE_754_FLOAT16_LE = 26,
    IEEE_754_FLOAT16_BE = 27
};
#define MACHINE_FORMAT_CODE_MIN 0
#define MACHINE_FORMAT_CODE_MAX 27


/*
 * Must come after arrayobject, arrayiterobject,
 * and enum machine_code_type definitions.
 */
#include "clinic/arraymodule.c.h"

#define array_Check(op, state) PyObject_TypeCheck(op, state->ArrayType)

static int
array_resize(arrayobject *self, Py_ssize_t newsize)
{
    char *items;
    size_t _new_size;

    if (self->ob_exports > 0 && newsize != Py_SIZE(self)) {
        PyErr_SetString(PyExc_BufferError,
            "cannot resize an array that is exporting buffers");
        return -1;
    }

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize is 16 smaller than the
       current size, then proceed with the realloc() to shrink the array.
    */

    if (self->allocated >= newsize &&
        Py_SIZE(self) < newsize + 16 &&
        self->ob_item != NULL) {
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    if (newsize == 0) {
        PyMem_Free(self->ob_item);
        self->ob_item = NULL;
        Py_SET_SIZE(self, 0);
        self->allocated = 0;
        return 0;
    }

    /* This over-allocates proportional to the array size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
     * Note, the pattern starts out the same as for lists but then
     * grows at a smaller rate so that larger arrays only overallocate
     * by about 1/16th -- this is done because arrays are presumed to be more
     * memory critical.
     */

    _new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
    items = self->ob_item;
    /* XXX The following multiplication and division does not optimize away
       like it does for lists since the size is not known at compile time */
    if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
        PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = _new_size;
    return 0;
}

/****************************************************************************
Get and Set functions for each type.
A Get function takes an arrayobject* and an integer index, returning the
array value at that index wrapped in an appropriate PyObject*.
A Set function takes an arrayobject, integer index, and PyObject*; sets
the array value at that index to the raw C data extracted from the PyObject*,
and returns 0 if successful, else nonzero on failure (PyObject* not of an
appropriate type or value).
Note that the basic Get and Set functions do NOT check that the index is
in bounds; that's the responsibility of the caller.
****************************************************************************/

/* Macro to check array buffer validity and bounds after calling
   user-defined methods (like __index__ or __float__) that might modify
   the array during the call.
*/
#define CHECK_ARRAY_BOUNDS(OP, IDX)                         \
    do {                                                    \
        if ((IDX) >= 0 && ((OP)->ob_item == NULL ||         \
                  (IDX) >= Py_SIZE((OP)))) {                \
            PyErr_SetString(PyExc_IndexError,               \
                    "array assignment index out of range"); \
            return -1;                                      \
        }                                                   \
    } while (0)

#define CHECK_ARRAY_BOUNDS_WITH_CLEANUP(OP, IDX, VAL, CLEANUP)  \
    do {                                                        \
        if ((IDX) >= 0 && ((OP)->ob_item == NULL ||             \
                  (IDX) >= Py_SIZE((OP)))) {                    \
            PyErr_SetString(PyExc_IndexError,                   \
                    "array assignment index out of range");     \
            if (CLEANUP) {                                      \
                Py_DECREF(VAL);                                 \
            }                                                   \
            return -1;                                          \
        }                                                       \
    } while (0)

static PyObject *
b_getitem(arrayobject *ap, Py_ssize_t i)
{
    long x = ((signed char *)ap->ob_item)[i];
    return PyLong_FromLong(x);
}

static int
b_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    short x;
    /* PyArg_Parse's 'b' formatter is for an unsigned char, therefore
       must use the next size up that is signed ('h') and manually do
       the overflow checking */
    if (!PyArg_Parse(v, "h;array item must be integer", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (x < -128) {
        PyErr_SetString(PyExc_OverflowError,
            "signed char is less than minimum");
        return -1;
    }
    else if (x > 127) {
        PyErr_SetString(PyExc_OverflowError,
            "signed char is greater than maximum");
        return -1;
    }
    if (i >= 0)
        ((char *)ap->ob_item)[i] = (char)x;
    return 0;
}

static PyObject *
BB_getitem(arrayobject *ap, Py_ssize_t i)
{
    long x = ((unsigned char *)ap->ob_item)[i];
    return PyLong_FromLong(x);
}

static int
BB_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned char x;
    /* 'B' == unsigned char, maps to PyArg_Parse's 'b' formatter */
    if (!PyArg_Parse(v, "b;array item must be integer", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
        ((unsigned char *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
u_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyUnicode_FromOrdinal(((wchar_t *) ap->ob_item)[i]);
}

static int
u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    if (!PyUnicode_Check(v)) {
        PyErr_Format(PyExc_TypeError,
                     "array item must be a unicode character, not %T",
                     v);
        return -1;
    }

    Py_ssize_t len = PyUnicode_AsWideChar(v, NULL, 0);
    if (len != 2) {
        if (PyUnicode_GET_LENGTH(v) != 1) {
            PyErr_Format(PyExc_TypeError,
                         "array item must be a unicode character, "
                         "not a string of length %zd",
                         PyUnicode_GET_LENGTH(v));
        }
        else {
            PyErr_Format(PyExc_TypeError,
                         "string %A cannot be converted to "
                         "a single wchar_t character",
                         v);
        }
        return -1;
    }

    wchar_t w;
    len = PyUnicode_AsWideChar(v, &w, 1);
    assert(len == 1);

    if (i >= 0) {
        ((wchar_t *)ap->ob_item)[i] = w;
    }
    return 0;
}

static PyObject *
w_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyUnicode_FromOrdinal(((Py_UCS4 *) ap->ob_item)[i]);
}

static int
w_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    if (!PyUnicode_Check(v)) {
        PyErr_Format(PyExc_TypeError,
                     "array item must be a unicode character, not %T",
                     v);
        return -1;
    }

    if (PyUnicode_GET_LENGTH(v) != 1) {
        PyErr_Format(PyExc_TypeError,
                     "array item must be a unicode character, "
                     "not a string of length %zd",
                     PyUnicode_GET_LENGTH(v));
        return -1;
    }

    if (i >= 0) {
        ((Py_UCS4 *)ap->ob_item)[i] = PyUnicode_READ_CHAR(v, 0);
    }
    return 0;
}

static PyObject *
h_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong((long) ((short *)ap->ob_item)[i]);
}


static int
h_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    short x;
    /* 'h' == signed short, maps to PyArg_Parse's 'h' formatter */
    if (!PyArg_Parse(v, "h;array item must be integer", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
                 ((short *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
HH_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong((long) ((unsigned short *)ap->ob_item)[i]);
}

static int
HH_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    int x;
    /* PyArg_Parse's 'h' formatter is for a signed short, therefore
       must use the next size up and manually do the overflow checking */
    if (!PyArg_Parse(v, "i;array item must be integer", &x))
        return -1;
    else if (x < 0) {
        PyErr_SetString(PyExc_OverflowError,
            "unsigned short is less than minimum");
        return -1;
    }
    else if (x > USHRT_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "unsigned short is greater than maximum");
        return -1;
    }

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
        ((short *)ap->ob_item)[i] = (short)x;
    return 0;
}

static PyObject *
i_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong((long) ((int *)ap->ob_item)[i]);
}

static int
i_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    int x;
    /* 'i' == signed int, maps to PyArg_Parse's 'i' formatter */
    if (!PyArg_Parse(v, "i;array item must be integer", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
                 ((int *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
II_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromUnsignedLong(
        (unsigned long) ((unsigned int *)ap->ob_item)[i]);
}

static int
II_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned long x;
    int do_decref = 0; /* if nb_int was called */

    if (!PyLong_Check(v)) {
        Py_INCREF(v);
        PyObject *res = _PyNumber_Index(v);
        Py_DECREF(v);
        if (NULL == res) {
            return -1;
        }
        v = res;
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLong(v);
    if (x == (unsigned long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (x > UINT_MAX) {
        PyErr_SetString(PyExc_OverflowError,
                        "unsigned int is greater than maximum");
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }

    CHECK_ARRAY_BOUNDS_WITH_CLEANUP(ap, i, v, do_decref);

    if (i >= 0)
        ((unsigned int *)ap->ob_item)[i] = (unsigned int)x;

    if (do_decref) {
        Py_DECREF(v);
    }
    return 0;
}

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

static int
l_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    long x;
    if (!PyArg_Parse(v, "l;array item must be integer", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
                 ((long *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
LL_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromUnsignedLong(((unsigned long *)ap->ob_item)[i]);
}

static int
LL_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned long x;
    int do_decref = 0; /* if nb_int was called */

    if (!PyLong_Check(v)) {
        Py_INCREF(v);
        PyObject *res = _PyNumber_Index(v);
        Py_DECREF(v);
        if (NULL == res) {
            return -1;
        }
        v = res;
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLong(v);
    if (x == (unsigned long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }

    CHECK_ARRAY_BOUNDS_WITH_CLEANUP(ap, i, v, do_decref);

    if (i >= 0)
        ((unsigned long *)ap->ob_item)[i] = x;

    if (do_decref) {
        Py_DECREF(v);
    }
    return 0;
}

static PyObject *
q_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLongLong(((long long *)ap->ob_item)[i]);
}

static int
q_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    long long x;
    if (!PyArg_Parse(v, "L;array item must be integer", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
        ((long long *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
QQ_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromUnsignedLongLong(
        ((unsigned long long *)ap->ob_item)[i]);
}

static int
QQ_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    unsigned long long x;
    int do_decref = 0; /* if nb_int was called */

    if (!PyLong_Check(v)) {
        Py_INCREF(v);
        PyObject *res = _PyNumber_Index(v);
        Py_DECREF(v);
        if (NULL == res) {
            return -1;
        }
        v = res;
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLongLong(v);
    if (x == (unsigned long long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }

    CHECK_ARRAY_BOUNDS_WITH_CLEANUP(ap, i, v, do_decref);

    if (i >= 0)
        ((unsigned long long *)ap->ob_item)[i] = x;

    if (do_decref) {
        Py_DECREF(v);
    }
    return 0;
}

static PyObject *
e_getitem(arrayobject *ap, Py_ssize_t i)
{
    double x = PyFloat_Unpack2(ap->ob_item + sizeof(short)*i,
                               PY_LITTLE_ENDIAN);

    return PyFloat_FromDouble(x);
}

static int
e_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    float x;
    if (!PyArg_Parse(v, "f;array item must be float", &x)) {
        return -1;
    }

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0) {
        return PyFloat_Pack2(x, ap->ob_item + sizeof(short)*i,
                             PY_LITTLE_ENDIAN);
    }
    return 0;
}

static PyObject *
f_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyFloat_FromDouble((double) ((float *)ap->ob_item)[i]);
}

static int
f_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    float x;
    if (!PyArg_Parse(v, "f;array item must be float", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
                 ((float *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
d_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyFloat_FromDouble(((double *)ap->ob_item)[i]);
}

static int
d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    double x;
    if (!PyArg_Parse(v, "d;array item must be float", &x))
        return -1;

    CHECK_ARRAY_BOUNDS(ap, i);

    if (i >= 0)
                 ((double *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
cf_getitem(arrayobject *ap, Py_ssize_t i)
{
    float f[2];

    memcpy(&f, ap->ob_item + i*sizeof(f), sizeof(f));
    return PyComplex_FromDoubles(f[0], f[1]);
}

static int
cf_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    Py_complex x;
    float f[2];

    if (!PyArg_Parse(v, "D;array item must be complex", &x)) {
        return -1;
    }

    CHECK_ARRAY_BOUNDS(ap, i);

    f[0] = (float)x.real;
    f[1] = (float)x.imag;
    if (i >= 0) {
        memcpy(ap->ob_item + i*sizeof(f), &f, sizeof(f));
    }
    return 0;
}

static PyObject *
cd_getitem(arrayobject *ap, Py_ssize_t i)
{
    double f[2];

    memcpy(&f, ap->ob_item + i*sizeof(f), sizeof(f));
    return PyComplex_FromDoubles(f[0], f[1]);
}

static int
cd_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    Py_complex x;
    double f[2];

    if (!PyArg_Parse(v, "D;array item must be complex", &x)) {
        return -1;
    }

    CHECK_ARRAY_BOUNDS(ap, i);

    f[0] = x.real;
    f[1] = x.imag;
    if (i >= 0) {
        memcpy(ap->ob_item + i*sizeof(f), &f, sizeof(f));
    }
    return 0;
}

#define DEFINE_COMPAREITEMS(code, type) \
    static int \
    code##_compareitems(const void *lhs, const void *rhs, Py_ssize_t length) \
    { \
        const type *a = lhs, *b = rhs; \
        for (Py_ssize_t i = 0; i < length; ++i) \
            if (a[i] != b[i]) \
                return a[i] < b[i] ? -1 : 1; \
        return 0; \
    }

DEFINE_COMPAREITEMS(b, signed char)
DEFINE_COMPAREITEMS(BB, unsigned char)
DEFINE_COMPAREITEMS(u, wchar_t)
DEFINE_COMPAREITEMS(w, Py_UCS4)
DEFINE_COMPAREITEMS(h, short)
DEFINE_COMPAREITEMS(HH, unsigned short)
DEFINE_COMPAREITEMS(i, int)
DEFINE_COMPAREITEMS(II, unsigned int)
DEFINE_COMPAREITEMS(l, long)
DEFINE_COMPAREITEMS(LL, unsigned long)
DEFINE_COMPAREITEMS(q, long long)
DEFINE_COMPAREITEMS(QQ, unsigned long long)

/* Description of types.
 *
 * Don't forget to update typecode_to_mformat_code() if you add a new
 * typecode.
 */
static const struct arraydescr descriptors[] = {
    {"b", 1, b_getitem, b_setitem, b_compareitems, 1, 1},
    {"B", 1, BB_getitem, BB_setitem, BB_compareitems, 1, 0},
    {"u", sizeof(wchar_t), u_getitem, u_setitem, u_compareitems, 0, 0},
    {"w", sizeof(Py_UCS4), w_getitem, w_setitem, w_compareitems, 0, 0,},
    {"h", sizeof(short), h_getitem, h_setitem, h_compareitems, 1, 1},
    {"H", sizeof(short), HH_getitem, HH_setitem, HH_compareitems, 1, 0},
    {"i", sizeof(int), i_getitem, i_setitem, i_compareitems, 1, 1},
    {"I", sizeof(int), II_getitem, II_setitem, II_compareitems, 1, 0},
    {"l", sizeof(long), l_getitem, l_setitem, l_compareitems, 1, 1},
    {"L", sizeof(long), LL_getitem, LL_setitem, LL_compareitems, 1, 0},
    {"q", sizeof(long long), q_getitem, q_setitem, q_compareitems, 1, 1},
    {"Q", sizeof(long long), QQ_getitem, QQ_setitem, QQ_compareitems, 1, 0},
    {"e", sizeof(short), e_getitem, e_setitem, NULL, 0, 0},
    {"f", sizeof(float), f_getitem, f_setitem, NULL, 0, 0},
    {"d", sizeof(double), d_getitem, d_setitem, NULL, 0, 0},
    {"Zf", 2*sizeof(float), cf_getitem, cf_setitem, NULL, 0, 0},
    {"Zd", 2*sizeof(double), cd_getitem, cd_setitem, NULL, 0, 0},
    {"", 0, 0, 0, 0, 0, 0} /* Sentinel */
};

/****************************************************************************
Implementations of array object methods.
****************************************************************************/
/*[clinic input]
class array.array "arrayobject *" "ArrayType"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=a5c29edf59f176a3]*/

static PyObject *
newarrayobject(PyTypeObject *type, Py_ssize_t size, const struct arraydescr *descr)
{
    arrayobject *op;
    size_t nbytes;

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }

    /* Check for overflow */
    if (size > PY_SSIZE_T_MAX / descr->itemsize) {
        return PyErr_NoMemory();
    }
    nbytes = size * descr->itemsize;
    op = (arrayobject *) type->tp_alloc(type, 0);
    if (op == NULL) {
        return NULL;
    }
    op->ob_descr = descr;
    op->allocated = size;
    op->weakreflist = NULL;
    Py_SET_SIZE(op, size);
    if (size <= 0) {
        op->ob_item = NULL;
    }
    else {
        op->ob_item = PyMem_NEW(char, nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    op->ob_exports = 0;
    return (PyObject *) op;
}

static PyObject *
getarrayitem(PyObject *op, Py_ssize_t i)
{
#ifndef NDEBUG
    array_state *state = find_array_state_by_type(Py_TYPE(op));
    assert(array_Check(op, state));
#endif
    arrayobject *ap;
    ap = (arrayobject *)op;
    assert(i>=0 && i<Py_SIZE(ap));
    return (*ap->ob_descr->getitem)(ap, i);
}

static int
ins1(arrayobject *self, Py_ssize_t where, PyObject *v)
{
    char *items;
    Py_ssize_t n = Py_SIZE(self);
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if ((*self->ob_descr->setitem)(self, -1, v) < 0)
        return -1;

    if (array_resize(self, n+1) == -1)
        return -1;
    items = self->ob_item;
    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    /* appends don't need to call memmove() */
    if (where != n)
        memmove(items + (where+1)*self->ob_descr->itemsize,
            items + where*self->ob_descr->itemsize,
            (n-where)*self->ob_descr->itemsize);
    return (*self->ob_descr->setitem)(self, where, v);
}

/* Methods */
static void
array_dealloc(PyObject *op)
{
    PyTypeObject *tp = Py_TYPE(op);
    PyObject_GC_UnTrack(op);

    arrayobject *self = arrayobject_CAST(op);
    FT_CLEAR_WEAKREFS(op, self->weakreflist);
    if (self->ob_item != NULL) {
        PyMem_Free(self->ob_item);
    }
    tp->tp_free(op);
    Py_DECREF(tp);
}

static PyObject *
array_richcompare(PyObject *v, PyObject *w, int op)
{
    array_state *state = find_array_state_by_type(Py_TYPE(v));
    arrayobject *va, *wa;
    PyObject *vi = NULL;
    PyObject *wi = NULL;
    Py_ssize_t i, k;
    PyObject *res;

    if (!array_Check(v, state) || !array_Check(w, state))
        Py_RETURN_NOTIMPLEMENTED;

    va = (arrayobject *)v;
    wa = (arrayobject *)w;

    if (Py_SIZE(va) != Py_SIZE(wa) && (op == Py_EQ || op == Py_NE)) {
        /* Shortcut: if the lengths differ, the arrays differ */
        if (op == Py_EQ)
            res = Py_False;
        else
            res = Py_True;
        return Py_NewRef(res);
    }

    if (va->ob_descr == wa->ob_descr && va->ob_descr->compareitems != NULL) {
        /* Fast path:
           arrays with same types can have their buffers compared directly */
        Py_ssize_t common_length = Py_MIN(Py_SIZE(va), Py_SIZE(wa));
        int result = va->ob_descr->compareitems(va->ob_item, wa->ob_item,
                                                common_length);
        if (result == 0)
            goto compare_sizes;

        int cmp;
        switch (op) {
        case Py_LT: cmp = result < 0; break;
        case Py_LE: cmp = result <= 0; break;
        case Py_EQ: cmp = result == 0; break;
        case Py_NE: cmp = result != 0; break;
        case Py_GT: cmp = result > 0; break;
        case Py_GE: cmp = result >= 0; break;
        default: return NULL; /* cannot happen */
        }
        PyObject *res = cmp ? Py_True : Py_False;
        return Py_NewRef(res);
    }


    /* Search for the first index where items are different */
    k = 1;
    for (i = 0; i < Py_SIZE(va) && i < Py_SIZE(wa); i++) {
        vi = getarrayitem(v, i);
        if (vi == NULL) {
            return NULL;
        }
        wi = getarrayitem(w, i);
        if (wi == NULL) {
            Py_DECREF(vi);
            return NULL;
        }
        k = PyObject_RichCompareBool(vi, wi, Py_EQ);
        if (k == 0)
            break; /* Keeping vi and wi alive! */
        Py_DECREF(vi);
        Py_DECREF(wi);
        if (k < 0)
            return NULL;
    }

    if (k) {
        /* No more items to compare -- compare sizes */
        compare_sizes: ;
        Py_ssize_t vs = Py_SIZE(va);
        Py_ssize_t ws = Py_SIZE(wa);
        int cmp;
        switch (op) {
        case Py_LT: cmp = vs <  ws; break;
        case Py_LE: cmp = vs <= ws; break;
        /* If the lengths were not equal,
           the earlier fast-path check would have caught that. */
        case Py_EQ: assert(vs == ws); cmp = 1; break;
        case Py_NE: assert(vs == ws); cmp = 0; break;
        case Py_GT: cmp = vs >  ws; break;
        case Py_GE: cmp = vs >= ws; break;
        default: return NULL; /* cannot happen */
        }
        if (cmp)
            res = Py_True;
        else
            res = Py_False;
        return Py_NewRef(res);
    }

    /* We have an item that differs.  First, shortcuts for EQ/NE */
    if (op == Py_EQ) {
        res = Py_NewRef(Py_False);
    }
    else if (op == Py_NE) {
        res = Py_NewRef(Py_True);
    }
    else {
        /* Compare the final item again using the proper operator */
        res = PyObject_RichCompare(vi, wi, op);
    }
    Py_DECREF(vi);