Modules/arraymodule.c

   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) (Py_TYPE(op) == &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         Py_SIZE(self) < newsize + 16 &&
  57         self->ob_item != NULL) {
  58         Py_SIZE(self) = 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) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
  75     items = self->ob_item;
  76     /* XXX The following multiplication and division does not optimize away
  77        like it does for lists since the size is not known at compile time */
  78     if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
  79         PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
  80     else
  81         items = NULL;
  82     if (items == NULL) {
  83         PyErr_NoMemory();
  84         return -1;
  85     }
  86     self->ob_item = items;
  87     Py_SIZE(self) = 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_descr = descr;
 436     op->allocated = size;
 437     op->weakreflist = NULL;
 438     Py_SIZE(op) = size;
 439     if (size <= 0) {
 440         op->ob_item = NULL;
 441     }
 442     else {
 443         op->ob_item = PyMem_NEW(char, nbytes);
 444         if (op->ob_item == NULL) {
 445             Py_DECREF(op);
 446             return PyErr_NoMemory();
 447         }
 448     }
 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<Py_SIZE(ap));
 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 = Py_SIZE(self);
 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     Py_TYPE(op)->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 (Py_SIZE(va) != Py_SIZE(wa) && (op == Py_EQ || op == Py_NE)) {
 522         /* Shortcut: if the lengths differ, the arrays differ */
 523         if (op == Py_EQ)
 524             res = Py_False;
 525         else
 526             res = Py_True;
 527         Py_INCREF(res);
 528         return res;
 529     }
 530
 531     /* Search for the first index where items are different */
 532     k = 1;
 533     for (i = 0; i < Py_SIZE(va) && i < Py_SIZE(wa); i++) {
 534         vi = getarrayitem(v, i);
 535         wi = getarrayitem(w, i);
 536         if (vi == NULL || wi == NULL) {
 537             Py_XDECREF(vi);
 538             Py_XDECREF(wi);
 539             return NULL;
 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 = Py_SIZE(va);
 553         Py_ssize_t ws = Py_SIZE(wa);
 554         int cmp;
 555         switch (op) {
 556         case Py_LT: cmp = vs <  ws; break;
 557         case Py_LE: cmp = vs <= ws; break;
 558         case Py_EQ: cmp = vs == ws; break;
 559         case Py_NE: cmp = vs != ws; break;
 560         case Py_GT: cmp = vs >  ws; break;
 561         case Py_GE: cmp = vs >= ws; break;
 562         default: return NULL; /* cannot happen */
 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 Py_SIZE(a);
 594 }
 595
 596 static PyObject *
 597 array_item(arrayobject *a, Py_ssize_t i)
 598 {
 599     if (i < 0 || i >= Py_SIZE(a)) {
 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 > Py_SIZE(a))
 613         ilow = Py_SIZE(a);
 614     if (ihigh < 0)
 615         ihigh = 0;
 616     if (ihigh < ilow)
 617         ihigh = ilow;
 618     else if (ihigh > Py_SIZE(a))
 619         ihigh = Py_SIZE(a);
 620     np = (arrayobject *) newarrayobject(&Arraytype, ihigh - ilow, a->ob_descr);
 621     if (np == NULL)
 622         return NULL;
 623     memcpy(np->ob_item, a->ob_item + ilow * a->ob_descr->itemsize,
 624            (ihigh-ilow) * a->ob_descr->itemsize);
 625     return (PyObject *)np;
 626 }
 627
 628 static PyObject *
 629 array_copy(arrayobject *a, PyObject *unused)
 630 {
 631     return array_slice(a, 0, Py_SIZE(a));
 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                  Py_TYPE(bb)->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     if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b)) {
 656         return PyErr_NoMemory();
 657     }
 658     size = Py_SIZE(a) + Py_SIZE(b);
 659     np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
 660     if (np == NULL) {
 661         return NULL;
 662     }
 663     memcpy(np->ob_item, a->ob_item, Py_SIZE(a)*a->ob_descr->itemsize);
 664     memcpy(np->ob_item + Py_SIZE(a)*a->ob_descr->itemsize,
 665            b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
 666     return (PyObject *)np;
 667 #undef b
 668 }
 669
 670 static PyObject *
 671 array_repeat(arrayobject *a, Py_ssize_t n)
 672 {
 673     Py_ssize_t i;
 674     Py_ssize_t size;
 675     arrayobject *np;
 676     char *p;
 677     Py_ssize_t nbytes;
 678     if (n < 0)
 679         n = 0;
 680     if ((Py_SIZE(a) != 0) && (n > PY_SSIZE_T_MAX / Py_SIZE(a))) {
 681         return PyErr_NoMemory();
 682     }
 683     size = Py_SIZE(a) * n;
 684     np = (arrayobject *) newarrayobject(&Arraytype, size, a->ob_descr);
 685     if (np == NULL)
 686         return NULL;
 687     p = np->ob_item;
 688     nbytes = Py_SIZE(a) * a->ob_descr->itemsize;
 689     for (i = 0; i < n; i++) {
 690         memcpy(p, a->ob_item, nbytes);
 691         p += nbytes;
 692     }
 693     return (PyObject *) np;
 694 }
 695
 696 static int
 697 array_ass_slice(arrayobject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
 698 {
 699     char *item;
 700     Py_ssize_t n; /* Size of replacement array */
 701     Py_ssize_t d; /* Change in size */
 702 #define b ((arrayobject *)v)
 703     if (v == NULL)
 704         n = 0;
 705     else if (array_Check(v)) {
 706         n = Py_SIZE(b);
 707         if (a == b) {
 708             /* Special case "a[i:j] = a" -- copy b first */
 709             int ret;
 710             v = array_slice(b, 0, n);
 711             if (!v)
 712                 return -1;
 713             ret = array_ass_slice(a, ilow, ihigh, v);
 714             Py_DECREF(v);
 715             return ret;
 716         }
 717         if (b->ob_descr != a->ob_descr) {
 718             PyErr_BadArgument();
 719             return -1;
 720         }
 721     }
 722     else {
 723         PyErr_Format(PyExc_TypeError,
 724          "can only assign array (not \"%.200s\") to array slice",
 725                          Py_TYPE(v)->tp_name);
 726         return -1;
 727     }
 728     if (ilow < 0)
 729         ilow = 0;
 730     else if (ilow > Py_SIZE(a))
 731         ilow = Py_SIZE(a);
 732     if (ihigh < 0)
 733         ihigh = 0;
 734     if (ihigh < ilow)
 735         ihigh = ilow;
 736     else if (ihigh > Py_SIZE(a))
 737         ihigh = Py_SIZE(a);
 738     item = a->ob_item;
 739     d = n - (ihigh-ilow);
 740     if (d < 0) { /* Delete -d items */
 741         memmove(item + (ihigh+d)*a->ob_descr->itemsize,
 742             item + ihigh*a->ob_descr->itemsize,
 743             (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
 744         Py_SIZE(a) += d;
 745         PyMem_RESIZE(item, char, Py_SIZE(a)*a->ob_descr->itemsize);
 746                                         /* Can't fail */
 747         a->ob_item = item;
 748         a->allocated = Py_SIZE(a);
 749     }
 750     else if (d > 0) { /* Insert d items */
 751         PyMem_RESIZE(item, char,
 752                      (Py_SIZE(a) + d)*a->ob_descr->itemsize);
 753         if (item == NULL) {
 754             PyErr_NoMemory();
 755             return -1;
 756         }
 757         memmove(item + (ihigh+d)*a->ob_descr->itemsize,
 758             item + ihigh*a->ob_descr->itemsize,
 759             (Py_SIZE(a)-ihigh)*a->ob_descr->itemsize);
 760         a->ob_item = item;
 761         Py_SIZE(a) += d;
 762         a->allocated = Py_SIZE(a);
 763     }
 764     if (n > 0)
 765         memcpy(item + ilow*a->ob_descr->itemsize, b->ob_item,
 766                n*b->ob_descr->itemsize);
 767     return 0;
 768 #undef b
 769 }
 770
 771 static int
 772 array_ass_item(arrayobject *a, Py_ssize_t i, PyObject *v)
 773 {
 774     if (i < 0 || i >= Py_SIZE(a)) {
 775         PyErr_SetString(PyExc_IndexError,
 776                          "array assignment index out of range");
 777         return -1;
 778     }
 779     if (v == NULL)
 780         return array_ass_slice(a, i, i+1, v);
 781     return (*a->ob_descr->setitem)(a, i, v);
 782 }
 783
 784 static int
 785 setarrayitem(PyObject *a, Py_ssize_t i, PyObject *v)
 786 {
 787     assert(array_Check(a));
 788     return array_ass_item((arrayobject *)a, i, v);
 789 }
 790
 791 static int
 792 array_iter_extend(arrayobject *self, PyObject *bb)
 793 {
 794     PyObject *it, *v;
 795
 796     it = PyObject_GetIter(bb);
 797     if (it == NULL)
 798         return -1;
 799
 800     while ((v = PyIter_Next(it)) != NULL) {
 801         if (ins1(self, Py_SIZE(self), v) != 0) {
 802             Py_DECREF(v);
 803             Py_DECREF(it);
 804             return -1;
 805         }
 806         Py_DECREF(v);
 807     }
 808     Py_DECREF(it);
 809     if (PyErr_Occurred())
 810         return -1;
 811     return 0;
 812 }
 813
 814 static int
 815 array_do_extend(arrayobject *self, PyObject *bb)
 816 {
 817     Py_ssize_t size;
 818     char *old_item;
 819
 820     if (!array_Check(bb))
 821         return array_iter_extend(self, bb);
 822 #define b ((arrayobject *)bb)
 823     if (self->ob_descr != b->ob_descr) {
 824         PyErr_SetString(PyExc_TypeError,
 825                      "can only extend with array of same kind");
 826         return -1;
 827     }
 828     if ((Py_SIZE(self) > PY_SSIZE_T_MAX - Py_SIZE(b)) ||
 829         ((Py_SIZE(self) + Py_SIZE(b)) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {
 830         PyErr_NoMemory();
 831         return -1;
 832     }
 833     size = Py_SIZE(self) + Py_SIZE(b);
 834     old_item = self->ob_item;
 835     PyMem_RESIZE(self->ob_item, char, size*self->ob_descr->itemsize);
 836     if (self->ob_item == NULL) {
 837         self->ob_item = old_item;
 838         PyErr_NoMemory();
 839         return -1;
 840     }
 841     memcpy(self->ob_item + Py_SIZE(self)*self->ob_descr->itemsize,
 842            b->ob_item, Py_SIZE(b)*b->ob_descr->itemsize);
 843     Py_SIZE(self) = size;
 844     self->allocated = size;
 845
 846     return 0;
 847 #undef b
 848 }
 849
 850 static PyObject *
 851 array_inplace_concat(arrayobject *self, PyObject *bb)
 852 {
 853     if (!array_Check(bb)) {
 854         PyErr_Format(PyExc_TypeError,
 855             "can only extend array with array (not \"%.200s\")",
 856             Py_TYPE(bb)->tp_name);
 857         return NULL;
 858     }
 859     if (array_do_extend(self, bb) == -1)
 860         return NULL;
 861     Py_INCREF(self);
 862     return (PyObject *)self;
 863 }
 864
 865 static PyObject *
 866 array_inplace_repeat(arrayobject *self, Py_ssize_t n)
 867 {
 868     char *items, *p;
 869     Py_ssize_t size, i;
 870
 871     if (Py_SIZE(self) > 0) {
 872         if (n < 0)
 873             n = 0;
 874         items = self->ob_item;
 875         if ((self->ob_descr->itemsize != 0) &&
 876             (Py_SIZE(self) > PY_SSIZE_T_MAX / self->ob_descr->itemsize)) {
 877             return PyErr_NoMemory();
 878         }
 879         size = Py_SIZE(self) * self->ob_descr->itemsize;
 880         if (n == 0) {
 881             PyMem_FREE(items);
 882             self->ob_item = NULL;
 883             Py_SIZE(self) = 0;
 884             self->allocated = 0;
 885         }
 886         else {
 887             if (size > PY_SSIZE_T_MAX / n) {
 888                 return PyErr_NoMemory();
 889             }
 890             PyMem_RESIZE(items, char, n * size);
 891             if (items == NULL)
 892                 return PyErr_NoMemory();
 893             p = items;
 894             for (i = 1; i < n; i++) {
 895                 p += size;
 896                 memcpy(p, items, size);
 897             }
 898             self->ob_item = items;
 899             Py_SIZE(self) *= n;
 900             self->allocated = Py_SIZE(self);
 901         }
 902     }
 903     Py_INCREF(self);
 904     return (PyObject *)self;
 905 }
 906
 907
 908 static PyObject *
 909 ins(arrayobject *self, Py_ssize_t where, PyObject *v)
 910 {
 911     if (ins1(self, where, v) != 0)
 912         return NULL;
 913     Py_INCREF(Py_None);
 914     return Py_None;
 915 }
 916
 917 static PyObject *
 918 array_count(arrayobject *self, PyObject *v)
 919 {
 920     Py_ssize_t count = 0;
 921     Py_ssize_t i;
 922
 923     for (i = 0; i < Py_SIZE(self); i++) {
 924         PyObject *selfi = getarrayitem((PyObject *)self, i);
 925         int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
 926         Py_DECREF(selfi);
 927         if (cmp > 0)
 928             count++;
 929         else if (cmp < 0)
 930             return NULL;
 931     }
 932     return PyInt_FromSsize_t(count);
 933 }
 934
 935 PyDoc_STRVAR(count_doc,
 936 "count(x)\n\
 937 \n\
 938 Return number of occurrences of x in the array.");
 939
 940 static PyObject *
 941 array_index(arrayobject *self, PyObject *v)
 942 {
 943     Py_ssize_t i;
 944
 945     for (i = 0; i < Py_SIZE(self); i++) {
 946         PyObject *selfi = getarrayitem((PyObject *)self, i);
 947         int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
 948         Py_DECREF(selfi);
 949         if (cmp > 0) {
 950             return PyInt_FromLong((long)i);
 951         }
 952         else if (cmp < 0)
 953             return NULL;
 954     }
 955     PyErr_SetString(PyExc_ValueError, "array.index(x): x not in list");
 956     return NULL;
 957 }
 958
 959 PyDoc_STRVAR(index_doc,
 960 "index(x)\n\
 961 \n\
 962 Return index of first occurrence of x in the array.");
 963
 964 static int
 965 array_contains(arrayobject *self, PyObject *v)
 966 {
 967     Py_ssize_t i;
 968     int cmp;
 969
 970     for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(self); i++) {
 971         PyObject *selfi = getarrayitem((PyObject *)self, i);
 972         cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
 973         Py_DECREF(selfi);
 974     }
 975     return cmp;
 976 }
 977
 978 static PyObject *
 979 array_remove(arrayobject *self, PyObject *v)
 980 {
 981     int i;
 982
 983     for (i = 0; i < Py_SIZE(self); i++) {
 984         PyObject *selfi = getarrayitem((PyObject *)self,i);
 985         int cmp = PyObject_RichCompareBool(selfi, v, Py_EQ);
 986         Py_DECREF(selfi);
 987         if (cmp > 0) {
 988             if (array_ass_slice(self, i, i+1,
 989                                (PyObject *)NULL) != 0)
 990                 return NULL;
 991             Py_INCREF(Py_None);
 992             return Py_None;
 993         }
 994         else if (cmp < 0)
 995             return NULL;
 996     }
 997     PyErr_SetString(PyExc_ValueError, "array.remove(x): x not in list");
 998     return NULL;
 999 }
1000
1001 PyDoc_STRVAR(remove_doc,
1002 "remove(x)\n\
1003 \n\
1004 Remove the first occurrence of x in the array.");
1005
1006 static PyObject *
1007 array_pop(arrayobject *self, PyObject *args)
1008 {
1009     Py_ssize_t i = -1;
1010     PyObject *v;
1011     if (!PyArg_ParseTuple(args, "|n:pop", &i))
1012         return NULL;
1013     if (Py_SIZE(self) == 0) {
1014         /* Special-case most common failure cause */
1015         PyErr_SetString(PyExc_IndexError, "pop from empty array");
1016         return NULL;
1017     }
1018     if (i < 0)
1019         i += Py_SIZE(self);
1020     if (i < 0 || i >= Py_SIZE(self)) {
1021         PyErr_SetString(PyExc_IndexError, "pop index out of range");
1022         return NULL;
1023     }
1024     v = getarrayitem((PyObject *)self,i);
1025     if (array_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
1026         Py_DECREF(v);
1027         return NULL;
1028     }
1029     return v;
1030 }
1031
1032 PyDoc_STRVAR(pop_doc,
1033 "pop([i])\n\
1034 \n\
1035 Return the i-th element and delete it from the array. i defaults to -1.");
1036
1037 static PyObject *
1038 array_extend(arrayobject *self, PyObject *bb)
1039 {
1040     if (array_do_extend(self, bb) == -1)
1041         return NULL;
1042     Py_INCREF(Py_None);
1043     return Py_None;
1044 }
1045
1046 PyDoc_STRVAR(extend_doc,
1047 "extend(array or iterable)\n\
1048 \n\
1049  Append items to the end of the array.");
1050
1051 static PyObject *
1052 array_insert(arrayobject *self, PyObject *args)
1053 {
1054     Py_ssize_t i;
1055     PyObject *v;
1056     if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
1057         return NULL;
1058     return ins(self, i, v);
1059 }
1060
1061 PyDoc_STRVAR(insert_doc,
1062 "insert(i,x)\n\
1063 \n\
1064 Insert a new item x into the array before position i.");
1065
1066
1067 static PyObject *
1068 array_buffer_info(arrayobject *self, PyObject *unused)
1069 {
1070     PyObject* retval = NULL;
1071     retval = PyTuple_New(2);
1072     if (!retval)
1073         return NULL;
1074
1075     PyTuple_SET_ITEM(retval, 0, PyLong_FromVoidPtr(self->ob_item));
1076     PyTuple_SET_ITEM(retval, 1, PyInt_FromLong((long)(Py_SIZE(self))));
1077
1078     return retval;
1079 }
1080
1081 PyDoc_STRVAR(buffer_info_doc,
1082 "buffer_info() -> (address, length)\n\
1083 \n\
1084 Return a tuple (address, length) giving the current memory address and\n\
1085 the length in items of the buffer used to hold array's contents\n\
1086 The length should be multiplied by the itemsize attribute to calculate\n\
1087 the buffer length in bytes.");
1088
1089
1090 static PyObject *
1091 array_append(arrayobject *self, PyObject *v)
1092 {
1093     return ins(self, Py_SIZE(self), v);
1094 }
1095
1096 PyDoc_STRVAR(append_doc,
1097 "append(x)\n\
1098 \n\
1099 Append new value x to the end of the array.");
1100
1101
1102 static PyObject *
1103 array_byteswap(arrayobject *self, PyObject *unused)
1104 {
1105     char *p;
1106     Py_ssize_t i;
1107
1108     switch (self->ob_descr->itemsize) {
1109     case 1:
1110         break;
1111     case 2:
1112         for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 2) {
1113             char p0 = p[0];
1114             p[0] = p[1];
1115             p[1] = p0;
1116         }
1117         break;
1118     case 4:
1119         for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 4) {
1120             char p0 = p[0];
1121             char p1 = p[1];
1122             p[0] = p[3];
1123             p[1] = p[2];
1124             p[2] = p1;
1125             p[3] = p0;
1126         }
1127         break;
1128     case 8:
1129         for (p = self->ob_item, i = Py_SIZE(self); --i >= 0; p += 8) {
1130             char p0 = p[0];
1131             char p1 = p[1];
1132             char p2 = p[2];
1133             char p3 = p[3];
1134             p[0] = p[7];
1135             p[1] = p[6];
1136             p[2] = p[5];
1137             p[3] = p[4];
1138             p[4] = p3;
1139             p[5] = p2;
1140             p[6] = p1;
1141             p[7] = p0;
1142         }
1143         break;
1144     default:
1145         PyErr_SetString(PyExc_RuntimeError,
1146                    "don't know how to byteswap this array type");
1147         return NULL;
1148     }
1149     Py_INCREF(Py_None);
1150     return Py_None;
1151 }
1152
1153 PyDoc_STRVAR(byteswap_doc,
1154 "byteswap()\n\
1155 \n\
1156 Byteswap all items of the array.  If the items in the array are not 1, 2,\n\
1157 4, or 8 bytes in size, RuntimeError is raised.");
1158
1159 static PyObject *
1160 array_reverse(arrayobject *self, PyObject *unused)
1161 {
1162     register Py_ssize_t itemsize = self->ob_descr->itemsize;
1163     register char *p, *q;
1164     /* little buffer to hold items while swapping */
1165     char tmp[256];      /* 8 is probably enough -- but why skimp */
1166     assert((size_t)itemsize <= sizeof(tmp));
1167
1168     if (Py_SIZE(self) > 1) {
1169         for (p = self->ob_item,
1170              q = self->ob_item + (Py_SIZE(self) - 1)*itemsize;
1171              p < q;
1172              p += itemsize, q -= itemsize) {
1173             /* memory areas guaranteed disjoint, so memcpy
1174              * is safe (& memmove may be slower).
1175              */
1176             memcpy(tmp, p, itemsize);
1177             memcpy(p, q, itemsize);
1178             memcpy(q, tmp, itemsize);
1179         }
1180     }
1181
1182     Py_INCREF(Py_None);
1183     return Py_None;
1184 }
1185
1186 PyDoc_STRVAR(reverse_doc,
1187 "reverse()\n\
1188 \n\
1189 Reverse the order of the items in the array.");
1190
1191 static PyObject *
1192 array_fromfile(arrayobject *self, PyObject *args)
1193 {
1194     PyObject *f;
1195     Py_ssize_t n;
1196     FILE *fp;
1197     if (!PyArg_ParseTuple(args, "On:fromfile", &f, &n))
1198         return NULL;
1199     fp = PyFile_AsFile(f);
1200     if (fp == NULL) {
1201         PyErr_SetString(PyExc_TypeError, "arg1 must be open file");
1202         return NULL;
1203     }
1204     if (n > 0) {
1205         char *item = self->ob_item;
1206         Py_ssize_t itemsize = self->ob_descr->itemsize;
1207         size_t nread;
1208         Py_ssize_t newlength;
1209         size_t newbytes;
1210         /* Be careful here about overflow */
1211         if ((newlength = Py_SIZE(self) + n) <= 0 ||
1212             (newbytes = newlength * itemsize) / itemsize !=
1213             (size_t)newlength)
1214             goto nomem;
1215         PyMem_RESIZE(item, char, newbytes);
1216         if (item == NULL) {
1217           nomem:
1218             PyErr_NoMemory();
1219             return NULL;
1220         }
1221         self->ob_item = item;
1222         Py_SIZE(self) += n;
1223         self->allocated = Py_SIZE(self);
1224         nread = fread(item + (Py_SIZE(self) - n) * itemsize,
1225                       itemsize, n, fp);
1226         if (nread < (size_t)n) {
1227           Py_SIZE(self) -= (n - nread);
1228             PyMem_RESIZE(item, char, Py_SIZE(self)*itemsize);
1229             self->ob_item = item;
1230             self->allocated = Py_SIZE(self);
1231             if (ferror(fp)) {
1232                 PyErr_SetFromErrno(PyExc_IOError);
1233                 clearerr(fp);
1234             }
1235             else {
1236                 PyErr_SetString(PyExc_EOFError,
1237                                 "not enough items in file");
1238             }
1239             return NULL;
1240         }
1241     }
1242     Py_INCREF(Py_None);
1243     return Py_None;
1244 }
1245
1246 PyDoc_STRVAR(fromfile_doc,
1247 "fromfile(f, n)\n\
1248 \n\
1249 Read n objects from the file object f and append them to the end of the\n\
1250 array.  Also called as read.");
1251
1252
1253 static PyObject *
1254 array_fromfile_as_read(arrayobject *self, PyObject *args)
1255 {
1256     if (PyErr_WarnPy3k("array.read() not supported in 3.x; "
1257                        "use array.fromfile()", 1) < 0)
1258         return NULL;
1259     return array_fromfile(self, args);
1260 }
1261
1262
1263 static PyObject *
1264 array_tofile(arrayobject *self, PyObject *f)
1265 {
1266     FILE *fp;
1267
1268     fp = PyFile_AsFile(f);
1269     if (fp == NULL) {
1270         PyErr_SetString(PyExc_TypeError, "arg must be open file");
1271         return NULL;
1272     }
1273     if (self->ob_size > 0) {
1274         if (fwrite(self->ob_item, self->ob_descr->itemsize,
1275                    self->ob_size, fp) != (size_t)self->ob_size) {
1276             PyErr_SetFromErrno(PyExc_IOError);
1277             clearerr(fp);
1278             return NULL;
1279         }
1280     }
1281     Py_INCREF(Py_None);
1282     return Py_None;
1283 }
1284
1285 PyDoc_STRVAR(tofile_doc,
1286 "tofile(f)\n\
1287 \n\
1288 Write all items (as machine values) to the file object f.  Also called as\n\
1289 write.");
1290
1291
1292 static PyObject *
1293 array_tofile_as_write(arrayobject *self, PyObject *f)
1294 {
1295     if (PyErr_WarnPy3k("array.write() not supported in 3.x; "
1296                        "use array.tofile()", 1) < 0)
1297         return NULL;
1298     return array_tofile(self, f);
1299 }
1300
1301
1302 static PyObject *
1303 array_fromlist(arrayobject *self, PyObject *list)
1304 {
1305     Py_ssize_t n;
1306     Py_ssize_t itemsize = self->ob_descr->itemsize;
1307
1308     if (!PyList_Check(list)) {
1309         PyErr_SetString(PyExc_TypeError, "arg must be list");
1310         return NULL;
1311     }
1312     n = PyList_Size(list);
1313     if (n > 0) {
1314         char *item = self->ob_item;
1315         Py_ssize_t i;
1316         PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1317         if (item == NULL) {
1318             PyErr_NoMemory();
1319             return NULL;
1320         }
1321         self->ob_item = item;
1322         Py_SIZE(self) += n;
1323         self->allocated = Py_SIZE(self);
1324         for (i = 0; i < n; i++) {
1325             PyObject *v = PyList_GetItem(list, i);
1326             if ((*self->ob_descr->setitem)(self,
1327                             Py_SIZE(self) - n + i, v) != 0) {
1328                 Py_SIZE(self) -= n;
1329                 if (itemsize && (self->ob_size > PY_SSIZE_T_MAX / itemsize)) {
1330                     return PyErr_NoMemory();
1331                 }
1332                 PyMem_RESIZE(item, char,
1333                                   Py_SIZE(self) * itemsize);
1334                 self->ob_item = item;
1335                 self->allocated = Py_SIZE(self);
1336                 return NULL;
1337             }
1338         }
1339     }
1340     Py_INCREF(Py_None);
1341     return Py_None;
1342 }
1343
1344 PyDoc_STRVAR(fromlist_doc,
1345 "fromlist(list)\n\
1346 \n\
1347 Append items to array from list.");
1348
1349
1350 static PyObject *
1351 array_tolist(arrayobject *self, PyObject *unused)
1352 {
1353     PyObject *list = PyList_New(Py_SIZE(self));
1354     Py_ssize_t i;
1355
1356     if (list == NULL)
1357         return NULL;
1358     for (i = 0; i < Py_SIZE(self); i++) {
1359         PyObject *v = getarrayitem((PyObject *)self, i);
1360         if (v == NULL) {
1361             Py_DECREF(list);
1362             return NULL;
1363         }
1364         PyList_SetItem(list, i, v);
1365     }
1366     return list;
1367 }
1368
1369 PyDoc_STRVAR(tolist_doc,
1370 "tolist() -> list\n\
1371 \n\
1372 Convert array to an ordinary list with the same items.");
1373
1374
1375 static PyObject *
1376 array_fromstring(arrayobject *self, PyObject *args)
1377 {
1378     char *str;
1379     Py_ssize_t n;
1380     int itemsize = self->ob_descr->itemsize;
1381     if (!PyArg_ParseTuple(args, "s#:fromstring", &str, &n))
1382         return NULL;
1383     if (n % itemsize != 0) {
1384         PyErr_SetString(PyExc_ValueError,
1385                    "string length not a multiple of item size");
1386         return NULL;
1387     }
1388     n = n / itemsize;
1389     if (n > 0) {
1390         char *item = self->ob_item;
1391         if ((n > PY_SSIZE_T_MAX - Py_SIZE(self)) ||
1392             ((Py_SIZE(self) + n) > PY_SSIZE_T_MAX / itemsize)) {
1393                 return PyErr_NoMemory();
1394         }
1395         PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1396         if (item == NULL) {
1397             PyErr_NoMemory();
1398             return NULL;
1399         }
1400         self->ob_item = item;
1401         Py_SIZE(self) += n;
1402         self->allocated = Py_SIZE(self);
1403         memcpy(item + (Py_SIZE(self) - n) * itemsize,
1404                str, itemsize*n);
1405     }
1406     Py_INCREF(Py_None);
1407     return Py_None;
1408 }
1409
1410 PyDoc_STRVAR(fromstring_doc,
1411 "fromstring(string)\n\
1412 \n\
1413 Appends items from the string, interpreting it as an array of machine\n\
1414 values,as if it had been read from a file using the fromfile() method).");
1415
1416
1417 static PyObject *
1418 array_tostring(arrayobject *self, PyObject *unused)
1419 {
1420     if (self->ob_size <= PY_SSIZE_T_MAX / self->ob_descr->itemsize) {
1421         return PyString_FromStringAndSize(self->ob_item,
1422                             Py_SIZE(self) * self->ob_descr->itemsize);
1423     } else {
1424         return PyErr_NoMemory();
1425     }
1426 }
1427
1428 PyDoc_STRVAR(tostring_doc,
1429 "tostring() -> string\n\
1430 \n\
1431 Convert the array to an array of machine values and return the string\n\
1432 representation.");
1433
1434
1435
1436 #ifdef Py_USING_UNICODE
1437 static PyObject *
1438 array_fromunicode(arrayobject *self, PyObject *args)
1439 {
1440     Py_UNICODE *ustr;
1441     Py_ssize_t n;
1442
1443     if (!PyArg_ParseTuple(args, "u#:fromunicode", &ustr, &n))
1444         return NULL;
1445     if (self->ob_descr->typecode != 'u') {
1446         PyErr_SetString(PyExc_ValueError,
1447             "fromunicode() may only be called on "
1448             "type 'u' arrays");
1449         return NULL;
1450     }
1451     if (n > 0) {
1452         Py_UNICODE *item = (Py_UNICODE *) self->ob_item;
1453         if (Py_SIZE(self) > PY_SSIZE_T_MAX - n) {
1454             return PyErr_NoMemory();
1455         }
1456         PyMem_RESIZE(item, Py_UNICODE, Py_SIZE(self) + n);
1457         if (item == NULL) {
1458             PyErr_NoMemory();
1459             return NULL;
1460         }
1461         self->ob_item = (char *) item;
1462         Py_SIZE(self) += n;
1463         self->allocated = Py_SIZE(self);
1464         memcpy(item + Py_SIZE(self) - n,
1465                ustr, n * sizeof(Py_UNICODE));
1466     }
1467
1468     Py_INCREF(Py_None);
1469     return Py_None;
1470 }
1471
1472 PyDoc_STRVAR(fromunicode_doc,
1473 "fromunicode(ustr)\n\
1474 \n\
1475 Extends this array with data from the unicode string ustr.\n\
1476 The array must be a type 'u' array; otherwise a ValueError\n\
1477 is raised.  Use array.fromstring(ustr.decode(...)) to\n\
1478 append Unicode data to an array of some other type.");
1479
1480
1481 static PyObject *
1482 array_tounicode(arrayobject *self, PyObject *unused)
1483 {
1484     if (self->ob_descr->typecode != 'u') {
1485         PyErr_SetString(PyExc_ValueError,
1486             "tounicode() may only be called on type 'u' arrays");
1487         return NULL;
1488     }
1489     return PyUnicode_FromUnicode((Py_UNICODE *) self->ob_item, Py_SIZE(self));
1490 }
1491
1492 PyDoc_STRVAR(tounicode_doc,
1493 "tounicode() -> unicode\n\
1494 \n\
1495 Convert the array to a unicode string.  The array must be\n\
1496 a type 'u' array; otherwise a ValueError is raised.  Use\n\
1497 array.tostring().decode() to obtain a unicode string from\n\
1498 an array of some other type.");
1499
1500 #endif /* Py_USING_UNICODE */
1501
1502 static PyObject *
1503 array_reduce(arrayobject *array)
1504 {
1505     PyObject *dict, *result, *list;
1506
1507     dict = PyObject_GetAttrString((PyObject *)array, "__dict__");
1508     if (dict == NULL) {
1509         if (!PyErr_ExceptionMatches(PyExc_AttributeError))
1510             return NULL;
1511         PyErr_Clear();
1512         dict = Py_None;
1513         Py_INCREF(dict);
1514     }
1515     /* Unlike in Python 3.x, we never use the more efficient memory
1516      * representation of an array for pickling.  This is unfortunately
1517      * necessary to allow array objects to be unpickled by Python 3.x,
1518      * since str objects from 2.x are always decoded to unicode in
1519      * Python 3.x.
1520      */
1521     list = array_tolist(array, NULL);
1522     if (list == NULL) {
1523         Py_DECREF(dict);
1524         return NULL;
1525     }
1526     result = Py_BuildValue(
1527         "O(cO)O", Py_TYPE(array), array->ob_descr->typecode, list, dict);
1528     Py_DECREF(list);
1529     Py_DECREF(dict);
1530     return result;
1531 }
1532
1533 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1534
1535 static PyObject *
1536 array_get_typecode(arrayobject *a, void *closure)
1537 {
1538     char tc = a->ob_descr->typecode;
1539     return PyString_FromStringAndSize(&tc, 1);
1540 }
1541
1542 static PyObject *
1543 array_get_itemsize(arrayobject *a, void *closure)
1544 {
1545     return PyInt_FromLong((long)a->ob_descr->itemsize);
1546 }
1547
1548 static PyGetSetDef array_getsets [] = {
1549     {"typecode", (getter) array_get_typecode, NULL,
1550      "the typecode character used to create the array"},
1551     {"itemsize", (getter) array_get_itemsize, NULL,
1552      "the size, in bytes, of one array item"},
1553     {NULL}
1554 };
1555
1556 static PyMethodDef array_methods[] = {
1557     {"append",          (PyCFunction)array_append,      METH_O,
1558      append_doc},
1559     {"buffer_info", (PyCFunction)array_buffer_info, METH_NOARGS,
1560      buffer_info_doc},
1561     {"byteswap",        (PyCFunction)array_byteswap,    METH_NOARGS,
1562      byteswap_doc},
1563     {"__copy__",        (PyCFunction)array_copy,        METH_NOARGS,
1564      copy_doc},
1565     {"count",           (PyCFunction)array_count,       METH_O,
1566      count_doc},
1567     {"__deepcopy__",(PyCFunction)array_copy,            METH_O,
1568      copy_doc},
1569     {"extend",      (PyCFunction)array_extend,          METH_O,
1570      extend_doc},
1571     {"fromfile",        (PyCFunction)array_fromfile,    METH_VARARGS,
1572      fromfile_doc},
1573     {"fromlist",        (PyCFunction)array_fromlist,    METH_O,
1574      fromlist_doc},
1575     {"fromstring",      (PyCFunction)array_fromstring,  METH_VARARGS,
1576      fromstring_doc},
1577 #ifdef Py_USING_UNICODE
1578     {"fromunicode",     (PyCFunction)array_fromunicode, METH_VARARGS,
1579      fromunicode_doc},
1580 #endif
1581     {"index",           (PyCFunction)array_index,       METH_O,
1582      index_doc},
1583     {"insert",          (PyCFunction)array_insert,      METH_VARARGS,
1584      insert_doc},
1585     {"pop",             (PyCFunction)array_pop,         METH_VARARGS,
1586      pop_doc},
1587     {"read",            (PyCFunction)array_fromfile_as_read,    METH_VARARGS,
1588      fromfile_doc},
1589     {"__reduce__",      (PyCFunction)array_reduce,      METH_NOARGS,
1590      reduce_doc},
1591     {"remove",          (PyCFunction)array_remove,      METH_O,
1592      remove_doc},
1593     {"reverse",         (PyCFunction)array_reverse,     METH_NOARGS,
1594      reverse_doc},
1595 /*      {"sort",        (PyCFunction)array_sort,        METH_VARARGS,
1596     sort_doc},*/
1597     {"tofile",          (PyCFunction)array_tofile,      METH_O,
1598      tofile_doc},
1599     {"tolist",          (PyCFunction)array_tolist,      METH_NOARGS,
1600      tolist_doc},
1601     {"tostring",        (PyCFunction)array_tostring,    METH_NOARGS,
1602      tostring_doc},
1603 #ifdef Py_USING_UNICODE
1604     {"tounicode",   (PyCFunction)array_tounicode,       METH_NOARGS,
1605      tounicode_doc},
1606 #endif
1607     {"write",           (PyCFunction)array_tofile_as_write,     METH_O,
1608      tofile_doc},
1609     {NULL,              NULL}           /* sentinel */
1610 };
1611
1612 static PyObject *
1613 array_repr(arrayobject *a)
1614 {
1615     char buf[256], typecode;
1616     PyObject *s, *t, *v = NULL;
1617     Py_ssize_t len;
1618
1619     len = Py_SIZE(a);
1620     typecode = a->ob_descr->typecode;
1621     if (len == 0) {
1622         PyOS_snprintf(buf, sizeof(buf), "array('%c')", typecode);
1623         return PyString_FromString(buf);
1624     }
1625
1626     if (typecode == 'c')
1627         v = array_tostring(a, NULL);
1628 #ifdef Py_USING_UNICODE
1629     else if (typecode == 'u')
1630         v = array_tounicode(a, NULL);
1631 #endif
1632     else
1633         v = array_tolist(a, NULL);
1634     t = PyObject_Repr(v);
1635     Py_XDECREF(v);
1636
1637     PyOS_snprintf(buf, sizeof(buf), "array('%c', ", typecode);
1638     s = PyString_FromString(buf);
1639     PyString_ConcatAndDel(&s, t);
1640     PyString_ConcatAndDel(&s, PyString_FromString(")"));
1641     return s;
1642 }
1643
1644 static PyObject*
1645 array_subscr(arrayobject* self, PyObject* item)
1646 {
1647     if (PyIndex_Check(item)) {
1648         Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1649         if (i==-1 && PyErr_Occurred()) {
1650             return NULL;
1651         }
1652         if (i < 0)
1653             i += Py_SIZE(self);
1654         return array_item(self, i);
1655     }
1656     else if (PySlice_Check(item)) {
1657         Py_ssize_t start, stop, step, slicelength, cur, i;
1658         PyObject* result;
1659         arrayobject* ar;
1660         int itemsize = self->ob_descr->itemsize;
1661
1662         if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
1663                          &start, &stop, &step, &slicelength) < 0) {
1664             return NULL;
1665         }
1666
1667         if (slicelength <= 0) {
1668             return newarrayobject(&Arraytype, 0, self->ob_descr);
1669         }
1670         else if (step == 1) {
1671             PyObject *result = newarrayobject(&Arraytype,
1672                                     slicelength, self->ob_descr);
1673             if (result == NULL)
1674                 return NULL;
1675             memcpy(((arrayobject *)result)->ob_item,
1676                    self->ob_item + start * itemsize,
1677                    slicelength * itemsize);
1678             return result;
1679         }
1680         else {
1681             result = newarrayobject(&Arraytype, slicelength, self->ob_descr);
1682             if (!result) return NULL;
1683
1684             ar = (arrayobject*)result;
1685
1686             for (cur = start, i = 0; i < slicelength;
1687                  cur += step, i++) {
1688                 memcpy(ar->ob_item + i*itemsize,
1689                        self->ob_item + cur*itemsize,
1690                        itemsize);
1691             }
1692
1693             return result;
1694         }
1695     }
1696     else {
1697         PyErr_SetString(PyExc_TypeError,
1698                         "array indices must be integers");
1699         return NULL;
1700     }
1701 }
1702
1703 static int
1704 array_ass_subscr(arrayobject* self, PyObject* item, PyObject* value)
1705 {
1706     Py_ssize_t start, stop, step, slicelength, needed;
1707     arrayobject* other;
1708     int itemsize;
1709
1710     if (PyIndex_Check(item)) {
1711         Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1712
1713         if (i == -1 && PyErr_Occurred())
1714             return -1;
1715         if (i < 0)
1716             i += Py_SIZE(self);
1717         if (i < 0 || i >= Py_SIZE(self)) {
1718             PyErr_SetString(PyExc_IndexError,
1719                 "array assignment index out of range");
1720             return -1;
1721         }
1722         if (value == NULL) {
1723             /* Fall through to slice assignment */
1724             start = i;
1725             stop = i + 1;
1726             step = 1;
1727             slicelength = 1;
1728         }
1729         else
1730             return (*self->ob_descr->setitem)(self, i, value);
1731     }
1732     else if (PySlice_Check(item)) {
1733         if (PySlice_GetIndicesEx((PySliceObject *)item,
1734                                  Py_SIZE(self), &start, &stop,
1735                                  &step, &slicelength) < 0) {
1736             return -1;
1737         }
1738     }
1739     else {
1740         PyErr_SetString(PyExc_TypeError,
1741                         "array indices must be integer");
1742         return -1;
1743     }
1744     if (value == NULL) {
1745         other = NULL;
1746         needed = 0;
1747     }
1748     else if (array_Check(value)) {
1749         other = (arrayobject *)value;
1750         needed = Py_SIZE(other);
1751         if (self == other) {
1752             /* Special case "self[i:j] = self" -- copy self first */
1753             int ret;
1754             value = array_slice(other, 0, needed);
1755             if (value == NULL)
1756                 return -1;
1757             ret = array_ass_subscr(self, item, value);
1758             Py_DECREF(value);
1759             return ret;
1760         }
1761         if (other->ob_descr != self->ob_descr) {
1762             PyErr_BadArgument();
1763             return -1;
1764         }
1765     }
1766     else {
1767         PyErr_Format(PyExc_TypeError,
1768          "can only assign array (not \"%.200s\") to array slice",
1769                          Py_TYPE(value)->tp_name);
1770         return -1;
1771     }
1772     itemsize = self->ob_descr->itemsize;
1773     /* for 'a[2:1] = ...', the insertion point is 'start', not 'stop' */
1774     if ((step > 0 && stop < start) ||
1775         (step < 0 && stop > start))
1776         stop = start;
1777     if (step == 1) {
1778         if (slicelength > needed) {
1779             memmove(self->ob_item + (start + needed) * itemsize,
1780                 self->ob_item + stop * itemsize,
1781                 (Py_SIZE(self) - stop) * itemsize);
1782             if (array_resize(self, Py_SIZE(self) +
1783                              needed - slicelength) < 0)
1784                 return -1;
1785         }
1786         else if (slicelength < needed) {
1787             if (array_resize(self, Py_SIZE(self) +
1788                              needed - slicelength) < 0)
1789                 return -1;
1790             memmove(self->ob_item + (start + needed) * itemsize,
1791                 self->ob_item + stop * itemsize,
1792                 (Py_SIZE(self) - start - needed) * itemsize);
1793         }
1794         if (needed > 0)
1795             memcpy(self->ob_item + start * itemsize,
1796                    other->ob_item, needed * itemsize);
1797         return 0;
1798     }
1799     else if (needed == 0) {
1800         /* Delete slice */
1801         size_t cur;
1802         Py_ssize_t i;
1803
1804         if (step < 0) {
1805             stop = start + 1;
1806             start = stop + step * (slicelength - 1) - 1;
1807             step = -step;
1808         }
1809         for (cur = start, i = 0; i < slicelength;
1810              cur += step, i++) {
1811             Py_ssize_t lim = step - 1;
1812
1813             if (cur + step >= (size_t)Py_SIZE(self))
1814                 lim = Py_SIZE(self) - cur - 1;
1815             memmove(self->ob_item + (cur - i) * itemsize,
1816                 self->ob_item + (cur + 1) * itemsize,
1817                 lim * itemsize);
1818         }
1819         cur = start + slicelength * step;
1820         if (cur < (size_t)Py_SIZE(self)) {
1821             memmove(self->ob_item + (cur-slicelength) * itemsize,
1822                 self->ob_item + cur * itemsize,
1823                 (Py_SIZE(self) - cur) * itemsize);
1824         }
1825         if (array_resize(self, Py_SIZE(self) - slicelength) < 0)
1826             return -1;
1827         return 0;
1828     }
1829     else {
1830         Py_ssize_t cur, i;
1831
1832         if (needed != slicelength) {
1833             PyErr_Format(PyExc_ValueError,
1834                 "attempt to assign array of size %zd "
1835                 "to extended slice of size %zd",
1836                 needed, slicelength);
1837             return -1;
1838         }
1839         for (cur = start, i = 0; i < slicelength;
1840              cur += step, i++) {
1841             memcpy(self->ob_item + cur * itemsize,
1842                    other->ob_item + i * itemsize,
1843                    itemsize);
1844         }
1845         return 0;
1846     }
1847 }
1848
1849 static PyMappingMethods array_as_mapping = {
1850     (lenfunc)array_length,
1851     (binaryfunc)array_subscr,
1852     (objobjargproc)array_ass_subscr
1853 };
1854
1855 static const void *emptybuf = "";
1856
1857 static Py_ssize_t
1858 array_buffer_getreadbuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1859 {
1860     if ( index != 0 ) {
1861         PyErr_SetString(PyExc_SystemError,
1862                         "Accessing non-existent array segment");
1863         return -1;
1864     }
1865     *ptr = (void *)self->ob_item;
1866     if (*ptr == NULL)
1867         *ptr = emptybuf;
1868     return Py_SIZE(self)*self->ob_descr->itemsize;
1869 }
1870
1871 static Py_ssize_t
1872 array_buffer_getwritebuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1873 {
1874     if ( index != 0 ) {
1875         PyErr_SetString(PyExc_SystemError,
1876                         "Accessing non-existent array segment");
1877         return -1;
1878     }
1879     *ptr = (void *)self->ob_item;
1880     if (*ptr == NULL)
1881         *ptr = emptybuf;
1882     return Py_SIZE(self)*self->ob_descr->itemsize;
1883 }
1884
1885 static Py_ssize_t
1886 array_buffer_getsegcount(arrayobject *self, Py_ssize_t *lenp)
1887 {
1888     if ( lenp )
1889         *lenp = Py_SIZE(self)*self->ob_descr->itemsize;
1890     return 1;
1891 }
1892
1893 static PySequenceMethods array_as_sequence = {
1894     (lenfunc)array_length,                      /*sq_length*/
1895     (binaryfunc)array_concat,               /*sq_concat*/
1896     (ssizeargfunc)array_repeat,                 /*sq_repeat*/
1897     (ssizeargfunc)array_item,                           /*sq_item*/
1898     (ssizessizeargfunc)array_slice,             /*sq_slice*/
1899     (ssizeobjargproc)array_ass_item,                    /*sq_ass_item*/
1900     (ssizessizeobjargproc)array_ass_slice,      /*sq_ass_slice*/
1901     (objobjproc)array_contains,                 /*sq_contains*/
1902     (binaryfunc)array_inplace_concat,           /*sq_inplace_concat*/
1903     (ssizeargfunc)array_inplace_repeat          /*sq_inplace_repeat*/
1904 };
1905
1906 static PyBufferProcs array_as_buffer = {
1907     (readbufferproc)array_buffer_getreadbuf,
1908     (writebufferproc)array_buffer_getwritebuf,
1909     (segcountproc)array_buffer_getsegcount,
1910     NULL,
1911 };
1912
1913 static PyObject *
1914 array_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1915 {
1916     char c;
1917     PyObject *initial = NULL, *it = NULL;
1918     struct arraydescr *descr;
1919
1920     if (type == &Arraytype && !_PyArg_NoKeywords("array.array()", kwds))
1921         return NULL;
1922
1923     if (!PyArg_ParseTuple(args, "c|O:array", &c, &initial))
1924         return NULL;
1925
1926     if (!(initial == NULL || PyList_Check(initial)
1927           || PyString_Check(initial) || PyTuple_Check(initial)
1928           || (c == 'u' && PyUnicode_Check(initial)))) {
1929         it = PyObject_GetIter(initial);
1930         if (it == NULL)
1931             return NULL;
1932         /* We set initial to NULL so that the subsequent code
1933            will create an empty array of the appropriate type
1934            and afterwards we can use array_iter_extend to populate
1935            the array.
1936         */
1937         initial = NULL;
1938     }
1939     for (descr = descriptors; descr->typecode != '\0'; descr++) {
1940         if (descr->typecode == c) {
1941             PyObject *a;
1942             Py_ssize_t len;
1943
1944             if (initial == NULL || !(PyList_Check(initial)
1945                 || PyTuple_Check(initial)))
1946                 len = 0;
1947             else
1948                 len = PySequence_Size(initial);
1949
1950             a = newarrayobject(type, len, descr);
1951             if (a == NULL)
1952                 return NULL;
1953
1954             if (len > 0) {
1955                 Py_ssize_t i;
1956                 for (i = 0; i < len; i++) {
1957                     PyObject *v =
1958                         PySequence_GetItem(initial, i);
1959                     if (v == NULL) {
1960                         Py_DECREF(a);
1961                         return NULL;
1962                     }
1963                     if (setarrayitem(a, i, v) != 0) {
1964                         Py_DECREF(v);
1965                         Py_DECREF(a);
1966                         return NULL;
1967                     }
1968                     Py_DECREF(v);
1969                 }
1970             } else if (initial != NULL && PyString_Check(initial)) {
1971                 PyObject *t_initial, *v;
1972                 t_initial = PyTuple_Pack(1, initial);
1973                 if (t_initial == NULL) {
1974                     Py_DECREF(a);
1975                     return NULL;
1976                 }
1977                 v = array_fromstring((arrayobject *)a,
1978                                          t_initial);
1979                 Py_DECREF(t_initial);
1980                 if (v == NULL) {
1981                     Py_DECREF(a);
1982                     return NULL;
1983                 }
1984                 Py_DECREF(v);
1985 #ifdef Py_USING_UNICODE
1986             } else if (initial != NULL && PyUnicode_Check(initial))  {
1987                 Py_ssize_t n = PyUnicode_GET_DATA_SIZE(initial);
1988                 if (n > 0) {
1989                     arrayobject *self = (arrayobject *)a;
1990                     char *item = self->ob_item;
1991                     item = (char *)PyMem_Realloc(item, n);
1992                     if (item == NULL) {
1993                         PyErr_NoMemory();
1994                         Py_DECREF(a);
1995                         return NULL;
1996                     }
1997                     self->ob_item = item;
1998                     Py_SIZE(self) = n / sizeof(Py_UNICODE);
1999                     memcpy(item, PyUnicode_AS_DATA(initial), n);
2000                     self->allocated = Py_SIZE(self);
2001                 }
2002 #endif
2003             }
2004             if (it != NULL) {
2005                 if (array_iter_extend((arrayobject *)a, it) == -1) {
2006                     Py_DECREF(it);
2007                     Py_DECREF(a);
2008                     return NULL;
2009                 }
2010                 Py_DECREF(it);
2011             }
2012             return a;
2013         }
2014     }
2015     PyErr_SetString(PyExc_ValueError,
2016         "bad typecode (must be c, b, B, u, h, H, i, I, l, L, f or d)");
2017     return NULL;
2018 }
2019
2020
2021 PyDoc_STRVAR(module_doc,
2022 "This module defines an object type which can efficiently represent\n\
2023 an array of basic values: characters, integers, floating point\n\
2024 numbers.  Arrays are sequence types and behave very much like lists,\n\
2025 except that the type of objects stored in them is constrained.  The\n\
2026 type is specified at object creation time by using a type code, which\n\
2027 is a single character.  The following type codes are defined:\n\
2028 \n\
2029     Type code   C Type             Minimum size in bytes \n\
2030     'c'         character          1 \n\
2031     'b'         signed integer     1 \n\
2032     'B'         unsigned integer   1 \n\
2033     'u'         Unicode character  2 \n\
2034     'h'         signed integer     2 \n\
2035     'H'         unsigned integer   2 \n\
2036     'i'         signed integer     2 \n\
2037     'I'         unsigned integer   2 \n\
2038     'l'         signed integer     4 \n\
2039     'L'         unsigned integer   4 \n\
2040     'f'         floating point     4 \n\
2041     'd'         floating point     8 \n\
2042 \n\
2043 The constructor is:\n\
2044 \n\
2045 array(typecode [, initializer]) -- create a new array\n\
2046 ");
2047
2048 PyDoc_STRVAR(arraytype_doc,
2049 "array(typecode [, initializer]) -> array\n\
2050 \n\
2051 Return a new array whose items are restricted by typecode, and\n\
2052 initialized from the optional initializer value, which must be a list,\n\
2053 string or iterable over elements of the appropriate type.\n\
2054 \n\
2055 Arrays represent basic values and behave very much like lists, except\n\
2056 the type of objects stored in them is constrained.\n\
2057 \n\
2058 Methods:\n\
2059 \n\
2060 append() -- append a new item to the end of the array\n\
2061 buffer_info() -- return information giving the current memory info\n\
2062 byteswap() -- byteswap all the items of the array\n\
2063 count() -- return number of occurrences of an object\n\
2064 extend() -- extend array by appending multiple elements from an iterable\n\
2065 fromfile() -- read items from a file object\n\
2066 fromlist() -- append items from the list\n\
2067 fromstring() -- append items from the string\n\
2068 index() -- return index of first occurrence of an object\n\
2069 insert() -- insert a new item into the array at a provided position\n\
2070 pop() -- remove and return item (default last)\n\
2071 read() -- DEPRECATED, use fromfile()\n\
2072 remove() -- remove first occurrence of an object\n\
2073 reverse() -- reverse the order of the items in the array\n\
2074 tofile() -- write all items to a file object\n\
2075 tolist() -- return the array converted to an ordinary list\n\
2076 tostring() -- return the array converted to a string\n\
2077 write() -- DEPRECATED, use tofile()\n\
2078 \n\
2079 Attributes:\n\
2080 \n\
2081 typecode -- the typecode character used to create the array\n\
2082 itemsize -- the length in bytes of one array item\n\
2083 ");
2084
2085 static PyObject *array_iter(arrayobject *ao);
2086
2087 static PyTypeObject Arraytype = {
2088     PyVarObject_HEAD_INIT(NULL, 0)
2089     "array.array",
2090     sizeof(arrayobject),
2091     0,
2092     (destructor)array_dealloc,                  /* tp_dealloc */
2093     0,                                          /* tp_print */
2094     0,                                          /* tp_getattr */
2095     0,                                          /* tp_setattr */
2096     0,                                          /* tp_compare */
2097     (reprfunc)array_repr,                       /* tp_repr */
2098     0,                                          /* tp_as_number*/
2099     &array_as_sequence,                         /* tp_as_sequence*/
2100     &array_as_mapping,                          /* tp_as_mapping*/
2101     0,                                          /* tp_hash */
2102     0,                                          /* tp_call */
2103     0,                                          /* tp_str */
2104     PyObject_GenericGetAttr,                    /* tp_getattro */
2105     0,                                          /* tp_setattro */
2106     &array_as_buffer,                           /* tp_as_buffer*/
2107     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS,  /* tp_flags */
2108     arraytype_doc,                              /* tp_doc */
2109     0,                                          /* tp_traverse */
2110     0,                                          /* tp_clear */
2111     array_richcompare,                          /* tp_richcompare */
2112     offsetof(arrayobject, weakreflist),         /* tp_weaklistoffset */
2113     (getiterfunc)array_iter,                    /* tp_iter */
2114     0,                                          /* tp_iternext */
2115     array_methods,                              /* tp_methods */
2116     0,                                          /* tp_members */
2117     array_getsets,                              /* tp_getset */
2118     0,                                          /* tp_base */
2119     0,                                          /* tp_dict */
2120     0,                                          /* tp_descr_get */
2121     0,                                          /* tp_descr_set */
2122     0,                                          /* tp_dictoffset */
2123     0,                                          /* tp_init */
2124     PyType_GenericAlloc,                        /* tp_alloc */
2125     array_new,                                  /* tp_new */
2126     PyObject_Del,                               /* tp_free */
2127 };
2128
2129
2130 /*********************** Array Iterator **************************/
2131
2132 typedef struct {
2133     PyObject_HEAD
2134     Py_ssize_t                          index;
2135     arrayobject                 *ao;
2136     PyObject                    * (*getitem)(struct arrayobject *, Py_ssize_t);
2137 } arrayiterobject;
2138
2139 static PyTypeObject PyArrayIter_Type;
2140
2141 #define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)
2142
2143 static PyObject *
2144 array_iter(arrayobject *ao)
2145 {
2146     arrayiterobject *it;
2147
2148     if (!array_Check(ao)) {
2149         PyErr_BadInternalCall();
2150         return NULL;
2151     }
2152
2153     it = PyObject_GC_New(arrayiterobject, &PyArrayIter_Type);
2154     if (it == NULL)
2155         return NULL;
2156
2157     Py_INCREF(ao);
2158     it->ao = ao;
2159     it->index = 0;
2160     it->getitem = ao->ob_descr->getitem;
2161     PyObject_GC_Track(it);
2162     return (PyObject *)it;
2163 }
2164
2165 static PyObject *
2166 arrayiter_next(arrayiterobject *it)
2167 {
2168     assert(PyArrayIter_Check(it));
2169     if (it->index < Py_SIZE(it->ao))
2170         return (*it->getitem)(it->ao, it->index++);
2171     return NULL;
2172 }
2173
2174 static void
2175 arrayiter_dealloc(arrayiterobject *it)
2176 {
2177     PyObject_GC_UnTrack(it);
2178     Py_XDECREF(it->ao);
2179     PyObject_GC_Del(it);
2180 }
2181
2182 static int
2183 arrayiter_traverse(arrayiterobject *it, visitproc visit, void *arg)
2184 {
2185     Py_VISIT(it->ao);
2186     return 0;
2187 }
2188
2189 static PyTypeObject PyArrayIter_Type = {
2190     PyVarObject_HEAD_INIT(NULL, 0)
2191     "arrayiterator",                        /* tp_name */
2192     sizeof(arrayiterobject),                /* tp_basicsize */
2193     0,                                      /* tp_itemsize */
2194     /* methods */
2195     (destructor)arrayiter_dealloc,              /* tp_dealloc */
2196     0,                                      /* tp_print */
2197     0,                                      /* tp_getattr */
2198     0,                                      /* tp_setattr */
2199     0,                                      /* tp_compare */
2200     0,                                      /* tp_repr */
2201     0,                                      /* tp_as_number */
2202     0,                                      /* tp_as_sequence */
2203     0,                                      /* tp_as_mapping */
2204     0,                                      /* tp_hash */
2205     0,                                      /* tp_call */
2206     0,                                      /* tp_str */
2207     PyObject_GenericGetAttr,                /* tp_getattro */
2208     0,                                      /* tp_setattro */
2209     0,                                      /* tp_as_buffer */
2210     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2211     0,                                      /* tp_doc */
2212     (traverseproc)arrayiter_traverse,           /* tp_traverse */
2213     0,                                          /* tp_clear */
2214     0,                                      /* tp_richcompare */
2215     0,                                      /* tp_weaklistoffset */
2216     PyObject_SelfIter,                          /* tp_iter */
2217     (iternextfunc)arrayiter_next,               /* tp_iternext */
2218     0,                                          /* tp_methods */
2219 };
2220
2221
2222 /*********************** Install Module **************************/
2223
2224 /* No functions in array module. */
2225 static PyMethodDef a_methods[] = {
2226     {NULL, NULL, 0, NULL}        /* Sentinel */
2227 };
2228
2229
2230 PyMODINIT_FUNC
2231 initarray(void)
2232 {
2233     PyObject *m;
2234
2235     Arraytype.ob_type = &PyType_Type;
2236     PyArrayIter_Type.ob_type = &PyType_Type;
2237     m = Py_InitModule3("array", a_methods, module_doc);
2238     if (m == NULL)
2239         return;
2240
2241     Py_INCREF((PyObject *)&Arraytype);
2242     PyModule_AddObject(m, "ArrayType", (PyObject *)&Arraytype);
2243     Py_INCREF((PyObject *)&Arraytype);
2244     PyModule_AddObject(m, "array", (PyObject *)&Arraytype);
2245     /* No need to check the error here, the caller will do that */
2246 }