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