l4/pkg/python/contrib/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, (int) 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, (int) 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_reduce(arrayobject *array)
1161 {
1162         PyObject *dict, *result;
1163
1164         dict = PyObject_GetAttrString((PyObject *)array, "__dict__");
1165         if (dict == NULL) {
1166                 PyErr_Clear();
1167                 dict = Py_None;
1168                 Py_INCREF(dict);
1169         }
1170         if (Py_SIZE(array) > 0) {
1171                 if (array->ob_descr->itemsize
1172                                 > PY_SSIZE_T_MAX / array->ob_size) {
1173                         return PyErr_NoMemory();
1174                 }
1175                 result = Py_BuildValue("O(cs#)O",
1176                         Py_TYPE(array),
1177                         array->ob_descr->typecode,
1178                         array->ob_item,
1179                         Py_SIZE(array) * array->ob_descr->itemsize,
1180                         dict);
1181         } else {
1182                 result = Py_BuildValue("O(c)O",
1183                         Py_TYPE(array),
1184                         array->ob_descr->typecode,
1185                         dict);
1186         }
1187         Py_DECREF(dict);
1188         return result;
1189 }
1190
1191 PyDoc_STRVAR(array_doc, "Return state information for pickling.");
1192
1193 static PyObject *
1194 array_reverse(arrayobject *self, PyObject *unused)
1195 {
1196         register Py_ssize_t itemsize = self->ob_descr->itemsize;
1197         register char *p, *q;
1198         /* little buffer to hold items while swapping */
1199         char tmp[256];  /* 8 is probably enough -- but why skimp */
1200         assert((size_t)itemsize <= sizeof(tmp));
1201
1202         if (Py_SIZE(self) > 1) {
1203                 for (p = self->ob_item,
1204                      q = self->ob_item + (Py_SIZE(self) - 1)*itemsize;
1205                      p < q;
1206                      p += itemsize, q -= itemsize) {
1207                         /* memory areas guaranteed disjoint, so memcpy
1208                          * is safe (& memmove may be slower).
1209                          */
1210                         memcpy(tmp, p, itemsize);
1211                         memcpy(p, q, itemsize);
1212                         memcpy(q, tmp, itemsize);
1213                 }
1214         }
1215
1216         Py_INCREF(Py_None);
1217         return Py_None;
1218 }
1219
1220 PyDoc_STRVAR(reverse_doc,
1221 "reverse()\n\
1222 \n\
1223 Reverse the order of the items in the array.");
1224
1225 static PyObject *
1226 array_fromfile(arrayobject *self, PyObject *args)
1227 {
1228         PyObject *f;
1229         Py_ssize_t n;
1230         FILE *fp;
1231         if (!PyArg_ParseTuple(args, "On:fromfile", &f, &n))
1232                 return NULL;
1233         fp = PyFile_AsFile(f);
1234         if (fp == NULL) {
1235                 PyErr_SetString(PyExc_TypeError, "arg1 must be open file");
1236                 return NULL;
1237         }
1238         if (n > 0) {
1239                 char *item = self->ob_item;
1240                 Py_ssize_t itemsize = self->ob_descr->itemsize;
1241                 size_t nread;
1242                 Py_ssize_t newlength;
1243                 size_t newbytes;
1244                 /* Be careful here about overflow */
1245                 if ((newlength = Py_SIZE(self) + n) <= 0 ||
1246                     (newbytes = newlength * itemsize) / itemsize !=
1247                     (size_t)newlength)
1248                         goto nomem;
1249                 PyMem_RESIZE(item, char, newbytes);
1250                 if (item == NULL) {
1251                   nomem:
1252                         PyErr_NoMemory();
1253                         return NULL;
1254                 }
1255                 self->ob_item = item;
1256                 Py_SIZE(self) += n;
1257                 self->allocated = Py_SIZE(self);
1258                 nread = fread(item + (Py_SIZE(self) - n) * itemsize,
1259                               itemsize, n, fp);
1260                 if (nread < (size_t)n) {
1261                   Py_SIZE(self) -= (n - nread);
1262                         PyMem_RESIZE(item, char, Py_SIZE(self)*itemsize);
1263                         self->ob_item = item;
1264                         self->allocated = Py_SIZE(self);
1265                         PyErr_SetString(PyExc_EOFError,
1266                                          "not enough items in file");
1267                         return NULL;
1268                 }
1269         }
1270         Py_INCREF(Py_None);
1271         return Py_None;
1272 }
1273
1274 PyDoc_STRVAR(fromfile_doc,
1275 "fromfile(f, n)\n\
1276 \n\
1277 Read n objects from the file object f and append them to the end of the\n\
1278 array.  Also called as read.");
1279
1280
1281 static PyObject *
1282 array_fromfile_as_read(arrayobject *self, PyObject *args)
1283 {
1284         if (PyErr_WarnPy3k("array.read() not supported in 3.x; "
1285                            "use array.fromfile()", 1) < 0)
1286                 return NULL;
1287         return array_fromfile(self, args);
1288 }
1289
1290
1291 static PyObject *
1292 array_tofile(arrayobject *self, PyObject *f)
1293 {
1294         FILE *fp;
1295
1296         fp = PyFile_AsFile(f);
1297         if (fp == NULL) {
1298                 PyErr_SetString(PyExc_TypeError, "arg must be open file");
1299                 return NULL;
1300         }
1301         if (self->ob_size > 0) {
1302                 if (fwrite(self->ob_item, self->ob_descr->itemsize,
1303                            self->ob_size, fp) != (size_t)self->ob_size) {
1304                         PyErr_SetFromErrno(PyExc_IOError);
1305                         clearerr(fp);
1306                         return NULL;
1307                 }
1308         }
1309         Py_INCREF(Py_None);
1310         return Py_None;
1311 }
1312
1313 PyDoc_STRVAR(tofile_doc,
1314 "tofile(f)\n\
1315 \n\
1316 Write all items (as machine values) to the file object f.  Also called as\n\
1317 write.");
1318
1319
1320 static PyObject *
1321 array_tofile_as_write(arrayobject *self, PyObject *f)
1322 {
1323         if (PyErr_WarnPy3k("array.write() not supported in 3.x; "
1324                            "use array.tofile()", 1) < 0)
1325                 return NULL;
1326         return array_tofile(self, f);
1327 }
1328
1329
1330 static PyObject *
1331 array_fromlist(arrayobject *self, PyObject *list)
1332 {
1333         Py_ssize_t n;
1334         Py_ssize_t itemsize = self->ob_descr->itemsize;
1335
1336         if (!PyList_Check(list)) {
1337                 PyErr_SetString(PyExc_TypeError, "arg must be list");
1338                 return NULL;
1339         }
1340         n = PyList_Size(list);
1341         if (n > 0) {
1342                 char *item = self->ob_item;
1343                 Py_ssize_t i;
1344                 PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1345                 if (item == NULL) {
1346                         PyErr_NoMemory();
1347                         return NULL;
1348                 }
1349                 self->ob_item = item;
1350                 Py_SIZE(self) += n;
1351                 self->allocated = Py_SIZE(self);
1352                 for (i = 0; i < n; i++) {
1353                         PyObject *v = PyList_GetItem(list, i);
1354                         if ((*self->ob_descr->setitem)(self,
1355                                         Py_SIZE(self) - n + i, v) != 0) {
1356                                 Py_SIZE(self) -= n;
1357                                 if (itemsize && (self->ob_size > PY_SSIZE_T_MAX / itemsize)) {
1358                                         return PyErr_NoMemory();
1359                                 }
1360                                 PyMem_RESIZE(item, char,
1361                                                   Py_SIZE(self) * itemsize);
1362                                 self->ob_item = item;
1363                                 self->allocated = Py_SIZE(self);
1364                                 return NULL;
1365                         }
1366                 }
1367         }
1368         Py_INCREF(Py_None);
1369         return Py_None;
1370 }
1371
1372 PyDoc_STRVAR(fromlist_doc,
1373 "fromlist(list)\n\
1374 \n\
1375 Append items to array from list.");
1376
1377
1378 static PyObject *
1379 array_tolist(arrayobject *self, PyObject *unused)
1380 {
1381         PyObject *list = PyList_New(Py_SIZE(self));
1382         Py_ssize_t i;
1383
1384         if (list == NULL)
1385                 return NULL;
1386         for (i = 0; i < Py_SIZE(self); i++) {
1387                 PyObject *v = getarrayitem((PyObject *)self, i);
1388                 if (v == NULL) {
1389                         Py_DECREF(list);
1390                         return NULL;
1391                 }
1392                 PyList_SetItem(list, i, v);
1393         }
1394         return list;
1395 }
1396
1397 PyDoc_STRVAR(tolist_doc,
1398 "tolist() -> list\n\
1399 \n\
1400 Convert array to an ordinary list with the same items.");
1401
1402
1403 static PyObject *
1404 array_fromstring(arrayobject *self, PyObject *args)
1405 {
1406         char *str;
1407         Py_ssize_t n;
1408         int itemsize = self->ob_descr->itemsize;
1409         if (!PyArg_ParseTuple(args, "s#:fromstring", &str, &n))
1410                 return NULL;
1411         if (n % itemsize != 0) {
1412                 PyErr_SetString(PyExc_ValueError,
1413                            "string length not a multiple of item size");
1414                 return NULL;
1415         }
1416         n = n / itemsize;
1417         if (n > 0) {
1418                 char *item = self->ob_item;
1419                 if ((n > PY_SSIZE_T_MAX - Py_SIZE(self)) ||
1420                         ((Py_SIZE(self) + n) > PY_SSIZE_T_MAX / itemsize)) {
1421                                 return PyErr_NoMemory();
1422                 }
1423                 PyMem_RESIZE(item, char, (Py_SIZE(self) + n) * itemsize);
1424                 if (item == NULL) {
1425                         PyErr_NoMemory();
1426                         return NULL;
1427                 }
1428                 self->ob_item = item;
1429                 Py_SIZE(self) += n;
1430                 self->allocated = Py_SIZE(self);
1431                 memcpy(item + (Py_SIZE(self) - n) * itemsize,
1432                        str, itemsize*n);
1433         }
1434         Py_INCREF(Py_None);
1435         return Py_None;
1436 }
1437
1438 PyDoc_STRVAR(fromstring_doc,
1439 "fromstring(string)\n\
1440 \n\
1441 Appends items from the string, interpreting it as an array of machine\n\
1442 values,as if it had been read from a file using the fromfile() method).");
1443
1444
1445 static PyObject *
1446 array_tostring(arrayobject *self, PyObject *unused)
1447 {
1448         if (self->ob_size <= PY_SSIZE_T_MAX / self->ob_descr->itemsize) {
1449                 return PyString_FromStringAndSize(self->ob_item,
1450                                     Py_SIZE(self) * self->ob_descr->itemsize);
1451         } else {
1452                 return PyErr_NoMemory();
1453         }
1454 }
1455
1456 PyDoc_STRVAR(tostring_doc,
1457 "tostring() -> string\n\
1458 \n\
1459 Convert the array to an array of machine values and return the string\n\
1460 representation.");
1461
1462
1463
1464 #ifdef Py_USING_UNICODE
1465 static PyObject *
1466 array_fromunicode(arrayobject *self, PyObject *args)
1467 {
1468         Py_UNICODE *ustr;
1469         Py_ssize_t n;
1470
1471         if (!PyArg_ParseTuple(args, "u#:fromunicode", &ustr, &n))
1472                 return NULL;
1473         if (self->ob_descr->typecode != 'u') {
1474                 PyErr_SetString(PyExc_ValueError,
1475                         "fromunicode() may only be called on "
1476                         "type 'u' arrays");
1477                 return NULL;
1478         }
1479         if (n > 0) {
1480                 Py_UNICODE *item = (Py_UNICODE *) self->ob_item;
1481                 if (Py_SIZE(self) > PY_SSIZE_T_MAX - n) {
1482                         return PyErr_NoMemory();
1483                 }
1484                 PyMem_RESIZE(item, Py_UNICODE, Py_SIZE(self) + n);
1485                 if (item == NULL) {
1486                         PyErr_NoMemory();
1487                         return NULL;
1488                 }
1489                 self->ob_item = (char *) item;
1490                 Py_SIZE(self) += n;
1491                 self->allocated = Py_SIZE(self);
1492                 memcpy(item + Py_SIZE(self) - n,
1493                        ustr, n * sizeof(Py_UNICODE));
1494         }
1495
1496         Py_INCREF(Py_None);
1497         return Py_None;
1498 }
1499
1500 PyDoc_STRVAR(fromunicode_doc,
1501 "fromunicode(ustr)\n\
1502 \n\
1503 Extends this array with data from the unicode string ustr.\n\
1504 The array must be a type 'u' array; otherwise a ValueError\n\
1505 is raised.  Use array.fromstring(ustr.decode(...)) to\n\
1506 append Unicode data to an array of some other type.");
1507
1508
1509 static PyObject *
1510 array_tounicode(arrayobject *self, PyObject *unused)
1511 {
1512         if (self->ob_descr->typecode != 'u') {
1513                 PyErr_SetString(PyExc_ValueError,
1514                         "tounicode() may only be called on type 'u' arrays");
1515                 return NULL;
1516         }
1517         return PyUnicode_FromUnicode((Py_UNICODE *) self->ob_item, Py_SIZE(self));
1518 }
1519
1520 PyDoc_STRVAR(tounicode_doc,
1521 "tounicode() -> unicode\n\
1522 \n\
1523 Convert the array to a unicode string.  The array must be\n\
1524 a type 'u' array; otherwise a ValueError is raised.  Use\n\
1525 array.tostring().decode() to obtain a unicode string from\n\
1526 an array of some other type.");
1527
1528 #endif /* Py_USING_UNICODE */
1529
1530
1531 static PyObject *
1532 array_get_typecode(arrayobject *a, void *closure)
1533 {
1534         char tc = a->ob_descr->typecode;
1535         return PyString_FromStringAndSize(&tc, 1);
1536 }
1537
1538 static PyObject *
1539 array_get_itemsize(arrayobject *a, void *closure)
1540 {
1541         return PyInt_FromLong((long)a->ob_descr->itemsize);
1542 }
1543
1544 static PyGetSetDef array_getsets [] = {
1545         {"typecode", (getter) array_get_typecode, NULL,
1546          "the typecode character used to create the array"},
1547         {"itemsize", (getter) array_get_itemsize, NULL,
1548          "the size, in bytes, of one array item"},
1549         {NULL}
1550 };
1551
1552 static PyMethodDef array_methods[] = {
1553         {"append",      (PyCFunction)array_append,      METH_O,
1554          append_doc},
1555         {"buffer_info", (PyCFunction)array_buffer_info, METH_NOARGS,
1556          buffer_info_doc},
1557         {"byteswap",    (PyCFunction)array_byteswap,    METH_NOARGS,
1558          byteswap_doc},
1559         {"__copy__",    (PyCFunction)array_copy,        METH_NOARGS,
1560          copy_doc},
1561         {"count",       (PyCFunction)array_count,       METH_O,
1562          count_doc},
1563         {"__deepcopy__",(PyCFunction)array_copy,        METH_O,
1564          copy_doc},
1565         {"extend",      (PyCFunction)array_extend,      METH_O,
1566          extend_doc},
1567         {"fromfile",    (PyCFunction)array_fromfile,    METH_VARARGS,
1568          fromfile_doc},
1569         {"fromlist",    (PyCFunction)array_fromlist,    METH_O,
1570          fromlist_doc},
1571         {"fromstring",  (PyCFunction)array_fromstring,  METH_VARARGS,
1572          fromstring_doc},
1573 #ifdef Py_USING_UNICODE
1574         {"fromunicode", (PyCFunction)array_fromunicode, METH_VARARGS,
1575          fromunicode_doc},
1576 #endif
1577         {"index",       (PyCFunction)array_index,       METH_O,
1578          index_doc},
1579         {"insert",      (PyCFunction)array_insert,      METH_VARARGS,
1580          insert_doc},
1581         {"pop",         (PyCFunction)array_pop,         METH_VARARGS,
1582          pop_doc},
1583         {"read",        (PyCFunction)array_fromfile_as_read,    METH_VARARGS,
1584          fromfile_doc},
1585         {"__reduce__",  (PyCFunction)array_reduce,      METH_NOARGS,
1586          array_doc},
1587         {"remove",      (PyCFunction)array_remove,      METH_O,
1588          remove_doc},
1589         {"reverse",     (PyCFunction)array_reverse,     METH_NOARGS,
1590          reverse_doc},
1591 /*      {"sort",        (PyCFunction)array_sort,        METH_VARARGS,
1592         sort_doc},*/
1593         {"tofile",      (PyCFunction)array_tofile,      METH_O,
1594          tofile_doc},
1595         {"tolist",      (PyCFunction)array_tolist,      METH_NOARGS,
1596          tolist_doc},
1597         {"tostring",    (PyCFunction)array_tostring,    METH_NOARGS,
1598          tostring_doc},
1599 #ifdef Py_USING_UNICODE
1600         {"tounicode",   (PyCFunction)array_tounicode,   METH_NOARGS,
1601          tounicode_doc},
1602 #endif
1603         {"write",       (PyCFunction)array_tofile_as_write,     METH_O,
1604          tofile_doc},
1605         {NULL,          NULL}           /* sentinel */
1606 };
1607
1608 static PyObject *
1609 array_repr(arrayobject *a)
1610 {
1611         char buf[256], typecode;
1612         PyObject *s, *t, *v = NULL;
1613         Py_ssize_t len;
1614
1615         len = Py_SIZE(a);
1616         typecode = a->ob_descr->typecode;
1617         if (len == 0) {
1618                 PyOS_snprintf(buf, sizeof(buf), "array('%c')", typecode);
1619                 return PyString_FromString(buf);
1620         }
1621
1622         if (typecode == 'c')
1623                 v = array_tostring(a, NULL);
1624 #ifdef Py_USING_UNICODE
1625         else if (typecode == 'u')
1626                 v = array_tounicode(a, NULL);
1627 #endif
1628         else
1629                 v = array_tolist(a, NULL);
1630         t = PyObject_Repr(v);
1631         Py_XDECREF(v);
1632
1633         PyOS_snprintf(buf, sizeof(buf), "array('%c', ", typecode);
1634         s = PyString_FromString(buf);
1635         PyString_ConcatAndDel(&s, t);
1636         PyString_ConcatAndDel(&s, PyString_FromString(")"));
1637         return s;
1638 }
1639
1640 static PyObject*
1641 array_subscr(arrayobject* self, PyObject* item)
1642 {
1643         if (PyIndex_Check(item)) {
1644                 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1645                 if (i==-1 && PyErr_Occurred()) {
1646                         return NULL;
1647                 }
1648                 if (i < 0)
1649                         i += Py_SIZE(self);
1650                 return array_item(self, i);
1651         }
1652         else if (PySlice_Check(item)) {
1653                 Py_ssize_t start, stop, step, slicelength, cur, i;
1654                 PyObject* result;
1655                 arrayobject* ar;
1656                 int itemsize = self->ob_descr->itemsize;
1657
1658                 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
1659                                  &start, &stop, &step, &slicelength) < 0) {
1660                         return NULL;
1661                 }
1662
1663                 if (slicelength <= 0) {
1664                         return newarrayobject(&Arraytype, 0, self->ob_descr);
1665                 }
1666                 else if (step == 1) {
1667                         PyObject *result = newarrayobject(&Arraytype,
1668                                                 slicelength, self->ob_descr);
1669                         if (result == NULL)
1670                                 return NULL;
1671                         memcpy(((arrayobject *)result)->ob_item,
1672                                self->ob_item + start * itemsize,
1673                                slicelength * itemsize);
1674                         return result;
1675                 }
1676                 else {
1677                         result = newarrayobject(&Arraytype, slicelength, self->ob_descr);
1678                         if (!result) return NULL;
1679
1680                         ar = (arrayobject*)result;
1681
1682                         for (cur = start, i = 0; i < slicelength;
1683                              cur += step, i++) {
1684                                 memcpy(ar->ob_item + i*itemsize,
1685                                        self->ob_item + cur*itemsize,
1686                                        itemsize);
1687                         }
1688
1689                         return result;
1690                 }
1691         }
1692         else {
1693                 PyErr_SetString(PyExc_TypeError,
1694                                 "array indices must be integers");
1695                 return NULL;
1696         }
1697 }
1698
1699 static int
1700 array_ass_subscr(arrayobject* self, PyObject* item, PyObject* value)
1701 {
1702         Py_ssize_t start, stop, step, slicelength, needed;
1703         arrayobject* other;
1704         int itemsize;
1705
1706         if (PyIndex_Check(item)) {
1707                 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
1708
1709                 if (i == -1 && PyErr_Occurred())
1710                         return -1;
1711                 if (i < 0)
1712                         i += Py_SIZE(self);
1713                 if (i < 0 || i >= Py_SIZE(self)) {
1714                         PyErr_SetString(PyExc_IndexError,
1715                                 "array assignment index out of range");
1716                         return -1;
1717                 }
1718                 if (value == NULL) {
1719                         /* Fall through to slice assignment */
1720                         start = i;
1721                         stop = i + 1;
1722                         step = 1;
1723                         slicelength = 1;
1724                 }
1725                 else
1726                         return (*self->ob_descr->setitem)(self, i, value);
1727         }
1728         else if (PySlice_Check(item)) {
1729                 if (PySlice_GetIndicesEx((PySliceObject *)item,
1730                                          Py_SIZE(self), &start, &stop,
1731                                          &step, &slicelength) < 0) {
1732                         return -1;
1733                 }
1734         }
1735         else {
1736                 PyErr_SetString(PyExc_TypeError,
1737                                 "array indices must be integer");
1738                 return -1;
1739         }
1740         if (value == NULL) {
1741                 other = NULL;
1742                 needed = 0;
1743         }
1744         else if (array_Check(value)) {
1745                 other = (arrayobject *)value;
1746                 needed = Py_SIZE(other);
1747                 if (self == other) {
1748                         /* Special case "self[i:j] = self" -- copy self first */
1749                         int ret;
1750                         value = array_slice(other, 0, needed);
1751                         if (value == NULL)
1752                                 return -1;
1753                         ret = array_ass_subscr(self, item, value);
1754                         Py_DECREF(value);
1755                         return ret;
1756                 }
1757                 if (other->ob_descr != self->ob_descr) {
1758                         PyErr_BadArgument();
1759                         return -1;
1760                 }
1761         }
1762         else {
1763                 PyErr_Format(PyExc_TypeError,
1764              "can only assign array (not \"%.200s\") to array slice",
1765                              Py_TYPE(value)->tp_name);
1766                 return -1;
1767         }
1768         itemsize = self->ob_descr->itemsize;
1769         /* for 'a[2:1] = ...', the insertion point is 'start', not 'stop' */
1770         if ((step > 0 && stop < start) ||
1771             (step < 0 && stop > start))
1772                 stop = start;
1773         if (step == 1) {
1774                 if (slicelength > needed) {
1775                         memmove(self->ob_item + (start + needed) * itemsize,
1776                                 self->ob_item + stop * itemsize,
1777                                 (Py_SIZE(self) - stop) * itemsize);
1778                         if (array_resize(self, Py_SIZE(self) +
1779                                          needed - slicelength) < 0)
1780                                 return -1;
1781                 }
1782                 else if (slicelength < needed) {
1783                         if (array_resize(self, Py_SIZE(self) +
1784                                          needed - slicelength) < 0)
1785                                 return -1;
1786                         memmove(self->ob_item + (start + needed) * itemsize,
1787                                 self->ob_item + stop * itemsize,
1788                                 (Py_SIZE(self) - start - needed) * itemsize);
1789                 }
1790                 if (needed > 0)
1791                         memcpy(self->ob_item + start * itemsize,
1792                                other->ob_item, needed * itemsize);
1793                 return 0;
1794         }
1795         else if (needed == 0) {
1796                 /* Delete slice */
1797                 Py_ssize_t cur, i;
1798
1799                 if (step < 0) {
1800                         stop = start + 1;
1801                         start = stop + step * (slicelength - 1) - 1;
1802                         step = -step;
1803                 }
1804                 for (cur = start, i = 0; i < slicelength;
1805                      cur += step, i++) {
1806                         Py_ssize_t lim = step - 1;
1807
1808                         if (cur + step >= Py_SIZE(self))
1809                                 lim = Py_SIZE(self) - cur - 1;
1810                         memmove(self->ob_item + (cur - i) * itemsize,
1811                                 self->ob_item + (cur + 1) * itemsize,
1812                                 lim * itemsize);
1813                 }
1814                 cur = start + slicelength * step;
1815                 if (cur < Py_SIZE(self)) {
1816                         memmove(self->ob_item + (cur-slicelength) * itemsize,
1817                                 self->ob_item + cur * itemsize,
1818                                 (Py_SIZE(self) - cur) * itemsize);
1819                 }
1820                 if (array_resize(self, Py_SIZE(self) - slicelength) < 0)
1821                         return -1;
1822                 return 0;
1823         }
1824         else {
1825                 Py_ssize_t cur, i;
1826
1827                 if (needed != slicelength) {
1828                         PyErr_Format(PyExc_ValueError,
1829                                 "attempt to assign array of size %zd "
1830                                 "to extended slice of size %zd",
1831                                 needed, slicelength);
1832                         return -1;
1833                 }
1834                 for (cur = start, i = 0; i < slicelength;
1835                      cur += step, i++) {
1836                         memcpy(self->ob_item + cur * itemsize,
1837                                other->ob_item + i * itemsize,
1838                                itemsize);
1839                 }
1840                 return 0;
1841         }
1842 }
1843
1844 static PyMappingMethods array_as_mapping = {
1845         (lenfunc)array_length,
1846         (binaryfunc)array_subscr,
1847         (objobjargproc)array_ass_subscr
1848 };
1849
1850 static const void *emptybuf = "";
1851
1852 static Py_ssize_t
1853 array_buffer_getreadbuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1854 {
1855         if ( index != 0 ) {
1856                 PyErr_SetString(PyExc_SystemError,
1857                                 "Accessing non-existent array segment");
1858                 return -1;
1859         }
1860         *ptr = (void *)self->ob_item;
1861         if (*ptr == NULL)
1862                 *ptr = emptybuf;
1863         return Py_SIZE(self)*self->ob_descr->itemsize;
1864 }
1865
1866 static Py_ssize_t
1867 array_buffer_getwritebuf(arrayobject *self, Py_ssize_t index, const void **ptr)
1868 {
1869         if ( index != 0 ) {
1870                 PyErr_SetString(PyExc_SystemError,
1871                                 "Accessing non-existent array segment");
1872                 return -1;
1873         }
1874         *ptr = (void *)self->ob_item;
1875         if (*ptr == NULL)
1876                 *ptr = emptybuf;
1877         return Py_SIZE(self)*self->ob_descr->itemsize;
1878 }
1879
1880 static Py_ssize_t
1881 array_buffer_getsegcount(arrayobject *self, Py_ssize_t *lenp)
1882 {
1883         if ( lenp )
1884                 *lenp = Py_SIZE(self)*self->ob_descr->itemsize;
1885         return 1;
1886 }
1887
1888 static PySequenceMethods array_as_sequence = {
1889         (lenfunc)array_length,                  /*sq_length*/
1890         (binaryfunc)array_concat,               /*sq_concat*/
1891         (ssizeargfunc)array_repeat,             /*sq_repeat*/
1892         (ssizeargfunc)array_item,                       /*sq_item*/
1893         (ssizessizeargfunc)array_slice,         /*sq_slice*/
1894         (ssizeobjargproc)array_ass_item,                /*sq_ass_item*/
1895         (ssizessizeobjargproc)array_ass_slice,  /*sq_ass_slice*/
1896         (objobjproc)array_contains,             /*sq_contains*/
1897         (binaryfunc)array_inplace_concat,       /*sq_inplace_concat*/
1898         (ssizeargfunc)array_inplace_repeat      /*sq_inplace_repeat*/
1899 };
1900
1901 static PyBufferProcs array_as_buffer = {
1902         (readbufferproc)array_buffer_getreadbuf,
1903         (writebufferproc)array_buffer_getwritebuf,
1904         (segcountproc)array_buffer_getsegcount,
1905         NULL,
1906 };
1907
1908 static PyObject *
1909 array_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1910 {
1911         char c;
1912         PyObject *initial = NULL, *it = NULL;
1913         struct arraydescr *descr;
1914
1915         if (type == &Arraytype && !_PyArg_NoKeywords("array.array()", kwds))
1916                 return NULL;
1917
1918         if (!PyArg_ParseTuple(args, "c|O:array", &c, &initial))
1919                 return NULL;
1920
1921         if (!(initial == NULL || PyList_Check(initial)
1922               || PyString_Check(initial) || PyTuple_Check(initial)
1923               || (c == 'u' && PyUnicode_Check(initial)))) {
1924                 it = PyObject_GetIter(initial);
1925                 if (it == NULL)
1926                         return NULL;
1927                 /* We set initial to NULL so that the subsequent code
1928                    will create an empty array of the appropriate type
1929                    and afterwards we can use array_iter_extend to populate
1930                    the array.
1931                 */
1932                 initial = NULL;
1933         }
1934         for (descr = descriptors; descr->typecode != '\0'; descr++) {
1935                 if (descr->typecode == c) {
1936                         PyObject *a;
1937                         Py_ssize_t len;
1938
1939                         if (initial == NULL || !(PyList_Check(initial)
1940                                 || PyTuple_Check(initial)))
1941                                 len = 0;
1942                         else
1943                                 len = PySequence_Size(initial);
1944
1945                         a = newarrayobject(type, len, descr);
1946                         if (a == NULL)
1947                                 return NULL;
1948
1949                         if (len > 0) {
1950                                 Py_ssize_t i;
1951                                 for (i = 0; i < len; i++) {
1952                                         PyObject *v =
1953                                                 PySequence_GetItem(initial, i);
1954                                         if (v == NULL) {
1955                                                 Py_DECREF(a);
1956                                                 return NULL;
1957                                         }
1958                                         if (setarrayitem(a, i, v) != 0) {
1959                                                 Py_DECREF(v);
1960                                                 Py_DECREF(a);
1961                                                 return NULL;
1962                                         }
1963                                         Py_DECREF(v);
1964                                 }
1965                         } else if (initial != NULL && PyString_Check(initial)) {
1966                                 PyObject *t_initial, *v;
1967                                 t_initial = PyTuple_Pack(1, initial);
1968                                 if (t_initial == NULL) {
1969                                         Py_DECREF(a);
1970                                         return NULL;
1971                                 }
1972                                 v = array_fromstring((arrayobject *)a,
1973                                                          t_initial);
1974                                 Py_DECREF(t_initial);
1975                                 if (v == NULL) {
1976                                         Py_DECREF(a);
1977                                         return NULL;
1978                                 }
1979                                 Py_DECREF(v);
1980 #ifdef Py_USING_UNICODE
1981                         } else if (initial != NULL && PyUnicode_Check(initial))  {
1982                                 Py_ssize_t n = PyUnicode_GET_DATA_SIZE(initial);
1983                                 if (n > 0) {
1984                                         arrayobject *self = (arrayobject *)a;
1985                                         char *item = self->ob_item;
1986                                         item = (char *)PyMem_Realloc(item, n);
1987                                         if (item == NULL) {
1988                                                 PyErr_NoMemory();
1989                                                 Py_DECREF(a);
1990                                                 return NULL;
1991                                         }
1992                                         self->ob_item = item;
1993                                         Py_SIZE(self) = n / sizeof(Py_UNICODE);
1994                                         memcpy(item, PyUnicode_AS_DATA(initial), n);
1995                                         self->allocated = Py_SIZE(self);
1996                                 }
1997 #endif
1998                         }
1999                         if (it != NULL) {
2000                                 if (array_iter_extend((arrayobject *)a, it) == -1) {
2001                                         Py_DECREF(it);
2002                                         Py_DECREF(a);
2003                                         return NULL;
2004                                 }
2005                                 Py_DECREF(it);
2006                         }
2007                         return a;
2008                 }
2009         }
2010         PyErr_SetString(PyExc_ValueError,
2011                 "bad typecode (must be c, b, B, u, h, H, i, I, l, L, f or d)");
2012         return NULL;
2013 }
2014
2015
2016 PyDoc_STRVAR(module_doc,
2017 "This module defines an object type which can efficiently represent\n\
2018 an array of basic values: characters, integers, floating point\n\
2019 numbers.  Arrays are sequence types and behave very much like lists,\n\
2020 except that the type of objects stored in them is constrained.  The\n\
2021 type is specified at object creation time by using a type code, which\n\
2022 is a single character.  The following type codes are defined:\n\
2023 \n\
2024     Type code   C Type             Minimum size in bytes \n\
2025     'c'         character          1 \n\
2026     'b'         signed integer     1 \n\
2027     'B'         unsigned integer   1 \n\
2028     'u'         Unicode character  2 \n\
2029     'h'         signed integer     2 \n\
2030     'H'         unsigned integer   2 \n\
2031     'i'         signed integer     2 \n\
2032     'I'         unsigned integer   2 \n\
2033     'l'         signed integer     4 \n\
2034     'L'         unsigned integer   4 \n\
2035     'f'         floating point     4 \n\
2036     'd'         floating point     8 \n\
2037 \n\
2038 The constructor is:\n\
2039 \n\
2040 array(typecode [, initializer]) -- create a new array\n\
2041 ");
2042
2043 PyDoc_STRVAR(arraytype_doc,
2044 "array(typecode [, initializer]) -> array\n\
2045 \n\
2046 Return a new array whose items are restricted by typecode, and\n\
2047 initialized from the optional initializer value, which must be a list,\n\
2048 string. or iterable over elements of the appropriate type.\n\
2049 \n\
2050 Arrays represent basic values and behave very much like lists, except\n\
2051 the type of objects stored in them is constrained.\n\
2052 \n\
2053 Methods:\n\
2054 \n\
2055 append() -- append a new item to the end of the array\n\
2056 buffer_info() -- return information giving the current memory info\n\
2057 byteswap() -- byteswap all the items of the array\n\
2058 count() -- return number of occurrences of an object\n\
2059 extend() -- extend array by appending multiple elements from an iterable\n\
2060 fromfile() -- read items from a file object\n\
2061 fromlist() -- append items from the list\n\
2062 fromstring() -- append items from the string\n\
2063 index() -- return index of first occurrence of an object\n\
2064 insert() -- insert a new item into the array at a provided position\n\
2065 pop() -- remove and return item (default last)\n\
2066 read() -- DEPRECATED, use fromfile()\n\
2067 remove() -- remove first occurrence of an object\n\
2068 reverse() -- reverse the order of the items in the array\n\
2069 tofile() -- write all items to a file object\n\
2070 tolist() -- return the array converted to an ordinary list\n\
2071 tostring() -- return the array converted to a string\n\
2072 write() -- DEPRECATED, use tofile()\n\
2073 \n\
2074 Attributes:\n\
2075 \n\
2076 typecode -- the typecode character used to create the array\n\
2077 itemsize -- the length in bytes of one array item\n\
2078 ");
2079
2080 static PyObject *array_iter(arrayobject *ao);
2081
2082 static PyTypeObject Arraytype = {
2083         PyVarObject_HEAD_INIT(NULL, 0)
2084         "array.array",
2085         sizeof(arrayobject),
2086         0,
2087         (destructor)array_dealloc,              /* tp_dealloc */
2088         0,                                      /* tp_print */
2089         0,                                      /* tp_getattr */
2090         0,                                      /* tp_setattr */
2091         0,                                      /* tp_compare */
2092         (reprfunc)array_repr,                   /* tp_repr */
2093         0,                                      /* tp_as_number*/
2094         &array_as_sequence,                     /* tp_as_sequence*/
2095         &array_as_mapping,                      /* tp_as_mapping*/
2096         0,                                      /* tp_hash */
2097         0,                                      /* tp_call */
2098         0,                                      /* tp_str */
2099         PyObject_GenericGetAttr,                /* tp_getattro */
2100         0,                                      /* tp_setattro */
2101         &array_as_buffer,                       /* tp_as_buffer*/
2102         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_WEAKREFS,  /* tp_flags */
2103         arraytype_doc,                          /* tp_doc */
2104         0,                                      /* tp_traverse */
2105         0,                                      /* tp_clear */
2106         array_richcompare,                      /* tp_richcompare */
2107         offsetof(arrayobject, weakreflist),     /* tp_weaklistoffset */
2108         (getiterfunc)array_iter,                /* tp_iter */
2109         0,                                      /* tp_iternext */
2110         array_methods,                          /* tp_methods */
2111         0,                                      /* tp_members */
2112         array_getsets,                          /* tp_getset */
2113         0,                                      /* tp_base */
2114         0,                                      /* tp_dict */
2115         0,                                      /* tp_descr_get */
2116         0,                                      /* tp_descr_set */
2117         0,                                      /* tp_dictoffset */
2118         0,                                      /* tp_init */
2119         PyType_GenericAlloc,                    /* tp_alloc */
2120         array_new,                              /* tp_new */
2121         PyObject_Del,                           /* tp_free */
2122 };
2123
2124
2125 /*********************** Array Iterator **************************/
2126
2127 typedef struct {
2128         PyObject_HEAD
2129         Py_ssize_t                      index;
2130         arrayobject             *ao;
2131         PyObject                * (*getitem)(struct arrayobject *, Py_ssize_t);
2132 } arrayiterobject;
2133
2134 static PyTypeObject PyArrayIter_Type;
2135
2136 #define PyArrayIter_Check(op) PyObject_TypeCheck(op, &PyArrayIter_Type)
2137
2138 static PyObject *
2139 array_iter(arrayobject *ao)
2140 {
2141         arrayiterobject *it;
2142
2143         if (!array_Check(ao)) {
2144                 PyErr_BadInternalCall();
2145                 return NULL;
2146         }
2147
2148         it = PyObject_GC_New(arrayiterobject, &PyArrayIter_Type);
2149         if (it == NULL)
2150                 return NULL;
2151
2152         Py_INCREF(ao);
2153         it->ao = ao;
2154         it->index = 0;
2155         it->getitem = ao->ob_descr->getitem;
2156         PyObject_GC_Track(it);
2157         return (PyObject *)it;
2158 }
2159
2160 static PyObject *
2161 arrayiter_next(arrayiterobject *it)
2162 {
2163         assert(PyArrayIter_Check(it));
2164         if (it->index < Py_SIZE(it->ao))
2165                 return (*it->getitem)(it->ao, it->index++);
2166         return NULL;
2167 }
2168
2169 static void
2170 arrayiter_dealloc(arrayiterobject *it)
2171 {
2172         PyObject_GC_UnTrack(it);
2173         Py_XDECREF(it->ao);
2174         PyObject_GC_Del(it);
2175 }
2176
2177 static int
2178 arrayiter_traverse(arrayiterobject *it, visitproc visit, void *arg)
2179 {
2180         Py_VISIT(it->ao);
2181         return 0;
2182 }
2183
2184 static PyTypeObject PyArrayIter_Type = {
2185         PyVarObject_HEAD_INIT(NULL, 0)
2186         "arrayiterator",                        /* tp_name */
2187         sizeof(arrayiterobject),                /* tp_basicsize */
2188         0,                                      /* tp_itemsize */
2189         /* methods */
2190         (destructor)arrayiter_dealloc,          /* tp_dealloc */
2191         0,                                      /* tp_print */
2192         0,                                      /* tp_getattr */
2193         0,                                      /* tp_setattr */
2194         0,                                      /* tp_compare */
2195         0,                                      /* tp_repr */
2196         0,                                      /* tp_as_number */
2197         0,                                      /* tp_as_sequence */
2198         0,                                      /* tp_as_mapping */
2199         0,                                      /* tp_hash */
2200         0,                                      /* tp_call */
2201         0,                                      /* tp_str */
2202         PyObject_GenericGetAttr,                /* tp_getattro */
2203         0,                                      /* tp_setattro */
2204         0,                                      /* tp_as_buffer */
2205         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2206         0,                                      /* tp_doc */
2207         (traverseproc)arrayiter_traverse,       /* tp_traverse */
2208         0,                                      /* tp_clear */
2209         0,                                      /* tp_richcompare */
2210         0,                                      /* tp_weaklistoffset */
2211         PyObject_SelfIter,                      /* tp_iter */
2212         (iternextfunc)arrayiter_next,           /* tp_iternext */
2213         0,                                      /* tp_methods */
2214 };
2215
2216
2217 /*********************** Install Module **************************/
2218
2219 /* No functions in array module. */
2220 static PyMethodDef a_methods[] = {
2221     {NULL, NULL, 0, NULL}        /* Sentinel */
2222 };
2223
2224
2225 PyMODINIT_FUNC
2226 initarray(void)
2227 {
2228         PyObject *m;
2229
2230         Arraytype.ob_type = &PyType_Type;
2231         PyArrayIter_Type.ob_type = &PyType_Type;
2232         m = Py_InitModule3("array", a_methods, module_doc);
2233         if (m == NULL)
2234                 return;
2235
2236         Py_INCREF((PyObject *)&Arraytype);
2237         PyModule_AddObject(m, "ArrayType", (PyObject *)&Arraytype);
2238         Py_INCREF((PyObject *)&Arraytype);
2239         PyModule_AddObject(m, "array", (PyObject *)&Arraytype);
2240         /* No need to check the error here, the caller will do that */
2241 }