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