Context Navigation

arraymodule.c

Visit:

Last change on this file was 3225, checked in by bird, 18 years ago
Python 2.5
File size: 50.8 KB

Line
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_NOARGS,
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_sizeself->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 (!_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	}

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: vendor/python/2.5/Modules/arraymodule.c

Download in other formats: