Issue #1670765: Prevent email.generator.Generator from re-wrapping
[python.git] / Objects / listobject.c
blobdea51ed768a6385f259f45c999098c0ab061fcb2
1 /* List object implementation */
3 #include "Python.h"
5 #ifdef STDC_HEADERS
6 #include <stddef.h>
7 #else
8 #include <sys/types.h> /* For size_t */
9 #endif
11 /* Ensure ob_item has room for at least newsize elements, and set
12 * ob_size to newsize. If newsize > ob_size on entry, the content
13 * of the new slots at exit is undefined heap trash; it's the caller's
14 * responsiblity to overwrite them with sane values.
15 * The number of allocated elements may grow, shrink, or stay the same.
16 * Failure is impossible if newsize <= self.allocated on entry, although
17 * that partly relies on an assumption that the system realloc() never
18 * fails when passed a number of bytes <= the number of bytes last
19 * allocated (the C standard doesn't guarantee this, but it's hard to
20 * imagine a realloc implementation where it wouldn't be true).
21 * Note that self->ob_item may change, and even if newsize is less
22 * than ob_size on entry.
24 static int
25 list_resize(PyListObject *self, Py_ssize_t newsize)
27 PyObject **items;
28 size_t new_allocated;
29 Py_ssize_t allocated = self->allocated;
31 /* Bypass realloc() when a previous overallocation is large enough
32 to accommodate the newsize. If the newsize falls lower than half
33 the allocated size, then proceed with the realloc() to shrink the list.
35 if (allocated >= newsize && newsize >= (allocated >> 1)) {
36 assert(self->ob_item != NULL || newsize == 0);
37 Py_SIZE(self) = newsize;
38 return 0;
41 /* This over-allocates proportional to the list size, making room
42 * for additional growth. The over-allocation is mild, but is
43 * enough to give linear-time amortized behavior over a long
44 * sequence of appends() in the presence of a poorly-performing
45 * system realloc().
46 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
48 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
50 /* check for integer overflow */
51 if (new_allocated > PY_SIZE_MAX - newsize) {
52 PyErr_NoMemory();
53 return -1;
54 } else {
55 new_allocated += newsize;
58 if (newsize == 0)
59 new_allocated = 0;
60 items = self->ob_item;
61 if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))
62 PyMem_RESIZE(items, PyObject *, new_allocated);
63 else
64 items = NULL;
65 if (items == NULL) {
66 PyErr_NoMemory();
67 return -1;
69 self->ob_item = items;
70 Py_SIZE(self) = newsize;
71 self->allocated = new_allocated;
72 return 0;
75 /* Debug statistic to compare allocations with reuse through the free list */
76 #undef SHOW_ALLOC_COUNT
77 #ifdef SHOW_ALLOC_COUNT
78 static size_t count_alloc = 0;
79 static size_t count_reuse = 0;
81 static void
82 show_alloc(void)
84 fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",
85 count_alloc);
86 fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T
87 "d\n", count_reuse);
88 fprintf(stderr, "%.2f%% reuse rate\n\n",
89 (100.0*count_reuse/(count_alloc+count_reuse)));
91 #endif
93 /* Empty list reuse scheme to save calls to malloc and free */
94 #ifndef PyList_MAXFREELIST
95 #define PyList_MAXFREELIST 80
96 #endif
97 static PyListObject *free_list[PyList_MAXFREELIST];
98 static int numfree = 0;
100 void
101 PyList_Fini(void)
103 PyListObject *op;
105 while (numfree) {
106 op = free_list[--numfree];
107 assert(PyList_CheckExact(op));
108 PyObject_GC_Del(op);
112 PyObject *
113 PyList_New(Py_ssize_t size)
115 PyListObject *op;
116 size_t nbytes;
117 #ifdef SHOW_ALLOC_COUNT
118 static int initialized = 0;
119 if (!initialized) {
120 Py_AtExit(show_alloc);
121 initialized = 1;
123 #endif
125 if (size < 0) {
126 PyErr_BadInternalCall();
127 return NULL;
129 nbytes = size * sizeof(PyObject *);
130 /* Check for overflow without an actual overflow,
131 * which can cause compiler to optimise out */
132 if (size > PY_SIZE_MAX / sizeof(PyObject *))
133 return PyErr_NoMemory();
134 if (numfree) {
135 numfree--;
136 op = free_list[numfree];
137 _Py_NewReference((PyObject *)op);
138 #ifdef SHOW_ALLOC_COUNT
139 count_reuse++;
140 #endif
141 } else {
142 op = PyObject_GC_New(PyListObject, &PyList_Type);
143 if (op == NULL)
144 return NULL;
145 #ifdef SHOW_ALLOC_COUNT
146 count_alloc++;
147 #endif
149 if (size <= 0)
150 op->ob_item = NULL;
151 else {
152 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
153 if (op->ob_item == NULL) {
154 Py_DECREF(op);
155 return PyErr_NoMemory();
157 memset(op->ob_item, 0, nbytes);
159 Py_SIZE(op) = size;
160 op->allocated = size;
161 _PyObject_GC_TRACK(op);
162 return (PyObject *) op;
165 Py_ssize_t
166 PyList_Size(PyObject *op)
168 if (!PyList_Check(op)) {
169 PyErr_BadInternalCall();
170 return -1;
172 else
173 return Py_SIZE(op);
176 static PyObject *indexerr = NULL;
178 PyObject *
179 PyList_GetItem(PyObject *op, Py_ssize_t i)
181 if (!PyList_Check(op)) {
182 PyErr_BadInternalCall();
183 return NULL;
185 if (i < 0 || i >= Py_SIZE(op)) {
186 if (indexerr == NULL) {
187 indexerr = PyString_FromString(
188 "list index out of range");
189 if (indexerr == NULL)
190 return NULL;
192 PyErr_SetObject(PyExc_IndexError, indexerr);
193 return NULL;
195 return ((PyListObject *)op) -> ob_item[i];
199 PyList_SetItem(register PyObject *op, register Py_ssize_t i,
200 register PyObject *newitem)
202 register PyObject *olditem;
203 register PyObject **p;
204 if (!PyList_Check(op)) {
205 Py_XDECREF(newitem);
206 PyErr_BadInternalCall();
207 return -1;
209 if (i < 0 || i >= Py_SIZE(op)) {
210 Py_XDECREF(newitem);
211 PyErr_SetString(PyExc_IndexError,
212 "list assignment index out of range");
213 return -1;
215 p = ((PyListObject *)op) -> ob_item + i;
216 olditem = *p;
217 *p = newitem;
218 Py_XDECREF(olditem);
219 return 0;
222 static int
223 ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
225 Py_ssize_t i, n = Py_SIZE(self);
226 PyObject **items;
227 if (v == NULL) {
228 PyErr_BadInternalCall();
229 return -1;
231 if (n == PY_SSIZE_T_MAX) {
232 PyErr_SetString(PyExc_OverflowError,
233 "cannot add more objects to list");
234 return -1;
237 if (list_resize(self, n+1) == -1)
238 return -1;
240 if (where < 0) {
241 where += n;
242 if (where < 0)
243 where = 0;
245 if (where > n)
246 where = n;
247 items = self->ob_item;
248 for (i = n; --i >= where; )
249 items[i+1] = items[i];
250 Py_INCREF(v);
251 items[where] = v;
252 return 0;
256 PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
258 if (!PyList_Check(op)) {
259 PyErr_BadInternalCall();
260 return -1;
262 return ins1((PyListObject *)op, where, newitem);
265 static int
266 app1(PyListObject *self, PyObject *v)
268 Py_ssize_t n = PyList_GET_SIZE(self);
270 assert (v != NULL);
271 if (n == PY_SSIZE_T_MAX) {
272 PyErr_SetString(PyExc_OverflowError,
273 "cannot add more objects to list");
274 return -1;
277 if (list_resize(self, n+1) == -1)
278 return -1;
280 Py_INCREF(v);
281 PyList_SET_ITEM(self, n, v);
282 return 0;
286 PyList_Append(PyObject *op, PyObject *newitem)
288 if (PyList_Check(op) && (newitem != NULL))
289 return app1((PyListObject *)op, newitem);
290 PyErr_BadInternalCall();
291 return -1;
294 /* Methods */
296 static void
297 list_dealloc(PyListObject *op)
299 Py_ssize_t i;
300 PyObject_GC_UnTrack(op);
301 Py_TRASHCAN_SAFE_BEGIN(op)
302 if (op->ob_item != NULL) {
303 /* Do it backwards, for Christian Tismer.
304 There's a simple test case where somehow this reduces
305 thrashing when a *very* large list is created and
306 immediately deleted. */
307 i = Py_SIZE(op);
308 while (--i >= 0) {
309 Py_XDECREF(op->ob_item[i]);
311 PyMem_FREE(op->ob_item);
313 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
314 free_list[numfree++] = op;
315 else
316 Py_TYPE(op)->tp_free((PyObject *)op);
317 Py_TRASHCAN_SAFE_END(op)
320 static int
321 list_print(PyListObject *op, FILE *fp, int flags)
323 int rc;
324 Py_ssize_t i;
325 PyObject *item;
327 rc = Py_ReprEnter((PyObject*)op);
328 if (rc != 0) {
329 if (rc < 0)
330 return rc;
331 Py_BEGIN_ALLOW_THREADS
332 fprintf(fp, "[...]");
333 Py_END_ALLOW_THREADS
334 return 0;
336 Py_BEGIN_ALLOW_THREADS
337 fprintf(fp, "[");
338 Py_END_ALLOW_THREADS
339 for (i = 0; i < Py_SIZE(op); i++) {
340 item = op->ob_item[i];
341 Py_INCREF(item);
342 if (i > 0) {
343 Py_BEGIN_ALLOW_THREADS
344 fprintf(fp, ", ");
345 Py_END_ALLOW_THREADS
347 if (PyObject_Print(item, fp, 0) != 0) {
348 Py_DECREF(item);
349 Py_ReprLeave((PyObject *)op);
350 return -1;
352 Py_DECREF(item);
354 Py_BEGIN_ALLOW_THREADS
355 fprintf(fp, "]");
356 Py_END_ALLOW_THREADS
357 Py_ReprLeave((PyObject *)op);
358 return 0;
361 static PyObject *
362 list_repr(PyListObject *v)
364 Py_ssize_t i;
365 PyObject *s, *temp;
366 PyObject *pieces = NULL, *result = NULL;
368 i = Py_ReprEnter((PyObject*)v);
369 if (i != 0) {
370 return i > 0 ? PyString_FromString("[...]") : NULL;
373 if (Py_SIZE(v) == 0) {
374 result = PyString_FromString("[]");
375 goto Done;
378 pieces = PyList_New(0);
379 if (pieces == NULL)
380 goto Done;
382 /* Do repr() on each element. Note that this may mutate the list,
383 so must refetch the list size on each iteration. */
384 for (i = 0; i < Py_SIZE(v); ++i) {
385 int status;
386 if (Py_EnterRecursiveCall(" while getting the repr of a list"))
387 goto Done;
388 s = PyObject_Repr(v->ob_item[i]);
389 Py_LeaveRecursiveCall();
390 if (s == NULL)
391 goto Done;
392 status = PyList_Append(pieces, s);
393 Py_DECREF(s); /* append created a new ref */
394 if (status < 0)
395 goto Done;
398 /* Add "[]" decorations to the first and last items. */
399 assert(PyList_GET_SIZE(pieces) > 0);
400 s = PyString_FromString("[");
401 if (s == NULL)
402 goto Done;
403 temp = PyList_GET_ITEM(pieces, 0);
404 PyString_ConcatAndDel(&s, temp);
405 PyList_SET_ITEM(pieces, 0, s);
406 if (s == NULL)
407 goto Done;
409 s = PyString_FromString("]");
410 if (s == NULL)
411 goto Done;
412 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
413 PyString_ConcatAndDel(&temp, s);
414 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
415 if (temp == NULL)
416 goto Done;
418 /* Paste them all together with ", " between. */
419 s = PyString_FromString(", ");
420 if (s == NULL)
421 goto Done;
422 result = _PyString_Join(s, pieces);
423 Py_DECREF(s);
425 Done:
426 Py_XDECREF(pieces);
427 Py_ReprLeave((PyObject *)v);
428 return result;
431 static Py_ssize_t
432 list_length(PyListObject *a)
434 return Py_SIZE(a);
437 static int
438 list_contains(PyListObject *a, PyObject *el)
440 Py_ssize_t i;
441 int cmp;
443 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
444 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
445 Py_EQ);
446 return cmp;
449 static PyObject *
450 list_item(PyListObject *a, Py_ssize_t i)
452 if (i < 0 || i >= Py_SIZE(a)) {
453 if (indexerr == NULL) {
454 indexerr = PyString_FromString(
455 "list index out of range");
456 if (indexerr == NULL)
457 return NULL;
459 PyErr_SetObject(PyExc_IndexError, indexerr);
460 return NULL;
462 Py_INCREF(a->ob_item[i]);
463 return a->ob_item[i];
466 static PyObject *
467 list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
469 PyListObject *np;
470 PyObject **src, **dest;
471 Py_ssize_t i, len;
472 if (ilow < 0)
473 ilow = 0;
474 else if (ilow > Py_SIZE(a))
475 ilow = Py_SIZE(a);
476 if (ihigh < ilow)
477 ihigh = ilow;
478 else if (ihigh > Py_SIZE(a))
479 ihigh = Py_SIZE(a);
480 len = ihigh - ilow;
481 np = (PyListObject *) PyList_New(len);
482 if (np == NULL)
483 return NULL;
485 src = a->ob_item + ilow;
486 dest = np->ob_item;
487 for (i = 0; i < len; i++) {
488 PyObject *v = src[i];
489 Py_INCREF(v);
490 dest[i] = v;
492 return (PyObject *)np;
495 PyObject *
496 PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
498 if (!PyList_Check(a)) {
499 PyErr_BadInternalCall();
500 return NULL;
502 return list_slice((PyListObject *)a, ilow, ihigh);
505 static PyObject *
506 list_concat(PyListObject *a, PyObject *bb)
508 Py_ssize_t size;
509 Py_ssize_t i;
510 PyObject **src, **dest;
511 PyListObject *np;
512 if (!PyList_Check(bb)) {
513 PyErr_Format(PyExc_TypeError,
514 "can only concatenate list (not \"%.200s\") to list",
515 bb->ob_type->tp_name);
516 return NULL;
518 #define b ((PyListObject *)bb)
519 size = Py_SIZE(a) + Py_SIZE(b);
520 if (size < 0)
521 return PyErr_NoMemory();
522 np = (PyListObject *) PyList_New(size);
523 if (np == NULL) {
524 return NULL;
526 src = a->ob_item;
527 dest = np->ob_item;
528 for (i = 0; i < Py_SIZE(a); i++) {
529 PyObject *v = src[i];
530 Py_INCREF(v);
531 dest[i] = v;
533 src = b->ob_item;
534 dest = np->ob_item + Py_SIZE(a);
535 for (i = 0; i < Py_SIZE(b); i++) {
536 PyObject *v = src[i];
537 Py_INCREF(v);
538 dest[i] = v;
540 return (PyObject *)np;
541 #undef b
544 static PyObject *
545 list_repeat(PyListObject *a, Py_ssize_t n)
547 Py_ssize_t i, j;
548 Py_ssize_t size;
549 PyListObject *np;
550 PyObject **p, **items;
551 PyObject *elem;
552 if (n < 0)
553 n = 0;
554 size = Py_SIZE(a) * n;
555 if (n && size/n != Py_SIZE(a))
556 return PyErr_NoMemory();
557 if (size == 0)
558 return PyList_New(0);
559 np = (PyListObject *) PyList_New(size);
560 if (np == NULL)
561 return NULL;
563 items = np->ob_item;
564 if (Py_SIZE(a) == 1) {
565 elem = a->ob_item[0];
566 for (i = 0; i < n; i++) {
567 items[i] = elem;
568 Py_INCREF(elem);
570 return (PyObject *) np;
572 p = np->ob_item;
573 items = a->ob_item;
574 for (i = 0; i < n; i++) {
575 for (j = 0; j < Py_SIZE(a); j++) {
576 *p = items[j];
577 Py_INCREF(*p);
578 p++;
581 return (PyObject *) np;
584 static int
585 list_clear(PyListObject *a)
587 Py_ssize_t i;
588 PyObject **item = a->ob_item;
589 if (item != NULL) {
590 /* Because XDECREF can recursively invoke operations on
591 this list, we make it empty first. */
592 i = Py_SIZE(a);
593 Py_SIZE(a) = 0;
594 a->ob_item = NULL;
595 a->allocated = 0;
596 while (--i >= 0) {
597 Py_XDECREF(item[i]);
599 PyMem_FREE(item);
601 /* Never fails; the return value can be ignored.
602 Note that there is no guarantee that the list is actually empty
603 at this point, because XDECREF may have populated it again! */
604 return 0;
607 /* a[ilow:ihigh] = v if v != NULL.
608 * del a[ilow:ihigh] if v == NULL.
610 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
611 * guaranteed the call cannot fail.
613 static int
614 list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
616 /* Because [X]DECREF can recursively invoke list operations on
617 this list, we must postpone all [X]DECREF activity until
618 after the list is back in its canonical shape. Therefore
619 we must allocate an additional array, 'recycle', into which
620 we temporarily copy the items that are deleted from the
621 list. :-( */
622 PyObject *recycle_on_stack[8];
623 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
624 PyObject **item;
625 PyObject **vitem = NULL;
626 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
627 Py_ssize_t n; /* # of elements in replacement list */
628 Py_ssize_t norig; /* # of elements in list getting replaced */
629 Py_ssize_t d; /* Change in size */
630 Py_ssize_t k;
631 size_t s;
632 int result = -1; /* guilty until proved innocent */
633 #define b ((PyListObject *)v)
634 if (v == NULL)
635 n = 0;
636 else {
637 if (a == b) {
638 /* Special case "a[i:j] = a" -- copy b first */
639 v = list_slice(b, 0, Py_SIZE(b));
640 if (v == NULL)
641 return result;
642 result = list_ass_slice(a, ilow, ihigh, v);
643 Py_DECREF(v);
644 return result;
646 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
647 if(v_as_SF == NULL)
648 goto Error;
649 n = PySequence_Fast_GET_SIZE(v_as_SF);
650 vitem = PySequence_Fast_ITEMS(v_as_SF);
652 if (ilow < 0)
653 ilow = 0;
654 else if (ilow > Py_SIZE(a))
655 ilow = Py_SIZE(a);
657 if (ihigh < ilow)
658 ihigh = ilow;
659 else if (ihigh > Py_SIZE(a))
660 ihigh = Py_SIZE(a);
662 norig = ihigh - ilow;
663 assert(norig >= 0);
664 d = n - norig;
665 if (Py_SIZE(a) + d == 0) {
666 Py_XDECREF(v_as_SF);
667 return list_clear(a);
669 item = a->ob_item;
670 /* recycle the items that we are about to remove */
671 s = norig * sizeof(PyObject *);
672 if (s > sizeof(recycle_on_stack)) {
673 recycle = (PyObject **)PyMem_MALLOC(s);
674 if (recycle == NULL) {
675 PyErr_NoMemory();
676 goto Error;
679 memcpy(recycle, &item[ilow], s);
681 if (d < 0) { /* Delete -d items */
682 memmove(&item[ihigh+d], &item[ihigh],
683 (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
684 list_resize(a, Py_SIZE(a) + d);
685 item = a->ob_item;
687 else if (d > 0) { /* Insert d items */
688 k = Py_SIZE(a);
689 if (list_resize(a, k+d) < 0)
690 goto Error;
691 item = a->ob_item;
692 memmove(&item[ihigh+d], &item[ihigh],
693 (k - ihigh)*sizeof(PyObject *));
695 for (k = 0; k < n; k++, ilow++) {
696 PyObject *w = vitem[k];
697 Py_XINCREF(w);
698 item[ilow] = w;
700 for (k = norig - 1; k >= 0; --k)
701 Py_XDECREF(recycle[k]);
702 result = 0;
703 Error:
704 if (recycle != recycle_on_stack)
705 PyMem_FREE(recycle);
706 Py_XDECREF(v_as_SF);
707 return result;
708 #undef b
712 PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
714 if (!PyList_Check(a)) {
715 PyErr_BadInternalCall();
716 return -1;
718 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
721 static PyObject *
722 list_inplace_repeat(PyListObject *self, Py_ssize_t n)
724 PyObject **items;
725 Py_ssize_t size, i, j, p;
728 size = PyList_GET_SIZE(self);
729 if (size == 0 || n == 1) {
730 Py_INCREF(self);
731 return (PyObject *)self;
734 if (n < 1) {
735 (void)list_clear(self);
736 Py_INCREF(self);
737 return (PyObject *)self;
740 if (size > PY_SSIZE_T_MAX / n) {
741 return PyErr_NoMemory();
744 if (list_resize(self, size*n) == -1)
745 return NULL;
747 p = size;
748 items = self->ob_item;
749 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
750 for (j = 0; j < size; j++) {
751 PyObject *o = items[j];
752 Py_INCREF(o);
753 items[p++] = o;
756 Py_INCREF(self);
757 return (PyObject *)self;
760 static int
761 list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
763 PyObject *old_value;
764 if (i < 0 || i >= Py_SIZE(a)) {
765 PyErr_SetString(PyExc_IndexError,
766 "list assignment index out of range");
767 return -1;
769 if (v == NULL)
770 return list_ass_slice(a, i, i+1, v);
771 Py_INCREF(v);
772 old_value = a->ob_item[i];
773 a->ob_item[i] = v;
774 Py_DECREF(old_value);
775 return 0;
778 static PyObject *
779 listinsert(PyListObject *self, PyObject *args)
781 Py_ssize_t i;
782 PyObject *v;
783 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
784 return NULL;
785 if (ins1(self, i, v) == 0)
786 Py_RETURN_NONE;
787 return NULL;
790 static PyObject *
791 listappend(PyListObject *self, PyObject *v)
793 if (app1(self, v) == 0)
794 Py_RETURN_NONE;
795 return NULL;
798 static PyObject *
799 listextend(PyListObject *self, PyObject *b)
801 PyObject *it; /* iter(v) */
802 Py_ssize_t m; /* size of self */
803 Py_ssize_t n; /* guess for size of b */
804 Py_ssize_t mn; /* m + n */
805 Py_ssize_t i;
806 PyObject *(*iternext)(PyObject *);
808 /* Special cases:
809 1) lists and tuples which can use PySequence_Fast ops
810 2) extending self to self requires making a copy first
812 if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
813 PyObject **src, **dest;
814 b = PySequence_Fast(b, "argument must be iterable");
815 if (!b)
816 return NULL;
817 n = PySequence_Fast_GET_SIZE(b);
818 if (n == 0) {
819 /* short circuit when b is empty */
820 Py_DECREF(b);
821 Py_RETURN_NONE;
823 m = Py_SIZE(self);
824 if (list_resize(self, m + n) == -1) {
825 Py_DECREF(b);
826 return NULL;
828 /* note that we may still have self == b here for the
829 * situation a.extend(a), but the following code works
830 * in that case too. Just make sure to resize self
831 * before calling PySequence_Fast_ITEMS.
833 /* populate the end of self with b's items */
834 src = PySequence_Fast_ITEMS(b);
835 dest = self->ob_item + m;
836 for (i = 0; i < n; i++) {
837 PyObject *o = src[i];
838 Py_INCREF(o);
839 dest[i] = o;
841 Py_DECREF(b);
842 Py_RETURN_NONE;
845 it = PyObject_GetIter(b);
846 if (it == NULL)
847 return NULL;
848 iternext = *it->ob_type->tp_iternext;
850 /* Guess a result list size. */
851 n = _PyObject_LengthHint(b, 8);
852 if (n == -1) {
853 Py_DECREF(it);
854 return NULL;
856 m = Py_SIZE(self);
857 mn = m + n;
858 if (mn >= m) {
859 /* Make room. */
860 if (list_resize(self, mn) == -1)
861 goto error;
862 /* Make the list sane again. */
863 Py_SIZE(self) = m;
865 /* Else m + n overflowed; on the chance that n lied, and there really
866 * is enough room, ignore it. If n was telling the truth, we'll
867 * eventually run out of memory during the loop.
870 /* Run iterator to exhaustion. */
871 for (;;) {
872 PyObject *item = iternext(it);
873 if (item == NULL) {
874 if (PyErr_Occurred()) {
875 if (PyErr_ExceptionMatches(PyExc_StopIteration))
876 PyErr_Clear();
877 else
878 goto error;
880 break;
882 if (Py_SIZE(self) < self->allocated) {
883 /* steals ref */
884 PyList_SET_ITEM(self, Py_SIZE(self), item);
885 ++Py_SIZE(self);
887 else {
888 int status = app1(self, item);
889 Py_DECREF(item); /* append creates a new ref */
890 if (status < 0)
891 goto error;
895 /* Cut back result list if initial guess was too large. */
896 if (Py_SIZE(self) < self->allocated)
897 list_resize(self, Py_SIZE(self)); /* shrinking can't fail */
899 Py_DECREF(it);
900 Py_RETURN_NONE;
902 error:
903 Py_DECREF(it);
904 return NULL;
907 PyObject *
908 _PyList_Extend(PyListObject *self, PyObject *b)
910 return listextend(self, b);
913 static PyObject *
914 list_inplace_concat(PyListObject *self, PyObject *other)
916 PyObject *result;
918 result = listextend(self, other);
919 if (result == NULL)
920 return result;
921 Py_DECREF(result);
922 Py_INCREF(self);
923 return (PyObject *)self;
926 static PyObject *
927 listpop(PyListObject *self, PyObject *args)
929 Py_ssize_t i = -1;
930 PyObject *v;
931 int status;
933 if (!PyArg_ParseTuple(args, "|n:pop", &i))
934 return NULL;
936 if (Py_SIZE(self) == 0) {
937 /* Special-case most common failure cause */
938 PyErr_SetString(PyExc_IndexError, "pop from empty list");
939 return NULL;
941 if (i < 0)
942 i += Py_SIZE(self);
943 if (i < 0 || i >= Py_SIZE(self)) {
944 PyErr_SetString(PyExc_IndexError, "pop index out of range");
945 return NULL;
947 v = self->ob_item[i];
948 if (i == Py_SIZE(self) - 1) {
949 status = list_resize(self, Py_SIZE(self) - 1);
950 assert(status >= 0);
951 return v; /* and v now owns the reference the list had */
953 Py_INCREF(v);
954 status = list_ass_slice(self, i, i+1, (PyObject *)NULL);
955 assert(status >= 0);
956 /* Use status, so that in a release build compilers don't
957 * complain about the unused name.
959 (void) status;
961 return v;
964 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
965 static void
966 reverse_slice(PyObject **lo, PyObject **hi)
968 assert(lo && hi);
970 --hi;
971 while (lo < hi) {
972 PyObject *t = *lo;
973 *lo = *hi;
974 *hi = t;
975 ++lo;
976 --hi;
980 /* Lots of code for an adaptive, stable, natural mergesort. There are many
981 * pieces to this algorithm; read listsort.txt for overviews and details.
984 /* Comparison function. Takes care of calling a user-supplied
985 * comparison function (any callable Python object), which must not be
986 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
987 * with Py_LT if you know it's NULL).
988 * Returns -1 on error, 1 if x < y, 0 if x >= y.
990 static int
991 islt(PyObject *x, PyObject *y, PyObject *compare)
993 PyObject *res;
994 PyObject *args;
995 Py_ssize_t i;
997 assert(compare != NULL);
998 /* Call the user's comparison function and translate the 3-way
999 * result into true or false (or error).
1001 args = PyTuple_New(2);
1002 if (args == NULL)
1003 return -1;
1004 Py_INCREF(x);
1005 Py_INCREF(y);
1006 PyTuple_SET_ITEM(args, 0, x);
1007 PyTuple_SET_ITEM(args, 1, y);
1008 res = PyObject_Call(compare, args, NULL);
1009 Py_DECREF(args);
1010 if (res == NULL)
1011 return -1;
1012 if (!PyInt_Check(res)) {
1013 PyErr_Format(PyExc_TypeError,
1014 "comparison function must return int, not %.200s",
1015 res->ob_type->tp_name);
1016 Py_DECREF(res);
1017 return -1;
1019 i = PyInt_AsLong(res);
1020 Py_DECREF(res);
1021 return i < 0;
1024 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
1025 * islt. This avoids a layer of function call in the usual case, and
1026 * sorting does many comparisons.
1027 * Returns -1 on error, 1 if x < y, 0 if x >= y.
1029 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
1030 PyObject_RichCompareBool(X, Y, Py_LT) : \
1031 islt(X, Y, COMPARE))
1033 /* Compare X to Y via "<". Goto "fail" if the comparison raises an
1034 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
1035 started. It makes more sense in context <wink>. X and Y are PyObject*s.
1037 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
1038 if (k)
1040 /* binarysort is the best method for sorting small arrays: it does
1041 few compares, but can do data movement quadratic in the number of
1042 elements.
1043 [lo, hi) is a contiguous slice of a list, and is sorted via
1044 binary insertion. This sort is stable.
1045 On entry, must have lo <= start <= hi, and that [lo, start) is already
1046 sorted (pass start == lo if you don't know!).
1047 If islt() complains return -1, else 0.
1048 Even in case of error, the output slice will be some permutation of
1049 the input (nothing is lost or duplicated).
1051 static int
1052 binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
1053 /* compare -- comparison function object, or NULL for default */
1055 register Py_ssize_t k;
1056 register PyObject **l, **p, **r;
1057 register PyObject *pivot;
1059 assert(lo <= start && start <= hi);
1060 /* assert [lo, start) is sorted */
1061 if (lo == start)
1062 ++start;
1063 for (; start < hi; ++start) {
1064 /* set l to where *start belongs */
1065 l = lo;
1066 r = start;
1067 pivot = *r;
1068 /* Invariants:
1069 * pivot >= all in [lo, l).
1070 * pivot < all in [r, start).
1071 * The second is vacuously true at the start.
1073 assert(l < r);
1074 do {
1075 p = l + ((r - l) >> 1);
1076 IFLT(pivot, *p)
1077 r = p;
1078 else
1079 l = p+1;
1080 } while (l < r);
1081 assert(l == r);
1082 /* The invariants still hold, so pivot >= all in [lo, l) and
1083 pivot < all in [l, start), so pivot belongs at l. Note
1084 that if there are elements equal to pivot, l points to the
1085 first slot after them -- that's why this sort is stable.
1086 Slide over to make room.
1087 Caution: using memmove is much slower under MSVC 5;
1088 we're not usually moving many slots. */
1089 for (p = start; p > l; --p)
1090 *p = *(p-1);
1091 *l = pivot;
1093 return 0;
1095 fail:
1096 return -1;
1100 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1101 is required on entry. "A run" is the longest ascending sequence, with
1103 lo[0] <= lo[1] <= lo[2] <= ...
1105 or the longest descending sequence, with
1107 lo[0] > lo[1] > lo[2] > ...
1109 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1110 For its intended use in a stable mergesort, the strictness of the defn of
1111 "descending" is needed so that the caller can safely reverse a descending
1112 sequence without violating stability (strict > ensures there are no equal
1113 elements to get out of order).
1115 Returns -1 in case of error.
1117 static Py_ssize_t
1118 count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)
1120 Py_ssize_t k;
1121 Py_ssize_t n;
1123 assert(lo < hi);
1124 *descending = 0;
1125 ++lo;
1126 if (lo == hi)
1127 return 1;
1129 n = 2;
1130 IFLT(*lo, *(lo-1)) {
1131 *descending = 1;
1132 for (lo = lo+1; lo < hi; ++lo, ++n) {
1133 IFLT(*lo, *(lo-1))
1135 else
1136 break;
1139 else {
1140 for (lo = lo+1; lo < hi; ++lo, ++n) {
1141 IFLT(*lo, *(lo-1))
1142 break;
1146 return n;
1147 fail:
1148 return -1;
1152 Locate the proper position of key in a sorted vector; if the vector contains
1153 an element equal to key, return the position immediately to the left of
1154 the leftmost equal element. [gallop_right() does the same except returns
1155 the position to the right of the rightmost equal element (if any).]
1157 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
1159 "hint" is an index at which to begin the search, 0 <= hint < n. The closer
1160 hint is to the final result, the faster this runs.
1162 The return value is the int k in 0..n such that
1164 a[k-1] < key <= a[k]
1166 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1167 key belongs at index k; or, IOW, the first k elements of a should precede
1168 key, and the last n-k should follow key.
1170 Returns -1 on error. See listsort.txt for info on the method.
1172 static Py_ssize_t
1173 gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)
1175 Py_ssize_t ofs;
1176 Py_ssize_t lastofs;
1177 Py_ssize_t k;
1179 assert(key && a && n > 0 && hint >= 0 && hint < n);
1181 a += hint;
1182 lastofs = 0;
1183 ofs = 1;
1184 IFLT(*a, key) {
1185 /* a[hint] < key -- gallop right, until
1186 * a[hint + lastofs] < key <= a[hint + ofs]
1188 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1189 while (ofs < maxofs) {
1190 IFLT(a[ofs], key) {
1191 lastofs = ofs;
1192 ofs = (ofs << 1) + 1;
1193 if (ofs <= 0) /* int overflow */
1194 ofs = maxofs;
1196 else /* key <= a[hint + ofs] */
1197 break;
1199 if (ofs > maxofs)
1200 ofs = maxofs;
1201 /* Translate back to offsets relative to &a[0]. */
1202 lastofs += hint;
1203 ofs += hint;
1205 else {
1206 /* key <= a[hint] -- gallop left, until
1207 * a[hint - ofs] < key <= a[hint - lastofs]
1209 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1210 while (ofs < maxofs) {
1211 IFLT(*(a-ofs), key)
1212 break;
1213 /* key <= a[hint - ofs] */
1214 lastofs = ofs;
1215 ofs = (ofs << 1) + 1;
1216 if (ofs <= 0) /* int overflow */
1217 ofs = maxofs;
1219 if (ofs > maxofs)
1220 ofs = maxofs;
1221 /* Translate back to positive offsets relative to &a[0]. */
1222 k = lastofs;
1223 lastofs = hint - ofs;
1224 ofs = hint - k;
1226 a -= hint;
1228 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1229 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1230 * right of lastofs but no farther right than ofs. Do a binary
1231 * search, with invariant a[lastofs-1] < key <= a[ofs].
1233 ++lastofs;
1234 while (lastofs < ofs) {
1235 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
1237 IFLT(a[m], key)
1238 lastofs = m+1; /* a[m] < key */
1239 else
1240 ofs = m; /* key <= a[m] */
1242 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1243 return ofs;
1245 fail:
1246 return -1;
1250 Exactly like gallop_left(), except that if key already exists in a[0:n],
1251 finds the position immediately to the right of the rightmost equal value.
1253 The return value is the int k in 0..n such that
1255 a[k-1] <= key < a[k]
1257 or -1 if error.
1259 The code duplication is massive, but this is enough different given that
1260 we're sticking to "<" comparisons that it's much harder to follow if
1261 written as one routine with yet another "left or right?" flag.
1263 static Py_ssize_t
1264 gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)
1266 Py_ssize_t ofs;
1267 Py_ssize_t lastofs;
1268 Py_ssize_t k;
1270 assert(key && a && n > 0 && hint >= 0 && hint < n);
1272 a += hint;
1273 lastofs = 0;
1274 ofs = 1;
1275 IFLT(key, *a) {
1276 /* key < a[hint] -- gallop left, until
1277 * a[hint - ofs] <= key < a[hint - lastofs]
1279 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1280 while (ofs < maxofs) {
1281 IFLT(key, *(a-ofs)) {
1282 lastofs = ofs;
1283 ofs = (ofs << 1) + 1;
1284 if (ofs <= 0) /* int overflow */
1285 ofs = maxofs;
1287 else /* a[hint - ofs] <= key */
1288 break;
1290 if (ofs > maxofs)
1291 ofs = maxofs;
1292 /* Translate back to positive offsets relative to &a[0]. */
1293 k = lastofs;
1294 lastofs = hint - ofs;
1295 ofs = hint - k;
1297 else {
1298 /* a[hint] <= key -- gallop right, until
1299 * a[hint + lastofs] <= key < a[hint + ofs]
1301 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1302 while (ofs < maxofs) {
1303 IFLT(key, a[ofs])
1304 break;
1305 /* a[hint + ofs] <= key */
1306 lastofs = ofs;
1307 ofs = (ofs << 1) + 1;
1308 if (ofs <= 0) /* int overflow */
1309 ofs = maxofs;
1311 if (ofs > maxofs)
1312 ofs = maxofs;
1313 /* Translate back to offsets relative to &a[0]. */
1314 lastofs += hint;
1315 ofs += hint;
1317 a -= hint;
1319 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1320 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1321 * right of lastofs but no farther right than ofs. Do a binary
1322 * search, with invariant a[lastofs-1] <= key < a[ofs].
1324 ++lastofs;
1325 while (lastofs < ofs) {
1326 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
1328 IFLT(key, a[m])
1329 ofs = m; /* key < a[m] */
1330 else
1331 lastofs = m+1; /* a[m] <= key */
1333 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1334 return ofs;
1336 fail:
1337 return -1;
1340 /* The maximum number of entries in a MergeState's pending-runs stack.
1341 * This is enough to sort arrays of size up to about
1342 * 32 * phi ** MAX_MERGE_PENDING
1343 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1344 * with 2**64 elements.
1346 #define MAX_MERGE_PENDING 85
1348 /* When we get into galloping mode, we stay there until both runs win less
1349 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1351 #define MIN_GALLOP 7
1353 /* Avoid malloc for small temp arrays. */
1354 #define MERGESTATE_TEMP_SIZE 256
1356 /* One MergeState exists on the stack per invocation of mergesort. It's just
1357 * a convenient way to pass state around among the helper functions.
1359 struct s_slice {
1360 PyObject **base;
1361 Py_ssize_t len;
1364 typedef struct s_MergeState {
1365 /* The user-supplied comparison function. or NULL if none given. */
1366 PyObject *compare;
1368 /* This controls when we get *into* galloping mode. It's initialized
1369 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1370 * random data, and lower for highly structured data.
1372 Py_ssize_t min_gallop;
1374 /* 'a' is temp storage to help with merges. It contains room for
1375 * alloced entries.
1377 PyObject **a; /* may point to temparray below */
1378 Py_ssize_t alloced;
1380 /* A stack of n pending runs yet to be merged. Run #i starts at
1381 * address base[i] and extends for len[i] elements. It's always
1382 * true (so long as the indices are in bounds) that
1384 * pending[i].base + pending[i].len == pending[i+1].base
1386 * so we could cut the storage for this, but it's a minor amount,
1387 * and keeping all the info explicit simplifies the code.
1389 int n;
1390 struct s_slice pending[MAX_MERGE_PENDING];
1392 /* 'a' points to this when possible, rather than muck with malloc. */
1393 PyObject *temparray[MERGESTATE_TEMP_SIZE];
1394 } MergeState;
1396 /* Conceptually a MergeState's constructor. */
1397 static void
1398 merge_init(MergeState *ms, PyObject *compare)
1400 assert(ms != NULL);
1401 ms->compare = compare;
1402 ms->a = ms->temparray;
1403 ms->alloced = MERGESTATE_TEMP_SIZE;
1404 ms->n = 0;
1405 ms->min_gallop = MIN_GALLOP;
1408 /* Free all the temp memory owned by the MergeState. This must be called
1409 * when you're done with a MergeState, and may be called before then if
1410 * you want to free the temp memory early.
1412 static void
1413 merge_freemem(MergeState *ms)
1415 assert(ms != NULL);
1416 if (ms->a != ms->temparray)
1417 PyMem_Free(ms->a);
1418 ms->a = ms->temparray;
1419 ms->alloced = MERGESTATE_TEMP_SIZE;
1422 /* Ensure enough temp memory for 'need' array slots is available.
1423 * Returns 0 on success and -1 if the memory can't be gotten.
1425 static int
1426 merge_getmem(MergeState *ms, Py_ssize_t need)
1428 assert(ms != NULL);
1429 if (need <= ms->alloced)
1430 return 0;
1431 /* Don't realloc! That can cost cycles to copy the old data, but
1432 * we don't care what's in the block.
1434 merge_freemem(ms);
1435 if (need > PY_SSIZE_T_MAX / sizeof(PyObject*)) {
1436 PyErr_NoMemory();
1437 return -1;
1439 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));
1440 if (ms->a) {
1441 ms->alloced = need;
1442 return 0;
1444 PyErr_NoMemory();
1445 merge_freemem(ms); /* reset to sane state */
1446 return -1;
1448 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1449 merge_getmem(MS, NEED))
1451 /* Merge the na elements starting at pa with the nb elements starting at pb
1452 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1453 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1454 * merge, and should have na <= nb. See listsort.txt for more info.
1455 * Return 0 if successful, -1 if error.
1457 static Py_ssize_t
1458 merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
1459 PyObject **pb, Py_ssize_t nb)
1461 Py_ssize_t k;
1462 PyObject *compare;
1463 PyObject **dest;
1464 int result = -1; /* guilty until proved innocent */
1465 Py_ssize_t min_gallop;
1467 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1468 if (MERGE_GETMEM(ms, na) < 0)
1469 return -1;
1470 memcpy(ms->a, pa, na * sizeof(PyObject*));
1471 dest = pa;
1472 pa = ms->a;
1474 *dest++ = *pb++;
1475 --nb;
1476 if (nb == 0)
1477 goto Succeed;
1478 if (na == 1)
1479 goto CopyB;
1481 min_gallop = ms->min_gallop;
1482 compare = ms->compare;
1483 for (;;) {
1484 Py_ssize_t acount = 0; /* # of times A won in a row */
1485 Py_ssize_t bcount = 0; /* # of times B won in a row */
1487 /* Do the straightforward thing until (if ever) one run
1488 * appears to win consistently.
1490 for (;;) {
1491 assert(na > 1 && nb > 0);
1492 k = ISLT(*pb, *pa, compare);
1493 if (k) {
1494 if (k < 0)
1495 goto Fail;
1496 *dest++ = *pb++;
1497 ++bcount;
1498 acount = 0;
1499 --nb;
1500 if (nb == 0)
1501 goto Succeed;
1502 if (bcount >= min_gallop)
1503 break;
1505 else {
1506 *dest++ = *pa++;
1507 ++acount;
1508 bcount = 0;
1509 --na;
1510 if (na == 1)
1511 goto CopyB;
1512 if (acount >= min_gallop)
1513 break;
1517 /* One run is winning so consistently that galloping may
1518 * be a huge win. So try that, and continue galloping until
1519 * (if ever) neither run appears to be winning consistently
1520 * anymore.
1522 ++min_gallop;
1523 do {
1524 assert(na > 1 && nb > 0);
1525 min_gallop -= min_gallop > 1;
1526 ms->min_gallop = min_gallop;
1527 k = gallop_right(*pb, pa, na, 0, compare);
1528 acount = k;
1529 if (k) {
1530 if (k < 0)
1531 goto Fail;
1532 memcpy(dest, pa, k * sizeof(PyObject *));
1533 dest += k;
1534 pa += k;
1535 na -= k;
1536 if (na == 1)
1537 goto CopyB;
1538 /* na==0 is impossible now if the comparison
1539 * function is consistent, but we can't assume
1540 * that it is.
1542 if (na == 0)
1543 goto Succeed;
1545 *dest++ = *pb++;
1546 --nb;
1547 if (nb == 0)
1548 goto Succeed;
1550 k = gallop_left(*pa, pb, nb, 0, compare);
1551 bcount = k;
1552 if (k) {
1553 if (k < 0)
1554 goto Fail;
1555 memmove(dest, pb, k * sizeof(PyObject *));
1556 dest += k;
1557 pb += k;
1558 nb -= k;
1559 if (nb == 0)
1560 goto Succeed;
1562 *dest++ = *pa++;
1563 --na;
1564 if (na == 1)
1565 goto CopyB;
1566 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1567 ++min_gallop; /* penalize it for leaving galloping mode */
1568 ms->min_gallop = min_gallop;
1570 Succeed:
1571 result = 0;
1572 Fail:
1573 if (na)
1574 memcpy(dest, pa, na * sizeof(PyObject*));
1575 return result;
1576 CopyB:
1577 assert(na == 1 && nb > 0);
1578 /* The last element of pa belongs at the end of the merge. */
1579 memmove(dest, pb, nb * sizeof(PyObject *));
1580 dest[nb] = *pa;
1581 return 0;
1584 /* Merge the na elements starting at pa with the nb elements starting at pb
1585 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1586 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1587 * merge, and should have na >= nb. See listsort.txt for more info.
1588 * Return 0 if successful, -1 if error.
1590 static Py_ssize_t
1591 merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb)
1593 Py_ssize_t k;
1594 PyObject *compare;
1595 PyObject **dest;
1596 int result = -1; /* guilty until proved innocent */
1597 PyObject **basea;
1598 PyObject **baseb;
1599 Py_ssize_t min_gallop;
1601 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1602 if (MERGE_GETMEM(ms, nb) < 0)
1603 return -1;
1604 dest = pb + nb - 1;
1605 memcpy(ms->a, pb, nb * sizeof(PyObject*));
1606 basea = pa;
1607 baseb = ms->a;
1608 pb = ms->a + nb - 1;
1609 pa += na - 1;
1611 *dest-- = *pa--;
1612 --na;
1613 if (na == 0)
1614 goto Succeed;
1615 if (nb == 1)
1616 goto CopyA;
1618 min_gallop = ms->min_gallop;
1619 compare = ms->compare;
1620 for (;;) {
1621 Py_ssize_t acount = 0; /* # of times A won in a row */
1622 Py_ssize_t bcount = 0; /* # of times B won in a row */
1624 /* Do the straightforward thing until (if ever) one run
1625 * appears to win consistently.
1627 for (;;) {
1628 assert(na > 0 && nb > 1);
1629 k = ISLT(*pb, *pa, compare);
1630 if (k) {
1631 if (k < 0)
1632 goto Fail;
1633 *dest-- = *pa--;
1634 ++acount;
1635 bcount = 0;
1636 --na;
1637 if (na == 0)
1638 goto Succeed;
1639 if (acount >= min_gallop)
1640 break;
1642 else {
1643 *dest-- = *pb--;
1644 ++bcount;
1645 acount = 0;
1646 --nb;
1647 if (nb == 1)
1648 goto CopyA;
1649 if (bcount >= min_gallop)
1650 break;
1654 /* One run is winning so consistently that galloping may
1655 * be a huge win. So try that, and continue galloping until
1656 * (if ever) neither run appears to be winning consistently
1657 * anymore.
1659 ++min_gallop;
1660 do {
1661 assert(na > 0 && nb > 1);
1662 min_gallop -= min_gallop > 1;
1663 ms->min_gallop = min_gallop;
1664 k = gallop_right(*pb, basea, na, na-1, compare);
1665 if (k < 0)
1666 goto Fail;
1667 k = na - k;
1668 acount = k;
1669 if (k) {
1670 dest -= k;
1671 pa -= k;
1672 memmove(dest+1, pa+1, k * sizeof(PyObject *));
1673 na -= k;
1674 if (na == 0)
1675 goto Succeed;
1677 *dest-- = *pb--;
1678 --nb;
1679 if (nb == 1)
1680 goto CopyA;
1682 k = gallop_left(*pa, baseb, nb, nb-1, compare);
1683 if (k < 0)
1684 goto Fail;
1685 k = nb - k;
1686 bcount = k;
1687 if (k) {
1688 dest -= k;
1689 pb -= k;
1690 memcpy(dest+1, pb+1, k * sizeof(PyObject *));
1691 nb -= k;
1692 if (nb == 1)
1693 goto CopyA;
1694 /* nb==0 is impossible now if the comparison
1695 * function is consistent, but we can't assume
1696 * that it is.
1698 if (nb == 0)
1699 goto Succeed;
1701 *dest-- = *pa--;
1702 --na;
1703 if (na == 0)
1704 goto Succeed;
1705 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1706 ++min_gallop; /* penalize it for leaving galloping mode */
1707 ms->min_gallop = min_gallop;
1709 Succeed:
1710 result = 0;
1711 Fail:
1712 if (nb)
1713 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
1714 return result;
1715 CopyA:
1716 assert(nb == 1 && na > 0);
1717 /* The first element of pb belongs at the front of the merge. */
1718 dest -= na;
1719 pa -= na;
1720 memmove(dest+1, pa+1, na * sizeof(PyObject *));
1721 *dest = *pb;
1722 return 0;
1725 /* Merge the two runs at stack indices i and i+1.
1726 * Returns 0 on success, -1 on error.
1728 static Py_ssize_t
1729 merge_at(MergeState *ms, Py_ssize_t i)
1731 PyObject **pa, **pb;
1732 Py_ssize_t na, nb;
1733 Py_ssize_t k;
1734 PyObject *compare;
1736 assert(ms != NULL);
1737 assert(ms->n >= 2);
1738 assert(i >= 0);
1739 assert(i == ms->n - 2 || i == ms->n - 3);
1741 pa = ms->pending[i].base;
1742 na = ms->pending[i].len;
1743 pb = ms->pending[i+1].base;
1744 nb = ms->pending[i+1].len;
1745 assert(na > 0 && nb > 0);
1746 assert(pa + na == pb);
1748 /* Record the length of the combined runs; if i is the 3rd-last
1749 * run now, also slide over the last run (which isn't involved
1750 * in this merge). The current run i+1 goes away in any case.
1752 ms->pending[i].len = na + nb;
1753 if (i == ms->n - 3)
1754 ms->pending[i+1] = ms->pending[i+2];
1755 --ms->n;
1757 /* Where does b start in a? Elements in a before that can be
1758 * ignored (already in place).
1760 compare = ms->compare;
1761 k = gallop_right(*pb, pa, na, 0, compare);
1762 if (k < 0)
1763 return -1;
1764 pa += k;
1765 na -= k;
1766 if (na == 0)
1767 return 0;
1769 /* Where does a end in b? Elements in b after that can be
1770 * ignored (already in place).
1772 nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);
1773 if (nb <= 0)
1774 return nb;
1776 /* Merge what remains of the runs, using a temp array with
1777 * min(na, nb) elements.
1779 if (na <= nb)
1780 return merge_lo(ms, pa, na, pb, nb);
1781 else
1782 return merge_hi(ms, pa, na, pb, nb);
1785 /* Examine the stack of runs waiting to be merged, merging adjacent runs
1786 * until the stack invariants are re-established:
1788 * 1. len[-3] > len[-2] + len[-1]
1789 * 2. len[-2] > len[-1]
1791 * See listsort.txt for more info.
1793 * Returns 0 on success, -1 on error.
1795 static int
1796 merge_collapse(MergeState *ms)
1798 struct s_slice *p = ms->pending;
1800 assert(ms);
1801 while (ms->n > 1) {
1802 Py_ssize_t n = ms->n - 2;
1803 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
1804 if (p[n-1].len < p[n+1].len)
1805 --n;
1806 if (merge_at(ms, n) < 0)
1807 return -1;
1809 else if (p[n].len <= p[n+1].len) {
1810 if (merge_at(ms, n) < 0)
1811 return -1;
1813 else
1814 break;
1816 return 0;
1819 /* Regardless of invariants, merge all runs on the stack until only one
1820 * remains. This is used at the end of the mergesort.
1822 * Returns 0 on success, -1 on error.
1824 static int
1825 merge_force_collapse(MergeState *ms)
1827 struct s_slice *p = ms->pending;
1829 assert(ms);
1830 while (ms->n > 1) {
1831 Py_ssize_t n = ms->n - 2;
1832 if (n > 0 && p[n-1].len < p[n+1].len)
1833 --n;
1834 if (merge_at(ms, n) < 0)
1835 return -1;
1837 return 0;
1840 /* Compute a good value for the minimum run length; natural runs shorter
1841 * than this are boosted artificially via binary insertion.
1843 * If n < 64, return n (it's too small to bother with fancy stuff).
1844 * Else if n is an exact power of 2, return 32.
1845 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1846 * strictly less than, an exact power of 2.
1848 * See listsort.txt for more info.
1850 static Py_ssize_t
1851 merge_compute_minrun(Py_ssize_t n)
1853 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
1855 assert(n >= 0);
1856 while (n >= 64) {
1857 r |= n & 1;
1858 n >>= 1;
1860 return n + r;
1863 /* Special wrapper to support stable sorting using the decorate-sort-undecorate
1864 pattern. Holds a key which is used for comparisons and the original record
1865 which is returned during the undecorate phase. By exposing only the key
1866 during comparisons, the underlying sort stability characteristics are left
1867 unchanged. Also, if a custom comparison function is used, it will only see
1868 the key instead of a full record. */
1870 typedef struct {
1871 PyObject_HEAD
1872 PyObject *key;
1873 PyObject *value;
1874 } sortwrapperobject;
1876 PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key.");
1877 static PyObject *
1878 sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int);
1879 static void
1880 sortwrapper_dealloc(sortwrapperobject *);
1882 static PyTypeObject sortwrapper_type = {
1883 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1884 "sortwrapper", /* tp_name */
1885 sizeof(sortwrapperobject), /* tp_basicsize */
1886 0, /* tp_itemsize */
1887 /* methods */
1888 (destructor)sortwrapper_dealloc, /* tp_dealloc */
1889 0, /* tp_print */
1890 0, /* tp_getattr */
1891 0, /* tp_setattr */
1892 0, /* tp_compare */
1893 0, /* tp_repr */
1894 0, /* tp_as_number */
1895 0, /* tp_as_sequence */
1896 0, /* tp_as_mapping */
1897 0, /* tp_hash */
1898 0, /* tp_call */
1899 0, /* tp_str */
1900 PyObject_GenericGetAttr, /* tp_getattro */
1901 0, /* tp_setattro */
1902 0, /* tp_as_buffer */
1903 Py_TPFLAGS_DEFAULT |
1904 Py_TPFLAGS_HAVE_RICHCOMPARE, /* tp_flags */
1905 sortwrapper_doc, /* tp_doc */
1906 0, /* tp_traverse */
1907 0, /* tp_clear */
1908 (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */
1912 static PyObject *
1913 sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
1915 if (!PyObject_TypeCheck(b, &sortwrapper_type)) {
1916 PyErr_SetString(PyExc_TypeError,
1917 "expected a sortwrapperobject");
1918 return NULL;
1920 return PyObject_RichCompare(a->key, b->key, op);
1923 static void
1924 sortwrapper_dealloc(sortwrapperobject *so)
1926 Py_XDECREF(so->key);
1927 Py_XDECREF(so->value);
1928 PyObject_Del(so);
1931 /* Returns a new reference to a sortwrapper.
1932 Consumes the references to the two underlying objects. */
1934 static PyObject *
1935 build_sortwrapper(PyObject *key, PyObject *value)
1937 sortwrapperobject *so;
1939 so = PyObject_New(sortwrapperobject, &sortwrapper_type);
1940 if (so == NULL)
1941 return NULL;
1942 so->key = key;
1943 so->value = value;
1944 return (PyObject *)so;
1947 /* Returns a new reference to the value underlying the wrapper. */
1948 static PyObject *
1949 sortwrapper_getvalue(PyObject *so)
1951 PyObject *value;
1953 if (!PyObject_TypeCheck(so, &sortwrapper_type)) {
1954 PyErr_SetString(PyExc_TypeError,
1955 "expected a sortwrapperobject");
1956 return NULL;
1958 value = ((sortwrapperobject *)so)->value;
1959 Py_INCREF(value);
1960 return value;
1963 /* Wrapper for user specified cmp functions in combination with a
1964 specified key function. Makes sure the cmp function is presented
1965 with the actual key instead of the sortwrapper */
1967 typedef struct {
1968 PyObject_HEAD
1969 PyObject *func;
1970 } cmpwrapperobject;
1972 static void
1973 cmpwrapper_dealloc(cmpwrapperobject *co)
1975 Py_XDECREF(co->func);
1976 PyObject_Del(co);
1979 static PyObject *
1980 cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds)
1982 PyObject *x, *y, *xx, *yy;
1984 if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y))
1985 return NULL;
1986 if (!PyObject_TypeCheck(x, &sortwrapper_type) ||
1987 !PyObject_TypeCheck(y, &sortwrapper_type)) {
1988 PyErr_SetString(PyExc_TypeError,
1989 "expected a sortwrapperobject");
1990 return NULL;
1992 xx = ((sortwrapperobject *)x)->key;
1993 yy = ((sortwrapperobject *)y)->key;
1994 return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL);
1997 PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys.");
1999 static PyTypeObject cmpwrapper_type = {
2000 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2001 "cmpwrapper", /* tp_name */
2002 sizeof(cmpwrapperobject), /* tp_basicsize */
2003 0, /* tp_itemsize */
2004 /* methods */
2005 (destructor)cmpwrapper_dealloc, /* tp_dealloc */
2006 0, /* tp_print */
2007 0, /* tp_getattr */
2008 0, /* tp_setattr */
2009 0, /* tp_compare */
2010 0, /* tp_repr */
2011 0, /* tp_as_number */
2012 0, /* tp_as_sequence */
2013 0, /* tp_as_mapping */
2014 0, /* tp_hash */
2015 (ternaryfunc)cmpwrapper_call, /* tp_call */
2016 0, /* tp_str */
2017 PyObject_GenericGetAttr, /* tp_getattro */
2018 0, /* tp_setattro */
2019 0, /* tp_as_buffer */
2020 Py_TPFLAGS_DEFAULT, /* tp_flags */
2021 cmpwrapper_doc, /* tp_doc */
2024 static PyObject *
2025 build_cmpwrapper(PyObject *cmpfunc)
2027 cmpwrapperobject *co;
2029 co = PyObject_New(cmpwrapperobject, &cmpwrapper_type);
2030 if (co == NULL)
2031 return NULL;
2032 Py_INCREF(cmpfunc);
2033 co->func = cmpfunc;
2034 return (PyObject *)co;
2037 /* An adaptive, stable, natural mergesort. See listsort.txt.
2038 * Returns Py_None on success, NULL on error. Even in case of error, the
2039 * list will be some permutation of its input state (nothing is lost or
2040 * duplicated).
2042 static PyObject *
2043 listsort(PyListObject *self, PyObject *args, PyObject *kwds)
2045 MergeState ms;
2046 PyObject **lo, **hi;
2047 Py_ssize_t nremaining;
2048 Py_ssize_t minrun;
2049 Py_ssize_t saved_ob_size, saved_allocated;
2050 PyObject **saved_ob_item;
2051 PyObject **final_ob_item;
2052 PyObject *compare = NULL;
2053 PyObject *result = NULL; /* guilty until proved innocent */
2054 int reverse = 0;
2055 PyObject *keyfunc = NULL;
2056 Py_ssize_t i;
2057 PyObject *key, *value, *kvpair;
2058 static char *kwlist[] = {"cmp", "key", "reverse", 0};
2060 assert(self != NULL);
2061 assert (PyList_Check(self));
2062 if (args != NULL) {
2063 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",
2064 kwlist, &compare, &keyfunc, &reverse))
2065 return NULL;
2067 if (compare == Py_None)
2068 compare = NULL;
2069 if (compare != NULL &&
2070 PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0)
2071 return NULL;
2072 if (keyfunc == Py_None)
2073 keyfunc = NULL;
2074 if (compare != NULL && keyfunc != NULL) {
2075 compare = build_cmpwrapper(compare);
2076 if (compare == NULL)
2077 return NULL;
2078 } else
2079 Py_XINCREF(compare);
2081 /* The list is temporarily made empty, so that mutations performed
2082 * by comparison functions can't affect the slice of memory we're
2083 * sorting (allowing mutations during sorting is a core-dump
2084 * factory, since ob_item may change).
2086 saved_ob_size = Py_SIZE(self);
2087 saved_ob_item = self->ob_item;
2088 saved_allocated = self->allocated;
2089 Py_SIZE(self) = 0;
2090 self->ob_item = NULL;
2091 self->allocated = -1; /* any operation will reset it to >= 0 */
2093 if (keyfunc != NULL) {
2094 for (i=0 ; i < saved_ob_size ; i++) {
2095 value = saved_ob_item[i];
2096 key = PyObject_CallFunctionObjArgs(keyfunc, value,
2097 NULL);
2098 if (key == NULL) {
2099 for (i=i-1 ; i>=0 ; i--) {
2100 kvpair = saved_ob_item[i];
2101 value = sortwrapper_getvalue(kvpair);
2102 saved_ob_item[i] = value;
2103 Py_DECREF(kvpair);
2105 goto dsu_fail;
2107 kvpair = build_sortwrapper(key, value);
2108 if (kvpair == NULL)
2109 goto dsu_fail;
2110 saved_ob_item[i] = kvpair;
2114 /* Reverse sort stability achieved by initially reversing the list,
2115 applying a stable forward sort, then reversing the final result. */
2116 if (reverse && saved_ob_size > 1)
2117 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
2119 merge_init(&ms, compare);
2121 nremaining = saved_ob_size;
2122 if (nremaining < 2)
2123 goto succeed;
2125 /* March over the array once, left to right, finding natural runs,
2126 * and extending short natural runs to minrun elements.
2128 lo = saved_ob_item;
2129 hi = lo + nremaining;
2130 minrun = merge_compute_minrun(nremaining);
2131 do {
2132 int descending;
2133 Py_ssize_t n;
2135 /* Identify next run. */
2136 n = count_run(lo, hi, compare, &descending);
2137 if (n < 0)
2138 goto fail;
2139 if (descending)
2140 reverse_slice(lo, lo + n);
2141 /* If short, extend to min(minrun, nremaining). */
2142 if (n < minrun) {
2143 const Py_ssize_t force = nremaining <= minrun ?
2144 nremaining : minrun;
2145 if (binarysort(lo, lo + force, lo + n, compare) < 0)
2146 goto fail;
2147 n = force;
2149 /* Push run onto pending-runs stack, and maybe merge. */
2150 assert(ms.n < MAX_MERGE_PENDING);
2151 ms.pending[ms.n].base = lo;
2152 ms.pending[ms.n].len = n;
2153 ++ms.n;
2154 if (merge_collapse(&ms) < 0)
2155 goto fail;
2156 /* Advance to find next run. */
2157 lo += n;
2158 nremaining -= n;
2159 } while (nremaining);
2160 assert(lo == hi);
2162 if (merge_force_collapse(&ms) < 0)
2163 goto fail;
2164 assert(ms.n == 1);
2165 assert(ms.pending[0].base == saved_ob_item);
2166 assert(ms.pending[0].len == saved_ob_size);
2168 succeed:
2169 result = Py_None;
2170 fail:
2171 if (keyfunc != NULL) {
2172 for (i=0 ; i < saved_ob_size ; i++) {
2173 kvpair = saved_ob_item[i];
2174 value = sortwrapper_getvalue(kvpair);
2175 saved_ob_item[i] = value;
2176 Py_DECREF(kvpair);
2180 if (self->allocated != -1 && result != NULL) {
2181 /* The user mucked with the list during the sort,
2182 * and we don't already have another error to report.
2184 PyErr_SetString(PyExc_ValueError, "list modified during sort");
2185 result = NULL;
2188 if (reverse && saved_ob_size > 1)
2189 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
2191 merge_freemem(&ms);
2193 dsu_fail:
2194 final_ob_item = self->ob_item;
2195 i = Py_SIZE(self);
2196 Py_SIZE(self) = saved_ob_size;
2197 self->ob_item = saved_ob_item;
2198 self->allocated = saved_allocated;
2199 if (final_ob_item != NULL) {
2200 /* we cannot use list_clear() for this because it does not
2201 guarantee that the list is really empty when it returns */
2202 while (--i >= 0) {
2203 Py_XDECREF(final_ob_item[i]);
2205 PyMem_FREE(final_ob_item);
2207 Py_XDECREF(compare);
2208 Py_XINCREF(result);
2209 return result;
2211 #undef IFLT
2212 #undef ISLT
2215 PyList_Sort(PyObject *v)
2217 if (v == NULL || !PyList_Check(v)) {
2218 PyErr_BadInternalCall();
2219 return -1;
2221 v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
2222 if (v == NULL)
2223 return -1;
2224 Py_DECREF(v);
2225 return 0;
2228 static PyObject *
2229 listreverse(PyListObject *self)
2231 if (Py_SIZE(self) > 1)
2232 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2233 Py_RETURN_NONE;
2237 PyList_Reverse(PyObject *v)
2239 PyListObject *self = (PyListObject *)v;
2241 if (v == NULL || !PyList_Check(v)) {
2242 PyErr_BadInternalCall();
2243 return -1;
2245 if (Py_SIZE(self) > 1)
2246 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2247 return 0;
2250 PyObject *
2251 PyList_AsTuple(PyObject *v)
2253 PyObject *w;
2254 PyObject **p, **q;
2255 Py_ssize_t n;
2256 if (v == NULL || !PyList_Check(v)) {
2257 PyErr_BadInternalCall();
2258 return NULL;
2260 n = Py_SIZE(v);
2261 w = PyTuple_New(n);
2262 if (w == NULL)
2263 return NULL;
2264 p = ((PyTupleObject *)w)->ob_item;
2265 q = ((PyListObject *)v)->ob_item;
2266 while (--n >= 0) {
2267 Py_INCREF(*q);
2268 *p = *q;
2269 p++;
2270 q++;
2272 return w;
2275 static PyObject *
2276 listindex(PyListObject *self, PyObject *args)
2278 Py_ssize_t i, start=0, stop=Py_SIZE(self);
2279 PyObject *v, *format_tuple, *err_string;
2280 static PyObject *err_format = NULL;
2282 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
2283 _PyEval_SliceIndex, &start,
2284 _PyEval_SliceIndex, &stop))
2285 return NULL;
2286 if (start < 0) {
2287 start += Py_SIZE(self);
2288 if (start < 0)
2289 start = 0;
2291 if (stop < 0) {
2292 stop += Py_SIZE(self);
2293 if (stop < 0)
2294 stop = 0;
2296 for (i = start; i < stop && i < Py_SIZE(self); i++) {
2297 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2298 if (cmp > 0)
2299 return PyInt_FromSsize_t(i);
2300 else if (cmp < 0)
2301 return NULL;
2303 if (err_format == NULL) {
2304 err_format = PyString_FromString("%r is not in list");
2305 if (err_format == NULL)
2306 return NULL;
2308 format_tuple = PyTuple_Pack(1, v);
2309 if (format_tuple == NULL)
2310 return NULL;
2311 err_string = PyString_Format(err_format, format_tuple);
2312 Py_DECREF(format_tuple);
2313 if (err_string == NULL)
2314 return NULL;
2315 PyErr_SetObject(PyExc_ValueError, err_string);
2316 Py_DECREF(err_string);
2317 return NULL;
2320 static PyObject *
2321 listcount(PyListObject *self, PyObject *v)
2323 Py_ssize_t count = 0;
2324 Py_ssize_t i;
2326 for (i = 0; i < Py_SIZE(self); i++) {
2327 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2328 if (cmp > 0)
2329 count++;
2330 else if (cmp < 0)
2331 return NULL;
2333 return PyInt_FromSsize_t(count);
2336 static PyObject *
2337 listremove(PyListObject *self, PyObject *v)
2339 Py_ssize_t i;
2341 for (i = 0; i < Py_SIZE(self); i++) {
2342 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2343 if (cmp > 0) {
2344 if (list_ass_slice(self, i, i+1,
2345 (PyObject *)NULL) == 0)
2346 Py_RETURN_NONE;
2347 return NULL;
2349 else if (cmp < 0)
2350 return NULL;
2352 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
2353 return NULL;
2356 static int
2357 list_traverse(PyListObject *o, visitproc visit, void *arg)
2359 Py_ssize_t i;
2361 for (i = Py_SIZE(o); --i >= 0; )
2362 Py_VISIT(o->ob_item[i]);
2363 return 0;
2366 static PyObject *
2367 list_richcompare(PyObject *v, PyObject *w, int op)
2369 PyListObject *vl, *wl;
2370 Py_ssize_t i;
2372 if (!PyList_Check(v) || !PyList_Check(w)) {
2373 Py_INCREF(Py_NotImplemented);
2374 return Py_NotImplemented;
2377 vl = (PyListObject *)v;
2378 wl = (PyListObject *)w;
2380 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
2381 /* Shortcut: if the lengths differ, the lists differ */
2382 PyObject *res;
2383 if (op == Py_EQ)
2384 res = Py_False;
2385 else
2386 res = Py_True;
2387 Py_INCREF(res);
2388 return res;
2391 /* Search for the first index where items are different */
2392 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
2393 int k = PyObject_RichCompareBool(vl->ob_item[i],
2394 wl->ob_item[i], Py_EQ);
2395 if (k < 0)
2396 return NULL;
2397 if (!k)
2398 break;
2401 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
2402 /* No more items to compare -- compare sizes */
2403 Py_ssize_t vs = Py_SIZE(vl);
2404 Py_ssize_t ws = Py_SIZE(wl);
2405 int cmp;
2406 PyObject *res;
2407 switch (op) {
2408 case Py_LT: cmp = vs < ws; break;
2409 case Py_LE: cmp = vs <= ws; break;
2410 case Py_EQ: cmp = vs == ws; break;
2411 case Py_NE: cmp = vs != ws; break;
2412 case Py_GT: cmp = vs > ws; break;
2413 case Py_GE: cmp = vs >= ws; break;
2414 default: return NULL; /* cannot happen */
2416 if (cmp)
2417 res = Py_True;
2418 else
2419 res = Py_False;
2420 Py_INCREF(res);
2421 return res;
2424 /* We have an item that differs -- shortcuts for EQ/NE */
2425 if (op == Py_EQ) {
2426 Py_INCREF(Py_False);
2427 return Py_False;
2429 if (op == Py_NE) {
2430 Py_INCREF(Py_True);
2431 return Py_True;
2434 /* Compare the final item again using the proper operator */
2435 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
2438 static int
2439 list_init(PyListObject *self, PyObject *args, PyObject *kw)
2441 PyObject *arg = NULL;
2442 static char *kwlist[] = {"sequence", 0};
2444 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
2445 return -1;
2447 /* Verify list invariants established by PyType_GenericAlloc() */
2448 assert(0 <= Py_SIZE(self));
2449 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
2450 assert(self->ob_item != NULL ||
2451 self->allocated == 0 || self->allocated == -1);
2453 /* Empty previous contents */
2454 if (self->ob_item != NULL) {
2455 (void)list_clear(self);
2457 if (arg != NULL) {
2458 PyObject *rv = listextend(self, arg);
2459 if (rv == NULL)
2460 return -1;
2461 Py_DECREF(rv);
2463 return 0;
2466 static PyObject *
2467 list_sizeof(PyListObject *self)
2469 Py_ssize_t res;
2471 res = sizeof(PyListObject) + self->allocated * sizeof(void*);
2472 return PyInt_FromSsize_t(res);
2475 static PyObject *list_iter(PyObject *seq);
2476 static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
2478 PyDoc_STRVAR(getitem_doc,
2479 "x.__getitem__(y) <==> x[y]");
2480 PyDoc_STRVAR(reversed_doc,
2481 "L.__reversed__() -- return a reverse iterator over the list");
2482 PyDoc_STRVAR(sizeof_doc,
2483 "L.__sizeof__() -- size of L in memory, in bytes");
2484 PyDoc_STRVAR(append_doc,
2485 "L.append(object) -- append object to end");
2486 PyDoc_STRVAR(extend_doc,
2487 "L.extend(iterable) -- extend list by appending elements from the iterable");
2488 PyDoc_STRVAR(insert_doc,
2489 "L.insert(index, object) -- insert object before index");
2490 PyDoc_STRVAR(pop_doc,
2491 "L.pop([index]) -> item -- remove and return item at index (default last).\n"
2492 "Raises IndexError if list is empty or index is out of range.");
2493 PyDoc_STRVAR(remove_doc,
2494 "L.remove(value) -- remove first occurrence of value.\n"
2495 "Raises ValueError if the value is not present.");
2496 PyDoc_STRVAR(index_doc,
2497 "L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
2498 "Raises ValueError if the value is not present.");
2499 PyDoc_STRVAR(count_doc,
2500 "L.count(value) -> integer -- return number of occurrences of value");
2501 PyDoc_STRVAR(reverse_doc,
2502 "L.reverse() -- reverse *IN PLACE*");
2503 PyDoc_STRVAR(sort_doc,
2504 "L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
2505 cmp(x, y) -> -1, 0, 1");
2507 static PyObject *list_subscript(PyListObject*, PyObject*);
2509 static PyMethodDef list_methods[] = {
2510 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
2511 {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
2512 {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
2513 {"append", (PyCFunction)listappend, METH_O, append_doc},
2514 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
2515 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
2516 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
2517 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
2518 {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
2519 {"count", (PyCFunction)listcount, METH_O, count_doc},
2520 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
2521 {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
2522 {NULL, NULL} /* sentinel */
2525 static PySequenceMethods list_as_sequence = {
2526 (lenfunc)list_length, /* sq_length */
2527 (binaryfunc)list_concat, /* sq_concat */
2528 (ssizeargfunc)list_repeat, /* sq_repeat */
2529 (ssizeargfunc)list_item, /* sq_item */
2530 (ssizessizeargfunc)list_slice, /* sq_slice */
2531 (ssizeobjargproc)list_ass_item, /* sq_ass_item */
2532 (ssizessizeobjargproc)list_ass_slice, /* sq_ass_slice */
2533 (objobjproc)list_contains, /* sq_contains */
2534 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
2535 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
2538 PyDoc_STRVAR(list_doc,
2539 "list() -> new list\n"
2540 "list(sequence) -> new list initialized from sequence's items");
2543 static PyObject *
2544 list_subscript(PyListObject* self, PyObject* item)
2546 if (PyIndex_Check(item)) {
2547 Py_ssize_t i;
2548 i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2549 if (i == -1 && PyErr_Occurred())
2550 return NULL;
2551 if (i < 0)
2552 i += PyList_GET_SIZE(self);
2553 return list_item(self, i);
2555 else if (PySlice_Check(item)) {
2556 Py_ssize_t start, stop, step, slicelength, cur, i;
2557 PyObject* result;
2558 PyObject* it;
2559 PyObject **src, **dest;
2561 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
2562 &start, &stop, &step, &slicelength) < 0) {
2563 return NULL;
2566 if (slicelength <= 0) {
2567 return PyList_New(0);
2569 else if (step == 1) {
2570 return list_slice(self, start, stop);
2572 else {
2573 result = PyList_New(slicelength);
2574 if (!result) return NULL;
2576 src = self->ob_item;
2577 dest = ((PyListObject *)result)->ob_item;
2578 for (cur = start, i = 0; i < slicelength;
2579 cur += step, i++) {
2580 it = src[cur];
2581 Py_INCREF(it);
2582 dest[i] = it;
2585 return result;
2588 else {
2589 PyErr_Format(PyExc_TypeError,
2590 "list indices must be integers, not %.200s",
2591 item->ob_type->tp_name);
2592 return NULL;
2596 static int
2597 list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2599 if (PyIndex_Check(item)) {
2600 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2601 if (i == -1 && PyErr_Occurred())
2602 return -1;
2603 if (i < 0)
2604 i += PyList_GET_SIZE(self);
2605 return list_ass_item(self, i, value);
2607 else if (PySlice_Check(item)) {
2608 Py_ssize_t start, stop, step, slicelength;
2610 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
2611 &start, &stop, &step, &slicelength) < 0) {
2612 return -1;
2615 if (step == 1)
2616 return list_ass_slice(self, start, stop, value);
2618 /* Make sure s[5:2] = [..] inserts at the right place:
2619 before 5, not before 2. */
2620 if ((step < 0 && start < stop) ||
2621 (step > 0 && start > stop))
2622 stop = start;
2624 if (value == NULL) {
2625 /* delete slice */
2626 PyObject **garbage;
2627 Py_ssize_t cur, i;
2629 if (slicelength <= 0)
2630 return 0;
2632 if (step < 0) {
2633 stop = start + 1;
2634 start = stop + step*(slicelength - 1) - 1;
2635 step = -step;
2638 assert(slicelength <= PY_SIZE_MAX / sizeof(PyObject*));
2640 garbage = (PyObject**)
2641 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2642 if (!garbage) {
2643 PyErr_NoMemory();
2644 return -1;
2647 /* drawing pictures might help understand these for
2648 loops. Basically, we memmove the parts of the
2649 list that are *not* part of the slice: step-1
2650 items for each item that is part of the slice,
2651 and then tail end of the list that was not
2652 covered by the slice */
2653 for (cur = start, i = 0;
2654 cur < stop;
2655 cur += step, i++) {
2656 Py_ssize_t lim = step - 1;
2658 garbage[i] = PyList_GET_ITEM(self, cur);
2660 if (cur + step >= Py_SIZE(self)) {
2661 lim = Py_SIZE(self) - cur - 1;
2664 memmove(self->ob_item + cur - i,
2665 self->ob_item + cur + 1,
2666 lim * sizeof(PyObject *));
2668 cur = start + slicelength*step;
2669 if (cur < Py_SIZE(self)) {
2670 memmove(self->ob_item + cur - slicelength,
2671 self->ob_item + cur,
2672 (Py_SIZE(self) - cur) *
2673 sizeof(PyObject *));
2676 Py_SIZE(self) -= slicelength;
2677 list_resize(self, Py_SIZE(self));
2679 for (i = 0; i < slicelength; i++) {
2680 Py_DECREF(garbage[i]);
2682 PyMem_FREE(garbage);
2684 return 0;
2686 else {
2687 /* assign slice */
2688 PyObject *ins, *seq;
2689 PyObject **garbage, **seqitems, **selfitems;
2690 Py_ssize_t cur, i;
2692 /* protect against a[::-1] = a */
2693 if (self == (PyListObject*)value) {
2694 seq = list_slice((PyListObject*)value, 0,
2695 PyList_GET_SIZE(value));
2697 else {
2698 seq = PySequence_Fast(value,
2699 "must assign iterable "
2700 "to extended slice");
2702 if (!seq)
2703 return -1;
2705 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2706 PyErr_Format(PyExc_ValueError,
2707 "attempt to assign sequence of "
2708 "size %zd to extended slice of "
2709 "size %zd",
2710 PySequence_Fast_GET_SIZE(seq),
2711 slicelength);
2712 Py_DECREF(seq);
2713 return -1;
2716 if (!slicelength) {
2717 Py_DECREF(seq);
2718 return 0;
2721 garbage = (PyObject**)
2722 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2723 if (!garbage) {
2724 Py_DECREF(seq);
2725 PyErr_NoMemory();
2726 return -1;
2729 selfitems = self->ob_item;
2730 seqitems = PySequence_Fast_ITEMS(seq);
2731 for (cur = start, i = 0; i < slicelength;
2732 cur += step, i++) {
2733 garbage[i] = selfitems[cur];
2734 ins = seqitems[i];
2735 Py_INCREF(ins);
2736 selfitems[cur] = ins;
2739 for (i = 0; i < slicelength; i++) {
2740 Py_DECREF(garbage[i]);
2743 PyMem_FREE(garbage);
2744 Py_DECREF(seq);
2746 return 0;
2749 else {
2750 PyErr_Format(PyExc_TypeError,
2751 "list indices must be integers, not %.200s",
2752 item->ob_type->tp_name);
2753 return -1;
2757 static PyMappingMethods list_as_mapping = {
2758 (lenfunc)list_length,
2759 (binaryfunc)list_subscript,
2760 (objobjargproc)list_ass_subscript
2763 PyTypeObject PyList_Type = {
2764 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2765 "list",
2766 sizeof(PyListObject),
2768 (destructor)list_dealloc, /* tp_dealloc */
2769 (printfunc)list_print, /* tp_print */
2770 0, /* tp_getattr */
2771 0, /* tp_setattr */
2772 0, /* tp_compare */
2773 (reprfunc)list_repr, /* tp_repr */
2774 0, /* tp_as_number */
2775 &list_as_sequence, /* tp_as_sequence */
2776 &list_as_mapping, /* tp_as_mapping */
2777 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
2778 0, /* tp_call */
2779 0, /* tp_str */
2780 PyObject_GenericGetAttr, /* tp_getattro */
2781 0, /* tp_setattro */
2782 0, /* tp_as_buffer */
2783 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2784 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
2785 list_doc, /* tp_doc */
2786 (traverseproc)list_traverse, /* tp_traverse */
2787 (inquiry)list_clear, /* tp_clear */
2788 list_richcompare, /* tp_richcompare */
2789 0, /* tp_weaklistoffset */
2790 list_iter, /* tp_iter */
2791 0, /* tp_iternext */
2792 list_methods, /* tp_methods */
2793 0, /* tp_members */
2794 0, /* tp_getset */
2795 0, /* tp_base */
2796 0, /* tp_dict */
2797 0, /* tp_descr_get */
2798 0, /* tp_descr_set */
2799 0, /* tp_dictoffset */
2800 (initproc)list_init, /* tp_init */
2801 PyType_GenericAlloc, /* tp_alloc */
2802 PyType_GenericNew, /* tp_new */
2803 PyObject_GC_Del, /* tp_free */
2807 /*********************** List Iterator **************************/
2809 typedef struct {
2810 PyObject_HEAD
2811 long it_index;
2812 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
2813 } listiterobject;
2815 static PyObject *list_iter(PyObject *);
2816 static void listiter_dealloc(listiterobject *);
2817 static int listiter_traverse(listiterobject *, visitproc, void *);
2818 static PyObject *listiter_next(listiterobject *);
2819 static PyObject *listiter_len(listiterobject *);
2821 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
2823 static PyMethodDef listiter_methods[] = {
2824 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
2825 {NULL, NULL} /* sentinel */
2828 PyTypeObject PyListIter_Type = {
2829 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2830 "listiterator", /* tp_name */
2831 sizeof(listiterobject), /* tp_basicsize */
2832 0, /* tp_itemsize */
2833 /* methods */
2834 (destructor)listiter_dealloc, /* tp_dealloc */
2835 0, /* tp_print */
2836 0, /* tp_getattr */
2837 0, /* tp_setattr */
2838 0, /* tp_compare */
2839 0, /* tp_repr */
2840 0, /* tp_as_number */
2841 0, /* tp_as_sequence */
2842 0, /* tp_as_mapping */
2843 0, /* tp_hash */
2844 0, /* tp_call */
2845 0, /* tp_str */
2846 PyObject_GenericGetAttr, /* tp_getattro */
2847 0, /* tp_setattro */
2848 0, /* tp_as_buffer */
2849 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2850 0, /* tp_doc */
2851 (traverseproc)listiter_traverse, /* tp_traverse */
2852 0, /* tp_clear */
2853 0, /* tp_richcompare */
2854 0, /* tp_weaklistoffset */
2855 PyObject_SelfIter, /* tp_iter */
2856 (iternextfunc)listiter_next, /* tp_iternext */
2857 listiter_methods, /* tp_methods */
2858 0, /* tp_members */
2862 static PyObject *
2863 list_iter(PyObject *seq)
2865 listiterobject *it;
2867 if (!PyList_Check(seq)) {
2868 PyErr_BadInternalCall();
2869 return NULL;
2871 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2872 if (it == NULL)
2873 return NULL;
2874 it->it_index = 0;
2875 Py_INCREF(seq);
2876 it->it_seq = (PyListObject *)seq;
2877 _PyObject_GC_TRACK(it);
2878 return (PyObject *)it;
2881 static void
2882 listiter_dealloc(listiterobject *it)
2884 _PyObject_GC_UNTRACK(it);
2885 Py_XDECREF(it->it_seq);
2886 PyObject_GC_Del(it);
2889 static int
2890 listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2892 Py_VISIT(it->it_seq);
2893 return 0;
2896 static PyObject *
2897 listiter_next(listiterobject *it)
2899 PyListObject *seq;
2900 PyObject *item;
2902 assert(it != NULL);
2903 seq = it->it_seq;
2904 if (seq == NULL)
2905 return NULL;
2906 assert(PyList_Check(seq));
2908 if (it->it_index < PyList_GET_SIZE(seq)) {
2909 item = PyList_GET_ITEM(seq, it->it_index);
2910 ++it->it_index;
2911 Py_INCREF(item);
2912 return item;
2915 Py_DECREF(seq);
2916 it->it_seq = NULL;
2917 return NULL;
2920 static PyObject *
2921 listiter_len(listiterobject *it)
2923 Py_ssize_t len;
2924 if (it->it_seq) {
2925 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
2926 if (len >= 0)
2927 return PyInt_FromSsize_t(len);
2929 return PyInt_FromLong(0);
2931 /*********************** List Reverse Iterator **************************/
2933 typedef struct {
2934 PyObject_HEAD
2935 Py_ssize_t it_index;
2936 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
2937 } listreviterobject;
2939 static PyObject *list_reversed(PyListObject *, PyObject *);
2940 static void listreviter_dealloc(listreviterobject *);
2941 static int listreviter_traverse(listreviterobject *, visitproc, void *);
2942 static PyObject *listreviter_next(listreviterobject *);
2943 static PyObject *listreviter_len(listreviterobject *);
2945 static PyMethodDef listreviter_methods[] = {
2946 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
2947 {NULL, NULL} /* sentinel */
2950 PyTypeObject PyListRevIter_Type = {
2951 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2952 "listreverseiterator", /* tp_name */
2953 sizeof(listreviterobject), /* tp_basicsize */
2954 0, /* tp_itemsize */
2955 /* methods */
2956 (destructor)listreviter_dealloc, /* tp_dealloc */
2957 0, /* tp_print */
2958 0, /* tp_getattr */
2959 0, /* tp_setattr */
2960 0, /* tp_compare */
2961 0, /* tp_repr */
2962 0, /* tp_as_number */
2963 0, /* tp_as_sequence */
2964 0, /* tp_as_mapping */
2965 0, /* tp_hash */
2966 0, /* tp_call */
2967 0, /* tp_str */
2968 PyObject_GenericGetAttr, /* tp_getattro */
2969 0, /* tp_setattro */
2970 0, /* tp_as_buffer */
2971 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2972 0, /* tp_doc */
2973 (traverseproc)listreviter_traverse, /* tp_traverse */
2974 0, /* tp_clear */
2975 0, /* tp_richcompare */
2976 0, /* tp_weaklistoffset */
2977 PyObject_SelfIter, /* tp_iter */
2978 (iternextfunc)listreviter_next, /* tp_iternext */
2979 listreviter_methods, /* tp_methods */
2983 static PyObject *
2984 list_reversed(PyListObject *seq, PyObject *unused)
2986 listreviterobject *it;
2988 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
2989 if (it == NULL)
2990 return NULL;
2991 assert(PyList_Check(seq));
2992 it->it_index = PyList_GET_SIZE(seq) - 1;
2993 Py_INCREF(seq);
2994 it->it_seq = seq;
2995 PyObject_GC_Track(it);
2996 return (PyObject *)it;
2999 static void
3000 listreviter_dealloc(listreviterobject *it)
3002 PyObject_GC_UnTrack(it);
3003 Py_XDECREF(it->it_seq);
3004 PyObject_GC_Del(it);
3007 static int
3008 listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
3010 Py_VISIT(it->it_seq);
3011 return 0;
3014 static PyObject *
3015 listreviter_next(listreviterobject *it)
3017 PyObject *item;
3018 Py_ssize_t index = it->it_index;
3019 PyListObject *seq = it->it_seq;
3021 if (index>=0 && index < PyList_GET_SIZE(seq)) {
3022 item = PyList_GET_ITEM(seq, index);
3023 it->it_index--;
3024 Py_INCREF(item);
3025 return item;
3027 it->it_index = -1;
3028 if (seq != NULL) {
3029 it->it_seq = NULL;
3030 Py_DECREF(seq);
3032 return NULL;
3035 static PyObject *
3036 listreviter_len(listreviterobject *it)
3038 Py_ssize_t len = it->it_index + 1;
3039 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
3040 len = 0;
3041 return PyLong_FromSsize_t(len);