Branch data 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 : 75138150 : get_list_state(void)
23 : : {
24 : 75138150 : PyInterpreterState *interp = _PyInterpreterState_GET();
25 : 75138150 : 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 : 24238104 : list_resize(PyListObject *self, Py_ssize_t newsize)
45 : : {
46 : : PyObject **items;
47 : : size_t new_allocated, num_allocated_bytes;
48 : 24238104 : 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 [ + + + + ]: 24238104 : if (allocated >= newsize && newsize >= (allocated >> 1)) {
55 : : assert(self->ob_item != NULL || newsize == 0);
56 : 6654914 : Py_SET_SIZE(self, newsize);
57 : 6654914 : 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 : 17583190 : 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 [ + + ]: 17583190 : if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
75 : 110069 : new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
76 : :
77 [ + + ]: 17583190 : if (newsize == 0)
78 : 183271 : new_allocated = 0;
79 : 17583190 : num_allocated_bytes = new_allocated * sizeof(PyObject *);
80 : 17583190 : items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
81 [ - + ]: 17583190 : if (items == NULL) {
82 : : PyErr_NoMemory();
83 : 0 : return -1;
84 : : }
85 : 17583190 : self->ob_item = items;
86 : 17583190 : Py_SET_SIZE(self, newsize);
87 : 17583190 : self->allocated = new_allocated;
88 : 17583190 : return 0;
89 : : }
90 : :
91 : : static int
92 : 7532203 : list_preallocate_exact(PyListObject *self, Py_ssize_t size)
93 : : {
94 : : assert(self->ob_item == NULL);
95 : : 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 : 7532203 : size = (size + 1) & ~(size_t)1;
103 [ + - ]: 7532203 : PyObject **items = PyMem_New(PyObject*, size);
104 [ - + ]: 7532203 : if (items == NULL) {
105 : : PyErr_NoMemory();
106 : 0 : return -1;
107 : : }
108 : 7532203 : self->ob_item = items;
109 : 7532203 : self->allocated = size;
110 : 7532203 : return 0;
111 : : }
112 : :
113 : : void
114 : 29824 : _PyList_ClearFreeList(PyInterpreterState *interp)
115 : : {
116 : : #if PyList_MAXFREELIST > 0
117 : 29824 : struct _Py_list_state *state = &interp->list;
118 [ + + ]: 596684 : while (state->numfree) {
119 : 566860 : PyListObject *op = state->free_list[--state->numfree];
120 : : assert(PyList_CheckExact(op));
121 : 566860 : PyObject_GC_Del(op);
122 : : }
123 : : #endif
124 : 29824 : }
125 : :
126 : : void
127 : 3125 : _PyList_Fini(PyInterpreterState *interp)
128 : : {
129 : 3125 : _PyList_ClearFreeList(interp);
130 : : #if defined(Py_DEBUG) && PyList_MAXFREELIST > 0
131 : : struct _Py_list_state *state = &interp->list;
132 : : state->numfree = -1;
133 : : #endif
134 : 3125 : }
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 : 34618936 : PyList_New(Py_ssize_t size)
150 : : {
151 : : PyListObject *op;
152 : :
153 [ - + ]: 34618936 : if (size < 0) {
154 : 0 : PyErr_BadInternalCall();
155 : 0 : return NULL;
156 : : }
157 : :
158 : : #if PyList_MAXFREELIST > 0
159 : 34618936 : struct _Py_list_state *state = get_list_state();
160 : : #ifdef Py_DEBUG
161 : : // PyList_New() must not be called after _PyList_Fini()
162 : : assert(state->numfree != -1);
163 : : #endif
164 [ + + ]: 34618936 : if (PyList_MAXFREELIST && state->numfree) {
165 : 30305997 : state->numfree--;
166 : 30305997 : op = state->free_list[state->numfree];
167 : : OBJECT_STAT_INC(from_freelist);
168 : 30305997 : _Py_NewReference((PyObject *)op);
169 : : }
170 : : else
171 : : #endif
172 : : {
173 : 4312939 : op = PyObject_GC_New(PyListObject, &PyList_Type);
174 [ + + ]: 4312939 : if (op == NULL) {
175 : 2 : return NULL;
176 : : }
177 : : }
178 [ + + ]: 34618934 : if (size <= 0) {
179 : 22283006 : op->ob_item = NULL;
180 : : }
181 : : else {
182 : 12335928 : op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
183 [ - + ]: 12335928 : if (op->ob_item == NULL) {
184 : 0 : Py_DECREF(op);
185 : : return PyErr_NoMemory();
186 : : }
187 : : }
188 : 34618934 : Py_SET_SIZE(op, size);
189 : 34618934 : op->allocated = size;
190 : 34618934 : _PyObject_GC_TRACK(op);
191 : 34618934 : return (PyObject *) op;
192 : : }
193 : :
194 : : static PyObject *
195 : 2799293 : list_new_prealloc(Py_ssize_t size)
196 : : {
197 : : assert(size > 0);
198 : 2799293 : PyListObject *op = (PyListObject *) PyList_New(0);
199 [ - + ]: 2799293 : if (op == NULL) {
200 : 0 : return NULL;
201 : : }
202 : : assert(op->ob_item == NULL);
203 [ + - ]: 2799293 : op->ob_item = PyMem_New(PyObject *, size);
204 [ - + ]: 2799293 : if (op->ob_item == NULL) {
205 : 0 : Py_DECREF(op);
206 : : return PyErr_NoMemory();
207 : : }
208 : 2799293 : op->allocated = size;
209 : 2799293 : return (PyObject *) op;
210 : : }
211 : :
212 : : Py_ssize_t
213 : 544929 : PyList_Size(PyObject *op)
214 : : {
215 [ - + ]: 544929 : if (!PyList_Check(op)) {
216 : 0 : PyErr_BadInternalCall();
217 : 0 : return -1;
218 : : }
219 : : else
220 : 544929 : return Py_SIZE(op);
221 : : }
222 : :
223 : : static inline int
224 : 20842726 : 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 : 20842726 : return (size_t) i < (size_t) limit;
234 : : }
235 : :
236 : : PyObject *
237 : 150520 : PyList_GetItem(PyObject *op, Py_ssize_t i)
238 : : {
239 [ - + ]: 150520 : if (!PyList_Check(op)) {
240 : 0 : PyErr_BadInternalCall();
241 : 0 : return NULL;
242 : : }
243 [ + + ]: 150520 : 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 : 150519 : return ((PyListObject *)op) -> ob_item[i];
249 : : }
250 : :
251 : : int
252 : 41507 : PyList_SetItem(PyObject *op, Py_ssize_t i,
253 : : PyObject *newitem)
254 : : {
255 : : PyObject **p;
256 [ - + ]: 41507 : if (!PyList_Check(op)) {
257 : 0 : Py_XDECREF(newitem);
258 : 0 : PyErr_BadInternalCall();
259 : 0 : return -1;
260 : : }
261 [ - + ]: 41507 : 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 : 41507 : p = ((PyListObject *)op) -> ob_item + i;
268 : 41507 : Py_XSETREF(*p, newitem);
269 : 41507 : return 0;
270 : : }
271 : :
272 : : static int
273 : 108418 : ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
274 : : {
275 : 108418 : Py_ssize_t i, n = Py_SIZE(self);
276 : : PyObject **items;
277 [ - + ]: 108418 : if (v == NULL) {
278 : 0 : PyErr_BadInternalCall();
279 : 0 : return -1;
280 : : }
281 : :
282 : : assert((size_t)n + 1 < PY_SSIZE_T_MAX);
283 [ - + ]: 108418 : if (list_resize(self, n+1) < 0)
284 : 0 : return -1;
285 : :
286 [ + + ]: 108418 : if (where < 0) {
287 : 36 : where += n;
288 [ + + ]: 36 : if (where < 0)
289 : 16 : where = 0;
290 : : }
291 [ + + ]: 108418 : if (where > n)
292 : 16 : where = n;
293 : 108418 : items = self->ob_item;
294 [ + + ]: 853617 : for (i = n; --i >= where; )
295 : 745199 : items[i+1] = items[i];
296 : 108418 : Py_INCREF(v);
297 : 108418 : items[where] = v;
298 : 108418 : return 0;
299 : : }
300 : :
301 : : int
302 : 74228 : PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
303 : : {
304 [ - + ]: 74228 : if (!PyList_Check(op)) {
305 : 0 : PyErr_BadInternalCall();
306 : 0 : return -1;
307 : : }
308 : 74228 : return ins1((PyListObject *)op, where, newitem);
309 : : }
310 : :
311 : : /* internal, used by _PyList_AppendTakeRef */
312 : : int
313 : 15161484 : _PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)
314 : : {
315 : 15161484 : Py_ssize_t len = PyList_GET_SIZE(self);
316 : : assert(self->allocated == -1 || self->allocated == len);
317 [ - + ]: 15161484 : if (list_resize(self, len + 1) < 0) {
318 : 0 : Py_DECREF(newitem);
319 : 0 : return -1;
320 : : }
321 : 15161484 : PyList_SET_ITEM(self, len, newitem);
322 : 15161484 : return 0;
323 : : }
324 : :
325 : : int
326 : 134323264 : PyList_Append(PyObject *op, PyObject *newitem)
327 : : {
328 [ + - + - ]: 134323264 : if (PyList_Check(op) && (newitem != NULL)) {
329 : 134323264 : Py_INCREF(newitem);
330 : 134323264 : return _PyList_AppendTakeRef((PyListObject *)op, newitem);
331 : : }
332 : 0 : PyErr_BadInternalCall();
333 : 0 : return -1;
334 : : }
335 : :
336 : : /* Methods */
337 : :
338 : : static void
339 : 40524022 : list_dealloc(PyListObject *op)
340 : : {
341 : : Py_ssize_t i;
342 : 40524022 : PyObject_GC_UnTrack(op);
343 [ + + + + ]: 40524022 : Py_TRASHCAN_BEGIN(op, list_dealloc)
344 [ + + ]: 40519213 : 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 : 31234896 : i = Py_SIZE(op);
350 [ + + ]: 368524664 : while (--i >= 0) {
351 : 337289768 : Py_XDECREF(op->ob_item[i]);
352 : : }
353 : 31234896 : PyMem_Free(op->ob_item);
354 : : }
355 : : #if PyList_MAXFREELIST > 0
356 : 40519213 : struct _Py_list_state *state = get_list_state();
357 : : #ifdef Py_DEBUG
358 : : // list_dealloc() must not be called after _PyList_Fini()
359 : : assert(state->numfree != -1);
360 : : #endif
361 [ + + + + ]: 40519213 : if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {
362 : 30873198 : state->free_list[state->numfree++] = op;
363 : 30873198 : OBJECT_STAT_INC(to_freelist);
364 : : }
365 : : else
366 : : #endif
367 : : {
368 : 9646015 : Py_TYPE(op)->tp_free((PyObject *)op);
369 : : }
370 [ + + ]: 40519213 : Py_TRASHCAN_END
371 : 40524022 : }
372 : :
373 : : static PyObject *
374 : 158627 : list_repr(PyListObject *v)
375 : : {
376 : : Py_ssize_t i;
377 : : PyObject *s;
378 : : _PyUnicodeWriter writer;
379 : :
380 [ + + ]: 158627 : if (Py_SIZE(v) == 0) {
381 : 72275 : return PyUnicode_FromString("[]");
382 : : }
383 : :
384 : 86352 : i = Py_ReprEnter((PyObject*)v);
385 [ + + ]: 86352 : if (i != 0) {
386 [ + - ]: 12 : return i > 0 ? PyUnicode_FromString("[...]") : NULL;
387 : : }
388 : :
389 : 86340 : _PyUnicodeWriter_Init(&writer);
390 : 86340 : writer.overallocate = 1;
391 : : /* "[" + "1" + ", 2" * (len - 1) + "]" */
392 : 86340 : writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
393 : :
394 [ - + ]: 86340 : 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 [ + + ]: 1772457 : for (i = 0; i < Py_SIZE(v); ++i) {
400 [ + + ]: 1687806 : if (i > 0) {
401 [ - + ]: 1601466 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
402 : 0 : goto error;
403 : : }
404 : :
405 : 1687806 : s = PyObject_Repr(v->ob_item[i]);
406 [ + + ]: 1687806 : if (s == NULL)
407 : 1689 : goto error;
408 : :
409 [ - + ]: 1686117 : if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
410 : 0 : Py_DECREF(s);
411 : 0 : goto error;
412 : : }
413 : 1686117 : Py_DECREF(s);
414 : : }
415 : :
416 : 84651 : writer.overallocate = 0;
417 [ - + ]: 84651 : if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
418 : 0 : goto error;
419 : :
420 : 84651 : Py_ReprLeave((PyObject *)v);
421 : 84651 : 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 : 21427997 : list_length(PyListObject *a)
431 : : {
432 : 21427997 : return Py_SIZE(a);
433 : : }
434 : :
435 : : static int
436 : 5875786 : list_contains(PyListObject *a, PyObject *el)
437 : : {
438 : : PyObject *item;
439 : : Py_ssize_t i;
440 : : int cmp;
441 : :
442 [ + + + + ]: 25248960 : for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
443 : 19373174 : item = PyList_GET_ITEM(a, i);
444 : 19373174 : Py_INCREF(item);
445 : 19373174 : cmp = PyObject_RichCompareBool(item, el, Py_EQ);
446 : 19373174 : Py_DECREF(item);
447 : : }
448 : 5875786 : return cmp;
449 : : }
450 : :
451 : : static PyObject *
452 : 15513782 : list_item(PyListObject *a, Py_ssize_t i)
453 : : {
454 [ + + ]: 15513782 : if (!valid_index(i, Py_SIZE(a))) {
455 : 396133 : PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));
456 : 396133 : return NULL;
457 : : }
458 : 15117649 : Py_INCREF(a->ob_item[i]);
459 : 15117649 : return a->ob_item[i];
460 : : }
461 : :
462 : : static PyObject *
463 : 2243379 : 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 : 2243379 : len = ihigh - ilow;
469 [ + + ]: 2243379 : if (len <= 0) {
470 : 136 : return PyList_New(0);
471 : : }
472 : 2243243 : np = (PyListObject *) list_new_prealloc(len);
473 [ - + ]: 2243243 : if (np == NULL)
474 : 0 : return NULL;
475 : :
476 : 2243243 : src = a->ob_item + ilow;
477 : 2243243 : dest = np->ob_item;
478 [ + + ]: 21334917 : for (i = 0; i < len; i++) {
479 : 19091674 : PyObject *v = src[i];
480 : 19091674 : Py_INCREF(v);
481 : 19091674 : dest[i] = v;
482 : : }
483 : 2243243 : Py_SET_SIZE(np, len);
484 : 2243243 : return (PyObject *)np;
485 : : }
486 : :
487 : : PyObject *
488 : 2356 : PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
489 : : {
490 [ - + ]: 2356 : if (!PyList_Check(a)) {
491 : 0 : PyErr_BadInternalCall();
492 : 0 : return NULL;
493 : : }
494 [ - + ]: 2356 : if (ilow < 0) {
495 : 0 : ilow = 0;
496 : : }
497 [ - + ]: 2356 : else if (ilow > Py_SIZE(a)) {
498 : 0 : ilow = Py_SIZE(a);
499 : : }
500 [ - + ]: 2356 : if (ihigh < ilow) {
501 : 0 : ihigh = ilow;
502 : : }
503 [ - + ]: 2356 : else if (ihigh > Py_SIZE(a)) {
504 : 0 : ihigh = Py_SIZE(a);
505 : : }
506 : 2356 : return list_slice((PyListObject *)a, ilow, ihigh);
507 : : }
508 : :
509 : : static PyObject *
510 : 445588 : 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 [ + + ]: 445588 : 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 : : assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
524 : 445584 : size = Py_SIZE(a) + Py_SIZE(b);
525 [ + + ]: 445584 : if (size == 0) {
526 : 76548 : return PyList_New(0);
527 : : }
528 : 369036 : np = (PyListObject *) list_new_prealloc(size);
529 [ - + ]: 369036 : if (np == NULL) {
530 : 0 : return NULL;
531 : : }
532 : 369036 : src = a->ob_item;
533 : 369036 : dest = np->ob_item;
534 [ + + ]: 4606379 : for (i = 0; i < Py_SIZE(a); i++) {
535 : 4237343 : PyObject *v = src[i];
536 : 4237343 : Py_INCREF(v);
537 : 4237343 : dest[i] = v;
538 : : }
539 : 369036 : src = b->ob_item;
540 : 369036 : dest = np->ob_item + Py_SIZE(a);
541 [ + + ]: 2775228 : for (i = 0; i < Py_SIZE(b); i++) {
542 : 2406192 : PyObject *v = src[i];
543 : 2406192 : Py_INCREF(v);
544 : 2406192 : dest[i] = v;
545 : : }
546 : 369036 : Py_SET_SIZE(np, size);
547 : 369036 : return (PyObject *)np;
548 : : #undef b
549 : : }
550 : :
551 : : static PyObject *
552 : 159638 : list_repeat(PyListObject *a, Py_ssize_t n)
553 : : {
554 : : Py_ssize_t size;
555 : : PyListObject *np;
556 [ + + ]: 159638 : if (n < 0)
557 : 93 : n = 0;
558 [ + + + + ]: 159638 : if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
559 : : return PyErr_NoMemory();
560 : 159637 : size = Py_SIZE(a) * n;
561 [ + + ]: 159637 : if (size == 0)
562 : 9816 : return PyList_New(0);
563 : 149821 : np = (PyListObject *) list_new_prealloc(size);
564 [ - + ]: 149821 : if (np == NULL)
565 : 0 : return NULL;
566 : 149821 : PyObject **dest = np->ob_item;
567 : 149821 : PyObject **dest_end = dest + size;
568 [ + + ]: 149821 : if (Py_SIZE(a) == 1) {
569 : 148265 : PyObject *elem = a->ob_item[0];
570 : 148265 : Py_SET_REFCNT(elem, Py_REFCNT(elem) + n);
571 : : #ifdef Py_REF_DEBUG
572 : : _Py_RefTotal += n;
573 : : #endif
574 [ + + ]: 7618841 : while (dest < dest_end) {
575 : 7470576 : *dest++ = elem;
576 : : }
577 : : }
578 : : else {
579 : 1556 : PyObject **src = a->ob_item;
580 : 1556 : PyObject **src_end = src + Py_SIZE(a);
581 [ + + ]: 28523 : while (src < src_end) {
582 : 26967 : Py_SET_REFCNT(*src, Py_REFCNT(*src) + n);
583 : : #ifdef Py_REF_DEBUG
584 : : _Py_RefTotal += n;
585 : : #endif
586 : 26967 : *dest++ = *src++;
587 : : }
588 : : // Now src chases after dest in the same buffer
589 : 1556 : src = np->ob_item;
590 [ + + ]: 1420833 : while (dest < dest_end) {
591 : 1419277 : *dest++ = *src++;
592 : : }
593 : : }
594 : 149821 : Py_SET_SIZE(np, size);
595 : 149821 : return (PyObject *) np;
596 : : }
597 : :
598 : : static int
599 : 432879 : _list_clear(PyListObject *a)
600 : : {
601 : : Py_ssize_t i;
602 : 432879 : PyObject **item = a->ob_item;
603 [ + + ]: 432879 : if (item != NULL) {
604 : : /* Because XDECREF can recursively invoke operations on
605 : : this list, we make it empty first. */
606 : 407188 : i = Py_SIZE(a);
607 : 407188 : Py_SET_SIZE(a, 0);
608 : 407188 : a->ob_item = NULL;
609 : 407188 : a->allocated = 0;
610 [ + + ]: 1165499 : while (--i >= 0) {
611 : 758311 : Py_XDECREF(item[i]);
612 : : }
613 : 407188 : 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 : 432879 : 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 : 1944679 : 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 : 1944679 : PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
638 : : PyObject **item;
639 : 1944679 : PyObject **vitem = NULL;
640 : 1944679 : 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 : 1944679 : int result = -1; /* guilty until proved innocent */
647 : : #define b ((PyListObject *)v)
648 [ + + ]: 1944679 : if (v == NULL)
649 : 1591767 : n = 0;
650 : : else {
651 [ + + ]: 352912 : 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 : 352909 : v_as_SF = PySequence_Fast(v, "can only assign an iterable");
661 [ + + ]: 352909 : if(v_as_SF == NULL)
662 : 2 : goto Error;
663 [ + + ]: 352907 : n = PySequence_Fast_GET_SIZE(v_as_SF);
664 [ + + ]: 352907 : vitem = PySequence_Fast_ITEMS(v_as_SF);
665 : : }
666 [ - + ]: 1944674 : if (ilow < 0)
667 : 0 : ilow = 0;
668 [ + + ]: 1944674 : else if (ilow > Py_SIZE(a))
669 : 54 : ilow = Py_SIZE(a);
670 : :
671 [ + + ]: 1944674 : if (ihigh < ilow)
672 : 2384 : ihigh = ilow;
673 [ + + ]: 1942290 : else if (ihigh > Py_SIZE(a))
674 : 54 : ihigh = Py_SIZE(a);
675 : :
676 : 1944674 : norig = ihigh - ilow;
677 : : assert(norig >= 0);
678 : 1944674 : d = n - norig;
679 [ + + ]: 1944674 : if (Py_SIZE(a) + d == 0) {
680 : 397522 : Py_XDECREF(v_as_SF);
681 : 397522 : return _list_clear(a);
682 : : }
683 : 1547152 : item = a->ob_item;
684 : : /* recycle the items that we are about to remove */
685 : 1547152 : s = norig * sizeof(PyObject *);
686 : : /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
687 [ + + ]: 1547152 : if (s) {
688 [ + + ]: 1407730 : if (s > sizeof(recycle_on_stack)) {
689 : 462 : recycle = (PyObject **)PyMem_Malloc(s);
690 [ - + ]: 462 : if (recycle == NULL) {
691 : : PyErr_NoMemory();
692 : 0 : goto Error;
693 : : }
694 : : }
695 : 1407730 : memcpy(recycle, &item[ilow], s);
696 : : }
697 : :
698 [ + + ]: 1547152 : if (d < 0) { /* Delete -d items */
699 : : Py_ssize_t tail;
700 : 1376079 : tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
701 : 1376079 : memmove(&item[ihigh+d], &item[ihigh], tail);
702 [ - + ]: 1376079 : 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 : 1376079 : item = a->ob_item;
708 : : }
709 [ + + ]: 171073 : else if (d > 0) { /* Insert d items */
710 : 138098 : k = Py_SIZE(a);
711 [ - + ]: 138098 : if (list_resize(a, k+d) < 0)
712 : 0 : goto Error;
713 : 138098 : item = a->ob_item;
714 : 138098 : memmove(&item[ihigh+d], &item[ihigh],
715 : 138098 : (k - ihigh)*sizeof(PyObject *));
716 : : }
717 [ + + ]: 3325867 : for (k = 0; k < n; k++, ilow++) {
718 : 1778715 : PyObject *w = vitem[k];
719 : 1778715 : Py_XINCREF(w);
720 : 1778715 : item[ilow] = w;
721 : : }
722 [ + + ]: 3279395 : for (k = norig - 1; k >= 0; --k)
723 : 1732243 : Py_XDECREF(recycle[k]);
724 : 1547152 : result = 0;
725 : 1547154 : Error:
726 [ + + ]: 1547154 : if (recycle != recycle_on_stack)
727 : 462 : PyMem_Free(recycle);
728 : 1547154 : Py_XDECREF(v_as_SF);
729 : 1547154 : return result;
730 : : #undef b
731 : : }
732 : :
733 : : int
734 : 733450 : PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
735 : : {
736 [ - + ]: 733450 : if (!PyList_Check(a)) {
737 : 0 : PyErr_BadInternalCall();
738 : 0 : return -1;
739 : : }
740 : 733450 : 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 : : 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 : 2555651 : list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
784 : : {
785 [ + + ]: 2555651 : 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 [ + + ]: 2555629 : if (v == NULL)
791 : 574257 : return list_ass_slice(a, i, i+1, v);
792 : 1981372 : Py_INCREF(v);
793 : 1981372 : Py_SETREF(a->ob_item[i], v);
794 : 1981372 : 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 : 34190 : list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
809 : : /*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
810 : : {
811 [ + - ]: 34190 : if (ins1(self, index, object) == 0)
812 : 34190 : 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 : 8034 : list_clear_impl(PyListObject *self)
824 : : /*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/
825 : : {
826 : 8034 : _list_clear(self);
827 : 8034 : 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 : 2511 : list_copy_impl(PyListObject *self)
838 : : /*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/
839 : : {
840 : 2511 : 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 : 8674194 : list_append(PyListObject *self, PyObject *object)
854 : : /*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
855 : : {
856 [ - + ]: 8674194 : if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {
857 : 0 : return NULL;
858 : : }
859 : 8674194 : 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 : 12468571 : 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 [ + + + + : 12468571 : if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
- + ]
886 : : (PyObject *)self == iterable) {
887 : : PyObject **src, **dest;
888 : 10995438 : iterable = PySequence_Fast(iterable, "argument must be iterable");
889 [ - + ]: 10995438 : if (!iterable)
890 : 0 : return NULL;
891 [ + + ]: 10995438 : n = PySequence_Fast_GET_SIZE(iterable);
892 [ + + ]: 10995438 : if (n == 0) {
893 : : /* short circuit when iterable is empty */
894 : 811451 : Py_DECREF(iterable);
895 : 811451 : Py_RETURN_NONE;
896 : : }
897 : 10183987 : 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 : : assert(m < PY_SSIZE_T_MAX - n);
901 [ + + ]: 10183987 : if (self->ob_item == NULL) {
902 [ - + ]: 6165713 : if (list_preallocate_exact(self, n) < 0) {
903 : 0 : return NULL;
904 : : }
905 : 6165713 : Py_SET_SIZE(self, n);
906 : : }
907 [ - + ]: 4018274 : 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 [ + + ]: 10183987 : src = PySequence_Fast_ITEMS(iterable);
918 : 10183987 : dest = self->ob_item + m;
919 [ + + ]: 36932117 : for (i = 0; i < n; i++) {
920 : 26748130 : PyObject *o = src[i];
921 : 26748130 : Py_INCREF(o);
922 : 26748130 : dest[i] = o;
923 : : }
924 : 10183987 : Py_DECREF(iterable);
925 : 10183987 : Py_RETURN_NONE;
926 : : }
927 : :
928 : 1473133 : it = PyObject_GetIter(iterable);
929 [ + + ]: 1473133 : if (it == NULL)
930 : 117 : return NULL;
931 : 1473016 : iternext = *Py_TYPE(it)->tp_iternext;
932 : :
933 : : /* Guess a result list size. */
934 : 1473016 : n = PyObject_LengthHint(iterable, 8);
935 [ + + ]: 1473016 : if (n < 0) {
936 : 5 : Py_DECREF(it);
937 : 5 : return NULL;
938 : : }
939 : 1473011 : m = Py_SIZE(self);
940 [ + + ]: 1473011 : 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 [ + + ]: 1473009 : else if (self->ob_item == NULL) {
947 [ + + - + ]: 1406021 : if (n && list_preallocate_exact(self, n) < 0)
948 : 0 : goto error;
949 : : }
950 : : else {
951 : : /* Make room. */
952 [ - + ]: 66988 : if (list_resize(self, m + n) < 0)
953 : 0 : goto error;
954 : : /* Make the list sane again. */
955 : 66988 : Py_SET_SIZE(self, m);
956 : : }
957 : :
958 : : /* Run iterator to exhaustion. */
959 : 22898043 : for (;;) {
960 : 24371054 : PyObject *item = iternext(it);
961 [ + + ]: 24371049 : if (item == NULL) {
962 [ + + ]: 1473006 : if (PyErr_Occurred()) {
963 [ + + ]: 2400 : if (PyErr_ExceptionMatches(PyExc_StopIteration))
964 : 1743 : PyErr_Clear();
965 : : else
966 : 657 : goto error;
967 : : }
968 : 1472349 : break;
969 : : }
970 [ + + ]: 22898043 : if (Py_SIZE(self) < self->allocated) {
971 : : /* steals ref */
972 : 22653265 : PyList_SET_ITEM(self, Py_SIZE(self), item);
973 : 22653265 : Py_SET_SIZE(self, Py_SIZE(self) + 1);
974 : : }
975 : : else {
976 [ - + ]: 244778 : 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 [ + + ]: 1472349 : if (Py_SIZE(self) < self->allocated) {
983 [ - + ]: 1071279 : if (list_resize(self, Py_SIZE(self)) < 0)
984 : 0 : goto error;
985 : : }
986 : :
987 : 1472349 : Py_DECREF(it);
988 : 1472349 : Py_RETURN_NONE;
989 : :
990 : 657 : error:
991 : 657 : Py_DECREF(it);
992 : 657 : return NULL;
993 : : }
994 : :
995 : : PyObject *
996 : 2973764 : _PyList_Extend(PyListObject *self, PyObject *iterable)
997 : : {
998 : 2973764 : return list_extend(self, iterable);
999 : : }
1000 : :
1001 : : static PyObject *
1002 : 161650 : list_inplace_concat(PyListObject *self, PyObject *other)
1003 : : {
1004 : : PyObject *result;
1005 : :
1006 : 161650 : result = list_extend(self, other);
1007 [ + + ]: 161650 : if (result == NULL)
1008 : 1 : return result;
1009 : 161649 : Py_DECREF(result);
1010 : 161649 : Py_INCREF(self);
1011 : 161649 : 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 : 2694691 : 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 [ + + ]: 2694691 : if (Py_SIZE(self) == 0) {
1033 : : /* Special-case most common failure cause */
1034 : 113425 : PyErr_SetString(PyExc_IndexError, "pop from empty list");
1035 : 113425 : return NULL;
1036 : : }
1037 [ + + ]: 2581266 : if (index < 0)
1038 : 2286992 : index += Py_SIZE(self);
1039 [ + + ]: 2581266 : if (!valid_index(index, Py_SIZE(self))) {
1040 : 2 : PyErr_SetString(PyExc_IndexError, "pop index out of range");
1041 : 2 : return NULL;
1042 : : }
1043 : 2581264 : v = self->ob_item[index];
1044 [ + + ]: 2581264 : if (index == Py_SIZE(self) - 1) {
1045 : 2291355 : status = list_resize(self, Py_SIZE(self) - 1);
1046 [ + - ]: 2291355 : if (status >= 0)
1047 : 2291355 : 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 : 703120 : reverse_slice(PyObject **lo, PyObject **hi)
1063 : : {
1064 : : assert(lo && hi);
1065 : :
1066 : 703120 : --hi;
1067 [ + + ]: 2104799 : while (lo < hi) {
1068 : 1401679 : PyObject *t = *lo;
1069 : 1401679 : *lo = *hi;
1070 : 1401679 : *hi = t;
1071 : 1401679 : ++lo;
1072 : 1401679 : --hi;
1073 : : }
1074 : 703120 : }
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 : 12398 : sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
1096 : : {
1097 : 12398 : s1->keys[i] = s2->keys[j];
1098 [ + + ]: 12398 : if (s1->values != NULL)
1099 : 618 : s1->values[i] = s2->values[j];
1100 : 12398 : }
1101 : :
1102 : : Py_LOCAL_INLINE(void)
1103 : 3454750 : sortslice_copy_incr(sortslice *dst, sortslice *src)
1104 : : {
1105 : 3454750 : *dst->keys++ = *src->keys++;
1106 [ + + ]: 3454750 : if (dst->values != NULL)
1107 : 84550 : *dst->values++ = *src->values++;
1108 : 3454750 : }
1109 : :
1110 : : Py_LOCAL_INLINE(void)
1111 : 2403402 : sortslice_copy_decr(sortslice *dst, sortslice *src)
1112 : : {
1113 : 2403402 : *dst->keys-- = *src->keys--;
1114 [ + + ]: 2403402 : if (dst->values != NULL)
1115 : 133933 : *dst->values-- = *src->values--;
1116 : 2403402 : }
1117 : :
1118 : :
1119 : : Py_LOCAL_INLINE(void)
1120 : 178007 : sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
1121 : : Py_ssize_t n)
1122 : : {
1123 : 178007 : memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1124 [ + + ]: 178007 : if (s1->values != NULL)
1125 : 3281 : memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1126 : 178007 : }
1127 : :
1128 : : Py_LOCAL_INLINE(void)
1129 : 108636 : sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
1130 : : Py_ssize_t n)
1131 : : {
1132 : 108636 : memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1133 [ + + ]: 108636 : if (s1->values != NULL)
1134 : 6440 : memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1135 : 108636 : }
1136 : :
1137 : : Py_LOCAL_INLINE(void)
1138 : 1852702 : sortslice_advance(sortslice *slice, Py_ssize_t n)
1139 : : {
1140 : 1852702 : slice->keys += n;
1141 [ + + ]: 1852702 : if (slice->values != NULL)
1142 : 134096 : slice->values += n;
1143 : 1852702 : }
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 : 1072622 : 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 : : assert(lo.keys <= start && start <= hi);
1257 : : /* assert [lo, start) is sorted */
1258 [ - + ]: 1072622 : if (lo.keys == start)
1259 : 0 : ++start;
1260 [ + + ]: 9245047 : for (; start < hi; ++start) {
1261 : : /* set l to where *start belongs */
1262 : 8172431 : l = lo.keys;
1263 : 8172431 : r = start;
1264 : 8172431 : 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 : : assert(l < r);
1271 : : do {
1272 : 27778733 : p = l + ((r - l) >> 1);
1273 [ + + + + ]: 27778733 : IFLT(pivot, *p)
1274 : 14691380 : r = p;
1275 : : else
1276 : 13087347 : l = p+1;
1277 [ + + ]: 27778727 : } while (l < r);
1278 : : 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 [ + + ]: 63429965 : for (p = start; p > l; --p)
1287 : 55257540 : *p = *(p-1);
1288 : 8172425 : *l = pivot;
1289 [ + + ]: 8172425 : if (lo.values != NULL) {
1290 : 182992 : Py_ssize_t offset = lo.values - lo.keys;
1291 : 182992 : p = start + offset;
1292 : 182992 : pivot = *p;
1293 : 182992 : l += offset;
1294 [ + + ]: 1522259 : for (p = start + offset; p > l; --p)
1295 : 1339267 : *p = *(p-1);
1296 : 182992 : *l = pivot;
1297 : : }
1298 : : }
1299 : 1072616 : return 0;
1300 : :
1301 : 6 : fail:
1302 : 6 : 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 : 1391656 : count_run(MergeState *ms, PyObject **lo, PyObject **hi, int *descending)
1325 : : {
1326 : : Py_ssize_t k;
1327 : : Py_ssize_t n;
1328 : :
1329 : : assert(lo < hi);
1330 : 1391656 : *descending = 0;
1331 : 1391656 : ++lo;
1332 [ + + ]: 1391656 : if (lo == hi)
1333 : 16 : return 1;
1334 : :
1335 : 1391640 : n = 2;
1336 [ + + + + ]: 1391640 : IFLT(*lo, *(lo-1)) {
1337 : 635494 : *descending = 1;
1338 [ + + ]: 936852 : for (lo = lo+1; lo < hi; ++lo, ++n) {
1339 [ + + + + ]: 820457 : IFLT(*lo, *(lo-1))
1340 : : ;
1341 : : else
1342 : 519098 : break;
1343 : : }
1344 : : }
1345 : : else {
1346 [ + + ]: 1911239 : for (lo = lo+1; lo < hi; ++lo, ++n) {
1347 [ + + + + ]: 1708885 : IFLT(*lo, *(lo-1))
1348 : 553765 : break;
1349 : : }
1350 : : }
1351 : :
1352 : 1391612 : 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 : 198777 : 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 : : assert(key && a && n > 0 && hint >= 0 && hint < n);
1386 : :
1387 : 198777 : a += hint;
1388 : 198777 : lastofs = 0;
1389 : 198777 : ofs = 1;
1390 [ - + + + ]: 198777 : IFLT(*a, key) {
1391 : : /* a[hint] < key -- gallop right, until
1392 : : * a[hint + lastofs] < key <= a[hint + ofs]
1393 : : */
1394 : 115820 : const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1395 [ + + ]: 260597 : while (ofs < maxofs) {
1396 [ - + + + ]: 209219 : IFLT(a[ofs], key) {
1397 : 144777 : lastofs = ofs;
1398 : : assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1399 : 144777 : ofs = (ofs << 1) + 1;
1400 : : }
1401 : : else /* key <= a[hint + ofs] */
1402 : 64442 : break;
1403 : : }
1404 [ + + ]: 115820 : if (ofs > maxofs)
1405 : 6643 : ofs = maxofs;
1406 : : /* Translate back to offsets relative to &a[0]. */
1407 : 115820 : lastofs += hint;
1408 : 115820 : ofs += hint;
1409 : : }
1410 : : else {
1411 : : /* key <= a[hint] -- gallop left, until
1412 : : * a[hint - ofs] < key <= a[hint - lastofs]
1413 : : */
1414 : 82957 : const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1415 [ + + ]: 159510 : while (ofs < maxofs) {
1416 [ - + + + ]: 123438 : IFLT(*(a-ofs), key)
1417 : 46885 : break;
1418 : : /* key <= a[hint - ofs] */
1419 : 76553 : lastofs = ofs;
1420 : : assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1421 : 76553 : ofs = (ofs << 1) + 1;
1422 : : }
1423 [ + + ]: 82957 : if (ofs > maxofs)
1424 : 443 : ofs = maxofs;
1425 : : /* Translate back to positive offsets relative to &a[0]. */
1426 : 82957 : k = lastofs;
1427 : 82957 : lastofs = hint - ofs;
1428 : 82957 : ofs = hint - k;
1429 : : }
1430 : 198777 : a -= hint;
1431 : :
1432 : : 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 : 198777 : ++lastofs;
1438 [ + + ]: 412600 : while (lastofs < ofs) {
1439 : 213823 : Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
1440 : :
1441 [ - + + + ]: 213823 : IFLT(a[m], key)
1442 : 99347 : lastofs = m+1; /* a[m] < key */
1443 : : else
1444 : 114476 : ofs = m; /* key <= a[m] */
1445 : : }
1446 : : assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1447 : 198777 : 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 : 205965 : 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 : : assert(key && a && n > 0 && hint >= 0 && hint < n);
1475 : :
1476 : 205965 : a += hint;
1477 : 205965 : lastofs = 0;
1478 : 205965 : ofs = 1;
1479 [ - + + + ]: 205965 : IFLT(key, *a) {
1480 : : /* key < a[hint] -- gallop left, until
1481 : : * a[hint - ofs] <= key < a[hint - lastofs]
1482 : : */
1483 : 110161 : const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1484 [ + + ]: 162239 : while (ofs < maxofs) {
1485 [ - + + + ]: 72462 : IFLT(key, *(a-ofs)) {
1486 : 52078 : lastofs = ofs;
1487 : : assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1488 : 52078 : ofs = (ofs << 1) + 1;
1489 : : }
1490 : : else /* a[hint - ofs] <= key */
1491 : 20384 : break;
1492 : : }
1493 [ + + ]: 110161 : if (ofs > maxofs)
1494 : 3312 : ofs = maxofs;
1495 : : /* Translate back to positive offsets relative to &a[0]. */
1496 : 110161 : k = lastofs;
1497 : 110161 : lastofs = hint - ofs;
1498 : 110161 : ofs = hint - k;
1499 : : }
1500 : : else {
1501 : : /* a[hint] <= key -- gallop right, until
1502 : : * a[hint + lastofs] <= key < a[hint + ofs]
1503 : : */
1504 : 95804 : const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1505 [ + + ]: 259423 : while (ofs < maxofs) {
1506 [ - + + + ]: 241822 : IFLT(key, a[ofs])
1507 : 78203 : break;
1508 : : /* a[hint + ofs] <= key */
1509 : 163619 : lastofs = ofs;
1510 : : assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
1511 : 163619 : ofs = (ofs << 1) + 1;
1512 : : }
1513 [ + + ]: 95804 : if (ofs > maxofs)
1514 : 1109 : ofs = maxofs;
1515 : : /* Translate back to offsets relative to &a[0]. */
1516 : 95804 : lastofs += hint;
1517 : 95804 : ofs += hint;
1518 : : }
1519 : 205965 : a -= hint;
1520 : :
1521 : : 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 : 205965 : ++lastofs;
1527 [ + + ]: 416458 : while (lastofs < ofs) {
1528 : 210493 : Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
1529 : :
1530 [ - + + + ]: 210493 : IFLT(key, a[m])
1531 : 121707 : ofs = m; /* key < a[m] */
1532 : : else
1533 : 88786 : lastofs = m+1; /* a[m] <= key */
1534 : : }
1535 : : assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1536 : 205965 : return ofs;
1537 : :
1538 : 0 : fail:
1539 : 0 : return -1;
1540 : : }
1541 : :
1542 : : /* Conceptually a MergeState's constructor. */
1543 : : static void
1544 : 1996552 : merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc,
1545 : : sortslice *lo)
1546 : : {
1547 : : assert(ms != NULL);
1548 [ + + ]: 1996552 : 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 : 302261 : 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 [ + + ]: 302261 : if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
1560 : 132 : ms->alloced = MERGESTATE_TEMP_SIZE / 2;
1561 : 302261 : ms->a.values = &ms->temparray[ms->alloced];
1562 : : }
1563 : : else {
1564 : 1694291 : ms->alloced = MERGESTATE_TEMP_SIZE;
1565 : 1694291 : ms->a.values = NULL;
1566 : : }
1567 : 1996552 : ms->a.keys = ms->temparray;
1568 : 1996552 : ms->n = 0;
1569 : 1996552 : ms->min_gallop = MIN_GALLOP;
1570 : 1996552 : ms->listlen = list_size;
1571 : 1996552 : ms->basekeys = lo->keys;
1572 : 1996552 : }
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 : 1997036 : merge_freemem(MergeState *ms)
1580 : : {
1581 : : assert(ms != NULL);
1582 [ + + ]: 1997036 : if (ms->a.keys != ms->temparray) {
1583 : 484 : PyMem_Free(ms->a.keys);
1584 : 484 : ms->a.keys = NULL;
1585 : : }
1586 : 1997036 : }
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 : 484 : merge_getmem(MergeState *ms, Py_ssize_t need)
1593 : : {
1594 : : int multiplier;
1595 : :
1596 : : assert(ms != NULL);
1597 [ - + ]: 484 : if (need <= ms->alloced)
1598 : 0 : return 0;
1599 : :
1600 [ + + ]: 484 : 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 : 484 : merge_freemem(ms);
1606 [ - + ]: 484 : if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject *) / multiplier) {
1607 : : PyErr_NoMemory();
1608 : 0 : return -1;
1609 : : }
1610 : 484 : ms->a.keys = (PyObject **)PyMem_Malloc(multiplier * need
1611 : : * sizeof(PyObject *));
1612 [ + - ]: 484 : if (ms->a.keys != NULL) {
1613 : 484 : ms->alloced = need;
1614 [ + + ]: 484 : if (ms->a.values != NULL)
1615 : 136 : ms->a.values = &ms->a.keys[need];
1616 : 484 : return 0;
1617 : : }
1618 : : 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 : 34303 : 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 : 34303 : int result = -1; /* guilty until proved innocent */
1637 : : Py_ssize_t min_gallop;
1638 : :
1639 : : assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1640 : : assert(ssa.keys + na == ssb.keys);
1641 [ + + - + ]: 34303 : if (MERGE_GETMEM(ms, na) < 0)
1642 : 0 : return -1;
1643 : 34303 : sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
1644 : 34303 : dest = ssa;
1645 : 34303 : ssa = ms->a;
1646 : :
1647 : 34303 : sortslice_copy_incr(&dest, &ssb);
1648 : 34303 : --nb;
1649 [ + + ]: 34303 : if (nb == 0)
1650 : 5 : goto Succeed;
1651 [ + + ]: 34298 : if (na == 1)
1652 : 10 : goto CopyB;
1653 : :
1654 : 34288 : min_gallop = ms->min_gallop;
1655 : 55471 : for (;;) {
1656 : 89759 : Py_ssize_t acount = 0; /* # of times A won in a row */
1657 : 89759 : 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 : 3115282 : assert(na > 1 && nb > 0);
1664 : 3205041 : k = ISLT(ssb.keys[0], ssa.keys[0]);
1665 [ + + ]: 3205041 : if (k) {
1666 [ + + ]: 1617749 : if (k < 0)
1667 : 2 : goto Fail;
1668 : 1617747 : sortslice_copy_incr(&dest, &ssb);
1669 : 1617747 : ++bcount;
1670 : 1617747 : acount = 0;
1671 : 1617747 : --nb;
1672 [ + + ]: 1617747 : if (nb == 0)
1673 : 17712 : goto Succeed;
1674 [ + + ]: 1600035 : if (bcount >= min_gallop)
1675 : 38674 : break;
1676 : : }
1677 : : else {
1678 : 1587292 : sortslice_copy_incr(&dest, &ssa);
1679 : 1587292 : ++acount;
1680 : 1587292 : bcount = 0;
1681 : 1587292 : --na;
1682 [ + + ]: 1587292 : if (na == 1)
1683 : 7413 : goto CopyB;
1684 [ + + ]: 1579879 : if (acount >= min_gallop)
1685 : 25958 : 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 : 64632 : ++min_gallop;
1695 : : do {
1696 : : assert(na > 1 && nb > 0);
1697 : 112243 : min_gallop -= min_gallop > 1;
1698 : 112243 : ms->min_gallop = min_gallop;
1699 : 112243 : k = gallop_right(ms, ssb.keys[0], ssa.keys, na, 0);
1700 : 112243 : acount = k;
1701 [ + + ]: 112243 : if (k) {
1702 [ - + ]: 55318 : if (k < 0)
1703 : 0 : goto Fail;
1704 : 55318 : sortslice_memcpy(&dest, 0, &ssa, 0, k);
1705 : 55318 : sortslice_advance(&dest, k);
1706 : 55318 : sortslice_advance(&ssa, k);
1707 : 55318 : na -= k;
1708 [ + + ]: 55318 : if (na == 1)
1709 : 50 : 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 [ + + ]: 55268 : if (na == 0)
1715 : 2 : goto Succeed;
1716 : : }
1717 : 112191 : sortslice_copy_incr(&dest, &ssb);
1718 : 112191 : --nb;
1719 [ + + ]: 112191 : if (nb == 0)
1720 : 4401 : goto Succeed;
1721 : :
1722 : 107790 : k = gallop_left(ms, ssa.keys[0], ssb.keys, nb, 0);
1723 : 107790 : bcount = k;
1724 [ + + ]: 107790 : if (k) {
1725 [ - + ]: 72249 : if (k < 0)
1726 : 0 : goto Fail;
1727 : 72249 : sortslice_memmove(&dest, 0, &ssb, 0, k);
1728 : 72249 : sortslice_advance(&dest, k);
1729 : 72249 : sortslice_advance(&ssb, k);
1730 : 72249 : nb -= k;
1731 [ + + ]: 72249 : if (nb == 0)
1732 : 4573 : goto Succeed;
1733 : : }
1734 : 103217 : sortslice_copy_incr(&dest, &ssa);
1735 : 103217 : --na;
1736 [ + + ]: 103217 : if (na == 1)
1737 : 135 : goto CopyB;
1738 [ + + + + ]: 103082 : } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1739 : 55471 : ++min_gallop; /* penalize it for leaving galloping mode */
1740 : 55471 : ms->min_gallop = min_gallop;
1741 : : }
1742 : 26693 : Succeed:
1743 : 26693 : result = 0;
1744 : 26695 : Fail:
1745 [ + + ]: 26695 : if (na)
1746 : 26693 : sortslice_memcpy(&dest, 0, &ssa, 0, na);
1747 : 26695 : return result;
1748 : 7608 : CopyB:
1749 : : assert(na == 1 && nb > 0);
1750 : : /* The last element of ssa belongs at the end of the merge. */
1751 : 7608 : sortslice_memmove(&dest, 0, &ssb, 0, nb);
1752 : 7608 : sortslice_copy(&dest, nb, &ssa, 0);
1753 : 7608 : 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 : 18939 : 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 : 18939 : int result = -1; /* guilty until proved innocent */
1769 : : Py_ssize_t min_gallop;
1770 : :
1771 : : assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1772 : : assert(ssa.keys + na == ssb.keys);
1773 [ + + - + ]: 18939 : if (MERGE_GETMEM(ms, nb) < 0)
1774 : 0 : return -1;
1775 : 18939 : dest = ssb;
1776 : 18939 : sortslice_advance(&dest, nb-1);
1777 : 18939 : sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
1778 : 18939 : basea = ssa;
1779 : 18939 : baseb = ms->a;
1780 : 18939 : ssb.keys = ms->a.keys + nb - 1;
1781 [ + + ]: 18939 : if (ssb.values != NULL)
1782 : 695 : ssb.values = ms->a.values + nb - 1;
1783 : 18939 : sortslice_advance(&ssa, na - 1);
1784 : :
1785 : 18939 : sortslice_copy_decr(&dest, &ssa);
1786 : 18939 : --na;
1787 [ - + ]: 18939 : if (na == 0)
1788 : 0 : goto Succeed;
1789 [ + + ]: 18939 : if (nb == 1)
1790 : 57 : goto CopyA;
1791 : :
1792 : 18882 : min_gallop = ms->min_gallop;
1793 : 22288 : for (;;) {
1794 : 41170 : Py_ssize_t acount = 0; /* # of times A won in a row */
1795 : 41170 : 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 : 2267950 : assert(na > 0 && nb > 1);
1802 : 2309120 : k = ISLT(ssb.keys[0], ssa.keys[0]);
1803 [ + + ]: 2309120 : if (k) {
1804 [ - + ]: 1208199 : if (k < 0)
1805 : 0 : goto Fail;
1806 : 1208199 : sortslice_copy_decr(&dest, &ssa);
1807 : 1208199 : ++acount;
1808 : 1208199 : bcount = 0;
1809 : 1208199 : --na;
1810 [ + + ]: 1208199 : if (na == 0)
1811 : 10752 : goto Succeed;
1812 [ + + ]: 1197447 : if (acount >= min_gallop)
1813 : 15391 : break;
1814 : : }
1815 : : else {
1816 : 1100921 : sortslice_copy_decr(&dest, &ssb);
1817 : 1100921 : ++bcount;
1818 : 1100921 : acount = 0;
1819 : 1100921 : --nb;
1820 [ + + ]: 1100921 : if (nb == 1)
1821 : 4537 : goto CopyA;
1822 [ + + ]: 1096384 : if (bcount >= min_gallop)
1823 : 10490 : 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 : 25881 : ++min_gallop;
1833 : : do {
1834 : : assert(na > 0 && nb > 1);
1835 : 40422 : min_gallop -= min_gallop > 1;
1836 : 40422 : ms->min_gallop = min_gallop;
1837 : 40422 : k = gallop_right(ms, ssb.keys[0], basea.keys, na, na-1);
1838 [ - + ]: 40422 : if (k < 0)
1839 : 0 : goto Fail;
1840 : 40422 : k = na - k;
1841 : 40422 : acount = k;
1842 [ + + ]: 40422 : if (k) {
1843 : 23989 : sortslice_advance(&dest, -k);
1844 : 23989 : sortslice_advance(&ssa, -k);
1845 : 23989 : sortslice_memmove(&dest, 1, &ssa, 1, k);
1846 : 23989 : na -= k;
1847 [ + + ]: 23989 : if (na == 0)
1848 : 2652 : goto Succeed;
1849 : : }
1850 : 37770 : sortslice_copy_decr(&dest, &ssb);
1851 : 37770 : --nb;
1852 [ + + ]: 37770 : if (nb == 1)
1853 : 25 : goto CopyA;
1854 : :
1855 : 37745 : k = gallop_left(ms, ssa.keys[0], baseb.keys, nb, nb-1);
1856 [ - + ]: 37745 : if (k < 0)
1857 : 0 : goto Fail;
1858 : 37745 : k = nb - k;
1859 : 37745 : bcount = k;
1860 [ + + ]: 37745 : if (k) {
1861 : 28606 : sortslice_advance(&dest, -k);
1862 : 28606 : sortslice_advance(&ssb, -k);
1863 : 28606 : sortslice_memcpy(&dest, 1, &ssb, 1, k);
1864 : 28606 : nb -= k;
1865 [ + + ]: 28606 : if (nb == 1)
1866 : 171 : 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 [ + + ]: 28435 : if (nb == 0)
1872 : 1 : goto Succeed;
1873 : : }
1874 : 37573 : sortslice_copy_decr(&dest, &ssa);
1875 : 37573 : --na;
1876 [ + + ]: 37573 : if (na == 0)
1877 : 744 : goto Succeed;
1878 [ + + + + ]: 36829 : } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1879 : 22288 : ++min_gallop; /* penalize it for leaving galloping mode */
1880 : 22288 : ms->min_gallop = min_gallop;
1881 : : }
1882 : 14149 : Succeed:
1883 : 14149 : result = 0;
1884 : 14149 : Fail:
1885 [ + + ]: 14149 : if (nb)
1886 : 14148 : sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
1887 : 14149 : return result;
1888 : 4790 : CopyA:
1889 : : assert(nb == 1 && na > 0);
1890 : : /* The first element of ssb belongs at the front of the merge. */
1891 : 4790 : sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
1892 : 4790 : sortslice_advance(&dest, -na);
1893 : 4790 : sortslice_advance(&ssa, -na);
1894 : 4790 : sortslice_copy(&dest, 0, &ssb, 0);
1895 : 4790 : 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 : 53300 : 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 : : assert(ms != NULL);
1909 : : assert(ms->n >= 2);
1910 : : assert(i >= 0);
1911 : : assert(i == ms->n - 2 || i == ms->n - 3);
1912 : :
1913 : 53300 : ssa = ms->pending[i].base;
1914 : 53300 : na = ms->pending[i].len;
1915 : 53300 : ssb = ms->pending[i+1].base;
1916 : 53300 : nb = ms->pending[i+1].len;
1917 : : assert(na > 0 && nb > 0);
1918 : : 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 : 53300 : ms->pending[i].len = na + nb;
1925 [ + + ]: 53300 : if (i == ms->n - 3)
1926 : 8 : ms->pending[i+1] = ms->pending[i+2];
1927 : 53300 : --ms->n;
1928 : :
1929 : : /* Where does b start in a? Elements in a before that can be
1930 : : * ignored (already in place).
1931 : : */
1932 : 53300 : k = gallop_right(ms, *ssb.keys, ssa.keys, na, 0);
1933 [ - + ]: 53300 : if (k < 0)
1934 : 0 : return -1;
1935 : 53300 : sortslice_advance(&ssa, k);
1936 : 53300 : na -= k;
1937 [ + + ]: 53300 : if (na == 0)
1938 : 58 : return 0;
1939 : :
1940 : : /* Where does a end in b? Elements in b after that can be
1941 : : * ignored (already in place).
1942 : : */
1943 : 53242 : nb = gallop_left(ms, ssa.keys[na-1], ssb.keys, nb, nb-1);
1944 [ - + ]: 53242 : if (nb <= 0)
1945 : 0 : return nb;
1946 : :
1947 : : /* Merge what remains of the runs, using a temp array with
1948 : : * min(na, nb) elements.
1949 : : */
1950 [ + + ]: 53242 : if (na <= nb)
1951 : 34303 : return merge_lo(ms, ssa, na, ssb, nb);
1952 : : else
1953 : 18939 : 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 : 53308 : powerloop(Py_ssize_t s1, Py_ssize_t n1, Py_ssize_t n2, Py_ssize_t n)
1963 : : {
1964 : 53308 : int result = 0;
1965 : : assert(s1 >= 0);
1966 : : assert(n1 > 0 && n2 > 0);
1967 : : 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 : 53308 : Py_ssize_t a = 2 * s1 + n1; /* 2*a */
1978 : 53308 : 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 : 143805 : ++result;
1982 [ + + ]: 143805 : if (a >= n) { /* both quotient bits are 1 */
1983 : : assert(b >= a);
1984 : 45233 : a -= n;
1985 : 45233 : b -= n;
1986 : : }
1987 [ + + ]: 98572 : else if (b >= n) { /* a/n bit is 0, b/n bit is 1 */
1988 : 53308 : break;
1989 : : } /* else both quotient bits are 0 */
1990 : : assert(a < b && b < n);
1991 : 90497 : a <<= 1;
1992 : 90497 : b <<= 1;
1993 : : }
1994 : 53308 : 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 : 1391622 : found_new_run(MergeState *ms, Py_ssize_t n2)
2010 : : {
2011 : : assert(ms);
2012 [ + + ]: 1391622 : if (ms->n) {
2013 : : assert(ms->n > 0);
2014 : 53308 : struct s_slice *p = ms->pending;
2015 : 53308 : Py_ssize_t s1 = p[ms->n - 1].base.keys - ms->basekeys; /* start index */
2016 : 53308 : Py_ssize_t n1 = p[ms->n - 1].len;
2017 : 53308 : int power = powerloop(s1, n1, n2, ms->listlen);
2018 [ + + + + ]: 79355 : while (ms->n > 1 && p[ms->n - 2].power > power) {
2019 [ + + ]: 26049 : if (merge_at(ms, ms->n - 2) < 0)
2020 : 2 : return -1;
2021 : : }
2022 : : assert(ms->n < 2 || p[ms->n - 2].power < power);
2023 : 53306 : p[ms->n - 1].power = power;
2024 : : }
2025 : 1391620 : 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 : 1338308 : merge_force_collapse(MergeState *ms)
2035 : : {
2036 : 1338308 : struct s_slice *p = ms->pending;
2037 : :
2038 : : assert(ms);
2039 [ + + ]: 1365559 : while (ms->n > 1) {
2040 : 27251 : Py_ssize_t n = ms->n - 2;
2041 [ + + + + ]: 27251 : if (n > 0 && p[n-1].len < p[n+1].len)
2042 : 8 : --n;
2043 [ - + ]: 27251 : if (merge_at(ms, n) < 0)
2044 : 0 : return -1;
2045 : : }
2046 : 1338308 : 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 : 1338344 : merge_compute_minrun(Py_ssize_t n)
2061 : : {
2062 : 1338344 : Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
2063 : :
2064 : : assert(n >= 0);
2065 [ + + ]: 1366790 : while (n >= 64) {
2066 : 28446 : r |= n & 1;
2067 : 28446 : n >>= 1;
2068 : : }
2069 : 1338344 : return n + r;
2070 : : }
2071 : :
2072 : : static void
2073 : 635493 : reverse_sortslice(sortslice *s, Py_ssize_t n)
2074 : : {
2075 : 635493 : reverse_slice(s->keys, &s->keys[n]);
2076 [ + + ]: 635493 : if (s->values != NULL)
2077 : 11814 : reverse_slice(s->values, &s->values[n]);
2078 : 635493 : }
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 : 204900 : safe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
2092 : : {
2093 : : /* No assumptions necessary! */
2094 : 204900 : 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 : 937930 : 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 [ + + ]: 937930 : if (Py_TYPE(v)->tp_richcompare != ms->key_richcompare)
2108 : 2 : return PyObject_RichCompareBool(v, w, Py_LT);
2109 : :
2110 : : assert(ms->key_richcompare != NULL);
2111 : 937928 : res_obj = (*(ms->key_richcompare))(v, w, Py_LT);
2112 : :
2113 [ + + ]: 937928 : if (res_obj == Py_NotImplemented) {
2114 : 7 : Py_DECREF(res_obj);
2115 : 7 : return PyObject_RichCompareBool(v, w, Py_LT);
2116 : : }
2117 [ + + ]: 937921 : if (res_obj == NULL)
2118 : 8 : return -1;
2119 : :
2120 [ + - ]: 937913 : if (PyBool_Check(res_obj)) {
2121 : 937913 : res = (res_obj == Py_True);
2122 : : }
2123 : : else {
2124 : 0 : res = PyObject_IsTrue(res_obj);
2125 : : }
2126 : 937913 : 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 : 937913 : return res;
2134 : : }
2135 : :
2136 : : /* Latin string compare: safe for any two latin (one byte per char) strings. */
2137 : : static int
2138 : 28779609 : 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 : : assert(Py_IS_TYPE(v, &PyUnicode_Type));
2145 : : assert(Py_IS_TYPE(w, &PyUnicode_Type));
2146 : : assert(PyUnicode_KIND(v) == PyUnicode_KIND(w));
2147 : : assert(PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
2148 : :
2149 [ + + ]: 28779609 : len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
2150 : 28779609 : res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);
2151 : :
2152 : 28779609 : res = (res != 0 ?
2153 [ + + ]: 28779609 : res < 0 :
2154 : 1197401 : PyUnicode_GET_LENGTH(v) < PyUnicode_GET_LENGTH(w));
2155 : :
2156 : : assert(res == PyObject_RichCompareBool(v, w, Py_LT));;
2157 : 28779609 : return res;
2158 : : }
2159 : :
2160 : : /* Bounded int compare: compare any two longs that fit in a single machine word. */
2161 : : static int
2162 : 8483879 : 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 : : assert(Py_IS_TYPE(v, &PyLong_Type));
2168 : : assert(Py_IS_TYPE(w, &PyLong_Type));
2169 : : assert(Py_ABS(Py_SIZE(v)) <= 1);
2170 : : assert(Py_ABS(Py_SIZE(w)) <= 1);
2171 : :
2172 : 8483879 : vl = (PyLongObject*)v;
2173 : 8483879 : wl = (PyLongObject*)w;
2174 : :
2175 [ + + ]: 8483879 : v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->ob_digit[0];
2176 [ + + ]: 8483879 : w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->ob_digit[0];
2177 : :
2178 [ + + ]: 8483879 : if (Py_SIZE(vl) < 0)
2179 : 95476 : v0 = -v0;
2180 [ + + ]: 8483879 : if (Py_SIZE(wl) < 0)
2181 : 96707 : w0 = -w0;
2182 : :
2183 : 8483879 : res = v0 < w0;
2184 : : assert(res == PyObject_RichCompareBool(v, w, Py_LT));
2185 : 8483879 : return res;
2186 : : }
2187 : :
2188 : : /* Float compare: compare any two floats. */
2189 : : static int
2190 : 364791 : unsafe_float_compare(PyObject *v, PyObject *w, MergeState *ms)
2191 : : {
2192 : : int res;
2193 : :
2194 : : /* Modified from Objects/floatobject.c:float_richcompare, assuming: */
2195 : : assert(Py_IS_TYPE(v, &PyFloat_Type));
2196 : : assert(Py_IS_TYPE(w, &PyFloat_Type));
2197 : :
2198 : 364791 : res = PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w);
2199 : : assert(res == PyObject_RichCompareBool(v, w, Py_LT));
2200 : 364791 : 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 : 4281282 : 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 : : assert(Py_IS_TYPE(v, &PyTuple_Type));
2235 : : assert(Py_IS_TYPE(w, &PyTuple_Type));
2236 : : assert(Py_SIZE(v) > 0);
2237 : : assert(Py_SIZE(w) > 0);
2238 : :
2239 : 4281282 : vt = (PyTupleObject *)v;
2240 : 4281282 : wt = (PyTupleObject *)w;
2241 : 4281282 : i = 0;
2242 [ + + ]: 4281282 : if (ms->first_tuple_items_resolved_it) {
2243 : : /* See whether fast compares of the first elements settle it. */
2244 : 2646731 : k = ms->tuple_elem_compare(vt->ob_item[0], wt->ob_item[0], ms);
2245 [ + + ]: 2646731 : if (k) /* error, or v < w */
2246 : 1147963 : return k;
2247 : 1498768 : k = ms->tuple_elem_compare(wt->ob_item[0], vt->ob_item[0], ms);
2248 [ + + ]: 1498768 : if (k > 0) /* w < v */
2249 : 1274187 : return 0;
2250 [ - + ]: 224581 : 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 : 224581 : i = 1;
2258 : 224581 : 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 : : assert(! ms->first_tuple_items_resolved_it);
2264 : :
2265 : 1859132 : vlen = Py_SIZE(vt);
2266 : 1859132 : wlen = Py_SIZE(wt);
2267 [ + + + + ]: 6523847 : for (; i < vlen && i < wlen; i++) {
2268 : 6486894 : k = PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_EQ);
2269 [ + + ]: 6486894 : if (!k) { /* not equal */
2270 [ + + ]: 1822179 : if (i) {
2271 : 1605162 : return PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i],
2272 : : Py_LT);
2273 : : }
2274 : : else {
2275 : 217017 : ms->first_tuple_items_resolved_it = 1;
2276 : 217017 : return ms->tuple_elem_compare(vt->ob_item[0], wt->ob_item[0],
2277 : : ms);
2278 : : }
2279 : : }
2280 [ - + ]: 4664715 : if (k < 0)
2281 : 0 : return -1;
2282 : : }
2283 : : /* all equal until we fell off the end */
2284 : 36953 : 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 : 1996584 : 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 : 1996584 : PyObject *result = NULL; /* guilty until proved innocent */
2323 : : Py_ssize_t i;
2324 : : PyObject **keys;
2325 : :
2326 : : assert(self != NULL);
2327 : : assert(PyList_Check(self));
2328 [ + + ]: 1996584 : if (keyfunc == Py_None)
2329 : 560495 : 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 : 1996584 : saved_ob_size = Py_SIZE(self);
2337 : 1996584 : saved_ob_item = self->ob_item;
2338 : 1996584 : saved_allocated = self->allocated;
2339 : 1996584 : Py_SET_SIZE(self, 0);
2340 : 1996584 : self->ob_item = NULL;
2341 : 1996584 : self->allocated = -1; /* any operation will reset it to >= 0 */
2342 : :
2343 [ + + ]: 1996584 : if (keyfunc == NULL) {
2344 : 1694291 : keys = NULL;
2345 : 1694291 : lo.keys = saved_ob_item;
2346 : 1694291 : lo.values = NULL;
2347 : : }
2348 : : else {
2349 [ + + ]: 302293 : if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
2350 : : /* Leverage stack space we allocated but won't otherwise use */
2351 : 302069 : keys = &ms.temparray[saved_ob_size+1];
2352 : : else {
2353 : 224 : keys = PyMem_Malloc(sizeof(PyObject *) * saved_ob_size);
2354 [ - + ]: 224 : if (keys == NULL) {
2355 : : PyErr_NoMemory();
2356 : 0 : goto keyfunc_fail;
2357 : : }
2358 : : }
2359 : :
2360 [ + + ]: 928358 : for (i = 0; i < saved_ob_size ; i++) {
2361 : 626097 : keys[i] = PyObject_CallOneArg(keyfunc, saved_ob_item[i]);
2362 [ + + ]: 626097 : 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 : 302261 : lo.keys = keys;
2372 : 302261 : 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 [ + + ]: 1996552 : if (saved_ob_size > 1) {
2381 : : /* Assume the first element is representative of the whole list. */
2382 [ + + + - ]: 1360810 : int keys_are_in_tuples = (Py_IS_TYPE(lo.keys[0], &PyTuple_Type) &&
2383 : 22466 : Py_SIZE(lo.keys[0]) > 0);
2384 : :
2385 : 1338344 : PyTypeObject* key_type = (keys_are_in_tuples ?
2386 [ + + ]: 1338344 : Py_TYPE(PyTuple_GET_ITEM(lo.keys[0], 0)) :
2387 : 1315878 : Py_TYPE(lo.keys[0]));
2388 : :
2389 : 1338344 : int keys_are_all_same_type = 1;
2390 : 1338344 : int strings_are_latin = 1;
2391 : 1338344 : int ints_are_bounded = 1;
2392 : :
2393 : : /* Prove that assumption by checking every key. */
2394 [ + + ]: 13752210 : for (i=0; i < saved_ob_size; i++) {
2395 : :
2396 [ + + + + ]: 13060455 : if (keys_are_in_tuples &&
2397 [ - + ]: 1293094 : !(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 : 12413905 : PyObject *key = (keys_are_in_tuples ?
2407 [ + + ]: 12413905 : PyTuple_GET_ITEM(lo.keys[i], 0) :
2408 : 11767359 : lo.keys[i]);
2409 : :
2410 [ + + ]: 12413905 : 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 [ + + ]: 12413866 : if (keys_are_all_same_type) {
2420 [ + + + + : 15726949 : if (key_type == &PyLong_Type &&
+ + ]
2421 : 48244 : ints_are_bounded &&
2422 [ + + + + ]: 6626244 : Py_ABS(Py_SIZE(key)) > 1) {
2423 : :
2424 : 2557 : ints_are_bounded = 0;
2425 : : }
2426 [ + + + + ]: 12411270 : else if (key_type == &PyUnicode_Type &&
2427 : 8653812 : strings_are_latin &&
2428 [ + + ]: 8653812 : 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 [ + + ]: 1338344 : if (keys_are_all_same_type) {
2437 : :
2438 [ + + + + ]: 1338270 : if (key_type == &PyUnicode_Type && strings_are_latin) {
2439 : 906115 : ms.key_compare = unsafe_latin_compare;
2440 : : }
2441 [ + + + + ]: 432155 : else if (key_type == &PyLong_Type && ints_are_bounded) {
2442 : 412923 : ms.key_compare = unsafe_long_compare;
2443 : : }
2444 [ + + ]: 19232 : else if (key_type == &PyFloat_Type) {
2445 : 176 : ms.key_compare = unsafe_float_compare;
2446 : : }
2447 [ + - ]: 19056 : else if ((ms.key_richcompare = key_type->tp_richcompare) != NULL) {
2448 : 19056 : 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 [ + + ]: 1338344 : 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 [ + + ]: 22464 : if (key_type == &PyTuple_Type) {
2462 : 84 : ms.tuple_elem_compare = safe_object_compare;
2463 : : }
2464 : : else {
2465 : 22380 : ms.tuple_elem_compare = ms.key_compare;
2466 : : }
2467 : :
2468 : 22464 : ms.key_compare = unsafe_tuple_compare;
2469 : 22464 : ms.first_tuple_items_resolved_it = 1; /* be optimistic */
2470 : : }
2471 : : }
2472 : : /* End of pre-sort check: ms is now set properly! */
2473 : :
2474 : 1996552 : merge_init(&ms, saved_ob_size, keys != NULL, &lo);
2475 : :
2476 : 1996552 : nremaining = saved_ob_size;
2477 [ + + ]: 1996552 : if (nremaining < 2)
2478 : 658208 : 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 [ + + ]: 1338344 : if (reverse) {
2483 [ + + ]: 4552 : if (keys != NULL)
2484 : 2526 : reverse_slice(&keys[0], &keys[saved_ob_size]);
2485 : 4552 : 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 : 1338344 : minrun = merge_compute_minrun(nremaining);
2492 : : do {
2493 : : int descending;
2494 : : Py_ssize_t n;
2495 : :
2496 : : /* Identify next run. */
2497 : 1391656 : n = count_run(&ms, lo.keys, lo.keys + nremaining, &descending);
2498 [ + + ]: 1391656 : if (n < 0)
2499 : 36 : goto fail;
2500 [ + + ]: 1391628 : if (descending)
2501 : 635493 : reverse_sortslice(&lo, n);
2502 : : /* If short, extend to min(minrun, nremaining). */
2503 [ + + ]: 1391628 : if (n < minrun) {
2504 : 1072622 : const Py_ssize_t force = nremaining <= minrun ?
2505 : : nremaining : minrun;
2506 [ + + ]: 1072622 : if (binarysort(&ms, lo, lo.keys + force, lo.keys + n) < 0)
2507 : 6 : goto fail;
2508 : 1072616 : n = force;
2509 : : }
2510 : : /* Maybe merge pending runs. */
2511 : : assert(ms.n == 0 || ms.pending[ms.n -1].base.keys +
2512 : : ms.pending[ms.n-1].len == lo.keys);
2513 [ + + ]: 1391622 : if (found_new_run(&ms, n) < 0)
2514 : 2 : goto fail;
2515 : : /* Push new run on stack. */
2516 : : assert(ms.n < MAX_MERGE_PENDING);
2517 : 1391620 : ms.pending[ms.n].base = lo;
2518 : 1391620 : ms.pending[ms.n].len = n;
2519 : 1391620 : ++ms.n;
2520 : : /* Advance to find next run. */
2521 : 1391620 : sortslice_advance(&lo, n);
2522 : 1391620 : nremaining -= n;
2523 [ + + ]: 1391620 : } while (nremaining);
2524 : :
2525 [ - + ]: 1338308 : if (merge_force_collapse(&ms) < 0)
2526 : 0 : goto fail;
2527 : : assert(ms.n == 1);
2528 : : assert(keys == NULL
2529 : : ? ms.pending[0].base.keys == saved_ob_item
2530 : : : ms.pending[0].base.keys == &keys[0]);
2531 : : assert(ms.pending[0].len == saved_ob_size);
2532 : 1338308 : lo = ms.pending[0].base;
2533 : :
2534 : 1996516 : succeed:
2535 : 1996516 : result = Py_None;
2536 : 1996552 : fail:
2537 [ + + ]: 1996552 : if (keys != NULL) {
2538 [ + + ]: 928321 : for (i = 0; i < saved_ob_size; i++)
2539 : 626060 : Py_DECREF(keys[i]);
2540 [ + + ]: 302261 : if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
2541 : 215 : PyMem_Free(keys);
2542 : : }
2543 : :
2544 [ + + + - ]: 1996552 : 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 [ + + + + ]: 1996552 : if (reverse && saved_ob_size > 1)
2553 : 4552 : reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
2554 : :
2555 : 1996552 : merge_freemem(&ms);
2556 : :
2557 : 1996584 : keyfunc_fail:
2558 : 1996584 : final_ob_item = self->ob_item;
2559 : 1996584 : i = Py_SIZE(self);
2560 : 1996584 : Py_SET_SIZE(self, saved_ob_size);
2561 : 1996584 : self->ob_item = saved_ob_item;
2562 : 1996584 : self->allocated = saved_allocated;
2563 [ + + ]: 1996584 : 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 [ + + ]: 148 : while (--i >= 0) {
2567 : 122 : Py_XDECREF(final_ob_item[i]);
2568 : : }
2569 : 26 : PyMem_Free(final_ob_item);
2570 : : }
2571 : 1996584 : Py_XINCREF(result);
2572 : 1996584 : return result;
2573 : : }
2574 : : #undef IFLT
2575 : : #undef ISLT
2576 : :
2577 : : int
2578 : 1133796 : PyList_Sort(PyObject *v)
2579 : : {
2580 [ + - - + ]: 1133796 : if (v == NULL || !PyList_Check(v)) {
2581 : 0 : PyErr_BadInternalCall();
2582 : 0 : return -1;
2583 : : }
2584 : 1133796 : v = list_sort_impl((PyListObject *)v, NULL, 0);
2585 [ + + ]: 1133796 : if (v == NULL)
2586 : 1 : return -1;
2587 : 1133795 : Py_DECREF(v);
2588 : 1133795 : 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 : 77667 : list_reverse_impl(PyListObject *self)
2599 : : /*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
2600 : : {
2601 [ + + ]: 77667 : if (Py_SIZE(self) > 1)
2602 : 40044 : reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2603 : 77667 : Py_RETURN_NONE;
2604 : : }
2605 : :
2606 : : int
2607 : 5125 : PyList_Reverse(PyObject *v)
2608 : : {
2609 : 5125 : PyListObject *self = (PyListObject *)v;
2610 : :
2611 [ + - - + ]: 5125 : if (v == NULL || !PyList_Check(v)) {
2612 : 0 : PyErr_BadInternalCall();
2613 : 0 : return -1;
2614 : : }
2615 [ + + ]: 5125 : if (Py_SIZE(self) > 1)
2616 : 4139 : reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2617 : 5125 : return 0;
2618 : : }
2619 : :
2620 : : PyObject *
2621 : 2943794 : PyList_AsTuple(PyObject *v)
2622 : : {
2623 [ + - - + ]: 2943794 : if (v == NULL || !PyList_Check(v)) {
2624 : 0 : PyErr_BadInternalCall();
2625 : 0 : return NULL;
2626 : : }
2627 : 2943794 : 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 : 104259 : 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 [ + + ]: 104259 : if (start < 0) {
2651 : 33956 : start += Py_SIZE(self);
2652 [ + + ]: 33956 : if (start < 0)
2653 : 18866 : start = 0;
2654 : : }
2655 [ + + ]: 104259 : if (stop < 0) {
2656 : 33934 : stop += Py_SIZE(self);
2657 [ + + ]: 33934 : if (stop < 0)
2658 : 18866 : stop = 0;
2659 : : }
2660 [ + + + + ]: 717940 : for (i = start; i < stop && i < Py_SIZE(self); i++) {
2661 : 667211 : PyObject *obj = self->ob_item[i];
2662 : 667211 : Py_INCREF(obj);
2663 : 667211 : int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2664 : 667211 : Py_DECREF(obj);
2665 [ + + ]: 667211 : if (cmp > 0)
2666 : 53528 : return PyLong_FromSsize_t(i);
2667 [ + + ]: 613683 : else if (cmp < 0)
2668 : 2 : return NULL;
2669 : : }
2670 : 50729 : PyErr_Format(PyExc_ValueError, "%R is not in list", value);
2671 : 50729 : 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 [ + + ]: 249786 : for (i = 0; i < Py_SIZE(self); i++) {
2691 : 243129 : PyObject *obj = self->ob_item[i];
2692 [ + + ]: 243129 : if (obj == value) {
2693 : 34797 : count++;
2694 : 34797 : continue;
2695 : : }
2696 : 208332 : Py_INCREF(obj);
2697 : 208332 : int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2698 : 208332 : Py_DECREF(obj);
2699 [ + + ]: 208332 : if (cmp > 0)
2700 : 97 : count++;
2701 [ + + ]: 208235 : 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 : 112439 : list_remove(PyListObject *self, PyObject *value)
2720 : : /*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
2721 : : {
2722 : : Py_ssize_t i;
2723 : :
2724 [ + + ]: 355208 : for (i = 0; i < Py_SIZE(self); i++) {
2725 : 341340 : PyObject *obj = self->ob_item[i];
2726 : 341340 : Py_INCREF(obj);
2727 : 341340 : int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
2728 : 341340 : Py_DECREF(obj);
2729 [ + + ]: 341340 : if (cmp > 0) {
2730 [ + - ]: 98567 : if (list_ass_slice(self, i, i+1,
2731 : : (PyObject *)NULL) == 0)
2732 : 98567 : Py_RETURN_NONE;
2733 : 0 : return NULL;
2734 : : }
2735 [ + + ]: 242773 : else if (cmp < 0)
2736 : 4 : return NULL;
2737 : : }
2738 : 13868 : PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
2739 : 13868 : return NULL;
2740 : : }
2741 : :
2742 : : static int
2743 : 95858715 : list_traverse(PyListObject *o, visitproc visit, void *arg)
2744 : : {
2745 : : Py_ssize_t i;
2746 : :
2747 [ + + ]: 638276807 : for (i = Py_SIZE(o); --i >= 0; )
2748 [ + + + + ]: 542418249 : Py_VISIT(o->ob_item[i]);
2749 : 95858558 : return 0;
2750 : : }
2751 : :
2752 : : static PyObject *
2753 : 2836838 : list_richcompare(PyObject *v, PyObject *w, int op)
2754 : : {
2755 : : PyListObject *vl, *wl;
2756 : : Py_ssize_t i;
2757 : :
2758 [ + - + + ]: 2836838 : if (!PyList_Check(v) || !PyList_Check(w))
2759 : 303713 : Py_RETURN_NOTIMPLEMENTED;
2760 : :
2761 : 2533125 : vl = (PyListObject *)v;
2762 : 2533125 : wl = (PyListObject *)w;
2763 : :
2764 [ + + + + : 2533125 : if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
+ + ]
2765 : : /* Shortcut: if the lengths differ, the lists differ */
2766 [ + + ]: 411566 : if (op == Py_EQ)
2767 : 405539 : Py_RETURN_FALSE;
2768 : : else
2769 : 6027 : Py_RETURN_TRUE;
2770 : : }
2771 : :
2772 : : /* Search for the first index where items are different */
2773 [ + + + + ]: 15031124 : for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
2774 : 14067784 : PyObject *vitem = vl->ob_item[i];
2775 : 14067784 : PyObject *witem = wl->ob_item[i];
2776 [ + + ]: 14067784 : if (vitem == witem) {
2777 : 3526443 : continue;
2778 : : }
2779 : :
2780 : 10541341 : Py_INCREF(vitem);
2781 : 10541341 : Py_INCREF(witem);
2782 : 10541341 : int k = PyObject_RichCompareBool(vitem, witem, Py_EQ);
2783 : 10541341 : Py_DECREF(vitem);
2784 : 10541341 : Py_DECREF(witem);
2785 [ + + ]: 10541341 : if (k < 0)
2786 : 11269 : return NULL;
2787 [ + + ]: 10530072 : if (!k)
2788 : 1146950 : break;
2789 : : }
2790 : :
2791 [ + + + + ]: 2110290 : if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
2792 : : /* No more items to compare -- compare sizes */
2793 [ + + + + : 963342 : Py_RETURN_RICHCOMPARE(Py_SIZE(vl), Py_SIZE(wl), op);
+ + - + +
- + + + +
+ + - +
+ ]
2794 : : }
2795 : :
2796 : : /* We have an item that differs -- shortcuts for EQ/NE */
2797 [ + + ]: 1146948 : if (op == Py_EQ) {
2798 : 1028557 : Py_RETURN_FALSE;
2799 : : }
2800 [ + + ]: 118391 : if (op == Py_NE) {
2801 : 1955 : Py_RETURN_TRUE;
2802 : : }
2803 : :
2804 : : /* Compare the final item again using the proper operator */
2805 : 116436 : 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 : 5714618 : 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 : : assert(0 <= Py_SIZE(self));
2826 : : assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
2827 : : assert(self->ob_item != NULL ||
2828 : : self->allocated == 0 || self->allocated == -1);
2829 : :
2830 : : /* Empty previous contents */
2831 [ + + ]: 5714618 : if (self->ob_item != NULL) {
2832 : 2 : (void)_list_clear(self);
2833 : : }
2834 [ + + ]: 5714618 : if (iterable != NULL) {
2835 : 5616294 : PyObject *rv = list_extend(self, iterable);
2836 [ + + ]: 5616293 : if (rv == NULL)
2837 : 377 : return -1;
2838 : 5615916 : Py_DECREF(rv);
2839 : : }
2840 : 5714240 : return 0;
2841 : : }
2842 : :
2843 : : static PyObject *
2844 : 1590582 : list_vectorcall(PyObject *type, PyObject * const*args,
2845 : : size_t nargsf, PyObject *kwnames)
2846 : : {
2847 [ + + + - ]: 1590582 : if (!_PyArg_NoKwnames("list", kwnames)) {
2848 : 4 : return NULL;
2849 : : }
2850 : 1590578 : Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
2851 [ + - - + : 1590578 : if (!_PyArg_CheckPositional("list", nargs, 0, 1)) {
- - ]
2852 : 0 : return NULL;
2853 : : }
2854 : :
2855 : 1590578 : PyObject *list = PyType_GenericAlloc(_PyType_CAST(type), 0);
2856 [ - + ]: 1590578 : if (list == NULL) {
2857 : 0 : return NULL;
2858 : : }
2859 [ + + ]: 1590578 : if (nargs) {
2860 [ + + ]: 1416431 : if (list___init___impl((PyListObject *)list, args[0])) {
2861 : 377 : Py_DECREF(list);
2862 : 377 : return NULL;
2863 : : }
2864 : : }
2865 : 1590200 : 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 : 14937641 : list_subscript(PyListObject* self, PyObject* item)
2922 : : {
2923 [ + + ]: 14937641 : if (_PyIndex_Check(item)) {
2924 : : Py_ssize_t i;
2925 : 10836282 : i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2926 [ + + + + ]: 10836282 : if (i == -1 && PyErr_Occurred())
2927 : 7 : return NULL;
2928 [ + + ]: 10836275 : if (i < 0)
2929 : 9443039 : i += PyList_GET_SIZE(self);
2930 : 10836275 : return list_item(self, i);
2931 : : }
2932 [ + + ]: 4101359 : 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 [ + + ]: 4101333 : if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2940 : 11 : return NULL;
2941 : : }
2942 : 4101322 : slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2943 : : step);
2944 : :
2945 [ + + ]: 4101322 : if (slicelength <= 0) {
2946 : 1825621 : return PyList_New(0);
2947 : : }
2948 [ + + ]: 2275701 : else if (step == 1) {
2949 : 2238508 : return list_slice(self, start, stop);
2950 : : }
2951 : : else {
2952 : 37193 : result = list_new_prealloc(slicelength);
2953 [ - + ]: 37193 : if (!result) return NULL;
2954 : :
2955 : 37193 : src = self->ob_item;
2956 : 37193 : dest = ((PyListObject *)result)->ob_item;
2957 [ + + ]: 215469 : for (cur = start, i = 0; i < slicelength;
2958 : 178276 : cur += (size_t)step, i++) {
2959 : 178276 : it = src[cur];
2960 : 178276 : Py_INCREF(it);
2961 : 178276 : dest[i] = it;
2962 : : }
2963 : 37193 : Py_SET_SIZE(result, slicelength);
2964 : 37193 : 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 : 2485576 : list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2977 : : {
2978 [ + + ]: 2485576 : if (_PyIndex_Check(item)) {
2979 : 2207517 : Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2980 [ + + - + ]: 2207517 : if (i == -1 && PyErr_Occurred())
2981 : 0 : return -1;
2982 [ + + ]: 2207517 : if (i < 0)
2983 : 1936562 : i += PyList_GET_SIZE(self);
2984 : 2207517 : return list_ass_item(self, i, value);
2985 : : }
2986 [ + + ]: 278059 : else if (PySlice_Check(item)) {
2987 : : Py_ssize_t start, stop, step, slicelength;
2988 : :
2989 [ + + ]: 278051 : if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
2990 : 2 : return -1;
2991 : : }
2992 : 278049 : slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
2993 : : step);
2994 : :
2995 [ + + ]: 278049 : if (step == 1)
2996 : 248493 : 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 [ + + + + ]: 29556 : if ((step < 0 && start < stop) ||
3001 [ + + + + ]: 25132 : (step > 0 && start > stop))
3002 : 9098 : stop = start;
3003 : :
3004 [ + + ]: 29556 : 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 : : 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 [ + + ]: 15662 : if (self == (PyListObject*)value) {
3075 : 1 : seq = list_slice((PyListObject*)value, 0,
3076 : : PyList_GET_SIZE(value));
3077 : : }
3078 : : else {
3079 : 15661 : seq = PySequence_Fast(value,
3080 : : "must assign iterable "
3081 : : "to extended slice");
3082 : : }
3083 [ - + ]: 15662 : if (!seq)
3084 : 0 : return -1;
3085 : :
3086 [ + + + + ]: 15662 : if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
3087 [ + - ]: 1252 : PyErr_Format(PyExc_ValueError,
3088 : : "attempt to assign sequence of "
3089 : : "size %zd to extended slice of "
3090 : : "size %zd",
3091 : 1252 : PySequence_Fast_GET_SIZE(seq),
3092 : : slicelength);
3093 : 626 : Py_DECREF(seq);
3094 : 626 : return -1;
3095 : : }
3096 : :
3097 [ + + ]: 15036 : if (!slicelength) {
3098 : 8275 : Py_DECREF(seq);
3099 : 8275 : return 0;
3100 : : }
3101 : :
3102 : : garbage = (PyObject**)
3103 : 6761 : PyMem_Malloc(slicelength*sizeof(PyObject*));
3104 [ - + ]: 6761 : if (!garbage) {
3105 : 0 : Py_DECREF(seq);
3106 : : PyErr_NoMemory();
3107 : 0 : return -1;
3108 : : }
3109 : :
3110 : 6761 : selfitems = self->ob_item;
3111 [ + + ]: 6761 : seqitems = PySequence_Fast_ITEMS(seq);
3112 [ + + ]: 53733 : for (cur = start, i = 0; i < slicelength;
3113 : 46972 : cur += (size_t)step, i++) {
3114 : 46972 : garbage[i] = selfitems[cur];
3115 : 46972 : ins = seqitems[i];
3116 : 46972 : Py_INCREF(ins);
3117 : 46972 : selfitems[cur] = ins;
3118 : : }
3119 : :
3120 [ + + ]: 53733 : for (i = 0; i < slicelength; i++) {
3121 : 46972 : Py_DECREF(garbage[i]);
3122 : : }
3123 : :
3124 : 6761 : PyMem_Free(garbage);
3125 : 6761 : Py_DECREF(seq);
3126 : :
3127 : 6761 : 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 : 18697173 : list_iter(PyObject *seq)
3246 : : {
3247 : : _PyListIterObject *it;
3248 : :
3249 [ - + ]: 18697173 : if (!PyList_Check(seq)) {
3250 : 0 : PyErr_BadInternalCall();
3251 : 0 : return NULL;
3252 : : }
3253 : 18697173 : it = PyObject_GC_New(_PyListIterObject, &PyListIter_Type);
3254 [ - + ]: 18697173 : if (it == NULL)
3255 : 0 : return NULL;
3256 : 18697173 : it->it_index = 0;
3257 : 18697173 : Py_INCREF(seq);
3258 : 18697173 : it->it_seq = (PyListObject *)seq;
3259 : 18697173 : _PyObject_GC_TRACK(it);
3260 : 18697173 : return (PyObject *)it;
3261 : : }
3262 : :
3263 : : static void
3264 : 18697164 : listiter_dealloc(_PyListIterObject *it)
3265 : : {
3266 : 18697164 : _PyObject_GC_UNTRACK(it);
3267 : 18697164 : Py_XDECREF(it->it_seq);
3268 : 18697164 : PyObject_GC_Del(it);
3269 : 18697164 : }
3270 : :
3271 : : static int
3272 : 202356 : listiter_traverse(_PyListIterObject *it, visitproc visit, void *arg)
3273 : : {
3274 [ + + - + ]: 202356 : Py_VISIT(it->it_seq);
3275 : 202356 : return 0;
3276 : : }
3277 : :
3278 : : static PyObject *
3279 : 34275673 : listiter_next(_PyListIterObject *it)
3280 : : {
3281 : : PyListObject *seq;
3282 : : PyObject *item;
3283 : :
3284 : : assert(it != NULL);
3285 : 34275673 : seq = it->it_seq;
3286 [ + + ]: 34275673 : if (seq == NULL)
3287 : 514 : return NULL;
3288 : : assert(PyList_Check(seq));
3289 : :
3290 [ + + ]: 34275159 : if (it->it_index < PyList_GET_SIZE(seq)) {
3291 : 26510152 : item = PyList_GET_ITEM(seq, it->it_index);
3292 : 26510152 : ++it->it_index;
3293 : 26510152 : Py_INCREF(item);
3294 : 26510152 : return item;
3295 : : }
3296 : :
3297 : 7765007 : it->it_seq = NULL;
3298 : 7765007 : Py_DECREF(seq);
3299 : 7765007 : return NULL;
3300 : : }
3301 : :
3302 : : static PyObject *
3303 : 8312 : listiter_len(_PyListIterObject *it, PyObject *Py_UNUSED(ignored))
3304 : : {
3305 : : Py_ssize_t len;
3306 [ + + ]: 8312 : if (it->it_seq) {
3307 : 8307 : len = PyList_GET_SIZE(it->it_seq) - it->it_index;
3308 [ + + ]: 8307 : if (len >= 0)
3309 : 8305 : 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 : 96125 : list___reversed___impl(PyListObject *self)
3399 : : /*[clinic end generated code: output=b166f073208c888c input=eadb6e17f8a6a280]*/
3400 : : {
3401 : : listreviterobject *it;
3402 : :
3403 : 96125 : it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
3404 [ - + ]: 96125 : if (it == NULL)
3405 : 0 : return NULL;
3406 : : assert(PyList_Check(self));
3407 : 96125 : it->it_index = PyList_GET_SIZE(self) - 1;
3408 : 96125 : Py_INCREF(self);
3409 : 96125 : it->it_seq = self;
3410 : 96125 : PyObject_GC_Track(it);
3411 : 96125 : return (PyObject *)it;
3412 : : }
3413 : :
3414 : : static void
3415 : 96124 : listreviter_dealloc(listreviterobject *it)
3416 : : {
3417 : 96124 : PyObject_GC_UnTrack(it);
3418 : 96124 : Py_XDECREF(it->it_seq);
3419 : 96124 : PyObject_GC_Del(it);
3420 : 96124 : }
3421 : :
3422 : : static int
3423 : 120 : listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
3424 : : {
3425 [ + + - + ]: 120 : Py_VISIT(it->it_seq);
3426 : 120 : return 0;
3427 : : }
3428 : :
3429 : : static PyObject *
3430 : 377773 : listreviter_next(listreviterobject *it)
3431 : : {
3432 : : PyObject *item;
3433 : : Py_ssize_t index;
3434 : : PyListObject *seq;
3435 : :
3436 : : assert(it != NULL);
3437 : 377773 : seq = it->it_seq;
3438 [ + + ]: 377773 : if (seq == NULL) {
3439 : 2 : return NULL;
3440 : : }
3441 : : assert(PyList_Check(seq));
3442 : :
3443 : 377771 : index = it->it_index;
3444 [ + + + + ]: 377771 : if (index>=0 && index < PyList_GET_SIZE(seq)) {
3445 : 295271 : item = PyList_GET_ITEM(seq, index);
3446 : 295271 : it->it_index--;
3447 : 295271 : Py_INCREF(item);
3448 : 295271 : return item;
3449 : : }
3450 : 82500 : it->it_index = -1;
3451 : 82500 : it->it_seq = NULL;
3452 : 82500 : Py_DECREF(seq);
3453 : 82500 : return NULL;
3454 : : }
3455 : :
3456 : : static PyObject *
3457 : 5390 : listreviter_len(listreviterobject *it, PyObject *Py_UNUSED(ignored))
3458 : : {
3459 : 5390 : Py_ssize_t len = it->it_index + 1;
3460 [ + + + + ]: 5390 : if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
3461 : 4 : len = 0;
3462 : 5390 : 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 : : }
|
