1 /* List object implementation */
8 #include <sys/types.h> /* For size_t */
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.
25 list_resize(PyListObject
*self
, Py_ssize_t newsize
)
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 self
->ob_size
= newsize
;
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
46 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
48 new_allocated
= (newsize
>> 3) + (newsize
< 9 ? 3 : 6) + newsize
;
51 items
= self
->ob_item
;
52 if (new_allocated
<= ((~(size_t)0) / sizeof(PyObject
*)))
53 PyMem_RESIZE(items
, PyObject
*, new_allocated
);
60 self
->ob_item
= items
;
61 self
->ob_size
= newsize
;
62 self
->allocated
= new_allocated
;
66 /* Empty list reuse scheme to save calls to malloc and free */
67 #define MAXFREELISTS 80
68 static PyListObject
*free_lists
[MAXFREELISTS
];
69 static int num_free_lists
= 0;
76 while (num_free_lists
) {
78 op
= free_lists
[num_free_lists
];
79 assert(PyList_CheckExact(op
));
85 PyList_New(Py_ssize_t size
)
91 PyErr_BadInternalCall();
94 nbytes
= size
* sizeof(PyObject
*);
95 /* Check for overflow */
96 if (nbytes
/ sizeof(PyObject
*) != (size_t)size
)
97 return PyErr_NoMemory();
100 op
= free_lists
[num_free_lists
];
101 _Py_NewReference((PyObject
*)op
);
103 op
= PyObject_GC_New(PyListObject
, &PyList_Type
);
110 op
->ob_item
= (PyObject
**) PyMem_MALLOC(nbytes
);
111 if (op
->ob_item
== NULL
)
112 return PyErr_NoMemory();
113 memset(op
->ob_item
, 0, nbytes
);
116 op
->allocated
= size
;
117 _PyObject_GC_TRACK(op
);
118 return (PyObject
*) op
;
122 PyList_Size(PyObject
*op
)
124 if (!PyList_Check(op
)) {
125 PyErr_BadInternalCall();
129 return ((PyListObject
*)op
) -> ob_size
;
132 static PyObject
*indexerr
= NULL
;
135 PyList_GetItem(PyObject
*op
, Py_ssize_t i
)
137 if (!PyList_Check(op
)) {
138 PyErr_BadInternalCall();
141 if (i
< 0 || i
>= ((PyListObject
*)op
) -> ob_size
) {
142 if (indexerr
== NULL
)
143 indexerr
= PyString_FromString(
144 "list index out of range");
145 PyErr_SetObject(PyExc_IndexError
, indexerr
);
148 return ((PyListObject
*)op
) -> ob_item
[i
];
152 PyList_SetItem(register PyObject
*op
, register Py_ssize_t i
,
153 register PyObject
*newitem
)
155 register PyObject
*olditem
;
156 register PyObject
**p
;
157 if (!PyList_Check(op
)) {
159 PyErr_BadInternalCall();
162 if (i
< 0 || i
>= ((PyListObject
*)op
) -> ob_size
) {
164 PyErr_SetString(PyExc_IndexError
,
165 "list assignment index out of range");
168 p
= ((PyListObject
*)op
) -> ob_item
+ i
;
176 ins1(PyListObject
*self
, Py_ssize_t where
, PyObject
*v
)
178 Py_ssize_t i
, n
= self
->ob_size
;
181 PyErr_BadInternalCall();
184 if (n
== PY_SSIZE_T_MAX
) {
185 PyErr_SetString(PyExc_OverflowError
,
186 "cannot add more objects to list");
190 if (list_resize(self
, n
+1) == -1)
200 items
= self
->ob_item
;
201 for (i
= n
; --i
>= where
; )
202 items
[i
+1] = items
[i
];
209 PyList_Insert(PyObject
*op
, Py_ssize_t where
, PyObject
*newitem
)
211 if (!PyList_Check(op
)) {
212 PyErr_BadInternalCall();
215 return ins1((PyListObject
*)op
, where
, newitem
);
219 app1(PyListObject
*self
, PyObject
*v
)
221 Py_ssize_t n
= PyList_GET_SIZE(self
);
224 if (n
== PY_SSIZE_T_MAX
) {
225 PyErr_SetString(PyExc_OverflowError
,
226 "cannot add more objects to list");
230 if (list_resize(self
, n
+1) == -1)
234 PyList_SET_ITEM(self
, n
, v
);
239 PyList_Append(PyObject
*op
, PyObject
*newitem
)
241 if (PyList_Check(op
) && (newitem
!= NULL
))
242 return app1((PyListObject
*)op
, newitem
);
243 PyErr_BadInternalCall();
250 list_dealloc(PyListObject
*op
)
253 PyObject_GC_UnTrack(op
);
254 Py_TRASHCAN_SAFE_BEGIN(op
)
255 if (op
->ob_item
!= NULL
) {
256 /* Do it backwards, for Christian Tismer.
257 There's a simple test case where somehow this reduces
258 thrashing when a *very* large list is created and
259 immediately deleted. */
262 Py_XDECREF(op
->ob_item
[i
]);
264 PyMem_FREE(op
->ob_item
);
266 if (num_free_lists
< MAXFREELISTS
&& PyList_CheckExact(op
))
267 free_lists
[num_free_lists
++] = op
;
269 op
->ob_type
->tp_free((PyObject
*)op
);
270 Py_TRASHCAN_SAFE_END(op
)
274 list_print(PyListObject
*op
, FILE *fp
, int flags
)
279 rc
= Py_ReprEnter((PyObject
*)op
);
283 fprintf(fp
, "[...]");
287 for (i
= 0; i
< op
->ob_size
; i
++) {
290 if (PyObject_Print(op
->ob_item
[i
], fp
, 0) != 0) {
291 Py_ReprLeave((PyObject
*)op
);
296 Py_ReprLeave((PyObject
*)op
);
301 list_repr(PyListObject
*v
)
305 PyObject
*pieces
= NULL
, *result
= NULL
;
307 i
= Py_ReprEnter((PyObject
*)v
);
309 return i
> 0 ? PyString_FromString("[...]") : NULL
;
312 if (v
->ob_size
== 0) {
313 result
= PyString_FromString("[]");
317 pieces
= PyList_New(0);
321 /* Do repr() on each element. Note that this may mutate the list,
322 so must refetch the list size on each iteration. */
323 for (i
= 0; i
< v
->ob_size
; ++i
) {
325 s
= PyObject_Repr(v
->ob_item
[i
]);
328 status
= PyList_Append(pieces
, s
);
329 Py_DECREF(s
); /* append created a new ref */
334 /* Add "[]" decorations to the first and last items. */
335 assert(PyList_GET_SIZE(pieces
) > 0);
336 s
= PyString_FromString("[");
339 temp
= PyList_GET_ITEM(pieces
, 0);
340 PyString_ConcatAndDel(&s
, temp
);
341 PyList_SET_ITEM(pieces
, 0, s
);
345 s
= PyString_FromString("]");
348 temp
= PyList_GET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1);
349 PyString_ConcatAndDel(&temp
, s
);
350 PyList_SET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1, temp
);
354 /* Paste them all together with ", " between. */
355 s
= PyString_FromString(", ");
358 result
= _PyString_Join(s
, pieces
);
363 Py_ReprLeave((PyObject
*)v
);
368 list_length(PyListObject
*a
)
374 list_contains(PyListObject
*a
, PyObject
*el
)
379 for (i
= 0, cmp
= 0 ; cmp
== 0 && i
< a
->ob_size
; ++i
)
380 cmp
= PyObject_RichCompareBool(el
, PyList_GET_ITEM(a
, i
),
386 list_item(PyListObject
*a
, Py_ssize_t i
)
388 if (i
< 0 || i
>= a
->ob_size
) {
389 if (indexerr
== NULL
)
390 indexerr
= PyString_FromString(
391 "list index out of range");
392 PyErr_SetObject(PyExc_IndexError
, indexerr
);
395 Py_INCREF(a
->ob_item
[i
]);
396 return a
->ob_item
[i
];
400 list_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
403 PyObject
**src
, **dest
;
407 else if (ilow
> a
->ob_size
)
411 else if (ihigh
> a
->ob_size
)
414 np
= (PyListObject
*) PyList_New(len
);
418 src
= a
->ob_item
+ ilow
;
420 for (i
= 0; i
< len
; i
++) {
421 PyObject
*v
= src
[i
];
425 return (PyObject
*)np
;
429 PyList_GetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
431 if (!PyList_Check(a
)) {
432 PyErr_BadInternalCall();
435 return list_slice((PyListObject
*)a
, ilow
, ihigh
);
439 list_concat(PyListObject
*a
, PyObject
*bb
)
443 PyObject
**src
, **dest
;
445 if (!PyList_Check(bb
)) {
446 PyErr_Format(PyExc_TypeError
,
447 "can only concatenate list (not \"%.200s\") to list",
448 bb
->ob_type
->tp_name
);
451 #define b ((PyListObject *)bb)
452 size
= a
->ob_size
+ b
->ob_size
;
454 return PyErr_NoMemory();
455 np
= (PyListObject
*) PyList_New(size
);
461 for (i
= 0; i
< a
->ob_size
; i
++) {
462 PyObject
*v
= src
[i
];
467 dest
= np
->ob_item
+ a
->ob_size
;
468 for (i
= 0; i
< b
->ob_size
; i
++) {
469 PyObject
*v
= src
[i
];
473 return (PyObject
*)np
;
478 list_repeat(PyListObject
*a
, Py_ssize_t n
)
483 PyObject
**p
, **items
;
487 size
= a
->ob_size
* n
;
489 return PyList_New(0);
490 if (n
&& size
/n
!= a
->ob_size
)
491 return PyErr_NoMemory();
492 np
= (PyListObject
*) PyList_New(size
);
497 if (a
->ob_size
== 1) {
498 elem
= a
->ob_item
[0];
499 for (i
= 0; i
< n
; i
++) {
503 return (PyObject
*) np
;
507 for (i
= 0; i
< n
; i
++) {
508 for (j
= 0; j
< a
->ob_size
; j
++) {
514 return (PyObject
*) np
;
518 list_clear(PyListObject
*a
)
521 PyObject
**item
= a
->ob_item
;
523 /* Because XDECREF can recursively invoke operations on
524 this list, we make it empty first. */
534 /* Never fails; the return value can be ignored.
535 Note that there is no guarantee that the list is actually empty
536 at this point, because XDECREF may have populated it again! */
540 /* a[ilow:ihigh] = v if v != NULL.
541 * del a[ilow:ihigh] if v == NULL.
543 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
544 * guaranteed the call cannot fail.
547 list_ass_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
549 /* Because [X]DECREF can recursively invoke list operations on
550 this list, we must postpone all [X]DECREF activity until
551 after the list is back in its canonical shape. Therefore
552 we must allocate an additional array, 'recycle', into which
553 we temporarily copy the items that are deleted from the
555 PyObject
*recycle_on_stack
[8];
556 PyObject
**recycle
= recycle_on_stack
; /* will allocate more if needed */
558 PyObject
**vitem
= NULL
;
559 PyObject
*v_as_SF
= NULL
; /* PySequence_Fast(v) */
560 Py_ssize_t n
; /* # of elements in replacement list */
561 Py_ssize_t norig
; /* # of elements in list getting replaced */
562 Py_ssize_t d
; /* Change in size */
565 int result
= -1; /* guilty until proved innocent */
566 #define b ((PyListObject *)v)
571 /* Special case "a[i:j] = a" -- copy b first */
572 v
= list_slice(b
, 0, b
->ob_size
);
575 result
= list_ass_slice(a
, ilow
, ihigh
, v
);
579 v_as_SF
= PySequence_Fast(v
, "can only assign an iterable");
582 n
= PySequence_Fast_GET_SIZE(v_as_SF
);
583 vitem
= PySequence_Fast_ITEMS(v_as_SF
);
587 else if (ilow
> a
->ob_size
)
592 else if (ihigh
> a
->ob_size
)
595 norig
= ihigh
- ilow
;
598 if (a
->ob_size
+ d
== 0) {
600 return list_clear(a
);
603 /* recycle the items that we are about to remove */
604 s
= norig
* sizeof(PyObject
*);
605 if (s
> sizeof(recycle_on_stack
)) {
606 recycle
= (PyObject
**)PyMem_MALLOC(s
);
607 if (recycle
== NULL
) {
612 memcpy(recycle
, &item
[ilow
], s
);
614 if (d
< 0) { /* Delete -d items */
615 memmove(&item
[ihigh
+d
], &item
[ihigh
],
616 (a
->ob_size
- ihigh
)*sizeof(PyObject
*));
617 list_resize(a
, a
->ob_size
+ d
);
620 else if (d
> 0) { /* Insert d items */
622 if (list_resize(a
, k
+d
) < 0)
625 memmove(&item
[ihigh
+d
], &item
[ihigh
],
626 (k
- ihigh
)*sizeof(PyObject
*));
628 for (k
= 0; k
< n
; k
++, ilow
++) {
629 PyObject
*w
= vitem
[k
];
633 for (k
= norig
- 1; k
>= 0; --k
)
634 Py_XDECREF(recycle
[k
]);
637 if (recycle
!= recycle_on_stack
)
645 PyList_SetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
647 if (!PyList_Check(a
)) {
648 PyErr_BadInternalCall();
651 return list_ass_slice((PyListObject
*)a
, ilow
, ihigh
, v
);
655 list_inplace_repeat(PyListObject
*self
, Py_ssize_t n
)
658 Py_ssize_t size
, i
, j
, p
;
661 size
= PyList_GET_SIZE(self
);
664 return (PyObject
*)self
;
668 (void)list_clear(self
);
670 return (PyObject
*)self
;
673 if (list_resize(self
, size
*n
) == -1)
677 items
= self
->ob_item
;
678 for (i
= 1; i
< n
; i
++) { /* Start counting at 1, not 0 */
679 for (j
= 0; j
< size
; j
++) {
680 PyObject
*o
= items
[j
];
686 return (PyObject
*)self
;
690 list_ass_item(PyListObject
*a
, Py_ssize_t i
, PyObject
*v
)
693 if (i
< 0 || i
>= a
->ob_size
) {
694 PyErr_SetString(PyExc_IndexError
,
695 "list assignment index out of range");
699 return list_ass_slice(a
, i
, i
+1, v
);
701 old_value
= a
->ob_item
[i
];
703 Py_DECREF(old_value
);
708 listinsert(PyListObject
*self
, PyObject
*args
)
712 if (!PyArg_ParseTuple(args
, "nO:insert", &i
, &v
))
714 if (ins1(self
, i
, v
) == 0)
720 listappend(PyListObject
*self
, PyObject
*v
)
722 if (app1(self
, v
) == 0)
728 listextend(PyListObject
*self
, PyObject
*b
)
730 PyObject
*it
; /* iter(v) */
731 Py_ssize_t m
; /* size of self */
732 Py_ssize_t n
; /* guess for size of b */
733 Py_ssize_t mn
; /* m + n */
735 PyObject
*(*iternext
)(PyObject
*);
738 1) lists and tuples which can use PySequence_Fast ops
739 2) extending self to self requires making a copy first
741 if (PyList_CheckExact(b
) || PyTuple_CheckExact(b
) || (PyObject
*)self
== b
) {
742 PyObject
**src
, **dest
;
743 b
= PySequence_Fast(b
, "argument must be iterable");
746 n
= PySequence_Fast_GET_SIZE(b
);
748 /* short circuit when b is empty */
753 if (list_resize(self
, m
+ n
) == -1) {
757 /* note that we may still have self == b here for the
758 * situation a.extend(a), but the following code works
759 * in that case too. Just make sure to resize self
760 * before calling PySequence_Fast_ITEMS.
762 /* populate the end of self with b's items */
763 src
= PySequence_Fast_ITEMS(b
);
764 dest
= self
->ob_item
+ m
;
765 for (i
= 0; i
< n
; i
++) {
766 PyObject
*o
= src
[i
];
774 it
= PyObject_GetIter(b
);
777 iternext
= *it
->ob_type
->tp_iternext
;
779 /* Guess a result list size. */
780 n
= _PyObject_LengthHint(b
);
782 if (!PyErr_ExceptionMatches(PyExc_TypeError
) &&
783 !PyErr_ExceptionMatches(PyExc_AttributeError
)) {
788 n
= 8; /* arbitrary */
794 if (list_resize(self
, mn
) == -1)
796 /* Make the list sane again. */
799 /* Else m + n overflowed; on the chance that n lied, and there really
800 * is enough room, ignore it. If n was telling the truth, we'll
801 * eventually run out of memory during the loop.
804 /* Run iterator to exhaustion. */
806 PyObject
*item
= iternext(it
);
808 if (PyErr_Occurred()) {
809 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
816 if (self
->ob_size
< self
->allocated
) {
818 PyList_SET_ITEM(self
, self
->ob_size
, item
);
822 int status
= app1(self
, item
);
823 Py_DECREF(item
); /* append creates a new ref */
829 /* Cut back result list if initial guess was too large. */
830 if (self
->ob_size
< self
->allocated
)
831 list_resize(self
, self
->ob_size
); /* shrinking can't fail */
842 _PyList_Extend(PyListObject
*self
, PyObject
*b
)
844 return listextend(self
, b
);
848 list_inplace_concat(PyListObject
*self
, PyObject
*other
)
852 result
= listextend(self
, other
);
857 return (PyObject
*)self
;
861 listpop(PyListObject
*self
, PyObject
*args
)
864 PyObject
*v
, *arg
= NULL
;
867 if (!PyArg_UnpackTuple(args
, "pop", 0, 1, &arg
))
870 if (PyInt_Check(arg
))
871 i
= PyInt_AS_LONG((PyIntObject
*) arg
);
872 else if (!PyArg_ParseTuple(args
, "|n:pop", &i
))
875 if (self
->ob_size
== 0) {
876 /* Special-case most common failure cause */
877 PyErr_SetString(PyExc_IndexError
, "pop from empty list");
882 if (i
< 0 || i
>= self
->ob_size
) {
883 PyErr_SetString(PyExc_IndexError
, "pop index out of range");
886 v
= self
->ob_item
[i
];
887 if (i
== self
->ob_size
- 1) {
888 status
= list_resize(self
, self
->ob_size
- 1);
890 return v
; /* and v now owns the reference the list had */
893 status
= list_ass_slice(self
, i
, i
+1, (PyObject
*)NULL
);
895 /* Use status, so that in a release build compilers don't
896 * complain about the unused name.
903 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
905 reverse_slice(PyObject
**lo
, PyObject
**hi
)
919 /* Lots of code for an adaptive, stable, natural mergesort. There are many
920 * pieces to this algorithm; read listsort.txt for overviews and details.
923 /* Comparison function. Takes care of calling a user-supplied
924 * comparison function (any callable Python object), which must not be
925 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
926 * with Py_LT if you know it's NULL).
927 * Returns -1 on error, 1 if x < y, 0 if x >= y.
930 islt(PyObject
*x
, PyObject
*y
, PyObject
*compare
)
936 assert(compare
!= NULL
);
937 /* Call the user's comparison function and translate the 3-way
938 * result into true or false (or error).
940 args
= PyTuple_New(2);
945 PyTuple_SET_ITEM(args
, 0, x
);
946 PyTuple_SET_ITEM(args
, 1, y
);
947 res
= PyObject_Call(compare
, args
, NULL
);
951 if (!PyInt_Check(res
)) {
953 PyErr_SetString(PyExc_TypeError
,
954 "comparison function must return int");
957 i
= PyInt_AsLong(res
);
962 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
963 * islt. This avoids a layer of function call in the usual case, and
964 * sorting does many comparisons.
965 * Returns -1 on error, 1 if x < y, 0 if x >= y.
967 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
968 PyObject_RichCompareBool(X, Y, Py_LT) : \
971 /* Compare X to Y via "<". Goto "fail" if the comparison raises an
972 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
973 started. It makes more sense in context <wink>. X and Y are PyObject*s.
975 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
978 /* binarysort is the best method for sorting small arrays: it does
979 few compares, but can do data movement quadratic in the number of
981 [lo, hi) is a contiguous slice of a list, and is sorted via
982 binary insertion. This sort is stable.
983 On entry, must have lo <= start <= hi, and that [lo, start) is already
984 sorted (pass start == lo if you don't know!).
985 If islt() complains return -1, else 0.
986 Even in case of error, the output slice will be some permutation of
987 the input (nothing is lost or duplicated).
990 binarysort(PyObject
**lo
, PyObject
**hi
, PyObject
**start
, PyObject
*compare
)
991 /* compare -- comparison function object, or NULL for default */
993 register Py_ssize_t k
;
994 register PyObject
**l
, **p
, **r
;
995 register PyObject
*pivot
;
997 assert(lo
<= start
&& start
<= hi
);
998 /* assert [lo, start) is sorted */
1001 for (; start
< hi
; ++start
) {
1002 /* set l to where *start belongs */
1007 * pivot >= all in [lo, l).
1008 * pivot < all in [r, start).
1009 * The second is vacuously true at the start.
1013 p
= l
+ ((r
- l
) >> 1);
1020 /* The invariants still hold, so pivot >= all in [lo, l) and
1021 pivot < all in [l, start), so pivot belongs at l. Note
1022 that if there are elements equal to pivot, l points to the
1023 first slot after them -- that's why this sort is stable.
1024 Slide over to make room.
1025 Caution: using memmove is much slower under MSVC 5;
1026 we're not usually moving many slots. */
1027 for (p
= start
; p
> l
; --p
)
1038 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1039 is required on entry. "A run" is the longest ascending sequence, with
1041 lo[0] <= lo[1] <= lo[2] <= ...
1043 or the longest descending sequence, with
1045 lo[0] > lo[1] > lo[2] > ...
1047 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1048 For its intended use in a stable mergesort, the strictness of the defn of
1049 "descending" is needed so that the caller can safely reverse a descending
1050 sequence without violating stability (strict > ensures there are no equal
1051 elements to get out of order).
1053 Returns -1 in case of error.
1056 count_run(PyObject
**lo
, PyObject
**hi
, PyObject
*compare
, int *descending
)
1068 IFLT(*lo
, *(lo
-1)) {
1070 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1078 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1090 Locate the proper position of key in a sorted vector; if the vector contains
1091 an element equal to key, return the position immediately to the left of
1092 the leftmost equal element. [gallop_right() does the same except returns
1093 the position to the right of the rightmost equal element (if any).]
1095 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
1097 "hint" is an index at which to begin the search, 0 <= hint < n. The closer
1098 hint is to the final result, the faster this runs.
1100 The return value is the int k in 0..n such that
1102 a[k-1] < key <= a[k]
1104 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1105 key belongs at index k; or, IOW, the first k elements of a should precede
1106 key, and the last n-k should follow key.
1108 Returns -1 on error. See listsort.txt for info on the method.
1111 gallop_left(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1117 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1123 /* a[hint] < key -- gallop right, until
1124 * a[hint + lastofs] < key <= a[hint + ofs]
1126 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1127 while (ofs
< maxofs
) {
1130 ofs
= (ofs
<< 1) + 1;
1131 if (ofs
<= 0) /* int overflow */
1134 else /* key <= a[hint + ofs] */
1139 /* Translate back to offsets relative to &a[0]. */
1144 /* key <= a[hint] -- gallop left, until
1145 * a[hint - ofs] < key <= a[hint - lastofs]
1147 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1148 while (ofs
< maxofs
) {
1151 /* key <= a[hint - ofs] */
1153 ofs
= (ofs
<< 1) + 1;
1154 if (ofs
<= 0) /* int overflow */
1159 /* Translate back to positive offsets relative to &a[0]. */
1161 lastofs
= hint
- ofs
;
1166 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1167 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1168 * right of lastofs but no farther right than ofs. Do a binary
1169 * search, with invariant a[lastofs-1] < key <= a[ofs].
1172 while (lastofs
< ofs
) {
1173 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1176 lastofs
= m
+1; /* a[m] < key */
1178 ofs
= m
; /* key <= a[m] */
1180 assert(lastofs
== ofs
); /* so a[ofs-1] < key <= a[ofs] */
1188 Exactly like gallop_left(), except that if key already exists in a[0:n],
1189 finds the position immediately to the right of the rightmost equal value.
1191 The return value is the int k in 0..n such that
1193 a[k-1] <= key < a[k]
1197 The code duplication is massive, but this is enough different given that
1198 we're sticking to "<" comparisons that it's much harder to follow if
1199 written as one routine with yet another "left or right?" flag.
1202 gallop_right(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1208 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1214 /* key < a[hint] -- gallop left, until
1215 * a[hint - ofs] <= key < a[hint - lastofs]
1217 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1218 while (ofs
< maxofs
) {
1219 IFLT(key
, *(a
-ofs
)) {
1221 ofs
= (ofs
<< 1) + 1;
1222 if (ofs
<= 0) /* int overflow */
1225 else /* a[hint - ofs] <= key */
1230 /* Translate back to positive offsets relative to &a[0]. */
1232 lastofs
= hint
- ofs
;
1236 /* a[hint] <= key -- gallop right, until
1237 * a[hint + lastofs] <= key < a[hint + ofs]
1239 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1240 while (ofs
< maxofs
) {
1243 /* a[hint + ofs] <= key */
1245 ofs
= (ofs
<< 1) + 1;
1246 if (ofs
<= 0) /* int overflow */
1251 /* Translate back to offsets relative to &a[0]. */
1257 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1258 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1259 * right of lastofs but no farther right than ofs. Do a binary
1260 * search, with invariant a[lastofs-1] <= key < a[ofs].
1263 while (lastofs
< ofs
) {
1264 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1267 ofs
= m
; /* key < a[m] */
1269 lastofs
= m
+1; /* a[m] <= key */
1271 assert(lastofs
== ofs
); /* so a[ofs-1] <= key < a[ofs] */
1278 /* The maximum number of entries in a MergeState's pending-runs stack.
1279 * This is enough to sort arrays of size up to about
1280 * 32 * phi ** MAX_MERGE_PENDING
1281 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1282 * with 2**64 elements.
1284 #define MAX_MERGE_PENDING 85
1286 /* When we get into galloping mode, we stay there until both runs win less
1287 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1289 #define MIN_GALLOP 7
1291 /* Avoid malloc for small temp arrays. */
1292 #define MERGESTATE_TEMP_SIZE 256
1294 /* One MergeState exists on the stack per invocation of mergesort. It's just
1295 * a convenient way to pass state around among the helper functions.
1302 typedef struct s_MergeState
{
1303 /* The user-supplied comparison function. or NULL if none given. */
1306 /* This controls when we get *into* galloping mode. It's initialized
1307 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1308 * random data, and lower for highly structured data.
1310 Py_ssize_t min_gallop
;
1312 /* 'a' is temp storage to help with merges. It contains room for
1315 PyObject
**a
; /* may point to temparray below */
1318 /* A stack of n pending runs yet to be merged. Run #i starts at
1319 * address base[i] and extends for len[i] elements. It's always
1320 * true (so long as the indices are in bounds) that
1322 * pending[i].base + pending[i].len == pending[i+1].base
1324 * so we could cut the storage for this, but it's a minor amount,
1325 * and keeping all the info explicit simplifies the code.
1328 struct s_slice pending
[MAX_MERGE_PENDING
];
1330 /* 'a' points to this when possible, rather than muck with malloc. */
1331 PyObject
*temparray
[MERGESTATE_TEMP_SIZE
];
1334 /* Conceptually a MergeState's constructor. */
1336 merge_init(MergeState
*ms
, PyObject
*compare
)
1339 ms
->compare
= compare
;
1340 ms
->a
= ms
->temparray
;
1341 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1343 ms
->min_gallop
= MIN_GALLOP
;
1346 /* Free all the temp memory owned by the MergeState. This must be called
1347 * when you're done with a MergeState, and may be called before then if
1348 * you want to free the temp memory early.
1351 merge_freemem(MergeState
*ms
)
1354 if (ms
->a
!= ms
->temparray
)
1356 ms
->a
= ms
->temparray
;
1357 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1360 /* Ensure enough temp memory for 'need' array slots is available.
1361 * Returns 0 on success and -1 if the memory can't be gotten.
1364 merge_getmem(MergeState
*ms
, Py_ssize_t need
)
1367 if (need
<= ms
->alloced
)
1369 /* Don't realloc! That can cost cycles to copy the old data, but
1370 * we don't care what's in the block.
1373 ms
->a
= (PyObject
**)PyMem_Malloc(need
* sizeof(PyObject
*));
1379 merge_freemem(ms
); /* reset to sane state */
1382 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1383 merge_getmem(MS, NEED))
1385 /* Merge the na elements starting at pa with the nb elements starting at pb
1386 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1387 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1388 * merge, and should have na <= nb. See listsort.txt for more info.
1389 * Return 0 if successful, -1 if error.
1392 merge_lo(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
,
1393 PyObject
**pb
, Py_ssize_t nb
)
1398 int result
= -1; /* guilty until proved innocent */
1399 Py_ssize_t min_gallop
= ms
->min_gallop
;
1401 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1402 if (MERGE_GETMEM(ms
, na
) < 0)
1404 memcpy(ms
->a
, pa
, na
* sizeof(PyObject
*));
1415 compare
= ms
->compare
;
1417 Py_ssize_t acount
= 0; /* # of times A won in a row */
1418 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1420 /* Do the straightforward thing until (if ever) one run
1421 * appears to win consistently.
1424 assert(na
> 1 && nb
> 0);
1425 k
= ISLT(*pb
, *pa
, compare
);
1435 if (bcount
>= min_gallop
)
1445 if (acount
>= min_gallop
)
1450 /* One run is winning so consistently that galloping may
1451 * be a huge win. So try that, and continue galloping until
1452 * (if ever) neither run appears to be winning consistently
1457 assert(na
> 1 && nb
> 0);
1458 min_gallop
-= min_gallop
> 1;
1459 ms
->min_gallop
= min_gallop
;
1460 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1465 memcpy(dest
, pa
, k
* sizeof(PyObject
*));
1471 /* na==0 is impossible now if the comparison
1472 * function is consistent, but we can't assume
1483 k
= gallop_left(*pa
, pb
, nb
, 0, compare
);
1488 memmove(dest
, pb
, k
* sizeof(PyObject
*));
1499 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1500 ++min_gallop
; /* penalize it for leaving galloping mode */
1501 ms
->min_gallop
= min_gallop
;
1507 memcpy(dest
, pa
, na
* sizeof(PyObject
*));
1510 assert(na
== 1 && nb
> 0);
1511 /* The last element of pa belongs at the end of the merge. */
1512 memmove(dest
, pb
, nb
* sizeof(PyObject
*));
1517 /* Merge the na elements starting at pa with the nb elements starting at pb
1518 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1519 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1520 * merge, and should have na >= nb. See listsort.txt for more info.
1521 * Return 0 if successful, -1 if error.
1524 merge_hi(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
, PyObject
**pb
, Py_ssize_t nb
)
1529 int result
= -1; /* guilty until proved innocent */
1532 Py_ssize_t min_gallop
= ms
->min_gallop
;
1534 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1535 if (MERGE_GETMEM(ms
, nb
) < 0)
1538 memcpy(ms
->a
, pb
, nb
* sizeof(PyObject
*));
1541 pb
= ms
->a
+ nb
- 1;
1551 compare
= ms
->compare
;
1553 Py_ssize_t acount
= 0; /* # of times A won in a row */
1554 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1556 /* Do the straightforward thing until (if ever) one run
1557 * appears to win consistently.
1560 assert(na
> 0 && nb
> 1);
1561 k
= ISLT(*pb
, *pa
, compare
);
1571 if (acount
>= min_gallop
)
1581 if (bcount
>= min_gallop
)
1586 /* One run is winning so consistently that galloping may
1587 * be a huge win. So try that, and continue galloping until
1588 * (if ever) neither run appears to be winning consistently
1593 assert(na
> 0 && nb
> 1);
1594 min_gallop
-= min_gallop
> 1;
1595 ms
->min_gallop
= min_gallop
;
1596 k
= gallop_right(*pb
, basea
, na
, na
-1, compare
);
1604 memmove(dest
+1, pa
+1, k
* sizeof(PyObject
*));
1614 k
= gallop_left(*pa
, baseb
, nb
, nb
-1, compare
);
1622 memcpy(dest
+1, pb
+1, k
* sizeof(PyObject
*));
1626 /* nb==0 is impossible now if the comparison
1627 * function is consistent, but we can't assume
1637 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1638 ++min_gallop
; /* penalize it for leaving galloping mode */
1639 ms
->min_gallop
= min_gallop
;
1645 memcpy(dest
-(nb
-1), baseb
, nb
* sizeof(PyObject
*));
1648 assert(nb
== 1 && na
> 0);
1649 /* The first element of pb belongs at the front of the merge. */
1652 memmove(dest
+1, pa
+1, na
* sizeof(PyObject
*));
1657 /* Merge the two runs at stack indices i and i+1.
1658 * Returns 0 on success, -1 on error.
1661 merge_at(MergeState
*ms
, Py_ssize_t i
)
1663 PyObject
**pa
, **pb
;
1671 assert(i
== ms
->n
- 2 || i
== ms
->n
- 3);
1673 pa
= ms
->pending
[i
].base
;
1674 na
= ms
->pending
[i
].len
;
1675 pb
= ms
->pending
[i
+1].base
;
1676 nb
= ms
->pending
[i
+1].len
;
1677 assert(na
> 0 && nb
> 0);
1678 assert(pa
+ na
== pb
);
1680 /* Record the length of the combined runs; if i is the 3rd-last
1681 * run now, also slide over the last run (which isn't involved
1682 * in this merge). The current run i+1 goes away in any case.
1684 ms
->pending
[i
].len
= na
+ nb
;
1686 ms
->pending
[i
+1] = ms
->pending
[i
+2];
1689 /* Where does b start in a? Elements in a before that can be
1690 * ignored (already in place).
1692 compare
= ms
->compare
;
1693 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1701 /* Where does a end in b? Elements in b after that can be
1702 * ignored (already in place).
1704 nb
= gallop_left(pa
[na
-1], pb
, nb
, nb
-1, compare
);
1708 /* Merge what remains of the runs, using a temp array with
1709 * min(na, nb) elements.
1712 return merge_lo(ms
, pa
, na
, pb
, nb
);
1714 return merge_hi(ms
, pa
, na
, pb
, nb
);
1717 /* Examine the stack of runs waiting to be merged, merging adjacent runs
1718 * until the stack invariants are re-established:
1720 * 1. len[-3] > len[-2] + len[-1]
1721 * 2. len[-2] > len[-1]
1723 * See listsort.txt for more info.
1725 * Returns 0 on success, -1 on error.
1728 merge_collapse(MergeState
*ms
)
1730 struct s_slice
*p
= ms
->pending
;
1734 Py_ssize_t n
= ms
->n
- 2;
1735 if (n
> 0 && p
[n
-1].len
<= p
[n
].len
+ p
[n
+1].len
) {
1736 if (p
[n
-1].len
< p
[n
+1].len
)
1738 if (merge_at(ms
, n
) < 0)
1741 else if (p
[n
].len
<= p
[n
+1].len
) {
1742 if (merge_at(ms
, n
) < 0)
1751 /* Regardless of invariants, merge all runs on the stack until only one
1752 * remains. This is used at the end of the mergesort.
1754 * Returns 0 on success, -1 on error.
1757 merge_force_collapse(MergeState
*ms
)
1759 struct s_slice
*p
= ms
->pending
;
1763 Py_ssize_t n
= ms
->n
- 2;
1764 if (n
> 0 && p
[n
-1].len
< p
[n
+1].len
)
1766 if (merge_at(ms
, n
) < 0)
1772 /* Compute a good value for the minimum run length; natural runs shorter
1773 * than this are boosted artificially via binary insertion.
1775 * If n < 64, return n (it's too small to bother with fancy stuff).
1776 * Else if n is an exact power of 2, return 32.
1777 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1778 * strictly less than, an exact power of 2.
1780 * See listsort.txt for more info.
1783 merge_compute_minrun(Py_ssize_t n
)
1785 Py_ssize_t r
= 0; /* becomes 1 if any 1 bits are shifted off */
1795 /* Special wrapper to support stable sorting using the decorate-sort-undecorate
1796 pattern. Holds a key which is used for comparisons and the original record
1797 which is returned during the undecorate phase. By exposing only the key
1798 during comparisons, the underlying sort stability characteristics are left
1799 unchanged. Also, if a custom comparison function is used, it will only see
1800 the key instead of a full record. */
1806 } sortwrapperobject
;
1808 PyDoc_STRVAR(sortwrapper_doc
, "Object wrapper with a custom sort key.");
1810 sortwrapper_richcompare(sortwrapperobject
*, sortwrapperobject
*, int);
1812 sortwrapper_dealloc(sortwrapperobject
*);
1814 static PyTypeObject sortwrapper_type
= {
1815 PyObject_HEAD_INIT(&PyType_Type
)
1817 "sortwrapper", /* tp_name */
1818 sizeof(sortwrapperobject
), /* tp_basicsize */
1819 0, /* tp_itemsize */
1821 (destructor
)sortwrapper_dealloc
, /* tp_dealloc */
1827 0, /* tp_as_number */
1828 0, /* tp_as_sequence */
1829 0, /* tp_as_mapping */
1833 PyObject_GenericGetAttr
, /* tp_getattro */
1834 0, /* tp_setattro */
1835 0, /* tp_as_buffer */
1836 Py_TPFLAGS_DEFAULT
|
1837 Py_TPFLAGS_HAVE_RICHCOMPARE
, /* tp_flags */
1838 sortwrapper_doc
, /* tp_doc */
1839 0, /* tp_traverse */
1841 (richcmpfunc
)sortwrapper_richcompare
, /* tp_richcompare */
1846 sortwrapper_richcompare(sortwrapperobject
*a
, sortwrapperobject
*b
, int op
)
1848 if (!PyObject_TypeCheck(b
, &sortwrapper_type
)) {
1849 PyErr_SetString(PyExc_TypeError
,
1850 "expected a sortwrapperobject");
1853 return PyObject_RichCompare(a
->key
, b
->key
, op
);
1857 sortwrapper_dealloc(sortwrapperobject
*so
)
1859 Py_XDECREF(so
->key
);
1860 Py_XDECREF(so
->value
);
1864 /* Returns a new reference to a sortwrapper.
1865 Consumes the references to the two underlying objects. */
1868 build_sortwrapper(PyObject
*key
, PyObject
*value
)
1870 sortwrapperobject
*so
;
1872 so
= PyObject_New(sortwrapperobject
, &sortwrapper_type
);
1877 return (PyObject
*)so
;
1880 /* Returns a new reference to the value underlying the wrapper. */
1882 sortwrapper_getvalue(PyObject
*so
)
1886 if (!PyObject_TypeCheck(so
, &sortwrapper_type
)) {
1887 PyErr_SetString(PyExc_TypeError
,
1888 "expected a sortwrapperobject");
1891 value
= ((sortwrapperobject
*)so
)->value
;
1896 /* Wrapper for user specified cmp functions in combination with a
1897 specified key function. Makes sure the cmp function is presented
1898 with the actual key instead of the sortwrapper */
1906 cmpwrapper_dealloc(cmpwrapperobject
*co
)
1908 Py_XDECREF(co
->func
);
1913 cmpwrapper_call(cmpwrapperobject
*co
, PyObject
*args
, PyObject
*kwds
)
1915 PyObject
*x
, *y
, *xx
, *yy
;
1917 if (!PyArg_UnpackTuple(args
, "", 2, 2, &x
, &y
))
1919 if (!PyObject_TypeCheck(x
, &sortwrapper_type
) ||
1920 !PyObject_TypeCheck(y
, &sortwrapper_type
)) {
1921 PyErr_SetString(PyExc_TypeError
,
1922 "expected a sortwrapperobject");
1925 xx
= ((sortwrapperobject
*)x
)->key
;
1926 yy
= ((sortwrapperobject
*)y
)->key
;
1927 return PyObject_CallFunctionObjArgs(co
->func
, xx
, yy
, NULL
);
1930 PyDoc_STRVAR(cmpwrapper_doc
, "cmp() wrapper for sort with custom keys.");
1932 static PyTypeObject cmpwrapper_type
= {
1933 PyObject_HEAD_INIT(&PyType_Type
)
1935 "cmpwrapper", /* tp_name */
1936 sizeof(cmpwrapperobject
), /* tp_basicsize */
1937 0, /* tp_itemsize */
1939 (destructor
)cmpwrapper_dealloc
, /* tp_dealloc */
1945 0, /* tp_as_number */
1946 0, /* tp_as_sequence */
1947 0, /* tp_as_mapping */
1949 (ternaryfunc
)cmpwrapper_call
, /* tp_call */
1951 PyObject_GenericGetAttr
, /* tp_getattro */
1952 0, /* tp_setattro */
1953 0, /* tp_as_buffer */
1954 Py_TPFLAGS_DEFAULT
, /* tp_flags */
1955 cmpwrapper_doc
, /* tp_doc */
1959 build_cmpwrapper(PyObject
*cmpfunc
)
1961 cmpwrapperobject
*co
;
1963 co
= PyObject_New(cmpwrapperobject
, &cmpwrapper_type
);
1968 return (PyObject
*)co
;
1971 /* An adaptive, stable, natural mergesort. See listsort.txt.
1972 * Returns Py_None on success, NULL on error. Even in case of error, the
1973 * list will be some permutation of its input state (nothing is lost or
1977 listsort(PyListObject
*self
, PyObject
*args
, PyObject
*kwds
)
1980 PyObject
**lo
, **hi
;
1981 Py_ssize_t nremaining
;
1983 Py_ssize_t saved_ob_size
, saved_allocated
;
1984 PyObject
**saved_ob_item
;
1985 PyObject
**final_ob_item
;
1986 PyObject
*compare
= NULL
;
1987 PyObject
*result
= NULL
; /* guilty until proved innocent */
1989 PyObject
*keyfunc
= NULL
;
1991 PyObject
*key
, *value
, *kvpair
;
1992 static char *kwlist
[] = {"cmp", "key", "reverse", 0};
1994 assert(self
!= NULL
);
1995 assert (PyList_Check(self
));
1997 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|OOi:sort",
1998 kwlist
, &compare
, &keyfunc
, &reverse
))
2001 if (compare
== Py_None
)
2003 if (keyfunc
== Py_None
)
2005 if (compare
!= NULL
&& keyfunc
!= NULL
) {
2006 compare
= build_cmpwrapper(compare
);
2007 if (compare
== NULL
)
2010 Py_XINCREF(compare
);
2012 /* The list is temporarily made empty, so that mutations performed
2013 * by comparison functions can't affect the slice of memory we're
2014 * sorting (allowing mutations during sorting is a core-dump
2015 * factory, since ob_item may change).
2017 saved_ob_size
= self
->ob_size
;
2018 saved_ob_item
= self
->ob_item
;
2019 saved_allocated
= self
->allocated
;
2021 self
->ob_item
= NULL
;
2022 self
->allocated
= -1; /* any operation will reset it to >= 0 */
2024 if (keyfunc
!= NULL
) {
2025 for (i
=0 ; i
< saved_ob_size
; i
++) {
2026 value
= saved_ob_item
[i
];
2027 key
= PyObject_CallFunctionObjArgs(keyfunc
, value
,
2030 for (i
=i
-1 ; i
>=0 ; i
--) {
2031 kvpair
= saved_ob_item
[i
];
2032 value
= sortwrapper_getvalue(kvpair
);
2033 saved_ob_item
[i
] = value
;
2038 kvpair
= build_sortwrapper(key
, value
);
2041 saved_ob_item
[i
] = kvpair
;
2045 /* Reverse sort stability achieved by initially reversing the list,
2046 applying a stable forward sort, then reversing the final result. */
2047 if (reverse
&& saved_ob_size
> 1)
2048 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2050 merge_init(&ms
, compare
);
2052 nremaining
= saved_ob_size
;
2056 /* March over the array once, left to right, finding natural runs,
2057 * and extending short natural runs to minrun elements.
2060 hi
= lo
+ nremaining
;
2061 minrun
= merge_compute_minrun(nremaining
);
2066 /* Identify next run. */
2067 n
= count_run(lo
, hi
, compare
, &descending
);
2071 reverse_slice(lo
, lo
+ n
);
2072 /* If short, extend to min(minrun, nremaining). */
2074 const Py_ssize_t force
= nremaining
<= minrun
?
2075 nremaining
: minrun
;
2076 if (binarysort(lo
, lo
+ force
, lo
+ n
, compare
) < 0)
2080 /* Push run onto pending-runs stack, and maybe merge. */
2081 assert(ms
.n
< MAX_MERGE_PENDING
);
2082 ms
.pending
[ms
.n
].base
= lo
;
2083 ms
.pending
[ms
.n
].len
= n
;
2085 if (merge_collapse(&ms
) < 0)
2087 /* Advance to find next run. */
2090 } while (nremaining
);
2093 if (merge_force_collapse(&ms
) < 0)
2096 assert(ms
.pending
[0].base
== saved_ob_item
);
2097 assert(ms
.pending
[0].len
== saved_ob_size
);
2102 if (keyfunc
!= NULL
) {
2103 for (i
=0 ; i
< saved_ob_size
; i
++) {
2104 kvpair
= saved_ob_item
[i
];
2105 value
= sortwrapper_getvalue(kvpair
);
2106 saved_ob_item
[i
] = value
;
2111 if (self
->allocated
!= -1 && result
!= NULL
) {
2112 /* The user mucked with the list during the sort,
2113 * and we don't already have another error to report.
2115 PyErr_SetString(PyExc_ValueError
, "list modified during sort");
2119 if (reverse
&& saved_ob_size
> 1)
2120 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2125 final_ob_item
= self
->ob_item
;
2127 self
->ob_size
= saved_ob_size
;
2128 self
->ob_item
= saved_ob_item
;
2129 self
->allocated
= saved_allocated
;
2130 if (final_ob_item
!= NULL
) {
2131 /* we cannot use list_clear() for this because it does not
2132 guarantee that the list is really empty when it returns */
2134 Py_XDECREF(final_ob_item
[i
]);
2136 PyMem_FREE(final_ob_item
);
2138 Py_XDECREF(compare
);
2146 PyList_Sort(PyObject
*v
)
2148 if (v
== NULL
|| !PyList_Check(v
)) {
2149 PyErr_BadInternalCall();
2152 v
= listsort((PyListObject
*)v
, (PyObject
*)NULL
, (PyObject
*)NULL
);
2160 listreverse(PyListObject
*self
)
2162 if (self
->ob_size
> 1)
2163 reverse_slice(self
->ob_item
, self
->ob_item
+ self
->ob_size
);
2168 PyList_Reverse(PyObject
*v
)
2170 PyListObject
*self
= (PyListObject
*)v
;
2172 if (v
== NULL
|| !PyList_Check(v
)) {
2173 PyErr_BadInternalCall();
2176 if (self
->ob_size
> 1)
2177 reverse_slice(self
->ob_item
, self
->ob_item
+ self
->ob_size
);
2182 PyList_AsTuple(PyObject
*v
)
2187 if (v
== NULL
|| !PyList_Check(v
)) {
2188 PyErr_BadInternalCall();
2191 n
= ((PyListObject
*)v
)->ob_size
;
2195 p
= ((PyTupleObject
*)w
)->ob_item
;
2197 (void *)((PyListObject
*)v
)->ob_item
,
2198 n
*sizeof(PyObject
*));
2207 listindex(PyListObject
*self
, PyObject
*args
)
2209 Py_ssize_t i
, start
=0, stop
=self
->ob_size
;
2212 if (!PyArg_ParseTuple(args
, "O|O&O&:index", &v
,
2213 _PyEval_SliceIndex
, &start
,
2214 _PyEval_SliceIndex
, &stop
))
2217 start
+= self
->ob_size
;
2222 stop
+= self
->ob_size
;
2226 for (i
= start
; i
< stop
&& i
< self
->ob_size
; i
++) {
2227 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2229 return PyInt_FromSsize_t(i
);
2233 PyErr_SetString(PyExc_ValueError
, "list.index(x): x not in list");
2238 listcount(PyListObject
*self
, PyObject
*v
)
2240 Py_ssize_t count
= 0;
2243 for (i
= 0; i
< self
->ob_size
; i
++) {
2244 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2250 return PyInt_FromSsize_t(count
);
2254 listremove(PyListObject
*self
, PyObject
*v
)
2258 for (i
= 0; i
< self
->ob_size
; i
++) {
2259 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2261 if (list_ass_slice(self
, i
, i
+1,
2262 (PyObject
*)NULL
) == 0)
2269 PyErr_SetString(PyExc_ValueError
, "list.remove(x): x not in list");
2274 list_traverse(PyListObject
*o
, visitproc visit
, void *arg
)
2278 for (i
= o
->ob_size
; --i
>= 0; )
2279 Py_VISIT(o
->ob_item
[i
]);
2284 list_richcompare(PyObject
*v
, PyObject
*w
, int op
)
2286 PyListObject
*vl
, *wl
;
2289 if (!PyList_Check(v
) || !PyList_Check(w
)) {
2290 Py_INCREF(Py_NotImplemented
);
2291 return Py_NotImplemented
;
2294 vl
= (PyListObject
*)v
;
2295 wl
= (PyListObject
*)w
;
2297 if (vl
->ob_size
!= wl
->ob_size
&& (op
== Py_EQ
|| op
== Py_NE
)) {
2298 /* Shortcut: if the lengths differ, the lists differ */
2308 /* Search for the first index where items are different */
2309 for (i
= 0; i
< vl
->ob_size
&& i
< wl
->ob_size
; i
++) {
2310 int k
= PyObject_RichCompareBool(vl
->ob_item
[i
],
2311 wl
->ob_item
[i
], Py_EQ
);
2318 if (i
>= vl
->ob_size
|| i
>= wl
->ob_size
) {
2319 /* No more items to compare -- compare sizes */
2320 Py_ssize_t vs
= vl
->ob_size
;
2321 Py_ssize_t ws
= wl
->ob_size
;
2325 case Py_LT
: cmp
= vs
< ws
; break;
2326 case Py_LE
: cmp
= vs
<= ws
; break;
2327 case Py_EQ
: cmp
= vs
== ws
; break;
2328 case Py_NE
: cmp
= vs
!= ws
; break;
2329 case Py_GT
: cmp
= vs
> ws
; break;
2330 case Py_GE
: cmp
= vs
>= ws
; break;
2331 default: return NULL
; /* cannot happen */
2341 /* We have an item that differs -- shortcuts for EQ/NE */
2343 Py_INCREF(Py_False
);
2351 /* Compare the final item again using the proper operator */
2352 return PyObject_RichCompare(vl
->ob_item
[i
], wl
->ob_item
[i
], op
);
2356 list_init(PyListObject
*self
, PyObject
*args
, PyObject
*kw
)
2358 PyObject
*arg
= NULL
;
2359 static char *kwlist
[] = {"sequence", 0};
2361 if (!PyArg_ParseTupleAndKeywords(args
, kw
, "|O:list", kwlist
, &arg
))
2364 /* Verify list invariants established by PyType_GenericAlloc() */
2365 assert(0 <= self
->ob_size
);
2366 assert(self
->ob_size
<= self
->allocated
|| self
->allocated
== -1);
2367 assert(self
->ob_item
!= NULL
||
2368 self
->allocated
== 0 || self
->allocated
== -1);
2370 /* Empty previous contents */
2371 if (self
->ob_item
!= NULL
) {
2372 (void)list_clear(self
);
2375 PyObject
*rv
= listextend(self
, arg
);
2384 list_nohash(PyObject
*self
)
2386 PyErr_SetString(PyExc_TypeError
, "list objects are unhashable");
2390 static PyObject
*list_iter(PyObject
*seq
);
2391 static PyObject
*list_reversed(PyListObject
* seq
, PyObject
* unused
);
2393 PyDoc_STRVAR(getitem_doc
,
2394 "x.__getitem__(y) <==> x[y]");
2395 PyDoc_STRVAR(reversed_doc
,
2396 "L.__reversed__() -- return a reverse iterator over the list");
2397 PyDoc_STRVAR(append_doc
,
2398 "L.append(object) -- append object to end");
2399 PyDoc_STRVAR(extend_doc
,
2400 "L.extend(iterable) -- extend list by appending elements from the iterable");
2401 PyDoc_STRVAR(insert_doc
,
2402 "L.insert(index, object) -- insert object before index");
2403 PyDoc_STRVAR(pop_doc
,
2404 "L.pop([index]) -> item -- remove and return item at index (default last)");
2405 PyDoc_STRVAR(remove_doc
,
2406 "L.remove(value) -- remove first occurrence of value");
2407 PyDoc_STRVAR(index_doc
,
2408 "L.index(value, [start, [stop]]) -> integer -- return first index of value");
2409 PyDoc_STRVAR(count_doc
,
2410 "L.count(value) -> integer -- return number of occurrences of value");
2411 PyDoc_STRVAR(reverse_doc
,
2412 "L.reverse() -- reverse *IN PLACE*");
2413 PyDoc_STRVAR(sort_doc
,
2414 "L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
2415 cmp(x, y) -> -1, 0, 1");
2417 static PyObject
*list_subscript(PyListObject
*, PyObject
*);
2419 static PyMethodDef list_methods
[] = {
2420 {"__getitem__", (PyCFunction
)list_subscript
, METH_O
|METH_COEXIST
, getitem_doc
},
2421 {"__reversed__",(PyCFunction
)list_reversed
, METH_NOARGS
, reversed_doc
},
2422 {"append", (PyCFunction
)listappend
, METH_O
, append_doc
},
2423 {"insert", (PyCFunction
)listinsert
, METH_VARARGS
, insert_doc
},
2424 {"extend", (PyCFunction
)listextend
, METH_O
, extend_doc
},
2425 {"pop", (PyCFunction
)listpop
, METH_VARARGS
, pop_doc
},
2426 {"remove", (PyCFunction
)listremove
, METH_O
, remove_doc
},
2427 {"index", (PyCFunction
)listindex
, METH_VARARGS
, index_doc
},
2428 {"count", (PyCFunction
)listcount
, METH_O
, count_doc
},
2429 {"reverse", (PyCFunction
)listreverse
, METH_NOARGS
, reverse_doc
},
2430 {"sort", (PyCFunction
)listsort
, METH_VARARGS
| METH_KEYWORDS
, sort_doc
},
2431 {NULL
, NULL
} /* sentinel */
2434 static PySequenceMethods list_as_sequence
= {
2435 (lenfunc
)list_length
, /* sq_length */
2436 (binaryfunc
)list_concat
, /* sq_concat */
2437 (ssizeargfunc
)list_repeat
, /* sq_repeat */
2438 (ssizeargfunc
)list_item
, /* sq_item */
2439 (ssizessizeargfunc
)list_slice
, /* sq_slice */
2440 (ssizeobjargproc
)list_ass_item
, /* sq_ass_item */
2441 (ssizessizeobjargproc
)list_ass_slice
, /* sq_ass_slice */
2442 (objobjproc
)list_contains
, /* sq_contains */
2443 (binaryfunc
)list_inplace_concat
, /* sq_inplace_concat */
2444 (ssizeargfunc
)list_inplace_repeat
, /* sq_inplace_repeat */
2447 PyDoc_STRVAR(list_doc
,
2448 "list() -> new list\n"
2449 "list(sequence) -> new list initialized from sequence's items");
2451 #define HASINDEX(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_HAVE_INDEX)
2454 list_subscript(PyListObject
* self
, PyObject
* item
)
2456 PyNumberMethods
*nb
= item
->ob_type
->tp_as_number
;
2457 if (nb
!= NULL
&& HASINDEX(item
) && nb
->nb_index
!= NULL
) {
2458 Py_ssize_t i
= nb
->nb_index(item
);
2459 if (i
== -1 && PyErr_Occurred())
2462 i
+= PyList_GET_SIZE(self
);
2463 return list_item(self
, i
);
2465 else if (PySlice_Check(item
)) {
2466 Py_ssize_t start
, stop
, step
, slicelength
, cur
, i
;
2469 PyObject
**src
, **dest
;
2471 if (PySlice_GetIndicesEx((PySliceObject
*)item
, self
->ob_size
,
2472 &start
, &stop
, &step
, &slicelength
) < 0) {
2476 if (slicelength
<= 0) {
2477 return PyList_New(0);
2480 result
= PyList_New(slicelength
);
2481 if (!result
) return NULL
;
2483 src
= self
->ob_item
;
2484 dest
= ((PyListObject
*)result
)->ob_item
;
2485 for (cur
= start
, i
= 0; i
< slicelength
;
2496 PyErr_SetString(PyExc_TypeError
,
2497 "list indices must be integers");
2503 list_ass_subscript(PyListObject
* self
, PyObject
* item
, PyObject
* value
)
2505 PyNumberMethods
*nb
= item
->ob_type
->tp_as_number
;
2506 if (nb
!= NULL
&& HASINDEX(item
) && nb
->nb_index
!= NULL
) {
2507 Py_ssize_t i
= nb
->nb_index(item
);
2508 if (i
== -1 && PyErr_Occurred())
2511 i
+= PyList_GET_SIZE(self
);
2512 return list_ass_item(self
, i
, value
);
2514 else if (PySlice_Check(item
)) {
2515 Py_ssize_t start
, stop
, step
, slicelength
;
2517 if (PySlice_GetIndicesEx((PySliceObject
*)item
, self
->ob_size
,
2518 &start
, &stop
, &step
, &slicelength
) < 0) {
2522 /* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
2523 if (step
== 1 && ((PySliceObject
*)item
)->step
== Py_None
)
2524 return list_ass_slice(self
, start
, stop
, value
);
2526 if (value
== NULL
) {
2531 if (slicelength
<= 0)
2536 start
= stop
+ step
*(slicelength
- 1) - 1;
2540 garbage
= (PyObject
**)
2541 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2543 /* drawing pictures might help
2544 understand these for loops */
2545 for (cur
= start
, i
= 0;
2548 Py_ssize_t lim
= step
;
2550 garbage
[i
] = PyList_GET_ITEM(self
, cur
);
2552 if (cur
+ step
>= self
->ob_size
) {
2553 lim
= self
->ob_size
- cur
- 1;
2556 memmove(self
->ob_item
+ cur
- i
,
2557 self
->ob_item
+ cur
+ 1,
2558 lim
* sizeof(PyObject
*));
2561 for (cur
= start
+ slicelength
*step
+ 1;
2562 cur
< self
->ob_size
; cur
++) {
2563 PyList_SET_ITEM(self
, cur
- slicelength
,
2564 PyList_GET_ITEM(self
, cur
));
2567 self
->ob_size
-= slicelength
;
2568 list_resize(self
, self
->ob_size
);
2570 for (i
= 0; i
< slicelength
; i
++) {
2571 Py_DECREF(garbage
[i
]);
2573 PyMem_FREE(garbage
);
2579 PyObject
**garbage
, *ins
, *seq
, **seqitems
, **selfitems
;
2582 /* protect against a[::-1] = a */
2583 if (self
== (PyListObject
*)value
) {
2584 seq
= list_slice((PyListObject
*)value
, 0,
2585 PyList_GET_SIZE(value
));
2588 seq
= PySequence_Fast(value
,
2589 "must assign iterable to extended slice");
2594 if (PySequence_Fast_GET_SIZE(seq
) != slicelength
) {
2595 PyErr_Format(PyExc_ValueError
,
2596 "attempt to assign sequence of size %zd to extended slice of size %zd",
2597 PySequence_Fast_GET_SIZE(seq
),
2608 garbage
= (PyObject
**)
2609 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2611 selfitems
= self
->ob_item
;
2612 seqitems
= PySequence_Fast_ITEMS(seq
);
2613 for (cur
= start
, i
= 0; i
< slicelength
;
2615 garbage
[i
] = selfitems
[cur
];
2618 selfitems
[cur
] = ins
;
2621 for (i
= 0; i
< slicelength
; i
++) {
2622 Py_DECREF(garbage
[i
]);
2625 PyMem_FREE(garbage
);
2632 PyErr_SetString(PyExc_TypeError
,
2633 "list indices must be integers");
2638 static PyMappingMethods list_as_mapping
= {
2639 (lenfunc
)list_length
,
2640 (binaryfunc
)list_subscript
,
2641 (objobjargproc
)list_ass_subscript
2644 PyTypeObject PyList_Type
= {
2645 PyObject_HEAD_INIT(&PyType_Type
)
2648 sizeof(PyListObject
),
2650 (destructor
)list_dealloc
, /* tp_dealloc */
2651 (printfunc
)list_print
, /* tp_print */
2655 (reprfunc
)list_repr
, /* tp_repr */
2656 0, /* tp_as_number */
2657 &list_as_sequence
, /* tp_as_sequence */
2658 &list_as_mapping
, /* tp_as_mapping */
2659 list_nohash
, /* tp_hash */
2662 PyObject_GenericGetAttr
, /* tp_getattro */
2663 0, /* tp_setattro */
2664 0, /* tp_as_buffer */
2665 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2666 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2667 list_doc
, /* tp_doc */
2668 (traverseproc
)list_traverse
, /* tp_traverse */
2669 (inquiry
)list_clear
, /* tp_clear */
2670 list_richcompare
, /* tp_richcompare */
2671 0, /* tp_weaklistoffset */
2672 list_iter
, /* tp_iter */
2673 0, /* tp_iternext */
2674 list_methods
, /* tp_methods */
2679 0, /* tp_descr_get */
2680 0, /* tp_descr_set */
2681 0, /* tp_dictoffset */
2682 (initproc
)list_init
, /* tp_init */
2683 PyType_GenericAlloc
, /* tp_alloc */
2684 PyType_GenericNew
, /* tp_new */
2685 PyObject_GC_Del
, /* tp_free */
2689 /*********************** List Iterator **************************/
2694 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2697 static PyObject
*list_iter(PyObject
*);
2698 static void listiter_dealloc(listiterobject
*);
2699 static int listiter_traverse(listiterobject
*, visitproc
, void *);
2700 static PyObject
*listiter_next(listiterobject
*);
2701 static PyObject
*listiter_len(listiterobject
*);
2703 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
2705 static PyMethodDef listiter_methods
[] = {
2706 {"__length_hint__", (PyCFunction
)listiter_len
, METH_NOARGS
, length_hint_doc
},
2707 {NULL
, NULL
} /* sentinel */
2710 PyTypeObject PyListIter_Type
= {
2711 PyObject_HEAD_INIT(&PyType_Type
)
2713 "listiterator", /* tp_name */
2714 sizeof(listiterobject
), /* tp_basicsize */
2715 0, /* tp_itemsize */
2717 (destructor
)listiter_dealloc
, /* tp_dealloc */
2723 0, /* tp_as_number */
2724 0, /* tp_as_sequence */
2725 0, /* tp_as_mapping */
2729 PyObject_GenericGetAttr
, /* tp_getattro */
2730 0, /* tp_setattro */
2731 0, /* tp_as_buffer */
2732 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2734 (traverseproc
)listiter_traverse
, /* tp_traverse */
2736 0, /* tp_richcompare */
2737 0, /* tp_weaklistoffset */
2738 PyObject_SelfIter
, /* tp_iter */
2739 (iternextfunc
)listiter_next
, /* tp_iternext */
2740 listiter_methods
, /* tp_methods */
2746 list_iter(PyObject
*seq
)
2750 if (!PyList_Check(seq
)) {
2751 PyErr_BadInternalCall();
2754 it
= PyObject_GC_New(listiterobject
, &PyListIter_Type
);
2759 it
->it_seq
= (PyListObject
*)seq
;
2760 _PyObject_GC_TRACK(it
);
2761 return (PyObject
*)it
;
2765 listiter_dealloc(listiterobject
*it
)
2767 _PyObject_GC_UNTRACK(it
);
2768 Py_XDECREF(it
->it_seq
);
2769 PyObject_GC_Del(it
);
2773 listiter_traverse(listiterobject
*it
, visitproc visit
, void *arg
)
2775 Py_VISIT(it
->it_seq
);
2780 listiter_next(listiterobject
*it
)
2789 assert(PyList_Check(seq
));
2791 if (it
->it_index
< PyList_GET_SIZE(seq
)) {
2792 item
= PyList_GET_ITEM(seq
, it
->it_index
);
2804 listiter_len(listiterobject
*it
)
2808 len
= PyList_GET_SIZE(it
->it_seq
) - it
->it_index
;
2810 return PyInt_FromSsize_t(len
);
2812 return PyInt_FromLong(0);
2814 /*********************** List Reverse Iterator **************************/
2818 Py_ssize_t it_index
;
2819 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2820 } listreviterobject
;
2822 static PyObject
*list_reversed(PyListObject
*, PyObject
*);
2823 static void listreviter_dealloc(listreviterobject
*);
2824 static int listreviter_traverse(listreviterobject
*, visitproc
, void *);
2825 static PyObject
*listreviter_next(listreviterobject
*);
2826 static Py_ssize_t
listreviter_len(listreviterobject
*);
2828 static PySequenceMethods listreviter_as_sequence
= {
2829 (lenfunc
)listreviter_len
, /* sq_length */
2833 PyTypeObject PyListRevIter_Type
= {
2834 PyObject_HEAD_INIT(&PyType_Type
)
2836 "listreverseiterator", /* tp_name */
2837 sizeof(listreviterobject
), /* tp_basicsize */
2838 0, /* tp_itemsize */
2840 (destructor
)listreviter_dealloc
, /* tp_dealloc */
2846 0, /* tp_as_number */
2847 &listreviter_as_sequence
, /* tp_as_sequence */
2848 0, /* tp_as_mapping */
2852 PyObject_GenericGetAttr
, /* tp_getattro */
2853 0, /* tp_setattro */
2854 0, /* tp_as_buffer */
2855 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2857 (traverseproc
)listreviter_traverse
, /* tp_traverse */
2859 0, /* tp_richcompare */
2860 0, /* tp_weaklistoffset */
2861 PyObject_SelfIter
, /* tp_iter */
2862 (iternextfunc
)listreviter_next
, /* tp_iternext */
2867 list_reversed(PyListObject
*seq
, PyObject
*unused
)
2869 listreviterobject
*it
;
2871 it
= PyObject_GC_New(listreviterobject
, &PyListRevIter_Type
);
2874 assert(PyList_Check(seq
));
2875 it
->it_index
= PyList_GET_SIZE(seq
) - 1;
2878 PyObject_GC_Track(it
);
2879 return (PyObject
*)it
;
2883 listreviter_dealloc(listreviterobject
*it
)
2885 PyObject_GC_UnTrack(it
);
2886 Py_XDECREF(it
->it_seq
);
2887 PyObject_GC_Del(it
);
2891 listreviter_traverse(listreviterobject
*it
, visitproc visit
, void *arg
)
2893 Py_VISIT(it
->it_seq
);
2898 listreviter_next(listreviterobject
*it
)
2901 Py_ssize_t index
= it
->it_index
;
2902 PyListObject
*seq
= it
->it_seq
;
2904 if (index
>=0 && index
< PyList_GET_SIZE(seq
)) {
2905 item
= PyList_GET_ITEM(seq
, index
);
2919 listreviter_len(listreviterobject
*it
)
2921 Py_ssize_t len
= it
->it_index
+ 1;
2922 if (it
->it_seq
== NULL
|| PyList_GET_SIZE(it
->it_seq
) < len
)