• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* Array object implementation */
2 
3 /* An array is a uniform list -- all items have the same type.
4    The item type is restricted to simple C types like int or float */
5 
6 #define PY_SSIZE_T_CLEAN
7 #include "Python.h"
8 #include "structmember.h"
9 
10 #ifdef STDC_HEADERS
11 #include <stddef.h>
12 #else /* !STDC_HEADERS */
13 #ifdef HAVE_SYS_TYPES_H
14 #include <sys/types.h>          /* For size_t */
15 #endif /* HAVE_SYS_TYPES_H */
16 #endif /* !STDC_HEADERS */
17 
18 /*[clinic input]
19 module array
20 [clinic start generated code]*/
21 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=7d1b8d7f5958fd83]*/
22 
23 struct arrayobject; /* Forward */
24 
25 /* All possible arraydescr values are defined in the vector "descriptors"
26  * below.  That's defined later because the appropriate get and set
27  * functions aren't visible yet.
28  */
29 struct arraydescr {
30     char typecode;
31     int itemsize;
32     PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
33     int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
34     int (*compareitems)(const void *, const void *, Py_ssize_t);
35     const char *formats;
36     int is_integer_type;
37     int is_signed;
38 };
39 
40 typedef struct arrayobject {
41     PyObject_VAR_HEAD
42     char *ob_item;
43     Py_ssize_t allocated;
44     const struct arraydescr *ob_descr;
45     PyObject *weakreflist; /* List of weak references */
46     int ob_exports;  /* Number of exported buffers */
47 } arrayobject;
48 
49 static PyTypeObject Arraytype;
50 
51 typedef struct {
52     PyObject_HEAD
53     Py_ssize_t index;
54     arrayobject *ao;
55     PyObject* (*getitem)(struct arrayobject *, Py_ssize_t);
56 } arrayiterobject;
57 
58 static PyTypeObject PyArrayIter_Type;
59 
60 #define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)
61 
62 enum machine_format_code {
63     UNKNOWN_FORMAT = -1,
64     /* UNKNOWN_FORMAT is used to indicate that the machine format for an
65      * array type code cannot be interpreted. When this occurs, a list of
66      * Python objects is used to represent the content of the array
67      * instead of using the memory content of the array directly. In that
68      * case, the array_reconstructor mechanism is bypassed completely, and
69      * the standard array constructor is used instead.
70      *
71      * This is will most likely occur when the machine doesn't use IEEE
72      * floating-point numbers.
73      */
74 
75     UNSIGNED_INT8 = 0,
76     SIGNED_INT8 = 1,
77     UNSIGNED_INT16_LE = 2,
78     UNSIGNED_INT16_BE = 3,
79     SIGNED_INT16_LE = 4,
80     SIGNED_INT16_BE = 5,
81     UNSIGNED_INT32_LE = 6,
82     UNSIGNED_INT32_BE = 7,
83     SIGNED_INT32_LE = 8,
84     SIGNED_INT32_BE = 9,
85     UNSIGNED_INT64_LE = 10,
86     UNSIGNED_INT64_BE = 11,
87     SIGNED_INT64_LE = 12,
88     SIGNED_INT64_BE = 13,
89     IEEE_754_FLOAT_LE = 14,
90     IEEE_754_FLOAT_BE = 15,
91     IEEE_754_DOUBLE_LE = 16,
92     IEEE_754_DOUBLE_BE = 17,
93     UTF16_LE = 18,
94     UTF16_BE = 19,
95     UTF32_LE = 20,
96     UTF32_BE = 21
97 };
98 #define MACHINE_FORMAT_CODE_MIN 0
99 #define MACHINE_FORMAT_CODE_MAX 21
100 
101 
102 /*
103  * Must come after arrayobject, arrayiterobject,
104  * and enum machine_code_type definitions.
105  */
106 #include "clinic/arraymodule.c.h"
107 
108 #define array_Check(op) PyObject_TypeCheck(op, &Arraytype)
109 #define array_CheckExact(op) (Py_TYPE(op) == &Arraytype)
110 
111 static int
array_resize(arrayobject * self,Py_ssize_t newsize)112 array_resize(arrayobject *self, Py_ssize_t newsize)
113 {
114     char *items;
115     size_t _new_size;
116 
117     if (self->ob_exports > 0 && newsize != Py_SIZE(self)) {
118         PyErr_SetString(PyExc_BufferError,
119             "cannot resize an array that is exporting buffers");
120         return -1;
121     }
122 
123     /* Bypass realloc() when a previous overallocation is large enough
124        to accommodate the newsize.  If the newsize is 16 smaller than the
125        current size, then proceed with the realloc() to shrink the array.
126     */
127 
128     if (self->allocated >= newsize &&
129         Py_SIZE(self) < newsize + 16 &&
130         self->ob_item != NULL) {
131         Py_SIZE(self) = newsize;
132         return 0;
133     }
134 
135     if (newsize == 0) {
136         PyMem_FREE(self->ob_item);
137         self->ob_item = NULL;
138         Py_SIZE(self) = 0;
139         self->allocated = 0;
140         return 0;
141     }
142 
143     /* This over-allocates proportional to the array size, making room
144      * for additional growth.  The over-allocation is mild, but is
145      * enough to give linear-time amortized behavior over a long
146      * sequence of appends() in the presence of a poorly-performing
147      * system realloc().
148      * The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
149      * Note, the pattern starts out the same as for lists but then
150      * grows at a smaller rate so that larger arrays only overallocate
151      * by about 1/16th -- this is done because arrays are presumed to be more
152      * memory critical.
153      */
154 
155     _new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
156     items = self->ob_item;
157     /* XXX The following multiplication and division does not optimize away
158        like it does for lists since the size is not known at compile time */
159     if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
160         PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
161     else
162         items = NULL;
163     if (items == NULL) {
164         PyErr_NoMemory();
165         return -1;
166     }
167     self->ob_item = items;
168     Py_SIZE(self) = newsize;
169     self->allocated = _new_size;
170     return 0;
171 }
172 
173 /****************************************************************************
174 Get and Set functions for each type.
175 A Get function takes an arrayobject* and an integer index, returning the
176 array value at that index wrapped in an appropriate PyObject*.
177 A Set function takes an arrayobject, integer index, and PyObject*; sets
178 the array value at that index to the raw C data extracted from the PyObject*,
179 and returns 0 if successful, else nonzero on failure (PyObject* not of an
180 appropriate type or value).
181 Note that the basic Get and Set functions do NOT check that the index is
182 in bounds; that's the responsibility of the caller.
183 ****************************************************************************/
184 
185 static PyObject *
b_getitem(arrayobject * ap,Py_ssize_t i)186 b_getitem(arrayobject *ap, Py_ssize_t i)
187 {
188     long x = ((char *)ap->ob_item)[i];
189     if (x >= 128)
190         x -= 256;
191     return PyLong_FromLong(x);
192 }
193 
194 static int
b_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)195 b_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
196 {
197     short x;
198     /* PyArg_Parse's 'b' formatter is for an unsigned char, therefore
199        must use the next size up that is signed ('h') and manually do
200        the overflow checking */
201     if (!PyArg_Parse(v, "h;array item must be integer", &x))
202         return -1;
203     else if (x < -128) {
204         PyErr_SetString(PyExc_OverflowError,
205             "signed char is less than minimum");
206         return -1;
207     }
208     else if (x > 127) {
209         PyErr_SetString(PyExc_OverflowError,
210             "signed char is greater than maximum");
211         return -1;
212     }
213     if (i >= 0)
214         ((char *)ap->ob_item)[i] = (char)x;
215     return 0;
216 }
217 
218 static PyObject *
BB_getitem(arrayobject * ap,Py_ssize_t i)219 BB_getitem(arrayobject *ap, Py_ssize_t i)
220 {
221     long x = ((unsigned char *)ap->ob_item)[i];
222     return PyLong_FromLong(x);
223 }
224 
225 static int
BB_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)226 BB_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
227 {
228     unsigned char x;
229     /* 'B' == unsigned char, maps to PyArg_Parse's 'b' formatter */
230     if (!PyArg_Parse(v, "b;array item must be integer", &x))
231         return -1;
232     if (i >= 0)
233         ((char *)ap->ob_item)[i] = x;
234     return 0;
235 }
236 
237 static PyObject *
u_getitem(arrayobject * ap,Py_ssize_t i)238 u_getitem(arrayobject *ap, Py_ssize_t i)
239 {
240     return PyUnicode_FromOrdinal(((Py_UNICODE *) ap->ob_item)[i]);
241 }
242 
243 static int
u_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)244 u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
245 {
246     Py_UNICODE *p;
247     Py_ssize_t len;
248 
249     if (!PyArg_Parse(v, "u#;array item must be unicode character", &p, &len))
250         return -1;
251     if (len != 1) {
252         PyErr_SetString(PyExc_TypeError,
253                         "array item must be unicode character");
254         return -1;
255     }
256     if (i >= 0)
257         ((Py_UNICODE *)ap->ob_item)[i] = p[0];
258     return 0;
259 }
260 
261 
262 static PyObject *
h_getitem(arrayobject * ap,Py_ssize_t i)263 h_getitem(arrayobject *ap, Py_ssize_t i)
264 {
265     return PyLong_FromLong((long) ((short *)ap->ob_item)[i]);
266 }
267 
268 
269 static int
h_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)270 h_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
271 {
272     short x;
273     /* 'h' == signed short, maps to PyArg_Parse's 'h' formatter */
274     if (!PyArg_Parse(v, "h;array item must be integer", &x))
275         return -1;
276     if (i >= 0)
277                  ((short *)ap->ob_item)[i] = x;
278     return 0;
279 }
280 
281 static PyObject *
HH_getitem(arrayobject * ap,Py_ssize_t i)282 HH_getitem(arrayobject *ap, Py_ssize_t i)
283 {
284     return PyLong_FromLong((long) ((unsigned short *)ap->ob_item)[i]);
285 }
286 
287 static int
HH_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)288 HH_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
289 {
290     int x;
291     /* PyArg_Parse's 'h' formatter is for a signed short, therefore
292        must use the next size up and manually do the overflow checking */
293     if (!PyArg_Parse(v, "i;array item must be integer", &x))
294         return -1;
295     else if (x < 0) {
296         PyErr_SetString(PyExc_OverflowError,
297             "unsigned short is less than minimum");
298         return -1;
299     }
300     else if (x > USHRT_MAX) {
301         PyErr_SetString(PyExc_OverflowError,
302             "unsigned short is greater than maximum");
303         return -1;
304     }
305     if (i >= 0)
306         ((short *)ap->ob_item)[i] = (short)x;
307     return 0;
308 }
309 
310 static PyObject *
i_getitem(arrayobject * ap,Py_ssize_t i)311 i_getitem(arrayobject *ap, Py_ssize_t i)
312 {
313     return PyLong_FromLong((long) ((int *)ap->ob_item)[i]);
314 }
315 
316 static int
i_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)317 i_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
318 {
319     int x;
320     /* 'i' == signed int, maps to PyArg_Parse's 'i' formatter */
321     if (!PyArg_Parse(v, "i;array item must be integer", &x))
322         return -1;
323     if (i >= 0)
324                  ((int *)ap->ob_item)[i] = x;
325     return 0;
326 }
327 
328 static PyObject *
II_getitem(arrayobject * ap,Py_ssize_t i)329 II_getitem(arrayobject *ap, Py_ssize_t i)
330 {
331     return PyLong_FromUnsignedLong(
332         (unsigned long) ((unsigned int *)ap->ob_item)[i]);
333 }
334 
335 static PyObject *
get_int_unless_float(PyObject * v)336 get_int_unless_float(PyObject *v)
337 {
338     if (PyFloat_Check(v)) {
339         PyErr_SetString(PyExc_TypeError,
340                         "array item must be integer");
341         return NULL;
342     }
343     return (PyObject *)_PyLong_FromNbInt(v);
344 }
345 
346 static int
II_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)347 II_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
348 {
349     unsigned long x;
350     int do_decref = 0; /* if nb_int was called */
351 
352     if (!PyLong_Check(v)) {
353         v = get_int_unless_float(v);
354         if (NULL == v) {
355             return -1;
356         }
357         do_decref = 1;
358     }
359     x = PyLong_AsUnsignedLong(v);
360     if (x == (unsigned long)-1 && PyErr_Occurred()) {
361         if (do_decref) {
362             Py_DECREF(v);
363         }
364         return -1;
365     }
366     if (x > UINT_MAX) {
367         PyErr_SetString(PyExc_OverflowError,
368                         "unsigned int is greater than maximum");
369         if (do_decref) {
370             Py_DECREF(v);
371         }
372         return -1;
373     }
374     if (i >= 0)
375         ((unsigned int *)ap->ob_item)[i] = (unsigned int)x;
376 
377     if (do_decref) {
378         Py_DECREF(v);
379     }
380     return 0;
381 }
382 
383 static PyObject *
l_getitem(arrayobject * ap,Py_ssize_t i)384 l_getitem(arrayobject *ap, Py_ssize_t i)
385 {
386     return PyLong_FromLong(((long *)ap->ob_item)[i]);
387 }
388 
389 static int
l_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)390 l_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
391 {
392     long x;
393     if (!PyArg_Parse(v, "l;array item must be integer", &x))
394         return -1;
395     if (i >= 0)
396                  ((long *)ap->ob_item)[i] = x;
397     return 0;
398 }
399 
400 static PyObject *
LL_getitem(arrayobject * ap,Py_ssize_t i)401 LL_getitem(arrayobject *ap, Py_ssize_t i)
402 {
403     return PyLong_FromUnsignedLong(((unsigned long *)ap->ob_item)[i]);
404 }
405 
406 static int
LL_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)407 LL_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
408 {
409     unsigned long x;
410     int do_decref = 0; /* if nb_int was called */
411 
412     if (!PyLong_Check(v)) {
413         v = get_int_unless_float(v);
414         if (NULL == v) {
415             return -1;
416         }
417         do_decref = 1;
418     }
419     x = PyLong_AsUnsignedLong(v);
420     if (x == (unsigned long)-1 && PyErr_Occurred()) {
421         if (do_decref) {
422             Py_DECREF(v);
423         }
424         return -1;
425     }
426     if (i >= 0)
427         ((unsigned long *)ap->ob_item)[i] = x;
428 
429     if (do_decref) {
430         Py_DECREF(v);
431     }
432     return 0;
433 }
434 
435 static PyObject *
q_getitem(arrayobject * ap,Py_ssize_t i)436 q_getitem(arrayobject *ap, Py_ssize_t i)
437 {
438     return PyLong_FromLongLong(((long long *)ap->ob_item)[i]);
439 }
440 
441 static int
q_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)442 q_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
443 {
444     long long x;
445     if (!PyArg_Parse(v, "L;array item must be integer", &x))
446         return -1;
447     if (i >= 0)
448         ((long long *)ap->ob_item)[i] = x;
449     return 0;
450 }
451 
452 static PyObject *
QQ_getitem(arrayobject * ap,Py_ssize_t i)453 QQ_getitem(arrayobject *ap, Py_ssize_t i)
454 {
455     return PyLong_FromUnsignedLongLong(
456         ((unsigned long long *)ap->ob_item)[i]);
457 }
458 
459 static int
QQ_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)460 QQ_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
461 {
462     unsigned long long x;
463     int do_decref = 0; /* if nb_int was called */
464 
465     if (!PyLong_Check(v)) {
466         v = get_int_unless_float(v);
467         if (NULL == v) {
468             return -1;
469         }
470         do_decref = 1;
471     }
472     x = PyLong_AsUnsignedLongLong(v);
473     if (x == (unsigned long long)-1 && PyErr_Occurred()) {
474         if (do_decref) {
475             Py_DECREF(v);
476         }
477         return -1;
478     }
479     if (i >= 0)
480         ((unsigned long long *)ap->ob_item)[i] = x;
481 
482     if (do_decref) {
483         Py_DECREF(v);
484     }
485     return 0;
486 }
487 
488 static PyObject *
f_getitem(arrayobject * ap,Py_ssize_t i)489 f_getitem(arrayobject *ap, Py_ssize_t i)
490 {
491     return PyFloat_FromDouble((double) ((float *)ap->ob_item)[i]);
492 }
493 
494 static int
f_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)495 f_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
496 {
497     float x;
498     if (!PyArg_Parse(v, "f;array item must be float", &x))
499         return -1;
500     if (i >= 0)
501                  ((float *)ap->ob_item)[i] = x;
502     return 0;
503 }
504 
505 static PyObject *
d_getitem(arrayobject * ap,Py_ssize_t i)506 d_getitem(arrayobject *ap, Py_ssize_t i)
507 {
508     return PyFloat_FromDouble(((double *)ap->ob_item)[i]);
509 }
510 
511 static int
d_setitem(arrayobject * ap,Py_ssize_t i,PyObject * v)512 d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
513 {
514     double x;
515     if (!PyArg_Parse(v, "d;array item must be float", &x))
516         return -1;
517     if (i >= 0)
518                  ((double *)ap->ob_item)[i] = x;
519     return 0;
520 }
521 
522 #define DEFINE_COMPAREITEMS(code, type) \
523     static int \
524     code##_compareitems(const void *lhs, const void *rhs, Py_ssize_t length) \
525     { \
526         const type *a = lhs, *b = rhs; \
527         for (Py_ssize_t i = 0; i < length; ++i) \
528             if (a[i] != b[i]) \
529                 return a[i] < b[i] ? -1 : 1; \
530         return 0; \
531     }
532 
533 DEFINE_COMPAREITEMS(b, signed char)
534 DEFINE_COMPAREITEMS(BB, unsigned char)
535 DEFINE_COMPAREITEMS(u, Py_UNICODE)
536 DEFINE_COMPAREITEMS(h, short)
537 DEFINE_COMPAREITEMS(HH, unsigned short)
538 DEFINE_COMPAREITEMS(i, int)
539 DEFINE_COMPAREITEMS(II, unsigned int)
540 DEFINE_COMPAREITEMS(l, long)
541 DEFINE_COMPAREITEMS(LL, unsigned long)
542 DEFINE_COMPAREITEMS(q, long long)
543 DEFINE_COMPAREITEMS(QQ, unsigned long long)
544 
545 /* Description of types.
546  *
547  * Don't forget to update typecode_to_mformat_code() if you add a new
548  * typecode.
549  */
550 static const struct arraydescr descriptors[] = {
551     {'b', 1, b_getitem, b_setitem, b_compareitems, "b", 1, 1},
552     {'B', 1, BB_getitem, BB_setitem, BB_compareitems, "B", 1, 0},
553     {'u', sizeof(Py_UNICODE), u_getitem, u_setitem, u_compareitems, "u", 0, 0},
554     {'h', sizeof(short), h_getitem, h_setitem, h_compareitems, "h", 1, 1},
555     {'H', sizeof(short), HH_getitem, HH_setitem, HH_compareitems, "H", 1, 0},
556     {'i', sizeof(int), i_getitem, i_setitem, i_compareitems, "i", 1, 1},
557     {'I', sizeof(int), II_getitem, II_setitem, II_compareitems, "I", 1, 0},
558     {'l', sizeof(long), l_getitem, l_setitem, l_compareitems, "l", 1, 1},
559     {'L', sizeof(long), LL_getitem, LL_setitem, LL_compareitems, "L", 1, 0},
560     {'q', sizeof(long long), q_getitem, q_setitem, q_compareitems, "q", 1, 1},
561     {'Q', sizeof(long long), QQ_getitem, QQ_setitem, QQ_compareitems, "Q", 1, 0},
562     {'f', sizeof(float), f_getitem, f_setitem, NULL, "f", 0, 0},
563     {'d', sizeof(double), d_getitem, d_setitem, NULL, "d", 0, 0},
564     {'\0', 0, 0, 0, 0, 0, 0} /* Sentinel */
565 };
566 
567 /****************************************************************************
568 Implementations of array object methods.
569 ****************************************************************************/
570 /*[clinic input]
571 class array.array "arrayobject *" "&Arraytype"
572 [clinic start generated code]*/
573 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=ad43d37e942a8854]*/
574 
575 static PyObject *
newarrayobject(PyTypeObject * type,Py_ssize_t size,const struct arraydescr * descr)576 newarrayobject(PyTypeObject *type, Py_ssize_t size, const struct arraydescr *descr)
577 {
578     arrayobject *op;
579     size_t nbytes;
580 
581     if (size < 0) {
582         PyErr_BadInternalCall();
583         return NULL;
584     }
585 
586     /* Check for overflow */
587     if (size > PY_SSIZE_T_MAX / descr->itemsize) {
588         return PyErr_NoMemory();
589     }
590     nbytes = size * descr->itemsize;
591     op = (arrayobject *) type->tp_alloc(type, 0);
592     if (op == NULL) {
593         return NULL;
594     }
595     op->ob_descr = descr;
596     op->allocated = size;
597     op->weakreflist = NULL;
598     Py_SIZE(op) = size;
599     if (size <= 0) {
600         op->ob_item = NULL;
601     }
602     else {
603         op->ob_item = PyMem_NEW(char, nbytes);
604         if (op->ob_item == NULL) {
605             Py_DECREF(op);
606             return PyErr_NoMemory();
607         }
608     }
609     op->ob_exports = 0;
610     return (PyObject *) op;
611 }
612 
613 static PyObject *
getarrayitem(PyObject * op,Py_ssize_t i)614 getarrayitem(PyObject *op, Py_ssize_t i)
615 {
616     arrayobject *ap;
617     assert(array_Check(op));
618     ap = (arrayobject *)op;
619     assert(i>=0 && i<Py_SIZE(ap));
620     return (*ap->ob_descr->getitem)(ap, i);
621 }
622 
623 static int
ins1(arrayobject * self,Py_ssize_t where,PyObject * v)624 ins1(arrayobject *self, Py_ssize_t where, PyObject *v)
625 {
626     char *items;
627     Py_ssize_t n = Py_SIZE(self);
628     if (v == NULL) {
629         PyErr_BadInternalCall();
630         return -1;
631     }
632     if ((*self->ob_descr->setitem)(self, -1, v) < 0)
633         return -1;
634 
635     if (array_resize(self, n+1) == -1)
636         return -1;
637     items = self->ob_item;
638     if (where < 0) {
639         where += n;
640         if (where < 0)
641             where = 0;
642     }
643     if (where > n)
644         where = n;
645     /* appends don't need to call memmove() */
646     if (where != n)
647         memmove(items + (where+1)*self->ob_descr->itemsize,
648             items + where*self->ob_descr->itemsize,
649             (n-where)*self->ob_descr->itemsize);
650     return (*self->ob_descr->setitem)(self, where, v);
651 }
652 
653 /* Methods */
654 
655 static void
array_dealloc(arrayobject * op)656 array_dealloc(arrayobject *op)
657 {
658     if (op->weakreflist != NULL)
659         PyObject_ClearWeakRefs((PyObject *) op);
660     if (op->ob_item != NULL)
661         PyMem_DEL(op->ob_item);
662     Py_TYPE(op)->tp_free((PyObject *)op);
663 }
664 
665 static PyObject *
array_richcompare(PyObject * v,PyObject * w,int op)666 array_richcompare(PyObject *v, PyObject *w, int op)
667 {
668     arrayobject *va, *wa;
669     PyObject *vi = NULL;
670     PyObject *wi = NULL;
671     Py_ssize_t i, k;
672     PyObject *res;
673 
674     if (!array_Check(v) || !array_Check(w))
675         Py_RETURN_NOTIMPLEMENTED;
676 
677     va = (arrayobject *)v;
678     wa = (arrayobject *)w;
679 
680     if (Py_SIZE(va) != Py_SIZE(wa) && (op == Py_EQ || op == Py_NE)) {
681         /* Shortcut: if the lengths differ, the arrays differ */
682         if (op == Py_EQ)
683             res = Py_False;
684         else
685             res = Py_True;
686         Py_INCREF(res);
687         return res;
688     }
689 
690     if (va->ob_descr == wa->ob_descr && va->ob_descr->compareitems != NULL) {
691         /* Fast path:
692            arrays with same types can have their buffers compared directly */
693         Py_ssize_t common_length = Py_MIN(Py_SIZE(va), Py_SIZE(wa));
694         int result = va->ob_descr->compareitems(va->ob_item, wa->ob_item,
695                                                 common_length);
696         if (result == 0)
697             goto compare_sizes;
698 
699         int cmp;
700         switch (op) {
701         case Py_LT: cmp = result < 0; break;
702         case Py_LE: cmp = result <= 0; break;
703         case Py_EQ: cmp = result == 0; break;
704         case Py_NE: cmp = result != 0; break;
705         case Py_GT: cmp = result > 0; break;
706         case Py_GE: cmp = result >= 0; break;
707         default: return NULL; /* cannot happen */
708         }
709         PyObject *res = cmp ? Py_True : Py_False;
710         Py_INCREF(res);
711         return res;
712     }
713 
714 
715     /* Search for the first index where items are different */
716     k = 1;
717     for (i = 0; i < Py_SIZE(va) && i < Py_SIZE(wa); i++) {
718         vi = getarrayitem(v, i);
719         wi = getarrayitem(w, i);
720         if (vi == NULL || wi == NULL) {
721             Py_XDECREF(vi);
722             Py_XDECREF(wi);
723             return NULL;
724         }
725         k = PyObject_RichCompareBool(vi, wi, Py_EQ);
726         if (k == 0)
727             break; /* Keeping vi and wi alive! */
728         Py_DECREF(vi);
729         Py_DECREF(wi);
730         if (k < 0)
731             return NULL;
732     }
733 
734     if (k) {
735         /* No more items to compare -- compare sizes */
736         compare_sizes: ;
737         Py_ssize_t vs = Py_SIZE(va);
738         Py_ssize_t ws = Py_SIZE(wa);
739         int cmp;
740         switch (op) {
741         case Py_LT: cmp = vs <  ws; break;
742         case Py_LE: cmp = vs <= ws; break;
743         /* If the lengths were not equal,
744            the earlier fast-path check would have caught that. */
745         case Py_EQ: assert(vs == ws); cmp = 1; break;
746         case Py_NE: assert(vs == ws); cmp = 0; break;
747         case Py_GT: cmp = vs >  ws; break;
748         case Py_GE: cmp = vs >= ws; break;
749         default: return NULL; /* cannot happen */
750         }
751         if (cmp)
752             res = Py_True;
753         else
754             res = Py_False;
755         Py_INCREF(res);
756         return res;
757     }
758 
759     /* We have an item that differs.  First, shortcuts for EQ/NE */
760     if (op == Py_EQ) {
761         Py_INCREF(Py_False);
762         res = Py_False;
763     }
764     else if (op == Py_NE) {
765         Py_INCREF(Py_True);
766         res = Py_True;
767     }
768     else {
769         /* Compare the final item again using the proper operator */
770         res = PyObject_RichCompare(vi, wi, op);
771     }
772     Py_DECREF(vi);
773     Py_DECREF(wi);
774     return res;
775 }
776 
777 static Py_ssize_t
array_length(arrayobject * a)778 array_length(arrayobject *a)
779 {
780     return Py_SIZE(a);
781 }
782 
783 static PyObject *
array_item(arrayobject * a,Py_ssize_t i)784 array_item(arrayobject *a, Py_ssize_t i)
785 {
786     if (i < 0 || i >= Py_SIZE(a)) {
787         PyErr_SetString(PyExc_IndexError, "array index out of range");
788         return NULL;
789     }
790     return getarrayitem((PyObject *)a, i);
791 }
792 
793 static PyObject *
array_slice(arrayobject * a,Py_ssize_t ilow,Py_ssize_t ihigh)794 array_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
795 {
796     arrayobject *np;
797     if (ilow < 0)
798         ilow = 0;
799     else if (ilow > Py_SIZE(a))
800         ilow = Py_SIZE(a);
801     if (ihigh < 0)
802         ihigh = 0;
803     if (ihigh < ilow)
804         ihigh = ilow;
805     else if (ihigh > Py_SIZE(a))
806         ihigh = Py_SIZE(a);
807     np = (arrayobject *) newarrayobject(&Arraytype, ihigh - ilow, a->ob_descr);
808     if (np == NULL)
809         return NULL;
810     if (ihigh > ilow) {
811         memcpy(np->ob_item, a->ob_item + ilow * a->ob_descr->itemsize,
812                (ihigh-ilow) * a->ob_descr->itemsize);
813     }
814     return (PyObject *)np;
815 }
816 
817 
818 /*[clinic input]
819 array.array.__copy__
820 
821 Return a copy of the array.
822 [clinic start generated code]*/
823 
824 static PyObject *
array_array___copy___impl(arrayobject * self)825 array_array___copy___impl(arrayobject *self)
826 /*[clinic end generated code: output=dec7c3f925d9619e input=ad1ee5b086965f09]*/
827 {
828     return array_slice(self, 0, Py_SIZE(self));
829 }
830 
831 /*[clinic input]
832 array.array.__deepcopy__
833 
834     unused: object
835     /
836 
837 Return a copy of the array.
838 [clinic start generated code]*/
839 
840 static PyObject *
array_array___deepcopy__(arrayobject * self,PyObject * unused)841 array_array___deepcopy__(arrayobject *self, PyObject *unused)
842 /*[clinic end generated code: output=1ec748d8e14a9faa input=2405ecb4933748c4]*/
843 {
844     return array_array___copy___impl(self);
845 }
846 
847 static PyObject *
array_concat(arrayobject * a,PyObject * bb)848 array_concat(arrayobject *a, PyObject *bb)
849 {
850     Py_ssize_t size;
851     arrayobject *np;
852     if (!array_Check(bb)) {
853         PyErr_Format(PyExc_TypeError,
854              "can only append array (not \"%.200s\") to array",
855                  Py_TYPE(bb)->tp_name);
856         return NULL;
857     }
858 #define b ((arrayobject *)bb)
859     if (a->ob_descr != b->ob_descr) {
860         PyErr_BadArgument();
861         return NULL;
862     }
863     if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b)) {
864         return PyErr_NoMemory();
865     }
866     size = Py_SIZE(a) + Py_SIZE(b);
867     np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
868     if (np == NULL) {
869         return NULL;
870     }
871     if (Py_SIZE(a) > 0) {
872         memcpy(np->ob_item, a->ob_item, Py_SIZE(a)*a->ob_descr->itemsize);
873     }
874     if (Py_SIZE(b) > 0) {
875         memcpy(np->ob_item + Py_SIZE(a)*a->ob_descr->itemsize,
876                b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
877     }
878     return (PyObject *)np;
879 #undef b
880 }
881 
882 static PyObject *
array_repeat(arrayobject * a,Py_ssize_t n)883 array_repeat(arrayobject *a, Py_ssize_t n)
884 {
885     Py_ssize_t size;
886     arrayobject *np;
887     Py_ssize_t oldbytes, newbytes;
888     if (n < 0)
889         n = 0;
890     if ((Py_SIZE(a) != 0) && (n > PY_SSIZE_T_MAX / Py_SIZE(a))) {
891         return PyErr_NoMemory();
892     }
893     size = Py_SIZE(a) * n;
894     np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
895     if (np == NULL)
896         return NULL;
897     if (size == 0)
898         return (PyObject *)np;
899     oldbytes = Py_SIZE(a) * a->ob_descr->itemsize;
900     newbytes = oldbytes * n;
901     /* this follows the code in unicode_repeat */
902     if (oldbytes == 1) {
903         memset(np->ob_item, a->ob_item[0], newbytes);
904     } else {
905         Py_ssize_t done = oldbytes;
906         memcpy(np->ob_item, a->ob_item, oldbytes);
907         while (done < newbytes) {
908             Py_ssize_t ncopy = (done <= newbytes-done) ? done : newbytes-done;
909             memcpy(np->ob_item+done, np->ob_item, ncopy);
910             done += ncopy;
911         }
912     }
913     return (PyObject *)np;
914 }
915 
916 static int
array_del_slice(arrayobject * a,Py_ssize_t ilow,Py_ssize_t ihigh)917 array_del_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
918 {
919     char *item;
920     Py_ssize_t d; /* Change in size */
921     if (ilow < 0)
922         ilow = 0;
923     else if (ilow > Py_SIZE(a))
924         ilow = Py_SIZE(a);
925     if (ihigh < 0)
926         ihigh = 0;
927     if (ihigh < ilow)
928         ihigh = ilow;
929     else if (ihigh > Py_SIZE(a))
930         ihigh = Py_SIZE(a);
931     item = a->ob_item;
932     d = ihigh-ilow;
933     /* Issue #4509: If the array has exported buffers and the slice
934        assignment would change the size of the array, fail early to make
935        sure we don't modify it. */
936     if (d != 0 && a->ob_exports > 0) {
937         PyErr_SetString(PyExc_BufferError,
938             "cannot resize an array that is exporting buffers");
939         return -1;
940     }
941     if (d > 0) { /* Delete d items */
942         memmove(item + (ihigh-d)*a->ob_descr->itemsize,
943             item + ihigh*a->ob_descr->itemsize,
944             (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
945         if (array_resize(a, Py_SIZE(a) - d) == -1)
946             return -1;
947     }
948     return 0;
949 }
950 
951 static int
array_ass_item(arrayobject * a,Py_ssize_t i,PyObject * v)952 array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)
953 {
954     if (i < 0 || i >= Py_SIZE(a)) {
955         PyErr_SetString(PyExc_IndexError,
956                          "array assignment index out of range");
957         return -1;
958     }
959     if (v == NULL)
960         return array_del_slice(a, i, i+1);
961     return (*a->ob_descr->setitem)(a, i, v);
962 }
963 
964 static int
setarrayitem(PyObject * a,Py_ssize_t i,PyObject * v)965 setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)
966 {
967     assert(array_Check(a));
968     return array_ass_item((arrayobject *)a, i, v);
969 }
970 
971 static int
array_iter_extend(arrayobject * self,PyObject * bb)972 array_iter_extend(arrayobject *self, PyObject *bb)
973 {
974     PyObject *it, *v;
975 
976     it = PyObject_GetIter(bb);
977     if (it == NULL)
978         return -1;
979 
980     while ((v = PyIter_Next(it)) != NULL) {
981         if (ins1(self, Py_SIZE(self), v) != 0) {
982             Py_DECREF(v);
983             Py_DECREF(it);
984             return -1;
985         }
986         Py_DECREF(v);
987     }
988     Py_DECREF(it);
989     if (PyErr_Occurred())
990         return -1;
991     return 0;
992 }
993 
994 static int
array_do_extend(arrayobject * self,PyObject * bb)995 array_do_extend(arrayobject *self, PyObject *bb)
996 {
997     Py_ssize_t size, oldsize, bbsize;
998 
999     if (!array_Check(bb))
1000         return array_iter_extend(self, bb);
1001 #define b ((arrayobject *)bb)
1002     if (self->ob_descr != b->ob_descr) {
1003         PyErr_SetString(PyExc_TypeError,
1004                      "can only extend with array of same kind");
1005         return -1;
1006     }
1007     if ((Py_SIZE(self) > PY_SSIZE_T_MAX - Py_SIZE(b)) ||
1008         ((Py_SIZE(self) + Py_SIZE(b)) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {
1009         PyErr_NoMemory();
1010         return -1;
1011     }
1012     oldsize = Py_SIZE(self);
1013     /* Get the size of bb before resizing the array since bb could be self. */
1014     bbsize = Py_SIZE(bb);
1015     size = oldsize + Py_SIZE(b);
1016     if (array_resize(self, size) == -1)
1017         return -1;
1018     if (bbsize > 0) {
1019         memcpy(self->ob_item + oldsize * self->ob_descr->itemsize,
1020             b->ob_item, bbsize * b->ob_descr->itemsize);
1021     }
1022 
1023     return 0;
1024 #undef b
1025 }
1026 
1027 static PyObject *
array_inplace_concat(arrayobject * self,PyObject * bb)1028 array_inplace_concat(arrayobject *self, PyObject *bb)
1029 {
1030     if (!array_Check(bb)) {
1031         PyErr_Format(PyExc_TypeError,
1032             "can only extend array with array (not \"%.200s\")",
1033             Py_TYPE(bb)->tp_name);
1034         return NULL;
1035     }
1036     if (array_do_extend(self, bb) == -1)
1037         return NULL;
1038     Py_INCREF(self);
1039     return (PyObject *)self;
1040 }
1041 
1042 static PyObject *
array_inplace_repeat(arrayobject * self,Py_ssize_t n)1043 array_inplace_repeat(arrayobject *self, Py_ssize_t n)
1044 {
1045     char *items, *p;
1046     Py_ssize_t size, i;
1047 
1048     if (Py_SIZE(self) > 0) {
1049         if (n < 0)
1050             n = 0;
1051         if ((self->ob_descr->itemsize != 0) &&
1052             (Py_SIZE(self) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {
1053             return PyErr_NoMemory();
1054         }
1055         size = Py_SIZE(self) * self->ob_descr->itemsize;
1056         if (n > 0 && size > PY_SSIZE_T_MAX / n) {
1057             return PyErr_NoMemory();
1058         }
1059         if (array_resize(self, n * Py_SIZE(self)) == -1)
1060             return NULL;
1061         items = p = self->ob_item;
1062         for (i = 1; i < n; i++) {
1063             p += size;
1064             memcpy(p, items, size);
1065         }
1066     }
1067     Py_INCREF(self);
1068     return (PyObject *)self;
1069 }
1070 
1071 
1072 static PyObject *
ins(arrayobject * self,Py_ssize_t where,PyObject * v)1073 ins(arrayobject *self, Py_ssize_t where, PyObject *v)
1074 {
1075     if (ins1(self, where, v) != 0)
1076         return NULL;
1077     Py_RETURN_NONE;
1078 }
1079 
1080 /*[clinic input]
1081 array.array.count
1082 
1083     v: object
1084     /
1085 
1086 Return number of occurrences of v in the array.
1087 [clinic start generated code]*/
1088 
1089 static PyObject *
array_array_count(arrayobject * self,PyObject * v)1090 array_array_count(arrayobject *self, PyObject *v)
1091 /*[clinic end generated code: output=3dd3624bf7135a3a input=d9bce9d65e39d1f5]*/
1092 {
1093     Py_ssize_t count = 0;
1094     Py_ssize_t i;
1095 
1096     for (i = 0; i < Py_SIZE(self); i++) {
1097         PyObject *selfi;
1098         int cmp;
1099 
1100         selfi = getarrayitem((PyObject *)self, i);
1101         if (selfi == NULL)
1102             return NULL;
1103         cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
1104         Py_DECREF(selfi);
1105         if (cmp > 0)
1106             count++;
1107         else if (cmp < 0)
1108             return NULL;
1109     }
1110     return PyLong_FromSsize_t(count);
1111 }
1112 
1113 
1114 /*[clinic input]
1115 array.array.index
1116 
1117     v: object
1118     /
1119 
1120 Return index of first occurrence of v in the array.
1121 [clinic start generated code]*/
1122 
1123 static PyObject *
array_array_index(arrayobject * self,PyObject * v)1124 array_array_index(arrayobject *self, PyObject *v)
1125 /*[clinic end generated code: output=d48498d325602167 input=cf619898c6649d08]*/
1126 {
1127     Py_ssize_t i;
1128 
1129     for (i = 0; i < Py_SIZE(self); i++) {
1130         PyObject *selfi;
1131         int cmp;
1132 
1133         selfi = getarrayitem((PyObject *)self, i);
1134         if (selfi == NULL)
1135             return NULL;
1136         cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
1137         Py_DECREF(selfi);
1138         if (cmp > 0) {
1139             return PyLong_FromLong((long)i);
1140         }
1141         else if (cmp < 0)
1142             return NULL;
1143     }
1144     PyErr_SetString(PyExc_ValueError, "array.index(x): x not in array");
1145     return NULL;
1146 }
1147 
1148 static int
array_contains(arrayobject * self,PyObject * v)1149 array_contains(arrayobject *self, PyObject *v)
1150 {
1151     Py_ssize_t i;
1152     int cmp;
1153 
1154     for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(self); i++) {
1155         PyObject *selfi = getarrayitem((PyObject *)self, i);
1156         if (selfi == NULL)
1157             return -1;
1158         cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
1159         Py_DECREF(selfi);
1160     }
1161     return cmp;
1162 }
1163 
1164 /*[clinic input]
1165 array.array.remove
1166 
1167     v: object
1168     /
1169 
1170 Remove the first occurrence of v in the array.
1171 [clinic start generated code]*/
1172 
1173 static PyObject *
array_array_remove(arrayobject * self,PyObject * v)1174 array_array_remove(arrayobject *self, PyObject *v)
1175 /*[clinic end generated code: output=bef06be9fdf9dceb input=0b1e5aed25590027]*/
1176 {
1177     int i;
1178 
1179     for (i = 0; i < Py_SIZE(self); i++) {
1180         PyObject *selfi;
1181         int cmp;
1182 
1183         selfi = getarrayitem((PyObject *)self,i);
1184         if (selfi == NULL)
1185             return NULL;
1186         cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
1187         Py_DECREF(selfi);
1188         if (cmp > 0) {
1189             if (array_del_slice(self, i, i+1) != 0)
1190                 return NULL;
1191             Py_RETURN_NONE;
1192         }
1193         else if (cmp < 0)
1194             return NULL;
1195     }
1196     PyErr_SetString(PyExc_ValueError, "array.remove(x): x not in array");
1197     return NULL;
1198 }
1199 
1200 /*[clinic input]
1201 array.array.pop
1202 
1203     i: Py_ssize_t = -1
1204     /
1205 
1206 Return the i-th element and delete it from the array.
1207 
1208 i defaults to -1.
1209 [clinic start generated code]*/
1210 
1211 static PyObject *
array_array_pop_impl(arrayobject * self,Py_ssize_t i)1212 array_array_pop_impl(arrayobject *self, Py_ssize_t i)
1213 /*[clinic end generated code: output=bc1f0c54fe5308e4 input=8e5feb4c1a11cd44]*/
1214 {
1215     PyObject *v;
1216 
1217     if (Py_SIZE(self) == 0) {
1218         /* Special-case most common failure cause */
1219         PyErr_SetString(PyExc_IndexError, "pop from empty array");
1220         return NULL;
1221     }
1222     if (i < 0)
1223         i += Py_SIZE(self);
1224     if (i < 0 || i >= Py_SIZE(self)) {
1225         PyErr_SetString(PyExc_IndexError, "pop index out of range");
1226         return NULL;
1227     }
1228     v = getarrayitem((PyObject *)self, i);
1229     if (v == NULL)
1230         return NULL;
1231     if (array_del_slice(self, i, i+1) != 0) {
1232         Py_DECREF(v);
1233         return NULL;
1234     }
1235     return v;
1236 }
1237 
1238 /*[clinic input]
1239 array.array.extend
1240 
1241     bb: object
1242     /
1243 
1244 Append items to the end of the array.
1245 [clinic start generated code]*/
1246 
1247 static PyObject *
array_array_extend(arrayobject * self,PyObject * bb)1248 array_array_extend(arrayobject *self, PyObject *bb)
1249 /*[clinic end generated code: output=bbddbc8e8bef871d input=43be86aba5c31e44]*/
1250 {
1251     if (array_do_extend(self, bb) == -1)
1252         return NULL;
1253     Py_RETURN_NONE;
1254 }
1255 
1256 /*[clinic input]
1257 array.array.insert
1258 
1259     i: Py_ssize_t
1260     v: object
1261     /
1262 
1263 Insert a new item v into the array before position i.
1264 [clinic start generated code]*/
1265 
1266 static PyObject *
array_array_insert_impl(arrayobject * self,Py_ssize_t i,PyObject * v)1267 array_array_insert_impl(arrayobject *self, Py_ssize_t i, PyObject *v)
1268 /*[clinic end generated code: output=5a3648e278348564 input=5577d1b4383e9313]*/
1269 {
1270     return ins(self, i, v);
1271 }
1272 
1273 /*[clinic input]
1274 array.array.buffer_info
1275 
1276 Return a tuple (address, length) giving the current memory address and the length in items of the buffer used to hold array's contents.
1277 
1278 The length should be multiplied by the itemsize attribute to calculate
1279 the buffer length in bytes.
1280 [clinic start generated code]*/
1281 
1282 static PyObject *
array_array_buffer_info_impl(arrayobject * self)1283 array_array_buffer_info_impl(arrayobject *self)
1284 /*[clinic end generated code: output=9b2a4ec3ae7e98e7 input=a58bae5c6e1ac6a6]*/
1285 {
1286     PyObject *retval = NULL, *v;
1287 
1288     retval = PyTuple_New(2);
1289     if (!retval)
1290         return NULL;
1291 
1292     v = PyLong_FromVoidPtr(self->ob_item);
1293     if (v == NULL) {
1294         Py_DECREF(retval);
1295         return NULL;
1296     }
1297     PyTuple_SET_ITEM(retval, 0, v);
1298 
1299     v = PyLong_FromSsize_t(Py_SIZE(self));
1300     if (v == NULL) {
1301         Py_DECREF(retval);
1302         return NULL;
1303     }
1304     PyTuple_SET_ITEM(retval, 1, v);
1305 
1306     return retval;
1307 }
1308 
1309 /*[clinic input]
1310 array.array.append
1311 
1312     v: object
1313     /
1314 
1315 Append new value v to the end of the array.
1316 [clinic start generated code]*/
1317 
1318 static PyObject *
array_array_append(arrayobject * self,PyObject * v)1319 array_array_append(arrayobject *self, PyObject *v)
1320 /*[clinic end generated code: output=745a0669bf8db0e2 input=0b98d9d78e78f0fa]*/
1321 {
1322     return ins(self, Py_SIZE(self), v);
1323 }
1324 
1325 /*[clinic input]
1326 array.array.byteswap
1327 
1328 Byteswap all items of the array.
1329 
1330 If the items in the array are not 1, 2, 4, or 8 bytes in size, RuntimeError is
1331 raised.
1332 [clinic start generated code]*/
1333 
1334 static PyObject *
array_array_byteswap_impl(arrayobject * self)1335 array_array_byteswap_impl(arrayobject *self)
1336 /*[clinic end generated code: output=5f8236cbdf0d90b5 input=6a85591b950a0186]*/
1337 {
1338     char *p;
1339     Py_ssize_t i;
1340 
1341     switch (self->ob_descr->itemsize) {
1342     case 1:
1343         break;
1344     case 2:
1345         for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 2) {
1346             char p0 = p[0];
1347             p[0] = p[1];
1348             p[1] = p0;
1349         }
1350         break;
1351     case 4:
1352         for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 4) {
1353             char p0 = p[0];
1354             char p1 = p[1];
1355             p[0] = p[3];
1356             p[1] = p[2];
1357             p[2] = p1;
1358             p[3] = p0;
1359         }
1360         break;
1361     case 8:
1362         for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 8) {
1363             char p0 = p[0];
1364             char p1 = p[1];
1365             char p2 = p[2];
1366             char p3 = p[3];
1367             p[0] = p[7];
1368             p[1] = p[6];
1369             p[2] = p[5];
1370             p[3] = p[4];
1371             p[4] = p3;
1372             p[5] = p2;
1373             p[6] = p1;
1374             p[7] = p0;
1375         }
1376         break;
1377     default:
1378         PyErr_SetString(PyExc_RuntimeError,
1379                    "don't know how to byteswap this array type");
1380         return NULL;
1381     }
1382     Py_RETURN_NONE;
1383 }
1384 
1385 /*[clinic input]
1386 array.array.reverse
1387 
1388 Reverse the order of the items in the array.
1389 [clinic start generated code]*/
1390 
1391 static PyObject *
array_array_reverse_impl(arrayobject * self)1392 array_array_reverse_impl(arrayobject *self)
1393 /*[clinic end generated code: output=c04868b36f6f4089 input=cd904f01b27d966a]*/
1394 {
1395     Py_ssize_t itemsize = self->ob_descr->itemsize;
1396     char *p, *q;
1397     /* little buffer to hold items while swapping */
1398     char tmp[256];      /* 8 is probably enough -- but why skimp */
1399     assert((size_t)itemsize <= sizeof(tmp));
1400 
1401     if (Py_SIZE(self) > 1) {
1402         for (p = self->ob_item,
1403              q = self->ob_item + (Py_SIZE(self) - 1)*itemsize;
1404              p < q;
1405              p += itemsize, q -= itemsize) {
1406             /* memory areas guaranteed disjoint, so memcpy
1407              * is safe (& memmove may be slower).
1408              */
1409             memcpy(tmp, p, itemsize);
1410             memcpy(p, q, itemsize);
1411             memcpy(q, tmp, itemsize);
1412         }
1413     }
1414 
1415     Py_RETURN_NONE;
1416 }
1417 
1418 /*[clinic input]
1419 array.array.fromfile
1420 
1421     f: object
1422     n: Py_ssize_t
1423     /
1424 
1425 Read n objects from the file object f and append them to the end of the array.
1426 [clinic start generated code]*/
1427 
1428 static PyObject *
array_array_fromfile_impl(arrayobject * self,PyObject * f,Py_ssize_t n)1429 array_array_fromfile_impl(arrayobject *self, PyObject *f, Py_ssize_t n)
1430 /*[clinic end generated code: output=ec9f600e10f53510 input=e188afe8e58adf40]*/
1431 {
1432     PyObject *b, *res;
1433     Py_ssize_t itemsize = self->ob_descr->itemsize;
1434     Py_ssize_t nbytes;
1435     _Py_IDENTIFIER(read);
1436     int not_enough_bytes;
1437 
1438     if (n < 0) {
1439         PyErr_SetString(PyExc_ValueError, "negative count");
1440         return NULL;
1441     }
1442     if (n > PY_SSIZE_T_MAX / itemsize) {
1443         PyErr_NoMemory();
1444         return NULL;
1445     }
1446     nbytes = n * itemsize;
1447 
1448     b = _PyObject_CallMethodId(f, &PyId_read, "n", nbytes);
1449     if (b == NULL)
1450         return NULL;
1451 
1452     if (!PyBytes_Check(b)) {
1453         PyErr_SetString(PyExc_TypeError,
1454                         "read() didn't return bytes");
1455         Py_DECREF(b);
1456         return NULL;
1457     }
1458 
1459     not_enough_bytes = (PyBytes_GET_SIZE(b) != nbytes);
1460 
1461     res = array_array_frombytes(self, b);
1462     Py_DECREF(b);
1463     if (res == NULL)
1464         return NULL;
1465 
1466     if (not_enough_bytes) {
1467         PyErr_SetString(PyExc_EOFError,
1468                         "read() didn't return enough bytes");
1469         Py_DECREF(res);
1470         return NULL;
1471     }
1472 
1473     return res;
1474 }
1475 
1476 /*[clinic input]
1477 array.array.tofile
1478 
1479     f: object
1480     /
1481 
1482 Write all items (as machine values) to the file object f.
1483 [clinic start generated code]*/
1484 
1485 static PyObject *
array_array_tofile(arrayobject * self,PyObject * f)1486 array_array_tofile(arrayobject *self, PyObject *f)
1487 /*[clinic end generated code: output=3a2cfa8128df0777 input=b0669a484aab0831]*/
1488 {
1489     Py_ssize_t nbytes = Py_SIZE(self) * self->ob_descr->itemsize;
1490     /* Write 64K blocks at a time */
1491     /* XXX Make the block size settable */
1492     int BLOCKSIZE = 64*1024;
1493     Py_ssize_t nblocks = (nbytes + BLOCKSIZE - 1) / BLOCKSIZE;
1494     Py_ssize_t i;
1495 
1496     if (Py_SIZE(self) == 0)
1497         goto done;
1498 
1499     for (i = 0; i < nblocks; i++) {
1500         char* ptr = self->ob_item + i*BLOCKSIZE;
1501         Py_ssize_t size = BLOCKSIZE;
1502         PyObject *bytes, *res;
1503         _Py_IDENTIFIER(write);
1504 
1505         if (i*BLOCKSIZE + size > nbytes)
1506             size = nbytes - i*BLOCKSIZE;
1507         bytes = PyBytes_FromStringAndSize(ptr, size);
1508         if (bytes == NULL)
1509             return NULL;
1510         res = _PyObject_CallMethodIdObjArgs(f, &PyId_write, bytes, NULL);
1511         Py_DECREF(bytes);
1512         if (res == NULL)
1513             return NULL;
1514         Py_DECREF(res); /* drop write result */
1515     }
1516 
1517   done:
1518     Py_RETURN_NONE;
1519 }
1520 
1521 /*[clinic input]
1522 array.array.fromlist
1523 
1524     list: object
1525     /
1526 
1527 Append items to array from list.
1528 [clinic start generated code]*/
1529 
1530 static PyObject *
array_array_fromlist(arrayobject * self,PyObject * list)1531 array_array_fromlist(arrayobject *self, PyObject *list)
1532 /*[clinic end generated code: output=26411c2d228a3e3f input=be2605a96c49680f]*/
1533 {
1534     Py_ssize_t n;
1535 
1536     if (!PyList_Check(list)) {
1537         PyErr_SetString(PyExc_TypeError, "arg must be list");
1538         return NULL;
1539     }
1540     n = PyList_Size(list);
1541     if (n > 0) {
1542         Py_ssize_t i, old_size;
1543         old_size = Py_SIZE(self);
1544         if (array_resize(self, old_size + n) == -1)
1545             return NULL;
1546         for (i = 0; i < n; i++) {
1547             PyObject *v = PyList_GET_ITEM(list, i);
1548             if ((*self->ob_descr->setitem)(self,
1549                             Py_SIZE(self) - n + i, v) != 0) {
1550                 array_resize(self, old_size);
1551                 return NULL;
1552             }
1553             if (n != PyList_GET_SIZE(list)) {
1554                 PyErr_SetString(PyExc_RuntimeError,
1555                                 "list changed size during iteration");
1556                 array_resize(self, old_size);
1557                 return NULL;
1558             }
1559         }
1560     }
1561     Py_RETURN_NONE;
1562 }
1563 
1564 /*[clinic input]
1565 array.array.tolist
1566 
1567 Convert array to an ordinary list with the same items.
1568 [clinic start generated code]*/
1569 
1570 static PyObject *
array_array_tolist_impl(arrayobject * self)1571 array_array_tolist_impl(arrayobject *self)
1572 /*[clinic end generated code: output=00b60cc9eab8ef89 input=a8d7784a94f86b53]*/
1573 {
1574     PyObject *list = PyList_New(Py_SIZE(self));
1575     Py_ssize_t i;
1576 
1577     if (list == NULL)
1578         return NULL;
1579     for (i = 0; i < Py_SIZE(self); i++) {
1580         PyObject *v = getarrayitem((PyObject *)self, i);
1581         if (v == NULL)
1582             goto error;
1583         PyList_SET_ITEM(list, i, v);
1584     }
1585     return list;
1586 
1587 error:
1588     Py_DECREF(list);
1589     return NULL;
1590 }
1591 
1592 static PyObject *
frombytes(arrayobject * self,Py_buffer * buffer)1593 frombytes(arrayobject *self, Py_buffer *buffer)
1594 {
1595     int itemsize = self->ob_descr->itemsize;
1596     Py_ssize_t n;
1597     if (buffer->itemsize != 1) {
1598         PyBuffer_Release(buffer);
1599         PyErr_SetString(PyExc_TypeError, "a bytes-like object is required");
1600         return NULL;
1601     }
1602     n = buffer->len;
1603     if (n % itemsize != 0) {
1604         PyBuffer_Release(buffer);
1605         PyErr_SetString(PyExc_ValueError,
1606                    "bytes length not a multiple of item size");
1607         return NULL;
1608     }
1609     n = n / itemsize;
1610     if (n > 0) {
1611         Py_ssize_t old_size = Py_SIZE(self);
1612         if ((n > PY_SSIZE_T_MAX - old_size) ||
1613             ((old_size + n) > PY_SSIZE_T_MAX / itemsize)) {
1614                 PyBuffer_Release(buffer);
1615                 return PyErr_NoMemory();
1616         }
1617         if (array_resize(self, old_size + n) == -1) {
1618             PyBuffer_Release(buffer);
1619             return NULL;
1620         }
1621         memcpy(self->ob_item + old_size * itemsize,
1622             buffer->buf, n * itemsize);
1623     }
1624     PyBuffer_Release(buffer);
1625     Py_RETURN_NONE;
1626 }
1627 
1628 /*[clinic input]
1629 array.array.fromstring
1630 
1631     buffer: Py_buffer(accept={str, buffer})
1632     /
1633 
1634 Appends items from the string, interpreting it as an array of machine values, as if it had been read from a file using the fromfile() method).
1635 
1636 This method is deprecated. Use frombytes instead.
1637 [clinic start generated code]*/
1638 
1639 static PyObject *
array_array_fromstring_impl(arrayobject * self,Py_buffer * buffer)1640 array_array_fromstring_impl(arrayobject *self, Py_buffer *buffer)
1641 /*[clinic end generated code: output=31c4baa779df84ce input=a3341a512e11d773]*/
1642 {
1643     if (PyErr_WarnEx(PyExc_DeprecationWarning,
1644             "fromstring() is deprecated. Use frombytes() instead.", 2) != 0)
1645         return NULL;
1646     return frombytes(self, buffer);
1647 }
1648 
1649 /*[clinic input]
1650 array.array.frombytes
1651 
1652     buffer: Py_buffer
1653     /
1654 
1655 Appends items from the string, interpreting it as an array of machine values, as if it had been read from a file using the fromfile() method).
1656 [clinic start generated code]*/
1657 
1658 static PyObject *
array_array_frombytes_impl(arrayobject * self,Py_buffer * buffer)1659 array_array_frombytes_impl(arrayobject *self, Py_buffer *buffer)
1660 /*[clinic end generated code: output=d9842c8f7510a516 input=2bbf2b53ebfcc988]*/
1661 {
1662     return frombytes(self, buffer);
1663 }
1664 
1665 /*[clinic input]
1666 array.array.tobytes
1667 
1668 Convert the array to an array of machine values and return the bytes representation.
1669 [clinic start generated code]*/
1670 
1671 static PyObject *
array_array_tobytes_impl(arrayobject * self)1672 array_array_tobytes_impl(arrayobject *self)
1673 /*[clinic end generated code: output=87318e4edcdc2bb6 input=90ee495f96de34f5]*/
1674 {
1675     if (Py_SIZE(self) <= PY_SSIZE_T_MAX / self->ob_descr->itemsize) {
1676         return PyBytes_FromStringAndSize(self->ob_item,
1677                             Py_SIZE(self) * self->ob_descr->itemsize);
1678     } else {
1679         return PyErr_NoMemory();
1680     }
1681 }
1682 
1683 /*[clinic input]
1684 array.array.tostring
1685 
1686 Convert the array to an array of machine values and return the bytes representation.
1687 
1688 This method is deprecated. Use tobytes instead.
1689 [clinic start generated code]*/
1690 
1691 static PyObject *
array_array_tostring_impl(arrayobject * self)1692 array_array_tostring_impl(arrayobject *self)
1693 /*[clinic end generated code: output=7d6bd92745a2c8f3 input=b6c0ddee7b30457e]*/
1694 {
1695     if (PyErr_WarnEx(PyExc_DeprecationWarning,
1696             "tostring() is deprecated. Use tobytes() instead.", 2) != 0)
1697         return NULL;
1698     return array_array_tobytes_impl(self);
1699 }
1700 
1701 /*[clinic input]
1702 array.array.fromunicode
1703 
1704     ustr: Py_UNICODE(zeroes=True)
1705     /
1706 
1707 Extends this array with data from the unicode string ustr.
1708 
1709 The array must be a unicode type array; otherwise a ValueError is raised.
1710 Use array.frombytes(ustr.encode(...)) to append Unicode data to an array of
1711 some other type.
1712 [clinic start generated code]*/
1713 
1714 static PyObject *
array_array_fromunicode_impl(arrayobject * self,const Py_UNICODE * ustr,Py_ssize_clean_t ustr_length)1715 array_array_fromunicode_impl(arrayobject *self, const Py_UNICODE *ustr,
1716                              Py_ssize_clean_t ustr_length)
1717 /*[clinic end generated code: output=cf2f662908e2befc input=150f00566ffbca6e]*/
1718 {
1719     char typecode;
1720 
1721     typecode = self->ob_descr->typecode;
1722     if (typecode != 'u') {
1723         PyErr_SetString(PyExc_ValueError,
1724             "fromunicode() may only be called on "
1725             "unicode type arrays");
1726         return NULL;
1727     }
1728     if (ustr_length > 0) {
1729         Py_ssize_t old_size = Py_SIZE(self);
1730         if (array_resize(self, old_size + ustr_length) == -1)
1731             return NULL;
1732         memcpy(self->ob_item + old_size * sizeof(Py_UNICODE),
1733                ustr, ustr_length * sizeof(Py_UNICODE));
1734     }
1735 
1736     Py_RETURN_NONE;
1737 }
1738 
1739 /*[clinic input]
1740 array.array.tounicode
1741 
1742 Extends this array with data from the unicode string ustr.
1743 
1744 Convert the array to a unicode string.  The array must be a unicode type array;
1745 otherwise a ValueError is raised.  Use array.tobytes().decode() to obtain a
1746 unicode string from an array of some other type.
1747 [clinic start generated code]*/
1748 
1749 static PyObject *
array_array_tounicode_impl(arrayobject * self)1750 array_array_tounicode_impl(arrayobject *self)
1751 /*[clinic end generated code: output=08e442378336e1ef input=127242eebe70b66d]*/
1752 {
1753     char typecode;
1754     typecode = self->ob_descr->typecode;
1755     if (typecode != 'u') {
1756         PyErr_SetString(PyExc_ValueError,
1757              "tounicode() may only be called on unicode type arrays");
1758         return NULL;
1759     }
1760     return PyUnicode_FromWideChar((Py_UNICODE *) self->ob_item, Py_SIZE(self));
1761 }
1762 
1763 /*[clinic input]
1764 array.array.__sizeof__
1765 
1766 Size of the array in memory, in bytes.
1767 [clinic start generated code]*/
1768 
1769 static PyObject *
array_array___sizeof___impl(arrayobject * self)1770 array_array___sizeof___impl(arrayobject *self)
1771 /*[clinic end generated code: output=d8e1c61ebbe3eaed input=805586565bf2b3c6]*/
1772 {
1773     Py_ssize_t res;
1774     res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * self->ob_descr->itemsize;
1775     return PyLong_FromSsize_t(res);
1776 }
1777 
1778 
1779 /*********************** Pickling support ************************/
1780 
1781 static const struct mformatdescr {
1782     size_t size;
1783     int is_signed;
1784     int is_big_endian;
1785 } mformat_descriptors[] = {
1786     {1, 0, 0},                  /* 0: UNSIGNED_INT8 */
1787     {1, 1, 0},                  /* 1: SIGNED_INT8 */
1788     {2, 0, 0},                  /* 2: UNSIGNED_INT16_LE */
1789     {2, 0, 1},                  /* 3: UNSIGNED_INT16_BE */
1790     {2, 1, 0},                  /* 4: SIGNED_INT16_LE */
1791     {2, 1, 1},                  /* 5: SIGNED_INT16_BE */
1792     {4, 0, 0},                  /* 6: UNSIGNED_INT32_LE */
1793     {4, 0, 1},                  /* 7: UNSIGNED_INT32_BE */
1794     {4, 1, 0},                  /* 8: SIGNED_INT32_LE */
1795     {4, 1, 1},                  /* 9: SIGNED_INT32_BE */
1796     {8, 0, 0},                  /* 10: UNSIGNED_INT64_LE */
1797     {8, 0, 1},                  /* 11: UNSIGNED_INT64_BE */
1798     {8, 1, 0},                  /* 12: SIGNED_INT64_LE */
1799     {8, 1, 1},                  /* 13: SIGNED_INT64_BE */
1800     {4, 0, 0},                  /* 14: IEEE_754_FLOAT_LE */
1801     {4, 0, 1},                  /* 15: IEEE_754_FLOAT_BE */
1802     {8, 0, 0},                  /* 16: IEEE_754_DOUBLE_LE */
1803     {8, 0, 1},                  /* 17: IEEE_754_DOUBLE_BE */
1804     {4, 0, 0},                  /* 18: UTF16_LE */
1805     {4, 0, 1},                  /* 19: UTF16_BE */
1806     {8, 0, 0},                  /* 20: UTF32_LE */
1807     {8, 0, 1}                   /* 21: UTF32_BE */
1808 };
1809 
1810 
1811 /*
1812  * Internal: This function is used to find the machine format of a given
1813  * array type code. This returns UNKNOWN_FORMAT when the machine format cannot
1814  * be found.
1815  */
1816 static enum machine_format_code
typecode_to_mformat_code(char typecode)1817 typecode_to_mformat_code(char typecode)
1818 {
1819     const int is_big_endian = PY_BIG_ENDIAN;
1820 
1821     size_t intsize;
1822     int is_signed;
1823 
1824     switch (typecode) {
1825     case 'b':
1826         return SIGNED_INT8;
1827     case 'B':
1828         return UNSIGNED_INT8;
1829 
1830     case 'u':
1831         if (sizeof(Py_UNICODE) == 2) {
1832             return UTF16_LE + is_big_endian;
1833         }
1834         if (sizeof(Py_UNICODE) == 4) {
1835             return UTF32_LE + is_big_endian;
1836         }
1837         return UNKNOWN_FORMAT;
1838 
1839     case 'f':
1840         if (sizeof(float) == 4) {
1841             const float y = 16711938.0;
1842             if (memcmp(&y, "\x4b\x7f\x01\x02", 4) == 0)
1843                 return IEEE_754_FLOAT_BE;
1844             if (memcmp(&y, "\x02\x01\x7f\x4b", 4) == 0)
1845                 return IEEE_754_FLOAT_LE;
1846         }
1847         return UNKNOWN_FORMAT;
1848 
1849     case 'd':
1850         if (sizeof(double) == 8) {
1851             const double x = 9006104071832581.0;
1852             if (memcmp(&x, "\x43\x3f\xff\x01\x02\x03\x04\x05", 8) == 0)
1853                 return IEEE_754_DOUBLE_BE;
1854             if (memcmp(&x, "\x05\x04\x03\x02\x01\xff\x3f\x43", 8) == 0)
1855                 return IEEE_754_DOUBLE_LE;
1856         }
1857         return UNKNOWN_FORMAT;
1858 
1859     /* Integers */
1860     case 'h':
1861         intsize = sizeof(short);
1862         is_signed = 1;
1863         break;
1864     case 'H':
1865         intsize = sizeof(short);
1866         is_signed = 0;
1867         break;
1868     case 'i':
1869         intsize = sizeof(int);
1870         is_signed = 1;
1871         break;
1872     case 'I':
1873         intsize = sizeof(int);
1874         is_signed = 0;
1875         break;
1876     case 'l':
1877         intsize = sizeof(long);
1878         is_signed = 1;
1879         break;
1880     case 'L':
1881         intsize = sizeof(long);
1882         is_signed = 0;
1883         break;
1884     case 'q':
1885         intsize = sizeof(long long);
1886         is_signed = 1;
1887         break;
1888     case 'Q':
1889         intsize = sizeof(long long);
1890         is_signed = 0;
1891         break;
1892     default:
1893         return UNKNOWN_FORMAT;
1894     }
1895     switch (intsize) {
1896     case 2:
1897         return UNSIGNED_INT16_LE + is_big_endian + (2 * is_signed);
1898     case 4:
1899         return UNSIGNED_INT32_LE + is_big_endian + (2 * is_signed);
1900     case 8:
1901         return UNSIGNED_INT64_LE + is_big_endian + (2 * is_signed);
1902     default:
1903         return UNKNOWN_FORMAT;
1904     }
1905 }
1906 
1907 /* Forward declaration. */
1908 static PyObject *array_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
1909 
1910 /*
1911  * Internal: This function wraps the array constructor--i.e., array_new()--to
1912  * allow the creation of array objects from C code without having to deal
1913  * directly the tuple argument of array_new(). The typecode argument is a
1914  * Unicode character value, like 'i' or 'f' for example, representing an array
1915  * type code. The items argument is a bytes or a list object from which
1916  * contains the initial value of the array.
1917  *
1918  * On success, this functions returns the array object created. Otherwise,
1919  * NULL is returned to indicate a failure.
1920  */
1921 static PyObject *
make_array(PyTypeObject * arraytype,char typecode,PyObject * items)1922 make_array(PyTypeObject *arraytype, char typecode, PyObject *items)
1923 {
1924     PyObject *new_args;
1925     PyObject *array_obj;
1926     PyObject *typecode_obj;
1927 
1928     assert(arraytype != NULL);
1929     assert(items != NULL);
1930 
1931     typecode_obj = PyUnicode_FromOrdinal(typecode);
1932     if (typecode_obj == NULL)
1933         return NULL;
1934 
1935     new_args = PyTuple_New(2);
1936     if (new_args == NULL) {
1937         Py_DECREF(typecode_obj);
1938         return NULL;
1939     }
1940     Py_INCREF(items);
1941     PyTuple_SET_ITEM(new_args, 0, typecode_obj);
1942     PyTuple_SET_ITEM(new_args, 1, items);
1943 
1944     array_obj = array_new(arraytype, new_args, NULL);
1945     Py_DECREF(new_args);
1946     if (array_obj == NULL)
1947         return NULL;
1948 
1949     return array_obj;
1950 }
1951 
1952 /*
1953  * This functions is a special constructor used when unpickling an array. It
1954  * provides a portable way to rebuild an array from its memory representation.
1955  */
1956 /*[clinic input]
1957 array._array_reconstructor
1958 
1959     arraytype: object(type="PyTypeObject *")
1960     typecode: int(accept={str})
1961     mformat_code: int(type="enum machine_format_code")
1962     items: object
1963     /
1964 
1965 Internal. Used for pickling support.
1966 [clinic start generated code]*/
1967 
1968 static PyObject *
array__array_reconstructor_impl(PyObject * module,PyTypeObject * arraytype,int typecode,enum machine_format_code mformat_code,PyObject * items)1969 array__array_reconstructor_impl(PyObject *module, PyTypeObject *arraytype,
1970                                 int typecode,
1971                                 enum machine_format_code mformat_code,
1972                                 PyObject *items)
1973 /*[clinic end generated code: output=e05263141ba28365 input=2464dc8f4c7736b5]*/
1974 {
1975     PyObject *converted_items;
1976     PyObject *result;
1977     const struct arraydescr *descr;
1978 
1979     if (!PyType_Check(arraytype)) {
1980         PyErr_Format(PyExc_TypeError,
1981             "first argument must be a type object, not %.200s",
1982             Py_TYPE(arraytype)->tp_name);
1983         return NULL;
1984     }
1985     if (!PyType_IsSubtype(arraytype, &Arraytype)) {
1986         PyErr_Format(PyExc_TypeError,
1987             "%.200s is not a subtype of %.200s",
1988             arraytype->tp_name, Arraytype.tp_name);
1989         return NULL;
1990     }
1991     for (descr = descriptors; descr->typecode != '\0'; descr++) {
1992         if ((int)descr->typecode == typecode)
1993             break;
1994     }
1995     if (descr->typecode == '\0') {
1996         PyErr_SetString(PyExc_ValueError,
1997                         "second argument must be a valid type code");
1998         return NULL;
1999     }
2000     if (mformat_code < MACHINE_FORMAT_CODE_MIN ||
2001         mformat_code > MACHINE_FORMAT_CODE_MAX) {
2002         PyErr_SetString(PyExc_ValueError,
2003             "third argument must be a valid machine format code.");
2004         return NULL;
2005     }
2006     if (!PyBytes_Check(items)) {
2007         PyErr_Format(PyExc_TypeError,
2008             "fourth argument should be bytes, not %.200s",
2009             Py_TYPE(items)->tp_name);
2010         return NULL;
2011     }
2012 
2013     /* Fast path: No decoding has to be done. */
2014     if (mformat_code == typecode_to_mformat_code((char)typecode) ||
2015         mformat_code == UNKNOWN_FORMAT) {
2016         return make_array(arraytype, (char)typecode, items);
2017     }
2018 
2019     /* Slow path: Decode the byte string according to the given machine
2020      * format code. This occurs when the computer unpickling the array
2021      * object is architecturally different from the one that pickled the
2022      * array.
2023      */
2024     if (Py_SIZE(items) % mformat_descriptors[mformat_code].size != 0) {
2025         PyErr_SetString(PyExc_ValueError,
2026                         "string length not a multiple of item size");
2027         return NULL;
2028     }
2029     switch (mformat_code) {
2030     case IEEE_754_FLOAT_LE:
2031     case IEEE_754_FLOAT_BE: {
2032         int i;
2033         int le = (mformat_code == IEEE_754_FLOAT_LE) ? 1 : 0;
2034         Py_ssize_t itemcount = Py_SIZE(items) / 4;
2035         const unsigned char *memstr =
2036             (unsigned char *)PyBytes_AS_STRING(items);
2037 
2038         converted_items = PyList_New(itemcount);
2039         if (converted_items == NULL)
2040             return NULL;
2041         for (i = 0; i < itemcount; i++) {
2042             PyObject *pyfloat = PyFloat_FromDouble(
2043                 _PyFloat_Unpack4(&memstr[i * 4], le));
2044             if (pyfloat == NULL) {
2045                 Py_DECREF(converted_items);
2046                 return NULL;
2047             }
2048             PyList_SET_ITEM(converted_items, i, pyfloat);
2049         }
2050         break;
2051     }
2052     case IEEE_754_DOUBLE_LE:
2053     case IEEE_754_DOUBLE_BE: {
2054         int i;
2055         int le = (mformat_code == IEEE_754_DOUBLE_LE) ? 1 : 0;
2056         Py_ssize_t itemcount = Py_SIZE(items) / 8;
2057         const unsigned char *memstr =
2058             (unsigned char *)PyBytes_AS_STRING(items);
2059 
2060         converted_items = PyList_New(itemcount);
2061         if (converted_items == NULL)
2062             return NULL;
2063         for (i = 0; i < itemcount; i++) {
2064             PyObject *pyfloat = PyFloat_FromDouble(
2065                 _PyFloat_Unpack8(&memstr[i * 8], le));
2066             if (pyfloat == NULL) {
2067                 Py_DECREF(converted_items);
2068                 return NULL;
2069             }
2070             PyList_SET_ITEM(converted_items, i, pyfloat);
2071         }
2072         break;
2073     }
2074     case UTF16_LE:
2075     case UTF16_BE: {
2076         int byteorder = (mformat_code == UTF16_LE) ? -1 : 1;
2077         converted_items = PyUnicode_DecodeUTF16(
2078             PyBytes_AS_STRING(items), Py_SIZE(items),
2079             "strict", &byteorder);
2080         if (converted_items == NULL)
2081             return NULL;
2082         break;
2083     }
2084     case UTF32_LE:
2085     case UTF32_BE: {
2086         int byteorder = (mformat_code == UTF32_LE) ? -1 : 1;
2087         converted_items = PyUnicode_DecodeUTF32(
2088             PyBytes_AS_STRING(items), Py_SIZE(items),
2089             "strict", &byteorder);
2090         if (converted_items == NULL)
2091             return NULL;
2092         break;
2093     }
2094 
2095     case UNSIGNED_INT8:
2096     case SIGNED_INT8:
2097     case UNSIGNED_INT16_LE:
2098     case UNSIGNED_INT16_BE:
2099     case SIGNED_INT16_LE:
2100     case SIGNED_INT16_BE:
2101     case UNSIGNED_INT32_LE:
2102     case UNSIGNED_INT32_BE:
2103     case SIGNED_INT32_LE:
2104     case SIGNED_INT32_BE:
2105     case UNSIGNED_INT64_LE:
2106     case UNSIGNED_INT64_BE:
2107     case SIGNED_INT64_LE:
2108     case SIGNED_INT64_BE: {
2109         int i;
2110         const struct mformatdescr mf_descr =
2111             mformat_descriptors[mformat_code];
2112         Py_ssize_t itemcount = Py_SIZE(items) / mf_descr.size;
2113         const unsigned char *memstr =
2114             (unsigned char *)PyBytes_AS_STRING(items);
2115         const struct arraydescr *descr;
2116 
2117         /* If possible, try to pack array's items using a data type
2118          * that fits better. This may result in an array with narrower
2119          * or wider elements.
2120          *
2121          * For example, if a 32-bit machine pickles an L-code array of
2122          * unsigned longs, then the array will be unpickled by 64-bit
2123          * machine as an I-code array of unsigned ints.
2124          *
2125          * XXX: Is it possible to write a unit test for this?
2126          */
2127         for (descr = descriptors; descr->typecode != '\0'; descr++) {
2128             if (descr->is_integer_type &&
2129                 (size_t)descr->itemsize == mf_descr.size &&
2130                 descr->is_signed == mf_descr.is_signed)
2131                 typecode = descr->typecode;
2132         }
2133 
2134         converted_items = PyList_New(itemcount);
2135         if (converted_items == NULL)
2136             return NULL;
2137         for (i = 0; i < itemcount; i++) {
2138             PyObject *pylong;
2139 
2140             pylong = _PyLong_FromByteArray(
2141                 &memstr[i * mf_descr.size],
2142                 mf_descr.size,
2143                 !mf_descr.is_big_endian,
2144                 mf_descr.is_signed);
2145             if (pylong == NULL) {
2146                 Py_DECREF(converted_items);
2147                 return NULL;
2148             }
2149             PyList_SET_ITEM(converted_items, i, pylong);
2150         }
2151         break;
2152     }
2153     case UNKNOWN_FORMAT:
2154         /* Impossible, but needed to shut up GCC about the unhandled
2155          * enumeration value.
2156          */
2157     default:
2158         PyErr_BadArgument();
2159         return NULL;
2160     }
2161 
2162     result = make_array(arraytype, (char)typecode, converted_items);
2163     Py_DECREF(converted_items);
2164     return result;
2165 }
2166 
2167 /*[clinic input]
2168 array.array.__reduce_ex__
2169 
2170     value: object
2171     /
2172 
2173 Return state information for pickling.
2174 [clinic start generated code]*/
2175 
2176 static PyObject *
array_array___reduce_ex__(arrayobject * self,PyObject * value)2177 array_array___reduce_ex__(arrayobject *self, PyObject *value)
2178 /*[clinic end generated code: output=051e0a6175d0eddb input=c36c3f85de7df6cd]*/
2179 {
2180     PyObject *dict;
2181     PyObject *result;
2182     PyObject *array_str;
2183     int typecode = self->ob_descr->typecode;
2184     int mformat_code;
2185     static PyObject *array_reconstructor = NULL;
2186     long protocol;
2187     _Py_IDENTIFIER(_array_reconstructor);
2188     _Py_IDENTIFIER(__dict__);
2189 
2190     if (array_reconstructor == NULL) {
2191         PyObject *array_module = PyImport_ImportModule("array");
2192         if (array_module == NULL)
2193             return NULL;
2194         array_reconstructor = _PyObject_GetAttrId(
2195             array_module,
2196             &PyId__array_reconstructor);
2197         Py_DECREF(array_module);
2198         if (array_reconstructor == NULL)
2199             return NULL;
2200     }
2201 
2202     if (!PyLong_Check(value)) {
2203         PyErr_SetString(PyExc_TypeError,
2204                         "__reduce_ex__ argument should be an integer");
2205         return NULL;
2206     }
2207     protocol = PyLong_AsLong(value);
2208     if (protocol == -1 && PyErr_Occurred())
2209         return NULL;
2210 
2211     if (_PyObject_LookupAttrId((PyObject *)self, &PyId___dict__, &dict) < 0) {
2212         return NULL;
2213     }
2214     if (dict == NULL) {
2215         dict = Py_None;
2216         Py_INCREF(dict);
2217     }
2218 
2219     mformat_code = typecode_to_mformat_code(typecode);
2220     if (mformat_code == UNKNOWN_FORMAT || protocol < 3) {
2221         /* Convert the array to a list if we got something weird
2222          * (e.g., non-IEEE floats), or we are pickling the array using
2223          * a Python 2.x compatible protocol.
2224          *
2225          * It is necessary to use a list representation for Python 2.x
2226          * compatible pickle protocol, since Python 2's str objects
2227          * are unpickled as unicode by Python 3. Thus it is impossible
2228          * to make arrays unpicklable by Python 3 by using their memory
2229          * representation, unless we resort to ugly hacks such as
2230          * coercing unicode objects to bytes in array_reconstructor.
2231          */
2232         PyObject *list;
2233         list = array_array_tolist_impl(self);
2234         if (list == NULL) {
2235             Py_DECREF(dict);
2236             return NULL;
2237         }
2238         result = Py_BuildValue(
2239             "O(CO)O", Py_TYPE(self), typecode, list, dict);
2240         Py_DECREF(list);
2241         Py_DECREF(dict);
2242         return result;
2243     }
2244 
2245     array_str = array_array_tobytes_impl(self);
2246     if (array_str == NULL) {
2247         Py_DECREF(dict);
2248         return NULL;
2249     }
2250     result = Py_BuildValue(
2251         "O(OCiN)O", array_reconstructor, Py_TYPE(self), typecode,
2252         mformat_code, array_str, dict);
2253     Py_DECREF(dict);
2254     return result;
2255 }
2256 
2257 static PyObject *
array_get_typecode(arrayobject * a,void * closure)2258 array_get_typecode(arrayobject *a, void *closure)
2259 {
2260     char typecode = a->ob_descr->typecode;
2261     return PyUnicode_FromOrdinal(typecode);
2262 }
2263 
2264 static PyObject *
array_get_itemsize(arrayobject * a,void * closure)2265 array_get_itemsize(arrayobject *a, void *closure)
2266 {
2267     return PyLong_FromLong((long)a->ob_descr->itemsize);
2268 }
2269 
2270 static PyGetSetDef array_getsets [] = {
2271     {"typecode", (getter) array_get_typecode, NULL,
2272      "the typecode character used to create the array"},
2273     {"itemsize", (getter) array_get_itemsize, NULL,
2274      "the size, in bytes, of one array item"},
2275     {NULL}
2276 };
2277 
2278 static PyMethodDef array_methods[] = {
2279     ARRAY_ARRAY_APPEND_METHODDEF
2280     ARRAY_ARRAY_BUFFER_INFO_METHODDEF
2281     ARRAY_ARRAY_BYTESWAP_METHODDEF
2282     ARRAY_ARRAY___COPY___METHODDEF
2283     ARRAY_ARRAY_COUNT_METHODDEF
2284     ARRAY_ARRAY___DEEPCOPY___METHODDEF
2285     ARRAY_ARRAY_EXTEND_METHODDEF
2286     ARRAY_ARRAY_FROMFILE_METHODDEF
2287     ARRAY_ARRAY_FROMLIST_METHODDEF
2288     ARRAY_ARRAY_FROMSTRING_METHODDEF
2289     ARRAY_ARRAY_FROMBYTES_METHODDEF
2290     ARRAY_ARRAY_FROMUNICODE_METHODDEF
2291     ARRAY_ARRAY_INDEX_METHODDEF
2292     ARRAY_ARRAY_INSERT_METHODDEF
2293     ARRAY_ARRAY_POP_METHODDEF
2294     ARRAY_ARRAY___REDUCE_EX___METHODDEF
2295     ARRAY_ARRAY_REMOVE_METHODDEF
2296     ARRAY_ARRAY_REVERSE_METHODDEF
2297     ARRAY_ARRAY_TOFILE_METHODDEF
2298     ARRAY_ARRAY_TOLIST_METHODDEF
2299     ARRAY_ARRAY_TOSTRING_METHODDEF
2300     ARRAY_ARRAY_TOBYTES_METHODDEF
2301     ARRAY_ARRAY_TOUNICODE_METHODDEF
2302     ARRAY_ARRAY___SIZEOF___METHODDEF
2303     {NULL, NULL}  /* sentinel */
2304 };
2305 
2306 static PyObject *
array_repr(arrayobject * a)2307 array_repr(arrayobject *a)
2308 {
2309     char typecode;
2310     PyObject *s, *v = NULL;
2311     Py_ssize_t len;
2312 
2313     len = Py_SIZE(a);
2314     typecode = a->ob_descr->typecode;
2315     if (len == 0) {
2316         return PyUnicode_FromFormat("%s('%c')",
2317                                     _PyType_Name(Py_TYPE(a)), (int)typecode);
2318     }
2319     if (typecode == 'u') {
2320         v = array_array_tounicode_impl(a);
2321     } else {
2322         v = array_array_tolist_impl(a);
2323     }
2324     if (v == NULL)
2325         return NULL;
2326 
2327     s = PyUnicode_FromFormat("%s('%c', %R)",
2328                              _PyType_Name(Py_TYPE(a)), (int)typecode, v);
2329     Py_DECREF(v);
2330     return s;
2331 }
2332 
2333 static PyObject*
array_subscr(arrayobject * self,PyObject * item)2334 array_subscr(arrayobject* self, PyObject* item)
2335 {
2336     if (PyIndex_Check(item)) {
2337         Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2338         if (i==-1 && PyErr_Occurred()) {
2339             return NULL;
2340         }
2341         if (i < 0)
2342             i += Py_SIZE(self);
2343         return array_item(self, i);
2344     }
2345     else if (PySlice_Check(item)) {
2346         Py_ssize_t start, stop, step, slicelength, cur, i;
2347         PyObject* result;
2348         arrayobject* ar;
2349         int itemsize = self->ob_descr->itemsize;
2350 
2351         if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2352             return NULL;
2353         }
2354         slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2355                                             step);
2356 
2357         if (slicelength <= 0) {
2358             return newarrayobject(&Arraytype, 0, self->ob_descr);
2359         }
2360         else if (step == 1) {
2361             PyObject *result = newarrayobject(&Arraytype,
2362                                     slicelength, self->ob_descr);
2363             if (result == NULL)
2364                 return NULL;
2365             memcpy(((arrayobject *)result)->ob_item,
2366                    self->ob_item + start * itemsize,
2367                    slicelength * itemsize);
2368             return result;
2369         }
2370         else {
2371             result = newarrayobject(&Arraytype, slicelength, self->ob_descr);
2372             if (!result) return NULL;
2373 
2374             ar = (arrayobject*)result;
2375 
2376             for (cur = start, i = 0; i < slicelength;
2377                  cur += step, i++) {
2378                 memcpy(ar->ob_item + i*itemsize,
2379                        self->ob_item + cur*itemsize,
2380                        itemsize);
2381             }
2382 
2383             return result;
2384         }
2385     }
2386     else {
2387         PyErr_SetString(PyExc_TypeError,
2388                         "array indices must be integers");
2389         return NULL;
2390     }
2391 }
2392 
2393 static int
array_ass_subscr(arrayobject * self,PyObject * item,PyObject * value)2394 array_ass_subscr(arrayobject* self, PyObject* item, PyObject* value)
2395 {
2396     Py_ssize_t start, stop, step, slicelength, needed;
2397     arrayobject* other;
2398     int itemsize;
2399 
2400     if (PyIndex_Check(item)) {
2401         Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2402 
2403         if (i == -1 && PyErr_Occurred())
2404             return -1;
2405         if (i < 0)
2406             i += Py_SIZE(self);
2407         if (i < 0 || i >= Py_SIZE(self)) {
2408             PyErr_SetString(PyExc_IndexError,
2409                 "array assignment index out of range");
2410             return -1;
2411         }
2412         if (value == NULL) {
2413             /* Fall through to slice assignment */
2414             start = i;
2415             stop = i + 1;
2416             step = 1;
2417             slicelength = 1;
2418         }
2419         else
2420             return (*self->ob_descr->setitem)(self, i, value);
2421     }
2422     else if (PySlice_Check(item)) {
2423         if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2424             return -1;
2425         }
2426         slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2427                                             step);
2428     }
2429     else {
2430         PyErr_SetString(PyExc_TypeError,
2431                         "array indices must be integers");
2432         return -1;
2433     }
2434     if (value == NULL) {
2435         other = NULL;
2436         needed = 0;
2437     }
2438     else if (array_Check(value)) {
2439         other = (arrayobject *)value;
2440         needed = Py_SIZE(other);
2441         if (self == other) {
2442             /* Special case "self[i:j] = self" -- copy self first */
2443             int ret;
2444             value = array_slice(other, 0, needed);
2445             if (value == NULL)
2446                 return -1;
2447             ret = array_ass_subscr(self, item, value);
2448             Py_DECREF(value);
2449             return ret;
2450         }
2451         if (other->ob_descr != self->ob_descr) {
2452             PyErr_BadArgument();
2453             return -1;
2454         }
2455     }
2456     else {
2457         PyErr_Format(PyExc_TypeError,
2458          "can only assign array (not \"%.200s\") to array slice",
2459                          Py_TYPE(value)->tp_name);
2460         return -1;
2461     }
2462     itemsize = self->ob_descr->itemsize;
2463     /* for 'a[2:1] = ...', the insertion point is 'start', not 'stop' */
2464     if ((step > 0 && stop < start) ||
2465         (step < 0 && stop > start))
2466         stop = start;
2467 
2468     /* Issue #4509: If the array has exported buffers and the slice
2469        assignment would change the size of the array, fail early to make
2470        sure we don't modify it. */
2471     if ((needed == 0 || slicelength != needed) && self->ob_exports > 0) {
2472         PyErr_SetString(PyExc_BufferError,
2473             "cannot resize an array that is exporting buffers");
2474         return -1;
2475     }
2476 
2477     if (step == 1) {
2478         if (slicelength > needed) {
2479             memmove(self->ob_item + (start + needed) * itemsize,
2480                 self->ob_item + stop * itemsize,
2481                 (Py_SIZE(self) - stop) * itemsize);
2482             if (array_resize(self, Py_SIZE(self) +
2483                 needed - slicelength) < 0)
2484                 return -1;
2485         }
2486         else if (slicelength < needed) {
2487             if (array_resize(self, Py_SIZE(self) +
2488                 needed - slicelength) < 0)
2489                 return -1;
2490             memmove(self->ob_item + (start + needed) * itemsize,
2491                 self->ob_item + stop * itemsize,
2492                 (Py_SIZE(self) - start - needed) * itemsize);
2493         }
2494         if (needed > 0)
2495             memcpy(self->ob_item + start * itemsize,
2496                    other->ob_item, needed * itemsize);
2497         return 0;
2498     }
2499     else if (needed == 0) {
2500         /* Delete slice */
2501         size_t cur;
2502         Py_ssize_t i;
2503 
2504         if (step < 0) {
2505             stop = start + 1;
2506             start = stop + step * (slicelength - 1) - 1;
2507             step = -step;
2508         }
2509         for (cur = start, i = 0; i < slicelength;
2510              cur += step, i++) {
2511             Py_ssize_t lim = step - 1;
2512 
2513             if (cur + step >= (size_t)Py_SIZE(self))
2514                 lim = Py_SIZE(self) - cur - 1;
2515             memmove(self->ob_item + (cur - i) * itemsize,
2516                 self->ob_item + (cur + 1) * itemsize,
2517                 lim * itemsize);
2518         }
2519         cur = start + (size_t)slicelength * step;
2520         if (cur < (size_t)Py_SIZE(self)) {
2521             memmove(self->ob_item + (cur-slicelength) * itemsize,
2522                 self->ob_item + cur * itemsize,
2523                 (Py_SIZE(self) - cur) * itemsize);
2524         }
2525         if (array_resize(self, Py_SIZE(self) - slicelength) < 0)
2526             return -1;
2527         return 0;
2528     }
2529     else {
2530         Py_ssize_t cur, i;
2531 
2532         if (needed != slicelength) {
2533             PyErr_Format(PyExc_ValueError,
2534                 "attempt to assign array of size %zd "
2535                 "to extended slice of size %zd",
2536                 needed, slicelength);
2537             return -1;
2538         }
2539         for (cur = start, i = 0; i < slicelength;
2540              cur += step, i++) {
2541             memcpy(self->ob_item + cur * itemsize,
2542                    other->ob_item + i * itemsize,
2543                    itemsize);
2544         }
2545         return 0;
2546     }
2547 }
2548 
2549 static PyMappingMethods array_as_mapping = {
2550     (lenfunc)array_length,
2551     (binaryfunc)array_subscr,
2552     (objobjargproc)array_ass_subscr
2553 };
2554 
2555 static const void *emptybuf = "";
2556 
2557 
2558 static int
array_buffer_getbuf(arrayobject * self,Py_buffer * view,int flags)2559 array_buffer_getbuf(arrayobject *self, Py_buffer *view, int flags)
2560 {
2561     if (view == NULL) {
2562         PyErr_SetString(PyExc_BufferError,
2563             "array_buffer_getbuf: view==NULL argument is obsolete");
2564         return -1;
2565     }
2566 
2567     view->buf = (void *)self->ob_item;
2568     view->obj = (PyObject*)self;
2569     Py_INCREF(self);
2570     if (view->buf == NULL)
2571         view->buf = (void *)emptybuf;
2572     view->len = (Py_SIZE(self)) * self->ob_descr->itemsize;
2573     view->readonly = 0;
2574     view->ndim = 1;
2575     view->itemsize = self->ob_descr->itemsize;
2576     view->suboffsets = NULL;
2577     view->shape = NULL;
2578     if ((flags & PyBUF_ND)==PyBUF_ND) {
2579         view->shape = &((Py_SIZE(self)));
2580     }
2581     view->strides = NULL;
2582     if ((flags & PyBUF_STRIDES)==PyBUF_STRIDES)
2583         view->strides = &(view->itemsize);
2584     view->format = NULL;
2585     view->internal = NULL;
2586     if ((flags & PyBUF_FORMAT) == PyBUF_FORMAT) {
2587         view->format = (char *)self->ob_descr->formats;
2588 #ifdef Py_UNICODE_WIDE
2589         if (self->ob_descr->typecode == 'u') {
2590             view->format = "w";
2591         }
2592 #endif
2593     }
2594 
2595     self->ob_exports++;
2596     return 0;
2597 }
2598 
2599 static void
array_buffer_relbuf(arrayobject * self,Py_buffer * view)2600 array_buffer_relbuf(arrayobject *self, Py_buffer *view)
2601 {
2602     self->ob_exports--;
2603 }
2604 
2605 static PySequenceMethods array_as_sequence = {
2606     (lenfunc)array_length,                      /*sq_length*/
2607     (binaryfunc)array_concat,               /*sq_concat*/
2608     (ssizeargfunc)array_repeat,                 /*sq_repeat*/
2609     (ssizeargfunc)array_item,                           /*sq_item*/
2610     0,                                          /*sq_slice*/
2611     (ssizeobjargproc)array_ass_item,                    /*sq_ass_item*/
2612     0,                                          /*sq_ass_slice*/
2613     (objobjproc)array_contains,                 /*sq_contains*/
2614     (binaryfunc)array_inplace_concat,           /*sq_inplace_concat*/
2615     (ssizeargfunc)array_inplace_repeat          /*sq_inplace_repeat*/
2616 };
2617 
2618 static PyBufferProcs array_as_buffer = {
2619     (getbufferproc)array_buffer_getbuf,
2620     (releasebufferproc)array_buffer_relbuf
2621 };
2622 
2623 static PyObject *
array_new(PyTypeObject * type,PyObject * args,PyObject * kwds)2624 array_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2625 {
2626     int c;
2627     PyObject *initial = NULL, *it = NULL;
2628     const struct arraydescr *descr;
2629 
2630     if (type == &Arraytype && !_PyArg_NoKeywords("array.array", kwds))
2631         return NULL;
2632 
2633     if (!PyArg_ParseTuple(args, "C|O:array", &c, &initial))
2634         return NULL;
2635 
2636     if (initial && c != 'u') {
2637         if (PyUnicode_Check(initial)) {
2638             PyErr_Format(PyExc_TypeError, "cannot use a str to initialize "
2639                          "an array with typecode '%c'", c);
2640             return NULL;
2641         }
2642         else if (array_Check(initial) &&
2643                  ((arrayobject*)initial)->ob_descr->typecode == 'u') {
2644             PyErr_Format(PyExc_TypeError, "cannot use a unicode array to "
2645                          "initialize an array with typecode '%c'", c);
2646             return NULL;
2647         }
2648     }
2649 
2650     if (!(initial == NULL || PyList_Check(initial)
2651           || PyByteArray_Check(initial)
2652           || PyBytes_Check(initial)
2653           || PyTuple_Check(initial)
2654           || ((c=='u') && PyUnicode_Check(initial))
2655           || (array_Check(initial)
2656               && c == ((arrayobject*)initial)->ob_descr->typecode))) {
2657         it = PyObject_GetIter(initial);
2658         if (it == NULL)
2659             return NULL;
2660         /* We set initial to NULL so that the subsequent code
2661            will create an empty array of the appropriate type
2662            and afterwards we can use array_iter_extend to populate
2663            the array.
2664         */
2665         initial = NULL;
2666     }
2667     for (descr = descriptors; descr->typecode != '\0'; descr++) {
2668         if (descr->typecode == c) {
2669             PyObject *a;
2670             Py_ssize_t len;
2671 
2672             if (initial == NULL)
2673                 len = 0;
2674             else if (PyList_Check(initial))
2675                 len = PyList_GET_SIZE(initial);
2676             else if (PyTuple_Check(initial) || array_Check(initial))
2677                 len = Py_SIZE(initial);
2678             else
2679                 len = 0;
2680 
2681             a = newarrayobject(type, len, descr);
2682             if (a == NULL)
2683                 return NULL;
2684 
2685             if (len > 0 && !array_Check(initial)) {
2686                 Py_ssize_t i;
2687                 for (i = 0; i < len; i++) {
2688                     PyObject *v =
2689                         PySequence_GetItem(initial, i);
2690                     if (v == NULL) {
2691                         Py_DECREF(a);
2692                         return NULL;
2693                     }
2694                     if (setarrayitem(a, i, v) != 0) {
2695                         Py_DECREF(v);
2696                         Py_DECREF(a);
2697                         return NULL;
2698                     }
2699                     Py_DECREF(v);
2700                 }
2701             }
2702             else if (initial != NULL && (PyByteArray_Check(initial) ||
2703                                PyBytes_Check(initial))) {
2704                 PyObject *v;
2705                 v = array_array_frombytes((arrayobject *)a,
2706                                           initial);
2707                 if (v == NULL) {
2708                     Py_DECREF(a);
2709                     return NULL;
2710                 }
2711                 Py_DECREF(v);
2712             }
2713             else if (initial != NULL && PyUnicode_Check(initial))  {
2714                 Py_UNICODE *ustr;
2715                 Py_ssize_t n;
2716 
2717                 ustr = PyUnicode_AsUnicode(initial);
2718                 if (ustr == NULL) {
2719                     PyErr_NoMemory();
2720                     Py_DECREF(a);
2721                     return NULL;
2722                 }
2723 
2724                 n = PyUnicode_GET_DATA_SIZE(initial);
2725                 if (n > 0) {
2726                     arrayobject *self = (arrayobject *)a;
2727                     char *item = self->ob_item;
2728                     item = (char *)PyMem_Realloc(item, n);
2729                     if (item == NULL) {
2730                         PyErr_NoMemory();
2731                         Py_DECREF(a);
2732                         return NULL;
2733                     }
2734                     self->ob_item = item;
2735                     Py_SIZE(self) = n / sizeof(Py_UNICODE);
2736                     memcpy(item, ustr, n);
2737                     self->allocated = Py_SIZE(self);
2738                 }
2739             }
2740             else if (initial != NULL && array_Check(initial) && len > 0) {
2741                 arrayobject *self = (arrayobject *)a;
2742                 arrayobject *other = (arrayobject *)initial;
2743                 memcpy(self->ob_item, other->ob_item, len * other->ob_descr->itemsize);
2744             }
2745             if (it != NULL) {
2746                 if (array_iter_extend((arrayobject *)a, it) == -1) {
2747                     Py_DECREF(it);
2748                     Py_DECREF(a);
2749                     return NULL;
2750                 }
2751                 Py_DECREF(it);
2752             }
2753             return a;
2754         }
2755     }
2756     PyErr_SetString(PyExc_ValueError,
2757         "bad typecode (must be b, B, u, h, H, i, I, l, L, q, Q, f or d)");
2758     return NULL;
2759 }
2760 
2761 
2762 PyDoc_STRVAR(module_doc,
2763 "This module defines an object type which can efficiently represent\n\
2764 an array of basic values: characters, integers, floating point\n\
2765 numbers.  Arrays are sequence types and behave very much like lists,\n\
2766 except that the type of objects stored in them is constrained.\n");
2767 
2768 PyDoc_STRVAR(arraytype_doc,
2769 "array(typecode [, initializer]) -> array\n\
2770 \n\
2771 Return a new array whose items are restricted by typecode, and\n\
2772 initialized from the optional initializer value, which must be a list,\n\
2773 string or iterable over elements of the appropriate type.\n\
2774 \n\
2775 Arrays represent basic values and behave very much like lists, except\n\
2776 the type of objects stored in them is constrained. The type is specified\n\
2777 at object creation time by using a type code, which is a single character.\n\
2778 The following type codes are defined:\n\
2779 \n\
2780     Type code   C Type             Minimum size in bytes \n\
2781     'b'         signed integer     1 \n\
2782     'B'         unsigned integer   1 \n\
2783     'u'         Unicode character  2 (see note) \n\
2784     'h'         signed integer     2 \n\
2785     'H'         unsigned integer   2 \n\
2786     'i'         signed integer     2 \n\
2787     'I'         unsigned integer   2 \n\
2788     'l'         signed integer     4 \n\
2789     'L'         unsigned integer   4 \n\
2790     'q'         signed integer     8 (see note) \n\
2791     'Q'         unsigned integer   8 (see note) \n\
2792     'f'         floating point     4 \n\
2793     'd'         floating point     8 \n\
2794 \n\
2795 NOTE: The 'u' typecode corresponds to Python's unicode character. On \n\
2796 narrow builds this is 2-bytes on wide builds this is 4-bytes.\n\
2797 \n\
2798 NOTE: The 'q' and 'Q' type codes are only available if the platform \n\
2799 C compiler used to build Python supports 'long long', or, on Windows, \n\
2800 '__int64'.\n\
2801 \n\
2802 Methods:\n\
2803 \n\
2804 append() -- append a new item to the end of the array\n\
2805 buffer_info() -- return information giving the current memory info\n\
2806 byteswap() -- byteswap all the items of the array\n\
2807 count() -- return number of occurrences of an object\n\
2808 extend() -- extend array by appending multiple elements from an iterable\n\
2809 fromfile() -- read items from a file object\n\
2810 fromlist() -- append items from the list\n\
2811 frombytes() -- append items from the string\n\
2812 index() -- return index of first occurrence of an object\n\
2813 insert() -- insert a new item into the array at a provided position\n\
2814 pop() -- remove and return item (default last)\n\
2815 remove() -- remove first occurrence of an object\n\
2816 reverse() -- reverse the order of the items in the array\n\
2817 tofile() -- write all items to a file object\n\
2818 tolist() -- return the array converted to an ordinary list\n\
2819 tobytes() -- return the array converted to a string\n\
2820 \n\
2821 Attributes:\n\
2822 \n\
2823 typecode -- the typecode character used to create the array\n\
2824 itemsize -- the length in bytes of one array item\n\
2825 ");
2826 
2827 static PyObject *array_iter(arrayobject *ao);
2828 
2829 static PyTypeObject Arraytype = {
2830     PyVarObject_HEAD_INIT(NULL, 0)
2831     "array.array",
2832     sizeof(arrayobject),
2833     0,
2834     (destructor)array_dealloc,                  /* tp_dealloc */
2835     0,                                          /* tp_print */
2836     0,                                          /* tp_getattr */
2837     0,                                          /* tp_setattr */
2838     0,                                          /* tp_reserved */
2839     (reprfunc)array_repr,                       /* tp_repr */
2840     0,                                          /* tp_as_number*/
2841     &array_as_sequence,                         /* tp_as_sequence*/
2842     &array_as_mapping,                          /* tp_as_mapping*/
2843     0,                                          /* tp_hash */
2844     0,                                          /* tp_call */
2845     0,                                          /* tp_str */
2846     PyObject_GenericGetAttr,                    /* tp_getattro */
2847     0,                                          /* tp_setattro */
2848     &array_as_buffer,                           /* tp_as_buffer*/
2849     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /* tp_flags */
2850     arraytype_doc,                              /* tp_doc */
2851     0,                                          /* tp_traverse */
2852     0,                                          /* tp_clear */
2853     array_richcompare,                          /* tp_richcompare */
2854     offsetof(arrayobject, weakreflist),         /* tp_weaklistoffset */
2855     (getiterfunc)array_iter,                    /* tp_iter */
2856     0,                                          /* tp_iternext */
2857     array_methods,                              /* tp_methods */
2858     0,                                          /* tp_members */
2859     array_getsets,                              /* tp_getset */
2860     0,                                          /* tp_base */
2861     0,                                          /* tp_dict */
2862     0,                                          /* tp_descr_get */
2863     0,                                          /* tp_descr_set */
2864     0,                                          /* tp_dictoffset */
2865     0,                                          /* tp_init */
2866     PyType_GenericAlloc,                        /* tp_alloc */
2867     array_new,                                  /* tp_new */
2868     PyObject_Del,                               /* tp_free */
2869 };
2870 
2871 
2872 /*********************** Array Iterator **************************/
2873 
2874 /*[clinic input]
2875 class array.arrayiterator "arrayiterobject *" "&PyArrayIter_Type"
2876 [clinic start generated code]*/
2877 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=5aefd2d74d8c8e30]*/
2878 
2879 static PyObject *
array_iter(arrayobject * ao)2880 array_iter(arrayobject *ao)
2881 {
2882     arrayiterobject *it;
2883 
2884     if (!array_Check(ao)) {
2885         PyErr_BadInternalCall();
2886         return NULL;
2887     }
2888 
2889     it = PyObject_GC_New(arrayiterobject, &PyArrayIter_Type);
2890     if (it == NULL)
2891         return NULL;
2892 
2893     Py_INCREF(ao);
2894     it->ao = ao;
2895     it->index = 0;
2896     it->getitem = ao->ob_descr->getitem;
2897     PyObject_GC_Track(it);
2898     return (PyObject *)it;
2899 }
2900 
2901 static PyObject *
arrayiter_next(arrayiterobject * it)2902 arrayiter_next(arrayiterobject *it)
2903 {
2904     arrayobject *ao;
2905 
2906     assert(it != NULL);
2907     assert(PyArrayIter_Check(it));
2908     ao = it->ao;
2909     if (ao == NULL) {
2910         return NULL;
2911     }
2912     assert(array_Check(ao));
2913     if (it->index < Py_SIZE(ao)) {
2914         return (*it->getitem)(ao, it->index++);
2915     }
2916     it->ao = NULL;
2917     Py_DECREF(ao);
2918     return NULL;
2919 }
2920 
2921 static void
arrayiter_dealloc(arrayiterobject * it)2922 arrayiter_dealloc(arrayiterobject *it)
2923 {
2924     PyObject_GC_UnTrack(it);
2925     Py_XDECREF(it->ao);
2926     PyObject_GC_Del(it);
2927 }
2928 
2929 static int
arrayiter_traverse(arrayiterobject * it,visitproc visit,void * arg)2930 arrayiter_traverse(arrayiterobject *it, visitproc visit, void *arg)
2931 {
2932     Py_VISIT(it->ao);
2933     return 0;
2934 }
2935 
2936 /*[clinic input]
2937 array.arrayiterator.__reduce__
2938 
2939 Return state information for pickling.
2940 [clinic start generated code]*/
2941 
2942 static PyObject *
array_arrayiterator___reduce___impl(arrayiterobject * self)2943 array_arrayiterator___reduce___impl(arrayiterobject *self)
2944 /*[clinic end generated code: output=7898a52e8e66e016 input=a062ea1e9951417a]*/
2945 {
2946     PyObject *func = _PyObject_GetBuiltin("iter");
2947     if (self->ao == NULL) {
2948         return Py_BuildValue("N(())", func);
2949     }
2950     return Py_BuildValue("N(O)n", func, self->ao, self->index);
2951 }
2952 
2953 /*[clinic input]
2954 array.arrayiterator.__setstate__
2955 
2956     state: object
2957     /
2958 
2959 Set state information for unpickling.
2960 [clinic start generated code]*/
2961 
2962 static PyObject *
array_arrayiterator___setstate__(arrayiterobject * self,PyObject * state)2963 array_arrayiterator___setstate__(arrayiterobject *self, PyObject *state)
2964 /*[clinic end generated code: output=397da9904e443cbe input=f47d5ceda19e787b]*/
2965 {
2966     Py_ssize_t index = PyLong_AsSsize_t(state);
2967     if (index == -1 && PyErr_Occurred())
2968         return NULL;
2969     if (index < 0)
2970         index = 0;
2971     else if (index > Py_SIZE(self->ao))
2972         index = Py_SIZE(self->ao); /* iterator exhausted */
2973     self->index = index;
2974     Py_RETURN_NONE;
2975 }
2976 
2977 static PyMethodDef arrayiter_methods[] = {
2978     ARRAY_ARRAYITERATOR___REDUCE___METHODDEF
2979     ARRAY_ARRAYITERATOR___SETSTATE___METHODDEF
2980     {NULL, NULL} /* sentinel */
2981 };
2982 
2983 static PyTypeObject PyArrayIter_Type = {
2984     PyVarObject_HEAD_INIT(NULL, 0)
2985     "arrayiterator",                        /* tp_name */
2986     sizeof(arrayiterobject),                /* tp_basicsize */
2987     0,                                      /* tp_itemsize */
2988     /* methods */
2989     (destructor)arrayiter_dealloc,              /* tp_dealloc */
2990     0,                                      /* tp_print */
2991     0,                                      /* tp_getattr */
2992     0,                                      /* tp_setattr */
2993     0,                                      /* tp_reserved */
2994     0,                                      /* tp_repr */
2995     0,                                      /* tp_as_number */
2996     0,                                      /* tp_as_sequence */
2997     0,                                      /* tp_as_mapping */
2998     0,                                      /* tp_hash */
2999     0,                                      /* tp_call */
3000     0,                                      /* tp_str */
3001     PyObject_GenericGetAttr,                /* tp_getattro */
3002     0,                                      /* tp_setattro */
3003     0,                                      /* tp_as_buffer */
3004     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3005     0,                                      /* tp_doc */
3006     (traverseproc)arrayiter_traverse,           /* tp_traverse */
3007     0,                                          /* tp_clear */
3008     0,                                      /* tp_richcompare */
3009     0,                                      /* tp_weaklistoffset */
3010     PyObject_SelfIter,                          /* tp_iter */
3011     (iternextfunc)arrayiter_next,               /* tp_iternext */
3012     arrayiter_methods,                      /* tp_methods */
3013 };
3014 
3015 
3016 /*********************** Install Module **************************/
3017 
3018 /* No functions in array module. */
3019 static PyMethodDef a_methods[] = {
3020     ARRAY__ARRAY_RECONSTRUCTOR_METHODDEF
3021     {NULL, NULL, 0, NULL}        /* Sentinel */
3022 };
3023 
3024 static int
array_modexec(PyObject * m)3025 array_modexec(PyObject *m)
3026 {
3027     char buffer[Py_ARRAY_LENGTH(descriptors)], *p;
3028     PyObject *typecodes;
3029     Py_ssize_t size = 0;
3030     const struct arraydescr *descr;
3031 
3032     if (PyType_Ready(&Arraytype) < 0)
3033         return -1;
3034     Py_TYPE(&PyArrayIter_Type) = &PyType_Type;
3035 
3036     Py_INCREF((PyObject *)&Arraytype);
3037     PyModule_AddObject(m, "ArrayType", (PyObject *)&Arraytype);
3038     Py_INCREF((PyObject *)&Arraytype);
3039     PyModule_AddObject(m, "array", (PyObject *)&Arraytype);
3040 
3041     for (descr=descriptors; descr->typecode != '\0'; descr++) {
3042         size++;
3043     }
3044 
3045     p = buffer;
3046     for (descr = descriptors; descr->typecode != '\0'; descr++) {
3047         *p++ = (char)descr->typecode;
3048     }
3049     typecodes = PyUnicode_DecodeASCII(buffer, p - buffer, NULL);
3050 
3051     PyModule_AddObject(m, "typecodes", typecodes);
3052 
3053     if (PyErr_Occurred()) {
3054         Py_DECREF(m);
3055         m = NULL;
3056     }
3057     return 0;
3058 }
3059 
3060 static PyModuleDef_Slot arrayslots[] = {
3061     {Py_mod_exec, array_modexec},
3062     {0, NULL}
3063 };
3064 
3065 
3066 static struct PyModuleDef arraymodule = {
3067     PyModuleDef_HEAD_INIT,
3068     "array",
3069     module_doc,
3070     0,
3071     a_methods,
3072     arrayslots,
3073     NULL,
3074     NULL,
3075     NULL
3076 };
3077 
3078 
3079 PyMODINIT_FUNC
PyInit_array(void)3080 PyInit_array(void)
3081 {
3082     return PyModuleDef_Init(&arraymodule);
3083 }
3084