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         if (compare == Py_None)
1661                 compare = NULL;
1662
1663         merge_init(&ms, compare);
1664
1665         /* The list is temporarily made empty, so that mutations performed
1666          * by comparison functions can't affect the slice of memory we're
1667          * sorting (allowing mutations during sorting is a core-dump
1668          * factory, since ob_item may change).
1669          */
1670         saved_ob_size = self->ob_size;
1671         saved_ob_item = self->ob_item;
1672         self->ob_size = 0;
1673         self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0);
1674
1675         nremaining = saved_ob_size;
1676         if (nremaining < 2)
1677                 goto succeed;
1678
1679         /* March over the array once, left to right, finding natural runs,
1680          * and extending short natural runs to minrun elements.
1681          */
1682         lo = saved_ob_item;
1683         hi = lo + nremaining;
1684         minrun = merge_compute_minrun(nremaining);
1685         do {
1686                 int descending;
1687                 int n;
1688
1689                 /* Identify next run. */
1690                 n = count_run(lo, hi, compare, &descending);
1691                 if (n < 0)
1692                         goto fail;
1693                 if (descending)
1694                         reverse_slice(lo, lo + n);
1695                 /* If short, extend to min(minrun, nremaining). */
1696                 if (n < minrun) {
1697                         const int force = nremaining <= minrun ?
1698                                           nremaining : minrun;
1699                         if (binarysort(lo, lo + force, lo + n, compare) < 0)
1700                                 goto fail;
1701                         n = force;
1702                 }
1703                 /* Push run onto pending-runs stack, and maybe merge. */
1704                 assert(ms.n < MAX_MERGE_PENDING);
1705                 ms.pending[ms.n].base = lo;
1706                 ms.pending[ms.n].len = n;
1707                 ++ms.n;
1708                 if (merge_collapse(&ms) < 0)
1709                         goto fail;
1710                 /* Advance to find next run. */
1711                 lo += n;
1712                 nremaining -= n;
1713         } while (nremaining);
1714         assert(lo == hi);
1715
1716         if (merge_force_collapse(&ms) < 0)
1717                 goto fail;
1718         assert(ms.n == 1);
1719         assert(ms.pending[0].base == saved_ob_item);
1720         assert(ms.pending[0].len == saved_ob_size);
1721
1722 succeed:
1723         result = Py_None;
1724 fail:
1725         if (self->ob_item != empty_ob_item || self->ob_size) {
1726                 /* The user mucked with the list during the sort. */
1727                 (void)list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL);
1728                 if (result != NULL) {
1729                         PyErr_SetString(PyExc_ValueError,
1730                                         "list modified during sort");
1731                         result = NULL;
1732                 }
1733         }
1734         if (self->ob_item == empty_ob_item)
1735                 PyMem_FREE(empty_ob_item);
1736         self->ob_size = saved_ob_size;
1737         self->ob_item = saved_ob_item;
1738         merge_freemem(&ms);
1739         Py_XINCREF(result);
1740         return result;
1741 }
1742 #undef IFLT
1743 #undef ISLT
1744
1745 int
1746 PyList_Sort(PyObject *v)
1747 {
1748         if (v == NULL || !PyList_Check(v)) {
1749                 PyErr_BadInternalCall();
1750                 return -1;
1751         }
1752         v = listsort((PyListObject *)v, (PyObject *)NULL);
1753         if (v == NULL)
1754                 return -1;
1755         Py_DECREF(v);
1756         return 0;
1757 }
1758
1759 static PyObject *
1760 listreverse(PyListObject *self)
1761 {
1762         if (self->ob_size > 1)
1763                 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
1764         Py_INCREF(Py_None);
1765         return Py_None;
1766 }
1767
1768 int
1769 PyList_Reverse(PyObject *v)
1770 {
1771         PyListObject *self = (PyListObject *)v;
1772
1773         if (v == NULL || !PyList_Check(v)) {
1774                 PyErr_BadInternalCall();
1775                 return -1;
1776         }
1777         if (self->ob_size > 1)
1778                 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
1779         return 0;
1780 }
1781
1782 PyObject *
1783 PyList_AsTuple(PyObject *v)
1784 {
1785         PyObject *w;
1786         PyObject **p;
1787         int n;
1788         if (v == NULL || !PyList_Check(v)) {
1789                 PyErr_BadInternalCall();
1790                 return NULL;
1791         }
1792         n = ((PyListObject *)v)->ob_size;
1793         w = PyTuple_New(n);
1794         if (w == NULL)
1795                 return NULL;
1796         p = ((PyTupleObject *)w)->ob_item;
1797         memcpy((void *)p,
1798                (void *)((PyListObject *)v)->ob_item,
1799                n*sizeof(PyObject *));
1800         while (--n >= 0) {
1801                 Py_INCREF(*p);
1802                 p++;
1803         }
1804         return w;
1805 }
1806
1807 static PyObject *
1808 listindex(PyListObject *self, PyObject *v)
1809 {
1810         int i;
1811
1812         for (i = 0; i < self->ob_size; i++) {
1813                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1814                 if (cmp > 0)
1815                         return PyInt_FromLong((long)i);
1816                 else if (cmp < 0)
1817                         return NULL;
1818         }
1819         PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
1820         return NULL;
1821 }
1822
1823 static PyObject *
1824 listcount(PyListObject *self, PyObject *v)
1825 {
1826         int count = 0;
1827         int i;
1828
1829         for (i = 0; i < self->ob_size; i++) {
1830                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1831                 if (cmp > 0)
1832                         count++;
1833                 else if (cmp < 0)
1834                         return NULL;
1835         }
1836         return PyInt_FromLong((long)count);
1837 }
1838
1839 static PyObject *
1840 listremove(PyListObject *self, PyObject *v)
1841 {
1842         int i;
1843
1844         for (i = 0; i < self->ob_size; i++) {
1845                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1846                 if (cmp > 0) {
1847                         if (list_ass_slice(self, i, i+1,
1848                                            (PyObject *)NULL) != 0)
1849                                 return NULL;
1850                         Py_INCREF(Py_None);
1851                         return Py_None;
1852                 }
1853                 else if (cmp < 0)
1854                         return NULL;
1855         }
1856         PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
1857         return NULL;
1858 }
1859
1860 static int
1861 list_traverse(PyListObject *o, visitproc visit, void *arg)
1862 {
1863         int i, err;
1864         PyObject *x;
1865
1866         for (i = o->ob_size; --i >= 0; ) {
1867                 x = o->ob_item[i];
1868                 if (x != NULL) {
1869                         err = visit(x, arg);
1870                         if (err)
1871                                 return err;
1872                 }
1873         }
1874         return 0;
1875 }
1876
1877 static int
1878 list_clear(PyListObject *lp)
1879 {
1880         (void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
1881         return 0;
1882 }
1883
1884 static PyObject *
1885 list_richcompare(PyObject *v, PyObject *w, int op)
1886 {
1887         PyListObject *vl, *wl;
1888         int i;
1889
1890         if (!PyList_Check(v) || !PyList_Check(w)) {
1891                 Py_INCREF(Py_NotImplemented);
1892                 return Py_NotImplemented;
1893         }
1894
1895         vl = (PyListObject *)v;
1896         wl = (PyListObject *)w;
1897
1898         if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
1899                 /* Shortcut: if the lengths differ, the lists differ */
1900                 PyObject *res;
1901                 if (op == Py_EQ)
1902                         res = Py_False;
1903                 else
1904                         res = Py_True;
1905                 Py_INCREF(res);
1906                 return res;
1907         }
1908
1909         /* Search for the first index where items are different */
1910         for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
1911                 int k = PyObject_RichCompareBool(vl->ob_item[i],
1912                                                  wl->ob_item[i], Py_EQ);
1913                 if (k < 0)
1914                         return NULL;
1915                 if (!k)
1916                         break;
1917         }
1918
1919         if (i >= vl->ob_size || i >= wl->ob_size) {
1920                 /* No more items to compare -- compare sizes */
1921                 int vs = vl->ob_size;
1922                 int ws = wl->ob_size;
1923                 int cmp;
1924                 PyObject *res;
1925                 switch (op) {
1926                 case Py_LT: cmp = vs <  ws; break;
1927                 case Py_LE: cmp = vs <= ws; break;
1928                 case Py_EQ: cmp = vs == ws; break;
1929                 case Py_NE: cmp = vs != ws; break;
1930                 case Py_GT: cmp = vs >  ws; break;
1931                 case Py_GE: cmp = vs >= ws; break;
1932                 default: return NULL; /* cannot happen */
1933                 }
1934                 if (cmp)
1935                         res = Py_True;
1936                 else
1937                         res = Py_False;
1938                 Py_INCREF(res);
1939                 return res;
1940         }
1941
1942         /* We have an item that differs -- shortcuts for EQ/NE */
1943         if (op == Py_EQ) {
1944                 Py_INCREF(Py_False);
1945                 return Py_False;
1946         }
1947         if (op == Py_NE) {
1948                 Py_INCREF(Py_True);
1949                 return Py_True;
1950         }
1951
1952         /* Compare the final item again using the proper operator */
1953         return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
1954 }
1955
1956 /* Adapted from newer code by Tim */
1957 static int
1958 list_fill(PyListObject *result, PyObject *v)
1959 {
1960         PyObject *it;      /* iter(v) */
1961         int n;             /* guess for result list size */
1962         int i;
1963
1964         n = result->ob_size;
1965
1966         /* Special-case list(a_list), for speed. */
1967         if (PyList_Check(v)) {
1968                 if (v == (PyObject *)result)
1969                         return 0; /* source is destination, we're done */
1970                 return list_ass_slice(result, 0, n, v);
1971         }
1972
1973         /* Empty previous contents */
1974         if (n != 0) {
1975                 if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
1976                         return -1;
1977         }
1978
1979         /* Get iterator.  There may be some low-level efficiency to be gained
1980          * by caching the tp_iternext slot instead of using PyIter_Next()
1981          * later, but premature optimization is the root etc.
1982          */
1983         it = PyObject_GetIter(v);
1984         if (it == NULL)
1985                 return -1;
1986
1987         /* Guess a result list size. */
1988         n = -1;  /* unknown */
1989         if (PySequence_Check(v) &&
1990             v->ob_type->tp_as_sequence->sq_length) {
1991                 n = PySequence_Size(v);
1992                 if (n < 0)
1993                         PyErr_Clear();
1994         }
1995         if (n < 0)
1996                 n = 8;  /* arbitrary */
1997         NRESIZE(result->ob_item, PyObject*, n);
1998         if (result->ob_item == NULL) {
1999                 PyErr_NoMemory();
2000                 goto error;
2001         }
2002         memset(result->ob_item, 0, sizeof(*result->ob_item) * n);
2003         result->ob_size = n;
2004
2005         /* Run iterator to exhaustion. */
2006         for (i = 0; ; i++) {
2007                 PyObject *item = PyIter_Next(it);
2008                 if (item == NULL) {
2009                         if (PyErr_Occurred())
2010                                 goto error;
2011                         break;
2012                 }
2013                 if (i < n)
2014                         PyList_SET_ITEM(result, i, item); /* steals ref */
2015                 else {
2016                         int status = ins1(result, result->ob_size, item);
2017                         Py_DECREF(item);  /* append creates a new ref */
2018                         if (status < 0)
2019                                 goto error;
2020                 }
2021         }
2022
2023         /* Cut back result list if initial guess was too large. */
2024         if (i < n && result != NULL) {
2025                 if (list_ass_slice(result, i, n, (PyObject *)NULL) != 0)
2026                         goto error;
2027         }
2028         Py_DECREF(it);
2029         return 0;
2030
2031   error:
2032         Py_DECREF(it);
2033         return -1;
2034 }
2035
2036 static int
2037 list_init(PyListObject *self, PyObject *args, PyObject *kw)
2038 {
2039         PyObject *arg = NULL;
2040         static char *kwlist[] = {"sequence", 0};
2041
2042         if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
2043                 return -1;
2044         if (arg != NULL)
2045                 return list_fill(self, arg);
2046         if (self->ob_size > 0)
2047                 return list_ass_slice(self, 0, self->ob_size, (PyObject*)NULL);
2048         return 0;
2049 }
2050
2051 static long
2052 list_nohash(PyObject *self)
2053 {
2054         PyErr_SetString(PyExc_TypeError, "list objects are unhashable");
2055         return -1;
2056 }
2057
2058 PyDoc_STRVAR(append_doc,
2059 "L.append(object) -- append object to end");
2060 PyDoc_STRVAR(extend_doc,
2061 "L.extend(iterable) -- extend list by appending elements from the iterable");
2062 PyDoc_STRVAR(insert_doc,
2063 "L.insert(index, object) -- insert object before index");
2064 PyDoc_STRVAR(pop_doc,
2065 "L.pop([index]) -> item -- remove and return item at index (default last)");
2066 PyDoc_STRVAR(remove_doc,
2067 "L.remove(value) -- remove first occurrence of value");
2068 PyDoc_STRVAR(index_doc,
2069 "L.index(value) -> integer -- return index of first occurrence of value");
2070 PyDoc_STRVAR(count_doc,
2071 "L.count(value) -> integer -- return number of occurrences of value");
2072 PyDoc_STRVAR(reverse_doc,
2073 "L.reverse() -- reverse *IN PLACE*");
2074 PyDoc_STRVAR(sort_doc,
2075 "L.sort(cmpfunc=None) -- stable sort *IN PLACE*; cmpfunc(x, y) -> -1, 0, 1");
2076
2077 static PyMethodDef list_methods[] = {
2078         {"append",      (PyCFunction)listappend,  METH_O, append_doc},
2079         {"insert",      (PyCFunction)listinsert,  METH_VARARGS, insert_doc},
2080         {"extend",      (PyCFunction)listextend,  METH_O, extend_doc},
2081         {"pop",         (PyCFunction)listpop,     METH_VARARGS, pop_doc},
2082         {"remove",      (PyCFunction)listremove,  METH_O, remove_doc},
2083         {"index",       (PyCFunction)listindex,   METH_O, index_doc},
2084         {"count",       (PyCFunction)listcount,   METH_O, count_doc},
2085         {"reverse",     (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
2086         {"sort",        (PyCFunction)listsort,    METH_VARARGS, sort_doc},
2087         {NULL,          NULL}           /* sentinel */
2088 };
2089
2090 static PySequenceMethods list_as_sequence = {
2091         (inquiry)list_length,                   /* sq_length */
2092         (binaryfunc)list_concat,                /* sq_concat */
2093         (intargfunc)list_repeat,                /* sq_repeat */
2094         (intargfunc)list_item,                  /* sq_item */
2095         (intintargfunc)list_slice,              /* sq_slice */
2096         (intobjargproc)list_ass_item,           /* sq_ass_item */
2097         (intintobjargproc)list_ass_slice,       /* sq_ass_slice */
2098         (objobjproc)list_contains,              /* sq_contains */
2099         (binaryfunc)list_inplace_concat,        /* sq_inplace_concat */
2100         (intargfunc)list_inplace_repeat,        /* sq_inplace_repeat */
2101 };
2102
2103 PyDoc_STRVAR(list_doc,
2104 "list() -> new list\n"
2105 "list(sequence) -> new list initialized from sequence's items");
2106
2107 static PyObject *list_iter(PyObject *seq);
2108
2109 static PyObject *
2110 list_subscript(PyListObject* self, PyObject* item)
2111 {
2112         if (PyInt_Check(item)) {
2113                 long i = PyInt_AS_LONG(item);
2114                 if (i < 0)
2115                         i += PyList_GET_SIZE(self);
2116                 return list_item(self, i);
2117         }
2118         else if (PyLong_Check(item)) {
2119                 long i = PyLong_AsLong(item);
2120                 if (i == -1 && PyErr_Occurred())
2121                         return NULL;
2122                 if (i < 0)
2123                         i += PyList_GET_SIZE(self);
2124                 return list_item(self, i);
2125         }
2126         else if (PySlice_Check(item)) {
2127                 int start, stop, step, slicelength, cur, i;
2128                 PyObject* result;
2129                 PyObject* it;
2130
2131                 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2132                                  &start, &stop, &step, &slicelength) < 0) {
2133                         return NULL;
2134                 }
2135
2136                 if (slicelength <= 0) {
2137                         return PyList_New(0);
2138                 }
2139                 else {
2140                         result = PyList_New(slicelength);
2141                         if (!result) return NULL;
2142
2143                         for (cur = start, i = 0; i < slicelength;
2144                              cur += step, i++) {
2145                                 it = PyList_GET_ITEM(self, cur);
2146                                 Py_INCREF(it);
2147                                 PyList_SET_ITEM(result, i, it);
2148                         }
2149
2150                         return result;
2151                 }
2152         }
2153         else {
2154                 PyErr_SetString(PyExc_TypeError,
2155                                 "list indices must be integers");
2156                 return NULL;
2157         }
2158 }
2159
2160 static int
2161 list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2162 {
2163         if (PyInt_Check(item)) {
2164                 long i = PyInt_AS_LONG(item);
2165                 if (i < 0)
2166                         i += PyList_GET_SIZE(self);
2167                 return list_ass_item(self, i, value);
2168         }
2169         else if (PyLong_Check(item)) {
2170                 long i = PyLong_AsLong(item);
2171                 if (i == -1 && PyErr_Occurred())
2172                         return -1;
2173                 if (i < 0)
2174                         i += PyList_GET_SIZE(self);
2175                 return list_ass_item(self, i, value);
2176         }
2177         else if (PySlice_Check(item)) {
2178                 int start, stop, step, slicelength;
2179
2180                 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2181                                  &start, &stop, &step, &slicelength) < 0) {
2182                         return -1;
2183                 }
2184
2185                 /* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
2186                 if (step == 1 && ((PySliceObject*)item)->step == Py_None)
2187                         return list_ass_slice(self, start, stop, value);
2188
2189                 if (value == NULL) {
2190                         /* delete slice */
2191                         PyObject **garbage, **it;
2192                         int cur, i, j;
2193
2194                         if (slicelength <= 0)
2195                                 return 0;
2196
2197                         if (step < 0) {
2198                                 stop = start + 1;
2199                                 start = stop + step*(slicelength - 1) - 1;
2200                                 step = -step;
2201                         }
2202
2203                         garbage = (PyObject**)
2204                                 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2205
2206                         /* drawing pictures might help
2207                            understand these for loops */
2208                         for (cur = start, i = 0;
2209                              cur < stop;
2210                              cur += step, i++) {
2211                                 int lim = step;
2212
2213                                 garbage[i] = PyList_GET_ITEM(self, cur);
2214
2215                                 if (cur + step >= self->ob_size) {
2216                                         lim = self->ob_size - cur - 1;
2217                                 }
2218
2219                                 for (j = 0; j < lim; j++) {
2220                                         PyList_SET_ITEM(self, cur + j - i,
2221                                                 PyList_GET_ITEM(self,
2222                                                                 cur + j + 1));
2223                                 }
2224                         }
2225                         for (cur = start + slicelength*step + 1;
2226                              cur < self->ob_size; cur++) {
2227                                 PyList_SET_ITEM(self, cur - slicelength,
2228                                                 PyList_GET_ITEM(self, cur));
2229                         }
2230                         self->ob_size -= slicelength;
2231                         it = self->ob_item;
2232                         NRESIZE(it, PyObject*, self->ob_size);
2233                         self->ob_item = it;
2234
2235                         for (i = 0; i < slicelength; i++) {
2236                                 Py_DECREF(garbage[i]);
2237                         }
2238                         PyMem_FREE(garbage);
2239
2240                         return 0;
2241                 }
2242                 else {
2243                         /* assign slice */
2244                         PyObject **garbage, *ins, *seq;
2245                         int cur, i;
2246
2247                         /* protect against a[::-1] = a */
2248                         if (self == (PyListObject*)value) {
2249                                 seq = list_slice((PyListObject*)value, 0,
2250                                                    PyList_GET_SIZE(value));
2251                         }
2252                         else {
2253                                 char msg[256];
2254                                 PyOS_snprintf(msg, sizeof(msg),
2255                       "must assign sequence (not \"%.200s\") to extended slice",
2256                                               value->ob_type->tp_name);
2257                                 seq = PySequence_Fast(value, msg);
2258                                 if (!seq)
2259                                         return -1;
2260                         }
2261
2262                         if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2263                                 PyErr_Format(PyExc_ValueError,
2264             "attempt to assign sequence of size %d to extended slice of size %d",
2265                                              PySequence_Fast_GET_SIZE(seq),
2266                                              slicelength);
2267                                 Py_DECREF(seq);
2268                                 return -1;
2269                         }
2270
2271                         if (!slicelength) {
2272                                 Py_DECREF(seq);
2273                                 return 0;
2274                         }
2275
2276                         garbage = (PyObject**)
2277                                 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2278
2279                         for (cur = start, i = 0; i < slicelength;
2280                              cur += step, i++) {
2281                                 garbage[i] = PyList_GET_ITEM(self, cur);
2282
2283                                 ins = PySequence_Fast_GET_ITEM(seq, i);
2284                                 Py_INCREF(ins);
2285                                 PyList_SET_ITEM(self, cur, ins);
2286                         }
2287
2288                         for (i = 0; i < slicelength; i++) {
2289                                 Py_DECREF(garbage[i]);
2290                         }
2291
2292                         PyMem_FREE(garbage);
2293                         Py_DECREF(seq);
2294
2295                         return 0;
2296                 }
2297         }
2298         else {
2299                 PyErr_SetString(PyExc_TypeError,
2300                                 "list indices must be integers");
2301                 return -1;
2302         }
2303 }
2304
2305 static PyMappingMethods list_as_mapping = {
2306         (inquiry)list_length,
2307         (binaryfunc)list_subscript,
2308         (objobjargproc)list_ass_subscript
2309 };
2310
2311 PyTypeObject PyList_Type = {
2312         PyObject_HEAD_INIT(&PyType_Type)
2313         0,
2314         "list",
2315         sizeof(PyListObject),
2316         0,
2317         (destructor)list_dealloc,               /* tp_dealloc */
2318         (printfunc)list_print,                  /* tp_print */
2319         0,                                      /* tp_getattr */
2320         0,                                      /* tp_setattr */
2321         0,                                      /* tp_compare */
2322         (reprfunc)list_repr,                    /* tp_repr */
2323         0,                                      /* tp_as_number */
2324         &list_as_sequence,                      /* tp_as_sequence */
2325         &list_as_mapping,                       /* tp_as_mapping */
2326         list_nohash,                            /* tp_hash */
2327         0,                                      /* tp_call */
2328         0,                                      /* tp_str */
2329         PyObject_GenericGetAttr,                /* tp_getattro */
2330         0,                                      /* tp_setattro */
2331         0,                                      /* tp_as_buffer */
2332         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2333                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
2334         list_doc,                               /* tp_doc */
2335         (traverseproc)list_traverse,            /* tp_traverse */
2336         (inquiry)list_clear,                    /* tp_clear */
2337         list_richcompare,                       /* tp_richcompare */
2338         0,                                      /* tp_weaklistoffset */
2339         list_iter,                              /* tp_iter */
2340         0,                                      /* tp_iternext */
2341         list_methods,                           /* tp_methods */
2342         0,                                      /* tp_members */
2343         0,                                      /* tp_getset */
2344         0,                                      /* tp_base */
2345         0,                                      /* tp_dict */
2346         0,                                      /* tp_descr_get */
2347         0,                                      /* tp_descr_set */
2348         0,                                      /* tp_dictoffset */
2349         (initproc)list_init,                    /* tp_init */
2350         PyType_GenericAlloc,                    /* tp_alloc */
2351         PyType_GenericNew,                      /* tp_new */
2352         PyObject_GC_Del,                        /* tp_free */
2353 };
2354
2355
2356 /*********************** List Iterator **************************/
2357
2358 typedef struct {
2359         PyObject_HEAD
2360         long it_index;
2361         PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
2362 } listiterobject;
2363
2364 PyTypeObject PyListIter_Type;
2365
2366 static PyObject *
2367 list_iter(PyObject *seq)
2368 {
2369         listiterobject *it;
2370
2371         if (!PyList_Check(seq)) {
2372                 PyErr_BadInternalCall();
2373                 return NULL;
2374         }
2375         it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2376         if (it == NULL)
2377                 return NULL;
2378         it->it_index = 0;
2379         Py_INCREF(seq);
2380         it->it_seq = (PyListObject *)seq;
2381         _PyObject_GC_TRACK(it);
2382         return (PyObject *)it;
2383 }
2384
2385 static void
2386 listiter_dealloc(listiterobject *it)
2387 {
2388         _PyObject_GC_UNTRACK(it);
2389         Py_XDECREF(it->it_seq);
2390         PyObject_GC_Del(it);
2391 }
2392
2393 static int
2394 listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2395 {
2396         if (it->it_seq == NULL)
2397                 return 0;
2398         return visit((PyObject *)it->it_seq, arg);
2399 }
2400
2401
2402 static PyObject *
2403 listiter_getiter(PyObject *it)
2404 {
2405         Py_INCREF(it);
2406         return it;
2407 }
2408
2409 static PyObject *
2410 listiter_next(listiterobject *it)
2411 {
2412         PyListObject *seq;
2413         PyObject *item;
2414
2415         assert(it != NULL);
2416         seq = it->it_seq;
2417         if (seq == NULL)
2418                 return NULL;
2419         assert(PyList_Check(seq));
2420
2421         if (it->it_index < PyList_GET_SIZE(seq)) {
2422                 item = PyList_GET_ITEM(seq, it->it_index);
2423                 ++it->it_index;
2424                 Py_INCREF(item);
2425                 return item;
2426         }
2427
2428         Py_DECREF(seq);
2429         it->it_seq = NULL;
2430         return NULL;
2431 }
2432
2433 PyTypeObject PyListIter_Type = {
2434         PyObject_HEAD_INIT(&PyType_Type)
2435         0,                                      /* ob_size */
2436         "listiterator",                         /* tp_name */
2437         sizeof(listiterobject),                 /* tp_basicsize */
2438         0,                                      /* tp_itemsize */
2439         /* methods */
2440         (destructor)listiter_dealloc,           /* tp_dealloc */
2441         0,                                      /* tp_print */
2442         0,                                      /* tp_getattr */
2443         0,                                      /* tp_setattr */
2444         0,                                      /* tp_compare */
2445         0,                                      /* tp_repr */
2446         0,                                      /* tp_as_number */
2447         0,                                      /* tp_as_sequence */
2448         0,                                      /* tp_as_mapping */
2449         0,                                      /* tp_hash */
2450         0,                                      /* tp_call */
2451         0,                                      /* tp_str */
2452         PyObject_GenericGetAttr,                /* tp_getattro */
2453         0,                                      /* tp_setattro */
2454         0,                                      /* tp_as_buffer */
2455         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2456         0,                                      /* tp_doc */
2457         (traverseproc)listiter_traverse,        /* tp_traverse */
2458         0,                                      /* tp_clear */
2459         0,                                      /* tp_richcompare */
2460         0,                                      /* tp_weaklistoffset */
2461         (getiterfunc)listiter_getiter,          /* tp_iter */
2462         (iternextfunc)listiter_next,            /* tp_iternext */
2463         0,                                      /* tp_methods */
2464         0,                                      /* tp_members */
2465         0,                                      /* tp_getset */
2466         0,                                      /* tp_base */
2467         0,                                      /* tp_dict */
2468         0,                                      /* tp_descr_get */
2469         0,                                      /* tp_descr_set */
2470 };