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