listobject.c 86.9 KB
Newer Older
Guido van Rossum's avatar
Guido van Rossum committed
1 2
/* List object implementation */

3
#include "Python.h"
4
#include "internal/pystate.h"
5
#include "accu.h"
6

7 8 9
#ifdef STDC_HEADERS
#include <stddef.h>
#else
10
#include <sys/types.h>          /* For size_t */
11
#endif
Guido van Rossum's avatar
Guido van Rossum committed
12

13 14 15 16 17 18 19
/*[clinic input]
class list "PyListObject *" "&PyList_Type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/

#include "clinic/listobject.c.h"

20 21 22
/* Ensure ob_item has room for at least newsize elements, and set
 * ob_size to newsize.  If newsize > ob_size on entry, the content
 * of the new slots at exit is undefined heap trash; it's the caller's
23
 * responsibility to overwrite them with sane values.
24 25 26 27 28 29 30 31 32
 * The number of allocated elements may grow, shrink, or stay the same.
 * Failure is impossible if newsize <= self.allocated on entry, although
 * that partly relies on an assumption that the system realloc() never
 * fails when passed a number of bytes <= the number of bytes last
 * allocated (the C standard doesn't guarantee this, but it's hard to
 * imagine a realloc implementation where it wouldn't be true).
 * Note that self->ob_item may change, and even if newsize is less
 * than ob_size on entry.
 */
33
static int
Martin v. Löwis's avatar
Martin v. Löwis committed
34
list_resize(PyListObject *self, Py_ssize_t newsize)
35
{
36
    PyObject **items;
37
    size_t new_allocated, num_allocated_bytes;
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
56 57
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
58
     */
59 60
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
61 62 63 64 65 66
        PyErr_NoMemory();
        return -1;
    }

    if (newsize == 0)
        new_allocated = 0;
67 68
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
69 70 71 72 73 74 75 76
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
77
}
78

Christian Heimes's avatar
Christian Heimes committed
79 80 81 82 83 84 85 86 87
/* Debug statistic to compare allocations with reuse through the free list */
#undef SHOW_ALLOC_COUNT
#ifdef SHOW_ALLOC_COUNT
static size_t count_alloc = 0;
static size_t count_reuse = 0;

static void
show_alloc(void)
{
88 89 90 91 92 93 94 95 96 97
    PyObject *xoptions, *value;
    _Py_IDENTIFIER(showalloccount);

    xoptions = PySys_GetXOptions();
    if (xoptions == NULL)
        return;
    value = _PyDict_GetItemId(xoptions, &PyId_showalloccount);
    if (value != Py_True)
        return;

98 99 100 101 102 103
    fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",
        count_alloc);
    fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T
        "d\n", count_reuse);
    fprintf(stderr, "%.2f%% reuse rate\n\n",
        (100.0*count_reuse/(count_alloc+count_reuse)));
Christian Heimes's avatar
Christian Heimes committed
104 105 106
}
#endif

107
/* Empty list reuse scheme to save calls to malloc and free */
Christian Heimes's avatar
Christian Heimes committed
108 109 110 111 112
#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;
113

114 115
int
PyList_ClearFreeList(void)
116
{
117
    PyListObject *op;
118
    int ret = numfree;
119 120 121 122 123
    while (numfree) {
        op = free_list[--numfree];
        assert(PyList_CheckExact(op));
        PyObject_GC_Del(op);
    }
124 125 126 127 128 129 130
    return ret;
}

void
PyList_Fini(void)
{
    PyList_ClearFreeList();
131 132
}

133 134 135 136 137 138 139 140 141
/* Print summary info about the state of the optimized allocator */
void
_PyList_DebugMallocStats(FILE *out)
{
    _PyDebugAllocatorStats(out,
                           "free PyListObject",
                           numfree, sizeof(PyListObject));
}

142
PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
143
PyList_New(Py_ssize_t size)
Guido van Rossum's avatar
Guido van Rossum committed
144
{
145
    PyListObject *op;
Christian Heimes's avatar
Christian Heimes committed
146
#ifdef SHOW_ALLOC_COUNT
147 148 149 150 151
    static int initialized = 0;
    if (!initialized) {
        Py_AtExit(show_alloc);
        initialized = 1;
    }
Christian Heimes's avatar
Christian Heimes committed
152
#endif
153

154 155 156 157 158 159 160 161
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
Christian Heimes's avatar
Christian Heimes committed
162
#ifdef SHOW_ALLOC_COUNT
163
        count_reuse++;
Christian Heimes's avatar
Christian Heimes committed
164
#endif
165 166 167 168
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
Christian Heimes's avatar
Christian Heimes committed
169
#ifdef SHOW_ALLOC_COUNT
170
        count_alloc++;
Christian Heimes's avatar
Christian Heimes committed
171
#endif
172 173 174 175
    }
    if (size <= 0)
        op->ob_item = NULL;
    else {
176
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
177 178 179 180 181 182 183 184 185
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
Guido van Rossum's avatar
Guido van Rossum committed
186 187
}

Martin v. Löwis's avatar
Martin v. Löwis committed
188
Py_ssize_t
189
PyList_Size(PyObject *op)
Guido van Rossum's avatar
Guido van Rossum committed
190
{
191 192 193 194 195 196
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    else
        return Py_SIZE(op);
Guido van Rossum's avatar
Guido van Rossum committed
197 198
}

Raymond Hettinger's avatar
Raymond Hettinger committed
199
static PyObject *indexerr = NULL;
200

201
PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
202
PyList_GetItem(PyObject *op, Py_ssize_t i)
Guido van Rossum's avatar
Guido van Rossum committed
203
{
204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum's avatar
Guido van Rossum committed
219 220 221
}

int
222 223
PyList_SetItem(PyObject *op, Py_ssize_t i,
               PyObject *newitem)
Guido van Rossum's avatar
Guido van Rossum committed
224
{
225
    PyObject **p;
226 227 228 229 230 231 232 233 234 235 236 237
    if (!PyList_Check(op)) {
        Py_XDECREF(newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        Py_XDECREF(newitem);
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    p = ((PyListObject *)op) -> ob_item + i;
238
    Py_XSETREF(*p, newitem);
239
    return 0;
Guido van Rossum's avatar
Guido van Rossum committed
240 241 242
}

static int
Martin v. Löwis's avatar
Martin v. Löwis committed
243
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
Guido van Rossum's avatar
Guido van Rossum committed
244
{
245 246 247 248 249 250 251 252 253 254 255 256
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

257
    if (list_resize(self, n+1) < 0)
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
        return -1;

    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
Guido van Rossum's avatar
Guido van Rossum committed
273 274 275
}

int
Martin v. Löwis's avatar
Martin v. Löwis committed
276
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
Guido van Rossum's avatar
Guido van Rossum committed
277
{
278 279 280 281 282
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return ins1((PyListObject *)op, where, newitem);
Guido van Rossum's avatar
Guido van Rossum committed
283 284
}

285 286 287
static int
app1(PyListObject *self, PyObject *v)
{
288
    Py_ssize_t n = PyList_GET_SIZE(self);
289

290 291 292 293 294 295
    assert (v != NULL);
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
296

297
    if (list_resize(self, n+1) < 0)
298
        return -1;
299

300 301 302
    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
303 304
}

Guido van Rossum's avatar
Guido van Rossum committed
305
int
306
PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum's avatar
Guido van Rossum committed
307
{
308 309 310 311
    if (PyList_Check(op) && (newitem != NULL))
        return app1((PyListObject *)op, newitem);
    PyErr_BadInternalCall();
    return -1;
Guido van Rossum's avatar
Guido van Rossum committed
312 313 314 315 316
}

/* Methods */

static void
317
list_dealloc(PyListObject *op)
Guido van Rossum's avatar
Guido van Rossum committed
318
{
319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_SAFE_BEGIN(op)
    if (op->ob_item != NULL) {
        /* Do it backwards, for Christian Tismer.
           There's a simple test case where somehow this reduces
           thrashing when a *very* large list is created and
           immediately deleted. */
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
Guido van Rossum's avatar
Guido van Rossum committed
338 339
}

340
static PyObject *
341
list_repr(PyListObject *v)
Guido van Rossum's avatar
Guido van Rossum committed
342
{
343
    Py_ssize_t i;
344 345
    PyObject *s;
    _PyUnicodeWriter writer;
346 347 348 349 350

    if (Py_SIZE(v) == 0) {
        return PyUnicode_FromString("[]");
    }

351 352 353 354 355
    i = Py_ReprEnter((PyObject*)v);
    if (i != 0) {
        return i > 0 ? PyUnicode_FromString("[...]") : NULL;
    }

356 357
    _PyUnicodeWriter_Init(&writer);
    writer.overallocate = 1;
358 359
    /* "[" + "1" + ", 2" * (len - 1) + "]" */
    writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
360

361
    if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)
362
        goto error;
363 364 365 366

    /* Do repr() on each element.  Note that this may mutate the list,
       so must refetch the list size on each iteration. */
    for (i = 0; i < Py_SIZE(v); ++i) {
367
        if (i > 0) {
368
            if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
369 370 371
                goto error;
        }

372
        if (Py_EnterRecursiveCall(" while getting the repr of a list"))
373
            goto error;
374 375
        s = PyObject_Repr(v->ob_item[i]);
        Py_LeaveRecursiveCall();
376
        if (s == NULL)
377
            goto error;
378 379 380

        if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
            Py_DECREF(s);
381
            goto error;
382 383
        }
        Py_DECREF(s);
384
    }
385

386
    writer.overallocate = 0;
387
    if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
388
        goto error;
389

390
    Py_ReprLeave((PyObject *)v);
391
    return _PyUnicodeWriter_Finish(&writer);
392

393
error:
394
    _PyUnicodeWriter_Dealloc(&writer);
395
    Py_ReprLeave((PyObject *)v);
396
    return NULL;
Guido van Rossum's avatar
Guido van Rossum committed
397 398
}

Martin v. Löwis's avatar
Martin v. Löwis committed
399
static Py_ssize_t
400
list_length(PyListObject *a)
Guido van Rossum's avatar
Guido van Rossum committed
401
{
402
    return Py_SIZE(a);
Guido van Rossum's avatar
Guido van Rossum committed
403 404
}

405
static int
406
list_contains(PyListObject *a, PyObject *el)
407
{
408 409
    Py_ssize_t i;
    int cmp;
410

411 412 413 414
    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
415 416
}

417
static PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
418
list_item(PyListObject *a, Py_ssize_t i)
Guido van Rossum's avatar
Guido van Rossum committed
419
{
420 421 422 423 424 425 426 427 428 429 430 431
    if (i < 0 || i >= Py_SIZE(a)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    Py_INCREF(a->ob_item[i]);
    return a->ob_item[i];
Guido van Rossum's avatar
Guido van Rossum committed
432 433
}

434
static PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
435
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum's avatar
Guido van Rossum committed
436
{
437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    len = ihigh - ilow;
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;

    src = a->ob_item + ilow;
    dest = np->ob_item;
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
Guido van Rossum's avatar
Guido van Rossum committed
461 462
}

463
PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
464
PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
465
{
466 467 468 469 470
    if (!PyList_Check(a)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    return list_slice((PyListObject *)a, ilow, ihigh);
471 472
}

473
static PyObject *
474
list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum's avatar
Guido van Rossum committed
475
{
476 477 478 479 480 481 482 483 484 485
    Py_ssize_t size;
    Py_ssize_t i;
    PyObject **src, **dest;
    PyListObject *np;
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                  "can only concatenate list (not \"%.200s\") to list",
                  bb->ob_type->tp_name);
        return NULL;
    }
486
#define b ((PyListObject *)bb)
487
    if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))
488
        return PyErr_NoMemory();
489
    size = Py_SIZE(a) + Py_SIZE(b);
490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508
    np = (PyListObject *) PyList_New(size);
    if (np == NULL) {
        return NULL;
    }
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
Guido van Rossum's avatar
Guido van Rossum committed
509 510 511
#undef b
}

512
static PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
513
list_repeat(PyListObject *a, Py_ssize_t n)
514
{
515 516 517 518 519 520 521
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
522
    if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
523
        return PyErr_NoMemory();
524
    size = Py_SIZE(a) * n;
525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);
    if (np == NULL)
        return NULL;

    items = np->ob_item;
    if (Py_SIZE(a) == 1) {
        elem = a->ob_item[0];
        for (i = 0; i < n; i++) {
            items[i] = elem;
            Py_INCREF(elem);
        }
        return (PyObject *) np;
    }
    p = np->ob_item;
    items = a->ob_item;
    for (i = 0; i < n; i++) {
        for (j = 0; j < Py_SIZE(a); j++) {
            *p = items[j];
            Py_INCREF(*p);
            p++;
        }
    }
    return (PyObject *) np;
550 551
}

552
static int
553
_list_clear(PyListObject *a)
554
{
555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
        /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
            Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there is no guarantee that the list is actually empty
       at this point, because XDECREF may have populated it again! */
    return 0;
573 574
}

575 576 577 578 579 580
/* a[ilow:ihigh] = v if v != NULL.
 * del a[ilow:ihigh] if v == NULL.
 *
 * Special speed gimmick:  when v is NULL and ihigh - ilow <= 8, it's
 * guaranteed the call cannot fail.
 */
Guido van Rossum's avatar
Guido van Rossum committed
581
static int
Martin v. Löwis's avatar
Martin v. Löwis committed
582
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum's avatar
Guido van Rossum committed
583
{
584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
    /* Because [X]DECREF can recursively invoke list operations on
       this list, we must postpone all [X]DECREF activity until
       after the list is back in its canonical shape.  Therefore
       we must allocate an additional array, 'recycle', into which
       we temporarily copy the items that are deleted from the
       list. :-( */
    PyObject *recycle_on_stack[8];
    PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
    PyObject **item;
    PyObject **vitem = NULL;
    PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
    Py_ssize_t n; /* # of elements in replacement list */
    Py_ssize_t norig; /* # of elements in list getting replaced */
    Py_ssize_t d; /* Change in size */
    Py_ssize_t k;
    size_t s;
    int result = -1;            /* guilty until proved innocent */
601
#define b ((PyListObject *)v)
602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634
    if (v == NULL)
        n = 0;
    else {
        if (a == b) {
            /* Special case "a[i:j] = a" -- copy b first */
            v = list_slice(b, 0, Py_SIZE(b));
            if (v == NULL)
                return result;
            result = list_ass_slice(a, ilow, ihigh, v);
            Py_DECREF(v);
            return result;
        }
        v_as_SF = PySequence_Fast(v, "can only assign an iterable");
        if(v_as_SF == NULL)
            goto Error;
        n = PySequence_Fast_GET_SIZE(v_as_SF);
        vitem = PySequence_Fast_ITEMS(v_as_SF);
    }
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);

    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);

    norig = ihigh - ilow;
    assert(norig >= 0);
    d = n - norig;
    if (Py_SIZE(a) + d == 0) {
        Py_XDECREF(v_as_SF);
635
        return _list_clear(a);
636 637 638 639
    }
    item = a->ob_item;
    /* recycle the items that we are about to remove */
    s = norig * sizeof(PyObject *);
640 641 642 643 644 645 646 647
    /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
    if (s) {
        if (s > sizeof(recycle_on_stack)) {
            recycle = (PyObject **)PyMem_MALLOC(s);
            if (recycle == NULL) {
                PyErr_NoMemory();
                goto Error;
            }
648
        }
649
        memcpy(recycle, &item[ilow], s);
650 651 652
    }

    if (d < 0) { /* Delete -d items */
653 654 655 656 657 658 659 660
        Py_ssize_t tail;
        tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
        memmove(&item[ihigh+d], &item[ihigh], tail);
        if (list_resize(a, Py_SIZE(a) + d) < 0) {
            memmove(&item[ihigh], &item[ihigh+d], tail);
            memcpy(&item[ilow], recycle, s);
            goto Error;
        }
661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678
        item = a->ob_item;
    }
    else if (d > 0) { /* Insert d items */
        k = Py_SIZE(a);
        if (list_resize(a, k+d) < 0)
            goto Error;
        item = a->ob_item;
        memmove(&item[ihigh+d], &item[ihigh],
            (k - ihigh)*sizeof(PyObject *));
    }
    for (k = 0; k < n; k++, ilow++) {
        PyObject *w = vitem[k];
        Py_XINCREF(w);
        item[ilow] = w;
    }
    for (k = norig - 1; k >= 0; --k)
        Py_XDECREF(recycle[k]);
    result = 0;
679
 Error:
680 681 682 683
    if (recycle != recycle_on_stack)
        PyMem_FREE(recycle);
    Py_XDECREF(v_as_SF);
    return result;
Guido van Rossum's avatar
Guido van Rossum committed
684 685 686
#undef b
}

687
int
Martin v. Löwis's avatar
Martin v. Löwis committed
688
PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
689
{
690 691 692 693 694
    if (!PyList_Check(a)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
695 696
}

697
static PyObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
698
list_inplace_repeat(PyListObject *self, Py_ssize_t n)
699
{
700 701
    PyObject **items;
    Py_ssize_t size, i, j, p;
702 703


704 705 706 707 708
    size = PyList_GET_SIZE(self);
    if (size == 0 || n == 1) {
        Py_INCREF(self);
        return (PyObject *)self;
    }
709

710
    if (n < 1) {
711
        (void)_list_clear(self);
712 713 714
        Py_INCREF(self);
        return (PyObject *)self;
    }
715

716 717 718
    if (size > PY_SSIZE_T_MAX / n) {
        return PyErr_NoMemory();
    }
719

720
    if (list_resize(self, size*n) < 0)
721
        return NULL;
722

723 724 725 726 727 728 729 730 731 732 733
    p = size;
    items = self->ob_item;
    for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
        for (j = 0; j < size; j++) {
            PyObject *o = items[j];
            Py_INCREF(o);
            items[p++] = o;
        }
    }
    Py_INCREF(self);
    return (PyObject *)self;
734 735
}

736
static int
Martin v. Löwis's avatar
Martin v. Löwis committed
737
list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
738
{
739 740 741 742 743 744 745 746
    if (i < 0 || i >= Py_SIZE(a)) {
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    if (v == NULL)
        return list_ass_slice(a, i, i+1, v);
    Py_INCREF(v);
747
    Py_SETREF(a->ob_item[i], v);
748
    return 0;
749 750
}

751 752 753 754 755 756 757 758 759 760
/*[clinic input]
list.insert

    index: Py_ssize_t
    object: object
    /

Insert object before index.
[clinic start generated code]*/

761
static PyObject *
762 763
list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
/*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
Guido van Rossum's avatar
Guido van Rossum committed
764
{
765
    if (ins1(self, index, object) == 0)
766 767
        Py_RETURN_NONE;
    return NULL;
Guido van Rossum's avatar
Guido van Rossum committed
768 769
}

770 771 772 773 774 775
/*[clinic input]
list.clear

Remove all items from list.
[clinic start generated code]*/

776
static PyObject *
777 778
list_clear_impl(PyListObject *self)
/*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/
779
{
780
    _list_clear(self);
781 782 783
    Py_RETURN_NONE;
}

784 785 786 787 788 789
/*[clinic input]
list.copy

Return a shallow copy of the list.
[clinic start generated code]*/

790
static PyObject *
791 792
list_copy_impl(PyListObject *self)
/*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/
793 794 795 796
{
    return list_slice(self, 0, Py_SIZE(self));
}

797 798 799 800 801 802 803 804 805
/*[clinic input]
list.append

     object: object
     /

Append object to the end of the list.
[clinic start generated code]*/

806
static PyObject *
807 808
list_append(PyListObject *self, PyObject *object)
/*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
Guido van Rossum's avatar
Guido van Rossum committed
809
{
810
    if (app1(self, object) == 0)
811 812
        Py_RETURN_NONE;
    return NULL;
Guido van Rossum's avatar
Guido van Rossum committed
813 814
}

815 816 817 818 819 820 821 822 823
/*[clinic input]
list.extend

     iterable: object
     /

Extend list by appending elements from the iterable.
[clinic start generated code]*/

824
static PyObject *
825 826
list_extend(PyListObject *self, PyObject *iterable)
/*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/
827
{
828 829
    PyObject *it;      /* iter(v) */
    Py_ssize_t m;                  /* size of self */
830
    Py_ssize_t n;                  /* guess for size of iterable */
831 832 833 834 835 836 837 838
    Py_ssize_t mn;                 /* m + n */
    Py_ssize_t i;
    PyObject *(*iternext)(PyObject *);

    /* Special cases:
       1) lists and tuples which can use PySequence_Fast ops
       2) extending self to self requires making a copy first
    */
839 840
    if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
                (PyObject *)self == iterable) {
841
        PyObject **src, **dest;
842 843
        iterable = PySequence_Fast(iterable, "argument must be iterable");
        if (!iterable)
844
            return NULL;
845
        n = PySequence_Fast_GET_SIZE(iterable);
846
        if (n == 0) {
847 848
            /* short circuit when iterable is empty */
            Py_DECREF(iterable);
849 850 851
            Py_RETURN_NONE;
        }
        m = Py_SIZE(self);
852 853 854
        /* It should not be possible to allocate a list large enough to cause
        an overflow on any relevant platform */
        assert(m < PY_SSIZE_T_MAX - n);
855
        if (list_resize(self, m + n) < 0) {
856
            Py_DECREF(iterable);
857 858
            return NULL;
        }
859
        /* note that we may still have self == iterable here for the
860 861 862 863
         * situation a.extend(a), but the following code works
         * in that case too.  Just make sure to resize self
         * before calling PySequence_Fast_ITEMS.
         */
864 865
        /* populate the end of self with iterable's items */
        src = PySequence_Fast_ITEMS(iterable);
866 867 868 869 870 871
        dest = self->ob_item + m;
        for (i = 0; i < n; i++) {
            PyObject *o = src[i];
            Py_INCREF(o);
            dest[i] = o;
        }
872
        Py_DECREF(iterable);
873 874 875
        Py_RETURN_NONE;
    }

876
    it = PyObject_GetIter(iterable);
877 878 879 880 881
    if (it == NULL)
        return NULL;
    iternext = *it->ob_type->tp_iternext;

    /* Guess a result list size. */
882
    n = PyObject_LengthHint(iterable, 8);
883
    if (n < 0) {
884 885 886 887
        Py_DECREF(it);
        return NULL;
    }
    m = Py_SIZE(self);
888 889 890 891 892 893 894 895
    if (m > PY_SSIZE_T_MAX - n) {
        /* m + n overflowed; on the chance that n lied, and there really
         * is enough room, ignore it.  If n was telling the truth, we'll
         * eventually run out of memory during the loop.
         */
    }
    else {
        mn = m + n;
896
        /* Make room. */
897
        if (list_resize(self, mn) < 0)
898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928
            goto error;
        /* Make the list sane again. */
        Py_SIZE(self) = m;
    }

    /* Run iterator to exhaustion. */
    for (;;) {
        PyObject *item = iternext(it);
        if (item == NULL) {
            if (PyErr_Occurred()) {
                if (PyErr_ExceptionMatches(PyExc_StopIteration))
                    PyErr_Clear();
                else
                    goto error;
            }
            break;
        }
        if (Py_SIZE(self) < self->allocated) {
            /* steals ref */
            PyList_SET_ITEM(self, Py_SIZE(self), item);
            ++Py_SIZE(self);
        }
        else {
            int status = app1(self, item);
            Py_DECREF(item);  /* append creates a new ref */
            if (status < 0)
                goto error;
        }
    }

    /* Cut back result list if initial guess was too large. */
929 930 931 932
    if (Py_SIZE(self) < self->allocated) {
        if (list_resize(self, Py_SIZE(self)) < 0)
            goto error;
    }
933 934 935

    Py_DECREF(it);
    Py_RETURN_NONE;
936 937

  error:
938 939
    Py_DECREF(it);
    return NULL;
940
}
941

942
PyObject *
943
_PyList_Extend(PyListObject *self, PyObject *iterable)
944
{
945
    return list_extend(self, iterable);
946 947
}

948 949 950
static PyObject *
list_inplace_concat(PyListObject *self, PyObject *other)
{
951
    PyObject *result;
952

953
    result = list_extend(self, other);
954 955 956 957 958
    if (result == NULL)
        return result;
    Py_DECREF(result);
    Py_INCREF(self);
    return (PyObject *)self;
959 960
}

961 962 963 964 965 966 967 968 969 970 971
/*[clinic input]
list.pop

    index: Py_ssize_t = -1
    /

Remove and return item at index (default last).

Raises IndexError if list is empty or index is out of range.
[clinic start generated code]*/

972
static PyObject *
973 974
list_pop_impl(PyListObject *self, Py_ssize_t index)
/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
975
{
976 977 978 979 980 981 982 983
    PyObject *v;
    int status;

    if (Py_SIZE(self) == 0) {
        /* Special-case most common failure cause */
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
984 985 986
    if (index < 0)
        index += Py_SIZE(self);
    if (index < 0 || index >= Py_SIZE(self)) {
987 988 989
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
990 991
    v = self->ob_item[index];
    if (index == Py_SIZE(self) - 1) {
992
        status = list_resize(self, Py_SIZE(self) - 1);
993 994 995 996
        if (status >= 0)
            return v; /* and v now owns the reference the list had */
        else
            return NULL;
997 998
    }
    Py_INCREF(v);
999
    status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
1000 1001 1002 1003
    if (status < 0) {
        Py_DECREF(v);
        return NULL;
    }
1004
    return v;
1005 1006
}

1007 1008 1009 1010
/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
1011
    assert(lo && hi);
1012

1013 1014 1015 1016 1017 1018 1019 1020
    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
1021 1022
}

1023 1024 1025
/* Lots of code for an adaptive, stable, natural mergesort.  There are many
 * pieces to this algorithm; read listsort.txt for overviews and details.
 */
1026

1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
/* A sortslice contains a pointer to an array of keys and a pointer to
 * an array of corresponding values.  In other words, keys[i]
 * corresponds with values[i].  If values == NULL, then the keys are
 * also the values.
 *
 * Several convenience routines are provided here, so that keys and
 * values are always moved in sync.
 */

typedef struct {
    PyObject **keys;
    PyObject **values;
} sortslice;

Py_LOCAL_INLINE(void)
sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
{
    s1->keys[i] = s2->keys[j];
    if (s1->values != NULL)
        s1->values[i] = s2->values[j];
}

Py_LOCAL_INLINE(void)
Benjamin Peterson's avatar
Benjamin Peterson committed
1050 1051
sortslice_copy_incr(sortslice *dst, sortslice *src)
{
1052 1053 1054 1055 1056 1057
    *dst->keys++ = *src->keys++;
    if (dst->values != NULL)
        *dst->values++ = *src->values++;
}

Py_LOCAL_INLINE(void)
Benjamin Peterson's avatar
Benjamin Peterson committed
1058 1059
sortslice_copy_decr(sortslice *dst, sortslice *src)
{
1060 1061 1062 1063 1064 1065 1066 1067
    *dst->keys-- = *src->keys--;
    if (dst->values != NULL)
        *dst->values-- = *src->values--;
}


Py_LOCAL_INLINE(void)
sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
Benjamin Peterson's avatar
Benjamin Peterson committed
1068 1069
                 Py_ssize_t n)
{
1070 1071 1072 1073 1074 1075 1076
    memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
    if (s1->values != NULL)
        memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
}

Py_LOCAL_INLINE(void)
sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
Benjamin Peterson's avatar
Benjamin Peterson committed
1077 1078
                  Py_ssize_t n)
{
1079 1080 1081 1082 1083 1084
    memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
    if (s1->values != NULL)
        memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
}

Py_LOCAL_INLINE(void)
Benjamin Peterson's avatar
Benjamin Peterson committed
1085 1086
sortslice_advance(sortslice *slice, Py_ssize_t n)
{
1087 1088 1089 1090 1091
    slice->keys += n;
    if (slice->values != NULL)
        slice->values += n;
}

1092
/* Comparison function: PyObject_RichCompareBool with Py_LT.
1093 1094
 * Returns -1 on error, 1 if x < y, 0 if x >= y.
 */
1095

1096
#define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT))
1097 1098

/* Compare X to Y via "<".  Goto "fail" if the comparison raises an
1099 1100 1101
   error.  Else "k" is set to true iff X<Y, and an "if (k)" block is
   started.  It makes more sense in context <wink>.  X and Y are PyObject*s.
*/
1102
#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail;  \
1103
           if (k)
1104 1105 1106 1107

/* binarysort is the best method for sorting small arrays: it does
   few compares, but can do data movement quadratic in the number of
   elements.
1108
   [lo, hi) is a contiguous slice of a list, and is sorted via
1109
   binary insertion.  This sort is stable.
1110 1111
   On entry, must have lo <= start <= hi, and that [lo, start) is already
   sorted (pass start == lo if you don't know!).
1112
   If islt() complains return -1, else 0.
1113 1114 1115 1116
   Even in case of error, the output slice will be some permutation of
   the input (nothing is lost or duplicated).
*/
static int
1117
binarysort(sortslice lo, PyObject **hi, PyObject **start)
1118
{
1119 1120 1121
    Py_ssize_t k;
    PyObject **l, **p, **r;
    PyObject *pivot;
1122

1123
    assert(lo.keys <= start && start <= hi);
1124
    /* assert [lo, start) is sorted */
1125
    if (lo.keys == start)
1126 1127 1128
        ++start;
    for (; start < hi; ++start) {
        /* set l to where *start belongs */
1129
        l = lo.keys;
1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155
        r = start;
        pivot = *r;
        /* Invariants:
         * pivot >= all in [lo, l).
         * pivot  < all in [r, start).
         * The second is vacuously true at the start.
         */
        assert(l < r);
        do {
            p = l + ((r - l) >> 1);
            IFLT(pivot, *p)
                r = p;
            else
                l = p+1;
        } while (l < r);
        assert(l == r);
        /* The invariants still hold, so pivot >= all in [lo, l) and
           pivot < all in [l, start), so pivot belongs at l.  Note
           that if there are elements equal to pivot, l points to the
           first slot after them -- that's why this sort is stable.
           Slide over to make room.
           Caution: using memmove is much slower under MSVC 5;
           we're not usually moving many slots. */
        for (p = start; p > l; --p)
            *p = *(p-1);
        *l = pivot;
1156 1157 1158 1159 1160 1161 1162 1163 1164
        if (lo.values != NULL) {
            Py_ssize_t offset = lo.values - lo.keys;
            p = start + offset;
            pivot = *p;
            l += offset;
            for (p = start + offset; p > l; --p)
                *p = *(p-1);
            *l = pivot;
        }
1165 1166
    }
    return 0;
1167

1168
 fail:
1169
    return -1;
1170 1171
}

1172 1173 1174
/*
Return the length of the run beginning at lo, in the slice [lo, hi).  lo < hi
is required on entry.  "A run" is the longest ascending sequence, with
1175

1176
    lo[0] <= lo[1] <= lo[2] <= ...
1177

1178
or the longest descending sequence, with
1179

1180 1181 1182 1183 1184 1185 1186
    lo[0] > lo[1] > lo[2] > ...

Boolean *descending is set to 0 in the former case, or to 1 in the latter.
For its intended use in a stable mergesort, the strictness of the defn of
"descending" is needed so that the caller can safely reverse a descending
sequence without violating stability (strict > ensures there are no equal
elements to get out of order).
1187

1188 1189
Returns -1 in case of error.
*/
Martin v. Löwis's avatar
Martin v. Löwis committed
1190
static Py_ssize_t
1191
count_run(PyObject **lo, PyObject **hi, int *descending)
1192
{
1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219
    Py_ssize_t k;
    Py_ssize_t n;

    assert(lo < hi);
    *descending = 0;
    ++lo;
    if (lo == hi)
        return 1;

    n = 2;
    IFLT(*lo, *(lo-1)) {
        *descending = 1;
        for (lo = lo+1; lo < hi; ++lo, ++n) {
            IFLT(*lo, *(lo-1))
                ;
            else
                break;
        }
    }
    else {
        for (lo = lo+1; lo < hi; ++lo, ++n) {
            IFLT(*lo, *(lo-1))
                break;
        }
    }

    return n;
1220
fail:
1221
    return -1;
1222
}
1223

1224 1225 1226 1227 1228
/*
Locate the proper position of key in a sorted vector; if the vector contains
an element equal to key, return the position immediately to the left of
the leftmost equal element.  [gallop_right() does the same except returns
the position to the right of the rightmost equal element (if any).]
1229

1230
"a" is a sorted vector with n elements, starting at a[0].  n must be > 0.
1231

1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244
"hint" is an index at which to begin the search, 0 <= hint < n.  The closer
hint is to the final result, the faster this runs.

The return value is the int k in 0..n such that

    a[k-1] < key <= a[k]

pretending that *(a-1) is minus infinity and a[n] is plus infinity.  IOW,
key belongs at index k; or, IOW, the first k elements of a should precede
key, and the last n-k should follow key.

Returns -1 on error.  See listsort.txt for info on the method.
*/
Martin v. Löwis's avatar
Martin v. Löwis committed
1245
static Py_ssize_t
1246
gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
1247
{
1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316
    Py_ssize_t ofs;
    Py_ssize_t lastofs;
    Py_ssize_t k;

    assert(key && a && n > 0 && hint >= 0 && hint < n);

    a += hint;
    lastofs = 0;
    ofs = 1;
    IFLT(*a, key) {
        /* a[hint] < key -- gallop right, until
         * a[hint + lastofs] < key <= a[hint + ofs]
         */
        const Py_ssize_t maxofs = n - hint;             /* &a[n-1] is highest */
        while (ofs < maxofs) {
            IFLT(a[ofs], key) {
                lastofs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)                   /* int overflow */
                    ofs = maxofs;
            }
            else                /* key <= a[hint + ofs] */
                break;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to offsets relative to &a[0]. */
        lastofs += hint;
        ofs += hint;
    }
    else {
        /* key <= a[hint] -- gallop left, until
         * a[hint - ofs] < key <= a[hint - lastofs]
         */
        const Py_ssize_t maxofs = hint + 1;             /* &a[0] is lowest */
        while (ofs < maxofs) {
            IFLT(*(a-ofs), key)
                break;
            /* key <= a[hint - ofs] */
            lastofs = ofs;
            ofs = (ofs << 1) + 1;
            if (ofs <= 0)               /* int overflow */
                ofs = maxofs;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to positive offsets relative to &a[0]. */
        k = lastofs;
        lastofs = hint - ofs;
        ofs = hint - k;
    }
    a -= hint;

    assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
    /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
     * right of lastofs but no farther right than ofs.  Do a binary
     * search, with invariant a[lastofs-1] < key <= a[ofs].
     */
    ++lastofs;
    while (lastofs < ofs) {
        Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);

        IFLT(a[m], key)
            lastofs = m+1;              /* a[m] < key */
        else
            ofs = m;                    /* key <= a[m] */
    }
    assert(lastofs == ofs);             /* so a[ofs-1] < key <= a[ofs] */
    return ofs;
1317

1318
fail:
1319
    return -1;
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335
}

/*
Exactly like gallop_left(), except that if key already exists in a[0:n],
finds the position immediately to the right of the rightmost equal value.

The return value is the int k in 0..n such that

    a[k-1] <= key < a[k]

or -1 if error.

The code duplication is massive, but this is enough different given that
we're sticking to "<" comparisons that it's much harder to follow if
written as one routine with yet another "left or right?" flag.
*/
Martin v. Löwis's avatar
Martin v. Löwis committed
1336
static Py_ssize_t
1337
gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
1338
{
1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407
    Py_ssize_t ofs;
    Py_ssize_t lastofs;
    Py_ssize_t k;

    assert(key && a && n > 0 && hint >= 0 && hint < n);

    a += hint;
    lastofs = 0;
    ofs = 1;
    IFLT(key, *a) {
        /* key < a[hint] -- gallop left, until
         * a[hint - ofs] <= key < a[hint - lastofs]
         */
        const Py_ssize_t maxofs = hint + 1;             /* &a[0] is lowest */
        while (ofs < maxofs) {
            IFLT(key, *(a-ofs)) {
                lastofs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)                   /* int overflow */
                    ofs = maxofs;
            }
            else                /* a[hint - ofs] <= key */
                break;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to positive offsets relative to &a[0]. */
        k = lastofs;
        lastofs = hint - ofs;
        ofs = hint - k;
    }
    else {
        /* a[hint] <= key -- gallop right, until
         * a[hint + lastofs] <= key < a[hint + ofs]
        */
        const Py_ssize_t maxofs = n - hint;             /* &a[n-1] is highest */
        while (ofs < maxofs) {
            IFLT(key, a[ofs])
                break;
            /* a[hint + ofs] <= key */
            lastofs = ofs;
            ofs = (ofs << 1) + 1;
            if (ofs <= 0)               /* int overflow */
                ofs = maxofs;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to offsets relative to &a[0]. */
        lastofs += hint;
        ofs += hint;
    }
    a -= hint;

    assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
    /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
     * right of lastofs but no farther right than ofs.  Do a binary
     * search, with invariant a[lastofs-1] <= key < a[ofs].
     */
    ++lastofs;
    while (lastofs < ofs) {
        Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);

        IFLT(key, a[m])
            ofs = m;                    /* key < a[m] */
        else
            lastofs = m+1;              /* a[m] <= key */
    }
    assert(lastofs == ofs);             /* so a[ofs-1] <= key < a[ofs] */
    return ofs;
1408 1409

fail:
1410
    return -1;
1411 1412 1413 1414 1415 1416 1417 1418 1419 1420
}

/* The maximum number of entries in a MergeState's pending-runs stack.
 * This is enough to sort arrays of size up to about
 *     32 * phi ** MAX_MERGE_PENDING
 * where phi ~= 1.618.  85 is ridiculouslylarge enough, good for an array
 * with 2**64 elements.
 */
#define MAX_MERGE_PENDING 85

1421 1422
/* When we get into galloping mode, we stay there until both runs win less
 * often than MIN_GALLOP consecutive times.  See listsort.txt for more info.
1423
 */
1424
#define MIN_GALLOP 7
1425 1426 1427 1428 1429 1430 1431

/* Avoid malloc for small temp arrays. */
#define MERGESTATE_TEMP_SIZE 256

/* One MergeState exists on the stack per invocation of mergesort.  It's just
 * a convenient way to pass state around among the helper functions.
 */
1432
struct s_slice {
1433
    sortslice base;
1434
    Py_ssize_t len;
1435 1436
};

1437
typedef struct s_MergeState {
1438 1439 1440 1441 1442 1443 1444 1445 1446
    /* This controls when we get *into* galloping mode.  It's initialized
     * to MIN_GALLOP.  merge_lo and merge_hi tend to nudge it higher for
     * random data, and lower for highly structured data.
     */
    Py_ssize_t min_gallop;

    /* 'a' is temp storage to help with merges.  It contains room for
     * alloced entries.
     */
1447
    sortslice a;        /* may point to temparray below */
1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463
    Py_ssize_t alloced;

    /* A stack of n pending runs yet to be merged.  Run #i starts at
     * address base[i] and extends for len[i] elements.  It's always
     * true (so long as the indices are in bounds) that
     *
     *     pending[i].base + pending[i].len == pending[i+1].base
     *
     * so we could cut the storage for this, but it's a minor amount,
     * and keeping all the info explicit simplifies the code.
     */
    int n;
    struct s_slice pending[MAX_MERGE_PENDING];

    /* 'a' points to this when possible, rather than muck with malloc. */
    PyObject *temparray[MERGESTATE_TEMP_SIZE];
1464 1465 1466 1467
} MergeState;

/* Conceptually a MergeState's constructor. */
static void
1468
merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc)
1469
{
1470
    assert(ms != NULL);
1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490
    if (has_keyfunc) {
        /* The temporary space for merging will need at most half the list
         * size rounded up.  Use the minimum possible space so we can use the
         * rest of temparray for other things.  In particular, if there is
         * enough extra space, listsort() will use it to store the keys.
         */
        ms->alloced = (list_size + 1) / 2;

        /* ms->alloced describes how many keys will be stored at
           ms->temparray, but we also need to store the values.  Hence,
           ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
        if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
            ms->alloced = MERGESTATE_TEMP_SIZE / 2;
        ms->a.values = &ms->temparray[ms->alloced];
    }
    else {
        ms->alloced = MERGESTATE_TEMP_SIZE;
        ms->a.values = NULL;
    }
    ms->a.keys = ms->temparray;
1491 1492
    ms->n = 0;
    ms->min_gallop = MIN_GALLOP;
1493 1494 1495 1496 1497 1498 1499 1500 1501
}

/* Free all the temp memory owned by the MergeState.  This must be called
 * when you're done with a MergeState, and may be called before then if
 * you want to free the temp memory early.
 */
static void
merge_freemem(MergeState *ms)
{
1502
    assert(ms != NULL);
1503 1504
    if (ms->a.keys != ms->temparray)
        PyMem_Free(ms->a.keys);
1505 1506 1507 1508 1509 1510
}

/* Ensure enough temp memory for 'need' array slots is available.
 * Returns 0 on success and -1 if the memory can't be gotten.
 */
static int
Martin v. Löwis's avatar
Martin v. Löwis committed
1511
merge_getmem(MergeState *ms, Py_ssize_t need)
1512
{
1513 1514
    int multiplier;

1515 1516 1517
    assert(ms != NULL);
    if (need <= ms->alloced)
        return 0;
1518 1519 1520

    multiplier = ms->a.values != NULL ? 2 : 1;

1521 1522 1523 1524
    /* Don't realloc!  That can cost cycles to copy the old data, but
     * we don't care what's in the block.
     */
    merge_freemem(ms);
1525
    if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) {
1526 1527 1528
        PyErr_NoMemory();
        return -1;
    }
1529 1530 1531
    ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need
                                          * sizeof(PyObject *));
    if (ms->a.keys != NULL) {
1532
        ms->alloced = need;
1533 1534
        if (ms->a.values != NULL)
            ms->a.values = &ms->a.keys[need];
1535 1536 1537 1538 1539 1540 1541
        return 0;
    }
    PyErr_NoMemory();
    return -1;
}
#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 :   \
                                merge_getmem(MS, NEED))
1542

1543 1544 1545 1546 1547
/* Merge the na elements starting at ssa with the nb elements starting at
 * ssb.keys = ssa.keys + na in a stable way, in-place.  na and nb must be > 0.
 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
 * should have na <= nb.  See listsort.txt for more info.  Return 0 if
 * successful, -1 if error.
1548
 */
Martin v. Löwis's avatar
Martin v. Löwis committed
1549
static Py_ssize_t
1550 1551
merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
         sortslice ssb, Py_ssize_t nb)
1552
{
1553
    Py_ssize_t k;
1554
    sortslice dest;
1555 1556 1557
    int result = -1;            /* guilty until proved innocent */
    Py_ssize_t min_gallop;

1558 1559
    assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
    assert(ssa.keys + na == ssb.keys);
1560 1561
    if (MERGE_GETMEM(ms, na) < 0)
        return -1;
1562 1563 1564
    sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
    dest = ssa;
    ssa = ms->a;
1565

1566
    sortslice_copy_incr(&dest, &ssb);
1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582
    --nb;
    if (nb == 0)
        goto Succeed;
    if (na == 1)
        goto CopyB;

    min_gallop = ms->min_gallop;
    for (;;) {
        Py_ssize_t acount = 0;          /* # of times A won in a row */
        Py_ssize_t bcount = 0;          /* # of times B won in a row */

        /* Do the straightforward thing until (if ever) one run
         * appears to win consistently.
         */
        for (;;) {
            assert(na > 1 && nb > 0);
1583
            k = ISLT(ssb.keys[0], ssa.keys[0]);
1584 1585 1586
            if (k) {
                if (k < 0)
                    goto Fail;
1587
                sortslice_copy_incr(&dest, &ssb);
1588 1589 1590 1591 1592 1593 1594 1595 1596
                ++bcount;
                acount = 0;
                --nb;
                if (nb == 0)
                    goto Succeed;
                if (bcount >= min_gallop)
                    break;
            }
            else {
1597
                sortslice_copy_incr(&dest, &ssa);
1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617
                ++acount;
                bcount = 0;
                --na;
                if (na == 1)
                    goto CopyB;
                if (acount >= min_gallop)
                    break;
            }
        }

        /* One run is winning so consistently that galloping may
         * be a huge win.  So try that, and continue galloping until
         * (if ever) neither run appears to be winning consistently
         * anymore.
         */
        ++min_gallop;
        do {
            assert(na > 1 && nb > 0);
            min_gallop -= min_gallop > 1;
            ms->min_gallop = min_gallop;
1618
            k = gallop_right(ssb.keys[0], ssa.keys, na, 0);
1619 1620 1621 1622
            acount = k;
            if (k) {
                if (k < 0)
                    goto Fail;
1623 1624 1625
                sortslice_memcpy(&dest, 0, &ssa, 0, k);
                sortslice_advance(&dest, k);
                sortslice_advance(&ssa, k);
1626 1627 1628 1629 1630 1631 1632 1633 1634 1635
                na -= k;
                if (na == 1)
                    goto CopyB;
                /* na==0 is impossible now if the comparison
                 * function is consistent, but we can't assume
                 * that it is.
                 */
                if (na == 0)
                    goto Succeed;
            }
1636
            sortslice_copy_incr(&dest, &ssb);
1637 1638 1639 1640
            --nb;
            if (nb == 0)
                goto Succeed;

1641
            k = gallop_left(ssa.keys[0], ssb.keys, nb, 0);
1642 1643 1644 1645
            bcount = k;
            if (k) {
                if (k < 0)
                    goto Fail;
1646 1647 1648
                sortslice_memmove(&dest, 0, &ssb, 0, k);
                sortslice_advance(&dest, k);
                sortslice_advance(&ssb, k);
1649 1650 1651 1652
                nb -= k;
                if (nb == 0)
                    goto Succeed;
            }
1653
            sortslice_copy_incr(&dest, &ssa);
1654 1655 1656 1657 1658 1659 1660
            --na;
            if (na == 1)
                goto CopyB;
        } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        ++min_gallop;           /* penalize it for leaving galloping mode */
        ms->min_gallop = min_gallop;
    }
1661
Succeed:
1662
    result = 0;
1663
Fail:
1664
    if (na)
1665
        sortslice_memcpy(&dest, 0, &ssa, 0, na);
1666
    return result;
1667
CopyB:
1668
    assert(na == 1 && nb > 0);
1669 1670 1671
    /* The last element of ssa belongs at the end of the merge. */
    sortslice_memmove(&dest, 0, &ssb, 0, nb);
    sortslice_copy(&dest, nb, &ssa, 0);
1672
    return 0;
1673 1674
}

1675 1676 1677 1678 1679
/* Merge the na elements starting at pa with the nb elements starting at
 * ssb.keys = ssa.keys + na in a stable way, in-place.  na and nb must be > 0.
 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
 * should have na >= nb.  See listsort.txt for more info.  Return 0 if
 * successful, -1 if error.
1680
 */
Martin v. Löwis's avatar
Martin v. Löwis committed
1681
static Py_ssize_t
1682 1683
merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
         sortslice ssb, Py_ssize_t nb)
1684
{
1685
    Py_ssize_t k;
1686
    sortslice dest, basea, baseb;
1687 1688 1689
    int result = -1;            /* guilty until proved innocent */
    Py_ssize_t min_gallop;

1690 1691
    assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
    assert(ssa.keys + na == ssb.keys);
1692 1693
    if (MERGE_GETMEM(ms, nb) < 0)
        return -1;
1694 1695 1696 1697
    dest = ssb;
    sortslice_advance(&dest, nb-1);
    sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
    basea = ssa;
1698
    baseb = ms->a;
1699 1700 1701 1702
    ssb.keys = ms->a.keys + nb - 1;
    if (ssb.values != NULL)
        ssb.values = ms->a.values + nb - 1;
    sortslice_advance(&ssa, na - 1);
1703

1704
    sortslice_copy_decr(&dest, &ssa);
1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720
    --na;
    if (na == 0)
        goto Succeed;
    if (nb == 1)
        goto CopyA;

    min_gallop = ms->min_gallop;
    for (;;) {
        Py_ssize_t acount = 0;          /* # of times A won in a row */
        Py_ssize_t bcount = 0;          /* # of times B won in a row */

        /* Do the straightforward thing until (if ever) one run
         * appears to win consistently.
         */
        for (;;) {
            assert(na > 0 && nb > 1);
1721
            k = ISLT(ssb.keys[0], ssa.keys[0]);
1722 1723 1724
            if (k) {
                if (k < 0)
                    goto Fail;
1725
                sortslice_copy_decr(&dest, &ssa);
1726 1727 1728 1729 1730 1731 1732 1733 1734
                ++acount;
                bcount = 0;
                --na;
                if (na == 0)
                    goto Succeed;
                if (acount >= min_gallop)
                    break;
            }
            else {
1735
                sortslice_copy_decr(&dest, &ssb);
1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755
                ++bcount;
                acount = 0;
                --nb;
                if (nb == 1)
                    goto CopyA;
                if (bcount >= min_gallop)
                    break;
            }
        }

        /* One run is winning so consistently that galloping may
         * be a huge win.  So try that, and continue galloping until
         * (if ever) neither run appears to be winning consistently
         * anymore.
         */
        ++min_gallop;
        do {
            assert(na > 0 && nb > 1);
            min_gallop -= min_gallop > 1;
            ms->min_gallop = min_gallop;
1756
            k = gallop_right(ssb.keys[0], basea.keys, na, na-1);
1757 1758 1759 1760 1761
            if (k < 0)
                goto Fail;
            k = na - k;
            acount = k;
            if (k) {
1762 1763 1764
                sortslice_advance(&dest, -k);
                sortslice_advance(&ssa, -k);
                sortslice_memmove(&dest, 1, &ssa, 1, k);
1765 1766 1767 1768
                na -= k;
                if (na == 0)
                    goto Succeed;
            }
1769
            sortslice_copy_decr(&dest, &ssb);
1770 1771 1772 1773
            --nb;
            if (nb == 1)
                goto CopyA;

1774
            k = gallop_left(ssa.keys[0], baseb.keys, nb, nb-1);
1775 1776 1777 1778 1779
            if (k < 0)
                goto Fail;
            k = nb - k;
            bcount = k;
            if (k) {
1780 1781 1782
                sortslice_advance(&dest, -k);
                sortslice_advance(&ssb, -k);
                sortslice_memcpy(&dest, 1, &ssb, 1, k);
1783 1784 1785 1786 1787 1788 1789 1790 1791 1792
                nb -= k;
                if (nb == 1)
                    goto CopyA;
                /* nb==0 is impossible now if the comparison
                 * function is consistent, but we can't assume
                 * that it is.
                 */
                if (nb == 0)
                    goto Succeed;
            }
1793
            sortslice_copy_decr(&dest, &ssa);
1794 1795 1796 1797 1798 1799 1800
            --na;
            if (na == 0)
                goto Succeed;
        } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        ++min_gallop;           /* penalize it for leaving galloping mode */
        ms->min_gallop = min_gallop;
    }
1801
Succeed:
1802
    result = 0;
1803
Fail:
1804
    if (nb)
1805
        sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
1806
    return result;
1807
CopyA:
1808
    assert(nb == 1 && na > 0);
1809 1810 1811 1812 1813
    /* The first element of ssb belongs at the front of the merge. */
    sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
    sortslice_advance(&dest, -na);
    sortslice_advance(&ssa, -na);
    sortslice_copy(&dest, 0, &ssb, 0);
1814
    return 0;
1815
}
1816

1817 1818 1819
/* Merge the two runs at stack indices i and i+1.
 * Returns 0 on success, -1 on error.
 */
Martin v. Löwis's avatar
Martin v. Löwis committed
1820 1821
static Py_ssize_t
merge_at(MergeState *ms, Py_ssize_t i)
1822
{
1823
    sortslice ssa, ssb;
1824 1825 1826 1827 1828 1829 1830 1831
    Py_ssize_t na, nb;
    Py_ssize_t k;

    assert(ms != NULL);
    assert(ms->n >= 2);
    assert(i >= 0);
    assert(i == ms->n - 2 || i == ms->n - 3);

1832
    ssa = ms->pending[i].base;
1833
    na = ms->pending[i].len;
1834
    ssb = ms->pending[i+1].base;
1835 1836
    nb = ms->pending[i+1].len;
    assert(na > 0 && nb > 0);
1837
    assert(ssa.keys + na == ssb.keys);
1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850

    /* Record the length of the combined runs; if i is the 3rd-last
     * run now, also slide over the last run (which isn't involved
     * in this merge).  The current run i+1 goes away in any case.
     */
    ms->pending[i].len = na + nb;
    if (i == ms->n - 3)
        ms->pending[i+1] = ms->pending[i+2];
    --ms->n;

    /* Where does b start in a?  Elements in a before that can be
     * ignored (already in place).
     */
1851
    k = gallop_right(*ssb.keys, ssa.keys, na, 0);
1852 1853
    if (k < 0)
        return -1;
1854
    sortslice_advance(&ssa, k);
1855 1856 1857 1858 1859 1860 1861
    na -= k;
    if (na == 0)
        return 0;

    /* Where does a end in b?  Elements in b after that can be
     * ignored (already in place).
     */
1862
    nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1);
1863 1864 1865 1866 1867 1868 1869
    if (nb <= 0)
        return nb;

    /* Merge what remains of the runs, using a temp array with
     * min(na, nb) elements.
     */
    if (na <= nb)
1870
        return merge_lo(ms, ssa, na, ssb, nb);
1871
    else
1872
        return merge_hi(ms, ssa, na, ssb, nb);
1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887
}

/* Examine the stack of runs waiting to be merged, merging adjacent runs
 * until the stack invariants are re-established:
 *
 * 1. len[-3] > len[-2] + len[-1]
 * 2. len[-2] > len[-1]
 *
 * See listsort.txt for more info.
 *
 * Returns 0 on success, -1 on error.
 */
static int
merge_collapse(MergeState *ms)
{
1888 1889 1890 1891 1892
    struct s_slice *p = ms->pending;

    assert(ms);
    while (ms->n > 1) {
        Py_ssize_t n = ms->n - 2;
1893 1894
        if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) ||
            (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) {
1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907
            if (p[n-1].len < p[n+1].len)
                --n;
            if (merge_at(ms, n) < 0)
                return -1;
        }
        else if (p[n].len <= p[n+1].len) {
                 if (merge_at(ms, n) < 0)
                        return -1;
        }
        else
            break;
    }
    return 0;
1908
}
1909

1910 1911 1912 1913 1914 1915 1916 1917
/* Regardless of invariants, merge all runs on the stack until only one
 * remains.  This is used at the end of the mergesort.
 *
 * Returns 0 on success, -1 on error.
 */
static int
merge_force_collapse(MergeState *ms)
{
1918
    struct s_slice *p = ms->pending;
1919

1920 1921 1922 1923 1924 1925 1926 1927 1928
    assert(ms);
    while (ms->n > 1) {
        Py_ssize_t n = ms->n - 2;
        if (n > 0 && p[n-1].len < p[n+1].len)
            --n;
        if (merge_at(ms, n) < 0)
            return -1;
    }
    return 0;
1929
}
1930

1931 1932 1933 1934 1935 1936 1937 1938 1939 1940
/* Compute a good value for the minimum run length; natural runs shorter
 * than this are boosted artificially via binary insertion.
 *
 * If n < 64, return n (it's too small to bother with fancy stuff).
 * Else if n is an exact power of 2, return 32.
 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
 * strictly less than, an exact power of 2.
 *
 * See listsort.txt for more info.
 */
Martin v. Löwis's avatar
Martin v. Löwis committed
1941 1942
static Py_ssize_t
merge_compute_minrun(Py_ssize_t n)
1943
{
1944
    Py_ssize_t r = 0;           /* becomes 1 if any 1 bits are shifted off */
1945

1946 1947 1948 1949 1950 1951
    assert(n >= 0);
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
1952
}
1953

1954
static void
1955
reverse_sortslice(sortslice *s, Py_ssize_t n)
1956
{
1957 1958 1959
    reverse_slice(s->keys, &s->keys[n]);
    if (s->values != NULL)
        reverse_slice(s->values, &s->values[n]);
1960 1961
}

1962 1963 1964 1965 1966
/* An adaptive, stable, natural mergesort.  See listsort.txt.
 * Returns Py_None on success, NULL on error.  Even in case of error, the
 * list will be some permutation of its input state (nothing is lost or
 * duplicated).
 */
1967 1968 1969 1970 1971
/*[clinic input]
list.sort

    *
    key as keyfunc: object = None
1972
    reverse: bool(accept={int}) = False
1973 1974 1975 1976

Stable sort *IN PLACE*.
[clinic start generated code]*/

1977
static PyObject *
1978
list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
1979
/*[clinic end generated code: output=57b9f9c5e23fbe42 input=b0fcf743982c5b90]*/
1980
{
1981 1982 1983
    MergeState ms;
    Py_ssize_t nremaining;
    Py_ssize_t minrun;
1984
    sortslice lo;
1985 1986 1987 1988 1989
    Py_ssize_t saved_ob_size, saved_allocated;
    PyObject **saved_ob_item;
    PyObject **final_ob_item;
    PyObject *result = NULL;            /* guilty until proved innocent */
    Py_ssize_t i;
1990
    PyObject **keys;
1991 1992

    assert(self != NULL);
1993
    assert(PyList_Check(self));
1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
    if (keyfunc == Py_None)
        keyfunc = NULL;

    /* The list is temporarily made empty, so that mutations performed
     * by comparison functions can't affect the slice of memory we're
     * sorting (allowing mutations during sorting is a core-dump
     * factory, since ob_item may change).
     */
    saved_ob_size = Py_SIZE(self);
    saved_ob_item = self->ob_item;
    saved_allocated = self->allocated;
    Py_SIZE(self) = 0;
    self->ob_item = NULL;
    self->allocated = -1; /* any operation will reset it to >= 0 */

2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019
    if (keyfunc == NULL) {
        keys = NULL;
        lo.keys = saved_ob_item;
        lo.values = NULL;
    }
    else {
        if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
            /* Leverage stack space we allocated but won't otherwise use */
            keys = &ms.temparray[saved_ob_size+1];
        else {
            keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);
2020 2021 2022 2023
            if (keys == NULL) {
                PyErr_NoMemory();
                goto keyfunc_fail;
            }
2024 2025 2026
        }

        for (i = 0; i < saved_ob_size ; i++) {
2027 2028
            keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i],
                                                   NULL);
2029 2030 2031
            if (keys[i] == NULL) {
                for (i=i-1 ; i>=0 ; i--)
                    Py_DECREF(keys[i]);
2032
                if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
2033
                    PyMem_FREE(keys);
2034
                goto keyfunc_fail;
2035 2036
            }
        }
2037 2038 2039

        lo.keys = keys;
        lo.values = saved_ob_item;
2040 2041
    }

2042
    merge_init(&ms, saved_ob_size, keys != NULL);
2043 2044 2045 2046 2047

    nremaining = saved_ob_size;
    if (nremaining < 2)
        goto succeed;

2048 2049
    /* Reverse sort stability achieved by initially reversing the list,
    applying a stable forward sort, then reversing the final result. */
2050 2051 2052 2053 2054
    if (reverse) {
        if (keys != NULL)
            reverse_slice(&keys[0], &keys[saved_ob_size]);
        reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
    }
2055

2056 2057 2058 2059 2060 2061 2062 2063 2064
    /* March over the array once, left to right, finding natural runs,
     * and extending short natural runs to minrun elements.
     */
    minrun = merge_compute_minrun(nremaining);
    do {
        int descending;
        Py_ssize_t n;

        /* Identify next run. */
2065
        n = count_run(lo.keys, lo.keys + nremaining, &descending);
2066 2067 2068
        if (n < 0)
            goto fail;
        if (descending)
2069
            reverse_sortslice(&lo, n);
2070 2071 2072 2073
        /* If short, extend to min(minrun, nremaining). */
        if (n < minrun) {
            const Py_ssize_t force = nremaining <= minrun ?
                              nremaining : minrun;
2074
            if (binarysort(lo, lo.keys + force, lo.keys + n) < 0)
2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085
                goto fail;
            n = force;
        }
        /* Push run onto pending-runs stack, and maybe merge. */
        assert(ms.n < MAX_MERGE_PENDING);
        ms.pending[ms.n].base = lo;
        ms.pending[ms.n].len = n;
        ++ms.n;
        if (merge_collapse(&ms) < 0)
            goto fail;
        /* Advance to find next run. */
2086
        sortslice_advance(&lo, n);
2087 2088 2089 2090 2091 2092
        nremaining -= n;
    } while (nremaining);

    if (merge_force_collapse(&ms) < 0)
        goto fail;
    assert(ms.n == 1);
2093 2094 2095
    assert(keys == NULL
           ? ms.pending[0].base.keys == saved_ob_item
           : ms.pending[0].base.keys == &keys[0]);
2096
    assert(ms.pending[0].len == saved_ob_size);
2097
    lo = ms.pending[0].base;
2098

2099
succeed:
2100
    result = Py_None;
2101
fail:
2102 2103 2104
    if (keys != NULL) {
        for (i = 0; i < saved_ob_size; i++)
            Py_DECREF(keys[i]);
2105
        if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
2106
            PyMem_FREE(keys);
2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120
    }

    if (self->allocated != -1 && result != NULL) {
        /* The user mucked with the list during the sort,
         * and we don't already have another error to report.
         */
        PyErr_SetString(PyExc_ValueError, "list modified during sort");
        result = NULL;
    }

    if (reverse && saved_ob_size > 1)
        reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);

    merge_freemem(&ms);
2121

2122
keyfunc_fail:
2123 2124 2125 2126 2127 2128
    final_ob_item = self->ob_item;
    i = Py_SIZE(self);
    Py_SIZE(self) = saved_ob_size;
    self->ob_item = saved_ob_item;
    self->allocated = saved_allocated;
    if (final_ob_item != NULL) {
2129
        /* we cannot use _list_clear() for this because it does not
2130 2131 2132 2133 2134 2135 2136 2137
           guarantee that the list is really empty when it returns */
        while (--i >= 0) {
            Py_XDECREF(final_ob_item[i]);
        }
        PyMem_FREE(final_ob_item);
    }
    Py_XINCREF(result);
    return result;
2138
}
2139
#undef IFLT
2140
#undef ISLT
2141

2142
int
2143
PyList_Sort(PyObject *v)
2144
{
2145 2146 2147 2148
    if (v == NULL || !PyList_Check(v)) {
        PyErr_BadInternalCall();
        return -1;
    }
2149
    v = list_sort_impl((PyListObject *)v, NULL, 0);
2150 2151 2152 2153
    if (v == NULL)
        return -1;
    Py_DECREF(v);
    return 0;
2154 2155
}

2156 2157 2158 2159 2160 2161
/*[clinic input]
list.reverse

Reverse *IN PLACE*.
[clinic start generated code]*/

2162
static PyObject *
2163 2164
list_reverse_impl(PyListObject *self)
/*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
2165
{
2166 2167 2168
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
2169 2170
}

2171
int
2172
PyList_Reverse(PyObject *v)
2173
{
2174
    PyListObject *self = (PyListObject *)v;
2175

2176 2177 2178 2179 2180 2181 2182
    if (v == NULL || !PyList_Check(v)) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    return 0;
2183 2184
}

2185
PyObject *
2186
PyList_AsTuple(PyObject *v)
2187
{
2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207
    PyObject *w;
    PyObject **p, **q;
    Py_ssize_t n;
    if (v == NULL || !PyList_Check(v)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    n = Py_SIZE(v);
    w = PyTuple_New(n);
    if (w == NULL)
        return NULL;
    p = ((PyTupleObject *)w)->ob_item;
    q = ((PyListObject *)v)->ob_item;
    while (--n >= 0) {
        Py_INCREF(*q);
        *p = *q;
        p++;
        q++;
    }
    return w;
2208 2209
}

2210 2211 2212 2213
/*[clinic input]
list.index

    value: object
2214 2215
    start: slice_index(accept={int}) = 0
    stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
2216 2217 2218 2219 2220 2221 2222
    /

Return first index of value.

Raises ValueError if the value is not present.
[clinic start generated code]*/

2223
static PyObject *
2224 2225
list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
                Py_ssize_t stop)
2226
/*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
2227
{
2228
    Py_ssize_t i;
2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240

    if (start < 0) {
        start += Py_SIZE(self);
        if (start < 0)
            start = 0;
    }
    if (stop < 0) {
        stop += Py_SIZE(self);
        if (stop < 0)
            stop = 0;
    }
    for (i = start; i < stop && i < Py_SIZE(self); i++) {
2241
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
2242 2243 2244 2245 2246
        if (cmp > 0)
            return PyLong_FromSsize_t(i);
        else if (cmp < 0)
            return NULL;
    }
2247
    PyErr_Format(PyExc_ValueError, "%R is not in list", value);
2248
    return NULL;
2249 2250
}

2251 2252 2253 2254 2255 2256 2257 2258 2259
/*[clinic input]
list.count

     value: object
     /

Return number of occurrences of value.
[clinic start generated code]*/

2260
static PyObject *
2261 2262
list_count(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
Guido van Rossum's avatar
Guido van Rossum committed
2263
{
2264 2265
    Py_ssize_t count = 0;
    Py_ssize_t i;
2266

2267
    for (i = 0; i < Py_SIZE(self); i++) {
2268
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
2269 2270 2271 2272 2273 2274
        if (cmp > 0)
            count++;
        else if (cmp < 0)
            return NULL;
    }
    return PyLong_FromSsize_t(count);
Guido van Rossum's avatar
Guido van Rossum committed
2275 2276
}

2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287
/*[clinic input]
list.remove

     value: object
     /

Remove first occurrence of value.

Raises ValueError if the value is not present.
[clinic start generated code]*/

2288
static PyObject *
2289 2290
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
2291
{
2292
    Py_ssize_t i;
2293

2294
    for (i = 0; i < Py_SIZE(self); i++) {
2295
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
2307 2308
}

2309 2310 2311
static int
list_traverse(PyListObject *o, visitproc visit, void *arg)
{
2312
    Py_ssize_t i;
2313

2314 2315 2316
    for (i = Py_SIZE(o); --i >= 0; )
        Py_VISIT(o->ob_item[i]);
    return 0;
2317 2318
}

2319 2320 2321
static PyObject *
list_richcompare(PyObject *v, PyObject *w, int op)
{
2322 2323 2324
    PyListObject *vl, *wl;
    Py_ssize_t i;

2325 2326
    if (!PyList_Check(v) || !PyList_Check(w))
        Py_RETURN_NOTIMPLEMENTED;
2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376

    vl = (PyListObject *)v;
    wl = (PyListObject *)w;

    if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
        /* Shortcut: if the lengths differ, the lists differ */
        PyObject *res;
        if (op == Py_EQ)
            res = Py_False;
        else
            res = Py_True;
        Py_INCREF(res);
        return res;
    }

    /* Search for the first index where items are different */
    for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
        int k = PyObject_RichCompareBool(vl->ob_item[i],
                                         wl->ob_item[i], Py_EQ);
        if (k < 0)
            return NULL;
        if (!k)
            break;
    }

    if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
        /* No more items to compare -- compare sizes */
        Py_ssize_t vs = Py_SIZE(vl);
        Py_ssize_t ws = Py_SIZE(wl);
        int cmp;
        PyObject *res;
        switch (op) {
        case Py_LT: cmp = vs <  ws; break;
        case Py_LE: cmp = vs <= ws; break;
        case Py_EQ: cmp = vs == ws; break;
        case Py_NE: cmp = vs != ws; break;
        case Py_GT: cmp = vs >  ws; break;
        case Py_GE: cmp = vs >= ws; break;
        default: return NULL; /* cannot happen */
        }
        if (cmp)
            res = Py_True;
        else
            res = Py_False;
        Py_INCREF(res);
        return res;
    }

    /* We have an item that differs -- shortcuts for EQ/NE */
    if (op == Py_EQ) {
2377
        Py_RETURN_FALSE;
2378 2379
    }
    if (op == Py_NE) {
2380
        Py_RETURN_TRUE;
2381 2382 2383 2384
    }

    /* Compare the final item again using the proper operator */
    return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
2385 2386
}

2387 2388
/*[clinic input]
list.__init__
2389

2390 2391 2392 2393 2394 2395 2396 2397
    iterable: object(c_default="NULL") = ()
    /

Built-in mutable sequence.

If no argument is given, the constructor creates a new empty list.
The argument must be an iterable if specified.
[clinic start generated code]*/
2398

2399 2400 2401 2402
static int
list___init___impl(PyListObject *self, PyObject *iterable)
/*[clinic end generated code: output=0f3c21379d01de48 input=b3f3fe7206af8f6b]*/
{
2403 2404 2405 2406 2407
    /* Verify list invariants established by PyType_GenericAlloc() */
    assert(0 <= Py_SIZE(self));
    assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
    assert(self->ob_item != NULL ||
           self->allocated == 0 || self->allocated == -1);
2408

2409 2410
    /* Empty previous contents */
    if (self->ob_item != NULL) {
2411
        (void)_list_clear(self);
2412
    }
2413 2414
    if (iterable != NULL) {
        PyObject *rv = list_extend(self, iterable);
2415 2416 2417 2418 2419
        if (rv == NULL)
            return -1;
        Py_DECREF(rv);
    }
    return 0;
2420 2421
}

2422 2423 2424 2425 2426 2427
/*[clinic input]
list.__sizeof__

Return the size of the list in memory, in bytes.
[clinic start generated code]*/

2428
static PyObject *
2429 2430
list___sizeof___impl(PyListObject *self)
/*[clinic end generated code: output=3417541f95f9a53e input=b8030a5d5ce8a187]*/
2431
{
2432
    Py_ssize_t res;
2433

2434
    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
2435
    return PyLong_FromSsize_t(res);
2436 2437
}

2438
static PyObject *list_iter(PyObject *seq);
2439 2440
static PyObject *list_subscript(PyListObject*, PyObject*);

2441
static PyMethodDef list_methods[] = {
2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455
    {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, "x.__getitem__(y) <==> x[y]"},
    LIST___REVERSED___METHODDEF
    LIST___SIZEOF___METHODDEF
    LIST_CLEAR_METHODDEF
    LIST_COPY_METHODDEF
    LIST_APPEND_METHODDEF
    LIST_INSERT_METHODDEF
    LIST_EXTEND_METHODDEF
    LIST_POP_METHODDEF
    LIST_REMOVE_METHODDEF
    LIST_INDEX_METHODDEF
    LIST_COUNT_METHODDEF
    LIST_REVERSE_METHODDEF
    LIST_SORT_METHODDEF
2456
    {NULL,              NULL}           /* sentinel */
Guido van Rossum's avatar
Guido van Rossum committed
2457 2458
};

2459
static PySequenceMethods list_as_sequence = {
2460 2461 2462 2463 2464 2465 2466 2467 2468 2469
    (lenfunc)list_length,                       /* sq_length */
    (binaryfunc)list_concat,                    /* sq_concat */
    (ssizeargfunc)list_repeat,                  /* sq_repeat */
    (ssizeargfunc)list_item,                    /* sq_item */
    0,                                          /* sq_slice */
    (ssizeobjargproc)list_ass_item,             /* sq_ass_item */
    0,                                          /* sq_ass_slice */
    (objobjproc)list_contains,                  /* sq_contains */
    (binaryfunc)list_inplace_concat,            /* sq_inplace_concat */
    (ssizeargfunc)list_inplace_repeat,          /* sq_inplace_repeat */
Guido van Rossum's avatar
Guido van Rossum committed
2470 2471
};

2472
static PyObject *
2473 2474
list_subscript(PyListObject* self, PyObject* item)
{
2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489
    if (PyIndex_Check(item)) {
        Py_ssize_t i;
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return NULL;
        if (i < 0)
            i += PyList_GET_SIZE(self);
        return list_item(self, i);
    }
    else if (PySlice_Check(item)) {
        Py_ssize_t start, stop, step, slicelength, cur, i;
        PyObject* result;
        PyObject* it;
        PyObject **src, **dest;

2490
        if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2491 2492
            return NULL;
        }
2493 2494
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
                                            step);
2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508

        if (slicelength <= 0) {
            return PyList_New(0);
        }
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        else {
            result = PyList_New(slicelength);
            if (!result) return NULL;

            src = self->ob_item;
            dest = ((PyListObject *)result)->ob_item;
            for (cur = start, i = 0; i < slicelength;
2509
                 cur += (size_t)step, i++) {
2510 2511 2512 2513 2514 2515 2516 2517 2518 2519
                it = src[cur];
                Py_INCREF(it);
                dest[i] = it;
            }

            return result;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
2520
                     "list indices must be integers or slices, not %.200s",
2521 2522 2523
                     item->ob_type->tp_name);
        return NULL;
    }
2524 2525
}

2526
static int
2527 2528
list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
{
2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539
    if (PyIndex_Check(item)) {
        Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return -1;
        if (i < 0)
            i += PyList_GET_SIZE(self);
        return list_ass_item(self, i, value);
    }
    else if (PySlice_Check(item)) {
        Py_ssize_t start, stop, step, slicelength;

2540
        if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2541 2542
            return -1;
        }
2543 2544
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
                                            step);
2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559

        if (step == 1)
            return list_ass_slice(self, start, stop, value);

        /* Make sure s[5:2] = [..] inserts at the right place:
           before 5, not before 2. */
        if ((step < 0 && start < stop) ||
            (step > 0 && start > stop))
            stop = start;

        if (value == NULL) {
            /* delete slice */
            PyObject **garbage;
            size_t cur;
            Py_ssize_t i;
2560
            int res;
2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598

            if (slicelength <= 0)
                return 0;

            if (step < 0) {
                stop = start + 1;
                start = stop + step*(slicelength - 1) - 1;
                step = -step;
            }

            garbage = (PyObject**)
                PyMem_MALLOC(slicelength*sizeof(PyObject*));
            if (!garbage) {
                PyErr_NoMemory();
                return -1;
            }

            /* drawing pictures might help understand these for
               loops. Basically, we memmove the parts of the
               list that are *not* part of the slice: step-1
               items for each item that is part of the slice,
               and then tail end of the list that was not
               covered by the slice */
            for (cur = start, i = 0;
                 cur < (size_t)stop;
                 cur += step, i++) {
                Py_ssize_t lim = step - 1;

                garbage[i] = PyList_GET_ITEM(self, cur);

                if (cur + step >= (size_t)Py_SIZE(self)) {
                    lim = Py_SIZE(self) - cur - 1;
                }

                memmove(self->ob_item + cur - i,
                    self->ob_item + cur + 1,
                    lim * sizeof(PyObject *));
            }
2599
            cur = start + (size_t)slicelength * step;
2600 2601 2602 2603 2604 2605 2606 2607
            if (cur < (size_t)Py_SIZE(self)) {
                memmove(self->ob_item + cur - slicelength,
                    self->ob_item + cur,
                    (Py_SIZE(self) - cur) *
                     sizeof(PyObject *));
            }

            Py_SIZE(self) -= slicelength;
2608
            res = list_resize(self, Py_SIZE(self));
2609 2610 2611 2612 2613 2614

            for (i = 0; i < slicelength; i++) {
                Py_DECREF(garbage[i]);
            }
            PyMem_FREE(garbage);

2615
            return res;
2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662
        }
        else {
            /* assign slice */
            PyObject *ins, *seq;
            PyObject **garbage, **seqitems, **selfitems;
            Py_ssize_t cur, i;

            /* protect against a[::-1] = a */
            if (self == (PyListObject*)value) {
                seq = list_slice((PyListObject*)value, 0,
                                   PyList_GET_SIZE(value));
            }
            else {
                seq = PySequence_Fast(value,
                                      "must assign iterable "
                                      "to extended slice");
            }
            if (!seq)
                return -1;

            if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
                PyErr_Format(PyExc_ValueError,
                    "attempt to assign sequence of "
                    "size %zd to extended slice of "
                    "size %zd",
                         PySequence_Fast_GET_SIZE(seq),
                         slicelength);
                Py_DECREF(seq);
                return -1;
            }

            if (!slicelength) {
                Py_DECREF(seq);
                return 0;
            }

            garbage = (PyObject**)
                PyMem_MALLOC(slicelength*sizeof(PyObject*));
            if (!garbage) {
                Py_DECREF(seq);
                PyErr_NoMemory();
                return -1;
            }

            selfitems = self->ob_item;
            seqitems = PySequence_Fast_ITEMS(seq);
            for (cur = start, i = 0; i < slicelength;
2663
                 cur += (size_t)step, i++) {
2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681
                garbage[i] = selfitems[cur];
                ins = seqitems[i];
                Py_INCREF(ins);
                selfitems[cur] = ins;
            }

            for (i = 0; i < slicelength; i++) {
                Py_DECREF(garbage[i]);
            }

            PyMem_FREE(garbage);
            Py_DECREF(seq);

            return 0;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
2682
                     "list indices must be integers or slices, not %.200s",
2683 2684 2685
                     item->ob_type->tp_name);
        return -1;
    }
2686 2687 2688
}

static PyMappingMethods list_as_mapping = {
2689 2690 2691
    (lenfunc)list_length,
    (binaryfunc)list_subscript,
    (objobjargproc)list_ass_subscript
2692 2693
};

2694
PyTypeObject PyList_Type = {
2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    sizeof(PyListObject),
    0,
    (destructor)list_dealloc,                   /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    (reprfunc)list_repr,                        /* tp_repr */
    0,                                          /* tp_as_number */
    &list_as_sequence,                          /* tp_as_sequence */
    &list_as_mapping,                           /* tp_as_mapping */
2708
    PyObject_HashNotImplemented,                /* tp_hash */
2709 2710 2711 2712 2713 2714
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2715 2716
        Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
    list___init____doc__,                       /* tp_doc */
2717
    (traverseproc)list_traverse,                /* tp_traverse */
2718
    (inquiry)_list_clear,                       /* tp_clear */
2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730
    list_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    list_iter,                                  /* tp_iter */
    0,                                          /* tp_iternext */
    list_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    0,                                          /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
2731
    (initproc)list___init__,                    /* tp_init */
2732 2733 2734
    PyType_GenericAlloc,                        /* tp_alloc */
    PyType_GenericNew,                          /* tp_new */
    PyObject_GC_Del,                            /* tp_free */
Guido van Rossum's avatar
Guido van Rossum committed
2735
};
2736

2737 2738 2739
/*********************** List Iterator **************************/

typedef struct {
2740
    PyObject_HEAD
2741
    Py_ssize_t it_index;
2742
    PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
2743 2744
} listiterobject;

2745 2746 2747 2748
static void listiter_dealloc(listiterobject *);
static int listiter_traverse(listiterobject *, visitproc, void *);
static PyObject *listiter_next(listiterobject *);
static PyObject *listiter_len(listiterobject *);
2749 2750 2751
static PyObject *listiter_reduce_general(void *_it, int forward);
static PyObject *listiter_reduce(listiterobject *);
static PyObject *listiter_setstate(listiterobject *, PyObject *state);
2752 2753

PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
2754 2755
PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
2756 2757

static PyMethodDef listiter_methods[] = {
2758
    {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
2759 2760
    {"__reduce__", (PyCFunction)listiter_reduce, METH_NOARGS, reduce_doc},
    {"__setstate__", (PyCFunction)listiter_setstate, METH_O, setstate_doc},
2761
    {NULL,              NULL}           /* sentinel */
2762 2763 2764
};

PyTypeObject PyListIter_Type = {
2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list_iterator",                            /* tp_name */
    sizeof(listiterobject),                     /* tp_basicsize */
    0,                                          /* tp_itemsize */
    /* methods */
    (destructor)listiter_dealloc,               /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    0,                                          /* tp_repr */
    0,                                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    0,                                          /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
    0,                                          /* tp_doc */
    (traverseproc)listiter_traverse,            /* tp_traverse */
    0,                                          /* tp_clear */
    0,                                          /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    PyObject_SelfIter,                          /* tp_iter */
    (iternextfunc)listiter_next,                /* tp_iternext */
    listiter_methods,                           /* tp_methods */
    0,                                          /* tp_members */
2795 2796
};

2797

2798
static PyObject *
2799 2800
list_iter(PyObject *seq)
{
2801
    listiterobject *it;
2802

2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814
    if (!PyList_Check(seq)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    it = PyObject_GC_New(listiterobject, &PyListIter_Type);
    if (it == NULL)
        return NULL;
    it->it_index = 0;
    Py_INCREF(seq);
    it->it_seq = (PyListObject *)seq;
    _PyObject_GC_TRACK(it);
    return (PyObject *)it;
2815 2816 2817 2818 2819
}

static void
listiter_dealloc(listiterobject *it)
{
2820 2821 2822
    _PyObject_GC_UNTRACK(it);
    Py_XDECREF(it->it_seq);
    PyObject_GC_Del(it);
2823 2824 2825 2826 2827
}

static int
listiter_traverse(listiterobject *it, visitproc visit, void *arg)
{
2828 2829
    Py_VISIT(it->it_seq);
    return 0;
2830 2831 2832
}

static PyObject *
2833
listiter_next(listiterobject *it)
2834
{
2835 2836
    PyListObject *seq;
    PyObject *item;
2837

2838 2839 2840 2841 2842
    assert(it != NULL);
    seq = it->it_seq;
    if (seq == NULL)
        return NULL;
    assert(PyList_Check(seq));
2843

2844 2845 2846 2847 2848 2849
    if (it->it_index < PyList_GET_SIZE(seq)) {
        item = PyList_GET_ITEM(seq, it->it_index);
        ++it->it_index;
        Py_INCREF(item);
        return item;
    }
2850

2851
    it->it_seq = NULL;
2852
    Py_DECREF(seq);
2853
    return NULL;
2854 2855
}

2856
static PyObject *
2857 2858
listiter_len(listiterobject *it)
{
2859 2860 2861 2862 2863 2864 2865
    Py_ssize_t len;
    if (it->it_seq) {
        len = PyList_GET_SIZE(it->it_seq) - it->it_index;
        if (len >= 0)
            return PyLong_FromSsize_t(len);
    }
    return PyLong_FromLong(0);
2866
}
2867 2868 2869 2870 2871 2872 2873 2874 2875 2876

static PyObject *
listiter_reduce(listiterobject *it)
{
    return listiter_reduce_general(it, 1);
}

static PyObject *
listiter_setstate(listiterobject *it, PyObject *state)
{
2877
    Py_ssize_t index = PyLong_AsSsize_t(state);
2878 2879 2880 2881 2882
    if (index == -1 && PyErr_Occurred())
        return NULL;
    if (it->it_seq != NULL) {
        if (index < 0)
            index = 0;
2883 2884
        else if (index > PyList_GET_SIZE(it->it_seq))
            index = PyList_GET_SIZE(it->it_seq); /* iterator exhausted */
2885 2886 2887 2888 2889
        it->it_index = index;
    }
    Py_RETURN_NONE;
}

2890
/*********************** List Reverse Iterator **************************/
2891

2892
typedef struct {
2893 2894 2895
    PyObject_HEAD
    Py_ssize_t it_index;
    PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
2896
} listreviterobject;
2897

2898 2899 2900
static void listreviter_dealloc(listreviterobject *);
static int listreviter_traverse(listreviterobject *, visitproc, void *);
static PyObject *listreviter_next(listreviterobject *);
2901
static PyObject *listreviter_len(listreviterobject *);
2902 2903
static PyObject *listreviter_reduce(listreviterobject *);
static PyObject *listreviter_setstate(listreviterobject *, PyObject *);
2904

2905
static PyMethodDef listreviter_methods[] = {
2906
    {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
2907 2908
    {"__reduce__", (PyCFunction)listreviter_reduce, METH_NOARGS, reduce_doc},
    {"__setstate__", (PyCFunction)listreviter_setstate, METH_O, setstate_doc},
2909
    {NULL,              NULL}           /* sentinel */
2910 2911
};

2912
PyTypeObject PyListRevIter_Type = {
2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list_reverseiterator",                     /* tp_name */
    sizeof(listreviterobject),                  /* tp_basicsize */
    0,                                          /* tp_itemsize */
    /* methods */
    (destructor)listreviter_dealloc,            /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    0,                                          /* tp_repr */
    0,                                          /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    0,                                          /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
    0,                                          /* tp_doc */
    (traverseproc)listreviter_traverse,         /* tp_traverse */
    0,                                          /* tp_clear */
    0,                                          /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    PyObject_SelfIter,                          /* tp_iter */
    (iternextfunc)listreviter_next,             /* tp_iternext */
    listreviter_methods,                /* tp_methods */
    0,
2943
};
2944

2945 2946 2947 2948 2949 2950
/*[clinic input]
list.__reversed__

Return a reverse iterator over the list.
[clinic start generated code]*/

2951
static PyObject *
2952 2953
list___reversed___impl(PyListObject *self)
/*[clinic end generated code: output=b166f073208c888c input=eadb6e17f8a6a280]*/
2954
{
2955
    listreviterobject *it;
2956

2957 2958 2959
    it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
    if (it == NULL)
        return NULL;
2960 2961 2962 2963
    assert(PyList_Check(self));
    it->it_index = PyList_GET_SIZE(self) - 1;
    Py_INCREF(self);
    it->it_seq = self;
2964 2965
    PyObject_GC_Track(it);
    return (PyObject *)it;
2966 2967 2968 2969 2970
}

static void
listreviter_dealloc(listreviterobject *it)
{
2971 2972 2973
    PyObject_GC_UnTrack(it);
    Py_XDECREF(it->it_seq);
    PyObject_GC_Del(it);
2974 2975 2976 2977 2978
}

static int
listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
{
2979 2980
    Py_VISIT(it->it_seq);
    return 0;
2981 2982 2983 2984 2985
}

static PyObject *
listreviter_next(listreviterobject *it)
{
2986
    PyObject *item;
2987 2988 2989 2990 2991 2992 2993 2994 2995
    Py_ssize_t index;
    PyListObject *seq;

    assert(it != NULL);
    seq = it->it_seq;
    if (seq == NULL) {
        return NULL;
    }
    assert(PyList_Check(seq));
2996

2997
    index = it->it_index;
2998 2999 3000 3001 3002 3003 3004
    if (index>=0 && index < PyList_GET_SIZE(seq)) {
        item = PyList_GET_ITEM(seq, index);
        it->it_index--;
        Py_INCREF(item);
        return item;
    }
    it->it_index = -1;
3005 3006
    it->it_seq = NULL;
    Py_DECREF(seq);
3007
    return NULL;
3008 3009
}

3010
static PyObject *
3011 3012
listreviter_len(listreviterobject *it)
{
3013 3014 3015 3016
    Py_ssize_t len = it->it_index + 1;
    if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
        len = 0;
    return PyLong_FromSsize_t(len);
3017
}
3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051

static PyObject *
listreviter_reduce(listreviterobject *it)
{
    return listiter_reduce_general(it, 0);
}

static PyObject *
listreviter_setstate(listreviterobject *it, PyObject *state)
{
    Py_ssize_t index = PyLong_AsSsize_t(state);
    if (index == -1 && PyErr_Occurred())
        return NULL;
    if (it->it_seq != NULL) {
        if (index < -1)
            index = -1;
        else if (index > PyList_GET_SIZE(it->it_seq) - 1)
            index = PyList_GET_SIZE(it->it_seq) - 1;
        it->it_index = index;
    }
    Py_RETURN_NONE;
}

/* common pickling support */

static PyObject *
listiter_reduce_general(void *_it, int forward)
{
    PyObject *list;

    /* the objects are not the same, index is of different types! */
    if (forward) {
        listiterobject *it = (listiterobject *)_it;
        if (it->it_seq)
3052
            return Py_BuildValue("N(O)n", _PyObject_GetBuiltin("iter"),
3053 3054 3055 3056
                                 it->it_seq, it->it_index);
    } else {
        listreviterobject *it = (listreviterobject *)_it;
        if (it->it_seq)
3057
            return Py_BuildValue("N(O)n", _PyObject_GetBuiltin("reversed"),
3058 3059 3060 3061 3062 3063
                                 it->it_seq, it->it_index);
    }
    /* empty iterator, create an empty list */
    list = PyList_New(0);
    if (list == NULL)
        return NULL;
3064
    return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
3065
}