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

struct arrayobject; /* Forward */

struct arraydescr {

};

typedef struct arrayobject {

} 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 {

};

#define MACHINE_FORMAT_CODE_MIN 0

#define MACHINE_FORMAT_CODE_MAX 21

#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

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

_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

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;

}

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

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_FromOrdinal(((Py_UNICODE *) ap->ob_item)[i]);

}

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

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;

}

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;

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)) {

v = get_int_unless_float(v);

if (NULL == v) {

return -1;

}

do_decref = 1;

}

x = PyLong_AsUnsignedLongLong(v);

if (x == (unsigned long long)-1 && PyErr_Occurred()) {

if (do_decref) {

Py_DECREF(v);

}

return -1;

}

if (i >= 0)

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

if (do_decref) {

Py_DECREF(v);

}

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;

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;

}

static const 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},

{'q', sizeof(long long), q_getitem, q_setitem, "q", 1, 1},

{'Q', sizeof(long long), QQ_getitem, QQ_setitem, "Q", 1, 0},

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

};

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_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);

}

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;

}

static PyObject *

array_array___copy___impl(arrayobject *self)

{

return array_slice(self, 0, Py_SIZE(self));

}

static PyObject *

array_array___deepcopy__(arrayobject *self, PyObject *unused)

{

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;

memcpy(np->ob_item, a->ob_item, oldbytes);

while (done < newbytes) {

Py_ssize_t ncopy = (done <= newbytes-done) ? done : newbytes-done;

memcpy(np->ob_item+done, np->ob_item, ncopy);

done += ncopy;

}

}

return (PyObject *)np;

}

static int

array_del_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

{

char *item;

Py_ssize_t d; /* Change in size */

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 = ihigh-ilow;

/* Issue #4509: If the array has exported buffers and the slice

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;

}

return 0;

}

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_del_slice(a, i, i+1);

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)) {

PyErr_NoMemory();

return -1;

}

oldsize = Py_SIZE(self);

/* Get the size of bb before resizing the array since bb could be self. */

bbsize = Py_SIZE(bb);

size = oldsize + Py_SIZE(b);

if (array_resize(self, size) == -1)

return -1;

if (bbsize > 0) {

memcpy(self->ob_item + oldsize * self->ob_descr->itemsize,

b->ob_item, bbsize * b->ob_descr->itemsize);

}

return 0;

#undef b

}

static PyObject *

array_inplace_concat(arrayobject *self, PyObject *bb)

{

if (!array_Check(bb)) {

PyErr_Format(PyExc_TypeError,

"can only extend array with array (not \"%.200s\")",

Py_TYPE(bb)->tp_name);

return NULL;

}

if (array_do_extend(self, bb) == -1)

return NULL;

Py_INCREF(self);

return (PyObject *)self;

}

static PyObject *

array_inplace_repeat(arrayobject *self, Py_ssize_t n)

{

char *items, *p;

Py_ssize_t size, i;

if (Py_SIZE(self) > 0) {

if (n < 0)

n = 0;

if ((self->ob_descr->itemsize != 0) &&