blob: 22cdbe3cfdd41d3bcfbd5f9d6f2ca498389e28da [file] [log] [blame]
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001/* List object implementation */
2
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003#include "Python.h"
Victor Stinnera15e2602020-04-08 02:01:56 +02004#include "pycore_abstract.h" // _PyIndex_Check()
Victor Stinnerbcda8f12018-11-21 22:27:47 +01005#include "pycore_object.h"
Sergey Fedoseev234531b2019-02-25 21:59:12 +05006#include "pycore_tupleobject.h"
Victor Stinnere281f7d2018-11-01 02:30:36 +01007#include "pycore_accu.h"
Guido van Rossumc0b618a1997-05-02 03:12:38 +00008
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00009#ifdef STDC_HEADERS
10#include <stddef.h>
11#else
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000012#include <sys/types.h> /* For size_t */
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000013#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000014
Serhiy Storchakafdd42c42017-03-11 09:19:20 +020015/*[clinic input]
16class list "PyListObject *" "&PyList_Type"
17[clinic start generated code]*/
18/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/
19
20#include "clinic/listobject.c.h"
21
Tim Peters8d9eb102004-07-31 02:24:20 +000022/* Ensure ob_item has room for at least newsize elements, and set
23 * ob_size to newsize. If newsize > ob_size on entry, the content
24 * of the new slots at exit is undefined heap trash; it's the caller's
Ezio Melotti13925002011-03-16 11:05:33 +020025 * responsibility to overwrite them with sane values.
Tim Peters8d9eb102004-07-31 02:24:20 +000026 * The number of allocated elements may grow, shrink, or stay the same.
27 * Failure is impossible if newsize <= self.allocated on entry, although
28 * that partly relies on an assumption that the system realloc() never
29 * fails when passed a number of bytes <= the number of bytes last
30 * allocated (the C standard doesn't guarantee this, but it's hard to
31 * imagine a realloc implementation where it wouldn't be true).
32 * Note that self->ob_item may change, and even if newsize is less
33 * than ob_size on entry.
34 */
Guido van Rossuma46d51d1995-01-26 22:59:43 +000035static int
Martin v. Löwis18e16552006-02-15 17:27:45 +000036list_resize(PyListObject *self, Py_ssize_t newsize)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000037{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000038 PyObject **items;
Xiang Zhang4cee0492017-02-22 12:32:30 +080039 size_t new_allocated, num_allocated_bytes;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000040 Py_ssize_t allocated = self->allocated;
Tim Peters65b8b842001-05-26 05:28:40 +000041
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000042 /* Bypass realloc() when a previous overallocation is large enough
43 to accommodate the newsize. If the newsize falls lower than half
44 the allocated size, then proceed with the realloc() to shrink the list.
45 */
46 if (allocated >= newsize && newsize >= (allocated >> 1)) {
47 assert(self->ob_item != NULL || newsize == 0);
Victor Stinner60ac6ed2020-02-07 23:18:08 +010048 Py_SET_SIZE(self, newsize);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000049 return 0;
50 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +000051
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000052 /* This over-allocates proportional to the list size, making room
53 * for additional growth. The over-allocation is mild, but is
54 * enough to give linear-time amortized behavior over a long
55 * sequence of appends() in the presence of a poorly-performing
56 * system realloc().
Serhiy Storchaka2fe815e2020-03-17 23:46:00 +020057 * Add padding to make the allocated size multiple of 4.
58 * The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
Xiang Zhang4cee0492017-02-22 12:32:30 +080059 * Note: new_allocated won't overflow because the largest possible value
60 * is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000061 */
Serhiy Storchaka2fe815e2020-03-17 23:46:00 +020062 new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
63 /* Do not overallocate if the new size is closer to overalocated size
64 * than to the old size.
65 */
66 if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
67 new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +000068
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000069 if (newsize == 0)
70 new_allocated = 0;
Xiang Zhang4cee0492017-02-22 12:32:30 +080071 num_allocated_bytes = new_allocated * sizeof(PyObject *);
72 items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000073 if (items == NULL) {
74 PyErr_NoMemory();
75 return -1;
76 }
77 self->ob_item = items;
Victor Stinner60ac6ed2020-02-07 23:18:08 +010078 Py_SET_SIZE(self, newsize);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000079 self->allocated = new_allocated;
80 return 0;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000081}
Guido van Rossuma46d51d1995-01-26 22:59:43 +000082
Pablo Galindo372d7052018-10-28 20:16:26 +000083static int
84list_preallocate_exact(PyListObject *self, Py_ssize_t size)
85{
86 assert(self->ob_item == NULL);
Sergey Fedoseev0e5f7712018-12-30 03:31:36 +050087 assert(size > 0);
Pablo Galindo372d7052018-10-28 20:16:26 +000088
Sergey Fedoseev0e5f7712018-12-30 03:31:36 +050089 PyObject **items = PyMem_New(PyObject*, size);
Pablo Galindo372d7052018-10-28 20:16:26 +000090 if (items == NULL) {
91 PyErr_NoMemory();
92 return -1;
93 }
94 self->ob_item = items;
Sergey Fedoseev0e5f7712018-12-30 03:31:36 +050095 self->allocated = size;
Pablo Galindo372d7052018-10-28 20:16:26 +000096 return 0;
97}
98
Victor Stinnerae00a5a2020-04-29 02:29:20 +020099void
Victor Stinner88ec9192020-06-05 02:05:41 +0200100_PyList_ClearFreeList(PyThreadState *tstate)
Raymond Hettingerfb09f0e2004-10-07 03:58:07 +0000101{
Victor Stinner88ec9192020-06-05 02:05:41 +0200102 struct _Py_list_state *state = &tstate->interp->list;
103 while (state->numfree) {
104 PyListObject *op = state->free_list[--state->numfree];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000105 assert(PyList_CheckExact(op));
106 PyObject_GC_Del(op);
107 }
Antoine Pitrou9a812cb2011-11-15 00:00:12 +0100108}
109
110void
Victor Stinner88ec9192020-06-05 02:05:41 +0200111_PyList_Fini(PyThreadState *tstate)
Antoine Pitrou9a812cb2011-11-15 00:00:12 +0100112{
Victor Stinner88ec9192020-06-05 02:05:41 +0200113 _PyList_ClearFreeList(tstate);
Victor Stinnerbcb19832020-06-08 02:14:47 +0200114#ifdef Py_DEBUG
115 struct _Py_list_state *state = &tstate->interp->list;
116 state->numfree = -1;
117#endif
Raymond Hettingerfb09f0e2004-10-07 03:58:07 +0000118}
119
David Malcolm49526f42012-06-22 14:55:41 -0400120/* Print summary info about the state of the optimized allocator */
121void
122_PyList_DebugMallocStats(FILE *out)
123{
Victor Stinner88ec9192020-06-05 02:05:41 +0200124 PyInterpreterState *interp = _PyInterpreterState_GET();
125 struct _Py_list_state *state = &interp->list;
David Malcolm49526f42012-06-22 14:55:41 -0400126 _PyDebugAllocatorStats(out,
127 "free PyListObject",
Victor Stinner88ec9192020-06-05 02:05:41 +0200128 state->numfree, sizeof(PyListObject));
David Malcolm49526f42012-06-22 14:55:41 -0400129}
130
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000131PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000132PyList_New(Py_ssize_t size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000133{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000134 if (size < 0) {
135 PyErr_BadInternalCall();
136 return NULL;
137 }
Victor Stinner88ec9192020-06-05 02:05:41 +0200138
139 PyInterpreterState *interp = _PyInterpreterState_GET();
140 struct _Py_list_state *state = &interp->list;
141 PyListObject *op;
Victor Stinnerbcb19832020-06-08 02:14:47 +0200142#ifdef Py_DEBUG
143 // PyList_New() must not be called after _PyList_Fini()
144 assert(state->numfree != -1);
145#endif
Victor Stinner88ec9192020-06-05 02:05:41 +0200146 if (state->numfree) {
147 state->numfree--;
148 op = state->free_list[state->numfree];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000149 _Py_NewReference((PyObject *)op);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000150 }
Victor Stinner88ec9192020-06-05 02:05:41 +0200151 else {
152 op = PyObject_GC_New(PyListObject, &PyList_Type);
153 if (op == NULL) {
154 return NULL;
155 }
156 }
157 if (size <= 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000158 op->ob_item = NULL;
Victor Stinner88ec9192020-06-05 02:05:41 +0200159 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000160 else {
Mark Dickinson5d132382016-08-21 08:55:15 +0100161 op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000162 if (op->ob_item == NULL) {
163 Py_DECREF(op);
164 return PyErr_NoMemory();
165 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000166 }
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100167 Py_SET_SIZE(op, size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000168 op->allocated = size;
169 _PyObject_GC_TRACK(op);
170 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000171}
172
Sergey Fedoseev2fc46972018-08-11 18:12:07 +0500173static PyObject *
174list_new_prealloc(Py_ssize_t size)
175{
176 PyListObject *op = (PyListObject *) PyList_New(0);
177 if (size == 0 || op == NULL) {
178 return (PyObject *) op;
179 }
180 assert(op->ob_item == NULL);
181 op->ob_item = PyMem_New(PyObject *, size);
182 if (op->ob_item == NULL) {
183 Py_DECREF(op);
184 return PyErr_NoMemory();
185 }
186 op->allocated = size;
187 return (PyObject *) op;
188}
189
Martin v. Löwis18e16552006-02-15 17:27:45 +0000190Py_ssize_t
Fred Drakea2f55112000-07-09 15:16:51 +0000191PyList_Size(PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000192{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000193 if (!PyList_Check(op)) {
194 PyErr_BadInternalCall();
195 return -1;
196 }
197 else
198 return Py_SIZE(op);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000199}
200
Raymond Hettingerf1aa8ae2018-10-10 20:37:28 -0700201static inline int
202valid_index(Py_ssize_t i, Py_ssize_t limit)
203{
204 /* The cast to size_t lets us use just a single comparison
205 to check whether i is in the range: 0 <= i < limit.
206
207 See: Section 14.2 "Bounds Checking" in the Agner Fog
208 optimization manual found at:
209 https://www.agner.org/optimize/optimizing_cpp.pdf
210 */
211 return (size_t) i < (size_t) limit;
212}
213
Raymond Hettingerfdfe6182004-05-05 06:28:16 +0000214static PyObject *indexerr = NULL;
Guido van Rossum929f1b81996-08-09 20:51:27 +0000215
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000216PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000217PyList_GetItem(PyObject *op, Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000218{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000219 if (!PyList_Check(op)) {
220 PyErr_BadInternalCall();
221 return NULL;
222 }
Raymond Hettingerf1aa8ae2018-10-10 20:37:28 -0700223 if (!valid_index(i, Py_SIZE(op))) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000224 if (indexerr == NULL) {
225 indexerr = PyUnicode_FromString(
226 "list index out of range");
227 if (indexerr == NULL)
228 return NULL;
229 }
230 PyErr_SetObject(PyExc_IndexError, indexerr);
231 return NULL;
232 }
233 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000234}
235
236int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200237PyList_SetItem(PyObject *op, Py_ssize_t i,
238 PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000239{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200240 PyObject **p;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000241 if (!PyList_Check(op)) {
242 Py_XDECREF(newitem);
243 PyErr_BadInternalCall();
244 return -1;
245 }
Raymond Hettingerf1aa8ae2018-10-10 20:37:28 -0700246 if (!valid_index(i, Py_SIZE(op))) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000247 Py_XDECREF(newitem);
248 PyErr_SetString(PyExc_IndexError,
249 "list assignment index out of range");
250 return -1;
251 }
252 p = ((PyListObject *)op) -> ob_item + i;
Serhiy Storchakaec397562016-04-06 09:50:03 +0300253 Py_XSETREF(*p, newitem);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000254 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000255}
256
257static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000258ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000259{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000260 Py_ssize_t i, n = Py_SIZE(self);
261 PyObject **items;
262 if (v == NULL) {
263 PyErr_BadInternalCall();
264 return -1;
265 }
Tim Petersb38e2b62004-07-29 02:29:26 +0000266
Sergey Fedoseeve682b262020-05-25 19:54:40 +0500267 assert((size_t)n + 1 < PY_SSIZE_T_MAX);
Raymond Hettinger0dceb912016-01-25 10:33:30 -0800268 if (list_resize(self, n+1) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000269 return -1;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000270
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000271 if (where < 0) {
272 where += n;
273 if (where < 0)
274 where = 0;
275 }
276 if (where > n)
277 where = n;
278 items = self->ob_item;
279 for (i = n; --i >= where; )
280 items[i+1] = items[i];
281 Py_INCREF(v);
282 items[where] = v;
283 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000284}
285
286int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000287PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000288{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000289 if (!PyList_Check(op)) {
290 PyErr_BadInternalCall();
291 return -1;
292 }
293 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000294}
295
Raymond Hettinger40a03822004-04-12 13:05:09 +0000296static int
297app1(PyListObject *self, PyObject *v)
298{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000299 Py_ssize_t n = PyList_GET_SIZE(self);
Raymond Hettinger40a03822004-04-12 13:05:09 +0000300
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000301 assert (v != NULL);
Sergey Fedoseeve682b262020-05-25 19:54:40 +0500302 assert((size_t)n + 1 < PY_SSIZE_T_MAX);
Raymond Hettinger0dceb912016-01-25 10:33:30 -0800303 if (list_resize(self, n+1) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000304 return -1;
Raymond Hettinger40a03822004-04-12 13:05:09 +0000305
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000306 Py_INCREF(v);
307 PyList_SET_ITEM(self, n, v);
308 return 0;
Raymond Hettinger40a03822004-04-12 13:05:09 +0000309}
310
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000311int
Fred Drakea2f55112000-07-09 15:16:51 +0000312PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000313{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000314 if (PyList_Check(op) && (newitem != NULL))
315 return app1((PyListObject *)op, newitem);
316 PyErr_BadInternalCall();
317 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000318}
319
320/* Methods */
321
322static void
Fred Drakea2f55112000-07-09 15:16:51 +0000323list_dealloc(PyListObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000324{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000325 Py_ssize_t i;
326 PyObject_GC_UnTrack(op);
Jeroen Demeyer351c6742019-05-10 19:21:11 +0200327 Py_TRASHCAN_BEGIN(op, list_dealloc)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000328 if (op->ob_item != NULL) {
329 /* Do it backwards, for Christian Tismer.
330 There's a simple test case where somehow this reduces
331 thrashing when a *very* large list is created and
332 immediately deleted. */
333 i = Py_SIZE(op);
334 while (--i >= 0) {
335 Py_XDECREF(op->ob_item[i]);
336 }
337 PyMem_FREE(op->ob_item);
338 }
Victor Stinner88ec9192020-06-05 02:05:41 +0200339 PyInterpreterState *interp = _PyInterpreterState_GET();
340 struct _Py_list_state *state = &interp->list;
Victor Stinnerbcb19832020-06-08 02:14:47 +0200341#ifdef Py_DEBUG
342 // list_dealloc() must not be called after _PyList_Fini()
343 assert(state->numfree != -1);
344#endif
Victor Stinner88ec9192020-06-05 02:05:41 +0200345 if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {
346 state->free_list[state->numfree++] = op;
347 }
348 else {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000349 Py_TYPE(op)->tp_free((PyObject *)op);
Victor Stinner88ec9192020-06-05 02:05:41 +0200350 }
Jeroen Demeyer351c6742019-05-10 19:21:11 +0200351 Py_TRASHCAN_END
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000352}
353
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000354static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000355list_repr(PyListObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000356{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000357 Py_ssize_t i;
Victor Stinner5c733472013-11-18 21:11:57 +0100358 PyObject *s;
Victor Stinner5c733472013-11-18 21:11:57 +0100359 _PyUnicodeWriter writer;
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200360
361 if (Py_SIZE(v) == 0) {
362 return PyUnicode_FromString("[]");
363 }
364
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000365 i = Py_ReprEnter((PyObject*)v);
366 if (i != 0) {
367 return i > 0 ? PyUnicode_FromString("[...]") : NULL;
368 }
Tim Petersa7259592001-06-16 05:11:17 +0000369
Victor Stinner5c733472013-11-18 21:11:57 +0100370 _PyUnicodeWriter_Init(&writer);
371 writer.overallocate = 1;
Victor Stinnerb8fb1972013-11-18 22:15:44 +0100372 /* "[" + "1" + ", 2" * (len - 1) + "]" */
373 writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
Tim Petersa7259592001-06-16 05:11:17 +0000374
Victor Stinner5c733472013-11-18 21:11:57 +0100375 if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200376 goto error;
Tim Petersa7259592001-06-16 05:11:17 +0000377
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000378 /* Do repr() on each element. Note that this may mutate the list,
379 so must refetch the list size on each iteration. */
380 for (i = 0; i < Py_SIZE(v); ++i) {
Victor Stinner5c733472013-11-18 21:11:57 +0100381 if (i > 0) {
Victor Stinner4a587072013-11-19 12:54:53 +0100382 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
Victor Stinner5c733472013-11-18 21:11:57 +0100383 goto error;
384 }
385
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000386 s = PyObject_Repr(v->ob_item[i]);
Victor Stinner5c733472013-11-18 21:11:57 +0100387 if (s == NULL)
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200388 goto error;
Victor Stinner5c733472013-11-18 21:11:57 +0100389
390 if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
391 Py_DECREF(s);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200392 goto error;
Victor Stinner5c733472013-11-18 21:11:57 +0100393 }
394 Py_DECREF(s);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000395 }
Victor Stinner5c733472013-11-18 21:11:57 +0100396
Victor Stinner4d3f1092013-11-19 12:09:00 +0100397 writer.overallocate = 0;
Victor Stinner5c733472013-11-18 21:11:57 +0100398 if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200399 goto error;
Tim Petersa7259592001-06-16 05:11:17 +0000400
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000401 Py_ReprLeave((PyObject *)v);
Victor Stinner5c733472013-11-18 21:11:57 +0100402 return _PyUnicodeWriter_Finish(&writer);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200403
404error:
Victor Stinner5c733472013-11-18 21:11:57 +0100405 _PyUnicodeWriter_Dealloc(&writer);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200406 Py_ReprLeave((PyObject *)v);
407 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000408}
409
Martin v. Löwis18e16552006-02-15 17:27:45 +0000410static Py_ssize_t
Fred Drakea2f55112000-07-09 15:16:51 +0000411list_length(PyListObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000412{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000413 return Py_SIZE(a);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000414}
415
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000416static int
Fred Drakea2f55112000-07-09 15:16:51 +0000417list_contains(PyListObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000418{
Dong-hee Na4dbf2d82020-01-28 00:02:23 +0900419 PyObject *item;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000420 Py_ssize_t i;
421 int cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000422
Dong-hee Na4dbf2d82020-01-28 00:02:23 +0900423 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
424 item = PyList_GET_ITEM(a, i);
425 Py_INCREF(item);
Dong-hee Na9e1ed512020-01-28 02:04:25 +0900426 cmp = PyObject_RichCompareBool(item, el, Py_EQ);
Dong-hee Na4dbf2d82020-01-28 00:02:23 +0900427 Py_DECREF(item);
428 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000429 return cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000430}
431
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000432static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000433list_item(PyListObject *a, Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000434{
Raymond Hettingerf1aa8ae2018-10-10 20:37:28 -0700435 if (!valid_index(i, Py_SIZE(a))) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000436 if (indexerr == NULL) {
437 indexerr = PyUnicode_FromString(
438 "list index out of range");
439 if (indexerr == NULL)
440 return NULL;
441 }
442 PyErr_SetObject(PyExc_IndexError, indexerr);
443 return NULL;
444 }
445 Py_INCREF(a->ob_item[i]);
446 return a->ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000447}
448
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000449static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000450list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000451{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000452 PyListObject *np;
453 PyObject **src, **dest;
454 Py_ssize_t i, len;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000455 len = ihigh - ilow;
Sergey Fedoseev2fc46972018-08-11 18:12:07 +0500456 np = (PyListObject *) list_new_prealloc(len);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000457 if (np == NULL)
458 return NULL;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000460 src = a->ob_item + ilow;
461 dest = np->ob_item;
462 for (i = 0; i < len; i++) {
463 PyObject *v = src[i];
464 Py_INCREF(v);
465 dest[i] = v;
466 }
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100467 Py_SET_SIZE(np, len);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000468 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000469}
470
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000471PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000472PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum234f9421993-06-17 12:35:49 +0000473{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000474 if (!PyList_Check(a)) {
475 PyErr_BadInternalCall();
476 return NULL;
477 }
Sergey Fedoseevef1b88b2019-02-21 11:51:52 +0500478 if (ilow < 0) {
479 ilow = 0;
480 }
481 else if (ilow > Py_SIZE(a)) {
482 ilow = Py_SIZE(a);
483 }
484 if (ihigh < ilow) {
485 ihigh = ilow;
486 }
487 else if (ihigh > Py_SIZE(a)) {
488 ihigh = Py_SIZE(a);
489 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000490 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000491}
492
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000493static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000494list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000495{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000496 Py_ssize_t size;
497 Py_ssize_t i;
498 PyObject **src, **dest;
499 PyListObject *np;
500 if (!PyList_Check(bb)) {
501 PyErr_Format(PyExc_TypeError,
502 "can only concatenate list (not \"%.200s\") to list",
Victor Stinner58ac7002020-02-07 03:04:21 +0100503 Py_TYPE(bb)->tp_name);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000504 return NULL;
505 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000506#define b ((PyListObject *)bb)
Sergey Fedoseeve682b262020-05-25 19:54:40 +0500507 assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
Martin Panterb93d8632016-07-25 02:39:20 +0000508 size = Py_SIZE(a) + Py_SIZE(b);
Sergey Fedoseev2fc46972018-08-11 18:12:07 +0500509 np = (PyListObject *) list_new_prealloc(size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000510 if (np == NULL) {
511 return NULL;
512 }
513 src = a->ob_item;
514 dest = np->ob_item;
515 for (i = 0; i < Py_SIZE(a); i++) {
516 PyObject *v = src[i];
517 Py_INCREF(v);
518 dest[i] = v;
519 }
520 src = b->ob_item;
521 dest = np->ob_item + Py_SIZE(a);
522 for (i = 0; i < Py_SIZE(b); i++) {
523 PyObject *v = src[i];
524 Py_INCREF(v);
525 dest[i] = v;
526 }
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100527 Py_SET_SIZE(np, size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000528 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000529#undef b
530}
531
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000532static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000533list_repeat(PyListObject *a, Py_ssize_t n)
Guido van Rossumed98d481991-03-06 13:07:53 +0000534{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000535 Py_ssize_t i, j;
536 Py_ssize_t size;
537 PyListObject *np;
538 PyObject **p, **items;
539 PyObject *elem;
540 if (n < 0)
541 n = 0;
Mark Dickinsonc0420fd2011-09-19 19:18:37 +0100542 if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000543 return PyErr_NoMemory();
Mark Dickinsonc0420fd2011-09-19 19:18:37 +0100544 size = Py_SIZE(a) * n;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000545 if (size == 0)
546 return PyList_New(0);
Sergey Fedoseev2fc46972018-08-11 18:12:07 +0500547 np = (PyListObject *) list_new_prealloc(size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000548 if (np == NULL)
549 return NULL;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000550
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000551 if (Py_SIZE(a) == 1) {
Sergey Fedoseev2fc46972018-08-11 18:12:07 +0500552 items = np->ob_item;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000553 elem = a->ob_item[0];
554 for (i = 0; i < n; i++) {
555 items[i] = elem;
556 Py_INCREF(elem);
557 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000558 }
Sergey Fedoseev2fc46972018-08-11 18:12:07 +0500559 else {
560 p = np->ob_item;
561 items = a->ob_item;
562 for (i = 0; i < n; i++) {
563 for (j = 0; j < Py_SIZE(a); j++) {
564 *p = items[j];
565 Py_INCREF(*p);
566 p++;
567 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000568 }
569 }
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100570 Py_SET_SIZE(np, size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000571 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000572}
573
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000574static int
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200575_list_clear(PyListObject *a)
Armin Rigo93677f02004-07-29 12:40:23 +0000576{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000577 Py_ssize_t i;
578 PyObject **item = a->ob_item;
579 if (item != NULL) {
580 /* Because XDECREF can recursively invoke operations on
581 this list, we make it empty first. */
582 i = Py_SIZE(a);
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100583 Py_SET_SIZE(a, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000584 a->ob_item = NULL;
585 a->allocated = 0;
586 while (--i >= 0) {
587 Py_XDECREF(item[i]);
588 }
589 PyMem_FREE(item);
590 }
591 /* Never fails; the return value can be ignored.
592 Note that there is no guarantee that the list is actually empty
593 at this point, because XDECREF may have populated it again! */
594 return 0;
Armin Rigo93677f02004-07-29 12:40:23 +0000595}
596
Tim Peters8fc4a912004-07-31 21:53:19 +0000597/* a[ilow:ihigh] = v if v != NULL.
598 * del a[ilow:ihigh] if v == NULL.
599 *
600 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
601 * guaranteed the call cannot fail.
602 */
Armin Rigo93677f02004-07-29 12:40:23 +0000603static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000604list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000605{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000606 /* Because [X]DECREF can recursively invoke list operations on
607 this list, we must postpone all [X]DECREF activity until
608 after the list is back in its canonical shape. Therefore
609 we must allocate an additional array, 'recycle', into which
610 we temporarily copy the items that are deleted from the
611 list. :-( */
612 PyObject *recycle_on_stack[8];
613 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
614 PyObject **item;
615 PyObject **vitem = NULL;
616 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
617 Py_ssize_t n; /* # of elements in replacement list */
618 Py_ssize_t norig; /* # of elements in list getting replaced */
619 Py_ssize_t d; /* Change in size */
620 Py_ssize_t k;
621 size_t s;
622 int result = -1; /* guilty until proved innocent */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000623#define b ((PyListObject *)v)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000624 if (v == NULL)
625 n = 0;
626 else {
627 if (a == b) {
628 /* Special case "a[i:j] = a" -- copy b first */
629 v = list_slice(b, 0, Py_SIZE(b));
630 if (v == NULL)
631 return result;
632 result = list_ass_slice(a, ilow, ihigh, v);
633 Py_DECREF(v);
634 return result;
635 }
636 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
637 if(v_as_SF == NULL)
638 goto Error;
639 n = PySequence_Fast_GET_SIZE(v_as_SF);
640 vitem = PySequence_Fast_ITEMS(v_as_SF);
641 }
642 if (ilow < 0)
643 ilow = 0;
644 else if (ilow > Py_SIZE(a))
645 ilow = Py_SIZE(a);
Tim Peters8d9eb102004-07-31 02:24:20 +0000646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000647 if (ihigh < ilow)
648 ihigh = ilow;
649 else if (ihigh > Py_SIZE(a))
650 ihigh = Py_SIZE(a);
Armin Rigo93677f02004-07-29 12:40:23 +0000651
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000652 norig = ihigh - ilow;
653 assert(norig >= 0);
654 d = n - norig;
655 if (Py_SIZE(a) + d == 0) {
656 Py_XDECREF(v_as_SF);
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200657 return _list_clear(a);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000658 }
659 item = a->ob_item;
660 /* recycle the items that we are about to remove */
661 s = norig * sizeof(PyObject *);
Benjamin Peterson5a7d9232016-09-06 17:58:25 -0700662 /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
663 if (s) {
664 if (s > sizeof(recycle_on_stack)) {
665 recycle = (PyObject **)PyMem_MALLOC(s);
666 if (recycle == NULL) {
667 PyErr_NoMemory();
668 goto Error;
669 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000670 }
Benjamin Peterson5a7d9232016-09-06 17:58:25 -0700671 memcpy(recycle, &item[ilow], s);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000672 }
Tim Peters8d9eb102004-07-31 02:24:20 +0000673
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000674 if (d < 0) { /* Delete -d items */
Victor Stinner2c40f642013-07-19 23:06:21 +0200675 Py_ssize_t tail;
676 tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
677 memmove(&item[ihigh+d], &item[ihigh], tail);
678 if (list_resize(a, Py_SIZE(a) + d) < 0) {
679 memmove(&item[ihigh], &item[ihigh+d], tail);
680 memcpy(&item[ilow], recycle, s);
681 goto Error;
682 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000683 item = a->ob_item;
684 }
685 else if (d > 0) { /* Insert d items */
686 k = Py_SIZE(a);
687 if (list_resize(a, k+d) < 0)
688 goto Error;
689 item = a->ob_item;
690 memmove(&item[ihigh+d], &item[ihigh],
691 (k - ihigh)*sizeof(PyObject *));
692 }
693 for (k = 0; k < n; k++, ilow++) {
694 PyObject *w = vitem[k];
695 Py_XINCREF(w);
696 item[ilow] = w;
697 }
698 for (k = norig - 1; k >= 0; --k)
699 Py_XDECREF(recycle[k]);
700 result = 0;
Tim Peters8d9eb102004-07-31 02:24:20 +0000701 Error:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000702 if (recycle != recycle_on_stack)
703 PyMem_FREE(recycle);
704 Py_XDECREF(v_as_SF);
705 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000706#undef b
707}
708
Guido van Rossum234f9421993-06-17 12:35:49 +0000709int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000710PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum234f9421993-06-17 12:35:49 +0000711{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000712 if (!PyList_Check(a)) {
713 PyErr_BadInternalCall();
714 return -1;
715 }
716 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000717}
718
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000719static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000720list_inplace_repeat(PyListObject *self, Py_ssize_t n)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000721{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000722 PyObject **items;
723 Py_ssize_t size, i, j, p;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000724
725
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000726 size = PyList_GET_SIZE(self);
727 if (size == 0 || n == 1) {
728 Py_INCREF(self);
729 return (PyObject *)self;
730 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000731
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000732 if (n < 1) {
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200733 (void)_list_clear(self);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000734 Py_INCREF(self);
735 return (PyObject *)self;
736 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000737
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000738 if (size > PY_SSIZE_T_MAX / n) {
739 return PyErr_NoMemory();
740 }
Christian Heimesaf98da12008-01-27 15:18:18 +0000741
Raymond Hettinger0dceb912016-01-25 10:33:30 -0800742 if (list_resize(self, size*n) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000743 return NULL;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000744
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000745 p = size;
746 items = self->ob_item;
747 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
748 for (j = 0; j < size; j++) {
749 PyObject *o = items[j];
750 Py_INCREF(o);
751 items[p++] = o;
752 }
753 }
754 Py_INCREF(self);
755 return (PyObject *)self;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000756}
757
Guido van Rossum4a450d01991-04-03 19:05:18 +0000758static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000759list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
Guido van Rossum4a450d01991-04-03 19:05:18 +0000760{
Raymond Hettingerf1aa8ae2018-10-10 20:37:28 -0700761 if (!valid_index(i, Py_SIZE(a))) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000762 PyErr_SetString(PyExc_IndexError,
763 "list assignment index out of range");
764 return -1;
765 }
766 if (v == NULL)
767 return list_ass_slice(a, i, i+1, v);
768 Py_INCREF(v);
Serhiy Storchakaf01e4082016-04-10 18:12:01 +0300769 Py_SETREF(a->ob_item[i], v);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000770 return 0;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000771}
772
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200773/*[clinic input]
774list.insert
775
776 index: Py_ssize_t
777 object: object
778 /
779
780Insert object before index.
781[clinic start generated code]*/
782
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000783static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200784list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
785/*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000786{
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200787 if (ins1(self, index, object) == 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000788 Py_RETURN_NONE;
789 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000790}
791
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200792/*[clinic input]
793list.clear
794
795Remove all items from list.
796[clinic start generated code]*/
797
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000798static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200799list_clear_impl(PyListObject *self)
800/*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/
Eli Benderskycbbaa962011-02-25 05:47:53 +0000801{
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200802 _list_clear(self);
Eli Benderskycbbaa962011-02-25 05:47:53 +0000803 Py_RETURN_NONE;
804}
805
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200806/*[clinic input]
807list.copy
808
809Return a shallow copy of the list.
810[clinic start generated code]*/
811
Eli Benderskycbbaa962011-02-25 05:47:53 +0000812static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200813list_copy_impl(PyListObject *self)
814/*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/
Eli Benderskycbbaa962011-02-25 05:47:53 +0000815{
816 return list_slice(self, 0, Py_SIZE(self));
817}
818
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200819/*[clinic input]
820list.append
821
822 object: object
823 /
824
825Append object to the end of the list.
826[clinic start generated code]*/
827
Eli Benderskycbbaa962011-02-25 05:47:53 +0000828static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200829list_append(PyListObject *self, PyObject *object)
830/*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000831{
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200832 if (app1(self, object) == 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000833 Py_RETURN_NONE;
834 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000835}
836
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200837/*[clinic input]
838list.extend
839
840 iterable: object
841 /
842
843Extend list by appending elements from the iterable.
844[clinic start generated code]*/
845
Barry Warsawdedf6d61998-10-09 16:37:25 +0000846static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200847list_extend(PyListObject *self, PyObject *iterable)
848/*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000849{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000850 PyObject *it; /* iter(v) */
851 Py_ssize_t m; /* size of self */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200852 Py_ssize_t n; /* guess for size of iterable */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000853 Py_ssize_t mn; /* m + n */
854 Py_ssize_t i;
855 PyObject *(*iternext)(PyObject *);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000856
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000857 /* Special cases:
858 1) lists and tuples which can use PySequence_Fast ops
859 2) extending self to self requires making a copy first
860 */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200861 if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
862 (PyObject *)self == iterable) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000863 PyObject **src, **dest;
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200864 iterable = PySequence_Fast(iterable, "argument must be iterable");
865 if (!iterable)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000866 return NULL;
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200867 n = PySequence_Fast_GET_SIZE(iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000868 if (n == 0) {
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200869 /* short circuit when iterable is empty */
870 Py_DECREF(iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000871 Py_RETURN_NONE;
872 }
873 m = Py_SIZE(self);
Martin Panter94b39ce2017-01-14 06:30:37 +0000874 /* It should not be possible to allocate a list large enough to cause
875 an overflow on any relevant platform */
876 assert(m < PY_SSIZE_T_MAX - n);
Raymond Hettinger0dceb912016-01-25 10:33:30 -0800877 if (list_resize(self, m + n) < 0) {
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200878 Py_DECREF(iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000879 return NULL;
880 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200881 /* note that we may still have self == iterable here for the
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000882 * situation a.extend(a), but the following code works
883 * in that case too. Just make sure to resize self
884 * before calling PySequence_Fast_ITEMS.
885 */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200886 /* populate the end of self with iterable's items */
887 src = PySequence_Fast_ITEMS(iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000888 dest = self->ob_item + m;
889 for (i = 0; i < n; i++) {
890 PyObject *o = src[i];
891 Py_INCREF(o);
892 dest[i] = o;
893 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200894 Py_DECREF(iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000895 Py_RETURN_NONE;
896 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000897
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200898 it = PyObject_GetIter(iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000899 if (it == NULL)
900 return NULL;
Victor Stinner58ac7002020-02-07 03:04:21 +0100901 iternext = *Py_TYPE(it)->tp_iternext;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000902
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000903 /* Guess a result list size. */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200904 n = PyObject_LengthHint(iterable, 8);
Raymond Hettinger0dceb912016-01-25 10:33:30 -0800905 if (n < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000906 Py_DECREF(it);
907 return NULL;
908 }
909 m = Py_SIZE(self);
Martin Panterb93d8632016-07-25 02:39:20 +0000910 if (m > PY_SSIZE_T_MAX - n) {
911 /* m + n overflowed; on the chance that n lied, and there really
912 * is enough room, ignore it. If n was telling the truth, we'll
913 * eventually run out of memory during the loop.
914 */
915 }
916 else {
917 mn = m + n;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000918 /* Make room. */
Raymond Hettinger0dceb912016-01-25 10:33:30 -0800919 if (list_resize(self, mn) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000920 goto error;
921 /* Make the list sane again. */
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100922 Py_SET_SIZE(self, m);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000923 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000924
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000925 /* Run iterator to exhaustion. */
926 for (;;) {
927 PyObject *item = iternext(it);
928 if (item == NULL) {
929 if (PyErr_Occurred()) {
930 if (PyErr_ExceptionMatches(PyExc_StopIteration))
931 PyErr_Clear();
932 else
933 goto error;
934 }
935 break;
936 }
937 if (Py_SIZE(self) < self->allocated) {
938 /* steals ref */
939 PyList_SET_ITEM(self, Py_SIZE(self), item);
Victor Stinner60ac6ed2020-02-07 23:18:08 +0100940 Py_SET_SIZE(self, Py_SIZE(self) + 1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000941 }
942 else {
943 int status = app1(self, item);
944 Py_DECREF(item); /* append creates a new ref */
945 if (status < 0)
946 goto error;
947 }
948 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000949
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000950 /* Cut back result list if initial guess was too large. */
Victor Stinner32fd6ea2013-07-16 21:45:58 +0200951 if (Py_SIZE(self) < self->allocated) {
952 if (list_resize(self, Py_SIZE(self)) < 0)
953 goto error;
954 }
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000955
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000956 Py_DECREF(it);
957 Py_RETURN_NONE;
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000958
959 error:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000960 Py_DECREF(it);
961 return NULL;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000962}
963
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000964PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200965_PyList_Extend(PyListObject *self, PyObject *iterable)
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000966{
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200967 return list_extend(self, iterable);
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000968}
969
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000970static PyObject *
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000971list_inplace_concat(PyListObject *self, PyObject *other)
972{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000973 PyObject *result;
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000974
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200975 result = list_extend(self, other);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000976 if (result == NULL)
977 return result;
978 Py_DECREF(result);
979 Py_INCREF(self);
980 return (PyObject *)self;
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000981}
982
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200983/*[clinic input]
984list.pop
985
986 index: Py_ssize_t = -1
987 /
988
989Remove and return item at index (default last).
990
991Raises IndexError if list is empty or index is out of range.
992[clinic start generated code]*/
993
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000994static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +0200995list_pop_impl(PyListObject *self, Py_ssize_t index)
996/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000997{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000998 PyObject *v;
999 int status;
Raymond Hettinger9eb86b32004-02-17 11:36:16 +00001000
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001001 if (Py_SIZE(self) == 0) {
1002 /* Special-case most common failure cause */
1003 PyErr_SetString(PyExc_IndexError, "pop from empty list");
1004 return NULL;
1005 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02001006 if (index < 0)
1007 index += Py_SIZE(self);
Raymond Hettingerf1aa8ae2018-10-10 20:37:28 -07001008 if (!valid_index(index, Py_SIZE(self))) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001009 PyErr_SetString(PyExc_IndexError, "pop index out of range");
1010 return NULL;
1011 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02001012 v = self->ob_item[index];
1013 if (index == Py_SIZE(self) - 1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001014 status = list_resize(self, Py_SIZE(self) - 1);
Victor Stinnerb27cd3e2013-07-08 22:20:44 +02001015 if (status >= 0)
1016 return v; /* and v now owns the reference the list had */
1017 else
1018 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001019 }
1020 Py_INCREF(v);
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02001021 status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
Victor Stinner095d99f2013-07-17 21:58:01 +02001022 if (status < 0) {
1023 Py_DECREF(v);
1024 return NULL;
1025 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001026 return v;
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00001027}
1028
Tim Peters8e2e7ca2002-07-19 02:33:08 +00001029/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
1030static void
1031reverse_slice(PyObject **lo, PyObject **hi)
1032{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001033 assert(lo && hi);
Tim Peters8e2e7ca2002-07-19 02:33:08 +00001034
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001035 --hi;
1036 while (lo < hi) {
1037 PyObject *t = *lo;
1038 *lo = *hi;
1039 *hi = t;
1040 ++lo;
1041 --hi;
1042 }
Tim Peters8e2e7ca2002-07-19 02:33:08 +00001043}
1044
Tim Petersa64dc242002-08-01 02:13:36 +00001045/* Lots of code for an adaptive, stable, natural mergesort. There are many
1046 * pieces to this algorithm; read listsort.txt for overviews and details.
1047 */
Guido van Rossum3f236de1996-12-10 23:55:39 +00001048
Daniel Stutzbach98338222010-12-02 21:55:33 +00001049/* A sortslice contains a pointer to an array of keys and a pointer to
1050 * an array of corresponding values. In other words, keys[i]
1051 * corresponds with values[i]. If values == NULL, then the keys are
1052 * also the values.
1053 *
1054 * Several convenience routines are provided here, so that keys and
1055 * values are always moved in sync.
1056 */
1057
1058typedef struct {
1059 PyObject **keys;
1060 PyObject **values;
1061} sortslice;
1062
1063Py_LOCAL_INLINE(void)
1064sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
1065{
1066 s1->keys[i] = s2->keys[j];
1067 if (s1->values != NULL)
1068 s1->values[i] = s2->values[j];
1069}
1070
1071Py_LOCAL_INLINE(void)
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001072sortslice_copy_incr(sortslice *dst, sortslice *src)
1073{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001074 *dst->keys++ = *src->keys++;
1075 if (dst->values != NULL)
1076 *dst->values++ = *src->values++;
1077}
1078
1079Py_LOCAL_INLINE(void)
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001080sortslice_copy_decr(sortslice *dst, sortslice *src)
1081{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001082 *dst->keys-- = *src->keys--;
1083 if (dst->values != NULL)
1084 *dst->values-- = *src->values--;
1085}
1086
1087
1088Py_LOCAL_INLINE(void)
1089sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001090 Py_ssize_t n)
1091{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001092 memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1093 if (s1->values != NULL)
1094 memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1095}
1096
1097Py_LOCAL_INLINE(void)
1098sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001099 Py_ssize_t n)
1100{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001101 memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1102 if (s1->values != NULL)
1103 memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1104}
1105
1106Py_LOCAL_INLINE(void)
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001107sortslice_advance(sortslice *slice, Py_ssize_t n)
1108{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001109 slice->keys += n;
1110 if (slice->values != NULL)
1111 slice->values += n;
1112}
1113
embg1e34da42018-01-28 20:03:23 -07001114/* Comparison function: ms->key_compare, which is set at run-time in
1115 * listsort_impl to optimize for various special cases.
Tim Petersa64dc242002-08-01 02:13:36 +00001116 * Returns -1 on error, 1 if x < y, 0 if x >= y.
1117 */
Guido van Rossum3f236de1996-12-10 23:55:39 +00001118
embg1e34da42018-01-28 20:03:23 -07001119#define ISLT(X, Y) (*(ms->key_compare))(X, Y, ms)
Tim Peters66860f62002-08-04 17:47:26 +00001120
1121/* Compare X to Y via "<". Goto "fail" if the comparison raises an
Tim Petersa8c974c2002-07-19 03:30:57 +00001122 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
1123 started. It makes more sense in context <wink>. X and Y are PyObject*s.
1124*/
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001125#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001126 if (k)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001127
embg1e34da42018-01-28 20:03:23 -07001128/* The maximum number of entries in a MergeState's pending-runs stack.
1129 * This is enough to sort arrays of size up to about
1130 * 32 * phi ** MAX_MERGE_PENDING
1131 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1132 * with 2**64 elements.
1133 */
1134#define MAX_MERGE_PENDING 85
1135
1136/* When we get into galloping mode, we stay there until both runs win less
1137 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1138 */
1139#define MIN_GALLOP 7
1140
1141/* Avoid malloc for small temp arrays. */
1142#define MERGESTATE_TEMP_SIZE 256
1143
1144/* One MergeState exists on the stack per invocation of mergesort. It's just
1145 * a convenient way to pass state around among the helper functions.
1146 */
1147struct s_slice {
1148 sortslice base;
1149 Py_ssize_t len;
1150};
1151
1152typedef struct s_MergeState MergeState;
1153struct s_MergeState {
1154 /* This controls when we get *into* galloping mode. It's initialized
1155 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1156 * random data, and lower for highly structured data.
1157 */
1158 Py_ssize_t min_gallop;
1159
1160 /* 'a' is temp storage to help with merges. It contains room for
1161 * alloced entries.
1162 */
1163 sortslice a; /* may point to temparray below */
1164 Py_ssize_t alloced;
1165
1166 /* A stack of n pending runs yet to be merged. Run #i starts at
1167 * address base[i] and extends for len[i] elements. It's always
1168 * true (so long as the indices are in bounds) that
1169 *
1170 * pending[i].base + pending[i].len == pending[i+1].base
1171 *
1172 * so we could cut the storage for this, but it's a minor amount,
1173 * and keeping all the info explicit simplifies the code.
1174 */
1175 int n;
1176 struct s_slice pending[MAX_MERGE_PENDING];
1177
1178 /* 'a' points to this when possible, rather than muck with malloc. */
1179 PyObject *temparray[MERGESTATE_TEMP_SIZE];
1180
1181 /* This is the function we will use to compare two keys,
1182 * even when none of our special cases apply and we have to use
1183 * safe_object_compare. */
1184 int (*key_compare)(PyObject *, PyObject *, MergeState *);
1185
1186 /* This function is used by unsafe_object_compare to optimize comparisons
1187 * when we know our list is type-homogeneous but we can't assume anything else.
Victor Stinner58ac7002020-02-07 03:04:21 +01001188 * In the pre-sort check it is set equal to Py_TYPE(key)->tp_richcompare */
embg1e34da42018-01-28 20:03:23 -07001189 PyObject *(*key_richcompare)(PyObject *, PyObject *, int);
1190
1191 /* This function is used by unsafe_tuple_compare to compare the first elements
1192 * of tuples. It may be set to safe_object_compare, but the idea is that hopefully
1193 * we can assume more, and use one of the special-case compares. */
1194 int (*tuple_elem_compare)(PyObject *, PyObject *, MergeState *);
1195};
1196
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001197/* binarysort is the best method for sorting small arrays: it does
1198 few compares, but can do data movement quadratic in the number of
1199 elements.
Guido van Rossum42812581998-06-17 14:15:44 +00001200 [lo, hi) is a contiguous slice of a list, and is sorted via
Tim Petersa8c974c2002-07-19 03:30:57 +00001201 binary insertion. This sort is stable.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001202 On entry, must have lo <= start <= hi, and that [lo, start) is already
1203 sorted (pass start == lo if you don't know!).
Tim Petersa8c974c2002-07-19 03:30:57 +00001204 If islt() complains return -1, else 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001205 Even in case of error, the output slice will be some permutation of
1206 the input (nothing is lost or duplicated).
1207*/
Guido van Rossum3f236de1996-12-10 23:55:39 +00001208static int
embg1e34da42018-01-28 20:03:23 -07001209binarysort(MergeState *ms, sortslice lo, PyObject **hi, PyObject **start)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001210{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +02001211 Py_ssize_t k;
1212 PyObject **l, **p, **r;
1213 PyObject *pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001214
Daniel Stutzbach98338222010-12-02 21:55:33 +00001215 assert(lo.keys <= start && start <= hi);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001216 /* assert [lo, start) is sorted */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001217 if (lo.keys == start)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001218 ++start;
1219 for (; start < hi; ++start) {
1220 /* set l to where *start belongs */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001221 l = lo.keys;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001222 r = start;
1223 pivot = *r;
1224 /* Invariants:
1225 * pivot >= all in [lo, l).
1226 * pivot < all in [r, start).
1227 * The second is vacuously true at the start.
1228 */
1229 assert(l < r);
1230 do {
1231 p = l + ((r - l) >> 1);
1232 IFLT(pivot, *p)
1233 r = p;
1234 else
1235 l = p+1;
1236 } while (l < r);
1237 assert(l == r);
1238 /* The invariants still hold, so pivot >= all in [lo, l) and
1239 pivot < all in [l, start), so pivot belongs at l. Note
1240 that if there are elements equal to pivot, l points to the
1241 first slot after them -- that's why this sort is stable.
1242 Slide over to make room.
1243 Caution: using memmove is much slower under MSVC 5;
1244 we're not usually moving many slots. */
1245 for (p = start; p > l; --p)
1246 *p = *(p-1);
1247 *l = pivot;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001248 if (lo.values != NULL) {
1249 Py_ssize_t offset = lo.values - lo.keys;
1250 p = start + offset;
1251 pivot = *p;
1252 l += offset;
1253 for (p = start + offset; p > l; --p)
1254 *p = *(p-1);
1255 *l = pivot;
1256 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001257 }
1258 return 0;
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001259
1260 fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001261 return -1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001262}
1263
Tim Petersa64dc242002-08-01 02:13:36 +00001264/*
1265Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1266is required on entry. "A run" is the longest ascending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001267
Tim Petersa64dc242002-08-01 02:13:36 +00001268 lo[0] <= lo[1] <= lo[2] <= ...
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001269
Tim Petersa64dc242002-08-01 02:13:36 +00001270or the longest descending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001271
Tim Petersa64dc242002-08-01 02:13:36 +00001272 lo[0] > lo[1] > lo[2] > ...
Tim Peters3b01a122002-07-19 02:35:45 +00001273
Tim Petersa64dc242002-08-01 02:13:36 +00001274Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1275For its intended use in a stable mergesort, the strictness of the defn of
1276"descending" is needed so that the caller can safely reverse a descending
1277sequence without violating stability (strict > ensures there are no equal
1278elements to get out of order).
1279
1280Returns -1 in case of error.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001281*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001282static Py_ssize_t
embg1e34da42018-01-28 20:03:23 -07001283count_run(MergeState *ms, PyObject **lo, PyObject **hi, int *descending)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001284{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001285 Py_ssize_t k;
1286 Py_ssize_t n;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001287
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001288 assert(lo < hi);
1289 *descending = 0;
1290 ++lo;
1291 if (lo == hi)
1292 return 1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001293
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001294 n = 2;
1295 IFLT(*lo, *(lo-1)) {
1296 *descending = 1;
1297 for (lo = lo+1; lo < hi; ++lo, ++n) {
1298 IFLT(*lo, *(lo-1))
1299 ;
1300 else
1301 break;
1302 }
1303 }
1304 else {
1305 for (lo = lo+1; lo < hi; ++lo, ++n) {
1306 IFLT(*lo, *(lo-1))
1307 break;
1308 }
1309 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001310
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001311 return n;
Tim Petersa64dc242002-08-01 02:13:36 +00001312fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001313 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001314}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001315
Tim Petersa64dc242002-08-01 02:13:36 +00001316/*
1317Locate the proper position of key in a sorted vector; if the vector contains
1318an element equal to key, return the position immediately to the left of
1319the leftmost equal element. [gallop_right() does the same except returns
1320the position to the right of the rightmost equal element (if any).]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001321
Tim Petersa64dc242002-08-01 02:13:36 +00001322"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001323
Tim Petersa64dc242002-08-01 02:13:36 +00001324"hint" is an index at which to begin the search, 0 <= hint < n. The closer
1325hint is to the final result, the faster this runs.
1326
1327The return value is the int k in 0..n such that
1328
1329 a[k-1] < key <= a[k]
1330
1331pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1332key belongs at index k; or, IOW, the first k elements of a should precede
1333key, and the last n-k should follow key.
1334
1335Returns -1 on error. See listsort.txt for info on the method.
1336*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001337static Py_ssize_t
embg1e34da42018-01-28 20:03:23 -07001338gallop_left(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
Tim Petersa64dc242002-08-01 02:13:36 +00001339{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001340 Py_ssize_t ofs;
1341 Py_ssize_t lastofs;
1342 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001343
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001344 assert(key && a && n > 0 && hint >= 0 && hint < n);
Tim Petersa64dc242002-08-01 02:13:36 +00001345
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001346 a += hint;
1347 lastofs = 0;
1348 ofs = 1;
1349 IFLT(*a, key) {
1350 /* a[hint] < key -- gallop right, until
1351 * a[hint + lastofs] < key <= a[hint + ofs]
1352 */
1353 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1354 while (ofs < maxofs) {
1355 IFLT(a[ofs], key) {
1356 lastofs = ofs;
Alexey Izbyshev6bc59172019-05-23 03:01:08 +03001357 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001358 ofs = (ofs << 1) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001359 }
1360 else /* key <= a[hint + ofs] */
1361 break;
1362 }
1363 if (ofs > maxofs)
1364 ofs = maxofs;
1365 /* Translate back to offsets relative to &a[0]. */
1366 lastofs += hint;
1367 ofs += hint;
1368 }
1369 else {
1370 /* key <= a[hint] -- gallop left, until
1371 * a[hint - ofs] < key <= a[hint - lastofs]
1372 */
1373 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1374 while (ofs < maxofs) {
1375 IFLT(*(a-ofs), key)
1376 break;
1377 /* key <= a[hint - ofs] */
1378 lastofs = ofs;
Alexey Izbyshev6bc59172019-05-23 03:01:08 +03001379 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001380 ofs = (ofs << 1) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001381 }
1382 if (ofs > maxofs)
1383 ofs = maxofs;
1384 /* Translate back to positive offsets relative to &a[0]. */
1385 k = lastofs;
1386 lastofs = hint - ofs;
1387 ofs = hint - k;
1388 }
1389 a -= hint;
Tim Petersa64dc242002-08-01 02:13:36 +00001390
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001391 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1392 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1393 * right of lastofs but no farther right than ofs. Do a binary
1394 * search, with invariant a[lastofs-1] < key <= a[ofs].
1395 */
1396 ++lastofs;
1397 while (lastofs < ofs) {
1398 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001399
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001400 IFLT(a[m], key)
1401 lastofs = m+1; /* a[m] < key */
1402 else
1403 ofs = m; /* key <= a[m] */
1404 }
1405 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1406 return ofs;
Tim Petersa64dc242002-08-01 02:13:36 +00001407
1408fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001409 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001410}
1411
1412/*
1413Exactly like gallop_left(), except that if key already exists in a[0:n],
1414finds the position immediately to the right of the rightmost equal value.
1415
1416The return value is the int k in 0..n such that
1417
1418 a[k-1] <= key < a[k]
1419
1420or -1 if error.
1421
1422The code duplication is massive, but this is enough different given that
1423we're sticking to "<" comparisons that it's much harder to follow if
1424written as one routine with yet another "left or right?" flag.
1425*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001426static Py_ssize_t
embg1e34da42018-01-28 20:03:23 -07001427gallop_right(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
Tim Petersa64dc242002-08-01 02:13:36 +00001428{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001429 Py_ssize_t ofs;
1430 Py_ssize_t lastofs;
1431 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001432
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001433 assert(key && a && n > 0 && hint >= 0 && hint < n);
Tim Petersa64dc242002-08-01 02:13:36 +00001434
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001435 a += hint;
1436 lastofs = 0;
1437 ofs = 1;
1438 IFLT(key, *a) {
1439 /* key < a[hint] -- gallop left, until
1440 * a[hint - ofs] <= key < a[hint - lastofs]
1441 */
1442 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1443 while (ofs < maxofs) {
1444 IFLT(key, *(a-ofs)) {
1445 lastofs = ofs;
Alexey Izbyshev6bc59172019-05-23 03:01:08 +03001446 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001447 ofs = (ofs << 1) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001448 }
1449 else /* a[hint - ofs] <= key */
1450 break;
1451 }
1452 if (ofs > maxofs)
1453 ofs = maxofs;
1454 /* Translate back to positive offsets relative to &a[0]. */
1455 k = lastofs;
1456 lastofs = hint - ofs;
1457 ofs = hint - k;
1458 }
1459 else {
1460 /* a[hint] <= key -- gallop right, until
1461 * a[hint + lastofs] <= key < a[hint + ofs]
1462 */
1463 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1464 while (ofs < maxofs) {
1465 IFLT(key, a[ofs])
1466 break;
1467 /* a[hint + ofs] <= key */
1468 lastofs = ofs;
Alexey Izbyshev6bc59172019-05-23 03:01:08 +03001469 assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001470 ofs = (ofs << 1) + 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001471 }
1472 if (ofs > maxofs)
1473 ofs = maxofs;
1474 /* Translate back to offsets relative to &a[0]. */
1475 lastofs += hint;
1476 ofs += hint;
1477 }
1478 a -= hint;
Tim Petersa64dc242002-08-01 02:13:36 +00001479
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001480 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1481 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1482 * right of lastofs but no farther right than ofs. Do a binary
1483 * search, with invariant a[lastofs-1] <= key < a[ofs].
1484 */
1485 ++lastofs;
1486 while (lastofs < ofs) {
1487 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001488
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001489 IFLT(key, a[m])
1490 ofs = m; /* key < a[m] */
1491 else
1492 lastofs = m+1; /* a[m] <= key */
1493 }
1494 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1495 return ofs;
Tim Petersa64dc242002-08-01 02:13:36 +00001496
1497fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001498 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001499}
1500
Tim Petersa64dc242002-08-01 02:13:36 +00001501/* Conceptually a MergeState's constructor. */
1502static void
Victor Stinner0fcab4a2011-01-04 12:59:15 +00001503merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc)
Tim Petersa64dc242002-08-01 02:13:36 +00001504{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001505 assert(ms != NULL);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001506 if (has_keyfunc) {
1507 /* The temporary space for merging will need at most half the list
1508 * size rounded up. Use the minimum possible space so we can use the
1509 * rest of temparray for other things. In particular, if there is
1510 * enough extra space, listsort() will use it to store the keys.
1511 */
1512 ms->alloced = (list_size + 1) / 2;
1513
1514 /* ms->alloced describes how many keys will be stored at
1515 ms->temparray, but we also need to store the values. Hence,
1516 ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
1517 if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
1518 ms->alloced = MERGESTATE_TEMP_SIZE / 2;
1519 ms->a.values = &ms->temparray[ms->alloced];
1520 }
1521 else {
1522 ms->alloced = MERGESTATE_TEMP_SIZE;
1523 ms->a.values = NULL;
1524 }
1525 ms->a.keys = ms->temparray;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001526 ms->n = 0;
1527 ms->min_gallop = MIN_GALLOP;
Tim Petersa64dc242002-08-01 02:13:36 +00001528}
1529
1530/* Free all the temp memory owned by the MergeState. This must be called
1531 * when you're done with a MergeState, and may be called before then if
1532 * you want to free the temp memory early.
1533 */
1534static void
1535merge_freemem(MergeState *ms)
1536{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001537 assert(ms != NULL);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001538 if (ms->a.keys != ms->temparray)
1539 PyMem_Free(ms->a.keys);
Tim Petersa64dc242002-08-01 02:13:36 +00001540}
1541
1542/* Ensure enough temp memory for 'need' array slots is available.
1543 * Returns 0 on success and -1 if the memory can't be gotten.
1544 */
1545static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001546merge_getmem(MergeState *ms, Py_ssize_t need)
Tim Petersa64dc242002-08-01 02:13:36 +00001547{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001548 int multiplier;
1549
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001550 assert(ms != NULL);
1551 if (need <= ms->alloced)
1552 return 0;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001553
1554 multiplier = ms->a.values != NULL ? 2 : 1;
1555
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001556 /* Don't realloc! That can cost cycles to copy the old data, but
1557 * we don't care what's in the block.
1558 */
1559 merge_freemem(ms);
embg1e34da42018-01-28 20:03:23 -07001560 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject *) / multiplier) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001561 PyErr_NoMemory();
1562 return -1;
1563 }
embg1e34da42018-01-28 20:03:23 -07001564 ms->a.keys = (PyObject **)PyMem_Malloc(multiplier * need
Daniel Stutzbach98338222010-12-02 21:55:33 +00001565 * sizeof(PyObject *));
1566 if (ms->a.keys != NULL) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001567 ms->alloced = need;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001568 if (ms->a.values != NULL)
1569 ms->a.values = &ms->a.keys[need];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001570 return 0;
1571 }
1572 PyErr_NoMemory();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001573 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001574}
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001575#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1576 merge_getmem(MS, NEED))
Tim Petersa64dc242002-08-01 02:13:36 +00001577
Daniel Stutzbach98338222010-12-02 21:55:33 +00001578/* Merge the na elements starting at ssa with the nb elements starting at
1579 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
1580 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
1581 * should have na <= nb. See listsort.txt for more info. Return 0 if
1582 * successful, -1 if error.
Tim Petersa64dc242002-08-01 02:13:36 +00001583 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001584static Py_ssize_t
Daniel Stutzbach98338222010-12-02 21:55:33 +00001585merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
1586 sortslice ssb, Py_ssize_t nb)
Tim Petersa64dc242002-08-01 02:13:36 +00001587{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001588 Py_ssize_t k;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001589 sortslice dest;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001590 int result = -1; /* guilty until proved innocent */
1591 Py_ssize_t min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001592
Daniel Stutzbach98338222010-12-02 21:55:33 +00001593 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1594 assert(ssa.keys + na == ssb.keys);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001595 if (MERGE_GETMEM(ms, na) < 0)
1596 return -1;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001597 sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
1598 dest = ssa;
1599 ssa = ms->a;
Tim Petersa64dc242002-08-01 02:13:36 +00001600
Daniel Stutzbach98338222010-12-02 21:55:33 +00001601 sortslice_copy_incr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001602 --nb;
1603 if (nb == 0)
1604 goto Succeed;
1605 if (na == 1)
1606 goto CopyB;
Tim Petersa64dc242002-08-01 02:13:36 +00001607
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001608 min_gallop = ms->min_gallop;
1609 for (;;) {
1610 Py_ssize_t acount = 0; /* # of times A won in a row */
1611 Py_ssize_t bcount = 0; /* # of times B won in a row */
Tim Petersa64dc242002-08-01 02:13:36 +00001612
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001613 /* Do the straightforward thing until (if ever) one run
1614 * appears to win consistently.
1615 */
1616 for (;;) {
1617 assert(na > 1 && nb > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001618 k = ISLT(ssb.keys[0], ssa.keys[0]);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001619 if (k) {
1620 if (k < 0)
1621 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001622 sortslice_copy_incr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001623 ++bcount;
1624 acount = 0;
1625 --nb;
1626 if (nb == 0)
1627 goto Succeed;
1628 if (bcount >= min_gallop)
1629 break;
1630 }
1631 else {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001632 sortslice_copy_incr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001633 ++acount;
1634 bcount = 0;
1635 --na;
1636 if (na == 1)
1637 goto CopyB;
1638 if (acount >= min_gallop)
1639 break;
1640 }
1641 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001642
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001643 /* One run is winning so consistently that galloping may
1644 * be a huge win. So try that, and continue galloping until
1645 * (if ever) neither run appears to be winning consistently
1646 * anymore.
1647 */
1648 ++min_gallop;
1649 do {
1650 assert(na > 1 && nb > 0);
1651 min_gallop -= min_gallop > 1;
1652 ms->min_gallop = min_gallop;
embg1e34da42018-01-28 20:03:23 -07001653 k = gallop_right(ms, ssb.keys[0], ssa.keys, na, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001654 acount = k;
1655 if (k) {
1656 if (k < 0)
1657 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001658 sortslice_memcpy(&dest, 0, &ssa, 0, k);
1659 sortslice_advance(&dest, k);
1660 sortslice_advance(&ssa, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001661 na -= k;
1662 if (na == 1)
1663 goto CopyB;
1664 /* na==0 is impossible now if the comparison
1665 * function is consistent, but we can't assume
1666 * that it is.
1667 */
1668 if (na == 0)
1669 goto Succeed;
1670 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001671 sortslice_copy_incr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001672 --nb;
1673 if (nb == 0)
1674 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001675
embg1e34da42018-01-28 20:03:23 -07001676 k = gallop_left(ms, ssa.keys[0], ssb.keys, nb, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001677 bcount = k;
1678 if (k) {
1679 if (k < 0)
1680 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001681 sortslice_memmove(&dest, 0, &ssb, 0, k);
1682 sortslice_advance(&dest, k);
1683 sortslice_advance(&ssb, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001684 nb -= k;
1685 if (nb == 0)
1686 goto Succeed;
1687 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001688 sortslice_copy_incr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001689 --na;
1690 if (na == 1)
1691 goto CopyB;
1692 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1693 ++min_gallop; /* penalize it for leaving galloping mode */
1694 ms->min_gallop = min_gallop;
1695 }
Tim Petersa64dc242002-08-01 02:13:36 +00001696Succeed:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001697 result = 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001698Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001699 if (na)
Daniel Stutzbach98338222010-12-02 21:55:33 +00001700 sortslice_memcpy(&dest, 0, &ssa, 0, na);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001701 return result;
Tim Petersa64dc242002-08-01 02:13:36 +00001702CopyB:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001703 assert(na == 1 && nb > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001704 /* The last element of ssa belongs at the end of the merge. */
1705 sortslice_memmove(&dest, 0, &ssb, 0, nb);
1706 sortslice_copy(&dest, nb, &ssa, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001707 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001708}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001709
Daniel Stutzbach98338222010-12-02 21:55:33 +00001710/* Merge the na elements starting at pa with the nb elements starting at
1711 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
1712 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
1713 * should have na >= nb. See listsort.txt for more info. Return 0 if
1714 * successful, -1 if error.
Tim Petersa64dc242002-08-01 02:13:36 +00001715 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001716static Py_ssize_t
Daniel Stutzbach98338222010-12-02 21:55:33 +00001717merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
1718 sortslice ssb, Py_ssize_t nb)
Tim Petersa64dc242002-08-01 02:13:36 +00001719{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001720 Py_ssize_t k;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001721 sortslice dest, basea, baseb;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001722 int result = -1; /* guilty until proved innocent */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001723 Py_ssize_t min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001724
Daniel Stutzbach98338222010-12-02 21:55:33 +00001725 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1726 assert(ssa.keys + na == ssb.keys);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001727 if (MERGE_GETMEM(ms, nb) < 0)
1728 return -1;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001729 dest = ssb;
1730 sortslice_advance(&dest, nb-1);
1731 sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
1732 basea = ssa;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001733 baseb = ms->a;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001734 ssb.keys = ms->a.keys + nb - 1;
1735 if (ssb.values != NULL)
1736 ssb.values = ms->a.values + nb - 1;
1737 sortslice_advance(&ssa, na - 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001738
Daniel Stutzbach98338222010-12-02 21:55:33 +00001739 sortslice_copy_decr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001740 --na;
1741 if (na == 0)
1742 goto Succeed;
1743 if (nb == 1)
1744 goto CopyA;
Tim Petersa64dc242002-08-01 02:13:36 +00001745
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001746 min_gallop = ms->min_gallop;
1747 for (;;) {
1748 Py_ssize_t acount = 0; /* # of times A won in a row */
1749 Py_ssize_t bcount = 0; /* # of times B won in a row */
Tim Petersa64dc242002-08-01 02:13:36 +00001750
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001751 /* Do the straightforward thing until (if ever) one run
1752 * appears to win consistently.
1753 */
1754 for (;;) {
1755 assert(na > 0 && nb > 1);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001756 k = ISLT(ssb.keys[0], ssa.keys[0]);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001757 if (k) {
1758 if (k < 0)
1759 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001760 sortslice_copy_decr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001761 ++acount;
1762 bcount = 0;
1763 --na;
1764 if (na == 0)
1765 goto Succeed;
1766 if (acount >= min_gallop)
1767 break;
1768 }
1769 else {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001770 sortslice_copy_decr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001771 ++bcount;
1772 acount = 0;
1773 --nb;
1774 if (nb == 1)
1775 goto CopyA;
1776 if (bcount >= min_gallop)
1777 break;
1778 }
1779 }
Tim Petersa64dc242002-08-01 02:13:36 +00001780
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001781 /* One run is winning so consistently that galloping may
1782 * be a huge win. So try that, and continue galloping until
1783 * (if ever) neither run appears to be winning consistently
1784 * anymore.
1785 */
1786 ++min_gallop;
1787 do {
1788 assert(na > 0 && nb > 1);
1789 min_gallop -= min_gallop > 1;
1790 ms->min_gallop = min_gallop;
embg1e34da42018-01-28 20:03:23 -07001791 k = gallop_right(ms, ssb.keys[0], basea.keys, na, na-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001792 if (k < 0)
1793 goto Fail;
1794 k = na - k;
1795 acount = k;
1796 if (k) {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001797 sortslice_advance(&dest, -k);
1798 sortslice_advance(&ssa, -k);
1799 sortslice_memmove(&dest, 1, &ssa, 1, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001800 na -= k;
1801 if (na == 0)
1802 goto Succeed;
1803 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001804 sortslice_copy_decr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001805 --nb;
1806 if (nb == 1)
1807 goto CopyA;
Tim Petersa64dc242002-08-01 02:13:36 +00001808
embg1e34da42018-01-28 20:03:23 -07001809 k = gallop_left(ms, ssa.keys[0], baseb.keys, nb, nb-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001810 if (k < 0)
1811 goto Fail;
1812 k = nb - k;
1813 bcount = k;
1814 if (k) {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001815 sortslice_advance(&dest, -k);
1816 sortslice_advance(&ssb, -k);
1817 sortslice_memcpy(&dest, 1, &ssb, 1, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001818 nb -= k;
1819 if (nb == 1)
1820 goto CopyA;
1821 /* nb==0 is impossible now if the comparison
1822 * function is consistent, but we can't assume
1823 * that it is.
1824 */
1825 if (nb == 0)
1826 goto Succeed;
1827 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001828 sortslice_copy_decr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001829 --na;
1830 if (na == 0)
1831 goto Succeed;
1832 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1833 ++min_gallop; /* penalize it for leaving galloping mode */
1834 ms->min_gallop = min_gallop;
1835 }
Tim Petersa64dc242002-08-01 02:13:36 +00001836Succeed:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001837 result = 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001838Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001839 if (nb)
Daniel Stutzbach98338222010-12-02 21:55:33 +00001840 sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001841 return result;
Tim Petersa64dc242002-08-01 02:13:36 +00001842CopyA:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001843 assert(nb == 1 && na > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001844 /* The first element of ssb belongs at the front of the merge. */
1845 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
1846 sortslice_advance(&dest, -na);
1847 sortslice_advance(&ssa, -na);
1848 sortslice_copy(&dest, 0, &ssb, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001849 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001850}
1851
1852/* Merge the two runs at stack indices i and i+1.
1853 * Returns 0 on success, -1 on error.
1854 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001855static Py_ssize_t
1856merge_at(MergeState *ms, Py_ssize_t i)
Tim Petersa64dc242002-08-01 02:13:36 +00001857{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001858 sortslice ssa, ssb;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001859 Py_ssize_t na, nb;
1860 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001861
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001862 assert(ms != NULL);
1863 assert(ms->n >= 2);
1864 assert(i >= 0);
1865 assert(i == ms->n - 2 || i == ms->n - 3);
Tim Petersa64dc242002-08-01 02:13:36 +00001866
Daniel Stutzbach98338222010-12-02 21:55:33 +00001867 ssa = ms->pending[i].base;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001868 na = ms->pending[i].len;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001869 ssb = ms->pending[i+1].base;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001870 nb = ms->pending[i+1].len;
1871 assert(na > 0 && nb > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001872 assert(ssa.keys + na == ssb.keys);
Tim Petersa64dc242002-08-01 02:13:36 +00001873
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001874 /* Record the length of the combined runs; if i is the 3rd-last
1875 * run now, also slide over the last run (which isn't involved
1876 * in this merge). The current run i+1 goes away in any case.
1877 */
1878 ms->pending[i].len = na + nb;
1879 if (i == ms->n - 3)
1880 ms->pending[i+1] = ms->pending[i+2];
1881 --ms->n;
Tim Petersa64dc242002-08-01 02:13:36 +00001882
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001883 /* Where does b start in a? Elements in a before that can be
1884 * ignored (already in place).
1885 */
embg1e34da42018-01-28 20:03:23 -07001886 k = gallop_right(ms, *ssb.keys, ssa.keys, na, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001887 if (k < 0)
1888 return -1;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001889 sortslice_advance(&ssa, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001890 na -= k;
1891 if (na == 0)
1892 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001893
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001894 /* Where does a end in b? Elements in b after that can be
1895 * ignored (already in place).
1896 */
embg1e34da42018-01-28 20:03:23 -07001897 nb = gallop_left(ms, ssa.keys[na-1], ssb.keys, nb, nb-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001898 if (nb <= 0)
1899 return nb;
Tim Petersa64dc242002-08-01 02:13:36 +00001900
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001901 /* Merge what remains of the runs, using a temp array with
1902 * min(na, nb) elements.
1903 */
1904 if (na <= nb)
Daniel Stutzbach98338222010-12-02 21:55:33 +00001905 return merge_lo(ms, ssa, na, ssb, nb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001906 else
Daniel Stutzbach98338222010-12-02 21:55:33 +00001907 return merge_hi(ms, ssa, na, ssb, nb);
Tim Petersa64dc242002-08-01 02:13:36 +00001908}
1909
1910/* Examine the stack of runs waiting to be merged, merging adjacent runs
1911 * until the stack invariants are re-established:
1912 *
1913 * 1. len[-3] > len[-2] + len[-1]
1914 * 2. len[-2] > len[-1]
1915 *
1916 * See listsort.txt for more info.
1917 *
1918 * Returns 0 on success, -1 on error.
1919 */
1920static int
1921merge_collapse(MergeState *ms)
1922{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001923 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001924
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001925 assert(ms);
1926 while (ms->n > 1) {
1927 Py_ssize_t n = ms->n - 2;
Benjamin Petersonb808d592015-02-25 10:12:26 -05001928 if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) ||
1929 (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001930 if (p[n-1].len < p[n+1].len)
1931 --n;
1932 if (merge_at(ms, n) < 0)
1933 return -1;
1934 }
1935 else if (p[n].len <= p[n+1].len) {
embg1e34da42018-01-28 20:03:23 -07001936 if (merge_at(ms, n) < 0)
1937 return -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001938 }
1939 else
1940 break;
1941 }
1942 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001943}
1944
1945/* Regardless of invariants, merge all runs on the stack until only one
1946 * remains. This is used at the end of the mergesort.
1947 *
1948 * Returns 0 on success, -1 on error.
1949 */
1950static int
1951merge_force_collapse(MergeState *ms)
1952{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001953 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001954
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001955 assert(ms);
1956 while (ms->n > 1) {
1957 Py_ssize_t n = ms->n - 2;
1958 if (n > 0 && p[n-1].len < p[n+1].len)
1959 --n;
1960 if (merge_at(ms, n) < 0)
1961 return -1;
1962 }
1963 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001964}
1965
1966/* Compute a good value for the minimum run length; natural runs shorter
1967 * than this are boosted artificially via binary insertion.
1968 *
1969 * If n < 64, return n (it's too small to bother with fancy stuff).
1970 * Else if n is an exact power of 2, return 32.
1971 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1972 * strictly less than, an exact power of 2.
1973 *
1974 * See listsort.txt for more info.
1975 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001976static Py_ssize_t
1977merge_compute_minrun(Py_ssize_t n)
Tim Petersa64dc242002-08-01 02:13:36 +00001978{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001979 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
Tim Petersa64dc242002-08-01 02:13:36 +00001980
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001981 assert(n >= 0);
1982 while (n >= 64) {
1983 r |= n & 1;
1984 n >>= 1;
1985 }
1986 return n + r;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001987}
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001988
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001989static void
Daniel Stutzbach98338222010-12-02 21:55:33 +00001990reverse_sortslice(sortslice *s, Py_ssize_t n)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001991{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001992 reverse_slice(s->keys, &s->keys[n]);
1993 if (s->values != NULL)
1994 reverse_slice(s->values, &s->values[n]);
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001995}
1996
embg1e34da42018-01-28 20:03:23 -07001997/* Here we define custom comparison functions to optimize for the cases one commonly
1998 * encounters in practice: homogeneous lists, often of one of the basic types. */
1999
2000/* This struct holds the comparison function and helper functions
2001 * selected in the pre-sort check. */
2002
2003/* These are the special case compare functions.
2004 * ms->key_compare will always point to one of these: */
2005
2006/* Heterogeneous compare: default, always safe to fall back on. */
2007static int
2008safe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
2009{
2010 /* No assumptions necessary! */
2011 return PyObject_RichCompareBool(v, w, Py_LT);
2012}
2013
2014/* Homogeneous compare: safe for any two compareable objects of the same type.
2015 * (ms->key_richcompare is set to ob_type->tp_richcompare in the
2016 * pre-sort check.)
2017 */
2018static int
2019unsafe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
2020{
2021 PyObject *res_obj; int res;
2022
2023 /* No assumptions, because we check first: */
Victor Stinner58ac7002020-02-07 03:04:21 +01002024 if (Py_TYPE(v)->tp_richcompare != ms->key_richcompare)
embg1e34da42018-01-28 20:03:23 -07002025 return PyObject_RichCompareBool(v, w, Py_LT);
2026
2027 assert(ms->key_richcompare != NULL);
2028 res_obj = (*(ms->key_richcompare))(v, w, Py_LT);
2029
2030 if (res_obj == Py_NotImplemented) {
2031 Py_DECREF(res_obj);
2032 return PyObject_RichCompareBool(v, w, Py_LT);
2033 }
2034 if (res_obj == NULL)
2035 return -1;
2036
2037 if (PyBool_Check(res_obj)) {
2038 res = (res_obj == Py_True);
2039 }
2040 else {
2041 res = PyObject_IsTrue(res_obj);
2042 }
2043 Py_DECREF(res_obj);
2044
2045 /* Note that we can't assert
2046 * res == PyObject_RichCompareBool(v, w, Py_LT);
2047 * because of evil compare functions like this:
2048 * lambda a, b: int(random.random() * 3) - 1)
2049 * (which is actually in test_sort.py) */
2050 return res;
2051}
2052
2053/* Latin string compare: safe for any two latin (one byte per char) strings. */
2054static int
2055unsafe_latin_compare(PyObject *v, PyObject *w, MergeState *ms)
2056{
Victor Stinner8017b802018-01-29 13:47:06 +01002057 Py_ssize_t len;
2058 int res;
embg1e34da42018-01-28 20:03:23 -07002059
2060 /* Modified from Objects/unicodeobject.c:unicode_compare, assuming: */
Andy Lesterdffe4c02020-03-04 07:15:20 -06002061 assert(Py_IS_TYPE(v, &PyUnicode_Type));
2062 assert(Py_IS_TYPE(w, &PyUnicode_Type));
embg1e34da42018-01-28 20:03:23 -07002063 assert(PyUnicode_KIND(v) == PyUnicode_KIND(w));
2064 assert(PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
2065
2066 len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
2067 res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);
2068
2069 res = (res != 0 ?
2070 res < 0 :
2071 PyUnicode_GET_LENGTH(v) < PyUnicode_GET_LENGTH(w));
2072
2073 assert(res == PyObject_RichCompareBool(v, w, Py_LT));;
2074 return res;
2075}
2076
2077/* Bounded int compare: compare any two longs that fit in a single machine word. */
2078static int
2079unsafe_long_compare(PyObject *v, PyObject *w, MergeState *ms)
2080{
2081 PyLongObject *vl, *wl; sdigit v0, w0; int res;
2082
2083 /* Modified from Objects/longobject.c:long_compare, assuming: */
Andy Lesterdffe4c02020-03-04 07:15:20 -06002084 assert(Py_IS_TYPE(v, &PyLong_Type));
2085 assert(Py_IS_TYPE(w, &PyLong_Type));
embg1e34da42018-01-28 20:03:23 -07002086 assert(Py_ABS(Py_SIZE(v)) <= 1);
2087 assert(Py_ABS(Py_SIZE(w)) <= 1);
2088
2089 vl = (PyLongObject*)v;
2090 wl = (PyLongObject*)w;
2091
2092 v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->ob_digit[0];
2093 w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->ob_digit[0];
2094
2095 if (Py_SIZE(vl) < 0)
2096 v0 = -v0;
2097 if (Py_SIZE(wl) < 0)
2098 w0 = -w0;
2099
2100 res = v0 < w0;
2101 assert(res == PyObject_RichCompareBool(v, w, Py_LT));
2102 return res;
2103}
2104
2105/* Float compare: compare any two floats. */
2106static int
2107unsafe_float_compare(PyObject *v, PyObject *w, MergeState *ms)
2108{
2109 int res;
2110
2111 /* Modified from Objects/floatobject.c:float_richcompare, assuming: */
Andy Lesterdffe4c02020-03-04 07:15:20 -06002112 assert(Py_IS_TYPE(v, &PyFloat_Type));
2113 assert(Py_IS_TYPE(w, &PyFloat_Type));
embg1e34da42018-01-28 20:03:23 -07002114
2115 res = PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w);
2116 assert(res == PyObject_RichCompareBool(v, w, Py_LT));
2117 return res;
2118}
2119
2120/* Tuple compare: compare *any* two tuples, using
2121 * ms->tuple_elem_compare to compare the first elements, which is set
2122 * using the same pre-sort check as we use for ms->key_compare,
2123 * but run on the list [x[0] for x in L]. This allows us to optimize compares
2124 * on two levels (as long as [x[0] for x in L] is type-homogeneous.) The idea is
2125 * that most tuple compares don't involve x[1:]. */
2126static int
2127unsafe_tuple_compare(PyObject *v, PyObject *w, MergeState *ms)
2128{
2129 PyTupleObject *vt, *wt;
2130 Py_ssize_t i, vlen, wlen;
2131 int k;
2132
2133 /* Modified from Objects/tupleobject.c:tuplerichcompare, assuming: */
Andy Lesterdffe4c02020-03-04 07:15:20 -06002134 assert(Py_IS_TYPE(v, &PyTuple_Type));
2135 assert(Py_IS_TYPE(w, &PyTuple_Type));
embg1e34da42018-01-28 20:03:23 -07002136 assert(Py_SIZE(v) > 0);
2137 assert(Py_SIZE(w) > 0);
2138
2139 vt = (PyTupleObject *)v;
2140 wt = (PyTupleObject *)w;
2141
2142 vlen = Py_SIZE(vt);
2143 wlen = Py_SIZE(wt);
2144
2145 for (i = 0; i < vlen && i < wlen; i++) {
2146 k = PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_EQ);
2147 if (k < 0)
2148 return -1;
2149 if (!k)
2150 break;
2151 }
2152
2153 if (i >= vlen || i >= wlen)
2154 return vlen < wlen;
2155
2156 if (i == 0)
2157 return ms->tuple_elem_compare(vt->ob_item[i], wt->ob_item[i], ms);
2158 else
2159 return PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_LT);
2160}
2161
Tim Petersa64dc242002-08-01 02:13:36 +00002162/* An adaptive, stable, natural mergesort. See listsort.txt.
2163 * Returns Py_None on success, NULL on error. Even in case of error, the
2164 * list will be some permutation of its input state (nothing is lost or
2165 * duplicated).
2166 */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002167/*[clinic input]
2168list.sort
2169
2170 *
2171 key as keyfunc: object = None
Serhiy Storchaka202fda52017-03-12 10:10:47 +02002172 reverse: bool(accept={int}) = False
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002173
Tim Hoffmann5c224762019-06-01 06:10:02 +02002174Sort the list in ascending order and return None.
2175
2176The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
2177order of two equal elements is maintained).
2178
2179If a key function is given, apply it once to each list item and sort them,
2180ascending or descending, according to their function values.
2181
2182The reverse flag can be set to sort in descending order.
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002183[clinic start generated code]*/
2184
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002185static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002186list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
Tim Hoffmann5c224762019-06-01 06:10:02 +02002187/*[clinic end generated code: output=57b9f9c5e23fbe42 input=cb56cd179a713060]*/
Guido van Rossum3f236de1996-12-10 23:55:39 +00002188{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002189 MergeState ms;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002190 Py_ssize_t nremaining;
2191 Py_ssize_t minrun;
Daniel Stutzbach98338222010-12-02 21:55:33 +00002192 sortslice lo;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002193 Py_ssize_t saved_ob_size, saved_allocated;
2194 PyObject **saved_ob_item;
2195 PyObject **final_ob_item;
2196 PyObject *result = NULL; /* guilty until proved innocent */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002197 Py_ssize_t i;
Daniel Stutzbach98338222010-12-02 21:55:33 +00002198 PyObject **keys;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002199
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002200 assert(self != NULL);
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002201 assert(PyList_Check(self));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002202 if (keyfunc == Py_None)
2203 keyfunc = NULL;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002204
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002205 /* The list is temporarily made empty, so that mutations performed
2206 * by comparison functions can't affect the slice of memory we're
2207 * sorting (allowing mutations during sorting is a core-dump
2208 * factory, since ob_item may change).
2209 */
2210 saved_ob_size = Py_SIZE(self);
2211 saved_ob_item = self->ob_item;
2212 saved_allocated = self->allocated;
Victor Stinner60ac6ed2020-02-07 23:18:08 +01002213 Py_SET_SIZE(self, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002214 self->ob_item = NULL;
2215 self->allocated = -1; /* any operation will reset it to >= 0 */
Tim Peters330f9e92002-07-19 07:05:44 +00002216
Daniel Stutzbach98338222010-12-02 21:55:33 +00002217 if (keyfunc == NULL) {
2218 keys = NULL;
2219 lo.keys = saved_ob_item;
2220 lo.values = NULL;
2221 }
2222 else {
2223 if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
2224 /* Leverage stack space we allocated but won't otherwise use */
2225 keys = &ms.temparray[saved_ob_size+1];
2226 else {
2227 keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);
Benjamin Peterson0823ffb2015-04-23 17:04:36 -04002228 if (keys == NULL) {
2229 PyErr_NoMemory();
2230 goto keyfunc_fail;
2231 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002232 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00002233
2234 for (i = 0; i < saved_ob_size ; i++) {
Petr Viktorinffd97532020-02-11 17:46:57 +01002235 keys[i] = PyObject_CallOneArg(keyfunc, saved_ob_item[i]);
Daniel Stutzbach98338222010-12-02 21:55:33 +00002236 if (keys[i] == NULL) {
2237 for (i=i-1 ; i>=0 ; i--)
2238 Py_DECREF(keys[i]);
Benjamin Peterson4a42cd42014-03-15 12:21:28 -05002239 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
Daniel Stutzbach8eda5f72011-03-02 23:37:50 +00002240 PyMem_FREE(keys);
Daniel Stutzbach98338222010-12-02 21:55:33 +00002241 goto keyfunc_fail;
2242 }
2243 }
2244
2245 lo.keys = keys;
2246 lo.values = saved_ob_item;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002247 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002248
embg1e34da42018-01-28 20:03:23 -07002249
2250 /* The pre-sort check: here's where we decide which compare function to use.
2251 * How much optimization is safe? We test for homogeneity with respect to
2252 * several properties that are expensive to check at compare-time, and
2253 * set ms appropriately. */
2254 if (saved_ob_size > 1) {
2255 /* Assume the first element is representative of the whole list. */
Andy Lesterdffe4c02020-03-04 07:15:20 -06002256 int keys_are_in_tuples = (Py_IS_TYPE(lo.keys[0], &PyTuple_Type) &&
embg1e34da42018-01-28 20:03:23 -07002257 Py_SIZE(lo.keys[0]) > 0);
2258
2259 PyTypeObject* key_type = (keys_are_in_tuples ?
Victor Stinner58ac7002020-02-07 03:04:21 +01002260 Py_TYPE(PyTuple_GET_ITEM(lo.keys[0], 0)) :
2261 Py_TYPE(lo.keys[0]));
embg1e34da42018-01-28 20:03:23 -07002262
2263 int keys_are_all_same_type = 1;
2264 int strings_are_latin = 1;
2265 int ints_are_bounded = 1;
2266
2267 /* Prove that assumption by checking every key. */
embg1e34da42018-01-28 20:03:23 -07002268 for (i=0; i < saved_ob_size; i++) {
2269
2270 if (keys_are_in_tuples &&
Andy Lesterdffe4c02020-03-04 07:15:20 -06002271 !(Py_IS_TYPE(lo.keys[i], &PyTuple_Type) && Py_SIZE(lo.keys[i]) != 0)) {
embg1e34da42018-01-28 20:03:23 -07002272 keys_are_in_tuples = 0;
2273 keys_are_all_same_type = 0;
2274 break;
2275 }
2276
2277 /* Note: for lists of tuples, key is the first element of the tuple
2278 * lo.keys[i], not lo.keys[i] itself! We verify type-homogeneity
2279 * for lists of tuples in the if-statement directly above. */
2280 PyObject *key = (keys_are_in_tuples ?
2281 PyTuple_GET_ITEM(lo.keys[i], 0) :
2282 lo.keys[i]);
2283
Andy Lesterdffe4c02020-03-04 07:15:20 -06002284 if (!Py_IS_TYPE(key, key_type)) {
embg1e34da42018-01-28 20:03:23 -07002285 keys_are_all_same_type = 0;
Rémi Lapeyredd5417a2019-03-25 08:25:37 +01002286 /* If keys are in tuple we must loop over the whole list to make
2287 sure all items are tuples */
2288 if (!keys_are_in_tuples) {
2289 break;
2290 }
embg1e34da42018-01-28 20:03:23 -07002291 }
2292
Rémi Lapeyredd5417a2019-03-25 08:25:37 +01002293 if (keys_are_all_same_type) {
2294 if (key_type == &PyLong_Type &&
2295 ints_are_bounded &&
2296 Py_ABS(Py_SIZE(key)) > 1) {
2297
embg1e34da42018-01-28 20:03:23 -07002298 ints_are_bounded = 0;
Rémi Lapeyredd5417a2019-03-25 08:25:37 +01002299 }
2300 else if (key_type == &PyUnicode_Type &&
2301 strings_are_latin &&
2302 PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND) {
2303
2304 strings_are_latin = 0;
2305 }
2306 }
embg1e34da42018-01-28 20:03:23 -07002307 }
embg1e34da42018-01-28 20:03:23 -07002308
2309 /* Choose the best compare, given what we now know about the keys. */
2310 if (keys_are_all_same_type) {
2311
2312 if (key_type == &PyUnicode_Type && strings_are_latin) {
2313 ms.key_compare = unsafe_latin_compare;
2314 }
2315 else if (key_type == &PyLong_Type && ints_are_bounded) {
2316 ms.key_compare = unsafe_long_compare;
2317 }
2318 else if (key_type == &PyFloat_Type) {
2319 ms.key_compare = unsafe_float_compare;
2320 }
2321 else if ((ms.key_richcompare = key_type->tp_richcompare) != NULL) {
2322 ms.key_compare = unsafe_object_compare;
2323 }
Zackery Spytzebc793d2019-02-21 00:47:14 -07002324 else {
2325 ms.key_compare = safe_object_compare;
2326 }
embg1e34da42018-01-28 20:03:23 -07002327 }
2328 else {
2329 ms.key_compare = safe_object_compare;
2330 }
2331
2332 if (keys_are_in_tuples) {
2333 /* Make sure we're not dealing with tuples of tuples
2334 * (remember: here, key_type refers list [key[0] for key in keys]) */
Rémi Lapeyredd5417a2019-03-25 08:25:37 +01002335 if (key_type == &PyTuple_Type) {
embg1e34da42018-01-28 20:03:23 -07002336 ms.tuple_elem_compare = safe_object_compare;
Rémi Lapeyredd5417a2019-03-25 08:25:37 +01002337 }
2338 else {
embg1e34da42018-01-28 20:03:23 -07002339 ms.tuple_elem_compare = ms.key_compare;
Rémi Lapeyredd5417a2019-03-25 08:25:37 +01002340 }
embg1e34da42018-01-28 20:03:23 -07002341
2342 ms.key_compare = unsafe_tuple_compare;
2343 }
2344 }
2345 /* End of pre-sort check: ms is now set properly! */
2346
Daniel Stutzbach98338222010-12-02 21:55:33 +00002347 merge_init(&ms, saved_ob_size, keys != NULL);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002348
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002349 nremaining = saved_ob_size;
2350 if (nremaining < 2)
2351 goto succeed;
Tim Peters330f9e92002-07-19 07:05:44 +00002352
Benjamin Peterson05380642010-08-23 19:35:39 +00002353 /* Reverse sort stability achieved by initially reversing the list,
2354 applying a stable forward sort, then reversing the final result. */
Daniel Stutzbach98338222010-12-02 21:55:33 +00002355 if (reverse) {
2356 if (keys != NULL)
2357 reverse_slice(&keys[0], &keys[saved_ob_size]);
2358 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
2359 }
Benjamin Peterson05380642010-08-23 19:35:39 +00002360
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002361 /* March over the array once, left to right, finding natural runs,
2362 * and extending short natural runs to minrun elements.
2363 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002364 minrun = merge_compute_minrun(nremaining);
2365 do {
2366 int descending;
2367 Py_ssize_t n;
Tim Peters330f9e92002-07-19 07:05:44 +00002368
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002369 /* Identify next run. */
embg1e34da42018-01-28 20:03:23 -07002370 n = count_run(&ms, lo.keys, lo.keys + nremaining, &descending);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002371 if (n < 0)
2372 goto fail;
2373 if (descending)
Daniel Stutzbach98338222010-12-02 21:55:33 +00002374 reverse_sortslice(&lo, n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002375 /* If short, extend to min(minrun, nremaining). */
2376 if (n < minrun) {
2377 const Py_ssize_t force = nremaining <= minrun ?
2378 nremaining : minrun;
embg1e34da42018-01-28 20:03:23 -07002379 if (binarysort(&ms, lo, lo.keys + force, lo.keys + n) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002380 goto fail;
2381 n = force;
2382 }
2383 /* Push run onto pending-runs stack, and maybe merge. */
2384 assert(ms.n < MAX_MERGE_PENDING);
2385 ms.pending[ms.n].base = lo;
2386 ms.pending[ms.n].len = n;
2387 ++ms.n;
2388 if (merge_collapse(&ms) < 0)
2389 goto fail;
2390 /* Advance to find next run. */
Daniel Stutzbach98338222010-12-02 21:55:33 +00002391 sortslice_advance(&lo, n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002392 nremaining -= n;
2393 } while (nremaining);
Tim Peters330f9e92002-07-19 07:05:44 +00002394
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002395 if (merge_force_collapse(&ms) < 0)
2396 goto fail;
2397 assert(ms.n == 1);
Daniel Stutzbach98338222010-12-02 21:55:33 +00002398 assert(keys == NULL
2399 ? ms.pending[0].base.keys == saved_ob_item
2400 : ms.pending[0].base.keys == &keys[0]);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002401 assert(ms.pending[0].len == saved_ob_size);
Daniel Stutzbach98338222010-12-02 21:55:33 +00002402 lo = ms.pending[0].base;
Tim Petersa64dc242002-08-01 02:13:36 +00002403
2404succeed:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002405 result = Py_None;
Tim Peters330f9e92002-07-19 07:05:44 +00002406fail:
Daniel Stutzbach98338222010-12-02 21:55:33 +00002407 if (keys != NULL) {
2408 for (i = 0; i < saved_ob_size; i++)
2409 Py_DECREF(keys[i]);
Benjamin Petersonef87f8c2014-03-14 21:54:31 -05002410 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
Daniel Stutzbach98338222010-12-02 21:55:33 +00002411 PyMem_FREE(keys);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002412 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002413
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002414 if (self->allocated != -1 && result != NULL) {
2415 /* The user mucked with the list during the sort,
2416 * and we don't already have another error to report.
2417 */
2418 PyErr_SetString(PyExc_ValueError, "list modified during sort");
2419 result = NULL;
2420 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002421
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002422 if (reverse && saved_ob_size > 1)
2423 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002424
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002425 merge_freemem(&ms);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002426
Daniel Stutzbach98338222010-12-02 21:55:33 +00002427keyfunc_fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002428 final_ob_item = self->ob_item;
2429 i = Py_SIZE(self);
Victor Stinner60ac6ed2020-02-07 23:18:08 +01002430 Py_SET_SIZE(self, saved_ob_size);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002431 self->ob_item = saved_ob_item;
2432 self->allocated = saved_allocated;
2433 if (final_ob_item != NULL) {
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002434 /* we cannot use _list_clear() for this because it does not
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002435 guarantee that the list is really empty when it returns */
2436 while (--i >= 0) {
2437 Py_XDECREF(final_ob_item[i]);
2438 }
2439 PyMem_FREE(final_ob_item);
2440 }
2441 Py_XINCREF(result);
2442 return result;
Guido van Rossum3f236de1996-12-10 23:55:39 +00002443}
Tim Peters330f9e92002-07-19 07:05:44 +00002444#undef IFLT
Tim Peters66860f62002-08-04 17:47:26 +00002445#undef ISLT
Tim Peters330f9e92002-07-19 07:05:44 +00002446
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002447int
Fred Drakea2f55112000-07-09 15:16:51 +00002448PyList_Sort(PyObject *v)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002449{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002450 if (v == NULL || !PyList_Check(v)) {
2451 PyErr_BadInternalCall();
2452 return -1;
2453 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002454 v = list_sort_impl((PyListObject *)v, NULL, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002455 if (v == NULL)
2456 return -1;
2457 Py_DECREF(v);
2458 return 0;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002459}
2460
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002461/*[clinic input]
2462list.reverse
2463
2464Reverse *IN PLACE*.
2465[clinic start generated code]*/
2466
Guido van Rossumb86c5492001-02-12 22:06:02 +00002467static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002468list_reverse_impl(PyListObject *self)
2469/*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
Guido van Rossumb86c5492001-02-12 22:06:02 +00002470{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002471 if (Py_SIZE(self) > 1)
2472 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2473 Py_RETURN_NONE;
Guido van Rossumed98d481991-03-06 13:07:53 +00002474}
2475
Guido van Rossum84c76f51990-10-30 13:32:20 +00002476int
Fred Drakea2f55112000-07-09 15:16:51 +00002477PyList_Reverse(PyObject *v)
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002478{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002479 PyListObject *self = (PyListObject *)v;
Tim Peters6063e262002-08-08 01:06:39 +00002480
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002481 if (v == NULL || !PyList_Check(v)) {
2482 PyErr_BadInternalCall();
2483 return -1;
2484 }
2485 if (Py_SIZE(self) > 1)
2486 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2487 return 0;
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002488}
2489
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002490PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00002491PyList_AsTuple(PyObject *v)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002492{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002493 if (v == NULL || !PyList_Check(v)) {
2494 PyErr_BadInternalCall();
2495 return NULL;
2496 }
Sergey Fedoseev234531b2019-02-25 21:59:12 +05002497 return _PyTuple_FromArray(((PyListObject *)v)->ob_item, Py_SIZE(v));
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002498}
2499
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002500/*[clinic input]
2501list.index
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002502
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002503 value: object
Serhiy Storchaka80ec8362017-03-19 19:37:40 +02002504 start: slice_index(accept={int}) = 0
2505 stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002506 /
2507
2508Return first index of value.
2509
2510Raises ValueError if the value is not present.
2511[clinic start generated code]*/
2512
2513static PyObject *
2514list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
2515 Py_ssize_t stop)
Serhiy Storchaka80ec8362017-03-19 19:37:40 +02002516/*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002517{
2518 Py_ssize_t i;
2519
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002520 if (start < 0) {
2521 start += Py_SIZE(self);
2522 if (start < 0)
2523 start = 0;
2524 }
2525 if (stop < 0) {
2526 stop += Py_SIZE(self);
2527 if (stop < 0)
2528 stop = 0;
2529 }
2530 for (i = start; i < stop && i < Py_SIZE(self); i++) {
Zackery Spytzd9e561d2019-12-30 12:32:58 -07002531 PyObject *obj = self->ob_item[i];
2532 Py_INCREF(obj);
2533 int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2534 Py_DECREF(obj);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002535 if (cmp > 0)
2536 return PyLong_FromSsize_t(i);
2537 else if (cmp < 0)
2538 return NULL;
2539 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002540 PyErr_Format(PyExc_ValueError, "%R is not in list", value);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002541 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002542}
2543
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002544/*[clinic input]
2545list.count
2546
2547 value: object
2548 /
2549
2550Return number of occurrences of value.
2551[clinic start generated code]*/
2552
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002553static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002554list_count(PyListObject *self, PyObject *value)
2555/*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
Guido van Rossume6f7d181991-10-20 20:20:40 +00002556{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002557 Py_ssize_t count = 0;
2558 Py_ssize_t i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002559
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002560 for (i = 0; i < Py_SIZE(self); i++) {
Zackery Spytzd9e561d2019-12-30 12:32:58 -07002561 PyObject *obj = self->ob_item[i];
Dong-hee Na14d80d02020-01-23 02:36:54 +09002562 if (obj == value) {
2563 count++;
2564 continue;
2565 }
Zackery Spytzd9e561d2019-12-30 12:32:58 -07002566 Py_INCREF(obj);
2567 int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2568 Py_DECREF(obj);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002569 if (cmp > 0)
2570 count++;
2571 else if (cmp < 0)
2572 return NULL;
2573 }
2574 return PyLong_FromSsize_t(count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00002575}
2576
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002577/*[clinic input]
2578list.remove
2579
2580 value: object
2581 /
2582
2583Remove first occurrence of value.
2584
2585Raises ValueError if the value is not present.
2586[clinic start generated code]*/
2587
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002588static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002589list_remove(PyListObject *self, PyObject *value)
2590/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
Guido van Rossumed98d481991-03-06 13:07:53 +00002591{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002592 Py_ssize_t i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002593
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002594 for (i = 0; i < Py_SIZE(self); i++) {
Zackery Spytzd9e561d2019-12-30 12:32:58 -07002595 PyObject *obj = self->ob_item[i];
2596 Py_INCREF(obj);
2597 int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2598 Py_DECREF(obj);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002599 if (cmp > 0) {
2600 if (list_ass_slice(self, i, i+1,
2601 (PyObject *)NULL) == 0)
2602 Py_RETURN_NONE;
2603 return NULL;
2604 }
2605 else if (cmp < 0)
2606 return NULL;
2607 }
2608 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
2609 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002610}
2611
Jeremy Hylton8caad492000-06-23 14:18:11 +00002612static int
2613list_traverse(PyListObject *o, visitproc visit, void *arg)
2614{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002615 Py_ssize_t i;
Jeremy Hylton8caad492000-06-23 14:18:11 +00002616
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002617 for (i = Py_SIZE(o); --i >= 0; )
2618 Py_VISIT(o->ob_item[i]);
2619 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00002620}
2621
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002622static PyObject *
2623list_richcompare(PyObject *v, PyObject *w, int op)
2624{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002625 PyListObject *vl, *wl;
2626 Py_ssize_t i;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002627
Brian Curtindfc80e32011-08-10 20:28:54 -05002628 if (!PyList_Check(v) || !PyList_Check(w))
2629 Py_RETURN_NOTIMPLEMENTED;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002630
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002631 vl = (PyListObject *)v;
2632 wl = (PyListObject *)w;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002633
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002634 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
2635 /* Shortcut: if the lengths differ, the lists differ */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002636 if (op == Py_EQ)
stratakise8b19652017-11-02 11:32:54 +01002637 Py_RETURN_FALSE;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002638 else
stratakise8b19652017-11-02 11:32:54 +01002639 Py_RETURN_TRUE;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002640 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002641
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002642 /* Search for the first index where items are different */
2643 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
Dong-hee Na2d5bf562019-12-31 10:04:22 +09002644 PyObject *vitem = vl->ob_item[i];
2645 PyObject *witem = wl->ob_item[i];
Inada Naokidfef9862019-12-31 10:58:37 +09002646 if (vitem == witem) {
2647 continue;
2648 }
Dong-hee Na2d5bf562019-12-31 10:04:22 +09002649
2650 Py_INCREF(vitem);
2651 Py_INCREF(witem);
sweeneydebe7ead62020-02-26 02:00:35 -05002652 int k = PyObject_RichCompareBool(vitem, witem, Py_EQ);
Dong-hee Na2d5bf562019-12-31 10:04:22 +09002653 Py_DECREF(vitem);
2654 Py_DECREF(witem);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002655 if (k < 0)
2656 return NULL;
2657 if (!k)
2658 break;
2659 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002660
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002661 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
2662 /* No more items to compare -- compare sizes */
stratakise8b19652017-11-02 11:32:54 +01002663 Py_RETURN_RICHCOMPARE(Py_SIZE(vl), Py_SIZE(wl), op);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002664 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002665
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002666 /* We have an item that differs -- shortcuts for EQ/NE */
2667 if (op == Py_EQ) {
Serhiy Storchaka228b12e2017-01-23 09:47:21 +02002668 Py_RETURN_FALSE;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002669 }
2670 if (op == Py_NE) {
Serhiy Storchaka228b12e2017-01-23 09:47:21 +02002671 Py_RETURN_TRUE;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002672 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002673
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002674 /* Compare the final item again using the proper operator */
2675 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002676}
2677
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002678/*[clinic input]
2679list.__init__
2680
2681 iterable: object(c_default="NULL") = ()
2682 /
2683
2684Built-in mutable sequence.
2685
2686If no argument is given, the constructor creates a new empty list.
2687The argument must be an iterable if specified.
2688[clinic start generated code]*/
2689
Tim Peters6d6c1a32001-08-02 04:15:00 +00002690static int
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002691list___init___impl(PyListObject *self, PyObject *iterable)
2692/*[clinic end generated code: output=0f3c21379d01de48 input=b3f3fe7206af8f6b]*/
Tim Peters6d6c1a32001-08-02 04:15:00 +00002693{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002694 /* Verify list invariants established by PyType_GenericAlloc() */
2695 assert(0 <= Py_SIZE(self));
2696 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
2697 assert(self->ob_item != NULL ||
2698 self->allocated == 0 || self->allocated == -1);
Raymond Hettingerc0aaa2d2004-07-29 23:31:29 +00002699
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002700 /* Empty previous contents */
2701 if (self->ob_item != NULL) {
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002702 (void)_list_clear(self);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002703 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002704 if (iterable != NULL) {
Pablo Galindo372d7052018-10-28 20:16:26 +00002705 if (_PyObject_HasLen(iterable)) {
2706 Py_ssize_t iter_len = PyObject_Size(iterable);
2707 if (iter_len == -1) {
2708 if (!PyErr_ExceptionMatches(PyExc_TypeError)) {
2709 return -1;
2710 }
2711 PyErr_Clear();
2712 }
2713 if (iter_len > 0 && self->ob_item == NULL
2714 && list_preallocate_exact(self, iter_len)) {
2715 return -1;
2716 }
2717 }
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002718 PyObject *rv = list_extend(self, iterable);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002719 if (rv == NULL)
2720 return -1;
2721 Py_DECREF(rv);
2722 }
2723 return 0;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002724}
2725
Petr Viktorince105542020-03-30 14:16:16 +02002726static PyObject *
2727list_vectorcall(PyObject *type, PyObject * const*args,
2728 size_t nargsf, PyObject *kwnames)
2729{
2730 if (!_PyArg_NoKwnames("list", kwnames)) {
2731 return NULL;
2732 }
2733 Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
2734 if (!_PyArg_CheckPositional("list", nargs, 0, 1)) {
2735 return NULL;
2736 }
2737
2738 assert(PyType_Check(type));
2739 PyObject *list = PyType_GenericAlloc((PyTypeObject *)type, 0);
2740 if (list == NULL) {
2741 return NULL;
2742 }
2743 if (nargs) {
2744 if (list___init___impl((PyListObject *)list, args[0])) {
2745 Py_DECREF(list);
2746 return NULL;
2747 }
2748 }
2749 return list;
2750}
2751
2752
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002753/*[clinic input]
2754list.__sizeof__
2755
2756Return the size of the list in memory, in bytes.
2757[clinic start generated code]*/
2758
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002759static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002760list___sizeof___impl(PyListObject *self)
2761/*[clinic end generated code: output=3417541f95f9a53e input=b8030a5d5ce8a187]*/
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002762{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002763 Py_ssize_t res;
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002764
Serhiy Storchaka5c4064e2015-12-19 20:05:25 +02002765 res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002766 return PyLong_FromSsize_t(res);
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002767}
2768
Raymond Hettinger1021c442003-11-07 15:38:09 +00002769static PyObject *list_iter(PyObject *seq);
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002770static PyObject *list_subscript(PyListObject*, PyObject*);
2771
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002772static PyMethodDef list_methods[] = {
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02002773 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, "x.__getitem__(y) <==> x[y]"},
2774 LIST___REVERSED___METHODDEF
2775 LIST___SIZEOF___METHODDEF
2776 LIST_CLEAR_METHODDEF
2777 LIST_COPY_METHODDEF
2778 LIST_APPEND_METHODDEF
2779 LIST_INSERT_METHODDEF
2780 LIST_EXTEND_METHODDEF
2781 LIST_POP_METHODDEF
2782 LIST_REMOVE_METHODDEF
2783 LIST_INDEX_METHODDEF
2784 LIST_COUNT_METHODDEF
2785 LIST_REVERSE_METHODDEF
2786 LIST_SORT_METHODDEF
Guido van Rossum48b069a2020-04-07 09:50:06 -07002787 {"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002788 {NULL, NULL} /* sentinel */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002789};
2790
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002791static PySequenceMethods list_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002792 (lenfunc)list_length, /* sq_length */
2793 (binaryfunc)list_concat, /* sq_concat */
2794 (ssizeargfunc)list_repeat, /* sq_repeat */
2795 (ssizeargfunc)list_item, /* sq_item */
2796 0, /* sq_slice */
2797 (ssizeobjargproc)list_ass_item, /* sq_ass_item */
2798 0, /* sq_ass_slice */
2799 (objobjproc)list_contains, /* sq_contains */
2800 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
2801 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002802};
2803
Jeremy Hyltona4b4c3b2002-07-13 03:51:17 +00002804static PyObject *
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002805list_subscript(PyListObject* self, PyObject* item)
2806{
Victor Stinnera15e2602020-04-08 02:01:56 +02002807 if (_PyIndex_Check(item)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002808 Py_ssize_t i;
2809 i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2810 if (i == -1 && PyErr_Occurred())
2811 return NULL;
2812 if (i < 0)
2813 i += PyList_GET_SIZE(self);
2814 return list_item(self, i);
2815 }
2816 else if (PySlice_Check(item)) {
HongWeipeng3c87a662019-09-08 18:15:56 +08002817 Py_ssize_t start, stop, step, slicelength, i;
2818 size_t cur;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002819 PyObject* result;
2820 PyObject* it;
2821 PyObject **src, **dest;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002822
Serhiy Storchakab879fe82017-04-08 09:53:51 +03002823 if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002824 return NULL;
2825 }
Serhiy Storchakab879fe82017-04-08 09:53:51 +03002826 slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2827 step);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002828
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002829 if (slicelength <= 0) {
2830 return PyList_New(0);
2831 }
2832 else if (step == 1) {
2833 return list_slice(self, start, stop);
2834 }
2835 else {
Sergey Fedoseev2fc46972018-08-11 18:12:07 +05002836 result = list_new_prealloc(slicelength);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002837 if (!result) return NULL;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002838
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002839 src = self->ob_item;
2840 dest = ((PyListObject *)result)->ob_item;
2841 for (cur = start, i = 0; i < slicelength;
Mark Dickinsonc7d93b72011-09-25 15:34:32 +01002842 cur += (size_t)step, i++) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002843 it = src[cur];
2844 Py_INCREF(it);
2845 dest[i] = it;
2846 }
Victor Stinner60ac6ed2020-02-07 23:18:08 +01002847 Py_SET_SIZE(result, slicelength);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002848 return result;
2849 }
2850 }
2851 else {
2852 PyErr_Format(PyExc_TypeError,
Terry Jan Reedyffff1442014-08-02 01:30:37 -04002853 "list indices must be integers or slices, not %.200s",
Victor Stinner58ac7002020-02-07 03:04:21 +01002854 Py_TYPE(item)->tp_name);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002855 return NULL;
2856 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002857}
2858
Tim Peters3b01a122002-07-19 02:35:45 +00002859static int
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002860list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2861{
Victor Stinnera15e2602020-04-08 02:01:56 +02002862 if (_PyIndex_Check(item)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002863 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2864 if (i == -1 && PyErr_Occurred())
2865 return -1;
2866 if (i < 0)
2867 i += PyList_GET_SIZE(self);
2868 return list_ass_item(self, i, value);
2869 }
2870 else if (PySlice_Check(item)) {
2871 Py_ssize_t start, stop, step, slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002872
Serhiy Storchakab879fe82017-04-08 09:53:51 +03002873 if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002874 return -1;
2875 }
Serhiy Storchakab879fe82017-04-08 09:53:51 +03002876 slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2877 step);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002878
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002879 if (step == 1)
2880 return list_ass_slice(self, start, stop, value);
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002881
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002882 /* Make sure s[5:2] = [..] inserts at the right place:
2883 before 5, not before 2. */
2884 if ((step < 0 && start < stop) ||
2885 (step > 0 && start > stop))
2886 stop = start;
Thomas Woutersed03b412007-08-28 21:37:11 +00002887
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002888 if (value == NULL) {
2889 /* delete slice */
2890 PyObject **garbage;
2891 size_t cur;
2892 Py_ssize_t i;
Victor Stinner35f28032013-11-21 12:16:35 +01002893 int res;
Tim Peters3b01a122002-07-19 02:35:45 +00002894
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002895 if (slicelength <= 0)
2896 return 0;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002897
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002898 if (step < 0) {
2899 stop = start + 1;
2900 start = stop + step*(slicelength - 1) - 1;
2901 step = -step;
2902 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002903
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002904 garbage = (PyObject**)
2905 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2906 if (!garbage) {
2907 PyErr_NoMemory();
2908 return -1;
2909 }
Tim Peters3b01a122002-07-19 02:35:45 +00002910
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002911 /* drawing pictures might help understand these for
2912 loops. Basically, we memmove the parts of the
2913 list that are *not* part of the slice: step-1
2914 items for each item that is part of the slice,
2915 and then tail end of the list that was not
2916 covered by the slice */
2917 for (cur = start, i = 0;
2918 cur < (size_t)stop;
2919 cur += step, i++) {
2920 Py_ssize_t lim = step - 1;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002921
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002922 garbage[i] = PyList_GET_ITEM(self, cur);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002923
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002924 if (cur + step >= (size_t)Py_SIZE(self)) {
2925 lim = Py_SIZE(self) - cur - 1;
2926 }
Michael W. Hudson56796f62002-07-29 14:35:04 +00002927
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002928 memmove(self->ob_item + cur - i,
2929 self->ob_item + cur + 1,
2930 lim * sizeof(PyObject *));
2931 }
Mark Dickinsonc7d93b72011-09-25 15:34:32 +01002932 cur = start + (size_t)slicelength * step;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002933 if (cur < (size_t)Py_SIZE(self)) {
2934 memmove(self->ob_item + cur - slicelength,
2935 self->ob_item + cur,
2936 (Py_SIZE(self) - cur) *
2937 sizeof(PyObject *));
2938 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002939
Victor Stinner60ac6ed2020-02-07 23:18:08 +01002940 Py_SET_SIZE(self, Py_SIZE(self) - slicelength);
Victor Stinner35f28032013-11-21 12:16:35 +01002941 res = list_resize(self, Py_SIZE(self));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002942
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002943 for (i = 0; i < slicelength; i++) {
2944 Py_DECREF(garbage[i]);
2945 }
2946 PyMem_FREE(garbage);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002947
Victor Stinner35f28032013-11-21 12:16:35 +01002948 return res;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002949 }
2950 else {
2951 /* assign slice */
2952 PyObject *ins, *seq;
2953 PyObject **garbage, **seqitems, **selfitems;
HongWeipeng3c87a662019-09-08 18:15:56 +08002954 Py_ssize_t i;
2955 size_t cur;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002956
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002957 /* protect against a[::-1] = a */
2958 if (self == (PyListObject*)value) {
2959 seq = list_slice((PyListObject*)value, 0,
2960 PyList_GET_SIZE(value));
2961 }
2962 else {
2963 seq = PySequence_Fast(value,
2964 "must assign iterable "
2965 "to extended slice");
2966 }
2967 if (!seq)
2968 return -1;
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002969
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002970 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2971 PyErr_Format(PyExc_ValueError,
2972 "attempt to assign sequence of "
2973 "size %zd to extended slice of "
2974 "size %zd",
2975 PySequence_Fast_GET_SIZE(seq),
2976 slicelength);
2977 Py_DECREF(seq);
2978 return -1;
2979 }
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002980
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002981 if (!slicelength) {
2982 Py_DECREF(seq);
2983 return 0;
2984 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002985
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002986 garbage = (PyObject**)
2987 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2988 if (!garbage) {
2989 Py_DECREF(seq);
2990 PyErr_NoMemory();
2991 return -1;
2992 }
Tim Peters3b01a122002-07-19 02:35:45 +00002993
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002994 selfitems = self->ob_item;
2995 seqitems = PySequence_Fast_ITEMS(seq);
2996 for (cur = start, i = 0; i < slicelength;
Mark Dickinsonc7d93b72011-09-25 15:34:32 +01002997 cur += (size_t)step, i++) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002998 garbage[i] = selfitems[cur];
2999 ins = seqitems[i];
3000 Py_INCREF(ins);
3001 selfitems[cur] = ins;
3002 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00003003
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003004 for (i = 0; i < slicelength; i++) {
3005 Py_DECREF(garbage[i]);
3006 }
Tim Peters3b01a122002-07-19 02:35:45 +00003007
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003008 PyMem_FREE(garbage);
3009 Py_DECREF(seq);
Tim Peters3b01a122002-07-19 02:35:45 +00003010
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003011 return 0;
3012 }
3013 }
3014 else {
3015 PyErr_Format(PyExc_TypeError,
Terry Jan Reedyffff1442014-08-02 01:30:37 -04003016 "list indices must be integers or slices, not %.200s",
Victor Stinner58ac7002020-02-07 03:04:21 +01003017 Py_TYPE(item)->tp_name);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003018 return -1;
3019 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00003020}
3021
3022static PyMappingMethods list_as_mapping = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003023 (lenfunc)list_length,
3024 (binaryfunc)list_subscript,
3025 (objobjargproc)list_ass_subscript
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00003026};
3027
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003028PyTypeObject PyList_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003029 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3030 "list",
3031 sizeof(PyListObject),
3032 0,
3033 (destructor)list_dealloc, /* tp_dealloc */
Jeroen Demeyer530f5062019-05-31 04:13:39 +02003034 0, /* tp_vectorcall_offset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003035 0, /* tp_getattr */
3036 0, /* tp_setattr */
Jeroen Demeyer530f5062019-05-31 04:13:39 +02003037 0, /* tp_as_async */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003038 (reprfunc)list_repr, /* tp_repr */
3039 0, /* tp_as_number */
3040 &list_as_sequence, /* tp_as_sequence */
3041 &list_as_mapping, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00003042 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003043 0, /* tp_call */
3044 0, /* tp_str */
3045 PyObject_GenericGetAttr, /* tp_getattro */
3046 0, /* tp_setattro */
3047 0, /* tp_as_buffer */
3048 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02003049 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
3050 list___init____doc__, /* tp_doc */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003051 (traverseproc)list_traverse, /* tp_traverse */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02003052 (inquiry)_list_clear, /* tp_clear */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003053 list_richcompare, /* tp_richcompare */
3054 0, /* tp_weaklistoffset */
3055 list_iter, /* tp_iter */
3056 0, /* tp_iternext */
3057 list_methods, /* tp_methods */
3058 0, /* tp_members */
3059 0, /* tp_getset */
3060 0, /* tp_base */
3061 0, /* tp_dict */
3062 0, /* tp_descr_get */
3063 0, /* tp_descr_set */
3064 0, /* tp_dictoffset */
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02003065 (initproc)list___init__, /* tp_init */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003066 PyType_GenericAlloc, /* tp_alloc */
3067 PyType_GenericNew, /* tp_new */
3068 PyObject_GC_Del, /* tp_free */
Petr Viktorince105542020-03-30 14:16:16 +02003069 .tp_vectorcall = list_vectorcall,
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00003070};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00003071
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00003072/*********************** List Iterator **************************/
3073
3074typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003075 PyObject_HEAD
Victor Stinner7660b882013-06-24 23:59:24 +02003076 Py_ssize_t it_index;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003077 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00003078} listiterobject;
3079
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003080static void listiter_dealloc(listiterobject *);
3081static int listiter_traverse(listiterobject *, visitproc, void *);
3082static PyObject *listiter_next(listiterobject *);
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303083static PyObject *listiter_len(listiterobject *, PyObject *);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003084static PyObject *listiter_reduce_general(void *_it, int forward);
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303085static PyObject *listiter_reduce(listiterobject *, PyObject *);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003086static PyObject *listiter_setstate(listiterobject *, PyObject *state);
Raymond Hettinger435bf582004-03-18 22:43:10 +00003087
Armin Rigof5b3e362006-02-11 21:32:43 +00003088PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003089PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
3090PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00003091
3092static PyMethodDef listiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003093 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003094 {"__reduce__", (PyCFunction)listiter_reduce, METH_NOARGS, reduce_doc},
3095 {"__setstate__", (PyCFunction)listiter_setstate, METH_O, setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003096 {NULL, NULL} /* sentinel */
Raymond Hettinger435bf582004-03-18 22:43:10 +00003097};
3098
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00003099PyTypeObject PyListIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003100 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3101 "list_iterator", /* tp_name */
3102 sizeof(listiterobject), /* tp_basicsize */
3103 0, /* tp_itemsize */
3104 /* methods */
3105 (destructor)listiter_dealloc, /* tp_dealloc */
Jeroen Demeyer530f5062019-05-31 04:13:39 +02003106 0, /* tp_vectorcall_offset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003107 0, /* tp_getattr */
3108 0, /* tp_setattr */
Jeroen Demeyer530f5062019-05-31 04:13:39 +02003109 0, /* tp_as_async */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003110 0, /* tp_repr */
3111 0, /* tp_as_number */
3112 0, /* tp_as_sequence */
3113 0, /* tp_as_mapping */
3114 0, /* tp_hash */
3115 0, /* tp_call */
3116 0, /* tp_str */
3117 PyObject_GenericGetAttr, /* tp_getattro */
3118 0, /* tp_setattro */
3119 0, /* tp_as_buffer */
3120 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3121 0, /* tp_doc */
3122 (traverseproc)listiter_traverse, /* tp_traverse */
3123 0, /* tp_clear */
3124 0, /* tp_richcompare */
3125 0, /* tp_weaklistoffset */
3126 PyObject_SelfIter, /* tp_iter */
3127 (iternextfunc)listiter_next, /* tp_iternext */
3128 listiter_methods, /* tp_methods */
3129 0, /* tp_members */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00003130};
Raymond Hettinger1021c442003-11-07 15:38:09 +00003131
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003132
3133static PyObject *
3134list_iter(PyObject *seq)
3135{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003136 listiterobject *it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003137
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003138 if (!PyList_Check(seq)) {
3139 PyErr_BadInternalCall();
3140 return NULL;
3141 }
3142 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
3143 if (it == NULL)
3144 return NULL;
3145 it->it_index = 0;
3146 Py_INCREF(seq);
3147 it->it_seq = (PyListObject *)seq;
3148 _PyObject_GC_TRACK(it);
3149 return (PyObject *)it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003150}
3151
3152static void
3153listiter_dealloc(listiterobject *it)
3154{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003155 _PyObject_GC_UNTRACK(it);
3156 Py_XDECREF(it->it_seq);
3157 PyObject_GC_Del(it);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003158}
3159
3160static int
3161listiter_traverse(listiterobject *it, visitproc visit, void *arg)
3162{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003163 Py_VISIT(it->it_seq);
3164 return 0;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003165}
3166
3167static PyObject *
3168listiter_next(listiterobject *it)
3169{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003170 PyListObject *seq;
3171 PyObject *item;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003172
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003173 assert(it != NULL);
3174 seq = it->it_seq;
3175 if (seq == NULL)
3176 return NULL;
3177 assert(PyList_Check(seq));
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003178
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003179 if (it->it_index < PyList_GET_SIZE(seq)) {
3180 item = PyList_GET_ITEM(seq, it->it_index);
3181 ++it->it_index;
3182 Py_INCREF(item);
3183 return item;
3184 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003185
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003186 it->it_seq = NULL;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03003187 Py_DECREF(seq);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003188 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003189}
3190
3191static PyObject *
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303192listiter_len(listiterobject *it, PyObject *Py_UNUSED(ignored))
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003193{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003194 Py_ssize_t len;
3195 if (it->it_seq) {
3196 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
3197 if (len >= 0)
3198 return PyLong_FromSsize_t(len);
3199 }
3200 return PyLong_FromLong(0);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003201}
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003202
3203static PyObject *
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303204listiter_reduce(listiterobject *it, PyObject *Py_UNUSED(ignored))
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003205{
3206 return listiter_reduce_general(it, 1);
3207}
3208
3209static PyObject *
3210listiter_setstate(listiterobject *it, PyObject *state)
3211{
Victor Stinner7660b882013-06-24 23:59:24 +02003212 Py_ssize_t index = PyLong_AsSsize_t(state);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003213 if (index == -1 && PyErr_Occurred())
3214 return NULL;
3215 if (it->it_seq != NULL) {
3216 if (index < 0)
3217 index = 0;
Kristján Valur Jónsson25dded02014-03-05 13:47:57 +00003218 else if (index > PyList_GET_SIZE(it->it_seq))
3219 index = PyList_GET_SIZE(it->it_seq); /* iterator exhausted */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003220 it->it_index = index;
3221 }
3222 Py_RETURN_NONE;
3223}
3224
Raymond Hettinger1021c442003-11-07 15:38:09 +00003225/*********************** List Reverse Iterator **************************/
3226
3227typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003228 PyObject_HEAD
3229 Py_ssize_t it_index;
3230 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger1021c442003-11-07 15:38:09 +00003231} listreviterobject;
3232
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003233static void listreviter_dealloc(listreviterobject *);
3234static int listreviter_traverse(listreviterobject *, visitproc, void *);
3235static PyObject *listreviter_next(listreviterobject *);
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303236static PyObject *listreviter_len(listreviterobject *, PyObject *);
3237static PyObject *listreviter_reduce(listreviterobject *, PyObject *);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003238static PyObject *listreviter_setstate(listreviterobject *, PyObject *);
Raymond Hettingeref9bf402004-03-10 10:10:42 +00003239
Raymond Hettingerf5b64112008-12-02 21:33:45 +00003240static PyMethodDef listreviter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003241 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003242 {"__reduce__", (PyCFunction)listreviter_reduce, METH_NOARGS, reduce_doc},
3243 {"__setstate__", (PyCFunction)listreviter_setstate, METH_O, setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003244 {NULL, NULL} /* sentinel */
Raymond Hettingeref9bf402004-03-10 10:10:42 +00003245};
3246
Raymond Hettinger1021c442003-11-07 15:38:09 +00003247PyTypeObject PyListRevIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003248 PyVarObject_HEAD_INIT(&PyType_Type, 0)
3249 "list_reverseiterator", /* tp_name */
3250 sizeof(listreviterobject), /* tp_basicsize */
3251 0, /* tp_itemsize */
3252 /* methods */
3253 (destructor)listreviter_dealloc, /* tp_dealloc */
Jeroen Demeyer530f5062019-05-31 04:13:39 +02003254 0, /* tp_vectorcall_offset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003255 0, /* tp_getattr */
3256 0, /* tp_setattr */
Jeroen Demeyer530f5062019-05-31 04:13:39 +02003257 0, /* tp_as_async */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003258 0, /* tp_repr */
3259 0, /* tp_as_number */
3260 0, /* tp_as_sequence */
3261 0, /* tp_as_mapping */
3262 0, /* tp_hash */
3263 0, /* tp_call */
3264 0, /* tp_str */
3265 PyObject_GenericGetAttr, /* tp_getattro */
3266 0, /* tp_setattro */
3267 0, /* tp_as_buffer */
3268 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
3269 0, /* tp_doc */
3270 (traverseproc)listreviter_traverse, /* tp_traverse */
3271 0, /* tp_clear */
3272 0, /* tp_richcompare */
3273 0, /* tp_weaklistoffset */
3274 PyObject_SelfIter, /* tp_iter */
3275 (iternextfunc)listreviter_next, /* tp_iternext */
3276 listreviter_methods, /* tp_methods */
3277 0,
Raymond Hettinger1021c442003-11-07 15:38:09 +00003278};
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003279
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02003280/*[clinic input]
3281list.__reversed__
3282
3283Return a reverse iterator over the list.
3284[clinic start generated code]*/
3285
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003286static PyObject *
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02003287list___reversed___impl(PyListObject *self)
3288/*[clinic end generated code: output=b166f073208c888c input=eadb6e17f8a6a280]*/
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003289{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003290 listreviterobject *it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003291
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003292 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
3293 if (it == NULL)
3294 return NULL;
Serhiy Storchakafdd42c42017-03-11 09:19:20 +02003295 assert(PyList_Check(self));
3296 it->it_index = PyList_GET_SIZE(self) - 1;
3297 Py_INCREF(self);
3298 it->it_seq = self;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003299 PyObject_GC_Track(it);
3300 return (PyObject *)it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003301}
3302
3303static void
3304listreviter_dealloc(listreviterobject *it)
3305{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003306 PyObject_GC_UnTrack(it);
3307 Py_XDECREF(it->it_seq);
3308 PyObject_GC_Del(it);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003309}
3310
3311static int
3312listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
3313{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003314 Py_VISIT(it->it_seq);
3315 return 0;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003316}
3317
3318static PyObject *
3319listreviter_next(listreviterobject *it)
3320{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003321 PyObject *item;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03003322 Py_ssize_t index;
3323 PyListObject *seq;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003324
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03003325 assert(it != NULL);
3326 seq = it->it_seq;
3327 if (seq == NULL) {
3328 return NULL;
3329 }
3330 assert(PyList_Check(seq));
3331
3332 index = it->it_index;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003333 if (index>=0 && index < PyList_GET_SIZE(seq)) {
3334 item = PyList_GET_ITEM(seq, index);
3335 it->it_index--;
3336 Py_INCREF(item);
3337 return item;
3338 }
3339 it->it_index = -1;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03003340 it->it_seq = NULL;
3341 Py_DECREF(seq);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003342 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003343}
3344
Raymond Hettingerf5b64112008-12-02 21:33:45 +00003345static PyObject *
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303346listreviter_len(listreviterobject *it, PyObject *Py_UNUSED(ignored))
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003347{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00003348 Py_ssize_t len = it->it_index + 1;
3349 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
3350 len = 0;
3351 return PyLong_FromSsize_t(len);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00003352}
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003353
3354static PyObject *
Siddhesh Poyarekar55edd0c2018-04-30 00:29:33 +05303355listreviter_reduce(listreviterobject *it, PyObject *Py_UNUSED(ignored))
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003356{
3357 return listiter_reduce_general(it, 0);
3358}
3359
3360static PyObject *
3361listreviter_setstate(listreviterobject *it, PyObject *state)
3362{
3363 Py_ssize_t index = PyLong_AsSsize_t(state);
3364 if (index == -1 && PyErr_Occurred())
3365 return NULL;
3366 if (it->it_seq != NULL) {
3367 if (index < -1)
3368 index = -1;
3369 else if (index > PyList_GET_SIZE(it->it_seq) - 1)
3370 index = PyList_GET_SIZE(it->it_seq) - 1;
3371 it->it_index = index;
3372 }
3373 Py_RETURN_NONE;
3374}
3375
3376/* common pickling support */
3377
3378static PyObject *
3379listiter_reduce_general(void *_it, int forward)
3380{
Serhiy Storchakabb86bf42018-12-11 08:28:18 +02003381 _Py_IDENTIFIER(iter);
3382 _Py_IDENTIFIER(reversed);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003383 PyObject *list;
3384
3385 /* the objects are not the same, index is of different types! */
3386 if (forward) {
3387 listiterobject *it = (listiterobject *)_it;
3388 if (it->it_seq)
Serhiy Storchakabb86bf42018-12-11 08:28:18 +02003389 return Py_BuildValue("N(O)n", _PyEval_GetBuiltinId(&PyId_iter),
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003390 it->it_seq, it->it_index);
3391 } else {
3392 listreviterobject *it = (listreviterobject *)_it;
3393 if (it->it_seq)
Serhiy Storchakabb86bf42018-12-11 08:28:18 +02003394 return Py_BuildValue("N(O)n", _PyEval_GetBuiltinId(&PyId_reversed),
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003395 it->it_seq, it->it_index);
3396 }
3397 /* empty iterator, create an empty list */
3398 list = PyList_New(0);
3399 if (list == NULL)
3400 return NULL;
Serhiy Storchakabb86bf42018-12-11 08:28:18 +02003401 return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00003402}