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 */

#define PY_SSIZE_T_CLEAN
#include "Python.h"
#include "structmember.h"

#ifdef STDC_HEADERS
#include <stddef.h>
#else /* !STDC_HEADERS */
#ifdef HAVE_SYS_TYPES_H
#include <sys/types.h>          /* For size_t */
#endif /* HAVE_SYS_TYPES_H */
#endif /* !STDC_HEADERS */

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

struct arrayobject; /* Forward */

/* 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;
    int itemsize;
    PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
    int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
    char *formats;
    int is_integer_type;
    int is_signed;
};

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

static PyTypeObject Arraytype;

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

static PyTypeObject PyArrayIter_Type;

#define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)

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.
     *
     * This is will most likely occur when the machine doesn't use IEEE
     * floating-point numbers.
     */

    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
};
#define MACHINE_FORMAT_CODE_MIN 0
#define MACHINE_FORMAT_CODE_MAX 21


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

#define array_Check(op) PyObject_TypeCheck(op, &Arraytype)
#define array_CheckExact(op) (Py_TYPE(op) == &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_SIZE(self) = newsize;
        return 0;
    }

    if (newsize == 0) {
        PyMem_FREE(self->ob_item);
        self->ob_item = NULL;
        Py_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_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.
****************************************************************************/

static PyObject *
b_getitem(arrayobject *ap, Py_ssize_t i)
{
    long x = ((char *)ap->ob_item)[i];
    if (x >= 128)
        x -= 256;
    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;
    else 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;
    if (i >= 0)
        ((char *)ap->ob_item)[i] = x;
    return 0;
}

static PyObject *
u_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyUnicode_FromUnicode(&((Py_UNICODE *) ap->ob_item)[i], 1);
}

static int
u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    Py_UNICODE *p;
    Py_ssize_t len;

    if (!PyArg_Parse(v, "u#;array item must be unicode character", &p, &len))
        return -1;
    if (len != 1) {
        PyErr_SetString(PyExc_TypeError,
                        "array item must be unicode character");
        return -1;
    }
    if (i >= 0)
        ((Py_UNICODE *)ap->ob_item)[i] = p[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;
    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;
    }
    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;
    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 PyObject *
get_int_unless_float(PyObject *v)
{
    if (PyFloat_Check(v)) {
        PyErr_SetString(PyExc_TypeError,
                        "array item must be integer");
        return NULL;
    }
    return (PyObject *)_PyLong_FromNbInt(v);
}

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)) {
        v = get_int_unless_float(v);
        if (NULL == v) {
            return -1;
        }
        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;
    }
    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;
    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)) {
        v = get_int_unless_float(v);
        if (NULL == v) {
            return -1;
        }
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLong(v);
    if (x == (unsigned long)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (i >= 0)
        ((unsigned long *)ap->ob_item)[i] = x;

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

#ifdef HAVE_LONG_LONG

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

static int
q_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
{
    PY_LONG_LONG x;
    if (!PyArg_Parse(v, "L;array item must be integer", &x))
        return -1;
    if (i >= 0)
        ((PY_LONG_LONG *)ap->ob_item)[i] = x;
    return 0;
}

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

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

    if (!PyLong_Check(v)) {
        v = get_int_unless_float(v);
        if (NULL == v) {
            return -1;
        }
        do_decref = 1;
    }
    x = PyLong_AsUnsignedLongLong(v);
    if (x == (unsigned PY_LONG_LONG)-1 && PyErr_Occurred()) {
        if (do_decref) {
            Py_DECREF(v);
        }
        return -1;
    }
    if (i >= 0)
        ((unsigned PY_LONG_LONG *)ap->ob_item)[i] = x;

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

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;
    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;
    if (i >= 0)
                 ((double *)ap->ob_item)[i] = x;
    return 0;
}


/* Description of types.
 *
 * Don't forget to update typecode_to_mformat_code() if you add a new
 * typecode.
 */
static struct arraydescr descriptors[] = {
    {'b', 1, b_getitem, b_setitem, "b", 1, 1},
    {'B', 1, BB_getitem, BB_setitem, "B", 1, 0},
    {'u', sizeof(Py_UNICODE), u_getitem, u_setitem, "u", 0, 0},
    {'h', sizeof(short), h_getitem, h_setitem, "h", 1, 1},
    {'H', sizeof(short), HH_getitem, HH_setitem, "H", 1, 0},
    {'i', sizeof(int), i_getitem, i_setitem, "i", 1, 1},
    {'I', sizeof(int), II_getitem, II_setitem, "I", 1, 0},
    {'l', sizeof(long), l_getitem, l_setitem, "l", 1, 1},
    {'L', sizeof(long), LL_getitem, LL_setitem, "L", 1, 0},
#ifdef HAVE_LONG_LONG
    {'q', sizeof(PY_LONG_LONG), q_getitem, q_setitem, "q", 1, 1},
    {'Q', sizeof(PY_LONG_LONG), QQ_getitem, QQ_setitem, "Q", 1, 0},
#endif
    {'f', sizeof(float), f_getitem, f_setitem, "f", 0, 0},
    {'d', sizeof(double), d_getitem, d_setitem, "d", 0, 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=ad43d37e942a8854]*/

static PyObject *
newarrayobject(PyTypeObject *type, Py_ssize_t size, 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_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)
{
    arrayobject *ap;
    assert(array_Check(op));
    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(arrayobject *op)
{
    if (op->weakreflist != NULL)
        PyObject_ClearWeakRefs((PyObject *) op);
    if (op->ob_item != NULL)
        PyMem_DEL(op->ob_item);
    Py_TYPE(op)->tp_free((PyObject *)op);
}

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

    if (!array_Check(v) || !array_Check(w))
        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;
        Py_INCREF(res);
        return 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);
        wi = getarrayitem(w, i);
        if (vi == NULL || wi == NULL) {
            Py_XDECREF(vi);
            Py_XDECREF(wi);
            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 */
        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;
        case Py_EQ: cmp = vs == ws; break;
        case Py_NE: cmp = vs != ws; 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;
        Py_INCREF(res);
        return res;
    }

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

static Py_ssize_t
array_length(arrayobject *a)
{
    return Py_SIZE(a);
}

static PyObject *
array_item(arrayobject *a, Py_ssize_t i)
{
    if (i < 0 || i >= Py_SIZE(a)) {
        PyErr_SetString(PyExc_IndexError, "array index out of range");
        return NULL;
    }
    return getarrayitem((PyObject *)a, i);
}

static PyObject *
array_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    arrayobject *np;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < 0)
        ihigh = 0;
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    np = (arrayobject *) newarrayobject(&Arraytype, ihigh - ilow, a->ob_descr);
    if (np == NULL)
        return NULL;
    if (ihigh > ilow) {
        memcpy(np->ob_item, a->ob_item + ilow * a->ob_descr->itemsize,
               (ihigh-ilow) * a->ob_descr->itemsize);
    }
    return (PyObject *)np;
}


/*[clinic input]
array.array.__copy__

Return a copy of the array.
[clinic start generated code]*/

static PyObject *
array_array___copy___impl(arrayobject *self)
/*[clinic end generated code: output=dec7c3f925d9619e input=ad1ee5b086965f09]*/
{
    return array_slice(self, 0, Py_SIZE(self));
}

/*[clinic input]
array.array.__deepcopy__

    unused: object
    /

Return a copy of the array.
[clinic start generated code]*/

static PyObject *
array_array___deepcopy__(arrayobject *self, PyObject *unused)
/*[clinic end generated code: output=1ec748d8e14a9faa input=2405ecb4933748c4]*/
{
    return array_array___copy___impl(self);
}

static PyObject *
array_concat(arrayobject *a, PyObject *bb)
{
    Py_ssize_t size;
    arrayobject *np;
    if (!array_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
             "can only append array (not \"%.200s\") to array",
                 Py_TYPE(bb)->tp_name);
        return NULL;
    }
#define b ((arrayobject *)bb)
    if (a->ob_descr != b->ob_descr) {
        PyErr_BadArgument();
        return NULL;
    }
    if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b)) {
        return PyErr_NoMemory();
    }
    size = Py_SIZE(a) + Py_SIZE(b);
    np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
    if (np == NULL) {
        return NULL;
    }
    if (Py_SIZE(a) > 0) {
        memcpy(np->ob_item, a->ob_item, Py_SIZE(a)*a->ob_descr->itemsize);
    }
    if (Py_SIZE(b) > 0) {
        memcpy(np->ob_item + Py_SIZE(a)*a->ob_descr->itemsize,
               b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
    }
    return (PyObject *)np;
#undef b
}

static PyObject *
array_repeat(arrayobject *a, Py_ssize_t n)
{
    Py_ssize_t size;
    arrayobject *np;
    Py_ssize_t oldbytes, newbytes;
    if (n < 0)
        n = 0;
    if ((Py_SIZE(a) != 0) && (n > PY_SSIZE_T_MAX / Py_SIZE(a))) {
        return PyErr_NoMemory();
    }
    size = Py_SIZE(a) * n;
    np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
    if (np == NULL)
        return NULL;
    if (size == 0)
        return (PyObject *)np;
    oldbytes = Py_SIZE(a) * a->ob_descr->itemsize;
    newbytes = oldbytes * n;
    /* this follows the code in unicode_repeat */
    if (oldbytes == 1) {
        memset(np->ob_item, a->ob_item[0], newbytes);
    } else {
        Py_ssize_t done = oldbytes;
        Py_MEMCPY(np->ob_item, a->ob_item, oldbytes);
        while (done < newbytes) {
            Py_ssize_t ncopy = (done <= newbytes-done) ? done : newbytes-done;
            Py_MEMCPY(np->ob_item+done, np->ob_item, ncopy);
            done += ncopy;
        }
    }
    return (PyObject *)np;
}

static int
array_ass_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
{
    char *item;
    Py_ssize_t n; /* Size of replacement array */
    Py_ssize_t d; /* Change in size */
#define b ((arrayobject *)v)
    if (v == NULL)
        n = 0;
    else if (array_Check(v)) {
        n = Py_SIZE(b);
        if (a == b) {
            /* Special case "a[i:j] = a" -- copy b first */
            int ret;
            v = array_slice(b, 0, n);
            if (!v)
                return -1;
            ret = array_ass_slice(a, ilow, ihigh, v);
            Py_DECREF(v);
            return ret;
        }
        if (b->ob_descr != a->ob_descr) {
            PyErr_BadArgument();
            return -1;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
         "can only assign array (not \"%.200s\") to array slice",
                         Py_TYPE(v)->tp_name);
        return -1;
    }
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < 0)
        ihigh = 0;
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    item = a->ob_item;
    d = n - (ihigh-ilow);
    /* Issue #4509: If the array has exported buffers and the slice
       assignment would change the size of the array, fail early to make
       sure we don't modify it. */
    if (d != 0 && a->ob_exports > 0) {
        PyErr_SetString(PyExc_BufferError,
            "cannot resize an array that is exporting buffers");
        return -1;
    }
    if (d < 0) { /* Delete -d items */
        memmove(item + (ihigh+d)*a->ob_descr->itemsize,
            item + ihigh*a->ob_descr->itemsize,
            (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
        if (array_resize(a, Py_SIZE(a) + d) == -1)
            return -1;
    }
    else if (d > 0) { /* Insert d items */
        if (array_resize(a, Py_SIZE(a) + d))
            return -1;
        memmove(item + (ihigh+d)*a->ob_descr->itemsize,
            item + ihigh*a->ob_descr->itemsize,
            (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
    }
    if (n > 0)
        memcpy(item + ilow*a->ob_descr->itemsize, b->ob_item,
               n*b->ob_descr->itemsize);
    return 0;
#undef b
}

static int
array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)
{
    if (i < 0 || i >= Py_SIZE(a)) {
        PyErr_SetString(PyExc_IndexError,
                         "array assignment index out of range");
        return -1;
    }
    if (v == NULL)
        return array_ass_slice(a, i, i+1, v);
    return (*a->ob_descr->setitem)(a, i, v);
}

static int
setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)
{
    assert(array_Check(a));
    return array_ass_item((arrayobject *)a, i, v);
}

static int
array_iter_extend(arrayobject *self, PyObject *bb)
{
    PyObject *it, *v;

    it = PyObject_GetIter(bb);
    if (it == NULL)
        return -1;

    while ((v = PyIter_Next(it)) != NULL) {
        if (ins1(self, Py_SIZE(self), v) != 0) {
            Py_DECREF(v);
            Py_DECREF(it);
            return -1;
        }
        Py_DECREF(v);
    }
    Py_DECREF(it);
    if (PyErr_Occurred())
        return -1;
    return 0;
}

static int
array_do_extend(arrayobject *self, PyObject *bb)
{
    Py_ssize_t size, oldsize, bbsize;

    if (!array_Check(bb))
        return array_iter_extend(self, bb);
#define b ((arrayobject *)bb)
    if (self->ob_descr != b->ob_descr) {
        PyErr_SetString(PyExc_TypeError,
                     "can only extend with array of same kind");
        return -1;
    }
    if ((Py_SIZE(self) > PY_SSIZE_T_MAX - Py_SIZE(b)) ||
        ((Py_SIZE(self) + Py_SIZE(b)) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {