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

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 {

int typecode;

int itemsize;

PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);

int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);

};

typedef struct arrayobject {

PyObject_VAR_HEAD

char *ob_item;

Py_ssize_t allocated;

struct arraydescr *ob_descr;

PyObject *weakreflist; /* List of weak references */

} arrayobject;

static PyTypeObject Arraytype;

#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;

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

*/

if (self->allocated >= newsize &&

Py_SIZE(self) < newsize + 16 &&

self->ob_item != NULL) {

Py_SIZE(self) = newsize;

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 *

c_getitem(arrayobject *ap, Py_ssize_t i)

{

return PyString_FromStringAndSize(&((char *)ap->ob_item)[i], 1);

}

static int

c_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

{

char x;

if (!PyArg_Parse(v, "c;array item must be char", &x))

return -1;

if (i >= 0)

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

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 PyInt_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 PyInt_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;

}

#ifdef Py_USING_UNICODE

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;

}

#endif

static PyObject *

h_getitem(arrayobject *ap, Py_ssize_t i)

{

return PyInt_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 PyInt_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 PyInt_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 int

II_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

{

unsigned long x;

if (PyLong_Check(v)) {

x = PyLong_AsUnsignedLong(v);

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

return -1;

}

else {

long y;

if (!PyArg_Parse(v, "l;array item must be integer", &y))

return -1;

if (y < 0) {

PyErr_SetString(PyExc_OverflowError,

"unsigned int is less than minimum");

return -1;

}

x = (unsigned long)y;

}

if (x > UINT_MAX) {

PyErr_SetString(PyExc_OverflowError,

"unsigned int is greater than maximum");

return -1;

}

if (i >= 0)

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

return 0;

}

static PyObject *

l_getitem(arrayobject *ap, Py_ssize_t i)

{

return PyInt_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;

if (PyLong_Check(v)) {

x = PyLong_AsUnsignedLong(v);

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

return -1;

}

else {

long y;

if (!PyArg_Parse(v, "l;array item must be integer", &y))

return -1;

if (y < 0) {

PyErr_SetString(PyExc_OverflowError,

"unsigned long is less than minimum");

return -1;

}

x = (unsigned long)y;

}

if (x > ULONG_MAX) {

PyErr_SetString(PyExc_OverflowError,

"unsigned long is greater than maximum");

return -1;

}

if (i >= 0)

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

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;

}

/* Description of types */

static struct arraydescr descriptors[] = {

{'c', sizeof(char), c_getitem, c_setitem},

{'b', sizeof(char), b_getitem, b_setitem},

{'B', sizeof(char), BB_getitem, BB_setitem},

#ifdef Py_USING_UNICODE

{'u', sizeof(Py_UNICODE), u_getitem, u_setitem},

#endif

{'h', sizeof(short), h_getitem, h_setitem},

{'H', sizeof(short), HH_getitem, HH_setitem},

{'i', sizeof(int), i_getitem, i_setitem},

{'I', sizeof(int), II_getitem, II_setitem},

{'l', sizeof(long), l_getitem, l_setitem},

{'L', sizeof(long), LL_getitem, LL_setitem},

{'f', sizeof(float), f_getitem, f_setitem},

{'d', sizeof(double), d_getitem, d_setitem},

{'\0', 0, 0, 0} /* Sentinel */

};

/****************************************************************************

Implementations of array object methods.

****************************************************************************/

static PyObject *

newarrayobject(PyTypeObject *type, Py_ssize_t size, struct arraydescr *descr)

{

arrayobject *op;

size_t nbytes;

if (size < 0) {

PyErr_BadInternalCall();

return NULL;

}

nbytes = size * descr->itemsize;

/* Check for overflow */

if (nbytes / descr->itemsize != (size_t)size) {

return PyErr_NoMemory();

}

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

}

}

return (PyObject *) op;

}

static PyObject *

getarrayitem(PyObject *op, Py_ssize_t i)

{

register 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_INCREF(Py_NotImplemented);

return Py_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;

memcpy(np->ob_item, a->ob_item + ilow * a->ob_descr->itemsize,

(ihigh-ilow) * a->ob_descr->itemsize);

return (PyObject *)np;

}

static PyObject *

array_copy(arrayobject *a, PyObject *unused)

{

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

}

PyDoc_STRVAR(copy_doc,

"copy(array)\n\

\n\

Return a copy of the array.");

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;

}

memcpy(np->ob_item, a->ob_item, Py_SIZE(a)*a->ob_descr->itemsize);

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 i;

Py_ssize_t size;

arrayobject *np;

char *p;

Py_ssize_t nbytes;

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;

p = np->ob_item;

nbytes = Py_SIZE(a) * a->ob_descr->itemsize;

for (i = 0; i < n; i++) {

memcpy(p, a->ob_item, nbytes);

p += nbytes;

}

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

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

Py_SIZE(a) += d;

PyMem_RESIZE(item, char, Py_SIZE(a)*a->ob_descr->itemsize);

/* Can't fail */

a->ob_item = item;

a->allocated = Py_SIZE(a);

}

else if (d > 0) { /* Insert d items */

PyMem_RESIZE(item, char,

(Py_SIZE(a) + d)*a->ob_descr->itemsize);

if (item == NULL) {

PyErr_NoMemory();

return -1;

}

memmove(item + (ihigh+d)*a->ob_descr->itemsize,

item + ihigh*a->ob_descr->itemsize,

(Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);

a->ob_item = item;

Py_SIZE(a) += d;

a->allocated = Py_SIZE(a);

}

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;

char *old_item;

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;

}

size = Py_SIZE(self) + Py_SIZE(b);

old_item = self->ob_item;

PyMem_RESIZE(self->ob_item, char, size*self->ob_descr->itemsize);

if (self->ob_item == NULL) {

self->ob_item = old_item;

PyErr_NoMemory();

return -1;

}

memcpy(self->ob_item + Py_SIZE(self)*self->ob_descr->itemsize,

b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);

Py_SIZE(self) = size;

self->allocated = size;

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;

items = self->ob_item;

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

(Py_SIZE(self) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {

return PyErr_NoMemory();

}

size = Py_SIZE(self) * self->ob_descr->itemsize;

if (n == 0) {

PyMem_FREE(items);

self->ob_item = NULL;

Py_SIZE(self) = 0;

self->allocated = 0;

}

else {

if (size > PY_SSIZE_T_MAX / n) {

return PyErr_NoMemory();

}

PyMem_RESIZE(items, char, n * size);

if (items == NULL)

return PyErr_NoMemory();

p = items;

for (i = 1; i < n; i++) {

p += size;

memcpy(p, items, size);

}

self->ob_item = items;

Py_SIZE(self) *= n;

self->allocated = Py_SIZE(self);

}

}

Py_INCREF(self);

return (PyObject *)self;

}

static PyObject *

ins(arrayobject *self, Py_ssize_t where, PyObject *v)

{

if (ins1(self, where, v) != 0)

return NULL;

Py_INCREF(Py_None);

return Py_None;

}

static PyObject *

array_count(arrayobject *self, PyObject *v)

{

Py_ssize_t count = 0;

Py_ssize_t i;

for (i = 0; i < Py_SIZE(self); i++) {

PyObject *selfi = getarrayitem((PyObject *)self, i);

int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);

Py_DECREF(selfi);

if (cmp > 0)

count++;

else if (cmp < 0)

return NULL;

}

return PyInt_FromSsize_t(count);

}

PyDoc_STRVAR(count_doc,

"count(x)\n\

\n\

Return number of occurrences of x in the array.");

static PyObject *

array_index(arrayobject *self, PyObject *v)

{

Py_ssize_t i;

for (i = 0; i < Py_SIZE(self); i++) {

PyObject *selfi = getarrayitem((PyObject *)self, i);

int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);

Py_DECREF(selfi);

if (cmp > 0) {

return PyInt_FromLong((long)i);

}

else if (cmp < 0)

return NULL;

}

PyErr_SetString(PyExc_ValueError, "array.index(x): x not in list");

return NULL;

}

PyDoc_STRVAR(index_doc,

"index(x)\n\

\n\

Return index of first occurrence of x in the array.");

static int

array_contains(arrayobject *self, PyObject *v)

{

Py_ssize_t i;

int cmp;

for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(self); i++) {

PyObject *selfi = getarrayitem((PyObject *)self, i);

cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);

Py_DECREF(selfi);

}

return cmp;

}

static PyObject *

array_remove(arrayobject *self, PyObject *v)

{

int i;

for (i = 0; i < Py_SIZE(self); i++) {

PyObject *selfi = getarrayitem((PyObject *)self,i);

int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);

Py_DECREF(selfi);

if (cmp > 0) {

if (array_ass_slice(self, i, i+1,

(PyObject *)NULL) != 0)

return NULL;

Py_INCREF(Py_None);

return Py_None;

}

else if (cmp < 0)

return NULL;

}

PyErr_SetString(PyExc_ValueError, "array.remove(x): x not in list");

return NULL;

}