?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Its time to stop listing (Unix, Windows) when we really mean "everything but Mac...
[python.git] / Modules / arraymodule.c
blob210ada60f72483c23b33803500866cefdd57a8f3
1 /* Array object implementation */
2
3 /* An array is a uniform list -- all items have the same type.
4 The item type is restricted to simple C types like int or float */
5
6 #define PY_SSIZE_T_CLEAN
7 #include "Python.h"
8 #include "structmember.h"
9
10 #ifdef STDC_HEADERS
11 #include <stddef.h>
12 #else /* !STDC_HEADERS */
13 #ifdef HAVE_SYS_TYPES_H
14 #include <sys/types.h> /* For size_t */
15 #endif /* HAVE_SYS_TYPES_H */
16 #endif /* !STDC_HEADERS */
17
18 struct arrayobject; /* Forward */
19
20 /* All possible arraydescr values are defined in the vector "descriptors"
21 * below. That's defined later because the appropriate get and set
22 * functions aren't visible yet.
23 */
24 struct arraydescr {
25 int typecode;
26 int itemsize;
27 PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
28 int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
29 };
30
31 typedef struct arrayobject {
32 PyObject_VAR_HEAD
33 char *ob_item;
34 Py_ssize_t allocated;
35 struct arraydescr *ob_descr;
36 PyObject *weakreflist; /* List of weak references */
37 } arrayobject;
38
39 static PyTypeObject Arraytype;
40
41 #define array_Check(op) PyObject_TypeCheck(op, &Arraytype)
42 #define array_CheckExact(op) ((op)->ob_type == &Arraytype)
43
44 static int
45 array_resize(arrayobject *self, Py_ssize_t newsize)
46 {
47 char *items;
48 size_t _new_size;
49
50 /* Bypass realloc() when a previous overallocation is large enough
51 to accommodate the newsize. If the newsize is 16 smaller than the
52 current size, then proceed with the realloc() to shrink the list.
53 */
54
55 if (self->allocated >= newsize &&
56 self->ob_size < newsize + 16 &&
57 self->ob_item != NULL) {
58 self->ob_size = newsize;
59 return 0;
60 }
61
62 /* This over-allocates proportional to the array size, making room
63 * for additional growth. The over-allocation is mild, but is
64 * enough to give linear-time amortized behavior over a long
65 * sequence of appends() in the presence of a poorly-performing
66 * system realloc().
67 * The growth pattern is: 0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
68 * Note, the pattern starts out the same as for lists but then
69 * grows at a smaller rate so that larger arrays only overallocate
70 * by about 1/16th -- this is done because arrays are presumed to be more
71 * memory critical.
72 */
73
74 _new_size = (newsize >> 4) + (self->ob_size < 8 ? 3 : 7) + newsize;
75 items = self->ob_item;
76 /* XXX The following multiplication and division does not optimize away
77 like it does for lists since the size is not known at compile time */
78 if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
79 PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
80 else
81 items = NULL;
82 if (items == NULL) {
83 PyErr_NoMemory();
84 return -1;
85 }
86 self->ob_item = items;
87 self->ob_size = newsize;
88 self->allocated = _new_size;
89 return 0;
90 }
91
92 /****************************************************************************
93 Get and Set functions for each type.
94 A Get function takes an arrayobject* and an integer index, returning the
95 array value at that index wrapped in an appropriate PyObject*.
96 A Set function takes an arrayobject, integer index, and PyObject*; sets
97 the array value at that index to the raw C data extracted from the PyObject*,
98 and returns 0 if successful, else nonzero on failure (PyObject* not of an
99 appropriate type or value).
100 Note that the basic Get and Set functions do NOT check that the index is
101 in bounds; that's the responsibility of the caller.
102 ****************************************************************************/
103
104 static PyObject *
105 c_getitem(arrayobject *ap, Py_ssize_t i)
106 {
107 return PyString_FromStringAndSize(&((char *)ap->ob_item)[i], 1);
108 }
109
110 static int
111 c_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
112 {
113 char x;
114 if (!PyArg_Parse(v, "c;array item must be char", &x))
115 return -1;
116 if (i >= 0)
117 ((char *)ap->ob_item)[i] = x;
118 return 0;
119 }
120
121 static PyObject *
122 b_getitem(arrayobject *ap, Py_ssize_t i)
123 {
124 long x = ((char *)ap->ob_item)[i];
125 if (x >= 128)
126 x -= 256;
127 return PyInt_FromLong(x);
128 }
129
130 static int
131 b_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
132 {
133 short x;
134 /* PyArg_Parse's 'b' formatter is for an unsigned char, therefore
135 must use the next size up that is signed ('h') and manually do
136 the overflow checking */
137 if (!PyArg_Parse(v, "h;array item must be integer", &x))
138 return -1;
139 else if (x < -128) {
140 PyErr_SetString(PyExc_OverflowError,
141 "signed char is less than minimum");
142 return -1;
143 }
144 else if (x > 127) {
145 PyErr_SetString(PyExc_OverflowError,
146 "signed char is greater than maximum");
147 return -1;
148 }
149 if (i >= 0)
150 ((char *)ap->ob_item)[i] = (char)x;
151 return 0;
152 }
153
154 static PyObject *
155 BB_getitem(arrayobject *ap, Py_ssize_t i)
156 {
157 long x = ((unsigned char *)ap->ob_item)[i];
158 return PyInt_FromLong(x);
159 }
160
161 static int
162 BB_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
163 {
164 unsigned char x;
165 /* 'B' == unsigned char, maps to PyArg_Parse's 'b' formatter */
166 if (!PyArg_Parse(v, "b;array item must be integer", &x))
167 return -1;
168 if (i >= 0)
169 ((char *)ap->ob_item)[i] = x;
170 return 0;
171 }
172
173 #ifdef Py_USING_UNICODE
174 static PyObject *
175 u_getitem(arrayobject *ap, Py_ssize_t i)
176 {
177 return PyUnicode_FromUnicode(&((Py_UNICODE *) ap->ob_item)[i], 1);
178 }
179
180 static int
181 u_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
182 {
183 Py_UNICODE *p;
184 Py_ssize_t len;
185
186 if (!PyArg_Parse(v, "u#;array item must be unicode character", &p, &len))
187 return -1;
188 if (len != 1) {
189 PyErr_SetString(PyExc_TypeError,
190 "array item must be unicode character");
191 return -1;
192 }
193 if (i >= 0)
194 ((Py_UNICODE *)ap->ob_item)[i] = p[0];
195 return 0;
196 }
197 #endif
198
199 static PyObject *
200 h_getitem(arrayobject *ap, Py_ssize_t i)
201 {
202 return PyInt_FromLong((long) ((short *)ap->ob_item)[i]);
203 }
204
205 static int
206 h_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
207 {
208 short x;
209 /* 'h' == signed short, maps to PyArg_Parse's 'h' formatter */
210 if (!PyArg_Parse(v, "h;array item must be integer", &x))
211 return -1;
212 if (i >= 0)
213 ((short *)ap->ob_item)[i] = x;
214 return 0;
215 }
216
217 static PyObject *
218 HH_getitem(arrayobject *ap, Py_ssize_t i)
219 {
220 return PyInt_FromLong((long) ((unsigned short *)ap->ob_item)[i]);
221 }
222
223 static int
224 HH_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
225 {
226 int x;
227 /* PyArg_Parse's 'h' formatter is for a signed short, therefore
228 must use the next size up and manually do the overflow checking */
229 if (!PyArg_Parse(v, "i;array item must be integer", &x))
230 return -1;
231 else if (x < 0) {
232 PyErr_SetString(PyExc_OverflowError,
233 "unsigned short is less than minimum");
234 return -1;
235 }
236 else if (x > USHRT_MAX) {
237 PyErr_SetString(PyExc_OverflowError,
238 "unsigned short is greater than maximum");
239 return -1;
240 }
241 if (i >= 0)
242 ((short *)ap->ob_item)[i] = (short)x;
243 return 0;
244 }
245
246 static PyObject *
247 i_getitem(arrayobject *ap, Py_ssize_t i)
248 {
249 return PyInt_FromLong((long) ((int *)ap->ob_item)[i]);
250 }
251
252 static int
253 i_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
254 {
255 int x;
256 /* 'i' == signed int, maps to PyArg_Parse's 'i' formatter */
257 if (!PyArg_Parse(v, "i;array item must be integer", &x))
258 return -1;
259 if (i >= 0)
260 ((int *)ap->ob_item)[i] = x;
261 return 0;
262 }
263
264 static PyObject *
265 II_getitem(arrayobject *ap, Py_ssize_t i)
266 {
267 return PyLong_FromUnsignedLong(
268 (unsigned long) ((unsigned int *)ap->ob_item)[i]);
269 }
270
271 static int
272 II_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
273 {
274 unsigned long x;
275 if (PyLong_Check(v)) {
276 x = PyLong_AsUnsignedLong(v);
277 if (x == (unsigned long) -1 && PyErr_Occurred())
278 return -1;
279 }
280 else {
281 long y;
282 if (!PyArg_Parse(v, "l;array item must be integer", &y))
283 return -1;
284 if (y < 0) {
285 PyErr_SetString(PyExc_OverflowError,
286 "unsigned int is less than minimum");
287 return -1;
288 }
289 x = (unsigned long)y;
290
291 }
292 if (x > UINT_MAX) {
293 PyErr_SetString(PyExc_OverflowError,
294 "unsigned int is greater than maximum");
295 return -1;
296 }
297
298 if (i >= 0)
299 ((unsigned int *)ap->ob_item)[i] = (unsigned int)x;
300 return 0;
301 }
302
303 static PyObject *
304 l_getitem(arrayobject *ap, Py_ssize_t i)
305 {
306 return PyInt_FromLong(((long *)ap->ob_item)[i]);
307 }
308
309 static int
310 l_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
311 {
312 long x;
313 if (!PyArg_Parse(v, "l;array item must be integer", &x))
314 return -1;
315 if (i >= 0)
316 ((long *)ap->ob_item)[i] = x;
317 return 0;
318 }
319
320 static PyObject *
321 LL_getitem(arrayobject *ap, Py_ssize_t i)
322 {
323 return PyLong_FromUnsignedLong(((unsigned long *)ap->ob_item)[i]);
324 }
325
326 static int
327 LL_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
328 {
329 unsigned long x;
330 if (PyLong_Check(v)) {
331 x = PyLong_AsUnsignedLong(v);
332 if (x == (unsigned long) -1 && PyErr_Occurred())
333 return -1;
334 }
335 else {
336 long y;
337 if (!PyArg_Parse(v, "l;array item must be integer", &y))
338 return -1;
339 if (y < 0) {
340 PyErr_SetString(PyExc_OverflowError,
341 "unsigned long is less than minimum");
342 return -1;
343 }
344 x = (unsigned long)y;
345
346 }
347 if (x > ULONG_MAX) {
348 PyErr_SetString(PyExc_OverflowError,
349 "unsigned long is greater than maximum");
350 return -1;
351 }
352
353 if (i >= 0)
354 ((unsigned long *)ap->ob_item)[i] = x;
355 return 0;
356 }
357
358 static PyObject *
359 f_getitem(arrayobject *ap, Py_ssize_t i)
360 {
361 return PyFloat_FromDouble((double) ((float *)ap->ob_item)[i]);
362 }
363
364 static int
365 f_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
366 {
367 float x;
368 if (!PyArg_Parse(v, "f;array item must be float", &x))
369 return -1;
370 if (i >= 0)
371 ((float *)ap->ob_item)[i] = x;
372 return 0;
373 }
374
375 static PyObject *
376 d_getitem(arrayobject *ap, Py_ssize_t i)
377 {
378 return PyFloat_FromDouble(((double *)ap->ob_item)[i]);
379 }
380
381 static int
382 d_setitem(arrayobject *ap, Py_ssize_t i, PyObject *v)
383 {
384 double x;
385 if (!PyArg_Parse(v, "d;array item must be float", &x))
386 return -1;
387 if (i >= 0)
388 ((double *)ap->ob_item)[i] = x;
389 return 0;
390 }
391
392 /* Description of types */
393 static struct arraydescr descriptors[] = {
394 {'c', sizeof(char), c_getitem, c_setitem},
395 {'b', sizeof(char), b_getitem, b_setitem},
396 {'B', sizeof(char), BB_getitem, BB_setitem},
397 #ifdef Py_USING_UNICODE
398 {'u', sizeof(Py_UNICODE), u_getitem, u_setitem},
399 #endif
400 {'h', sizeof(short), h_getitem, h_setitem},
401 {'H', sizeof(short), HH_getitem, HH_setitem},
402 {'i', sizeof(int), i_getitem, i_setitem},
403 {'I', sizeof(int), II_getitem, II_setitem},
404 {'l', sizeof(long), l_getitem, l_setitem},
405 {'L', sizeof(long), LL_getitem, LL_setitem},
406 {'f', sizeof(float), f_getitem, f_setitem},
407 {'d', sizeof(double), d_getitem, d_setitem},
408 {'\0', 0, 0, 0} /* Sentinel */
409 };
410
411 /****************************************************************************
412 Implementations of array object methods.
413 ****************************************************************************/
414
415 static PyObject *
416 newarrayobject(PyTypeObject *type, Py_ssize_t size, struct arraydescr *descr)
417 {
418 arrayobject *op;
419 size_t nbytes;
420
421 if (size < 0) {
422 PyErr_BadInternalCall();
423 return NULL;
424 }
425
426 nbytes = size * descr->itemsize;
427 /* Check for overflow */
428 if (nbytes / descr->itemsize != (size_t)size) {
429 return PyErr_NoMemory();
430 }
431 op = (arrayobject *) type->tp_alloc(type, 0);
432 if (op == NULL) {
433 return NULL;
434 }
435 op->ob_size = size;
436 if (size <= 0) {
437 op->ob_item = NULL;
438 }
439 else {
440 op->ob_item = PyMem_NEW(char, nbytes);
441 if (op->ob_item == NULL) {
442 PyObject_Del(op);
443 return PyErr_NoMemory();
444 }
445 }
446 op->ob_descr = descr;
447 op->allocated = size;
448 op->weakreflist = NULL;
449 return (PyObject *) op;
450 }
451
452 static PyObject *
453 getarrayitem(PyObject *op, Py_ssize_t i)
454 {
455 register arrayobject *ap;
456 assert(array_Check(op));
457 ap = (arrayobject *)op;
458 assert(i>=0 && i<ap->ob_size);
459 return (*ap->ob_descr->getitem)(ap, i);
460 }
461
462 static int
463 ins1(arrayobject *self, Py_ssize_t where, PyObject *v)
464 {
465 char *items;
466 Py_ssize_t n = self->ob_size;
467 if (v == NULL) {
468 PyErr_BadInternalCall();
469 return -1;
470 }
471 if ((*self->ob_descr->setitem)(self, -1, v) < 0)
472 return -1;
473
474 if (array_resize(self, n+1) == -1)
475 return -1;
476 items = self->ob_item;
477 if (where < 0) {
478 where += n;
479 if (where < 0)
480 where = 0;
481 }
482 if (where > n)
483 where = n;
484 /* appends don't need to call memmove() */
485 if (where != n)
486 memmove(items + (where+1)*self->ob_descr->itemsize,
487 items + where*self->ob_descr->itemsize,
488 (n-where)*self->ob_descr->itemsize);
489 return (*self->ob_descr->setitem)(self, where, v);
490 }
491
492 /* Methods */
493
494 static void
495 array_dealloc(arrayobject *op)
496 {
497 if (op->weakreflist != NULL)
498 PyObject_ClearWeakRefs((PyObject *) op);
499 if (op->ob_item != NULL)
500 PyMem_DEL(op->ob_item);
501 op->ob_type->tp_free((PyObject *)op);
502 }
503
504 static PyObject *
505 array_richcompare(PyObject *v, PyObject *w, int op)
506 {
507 arrayobject *va, *wa;
508 PyObject *vi = NULL;
509 PyObject *wi = NULL;
510 Py_ssize_t i, k;
511 PyObject *res;
512
513 if (!array_Check(v) || !array_Check(w)) {
514 Py_INCREF(Py_NotImplemented);
515 return Py_NotImplemented;
516 }
517
518 va = (arrayobject *)v;
519 wa = (arrayobject *)w;
520
521 if (va->ob_size != wa->ob_size && (op == Py_EQ || op == Py_NE)) {
522 /* Shortcut: if the lengths differ, the arrays differ */
523 if (op == Py_EQ)
524 res = Py_False;
525 else
526 res = Py_True;
527 Py_INCREF(res);
528 return res;
529 }
530
531 /* Search for the first index where items are different */
532 k = 1;
533 for (i = 0; i < va->ob_size && i < wa->ob_size; i++) {
534 vi = getarrayitem(v, i);
535 wi = getarrayitem(w, i);
536 if (vi == NULL || wi == NULL) {
537 Py_XDECREF(vi);
538 Py_XDECREF(wi);
539 return NULL;
540 }
541 k = PyObject_RichCompareBool(vi, wi, Py_EQ);
542 if (k == 0)
543 break; /* Keeping vi and wi alive! */
544 Py_DECREF(vi);
545 Py_DECREF(wi);
546 if (k < 0)
547 return NULL;
548 }
549
550 if (k) {
551 /* No more items to compare -- compare sizes */
552 Py_ssize_t vs = va->ob_size;
553 Py_ssize_t ws = wa->ob_size;
554 int cmp;
555 switch (op) {
556 case Py_LT: cmp = vs < ws; break;
557 case Py_LE: cmp = vs <= ws; break;
558 case Py_EQ: cmp = vs == ws; break;
559 case Py_NE: cmp = vs != ws; break;
560 case Py_GT: cmp = vs > ws; break;
561 case Py_GE: cmp = vs >= ws; break;
562 default: return NULL; /* cannot happen */
563 }
564 if (cmp)
565 res = Py_True;
566 else
567 res = Py_False;
568 Py_INCREF(res);
569 return res;
570 }
571
572 /* We have an item that differs. First, shortcuts for EQ/NE */
573 if (op == Py_EQ) {
574 Py_INCREF(Py_False);
575 res = Py_False;
576 }
577 else if (op == Py_NE) {
578 Py_INCREF(Py_True);
579 res = Py_True;
580 }
581 else {
582 /* Compare the final item again using the proper operator */
583 res = PyObject_RichCompare(vi, wi, op);
584 }
585 Py_DECREF(vi);
586 Py_DECREF(wi);
587 return res;
588 }
589
590 static Py_ssize_t
591 array_length(arrayobject *a)
592 {
593 return a->ob_size;
594 }
595
596 static PyObject *
597 array_item(arrayobject *a, Py_ssize_t i)
598 {
599 if (i < 0 || i >= a->ob_size) {
600 PyErr_SetString(PyExc_IndexError, "array index out of range");
601 return NULL;
602 }
603 return getarrayitem((PyObject *)a, i);
604 }
605
606 static PyObject *
607 array_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
608 {
609 arrayobject *np;
610 if (ilow < 0)
611 ilow = 0;
612 else if (ilow > a->ob_size)
613 ilow = a->ob_size;
614 if (ihigh < 0)
615 ihigh = 0;
616 if (ihigh < ilow)
617 ihigh = ilow;
618 else if (ihigh > a->ob_size)
619 ihigh = a->ob_size;
620 np = (arrayobject *) newarrayobject(&Arraytype, ihigh - ilow, a->ob_descr);
621 if (np == NULL)
622 return NULL;
623 memcpy(np->ob_item, a->ob_item + ilow * a->ob_descr->itemsize,
624 (ihigh-ilow) * a->ob_descr->itemsize);
625 return (PyObject *)np;
626 }
627
628 static PyObject *
629 array_copy(arrayobject *a, PyObject *unused)
630 {
631 return array_slice(a, 0, a->ob_size);
632 }
633
634 PyDoc_STRVAR(copy_doc,
635 "copy(array)\n\
636 \n\
637 Return a copy of the array.");
638
639 static PyObject *
640 array_concat(arrayobject *a, PyObject *bb)
641 {
642 Py_ssize_t size;
643 arrayobject *np;
644 if (!array_Check(bb)) {
645 PyErr_Format(PyExc_TypeError,
646 "can only append array (not \"%.200s\") to array",
647 bb->ob_type->tp_name);
648 return NULL;
649 }
650 #define b ((arrayobject *)bb)
651 if (a->ob_descr != b->ob_descr) {
652 PyErr_BadArgument();
653 return NULL;
654 }
655 size = a->ob_size + b->ob_size;
656 np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
657 if (np == NULL) {
658 return NULL;
659 }
660 memcpy(np->ob_item, a->ob_item, a->ob_size*a->ob_descr->itemsize);
661 memcpy(np->ob_item + a->ob_size*a->ob_descr->itemsize,
662 b->ob_item, b->ob_size*b->ob_descr->itemsize);
663 return (PyObject *)np;
664 #undef b
665 }
666
667 static PyObject *
668 array_repeat(arrayobject *a, Py_ssize_t n)
669 {
670 Py_ssize_t i;
671 Py_ssize_t size;
672 arrayobject *np;
673 char *p;
674 Py_ssize_t nbytes;
675 if (n < 0)
676 n = 0;
677 size = a->ob_size * n;
678 np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
679 if (np == NULL)
680 return NULL;
681 p = np->ob_item;
682 nbytes = a->ob_size * a->ob_descr->itemsize;
683 for (i = 0; i < n; i++) {
684 memcpy(p, a->ob_item, nbytes);
685 p += nbytes;
686 }
687 return (PyObject *) np;
688 }
689
690 static int
691 array_ass_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
692 {
693 char *item;
694 Py_ssize_t n; /* Size of replacement array */
695 Py_ssize_t d; /* Change in size */
696 #define b ((arrayobject *)v)
697 if (v == NULL)
698 n = 0;
699 else if (array_Check(v)) {
700 n = b->ob_size;
701 if (a == b) {
702 /* Special case "a[i:j] = a" -- copy b first */
703 int ret;
704 v = array_slice(b, 0, n);
705 if (!v)
706 return -1;
707 ret = array_ass_slice(a, ilow, ihigh, v);
708 Py_DECREF(v);
709 return ret;
710 }
711 if (b->ob_descr != a->ob_descr) {
712 PyErr_BadArgument();
713 return -1;
714 }
715 }
716 else {
717 PyErr_Format(PyExc_TypeError,
718 "can only assign array (not \"%.200s\") to array slice",
719 v->ob_type->tp_name);
720 return -1;
721 }
722 if (ilow < 0)
723 ilow = 0;
724 else if (ilow > a->ob_size)
725 ilow = a->ob_size;
726 if (ihigh < 0)
727 ihigh = 0;
728 if (ihigh < ilow)
729 ihigh = ilow;
730 else if (ihigh > a->ob_size)
731 ihigh = a->ob_size;
732 item = a->ob_item;
733 d = n - (ihigh-ilow);
734 if (d < 0) { /* Delete -d items */
735 memmove(item + (ihigh+d)*a->ob_descr->itemsize,
736 item + ihigh*a->ob_descr->itemsize,
737 (a->ob_size-ihigh)*a->ob_descr->itemsize);
738 a->ob_size += d;
739 PyMem_RESIZE(item, char, a->ob_size*a->ob_descr->itemsize);
740 /* Can't fail */
741 a->ob_item = item;
742 a->allocated = a->ob_size;
743 }
744 else if (d > 0) { /* Insert d items */
745 PyMem_RESIZE(item, char,
746 (a->ob_size + d)*a->ob_descr->itemsize);
747 if (item == NULL) {
748 PyErr_NoMemory();
749 return -1;
750 }
751 memmove(item + (ihigh+d)*a->ob_descr->itemsize,
752 item + ihigh*a->ob_descr->itemsize,
753 (a->ob_size-ihigh)*a->ob_descr->itemsize);
754 a->ob_item = item;
755 a->ob_size += d;
756 a->allocated = a->ob_size;
757 }
758 if (n > 0)
759 memcpy(item + ilow*a->ob_descr->itemsize, b->ob_item,
760 n*b->ob_descr->itemsize);
761 return 0;
762 #undef b
763 }
764
765 static int
766 array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)
767 {
768 if (i < 0 || i >= a->ob_size) {
769 PyErr_SetString(PyExc_IndexError,
770 "array assignment index out of range");
771 return -1;
772 }
773 if (v == NULL)
774 return array_ass_slice(a, i, i+1, v);
775 return (*a->ob_descr->setitem)(a, i, v);
776 }
777
778 static int
779 setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)
780 {
781 assert(array_Check(a));
782 return array_ass_item((arrayobject *)a, i, v);
783 }
784
785 static int
786 array_iter_extend(arrayobject *self, PyObject *bb)
787 {
788 PyObject *it, *v;
789
790 it = PyObject_GetIter(bb);
791 if (it == NULL)
792 return -1;
793
794 while ((v = PyIter_Next(it)) != NULL) {
795 if (ins1(self, (int) self->ob_size, v) != 0) {
796 Py_DECREF(v);
797 Py_DECREF(it);
798 return -1;
799 }
800 Py_DECREF(v);
801 }
802 Py_DECREF(it);
803 if (PyErr_Occurred())
804 return -1;
805 return 0;
806 }
807
808 static int
809 array_do_extend(arrayobject *self, PyObject *bb)
810 {
811 Py_ssize_t size;
812
813 if (!array_Check(bb))
814 return array_iter_extend(self, bb);
815 #define b ((arrayobject *)bb)
816 if (self->ob_descr != b->ob_descr) {
817 PyErr_SetString(PyExc_TypeError,
818 "can only extend with array of same kind");
819 return -1;
820 }
821 size = self->ob_size + b->ob_size;
822 PyMem_RESIZE(self->ob_item, char, size*self->ob_descr->itemsize);
823 if (self->ob_item == NULL) {
824 PyObject_Del(self);
825 PyErr_NoMemory();
826 return -1;
827 }
828 memcpy(self->ob_item + self->ob_size*self->ob_descr->itemsize,
829 b->ob_item, b->ob_size*b->ob_descr->itemsize);
830 self->ob_size = size;
831 self->allocated = size;
832
833 return 0;
834 #undef b
835 }
836
837 static PyObject *
838 array_inplace_concat(arrayobject *self, PyObject *bb)
839 {
840 if (!array_Check(bb)) {
841 PyErr_Format(PyExc_TypeError,
842 "can only extend array with array (not \"%.200s\")",
843 bb->ob_type->tp_name);
844 return NULL;
845 }
846 if (array_do_extend(self, bb) == -1)
847 return NULL;
848 Py_INCREF(self);
849 return (PyObject *)self;
850 }
851
852 static PyObject *
853 array_inplace_repeat(arrayobject *self, Py_ssize_t n)
854 {
855 char *items, *p;
856 Py_ssize_t size, i;
857
858 if (self->ob_size > 0) {
859 if (n < 0)
860 n = 0;
861 items = self->ob_item;
862 size = self->ob_size * self->ob_descr->itemsize;
863 if (n == 0) {
864 PyMem_FREE(items);
865 self->ob_item = NULL;
866 self->ob_size = 0;
867 self->allocated = 0;
868 }
869 else {
870 PyMem_Resize(items, char, n * size);
871 if (items == NULL)
872 return PyErr_NoMemory();
873 p = items;
874 for (i = 1; i < n; i++) {
875 p += size;
876 memcpy(p, items, size);
877 }
878 self->ob_item = items;
879 self->ob_size *= n;
880 self->allocated = self->ob_size;
881 }
882 }
883 Py_INCREF(self);
884 return (PyObject *)self;
885 }
886
887
888 static PyObject *
889 ins(arrayobject *self, Py_ssize_t where, PyObject *v)
890 {
891 if (ins1(self, where, v) != 0)
892 return NULL;
893 Py_INCREF(Py_None);
894 return Py_None;
895 }
896
897 static PyObject *
898 array_count(arrayobject *self, PyObject *v)
899 {
900 Py_ssize_t count = 0;
901 Py_ssize_t i;
902
903 for (i = 0; i < self->ob_size; i++) {
904 PyObject *selfi = getarrayitem((PyObject *)self, i);
905 int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
906 Py_DECREF(selfi);
907 if (cmp > 0)
908 count++;
909 else if (cmp < 0)
910 return NULL;
911 }
912 return PyInt_FromSsize_t(count);
913 }
914
915 PyDoc_STRVAR(count_doc,
916 "count(x)\n\
917 \n\
918 Return number of occurences of x in the array.");
919
920 static PyObject *
921 array_index(arrayobject *self, PyObject *v)
922 {
923 Py_ssize_t i;
924
925 for (i = 0; i < self->ob_size; i++) {
926 PyObject *selfi = getarrayitem((PyObject *)self, i);
927 int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
928 Py_DECREF(selfi);
929 if (cmp > 0) {
930 return PyInt_FromLong((long)i);
931 }
932 else if (cmp < 0)
933 return NULL;
934 }
935 PyErr_SetString(PyExc_ValueError, "array.index(x): x not in list");
936 return NULL;
937 }
938
939 PyDoc_STRVAR(index_doc,
940 "index(x)\n\
941 \n\
942 Return index of first occurence of x in the array.");
943
944 static int
945 array_contains(arrayobject *self, PyObject *v)
946 {
947 Py_ssize_t i;
948 int cmp;
949
950 for (i = 0, cmp = 0 ; cmp == 0 && i < self->ob_size; i++) {
951 PyObject *selfi = getarrayitem((PyObject *)self, i);
952 cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
953 Py_DECREF(selfi);
954 }
955 return cmp;
956 }
957
958 static PyObject *
959 array_remove(arrayobject *self, PyObject *v)
960 {
961 int i;
962
963 for (i = 0; i < self->ob_size; i++) {
964 PyObject *selfi = getarrayitem((PyObject *)self,i);
965 int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
966 Py_DECREF(selfi);
967 if (cmp > 0) {
968 if (array_ass_slice(self, i, i+1,
969 (PyObject *)NULL) != 0)
970 return NULL;
971 Py_INCREF(Py_None);
972 return Py_None;
973 }
974 else if (cmp < 0)
975 return NULL;
976 }
977 PyErr_SetString(PyExc_ValueError, "array.remove(x): x not in list");
978 return NULL;
979 }
980
981 PyDoc_STRVAR(remove_doc,
982 "remove(x)\n\
983 \n\
984 Remove the first occurence of x in the array.");
985
986 static PyObject *
987 array_pop(arrayobject *self, PyObject *args)
988 {
989 Py_ssize_t i = -1;
990 PyObject *v;
991 if (!PyArg_ParseTuple(args, "|n:pop", &i))
992 return NULL;
993 if (self->ob_size == 0) {
994 /* Special-case most common failure cause */
995 PyErr_SetString(PyExc_IndexError, "pop from empty array");
996 return NULL;
997 }
998 if (i < 0)
999 i += self->ob_size;
1000 if (i < 0 || i >= self->ob_size) {
1001 PyErr_SetString(PyExc_IndexError, "pop index out of range");
1002 return NULL;
1003 }
1004 v = getarrayitem((PyObject *)self,i);
1005 if (array_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
1006 Py_DECREF(v);
1007 return NULL;
1008 }
1009 return v;
1010 }
1011
1012 PyDoc_STRVAR(pop_doc,
1013 "pop([i])\n\
1014 \n\
1015 Return the i-th element and delete it from the array. i defaults to -1.");
1016
1017 static PyObject *
1018 array_extend(arrayobject *self, PyObject *bb)
1019 {
1020 if (array_do_extend(self, bb) == -1)
1021 return NULL;
1022 Py_INCREF(Py_None);
1023 return Py_None;
1024 }
1025
1026 PyDoc_STRVAR(extend_doc,
1027 "extend(array or iterable)\n\
1028 \n\
1029 Append items to the end of the array.");
1030
1031 static PyObject *
1032 array_insert(arrayobject *self, PyObject *args)
1033 {
1034 Py_ssize_t i;
1035 PyObject *v;
1036 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
1037 return NULL;
1038 return ins(self, i, v);
1039 }
1040
1041 PyDoc_STRVAR(insert_doc,
1042 "insert(i,x)\n\
1043 \n\
1044 Insert a new item x into the array before position i.");
1045
1046
1047 static PyObject *
1048 array_buffer_info(arrayobject *self, PyObject *unused)
1049 {
1050 PyObject* retval = NULL;
1051 retval = PyTuple_New(2);
1052 if (!retval)
1053 return NULL;
1054
1055 PyTuple_SET_ITEM(retval, 0, PyLong_FromVoidPtr(self->ob_item));
1056 PyTuple_SET_ITEM(retval, 1, PyInt_FromLong((long)(self->ob_size)));
1057
1058 return retval;
1059 }
1060
1061 PyDoc_STRVAR(buffer_info_doc,
1062 "buffer_info() -> (address, length)\n\
1063 \n\
1064 Return a tuple (address, length) giving the current memory address and\n\
1065 the length in items of the buffer used to hold array's contents\n\
1066 The length should be multiplied by the itemsize attribute to calculate\n\
1067 the buffer length in bytes.");
1068
1069
1070 static PyObject *
1071 array_append(arrayobject *self, PyObject *v)
1072 {
1073 return ins(self, (int) self->ob_size, v);
1074 }
1075
1076 PyDoc_STRVAR(append_doc,
1077 "append(x)\n\
1078 \n\
1079 Append new value x to the end of the array.");
1080
1081
1082 static PyObject *
1083 array_byteswap(arrayobject *self, PyObject *unused)
1084 {
1085 char *p;
1086 Py_ssize_t i;
1087
1088 switch (self->ob_descr->itemsize) {
1089 case 1:
1090 break;
1091 case 2:
1092 for (p = self->ob_item, i = self->ob_size; --i >= 0; p += 2) {
1093 char p0 = p[0];
1094 p[0] = p[1];
1095 p[1] = p0;
1096 }
1097 break;
1098 case 4:
1099 for (p = self->ob_item, i = self->ob_size; --i >= 0; p += 4) {
1100 char p0 = p[0];
1101 char p1 = p[1];
1102 p[0] = p[3];
1103 p[1] = p[2];
1104 p[2] = p1;
1105 p[3] = p0;
1106 }
1107 break;
1108 case 8:
1109 for (p = self->ob_item, i = self->ob_size; --i >= 0; p += 8) {
1110 char p0 = p[0];
1111 char p1 = p[1];
1112 char p2 = p[2];
1113 char p3 = p[3];
1114 p[0] = p[7];
1115 p[1] = p[6];
1116 p[2] = p[5];
1117 p[3] = p[4];
1118 p[4] = p3;
1119 p[5] = p2;
1120 p[6] = p1;
1121 p[7] = p0;
1122 }
1123 break;
1124 default:
1125 PyErr_SetString(PyExc_RuntimeError,
1126 "don't know how to byteswap this array type");
1127 return NULL;
1128 }
1129 Py_INCREF(Py_None);
1130 return Py_None;
1131 }
1132
1133 PyDoc_STRVAR(byteswap_doc,
1134 "byteswap()\n\
1135 \n\
1136 Byteswap all items of the array. If the items in the array are not 1, 2,\n\
1137 4, or 8 bytes in size, RuntimeError is raised.");
1138
1139 static PyObject *
1140 array_reduce(arrayobject *array)
1141 {
1142 PyObject *dict, *result;
1143
1144 dict = PyObject_GetAttrString((PyObject *)array, "__dict__");
1145 if (dict == NULL) {
1146 PyErr_Clear();
1147 dict = Py_None;
1148 Py_INCREF(dict);
1149 }
1150 result = Py_BuildValue("O(cs#)O",
1151 array->ob_type,
1152 array->ob_descr->typecode,
1153 array->ob_item,
1154 array->ob_size * array->ob_descr->itemsize,
1155 dict);
1156 Py_DECREF(dict);
1157 return result;
1158 }
1159
1160 PyDoc_STRVAR(array_doc, "Return state information for pickling.");
1161
1162 static PyObject *
1163 array_reverse(arrayobject *self, PyObject *unused)
1164 {
1165 register Py_ssize_t itemsize = self->ob_descr->itemsize;
1166 register char *p, *q;
1167 /* little buffer to hold items while swapping */
1168 char tmp[256]; /* 8 is probably enough -- but why skimp */
1169 assert((size_t)itemsize <= sizeof(tmp));
1170
1171 if (self->ob_size > 1) {
1172 for (p = self->ob_item,
1173 q = self->ob_item + (self->ob_size - 1)*itemsize;
1174 p < q;
1175 p += itemsize, q -= itemsize) {
1176 /* memory areas guaranteed disjoint, so memcpy
1177 * is safe (& memmove may be slower).
1178 */
1179 memcpy(tmp, p, itemsize);
1180 memcpy(p, q, itemsize);
1181 memcpy(q, tmp, itemsize);
1182 }
1183 }
1184
1185 Py_INCREF(Py_None);
1186 return Py_None;
1187 }
1188
1189 PyDoc_STRVAR(reverse_doc,
1190 "reverse()\n\
1191 \n\
1192 Reverse the order of the items in the array.");
1193
1194 static PyObject *
1195 array_fromfile(arrayobject *self, PyObject *args)
1196 {
1197 PyObject *f;
1198 Py_ssize_t n;
1199 FILE *fp;
1200 if (!PyArg_ParseTuple(args, "On:fromfile", &f, &n))
1201 return NULL;
1202 fp = PyFile_AsFile(f);
1203 if (fp == NULL) {
1204 PyErr_SetString(PyExc_TypeError, "arg1 must be open file");
1205 return NULL;
1206 }
1207 if (n > 0) {
1208 char *item = self->ob_item;
1209 Py_ssize_t itemsize = self->ob_descr->itemsize;
1210 size_t nread;
1211 Py_ssize_t newlength;
1212 size_t newbytes;
1213 /* Be careful here about overflow */
1214 if ((newlength = self->ob_size + n) <= 0 ||
1215 (newbytes = newlength * itemsize) / itemsize !=
1216 (size_t)newlength)
1217 goto nomem;
1218 PyMem_RESIZE(item, char, newbytes);
1219 if (item == NULL) {
1220 nomem:
1221 PyErr_NoMemory();
1222 return NULL;
1223 }
1224 self->ob_item = item;
1225 self->ob_size += n;
1226 self->allocated = self->ob_size;
1227 nread = fread(item + (self->ob_size - n) * itemsize,
1228 itemsize, n, fp);
1229 if (nread < (size_t)n) {
1230 self->ob_size -= (n - nread);
1231 PyMem_RESIZE(item, char, self->ob_size*itemsize);
1232 self->ob_item = item;
1233 self->allocated = self->ob_size;
1234 PyErr_SetString(PyExc_EOFError,
1235 "not enough items in file");
1236 return NULL;
1237 }
1238 }
1239 Py_INCREF(Py_None);
1240 return Py_None;
1241 }
1242
1243 PyDoc_STRVAR(fromfile_doc,
1244 "fromfile(f, n)\n\
1245 \n\
1246 Read n objects from the file object f and append them to the end of the\n\
1247 array. Also called as read.");
1248
1249
1250 static PyObject *
1251 array_tofile(arrayobject *self, PyObject *f)
1252 {
1253 FILE *fp;
1254
1255 fp = PyFile_AsFile(f);
1256 if (fp == NULL) {
1257 PyErr_SetString(PyExc_TypeError, "arg must be open file");
1258 return NULL;
1259 }
1260 if (self->ob_size > 0) {
1261 if (fwrite(self->ob_item, self->ob_descr->itemsize,
1262 self->ob_size, fp) != (size_t)self->ob_size) {
1263 PyErr_SetFromErrno(PyExc_IOError);
1264 clearerr(fp);
1265 return NULL;
1266 }
1267 }
1268 Py_INCREF(Py_None);
1269 return Py_None;
1270 }
1271
1272 PyDoc_STRVAR(tofile_doc,
1273 "tofile(f)\n\
1274 \n\
1275 Write all items (as machine values) to the file object f. Also called as\n\
1276 write.");
1277
1278
1279 static PyObject *
1280 array_fromlist(arrayobject *self, PyObject *list)
1281 {
1282 Py_ssize_t n;
1283 Py_ssize_t itemsize = self->ob_descr->itemsize;
1284
1285 if (!PyList_Check(list)) {
1286 PyErr_SetString(PyExc_TypeError, "arg must be list");
1287 return NULL;
1288 }
1289 n = PyList_Size(list);
1290 if (n > 0) {
1291 char *item = self->ob_item;
1292 Py_ssize_t i;
1293 PyMem_RESIZE(item, char, (self->ob_size + n) * itemsize);
1294 if (item == NULL) {
1295 PyErr_NoMemory();
1296 return NULL;
1297 }
1298 self->ob_item = item;
1299 self->ob_size += n;
1300 self->allocated = self->ob_size;
1301 for (i = 0; i < n; i++) {
1302 PyObject *v = PyList_GetItem(list, i);
1303 if ((*self->ob_descr->setitem)(self,
1304 self->ob_size - n + i, v) != 0) {
1305 self->ob_size -= n;
1306 PyMem_RESIZE(item, char,
1307 self->ob_size * itemsize);
1308 self->ob_item = item;
1309 self->allocated = self->ob_size;
1310 return NULL;
1311 }
1312 }
1313 }
1314 Py_INCREF(Py_None);
1315 return Py_None;
1316 }
1317
1318 PyDoc_STRVAR(fromlist_doc,
1319 "fromlist(list)\n\
1320 \n\
1321 Append items to array from list.");
1322
1323
1324 static PyObject *
1325 array_tolist(arrayobject *self, PyObject *unused)
1326 {
1327 PyObject *list = PyList_New(self->ob_size);
1328 Py_ssize_t i;
1329
1330 if (list == NULL)
1331 return NULL;
1332 for (i = 0; i < self->ob_size; i++) {
1333 PyObject *v = getarrayitem((PyObject *)self, i);
1334 if (v == NULL) {
1335 Py_DECREF(list);
1336 return NULL;
1337 }
1338 PyList_SetItem(list, i, v);
1339 }
1340 return list;
1341 }
1342
1343 PyDoc_STRVAR(tolist_doc,
1344 "tolist() -> list\n\
1345 \n\
1346 Convert array to an ordinary list with the same items.");
1347
1348
1349 static PyObject *
1350 array_fromstring(arrayobject *self, PyObject *args)
1351 {
1352 char *str;
1353 Py_ssize_t n;
1354 int itemsize = self->ob_descr->itemsize;
1355 if (!PyArg_ParseTuple(args, "s#:fromstring", &str, &n))
1356 return NULL;
1357 if (n % itemsize != 0) {
1358 PyErr_SetString(PyExc_ValueError,
1359 "string length not a multiple of item size");
1360 return NULL;
1361 }
1362 n = n / itemsize;
1363 if (n > 0) {
1364 char *item = self->ob_item;
1365 PyMem_RESIZE(item, char, (self->ob_size + n) * itemsize);
1366 if (item == NULL) {
1367 PyErr_NoMemory();
1368 return NULL;
1369 }
1370 self->ob_item = item;
1371 self->ob_size += n;
1372 self->allocated = self->ob_size;
1373 memcpy(item + (self->ob_size - n) * itemsize,
1374 str, itemsize*n);
1375 }
1376 Py_INCREF(Py_None);
1377 return Py_None;
1378 }
1379
1380 PyDoc_STRVAR(fromstring_doc,
1381 "fromstring(string)\n\
1382 \n\
1383 Appends items from the string, interpreting it as an array of machine\n\
1384 values,as if it had been read from a file using the fromfile() method).");
1385
1386
1387 static PyObject *
1388 array_tostring(arrayobject *self, PyObject *unused)
1389 {
1390 return PyString_FromStringAndSize(self->ob_item,
1391 self->ob_size * self->ob_descr->itemsize);
1392 }
1393
1394 PyDoc_STRVAR(tostring_doc,
1395 "tostring() -> string\n\
1396 \n\
1397 Convert the array to an array of machine values and return the string\n\
1398 representation.");
1399
1400
1401
1402 #ifdef Py_USING_UNICODE
1403 static PyObject *
1404 array_fromunicode(arrayobject *self, PyObject *args)
1405 {
1406 Py_UNICODE *ustr;
1407 Py_ssize_t n;
1408
1409 if (!PyArg_ParseTuple(args, "u#:fromunicode", &ustr, &n))
1410 return NULL;
1411 if (self->ob_descr->typecode != 'u') {
1412 PyErr_SetString(PyExc_ValueError,
1413 "fromunicode() may only be called on "
1414 "type 'u' arrays");
1415 return NULL;
1416 }
1417 if (n > 0) {
1418 Py_UNICODE *item = (Py_UNICODE *) self->ob_item;
1419 PyMem_RESIZE(item, Py_UNICODE, self->ob_size + n);
1420 if (item == NULL) {
1421 PyErr_NoMemory();
1422 return NULL;
1423 }
1424 self->ob_item = (char *) item;
1425 self->ob_size += n;
1426 self->allocated = self->ob_size;
1427 memcpy(item + self->ob_size - n,
1428 ustr, n * sizeof(Py_UNICODE));
1429 }
1430
1431 Py_INCREF(Py_None);
1432 return Py_None;
1433 }
1434
1435 PyDoc_STRVAR(fromunicode_doc,
1436 "fromunicode(ustr)\n\
1437 \n\
1438 Extends this array with data from the unicode string ustr.\n\
1439 The array must be a type 'u' array; otherwise a ValueError\n\
1440 is raised. Use array.fromstring(ustr.decode(...)) to\n\
1441 append Unicode data to an array of some other type.");
1442
1443
1444 static PyObject *
1445 array_tounicode(arrayobject *self, PyObject *unused)
1446 {
1447 if (self->ob_descr->typecode != 'u') {
1448 PyErr_SetString(PyExc_ValueError,
1449 "tounicode() may only be called on type 'u' arrays");
1450 return NULL;
1451 }
1452 return PyUnicode_FromUnicode((Py_UNICODE *) self->ob_item, self->ob_size);
1453 }
1454
1455 PyDoc_STRVAR(tounicode_doc,
1456 "tounicode() -> unicode\n\
1457 \n\
1458 Convert the array to a unicode string. The array must be\n\
1459 a type 'u' array; otherwise a ValueError is raised. Use\n\
1460 array.tostring().decode() to obtain a unicode string from\n\
1461 an array of some other type.");
1462
1463 #endif /* Py_USING_UNICODE */
1464
1465
1466 static PyObject *
1467 array_get_typecode(arrayobject *a, void *closure)
1468 {
1469 char tc = a->ob_descr->typecode;
1470 return PyString_FromStringAndSize(&tc, 1);
1471 }
1472
1473 static PyObject *
1474 array_get_itemsize(arrayobject *a, void *closure)
1475 {
1476 return PyInt_FromLong((long)a->ob_descr->itemsize);
1477 }
1478
1479 static PyGetSetDef array_getsets [] = {
1480 {"typecode", (getter) array_get_typecode, NULL,
1481 "the typecode character used to create the array"},
1482 {"itemsize", (getter) array_get_itemsize, NULL,
1483 "the size, in bytes, of one array item"},
1484 {NULL}
1485 };
1486
1487 PyMethodDef array_methods[] = {
1488 {"append", (PyCFunction)array_append, METH_O,
1489 append_doc},
1490 {"buffer_info", (PyCFunction)array_buffer_info, METH_NOARGS,
1491 buffer_info_doc},
1492 {"byteswap", (PyCFunction)array_byteswap, METH_NOARGS,
1493 byteswap_doc},
1494 {"__copy__", (PyCFunction)array_copy, METH_NOARGS,
1495 copy_doc},
1496 {"count", (PyCFunction)array_count, METH_O,
1497 count_doc},
1498 {"__deepcopy__",(PyCFunction)array_copy, METH_O,
1499 copy_doc},
1500 {"extend", (PyCFunction)array_extend, METH_O,
1501 extend_doc},
1502 {"fromfile", (PyCFunction)array_fromfile, METH_VARARGS,
1503 fromfile_doc},
1504 {"fromlist", (PyCFunction)array_fromlist, METH_O,
1505 fromlist_doc},
1506 {"fromstring", (PyCFunction)array_fromstring, METH_VARARGS,
1507 fromstring_doc},
1508 #ifdef Py_USING_UNICODE
1509 {"fromunicode", (PyCFunction)array_fromunicode, METH_VARARGS,
1510 fromunicode_doc},
1511 #endif
1512 {"index", (PyCFunction)array_index, METH_O,
1513 index_doc},
1514 {"insert", (PyCFunction)array_insert, METH_VARARGS,
1515 insert_doc},
1516 {"pop", (PyCFunction)array_pop, METH_VARARGS,
1517 pop_doc},
1518 {"read", (PyCFunction)array_fromfile, METH_VARARGS,
1519 fromfile_doc},
1520 {"__reduce__", (PyCFunction)array_reduce, METH_NOARGS,
1521 array_doc},
1522 {"remove", (PyCFunction)array_remove, METH_O,
1523 remove_doc},
1524 {"reverse", (PyCFunction)array_reverse, METH_NOARGS,
1525 reverse_doc},
1526 /* {"sort", (PyCFunction)array_sort, METH_VARARGS,
1527 sort_doc},*/
1528 {"tofile", (PyCFunction)array_tofile, METH_O,
1529 tofile_doc},
1530 {"tolist", (PyCFunction)array_tolist, METH_NOARGS,
1531 tolist_doc},
1532 {"tostring", (PyCFunction)array_tostring, METH_NOARGS,
1533 tostring_doc},
1534 #ifdef Py_USING_UNICODE
1535 {"tounicode", (PyCFunction)array_tounicode, METH_NOARGS,
1536 tounicode_doc},
1537 #endif
1538 {"write", (PyCFunction)array_tofile, METH_O,
1539 tofile_doc},
1540 {NULL, NULL} /* sentinel */
1541 };
1542
1543 static PyObject *
1544 array_repr(arrayobject *a)
1545 {
1546 char buf[256], typecode;
1547 PyObject *s, *t, *v = NULL;
1548 Py_ssize_t len;
1549
1550 len = a->ob_size;
1551 typecode = a->ob_descr->typecode;
1552 if (len == 0) {
1553 PyOS_snprintf(buf, sizeof(buf), "array('%c')", typecode);
1554 return PyString_FromString(buf);
1555 }
1556
1557 if (typecode == 'c')
1558 v = array_tostring(a, NULL);
1559 #ifdef Py_USING_UNICODE
1560 else if (typecode == 'u')
1561 v = array_tounicode(a, NULL);
1562 #endif
1563 else
1564 v = array_tolist(a, NULL);
1565 t = PyObject_Repr(v);
1566 Py_XDECREF(v);
1567
1568 PyOS_snprintf(buf, sizeof(buf), "array('%c', ", typecode);
1569 s = PyString_FromString(buf);
1570 PyString_ConcatAndDel(&s, t);
1571 PyString_ConcatAndDel(&s, PyString_FromString(")"));
1572 return s;
1573 }
1574
1575 static PyObject*
1576 array_subscr(arrayobject* self, PyObject* item)
1577 {
1578 if (PyIndex_Check(item)) {
1579 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1580 if (i==-1 && PyErr_Occurred()) {
1581 return NULL;
1582 }
1583 if (i < 0)
1584 i += self->ob_size;
1585 return array_item(self, i);
1586 }
1587 else if (PySlice_Check(item)) {
1588 Py_ssize_t start, stop, step, slicelength, cur, i;
1589 PyObject* result;
1590 arrayobject* ar;
1591 int itemsize = self->ob_descr->itemsize;
1592
1593 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
1594 &start, &stop, &step, &slicelength) < 0) {
1595 return NULL;
1596 }
1597
1598 if (slicelength <= 0) {
1599 return newarrayobject(&Arraytype, 0, self->ob_descr);
1600 }
1601 else {
1602 result = newarrayobject(&Arraytype, slicelength, self->ob_descr);
1603 if (!result) return NULL;
1604
1605 ar = (arrayobject*)result;
1606
1607 for (cur = start, i = 0; i < slicelength;
1608 cur += step, i++) {
1609 memcpy(ar->ob_item + i*itemsize,
1610 self->ob_item + cur*itemsize,
1611 itemsize);
1612 }
1613
1614 return result;
1615 }
1616 }
1617 else {
1618 PyErr_SetString(PyExc_TypeError,
1619 "list indices must be integers");
1620 return NULL;
1621 }
1622 }
1623
1624 static int
1625 array_ass_subscr(arrayobject* self, PyObject* item, PyObject* value)
1626 {
1627 if (PyIndex_Check(item)) {
1628 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1629 if (i==-1 && PyErr_Occurred())
1630 return -1;
1631 if (i < 0)
1632 i += self->ob_size;
1633 return array_ass_item(self, i, value);
1634 }
1635 else if (PySlice_Check(item)) {
1636 Py_ssize_t start, stop, step, slicelength;
1637 int itemsize = self->ob_descr->itemsize;
1638
1639 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
1640 &start, &stop, &step, &slicelength) < 0) {
1641 return -1;
1642 }
1643
1644 /* treat A[slice(a,b)] = v _exactly_ like A[a:b] = v */
1645 if (step == 1 && ((PySliceObject*)item)->step == Py_None)
1646 return array_ass_slice(self, start, stop, value);
1647
1648 if (value == NULL) {
1649 /* delete slice */
1650 Py_ssize_t cur, i, extra;
1651
1652 if (slicelength <= 0)
1653 return 0;
1654
1655 if (step < 0) {
1656 stop = start + 1;
1657 start = stop + step*(slicelength - 1) - 1;
1658 step = -step;
1659 }
1660
1661 for (cur = start, i = 0; i < slicelength - 1;
1662 cur += step, i++) {
1663 memmove(self->ob_item + (cur - i)*itemsize,
1664 self->ob_item + (cur + 1)*itemsize,
1665 (step - 1) * itemsize);
1666 }
1667 extra = self->ob_size - (cur + 1);
1668 if (extra > 0) {
1669 memmove(self->ob_item + (cur - i)*itemsize,
1670 self->ob_item + (cur + 1)*itemsize,
1671 extra*itemsize);
1672 }
1673
1674 self->ob_size -= slicelength;
1675 self->ob_item = (char *)PyMem_REALLOC(self->ob_item,
1676 itemsize*self->ob_size);
1677 self->allocated = self->ob_size;
1678
1679 return 0;
1680 }
1681 else {
1682 /* assign slice */
1683 Py_ssize_t cur, i;
1684 arrayobject* av;
1685
1686 if (!array_Check(value)) {
1687 PyErr_Format(PyExc_TypeError,
1688 "must assign array (not \"%.200s\") to slice",
1689 value->ob_type->tp_name);
1690 return -1;
1691 }
1692
1693 av = (arrayobject*)value;
1694
1695 if (av->ob_size != slicelength) {
1696 PyErr_Format(PyExc_ValueError,
1697 "attempt to assign array of size %ld to extended slice of size %ld",
1698 /*XXX*/(long)av->ob_size, /*XXX*/(long)slicelength);
1699 return -1;
1700 }
1701
1702 if (!slicelength)
1703 return 0;
1704
1705 /* protect against a[::-1] = a */
1706 if (self == av) {
1707 value = array_slice(av, 0, av->ob_size);
1708 av = (arrayobject*)value;
1709 if (!av)
1710 return -1;
1711 }
1712 else {
1713 Py_INCREF(value);
1714 }
1715
1716 for (cur = start, i = 0; i < slicelength;
1717 cur += step, i++) {
1718 memcpy(self->ob_item + cur*itemsize,
1719 av->ob_item + i*itemsize,
1720 itemsize);
1721 }
1722
1723 Py_DECREF(value);
1724
1725 return 0;
1726 }
1727 }
1728 else {
1729 PyErr_SetString(PyExc_TypeError,
1730 "list indices must be integers");
1731 return -1;
1732 }
1733 }
1734
1735 static PyMappingMethods array_as_mapping = {
1736 (lenfunc)array_length,
1737 (binaryfunc)array_subscr,
1738 (objobjargproc)array_ass_subscr
1739 };
1740
1741 static Py_ssize_t
1742 array_buffer_getreadbuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1743 {
1744 if ( index != 0 ) {
1745 PyErr_SetString(PyExc_SystemError,
1746 "Accessing non-existent array segment");
1747 return -1;
1748 }
1749 *ptr = (void *)self->ob_item;
1750 return self->ob_size*self->ob_descr->itemsize;
1751 }
1752
1753 static Py_ssize_t
1754 array_buffer_getwritebuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1755 {
1756 if ( index != 0 ) {
1757 PyErr_SetString(PyExc_SystemError,
1758 "Accessing non-existent array segment");
1759 return -1;
1760 }
1761 *ptr = (void *)self->ob_item;
1762 return self->ob_size*self->ob_descr->itemsize;
1763 }
1764
1765 static Py_ssize_t
1766 array_buffer_getsegcount(arrayobject *self, Py_ssize_t *lenp)
1767 {
1768 if ( lenp )
1769 *lenp = self->ob_size*self->ob_descr->itemsize;
1770 return 1;
1771 }
1772
1773 static PySequenceMethods array_as_sequence = {
1774 (lenfunc)array_length, /*sq_length*/
1775 (binaryfunc)array_concat, /*sq_concat*/
1776 (ssizeargfunc)array_repeat, /*sq_repeat*/
1777 (ssizeargfunc)array_item, /*sq_item*/
1778 (ssizessizeargfunc)array_slice, /*sq_slice*/
1779 (ssizeobjargproc)array_ass_item, /*sq_ass_item*/
1780 (ssizessizeobjargproc)array_ass_slice, /*sq_ass_slice*/
1781 (objobjproc)array_contains, /*sq_contains*/
1782 (binaryfunc)array_inplace_concat, /*sq_inplace_concat*/
1783 (ssizeargfunc)array_inplace_repeat /*sq_inplace_repeat*/
1784 };
1785
1786 static PyBufferProcs array_as_buffer = {
1787 (readbufferproc)array_buffer_getreadbuf,
1788 (writebufferproc)array_buffer_getwritebuf,
1789 (segcountproc)array_buffer_getsegcount,
1790 NULL,
1791 };
1792
1793 static PyObject *
1794 array_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1795 {
1796 char c;
1797 PyObject *initial = NULL, *it = NULL;
1798 struct arraydescr *descr;
1799
1800 if (type == &Arraytype && !_PyArg_NoKeywords("array.array()", kwds))
1801 return NULL;
1802
1803 if (!PyArg_ParseTuple(args, "c|O:array", &c, &initial))
1804 return NULL;
1805
1806 if (!(initial == NULL || PyList_Check(initial)
1807 || PyString_Check(initial) || PyTuple_Check(initial)
1808 || (c == 'u' && PyUnicode_Check(initial)))) {
1809 it = PyObject_GetIter(initial);
1810 if (it == NULL)
1811 return NULL;
1812 /* We set initial to NULL so that the subsequent code
1813 will create an empty array of the appropriate type
1814 and afterwards we can use array_iter_extend to populate
1815 the array.
1816 */
1817 initial = NULL;
1818 }
1819 for (descr = descriptors; descr->typecode != '\0'; descr++) {
1820 if (descr->typecode == c) {
1821 PyObject *a;
1822 Py_ssize_t len;
1823
1824 if (initial == NULL || !(PyList_Check(initial)
1825 || PyTuple_Check(initial)))
1826 len = 0;
1827 else
1828 len = PySequence_Size(initial);
1829
1830 a = newarrayobject(type, len, descr);
1831 if (a == NULL)
1832 return NULL;
1833
1834 if (len > 0) {
1835 Py_ssize_t i;
1836 for (i = 0; i < len; i++) {
1837 PyObject *v =
1838 PySequence_GetItem(initial, i);
1839 if (v == NULL) {
1840 Py_DECREF(a);
1841 return NULL;
1842 }
1843 if (setarrayitem(a, i, v) != 0) {
1844 Py_DECREF(v);
1845 Py_DECREF(a);
1846 return NULL;
1847 }
1848 Py_DECREF(v);
1849 }
1850 } else if (initial != NULL && PyString_Check(initial)) {
1851 PyObject *t_initial, *v;
1852 t_initial = PyTuple_Pack(1, initial);
1853 if (t_initial == NULL) {
1854 Py_DECREF(a);
1855 return NULL;
1856 }
1857 v = array_fromstring((arrayobject *)a,
1858 t_initial);
1859 Py_DECREF(t_initial);
1860 if (v == NULL) {
1861 Py_DECREF(a);
1862 return NULL;
1863 }
1864 Py_DECREF(v);
1865 #ifdef Py_USING_UNICODE
1866 } else if (initial != NULL && PyUnicode_Check(initial)) {
1867 Py_ssize_t n = PyUnicode_GET_DATA_SIZE(initial);
1868 if (n > 0) {
1869 arrayobject *self = (arrayobject *)a;
1870 char *item = self->ob_item;
1871 item = (char *)PyMem_Realloc(item, n);
1872 if (item == NULL) {
1873 PyErr_NoMemory();
1874 Py_DECREF(a);
1875 return NULL;
1876 }
1877 self->ob_item = item;
1878 self->ob_size = n / sizeof(Py_UNICODE);
1879 memcpy(item, PyUnicode_AS_DATA(initial), n);
1880 self->allocated = self->ob_size;
1881 }
1882 #endif
1883 }
1884 if (it != NULL) {
1885 if (array_iter_extend((arrayobject *)a, it) == -1) {
1886 Py_DECREF(it);
1887 Py_DECREF(a);
1888 return NULL;
1889 }
1890 Py_DECREF(it);
1891 }
1892 return a;
1893 }
1894 }
1895 PyErr_SetString(PyExc_ValueError,
1896 "bad typecode (must be c, b, B, u, h, H, i, I, l, L, f or d)");
1897 return NULL;
1898 }
1899
1900
1901 PyDoc_STRVAR(module_doc,
1902 "This module defines an object type which can efficiently represent\n\
1903 an array of basic values: characters, integers, floating point\n\
1904 numbers. Arrays are sequence types and behave very much like lists,\n\
1905 except that the type of objects stored in them is constrained. The\n\
1906 type is specified at object creation time by using a type code, which\n\
1907 is a single character. The following type codes are defined:\n\
1908 \n\
1909 Type code C Type Minimum size in bytes \n\
1910 'c' character 1 \n\
1911 'b' signed integer 1 \n\
1912 'B' unsigned integer 1 \n\
1913 'u' Unicode character 2 \n\
1914 'h' signed integer 2 \n\
1915 'H' unsigned integer 2 \n\
1916 'i' signed integer 2 \n\
1917 'I' unsigned integer 2 \n\
1918 'l' signed integer 4 \n\
1919 'L' unsigned integer 4 \n\
1920 'f' floating point 4 \n\
1921 'd' floating point 8 \n\
1922 \n\
1923 The constructor is:\n\
1924 \n\
1925 array(typecode [, initializer]) -- create a new array\n\
1926 ");
1927
1928 PyDoc_STRVAR(arraytype_doc,
1929 "array(typecode [, initializer]) -> array\n\
1930 \n\
1931 Return a new array whose items are restricted by typecode, and\n\
1932 initialized from the optional initializer value, which must be a list,\n\
1933 string. or iterable over elements of the appropriate type.\n\
1934 \n\
1935 Arrays represent basic values and behave very much like lists, except\n\
1936 the type of objects stored in them is constrained.\n\
1937 \n\
1938 Methods:\n\
1939 \n\
1940 append() -- append a new item to the end of the array\n\
1941 buffer_info() -- return information giving the current memory info\n\
1942 byteswap() -- byteswap all the items of the array\n\
1943 count() -- return number of occurences of an object\n\
1944 extend() -- extend array by appending multiple elements from an iterable\n\
1945 fromfile() -- read items from a file object\n\
1946 fromlist() -- append items from the list\n\
1947 fromstring() -- append items from the string\n\
1948 index() -- return index of first occurence of an object\n\
1949 insert() -- insert a new item into the array at a provided position\n\
1950 pop() -- remove and return item (default last)\n\
1951 read() -- DEPRECATED, use fromfile()\n\
1952 remove() -- remove first occurence of an object\n\
1953 reverse() -- reverse the order of the items in the array\n\
1954 tofile() -- write all items to a file object\n\
1955 tolist() -- return the array converted to an ordinary list\n\
1956 tostring() -- return the array converted to a string\n\
1957 write() -- DEPRECATED, use tofile()\n\
1958 \n\
1959 Attributes:\n\
1960 \n\
1961 typecode -- the typecode character used to create the array\n\
1962 itemsize -- the length in bytes of one array item\n\
1963 ");
1964
1965 static PyObject *array_iter(arrayobject *ao);
1966
1967 static PyTypeObject Arraytype = {
1968 PyObject_HEAD_INIT(NULL)
1969 0,
1970 "array.array",
1971 sizeof(arrayobject),
1972 0,
1973 (destructor)array_dealloc, /* tp_dealloc */
1974 0, /* tp_print */
1975 0, /* tp_getattr */
1976 0, /* tp_setattr */
1977 0, /* tp_compare */
1978 (reprfunc)array_repr, /* tp_repr */
1979 0, /* tp_as_number*/
1980 &array_as_sequence, /* tp_as_sequence*/
1981 &array_as_mapping, /* tp_as_mapping*/
1982 0, /* tp_hash */
1983 0, /* tp_call */
1984 0, /* tp_str */
1985 PyObject_GenericGetAttr, /* tp_getattro */
1986 0, /* tp_setattro */
1987 &array_as_buffer, /* tp_as_buffer*/
1988 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1989 arraytype_doc, /* tp_doc */
1990 0, /* tp_traverse */
1991 0, /* tp_clear */
1992 array_richcompare, /* tp_richcompare */
1993 offsetof(arrayobject, weakreflist), /* tp_weaklistoffset */
1994 (getiterfunc)array_iter, /* tp_iter */
1995 0, /* tp_iternext */
1996 array_methods, /* tp_methods */
1997 0, /* tp_members */
1998 array_getsets, /* tp_getset */
1999 0, /* tp_base */
2000 0, /* tp_dict */
2001 0, /* tp_descr_get */
2002 0, /* tp_descr_set */
2003 0, /* tp_dictoffset */
2004 0, /* tp_init */
2005 PyType_GenericAlloc, /* tp_alloc */
2006 array_new, /* tp_new */
2007 PyObject_Del, /* tp_free */
2008 };
2009
2010
2011 /*********************** Array Iterator **************************/
2012
2013 typedef struct {
2014 PyObject_HEAD
2015 Py_ssize_t index;
2016 arrayobject *ao;
2017 PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
2018 } arrayiterobject;
2019
2020 static PyTypeObject PyArrayIter_Type;
2021
2022 #define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)
2023
2024 static PyObject *
2025 array_iter(arrayobject *ao)
2026 {
2027 arrayiterobject *it;
2028
2029 if (!array_Check(ao)) {
2030 PyErr_BadInternalCall();
2031 return NULL;
2032 }
2033
2034 it = PyObject_GC_New(arrayiterobject, &PyArrayIter_Type);
2035 if (it == NULL)
2036 return NULL;
2037
2038 Py_INCREF(ao);
2039 it->ao = ao;
2040 it->index = 0;
2041 it->getitem = ao->ob_descr->getitem;
2042 PyObject_GC_Track(it);
2043 return (PyObject *)it;
2044 }
2045
2046 static PyObject *
2047 arrayiter_next(arrayiterobject *it)
2048 {
2049 assert(PyArrayIter_Check(it));
2050 if (it->index < it->ao->ob_size)
2051 return (*it->getitem)(it->ao, it->index++);
2052 return NULL;
2053 }
2054
2055 static void
2056 arrayiter_dealloc(arrayiterobject *it)
2057 {
2058 PyObject_GC_UnTrack(it);
2059 Py_XDECREF(it->ao);
2060 PyObject_GC_Del(it);
2061 }
2062
2063 static int
2064 arrayiter_traverse(arrayiterobject *it, visitproc visit, void *arg)
2065 {
2066 Py_VISIT(it->ao);
2067 return 0;
2068 }
2069
2070 static PyTypeObject PyArrayIter_Type = {
2071 PyObject_HEAD_INIT(NULL)
2072 0, /* ob_size */
2073 "arrayiterator", /* tp_name */
2074 sizeof(arrayiterobject), /* tp_basicsize */
2075 0, /* tp_itemsize */
2076 /* methods */
2077 (destructor)arrayiter_dealloc, /* tp_dealloc */
2078 0, /* tp_print */
2079 0, /* tp_getattr */
2080 0, /* tp_setattr */
2081 0, /* tp_compare */
2082 0, /* tp_repr */
2083 0, /* tp_as_number */
2084 0, /* tp_as_sequence */
2085 0, /* tp_as_mapping */
2086 0, /* tp_hash */
2087 0, /* tp_call */
2088 0, /* tp_str */
2089 PyObject_GenericGetAttr, /* tp_getattro */
2090 0, /* tp_setattro */
2091 0, /* tp_as_buffer */
2092 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2093 0, /* tp_doc */
2094 (traverseproc)arrayiter_traverse, /* tp_traverse */
2095 0, /* tp_clear */
2096 0, /* tp_richcompare */
2097 0, /* tp_weaklistoffset */
2098 PyObject_SelfIter, /* tp_iter */
2099 (iternextfunc)arrayiter_next, /* tp_iternext */
2100 0, /* tp_methods */
2101 };
2102
2103
2104 /*********************** Install Module **************************/
2105
2106 /* No functions in array module. */
2107 static PyMethodDef a_methods[] = {
2108 {NULL, NULL, 0, NULL} /* Sentinel */
2109 };
2110
2111
2112 PyMODINIT_FUNC
2113 initarray(void)
2114 {
2115 PyObject *m;
2116
2117 Arraytype.ob_type = &PyType_Type;
2118 PyArrayIter_Type.ob_type = &PyType_Type;
2119 m = Py_InitModule3("array", a_methods, module_doc);
2120 if (m == NULL)
2121 return;
2122
2123 Py_INCREF((PyObject *)&Arraytype);
2124 PyModule_AddObject(m, "ArrayType", (PyObject *)&Arraytype);
2125 Py_INCREF((PyObject *)&Arraytype);
2126 PyModule_AddObject(m, "array", (PyObject *)&Arraytype);
2127 /* No need to check the error here, the caller will do that */
2128 }
python git mirror