This reverts r63675 based on the discussion in this thread:
[python.git] / Modules / arraymodule.c
blob89ed27a0b7480b465622a4300337797bcc42b0f8
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 Py_SIZE(op) = size;
436 if (size <= 0) {
437 op->ob_item = NULL;
439 else {
440 op->ob_item = PyMem_NEW(char, nbytes);
441 if (op->ob_item == NULL) {
442 PyObject_Del(op);
443 return PyErr_NoMemory();
446 op->ob_descr = descr;
447 op->allocated = size;
448 op->weakreflist = NULL;
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 size = Py_SIZE(a) + Py_SIZE(b);
656 np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
657 if (np == NULL) {
658 return NULL;
660 memcpy(np->ob_item, a->ob_item, Py_SIZE(a)*a->ob_descr->itemsize);
661 memcpy(np->ob_item + Py_SIZE(a)*a->ob_descr->itemsize,
662 b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
663 return (PyObject *)np;
664 #undef b
667 static PyObject *
668 array_repeat(arrayobject *a, Py_ssize_t n)
670 Py_ssize_t i;
671 Py_ssize_t size;
672 arrayobject *np;
673 char *p;
674 Py_ssize_t nbytes;
675 if (n < 0)
676 n = 0;
677 size = Py_SIZE(a) * n;
678 np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
679 if (np == NULL)
680 return NULL;
681 p = np->ob_item;
682 nbytes = Py_SIZE(a) * a->ob_descr->itemsize;
683 for (i = 0; i < n; i++) {
684 memcpy(p, a->ob_item, nbytes);
685 p += nbytes;
687 return (PyObject *) np;
690 static int
691 array_ass_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
693 char *item;
694 Py_ssize_t n; /* Size of replacement array */
695 Py_ssize_t d; /* Change in size */
696 #define b ((arrayobject *)v)
697 if (v == NULL)
698 n = 0;
699 else if (array_Check(v)) {
700 n = Py_SIZE(b);
701 if (a == b) {
702 /* Special case "a[i:j] = a" -- copy b first */
703 int ret;
704 v = array_slice(b, 0, n);
705 if (!v)
706 return -1;
707 ret = array_ass_slice(a, ilow, ihigh, v);
708 Py_DECREF(v);
709 return ret;
711 if (b->ob_descr != a->ob_descr) {
712 PyErr_BadArgument();
713 return -1;
716 else {
717 PyErr_Format(PyExc_TypeError,
718 "can only assign array (not \"%.200s\") to array slice",
719 Py_TYPE(v)->tp_name);
720 return -1;
722 if (ilow < 0)
723 ilow = 0;
724 else if (ilow > Py_SIZE(a))
725 ilow = Py_SIZE(a);
726 if (ihigh < 0)
727 ihigh = 0;
728 if (ihigh < ilow)
729 ihigh = ilow;
730 else if (ihigh > Py_SIZE(a))
731 ihigh = Py_SIZE(a);
732 item = a->ob_item;
733 d = n - (ihigh-ilow);
734 if (d < 0) { /* Delete -d items */
735 memmove(item + (ihigh+d)*a->ob_descr->itemsize,
736 item + ihigh*a->ob_descr->itemsize,
737 (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
738 Py_SIZE(a) += d;
739 PyMem_RESIZE(item, char, Py_SIZE(a)*a->ob_descr->itemsize);
740 /* Can't fail */
741 a->ob_item = item;
742 a->allocated = Py_SIZE(a);
744 else if (d > 0) { /* Insert d items */
745 PyMem_RESIZE(item, char,
746 (Py_SIZE(a) + d)*a->ob_descr->itemsize);
747 if (item == NULL) {
748 PyErr_NoMemory();
749 return -1;
751 memmove(item + (ihigh+d)*a->ob_descr->itemsize,
752 item + ihigh*a->ob_descr->itemsize,
753 (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
754 a->ob_item = item;
755 Py_SIZE(a) += d;
756 a->allocated = Py_SIZE(a);
758 if (n > 0)
759 memcpy(item + ilow*a->ob_descr->itemsize, b->ob_item,
760 n*b->ob_descr->itemsize);
761 return 0;
762 #undef b
765 static int
766 array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)
768 if (i < 0 || i >= Py_SIZE(a)) {
769 PyErr_SetString(PyExc_IndexError,
770 "array assignment index out of range");
771 return -1;
773 if (v == NULL)
774 return array_ass_slice(a, i, i+1, v);
775 return (*a->ob_descr->setitem)(a, i, v);
778 static int
779 setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)
781 assert(array_Check(a));
782 return array_ass_item((arrayobject *)a, i, v);
785 static int
786 array_iter_extend(arrayobject *self, PyObject *bb)
788 PyObject *it, *v;
790 it = PyObject_GetIter(bb);
791 if (it == NULL)
792 return -1;
794 while ((v = PyIter_Next(it)) != NULL) {
795 if (ins1(self, (int) Py_SIZE(self), v) != 0) {
796 Py_DECREF(v);
797 Py_DECREF(it);
798 return -1;
800 Py_DECREF(v);
802 Py_DECREF(it);
803 if (PyErr_Occurred())
804 return -1;
805 return 0;
808 static int
809 array_do_extend(arrayobject *self, PyObject *bb)
811 Py_ssize_t size;
813 if (!array_Check(bb))
814 return array_iter_extend(self, bb);
815 #define b ((arrayobject *)bb)
816 if (self->ob_descr != b->ob_descr) {
817 PyErr_SetString(PyExc_TypeError,
818 "can only extend with array of same kind");
819 return -1;
821 size = Py_SIZE(self) + Py_SIZE(b);
822 PyMem_RESIZE(self->ob_item, char, size*self->ob_descr->itemsize);
823 if (self->ob_item == NULL) {
824 PyObject_Del(self);
825 PyErr_NoMemory();
826 return -1;
828 memcpy(self->ob_item + Py_SIZE(self)*self->ob_descr->itemsize,
829 b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
830 Py_SIZE(self) = size;
831 self->allocated = size;
833 return 0;
834 #undef b
837 static PyObject *
838 array_inplace_concat(arrayobject *self, PyObject *bb)
840 if (!array_Check(bb)) {
841 PyErr_Format(PyExc_TypeError,
842 "can only extend array with array (not \"%.200s\")",
843 Py_TYPE(bb)->tp_name);
844 return NULL;
846 if (array_do_extend(self, bb) == -1)
847 return NULL;
848 Py_INCREF(self);
849 return (PyObject *)self;
852 static PyObject *
853 array_inplace_repeat(arrayobject *self, Py_ssize_t n)
855 char *items, *p;
856 Py_ssize_t size, i;
858 if (Py_SIZE(self) > 0) {
859 if (n < 0)
860 n = 0;
861 items = self->ob_item;
862 size = Py_SIZE(self) * self->ob_descr->itemsize;
863 if (n == 0) {
864 PyMem_FREE(items);
865 self->ob_item = NULL;
866 Py_SIZE(self) = 0;
867 self->allocated = 0;
869 else {
870 PyMem_Resize(items, char, n * size);
871 if (items == NULL)
872 return PyErr_NoMemory();
873 p = items;
874 for (i = 1; i < n; i++) {
875 p += size;
876 memcpy(p, items, size);
878 self->ob_item = items;
879 Py_SIZE(self) *= n;
880 self->allocated = Py_SIZE(self);
883 Py_INCREF(self);
884 return (PyObject *)self;
888 static PyObject *
889 ins(arrayobject *self, Py_ssize_t where, PyObject *v)
891 if (ins1(self, where, v) != 0)
892 return NULL;
893 Py_INCREF(Py_None);
894 return Py_None;
897 static PyObject *
898 array_count(arrayobject *self, PyObject *v)
900 Py_ssize_t count = 0;
901 Py_ssize_t i;
903 for (i = 0; i < Py_SIZE(self); i++) {
904 PyObject *selfi = getarrayitem((PyObject *)self, i);
905 int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
906 Py_DECREF(selfi);
907 if (cmp > 0)
908 count++;
909 else if (cmp < 0)
910 return NULL;
912 return PyInt_FromSsize_t(count);
915 PyDoc_STRVAR(count_doc,
916 "count(x)\n\
918 Return number of occurences of x in the array.");
920 static PyObject *
921 array_index(arrayobject *self, PyObject *v)
923 Py_ssize_t i;
925 for (i = 0; i < Py_SIZE(self); i++) {
926 PyObject *selfi = getarrayitem((PyObject *)self, i);
927 int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
928 Py_DECREF(selfi);
929 if (cmp > 0) {
930 return PyInt_FromLong((long)i);
932 else if (cmp < 0)
933 return NULL;
935 PyErr_SetString(PyExc_ValueError, "array.index(x): x not in list");
936 return NULL;
939 PyDoc_STRVAR(index_doc,
940 "index(x)\n\
942 Return index of first occurence of x in the array.");
944 static int
945 array_contains(arrayobject *self, PyObject *v)
947 Py_ssize_t i;
948 int cmp;
950 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(self); i++) {
951 PyObject *selfi = getarrayitem((PyObject *)self, i);
952 cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
953 Py_DECREF(selfi);
955 return cmp;
958 static PyObject *
959 array_remove(arrayobject *self, PyObject *v)
961 int i;
963 for (i = 0; i < Py_SIZE(self); i++) {
964 PyObject *selfi = getarrayitem((PyObject *)self,i);
965 int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
966 Py_DECREF(selfi);
967 if (cmp > 0) {
968 if (array_ass_slice(self, i, i+1,
969 (PyObject *)NULL) != 0)
970 return NULL;
971 Py_INCREF(Py_None);
972 return Py_None;
974 else if (cmp < 0)
975 return NULL;
977 PyErr_SetString(PyExc_ValueError, "array.remove(x): x not in list");
978 return NULL;
981 PyDoc_STRVAR(remove_doc,
982 "remove(x)\n\
984 Remove the first occurence of x in the array.");
986 static PyObject *
987 array_pop(arrayobject *self, PyObject *args)
989 Py_ssize_t i = -1;
990 PyObject *v;
991 if (!PyArg_ParseTuple(args, "|n:pop", &i))
992 return NULL;
993 if (Py_SIZE(self) == 0) {
994 /* Special-case most common failure cause */
995 PyErr_SetString(PyExc_IndexError, "pop from empty array");
996 return NULL;
998 if (i < 0)
999 i += Py_SIZE(self);
1000 if (i < 0 || i >= Py_SIZE(self)) {
1001 PyErr_SetString(PyExc_IndexError, "pop index out of range");
1002 return NULL;
1004 v = getarrayitem((PyObject *)self,i);
1005 if (array_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
1006 Py_DECREF(v);
1007 return NULL;
1009 return v;
1012 PyDoc_STRVAR(pop_doc,
1013 "pop([i])\n\
1015 Return the i-th element and delete it from the array. i defaults to -1.");
1017 static PyObject *
1018 array_extend(arrayobject *self, PyObject *bb)
1020 if (array_do_extend(self, bb) == -1)
1021 return NULL;
1022 Py_INCREF(Py_None);
1023 return Py_None;
1026 PyDoc_STRVAR(extend_doc,
1027 "extend(array or iterable)\n\
1029 Append items to the end of the array.");
1031 static PyObject *
1032 array_insert(arrayobject *self, PyObject *args)
1034 Py_ssize_t i;
1035 PyObject *v;
1036 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
1037 return NULL;
1038 return ins(self, i, v);
1041 PyDoc_STRVAR(insert_doc,
1042 "insert(i,x)\n\
1044 Insert a new item x into the array before position i.");
1047 static PyObject *
1048 array_buffer_info(arrayobject *self, PyObject *unused)
1050 PyObject* retval = NULL;
1051 retval = PyTuple_New(2);
1052 if (!retval)
1053 return NULL;
1055 PyTuple_SET_ITEM(retval, 0, PyLong_FromVoidPtr(self->ob_item));
1056 PyTuple_SET_ITEM(retval, 1, PyInt_FromLong((long)(Py_SIZE(self))));
1058 return retval;
1061 PyDoc_STRVAR(buffer_info_doc,
1062 "buffer_info() -> (address, length)\n\
1064 Return a tuple (address, length) giving the current memory address and\n\
1065 the length in items of the buffer used to hold array's contents\n\
1066 The length should be multiplied by the itemsize attribute to calculate\n\
1067 the buffer length in bytes.");
1070 static PyObject *
1071 array_append(arrayobject *self, PyObject *v)
1073 return ins(self, (int) Py_SIZE(self), v);
1076 PyDoc_STRVAR(append_doc,
1077 "append(x)\n\
1079 Append new value x to the end of the array.");
1082 static PyObject *
1083 array_byteswap(arrayobject *self, PyObject *unused)
1085 char *p;
1086 Py_ssize_t i;
1088 switch (self->ob_descr->itemsize) {
1089 case 1:
1090 break;
1091 case 2:
1092 for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 2) {
1093 char p0 = p[0];
1094 p[0] = p[1];
1095 p[1] = p0;
1097 break;
1098 case 4:
1099 for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 4) {
1100 char p0 = p[0];
1101 char p1 = p[1];
1102 p[0] = p[3];
1103 p[1] = p[2];
1104 p[2] = p1;
1105 p[3] = p0;
1107 break;
1108 case 8:
1109 for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 8) {
1110 char p0 = p[0];
1111 char p1 = p[1];
1112 char p2 = p[2];
1113 char p3 = p[3];
1114 p[0] = p[7];
1115 p[1] = p[6];
1116 p[2] = p[5];
1117 p[3] = p[4];
1118 p[4] = p3;
1119 p[5] = p2;
1120 p[6] = p1;
1121 p[7] = p0;
1123 break;
1124 default:
1125 PyErr_SetString(PyExc_RuntimeError,
1126 "don't know how to byteswap this array type");
1127 return NULL;
1129 Py_INCREF(Py_None);
1130 return Py_None;
1133 PyDoc_STRVAR(byteswap_doc,
1134 "byteswap()\n\
1136 Byteswap all items of the array. If the items in the array are not 1, 2,\n\
1137 4, or 8 bytes in size, RuntimeError is raised.");
1139 static PyObject *
1140 array_reduce(arrayobject *array)
1142 PyObject *dict, *result;
1144 dict = PyObject_GetAttrString((PyObject *)array, "__dict__");
1145 if (dict == NULL) {
1146 PyErr_Clear();
1147 dict = Py_None;
1148 Py_INCREF(dict);
1150 if (Py_SIZE(array) > 0) {
1151 result = Py_BuildValue("O(cs#)O",
1152 Py_TYPE(array),
1153 array->ob_descr->typecode,
1154 array->ob_item,
1155 Py_SIZE(array) * array->ob_descr->itemsize,
1156 dict);
1157 } else {
1158 result = Py_BuildValue("O(c)O",
1159 Py_TYPE(array),
1160 array->ob_descr->typecode,
1161 dict);
1163 Py_DECREF(dict);
1164 return result;
1167 PyDoc_STRVAR(array_doc, "Return state information for pickling.");
1169 static PyObject *
1170 array_reverse(arrayobject *self, PyObject *unused)
1172 register Py_ssize_t itemsize = self->ob_descr->itemsize;
1173 register char *p, *q;
1174 /* little buffer to hold items while swapping */
1175 char tmp[256]; /* 8 is probably enough -- but why skimp */
1176 assert((size_t)itemsize <= sizeof(tmp));
1178 if (Py_SIZE(self) > 1) {
1179 for (p = self->ob_item,
1180 q = self->ob_item + (Py_SIZE(self) - 1)*itemsize;
1181 p < q;
1182 p += itemsize, q -= itemsize) {
1183 /* memory areas guaranteed disjoint, so memcpy
1184 * is safe (& memmove may be slower).
1186 memcpy(tmp, p, itemsize);
1187 memcpy(p, q, itemsize);
1188 memcpy(q, tmp, itemsize);
1192 Py_INCREF(Py_None);
1193 return Py_None;
1196 PyDoc_STRVAR(reverse_doc,
1197 "reverse()\n\
1199 Reverse the order of the items in the array.");
1201 static PyObject *
1202 array_fromfile(arrayobject *self, PyObject *args)
1204 PyObject *f;
1205 Py_ssize_t n;
1206 FILE *fp;
1207 if (!PyArg_ParseTuple(args, "On:fromfile", &f, &n))
1208 return NULL;
1209 fp = PyFile_AsFile(f);
1210 if (fp == NULL) {
1211 PyErr_SetString(PyExc_TypeError, "arg1 must be open file");
1212 return NULL;
1214 if (n > 0) {
1215 char *item = self->ob_item;
1216 Py_ssize_t itemsize = self->ob_descr->itemsize;
1217 size_t nread;
1218 Py_ssize_t newlength;
1219 size_t newbytes;
1220 /* Be careful here about overflow */
1221 if ((newlength = Py_SIZE(self) + n) <= 0 ||
1222 (newbytes = newlength * itemsize) / itemsize !=
1223 (size_t)newlength)
1224 goto nomem;
1225 PyMem_RESIZE(item, char, newbytes);
1226 if (item == NULL) {
1227 nomem:
1228 PyErr_NoMemory();
1229 return NULL;
1231 self->ob_item = item;
1232 Py_SIZE(self) += n;
1233 self->allocated = Py_SIZE(self);
1234 nread = fread(item + (Py_SIZE(self) - n) * itemsize,
1235 itemsize, n, fp);
1236 if (nread < (size_t)n) {
1237 Py_SIZE(self) -= (n - nread);
1238 PyMem_RESIZE(item, char, Py_SIZE(self)*itemsize);
1239 self->ob_item = item;
1240 self->allocated = Py_SIZE(self);
1241 PyErr_SetString(PyExc_EOFError,
1242 "not enough items in file");
1243 return NULL;
1246 Py_INCREF(Py_None);
1247 return Py_None;
1250 PyDoc_STRVAR(fromfile_doc,
1251 "fromfile(f, n)\n\
1253 Read n objects from the file object f and append them to the end of the\n\
1254 array. Also called as read.");
1257 static PyObject *
1258 array_fromfile_as_read(arrayobject *self, PyObject *args)
1260 if (PyErr_WarnPy3k("array.read() not supported in 3.x; "
1261 "use array.fromfile()", 1) < 0)
1262 return NULL;
1263 return array_fromfile(self, args);
1267 static PyObject *
1268 array_tofile(arrayobject *self, PyObject *f)
1270 FILE *fp;
1272 fp = PyFile_AsFile(f);
1273 if (fp == NULL) {
1274 PyErr_SetString(PyExc_TypeError, "arg must be open file");
1275 return NULL;
1277 if (self->ob_size > 0) {
1278 if (fwrite(self->ob_item, self->ob_descr->itemsize,
1279 self->ob_size, fp) != (size_t)self->ob_size) {
1280 PyErr_SetFromErrno(PyExc_IOError);
1281 clearerr(fp);
1282 return NULL;
1285 Py_INCREF(Py_None);
1286 return Py_None;
1289 PyDoc_STRVAR(tofile_doc,
1290 "tofile(f)\n\
1292 Write all items (as machine values) to the file object f. Also called as\n\
1293 write.");
1296 static PyObject *
1297 array_tofile_as_write(arrayobject *self, PyObject *f)
1299 if (PyErr_WarnPy3k("array.write() not supported in 3.x; "
1300 "use array.tofile()", 1) < 0)
1301 return NULL;
1302 return array_tofile(self, f);
1306 static PyObject *
1307 array_fromlist(arrayobject *self, PyObject *list)
1309 Py_ssize_t n;
1310 Py_ssize_t itemsize = self->ob_descr->itemsize;
1312 if (!PyList_Check(list)) {
1313 PyErr_SetString(PyExc_TypeError, "arg must be list");
1314 return NULL;
1316 n = PyList_Size(list);
1317 if (n > 0) {
1318 char *item = self->ob_item;
1319 Py_ssize_t i;
1320 PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1321 if (item == NULL) {
1322 PyErr_NoMemory();
1323 return NULL;
1325 self->ob_item = item;
1326 Py_SIZE(self) += n;
1327 self->allocated = Py_SIZE(self);
1328 for (i = 0; i < n; i++) {
1329 PyObject *v = PyList_GetItem(list, i);
1330 if ((*self->ob_descr->setitem)(self,
1331 Py_SIZE(self) - n + i, v) != 0) {
1332 Py_SIZE(self) -= n;
1333 PyMem_RESIZE(item, char,
1334 Py_SIZE(self) * itemsize);
1335 self->ob_item = item;
1336 self->allocated = Py_SIZE(self);
1337 return NULL;
1341 Py_INCREF(Py_None);
1342 return Py_None;
1345 PyDoc_STRVAR(fromlist_doc,
1346 "fromlist(list)\n\
1348 Append items to array from list.");
1351 static PyObject *
1352 array_tolist(arrayobject *self, PyObject *unused)
1354 PyObject *list = PyList_New(Py_SIZE(self));
1355 Py_ssize_t i;
1357 if (list == NULL)
1358 return NULL;
1359 for (i = 0; i < Py_SIZE(self); i++) {
1360 PyObject *v = getarrayitem((PyObject *)self, i);
1361 if (v == NULL) {
1362 Py_DECREF(list);
1363 return NULL;
1365 PyList_SetItem(list, i, v);
1367 return list;
1370 PyDoc_STRVAR(tolist_doc,
1371 "tolist() -> list\n\
1373 Convert array to an ordinary list with the same items.");
1376 static PyObject *
1377 array_fromstring(arrayobject *self, PyObject *args)
1379 char *str;
1380 Py_ssize_t n;
1381 int itemsize = self->ob_descr->itemsize;
1382 if (!PyArg_ParseTuple(args, "s#:fromstring", &str, &n))
1383 return NULL;
1384 if (n % itemsize != 0) {
1385 PyErr_SetString(PyExc_ValueError,
1386 "string length not a multiple of item size");
1387 return NULL;
1389 n = n / itemsize;
1390 if (n > 0) {
1391 char *item = self->ob_item;
1392 PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1393 if (item == NULL) {
1394 PyErr_NoMemory();
1395 return NULL;
1397 self->ob_item = item;
1398 Py_SIZE(self) += n;
1399 self->allocated = Py_SIZE(self);
1400 memcpy(item + (Py_SIZE(self) - n) * itemsize,
1401 str, itemsize*n);
1403 Py_INCREF(Py_None);
1404 return Py_None;
1407 PyDoc_STRVAR(fromstring_doc,
1408 "fromstring(string)\n\
1410 Appends items from the string, interpreting it as an array of machine\n\
1411 values,as if it had been read from a file using the fromfile() method).");
1414 static PyObject *
1415 array_tostring(arrayobject *self, PyObject *unused)
1417 return PyString_FromStringAndSize(self->ob_item,
1418 Py_SIZE(self) * self->ob_descr->itemsize);
1421 PyDoc_STRVAR(tostring_doc,
1422 "tostring() -> string\n\
1424 Convert the array to an array of machine values and return the string\n\
1425 representation.");
1429 #ifdef Py_USING_UNICODE
1430 static PyObject *
1431 array_fromunicode(arrayobject *self, PyObject *args)
1433 Py_UNICODE *ustr;
1434 Py_ssize_t n;
1436 if (!PyArg_ParseTuple(args, "u#:fromunicode", &ustr, &n))
1437 return NULL;
1438 if (self->ob_descr->typecode != 'u') {
1439 PyErr_SetString(PyExc_ValueError,
1440 "fromunicode() may only be called on "
1441 "type 'u' arrays");
1442 return NULL;
1444 if (n > 0) {
1445 Py_UNICODE *item = (Py_UNICODE *) self->ob_item;
1446 PyMem_RESIZE(item, Py_UNICODE, Py_SIZE(self) + n);
1447 if (item == NULL) {
1448 PyErr_NoMemory();
1449 return NULL;
1451 self->ob_item = (char *) item;
1452 Py_SIZE(self) += n;
1453 self->allocated = Py_SIZE(self);
1454 memcpy(item + Py_SIZE(self) - n,
1455 ustr, n * sizeof(Py_UNICODE));
1458 Py_INCREF(Py_None);
1459 return Py_None;
1462 PyDoc_STRVAR(fromunicode_doc,
1463 "fromunicode(ustr)\n\
1465 Extends this array with data from the unicode string ustr.\n\
1466 The array must be a type 'u' array; otherwise a ValueError\n\
1467 is raised. Use array.fromstring(ustr.decode(...)) to\n\
1468 append Unicode data to an array of some other type.");
1471 static PyObject *
1472 array_tounicode(arrayobject *self, PyObject *unused)
1474 if (self->ob_descr->typecode != 'u') {
1475 PyErr_SetString(PyExc_ValueError,
1476 "tounicode() may only be called on type 'u' arrays");
1477 return NULL;
1479 return PyUnicode_FromUnicode((Py_UNICODE *) self->ob_item, Py_SIZE(self));
1482 PyDoc_STRVAR(tounicode_doc,
1483 "tounicode() -> unicode\n\
1485 Convert the array to a unicode string. The array must be\n\
1486 a type 'u' array; otherwise a ValueError is raised. Use\n\
1487 array.tostring().decode() to obtain a unicode string from\n\
1488 an array of some other type.");
1490 #endif /* Py_USING_UNICODE */
1493 static PyObject *
1494 array_get_typecode(arrayobject *a, void *closure)
1496 char tc = a->ob_descr->typecode;
1497 return PyString_FromStringAndSize(&tc, 1);
1500 static PyObject *
1501 array_get_itemsize(arrayobject *a, void *closure)
1503 return PyInt_FromLong((long)a->ob_descr->itemsize);
1506 static PyGetSetDef array_getsets [] = {
1507 {"typecode", (getter) array_get_typecode, NULL,
1508 "the typecode character used to create the array"},
1509 {"itemsize", (getter) array_get_itemsize, NULL,
1510 "the size, in bytes, of one array item"},
1511 {NULL}
1514 PyMethodDef array_methods[] = {
1515 {"append", (PyCFunction)array_append, METH_O,
1516 append_doc},
1517 {"buffer_info", (PyCFunction)array_buffer_info, METH_NOARGS,
1518 buffer_info_doc},
1519 {"byteswap", (PyCFunction)array_byteswap, METH_NOARGS,
1520 byteswap_doc},
1521 {"__copy__", (PyCFunction)array_copy, METH_NOARGS,
1522 copy_doc},
1523 {"count", (PyCFunction)array_count, METH_O,
1524 count_doc},
1525 {"__deepcopy__",(PyCFunction)array_copy, METH_O,
1526 copy_doc},
1527 {"extend", (PyCFunction)array_extend, METH_O,
1528 extend_doc},
1529 {"fromfile", (PyCFunction)array_fromfile, METH_VARARGS,
1530 fromfile_doc},
1531 {"fromlist", (PyCFunction)array_fromlist, METH_O,
1532 fromlist_doc},
1533 {"fromstring", (PyCFunction)array_fromstring, METH_VARARGS,
1534 fromstring_doc},
1535 #ifdef Py_USING_UNICODE
1536 {"fromunicode", (PyCFunction)array_fromunicode, METH_VARARGS,
1537 fromunicode_doc},
1538 #endif
1539 {"index", (PyCFunction)array_index, METH_O,
1540 index_doc},
1541 {"insert", (PyCFunction)array_insert, METH_VARARGS,
1542 insert_doc},
1543 {"pop", (PyCFunction)array_pop, METH_VARARGS,
1544 pop_doc},
1545 {"read", (PyCFunction)array_fromfile_as_read, METH_VARARGS,
1546 fromfile_doc},
1547 {"__reduce__", (PyCFunction)array_reduce, METH_NOARGS,
1548 array_doc},
1549 {"remove", (PyCFunction)array_remove, METH_O,
1550 remove_doc},
1551 {"reverse", (PyCFunction)array_reverse, METH_NOARGS,
1552 reverse_doc},
1553 /* {"sort", (PyCFunction)array_sort, METH_VARARGS,
1554 sort_doc},*/
1555 {"tofile", (PyCFunction)array_tofile, METH_O,
1556 tofile_doc},
1557 {"tolist", (PyCFunction)array_tolist, METH_NOARGS,
1558 tolist_doc},
1559 {"tostring", (PyCFunction)array_tostring, METH_NOARGS,
1560 tostring_doc},
1561 #ifdef Py_USING_UNICODE
1562 {"tounicode", (PyCFunction)array_tounicode, METH_NOARGS,
1563 tounicode_doc},
1564 #endif
1565 {"write", (PyCFunction)array_tofile_as_write, METH_O,
1566 tofile_doc},
1567 {NULL, NULL} /* sentinel */
1570 static PyObject *
1571 array_repr(arrayobject *a)
1573 char buf[256], typecode;
1574 PyObject *s, *t, *v = NULL;
1575 Py_ssize_t len;
1577 len = Py_SIZE(a);
1578 typecode = a->ob_descr->typecode;
1579 if (len == 0) {
1580 PyOS_snprintf(buf, sizeof(buf), "array('%c')", typecode);
1581 return PyString_FromString(buf);
1584 if (typecode == 'c')
1585 v = array_tostring(a, NULL);
1586 #ifdef Py_USING_UNICODE
1587 else if (typecode == 'u')
1588 v = array_tounicode(a, NULL);
1589 #endif
1590 else
1591 v = array_tolist(a, NULL);
1592 t = PyObject_Repr(v);
1593 Py_XDECREF(v);
1595 PyOS_snprintf(buf, sizeof(buf), "array('%c', ", typecode);
1596 s = PyString_FromString(buf);
1597 PyString_ConcatAndDel(&s, t);
1598 PyString_ConcatAndDel(&s, PyString_FromString(")"));
1599 return s;
1602 static PyObject*
1603 array_subscr(arrayobject* self, PyObject* item)
1605 if (PyIndex_Check(item)) {
1606 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1607 if (i==-1 && PyErr_Occurred()) {
1608 return NULL;
1610 if (i < 0)
1611 i += Py_SIZE(self);
1612 return array_item(self, i);
1614 else if (PySlice_Check(item)) {
1615 Py_ssize_t start, stop, step, slicelength, cur, i;
1616 PyObject* result;
1617 arrayobject* ar;
1618 int itemsize = self->ob_descr->itemsize;
1620 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
1621 &start, &stop, &step, &slicelength) < 0) {
1622 return NULL;
1625 if (slicelength <= 0) {
1626 return newarrayobject(&Arraytype, 0, self->ob_descr);
1628 else if (step == 1) {
1629 PyObject *result = newarrayobject(&Arraytype,
1630 slicelength, self->ob_descr);
1631 if (result == NULL)
1632 return NULL;
1633 memcpy(((arrayobject *)result)->ob_item,
1634 self->ob_item + start * itemsize,
1635 slicelength * itemsize);
1636 return result;
1638 else {
1639 result = newarrayobject(&Arraytype, slicelength, self->ob_descr);
1640 if (!result) return NULL;
1642 ar = (arrayobject*)result;
1644 for (cur = start, i = 0; i < slicelength;
1645 cur += step, i++) {
1646 memcpy(ar->ob_item + i*itemsize,
1647 self->ob_item + cur*itemsize,
1648 itemsize);
1651 return result;
1654 else {
1655 PyErr_SetString(PyExc_TypeError,
1656 "array indices must be integers");
1657 return NULL;
1661 static int
1662 array_ass_subscr(arrayobject* self, PyObject* item, PyObject* value)
1664 Py_ssize_t start, stop, step, slicelength, needed;
1665 arrayobject* other;
1666 int itemsize;
1668 if (PyIndex_Check(item)) {
1669 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1671 if (i == -1 && PyErr_Occurred())
1672 return -1;
1673 if (i < 0)
1674 i += Py_SIZE(self);
1675 if (i < 0 || i >= Py_SIZE(self)) {
1676 PyErr_SetString(PyExc_IndexError,
1677 "array assignment index out of range");
1678 return -1;
1680 if (value == NULL) {
1681 /* Fall through to slice assignment */
1682 start = i;
1683 stop = i + 1;
1684 step = 1;
1685 slicelength = 1;
1687 else
1688 return (*self->ob_descr->setitem)(self, i, value);
1690 else if (PySlice_Check(item)) {
1691 if (PySlice_GetIndicesEx((PySliceObject *)item,
1692 Py_SIZE(self), &start, &stop,
1693 &step, &slicelength) < 0) {
1694 return -1;
1697 else {
1698 PyErr_SetString(PyExc_TypeError,
1699 "array indices must be integer");
1700 return -1;
1702 if (value == NULL) {
1703 other = NULL;
1704 needed = 0;
1706 else if (array_Check(value)) {
1707 other = (arrayobject *)value;
1708 needed = Py_SIZE(other);
1709 if (self == other) {
1710 /* Special case "self[i:j] = self" -- copy self first */
1711 int ret;
1712 value = array_slice(other, 0, needed);
1713 if (value == NULL)
1714 return -1;
1715 ret = array_ass_subscr(self, item, value);
1716 Py_DECREF(value);
1717 return ret;
1719 if (other->ob_descr != self->ob_descr) {
1720 PyErr_BadArgument();
1721 return -1;
1724 else {
1725 PyErr_Format(PyExc_TypeError,
1726 "can only assign array (not \"%.200s\") to array slice",
1727 Py_TYPE(value)->tp_name);
1728 return -1;
1730 itemsize = self->ob_descr->itemsize;
1731 /* for 'a[2:1] = ...', the insertion point is 'start', not 'stop' */
1732 if ((step > 0 && stop < start) ||
1733 (step < 0 && stop > start))
1734 stop = start;
1735 if (step == 1) {
1736 if (slicelength > needed) {
1737 memmove(self->ob_item + (start + needed) * itemsize,
1738 self->ob_item + stop * itemsize,
1739 (Py_SIZE(self) - stop) * itemsize);
1740 if (array_resize(self, Py_SIZE(self) +
1741 needed - slicelength) < 0)
1742 return -1;
1744 else if (slicelength < needed) {
1745 if (array_resize(self, Py_SIZE(self) +
1746 needed - slicelength) < 0)
1747 return -1;
1748 memmove(self->ob_item + (start + needed) * itemsize,
1749 self->ob_item + stop * itemsize,
1750 (Py_SIZE(self) - start - needed) * itemsize);
1752 if (needed > 0)
1753 memcpy(self->ob_item + start * itemsize,
1754 other->ob_item, needed * itemsize);
1755 return 0;
1757 else if (needed == 0) {
1758 /* Delete slice */
1759 Py_ssize_t cur, i;
1761 if (step < 0) {
1762 stop = start + 1;
1763 start = stop + step * (slicelength - 1) - 1;
1764 step = -step;
1766 for (cur = start, i = 0; i < slicelength;
1767 cur += step, i++) {
1768 Py_ssize_t lim = step - 1;
1770 if (cur + step >= Py_SIZE(self))
1771 lim = Py_SIZE(self) - cur - 1;
1772 memmove(self->ob_item + (cur - i) * itemsize,
1773 self->ob_item + (cur + 1) * itemsize,
1774 lim * itemsize);
1776 cur = start + slicelength * step;
1777 if (cur < Py_SIZE(self)) {
1778 memmove(self->ob_item + (cur-slicelength) * itemsize,
1779 self->ob_item + cur * itemsize,
1780 (Py_SIZE(self) - cur) * itemsize);
1782 if (array_resize(self, Py_SIZE(self) - slicelength) < 0)
1783 return -1;
1784 return 0;
1786 else {
1787 Py_ssize_t cur, i;
1789 if (needed != slicelength) {
1790 PyErr_Format(PyExc_ValueError,
1791 "attempt to assign array of size %zd "
1792 "to extended slice of size %zd",
1793 needed, slicelength);
1794 return -1;
1796 for (cur = start, i = 0; i < slicelength;
1797 cur += step, i++) {
1798 memcpy(self->ob_item + cur * itemsize,
1799 other->ob_item + i * itemsize,
1800 itemsize);
1802 return 0;
1806 static PyMappingMethods array_as_mapping = {
1807 (lenfunc)array_length,
1808 (binaryfunc)array_subscr,
1809 (objobjargproc)array_ass_subscr
1812 static const void *emptybuf = "";
1814 static Py_ssize_t
1815 array_buffer_getreadbuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1817 if ( index != 0 ) {
1818 PyErr_SetString(PyExc_SystemError,
1819 "Accessing non-existent array segment");
1820 return -1;
1822 *ptr = (void *)self->ob_item;
1823 if (*ptr == NULL)
1824 *ptr = emptybuf;
1825 return Py_SIZE(self)*self->ob_descr->itemsize;
1828 static Py_ssize_t
1829 array_buffer_getwritebuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1831 if ( index != 0 ) {
1832 PyErr_SetString(PyExc_SystemError,
1833 "Accessing non-existent array segment");
1834 return -1;
1836 *ptr = (void *)self->ob_item;
1837 if (*ptr == NULL)
1838 *ptr = emptybuf;
1839 return Py_SIZE(self)*self->ob_descr->itemsize;
1842 static Py_ssize_t
1843 array_buffer_getsegcount(arrayobject *self, Py_ssize_t *lenp)
1845 if ( lenp )
1846 *lenp = Py_SIZE(self)*self->ob_descr->itemsize;
1847 return 1;
1850 static PySequenceMethods array_as_sequence = {
1851 (lenfunc)array_length, /*sq_length*/
1852 (binaryfunc)array_concat, /*sq_concat*/
1853 (ssizeargfunc)array_repeat, /*sq_repeat*/
1854 (ssizeargfunc)array_item, /*sq_item*/
1855 (ssizessizeargfunc)array_slice, /*sq_slice*/
1856 (ssizeobjargproc)array_ass_item, /*sq_ass_item*/
1857 (ssizessizeobjargproc)array_ass_slice, /*sq_ass_slice*/
1858 (objobjproc)array_contains, /*sq_contains*/
1859 (binaryfunc)array_inplace_concat, /*sq_inplace_concat*/
1860 (ssizeargfunc)array_inplace_repeat /*sq_inplace_repeat*/
1863 static PyBufferProcs array_as_buffer = {
1864 (readbufferproc)array_buffer_getreadbuf,
1865 (writebufferproc)array_buffer_getwritebuf,
1866 (segcountproc)array_buffer_getsegcount,
1867 NULL,
1870 static PyObject *
1871 array_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1873 char c;
1874 PyObject *initial = NULL, *it = NULL;
1875 struct arraydescr *descr;
1877 if (type == &Arraytype && !_PyArg_NoKeywords("array.array()", kwds))
1878 return NULL;
1880 if (!PyArg_ParseTuple(args, "c|O:array", &c, &initial))
1881 return NULL;
1883 if (!(initial == NULL || PyList_Check(initial)
1884 || PyString_Check(initial) || PyTuple_Check(initial)
1885 || (c == 'u' && PyUnicode_Check(initial)))) {
1886 it = PyObject_GetIter(initial);
1887 if (it == NULL)
1888 return NULL;
1889 /* We set initial to NULL so that the subsequent code
1890 will create an empty array of the appropriate type
1891 and afterwards we can use array_iter_extend to populate
1892 the array.
1894 initial = NULL;
1896 for (descr = descriptors; descr->typecode != '\0'; descr++) {
1897 if (descr->typecode == c) {
1898 PyObject *a;
1899 Py_ssize_t len;
1901 if (initial == NULL || !(PyList_Check(initial)
1902 || PyTuple_Check(initial)))
1903 len = 0;
1904 else
1905 len = PySequence_Size(initial);
1907 a = newarrayobject(type, len, descr);
1908 if (a == NULL)
1909 return NULL;
1911 if (len > 0) {
1912 Py_ssize_t i;
1913 for (i = 0; i < len; i++) {
1914 PyObject *v =
1915 PySequence_GetItem(initial, i);
1916 if (v == NULL) {
1917 Py_DECREF(a);
1918 return NULL;
1920 if (setarrayitem(a, i, v) != 0) {
1921 Py_DECREF(v);
1922 Py_DECREF(a);
1923 return NULL;
1925 Py_DECREF(v);
1927 } else if (initial != NULL && PyString_Check(initial)) {
1928 PyObject *t_initial, *v;
1929 t_initial = PyTuple_Pack(1, initial);
1930 if (t_initial == NULL) {
1931 Py_DECREF(a);
1932 return NULL;
1934 v = array_fromstring((arrayobject *)a,
1935 t_initial);
1936 Py_DECREF(t_initial);
1937 if (v == NULL) {
1938 Py_DECREF(a);
1939 return NULL;
1941 Py_DECREF(v);
1942 #ifdef Py_USING_UNICODE
1943 } else if (initial != NULL && PyUnicode_Check(initial)) {
1944 Py_ssize_t n = PyUnicode_GET_DATA_SIZE(initial);
1945 if (n > 0) {
1946 arrayobject *self = (arrayobject *)a;
1947 char *item = self->ob_item;
1948 item = (char *)PyMem_Realloc(item, n);
1949 if (item == NULL) {
1950 PyErr_NoMemory();
1951 Py_DECREF(a);
1952 return NULL;
1954 self->ob_item = item;
1955 Py_SIZE(self) = n / sizeof(Py_UNICODE);
1956 memcpy(item, PyUnicode_AS_DATA(initial), n);
1957 self->allocated = Py_SIZE(self);
1959 #endif
1961 if (it != NULL) {
1962 if (array_iter_extend((arrayobject *)a, it) == -1) {
1963 Py_DECREF(it);
1964 Py_DECREF(a);
1965 return NULL;
1967 Py_DECREF(it);
1969 return a;
1972 PyErr_SetString(PyExc_ValueError,
1973 "bad typecode (must be c, b, B, u, h, H, i, I, l, L, f or d)");
1974 return NULL;
1978 PyDoc_STRVAR(module_doc,
1979 "This module defines an object type which can efficiently represent\n\
1980 an array of basic values: characters, integers, floating point\n\
1981 numbers. Arrays are sequence types and behave very much like lists,\n\
1982 except that the type of objects stored in them is constrained. The\n\
1983 type is specified at object creation time by using a type code, which\n\
1984 is a single character. The following type codes are defined:\n\
1986 Type code C Type Minimum size in bytes \n\
1987 'c' character 1 \n\
1988 'b' signed integer 1 \n\
1989 'B' unsigned integer 1 \n\
1990 'u' Unicode character 2 \n\
1991 'h' signed integer 2 \n\
1992 'H' unsigned integer 2 \n\
1993 'i' signed integer 2 \n\
1994 'I' unsigned integer 2 \n\
1995 'l' signed integer 4 \n\
1996 'L' unsigned integer 4 \n\
1997 'f' floating point 4 \n\
1998 'd' floating point 8 \n\
2000 The constructor is:\n\
2002 array(typecode [, initializer]) -- create a new array\n\
2005 PyDoc_STRVAR(arraytype_doc,
2006 "array(typecode [, initializer]) -> array\n\
2008 Return a new array whose items are restricted by typecode, and\n\
2009 initialized from the optional initializer value, which must be a list,\n\
2010 string. or iterable over elements of the appropriate type.\n\
2012 Arrays represent basic values and behave very much like lists, except\n\
2013 the type of objects stored in them is constrained.\n\
2015 Methods:\n\
2017 append() -- append a new item to the end of the array\n\
2018 buffer_info() -- return information giving the current memory info\n\
2019 byteswap() -- byteswap all the items of the array\n\
2020 count() -- return number of occurences of an object\n\
2021 extend() -- extend array by appending multiple elements from an iterable\n\
2022 fromfile() -- read items from a file object\n\
2023 fromlist() -- append items from the list\n\
2024 fromstring() -- append items from the string\n\
2025 index() -- return index of first occurence of an object\n\
2026 insert() -- insert a new item into the array at a provided position\n\
2027 pop() -- remove and return item (default last)\n\
2028 read() -- DEPRECATED, use fromfile()\n\
2029 remove() -- remove first occurence of an object\n\
2030 reverse() -- reverse the order of the items in the array\n\
2031 tofile() -- write all items to a file object\n\
2032 tolist() -- return the array converted to an ordinary list\n\
2033 tostring() -- return the array converted to a string\n\
2034 write() -- DEPRECATED, use tofile()\n\
2036 Attributes:\n\
2038 typecode -- the typecode character used to create the array\n\
2039 itemsize -- the length in bytes of one array item\n\
2042 static PyObject *array_iter(arrayobject *ao);
2044 static PyTypeObject Arraytype = {
2045 PyVarObject_HEAD_INIT(NULL, 0)
2046 "array.array",
2047 sizeof(arrayobject),
2049 (destructor)array_dealloc, /* tp_dealloc */
2050 0, /* tp_print */
2051 0, /* tp_getattr */
2052 0, /* tp_setattr */
2053 0, /* tp_compare */
2054 (reprfunc)array_repr, /* tp_repr */
2055 0, /* tp_as_number*/
2056 &array_as_sequence, /* tp_as_sequence*/
2057 &array_as_mapping, /* tp_as_mapping*/
2058 0, /* tp_hash */
2059 0, /* tp_call */
2060 0, /* tp_str */
2061 PyObject_GenericGetAttr, /* tp_getattro */
2062 0, /* tp_setattro */
2063 &array_as_buffer, /* tp_as_buffer*/
2064 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
2065 arraytype_doc, /* tp_doc */
2066 0, /* tp_traverse */
2067 0, /* tp_clear */
2068 array_richcompare, /* tp_richcompare */
2069 offsetof(arrayobject, weakreflist), /* tp_weaklistoffset */
2070 (getiterfunc)array_iter, /* tp_iter */
2071 0, /* tp_iternext */
2072 array_methods, /* tp_methods */
2073 0, /* tp_members */
2074 array_getsets, /* tp_getset */
2075 0, /* tp_base */
2076 0, /* tp_dict */
2077 0, /* tp_descr_get */
2078 0, /* tp_descr_set */
2079 0, /* tp_dictoffset */
2080 0, /* tp_init */
2081 PyType_GenericAlloc, /* tp_alloc */
2082 array_new, /* tp_new */
2083 PyObject_Del, /* tp_free */
2087 /*********************** Array Iterator **************************/
2089 typedef struct {
2090 PyObject_HEAD
2091 Py_ssize_t index;
2092 arrayobject *ao;
2093 PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
2094 } arrayiterobject;
2096 static PyTypeObject PyArrayIter_Type;
2098 #define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)
2100 static PyObject *
2101 array_iter(arrayobject *ao)
2103 arrayiterobject *it;
2105 if (!array_Check(ao)) {
2106 PyErr_BadInternalCall();
2107 return NULL;
2110 it = PyObject_GC_New(arrayiterobject, &PyArrayIter_Type);
2111 if (it == NULL)
2112 return NULL;
2114 Py_INCREF(ao);
2115 it->ao = ao;
2116 it->index = 0;
2117 it->getitem = ao->ob_descr->getitem;
2118 PyObject_GC_Track(it);
2119 return (PyObject *)it;
2122 static PyObject *
2123 arrayiter_next(arrayiterobject *it)
2125 assert(PyArrayIter_Check(it));
2126 if (it->index < Py_SIZE(it->ao))
2127 return (*it->getitem)(it->ao, it->index++);
2128 return NULL;
2131 static void
2132 arrayiter_dealloc(arrayiterobject *it)
2134 PyObject_GC_UnTrack(it);
2135 Py_XDECREF(it->ao);
2136 PyObject_GC_Del(it);
2139 static int
2140 arrayiter_traverse(arrayiterobject *it, visitproc visit, void *arg)
2142 Py_VISIT(it->ao);
2143 return 0;
2146 static PyTypeObject PyArrayIter_Type = {
2147 PyVarObject_HEAD_INIT(NULL, 0)
2148 "arrayiterator", /* tp_name */
2149 sizeof(arrayiterobject), /* tp_basicsize */
2150 0, /* tp_itemsize */
2151 /* methods */
2152 (destructor)arrayiter_dealloc, /* tp_dealloc */
2153 0, /* tp_print */
2154 0, /* tp_getattr */
2155 0, /* tp_setattr */
2156 0, /* tp_compare */
2157 0, /* tp_repr */
2158 0, /* tp_as_number */
2159 0, /* tp_as_sequence */
2160 0, /* tp_as_mapping */
2161 0, /* tp_hash */
2162 0, /* tp_call */
2163 0, /* tp_str */
2164 PyObject_GenericGetAttr, /* tp_getattro */
2165 0, /* tp_setattro */
2166 0, /* tp_as_buffer */
2167 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2168 0, /* tp_doc */
2169 (traverseproc)arrayiter_traverse, /* tp_traverse */
2170 0, /* tp_clear */
2171 0, /* tp_richcompare */
2172 0, /* tp_weaklistoffset */
2173 PyObject_SelfIter, /* tp_iter */
2174 (iternextfunc)arrayiter_next, /* tp_iternext */
2175 0, /* tp_methods */
2179 /*********************** Install Module **************************/
2181 /* No functions in array module. */
2182 static PyMethodDef a_methods[] = {
2183 {NULL, NULL, 0, NULL} /* Sentinel */
2187 PyMODINIT_FUNC
2188 initarray(void)
2190 PyObject *m;
2192 Arraytype.ob_type = &PyType_Type;
2193 PyArrayIter_Type.ob_type = &PyType_Type;
2194 m = Py_InitModule3("array", a_methods, module_doc);
2195 if (m == NULL)
2196 return;
2198 Py_INCREF((PyObject *)&Arraytype);
2199 PyModule_AddObject(m, "ArrayType", (PyObject *)&Arraytype);
2200 Py_INCREF((PyObject *)&Arraytype);
2201 PyModule_AddObject(m, "array", (PyObject *)&Arraytype);
2202 /* No need to check the error here, the caller will do that */