1 /* Array object implementation */

     2 

     3 /* An array is a uniform list -- all items have the same type.

     4    The item type is restricted to simple C types like int or float */

     5 

     6 #define PY_SSIZE_T_CLEAN

     7 #include "Python.h"

     8 #include "structmember.h"

     9 

    10 #ifdef STDC_HEADERS

    11 #include <stddef.h>

    12 #else /* !STDC_HEADERS */

    13 #ifdef HAVE_SYS_TYPES_H

    14 #include <sys/types.h>		/* For size_t */

    15 #endif /* HAVE_SYS_TYPES_H */

    16 #endif /* !STDC_HEADERS */

    17 

    18 struct arrayobject; /* Forward */

    19 

    20 /* All possible arraydescr values are defined in the vector "descriptors"

    21  * below.  That's defined later because the appropriate get and set

    22  * functions aren't visible yet.

    23  */

    24 struct arraydescr {

    25 	int typecode;

    26 	int itemsize;

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

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

    29 };

    30 

    31 typedef struct arrayobject {

    32 	PyObject_VAR_HEAD

    33 	char *ob_item;

    34 	Py_ssize_t allocated;

    35 	struct arraydescr *ob_descr;

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

    37 } arrayobject;

    38 

    39 static PyTypeObject Arraytype;

    40 

    41 #define array_Check(op) PyObject_TypeCheck(op, &Arraytype)

    42 #define array_CheckExact(op) (Py_TYPE(op) == &Arraytype)

    43 

    44 static int

    45 array_resize(arrayobject *self, Py_ssize_t newsize)

    46 {

    47 	char *items;

    48 	size_t _new_size;

    49 

    50 	/* Bypass realloc() when a previous overallocation is large enough

    51 	   to accommodate the newsize.  If the newsize is 16 smaller than the

    52 	   current size, then proceed with the realloc() to shrink the list.

    53 	*/

    54 

    55 	if (self->allocated >= newsize &&

    56 	    Py_SIZE(self) < newsize + 16 &&

    57 	    self->ob_item != NULL) {

    58 		Py_SIZE(self) = newsize;

    59 		return 0;

    60 	}

    61 

    62 	/* This over-allocates proportional to the array size, making room

    63 	 * for additional growth.  The over-allocation is mild, but is

    64 	 * enough to give linear-time amortized behavior over a long

    65 	 * sequence of appends() in the presence of a poorly-performing

    66 	 * system realloc().

    67 	 * The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...

    68 	 * Note, the pattern starts out the same as for lists but then

    69 	 * grows at a smaller rate so that larger arrays only overallocate

    70 	 * by about 1/16th -- this is done because arrays are presumed to be more

    71 	 * memory critical.

    72 	 */

    73 

    74 	_new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;

    75 	items = self->ob_item;

    76 	/* XXX The following multiplication and division does not optimize away 

    77 	   like it does for lists since the size is not known at compile time */

    78 	if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))

    79 		PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));

    80 	else

    81 		items = NULL;

    82 	if (items == NULL) {

    83 		PyErr_NoMemory();

    84 		return -1;

    85 	}

    86 	self->ob_item = items;

    87 	Py_SIZE(self) = newsize;

    88 	self->allocated = _new_size;

    89 	return 0;

    90 }

    91 

    92 /****************************************************************************

    93 Get and Set functions for each type.

    94 A Get function takes an arrayobject* and an integer index, returning the

    95 array value at that index wrapped in an appropriate PyObject*.

    96 A Set function takes an arrayobject, integer index, and PyObject*; sets

    97 the array value at that index to the raw C data extracted from the PyObject*,

    98 and returns 0 if successful, else nonzero on failure (PyObject* not of an

    99 appropriate type or value).

   100 Note that the basic Get and Set functions do NOT check that the index is

   101 in bounds; that's the responsibility of the caller.

   102 ****************************************************************************/

   103 

   104 static PyObject *

   105 c_getitem(arrayobject *ap, Py_ssize_t i)

   106 {

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

   108 }

   109 

   110 static int

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

   112 {

   113 	char x;

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

   115 		return -1;

   116 	if (i >= 0)

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

   118 	return 0;

   119 }

   120 

   121 static PyObject *

   122 b_getitem(arrayobject *ap, Py_ssize_t i)

   123 {

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

   125 	if (x >= 128)

   126 		x -= 256;

   127 	return PyInt_FromLong(x);

   128 }

   129 

   130 static int

   131 b_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   132 {

   133 	short x;

   134 	/* PyArg_Parse's 'b' formatter is for an unsigned char, therefore

   135 	   must use the next size up that is signed ('h') and manually do

   136 	   the overflow checking */

   137 	if (!PyArg_Parse(v, "h;array item must be integer", &x))

   138 		return -1;

   139 	else if (x < -128) {

   140 		PyErr_SetString(PyExc_OverflowError,

   141 			"signed char is less than minimum");

   142 		return -1;

   143 	}

   144 	else if (x > 127) {

   145 		PyErr_SetString(PyExc_OverflowError,

   146 			"signed char is greater than maximum");

   147 		return -1;

   148 	}

   149 	if (i >= 0)

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

   151 	return 0;

   152 }

   153 

   154 static PyObject *

   155 BB_getitem(arrayobject *ap, Py_ssize_t i)

   156 {

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

   158 	return PyInt_FromLong(x);

   159 }

   160 

   161 static int

   162 BB_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   163 {

   164 	unsigned char x;

   165 	/* 'B' == unsigned char, maps to PyArg_Parse's 'b' formatter */

   166 	if (!PyArg_Parse(v, "b;array item must be integer", &x))

   167 		return -1;

   168 	if (i >= 0)

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

   170 	return 0;

   171 }

   172 

   173 #ifdef Py_USING_UNICODE

   174 static PyObject *

   175 u_getitem(arrayobject *ap, Py_ssize_t i)

   176 {

   177 	return PyUnicode_FromUnicode(&((Py_UNICODE *) ap->ob_item)[i], 1);

   178 }

   179 

   180 static int

   181 u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   182 {

   183 	Py_UNICODE *p;

   184 	Py_ssize_t len;

   185 

   186 	if (!PyArg_Parse(v, "u#;array item must be unicode character", &p, &len))

   187 		return -1;

   188 	if (len != 1) {

   189 		PyErr_SetString(PyExc_TypeError,

   190 				"array item must be unicode character");

   191 		return -1;

   192 	}

   193 	if (i >= 0)

   194 		((Py_UNICODE *)ap->ob_item)[i] = p[0];

   195 	return 0;

   196 }

   197 #endif

   198 

   199 static PyObject *

   200 h_getitem(arrayobject *ap, Py_ssize_t i)

   201 {

   202 	return PyInt_FromLong((long) ((short *)ap->ob_item)[i]);

   203 }

   204 

   205 static int

   206 h_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   207 {

   208 	short x;

   209 	/* 'h' == signed short, maps to PyArg_Parse's 'h' formatter */

   210 	if (!PyArg_Parse(v, "h;array item must be integer", &x))

   211 		return -1;

   212 	if (i >= 0)

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

   214 	return 0;

   215 }

   216 

   217 static PyObject *

   218 HH_getitem(arrayobject *ap, Py_ssize_t i)

   219 {

   220 	return PyInt_FromLong((long) ((unsigned short *)ap->ob_item)[i]);

   221 }

   222 

   223 static int

   224 HH_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   225 {

   226 	int x;

   227 	/* PyArg_Parse's 'h' formatter is for a signed short, therefore

   228 	   must use the next size up and manually do the overflow checking */

   229 	if (!PyArg_Parse(v, "i;array item must be integer", &x))

   230 		return -1;

   231 	else if (x < 0) {

   232 		PyErr_SetString(PyExc_OverflowError,

   233 			"unsigned short is less than minimum");

   234 		return -1;

   235 	}

   236 	else if (x > USHRT_MAX) {

   237 		PyErr_SetString(PyExc_OverflowError,

   238 			"unsigned short is greater than maximum");

   239 		return -1;

   240 	}

   241 	if (i >= 0)

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

   243 	return 0;

   244 }

   245 

   246 static PyObject *

   247 i_getitem(arrayobject *ap, Py_ssize_t i)

   248 {

   249 	return PyInt_FromLong((long) ((int *)ap->ob_item)[i]);

   250 }

   251 

   252 static int

   253 i_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   254 {

   255 	int x;

   256 	/* 'i' == signed int, maps to PyArg_Parse's 'i' formatter */

   257 	if (!PyArg_Parse(v, "i;array item must be integer", &x))

   258 		return -1;

   259 	if (i >= 0)

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

   261 	return 0;

   262 }

   263 

   264 static PyObject *

   265 II_getitem(arrayobject *ap, Py_ssize_t i)

   266 {

   267 	return PyLong_FromUnsignedLong(

   268 		(unsigned long) ((unsigned int *)ap->ob_item)[i]);

   269 }

   270 

   271 static int

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

   273 {

   274 	unsigned long x;

   275 	if (PyLong_Check(v)) {

   276 		x = PyLong_AsUnsignedLong(v);

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

   278 			return -1;

   279 	}

   280 	else {

   281 		long y;

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

   283 			return -1;

   284 		if (y < 0) {

   285 			PyErr_SetString(PyExc_OverflowError,

   286 				"unsigned int is less than minimum");

   287 			return -1;

   288 		}

   289 		x = (unsigned long)y;

   290 

   291 	}

   292 	if (x > UINT_MAX) {

   293 		PyErr_SetString(PyExc_OverflowError,

   294 			"unsigned int is greater than maximum");

   295 		return -1;

   296 	}

   297 

   298 	if (i >= 0)

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

   300 	return 0;

   301 }

   302 

   303 static PyObject *

   304 l_getitem(arrayobject *ap, Py_ssize_t i)

   305 {

   306 	return PyInt_FromLong(((long *)ap->ob_item)[i]);

   307 }

   308 

   309 static int

   310 l_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   311 {

   312 	long x;

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

   314 		return -1;

   315 	if (i >= 0)

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

   317 	return 0;

   318 }

   319 

   320 static PyObject *

   321 LL_getitem(arrayobject *ap, Py_ssize_t i)

   322 {

   323 	return PyLong_FromUnsignedLong(((unsigned long *)ap->ob_item)[i]);

   324 }

   325 

   326 static int

   327 LL_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   328 {

   329 	unsigned long x;

   330 	if (PyLong_Check(v)) {

   331 		x = PyLong_AsUnsignedLong(v);

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

   333 			return -1;

   334 	}

   335 	else {

   336 		long y;

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

   338 			return -1;

   339 		if (y < 0) {

   340 			PyErr_SetString(PyExc_OverflowError,

   341 				"unsigned long is less than minimum");

   342 			return -1;

   343 		}

   344 		x = (unsigned long)y;

   345 

   346 	}

   347 	if (x > ULONG_MAX) {

   348 		PyErr_SetString(PyExc_OverflowError,

   349 			"unsigned long is greater than maximum");

   350 		return -1;

   351 	}

   352 

   353 	if (i >= 0)

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

   355 	return 0;

   356 }

   357 

   358 static PyObject *

   359 f_getitem(arrayobject *ap, Py_ssize_t i)

   360 {

   361 	return PyFloat_FromDouble((double) ((float *)ap->ob_item)[i]);

   362 }

   363 

   364 static int

   365 f_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   366 {

   367 	float x;

   368 	if (!PyArg_Parse(v, "f;array item must be float", &x))

   369 		return -1;

   370 	if (i >= 0)

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

   372 	return 0;

   373 }

   374 

   375 static PyObject *

   376 d_getitem(arrayobject *ap, Py_ssize_t i)

   377 {

   378 	return PyFloat_FromDouble(((double *)ap->ob_item)[i]);

   379 }

   380 

   381 static int

   382 d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)

   383 {

   384 	double x;

   385 	if (!PyArg_Parse(v, "d;array item must be float", &x))

   386 		return -1;

   387 	if (i >= 0)

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

   389 	return 0;

   390 }

   391 

   392 /* Description of types */

   393 static struct arraydescr descriptors[] = {

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

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

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

   397 #ifdef Py_USING_UNICODE

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

   399 #endif

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

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

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

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

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

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

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

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

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

   409 };

   410 

   411 /****************************************************************************

   412 Implementations of array object methods.

   413 ****************************************************************************/

   414 

   415 static PyObject *

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

   417 {

   418 	arrayobject *op;

   419 	size_t nbytes;

   420 

   421 	if (size < 0) {

   422 		PyErr_BadInternalCall();

   423 		return NULL;

   424 	}

   425 

   426 	nbytes = size * descr->itemsize;

   427 	/* Check for overflow */

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

   429 		return PyErr_NoMemory();

   430 	}

   431 	op = (arrayobject *) type->tp_alloc(type, 0);

   432 	if (op == NULL) {

   433 		return NULL;

   434 	}

   435 	op->ob_descr = descr;

   436 	op->allocated = size;

   437 	op->weakreflist = NULL;

   438 	Py_SIZE(op) = size;

   439 	if (size <= 0) {

   440 		op->ob_item = NULL;

   441 	}

   442 	else {

   443 		op->ob_item = PyMem_NEW(char, nbytes);

   444 		if (op->ob_item == NULL) {

   445 			Py_DECREF(op);

   446 			return PyErr_NoMemory();

   447 		}

   448 	}

   449 	return (PyObject *) op;

   450 }

   451 

   452 static PyObject *

   453 getarrayitem(PyObject *op, Py_ssize_t i)

   454 {

   455 	register arrayobject *ap;

   456 	assert(array_Check(op));

   457 	ap = (arrayobject *)op;

   458 	assert(i>=0 && i<Py_SIZE(ap));

   459 	return (*ap->ob_descr->getitem)(ap, i);

   460 }

   461 

   462 static int

   463 ins1(arrayobject *self, Py_ssize_t where, PyObject *v)

   464 {

   465 	char *items;

   466 	Py_ssize_t n = Py_SIZE(self);

   467 	if (v == NULL) {

   468 		PyErr_BadInternalCall();

   469 		return -1;

   470 	}

   471 	if ((*self->ob_descr->setitem)(self, -1, v) < 0)

   472 		return -1;

   473 

   474 	if (array_resize(self, n+1) == -1)

   475 		return -1;

   476 	items = self->ob_item;

   477 	if (where < 0) {

   478 		where += n;

   479 		if (where < 0)

   480 			where = 0;

   481 	}

   482 	if (where > n)

   483 		where = n;

   484 	/* appends don't need to call memmove() */

   485 	if (where != n)

   486 		memmove(items + (where+1)*self->ob_descr->itemsize,

   487 			items + where*self->ob_descr->itemsize,

   488 			(n-where)*self->ob_descr->itemsize);

   489 	return (*self->ob_descr->setitem)(self, where, v);

   490 }

   491 

   492 /* Methods */

   493 

   494 static void

   495 array_dealloc(arrayobject *op)

   496 {

   497 	if (op->weakreflist != NULL)

   498 		PyObject_ClearWeakRefs((PyObject *) op);

   499 	if (op->ob_item != NULL)

   500 		PyMem_DEL(op->ob_item);

   501 	Py_TYPE(op)->tp_free((PyObject *)op);

   502 }

   503 

   504 static PyObject *

   505 array_richcompare(PyObject *v, PyObject *w, int op)

   506 {

   507 	arrayobject *va, *wa;

   508 	PyObject *vi = NULL;

   509 	PyObject *wi = NULL;

   510 	Py_ssize_t i, k;

   511 	PyObject *res;

   512 

   513 	if (!array_Check(v) || !array_Check(w)) {

   514 		Py_INCREF(Py_NotImplemented);

   515 		return Py_NotImplemented;

   516 	}

   517 

   518 	va = (arrayobject *)v;

   519 	wa = (arrayobject *)w;

   520 

   521 	if (Py_SIZE(va) != Py_SIZE(wa) && (op == Py_EQ || op == Py_NE)) {

   522 		/* Shortcut: if the lengths differ, the arrays differ */

   523 		if (op == Py_EQ)

   524 			res = Py_False;

   525 		else

   526 			res = Py_True;

   527 		Py_INCREF(res);

   528 		return res;

   529 	}

   530 

   531 	/* Search for the first index where items are different */

   532 	k = 1;

   533 	for (i = 0; i < Py_SIZE(va) && i < Py_SIZE(wa); i++) {

   534 		vi = getarrayitem(v, i);

   535 		wi = getarrayitem(w, i);

   536 		if (vi == NULL || wi == NULL) {

   537 			Py_XDECREF(vi);

   538 			Py_XDECREF(wi);

   539 			return NULL;

   540 		}

   541 		k = PyObject_RichCompareBool(vi, wi, Py_EQ);

   542 		if (k == 0)

   543 			break; /* Keeping vi and wi alive! */

   544 		Py_DECREF(vi);

   545 		Py_DECREF(wi);

   546 		if (k < 0)

   547 			return NULL;

   548 	}

   549 

   550 	if (k) {

   551 		/* No more items to compare -- compare sizes */

   552 		Py_ssize_t vs = Py_SIZE(va);

   553 		Py_ssize_t ws = Py_SIZE(wa);

   554 		int cmp;

   555 		switch (op) {

   556 		case Py_LT: cmp = vs <  ws; break;

   557 		case Py_LE: cmp = vs <= ws; break;

   558 		case Py_EQ: cmp = vs == ws; break;

   559 		case Py_NE: cmp = vs != ws; break;

   560 		case Py_GT: cmp = vs >  ws; break;

   561 		case Py_GE: cmp = vs >= ws; break;

   562 		default: return NULL; /* cannot happen */

   563 		}

   564 		if (cmp)

   565 			res = Py_True;

   566 		else

   567 			res = Py_False;

   568 		Py_INCREF(res);

   569 		return res;

   570 	}

   571 

   572 	/* We have an item that differs.  First, shortcuts for EQ/NE */

   573 	if (op == Py_EQ) {

   574 		Py_INCREF(Py_False);

   575 		res = Py_False;

   576 	}

   577 	else if (op == Py_NE) {

   578 		Py_INCREF(Py_True);

   579 		res = Py_True;

   580 	}

   581 	else {

   582 		/* Compare the final item again using the proper operator */

   583 		res = PyObject_RichCompare(vi, wi, op);

   584 	}

   585 	Py_DECREF(vi);

   586 	Py_DECREF(wi);

   587 	return res;

   588 }

   589 

   590 static Py_ssize_t

   591 array_length(arrayobject *a)

   592 {

   593 	return Py_SIZE(a);

   594 }

   595 

   596 static PyObject *

   597 array_item(arrayobject *a, Py_ssize_t i)

   598 {

   599 	if (i < 0 || i >= Py_SIZE(a)) {

   600 		PyErr_SetString(PyExc_IndexError, "array index out of range");

   601 		return NULL;

   602 	}

   603 	return getarrayitem((PyObject *)a, i);

   604 }

   605 

   606 static PyObject *

   607 array_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

   608 {

   609 	arrayobject *np;

   610 	if (ilow < 0)

   611 		ilow = 0;

   612 	else if (ilow > Py_SIZE(a))

   613 		ilow = Py_SIZE(a);

   614 	if (ihigh < 0)

   615 		ihigh = 0;

   616 	if (ihigh < ilow)

   617 		ihigh = ilow;

   618 	else if (ihigh > Py_SIZE(a))

   619 		ihigh = Py_SIZE(a);

   620 	np = (arrayobject *) newarrayobject(&Arraytype, ihigh - ilow, a->ob_descr);

   621 	if (np == NULL)

   622 		return NULL;

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

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

   625 	return (PyObject *)np;

   626 }

   627 

   628 static PyObject *

   629 array_copy(arrayobject *a, PyObject *unused)

   630 {

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

   632 }

   633 

   634 PyDoc_STRVAR(copy_doc,

   635 "copy(array)\n\

   636 \n\

   637  Return a copy of the array.");

   638 

   639 static PyObject *

   640 array_concat(arrayobject *a, PyObject *bb)

   641 {

   642 	Py_ssize_t size;

   643 	arrayobject *np;

   644 	if (!array_Check(bb)) {

   645 		PyErr_Format(PyExc_TypeError,

   646 		     "can only append array (not \"%.200s\") to array",

   647 			     Py_TYPE(bb)->tp_name);

   648 		return NULL;

   649 	}

   650 #define b ((arrayobject *)bb)

   651 	if (a->ob_descr != b->ob_descr) {

   652 		PyErr_BadArgument();

   653 		return NULL;

   654 	}

   655 	if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b)) {

   656 		return PyErr_NoMemory();

   657 	}

   658 	size = Py_SIZE(a) + Py_SIZE(b);

   659 	np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);

   660 	if (np == NULL) {

   661 		return NULL;

   662 	}

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

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

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

   666 	return (PyObject *)np;

   667 #undef b

   668 }

   669 

   670 static PyObject *

   671 array_repeat(arrayobject *a, Py_ssize_t n)

   672 {

   673 	Py_ssize_t i;

   674 	Py_ssize_t size;

   675 	arrayobject *np;

   676 	char *p;

   677 	Py_ssize_t nbytes;

   678 	if (n < 0)

   679 		n = 0;

   680 	if ((Py_SIZE(a) != 0) && (n > PY_SSIZE_T_MAX / Py_SIZE(a))) {

   681 		return PyErr_NoMemory();

   682 	}

   683 	size = Py_SIZE(a) * n;

   684 	np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);

   685 	if (np == NULL)

   686 		return NULL;

   687 	p = np->ob_item;

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

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

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

   691 		p += nbytes;

   692 	}

   693 	return (PyObject *) np;

   694 }

   695 

   696 static int

   697 array_ass_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

   698 {

   699 	char *item;

   700 	Py_ssize_t n; /* Size of replacement array */

   701 	Py_ssize_t d; /* Change in size */

   702 #define b ((arrayobject *)v)

   703 	if (v == NULL)

   704 		n = 0;

   705 	else if (array_Check(v)) {

   706 		n = Py_SIZE(b);

   707 		if (a == b) {

   708 			/* Special case "a[i:j] = a" -- copy b first */

   709 			int ret;

   710 			v = array_slice(b, 0, n);

   711 			if (!v)

   712 				return -1;

   713 			ret = array_ass_slice(a, ilow, ihigh, v);

   714 			Py_DECREF(v);

   715 			return ret;

   716 		}

   717 		if (b->ob_descr != a->ob_descr) {

   718 			PyErr_BadArgument();

   719 			return -1;

   720 		}

   721 	}

   722 	else {

   723 		PyErr_Format(PyExc_TypeError,

   724 	     "can only assign array (not \"%.200s\") to array slice",

   725 			     Py_TYPE(v)->tp_name);

   726 		return -1;

   727 	}

   728 	if (ilow < 0)

   729 		ilow = 0;

   730 	else if (ilow > Py_SIZE(a))

   731 		ilow = Py_SIZE(a);

   732 	if (ihigh < 0)

   733 		ihigh = 0;

   734 	if (ihigh < ilow)

   735 		ihigh = ilow;

   736 	else if (ihigh > Py_SIZE(a))

   737 		ihigh = Py_SIZE(a);

   738 	item = a->ob_item;

   739 	d = n - (ihigh-ilow);

   740 	if (d < 0) { /* Delete -d items */

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

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

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

   744 		Py_SIZE(a) += d;

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

   746 						/* Can't fail */

   747 		a->ob_item = item;

   748 		a->allocated = Py_SIZE(a);

   749 	}

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

   751 		PyMem_RESIZE(item, char,

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

   753 		if (item == NULL) {

   754 			PyErr_NoMemory();

   755 			return -1;

   756 		}

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

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

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

   760 		a->ob_item = item;

   761 		Py_SIZE(a) += d;

   762 		a->allocated = Py_SIZE(a);

   763 	}

   764 	if (n > 0)

   765 		memcpy(item + ilow*a->ob_descr->itemsize, b->ob_item,

   766 		       n*b->ob_descr->itemsize);

   767 	return 0;

   768 #undef b

   769 }

   770 

   771 static int

   772 array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)

   773 {

   774 	if (i < 0 || i >= Py_SIZE(a)) {

   775 		PyErr_SetString(PyExc_IndexError,

   776 			         "array assignment index out of range");

   777 		return -1;

   778 	}

   779 	if (v == NULL)

   780 		return array_ass_slice(a, i, i+1, v);

   781 	return (*a->ob_descr->setitem)(a, i, v);

   782 }

   783 

   784 static int

   785 setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)

   786 {

   787 	assert(array_Check(a));

   788 	return array_ass_item((arrayobject *)a, i, v);

   789 }

   790 

   791 static int

   792 array_iter_extend(arrayobject *self, PyObject *bb)

   793 {

   794 	PyObject *it, *v;

   795 

   796 	it = PyObject_GetIter(bb);

   797 	if (it == NULL)

   798 		return -1;

   799 

   800 	while ((v = PyIter_Next(it)) != NULL) {

   801 		if (ins1(self, (int) Py_SIZE(self), v) != 0) {

   802 			Py_DECREF(v);

   803 			Py_DECREF(it);

   804 			return -1;

   805 		}

   806 		Py_DECREF(v);

   807 	}

   808 	Py_DECREF(it);

   809 	if (PyErr_Occurred())

   810 		return -1;

   811 	return 0;

   812 }

   813 

   814 static int

   815 array_do_extend(arrayobject *self, PyObject *bb)

   816 {

   817 	Py_ssize_t size;

   818 	char *old_item;

   819 

   820 	if (!array_Check(bb))

   821 		return array_iter_extend(self, bb);

   822 #define b ((arrayobject *)bb)

   823 	if (self->ob_descr != b->ob_descr) {

   824 		PyErr_SetString(PyExc_TypeError,

   825 			     "can only extend with array of same kind");

   826 		return -1;

   827 	}

   828 	if ((Py_SIZE(self) > PY_SSIZE_T_MAX - Py_SIZE(b)) ||

   829 		((Py_SIZE(self) + Py_SIZE(b)) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {

   830 		PyErr_NoMemory();

   831 		return -1;

   832 	}

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

   834 	old_item = self->ob_item;

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

   836         if (self->ob_item == NULL) {

   837 		self->ob_item = old_item;

   838 		PyErr_NoMemory();

   839 		return -1;

   840         }

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

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

   843 	Py_SIZE(self) = size;

   844 	self->allocated = size;

   845 

   846 	return 0;

   847 #undef b

   848 }

   849 

   850 static PyObject *

   851 array_inplace_concat(arrayobject *self, PyObject *bb)

   852 {

   853 	if (!array_Check(bb)) {

   854 		PyErr_Format(PyExc_TypeError,

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

   856 			Py_TYPE(bb)->tp_name);

   857 		return NULL;

   858 	}

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

   860 		return NULL;

   861 	Py_INCREF(self);

   862 	return (PyObject *)self;

   863 }

   864 

   865 static PyObject *

   866 array_inplace_repeat(arrayobject *self, Py_ssize_t n)

   867 {

   868 	char *items, *p;

   869 	Py_ssize_t size, i;

   870 

   871 	if (Py_SIZE(self) > 0) {

   872 		if (n < 0)

   873 			n = 0;

   874 		items = self->ob_item;

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

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

   877 			return PyErr_NoMemory();

   878 		}

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

   880 		if (n == 0) {

   881 			PyMem_FREE(items);

   882 			self->ob_item = NULL;

   883 			Py_SIZE(self) = 0;

   884 			self->allocated = 0;

   885 		}

   886 		else {

   887 			if (size > PY_SSIZE_T_MAX / n) {

   888 				return PyErr_NoMemory();

   889 			}

   890 			PyMem_RESIZE(items, char, n * size);

   891 			if (items == NULL)

   892 				return PyErr_NoMemory();

   893 			p = items;

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

   895 				p += size;

   896 				memcpy(p, items, size);

   897 			}

   898 			self->ob_item = items;

   899 			Py_SIZE(self) *= n;

   900 			self->allocated = Py_SIZE(self);

   901 		}

   902 	}

   903 	Py_INCREF(self);

   904 	return (PyObject *)self;

   905 }

   906 

   907 

   908 static PyObject *

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

   910 {

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

   912 		return NULL;

   913 	Py_INCREF(Py_None);

   914 	return Py_None;

   915 }

   916 

   917 static PyObject *

   918 array_count(arrayobject *self, PyObject *v)

   919 {

   920 	Py_ssize_t count = 0;

   921 	Py_ssize_t i;

   922 

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

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

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

   926 		Py_DECREF(selfi);

   927 		if (cmp > 0)

   928 			count++;

   929 		else if (cmp < 0)

   930 			return NULL;

   931 	}

   932 	return PyInt_FromSsize_t(count);

   933 }

   934 

   935 PyDoc_STRVAR(count_doc,

   936 "count(x)\n\

   937 \n\

   938 Return number of occurences of x in the array.");

   939 

   940 static PyObject *

   941 array_index(arrayobject *self, PyObject *v)

   942 {

   943 	Py_ssize_t i;

   944 

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

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

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

   948 		Py_DECREF(selfi);

   949 		if (cmp > 0) {

   950 			return PyInt_FromLong((long)i);

   951 		}

   952 		else if (cmp < 0)

   953 			return NULL;

   954 	}

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

   956 	return NULL;

   957 }

   958 

   959 PyDoc_STRVAR(index_doc,

   960 "index(x)\n\

   961 \n\

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

   963 

   964 static int

   965 array_contains(arrayobject *self, PyObject *v)

   966 {

   967 	Py_ssize_t i;

   968 	int cmp;

   969 

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

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

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

   973 		Py_DECREF(selfi);

   974 	}

   975 	return cmp;

   976 }

   977 

   978 static PyObject *

   979 array_remove(arrayobject *self, PyObject *v)

   980 {

   981 	int i;

   982 

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

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

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

   986 		Py_DECREF(selfi);

   987 		if (cmp > 0) {

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

   989 					   (PyObject *)NULL) != 0)

   990 				return NULL;

   991 			Py_INCREF(Py_None);

   992 			return Py_None;

   993 		}

   994 		else if (cmp < 0)

   995 			return NULL;

   996 	}

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

   998 	return NULL;

   999 }

  1000 

  1001 PyDoc_STRVAR(remove_doc,

  1002 "remove(x)\n\

  1003 \n\

  1004 Remove the first occurence of x in the array.");

  1005 

  1006 static PyObject *

  1007 array_pop(arrayobject *self, PyObject *args)

  1008 {

  1009 	Py_ssize_t i = -1;

  1010 	PyObject *v;

  1011 	if (!PyArg_ParseTuple(args, "|n:pop", &i))

  1012 		return NULL;

  1013 	if (Py_SIZE(self) == 0) {

  1014 		/* Special-case most common failure cause */

  1015 		PyErr_SetString(PyExc_IndexError, "pop from empty array");

  1016 		return NULL;

  1017 	}

  1018 	if (i < 0)

  1019 		i += Py_SIZE(self);

  1020 	if (i < 0 || i >= Py_SIZE(self)) {

  1021 		PyErr_SetString(PyExc_IndexError, "pop index out of range");

  1022 		return NULL;

  1023 	}

  1024 	v = getarrayitem((PyObject *)self,i);

  1025 	if (array_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {

  1026 		Py_DECREF(v);

  1027 		return NULL;

  1028 	}

  1029 	return v;

  1030 }

  1031 

  1032 PyDoc_STRVAR(pop_doc,

  1033 "pop([i])\n\

  1034 \n\

  1035 Return the i-th element and delete it from the array. i defaults to -1.");

  1036 

  1037 static PyObject *

  1038 array_extend(arrayobject *self, PyObject *bb)

  1039 {

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

  1041 		return NULL;

  1042 	Py_INCREF(Py_None);

  1043 	return Py_None;

  1044 }

  1045 

  1046 PyDoc_STRVAR(extend_doc,

  1047 "extend(array or iterable)\n\

  1048 \n\

  1049  Append items to the end of the array.");

  1050 

  1051 static PyObject *

  1052 array_insert(arrayobject *self, PyObject *args)

  1053 {

  1054 	Py_ssize_t i;

  1055 	PyObject *v;

  1056         if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))

  1057 		return NULL;

  1058 	return ins(self, i, v);

  1059 }

  1060 

  1061 PyDoc_STRVAR(insert_doc,

  1062 "insert(i,x)\n\

  1063 \n\

  1064 Insert a new item x into the array before position i.");

  1065 

  1066 

  1067 static PyObject *

  1068 array_buffer_info(arrayobject *self, PyObject *unused)

  1069 {

  1070 	PyObject* retval = NULL;

  1071 	retval = PyTuple_New(2);

  1072 	if (!retval)

  1073 		return NULL;

  1074 

  1075 	PyTuple_SET_ITEM(retval, 0, PyLong_FromVoidPtr(self->ob_item));

  1076 	PyTuple_SET_ITEM(retval, 1, PyInt_FromLong((long)(Py_SIZE(self))));

  1077 

  1078 	return retval;

  1079 }

  1080 

  1081 PyDoc_STRVAR(buffer_info_doc,

  1082 "buffer_info() -> (address, length)\n\

  1083 \n\

  1084 Return a tuple (address, length) giving the current memory address and\n\

  1085 the length in items of the buffer used to hold array's contents\n\

  1086 The length should be multiplied by the itemsize attribute to calculate\n\

  1087 the buffer length in bytes.");

  1088 

  1089 

  1090 static PyObject *

  1091 array_append(arrayobject *self, PyObject *v)

  1092 {

  1093 	return ins(self, (int) Py_SIZE(self), v);

  1094 }

  1095 

  1096 PyDoc_STRVAR(append_doc,

  1097 "append(x)\n\

  1098 \n\

  1099 Append new value x to the end of the array.");

  1100 

  1101 

  1102 static PyObject *

  1103 array_byteswap(arrayobject *self, PyObject *unused)

  1104 {

  1105 	char *p;

  1106 	Py_ssize_t i;

  1107 

  1108 	switch (self->ob_descr->itemsize) {

  1109 	case 1:

  1110 		break;

  1111 	case 2:

  1112 		for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 2) {

  1113 			char p0 = p[0];

  1114 			p[0] = p[1];

  1115 			p[1] = p0;

  1116 		}

  1117 		break;

  1118 	case 4:

  1119 		for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 4) {

  1120 			char p0 = p[0];

  1121 			char p1 = p[1];

  1122 			p[0] = p[3];

  1123 			p[1] = p[2];

  1124 			p[2] = p1;

  1125 			p[3] = p0;

  1126 		}

  1127 		break;

  1128 	case 8:

  1129 		for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 8) {

  1130 			char p0 = p[0];

  1131 			char p1 = p[1];

  1132 			char p2 = p[2];

  1133 			char p3 = p[3];

  1134 			p[0] = p[7];

  1135 			p[1] = p[6];