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