1/* List object implementation */
2
3#include "Python.h"
4#include "pycore_abstract.h" // _PyIndex_Check()
5#include "pycore_interp.h" // PyInterpreterState.list
6#include "pycore_object.h" // _PyObject_GC_TRACK()
7#include "pycore_tuple.h" // _PyTuple_FromArray()
8
9#ifdef STDC_HEADERS
10#include <stddef.h>
11#else
12#include <sys/types.h> /* For size_t */
13#endif
14
15/*[clinic input]
16class list "PyListObject *" "&PyList_Type"
17[clinic start generated code]*/
18/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/
19
20#include "clinic/listobject.c.h"
21
22
23static struct _Py_list_state *
24get_list_state(void)
25{
26 PyInterpreterState *interp = _PyInterpreterState_GET();
27 return &interp->list;
28}
29
30
31/* Ensure ob_item has room for at least newsize elements, and set
32 * ob_size to newsize. If newsize > ob_size on entry, the content
33 * of the new slots at exit is undefined heap trash; it's the caller's
34 * responsibility to overwrite them with sane values.
35 * The number of allocated elements may grow, shrink, or stay the same.
36 * Failure is impossible if newsize <= self.allocated on entry, although
37 * that partly relies on an assumption that the system realloc() never
38 * fails when passed a number of bytes <= the number of bytes last
39 * allocated (the C standard doesn't guarantee this, but it's hard to
40 * imagine a realloc implementation where it wouldn't be true).
41 * Note that self->ob_item may change, and even if newsize is less
42 * than ob_size on entry.
43 */
44static int
45list_resize(PyListObject *self, Py_ssize_t newsize)
46{
47 PyObject **items;
48 size_t new_allocated, num_allocated_bytes;
49 Py_ssize_t allocated = self->allocated;
50
51 /* Bypass realloc() when a previous overallocation is large enough
52 to accommodate the newsize. If the newsize falls lower than half
53 the allocated size, then proceed with the realloc() to shrink the list.
54 */
55 if (allocated >= newsize && newsize >= (allocated >> 1)) {
56 assert(self->ob_item != NULL || newsize == 0);
57 Py_SET_SIZE(self, newsize);
58 return 0;
59 }
60
61 /* This over-allocates proportional to the list size, making room
62 * for additional growth. The over-allocation is mild, but is
63 * enough to give linear-time amortized behavior over a long
64 * sequence of appends() in the presence of a poorly-performing
65 * system realloc().
66 * Add padding to make the allocated size multiple of 4.
67 * The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
68 * Note: new_allocated won't overflow because the largest possible value
69 * is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
70 */
71 new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
72 /* Do not overallocate if the new size is closer to overallocated size
73 * than to the old size.
74 */
75 if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
76 new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
77
78 if (newsize == 0)
79 new_allocated = 0;
80 num_allocated_bytes = new_allocated * sizeof(PyObject *);
81 items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
82 if (items == NULL) {
83 PyErr_NoMemory();
84 return -1;
85 }
86 self->ob_item = items;
87 Py_SET_SIZE(self, newsize);
88 self->allocated = new_allocated;
89 return 0;
90}
91
92static int
93list_preallocate_exact(PyListObject *self, Py_ssize_t size)
94{
95 assert(self->ob_item == NULL);
96 assert(size > 0);
97
98 PyObject **items = PyMem_New(PyObject*, size);
99 if (items == NULL) {
100 PyErr_NoMemory();
101 return -1;
102 }
103 self->ob_item = items;
104 self->allocated = size;
105 return 0;
106}
107
108void
109_PyList_ClearFreeList(PyInterpreterState *interp)
110{
111 struct _Py_list_state *state = &interp->list;
112 while (state->numfree) {
113 PyListObject *op = state->free_list[--state->numfree];
114 assert(PyList_CheckExact(op));
115 PyObject_GC_Del(op);
116 }
117}
118
119void
120_PyList_Fini(PyInterpreterState *interp)
121{
122 _PyList_ClearFreeList(interp);
123#ifdef Py_DEBUG
124 struct _Py_list_state *state = &interp->list;
125 state->numfree = -1;
126#endif
127}
128
129/* Print summary info about the state of the optimized allocator */
130void
131_PyList_DebugMallocStats(FILE *out)
132{
133 struct _Py_list_state *state = get_list_state();
134 _PyDebugAllocatorStats(out,
135 "free PyListObject",
136 state->numfree, sizeof(PyListObject));
137}
138
139PyObject *
140PyList_New(Py_ssize_t size)
141{
142 if (size < 0) {
143 PyErr_BadInternalCall();
144 return NULL;
145 }
146
147 struct _Py_list_state *state = get_list_state();
148 PyListObject *op;
149#ifdef Py_DEBUG
150 // PyList_New() must not be called after _PyList_Fini()
151 assert(state->numfree != -1);
152#endif
153 if (state->numfree) {
154 state->numfree--;
155 op = state->free_list[state->numfree];
156 _Py_NewReference((PyObject *)op);
157 }
158 else {
159 op = PyObject_GC_New(PyListObject, &PyList_Type);
160 if (op == NULL) {
161 return NULL;
162 }
163 }
164 if (size <= 0) {
165 op->ob_item = NULL;
166 }
167 else {
168 op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
169 if (op->ob_item == NULL) {
170 Py_DECREF(op);
171 return PyErr_NoMemory();
172 }
173 }
174 Py_SET_SIZE(op, size);
175 op->allocated = size;
176 _PyObject_GC_TRACK(op);
177 return (PyObject *) op;
178}
179
180static PyObject *
181list_new_prealloc(Py_ssize_t size)
182{
183 assert(size > 0);
184 PyListObject *op = (PyListObject *) PyList_New(0);
185 if (op == NULL) {
186 return NULL;
187 }
188 assert(op->ob_item == NULL);
189 op->ob_item = PyMem_New(PyObject *, size);
190 if (op->ob_item == NULL) {
191 Py_DECREF(op);
192 return PyErr_NoMemory();
193 }
194 op->allocated = size;
195 return (PyObject *) op;
196}
197
198Py_ssize_t
199PyList_Size(PyObject *op)
200{
201 if (!PyList_Check(op)) {
202 PyErr_BadInternalCall();
203 return -1;
204 }
205 else
206 return Py_SIZE(op);
207}
208
209static inline int
210valid_index(Py_ssize_t i, Py_ssize_t limit)
211{
212 /* The cast to size_t lets us use just a single comparison
213 to check whether i is in the range: 0 <= i < limit.
214
215 See: Section 14.2 "Bounds Checking" in the Agner Fog
216 optimization manual found at:
217 https://www.agner.org/optimize/optimizing_cpp.pdf
218 */
219 return (size_t) i < (size_t) limit;
220}
221
222static PyObject *indexerr = NULL;
223
224PyObject *
225PyList_GetItem(PyObject *op, Py_ssize_t i)
226{
227 if (!PyList_Check(op)) {
228 PyErr_BadInternalCall();
229 return NULL;
230 }
231 if (!valid_index(i, Py_SIZE(op))) {
232 if (indexerr == NULL) {
233 indexerr = PyUnicode_FromString(
234 "list index out of range");
235 if (indexerr == NULL)
236 return NULL;
237 }
238 PyErr_SetObject(PyExc_IndexError, indexerr);
239 return NULL;
240 }
241 return ((PyListObject *)op) -> ob_item[i];
242}
243
244int
245PyList_SetItem(PyObject *op, Py_ssize_t i,
246 PyObject *newitem)
247{
248 PyObject **p;
249 if (!PyList_Check(op)) {
250 Py_XDECREF(newitem);
251 PyErr_BadInternalCall();
252 return -1;
253 }
254 if (!valid_index(i, Py_SIZE(op))) {
255 Py_XDECREF(newitem);
256 PyErr_SetString(PyExc_IndexError,
257 "list assignment index out of range");
258 return -1;
259 }
260 p = ((PyListObject *)op) -> ob_item + i;
261 Py_XSETREF(*p, newitem);
262 return 0;
263}
264
265static int
266ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
267{
268 Py_ssize_t i, n = Py_SIZE(self);
269 PyObject **items;
270 if (v == NULL) {
271 PyErr_BadInternalCall();
272 return -1;
273 }
274
275 assert((size_t)n + 1 < PY_SSIZE_T_MAX);
276 if (list_resize(self, n+1) < 0)
277 return -1;
278
279 if (where < 0) {
280 where += n;
281 if (where < 0)
282 where = 0;
283 }
284 if (where > n)
285 where = n;
286 items = self->ob_item;
287 for (i = n; --i >= where; )
288 items[i+1] = items[i];
289 Py_INCREF(v);
290 items[where] = v;
291 return 0;
292}
293
294int
295PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
296{
297 if (!PyList_Check(op)) {
298 PyErr_BadInternalCall();
299 return -1;
300 }
301 return ins1((PyListObject *)op, where, newitem);
302}
303
304static int
305app1(PyListObject *self, PyObject *v)
306{
307 Py_ssize_t n = PyList_GET_SIZE(self);
308
309 assert (v != NULL);
310 assert((size_t)n + 1 < PY_SSIZE_T_MAX);
311 if (list_resize(self, n+1) < 0)
312 return -1;
313
314 Py_INCREF(v);
315 PyList_SET_ITEM(self, n, v);
316 return 0;
317}
318
319int
320PyList_Append(PyObject *op, PyObject *newitem)
321{
322 if (PyList_Check(op) && (newitem != NULL))
323 return app1((PyListObject *)op, newitem);
324 PyErr_BadInternalCall();
325 return -1;
326}
327
328/* Methods */
329
330static void
331list_dealloc(PyListObject *op)
332{
333 Py_ssize_t i;
334 PyObject_GC_UnTrack(op);
335 Py_TRASHCAN_BEGIN(op, list_dealloc)
336 if (op->ob_item != NULL) {
337 /* Do it backwards, for Christian Tismer.
338 There's a simple test case where somehow this reduces
339 thrashing when a *very* large list is created and
340 immediately deleted. */
341 i = Py_SIZE(op);
342 while (--i >= 0) {
343 Py_XDECREF(op->ob_item[i]);
344 }
345 PyMem_Free(op->ob_item);
346 }
347 struct _Py_list_state *state = get_list_state();
348#ifdef Py_DEBUG
349 // list_dealloc() must not be called after _PyList_Fini()
350 assert(state->numfree != -1);
351#endif
352 if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {
353 state->free_list[state->numfree++] = op;
354 }
355 else {
356 Py_TYPE(op)->tp_free((PyObject *)op);
357 }
358 Py_TRASHCAN_END
359}
360
361static PyObject *
362list_repr(PyListObject *v)
363{
364 Py_ssize_t i;
365 PyObject *s;
366 _PyUnicodeWriter writer;
367
368 if (Py_SIZE(v) == 0) {
369 return PyUnicode_FromString("[]");
370 }
371
372 i = Py_ReprEnter((PyObject*)v);
373 if (i != 0) {
374 return i > 0 ? PyUnicode_FromString("[...]") : NULL;
375 }
376
377 _PyUnicodeWriter_Init(&writer);
378 writer.overallocate = 1;
379 /* "[" + "1" + ", 2" * (len - 1) + "]" */
380 writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
381
382 if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)
383 goto error;
384
385 /* Do repr() on each element. Note that this may mutate the list,
386 so must refetch the list size on each iteration. */
387 for (i = 0; i < Py_SIZE(v); ++i) {
388 if (i > 0) {
389 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
390 goto error;
391 }
392
393 s = PyObject_Repr(v->ob_item[i]);
394 if (s == NULL)
395 goto error;
396
397 if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
398 Py_DECREF(s);
399 goto error;
400 }
401 Py_DECREF(s);
402 }
403
404 writer.overallocate = 0;
405 if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
406 goto error;
407
408 Py_ReprLeave((PyObject *)v);
409 return _PyUnicodeWriter_Finish(&writer);
410
411error:
412 _PyUnicodeWriter_Dealloc(&writer);
413 Py_ReprLeave((PyObject *)v);
414 return NULL;
415}
416
417static Py_ssize_t
418list_length(PyListObject *a)
419{
420 return Py_SIZE(a);
421}
422
423static int
424list_contains(PyListObject *a, PyObject *el)
425{
426 PyObject *item;
427 Py_ssize_t i;
428 int cmp;
429
430 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
431 item = PyList_GET_ITEM(a, i);
432 Py_INCREF(item);
433 cmp = PyObject_RichCompareBool(item, el, Py_EQ);
434 Py_DECREF(item);
435 }
436 return cmp;
437}
438
439static PyObject *
440list_item(PyListObject *a, Py_ssize_t i)
441{
442 if (!valid_index(i, Py_SIZE(a))) {
443 if (indexerr == NULL) {
444 indexerr = PyUnicode_FromString(
445 "list index out of range");
446 if (indexerr == NULL)
447 return NULL;
448 }
449 PyErr_SetObject(PyExc_IndexError, indexerr);
450 return NULL;
451 }
452 Py_INCREF(a->ob_item[i]);
453 return a->ob_item[i];
454}
455
456static PyObject *
457list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
458{
459 PyListObject *np;
460 PyObject **src, **dest;
461 Py_ssize_t i, len;
462 len = ihigh - ilow;
463 if (len <= 0) {
464 return PyList_New(0);
465 }
466 np = (PyListObject *) list_new_prealloc(len);
467 if (np == NULL)
468 return NULL;
469
470 src = a->ob_item + ilow;
471 dest = np->ob_item;
472 for (i = 0; i < len; i++) {
473 PyObject *v = src[i];
474 Py_INCREF(v);
475 dest[i] = v;
476 }
477 Py_SET_SIZE(np, len);
478 return (PyObject *)np;
479}
480
481PyObject *
482PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
483{
484 if (!PyList_Check(a)) {
485 PyErr_BadInternalCall();
486 return NULL;
487 }
488 if (ilow < 0) {
489 ilow = 0;
490 }
491 else if (ilow > Py_SIZE(a)) {
492 ilow = Py_SIZE(a);
493 }
494 if (ihigh < ilow) {
495 ihigh = ilow;
496 }
497 else if (ihigh > Py_SIZE(a)) {
498 ihigh = Py_SIZE(a);
499 }
500 return list_slice((PyListObject *)a, ilow, ihigh);
501}
502
503static PyObject *
504list_concat(PyListObject *a, PyObject *bb)
505{
506 Py_ssize_t size;
507 Py_ssize_t i;
508 PyObject **src, **dest;
509 PyListObject *np;
510 if (!PyList_Check(bb)) {
511 PyErr_Format(PyExc_TypeError,
512 "can only concatenate list (not \"%.200s\") to list",
513 Py_TYPE(bb)->tp_name);
514 return NULL;
515 }
516#define b ((PyListObject *)bb)
517 assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
518 size = Py_SIZE(a) + Py_SIZE(b);
519 if (size == 0) {
520 return PyList_New(0);
521 }
522 np = (PyListObject *) list_new_prealloc(size);
523 if (np == NULL) {
524 return NULL;
525 }
526 src = a->ob_item;
527 dest = np->ob_item;
528 for (i = 0; i < Py_SIZE(a); i++) {
529 PyObject *v = src[i];
530 Py_INCREF(v);
531 dest[i] = v;
532 }
533 src = b->ob_item;
534 dest = np->ob_item + Py_SIZE(a);
535 for (i = 0; i < Py_SIZE(b); i++) {
536 PyObject *v = src[i];
537 Py_INCREF(v);
538 dest[i] = v;
539 }
540 Py_SET_SIZE(np, size);
541 return (PyObject *)np;
542#undef b
543}
544
545static PyObject *
546list_repeat(PyListObject *a, Py_ssize_t n)
547{
548 Py_ssize_t i, j;
549 Py_ssize_t size;
550 PyListObject *np;
551 PyObject **p, **items;
552 PyObject *elem;
553 if (n < 0)
554 n = 0;
555 if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
556 return PyErr_NoMemory();
557 size = Py_SIZE(a) * n;
558 if (size == 0)
559 return PyList_New(0);
560 np = (PyListObject *) list_new_prealloc(size);
561 if (np == NULL)
562 return NULL;
563
564 if (Py_SIZE(a) == 1) {
565 items = np->ob_item;
566 elem = a->ob_item[0];
567 for (i = 0; i < n; i++) {
568 items[i] = elem;
569 Py_INCREF(elem);
570 }
571 }
572 else {
573 p = np->ob_item;
574 items = a->ob_item;
575 for (i = 0; i < n; i++) {
576 for (j = 0; j < Py_SIZE(a); j++) {
577 *p = items[j];
578 Py_INCREF(*p);
579 p++;
580 }
581 }
582 }
583 Py_SET_SIZE(np, size);
584 return (PyObject *) np;
585}
586
587static int
588_list_clear(PyListObject *a)
589{
590 Py_ssize_t i;
591 PyObject **item = a->ob_item;
592 if (item != NULL) {
593 /* Because XDECREF can recursively invoke operations on
594 this list, we make it empty first. */
595 i = Py_SIZE(a);
596 Py_SET_SIZE(a, 0);
597 a->ob_item = NULL;
598 a->allocated = 0;
599 while (--i >= 0) {
600 Py_XDECREF(item[i]);
601 }
602 PyMem_Free(item);
603 }
604 /* Never fails; the return value can be ignored.
605 Note that there is no guarantee that the list is actually empty
606 at this point, because XDECREF may have populated it again! */
607 return 0;
608}
609
610/* a[ilow:ihigh] = v if v != NULL.
611 * del a[ilow:ihigh] if v == NULL.
612 *
613 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
614 * guaranteed the call cannot fail.
615 */
616static int
617list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
618{
619 /* Because [X]DECREF can recursively invoke list operations on
620 this list, we must postpone all [X]DECREF activity until
621 after the list is back in its canonical shape. Therefore
622 we must allocate an additional array, 'recycle', into which
623 we temporarily copy the items that are deleted from the
624 list. :-( */
625 PyObject *recycle_on_stack[8];
626 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
627 PyObject **item;
628 PyObject **vitem = NULL;
629 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
630 Py_ssize_t n; /* # of elements in replacement list */
631 Py_ssize_t norig; /* # of elements in list getting replaced */
632 Py_ssize_t d; /* Change in size */
633 Py_ssize_t k;
634 size_t s;
635 int result = -1; /* guilty until proved innocent */
636#define b ((PyListObject *)v)
637 if (v == NULL)
638 n = 0;
639 else {
640 if (a == b) {
641 /* Special case "a[i:j] = a" -- copy b first */
642 v = list_slice(b, 0, Py_SIZE(b));
643 if (v == NULL)
644 return result;
645 result = list_ass_slice(a, ilow, ihigh, v);
646 Py_DECREF(v);
647 return result;
648 }
649 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
650 if(v_as_SF == NULL)
651 goto Error;
652 n = PySequence_Fast_GET_SIZE(v_as_SF);
653 vitem = PySequence_Fast_ITEMS(v_as_SF);
654 }
655 if (ilow < 0)
656 ilow = 0;
657 else if (ilow > Py_SIZE(a))
658 ilow = Py_SIZE(a);
659
660 if (ihigh < ilow)
661 ihigh = ilow;
662 else if (ihigh > Py_SIZE(a))
663 ihigh = Py_SIZE(a);
664
665 norig = ihigh - ilow;
666 assert(norig >= 0);
667 d = n - norig;
668 if (Py_SIZE(a) + d == 0) {
669 Py_XDECREF(v_as_SF);
670 return _list_clear(a);
671 }
672 item = a->ob_item;
673 /* recycle the items that we are about to remove */
674 s = norig * sizeof(PyObject *);
675 /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
676 if (s) {
677 if (s > sizeof(recycle_on_stack)) {
678 recycle = (PyObject **)PyMem_Malloc(s);
679 if (recycle == NULL) {
680 PyErr_NoMemory();
681 goto Error;
682 }
683 }
684 memcpy(recycle, &item[ilow], s);
685 }
686
687 if (d < 0) { /* Delete -d items */
688 Py_ssize_t tail;
689 tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
690 memmove(&item[ihigh+d], &item[ihigh], tail);
691 if (list_resize(a, Py_SIZE(a) + d) < 0) {
692 memmove(&item[ihigh], &item[ihigh+d], tail);
693 memcpy(&item[ilow], recycle, s);
694 goto Error;
695 }
696 item = a->ob_item;
697 }
698 else if (d > 0) { /* Insert d items */
699 k = Py_SIZE(a);
700 if (list_resize(a, k+d) < 0)
701 goto Error;
702 item = a->ob_item;
703 memmove(&item[ihigh+d], &item[ihigh],
704 (k - ihigh)*sizeof(PyObject *));
705 }
706 for (k = 0; k < n; k++, ilow++) {
707 PyObject *w = vitem[k];
708 Py_XINCREF(w);
709 item[ilow] = w;
710 }
711 for (k = norig - 1; k >= 0; --k)
712 Py_XDECREF(recycle[k]);
713 result = 0;
714 Error:
715 if (recycle != recycle_on_stack)
716 PyMem_Free(recycle);
717 Py_XDECREF(v_as_SF);
718 return result;
719#undef b
720}
721
722int
723PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
724{
725 if (!PyList_Check(a)) {
726 PyErr_BadInternalCall();
727 return -1;
728 }
729 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
730}
731
732static PyObject *
733list_inplace_repeat(PyListObject *self, Py_ssize_t n)
734{
735 PyObject **items;
736 Py_ssize_t size, i, j, p;
737
738
739 size = PyList_GET_SIZE(self);
740 if (size == 0 || n == 1) {
741 Py_INCREF(self);
742 return (PyObject *)self;
743 }
744
745 if (n < 1) {
746 (void)_list_clear(self);
747 Py_INCREF(self);
748 return (PyObject *)self;
749 }
750
751 if (size > PY_SSIZE_T_MAX / n) {
752 return PyErr_NoMemory();
753 }
754
755 if (list_resize(self, size*n) < 0)
756 return NULL;
757
758 p = size;
759 items = self->ob_item;
760 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
761 for (j = 0; j < size; j++) {
762 PyObject *o = items[j];
763 Py_INCREF(o);
764 items[p++] = o;
765 }
766 }
767 Py_INCREF(self);
768 return (PyObject *)self;
769}
770
771static int
772list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
773{
774 if (!valid_index(i, Py_SIZE(a))) {
775 PyErr_SetString(PyExc_IndexError,
776 "list assignment index out of range");
777 return -1;
778 }
779 if (v == NULL)
780 return list_ass_slice(a, i, i+1, v);
781 Py_INCREF(v);
782 Py_SETREF(a->ob_item[i], v);
783 return 0;
784}
785
786/*[clinic input]
787list.insert
788
789 index: Py_ssize_t
790 object: object
791 /
792
793Insert object before index.
794[clinic start generated code]*/
795
796static PyObject *
797list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
798/*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
799{
800 if (ins1(self, index, object) == 0)
801 Py_RETURN_NONE;
802 return NULL;
803}
804
805/*[clinic input]
806list.clear
807
808Remove all items from list.
809[clinic start generated code]*/
810
811static PyObject *
812list_clear_impl(PyListObject *self)
813/*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/
814{
815 _list_clear(self);
816 Py_RETURN_NONE;
817}
818
819/*[clinic input]
820list.copy
821
822Return a shallow copy of the list.
823[clinic start generated code]*/
824
825static PyObject *
826list_copy_impl(PyListObject *self)
827/*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/
828{
829 return list_slice(self, 0, Py_SIZE(self));
830}
831
832/*[clinic input]
833list.append
834
835 object: object
836 /
837
838Append object to the end of the list.
839[clinic start generated code]*/
840
841static PyObject *
842list_append(PyListObject *self, PyObject *object)
843/*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
844{
845 if (app1(self, object) == 0)
846 Py_RETURN_NONE;
847 return NULL;
848}
849
850/*[clinic input]
851list.extend
852
853 iterable: object
854 /
855
856Extend list by appending elements from the iterable.
857[clinic start generated code]*/
858
859static PyObject *
860list_extend(PyListObject *self, PyObject *iterable)
861/*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/
862{
863 PyObject *it; /* iter(v) */
864 Py_ssize_t m; /* size of self */
865 Py_ssize_t n; /* guess for size of iterable */
866 Py_ssize_t i;
867 PyObject *(*iternext)(PyObject *);
868
869 /* Special cases:
870 1) lists and tuples which can use PySequence_Fast ops
871 2) extending self to self requires making a copy first
872 */
873 if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
874 (PyObject *)self == iterable) {
875 PyObject **src, **dest;
876 iterable = PySequence_Fast(iterable, "argument must be iterable");
877 if (!iterable)
878 return NULL;
879 n = PySequence_Fast_GET_SIZE(iterable);
880 if (n == 0) {
881 /* short circuit when iterable is empty */
882 Py_DECREF(iterable);
883 Py_RETURN_NONE;
884 }
885 m = Py_SIZE(self);
886 /* It should not be possible to allocate a list large enough to cause
887 an overflow on any relevant platform */
888 assert(m < PY_SSIZE_T_MAX - n);
889 if (self->ob_item == NULL) {
890 if (list_preallocate_exact(self, n) < 0) {
891 return NULL;
892 }
893 Py_SET_SIZE(self, n);
894 }
895 else if (list_resize(self, m + n) < 0) {
896 Py_DECREF(iterable);
897 return NULL;
898 }
899 /* note that we may still have self == iterable here for the
900 * situation a.extend(a), but the following code works
901 * in that case too. Just make sure to resize self
902 * before calling PySequence_Fast_ITEMS.
903 */
904 /* populate the end of self with iterable's items */
905 src = PySequence_Fast_ITEMS(iterable);
906 dest = self->ob_item + m;
907 for (i = 0; i < n; i++) {
908 PyObject *o = src[i];
909 Py_INCREF(o);
910 dest[i] = o;
911 }
912 Py_DECREF(iterable);
913 Py_RETURN_NONE;
914 }
915
916 it = PyObject_GetIter(iterable);
917 if (it == NULL)
918 return NULL;
919 iternext = *Py_TYPE(it)->tp_iternext;
920
921 /* Guess a result list size. */
922 n = PyObject_LengthHint(iterable, 8);
923 if (n < 0) {
924 Py_DECREF(it);
925 return NULL;
926 }
927 m = Py_SIZE(self);
928 if (m > PY_SSIZE_T_MAX - n) {
929 /* m + n overflowed; on the chance that n lied, and there really
930 * is enough room, ignore it. If n was telling the truth, we'll
931 * eventually run out of memory during the loop.
932 */
933 }
934 else if (self->ob_item == NULL) {
935 if (n && list_preallocate_exact(self, n) < 0)
936 goto error;
937 }
938 else {
939 /* Make room. */
940 if (list_resize(self, m + n) < 0)
941 goto error;
942 /* Make the list sane again. */
943 Py_SET_SIZE(self, m);
944 }
945
946 /* Run iterator to exhaustion. */
947 for (;;) {
948 PyObject *item = iternext(it);
949 if (item == NULL) {
950 if (PyErr_Occurred()) {
951 if (PyErr_ExceptionMatches(PyExc_StopIteration))
952 PyErr_Clear();
953 else
954 goto error;
955 }
956 break;
957 }
958 if (Py_SIZE(self) < self->allocated) {
959 /* steals ref */
960 PyList_SET_ITEM(self, Py_SIZE(self), item);
961 Py_SET_SIZE(self, Py_SIZE(self) + 1);
962 }
963 else {
964 int status = app1(self, item);
965 Py_DECREF(item); /* append creates a new ref */
966 if (status < 0)
967 goto error;
968 }
969 }
970
971 /* Cut back result list if initial guess was too large. */
972 if (Py_SIZE(self) < self->allocated) {
973 if (list_resize(self, Py_SIZE(self)) < 0)
974 goto error;
975 }
976
977 Py_DECREF(it);
978 Py_RETURN_NONE;
979
980 error:
981 Py_DECREF(it);
982 return NULL;
983}
984
985PyObject *
986_PyList_Extend(PyListObject *self, PyObject *iterable)
987{
988 return list_extend(self, iterable);
989}
990
991static PyObject *
992list_inplace_concat(PyListObject *self, PyObject *other)
993{
994 PyObject *result;
995
996 result = list_extend(self, other);
997 if (result == NULL)
998 return result;
999 Py_DECREF(result);
1000 Py_INCREF(self);
1001 return (PyObject *)self;
1002}
1003
1004/*[clinic input]
1005list.pop
1006
1007 index: Py_ssize_t = -1
1008 /
1009
1010Remove and return item at index (default last).
1011
1012Raises IndexError if list is empty or index is out of range.
1013[clinic start generated code]*/
1014
1015static PyObject *
1016list_pop_impl(PyListObject *self, Py_ssize_t index)
1017/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
1018{
1019 PyObject *v;
1020 int status;
1021
1022 if (Py_SIZE(self) == 0) {
1023 /* Special-case most common failure cause */
1024 PyErr_SetString(PyExc_IndexError, "pop from empty list");
1025 return NULL;
1026 }
1027 if (index < 0)
1028 index += Py_SIZE(self);
1029 if (!valid_index(index, Py_SIZE(self))) {
1030 PyErr_SetString(PyExc_IndexError, "pop index out of range");
1031 return NULL;
1032 }
1033 v = self->ob_item[index];
1034 if (index == Py_SIZE(self) - 1) {
1035 status = list_resize(self, Py_SIZE(self) - 1);
1036 if (status >= 0)
1037 return v; /* and v now owns the reference the list had */
1038 else
1039 return NULL;
1040 }
1041 Py_INCREF(v);
1042 status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
1043 if (status < 0) {
1044 Py_DECREF(v);
1045 return NULL;
1046 }
1047 return v;
1048}
1049
1050/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
1051static void
1052reverse_slice(PyObject **lo, PyObject **hi)
1053{
1054 assert(lo && hi);
1055
1056 --hi;
1057 while (lo < hi) {
1058 PyObject *t = *lo;
1059 *lo = *hi;
1060 *hi = t;
1061 ++lo;
1062 --hi;
1063 }
1064}
1065
1066/* Lots of code for an adaptive, stable, natural mergesort. There are many
1067 * pieces to this algorithm; read listsort.txt for overviews and details.
1068 */
1069
1070/* A sortslice contains a pointer to an array of keys and a pointer to
1071 * an array of corresponding values. In other words, keys[i]
1072 * corresponds with values[i]. If values == NULL, then the keys are
1073 * also the values.
1074 *
1075 * Several convenience routines are provided here, so that keys and
1076 * values are always moved in sync.
1077 */
1078
1079typedef struct {
1080 PyObject **keys;
1081 PyObject **values;
1082} sortslice;
1083
1084Py_LOCAL_INLINE(void)
1085sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
1086{
1087 s1->keys[i] = s2->keys[j];
1088 if (s1->values != NULL)
1089 s1->values[i] = s2->values[j];
1090}
1091
1092Py_LOCAL_INLINE(void)
1093sortslice_copy_incr(sortslice *dst, sortslice *src)
1094{
1095 *dst->keys++ = *src->keys++;
1096 if (dst->values != NULL)
1097 *dst->values++ = *src->values++;
1098}
1099
1100Py_LOCAL_INLINE(void)
1101sortslice_copy_decr(sortslice *dst, sortslice *src)
1102{
1103 *dst->keys-- = *src->keys--;
1104 if (dst->values != NULL)
1105 *dst->values-- = *src->values--;
1106}
1107
1108
1109Py_LOCAL_INLINE(void)
1110sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
1111 Py_ssize_t n)
1112{
1113 memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1114 if (s1->values != NULL)
1115 memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1116}
1117
1118Py_LOCAL_INLINE(void)
1119sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
1120 Py_ssize_t n)
1121{
1122 memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1123 if (s1->values != NULL)
1124 memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1125}
1126
1127Py_LOCAL_INLINE(void)
1128sortslice_advance(sortslice *slice, Py_ssize_t n)
1129{
1130 slice->keys += n;
1131 if (slice->values != NULL)
1132 slice->values += n;
1133}
1134
1135/* Comparison function: ms->key_compare, which is set at run-time in
1136 * listsort_impl to optimize for various special cases.
1137 * Returns -1 on error, 1 if x < y, 0 if x >= y.
1138 */
1139
1140#define ISLT(X, Y) (*(ms->key_compare))(X, Y, ms)
1141
1142/* Compare X to Y via "<". Goto "fail" if the comparison raises an
1143 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
1144 started. It makes more sense in context <wink>. X and Y are PyObject*s.
1145*/
1146#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \
1147 if (k)
1148
1149/* The maximum number of entries in a MergeState's pending-runs stack.
1150 * This is enough to sort arrays of size up to about
1151 * 32 * phi ** MAX_MERGE_PENDING
1152 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1153 * with 2**64 elements.
1154 */
1155#define MAX_MERGE_PENDING 85
1156
1157/* When we get into galloping mode, we stay there until both runs win less
1158 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1159 */
1160#define MIN_GALLOP 7
1161
1162/* Avoid malloc for small temp arrays. */
1163#define MERGESTATE_TEMP_SIZE 256
1164
1165/* One MergeState exists on the stack per invocation of mergesort. It's just
1166 * a convenient way to pass state around among the helper functions.
1167 */
1168struct s_slice {
1169 sortslice base;
1170 Py_ssize_t len;
1171};
1172
1173typedef struct s_MergeState MergeState;
1174struct s_MergeState {
1175 /* This controls when we get *into* galloping mode. It's initialized
1176 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1177 * random data, and lower for highly structured data.
1178 */
1179 Py_ssize_t min_gallop;
1180
1181 /* 'a' is temp storage to help with merges. It contains room for
1182 * alloced entries.
1183 */
1184 sortslice a; /* may point to temparray below */
1185 Py_ssize_t alloced;
1186
1187 /* A stack of n pending runs yet to be merged. Run #i starts at
1188 * address base[i] and extends for len[i] elements. It's always
1189 * true (so long as the indices are in bounds) that
1190 *
1191 * pending[i].base + pending[i].len == pending[i+1].base
1192 *
1193 * so we could cut the storage for this, but it's a minor amount,
1194 * and keeping all the info explicit simplifies the code.
1195 */
1196 int n;
1197 struct s_slice pending[MAX_MERGE_PENDING];
1198
1199 /* 'a' points to this when possible, rather than muck with malloc. */
1200 PyObject *temparray[MERGESTATE_TEMP_SIZE];
1201
1202 /* This is the function we will use to compare two keys,
1203 * even when none of our special cases apply and we have to use
1204 * safe_object_compare. */
1205 int (*key_compare)(PyObject *, PyObject *, MergeState *);
1206
1207 /* This function is used by unsafe_object_compare to optimize comparisons
1208 * when we know our list is type-homogeneous but we can't assume anything else.
1209 * In the pre-sort check it is set equal to Py_TYPE(key)->tp_richcompare */
1210 PyObject *(*key_richcompare)(PyObject *, PyObject *, int);
1211
1212 /* This function is used by unsafe_tuple_compare to compare the first elements
1213 * of tuples. It may be set to safe_object_compare, but the idea is that hopefully
1214 * we can assume more, and use one of the special-case compares. */
1215 int (*tuple_elem_compare)(PyObject *, PyObject *, MergeState *);
1216};
1217
1218/* binarysort is the best method for sorting small arrays: it does
1219 few compares, but can do data movement quadratic in the number of
1220 elements.
1221 [lo, hi) is a contiguous slice of a list, and is sorted via
1222 binary insertion. This sort is stable.
1223 On entry, must have lo <= start <= hi, and that [lo, start) is already
1224 sorted (pass start == lo if you don't know!).
1225 If islt() complains return -1, else 0.
1226 Even in case of error, the output slice will be some permutation of
1227 the input (nothing is lost or duplicated).
1228*/
1229static int
1230binarysort(MergeState *ms, sortslice lo, PyObject **hi, PyObject **start)
1231{
1232 Py_ssize_t k;
1233 PyObject **l, **p, **r;
1234 PyObject *pivot;
1235
1236 assert(lo.keys <= start && start <= hi);
1237 /* assert [lo, start) is sorted */
1238 if (lo.keys == start)
1239 ++start;
1240 for (; start < hi; ++start) {
1241 /* set l to where *start belongs */
1242 l = lo.keys;
1243 r = start;
1244 pivot = *r;
1245 /* Invariants:
1246 * pivot >= all in [lo, l).
1247 * pivot < all in [r, start).
1248 * The second is vacuously true at the start.
1249 */
1250 assert(l < r);
1251 do {
1252 p = l + ((r - l) >> 1);
1253 IFLT(pivot, *p)
1254 r = p;
1255 else
1256 l = p+1;
1257 } while (l < r);
1258 assert(l == r);
1259 /* The invariants still hold, so pivot >= all in [lo, l) and
1260 pivot < all in [l, start), so pivot belongs at l. Note
1261 that if there are elements equal to pivot, l points to the
1262 first slot after them -- that's why this sort is stable.
1263 Slide over to make room.
1264 Caution: using memmove is much slower under MSVC 5;
1265 we're not usually moving many slots. */
1266 for (p = start; p > l; --p)
1267 *p = *(p-1);
1268 *l = pivot;
1269 if (lo.values != NULL) {
1270 Py_ssize_t offset = lo.values - lo.keys;
1271 p = start + offset;
1272 pivot = *p;
1273 l += offset;
1274 for (p = start + offset; p > l; --p)
1275 *p = *(p-1);
1276 *l = pivot;
1277 }
1278 }
1279 return 0;
1280
1281 fail:
1282 return -1;
1283}
1284
1285/*
1286Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1287is required on entry. "A run" is the longest ascending sequence, with
1288
1289 lo[0] <= lo[1] <= lo[2] <= ...
1290
1291or the longest descending sequence, with
1292
1293 lo[0] > lo[1] > lo[2] > ...
1294
1295Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1296For its intended use in a stable mergesort, the strictness of the defn of
1297"descending" is needed so that the caller can safely reverse a descending
1298sequence without violating stability (strict > ensures there are no equal
1299elements to get out of order).
1300
1301Returns -1 in case of error.
1302*/
1303static Py_ssize_t
1304count_run(MergeState *ms, PyObject **lo, PyObject **hi, int *descending)
1305{
1306 Py_ssize_t k;
1307 Py_ssize_t n;
1308
1309 assert(lo < hi);
1310 *descending = 0;
1311 ++lo;
1312 if (lo == hi)
1313 return 1;
1314
1315 n = 2;
1316 IFLT(*lo, *(lo-1)) {
1317 *descending = 1;
1318 for (lo = lo+1; lo < hi; ++lo, ++n) {
1319 IFLT(*lo, *(lo-1))
1320 ;
1321 else
1322 break;
1323 }
1324 }
1325 else {
1326 for (lo = lo+1; lo < hi; ++lo, ++n) {
1327 IFLT(*lo, *(lo-1))
1328 break;
1329 }
1330 }
1331
1332 return n;
1333fail:
1334 return -1;
1335}
1336
1337/*
1338Locate the proper position of key in a sorted vector; if the vector contains
1339an element equal to key, return the position immediately to the left of
1340the leftmost equal element. [gallop_right() does the same except returns
1341the position to the right of the rightmost equal element (if any).]
1342
1343"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
1344
1345"hint" is an index at which to begin the search, 0 <= hint < n. The closer
1346hint is to the final result, the faster this runs.
1347
1348The return value is the int k in 0..n such that
1349
1350 a[k-1] < key <= a[k]
1351
1352pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1353key belongs at index k; or, IOW, the first k elements of a should precede
1354key, and the last n-k should follow key.
1355
1356Returns -1 on error. See listsort.txt for info on the method.
1357*/
1358static Py_ssize_t
1359gallop_left(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
1360{
1361 Py_ssize_t ofs;
1362 Py_ssize_t lastofs;
1363 Py_ssize_t k;
1364
1365 assert(key && a && n > 0 && hint >= 0 && hint < n);
1366
1367 a += hint;
1368 lastofs = 0;
1369 ofs = 1;
1370 IFLT(*a, key) {
1371 /* a[hint] < key -- gallop right, until
1372 * a[hint + lastofs] < key <= a[hint + ofs]
1373 */
1374 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1375 while (ofs < maxofs) {
1376 IFLT(a[ofs], key) {
1377 lastofs = ofs;
1378 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1379 ofs = (ofs << 1) + 1;
1380 }
1381 else /* key <= a[hint + ofs] */
1382 break;
1383 }
1384 if (ofs > maxofs)
1385 ofs = maxofs;
1386 /* Translate back to offsets relative to &a[0]. */
1387 lastofs += hint;
1388 ofs += hint;
1389 }
1390 else {
1391 /* key <= a[hint] -- gallop left, until
1392 * a[hint - ofs] < key <= a[hint - lastofs]
1393 */
1394 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1395 while (ofs < maxofs) {
1396 IFLT(*(a-ofs), key)
1397 break;
1398 /* key <= a[hint - ofs] */
1399 lastofs = ofs;
1400 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1401 ofs = (ofs << 1) + 1;
1402 }
1403 if (ofs > maxofs)
1404 ofs = maxofs;
1405 /* Translate back to positive offsets relative to &a[0]. */
1406 k = lastofs;
1407 lastofs = hint - ofs;
1408 ofs = hint - k;
1409 }
1410 a -= hint;
1411
1412 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1413 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1414 * right of lastofs but no farther right than ofs. Do a binary
1415 * search, with invariant a[lastofs-1] < key <= a[ofs].
1416 */
1417 ++lastofs;
1418 while (lastofs < ofs) {
1419 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
1420
1421 IFLT(a[m], key)
1422 lastofs = m+1; /* a[m] < key */
1423 else
1424 ofs = m; /* key <= a[m] */
1425 }
1426 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1427 return ofs;
1428
1429fail:
1430 return -1;
1431}
1432
1433/*
1434Exactly like gallop_left(), except that if key already exists in a[0:n],
1435finds the position immediately to the right of the rightmost equal value.
1436
1437The return value is the int k in 0..n such that
1438
1439 a[k-1] <= key < a[k]
1440
1441or -1 if error.
1442
1443The code duplication is massive, but this is enough different given that
1444we're sticking to "<" comparisons that it's much harder to follow if
1445written as one routine with yet another "left or right?" flag.
1446*/
1447static Py_ssize_t
1448gallop_right(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
1449{
1450 Py_ssize_t ofs;
1451 Py_ssize_t lastofs;
1452 Py_ssize_t k;
1453
1454 assert(key && a && n > 0 && hint >= 0 && hint < n);
1455
1456 a += hint;
1457 lastofs = 0;
1458 ofs = 1;
1459 IFLT(key, *a) {
1460 /* key < a[hint] -- gallop left, until
1461 * a[hint - ofs] <= key < a[hint - lastofs]
1462 */
1463 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1464 while (ofs < maxofs) {
1465 IFLT(key, *(a-ofs)) {
1466 lastofs = ofs;
1467 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1468 ofs = (ofs << 1) + 1;
1469 }
1470 else /* a[hint - ofs] <= key */
1471 break;
1472 }
1473 if (ofs > maxofs)
1474 ofs = maxofs;
1475 /* Translate back to positive offsets relative to &a[0]. */
1476 k = lastofs;
1477 lastofs = hint - ofs;
1478 ofs = hint - k;
1479 }
1480 else {
1481 /* a[hint] <= key -- gallop right, until
1482 * a[hint + lastofs] <= key < a[hint + ofs]
1483 */
1484 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1485 while (ofs < maxofs) {
1486 IFLT(key, a[ofs])
1487 break;
1488 /* a[hint + ofs] <= key */
1489 lastofs = ofs;
1490 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1491 ofs = (ofs << 1) + 1;
1492 }
1493 if (ofs > maxofs)
1494 ofs = maxofs;
1495 /* Translate back to offsets relative to &a[0]. */
1496 lastofs += hint;
1497 ofs += hint;
1498 }
1499 a -= hint;
1500
1501 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1502 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1503 * right of lastofs but no farther right than ofs. Do a binary
1504 * search, with invariant a[lastofs-1] <= key < a[ofs].
1505 */
1506 ++lastofs;
1507 while (lastofs < ofs) {
1508 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
1509
1510 IFLT(key, a[m])
1511 ofs = m; /* key < a[m] */
1512 else
1513 lastofs = m+1; /* a[m] <= key */
1514 }
1515 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1516 return ofs;
1517
1518fail:
1519 return -1;
1520}
1521
1522/* Conceptually a MergeState's constructor. */
1523static void
1524merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc)
1525{
1526 assert(ms != NULL);
1527 if (has_keyfunc) {
1528 /* The temporary space for merging will need at most half the list
1529 * size rounded up. Use the minimum possible space so we can use the
1530 * rest of temparray for other things. In particular, if there is
1531 * enough extra space, listsort() will use it to store the keys.
1532 */
1533 ms->alloced = (list_size + 1) / 2;
1534
1535 /* ms->alloced describes how many keys will be stored at
1536 ms->temparray, but we also need to store the values. Hence,
1537 ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
1538 if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
1539 ms->alloced = MERGESTATE_TEMP_SIZE / 2;
1540 ms->a.values = &ms->temparray[ms->alloced];
1541 }
1542 else {
1543 ms->alloced = MERGESTATE_TEMP_SIZE;
1544 ms->a.values = NULL;
1545 }
1546 ms->a.keys = ms->temparray;
1547 ms->n = 0;
1548 ms->min_gallop = MIN_GALLOP;
1549}
1550
1551/* Free all the temp memory owned by the MergeState. This must be called
1552 * when you're done with a MergeState, and may be called before then if
1553 * you want to free the temp memory early.
1554 */
1555static void
1556merge_freemem(MergeState *ms)
1557{
1558 assert(ms != NULL);
1559 if (ms->a.keys != ms->temparray) {
1560 PyMem_Free(ms->a.keys);
1561 ms->a.keys = NULL;
1562 }
1563}
1564
1565/* Ensure enough temp memory for 'need' array slots is available.
1566 * Returns 0 on success and -1 if the memory can't be gotten.
1567 */
1568static int
1569merge_getmem(MergeState *ms, Py_ssize_t need)
1570{
1571 int multiplier;
1572
1573 assert(ms != NULL);
1574 if (need <= ms->alloced)
1575 return 0;
1576
1577 multiplier = ms->a.values != NULL ? 2 : 1;
1578
1579 /* Don't realloc! That can cost cycles to copy the old data, but
1580 * we don't care what's in the block.
1581 */
1582 merge_freemem(ms);
1583 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject *) / multiplier) {
1584 PyErr_NoMemory();
1585 return -1;
1586 }
1587 ms->a.keys = (PyObject **)PyMem_Malloc(multiplier * need
1588 * sizeof(PyObject *));
1589 if (ms->a.keys != NULL) {
1590 ms->alloced = need;
1591 if (ms->a.values != NULL)
1592 ms->a.values = &ms->a.keys[need];
1593 return 0;
1594 }
1595 PyErr_NoMemory();
1596 return -1;
1597}
1598#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1599 merge_getmem(MS, NEED))
1600
1601/* Merge the na elements starting at ssa with the nb elements starting at
1602 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
1603 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
1604 * should have na <= nb. See listsort.txt for more info. Return 0 if
1605 * successful, -1 if error.
1606 */
1607static Py_ssize_t
1608merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
1609 sortslice ssb, Py_ssize_t nb)
1610{
1611 Py_ssize_t k;
1612 sortslice dest;
1613 int result = -1; /* guilty until proved innocent */
1614 Py_ssize_t min_gallop;
1615
1616 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1617 assert(ssa.keys + na == ssb.keys);
1618 if (MERGE_GETMEM(ms, na) < 0)
1619 return -1;
1620 sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
1621 dest = ssa;
1622 ssa = ms->a;
1623
1624 sortslice_copy_incr(&dest, &ssb);
1625 --nb;
1626 if (nb == 0)
1627 goto Succeed;
1628 if (na == 1)
1629 goto CopyB;
1630
1631 min_gallop = ms->min_gallop;
1632 for (;;) {
1633 Py_ssize_t acount = 0; /* # of times A won in a row */
1634 Py_ssize_t bcount = 0; /* # of times B won in a row */
1635
1636 /* Do the straightforward thing until (if ever) one run
1637 * appears to win consistently.
1638 */
1639 for (;;) {
1640 assert(na > 1 && nb > 0);
1641 k = ISLT(ssb.keys[0], ssa.keys[0]);
1642 if (k) {
1643 if (k < 0)
1644 goto Fail;
1645 sortslice_copy_incr(&dest, &ssb);
1646 ++bcount;
1647 acount = 0;
1648 --nb;
1649 if (nb == 0)
1650 goto Succeed;
1651 if (bcount >= min_gallop)
1652 break;
1653 }
1654 else {
1655 sortslice_copy_incr(&dest, &ssa);
1656 ++acount;
1657 bcount = 0;
1658 --na;
1659 if (na == 1)
1660 goto CopyB;
1661 if (acount >= min_gallop)
1662 break;
1663 }
1664 }
1665
1666 /* One run is winning so consistently that galloping may
1667 * be a huge win. So try that, and continue galloping until
1668 * (if ever) neither run appears to be winning consistently
1669 * anymore.
1670 */
1671 ++min_gallop;
1672 do {
1673 assert(na > 1 && nb > 0);
1674 min_gallop -= min_gallop > 1;
1675 ms->min_gallop = min_gallop;
1676 k = gallop_right(ms, ssb.keys[0], ssa.keys, na, 0);
1677 acount = k;
1678 if (k) {
1679 if (k < 0)
1680 goto Fail;
1681 sortslice_memcpy(&dest, 0, &ssa, 0, k);
1682 sortslice_advance(&dest, k);
1683 sortslice_advance(&ssa, k);
1684 na -= k;
1685 if (na == 1)
1686 goto CopyB;
1687 /* na==0 is impossible now if the comparison
1688 * function is consistent, but we can't assume
1689 * that it is.
1690 */
1691 if (na == 0)
1692 goto Succeed;
1693 }
1694 sortslice_copy_incr(&dest, &ssb);
1695 --nb;
1696 if (nb == 0)
1697 goto Succeed;
1698
1699 k = gallop_left(ms, ssa.keys[0], ssb.keys, nb, 0);
1700 bcount = k;
1701 if (k) {
1702 if (k < 0)
1703 goto Fail;
1704 sortslice_memmove(&dest, 0, &ssb, 0, k);
1705 sortslice_advance(&dest, k);
1706 sortslice_advance(&ssb, k);
1707 nb -= k;
1708 if (nb == 0)
1709 goto Succeed;
1710 }
1711 sortslice_copy_incr(&dest, &ssa);
1712 --na;
1713 if (na == 1)
1714 goto CopyB;
1715 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1716 ++min_gallop; /* penalize it for leaving galloping mode */
1717 ms->min_gallop = min_gallop;
1718 }
1719Succeed:
1720 result = 0;
1721Fail:
1722 if (na)
1723 sortslice_memcpy(&dest, 0, &ssa, 0, na);
1724 return result;
1725CopyB:
1726 assert(na == 1 && nb > 0);
1727 /* The last element of ssa belongs at the end of the merge. */
1728 sortslice_memmove(&dest, 0, &ssb, 0, nb);
1729 sortslice_copy(&dest, nb, &ssa, 0);
1730 return 0;
1731}
1732
1733/* Merge the na elements starting at pa with the nb elements starting at
1734 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
1735 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
1736 * should have na >= nb. See listsort.txt for more info. Return 0 if
1737 * successful, -1 if error.
1738 */
1739static Py_ssize_t
1740merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
1741 sortslice ssb, Py_ssize_t nb)
1742{
1743 Py_ssize_t k;
1744 sortslice dest, basea, baseb;
1745 int result = -1; /* guilty until proved innocent */
1746 Py_ssize_t min_gallop;
1747
1748 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1749 assert(ssa.keys + na == ssb.keys);
1750 if (MERGE_GETMEM(ms, nb) < 0)
1751 return -1;
1752 dest = ssb;
1753 sortslice_advance(&dest, nb-1);
1754 sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
1755 basea = ssa;
1756 baseb = ms->a;
1757 ssb.keys = ms->a.keys + nb - 1;
1758 if (ssb.values != NULL)
1759 ssb.values = ms->a.values + nb - 1;
1760 sortslice_advance(&ssa, na - 1);
1761
1762 sortslice_copy_decr(&dest, &ssa);
1763 --na;
1764 if (na == 0)
1765 goto Succeed;
1766 if (nb == 1)
1767 goto CopyA;
1768
1769 min_gallop = ms->min_gallop;
1770 for (;;) {
1771 Py_ssize_t acount = 0; /* # of times A won in a row */
1772 Py_ssize_t bcount = 0; /* # of times B won in a row */
1773
1774 /* Do the straightforward thing until (if ever) one run
1775 * appears to win consistently.
1776 */
1777 for (;;) {
1778 assert(na > 0 && nb > 1);
1779 k = ISLT(ssb.keys[0], ssa.keys[0]);
1780 if (k) {
1781 if (k < 0)
1782 goto Fail;
1783 sortslice_copy_decr(&dest, &ssa);
1784 ++acount;
1785 bcount = 0;
1786 --na;
1787 if (na == 0)
1788 goto Succeed;
1789 if (acount >= min_gallop)
1790 break;
1791 }
1792 else {
1793 sortslice_copy_decr(&dest, &ssb);
1794 ++bcount;
1795 acount = 0;
1796 --nb;
1797 if (nb == 1)
1798 goto CopyA;
1799 if (bcount >= min_gallop)
1800 break;
1801 }
1802 }
1803
1804 /* One run is winning so consistently that galloping may
1805 * be a huge win. So try that, and continue galloping until
1806 * (if ever) neither run appears to be winning consistently
1807 * anymore.
1808 */
1809 ++min_gallop;
1810 do {
1811 assert(na > 0 && nb > 1);
1812 min_gallop -= min_gallop > 1;
1813 ms->min_gallop = min_gallop;
1814 k = gallop_right(ms, ssb.keys[0], basea.keys, na, na-1);
1815 if (k < 0)
1816 goto Fail;
1817 k = na - k;
1818 acount = k;
1819 if (k) {
1820 sortslice_advance(&dest, -k);
1821 sortslice_advance(&ssa, -k);
1822 sortslice_memmove(&dest, 1, &ssa, 1, k);
1823 na -= k;
1824 if (na == 0)
1825 goto Succeed;
1826 }
1827 sortslice_copy_decr(&dest, &ssb);
1828 --nb;
1829 if (nb == 1)
1830 goto CopyA;
1831
1832 k = gallop_left(ms, ssa.keys[0], baseb.keys, nb, nb-1);
1833 if (k < 0)
1834 goto Fail;
1835 k = nb - k;
1836 bcount = k;
1837 if (k) {
1838 sortslice_advance(&dest, -k);
1839 sortslice_advance(&ssb, -k);
1840 sortslice_memcpy(&dest, 1, &ssb, 1, k);
1841 nb -= k;
1842 if (nb == 1)
1843 goto CopyA;
1844 /* nb==0 is impossible now if the comparison
1845 * function is consistent, but we can't assume
1846 * that it is.
1847 */
1848 if (nb == 0)
1849 goto Succeed;
1850 }
1851 sortslice_copy_decr(&dest, &ssa);
1852 --na;
1853 if (na == 0)
1854 goto Succeed;
1855 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1856 ++min_gallop; /* penalize it for leaving galloping mode */
1857 ms->min_gallop = min_gallop;
1858 }
1859Succeed:
1860 result = 0;
1861Fail:
1862 if (nb)
1863 sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
1864 return result;
1865CopyA:
1866 assert(nb == 1 && na > 0);
1867 /* The first element of ssb belongs at the front of the merge. */
1868 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
1869 sortslice_advance(&dest, -na);
1870 sortslice_advance(&ssa, -na);
1871 sortslice_copy(&dest, 0, &ssb, 0);
1872 return 0;
1873}
1874
1875/* Merge the two runs at stack indices i and i+1.
1876 * Returns 0 on success, -1 on error.
1877 */
1878static Py_ssize_t
1879merge_at(MergeState *ms, Py_ssize_t i)
1880{
1881 sortslice ssa, ssb;
1882 Py_ssize_t na, nb;
1883 Py_ssize_t k;
1884
1885 assert(ms != NULL);
1886 assert(ms->n >= 2);
1887 assert(i >= 0);
1888 assert(i == ms->n - 2 || i == ms->n - 3);
1889
1890 ssa = ms->pending[i].base;
1891 na = ms->pending[i].len;
1892 ssb = ms->pending[i+1].base;
1893 nb = ms->pending[i+1].len;
1894 assert(na > 0 && nb > 0);
1895 assert(ssa.keys + na == ssb.keys);
1896
1897 /* Record the length of the combined runs; if i is the 3rd-last
1898 * run now, also slide over the last run (which isn't involved
1899 * in this merge). The current run i+1 goes away in any case.
1900 */
1901 ms->pending[i].len = na + nb;
1902 if (i == ms->n - 3)
1903 ms->pending[i+1] = ms->pending[i+2];
1904 --ms->n;
1905
1906 /* Where does b start in a? Elements in a before that can be
1907 * ignored (already in place).
1908 */
1909 k = gallop_right(ms, *ssb.keys, ssa.keys, na, 0);
1910 if (k < 0)
1911 return -1;
1912 sortslice_advance(&ssa, k);
1913 na -= k;
1914 if (na == 0)
1915 return 0;
1916
1917 /* Where does a end in b? Elements in b after that can be
1918 * ignored (already in place).
1919 */
1920 nb = gallop_left(ms, ssa.keys[na-1], ssb.keys, nb, nb-1);
1921 if (nb <= 0)
1922 return nb;
1923
1924 /* Merge what remains of the runs, using a temp array with
1925 * min(na, nb) elements.
1926 */
1927 if (na <= nb)
1928 return merge_lo(ms, ssa, na, ssb, nb);
1929 else
1930 return merge_hi(ms, ssa, na, ssb, nb);
1931}
1932
1933/* Examine the stack of runs waiting to be merged, merging adjacent runs
1934 * until the stack invariants are re-established:
1935 *
1936 * 1. len[-3] > len[-2] + len[-1]
1937 * 2. len[-2] > len[-1]
1938 *
1939 * See listsort.txt for more info.
1940 *
1941 * Returns 0 on success, -1 on error.
1942 */
1943static int
1944merge_collapse(MergeState *ms)
1945{
1946 struct s_slice *p = ms->pending;
1947
1948 assert(ms);
1949 while (ms->n > 1) {
1950 Py_ssize_t n = ms->n - 2;
1951 if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) ||
1952 (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) {
1953 if (p[n-1].len < p[n+1].len)
1954 --n;
1955 if (merge_at(ms, n) < 0)
1956 return -1;
1957 }
1958 else if (p[n].len <= p[n+1].len) {
1959 if (merge_at(ms, n) < 0)
1960 return -1;
1961 }
1962 else
1963 break;
1964 }
1965 return 0;
1966}
1967
1968/* Regardless of invariants, merge all runs on the stack until only one
1969 * remains. This is used at the end of the mergesort.
1970 *
1971 * Returns 0 on success, -1 on error.
1972 */
1973static int
1974merge_force_collapse(MergeState *ms)
1975{
1976 struct s_slice *p = ms->pending;
1977
1978 assert(ms);
1979 while (ms->n > 1) {
1980 Py_ssize_t n = ms->n - 2;
1981 if (n > 0 && p[n-1].len < p[n+1].len)
1982 --n;
1983 if (merge_at(ms, n) < 0)
1984 return -1;
1985 }
1986 return 0;
1987}
1988
1989/* Compute a good value for the minimum run length; natural runs shorter
1990 * than this are boosted artificially via binary insertion.
1991 *
1992 * If n < 64, return n (it's too small to bother with fancy stuff).
1993 * Else if n is an exact power of 2, return 32.
1994 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1995 * strictly less than, an exact power of 2.
1996 *
1997 * See listsort.txt for more info.
1998 */
1999static Py_ssize_t
2000merge_compute_minrun(Py_ssize_t n)
2001{
2002 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
2003
2004 assert(n >= 0);
2005 while (n >= 64) {
2006 r |= n & 1;
2007 n >>= 1;
2008 }
2009 return n + r;
2010}
2011
2012static void
2013reverse_sortslice(sortslice *s, Py_ssize_t n)
2014{
2015 reverse_slice(s->keys, &s->keys[n]);
2016 if (s->values != NULL)
2017 reverse_slice(s->values, &s->values[n]);
2018}
2019
2020/* Here we define custom comparison functions to optimize for the cases one commonly
2021 * encounters in practice: homogeneous lists, often of one of the basic types. */
2022
2023/* This struct holds the comparison function and helper functions
2024 * selected in the pre-sort check. */
2025
2026/* These are the special case compare functions.
2027 * ms->key_compare will always point to one of these: */
2028
2029/* Heterogeneous compare: default, always safe to fall back on. */
2030static int
2031safe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
2032{
2033 /* No assumptions necessary! */
2034 return PyObject_RichCompareBool(v, w, Py_LT);
2035}
2036
2037/* Homogeneous compare: safe for any two comparable objects of the same type.
2038 * (ms->key_richcompare is set to ob_type->tp_richcompare in the
2039 * pre-sort check.)
2040 */
2041static int
2042unsafe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
2043{
2044 PyObject *res_obj; int res;
2045
2046 /* No assumptions, because we check first: */
2047 if (Py_TYPE(v)->tp_richcompare != ms->key_richcompare)
2048 return PyObject_RichCompareBool(v, w, Py_LT);
2049
2050 assert(ms->key_richcompare != NULL);
2051 res_obj = (*(ms->key_richcompare))(v, w, Py_LT);
2052
2053 if (res_obj == Py_NotImplemented) {
2054 Py_DECREF(res_obj);
2055 return PyObject_RichCompareBool(v, w, Py_LT);
2056 }
2057 if (res_obj == NULL)
2058 return -1;
2059
2060 if (PyBool_Check(res_obj)) {
2061 res = (res_obj == Py_True);
2062 }
2063 else {
2064 res = PyObject_IsTrue(res_obj);
2065 }
2066 Py_DECREF(res_obj);
2067
2068 /* Note that we can't assert
2069 * res == PyObject_RichCompareBool(v, w, Py_LT);
2070 * because of evil compare functions like this:
2071 * lambda a, b: int(random.random() * 3) - 1)
2072 * (which is actually in test_sort.py) */
2073 return res;
2074}
2075
2076/* Latin string compare: safe for any two latin (one byte per char) strings. */
2077static int
2078unsafe_latin_compare(PyObject *v, PyObject *w, MergeState *ms)
2079{
2080 Py_ssize_t len;
2081 int res;
2082
2083 /* Modified from Objects/unicodeobject.c:unicode_compare, assuming: */
2084 assert(Py_IS_TYPE(v, &PyUnicode_Type));
2085 assert(Py_IS_TYPE(w, &PyUnicode_Type));
2086 assert(PyUnicode_KIND(v) == PyUnicode_KIND(w));
2087 assert(PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
2088
2089 len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
2090 res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);
2091
2092 res = (res != 0 ?
2093 res < 0 :
2094 PyUnicode_GET_LENGTH(v) < PyUnicode_GET_LENGTH(w));
2095
2096 assert(res == PyObject_RichCompareBool(v, w, Py_LT));;
2097 return res;
2098}
2099
2100/* Bounded int compare: compare any two longs that fit in a single machine word. */
2101static int
2102unsafe_long_compare(PyObject *v, PyObject *w, MergeState *ms)
2103{
2104 PyLongObject *vl, *wl; sdigit v0, w0; int res;
2105
2106 /* Modified from Objects/longobject.c:long_compare, assuming: */
2107 assert(Py_IS_TYPE(v, &PyLong_Type));
2108 assert(Py_IS_TYPE(w, &PyLong_Type));
2109 assert(Py_ABS(Py_SIZE(v)) <= 1);
2110 assert(Py_ABS(Py_SIZE(w)) <= 1);
2111
2112 vl = (PyLongObject*)v;
2113 wl = (PyLongObject*)w;
2114
2115 v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->ob_digit[0];
2116 w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->ob_digit[0];
2117
2118 if (Py_SIZE(vl) < 0)
2119 v0 = -v0;
2120 if (Py_SIZE(wl) < 0)
2121 w0 = -w0;
2122
2123 res = v0 < w0;
2124 assert(res == PyObject_RichCompareBool(v, w, Py_LT));
2125 return res;
2126}
2127
2128/* Float compare: compare any two floats. */
2129static int
2130unsafe_float_compare(PyObject *v, PyObject *w, MergeState *ms)
2131{
2132 int res;
2133
2134 /* Modified from Objects/floatobject.c:float_richcompare, assuming: */
2135 assert(Py_IS_TYPE(v, &PyFloat_Type));
2136 assert(Py_IS_TYPE(w, &PyFloat_Type));
2137
2138 res = PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w);
2139 assert(res == PyObject_RichCompareBool(v, w, Py_LT));
2140 return res;
2141}
2142
2143/* Tuple compare: compare *any* two tuples, using
2144 * ms->tuple_elem_compare to compare the first elements, which is set
2145 * using the same pre-sort check as we use for ms->key_compare,
2146 * but run on the list [x[0] for x in L]. This allows us to optimize compares
2147 * on two levels (as long as [x[0] for x in L] is type-homogeneous.) The idea is
2148 * that most tuple compares don't involve x[1:]. */
2149static int
2150unsafe_tuple_compare(PyObject *v, PyObject *w, MergeState *ms)
2151{
2152 PyTupleObject *vt, *wt;
2153 Py_ssize_t i, vlen, wlen;
2154 int k;
2155
2156 /* Modified from Objects/tupleobject.c:tuplerichcompare, assuming: */
2157 assert(Py_IS_TYPE(v, &PyTuple_Type));
2158 assert(Py_IS_TYPE(w, &PyTuple_Type));
2159 assert(Py_SIZE(v) > 0);
2160 assert(Py_SIZE(w) > 0);
2161
2162 vt = (PyTupleObject *)v;
2163 wt = (PyTupleObject *)w;
2164
2165 vlen = Py_SIZE(vt);
2166 wlen = Py_SIZE(wt);
2167
2168 for (i = 0; i < vlen && i < wlen; i++) {
2169 k = PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_EQ);
2170 if (k < 0)
2171 return -1;
2172 if (!k)
2173 break;
2174 }
2175
2176 if (i >= vlen || i >= wlen)
2177 return vlen < wlen;
2178
2179 if (i == 0)
2180 return ms->tuple_elem_compare(vt->ob_item[i], wt->ob_item[i], ms);
2181 else
2182 return PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_LT);
2183}
2184
2185/* An adaptive, stable, natural mergesort. See listsort.txt.
2186 * Returns Py_None on success, NULL on error. Even in case of error, the
2187 * list will be some permutation of its input state (nothing is lost or
2188 * duplicated).
2189 */
2190/*[clinic input]
2191list.sort
2192
2193 *
2194 key as keyfunc: object = None
2195 reverse: bool(accept={int}) = False
2196
2197Sort the list in ascending order and return None.
2198
2199The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
2200order of two equal elements is maintained).
2201
2202If a key function is given, apply it once to each list item and sort them,
2203ascending or descending, according to their function values.
2204
2205The reverse flag can be set to sort in descending order.
2206[clinic start generated code]*/
2207
2208static PyObject *
2209list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
2210/*[clinic end generated code: output=57b9f9c5e23fbe42 input=cb56cd179a713060]*/
2211{
2212 MergeState ms;
2213 Py_ssize_t nremaining;
2214 Py_ssize_t minrun;
2215 sortslice lo;
2216 Py_ssize_t saved_ob_size, saved_allocated;
2217 PyObject **saved_ob_item;
2218 PyObject **final_ob_item;
2219 PyObject *result = NULL; /* guilty until proved innocent */
2220 Py_ssize_t i;
2221 PyObject **keys;
2222
2223 assert(self != NULL);
2224 assert(PyList_Check(self));
2225 if (keyfunc == Py_None)
2226 keyfunc = NULL;
2227
2228 /* The list is temporarily made empty, so that mutations performed
2229 * by comparison functions can't affect the slice of memory we're
2230 * sorting (allowing mutations during sorting is a core-dump
2231 * factory, since ob_item may change).
2232 */
2233 saved_ob_size = Py_SIZE(self);
2234 saved_ob_item = self->ob_item;
2235 saved_allocated = self->allocated;
2236 Py_SET_SIZE(self, 0);
2237 self->ob_item = NULL;
2238 self->allocated = -1; /* any operation will reset it to >= 0 */
2239
2240 if (keyfunc == NULL) {
2241 keys = NULL;
2242 lo.keys = saved_ob_item;
2243 lo.values = NULL;
2244 }
2245 else {
2246 if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
2247 /* Leverage stack space we allocated but won't otherwise use */
2248 keys = &ms.temparray[saved_ob_size+1];
2249 else {
2250 keys = PyMem_Malloc(sizeof(PyObject *) * saved_ob_size);
2251 if (keys == NULL) {
2252 PyErr_NoMemory();
2253 goto keyfunc_fail;
2254 }
2255 }
2256
2257 for (i = 0; i < saved_ob_size ; i++) {
2258 keys[i] = PyObject_CallOneArg(keyfunc, saved_ob_item[i]);
2259 if (keys[i] == NULL) {
2260 for (i=i-1 ; i>=0 ; i--)
2261 Py_DECREF(keys[i]);
2262 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
2263 PyMem_Free(keys);
2264 goto keyfunc_fail;
2265 }
2266 }
2267
2268 lo.keys = keys;
2269 lo.values = saved_ob_item;
2270 }
2271
2272
2273 /* The pre-sort check: here's where we decide which compare function to use.
2274 * How much optimization is safe? We test for homogeneity with respect to
2275 * several properties that are expensive to check at compare-time, and
2276 * set ms appropriately. */
2277 if (saved_ob_size > 1) {
2278 /* Assume the first element is representative of the whole list. */
2279 int keys_are_in_tuples = (Py_IS_TYPE(lo.keys[0], &PyTuple_Type) &&
2280 Py_SIZE(lo.keys[0]) > 0);
2281
2282 PyTypeObject* key_type = (keys_are_in_tuples ?
2283 Py_TYPE(PyTuple_GET_ITEM(lo.keys[0], 0)) :
2284 Py_TYPE(lo.keys[0]));
2285
2286 int keys_are_all_same_type = 1;
2287 int strings_are_latin = 1;
2288 int ints_are_bounded = 1;
2289
2290 /* Prove that assumption by checking every key. */
2291 for (i=0; i < saved_ob_size; i++) {
2292
2293 if (keys_are_in_tuples &&
2294 !(Py_IS_TYPE(lo.keys[i], &PyTuple_Type) && Py_SIZE(lo.keys[i]) != 0)) {
2295 keys_are_in_tuples = 0;
2296 keys_are_all_same_type = 0;
2297 break;
2298 }
2299
2300 /* Note: for lists of tuples, key is the first element of the tuple
2301 * lo.keys[i], not lo.keys[i] itself! We verify type-homogeneity
2302 * for lists of tuples in the if-statement directly above. */
2303 PyObject *key = (keys_are_in_tuples ?
2304 PyTuple_GET_ITEM(lo.keys[i], 0) :
2305 lo.keys[i]);
2306
2307 if (!Py_IS_TYPE(key, key_type)) {
2308 keys_are_all_same_type = 0;
2309 /* If keys are in tuple we must loop over the whole list to make
2310 sure all items are tuples */
2311 if (!keys_are_in_tuples) {
2312 break;
2313 }
2314 }
2315
2316 if (keys_are_all_same_type) {
2317 if (key_type == &PyLong_Type &&
2318 ints_are_bounded &&
2319 Py_ABS(Py_SIZE(key)) > 1) {
2320
2321 ints_are_bounded = 0;
2322 }
2323 else if (key_type == &PyUnicode_Type &&
2324 strings_are_latin &&
2325 PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND) {
2326
2327 strings_are_latin = 0;
2328 }
2329 }
2330 }
2331
2332 /* Choose the best compare, given what we now know about the keys. */
2333 if (keys_are_all_same_type) {
2334
2335 if (key_type == &PyUnicode_Type && strings_are_latin) {
2336 ms.key_compare = unsafe_latin_compare;
2337 }
2338 else if (key_type == &PyLong_Type && ints_are_bounded) {
2339 ms.key_compare = unsafe_long_compare;
2340 }
2341 else if (key_type == &PyFloat_Type) {
2342 ms.key_compare = unsafe_float_compare;
2343 }
2344 else if ((ms.key_richcompare = key_type->tp_richcompare) != NULL) {
2345 ms.key_compare = unsafe_object_compare;
2346 }
2347 else {
2348 ms.key_compare = safe_object_compare;
2349 }
2350 }
2351 else {
2352 ms.key_compare = safe_object_compare;
2353 }
2354
2355 if (keys_are_in_tuples) {
2356 /* Make sure we're not dealing with tuples of tuples
2357 * (remember: here, key_type refers list [key[0] for key in keys]) */
2358 if (key_type == &PyTuple_Type) {
2359 ms.tuple_elem_compare = safe_object_compare;
2360 }
2361 else {
2362 ms.tuple_elem_compare = ms.key_compare;
2363 }
2364
2365 ms.key_compare = unsafe_tuple_compare;
2366 }
2367 }
2368 /* End of pre-sort check: ms is now set properly! */
2369
2370 merge_init(&ms, saved_ob_size, keys != NULL);
2371
2372 nremaining = saved_ob_size;
2373 if (nremaining < 2)
2374 goto succeed;
2375
2376 /* Reverse sort stability achieved by initially reversing the list,
2377 applying a stable forward sort, then reversing the final result. */
2378 if (reverse) {
2379 if (keys != NULL)
2380 reverse_slice(&keys[0], &keys[saved_ob_size]);
2381 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
2382 }
2383
2384 /* March over the array once, left to right, finding natural runs,
2385 * and extending short natural runs to minrun elements.
2386 */
2387 minrun = merge_compute_minrun(nremaining);
2388 do {
2389 int descending;
2390 Py_ssize_t n;
2391
2392 /* Identify next run. */
2393 n = count_run(&ms, lo.keys, lo.keys + nremaining, &descending);
2394 if (n < 0)
2395 goto fail;
2396 if (descending)
2397 reverse_sortslice(&lo, n);
2398 /* If short, extend to min(minrun, nremaining). */
2399 if (n < minrun) {
2400 const Py_ssize_t force = nremaining <= minrun ?
2401 nremaining : minrun;
2402 if (binarysort(&ms, lo, lo.keys + force, lo.keys + n) < 0)
2403 goto fail;
2404 n = force;
2405 }
2406 /* Push run onto pending-runs stack, and maybe merge. */
2407 assert(ms.n < MAX_MERGE_PENDING);
2408 ms.pending[ms.n].base = lo;
2409 ms.pending[ms.n].len = n;
2410 ++ms.n;
2411 if (merge_collapse(&ms) < 0)
2412 goto fail;
2413 /* Advance to find next run. */
2414 sortslice_advance(&lo, n);
2415 nremaining -= n;
2416 } while (nremaining);
2417
2418 if (merge_force_collapse(&ms) < 0)
2419 goto fail;
2420 assert(ms.n == 1);
2421 assert(keys == NULL
2422 ? ms.pending[0].base.keys == saved_ob_item
2423 : ms.pending[0].base.keys == &keys[0]);
2424 assert(ms.pending[0].len == saved_ob_size);
2425 lo = ms.pending[0].base;
2426
2427succeed:
2428 result = Py_None;
2429fail:
2430 if (keys != NULL) {
2431 for (i = 0; i < saved_ob_size; i++)
2432 Py_DECREF(keys[i]);
2433 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
2434 PyMem_Free(keys);
2435 }
2436
2437 if (self->allocated != -1 && result != NULL) {
2438 /* The user mucked with the list during the sort,
2439 * and we don't already have another error to report.
2440 */
2441 PyErr_SetString(PyExc_ValueError, "list modified during sort");
2442 result = NULL;
2443 }
2444
2445 if (reverse && saved_ob_size > 1)
2446 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
2447
2448 merge_freemem(&ms);
2449
2450keyfunc_fail:
2451 final_ob_item = self->ob_item;
2452 i = Py_SIZE(self);
2453 Py_SET_SIZE(self, saved_ob_size);
2454 self->ob_item = saved_ob_item;
2455 self->allocated = saved_allocated;
2456 if (final_ob_item != NULL) {
2457 /* we cannot use _list_clear() for this because it does not
2458 guarantee that the list is really empty when it returns */
2459 while (--i >= 0) {
2460 Py_XDECREF(final_ob_item[i]);
2461 }
2462 PyMem_Free(final_ob_item);
2463 }
2464 Py_XINCREF(result);
2465 return result;
2466}
2467#undef IFLT
2468#undef ISLT
2469
2470int
2471PyList_Sort(PyObject *v)
2472{
2473 if (v == NULL || !PyList_Check(v)) {
2474 PyErr_BadInternalCall();
2475 return -1;
2476 }
2477 v = list_sort_impl((PyListObject *)v, NULL, 0);
2478 if (v == NULL)
2479 return -1;
2480 Py_DECREF(v);
2481 return 0;
2482}
2483
2484/*[clinic input]
2485list.reverse
2486
2487Reverse *IN PLACE*.
2488[clinic start generated code]*/
2489
2490static PyObject *
2491list_reverse_impl(PyListObject *self)
2492/*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
2493{
2494 if (Py_SIZE(self) > 1)
2495 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2496 Py_RETURN_NONE;
2497}
2498
2499int
2500PyList_Reverse(PyObject *v)
2501{
2502 PyListObject *self = (PyListObject *)v;
2503
2504 if (v == NULL || !PyList_Check(v)) {
2505 PyErr_BadInternalCall();
2506 return -1;
2507 }
2508 if (Py_SIZE(self) > 1)
2509 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2510 return 0;
2511}
2512
2513PyObject *
2514PyList_AsTuple(PyObject *v)
2515{
2516 if (v == NULL || !PyList_Check(v)) {
2517 PyErr_BadInternalCall();
2518 return NULL;
2519 }
2520 return _PyTuple_FromArray(((PyListObject *)v)->ob_item, Py_SIZE(v));
2521}
2522
2523/*[clinic input]
2524list.index
2525
2526 value: object
2527 start: slice_index(accept={int}) = 0
2528 stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
2529 /
2530
2531Return first index of value.
2532
2533Raises ValueError if the value is not present.
2534[clinic start generated code]*/
2535
2536static PyObject *
2537list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
2538 Py_ssize_t stop)
2539/*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
2540{
2541 Py_ssize_t i;
2542
2543 if (start < 0) {
2544 start += Py_SIZE(self);
2545 if (start < 0)
2546 start = 0;
2547 }
2548 if (stop < 0) {
2549 stop += Py_SIZE(self);
2550 if (stop < 0)
2551 stop = 0;
2552 }
2553 for (i = start; i < stop && i < Py_SIZE(self); i++) {
2554 PyObject *obj = self->ob_item[i];
2555 Py_INCREF(obj);
2556 int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2557 Py_DECREF(obj);
2558 if (cmp > 0)
2559 return PyLong_FromSsize_t(i);
2560 else if (cmp < 0)
2561 return NULL;
2562 }
2563 PyErr_Format(PyExc_ValueError, "%R is not in list", value);
2564 return NULL;
2565}
2566
2567/*[clinic input]
2568list.count
2569
2570 value: object
2571 /
2572
2573Return number of occurrences of value.
2574[clinic start generated code]*/
2575
2576static PyObject *
2577list_count(PyListObject *self, PyObject *value)
2578/*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
2579{
2580 Py_ssize_t count = 0;
2581 Py_ssize_t i;
2582
2583 for (i = 0; i < Py_SIZE(self); i++) {
2584 PyObject *obj = self->ob_item[i];
2585 if (obj == value) {
2586 count++;
2587 continue;
2588 }
2589 Py_INCREF(obj);
2590 int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2591 Py_DECREF(obj);
2592 if (cmp > 0)
2593 count++;
2594 else if (cmp < 0)
2595 return NULL;
2596 }
2597 return PyLong_FromSsize_t(count);
2598}
2599
2600/*[clinic input]
2601list.remove
2602
2603 value: object
2604 /
2605
2606Remove first occurrence of value.
2607
2608Raises ValueError if the value is not present.
2609[clinic start generated code]*/
2610
2611static PyObject *
2612list_remove(PyListObject *self, PyObject *value)
2613/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
2614{
2615 Py_ssize_t i;
2616
2617 for (i = 0; i < Py_SIZE(self); i++) {
2618 PyObject *obj = self->ob_item[i];
2619 Py_INCREF(obj);
2620 int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2621 Py_DECREF(obj);
2622 if (cmp > 0) {
2623 if (list_ass_slice(self, i, i+1,
2624 (PyObject *)NULL) == 0)
2625 Py_RETURN_NONE;
2626 return NULL;
2627 }
2628 else if (cmp < 0)
2629 return NULL;
2630 }
2631 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
2632 return NULL;
2633}
2634
2635static int
2636list_traverse(PyListObject *o, visitproc visit, void *arg)
2637{
2638 Py_ssize_t i;
2639
2640 for (i = Py_SIZE(o); --i >= 0; )
2641 Py_VISIT(o->ob_item[i]);
2642 return 0;
2643}
2644
2645static PyObject *
2646list_richcompare(PyObject *v, PyObject *w, int op)
2647{
2648 PyListObject *vl, *wl;
2649 Py_ssize_t i;
2650
2651 if (!PyList_Check(v) || !PyList_Check(w))
2652 Py_RETURN_NOTIMPLEMENTED;
2653
2654 vl = (PyListObject *)v;
2655 wl = (PyListObject *)w;
2656
2657 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
2658 /* Shortcut: if the lengths differ, the lists differ */
2659 if (op == Py_EQ)
2660 Py_RETURN_FALSE;
2661 else
2662 Py_RETURN_TRUE;
2663 }
2664
2665 /* Search for the first index where items are different */
2666 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
2667 PyObject *vitem = vl->ob_item[i];
2668 PyObject *witem = wl->ob_item[i];
2669 if (vitem == witem) {
2670 continue;
2671 }
2672
2673 Py_INCREF(vitem);
2674 Py_INCREF(witem);
2675 int k = PyObject_RichCompareBool(vitem, witem, Py_EQ);
2676 Py_DECREF(vitem);
2677 Py_DECREF(witem);
2678 if (k < 0)
2679 return NULL;
2680 if (!k)
2681 break;
2682 }
2683
2684 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
2685 /* No more items to compare -- compare sizes */
2686 Py_RETURN_RICHCOMPARE(Py_SIZE(vl), Py_SIZE(wl), op);
2687 }
2688
2689 /* We have an item that differs -- shortcuts for EQ/NE */
2690 if (op == Py_EQ) {
2691 Py_RETURN_FALSE;
2692 }
2693 if (op == Py_NE) {
2694 Py_RETURN_TRUE;
2695 }
2696
2697 /* Compare the final item again using the proper operator */
2698 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
2699}
2700
2701/*[clinic input]
2702list.__init__
2703
2704 iterable: object(c_default="NULL") = ()
2705 /
2706
2707Built-in mutable sequence.
2708
2709If no argument is given, the constructor creates a new empty list.
2710The argument must be an iterable if specified.
2711[clinic start generated code]*/
2712
2713static int
2714list___init___impl(PyListObject *self, PyObject *iterable)
2715/*[clinic end generated code: output=0f3c21379d01de48 input=b3f3fe7206af8f6b]*/
2716{
2717 /* Verify list invariants established by PyType_GenericAlloc() */
2718 assert(0 <= Py_SIZE(self));
2719 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
2720 assert(self->ob_item != NULL ||
2721 self->allocated == 0 || self->allocated == -1);
2722
2723 /* Empty previous contents */
2724 if (self->ob_item != NULL) {
2725 (void)_list_clear(self);
2726 }
2727 if (iterable != NULL) {
2728 PyObject *rv = list_extend(self, iterable);
2729 if (rv == NULL)
2730 return -1;
2731 Py_DECREF(rv);
2732 }
2733 return 0;
2734}
2735
2736static PyObject *
2737list_vectorcall(PyObject *type, PyObject * const*args,
2738 size_t nargsf, PyObject *kwnames)
2739{
2740 if (!_PyArg_NoKwnames("list", kwnames)) {
2741 return NULL;
2742 }
2743 Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
2744 if (!_PyArg_CheckPositional("list", nargs, 0, 1)) {
2745 return NULL;
2746 }
2747
2748 assert(PyType_Check(type));
2749 PyObject *list = PyType_GenericAlloc((PyTypeObject *)type, 0);
2750 if (list == NULL) {
2751 return NULL;
2752 }
2753 if (nargs) {
2754 if (list___init___impl((PyListObject *)list, args[0])) {
2755 Py_DECREF(list);
2756 return NULL;
2757 }
2758 }
2759 return list;
2760}
2761
2762
2763/*[clinic input]
2764list.__sizeof__
2765
2766Return the size of the list in memory, in bytes.
2767[clinic start generated code]*/
2768
2769static PyObject *
2770list___sizeof___impl(PyListObject *self)
2771/*[clinic end generated code: output=3417541f95f9a53e input=b8030a5d5ce8a187]*/
2772{
2773 Py_ssize_t res;
2774
2775 res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
2776 return PyLong_FromSsize_t(res);
2777}
2778
2779static PyObject *list_iter(PyObject *seq);
2780static PyObject *list_subscript(PyListObject*, PyObject*);
2781
2782static PyMethodDef list_methods[] = {
2783 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, "x.__getitem__(y) <==> x[y]"},
2784 LIST___REVERSED___METHODDEF
2785 LIST___SIZEOF___METHODDEF
2786 LIST_CLEAR_METHODDEF
2787 LIST_COPY_METHODDEF
2788 LIST_APPEND_METHODDEF
2789 LIST_INSERT_METHODDEF
2790 LIST_EXTEND_METHODDEF
2791 LIST_POP_METHODDEF
2792 LIST_REMOVE_METHODDEF
2793 LIST_INDEX_METHODDEF
2794 LIST_COUNT_METHODDEF
2795 LIST_REVERSE_METHODDEF
2796 LIST_SORT_METHODDEF
2797 {"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
2798 {NULL, NULL} /* sentinel */
2799};
2800
2801static PySequenceMethods list_as_sequence = {
2802 (lenfunc)list_length, /* sq_length */
2803 (binaryfunc)list_concat, /* sq_concat */
2804 (ssizeargfunc)list_repeat, /* sq_repeat */
2805 (ssizeargfunc)list_item, /* sq_item */
2806 0, /* sq_slice */
2807 (ssizeobjargproc)list_ass_item, /* sq_ass_item */
2808 0, /* sq_ass_slice */
2809 (objobjproc)list_contains, /* sq_contains */
2810 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
2811 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
2812};
2813
2814static PyObject *
2815list_subscript(PyListObject* self, PyObject* item)
2816{
2817 if (_PyIndex_Check(item)) {
2818 Py_ssize_t i;
2819 i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2820 if (i == -1 && PyErr_Occurred())
2821 return NULL;
2822 if (i < 0)
2823 i += PyList_GET_SIZE(self);
2824 return list_item(self, i);
2825 }
2826 else if (PySlice_Check(item)) {
2827 Py_ssize_t start, stop, step, slicelength, i;
2828 size_t cur;
2829 PyObject* result;
2830 PyObject* it;
2831 PyObject **src, **dest;
2832
2833 if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2834 return NULL;
2835 }
2836 slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2837 step);
2838
2839 if (slicelength <= 0) {
2840 return PyList_New(0);
2841 }
2842 else if (step == 1) {
2843 return list_slice(self, start, stop);
2844 }
2845 else {
2846 result = list_new_prealloc(slicelength);
2847 if (!result) return NULL;
2848
2849 src = self->ob_item;
2850 dest = ((PyListObject *)result)->ob_item;
2851 for (cur = start, i = 0; i < slicelength;
2852 cur += (size_t)step, i++) {
2853 it = src[cur];
2854 Py_INCREF(it);
2855 dest[i] = it;
2856 }
2857 Py_SET_SIZE(result, slicelength);
2858 return result;
2859 }
2860 }
2861 else {
2862 PyErr_Format(PyExc_TypeError,
2863 "list indices must be integers or slices, not %.200s",
2864 Py_TYPE(item)->tp_name);
2865 return NULL;
2866 }
2867}
2868
2869static int
2870list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2871{
2872 if (_PyIndex_Check(item)) {
2873 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2874 if (i == -1 && PyErr_Occurred())
2875 return -1;
2876 if (i < 0)
2877 i += PyList_GET_SIZE(self);
2878 return list_ass_item(self, i, value);
2879 }
2880 else if (PySlice_Check(item)) {
2881 Py_ssize_t start, stop, step, slicelength;
2882
2883 if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2884 return -1;
2885 }
2886 slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2887 step);
2888
2889 if (step == 1)
2890 return list_ass_slice(self, start, stop, value);
2891
2892 /* Make sure s[5:2] = [..] inserts at the right place:
2893 before 5, not before 2. */
2894 if ((step < 0 && start < stop) ||
2895 (step > 0 && start > stop))
2896 stop = start;
2897
2898 if (value == NULL) {
2899 /* delete slice */
2900 PyObject **garbage;
2901 size_t cur;
2902 Py_ssize_t i;
2903 int res;
2904
2905 if (slicelength <= 0)
2906 return 0;
2907
2908 if (step < 0) {
2909 stop = start + 1;
2910 start = stop + step*(slicelength - 1) - 1;
2911 step = -step;
2912 }
2913
2914 garbage = (PyObject**)
2915 PyMem_Malloc(slicelength*sizeof(PyObject*));
2916 if (!garbage) {
2917 PyErr_NoMemory();
2918 return -1;
2919 }
2920
2921 /* drawing pictures might help understand these for
2922 loops. Basically, we memmove the parts of the
2923 list that are *not* part of the slice: step-1
2924 items for each item that is part of the slice,
2925 and then tail end of the list that was not
2926 covered by the slice */
2927 for (cur = start, i = 0;
2928 cur < (size_t)stop;
2929 cur += step, i++) {
2930 Py_ssize_t lim = step - 1;
2931
2932 garbage[i] = PyList_GET_ITEM(self, cur);
2933
2934 if (cur + step >= (size_t)Py_SIZE(self)) {
2935 lim = Py_SIZE(self) - cur - 1;
2936 }
2937
2938 memmove(self->ob_item + cur - i,
2939 self->ob_item + cur + 1,
2940 lim * sizeof(PyObject *));
2941 }
2942 cur = start + (size_t)slicelength * step;
2943 if (cur < (size_t)Py_SIZE(self)) {
2944 memmove(self->ob_item + cur - slicelength,
2945 self->ob_item + cur,
2946 (Py_SIZE(self) - cur) *
2947 sizeof(PyObject *));
2948 }
2949
2950 Py_SET_SIZE(self, Py_SIZE(self) - slicelength);
2951 res = list_resize(self, Py_SIZE(self));
2952
2953 for (i = 0; i < slicelength; i++) {
2954 Py_DECREF(garbage[i]);
2955 }
2956 PyMem_Free(garbage);
2957
2958 return res;
2959 }
2960 else {
2961 /* assign slice */
2962 PyObject *ins, *seq;
2963 PyObject **garbage, **seqitems, **selfitems;
2964 Py_ssize_t i;
2965 size_t cur;
2966
2967 /* protect against a[::-1] = a */
2968 if (self == (PyListObject*)value) {
2969 seq = list_slice((PyListObject*)value, 0,
2970 PyList_GET_SIZE(value));
2971 }
2972 else {
2973 seq = PySequence_Fast(value,
2974 "must assign iterable "
2975 "to extended slice");
2976 }
2977 if (!seq)
2978 return -1;
2979
2980 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2981 PyErr_Format(PyExc_ValueError,
2982 "attempt to assign sequence of "
2983 "size %zd to extended slice of "
2984 "size %zd",
2985 PySequence_Fast_GET_SIZE(seq),
2986 slicelength);
2987 Py_DECREF(seq);
2988 return -1;
2989 }
2990
2991 if (!slicelength) {
2992 Py_DECREF(seq);
2993 return 0;
2994 }
2995
2996 garbage = (PyObject**)
2997 PyMem_Malloc(slicelength*sizeof(PyObject*));
2998 if (!garbage) {
2999 Py_DECREF(seq);
3000 PyErr_NoMemory();
3001 return -1;
3002 }
3003
3004 selfitems = self->ob_item;
3005 seqitems = PySequence_Fast_ITEMS(seq);
3006 for (cur = start, i = 0; i < slicelength;
3007 cur += (size_t)step, i++) {
3008 garbage[i] = selfitems[cur];
3009 ins = seqitems[i];
3010 Py_INCREF(ins);
3011 selfitems[cur] = ins;
3012 }
3013
3014 for (i = 0; i < slicelength; i++) {
3015 Py_DECREF(garbage[i]);
3016 }
3017
3018 PyMem_Free(garbage);
3019 Py_DECREF(seq);
3020
3021 return 0;
3022 }
3023 }
3024 else {
3025 PyErr_Format(PyExc_TypeError,
3026 "list indices must be integers or slices, not %.200s",
3027 Py_TYPE(item)->tp_name);
3028 return -1;
3029 }
3030}
3031
3032static PyMappingMethods list_as_mapping = {
3033 (lenfunc)list_length,
3034 (binaryfunc)list_subscript,
3035 (objobjargproc)list_ass_subscript
3036};
3037
3038PyTypeObject PyList_Type = {
3039 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3040 "list",
3041 sizeof(PyListObject),
3042 0,
3043 (destructor)list_dealloc, /* tp_dealloc */
3044 0, /* tp_vectorcall_offset */
3045 0, /* tp_getattr */
3046 0, /* tp_setattr */
3047 0, /* tp_as_async */
3048 (reprfunc)list_repr, /* tp_repr */
3049 0, /* tp_as_number */
3050 &list_as_sequence, /* tp_as_sequence */
3051 &list_as_mapping, /* tp_as_mapping */
3052 PyObject_HashNotImplemented, /* tp_hash */
3053 0, /* tp_call */
3054 0, /* tp_str */
3055 PyObject_GenericGetAttr, /* tp_getattro */
3056 0, /* tp_setattro */
3057 0, /* tp_as_buffer */
3058 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3059 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS |
3060 _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE, /* tp_flags */
3061 list___init____doc__, /* tp_doc */
3062 (traverseproc)list_traverse, /* tp_traverse */
3063 (inquiry)_list_clear, /* tp_clear */
3064 list_richcompare, /* tp_richcompare */
3065 0, /* tp_weaklistoffset */
3066 list_iter, /* tp_iter */
3067 0, /* tp_iternext */
3068 list_methods, /* tp_methods */
3069 0, /* tp_members */
3070 0, /* tp_getset */
3071 0, /* tp_base */
3072 0, /* tp_dict */
3073 0, /* tp_descr_get */
3074 0, /* tp_descr_set */
3075 0, /* tp_dictoffset */
3076 (initproc)list___init__, /* tp_init */
3077 PyType_GenericAlloc, /* tp_alloc */
3078 PyType_GenericNew, /* tp_new */
3079 PyObject_GC_Del, /* tp_free */
3080 .tp_vectorcall = list_vectorcall,
3081};
3082
3083/*********************** List Iterator **************************/
3084
3085typedef struct {
3086 PyObject_HEAD
3087 Py_ssize_t it_index;
3088 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
3089} listiterobject;
3090
3091static void listiter_dealloc(listiterobject *);
3092static int listiter_traverse(listiterobject *, visitproc, void *);
3093static PyObject *listiter_next(listiterobject *);
3094static PyObject *listiter_len(listiterobject *, PyObject *);
3095static PyObject *listiter_reduce_general(void *_it, int forward);
3096static PyObject *listiter_reduce(listiterobject *, PyObject *);
3097static PyObject *listiter_setstate(listiterobject *, PyObject *state);
3098
3099PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
3100PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
3101PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
3102
3103static PyMethodDef listiter_methods[] = {
3104 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
3105 {"__reduce__", (PyCFunction)listiter_reduce, METH_NOARGS, reduce_doc},
3106 {"__setstate__", (PyCFunction)listiter_setstate, METH_O, setstate_doc},
3107 {NULL, NULL} /* sentinel */
3108};
3109
3110PyTypeObject PyListIter_Type = {
3111 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3112 "list_iterator", /* tp_name */
3113 sizeof(listiterobject), /* tp_basicsize */
3114 0, /* tp_itemsize */
3115 /* methods */
3116 (destructor)listiter_dealloc, /* tp_dealloc */
3117 0, /* tp_vectorcall_offset */
3118 0, /* tp_getattr */
3119 0, /* tp_setattr */
3120 0, /* tp_as_async */
3121 0, /* tp_repr */
3122 0, /* tp_as_number */
3123 0, /* tp_as_sequence */
3124 0, /* tp_as_mapping */
3125 0, /* tp_hash */
3126 0, /* tp_call */
3127 0, /* tp_str */
3128 PyObject_GenericGetAttr, /* tp_getattro */
3129 0, /* tp_setattro */
3130 0, /* tp_as_buffer */
3131 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3132 0, /* tp_doc */
3133 (traverseproc)listiter_traverse, /* tp_traverse */
3134 0, /* tp_clear */
3135 0, /* tp_richcompare */
3136 0, /* tp_weaklistoffset */
3137 PyObject_SelfIter, /* tp_iter */
3138 (iternextfunc)listiter_next, /* tp_iternext */
3139 listiter_methods, /* tp_methods */
3140 0, /* tp_members */
3141};
3142
3143
3144static PyObject *
3145list_iter(PyObject *seq)
3146{
3147 listiterobject *it;
3148
3149 if (!PyList_Check(seq)) {
3150 PyErr_BadInternalCall();
3151 return NULL;
3152 }
3153 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
3154 if (it == NULL)
3155 return NULL;
3156 it->it_index = 0;
3157 Py_INCREF(seq);
3158 it->it_seq = (PyListObject *)seq;
3159 _PyObject_GC_TRACK(it);
3160 return (PyObject *)it;
3161}
3162
3163static void
3164listiter_dealloc(listiterobject *it)
3165{
3166 _PyObject_GC_UNTRACK(it);
3167 Py_XDECREF(it->it_seq);
3168 PyObject_GC_Del(it);
3169}
3170
3171static int
3172listiter_traverse(listiterobject *it, visitproc visit, void *arg)
3173{
3174 Py_VISIT(it->it_seq);
3175 return 0;
3176}
3177
3178static PyObject *
3179listiter_next(listiterobject *it)
3180{
3181 PyListObject *seq;
3182 PyObject *item;
3183
3184 assert(it != NULL);
3185 seq = it->it_seq;
3186 if (seq == NULL)
3187 return NULL;
3188 assert(PyList_Check(seq));
3189
3190 if (it->it_index < PyList_GET_SIZE(seq)) {
3191 item = PyList_GET_ITEM(seq, it->it_index);
3192 ++it->it_index;
3193 Py_INCREF(item);
3194 return item;
3195 }
3196
3197 it->it_seq = NULL;
3198 Py_DECREF(seq);
3199 return NULL;
3200}
3201
3202static PyObject *
3203listiter_len(listiterobject *it, PyObject *Py_UNUSED(ignored))
3204{
3205 Py_ssize_t len;
3206 if (it->it_seq) {
3207 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
3208 if (len >= 0)
3209 return PyLong_FromSsize_t(len);
3210 }
3211 return PyLong_FromLong(0);
3212}
3213
3214static PyObject *
3215listiter_reduce(listiterobject *it, PyObject *Py_UNUSED(ignored))
3216{
3217 return listiter_reduce_general(it, 1);
3218}
3219
3220static PyObject *
3221listiter_setstate(listiterobject *it, PyObject *state)
3222{
3223 Py_ssize_t index = PyLong_AsSsize_t(state);
3224 if (index == -1 && PyErr_Occurred())
3225 return NULL;
3226 if (it->it_seq != NULL) {
3227 if (index < 0)
3228 index = 0;
3229 else if (index > PyList_GET_SIZE(it->it_seq))
3230 index = PyList_GET_SIZE(it->it_seq); /* iterator exhausted */
3231 it->it_index = index;
3232 }
3233 Py_RETURN_NONE;
3234}
3235
3236/*********************** List Reverse Iterator **************************/
3237
3238typedef struct {
3239 PyObject_HEAD
3240 Py_ssize_t it_index;
3241 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
3242} listreviterobject;
3243
3244static void listreviter_dealloc(listreviterobject *);
3245static int listreviter_traverse(listreviterobject *, visitproc, void *);
3246static PyObject *listreviter_next(listreviterobject *);
3247static PyObject *listreviter_len(listreviterobject *, PyObject *);
3248static PyObject *listreviter_reduce(listreviterobject *, PyObject *);
3249static PyObject *listreviter_setstate(listreviterobject *, PyObject *);
3250
3251static PyMethodDef listreviter_methods[] = {
3252 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
3253 {"__reduce__", (PyCFunction)listreviter_reduce, METH_NOARGS, reduce_doc},
3254 {"__setstate__", (PyCFunction)listreviter_setstate, METH_O, setstate_doc},
3255 {NULL, NULL} /* sentinel */
3256};
3257
3258PyTypeObject PyListRevIter_Type = {
3259 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3260 "list_reverseiterator", /* tp_name */
3261 sizeof(listreviterobject), /* tp_basicsize */
3262 0, /* tp_itemsize */
3263 /* methods */
3264 (destructor)listreviter_dealloc, /* tp_dealloc */
3265 0, /* tp_vectorcall_offset */
3266 0, /* tp_getattr */
3267 0, /* tp_setattr */
3268 0, /* tp_as_async */
3269 0, /* tp_repr */
3270 0, /* tp_as_number */
3271 0, /* tp_as_sequence */
3272 0, /* tp_as_mapping */
3273 0, /* tp_hash */
3274 0, /* tp_call */
3275 0, /* tp_str */
3276 PyObject_GenericGetAttr, /* tp_getattro */
3277 0, /* tp_setattro */
3278 0, /* tp_as_buffer */
3279 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3280 0, /* tp_doc */
3281 (traverseproc)listreviter_traverse, /* tp_traverse */
3282 0, /* tp_clear */
3283 0, /* tp_richcompare */
3284 0, /* tp_weaklistoffset */
3285 PyObject_SelfIter, /* tp_iter */
3286 (iternextfunc)listreviter_next, /* tp_iternext */
3287 listreviter_methods, /* tp_methods */
3288 0,
3289};
3290
3291/*[clinic input]
3292list.__reversed__
3293
3294Return a reverse iterator over the list.
3295[clinic start generated code]*/
3296
3297static PyObject *
3298list___reversed___impl(PyListObject *self)
3299/*[clinic end generated code: output=b166f073208c888c input=eadb6e17f8a6a280]*/
3300{
3301 listreviterobject *it;
3302
3303 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
3304 if (it == NULL)
3305 return NULL;
3306 assert(PyList_Check(self));
3307 it->it_index = PyList_GET_SIZE(self) - 1;
3308 Py_INCREF(self);
3309 it->it_seq = self;
3310 PyObject_GC_Track(it);
3311 return (PyObject *)it;
3312}
3313
3314static void
3315listreviter_dealloc(listreviterobject *it)
3316{
3317 PyObject_GC_UnTrack(it);
3318 Py_XDECREF(it->it_seq);
3319 PyObject_GC_Del(it);
3320}
3321
3322static int
3323listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
3324{
3325 Py_VISIT(it->it_seq);
3326 return 0;
3327}
3328
3329static PyObject *
3330listreviter_next(listreviterobject *it)
3331{
3332 PyObject *item;
3333 Py_ssize_t index;
3334 PyListObject *seq;
3335
3336 assert(it != NULL);
3337 seq = it->it_seq;
3338 if (seq == NULL) {
3339 return NULL;
3340 }
3341 assert(PyList_Check(seq));
3342
3343 index = it->it_index;
3344 if (index>=0 && index < PyList_GET_SIZE(seq)) {
3345 item = PyList_GET_ITEM(seq, index);
3346 it->it_index--;
3347 Py_INCREF(item);
3348 return item;
3349 }
3350 it->it_index = -1;
3351 it->it_seq = NULL;
3352 Py_DECREF(seq);
3353 return NULL;
3354}
3355
3356static PyObject *
3357listreviter_len(listreviterobject *it, PyObject *Py_UNUSED(ignored))
3358{
3359 Py_ssize_t len = it->it_index + 1;
3360 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
3361 len = 0;
3362 return PyLong_FromSsize_t(len);
3363}
3364
3365static PyObject *
3366listreviter_reduce(listreviterobject *it, PyObject *Py_UNUSED(ignored))
3367{
3368 return listiter_reduce_general(it, 0);
3369}
3370
3371static PyObject *
3372listreviter_setstate(listreviterobject *it, PyObject *state)
3373{
3374 Py_ssize_t index = PyLong_AsSsize_t(state);
3375 if (index == -1 && PyErr_Occurred())
3376 return NULL;
3377 if (it->it_seq != NULL) {
3378 if (index < -1)
3379 index = -1;
3380 else if (index > PyList_GET_SIZE(it->it_seq) - 1)
3381 index = PyList_GET_SIZE(it->it_seq) - 1;
3382 it->it_index = index;
3383 }
3384 Py_RETURN_NONE;
3385}
3386
3387/* common pickling support */
3388
3389static PyObject *
3390listiter_reduce_general(void *_it, int forward)
3391{
3392 _Py_IDENTIFIER(iter);
3393 _Py_IDENTIFIER(reversed);
3394 PyObject *list;
3395
3396 /* the objects are not the same, index is of different types! */
3397 if (forward) {
3398 listiterobject *it = (listiterobject *)_it;
3399 if (it->it_seq)
3400 return Py_BuildValue("N(O)n", _PyEval_GetBuiltinId(&PyId_iter),
3401 it->it_seq, it->it_index);
3402 } else {
3403 listreviterobject *it = (listreviterobject *)_it;
3404 if (it->it_seq)
3405 return Py_BuildValue("N(O)n", _PyEval_GetBuiltinId(&PyId_reversed),
3406 it->it_seq, it->it_index);
3407 }
3408 /* empty iterator, create an empty list */
3409 list = PyList_New(0);
3410 if (list == NULL)
3411 return NULL;
3412 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
3413}
3414