Objects/listobject.c

   1 /* List object implementation */
   2
   3 #include "Python.h"
   4
   5 #ifdef STDC_HEADERS
   6 #include <stddef.h>
   7 #else
   8 #include <sys/types.h>          /* For size_t */
   9 #endif
  10
  11 static int
  12 roundupsize(int n)
  13 {
  14         unsigned int nbits = 0;
  15         unsigned int n2 = (unsigned int)n >> 5;
  16
  17         /* Round up:
  18          * If n <       256, to a multiple of        8.
  19          * If n <      2048, to a multiple of       64.
  20          * If n <     16384, to a multiple of      512.
  21          * If n <    131072, to a multiple of     4096.
  22          * If n <   1048576, to a multiple of    32768.
  23          * If n <   8388608, to a multiple of   262144.
  24          * If n <  67108864, to a multiple of  2097152.
  25          * If n < 536870912, to a multiple of 16777216.
  26          * ...
  27          * If n < 2**(5+3*i), to a multiple of 2**(3*i).
  28          *
  29          * This over-allocates proportional to the list size, making room
  30          * for additional growth.  The over-allocation is mild, but is
  31          * enough to give linear-time amortized behavior over a long
  32          * sequence of appends() in the presence of a poorly-performing
  33          * system realloc() (which is a reality, e.g., across all flavors
  34          * of Windows, with Win9x behavior being particularly bad -- and
  35          * we've still got address space fragmentation problems on Win9x
  36          * even with this scheme, although it requires much longer lists to
  37          * provoke them than it used to).
  38          */
  39         do {
  40                 n2 >>= 3;
  41                 nbits += 3;
  42         } while (n2);
  43         return ((n >> nbits) + 1) << nbits;
  44  }
  45
  46 #define NRESIZE(var, type, nitems)                              \
  47 do {                                                            \
  48         size_t _new_size = roundupsize(nitems);                 \
  49         if (_new_size <= ((~(size_t)0) / sizeof(type)))         \
  50                 PyMem_RESIZE(var, type, _new_size);             \
  51         else                                                    \
  52                 var = NULL;                                     \
  53 } while (0)
  54
  55 PyObject *
  56 PyList_New(int size)
  57 {
  58         PyListObject *op;
  59         size_t nbytes;
  60         if (size < 0) {
  61                 PyErr_BadInternalCall();
  62                 return NULL;
  63         }
  64         nbytes = size * sizeof(PyObject *);
  65         /* Check for overflow */
  66         if (nbytes / sizeof(PyObject *) != (size_t)size) {
  67                 return PyErr_NoMemory();
  68         }
  69         op = PyObject_GC_New(PyListObject, &PyList_Type);
  70         if (op == NULL) {
  71                 return NULL;
  72         }
  73         if (size <= 0) {
  74                 op->ob_item = NULL;
  75         }
  76         else {
  77                 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
  78                 if (op->ob_item == NULL) {
  79                         return PyErr_NoMemory();
  80                 }
  81                 memset(op->ob_item, 0, sizeof(*op->ob_item) * size);
  82         }
  83         op->ob_size = size;
  84         _PyObject_GC_TRACK(op);
  85         return (PyObject *) op;
  86 }
  87
  88 int
  89 PyList_Size(PyObject *op)
  90 {
  91         if (!PyList_Check(op)) {
  92                 PyErr_BadInternalCall();
  93                 return -1;
  94         }
  95         else
  96                 return ((PyListObject *)op) -> ob_size;
  97 }
  98
  99 static PyObject *indexerr;
 100
 101 PyObject *
 102 PyList_GetItem(PyObject *op, int i)
 103 {
 104         if (!PyList_Check(op)) {
 105                 PyErr_BadInternalCall();
 106                 return NULL;
 107         }
 108         if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
 109                 if (indexerr == NULL)
 110                         indexerr = PyString_FromString(
 111                                 "list index out of range");
 112                 PyErr_SetObject(PyExc_IndexError, indexerr);
 113                 return NULL;
 114         }
 115         return ((PyListObject *)op) -> ob_item[i];
 116 }
 117
 118 int
 119 PyList_SetItem(register PyObject *op, register int i,
 120                register PyObject *newitem)
 121 {
 122         register PyObject *olditem;
 123         register PyObject **p;
 124         if (!PyList_Check(op)) {
 125                 Py_XDECREF(newitem);
 126                 PyErr_BadInternalCall();
 127                 return -1;
 128         }
 129         if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
 130                 Py_XDECREF(newitem);
 131                 PyErr_SetString(PyExc_IndexError,
 132                                 "list assignment index out of range");
 133                 return -1;
 134         }
 135         p = ((PyListObject *)op) -> ob_item + i;
 136         olditem = *p;
 137         *p = newitem;
 138         Py_XDECREF(olditem);
 139         return 0;
 140 }
 141
 142 static int
 143 ins1(PyListObject *self, int where, PyObject *v)
 144 {
 145         int i;
 146         PyObject **items;
 147         if (v == NULL) {
 148                 PyErr_BadInternalCall();
 149                 return -1;
 150         }
 151         if (self->ob_size == INT_MAX) {
 152                 PyErr_SetString(PyExc_OverflowError,
 153                         "cannot add more objects to list");
 154                 return -1;
 155         }
 156         items = self->ob_item;
 157         NRESIZE(items, PyObject *, self->ob_size+1);
 158         if (items == NULL) {
 159                 PyErr_NoMemory();
 160                 return -1;
 161         }
 162         if (where < 0)
 163                 where = 0;
 164         if (where > self->ob_size)
 165                 where = self->ob_size;
 166         for (i = self->ob_size; --i >= where; )
 167                 items[i+1] = items[i];
 168         Py_INCREF(v);
 169         items[where] = v;
 170         self->ob_item = items;
 171         self->ob_size++;
 172         return 0;
 173 }
 174
 175 int
 176 PyList_Insert(PyObject *op, int where, PyObject *newitem)
 177 {
 178         if (!PyList_Check(op)) {
 179                 PyErr_BadInternalCall();
 180                 return -1;
 181         }
 182         return ins1((PyListObject *)op, where, newitem);
 183 }
 184
 185 int
 186 PyList_Append(PyObject *op, PyObject *newitem)
 187 {
 188         if (!PyList_Check(op)) {
 189                 PyErr_BadInternalCall();
 190                 return -1;
 191         }
 192         return ins1((PyListObject *)op,
 193                 (int) ((PyListObject *)op)->ob_size, newitem);
 194 }
 195
 196 /* Methods */
 197
 198 static void
 199 list_dealloc(PyListObject *op)
 200 {
 201         int i;
 202         PyObject_GC_UnTrack(op);
 203         Py_TRASHCAN_SAFE_BEGIN(op)
 204         if (op->ob_item != NULL) {
 205                 /* Do it backwards, for Christian Tismer.
 206                    There's a simple test case where somehow this reduces
 207                    thrashing when a *very* large list is created and
 208                    immediately deleted. */
 209                 i = op->ob_size;
 210                 while (--i >= 0) {
 211                         Py_XDECREF(op->ob_item[i]);
 212                 }
 213                 PyMem_FREE(op->ob_item);
 214         }
 215         op->ob_type->tp_free((PyObject *)op);
 216         Py_TRASHCAN_SAFE_END(op)
 217 }
 218
 219 static int
 220 list_print(PyListObject *op, FILE *fp, int flags)
 221 {
 222         int i;
 223
 224         i = Py_ReprEnter((PyObject*)op);
 225         if (i != 0) {
 226                 if (i < 0)
 227                         return i;
 228                 fprintf(fp, "[...]");
 229                 return 0;
 230         }
 231         fprintf(fp, "[");
 232         for (i = 0; i < op->ob_size; i++) {
 233                 if (i > 0)
 234                         fprintf(fp, ", ");
 235                 if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
 236                         Py_ReprLeave((PyObject *)op);
 237                         return -1;
 238                 }
 239         }
 240         fprintf(fp, "]");
 241         Py_ReprLeave((PyObject *)op);
 242         return 0;
 243 }
 244
 245 static PyObject *
 246 list_repr(PyListObject *v)
 247 {
 248         int i;
 249         PyObject *s, *temp;
 250         PyObject *pieces = NULL, *result = NULL;
 251
 252         i = Py_ReprEnter((PyObject*)v);
 253         if (i != 0) {
 254                 return i > 0 ? PyString_FromString("[...]") : NULL;
 255         }
 256
 257         if (v->ob_size == 0) {
 258                 result = PyString_FromString("[]");
 259                 goto Done;
 260         }
 261
 262         pieces = PyList_New(0);
 263         if (pieces == NULL)
 264                 goto Done;
 265
 266         /* Do repr() on each element.  Note that this may mutate the list,
 267            so must refetch the list size on each iteration. */
 268         for (i = 0; i < v->ob_size; ++i) {
 269                 int status;
 270                 s = PyObject_Repr(v->ob_item[i]);
 271                 if (s == NULL)
 272                         goto Done;
 273                 status = PyList_Append(pieces, s);
 274                 Py_DECREF(s);  /* append created a new ref */
 275                 if (status < 0)
 276                         goto Done;
 277         }
 278
 279         /* Add "[]" decorations to the first and last items. */
 280         assert(PyList_GET_SIZE(pieces) > 0);
 281         s = PyString_FromString("[");
 282         if (s == NULL)
 283                 goto Done;
 284         temp = PyList_GET_ITEM(pieces, 0);
 285         PyString_ConcatAndDel(&s, temp);
 286         PyList_SET_ITEM(pieces, 0, s);
 287         if (s == NULL)
 288                 goto Done;
 289
 290         s = PyString_FromString("]");
 291         if (s == NULL)
 292                 goto Done;
 293         temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
 294         PyString_ConcatAndDel(&temp, s);
 295         PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
 296         if (temp == NULL)
 297                 goto Done;
 298
 299         /* Paste them all together with ", " between. */
 300         s = PyString_FromString(", ");
 301         if (s == NULL)
 302                 goto Done;
 303         result = _PyString_Join(s, pieces);
 304         Py_DECREF(s);
 305
 306 Done:
 307         Py_XDECREF(pieces);
 308         Py_ReprLeave((PyObject *)v);
 309         return result;
 310 }
 311
 312 static int
 313 list_length(PyListObject *a)
 314 {
 315         return a->ob_size;
 316 }
 317
 318
 319
 320 static int
 321 list_contains(PyListObject *a, PyObject *el)
 322 {
 323         int i, cmp;
 324
 325         for (i = 0, cmp = 0 ; cmp == 0 && i < a->ob_size; ++i)
 326                 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
 327                                                    Py_EQ);
 328         return cmp;
 329 }
 330
 331
 332 static PyObject *
 333 list_item(PyListObject *a, int i)
 334 {
 335         if (i < 0 || i >= a->ob_size) {
 336                 if (indexerr == NULL)
 337                         indexerr = PyString_FromString(
 338                                 "list index out of range");
 339                 PyErr_SetObject(PyExc_IndexError, indexerr);
 340                 return NULL;
 341         }
 342         Py_INCREF(a->ob_item[i]);
 343         return a->ob_item[i];
 344 }
 345
 346 static PyObject *
 347 list_slice(PyListObject *a, int ilow, int ihigh)
 348 {
 349         PyListObject *np;
 350         int i;
 351         if (ilow < 0)
 352                 ilow = 0;
 353         else if (ilow > a->ob_size)
 354                 ilow = a->ob_size;
 355         if (ihigh < ilow)
 356                 ihigh = ilow;
 357         else if (ihigh > a->ob_size)
 358                 ihigh = a->ob_size;
 359         np = (PyListObject *) PyList_New(ihigh - ilow);
 360         if (np == NULL)
 361                 return NULL;
 362         for (i = ilow; i < ihigh; i++) {
 363                 PyObject *v = a->ob_item[i];
 364                 Py_INCREF(v);
 365                 np->ob_item[i - ilow] = v;
 366         }
 367         return (PyObject *)np;
 368 }
 369
 370 PyObject *
 371 PyList_GetSlice(PyObject *a, int ilow, int ihigh)
 372 {
 373         if (!PyList_Check(a)) {
 374                 PyErr_BadInternalCall();
 375                 return NULL;
 376         }
 377         return list_slice((PyListObject *)a, ilow, ihigh);
 378 }
 379
 380 static PyObject *
 381 list_concat(PyListObject *a, PyObject *bb)
 382 {
 383         int size;
 384         int i;
 385         PyListObject *np;
 386         if (!PyList_Check(bb)) {
 387                 PyErr_Format(PyExc_TypeError,
 388                           "can only concatenate list (not \"%.200s\") to list",
 389                           bb->ob_type->tp_name);
 390                 return NULL;
 391         }
 392 #define b ((PyListObject *)bb)
 393         size = a->ob_size + b->ob_size;
 394         if (size < 0)
 395                 return PyErr_NoMemory();
 396         np = (PyListObject *) PyList_New(size);
 397         if (np == NULL) {
 398                 return NULL;
 399         }
 400         for (i = 0; i < a->ob_size; i++) {
 401                 PyObject *v = a->ob_item[i];
 402                 Py_INCREF(v);
 403                 np->ob_item[i] = v;
 404         }
 405         for (i = 0; i < b->ob_size; i++) {
 406                 PyObject *v = b->ob_item[i];
 407                 Py_INCREF(v);
 408                 np->ob_item[i + a->ob_size] = v;
 409         }
 410         return (PyObject *)np;
 411 #undef b
 412 }
 413
 414 static PyObject *
 415 list_repeat(PyListObject *a, int n)
 416 {
 417         int i, j;
 418         int size;
 419         PyListObject *np;
 420         PyObject **p;
 421         if (n < 0)
 422                 n = 0;
 423         size = a->ob_size * n;
 424         if (n && size/n != a->ob_size)
 425                 return PyErr_NoMemory();
 426         np = (PyListObject *) PyList_New(size);
 427         if (np == NULL)
 428                 return NULL;
 429         p = np->ob_item;
 430         for (i = 0; i < n; i++) {
 431                 for (j = 0; j < a->ob_size; j++) {
 432                         *p = a->ob_item[j];
 433                         Py_INCREF(*p);
 434                         p++;
 435                 }
 436         }
 437         return (PyObject *) np;
 438 }
 439
 440 static int
 441 list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
 442 {
 443         /* Because [X]DECREF can recursively invoke list operations on
 444            this list, we must postpone all [X]DECREF activity until
 445            after the list is back in its canonical shape.  Therefore
 446            we must allocate an additional array, 'recycle', into which
 447            we temporarily copy the items that are deleted from the
 448            list. :-( */
 449         PyObject **recycle, **p;
 450         PyObject **item;
 451         PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
 452         int n; /* Size of replacement list */
 453         int d; /* Change in size */
 454         int k; /* Loop index */
 455 #define b ((PyListObject *)v)
 456         if (v == NULL)
 457                 n = 0;
 458         else {
 459                 char msg[256];
 460                 PyOS_snprintf(msg, sizeof(msg),
 461                               "must assign sequence"
 462                               " (not \"%.200s\") to slice",
 463                               v->ob_type->tp_name);
 464                 v_as_SF = PySequence_Fast(v, msg);
 465                 if(v_as_SF == NULL)
 466                         return -1;
 467                 n = PySequence_Fast_GET_SIZE(v_as_SF);
 468
 469                 if (a == b) {
 470                         /* Special case "a[i:j] = a" -- copy b first */
 471                         int ret;
 472                         v = list_slice(b, 0, n);
 473                         ret = list_ass_slice(a, ilow, ihigh, v);
 474                         Py_DECREF(v);
 475                         return ret;
 476                 }
 477         }
 478         if (ilow < 0)
 479                 ilow = 0;
 480         else if (ilow > a->ob_size)
 481                 ilow = a->ob_size;
 482         if (ihigh < ilow)
 483                 ihigh = ilow;
 484         else if (ihigh > a->ob_size)
 485                 ihigh = a->ob_size;
 486         item = a->ob_item;
 487         d = n - (ihigh-ilow);
 488         if (ihigh > ilow)
 489                 p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
 490         else
 491                 p = recycle = NULL;
 492         if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
 493                 for (k = ilow; k < ihigh; k++)
 494                         *p++ = item[k];
 495                 if (d < 0) {
 496                         for (/*k = ihigh*/; k < a->ob_size; k++)
 497                                 item[k+d] = item[k];
 498                         a->ob_size += d;
 499                         NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
 500                         a->ob_item = item;
 501                 }
 502         }
 503         else { /* Insert d items; recycle ihigh-ilow items */
 504                 NRESIZE(item, PyObject *, a->ob_size + d);
 505                 if (item == NULL) {
 506                         if (recycle != NULL)
 507                                 PyMem_DEL(recycle);
 508                         PyErr_NoMemory();
 509                         return -1;
 510                 }
 511                 for (k = a->ob_size; --k >= ihigh; )
 512                         item[k+d] = item[k];
 513                 for (/*k = ihigh-1*/; k >= ilow; --k)
 514                         *p++ = item[k];
 515                 a->ob_item = item;
 516                 a->ob_size += d;
 517         }
 518         for (k = 0; k < n; k++, ilow++) {
 519                 PyObject *w = PySequence_Fast_GET_ITEM(v_as_SF, k);
 520                 Py_XINCREF(w);
 521                 item[ilow] = w;
 522         }
 523         if (recycle) {
 524                 while (--p >= recycle)
 525                         Py_XDECREF(*p);
 526                 PyMem_DEL(recycle);
 527         }
 528         if (a->ob_size == 0 && a->ob_item != NULL) {
 529                 PyMem_FREE(a->ob_item);
 530                 a->ob_item = NULL;
 531         }
 532         Py_XDECREF(v_as_SF);
 533         return 0;
 534 #undef b
 535 }
 536
 537 int
 538 PyList_SetSlice(PyObject *a, int ilow, int ihigh, PyObject *v)
 539 {
 540         if (!PyList_Check(a)) {
 541                 PyErr_BadInternalCall();
 542                 return -1;
 543         }
 544         return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
 545 }
 546
 547 static PyObject *
 548 list_inplace_repeat(PyListObject *self, int n)
 549 {
 550         PyObject **items;
 551         int size, i, j;
 552
 553
 554         size = PyList_GET_SIZE(self);
 555         if (size == 0) {
 556                 Py_INCREF(self);
 557                 return (PyObject *)self;
 558         }
 559
 560         items = self->ob_item;
 561
 562         if (n < 1) {
 563                 self->ob_item = NULL;
 564                 self->ob_size = 0;
 565                 for (i = 0; i < size; i++)
 566                         Py_XDECREF(items[i]);
 567                 PyMem_DEL(items);
 568                 Py_INCREF(self);
 569                 return (PyObject *)self;
 570         }
 571
 572         NRESIZE(items, PyObject*, size*n);
 573         if (items == NULL) {
 574                 PyErr_NoMemory();
 575                 goto finally;
 576         }
 577         self->ob_item = items;
 578         for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
 579                 for (j = 0; j < size; j++) {
 580                         PyObject *o = PyList_GET_ITEM(self, j);
 581                         Py_INCREF(o);
 582                         PyList_SET_ITEM(self, self->ob_size++, o);
 583                 }
 584         }
 585         Py_INCREF(self);
 586         return (PyObject *)self;
 587   finally:
 588         return NULL;
 589 }
 590
 591 static int
 592 list_ass_item(PyListObject *a, int i, PyObject *v)
 593 {
 594         PyObject *old_value;
 595         if (i < 0 || i >= a->ob_size) {
 596                 PyErr_SetString(PyExc_IndexError,
 597                                 "list assignment index out of range");
 598                 return -1;
 599         }
 600         if (v == NULL)
 601                 return list_ass_slice(a, i, i+1, v);
 602         Py_INCREF(v);
 603         old_value = a->ob_item[i];
 604         a->ob_item[i] = v;
 605         Py_DECREF(old_value);
 606         return 0;
 607 }
 608
 609 static PyObject *
 610 ins(PyListObject *self, int where, PyObject *v)
 611 {
 612         if (ins1(self, where, v) != 0)
 613                 return NULL;
 614         Py_INCREF(Py_None);
 615         return Py_None;
 616 }
 617
 618 static PyObject *
 619 listinsert(PyListObject *self, PyObject *args)
 620 {
 621         int i;
 622         PyObject *v;
 623         if (!PyArg_ParseTuple(args, "iO:insert", &i, &v))
 624                 return NULL;
 625         return ins(self, i, v);
 626 }
 627
 628 static PyObject *
 629 listappend(PyListObject *self, PyObject *v)
 630 {
 631         return ins(self, (int) self->ob_size, v);
 632 }
 633
 634 static int
 635 listextend_internal(PyListObject *self, PyObject *b)
 636 {
 637         PyObject **items;
 638         int selflen = PyList_GET_SIZE(self);
 639         int blen;
 640         register int i;
 641
 642         if (PyObject_Size(b) == 0) {
 643                 /* short circuit when b is empty */
 644                 Py_DECREF(b);
 645                 return 0;
 646         }
 647
 648         if (self == (PyListObject*)b) {
 649                 /* as in list_ass_slice() we must special case the
 650                  * situation: a.extend(a)
 651                  *
 652                  * XXX: I think this way ought to be faster than using
 653                  * list_slice() the way list_ass_slice() does.
 654                  */
 655                 Py_DECREF(b);
 656                 b = PyList_New(selflen);
 657                 if (!b)
 658                         return -1;
 659                 for (i = 0; i < selflen; i++) {
 660                         PyObject *o = PyList_GET_ITEM(self, i);
 661                         Py_INCREF(o);
 662                         PyList_SET_ITEM(b, i, o);
 663                 }
 664         }
 665
 666         blen = PyObject_Size(b);
 667
 668         /* resize a using idiom */
 669         items = self->ob_item;
 670         NRESIZE(items, PyObject*, selflen + blen);
 671         if (items == NULL) {
 672                 PyErr_NoMemory();
 673                 Py_DECREF(b);
 674                 return -1;
 675         }
 676
 677         self->ob_item = items;
 678
 679         /* populate the end of self with b's items */
 680         for (i = 0; i < blen; i++) {
 681                 PyObject *o = PySequence_Fast_GET_ITEM(b, i);
 682                 Py_INCREF(o);
 683                 PyList_SET_ITEM(self, self->ob_size++, o);
 684         }
 685         Py_DECREF(b);
 686         return 0;
 687 }
 688
 689
 690 static PyObject *
 691 list_inplace_concat(PyListObject *self, PyObject *other)
 692 {
 693         other = PySequence_Fast(other, "argument to += must be iterable");
 694         if (!other)
 695                 return NULL;
 696
 697         if (listextend_internal(self, other) < 0)
 698                 return NULL;
 699
 700         Py_INCREF(self);
 701         return (PyObject *)self;
 702 }
 703
 704 static PyObject *
 705 listextend(PyListObject *self, PyObject *b)
 706 {
 707
 708         b = PySequence_Fast(b, "list.extend() argument must be iterable");
 709         if (!b)
 710                 return NULL;
 711
 712         if (listextend_internal(self, b) < 0)
 713                 return NULL;
 714
 715         Py_INCREF(Py_None);
 716         return Py_None;
 717 }
 718
 719 static PyObject *
 720 listpop(PyListObject *self, PyObject *args)
 721 {
 722         int i = -1;
 723         PyObject *v;
 724         if (!PyArg_ParseTuple(args, "|i:pop", &i))
 725                 return NULL;
 726         if (self->ob_size == 0) {
 727                 /* Special-case most common failure cause */
 728                 PyErr_SetString(PyExc_IndexError, "pop from empty list");
 729                 return NULL;
 730         }
 731         if (i < 0)
 732                 i += self->ob_size;
 733         if (i < 0 || i >= self->ob_size) {
 734                 PyErr_SetString(PyExc_IndexError, "pop index out of range");
 735                 return NULL;
 736         }
 737         v = self->ob_item[i];
 738         Py_INCREF(v);
 739         if (list_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
 740                 Py_DECREF(v);
 741                 return NULL;
 742         }
 743         return v;
 744 }
 745
 746 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
 747 static void
 748 reverse_slice(PyObject **lo, PyObject **hi)
 749 {
 750         assert(lo && hi);
 751
 752         --hi;
 753         while (lo < hi) {
 754                 PyObject *t = *lo;
 755                 *lo = *hi;
 756                 *hi = t;
 757                 ++lo;
 758                 --hi;
 759         }
 760 }
 761
 762 /* Lots of code for an adaptive, stable, natural mergesort.  There are many
 763  * pieces to this algorithm; read listsort.txt for overviews and details.
 764  */
 765
 766 /* Comparison function.  Takes care of calling a user-supplied
 767  * comparison function (any callable Python object), which must not be
 768  * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
 769  * with Py_LT if you know it's NULL).
 770  * Returns -1 on error, 1 if x < y, 0 if x >= y.
 771  */
 772 static int
 773 islt(PyObject *x, PyObject *y, PyObject *compare)
 774 {
 775         PyObject *res;
 776         PyObject *args;
 777         int i;
 778
 779         assert(compare != NULL);
 780         /* Call the user's comparison function and translate the 3-way
 781          * result into true or false (or error).
 782          */
 783         args = PyTuple_New(2);
 784         if (args == NULL)
 785                 return -1;
 786         Py_INCREF(x);
 787         Py_INCREF(y);
 788         PyTuple_SET_ITEM(args, 0, x);
 789         PyTuple_SET_ITEM(args, 1, y);
 790         res = PyObject_Call(compare, args, NULL);
 791         Py_DECREF(args);
 792         if (res == NULL)
 793                 return -1;
 794         if (!PyInt_Check(res)) {
 795                 Py_DECREF(res);
 796                 PyErr_SetString(PyExc_TypeError,
 797                                 "comparison function must return int");
 798                 return -1;
 799         }
 800         i = PyInt_AsLong(res);
 801         Py_DECREF(res);
 802         return i < 0;
 803 }
 804
 805 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
 806  * islt.  This avoids a layer of function call in the usual case, and
 807  * sorting does many comparisons.
 808  * Returns -1 on error, 1 if x < y, 0 if x >= y.
 809  */
 810 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ?                        \
 811                              PyObject_RichCompareBool(X, Y, Py_LT) :    \
 812                              islt(X, Y, COMPARE))
 813
 814 /* Compare X to Y via "<".  Goto "fail" if the comparison raises an
 815    error.  Else "k" is set to true iff X<Y, and an "if (k)" block is
 816    started.  It makes more sense in context <wink>.  X and Y are PyObject*s.
 817 */
 818 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail;  \
 819                    if (k)
 820
 821 /* binarysort is the best method for sorting small arrays: it does
 822    few compares, but can do data movement quadratic in the number of
 823    elements.
 824    [lo, hi) is a contiguous slice of a list, and is sorted via
 825    binary insertion.  This sort is stable.
 826    On entry, must have lo <= start <= hi, and that [lo, start) is already
 827    sorted (pass start == lo if you don't know!).
 828    If islt() complains return -1, else 0.
 829    Even in case of error, the output slice will be some permutation of
 830    the input (nothing is lost or duplicated).
 831 */
 832 static int
 833 binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
 834      /* compare -- comparison function object, or NULL for default */
 835 {
 836         register int k;
 837         register PyObject **l, **p, **r;
 838         register PyObject *pivot;
 839
 840         assert(lo <= start && start <= hi);
 841         /* assert [lo, start) is sorted */
 842         if (lo == start)
 843                 ++start;
 844         for (; start < hi; ++start) {
 845                 /* set l to where *start belongs */
 846                 l = lo;
 847                 r = start;
 848                 pivot = *r;
 849                 /* Invariants:
 850                  * pivot >= all in [lo, l).
 851                  * pivot  < all in [r, start).
 852                  * The second is vacuously true at the start.
 853                  */
 854                 assert(l < r);
 855                 do {
 856                         p = l + ((r - l) >> 1);
 857                         IFLT(pivot, *p)
 858                                 r = p;
 859                         else
 860                                 l = p+1;
 861                 } while (l < r);
 862                 assert(l == r);
 863                 /* The invariants still hold, so pivot >= all in [lo, l) and
 864                    pivot < all in [l, start), so pivot belongs at l.  Note
 865                    that if there are elements equal to pivot, l points to the
 866                    first slot after them -- that's why this sort is stable.
 867                    Slide over to make room.
 868                    Caution: using memmove is much slower under MSVC 5;
 869                    we're not usually moving many slots. */
 870                 for (p = start; p > l; --p)
 871                         *p = *(p-1);
 872                 *l = pivot;
 873         }
 874         return 0;
 875
 876  fail:
 877         return -1;
 878 }
 879
 880 /*
 881 Return the length of the run beginning at lo, in the slice [lo, hi).  lo < hi
 882 is required on entry.  "A run" is the longest ascending sequence, with
 883
 884     lo[0] <= lo[1] <= lo[2] <= ...
 885
 886 or the longest descending sequence, with
 887
 888     lo[0] > lo[1] > lo[2] > ...
 889
 890 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
 891 For its intended use in a stable mergesort, the strictness of the defn of
 892 "descending" is needed so that the caller can safely reverse a descending
 893 sequence without violating stability (strict > ensures there are no equal
 894 elements to get out of order).
 895
 896 Returns -1 in case of error.
 897 */
 898 static int
 899 count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)
 900 {
 901         int k;
 902         int n;
 903
 904         assert(lo < hi);
 905         *descending = 0;
 906         ++lo;
 907         if (lo == hi)
 908                 return 1;
 909
 910         n = 2;
 911         IFLT(*lo, *(lo-1)) {
 912                 *descending = 1;
 913                 for (lo = lo+1; lo < hi; ++lo, ++n) {
 914                         IFLT(*lo, *(lo-1))
 915                                 ;
 916                         else
 917                                 break;
 918                 }
 919         }
 920         else {
 921                 for (lo = lo+1; lo < hi; ++lo, ++n) {
 922                         IFLT(*lo, *(lo-1))
 923                                 break;
 924                 }
 925         }
 926
 927         return n;
 928 fail:
 929         return -1;
 930 }
 931
 932 /*
 933 Locate the proper position of key in a sorted vector; if the vector contains
 934 an element equal to key, return the position immediately to the left of
 935 the leftmost equal element.  [gallop_right() does the same except returns
 936 the position to the right of the rightmost equal element (if any).]
 937
 938 "a" is a sorted vector with n elements, starting at a[0].  n must be > 0.
 939
 940 "hint" is an index at which to begin the search, 0 <= hint < n.  The closer
 941 hint is to the final result, the faster this runs.
 942
 943 The return value is the int k in 0..n such that
 944
 945     a[k-1] < key <= a[k]
 946
 947 pretending that *(a-1) is minus infinity and a[n] is plus infinity.  IOW,
 948 key belongs at index k; or, IOW, the first k elements of a should precede
 949 key, and the last n-k should follow key.
 950
 951 Returns -1 on error.  See listsort.txt for info on the method.
 952 */
 953 static int
 954 gallop_left(PyObject *key, PyObject **a, int n, int hint, PyObject *compare)
 955 {
 956         int ofs;
 957         int lastofs;
 958         int k;
 959
 960         assert(key && a && n > 0 && hint >= 0 && hint < n);
 961
 962         a += hint;
 963         lastofs = 0;
 964         ofs = 1;
 965         IFLT(*a, key) {
 966                 /* a[hint] < key -- gallop right, until
 967                  * a[hint + lastofs] < key <= a[hint + ofs]
 968                  */
 969                 const int maxofs = n - hint;    /* &a[n-1] is highest */
 970                 while (ofs < maxofs) {
 971                         IFLT(a[ofs], key) {
 972                                 lastofs = ofs;
 973                                 ofs = (ofs << 1) + 1;
 974                                 if (ofs <= 0)   /* int overflow */
 975                                         ofs = maxofs;
 976                         }
 977                         else    /* key <= a[hint + ofs] */
 978                                 break;
 979                 }
 980                 if (ofs > maxofs)
 981                         ofs = maxofs;
 982                 /* Translate back to offsets relative to &a[0]. */
 983                 lastofs += hint;
 984                 ofs += hint;
 985         }
 986         else {
 987                 /* key <= a[hint] -- gallop left, until
 988                  * a[hint - ofs] < key <= a[hint - lastofs]
 989                  */
 990                 const int maxofs = hint + 1;    /* &a[0] is lowest */
 991                 while (ofs < maxofs) {
 992                         IFLT(*(a-ofs), key)
 993                                 break;
 994                         /* key <= a[hint - ofs] */
 995                         lastofs = ofs;
 996                         ofs = (ofs << 1) + 1;
 997                         if (ofs <= 0)   /* int overflow */
 998                                 ofs = maxofs;
 999                 }
1000                 if (ofs > maxofs)
1001                         ofs = maxofs;
1002                 /* Translate back to positive offsets relative to &a[0]. */
1003                 k = lastofs;
1004                 lastofs = hint - ofs;
1005                 ofs = hint - k;
1006         }
1007         a -= hint;
1008
1009         assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1010         /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1011          * right of lastofs but no farther right than ofs.  Do a binary
1012          * search, with invariant a[lastofs-1] < key <= a[ofs].
1013          */
1014         ++lastofs;
1015         while (lastofs < ofs) {
1016                 int m = lastofs + ((ofs - lastofs) >> 1);
1017
1018                 IFLT(a[m], key)
1019                         lastofs = m+1;  /* a[m] < key */
1020                 else
1021                         ofs = m;        /* key <= a[m] */
1022         }
1023         assert(lastofs == ofs);         /* so a[ofs-1] < key <= a[ofs] */
1024         return ofs;
1025
1026 fail:
1027         return -1;
1028 }
1029
1030 /*
1031 Exactly like gallop_left(), except that if key already exists in a[0:n],
1032 finds the position immediately to the right of the rightmost equal value.
1033
1034 The return value is the int k in 0..n such that
1035
1036     a[k-1] <= key < a[k]
1037
1038 or -1 if error.
1039
1040 The code duplication is massive, but this is enough different given that
1041 we're sticking to "<" comparisons that it's much harder to follow if
1042 written as one routine with yet another "left or right?" flag.
1043 */
1044 static int
1045 gallop_right(PyObject *key, PyObject **a, int n, int hint, PyObject *compare)
1046 {
1047         int ofs;
1048         int lastofs;
1049         int k;
1050
1051         assert(key && a && n > 0 && hint >= 0 && hint < n);
1052
1053         a += hint;
1054         lastofs = 0;
1055         ofs = 1;
1056         IFLT(key, *a) {
1057                 /* key < a[hint] -- gallop left, until
1058                  * a[hint - ofs] <= key < a[hint - lastofs]
1059                  */
1060                 const int maxofs = hint + 1;    /* &a[0] is lowest */
1061                 while (ofs < maxofs) {
1062                         IFLT(key, *(a-ofs)) {
1063                                 lastofs = ofs;
1064                                 ofs = (ofs << 1) + 1;
1065                                 if (ofs <= 0)   /* int overflow */
1066                                         ofs = maxofs;
1067                         }
1068                         else    /* a[hint - ofs] <= key */
1069                                 break;
1070                 }
1071                 if (ofs > maxofs)
1072                         ofs = maxofs;
1073                 /* Translate back to positive offsets relative to &a[0]. */
1074                 k = lastofs;
1075                 lastofs = hint - ofs;
1076                 ofs = hint - k;
1077         }
1078         else {
1079                 /* a[hint] <= key -- gallop right, until
1080                  * a[hint + lastofs] <= key < a[hint + ofs]
1081                 */
1082                 const int maxofs = n - hint;    /* &a[n-1] is highest */
1083                 while (ofs < maxofs) {
1084                         IFLT(key, a[ofs])
1085                                 break;
1086                         /* a[hint + ofs] <= key */
1087                         lastofs = ofs;
1088                         ofs = (ofs << 1) + 1;
1089                         if (ofs <= 0)   /* int overflow */
1090                                 ofs = maxofs;
1091                 }
1092                 if (ofs > maxofs)
1093                         ofs = maxofs;
1094                 /* Translate back to offsets relative to &a[0]. */
1095                 lastofs += hint;
1096                 ofs += hint;
1097         }
1098         a -= hint;
1099
1100         assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1101         /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1102          * right of lastofs but no farther right than ofs.  Do a binary
1103          * search, with invariant a[lastofs-1] <= key < a[ofs].
1104          */
1105         ++lastofs;
1106         while (lastofs < ofs) {
1107                 int m = lastofs + ((ofs - lastofs) >> 1);
1108
1109                 IFLT(key, a[m])
1110                         ofs = m;        /* key < a[m] */
1111                 else
1112                         lastofs = m+1;  /* a[m] <= key */
1113         }
1114         assert(lastofs == ofs);         /* so a[ofs-1] <= key < a[ofs] */
1115         return ofs;
1116
1117 fail:
1118         return -1;
1119 }
1120
1121 /* The maximum number of entries in a MergeState's pending-runs stack.
1122  * This is enough to sort arrays of size up to about
1123  *     32 * phi ** MAX_MERGE_PENDING
1124  * where phi ~= 1.618.  85 is ridiculouslylarge enough, good for an array
1125  * with 2**64 elements.
1126  */
1127 #define MAX_MERGE_PENDING 85
1128
1129 /* When we get into galloping mode, we stay there until both runs win less
1130  * often than MIN_GALLOP consecutive times.  See listsort.txt for more info.
1131  */
1132 #define MIN_GALLOP 7
1133
1134 /* Avoid malloc for small temp arrays. */
1135 #define MERGESTATE_TEMP_SIZE 256
1136
1137 /* One MergeState exists on the stack per invocation of mergesort.  It's just
1138  * a convenient way to pass state around among the helper functions.
1139  */
1140 struct s_slice {
1141         PyObject **base;
1142         int len;
1143 };
1144
1145 typedef struct s_MergeState {
1146         /* The user-supplied comparison function. or NULL if none given. */
1147         PyObject *compare;
1148
1149         /* This controls when we get *into* galloping mode.  It's initialized
1150          * to MIN_GALLOP.  merge_lo and merge_hi tend to nudge it higher for
1151          * random data, and lower for highly structured data.
1152          */
1153         int min_gallop;
1154
1155         /* 'a' is temp storage to help with merges.  It contains room for
1156          * alloced entries.
1157          */
1158         PyObject **a;   /* may point to temparray below */
1159         int alloced;
1160
1161         /* A stack of n pending runs yet to be merged.  Run #i starts at
1162          * address base[i] and extends for len[i] elements.  It's always
1163          * true (so long as the indices are in bounds) that
1164          *
1165          *     pending[i].base + pending[i].len == pending[i+1].base
1166          *
1167          * so we could cut the storage for this, but it's a minor amount,
1168          * and keeping all the info explicit simplifies the code.
1169          */
1170         int n;
1171         struct s_slice pending[MAX_MERGE_PENDING];
1172
1173         /* 'a' points to this when possible, rather than muck with malloc. */
1174         PyObject *temparray[MERGESTATE_TEMP_SIZE];
1175 } MergeState;
1176
1177 /* Conceptually a MergeState's constructor. */
1178 static void
1179 merge_init(MergeState *ms, PyObject *compare)
1180 {
1181         assert(ms != NULL);
1182         ms->compare = compare;
1183         ms->a = ms->temparray;
1184         ms->alloced = MERGESTATE_TEMP_SIZE;
1185         ms->n = 0;
1186         ms->min_gallop = MIN_GALLOP;
1187 }
1188
1189 /* Free all the temp memory owned by the MergeState.  This must be called
1190  * when you're done with a MergeState, and may be called before then if
1191  * you want to free the temp memory early.
1192  */
1193 static void
1194 merge_freemem(MergeState *ms)
1195 {
1196         assert(ms != NULL);
1197         if (ms->a != ms->temparray)
1198                 PyMem_Free(ms->a);
1199         ms->a = ms->temparray;
1200         ms->alloced = MERGESTATE_TEMP_SIZE;
1201 }
1202
1203 /* Ensure enough temp memory for 'need' array slots is available.
1204  * Returns 0 on success and -1 if the memory can't be gotten.
1205  */
1206 static int
1207 merge_getmem(MergeState *ms, int need)
1208 {
1209         assert(ms != NULL);
1210         if (need <= ms->alloced)
1211                 return 0;
1212         /* Don't realloc!  That can cost cycles to copy the old data, but
1213          * we don't care what's in the block.
1214          */
1215         merge_freemem(ms);
1216         ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));
1217         if (ms->a) {
1218                 ms->alloced = need;
1219                 return 0;
1220         }
1221         PyErr_NoMemory();
1222         merge_freemem(ms);      /* reset to sane state */
1223         return -1;
1224 }
1225 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 :   \
1226                                 merge_getmem(MS, NEED))
1227
1228 /* Merge the na elements starting at pa with the nb elements starting at pb
1229  * in a stable way, in-place.  na and nb must be > 0, and pa + na == pb.
1230  * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1231  * merge, and should have na <= nb.  See listsort.txt for more info.
1232  * Return 0 if successful, -1 if error.
1233  */
1234 static int
1235 merge_lo(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb)
1236 {
1237         int k;
1238         PyObject *compare;
1239         PyObject **dest;
1240         int result = -1;        /* guilty until proved innocent */
1241         int min_gallop = ms->min_gallop;
1242
1243         assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1244         if (MERGE_GETMEM(ms, na) < 0)
1245                 return -1;
1246         memcpy(ms->a, pa, na * sizeof(PyObject*));
1247         dest = pa;
1248         pa = ms->a;
1249
1250         *dest++ = *pb++;
1251         --nb;
1252         if (nb == 0)
1253                 goto Succeed;
1254         if (na == 1)
1255                 goto CopyB;
1256
1257         compare = ms->compare;
1258         for (;;) {
1259                 int acount = 0; /* # of times A won in a row */
1260                 int bcount = 0; /* # of times B won in a row */
1261
1262                 /* Do the straightforward thing until (if ever) one run
1263                  * appears to win consistently.
1264                  */
1265                 for (;;) {
1266                         assert(na > 1 && nb > 0);
1267                         k = ISLT(*pb, *pa, compare);
1268                         if (k) {
1269                                 if (k < 0)
1270                                         goto Fail;
1271                                 *dest++ = *pb++;
1272                                 ++bcount;
1273                                 acount = 0;
1274                                 --nb;
1275                                 if (nb == 0)
1276                                         goto Succeed;
1277                                 if (bcount >= min_gallop)
1278                                         break;
1279                         }
1280                         else {
1281                                 *dest++ = *pa++;
1282                                 ++acount;
1283                                 bcount = 0;
1284                                 --na;
1285                                 if (na == 1)
1286                                         goto CopyB;
1287                                 if (acount >= min_gallop)
1288                                         break;
1289                         }
1290                 }
1291
1292                 /* One run is winning so consistently that galloping may
1293                  * be a huge win.  So try that, and continue galloping until
1294                  * (if ever) neither run appears to be winning consistently
1295                  * anymore.
1296                  */
1297                 ++min_gallop;
1298                 do {
1299                         assert(na > 1 && nb > 0);
1300                         min_gallop -= min_gallop > 1;
1301                         ms->min_gallop = min_gallop;
1302                         k = gallop_right(*pb, pa, na, 0, compare);
1303                         acount = k;
1304                         if (k) {
1305                                 if (k < 0)
1306                                         goto Fail;
1307                                 memcpy(dest, pa, k * sizeof(PyObject *));
1308                                 dest += k;
1309                                 pa += k;
1310                                 na -= k;
1311                                 if (na == 1)
1312                                         goto CopyB;
1313                                 /* na==0 is impossible now if the comparison
1314                                  * function is consistent, but we can't assume
1315                                  * that it is.
1316                                  */
1317                                 if (na == 0)
1318                                         goto Succeed;
1319                         }
1320                         *dest++ = *pb++;
1321                         --nb;
1322                         if (nb == 0)
1323                                 goto Succeed;
1324
1325                         k = gallop_left(*pa, pb, nb, 0, compare);
1326                         bcount = k;
1327                         if (k) {
1328                                 if (k < 0)
1329                                         goto Fail;
1330                                 memmove(dest, pb, k * sizeof(PyObject *));
1331                                 dest += k;
1332                                 pb += k;
1333                                 nb -= k;
1334                                 if (nb == 0)
1335                                         goto Succeed;
1336                         }
1337                         *dest++ = *pa++;
1338                         --na;
1339                         if (na == 1)
1340                                 goto CopyB;
1341                 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1342                 ++min_gallop;   /* penalize it for leaving galloping mode */
1343                 ms->min_gallop = min_gallop;
1344         }
1345 Succeed:
1346         result = 0;
1347 Fail:
1348         if (na)
1349                 memcpy(dest, pa, na * sizeof(PyObject*));
1350         return result;
1351 CopyB:
1352         assert(na == 1 && nb > 0);
1353         /* The last element of pa belongs at the end of the merge. */
1354         memmove(dest, pb, nb * sizeof(PyObject *));
1355         dest[nb] = *pa;
1356         return 0;
1357 }
1358
1359 /* Merge the na elements starting at pa with the nb elements starting at pb
1360  * in a stable way, in-place.  na and nb must be > 0, and pa + na == pb.
1361  * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1362  * merge, and should have na >= nb.  See listsort.txt for more info.
1363  * Return 0 if successful, -1 if error.
1364  */
1365 static int
1366 merge_hi(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb)
1367 {
1368         int k;
1369         PyObject *compare;
1370         PyObject **dest;
1371         int result = -1;        /* guilty until proved innocent */
1372         PyObject **basea;
1373         PyObject **baseb;
1374         int min_gallop = ms->min_gallop;
1375
1376         assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1377         if (MERGE_GETMEM(ms, nb) < 0)
1378                 return -1;
1379         dest = pb + nb - 1;
1380         memcpy(ms->a, pb, nb * sizeof(PyObject*));
1381         basea = pa;
1382         baseb = ms->a;
1383         pb = ms->a + nb - 1;
1384         pa += na - 1;
1385
1386         *dest-- = *pa--;
1387         --na;
1388         if (na == 0)
1389                 goto Succeed;
1390         if (nb == 1)
1391                 goto CopyA;
1392
1393         compare = ms->compare;
1394         for (;;) {
1395                 int acount = 0; /* # of times A won in a row */
1396                 int bcount = 0; /* # of times B won in a row */
1397
1398                 /* Do the straightforward thing until (if ever) one run
1399                  * appears to win consistently.
1400                  */
1401                 for (;;) {
1402                         assert(na > 0 && nb > 1);
1403                         k = ISLT(*pb, *pa, compare);
1404                         if (k) {
1405                                 if (k < 0)
1406                                         goto Fail;
1407                                 *dest-- = *pa--;
1408                                 ++acount;
1409                                 bcount = 0;
1410                                 --na;
1411                                 if (na == 0)
1412                                         goto Succeed;
1413                                 if (acount >= min_gallop)
1414                                         break;
1415                         }
1416                         else {
1417                                 *dest-- = *pb--;
1418                                 ++bcount;
1419                                 acount = 0;
1420                                 --nb;
1421                                 if (nb == 1)
1422                                         goto CopyA;
1423                                 if (bcount >= min_gallop)
1424                                         break;
1425                         }
1426                 }
1427
1428                 /* One run is winning so consistently that galloping may
1429                  * be a huge win.  So try that, and continue galloping until
1430                  * (if ever) neither run appears to be winning consistently
1431                  * anymore.
1432                  */
1433                 ++min_gallop;
1434                 do {
1435                         assert(na > 0 && nb > 1);
1436                         min_gallop -= min_gallop > 1;
1437                         ms->min_gallop = min_gallop;
1438                         k = gallop_right(*pb, basea, na, na-1, compare);
1439                         if (k < 0)
1440                                 goto Fail;
1441                         k = na - k;
1442                         acount = k;
1443                         if (k) {
1444                                 dest -= k;
1445                                 pa -= k;
1446                                 memmove(dest+1, pa+1, k * sizeof(PyObject *));
1447                                 na -= k;
1448                                 if (na == 0)
1449                                         goto Succeed;
1450                         }
1451                         *dest-- = *pb--;
1452                         --nb;
1453                         if (nb == 1)
1454                                 goto CopyA;
1455
1456                         k = gallop_left(*pa, baseb, nb, nb-1, compare);
1457                         if (k < 0)
1458                                 goto Fail;
1459                         k = nb - k;
1460                         bcount = k;
1461                         if (k) {
1462                                 dest -= k;
1463                                 pb -= k;
1464                                 memcpy(dest+1, pb+1, k * sizeof(PyObject *));
1465                                 nb -= k;
1466                                 if (nb == 1)
1467                                         goto CopyA;
1468                                 /* nb==0 is impossible now if the comparison
1469                                  * function is consistent, but we can't assume
1470                                  * that it is.
1471                                  */
1472                                 if (nb == 0)
1473                                         goto Succeed;
1474                         }
1475                         *dest-- = *pa--;
1476                         --na;
1477                         if (na == 0)
1478                                 goto Succeed;
1479                 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1480                 ++min_gallop;   /* penalize it for leaving galloping mode */
1481                 ms->min_gallop = min_gallop;
1482         }
1483 Succeed:
1484         result = 0;
1485 Fail:
1486         if (nb)
1487                 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
1488         return result;
1489 CopyA:
1490         assert(nb == 1 && na > 0);
1491         /* The first element of pb belongs at the front of the merge. */
1492         dest -= na;
1493         pa -= na;
1494         memmove(dest+1, pa+1, na * sizeof(PyObject *));
1495         *dest = *pb;
1496         return 0;
1497 }
1498
1499 /* Merge the two runs at stack indices i and i+1.
1500  * Returns 0 on success, -1 on error.
1501  */
1502 static int
1503 merge_at(MergeState *ms, int i)
1504 {
1505         PyObject **pa, **pb;
1506         int na, nb;
1507         int k;
1508         PyObject *compare;
1509
1510         assert(ms != NULL);
1511         assert(ms->n >= 2);
1512         assert(i >= 0);
1513         assert(i == ms->n - 2 || i == ms->n - 3);
1514
1515         pa = ms->pending[i].base;
1516         na = ms->pending[i].len;
1517         pb = ms->pending[i+1].base;
1518         nb = ms->pending[i+1].len;
1519         assert(na > 0 && nb > 0);
1520         assert(pa + na == pb);
1521
1522         /* Record the length of the combined runs; if i is the 3rd-last
1523          * run now, also slide over the last run (which isn't involved
1524          * in this merge).  The current run i+1 goes away in any case.
1525          */
1526         ms->pending[i].len = na + nb;
1527         if (i == ms->n - 3)
1528                 ms->pending[i+1] = ms->pending[i+2];
1529         --ms->n;
1530
1531         /* Where does b start in a?  Elements in a before that can be
1532          * ignored (already in place).
1533          */
1534         compare = ms->compare;
1535         k = gallop_right(*pb, pa, na, 0, compare);
1536         if (k < 0)
1537                 return -1;
1538         pa += k;
1539         na -= k;
1540         if (na == 0)
1541                 return 0;
1542
1543         /* Where does a end in b?  Elements in b after that can be
1544          * ignored (already in place).
1545          */
1546         nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);
1547         if (nb <= 0)
1548                 return nb;
1549
1550         /* Merge what remains of the runs, using a temp array with
1551          * min(na, nb) elements.
1552          */
1553         if (na <= nb)
1554                 return merge_lo(ms, pa, na, pb, nb);
1555         else
1556                 return merge_hi(ms, pa, na, pb, nb);
1557 }
1558
1559 /* Examine the stack of runs waiting to be merged, merging adjacent runs
1560  * until the stack invariants are re-established:
1561  *
1562  * 1. len[-3] > len[-2] + len[-1]
1563  * 2. len[-2] > len[-1]
1564  *
1565  * See listsort.txt for more info.
1566  *
1567  * Returns 0 on success, -1 on error.
1568  */
1569 static int
1570 merge_collapse(MergeState *ms)
1571 {
1572         struct s_slice *p = ms->pending;
1573
1574         assert(ms);
1575         while (ms->n > 1) {
1576                 int n = ms->n - 2;
1577                 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
1578                         if (p[n-1].len < p[n+1].len)
1579                                 --n;
1580                         if (merge_at(ms, n) < 0)
1581                                 return -1;
1582                 }
1583                 else if (p[n].len <= p[n+1].len) {
1584                          if (merge_at(ms, n) < 0)
1585                                 return -1;
1586                 }
1587                 else
1588                         break;
1589         }
1590         return 0;
1591 }
1592
1593 /* Regardless of invariants, merge all runs on the stack until only one
1594  * remains.  This is used at the end of the mergesort.
1595  *
1596  * Returns 0 on success, -1 on error.
1597  */
1598 static int
1599 merge_force_collapse(MergeState *ms)
1600 {
1601         struct s_slice *p = ms->pending;
1602
1603         assert(ms);
1604         while (ms->n > 1) {
1605                 int n = ms->n - 2;
1606                 if (n > 0 && p[n-1].len < p[n+1].len)
1607                         --n;
1608                 if (merge_at(ms, n) < 0)
1609                         return -1;
1610         }
1611         return 0;
1612 }
1613
1614 /* Compute a good value for the minimum run length; natural runs shorter
1615  * than this are boosted artificially via binary insertion.
1616  *
1617  * If n < 64, return n (it's too small to bother with fancy stuff).
1618  * Else if n is an exact power of 2, return 32.
1619  * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1620  * strictly less than, an exact power of 2.
1621  *
1622  * See listsort.txt for more info.
1623  */
1624 static int
1625 merge_compute_minrun(int n)
1626 {
1627         int r = 0;      /* becomes 1 if any 1 bits are shifted off */
1628
1629         assert(n >= 0);
1630         while (n >= 64) {
1631                 r |= n & 1;
1632                 n >>= 1;
1633         }
1634         return n + r;
1635 }
1636
1637 /* An adaptive, stable, natural mergesort.  See listsort.txt.
1638  * Returns Py_None on success, NULL on error.  Even in case of error, the
1639  * list will be some permutation of its input state (nothing is lost or
1640  * duplicated).
1641  */
1642 static PyObject *
1643 listsort(PyListObject *self, PyObject *args)
1644 {
1645         MergeState ms;
1646         PyObject **lo, **hi;
1647         int nremaining;
1648         int minrun;
1649         int saved_ob_size;
1650         PyObject **saved_ob_item;
1651         PyObject **empty_ob_item;
1652         PyObject *compare = NULL;
1653         PyObject *result = NULL;        /* guilty until proved innocent */
1654
1655         assert(self != NULL);
1656         if (args != NULL) {
1657                 if (!PyArg_UnpackTuple(args, "sort", 0, 1, &compare))
1658                         return NULL;
1659         }
1660         merge_init(&ms, compare);
1661
1662         /* The list is temporarily made empty, so that mutations performed
1663          * by comparison functions can't affect the slice of memory we're
1664          * sorting (allowing mutations during sorting is a core-dump
1665          * factory, since ob_item may change).
1666          */
1667         saved_ob_size = self->ob_size;
1668         saved_ob_item = self->ob_item;
1669         self->ob_size = 0;
1670         self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0);
1671
1672         nremaining = saved_ob_size;
1673         if (nremaining < 2)
1674                 goto succeed;
1675
1676         /* March over the array once, left to right, finding natural runs,
1677          * and extending short natural runs to minrun elements.
1678          */
1679         lo = saved_ob_item;
1680         hi = lo + nremaining;
1681         minrun = merge_compute_minrun(nremaining);
1682         do {
1683                 int descending;
1684                 int n;
1685
1686                 /* Identify next run. */
1687                 n = count_run(lo, hi, compare, &descending);
1688                 if (n < 0)
1689                         goto fail;
1690                 if (descending)
1691                         reverse_slice(lo, lo + n);
1692                 /* If short, extend to min(minrun, nremaining). */
1693                 if (n < minrun) {
1694                         const int force = nremaining <= minrun ?
1695                                           nremaining : minrun;
1696                         if (binarysort(lo, lo + force, lo + n, compare) < 0)
1697                                 goto fail;
1698                         n = force;
1699                 }
1700                 /* Push run onto pending-runs stack, and maybe merge. */
1701                 assert(ms.n < MAX_MERGE_PENDING);
1702                 ms.pending[ms.n].base = lo;
1703                 ms.pending[ms.n].len = n;
1704                 ++ms.n;
1705                 if (merge_collapse(&ms) < 0)
1706                         goto fail;
1707                 /* Advance to find next run. */
1708                 lo += n;
1709                 nremaining -= n;
1710         } while (nremaining);
1711         assert(lo == hi);
1712
1713         if (merge_force_collapse(&ms) < 0)
1714                 goto fail;
1715         assert(ms.n == 1);
1716         assert(ms.pending[0].base == saved_ob_item);
1717         assert(ms.pending[0].len == saved_ob_size);
1718
1719 succeed:
1720         result = Py_None;
1721 fail:
1722         if (self->ob_item != empty_ob_item || self->ob_size) {
1723                 /* The user mucked with the list during the sort. */
1724                 (void)list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL);
1725                 if (result != NULL) {
1726                         PyErr_SetString(PyExc_ValueError,
1727                                         "list modified during sort");
1728                         result = NULL;
1729                 }
1730         }
1731         if (self->ob_item == empty_ob_item)
1732                 PyMem_FREE(empty_ob_item);
1733         self->ob_size = saved_ob_size;
1734         self->ob_item = saved_ob_item;
1735         merge_freemem(&ms);
1736         Py_XINCREF(result);
1737         return result;
1738 }
1739 #undef IFLT
1740 #undef ISLT
1741
1742 int
1743 PyList_Sort(PyObject *v)
1744 {
1745         if (v == NULL || !PyList_Check(v)) {
1746                 PyErr_BadInternalCall();
1747                 return -1;
1748         }
1749         v = listsort((PyListObject *)v, (PyObject *)NULL);
1750         if (v == NULL)
1751                 return -1;
1752         Py_DECREF(v);
1753         return 0;
1754 }
1755
1756 static PyObject *
1757 listreverse(PyListObject *self)
1758 {
1759         if (self->ob_size > 1)
1760                 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
1761         Py_INCREF(Py_None);
1762         return Py_None;
1763 }
1764
1765 int
1766 PyList_Reverse(PyObject *v)
1767 {
1768         PyListObject *self = (PyListObject *)v;
1769
1770         if (v == NULL || !PyList_Check(v)) {
1771                 PyErr_BadInternalCall();
1772                 return -1;
1773         }
1774         if (self->ob_size > 1)
1775                 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
1776         return 0;
1777 }
1778
1779 PyObject *
1780 PyList_AsTuple(PyObject *v)
1781 {
1782         PyObject *w;
1783         PyObject **p;
1784         int n;
1785         if (v == NULL || !PyList_Check(v)) {
1786                 PyErr_BadInternalCall();
1787                 return NULL;
1788         }
1789         n = ((PyListObject *)v)->ob_size;
1790         w = PyTuple_New(n);
1791         if (w == NULL)
1792                 return NULL;
1793         p = ((PyTupleObject *)w)->ob_item;
1794         memcpy((void *)p,
1795                (void *)((PyListObject *)v)->ob_item,
1796                n*sizeof(PyObject *));
1797         while (--n >= 0) {
1798                 Py_INCREF(*p);
1799                 p++;
1800         }
1801         return w;
1802 }
1803
1804 static PyObject *
1805 listindex(PyListObject *self, PyObject *v)
1806 {
1807         int i;
1808
1809         for (i = 0; i < self->ob_size; i++) {
1810                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1811                 if (cmp > 0)
1812                         return PyInt_FromLong((long)i);
1813                 else if (cmp < 0)
1814                         return NULL;
1815         }
1816         PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
1817         return NULL;
1818 }
1819
1820 static PyObject *
1821 listcount(PyListObject *self, PyObject *v)
1822 {
1823         int count = 0;
1824         int i;
1825
1826         for (i = 0; i < self->ob_size; i++) {
1827                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1828                 if (cmp > 0)
1829                         count++;
1830                 else if (cmp < 0)
1831                         return NULL;
1832         }
1833         return PyInt_FromLong((long)count);
1834 }
1835
1836 static PyObject *
1837 listremove(PyListObject *self, PyObject *v)
1838 {
1839         int i;
1840
1841         for (i = 0; i < self->ob_size; i++) {
1842                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1843                 if (cmp > 0) {
1844                         if (list_ass_slice(self, i, i+1,
1845                                            (PyObject *)NULL) != 0)
1846                                 return NULL;
1847                         Py_INCREF(Py_None);
1848                         return Py_None;
1849                 }
1850                 else if (cmp < 0)
1851                         return NULL;
1852         }
1853         PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
1854         return NULL;
1855 }
1856
1857 static int
1858 list_traverse(PyListObject *o, visitproc visit, void *arg)
1859 {
1860         int i, err;
1861         PyObject *x;
1862
1863         for (i = o->ob_size; --i >= 0; ) {
1864                 x = o->ob_item[i];
1865                 if (x != NULL) {
1866                         err = visit(x, arg);
1867                         if (err)
1868                                 return err;
1869                 }
1870         }
1871         return 0;
1872 }
1873
1874 static int
1875 list_clear(PyListObject *lp)
1876 {
1877         (void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
1878         return 0;
1879 }
1880
1881 static PyObject *
1882 list_richcompare(PyObject *v, PyObject *w, int op)
1883 {
1884         PyListObject *vl, *wl;
1885         int i;
1886
1887         if (!PyList_Check(v) || !PyList_Check(w)) {
1888                 Py_INCREF(Py_NotImplemented);
1889                 return Py_NotImplemented;
1890         }
1891
1892         vl = (PyListObject *)v;
1893         wl = (PyListObject *)w;
1894
1895         if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
1896                 /* Shortcut: if the lengths differ, the lists differ */
1897                 PyObject *res;
1898                 if (op == Py_EQ)
1899                         res = Py_False;
1900                 else
1901                         res = Py_True;
1902                 Py_INCREF(res);
1903                 return res;
1904         }
1905
1906         /* Search for the first index where items are different */
1907         for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
1908                 int k = PyObject_RichCompareBool(vl->ob_item[i],
1909                                                  wl->ob_item[i], Py_EQ);
1910                 if (k < 0)
1911                         return NULL;
1912                 if (!k)
1913                         break;
1914         }
1915
1916         if (i >= vl->ob_size || i >= wl->ob_size) {
1917                 /* No more items to compare -- compare sizes */
1918                 int vs = vl->ob_size;
1919                 int ws = wl->ob_size;
1920                 int cmp;
1921                 PyObject *res;
1922                 switch (op) {
1923                 case Py_LT: cmp = vs <  ws; break;
1924                 case Py_LE: cmp = vs <= ws; break;
1925                 case Py_EQ: cmp = vs == ws; break;
1926                 case Py_NE: cmp = vs != ws; break;
1927                 case Py_GT: cmp = vs >  ws; break;
1928                 case Py_GE: cmp = vs >= ws; break;
1929                 default: return NULL; /* cannot happen */
1930                 }
1931                 if (cmp)
1932                         res = Py_True;
1933                 else
1934                         res = Py_False;
1935                 Py_INCREF(res);
1936                 return res;
1937         }
1938
1939         /* We have an item that differs -- shortcuts for EQ/NE */
1940         if (op == Py_EQ) {
1941                 Py_INCREF(Py_False);
1942                 return Py_False;
1943         }
1944         if (op == Py_NE) {
1945                 Py_INCREF(Py_True);
1946                 return Py_True;
1947         }
1948
1949         /* Compare the final item again using the proper operator */
1950         return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
1951 }
1952
1953 /* Adapted from newer code by Tim */
1954 static int
1955 list_fill(PyListObject *result, PyObject *v)
1956 {
1957         PyObject *it;      /* iter(v) */
1958         int n;             /* guess for result list size */
1959         int i;
1960
1961         n = result->ob_size;
1962
1963         /* Special-case list(a_list), for speed. */
1964         if (PyList_Check(v)) {
1965                 if (v == (PyObject *)result)
1966                         return 0; /* source is destination, we're done */
1967                 return list_ass_slice(result, 0, n, v);
1968         }
1969
1970         /* Empty previous contents */
1971         if (n != 0) {
1972                 if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
1973                         return -1;
1974         }
1975
1976         /* Get iterator.  There may be some low-level efficiency to be gained
1977          * by caching the tp_iternext slot instead of using PyIter_Next()
1978          * later, but premature optimization is the root etc.
1979          */
1980         it = PyObject_GetIter(v);
1981         if (it == NULL)
1982                 return -1;
1983
1984         /* Guess a result list size. */
1985         n = -1;  /* unknown */
1986         if (PySequence_Check(v) &&
1987             v->ob_type->tp_as_sequence->sq_length) {
1988                 n = PySequence_Size(v);
1989                 if (n < 0)
1990                         PyErr_Clear();
1991         }
1992         if (n < 0)
1993                 n = 8;  /* arbitrary */
1994         NRESIZE(result->ob_item, PyObject*, n);
1995         if (result->ob_item == NULL) {
1996                 PyErr_NoMemory();
1997                 goto error;
1998         }
1999         memset(result->ob_item, 0, sizeof(*result->ob_item) * n);
2000         result->ob_size = n;
2001
2002         /* Run iterator to exhaustion. */
2003         for (i = 0; ; i++) {
2004                 PyObject *item = PyIter_Next(it);
2005                 if (item == NULL) {
2006                         if (PyErr_Occurred())
2007                                 goto error;
2008                         break;
2009                 }
2010                 if (i < n)
2011                         PyList_SET_ITEM(result, i, item); /* steals ref */
2012                 else {
2013                         int status = ins1(result, result->ob_size, item);
2014                         Py_DECREF(item);  /* append creates a new ref */
2015                         if (status < 0)
2016                                 goto error;
2017                 }
2018         }
2019
2020         /* Cut back result list if initial guess was too large. */
2021         if (i < n && result != NULL) {
2022                 if (list_ass_slice(result, i, n, (PyObject *)NULL) != 0)
2023                         goto error;
2024         }
2025         Py_DECREF(it);
2026         return 0;
2027
2028   error:
2029         Py_DECREF(it);
2030         return -1;
2031 }
2032
2033 static int
2034 list_init(PyListObject *self, PyObject *args, PyObject *kw)
2035 {
2036         PyObject *arg = NULL;
2037         static char *kwlist[] = {"sequence", 0};
2038
2039         if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
2040                 return -1;
2041         if (arg != NULL)
2042                 return list_fill(self, arg);
2043         if (self->ob_size > 0)
2044                 return list_ass_slice(self, 0, self->ob_size, (PyObject*)NULL);
2045         return 0;
2046 }
2047
2048 static long
2049 list_nohash(PyObject *self)
2050 {
2051         PyErr_SetString(PyExc_TypeError, "list objects are unhashable");
2052         return -1;
2053 }
2054
2055 PyDoc_STRVAR(append_doc,
2056 "L.append(object) -- append object to end");
2057 PyDoc_STRVAR(extend_doc,
2058 "L.extend(iterable) -- extend list by appending elements from the iterable");
2059 PyDoc_STRVAR(insert_doc,
2060 "L.insert(index, object) -- insert object before index");
2061 PyDoc_STRVAR(pop_doc,
2062 "L.pop([index]) -> item -- remove and return item at index (default last)");
2063 PyDoc_STRVAR(remove_doc,
2064 "L.remove(value) -- remove first occurrence of value");
2065 PyDoc_STRVAR(index_doc,
2066 "L.index(value) -> integer -- return index of first occurrence of value");
2067 PyDoc_STRVAR(count_doc,
2068 "L.count(value) -> integer -- return number of occurrences of value");
2069 PyDoc_STRVAR(reverse_doc,
2070 "L.reverse() -- reverse *IN PLACE*");
2071 PyDoc_STRVAR(sort_doc,
2072 "L.sort([cmpfunc]) -- stable sort *IN PLACE*; cmpfunc(x, y) -> -1, 0, 1");
2073
2074 static PyMethodDef list_methods[] = {
2075         {"append",      (PyCFunction)listappend,  METH_O, append_doc},
2076         {"insert",      (PyCFunction)listinsert,  METH_VARARGS, insert_doc},
2077         {"extend",      (PyCFunction)listextend,  METH_O, extend_doc},
2078         {"pop",         (PyCFunction)listpop,     METH_VARARGS, pop_doc},
2079         {"remove",      (PyCFunction)listremove,  METH_O, remove_doc},
2080         {"index",       (PyCFunction)listindex,   METH_O, index_doc},
2081         {"count",       (PyCFunction)listcount,   METH_O, count_doc},
2082         {"reverse",     (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
2083         {"sort",        (PyCFunction)listsort,    METH_VARARGS, sort_doc},
2084         {NULL,          NULL}           /* sentinel */
2085 };
2086
2087 static PySequenceMethods list_as_sequence = {
2088         (inquiry)list_length,                   /* sq_length */
2089         (binaryfunc)list_concat,                /* sq_concat */
2090         (intargfunc)list_repeat,                /* sq_repeat */
2091         (intargfunc)list_item,                  /* sq_item */
2092         (intintargfunc)list_slice,              /* sq_slice */
2093         (intobjargproc)list_ass_item,           /* sq_ass_item */
2094         (intintobjargproc)list_ass_slice,       /* sq_ass_slice */
2095         (objobjproc)list_contains,              /* sq_contains */
2096         (binaryfunc)list_inplace_concat,        /* sq_inplace_concat */
2097         (intargfunc)list_inplace_repeat,        /* sq_inplace_repeat */
2098 };
2099
2100 PyDoc_STRVAR(list_doc,
2101 "list() -> new list\n"
2102 "list(sequence) -> new list initialized from sequence's items");
2103
2104 static PyObject *list_iter(PyObject *seq);
2105
2106 static PyObject *
2107 list_subscript(PyListObject* self, PyObject* item)
2108 {
2109         if (PyInt_Check(item)) {
2110                 long i = PyInt_AS_LONG(item);
2111                 if (i < 0)
2112                         i += PyList_GET_SIZE(self);
2113                 return list_item(self, i);
2114         }
2115         else if (PyLong_Check(item)) {
2116                 long i = PyLong_AsLong(item);
2117                 if (i == -1 && PyErr_Occurred())
2118                         return NULL;
2119                 if (i < 0)
2120                         i += PyList_GET_SIZE(self);
2121                 return list_item(self, i);
2122         }
2123         else if (PySlice_Check(item)) {
2124                 int start, stop, step, slicelength, cur, i;
2125                 PyObject* result;
2126                 PyObject* it;
2127
2128                 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2129                                  &start, &stop, &step, &slicelength) < 0) {
2130                         return NULL;
2131                 }
2132
2133                 if (slicelength <= 0) {
2134                         return PyList_New(0);
2135                 }
2136                 else {
2137                         result = PyList_New(slicelength);
2138                         if (!result) return NULL;
2139
2140                         for (cur = start, i = 0; i < slicelength;
2141                              cur += step, i++) {
2142                                 it = PyList_GET_ITEM(self, cur);
2143                                 Py_INCREF(it);
2144                                 PyList_SET_ITEM(result, i, it);
2145                         }
2146
2147                         return result;
2148                 }
2149         }
2150         else {
2151                 PyErr_SetString(PyExc_TypeError,
2152                                 "list indices must be integers");
2153                 return NULL;
2154         }
2155 }
2156
2157 static int
2158 list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2159 {
2160         if (PyInt_Check(item)) {
2161                 long i = PyInt_AS_LONG(item);
2162                 if (i < 0)
2163                         i += PyList_GET_SIZE(self);
2164                 return list_ass_item(self, i, value);
2165         }
2166         else if (PyLong_Check(item)) {
2167                 long i = PyLong_AsLong(item);
2168                 if (i == -1 && PyErr_Occurred())
2169                         return -1;
2170                 if (i < 0)
2171                         i += PyList_GET_SIZE(self);
2172                 return list_ass_item(self, i, value);
2173         }
2174         else if (PySlice_Check(item)) {
2175                 int start, stop, step, slicelength;
2176
2177                 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2178                                  &start, &stop, &step, &slicelength) < 0) {
2179                         return -1;
2180                 }
2181
2182                 /* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
2183                 if (step == 1 && ((PySliceObject*)item)->step == Py_None)
2184                         return list_ass_slice(self, start, stop, value);
2185
2186                 if (value == NULL) {
2187                         /* delete slice */
2188                         PyObject **garbage, **it;
2189                         int cur, i, j;
2190
2191                         if (slicelength <= 0)
2192                                 return 0;
2193
2194                         if (step < 0) {
2195                                 stop = start + 1;
2196                                 start = stop + step*(slicelength - 1) - 1;
2197                                 step = -step;
2198                         }
2199
2200                         garbage = (PyObject**)
2201                                 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2202
2203                         /* drawing pictures might help
2204                            understand these for loops */
2205                         for (cur = start, i = 0;
2206                              cur < stop;
2207                              cur += step, i++) {
2208                                 int lim = step;
2209
2210                                 garbage[i] = PyList_GET_ITEM(self, cur);
2211
2212                                 if (cur + step >= self->ob_size) {
2213                                         lim = self->ob_size - cur - 1;
2214                                 }
2215
2216                                 for (j = 0; j < lim; j++) {
2217                                         PyList_SET_ITEM(self, cur + j - i,
2218                                                 PyList_GET_ITEM(self,
2219                                                                 cur + j + 1));
2220                                 }
2221                         }
2222                         for (cur = start + slicelength*step + 1;
2223                              cur < self->ob_size; cur++) {
2224                                 PyList_SET_ITEM(self, cur - slicelength,
2225                                                 PyList_GET_ITEM(self, cur));
2226                         }
2227                         self->ob_size -= slicelength;
2228                         it = self->ob_item;
2229                         NRESIZE(it, PyObject*, self->ob_size);
2230                         self->ob_item = it;
2231
2232                         for (i = 0; i < slicelength; i++) {
2233                                 Py_DECREF(garbage[i]);
2234                         }
2235                         PyMem_FREE(garbage);
2236
2237                         return 0;
2238                 }
2239                 else {
2240                         /* assign slice */
2241                         PyObject **garbage, *ins, *seq;
2242                         int cur, i;
2243
2244                         /* protect against a[::-1] = a */
2245                         if (self == (PyListObject*)value) {
2246                                 seq = list_slice((PyListObject*)value, 0,
2247                                                    PyList_GET_SIZE(value));
2248                         }
2249                         else {
2250                                 char msg[256];
2251                                 PyOS_snprintf(msg, sizeof(msg),
2252                       "must assign sequence (not \"%.200s\") to extended slice",
2253                                               value->ob_type->tp_name);
2254                                 seq = PySequence_Fast(value, msg);
2255                                 if (!seq)
2256                                         return -1;
2257                         }
2258
2259                         if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2260                                 PyErr_Format(PyExc_ValueError,
2261             "attempt to assign sequence of size %d to extended slice of size %d",
2262                                              PySequence_Fast_GET_SIZE(seq),
2263                                              slicelength);
2264                                 Py_DECREF(seq);
2265                                 return -1;
2266                         }
2267
2268                         if (!slicelength) {
2269                                 Py_DECREF(seq);
2270                                 return 0;
2271                         }
2272
2273                         garbage = (PyObject**)
2274                                 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2275
2276                         for (cur = start, i = 0; i < slicelength;
2277                              cur += step, i++) {
2278                                 garbage[i] = PyList_GET_ITEM(self, cur);
2279
2280                                 ins = PySequence_Fast_GET_ITEM(seq, i);
2281                                 Py_INCREF(ins);
2282                                 PyList_SET_ITEM(self, cur, ins);
2283                         }
2284
2285                         for (i = 0; i < slicelength; i++) {
2286                                 Py_DECREF(garbage[i]);
2287                         }
2288
2289                         PyMem_FREE(garbage);
2290                         Py_DECREF(seq);
2291
2292                         return 0;
2293                 }
2294         }
2295         else {
2296                 PyErr_SetString(PyExc_TypeError,
2297                                 "list indices must be integers");
2298                 return -1;
2299         }
2300 }
2301
2302 static PyMappingMethods list_as_mapping = {
2303         (inquiry)list_length,
2304         (binaryfunc)list_subscript,
2305         (objobjargproc)list_ass_subscript
2306 };
2307
2308 PyTypeObject PyList_Type = {
2309         PyObject_HEAD_INIT(&PyType_Type)
2310         0,
2311         "list",
2312         sizeof(PyListObject),
2313         0,
2314         (destructor)list_dealloc,               /* tp_dealloc */
2315         (printfunc)list_print,                  /* tp_print */
2316         0,                                      /* tp_getattr */
2317         0,                                      /* tp_setattr */
2318         0,                                      /* tp_compare */
2319         (reprfunc)list_repr,                    /* tp_repr */
2320         0,                                      /* tp_as_number */
2321         &list_as_sequence,                      /* tp_as_sequence */
2322         &list_as_mapping,                       /* tp_as_mapping */
2323         list_nohash,                            /* tp_hash */
2324         0,                                      /* tp_call */
2325         0,                                      /* tp_str */
2326         PyObject_GenericGetAttr,                /* tp_getattro */
2327         0,                                      /* tp_setattro */
2328         0,                                      /* tp_as_buffer */
2329         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2330                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
2331         list_doc,                               /* tp_doc */
2332         (traverseproc)list_traverse,            /* tp_traverse */
2333         (inquiry)list_clear,                    /* tp_clear */
2334         list_richcompare,                       /* tp_richcompare */
2335         0,                                      /* tp_weaklistoffset */
2336         list_iter,                              /* tp_iter */
2337         0,                                      /* tp_iternext */
2338         list_methods,                           /* tp_methods */
2339         0,                                      /* tp_members */
2340         0,                                      /* tp_getset */
2341         0,                                      /* tp_base */
2342         0,                                      /* tp_dict */
2343         0,                                      /* tp_descr_get */
2344         0,                                      /* tp_descr_set */
2345         0,                                      /* tp_dictoffset */
2346         (initproc)list_init,                    /* tp_init */
2347         PyType_GenericAlloc,                    /* tp_alloc */
2348         PyType_GenericNew,                      /* tp_new */
2349         PyObject_GC_Del,                        /* tp_free */
2350 };
2351
2352
2353 /*********************** List Iterator **************************/
2354
2355 typedef struct {
2356         PyObject_HEAD
2357         long it_index;
2358         PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
2359 } listiterobject;
2360
2361 PyTypeObject PyListIter_Type;
2362
2363 static PyObject *
2364 list_iter(PyObject *seq)
2365 {
2366         listiterobject *it;
2367
2368         if (!PyList_Check(seq)) {
2369                 PyErr_BadInternalCall();
2370                 return NULL;
2371         }
2372         it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2373         if (it == NULL)
2374                 return NULL;
2375         it->it_index = 0;
2376         Py_INCREF(seq);
2377         it->it_seq = (PyListObject *)seq;
2378         _PyObject_GC_TRACK(it);
2379         return (PyObject *)it;
2380 }
2381
2382 static void
2383 listiter_dealloc(listiterobject *it)
2384 {
2385         _PyObject_GC_UNTRACK(it);
2386         Py_XDECREF(it->it_seq);
2387         PyObject_GC_Del(it);
2388 }
2389
2390 static int
2391 listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2392 {
2393         if (it->it_seq == NULL)
2394                 return 0;
2395         return visit((PyObject *)it->it_seq, arg);
2396 }
2397
2398
2399 static PyObject *
2400 listiter_getiter(PyObject *it)
2401 {
2402         Py_INCREF(it);
2403         return it;
2404 }
2405
2406 static PyObject *
2407 listiter_next(listiterobject *it)
2408 {
2409         PyListObject *seq;
2410         PyObject *item;
2411
2412         assert(it != NULL);
2413         seq = it->it_seq;
2414         if (seq == NULL)
2415                 return NULL;
2416         assert(PyList_Check(seq));
2417
2418         if (it->it_index < PyList_GET_SIZE(seq)) {
2419                 item = PyList_GET_ITEM(seq, it->it_index);
2420                 ++it->it_index;
2421                 Py_INCREF(item);
2422                 return item;
2423         }
2424
2425         Py_DECREF(seq);
2426         it->it_seq = NULL;
2427         return NULL;
2428 }
2429
2430 PyTypeObject PyListIter_Type = {
2431         PyObject_HEAD_INIT(&PyType_Type)
2432         0,                                      /* ob_size */
2433         "listiterator",                         /* tp_name */
2434         sizeof(listiterobject),                 /* tp_basicsize */
2435         0,                                      /* tp_itemsize */
2436         /* methods */
2437         (destructor)listiter_dealloc,           /* tp_dealloc */
2438         0,                                      /* tp_print */
2439         0,                                      /* tp_getattr */
2440         0,                                      /* tp_setattr */
2441         0,                                      /* tp_compare */
2442         0,                                      /* tp_repr */
2443         0,                                      /* tp_as_number */
2444         0,                                      /* tp_as_sequence */
2445         0,                                      /* tp_as_mapping */
2446         0,                                      /* tp_hash */
2447         0,                                      /* tp_call */
2448         0,                                      /* tp_str */
2449         PyObject_GenericGetAttr,                /* tp_getattro */
2450         0,                                      /* tp_setattro */
2451         0,                                      /* tp_as_buffer */
2452         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2453         0,                                      /* tp_doc */
2454         (traverseproc)listiter_traverse,        /* tp_traverse */
2455         0,                                      /* tp_clear */
2456         0,                                      /* tp_richcompare */
2457         0,                                      /* tp_weaklistoffset */
2458         (getiterfunc)listiter_getiter,          /* tp_iter */
2459         (iternextfunc)listiter_next,            /* tp_iternext */
2460         0,                                      /* tp_methods */
2461         0,                                      /* tp_members */
2462         0,                                      /* tp_getset */
2463         0,                                      /* tp_base */
2464         0,                                      /* tp_dict */
2465         0,                                      /* tp_descr_get */
2466         0,                                      /* tp_descr_set */
2467 };