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