Fix duplicate test numbers in extra.decTest
[python.git] / Modules / arraymodule.c
blob018ab873d42457aa10fda8b0f5375b4afcd375d5
1 /* Array object implementation */
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 */
6 #define PY_SSIZE_T_CLEAN
7 #include "Python.h"
8 #include "structmember.h"
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 */
18 struct arrayobject; /* Forward */
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.
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 *);
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;
39 static PyTypeObject Arraytype;
41 #define array_Check(op) PyObject_TypeCheck(op, &Arraytype)
42 #define array_CheckExact(op) (Py_TYPE(op) == &Arraytype)
44 static int
45 array_resize(arrayobject *self, Py_ssize_t newsize)
47 char *items;
48 size_t _new_size;
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.
55 if (self->allocated >= newsize &&
56 Py_SIZE(self) < newsize + 16 &&
57 self->ob_item != NULL) {
58 Py_SIZE(self) = newsize;
59 return 0;
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.
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;
86 self->ob_item = items;
87 Py_SIZE(self) = newsize;
88 self->allocated = _new_size;
89 return 0;
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 ****************************************************************************/
104 static PyObject *
105 c_getitem(arrayobject *ap, Py_ssize_t i)
107 return PyString_FromStringAndSize(&((char *)ap->ob_item)[i], 1);
110 static int
111 c_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
121 static PyObject *
122 b_getitem(arrayobject *ap, Py_ssize_t i)
124 long x = ((char *)ap->ob_item)[i];
125 if (x >= 128)
126 x -= 256;
127 return PyInt_FromLong(x);
130 static int
131 b_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
144 else if (x > 127) {
145 PyErr_SetString(PyExc_OverflowError,
146 "signed char is greater than maximum");
147 return -1;
149 if (i >= 0)
150 ((char *)ap->ob_item)[i] = (char)x;
151 return 0;
154 static PyObject *
155 BB_getitem(arrayobject *ap, Py_ssize_t i)
157 long x = ((unsigned char *)ap->ob_item)[i];
158 return PyInt_FromLong(x);
161 static int
162 BB_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
173 #ifdef Py_USING_UNICODE
174 static PyObject *
175 u_getitem(arrayobject *ap, Py_ssize_t i)
177 return PyUnicode_FromUnicode(&((Py_UNICODE *) ap->ob_item)[i], 1);
180 static int
181 u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
183 Py_UNICODE *p;
184 Py_ssize_t len;
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;
193 if (i >= 0)
194 ((Py_UNICODE *)ap->ob_item)[i] = p[0];
195 return 0;
197 #endif
199 static PyObject *
200 h_getitem(arrayobject *ap, Py_ssize_t i)
202 return PyInt_FromLong((long) ((short *)ap->ob_item)[i]);
205 static int
206 h_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
217 static PyObject *
218 HH_getitem(arrayobject *ap, Py_ssize_t i)
220 return PyInt_FromLong((long) ((unsigned short *)ap->ob_item)[i]);
223 static int
224 HH_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
236 else if (x > USHRT_MAX) {
237 PyErr_SetString(PyExc_OverflowError,
238 "unsigned short is greater than maximum");
239 return -1;
241 if (i >= 0)
242 ((short *)ap->ob_item)[i] = (short)x;
243 return 0;
246 static PyObject *
247 i_getitem(arrayobject *ap, Py_ssize_t i)
249 return PyInt_FromLong((long) ((int *)ap->ob_item)[i]);
252 static int
253 i_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
264 static PyObject *
265 II_getitem(arrayobject *ap, Py_ssize_t i)
267 return PyLong_FromUnsignedLong(
268 (unsigned long) ((unsigned int *)ap->ob_item)[i]);
271 static int
272 II_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
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;
289 x = (unsigned long)y;
292 if (x > UINT_MAX) {
293 PyErr_SetString(PyExc_OverflowError,
294 "unsigned int is greater than maximum");
295 return -1;
298 if (i >= 0)
299 ((unsigned int *)ap->ob_item)[i] = (unsigned int)x;
300 return 0;
303 static PyObject *
304 l_getitem(arrayobject *ap, Py_ssize_t i)
306 return PyInt_FromLong(((long *)ap->ob_item)[i]);
309 static int
310 l_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
320 static PyObject *
321 LL_getitem(arrayobject *ap, Py_ssize_t i)
323 return PyLong_FromUnsignedLong(((unsigned long *)ap->ob_item)[i]);
326 static int
327 LL_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
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;
344 x = (unsigned long)y;
347 if (x > ULONG_MAX) {
348 PyErr_SetString(PyExc_OverflowError,
349 "unsigned long is greater than maximum");
350 return -1;
353 if (i >= 0)
354 ((unsigned long *)ap->ob_item)[i] = x;
355 return 0;
358 static PyObject *
359 f_getitem(arrayobject *ap, Py_ssize_t i)
361 return PyFloat_FromDouble((double) ((float *)ap->ob_item)[i]);
364 static int
365 f_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
375 static PyObject *
376 d_getitem(arrayobject *ap, Py_ssize_t i)
378 return PyFloat_FromDouble(((double *)ap->ob_item)[i]);
381 static int
382 d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
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;
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 */
411 /****************************************************************************
412 Implementations of array object methods.
413 ****************************************************************************/
415 static PyObject *
416 newarrayobject(PyTypeObject *type, Py_ssize_t size, struct arraydescr *descr)
418 arrayobject *op;
419 size_t nbytes;
421 if (size < 0) {
422 PyErr_BadInternalCall();
423 return NULL;
426 nbytes = size * descr->itemsize;
427 /* Check for overflow */
428 if (nbytes / descr->itemsize != (size_t)size) {
429 return PyErr_NoMemory();
431 op = (arrayobject *) type->tp_alloc(type, 0);
432 if (op == NULL) {
433 return NULL;
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;
442 else {
443 op->ob_item = PyMem_NEW(char, nbytes);
444 if (op->ob_item == NULL) {
445 Py_DECREF(op);
446 return PyErr_NoMemory();
449 return (PyObject *) op;
452 static PyObject *
453 getarrayitem(PyObject *op, Py_ssize_t i)
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);
462 static int
463 ins1(arrayobject *self, Py_ssize_t where, PyObject *v)
465 char *items;
466 Py_ssize_t n = Py_SIZE(self);
467 if (v == NULL) {
468 PyErr_BadInternalCall();
469 return -1;
471 if ((*self->ob_descr->setitem)(self, -1, v) < 0)
472 return -1;
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;
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);
492 /* Methods */
494 static void
495 array_dealloc(arrayobject *op)
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);
504 static PyObject *
505 array_richcompare(PyObject *v, PyObject *w, int op)
507 arrayobject *va, *wa;
508 PyObject *vi = NULL;
509 PyObject *wi = NULL;
510 Py_ssize_t i, k;
511 PyObject *res;
513 if (!array_Check(v) || !array_Check(w)) {
514 Py_INCREF(Py_NotImplemented);
515 return Py_NotImplemented;
518 va = (arrayobject *)v;
519 wa = (arrayobject *)w;
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;
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;
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;
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 */
564 if (cmp)
565 res = Py_True;
566 else
567 res = Py_False;
568 Py_INCREF(res);
569 return res;
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;
577 else if (op == Py_NE) {
578 Py_INCREF(Py_True);
579 res = Py_True;
581 else {
582 /* Compare the final item again using the proper operator */
583 res = PyObject_RichCompare(vi, wi, op);
585 Py_DECREF(vi);
586 Py_DECREF(wi);
587 return res;
590 static Py_ssize_t
591 array_length(arrayobject *a)
593 return Py_SIZE(a);
596 static PyObject *
597 array_item(arrayobject *a, Py_ssize_t i)
599 if (i < 0 || i >= Py_SIZE(a)) {
600 PyErr_SetString(PyExc_IndexError, "array index out of range");
601 return NULL;
603 return getarrayitem((PyObject *)a, i);
606 static PyObject *
607 array_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
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;
628 static PyObject *
629 array_copy(arrayobject *a, PyObject *unused)
631 return array_slice(a, 0, Py_SIZE(a));
634 PyDoc_STRVAR(copy_doc,
635 "copy(array)\n\
637 Return a copy of the array.");
639 static PyObject *
640 array_concat(arrayobject *a, PyObject *bb)
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;
650 #define b ((arrayobject *)bb)
651 if (a->ob_descr != b->ob_descr) {
652 PyErr_BadArgument();
653 return NULL;
655 if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b)) {
656 return PyErr_NoMemory();
658 size = Py_SIZE(a) + Py_SIZE(b);
659 np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
660 if (np == NULL) {
661 return NULL;
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
670 static PyObject *
671 array_repeat(arrayobject *a, Py_ssize_t n)
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();
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;
693 return (PyObject *) np;
696 static int
697 array_ass_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
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;
717 if (b->ob_descr != a->ob_descr) {
718 PyErr_BadArgument();
719 return -1;
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;
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);
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;
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);
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
771 static int
772 array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)
774 if (i < 0 || i >= Py_SIZE(a)) {
775 PyErr_SetString(PyExc_IndexError,
776 "array assignment index out of range");
777 return -1;
779 if (v == NULL)
780 return array_ass_slice(a, i, i+1, v);
781 return (*a->ob_descr->setitem)(a, i, v);
784 static int
785 setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)
787 assert(array_Check(a));
788 return array_ass_item((arrayobject *)a, i, v);
791 static int
792 array_iter_extend(arrayobject *self, PyObject *bb)
794 PyObject *it, *v;
796 it = PyObject_GetIter(bb);
797 if (it == NULL)
798 return -1;
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;
806 Py_DECREF(v);
808 Py_DECREF(it);
809 if (PyErr_Occurred())
810 return -1;
811 return 0;
814 static int
815 array_do_extend(arrayobject *self, PyObject *bb)
817 Py_ssize_t size;
818 char *old_item;
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;
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;
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;
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;
846 return 0;
847 #undef b
850 static PyObject *
851 array_inplace_concat(arrayobject *self, PyObject *bb)
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;
859 if (array_do_extend(self, bb) == -1)
860 return NULL;
861 Py_INCREF(self);
862 return (PyObject *)self;
865 static PyObject *
866 array_inplace_repeat(arrayobject *self, Py_ssize_t n)
868 char *items, *p;
869 Py_ssize_t size, i;
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();
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;
886 else {
887 if (size > PY_SSIZE_T_MAX / n) {
888 return PyErr_NoMemory();
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);
898 self->ob_item = items;
899 Py_SIZE(self) *= n;
900 self->allocated = Py_SIZE(self);
903 Py_INCREF(self);
904 return (PyObject *)self;
908 static PyObject *
909 ins(arrayobject *self, Py_ssize_t where, PyObject *v)
911 if (ins1(self, where, v) != 0)
912 return NULL;
913 Py_INCREF(Py_None);
914 return Py_None;
917 static PyObject *
918 array_count(arrayobject *self, PyObject *v)
920 Py_ssize_t count = 0;
921 Py_ssize_t i;
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;
932 return PyInt_FromSsize_t(count);
935 PyDoc_STRVAR(count_doc,
936 "count(x)\n\
938 Return number of occurrences of x in the array.");
940 static PyObject *
941 array_index(arrayobject *self, PyObject *v)
943 Py_ssize_t i;
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);
952 else if (cmp < 0)
953 return NULL;
955 PyErr_SetString(PyExc_ValueError, "array.index(x): x not in list");
956 return NULL;
959 PyDoc_STRVAR(index_doc,
960 "index(x)\n\
962 Return index of first occurrence of x in the array.");
964 static int
965 array_contains(arrayobject *self, PyObject *v)
967 Py_ssize_t i;
968 int cmp;
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);
975 return cmp;
978 static PyObject *
979 array_remove(arrayobject *self, PyObject *v)
981 int i;
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;
994 else if (cmp < 0)
995 return NULL;
997 PyErr_SetString(PyExc_ValueError, "array.remove(x): x not in list");
998 return NULL;
1001 PyDoc_STRVAR(remove_doc,
1002 "remove(x)\n\
1004 Remove the first occurrence of x in the array.");
1006 static PyObject *
1007 array_pop(arrayobject *self, PyObject *args)
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;
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;
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;
1029 return v;
1032 PyDoc_STRVAR(pop_doc,
1033 "pop([i])\n\
1035 Return the i-th element and delete it from the array. i defaults to -1.");
1037 static PyObject *
1038 array_extend(arrayobject *self, PyObject *bb)
1040 if (array_do_extend(self, bb) == -1)
1041 return NULL;
1042 Py_INCREF(Py_None);
1043 return Py_None;
1046 PyDoc_STRVAR(extend_doc,
1047 "extend(array or iterable)\n\
1049 Append items to the end of the array.");
1051 static PyObject *
1052 array_insert(arrayobject *self, PyObject *args)
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);
1061 PyDoc_STRVAR(insert_doc,
1062 "insert(i,x)\n\
1064 Insert a new item x into the array before position i.");
1067 static PyObject *
1068 array_buffer_info(arrayobject *self, PyObject *unused)
1070 PyObject* retval = NULL;
1071 retval = PyTuple_New(2);
1072 if (!retval)
1073 return NULL;
1075 PyTuple_SET_ITEM(retval, 0, PyLong_FromVoidPtr(self->ob_item));
1076 PyTuple_SET_ITEM(retval, 1, PyInt_FromLong((long)(Py_SIZE(self))));
1078 return retval;
1081 PyDoc_STRVAR(buffer_info_doc,
1082 "buffer_info() -> (address, length)\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.");
1090 static PyObject *
1091 array_append(arrayobject *self, PyObject *v)
1093 return ins(self, (int) Py_SIZE(self), v);
1096 PyDoc_STRVAR(append_doc,
1097 "append(x)\n\
1099 Append new value x to the end of the array.");
1102 static PyObject *
1103 array_byteswap(arrayobject *self, PyObject *unused)
1105 char *p;
1106 Py_ssize_t i;
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;
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;
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];
1136 p[2] = p[5];
1137 p[3] = p[4];
1138 p[4] = p3;
1139 p[5] = p2;
1140 p[6] = p1;
1141 p[7] = p0;
1143 break;
1144 default:
1145 PyErr_SetString(PyExc_RuntimeError,
1146 "don't know how to byteswap this array type");
1147 return NULL;
1149 Py_INCREF(Py_None);
1150 return Py_None;
1153 PyDoc_STRVAR(byteswap_doc,
1154 "byteswap()\n\
1156 Byteswap all items of the array. If the items in the array are not 1, 2,\n\
1157 4, or 8 bytes in size, RuntimeError is raised.");
1159 static PyObject *
1160 array_reverse(arrayobject *self, PyObject *unused)
1162 register Py_ssize_t itemsize = self->ob_descr->itemsize;
1163 register char *p, *q;
1164 /* little buffer to hold items while swapping */
1165 char tmp[256]; /* 8 is probably enough -- but why skimp */
1166 assert((size_t)itemsize <= sizeof(tmp));
1168 if (Py_SIZE(self) > 1) {
1169 for (p = self->ob_item,
1170 q = self->ob_item + (Py_SIZE(self) - 1)*itemsize;
1171 p < q;
1172 p += itemsize, q -= itemsize) {
1173 /* memory areas guaranteed disjoint, so memcpy
1174 * is safe (& memmove may be slower).
1176 memcpy(tmp, p, itemsize);
1177 memcpy(p, q, itemsize);
1178 memcpy(q, tmp, itemsize);
1182 Py_INCREF(Py_None);
1183 return Py_None;
1186 PyDoc_STRVAR(reverse_doc,
1187 "reverse()\n\
1189 Reverse the order of the items in the array.");
1191 static PyObject *
1192 array_fromfile(arrayobject *self, PyObject *args)
1194 PyObject *f;
1195 Py_ssize_t n;
1196 FILE *fp;
1197 if (!PyArg_ParseTuple(args, "On:fromfile", &f, &n))
1198 return NULL;
1199 fp = PyFile_AsFile(f);
1200 if (fp == NULL) {
1201 PyErr_SetString(PyExc_TypeError, "arg1 must be open file");
1202 return NULL;
1204 if (n > 0) {
1205 char *item = self->ob_item;
1206 Py_ssize_t itemsize = self->ob_descr->itemsize;
1207 size_t nread;
1208 Py_ssize_t newlength;
1209 size_t newbytes;
1210 /* Be careful here about overflow */
1211 if ((newlength = Py_SIZE(self) + n) <= 0 ||
1212 (newbytes = newlength * itemsize) / itemsize !=
1213 (size_t)newlength)
1214 goto nomem;
1215 PyMem_RESIZE(item, char, newbytes);
1216 if (item == NULL) {
1217 nomem:
1218 PyErr_NoMemory();
1219 return NULL;
1221 self->ob_item = item;
1222 Py_SIZE(self) += n;
1223 self->allocated = Py_SIZE(self);
1224 nread = fread(item + (Py_SIZE(self) - n) * itemsize,
1225 itemsize, n, fp);
1226 if (nread < (size_t)n) {
1227 Py_SIZE(self) -= (n - nread);
1228 PyMem_RESIZE(item, char, Py_SIZE(self)*itemsize);
1229 self->ob_item = item;
1230 self->allocated = Py_SIZE(self);
1231 PyErr_SetString(PyExc_EOFError,
1232 "not enough items in file");
1233 return NULL;
1236 Py_INCREF(Py_None);
1237 return Py_None;
1240 PyDoc_STRVAR(fromfile_doc,
1241 "fromfile(f, n)\n\
1243 Read n objects from the file object f and append them to the end of the\n\
1244 array. Also called as read.");
1247 static PyObject *
1248 array_fromfile_as_read(arrayobject *self, PyObject *args)
1250 if (PyErr_WarnPy3k("array.read() not supported in 3.x; "
1251 "use array.fromfile()", 1) < 0)
1252 return NULL;
1253 return array_fromfile(self, args);
1257 static PyObject *
1258 array_tofile(arrayobject *self, PyObject *f)
1260 FILE *fp;
1262 fp = PyFile_AsFile(f);
1263 if (fp == NULL) {
1264 PyErr_SetString(PyExc_TypeError, "arg must be open file");
1265 return NULL;
1267 if (self->ob_size > 0) {
1268 if (fwrite(self->ob_item, self->ob_descr->itemsize,
1269 self->ob_size, fp) != (size_t)self->ob_size) {
1270 PyErr_SetFromErrno(PyExc_IOError);
1271 clearerr(fp);
1272 return NULL;
1275 Py_INCREF(Py_None);
1276 return Py_None;
1279 PyDoc_STRVAR(tofile_doc,
1280 "tofile(f)\n\
1282 Write all items (as machine values) to the file object f. Also called as\n\
1283 write.");
1286 static PyObject *
1287 array_tofile_as_write(arrayobject *self, PyObject *f)
1289 if (PyErr_WarnPy3k("array.write() not supported in 3.x; "
1290 "use array.tofile()", 1) < 0)
1291 return NULL;
1292 return array_tofile(self, f);
1296 static PyObject *
1297 array_fromlist(arrayobject *self, PyObject *list)
1299 Py_ssize_t n;
1300 Py_ssize_t itemsize = self->ob_descr->itemsize;
1302 if (!PyList_Check(list)) {
1303 PyErr_SetString(PyExc_TypeError, "arg must be list");
1304 return NULL;
1306 n = PyList_Size(list);
1307 if (n > 0) {
1308 char *item = self->ob_item;
1309 Py_ssize_t i;
1310 PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1311 if (item == NULL) {
1312 PyErr_NoMemory();
1313 return NULL;
1315 self->ob_item = item;
1316 Py_SIZE(self) += n;
1317 self->allocated = Py_SIZE(self);
1318 for (i = 0; i < n; i++) {
1319 PyObject *v = PyList_GetItem(list, i);
1320 if ((*self->ob_descr->setitem)(self,
1321 Py_SIZE(self) - n + i, v) != 0) {
1322 Py_SIZE(self) -= n;
1323 if (itemsize && (self->ob_size > PY_SSIZE_T_MAX / itemsize)) {
1324 return PyErr_NoMemory();
1326 PyMem_RESIZE(item, char,
1327 Py_SIZE(self) * itemsize);
1328 self->ob_item = item;
1329 self->allocated = Py_SIZE(self);
1330 return NULL;
1334 Py_INCREF(Py_None);
1335 return Py_None;
1338 PyDoc_STRVAR(fromlist_doc,
1339 "fromlist(list)\n\
1341 Append items to array from list.");
1344 static PyObject *
1345 array_tolist(arrayobject *self, PyObject *unused)
1347 PyObject *list = PyList_New(Py_SIZE(self));
1348 Py_ssize_t i;
1350 if (list == NULL)
1351 return NULL;
1352 for (i = 0; i < Py_SIZE(self); i++) {
1353 PyObject *v = getarrayitem((PyObject *)self, i);
1354 if (v == NULL) {
1355 Py_DECREF(list);
1356 return NULL;
1358 PyList_SetItem(list, i, v);
1360 return list;
1363 PyDoc_STRVAR(tolist_doc,
1364 "tolist() -> list\n\
1366 Convert array to an ordinary list with the same items.");
1369 static PyObject *
1370 array_fromstring(arrayobject *self, PyObject *args)
1372 char *str;
1373 Py_ssize_t n;
1374 int itemsize = self->ob_descr->itemsize;
1375 if (!PyArg_ParseTuple(args, "s#:fromstring", &str, &n))
1376 return NULL;
1377 if (n % itemsize != 0) {
1378 PyErr_SetString(PyExc_ValueError,
1379 "string length not a multiple of item size");
1380 return NULL;
1382 n = n / itemsize;
1383 if (n > 0) {
1384 char *item = self->ob_item;
1385 if ((n > PY_SSIZE_T_MAX - Py_SIZE(self)) ||
1386 ((Py_SIZE(self) + n) > PY_SSIZE_T_MAX / itemsize)) {
1387 return PyErr_NoMemory();
1389 PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1390 if (item == NULL) {
1391 PyErr_NoMemory();
1392 return NULL;
1394 self->ob_item = item;
1395 Py_SIZE(self) += n;
1396 self->allocated = Py_SIZE(self);
1397 memcpy(item + (Py_SIZE(self) - n) * itemsize,
1398 str, itemsize*n);
1400 Py_INCREF(Py_None);
1401 return Py_None;
1404 PyDoc_STRVAR(fromstring_doc,
1405 "fromstring(string)\n\
1407 Appends items from the string, interpreting it as an array of machine\n\
1408 values,as if it had been read from a file using the fromfile() method).");
1411 static PyObject *
1412 array_tostring(arrayobject *self, PyObject *unused)
1414 if (self->ob_size <= PY_SSIZE_T_MAX / self->ob_descr->itemsize) {
1415 return PyString_FromStringAndSize(self->ob_item,
1416 Py_SIZE(self) * self->ob_descr->itemsize);
1417 } else {
1418 return PyErr_NoMemory();
1422 PyDoc_STRVAR(tostring_doc,
1423 "tostring() -> string\n\
1425 Convert the array to an array of machine values and return the string\n\
1426 representation.");
1430 #ifdef Py_USING_UNICODE
1431 static PyObject *
1432 array_fromunicode(arrayobject *self, PyObject *args)
1434 Py_UNICODE *ustr;
1435 Py_ssize_t n;
1437 if (!PyArg_ParseTuple(args, "u#:fromunicode", &ustr, &n))
1438 return NULL;
1439 if (self->ob_descr->typecode != 'u') {
1440 PyErr_SetString(PyExc_ValueError,
1441 "fromunicode() may only be called on "
1442 "type 'u' arrays");
1443 return NULL;
1445 if (n > 0) {
1446 Py_UNICODE *item = (Py_UNICODE *) self->ob_item;
1447 if (Py_SIZE(self) > PY_SSIZE_T_MAX - n) {
1448 return PyErr_NoMemory();
1450 PyMem_RESIZE(item, Py_UNICODE, Py_SIZE(self) + n);
1451 if (item == NULL) {
1452 PyErr_NoMemory();
1453 return NULL;
1455 self->ob_item = (char *) item;
1456 Py_SIZE(self) += n;
1457 self->allocated = Py_SIZE(self);
1458 memcpy(item + Py_SIZE(self) - n,
1459 ustr, n * sizeof(Py_UNICODE));
1462 Py_INCREF(Py_None);
1463 return Py_None;
1466 PyDoc_STRVAR(fromunicode_doc,
1467 "fromunicode(ustr)\n\
1469 Extends this array with data from the unicode string ustr.\n\
1470 The array must be a type 'u' array; otherwise a ValueError\n\
1471 is raised. Use array.fromstring(ustr.decode(...)) to\n\
1472 append Unicode data to an array of some other type.");
1475 static PyObject *
1476 array_tounicode(arrayobject *self, PyObject *unused)
1478 if (self->ob_descr->typecode != 'u') {
1479 PyErr_SetString(PyExc_ValueError,
1480 "tounicode() may only be called on type 'u' arrays");
1481 return NULL;
1483 return PyUnicode_FromUnicode((Py_UNICODE *) self->ob_item, Py_SIZE(self));
1486 PyDoc_STRVAR(tounicode_doc,
1487 "tounicode() -> unicode\n\
1489 Convert the array to a unicode string. The array must be\n\
1490 a type 'u' array; otherwise a ValueError is raised. Use\n\
1491 array.tostring().decode() to obtain a unicode string from\n\
1492 an array of some other type.");
1494 #endif /* Py_USING_UNICODE */
1496 static PyObject *
1497 array_reduce(arrayobject *array)
1499 PyObject *dict, *result, *list;
1501 dict = PyObject_GetAttrString((PyObject *)array, "__dict__");
1502 if (dict == NULL) {
1503 if (!PyErr_ExceptionMatches(PyExc_AttributeError))
1504 return NULL;
1505 PyErr_Clear();
1506 dict = Py_None;
1507 Py_INCREF(dict);
1509 /* Unlike in Python 3.x, we never use the more efficient memory
1510 * representation of an array for pickling. This is unfortunately
1511 * necessary to allow array objects to be unpickled by Python 3.x,
1512 * since str objects from 2.x are always decoded to unicode in
1513 * Python 3.x.
1515 list = array_tolist(array, NULL);
1516 if (list == NULL) {
1517 Py_DECREF(dict);
1518 return NULL;
1520 result = Py_BuildValue(
1521 "O(cO)O", Py_TYPE(array), array->ob_descr->typecode, list, dict);
1522 Py_DECREF(list);
1523 Py_DECREF(dict);
1524 return result;
1527 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1529 static PyObject *
1530 array_get_typecode(arrayobject *a, void *closure)
1532 char tc = a->ob_descr->typecode;
1533 return PyString_FromStringAndSize(&tc, 1);
1536 static PyObject *
1537 array_get_itemsize(arrayobject *a, void *closure)
1539 return PyInt_FromLong((long)a->ob_descr->itemsize);
1542 static PyGetSetDef array_getsets [] = {
1543 {"typecode", (getter) array_get_typecode, NULL,
1544 "the typecode character used to create the array"},
1545 {"itemsize", (getter) array_get_itemsize, NULL,
1546 "the size, in bytes, of one array item"},
1547 {NULL}
1550 static PyMethodDef array_methods[] = {
1551 {"append", (PyCFunction)array_append, METH_O,
1552 append_doc},
1553 {"buffer_info", (PyCFunction)array_buffer_info, METH_NOARGS,
1554 buffer_info_doc},
1555 {"byteswap", (PyCFunction)array_byteswap, METH_NOARGS,
1556 byteswap_doc},
1557 {"__copy__", (PyCFunction)array_copy, METH_NOARGS,
1558 copy_doc},
1559 {"count", (PyCFunction)array_count, METH_O,
1560 count_doc},
1561 {"__deepcopy__",(PyCFunction)array_copy, METH_O,
1562 copy_doc},
1563 {"extend", (PyCFunction)array_extend, METH_O,
1564 extend_doc},
1565 {"fromfile", (PyCFunction)array_fromfile, METH_VARARGS,
1566 fromfile_doc},
1567 {"fromlist", (PyCFunction)array_fromlist, METH_O,
1568 fromlist_doc},
1569 {"fromstring", (PyCFunction)array_fromstring, METH_VARARGS,
1570 fromstring_doc},
1571 #ifdef Py_USING_UNICODE
1572 {"fromunicode", (PyCFunction)array_fromunicode, METH_VARARGS,
1573 fromunicode_doc},
1574 #endif
1575 {"index", (PyCFunction)array_index, METH_O,
1576 index_doc},
1577 {"insert", (PyCFunction)array_insert, METH_VARARGS,
1578 insert_doc},
1579 {"pop", (PyCFunction)array_pop, METH_VARARGS,
1580 pop_doc},
1581 {"read", (PyCFunction)array_fromfile_as_read, METH_VARARGS,
1582 fromfile_doc},
1583 {"__reduce__", (PyCFunction)array_reduce, METH_NOARGS,
1584 reduce_doc},
1585 {"remove", (PyCFunction)array_remove, METH_O,
1586 remove_doc},
1587 {"reverse", (PyCFunction)array_reverse, METH_NOARGS,
1588 reverse_doc},
1589 /* {"sort", (PyCFunction)array_sort, METH_VARARGS,
1590 sort_doc},*/
1591 {"tofile", (PyCFunction)array_tofile, METH_O,
1592 tofile_doc},
1593 {"tolist", (PyCFunction)array_tolist, METH_NOARGS,
1594 tolist_doc},
1595 {"tostring", (PyCFunction)array_tostring, METH_NOARGS,
1596 tostring_doc},
1597 #ifdef Py_USING_UNICODE
1598 {"tounicode", (PyCFunction)array_tounicode, METH_NOARGS,
1599 tounicode_doc},
1600 #endif
1601 {"write", (PyCFunction)array_tofile_as_write, METH_O,
1602 tofile_doc},
1603 {NULL, NULL} /* sentinel */
1606 static PyObject *
1607 array_repr(arrayobject *a)
1609 char buf[256], typecode;
1610 PyObject *s, *t, *v = NULL;
1611 Py_ssize_t len;
1613 len = Py_SIZE(a);
1614 typecode = a->ob_descr->typecode;
1615 if (len == 0) {
1616 PyOS_snprintf(buf, sizeof(buf), "array('%c')", typecode);
1617 return PyString_FromString(buf);
1620 if (typecode == 'c')
1621 v = array_tostring(a, NULL);
1622 #ifdef Py_USING_UNICODE
1623 else if (typecode == 'u')
1624 v = array_tounicode(a, NULL);
1625 #endif
1626 else
1627 v = array_tolist(a, NULL);
1628 t = PyObject_Repr(v);
1629 Py_XDECREF(v);
1631 PyOS_snprintf(buf, sizeof(buf), "array('%c', ", typecode);
1632 s = PyString_FromString(buf);
1633 PyString_ConcatAndDel(&s, t);
1634 PyString_ConcatAndDel(&s, PyString_FromString(")"));
1635 return s;
1638 static PyObject*
1639 array_subscr(arrayobject* self, PyObject* item)
1641 if (PyIndex_Check(item)) {
1642 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1643 if (i==-1 && PyErr_Occurred()) {
1644 return NULL;
1646 if (i < 0)
1647 i += Py_SIZE(self);
1648 return array_item(self, i);
1650 else if (PySlice_Check(item)) {
1651 Py_ssize_t start, stop, step, slicelength, cur, i;
1652 PyObject* result;
1653 arrayobject* ar;
1654 int itemsize = self->ob_descr->itemsize;
1656 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
1657 &start, &stop, &step, &slicelength) < 0) {
1658 return NULL;
1661 if (slicelength <= 0) {
1662 return newarrayobject(&Arraytype, 0, self->ob_descr);
1664 else if (step == 1) {
1665 PyObject *result = newarrayobject(&Arraytype,
1666 slicelength, self->ob_descr);
1667 if (result == NULL)
1668 return NULL;
1669 memcpy(((arrayobject *)result)->ob_item,
1670 self->ob_item + start * itemsize,
1671 slicelength * itemsize);
1672 return result;
1674 else {
1675 result = newarrayobject(&Arraytype, slicelength, self->ob_descr);
1676 if (!result) return NULL;
1678 ar = (arrayobject*)result;
1680 for (cur = start, i = 0; i < slicelength;
1681 cur += step, i++) {
1682 memcpy(ar->ob_item + i*itemsize,
1683 self->ob_item + cur*itemsize,
1684 itemsize);
1687 return result;
1690 else {
1691 PyErr_SetString(PyExc_TypeError,
1692 "array indices must be integers");
1693 return NULL;
1697 static int
1698 array_ass_subscr(arrayobject* self, PyObject* item, PyObject* value)
1700 Py_ssize_t start, stop, step, slicelength, needed;
1701 arrayobject* other;
1702 int itemsize;
1704 if (PyIndex_Check(item)) {
1705 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1707 if (i == -1 && PyErr_Occurred())
1708 return -1;
1709 if (i < 0)
1710 i += Py_SIZE(self);
1711 if (i < 0 || i >= Py_SIZE(self)) {
1712 PyErr_SetString(PyExc_IndexError,
1713 "array assignment index out of range");
1714 return -1;
1716 if (value == NULL) {
1717 /* Fall through to slice assignment */
1718 start = i;
1719 stop = i + 1;
1720 step = 1;
1721 slicelength = 1;
1723 else
1724 return (*self->ob_descr->setitem)(self, i, value);
1726 else if (PySlice_Check(item)) {
1727 if (PySlice_GetIndicesEx((PySliceObject *)item,
1728 Py_SIZE(self), &start, &stop,
1729 &step, &slicelength) < 0) {
1730 return -1;
1733 else {
1734 PyErr_SetString(PyExc_TypeError,
1735 "array indices must be integer");
1736 return -1;
1738 if (value == NULL) {
1739 other = NULL;
1740 needed = 0;
1742 else if (array_Check(value)) {
1743 other = (arrayobject *)value;
1744 needed = Py_SIZE(other);
1745 if (self == other) {
1746 /* Special case "self[i:j] = self" -- copy self first */
1747 int ret;
1748 value = array_slice(other, 0, needed);
1749 if (value == NULL)
1750 return -1;
1751 ret = array_ass_subscr(self, item, value);
1752 Py_DECREF(value);
1753 return ret;
1755 if (other->ob_descr != self->ob_descr) {
1756 PyErr_BadArgument();
1757 return -1;
1760 else {
1761 PyErr_Format(PyExc_TypeError,
1762 "can only assign array (not \"%.200s\") to array slice",
1763 Py_TYPE(value)->tp_name);
1764 return -1;
1766 itemsize = self->ob_descr->itemsize;
1767 /* for 'a[2:1] = ...', the insertion point is 'start', not 'stop' */
1768 if ((step > 0 && stop < start) ||
1769 (step < 0 && stop > start))
1770 stop = start;
1771 if (step == 1) {
1772 if (slicelength > needed) {
1773 memmove(self->ob_item + (start + needed) * itemsize,
1774 self->ob_item + stop * itemsize,
1775 (Py_SIZE(self) - stop) * itemsize);
1776 if (array_resize(self, Py_SIZE(self) +
1777 needed - slicelength) < 0)
1778 return -1;
1780 else if (slicelength < needed) {
1781 if (array_resize(self, Py_SIZE(self) +
1782 needed - slicelength) < 0)
1783 return -1;
1784 memmove(self->ob_item + (start + needed) * itemsize,
1785 self->ob_item + stop * itemsize,
1786 (Py_SIZE(self) - start - needed) * itemsize);
1788 if (needed > 0)
1789 memcpy(self->ob_item + start * itemsize,
1790 other->ob_item, needed * itemsize);
1791 return 0;
1793 else if (needed == 0) {
1794 /* Delete slice */
1795 Py_ssize_t cur, i;
1797 if (step < 0) {
1798 stop = start + 1;
1799 start = stop + step * (slicelength - 1) - 1;
1800 step = -step;
1802 for (cur = start, i = 0; i < slicelength;
1803 cur += step, i++) {
1804 Py_ssize_t lim = step - 1;
1806 if (cur + step >= Py_SIZE(self))
1807 lim = Py_SIZE(self) - cur - 1;
1808 memmove(self->ob_item + (cur - i) * itemsize,
1809 self->ob_item + (cur + 1) * itemsize,
1810 lim * itemsize);
1812 cur = start + slicelength * step;
1813 if (cur < Py_SIZE(self)) {
1814 memmove(self->ob_item + (cur-slicelength) * itemsize,
1815 self->ob_item + cur * itemsize,
1816 (Py_SIZE(self) - cur) * itemsize);
1818 if (array_resize(self, Py_SIZE(self) - slicelength) < 0)
1819 return -1;
1820 return 0;
1822 else {
1823 Py_ssize_t cur, i;
1825 if (needed != slicelength) {
1826 PyErr_Format(PyExc_ValueError,
1827 "attempt to assign array of size %zd "
1828 "to extended slice of size %zd",
1829 needed, slicelength);
1830 return -1;
1832 for (cur = start, i = 0; i < slicelength;
1833 cur += step, i++) {
1834 memcpy(self->ob_item + cur * itemsize,
1835 other->ob_item + i * itemsize,
1836 itemsize);
1838 return 0;
1842 static PyMappingMethods array_as_mapping = {
1843 (lenfunc)array_length,
1844 (binaryfunc)array_subscr,
1845 (objobjargproc)array_ass_subscr
1848 static const void *emptybuf = "";
1850 static Py_ssize_t
1851 array_buffer_getreadbuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1853 if ( index != 0 ) {
1854 PyErr_SetString(PyExc_SystemError,
1855 "Accessing non-existent array segment");
1856 return -1;
1858 *ptr = (void *)self->ob_item;
1859 if (*ptr == NULL)
1860 *ptr = emptybuf;
1861 return Py_SIZE(self)*self->ob_descr->itemsize;
1864 static Py_ssize_t
1865 array_buffer_getwritebuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1867 if ( index != 0 ) {
1868 PyErr_SetString(PyExc_SystemError,
1869 "Accessing non-existent array segment");
1870 return -1;
1872 *ptr = (void *)self->ob_item;
1873 if (*ptr == NULL)
1874 *ptr = emptybuf;
1875 return Py_SIZE(self)*self->ob_descr->itemsize;
1878 static Py_ssize_t
1879 array_buffer_getsegcount(arrayobject *self, Py_ssize_t *lenp)
1881 if ( lenp )
1882 *lenp = Py_SIZE(self)*self->ob_descr->itemsize;
1883 return 1;
1886 static PySequenceMethods array_as_sequence = {
1887 (lenfunc)array_length, /*sq_length*/
1888 (binaryfunc)array_concat, /*sq_concat*/
1889 (ssizeargfunc)array_repeat, /*sq_repeat*/
1890 (ssizeargfunc)array_item, /*sq_item*/
1891 (ssizessizeargfunc)array_slice, /*sq_slice*/
1892 (ssizeobjargproc)array_ass_item, /*sq_ass_item*/
1893 (ssizessizeobjargproc)array_ass_slice, /*sq_ass_slice*/
1894 (objobjproc)array_contains, /*sq_contains*/
1895 (binaryfunc)array_inplace_concat, /*sq_inplace_concat*/
1896 (ssizeargfunc)array_inplace_repeat /*sq_inplace_repeat*/
1899 static PyBufferProcs array_as_buffer = {
1900 (readbufferproc)array_buffer_getreadbuf,
1901 (writebufferproc)array_buffer_getwritebuf,
1902 (segcountproc)array_buffer_getsegcount,
1903 NULL,
1906 static PyObject *
1907 array_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1909 char c;
1910 PyObject *initial = NULL, *it = NULL;
1911 struct arraydescr *descr;
1913 if (type == &Arraytype && !_PyArg_NoKeywords("array.array()", kwds))
1914 return NULL;
1916 if (!PyArg_ParseTuple(args, "c|O:array", &c, &initial))
1917 return NULL;
1919 if (!(initial == NULL || PyList_Check(initial)
1920 || PyString_Check(initial) || PyTuple_Check(initial)
1921 || (c == 'u' && PyUnicode_Check(initial)))) {
1922 it = PyObject_GetIter(initial);
1923 if (it == NULL)
1924 return NULL;
1925 /* We set initial to NULL so that the subsequent code
1926 will create an empty array of the appropriate type
1927 and afterwards we can use array_iter_extend to populate
1928 the array.
1930 initial = NULL;
1932 for (descr = descriptors; descr->typecode != '\0'; descr++) {
1933 if (descr->typecode == c) {
1934 PyObject *a;
1935 Py_ssize_t len;
1937 if (initial == NULL || !(PyList_Check(initial)
1938 || PyTuple_Check(initial)))
1939 len = 0;
1940 else
1941 len = PySequence_Size(initial);
1943 a = newarrayobject(type, len, descr);
1944 if (a == NULL)
1945 return NULL;
1947 if (len > 0) {
1948 Py_ssize_t i;
1949 for (i = 0; i < len; i++) {
1950 PyObject *v =
1951 PySequence_GetItem(initial, i);
1952 if (v == NULL) {
1953 Py_DECREF(a);
1954 return NULL;
1956 if (setarrayitem(a, i, v) != 0) {
1957 Py_DECREF(v);
1958 Py_DECREF(a);
1959 return NULL;
1961 Py_DECREF(v);
1963 } else if (initial != NULL && PyString_Check(initial)) {
1964 PyObject *t_initial, *v;
1965 t_initial = PyTuple_Pack(1, initial);
1966 if (t_initial == NULL) {
1967 Py_DECREF(a);
1968 return NULL;
1970 v = array_fromstring((arrayobject *)a,
1971 t_initial);
1972 Py_DECREF(t_initial);
1973 if (v == NULL) {
1974 Py_DECREF(a);
1975 return NULL;
1977 Py_DECREF(v);
1978 #ifdef Py_USING_UNICODE
1979 } else if (initial != NULL && PyUnicode_Check(initial)) {
1980 Py_ssize_t n = PyUnicode_GET_DATA_SIZE(initial);
1981 if (n > 0) {
1982 arrayobject *self = (arrayobject *)a;
1983 char *item = self->ob_item;
1984 item = (char *)PyMem_Realloc(item, n);
1985 if (item == NULL) {
1986 PyErr_NoMemory();
1987 Py_DECREF(a);
1988 return NULL;
1990 self->ob_item = item;
1991 Py_SIZE(self) = n / sizeof(Py_UNICODE);
1992 memcpy(item, PyUnicode_AS_DATA(initial), n);
1993 self->allocated = Py_SIZE(self);
1995 #endif
1997 if (it != NULL) {
1998 if (array_iter_extend((arrayobject *)a, it) == -1) {
1999 Py_DECREF(it);
2000 Py_DECREF(a);
2001 return NULL;
2003 Py_DECREF(it);
2005 return a;
2008 PyErr_SetString(PyExc_ValueError,
2009 "bad typecode (must be c, b, B, u, h, H, i, I, l, L, f or d)");
2010 return NULL;
2014 PyDoc_STRVAR(module_doc,
2015 "This module defines an object type which can efficiently represent\n\
2016 an array of basic values: characters, integers, floating point\n\
2017 numbers. Arrays are sequence types and behave very much like lists,\n\
2018 except that the type of objects stored in them is constrained. The\n\
2019 type is specified at object creation time by using a type code, which\n\
2020 is a single character. The following type codes are defined:\n\
2022 Type code C Type Minimum size in bytes \n\
2023 'c' character 1 \n\
2024 'b' signed integer 1 \n\
2025 'B' unsigned integer 1 \n\
2026 'u' Unicode character 2 \n\
2027 'h' signed integer 2 \n\
2028 'H' unsigned integer 2 \n\
2029 'i' signed integer 2 \n\
2030 'I' unsigned integer 2 \n\
2031 'l' signed integer 4 \n\
2032 'L' unsigned integer 4 \n\
2033 'f' floating point 4 \n\
2034 'd' floating point 8 \n\
2036 The constructor is:\n\
2038 array(typecode [, initializer]) -- create a new array\n\
2041 PyDoc_STRVAR(arraytype_doc,
2042 "array(typecode [, initializer]) -> array\n\
2044 Return a new array whose items are restricted by typecode, and\n\
2045 initialized from the optional initializer value, which must be a list,\n\
2046 string. or iterable over elements of the appropriate type.\n\
2048 Arrays represent basic values and behave very much like lists, except\n\
2049 the type of objects stored in them is constrained.\n\
2051 Methods:\n\
2053 append() -- append a new item to the end of the array\n\
2054 buffer_info() -- return information giving the current memory info\n\
2055 byteswap() -- byteswap all the items of the array\n\
2056 count() -- return number of occurrences of an object\n\
2057 extend() -- extend array by appending multiple elements from an iterable\n\
2058 fromfile() -- read items from a file object\n\
2059 fromlist() -- append items from the list\n\
2060 fromstring() -- append items from the string\n\
2061 index() -- return index of first occurrence of an object\n\
2062 insert() -- insert a new item into the array at a provided position\n\
2063 pop() -- remove and return item (default last)\n\
2064 read() -- DEPRECATED, use fromfile()\n\
2065 remove() -- remove first occurrence of an object\n\
2066 reverse() -- reverse the order of the items in the array\n\
2067 tofile() -- write all items to a file object\n\
2068 tolist() -- return the array converted to an ordinary list\n\
2069 tostring() -- return the array converted to a string\n\
2070 write() -- DEPRECATED, use tofile()\n\
2072 Attributes:\n\
2074 typecode -- the typecode character used to create the array\n\
2075 itemsize -- the length in bytes of one array item\n\
2078 static PyObject *array_iter(arrayobject *ao);
2080 static PyTypeObject Arraytype = {
2081 PyVarObject_HEAD_INIT(NULL, 0)
2082 "array.array",
2083 sizeof(arrayobject),
2085 (destructor)array_dealloc, /* tp_dealloc */
2086 0, /* tp_print */
2087 0, /* tp_getattr */
2088 0, /* tp_setattr */
2089 0, /* tp_compare */
2090 (reprfunc)array_repr, /* tp_repr */
2091 0, /* tp_as_number*/
2092 &array_as_sequence, /* tp_as_sequence*/
2093 &array_as_mapping, /* tp_as_mapping*/
2094 0, /* tp_hash */
2095 0, /* tp_call */
2096 0, /* tp_str */
2097 PyObject_GenericGetAttr, /* tp_getattro */
2098 0, /* tp_setattro */
2099 &array_as_buffer, /* tp_as_buffer*/
2100 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
2101 arraytype_doc, /* tp_doc */
2102 0, /* tp_traverse */
2103 0, /* tp_clear */
2104 array_richcompare, /* tp_richcompare */
2105 offsetof(arrayobject, weakreflist), /* tp_weaklistoffset */
2106 (getiterfunc)array_iter, /* tp_iter */
2107 0, /* tp_iternext */
2108 array_methods, /* tp_methods */
2109 0, /* tp_members */
2110 array_getsets, /* tp_getset */
2111 0, /* tp_base */
2112 0, /* tp_dict */
2113 0, /* tp_descr_get */
2114 0, /* tp_descr_set */
2115 0, /* tp_dictoffset */
2116 0, /* tp_init */
2117 PyType_GenericAlloc, /* tp_alloc */
2118 array_new, /* tp_new */
2119 PyObject_Del, /* tp_free */
2123 /*********************** Array Iterator **************************/
2125 typedef struct {
2126 PyObject_HEAD
2127 Py_ssize_t index;
2128 arrayobject *ao;
2129 PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
2130 } arrayiterobject;
2132 static PyTypeObject PyArrayIter_Type;
2134 #define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)
2136 static PyObject *
2137 array_iter(arrayobject *ao)
2139 arrayiterobject *it;
2141 if (!array_Check(ao)) {
2142 PyErr_BadInternalCall();
2143 return NULL;
2146 it = PyObject_GC_New(arrayiterobject, &PyArrayIter_Type);
2147 if (it == NULL)
2148 return NULL;
2150 Py_INCREF(ao);
2151 it->ao = ao;
2152 it->index = 0;
2153 it->getitem = ao->ob_descr->getitem;
2154 PyObject_GC_Track(it);
2155 return (PyObject *)it;
2158 static PyObject *
2159 arrayiter_next(arrayiterobject *it)
2161 assert(PyArrayIter_Check(it));
2162 if (it->index < Py_SIZE(it->ao))
2163 return (*it->getitem)(it->ao, it->index++);
2164 return NULL;
2167 static void
2168 arrayiter_dealloc(arrayiterobject *it)
2170 PyObject_GC_UnTrack(it);
2171 Py_XDECREF(it->ao);
2172 PyObject_GC_Del(it);
2175 static int
2176 arrayiter_traverse(arrayiterobject *it, visitproc visit, void *arg)
2178 Py_VISIT(it->ao);
2179 return 0;
2182 static PyTypeObject PyArrayIter_Type = {
2183 PyVarObject_HEAD_INIT(NULL, 0)
2184 "arrayiterator", /* tp_name */
2185 sizeof(arrayiterobject), /* tp_basicsize */
2186 0, /* tp_itemsize */
2187 /* methods */
2188 (destructor)arrayiter_dealloc, /* tp_dealloc */
2189 0, /* tp_print */
2190 0, /* tp_getattr */
2191 0, /* tp_setattr */
2192 0, /* tp_compare */
2193 0, /* tp_repr */
2194 0, /* tp_as_number */
2195 0, /* tp_as_sequence */
2196 0, /* tp_as_mapping */
2197 0, /* tp_hash */
2198 0, /* tp_call */
2199 0, /* tp_str */
2200 PyObject_GenericGetAttr, /* tp_getattro */
2201 0, /* tp_setattro */
2202 0, /* tp_as_buffer */
2203 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2204 0, /* tp_doc */
2205 (traverseproc)arrayiter_traverse, /* tp_traverse */
2206 0, /* tp_clear */
2207 0, /* tp_richcompare */
2208 0, /* tp_weaklistoffset */
2209 PyObject_SelfIter, /* tp_iter */
2210 (iternextfunc)arrayiter_next, /* tp_iternext */
2211 0, /* tp_methods */
2215 /*********************** Install Module **************************/
2217 /* No functions in array module. */
2218 static PyMethodDef a_methods[] = {
2219 {NULL, NULL, 0, NULL} /* Sentinel */
2223 PyMODINIT_FUNC
2224 initarray(void)
2226 PyObject *m;
2228 Arraytype.ob_type = &PyType_Type;
2229 PyArrayIter_Type.ob_type = &PyType_Type;
2230 m = Py_InitModule3("array", a_methods, module_doc);
2231 if (m == NULL)
2232 return;
2234 Py_INCREF((PyObject *)&Arraytype);
2235 PyModule_AddObject(m, "ArrayType", (PyObject *)&Arraytype);
2236 Py_INCREF((PyObject *)&Arraytype);
2237 PyModule_AddObject(m, "array", (PyObject *)&Arraytype);
2238 /* No need to check the error here, the caller will do that */