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
) {
113 return PyErr_NoMemory();
115 memset(op
->ob_item
, 0, nbytes
);
118 op
->allocated
= size
;
119 _PyObject_GC_TRACK(op
);
120 return (PyObject
*) op
;
124 PyList_Size(PyObject
*op
)
126 if (!PyList_Check(op
)) {
127 PyErr_BadInternalCall();
131 return ((PyListObject
*)op
) -> ob_size
;
134 static PyObject
*indexerr
= NULL
;
137 PyList_GetItem(PyObject
*op
, Py_ssize_t i
)
139 if (!PyList_Check(op
)) {
140 PyErr_BadInternalCall();
143 if (i
< 0 || i
>= ((PyListObject
*)op
) -> ob_size
) {
144 if (indexerr
== NULL
)
145 indexerr
= PyString_FromString(
146 "list index out of range");
147 PyErr_SetObject(PyExc_IndexError
, indexerr
);
150 return ((PyListObject
*)op
) -> ob_item
[i
];
154 PyList_SetItem(register PyObject
*op
, register Py_ssize_t i
,
155 register PyObject
*newitem
)
157 register PyObject
*olditem
;
158 register PyObject
**p
;
159 if (!PyList_Check(op
)) {
161 PyErr_BadInternalCall();
164 if (i
< 0 || i
>= ((PyListObject
*)op
) -> ob_size
) {
166 PyErr_SetString(PyExc_IndexError
,
167 "list assignment index out of range");
170 p
= ((PyListObject
*)op
) -> ob_item
+ i
;
178 ins1(PyListObject
*self
, Py_ssize_t where
, PyObject
*v
)
180 Py_ssize_t i
, n
= self
->ob_size
;
183 PyErr_BadInternalCall();
186 if (n
== PY_SSIZE_T_MAX
) {
187 PyErr_SetString(PyExc_OverflowError
,
188 "cannot add more objects to list");
192 if (list_resize(self
, n
+1) == -1)
202 items
= self
->ob_item
;
203 for (i
= n
; --i
>= where
; )
204 items
[i
+1] = items
[i
];
211 PyList_Insert(PyObject
*op
, Py_ssize_t where
, PyObject
*newitem
)
213 if (!PyList_Check(op
)) {
214 PyErr_BadInternalCall();
217 return ins1((PyListObject
*)op
, where
, newitem
);
221 app1(PyListObject
*self
, PyObject
*v
)
223 Py_ssize_t n
= PyList_GET_SIZE(self
);
226 if (n
== PY_SSIZE_T_MAX
) {
227 PyErr_SetString(PyExc_OverflowError
,
228 "cannot add more objects to list");
232 if (list_resize(self
, n
+1) == -1)
236 PyList_SET_ITEM(self
, n
, v
);
241 PyList_Append(PyObject
*op
, PyObject
*newitem
)
243 if (PyList_Check(op
) && (newitem
!= NULL
))
244 return app1((PyListObject
*)op
, newitem
);
245 PyErr_BadInternalCall();
252 list_dealloc(PyListObject
*op
)
255 PyObject_GC_UnTrack(op
);
256 Py_TRASHCAN_SAFE_BEGIN(op
)
257 if (op
->ob_item
!= NULL
) {
258 /* Do it backwards, for Christian Tismer.
259 There's a simple test case where somehow this reduces
260 thrashing when a *very* large list is created and
261 immediately deleted. */
264 Py_XDECREF(op
->ob_item
[i
]);
266 PyMem_FREE(op
->ob_item
);
268 if (num_free_lists
< MAXFREELISTS
&& PyList_CheckExact(op
))
269 free_lists
[num_free_lists
++] = op
;
271 op
->ob_type
->tp_free((PyObject
*)op
);
272 Py_TRASHCAN_SAFE_END(op
)
276 list_print(PyListObject
*op
, FILE *fp
, int flags
)
281 rc
= Py_ReprEnter((PyObject
*)op
);
285 fprintf(fp
, "[...]");
289 for (i
= 0; i
< op
->ob_size
; i
++) {
292 if (PyObject_Print(op
->ob_item
[i
], fp
, 0) != 0) {
293 Py_ReprLeave((PyObject
*)op
);
298 Py_ReprLeave((PyObject
*)op
);
303 list_repr(PyListObject
*v
)
307 PyObject
*pieces
= NULL
, *result
= NULL
;
309 i
= Py_ReprEnter((PyObject
*)v
);
311 return i
> 0 ? PyString_FromString("[...]") : NULL
;
314 if (v
->ob_size
== 0) {
315 result
= PyString_FromString("[]");
319 pieces
= PyList_New(0);
323 /* Do repr() on each element. Note that this may mutate the list,
324 so must refetch the list size on each iteration. */
325 for (i
= 0; i
< v
->ob_size
; ++i
) {
327 s
= PyObject_Repr(v
->ob_item
[i
]);
330 status
= PyList_Append(pieces
, s
);
331 Py_DECREF(s
); /* append created a new ref */
336 /* Add "[]" decorations to the first and last items. */
337 assert(PyList_GET_SIZE(pieces
) > 0);
338 s
= PyString_FromString("[");
341 temp
= PyList_GET_ITEM(pieces
, 0);
342 PyString_ConcatAndDel(&s
, temp
);
343 PyList_SET_ITEM(pieces
, 0, s
);
347 s
= PyString_FromString("]");
350 temp
= PyList_GET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1);
351 PyString_ConcatAndDel(&temp
, s
);
352 PyList_SET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1, temp
);
356 /* Paste them all together with ", " between. */
357 s
= PyString_FromString(", ");
360 result
= _PyString_Join(s
, pieces
);
365 Py_ReprLeave((PyObject
*)v
);
370 list_length(PyListObject
*a
)
376 list_contains(PyListObject
*a
, PyObject
*el
)
381 for (i
= 0, cmp
= 0 ; cmp
== 0 && i
< a
->ob_size
; ++i
)
382 cmp
= PyObject_RichCompareBool(el
, PyList_GET_ITEM(a
, i
),
388 list_item(PyListObject
*a
, Py_ssize_t i
)
390 if (i
< 0 || i
>= a
->ob_size
) {
391 if (indexerr
== NULL
)
392 indexerr
= PyString_FromString(
393 "list index out of range");
394 PyErr_SetObject(PyExc_IndexError
, indexerr
);
397 Py_INCREF(a
->ob_item
[i
]);
398 return a
->ob_item
[i
];
402 list_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
405 PyObject
**src
, **dest
;
409 else if (ilow
> a
->ob_size
)
413 else if (ihigh
> a
->ob_size
)
416 np
= (PyListObject
*) PyList_New(len
);
420 src
= a
->ob_item
+ ilow
;
422 for (i
= 0; i
< len
; i
++) {
423 PyObject
*v
= src
[i
];
427 return (PyObject
*)np
;
431 PyList_GetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
433 if (!PyList_Check(a
)) {
434 PyErr_BadInternalCall();
437 return list_slice((PyListObject
*)a
, ilow
, ihigh
);
441 list_concat(PyListObject
*a
, PyObject
*bb
)
445 PyObject
**src
, **dest
;
447 if (!PyList_Check(bb
)) {
448 PyErr_Format(PyExc_TypeError
,
449 "can only concatenate list (not \"%.200s\") to list",
450 bb
->ob_type
->tp_name
);
453 #define b ((PyListObject *)bb)
454 size
= a
->ob_size
+ b
->ob_size
;
456 return PyErr_NoMemory();
457 np
= (PyListObject
*) PyList_New(size
);
463 for (i
= 0; i
< a
->ob_size
; i
++) {
464 PyObject
*v
= src
[i
];
469 dest
= np
->ob_item
+ a
->ob_size
;
470 for (i
= 0; i
< b
->ob_size
; i
++) {
471 PyObject
*v
= src
[i
];
475 return (PyObject
*)np
;
480 list_repeat(PyListObject
*a
, Py_ssize_t n
)
485 PyObject
**p
, **items
;
489 size
= a
->ob_size
* n
;
491 return PyList_New(0);
492 if (n
&& size
/n
!= a
->ob_size
)
493 return PyErr_NoMemory();
494 np
= (PyListObject
*) PyList_New(size
);
499 if (a
->ob_size
== 1) {
500 elem
= a
->ob_item
[0];
501 for (i
= 0; i
< n
; i
++) {
505 return (PyObject
*) np
;
509 for (i
= 0; i
< n
; i
++) {
510 for (j
= 0; j
< a
->ob_size
; j
++) {
516 return (PyObject
*) np
;
520 list_clear(PyListObject
*a
)
523 PyObject
**item
= a
->ob_item
;
525 /* Because XDECREF can recursively invoke operations on
526 this list, we make it empty first. */
536 /* Never fails; the return value can be ignored.
537 Note that there is no guarantee that the list is actually empty
538 at this point, because XDECREF may have populated it again! */
542 /* a[ilow:ihigh] = v if v != NULL.
543 * del a[ilow:ihigh] if v == NULL.
545 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
546 * guaranteed the call cannot fail.
549 list_ass_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
551 /* Because [X]DECREF can recursively invoke list operations on
552 this list, we must postpone all [X]DECREF activity until
553 after the list is back in its canonical shape. Therefore
554 we must allocate an additional array, 'recycle', into which
555 we temporarily copy the items that are deleted from the
557 PyObject
*recycle_on_stack
[8];
558 PyObject
**recycle
= recycle_on_stack
; /* will allocate more if needed */
560 PyObject
**vitem
= NULL
;
561 PyObject
*v_as_SF
= NULL
; /* PySequence_Fast(v) */
562 Py_ssize_t n
; /* # of elements in replacement list */
563 Py_ssize_t norig
; /* # of elements in list getting replaced */
564 Py_ssize_t d
; /* Change in size */
567 int result
= -1; /* guilty until proved innocent */
568 #define b ((PyListObject *)v)
573 /* Special case "a[i:j] = a" -- copy b first */
574 v
= list_slice(b
, 0, b
->ob_size
);
577 result
= list_ass_slice(a
, ilow
, ihigh
, v
);
581 v_as_SF
= PySequence_Fast(v
, "can only assign an iterable");
584 n
= PySequence_Fast_GET_SIZE(v_as_SF
);
585 vitem
= PySequence_Fast_ITEMS(v_as_SF
);
589 else if (ilow
> a
->ob_size
)
594 else if (ihigh
> a
->ob_size
)
597 norig
= ihigh
- ilow
;
600 if (a
->ob_size
+ d
== 0) {
602 return list_clear(a
);
605 /* recycle the items that we are about to remove */
606 s
= norig
* sizeof(PyObject
*);
607 if (s
> sizeof(recycle_on_stack
)) {
608 recycle
= (PyObject
**)PyMem_MALLOC(s
);
609 if (recycle
== NULL
) {
614 memcpy(recycle
, &item
[ilow
], s
);
616 if (d
< 0) { /* Delete -d items */
617 memmove(&item
[ihigh
+d
], &item
[ihigh
],
618 (a
->ob_size
- ihigh
)*sizeof(PyObject
*));
619 list_resize(a
, a
->ob_size
+ d
);
622 else if (d
> 0) { /* Insert d items */
624 if (list_resize(a
, k
+d
) < 0)
627 memmove(&item
[ihigh
+d
], &item
[ihigh
],
628 (k
- ihigh
)*sizeof(PyObject
*));
630 for (k
= 0; k
< n
; k
++, ilow
++) {
631 PyObject
*w
= vitem
[k
];
635 for (k
= norig
- 1; k
>= 0; --k
)
636 Py_XDECREF(recycle
[k
]);
639 if (recycle
!= recycle_on_stack
)
647 PyList_SetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
649 if (!PyList_Check(a
)) {
650 PyErr_BadInternalCall();
653 return list_ass_slice((PyListObject
*)a
, ilow
, ihigh
, v
);
657 list_inplace_repeat(PyListObject
*self
, Py_ssize_t n
)
660 Py_ssize_t size
, i
, j
, p
;
663 size
= PyList_GET_SIZE(self
);
666 return (PyObject
*)self
;
670 (void)list_clear(self
);
672 return (PyObject
*)self
;
675 if (list_resize(self
, size
*n
) == -1)
679 items
= self
->ob_item
;
680 for (i
= 1; i
< n
; i
++) { /* Start counting at 1, not 0 */
681 for (j
= 0; j
< size
; j
++) {
682 PyObject
*o
= items
[j
];
688 return (PyObject
*)self
;
692 list_ass_item(PyListObject
*a
, Py_ssize_t i
, PyObject
*v
)
695 if (i
< 0 || i
>= a
->ob_size
) {
696 PyErr_SetString(PyExc_IndexError
,
697 "list assignment index out of range");
701 return list_ass_slice(a
, i
, i
+1, v
);
703 old_value
= a
->ob_item
[i
];
705 Py_DECREF(old_value
);
710 listinsert(PyListObject
*self
, PyObject
*args
)
714 if (!PyArg_ParseTuple(args
, "nO:insert", &i
, &v
))
716 if (ins1(self
, i
, v
) == 0)
722 listappend(PyListObject
*self
, PyObject
*v
)
724 if (app1(self
, v
) == 0)
730 listextend(PyListObject
*self
, PyObject
*b
)
732 PyObject
*it
; /* iter(v) */
733 Py_ssize_t m
; /* size of self */
734 Py_ssize_t n
; /* guess for size of b */
735 Py_ssize_t mn
; /* m + n */
737 PyObject
*(*iternext
)(PyObject
*);
740 1) lists and tuples which can use PySequence_Fast ops
741 2) extending self to self requires making a copy first
743 if (PyList_CheckExact(b
) || PyTuple_CheckExact(b
) || (PyObject
*)self
== b
) {
744 PyObject
**src
, **dest
;
745 b
= PySequence_Fast(b
, "argument must be iterable");
748 n
= PySequence_Fast_GET_SIZE(b
);
750 /* short circuit when b is empty */
755 if (list_resize(self
, m
+ n
) == -1) {
759 /* note that we may still have self == b here for the
760 * situation a.extend(a), but the following code works
761 * in that case too. Just make sure to resize self
762 * before calling PySequence_Fast_ITEMS.
764 /* populate the end of self with b's items */
765 src
= PySequence_Fast_ITEMS(b
);
766 dest
= self
->ob_item
+ m
;
767 for (i
= 0; i
< n
; i
++) {
768 PyObject
*o
= src
[i
];
776 it
= PyObject_GetIter(b
);
779 iternext
= *it
->ob_type
->tp_iternext
;
781 /* Guess a result list size. */
782 n
= _PyObject_LengthHint(b
);
784 if (!PyErr_ExceptionMatches(PyExc_TypeError
) &&
785 !PyErr_ExceptionMatches(PyExc_AttributeError
)) {
790 n
= 8; /* arbitrary */
796 if (list_resize(self
, mn
) == -1)
798 /* Make the list sane again. */
801 /* Else m + n overflowed; on the chance that n lied, and there really
802 * is enough room, ignore it. If n was telling the truth, we'll
803 * eventually run out of memory during the loop.
806 /* Run iterator to exhaustion. */
808 PyObject
*item
= iternext(it
);
810 if (PyErr_Occurred()) {
811 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
818 if (self
->ob_size
< self
->allocated
) {
820 PyList_SET_ITEM(self
, self
->ob_size
, item
);
824 int status
= app1(self
, item
);
825 Py_DECREF(item
); /* append creates a new ref */
831 /* Cut back result list if initial guess was too large. */
832 if (self
->ob_size
< self
->allocated
)
833 list_resize(self
, self
->ob_size
); /* shrinking can't fail */
844 _PyList_Extend(PyListObject
*self
, PyObject
*b
)
846 return listextend(self
, b
);
850 list_inplace_concat(PyListObject
*self
, PyObject
*other
)
854 result
= listextend(self
, other
);
859 return (PyObject
*)self
;
863 listpop(PyListObject
*self
, PyObject
*args
)
866 PyObject
*v
, *arg
= NULL
;
869 if (!PyArg_UnpackTuple(args
, "pop", 0, 1, &arg
))
872 if (PyInt_Check(arg
))
873 i
= PyInt_AS_LONG((PyIntObject
*) arg
);
874 else if (!PyArg_ParseTuple(args
, "|n:pop", &i
))
877 if (self
->ob_size
== 0) {
878 /* Special-case most common failure cause */
879 PyErr_SetString(PyExc_IndexError
, "pop from empty list");
884 if (i
< 0 || i
>= self
->ob_size
) {
885 PyErr_SetString(PyExc_IndexError
, "pop index out of range");
888 v
= self
->ob_item
[i
];
889 if (i
== self
->ob_size
- 1) {
890 status
= list_resize(self
, self
->ob_size
- 1);
892 return v
; /* and v now owns the reference the list had */
895 status
= list_ass_slice(self
, i
, i
+1, (PyObject
*)NULL
);
897 /* Use status, so that in a release build compilers don't
898 * complain about the unused name.
905 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
907 reverse_slice(PyObject
**lo
, PyObject
**hi
)
921 /* Lots of code for an adaptive, stable, natural mergesort. There are many
922 * pieces to this algorithm; read listsort.txt for overviews and details.
925 /* Comparison function. Takes care of calling a user-supplied
926 * comparison function (any callable Python object), which must not be
927 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
928 * with Py_LT if you know it's NULL).
929 * Returns -1 on error, 1 if x < y, 0 if x >= y.
932 islt(PyObject
*x
, PyObject
*y
, PyObject
*compare
)
938 assert(compare
!= NULL
);
939 /* Call the user's comparison function and translate the 3-way
940 * result into true or false (or error).
942 args
= PyTuple_New(2);
947 PyTuple_SET_ITEM(args
, 0, x
);
948 PyTuple_SET_ITEM(args
, 1, y
);
949 res
= PyObject_Call(compare
, args
, NULL
);
953 if (!PyInt_Check(res
)) {
955 PyErr_SetString(PyExc_TypeError
,
956 "comparison function must return int");
959 i
= PyInt_AsLong(res
);
964 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
965 * islt. This avoids a layer of function call in the usual case, and
966 * sorting does many comparisons.
967 * Returns -1 on error, 1 if x < y, 0 if x >= y.
969 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
970 PyObject_RichCompareBool(X, Y, Py_LT) : \
973 /* Compare X to Y via "<". Goto "fail" if the comparison raises an
974 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
975 started. It makes more sense in context <wink>. X and Y are PyObject*s.
977 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
980 /* binarysort is the best method for sorting small arrays: it does
981 few compares, but can do data movement quadratic in the number of
983 [lo, hi) is a contiguous slice of a list, and is sorted via
984 binary insertion. This sort is stable.
985 On entry, must have lo <= start <= hi, and that [lo, start) is already
986 sorted (pass start == lo if you don't know!).
987 If islt() complains return -1, else 0.
988 Even in case of error, the output slice will be some permutation of
989 the input (nothing is lost or duplicated).
992 binarysort(PyObject
**lo
, PyObject
**hi
, PyObject
**start
, PyObject
*compare
)
993 /* compare -- comparison function object, or NULL for default */
995 register Py_ssize_t k
;
996 register PyObject
**l
, **p
, **r
;
997 register PyObject
*pivot
;
999 assert(lo
<= start
&& start
<= hi
);
1000 /* assert [lo, start) is sorted */
1003 for (; start
< hi
; ++start
) {
1004 /* set l to where *start belongs */
1009 * pivot >= all in [lo, l).
1010 * pivot < all in [r, start).
1011 * The second is vacuously true at the start.
1015 p
= l
+ ((r
- l
) >> 1);
1022 /* The invariants still hold, so pivot >= all in [lo, l) and
1023 pivot < all in [l, start), so pivot belongs at l. Note
1024 that if there are elements equal to pivot, l points to the
1025 first slot after them -- that's why this sort is stable.
1026 Slide over to make room.
1027 Caution: using memmove is much slower under MSVC 5;
1028 we're not usually moving many slots. */
1029 for (p
= start
; p
> l
; --p
)
1040 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1041 is required on entry. "A run" is the longest ascending sequence, with
1043 lo[0] <= lo[1] <= lo[2] <= ...
1045 or the longest descending sequence, with
1047 lo[0] > lo[1] > lo[2] > ...
1049 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1050 For its intended use in a stable mergesort, the strictness of the defn of
1051 "descending" is needed so that the caller can safely reverse a descending
1052 sequence without violating stability (strict > ensures there are no equal
1053 elements to get out of order).
1055 Returns -1 in case of error.
1058 count_run(PyObject
**lo
, PyObject
**hi
, PyObject
*compare
, int *descending
)
1070 IFLT(*lo
, *(lo
-1)) {
1072 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1080 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1092 Locate the proper position of key in a sorted vector; if the vector contains
1093 an element equal to key, return the position immediately to the left of
1094 the leftmost equal element. [gallop_right() does the same except returns
1095 the position to the right of the rightmost equal element (if any).]
1097 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
1099 "hint" is an index at which to begin the search, 0 <= hint < n. The closer
1100 hint is to the final result, the faster this runs.
1102 The return value is the int k in 0..n such that
1104 a[k-1] < key <= a[k]
1106 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1107 key belongs at index k; or, IOW, the first k elements of a should precede
1108 key, and the last n-k should follow key.
1110 Returns -1 on error. See listsort.txt for info on the method.
1113 gallop_left(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1119 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1125 /* a[hint] < key -- gallop right, until
1126 * a[hint + lastofs] < key <= a[hint + ofs]
1128 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1129 while (ofs
< maxofs
) {
1132 ofs
= (ofs
<< 1) + 1;
1133 if (ofs
<= 0) /* int overflow */
1136 else /* key <= a[hint + ofs] */
1141 /* Translate back to offsets relative to &a[0]. */
1146 /* key <= a[hint] -- gallop left, until
1147 * a[hint - ofs] < key <= a[hint - lastofs]
1149 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1150 while (ofs
< maxofs
) {
1153 /* key <= a[hint - ofs] */
1155 ofs
= (ofs
<< 1) + 1;
1156 if (ofs
<= 0) /* int overflow */
1161 /* Translate back to positive offsets relative to &a[0]. */
1163 lastofs
= hint
- ofs
;
1168 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1169 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1170 * right of lastofs but no farther right than ofs. Do a binary
1171 * search, with invariant a[lastofs-1] < key <= a[ofs].
1174 while (lastofs
< ofs
) {
1175 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1178 lastofs
= m
+1; /* a[m] < key */
1180 ofs
= m
; /* key <= a[m] */
1182 assert(lastofs
== ofs
); /* so a[ofs-1] < key <= a[ofs] */
1190 Exactly like gallop_left(), except that if key already exists in a[0:n],
1191 finds the position immediately to the right of the rightmost equal value.
1193 The return value is the int k in 0..n such that
1195 a[k-1] <= key < a[k]
1199 The code duplication is massive, but this is enough different given that
1200 we're sticking to "<" comparisons that it's much harder to follow if
1201 written as one routine with yet another "left or right?" flag.
1204 gallop_right(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1210 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1216 /* key < a[hint] -- gallop left, until
1217 * a[hint - ofs] <= key < a[hint - lastofs]
1219 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1220 while (ofs
< maxofs
) {
1221 IFLT(key
, *(a
-ofs
)) {
1223 ofs
= (ofs
<< 1) + 1;
1224 if (ofs
<= 0) /* int overflow */
1227 else /* a[hint - ofs] <= key */
1232 /* Translate back to positive offsets relative to &a[0]. */
1234 lastofs
= hint
- ofs
;
1238 /* a[hint] <= key -- gallop right, until
1239 * a[hint + lastofs] <= key < a[hint + ofs]
1241 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1242 while (ofs
< maxofs
) {
1245 /* a[hint + ofs] <= key */
1247 ofs
= (ofs
<< 1) + 1;
1248 if (ofs
<= 0) /* int overflow */
1253 /* Translate back to offsets relative to &a[0]. */
1259 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1260 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1261 * right of lastofs but no farther right than ofs. Do a binary
1262 * search, with invariant a[lastofs-1] <= key < a[ofs].
1265 while (lastofs
< ofs
) {
1266 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1269 ofs
= m
; /* key < a[m] */
1271 lastofs
= m
+1; /* a[m] <= key */
1273 assert(lastofs
== ofs
); /* so a[ofs-1] <= key < a[ofs] */
1280 /* The maximum number of entries in a MergeState's pending-runs stack.
1281 * This is enough to sort arrays of size up to about
1282 * 32 * phi ** MAX_MERGE_PENDING
1283 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1284 * with 2**64 elements.
1286 #define MAX_MERGE_PENDING 85
1288 /* When we get into galloping mode, we stay there until both runs win less
1289 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1291 #define MIN_GALLOP 7
1293 /* Avoid malloc for small temp arrays. */
1294 #define MERGESTATE_TEMP_SIZE 256
1296 /* One MergeState exists on the stack per invocation of mergesort. It's just
1297 * a convenient way to pass state around among the helper functions.
1304 typedef struct s_MergeState
{
1305 /* The user-supplied comparison function. or NULL if none given. */
1308 /* This controls when we get *into* galloping mode. It's initialized
1309 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1310 * random data, and lower for highly structured data.
1312 Py_ssize_t min_gallop
;
1314 /* 'a' is temp storage to help with merges. It contains room for
1317 PyObject
**a
; /* may point to temparray below */
1320 /* A stack of n pending runs yet to be merged. Run #i starts at
1321 * address base[i] and extends for len[i] elements. It's always
1322 * true (so long as the indices are in bounds) that
1324 * pending[i].base + pending[i].len == pending[i+1].base
1326 * so we could cut the storage for this, but it's a minor amount,
1327 * and keeping all the info explicit simplifies the code.
1330 struct s_slice pending
[MAX_MERGE_PENDING
];
1332 /* 'a' points to this when possible, rather than muck with malloc. */
1333 PyObject
*temparray
[MERGESTATE_TEMP_SIZE
];
1336 /* Conceptually a MergeState's constructor. */
1338 merge_init(MergeState
*ms
, PyObject
*compare
)
1341 ms
->compare
= compare
;
1342 ms
->a
= ms
->temparray
;
1343 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1345 ms
->min_gallop
= MIN_GALLOP
;
1348 /* Free all the temp memory owned by the MergeState. This must be called
1349 * when you're done with a MergeState, and may be called before then if
1350 * you want to free the temp memory early.
1353 merge_freemem(MergeState
*ms
)
1356 if (ms
->a
!= ms
->temparray
)
1358 ms
->a
= ms
->temparray
;
1359 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1362 /* Ensure enough temp memory for 'need' array slots is available.
1363 * Returns 0 on success and -1 if the memory can't be gotten.
1366 merge_getmem(MergeState
*ms
, Py_ssize_t need
)
1369 if (need
<= ms
->alloced
)
1371 /* Don't realloc! That can cost cycles to copy the old data, but
1372 * we don't care what's in the block.
1375 ms
->a
= (PyObject
**)PyMem_Malloc(need
* sizeof(PyObject
*));
1381 merge_freemem(ms
); /* reset to sane state */
1384 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1385 merge_getmem(MS, NEED))
1387 /* Merge the na elements starting at pa with the nb elements starting at pb
1388 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1389 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1390 * merge, and should have na <= nb. See listsort.txt for more info.
1391 * Return 0 if successful, -1 if error.
1394 merge_lo(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
,
1395 PyObject
**pb
, Py_ssize_t nb
)
1400 int result
= -1; /* guilty until proved innocent */
1401 Py_ssize_t min_gallop
= ms
->min_gallop
;
1403 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1404 if (MERGE_GETMEM(ms
, na
) < 0)
1406 memcpy(ms
->a
, pa
, na
* sizeof(PyObject
*));
1417 compare
= ms
->compare
;
1419 Py_ssize_t acount
= 0; /* # of times A won in a row */
1420 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1422 /* Do the straightforward thing until (if ever) one run
1423 * appears to win consistently.
1426 assert(na
> 1 && nb
> 0);
1427 k
= ISLT(*pb
, *pa
, compare
);
1437 if (bcount
>= min_gallop
)
1447 if (acount
>= min_gallop
)
1452 /* One run is winning so consistently that galloping may
1453 * be a huge win. So try that, and continue galloping until
1454 * (if ever) neither run appears to be winning consistently
1459 assert(na
> 1 && nb
> 0);
1460 min_gallop
-= min_gallop
> 1;
1461 ms
->min_gallop
= min_gallop
;
1462 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1467 memcpy(dest
, pa
, k
* sizeof(PyObject
*));
1473 /* na==0 is impossible now if the comparison
1474 * function is consistent, but we can't assume
1485 k
= gallop_left(*pa
, pb
, nb
, 0, compare
);
1490 memmove(dest
, pb
, k
* sizeof(PyObject
*));
1501 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1502 ++min_gallop
; /* penalize it for leaving galloping mode */
1503 ms
->min_gallop
= min_gallop
;
1509 memcpy(dest
, pa
, na
* sizeof(PyObject
*));
1512 assert(na
== 1 && nb
> 0);
1513 /* The last element of pa belongs at the end of the merge. */
1514 memmove(dest
, pb
, nb
* sizeof(PyObject
*));
1519 /* Merge the na elements starting at pa with the nb elements starting at pb
1520 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1521 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1522 * merge, and should have na >= nb. See listsort.txt for more info.
1523 * Return 0 if successful, -1 if error.
1526 merge_hi(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
, PyObject
**pb
, Py_ssize_t nb
)
1531 int result
= -1; /* guilty until proved innocent */
1534 Py_ssize_t min_gallop
= ms
->min_gallop
;
1536 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1537 if (MERGE_GETMEM(ms
, nb
) < 0)
1540 memcpy(ms
->a
, pb
, nb
* sizeof(PyObject
*));
1543 pb
= ms
->a
+ nb
- 1;
1553 compare
= ms
->compare
;
1555 Py_ssize_t acount
= 0; /* # of times A won in a row */
1556 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1558 /* Do the straightforward thing until (if ever) one run
1559 * appears to win consistently.
1562 assert(na
> 0 && nb
> 1);
1563 k
= ISLT(*pb
, *pa
, compare
);
1573 if (acount
>= min_gallop
)
1583 if (bcount
>= min_gallop
)
1588 /* One run is winning so consistently that galloping may
1589 * be a huge win. So try that, and continue galloping until
1590 * (if ever) neither run appears to be winning consistently
1595 assert(na
> 0 && nb
> 1);
1596 min_gallop
-= min_gallop
> 1;
1597 ms
->min_gallop
= min_gallop
;
1598 k
= gallop_right(*pb
, basea
, na
, na
-1, compare
);
1606 memmove(dest
+1, pa
+1, k
* sizeof(PyObject
*));
1616 k
= gallop_left(*pa
, baseb
, nb
, nb
-1, compare
);
1624 memcpy(dest
+1, pb
+1, k
* sizeof(PyObject
*));
1628 /* nb==0 is impossible now if the comparison
1629 * function is consistent, but we can't assume
1639 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1640 ++min_gallop
; /* penalize it for leaving galloping mode */
1641 ms
->min_gallop
= min_gallop
;
1647 memcpy(dest
-(nb
-1), baseb
, nb
* sizeof(PyObject
*));
1650 assert(nb
== 1 && na
> 0);
1651 /* The first element of pb belongs at the front of the merge. */
1654 memmove(dest
+1, pa
+1, na
* sizeof(PyObject
*));
1659 /* Merge the two runs at stack indices i and i+1.
1660 * Returns 0 on success, -1 on error.
1663 merge_at(MergeState
*ms
, Py_ssize_t i
)
1665 PyObject
**pa
, **pb
;
1673 assert(i
== ms
->n
- 2 || i
== ms
->n
- 3);
1675 pa
= ms
->pending
[i
].base
;
1676 na
= ms
->pending
[i
].len
;
1677 pb
= ms
->pending
[i
+1].base
;
1678 nb
= ms
->pending
[i
+1].len
;
1679 assert(na
> 0 && nb
> 0);
1680 assert(pa
+ na
== pb
);
1682 /* Record the length of the combined runs; if i is the 3rd-last
1683 * run now, also slide over the last run (which isn't involved
1684 * in this merge). The current run i+1 goes away in any case.
1686 ms
->pending
[i
].len
= na
+ nb
;
1688 ms
->pending
[i
+1] = ms
->pending
[i
+2];
1691 /* Where does b start in a? Elements in a before that can be
1692 * ignored (already in place).
1694 compare
= ms
->compare
;
1695 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1703 /* Where does a end in b? Elements in b after that can be
1704 * ignored (already in place).
1706 nb
= gallop_left(pa
[na
-1], pb
, nb
, nb
-1, compare
);
1710 /* Merge what remains of the runs, using a temp array with
1711 * min(na, nb) elements.
1714 return merge_lo(ms
, pa
, na
, pb
, nb
);
1716 return merge_hi(ms
, pa
, na
, pb
, nb
);
1719 /* Examine the stack of runs waiting to be merged, merging adjacent runs
1720 * until the stack invariants are re-established:
1722 * 1. len[-3] > len[-2] + len[-1]
1723 * 2. len[-2] > len[-1]
1725 * See listsort.txt for more info.
1727 * Returns 0 on success, -1 on error.
1730 merge_collapse(MergeState
*ms
)
1732 struct s_slice
*p
= ms
->pending
;
1736 Py_ssize_t n
= ms
->n
- 2;
1737 if (n
> 0 && p
[n
-1].len
<= p
[n
].len
+ p
[n
+1].len
) {
1738 if (p
[n
-1].len
< p
[n
+1].len
)
1740 if (merge_at(ms
, n
) < 0)
1743 else if (p
[n
].len
<= p
[n
+1].len
) {
1744 if (merge_at(ms
, n
) < 0)
1753 /* Regardless of invariants, merge all runs on the stack until only one
1754 * remains. This is used at the end of the mergesort.
1756 * Returns 0 on success, -1 on error.
1759 merge_force_collapse(MergeState
*ms
)
1761 struct s_slice
*p
= ms
->pending
;
1765 Py_ssize_t n
= ms
->n
- 2;
1766 if (n
> 0 && p
[n
-1].len
< p
[n
+1].len
)
1768 if (merge_at(ms
, n
) < 0)
1774 /* Compute a good value for the minimum run length; natural runs shorter
1775 * than this are boosted artificially via binary insertion.
1777 * If n < 64, return n (it's too small to bother with fancy stuff).
1778 * Else if n is an exact power of 2, return 32.
1779 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1780 * strictly less than, an exact power of 2.
1782 * See listsort.txt for more info.
1785 merge_compute_minrun(Py_ssize_t n
)
1787 Py_ssize_t r
= 0; /* becomes 1 if any 1 bits are shifted off */
1797 /* Special wrapper to support stable sorting using the decorate-sort-undecorate
1798 pattern. Holds a key which is used for comparisons and the original record
1799 which is returned during the undecorate phase. By exposing only the key
1800 during comparisons, the underlying sort stability characteristics are left
1801 unchanged. Also, if a custom comparison function is used, it will only see
1802 the key instead of a full record. */
1808 } sortwrapperobject
;
1810 PyDoc_STRVAR(sortwrapper_doc
, "Object wrapper with a custom sort key.");
1812 sortwrapper_richcompare(sortwrapperobject
*, sortwrapperobject
*, int);
1814 sortwrapper_dealloc(sortwrapperobject
*);
1816 static PyTypeObject sortwrapper_type
= {
1817 PyObject_HEAD_INIT(&PyType_Type
)
1819 "sortwrapper", /* tp_name */
1820 sizeof(sortwrapperobject
), /* tp_basicsize */
1821 0, /* tp_itemsize */
1823 (destructor
)sortwrapper_dealloc
, /* tp_dealloc */
1829 0, /* tp_as_number */
1830 0, /* tp_as_sequence */
1831 0, /* tp_as_mapping */
1835 PyObject_GenericGetAttr
, /* tp_getattro */
1836 0, /* tp_setattro */
1837 0, /* tp_as_buffer */
1838 Py_TPFLAGS_DEFAULT
|
1839 Py_TPFLAGS_HAVE_RICHCOMPARE
, /* tp_flags */
1840 sortwrapper_doc
, /* tp_doc */
1841 0, /* tp_traverse */
1843 (richcmpfunc
)sortwrapper_richcompare
, /* tp_richcompare */
1848 sortwrapper_richcompare(sortwrapperobject
*a
, sortwrapperobject
*b
, int op
)
1850 if (!PyObject_TypeCheck(b
, &sortwrapper_type
)) {
1851 PyErr_SetString(PyExc_TypeError
,
1852 "expected a sortwrapperobject");
1855 return PyObject_RichCompare(a
->key
, b
->key
, op
);
1859 sortwrapper_dealloc(sortwrapperobject
*so
)
1861 Py_XDECREF(so
->key
);
1862 Py_XDECREF(so
->value
);
1866 /* Returns a new reference to a sortwrapper.
1867 Consumes the references to the two underlying objects. */
1870 build_sortwrapper(PyObject
*key
, PyObject
*value
)
1872 sortwrapperobject
*so
;
1874 so
= PyObject_New(sortwrapperobject
, &sortwrapper_type
);
1879 return (PyObject
*)so
;
1882 /* Returns a new reference to the value underlying the wrapper. */
1884 sortwrapper_getvalue(PyObject
*so
)
1888 if (!PyObject_TypeCheck(so
, &sortwrapper_type
)) {
1889 PyErr_SetString(PyExc_TypeError
,
1890 "expected a sortwrapperobject");
1893 value
= ((sortwrapperobject
*)so
)->value
;
1898 /* Wrapper for user specified cmp functions in combination with a
1899 specified key function. Makes sure the cmp function is presented
1900 with the actual key instead of the sortwrapper */
1908 cmpwrapper_dealloc(cmpwrapperobject
*co
)
1910 Py_XDECREF(co
->func
);
1915 cmpwrapper_call(cmpwrapperobject
*co
, PyObject
*args
, PyObject
*kwds
)
1917 PyObject
*x
, *y
, *xx
, *yy
;
1919 if (!PyArg_UnpackTuple(args
, "", 2, 2, &x
, &y
))
1921 if (!PyObject_TypeCheck(x
, &sortwrapper_type
) ||
1922 !PyObject_TypeCheck(y
, &sortwrapper_type
)) {
1923 PyErr_SetString(PyExc_TypeError
,
1924 "expected a sortwrapperobject");
1927 xx
= ((sortwrapperobject
*)x
)->key
;
1928 yy
= ((sortwrapperobject
*)y
)->key
;
1929 return PyObject_CallFunctionObjArgs(co
->func
, xx
, yy
, NULL
);
1932 PyDoc_STRVAR(cmpwrapper_doc
, "cmp() wrapper for sort with custom keys.");
1934 static PyTypeObject cmpwrapper_type
= {
1935 PyObject_HEAD_INIT(&PyType_Type
)
1937 "cmpwrapper", /* tp_name */
1938 sizeof(cmpwrapperobject
), /* tp_basicsize */
1939 0, /* tp_itemsize */
1941 (destructor
)cmpwrapper_dealloc
, /* tp_dealloc */
1947 0, /* tp_as_number */
1948 0, /* tp_as_sequence */
1949 0, /* tp_as_mapping */
1951 (ternaryfunc
)cmpwrapper_call
, /* tp_call */
1953 PyObject_GenericGetAttr
, /* tp_getattro */
1954 0, /* tp_setattro */
1955 0, /* tp_as_buffer */
1956 Py_TPFLAGS_DEFAULT
, /* tp_flags */
1957 cmpwrapper_doc
, /* tp_doc */
1961 build_cmpwrapper(PyObject
*cmpfunc
)
1963 cmpwrapperobject
*co
;
1965 co
= PyObject_New(cmpwrapperobject
, &cmpwrapper_type
);
1970 return (PyObject
*)co
;
1973 /* An adaptive, stable, natural mergesort. See listsort.txt.
1974 * Returns Py_None on success, NULL on error. Even in case of error, the
1975 * list will be some permutation of its input state (nothing is lost or
1979 listsort(PyListObject
*self
, PyObject
*args
, PyObject
*kwds
)
1982 PyObject
**lo
, **hi
;
1983 Py_ssize_t nremaining
;
1985 Py_ssize_t saved_ob_size
, saved_allocated
;
1986 PyObject
**saved_ob_item
;
1987 PyObject
**final_ob_item
;
1988 PyObject
*compare
= NULL
;
1989 PyObject
*result
= NULL
; /* guilty until proved innocent */
1991 PyObject
*keyfunc
= NULL
;
1993 PyObject
*key
, *value
, *kvpair
;
1994 static char *kwlist
[] = {"cmp", "key", "reverse", 0};
1996 assert(self
!= NULL
);
1997 assert (PyList_Check(self
));
1999 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|OOi:sort",
2000 kwlist
, &compare
, &keyfunc
, &reverse
))
2003 if (compare
== Py_None
)
2005 if (keyfunc
== Py_None
)
2007 if (compare
!= NULL
&& keyfunc
!= NULL
) {
2008 compare
= build_cmpwrapper(compare
);
2009 if (compare
== NULL
)
2012 Py_XINCREF(compare
);
2014 /* The list is temporarily made empty, so that mutations performed
2015 * by comparison functions can't affect the slice of memory we're
2016 * sorting (allowing mutations during sorting is a core-dump
2017 * factory, since ob_item may change).
2019 saved_ob_size
= self
->ob_size
;
2020 saved_ob_item
= self
->ob_item
;
2021 saved_allocated
= self
->allocated
;
2023 self
->ob_item
= NULL
;
2024 self
->allocated
= -1; /* any operation will reset it to >= 0 */
2026 if (keyfunc
!= NULL
) {
2027 for (i
=0 ; i
< saved_ob_size
; i
++) {
2028 value
= saved_ob_item
[i
];
2029 key
= PyObject_CallFunctionObjArgs(keyfunc
, value
,
2032 for (i
=i
-1 ; i
>=0 ; i
--) {
2033 kvpair
= saved_ob_item
[i
];
2034 value
= sortwrapper_getvalue(kvpair
);
2035 saved_ob_item
[i
] = value
;
2040 kvpair
= build_sortwrapper(key
, value
);
2043 saved_ob_item
[i
] = kvpair
;
2047 /* Reverse sort stability achieved by initially reversing the list,
2048 applying a stable forward sort, then reversing the final result. */
2049 if (reverse
&& saved_ob_size
> 1)
2050 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2052 merge_init(&ms
, compare
);
2054 nremaining
= saved_ob_size
;
2058 /* March over the array once, left to right, finding natural runs,
2059 * and extending short natural runs to minrun elements.
2062 hi
= lo
+ nremaining
;
2063 minrun
= merge_compute_minrun(nremaining
);
2068 /* Identify next run. */
2069 n
= count_run(lo
, hi
, compare
, &descending
);
2073 reverse_slice(lo
, lo
+ n
);
2074 /* If short, extend to min(minrun, nremaining). */
2076 const Py_ssize_t force
= nremaining
<= minrun
?
2077 nremaining
: minrun
;
2078 if (binarysort(lo
, lo
+ force
, lo
+ n
, compare
) < 0)
2082 /* Push run onto pending-runs stack, and maybe merge. */
2083 assert(ms
.n
< MAX_MERGE_PENDING
);
2084 ms
.pending
[ms
.n
].base
= lo
;
2085 ms
.pending
[ms
.n
].len
= n
;
2087 if (merge_collapse(&ms
) < 0)
2089 /* Advance to find next run. */
2092 } while (nremaining
);
2095 if (merge_force_collapse(&ms
) < 0)
2098 assert(ms
.pending
[0].base
== saved_ob_item
);
2099 assert(ms
.pending
[0].len
== saved_ob_size
);
2104 if (keyfunc
!= NULL
) {
2105 for (i
=0 ; i
< saved_ob_size
; i
++) {
2106 kvpair
= saved_ob_item
[i
];
2107 value
= sortwrapper_getvalue(kvpair
);
2108 saved_ob_item
[i
] = value
;
2113 if (self
->allocated
!= -1 && result
!= NULL
) {
2114 /* The user mucked with the list during the sort,
2115 * and we don't already have another error to report.
2117 PyErr_SetString(PyExc_ValueError
, "list modified during sort");
2121 if (reverse
&& saved_ob_size
> 1)
2122 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2127 final_ob_item
= self
->ob_item
;
2129 self
->ob_size
= saved_ob_size
;
2130 self
->ob_item
= saved_ob_item
;
2131 self
->allocated
= saved_allocated
;
2132 if (final_ob_item
!= NULL
) {
2133 /* we cannot use list_clear() for this because it does not
2134 guarantee that the list is really empty when it returns */
2136 Py_XDECREF(final_ob_item
[i
]);
2138 PyMem_FREE(final_ob_item
);
2140 Py_XDECREF(compare
);
2148 PyList_Sort(PyObject
*v
)
2150 if (v
== NULL
|| !PyList_Check(v
)) {
2151 PyErr_BadInternalCall();
2154 v
= listsort((PyListObject
*)v
, (PyObject
*)NULL
, (PyObject
*)NULL
);
2162 listreverse(PyListObject
*self
)
2164 if (self
->ob_size
> 1)
2165 reverse_slice(self
->ob_item
, self
->ob_item
+ self
->ob_size
);
2170 PyList_Reverse(PyObject
*v
)
2172 PyListObject
*self
= (PyListObject
*)v
;
2174 if (v
== NULL
|| !PyList_Check(v
)) {
2175 PyErr_BadInternalCall();
2178 if (self
->ob_size
> 1)
2179 reverse_slice(self
->ob_item
, self
->ob_item
+ self
->ob_size
);
2184 PyList_AsTuple(PyObject
*v
)
2189 if (v
== NULL
|| !PyList_Check(v
)) {
2190 PyErr_BadInternalCall();
2193 n
= ((PyListObject
*)v
)->ob_size
;
2197 p
= ((PyTupleObject
*)w
)->ob_item
;
2199 (void *)((PyListObject
*)v
)->ob_item
,
2200 n
*sizeof(PyObject
*));
2209 listindex(PyListObject
*self
, PyObject
*args
)
2211 Py_ssize_t i
, start
=0, stop
=self
->ob_size
;
2214 if (!PyArg_ParseTuple(args
, "O|O&O&:index", &v
,
2215 _PyEval_SliceIndex
, &start
,
2216 _PyEval_SliceIndex
, &stop
))
2219 start
+= self
->ob_size
;
2224 stop
+= self
->ob_size
;
2228 for (i
= start
; i
< stop
&& i
< self
->ob_size
; i
++) {
2229 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2231 return PyInt_FromSsize_t(i
);
2235 PyErr_SetString(PyExc_ValueError
, "list.index(x): x not in list");
2240 listcount(PyListObject
*self
, PyObject
*v
)
2242 Py_ssize_t count
= 0;
2245 for (i
= 0; i
< self
->ob_size
; i
++) {
2246 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2252 return PyInt_FromSsize_t(count
);
2256 listremove(PyListObject
*self
, PyObject
*v
)
2260 for (i
= 0; i
< self
->ob_size
; i
++) {
2261 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2263 if (list_ass_slice(self
, i
, i
+1,
2264 (PyObject
*)NULL
) == 0)
2271 PyErr_SetString(PyExc_ValueError
, "list.remove(x): x not in list");
2276 list_traverse(PyListObject
*o
, visitproc visit
, void *arg
)
2280 for (i
= o
->ob_size
; --i
>= 0; )
2281 Py_VISIT(o
->ob_item
[i
]);
2286 list_richcompare(PyObject
*v
, PyObject
*w
, int op
)
2288 PyListObject
*vl
, *wl
;
2291 if (!PyList_Check(v
) || !PyList_Check(w
)) {
2292 Py_INCREF(Py_NotImplemented
);
2293 return Py_NotImplemented
;
2296 vl
= (PyListObject
*)v
;
2297 wl
= (PyListObject
*)w
;
2299 if (vl
->ob_size
!= wl
->ob_size
&& (op
== Py_EQ
|| op
== Py_NE
)) {
2300 /* Shortcut: if the lengths differ, the lists differ */
2310 /* Search for the first index where items are different */
2311 for (i
= 0; i
< vl
->ob_size
&& i
< wl
->ob_size
; i
++) {
2312 int k
= PyObject_RichCompareBool(vl
->ob_item
[i
],
2313 wl
->ob_item
[i
], Py_EQ
);
2320 if (i
>= vl
->ob_size
|| i
>= wl
->ob_size
) {
2321 /* No more items to compare -- compare sizes */
2322 Py_ssize_t vs
= vl
->ob_size
;
2323 Py_ssize_t ws
= wl
->ob_size
;
2327 case Py_LT
: cmp
= vs
< ws
; break;
2328 case Py_LE
: cmp
= vs
<= ws
; break;
2329 case Py_EQ
: cmp
= vs
== ws
; break;
2330 case Py_NE
: cmp
= vs
!= ws
; break;
2331 case Py_GT
: cmp
= vs
> ws
; break;
2332 case Py_GE
: cmp
= vs
>= ws
; break;
2333 default: return NULL
; /* cannot happen */
2343 /* We have an item that differs -- shortcuts for EQ/NE */
2345 Py_INCREF(Py_False
);
2353 /* Compare the final item again using the proper operator */
2354 return PyObject_RichCompare(vl
->ob_item
[i
], wl
->ob_item
[i
], op
);
2358 list_init(PyListObject
*self
, PyObject
*args
, PyObject
*kw
)
2360 PyObject
*arg
= NULL
;
2361 static char *kwlist
[] = {"sequence", 0};
2363 if (!PyArg_ParseTupleAndKeywords(args
, kw
, "|O:list", kwlist
, &arg
))
2366 /* Verify list invariants established by PyType_GenericAlloc() */
2367 assert(0 <= self
->ob_size
);
2368 assert(self
->ob_size
<= self
->allocated
|| self
->allocated
== -1);
2369 assert(self
->ob_item
!= NULL
||
2370 self
->allocated
== 0 || self
->allocated
== -1);
2372 /* Empty previous contents */
2373 if (self
->ob_item
!= NULL
) {
2374 (void)list_clear(self
);
2377 PyObject
*rv
= listextend(self
, arg
);
2386 list_nohash(PyObject
*self
)
2388 PyErr_SetString(PyExc_TypeError
, "list objects are unhashable");
2392 static PyObject
*list_iter(PyObject
*seq
);
2393 static PyObject
*list_reversed(PyListObject
* seq
, PyObject
* unused
);
2395 PyDoc_STRVAR(getitem_doc
,
2396 "x.__getitem__(y) <==> x[y]");
2397 PyDoc_STRVAR(reversed_doc
,
2398 "L.__reversed__() -- return a reverse iterator over the list");
2399 PyDoc_STRVAR(append_doc
,
2400 "L.append(object) -- append object to end");
2401 PyDoc_STRVAR(extend_doc
,
2402 "L.extend(iterable) -- extend list by appending elements from the iterable");
2403 PyDoc_STRVAR(insert_doc
,
2404 "L.insert(index, object) -- insert object before index");
2405 PyDoc_STRVAR(pop_doc
,
2406 "L.pop([index]) -> item -- remove and return item at index (default last)");
2407 PyDoc_STRVAR(remove_doc
,
2408 "L.remove(value) -- remove first occurrence of value");
2409 PyDoc_STRVAR(index_doc
,
2410 "L.index(value, [start, [stop]]) -> integer -- return first index of value");
2411 PyDoc_STRVAR(count_doc
,
2412 "L.count(value) -> integer -- return number of occurrences of value");
2413 PyDoc_STRVAR(reverse_doc
,
2414 "L.reverse() -- reverse *IN PLACE*");
2415 PyDoc_STRVAR(sort_doc
,
2416 "L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
2417 cmp(x, y) -> -1, 0, 1");
2419 static PyObject
*list_subscript(PyListObject
*, PyObject
*);
2421 static PyMethodDef list_methods
[] = {
2422 {"__getitem__", (PyCFunction
)list_subscript
, METH_O
|METH_COEXIST
, getitem_doc
},
2423 {"__reversed__",(PyCFunction
)list_reversed
, METH_NOARGS
, reversed_doc
},
2424 {"append", (PyCFunction
)listappend
, METH_O
, append_doc
},
2425 {"insert", (PyCFunction
)listinsert
, METH_VARARGS
, insert_doc
},
2426 {"extend", (PyCFunction
)listextend
, METH_O
, extend_doc
},
2427 {"pop", (PyCFunction
)listpop
, METH_VARARGS
, pop_doc
},
2428 {"remove", (PyCFunction
)listremove
, METH_O
, remove_doc
},
2429 {"index", (PyCFunction
)listindex
, METH_VARARGS
, index_doc
},
2430 {"count", (PyCFunction
)listcount
, METH_O
, count_doc
},
2431 {"reverse", (PyCFunction
)listreverse
, METH_NOARGS
, reverse_doc
},
2432 {"sort", (PyCFunction
)listsort
, METH_VARARGS
| METH_KEYWORDS
, sort_doc
},
2433 {NULL
, NULL
} /* sentinel */
2436 static PySequenceMethods list_as_sequence
= {
2437 (lenfunc
)list_length
, /* sq_length */
2438 (binaryfunc
)list_concat
, /* sq_concat */
2439 (ssizeargfunc
)list_repeat
, /* sq_repeat */
2440 (ssizeargfunc
)list_item
, /* sq_item */
2441 (ssizessizeargfunc
)list_slice
, /* sq_slice */
2442 (ssizeobjargproc
)list_ass_item
, /* sq_ass_item */
2443 (ssizessizeobjargproc
)list_ass_slice
, /* sq_ass_slice */
2444 (objobjproc
)list_contains
, /* sq_contains */
2445 (binaryfunc
)list_inplace_concat
, /* sq_inplace_concat */
2446 (ssizeargfunc
)list_inplace_repeat
, /* sq_inplace_repeat */
2449 PyDoc_STRVAR(list_doc
,
2450 "list() -> new list\n"
2451 "list(sequence) -> new list initialized from sequence's items");
2453 #define HASINDEX(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_HAVE_INDEX)
2456 list_subscript(PyListObject
* self
, PyObject
* item
)
2458 PyNumberMethods
*nb
= item
->ob_type
->tp_as_number
;
2459 if (nb
!= NULL
&& HASINDEX(item
) && nb
->nb_index
!= NULL
) {
2460 Py_ssize_t i
= nb
->nb_index(item
);
2461 if (i
== -1 && PyErr_Occurred())
2464 i
+= PyList_GET_SIZE(self
);
2465 return list_item(self
, i
);
2467 else if (PySlice_Check(item
)) {
2468 Py_ssize_t start
, stop
, step
, slicelength
, cur
, i
;
2471 PyObject
**src
, **dest
;
2473 if (PySlice_GetIndicesEx((PySliceObject
*)item
, self
->ob_size
,
2474 &start
, &stop
, &step
, &slicelength
) < 0) {
2478 if (slicelength
<= 0) {
2479 return PyList_New(0);
2482 result
= PyList_New(slicelength
);
2483 if (!result
) return NULL
;
2485 src
= self
->ob_item
;
2486 dest
= ((PyListObject
*)result
)->ob_item
;
2487 for (cur
= start
, i
= 0; i
< slicelength
;
2498 PyErr_SetString(PyExc_TypeError
,
2499 "list indices must be integers");
2505 list_ass_subscript(PyListObject
* self
, PyObject
* item
, PyObject
* value
)
2507 PyNumberMethods
*nb
= item
->ob_type
->tp_as_number
;
2508 if (nb
!= NULL
&& HASINDEX(item
) && nb
->nb_index
!= NULL
) {
2509 Py_ssize_t i
= nb
->nb_index(item
);
2510 if (i
== -1 && PyErr_Occurred())
2513 i
+= PyList_GET_SIZE(self
);
2514 return list_ass_item(self
, i
, value
);
2516 else if (PySlice_Check(item
)) {
2517 Py_ssize_t start
, stop
, step
, slicelength
;
2519 if (PySlice_GetIndicesEx((PySliceObject
*)item
, self
->ob_size
,
2520 &start
, &stop
, &step
, &slicelength
) < 0) {
2524 /* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
2525 if (step
== 1 && ((PySliceObject
*)item
)->step
== Py_None
)
2526 return list_ass_slice(self
, start
, stop
, value
);
2528 if (value
== NULL
) {
2533 if (slicelength
<= 0)
2538 start
= stop
+ step
*(slicelength
- 1) - 1;
2542 garbage
= (PyObject
**)
2543 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2545 /* drawing pictures might help
2546 understand these for loops */
2547 for (cur
= start
, i
= 0;
2550 Py_ssize_t lim
= step
;
2552 garbage
[i
] = PyList_GET_ITEM(self
, cur
);
2554 if (cur
+ step
>= self
->ob_size
) {
2555 lim
= self
->ob_size
- cur
- 1;
2558 memmove(self
->ob_item
+ cur
- i
,
2559 self
->ob_item
+ cur
+ 1,
2560 lim
* sizeof(PyObject
*));
2563 for (cur
= start
+ slicelength
*step
+ 1;
2564 cur
< self
->ob_size
; cur
++) {
2565 PyList_SET_ITEM(self
, cur
- slicelength
,
2566 PyList_GET_ITEM(self
, cur
));
2569 self
->ob_size
-= slicelength
;
2570 list_resize(self
, self
->ob_size
);
2572 for (i
= 0; i
< slicelength
; i
++) {
2573 Py_DECREF(garbage
[i
]);
2575 PyMem_FREE(garbage
);
2581 PyObject
**garbage
, *ins
, *seq
, **seqitems
, **selfitems
;
2584 /* protect against a[::-1] = a */
2585 if (self
== (PyListObject
*)value
) {
2586 seq
= list_slice((PyListObject
*)value
, 0,
2587 PyList_GET_SIZE(value
));
2590 seq
= PySequence_Fast(value
,
2591 "must assign iterable to extended slice");
2596 if (PySequence_Fast_GET_SIZE(seq
) != slicelength
) {
2597 PyErr_Format(PyExc_ValueError
,
2598 "attempt to assign sequence of size %zd to extended slice of size %zd",
2599 PySequence_Fast_GET_SIZE(seq
),
2610 garbage
= (PyObject
**)
2611 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2613 selfitems
= self
->ob_item
;
2614 seqitems
= PySequence_Fast_ITEMS(seq
);
2615 for (cur
= start
, i
= 0; i
< slicelength
;
2617 garbage
[i
] = selfitems
[cur
];
2620 selfitems
[cur
] = ins
;
2623 for (i
= 0; i
< slicelength
; i
++) {
2624 Py_DECREF(garbage
[i
]);
2627 PyMem_FREE(garbage
);
2634 PyErr_SetString(PyExc_TypeError
,
2635 "list indices must be integers");
2640 static PyMappingMethods list_as_mapping
= {
2641 (lenfunc
)list_length
,
2642 (binaryfunc
)list_subscript
,
2643 (objobjargproc
)list_ass_subscript
2646 PyTypeObject PyList_Type
= {
2647 PyObject_HEAD_INIT(&PyType_Type
)
2650 sizeof(PyListObject
),
2652 (destructor
)list_dealloc
, /* tp_dealloc */
2653 (printfunc
)list_print
, /* tp_print */
2657 (reprfunc
)list_repr
, /* tp_repr */
2658 0, /* tp_as_number */
2659 &list_as_sequence
, /* tp_as_sequence */
2660 &list_as_mapping
, /* tp_as_mapping */
2661 list_nohash
, /* tp_hash */
2664 PyObject_GenericGetAttr
, /* tp_getattro */
2665 0, /* tp_setattro */
2666 0, /* tp_as_buffer */
2667 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2668 Py_TPFLAGS_BASETYPE
, /* tp_flags */
2669 list_doc
, /* tp_doc */
2670 (traverseproc
)list_traverse
, /* tp_traverse */
2671 (inquiry
)list_clear
, /* tp_clear */
2672 list_richcompare
, /* tp_richcompare */
2673 0, /* tp_weaklistoffset */
2674 list_iter
, /* tp_iter */
2675 0, /* tp_iternext */
2676 list_methods
, /* tp_methods */
2681 0, /* tp_descr_get */
2682 0, /* tp_descr_set */
2683 0, /* tp_dictoffset */
2684 (initproc
)list_init
, /* tp_init */
2685 PyType_GenericAlloc
, /* tp_alloc */
2686 PyType_GenericNew
, /* tp_new */
2687 PyObject_GC_Del
, /* tp_free */
2691 /*********************** List Iterator **************************/
2696 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2699 static PyObject
*list_iter(PyObject
*);
2700 static void listiter_dealloc(listiterobject
*);
2701 static int listiter_traverse(listiterobject
*, visitproc
, void *);
2702 static PyObject
*listiter_next(listiterobject
*);
2703 static PyObject
*listiter_len(listiterobject
*);
2705 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
2707 static PyMethodDef listiter_methods
[] = {
2708 {"__length_hint__", (PyCFunction
)listiter_len
, METH_NOARGS
, length_hint_doc
},
2709 {NULL
, NULL
} /* sentinel */
2712 PyTypeObject PyListIter_Type
= {
2713 PyObject_HEAD_INIT(&PyType_Type
)
2715 "listiterator", /* tp_name */
2716 sizeof(listiterobject
), /* tp_basicsize */
2717 0, /* tp_itemsize */
2719 (destructor
)listiter_dealloc
, /* tp_dealloc */
2725 0, /* tp_as_number */
2726 0, /* tp_as_sequence */
2727 0, /* tp_as_mapping */
2731 PyObject_GenericGetAttr
, /* tp_getattro */
2732 0, /* tp_setattro */
2733 0, /* tp_as_buffer */
2734 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2736 (traverseproc
)listiter_traverse
, /* tp_traverse */
2738 0, /* tp_richcompare */
2739 0, /* tp_weaklistoffset */
2740 PyObject_SelfIter
, /* tp_iter */
2741 (iternextfunc
)listiter_next
, /* tp_iternext */
2742 listiter_methods
, /* tp_methods */
2748 list_iter(PyObject
*seq
)
2752 if (!PyList_Check(seq
)) {
2753 PyErr_BadInternalCall();
2756 it
= PyObject_GC_New(listiterobject
, &PyListIter_Type
);
2761 it
->it_seq
= (PyListObject
*)seq
;
2762 _PyObject_GC_TRACK(it
);
2763 return (PyObject
*)it
;
2767 listiter_dealloc(listiterobject
*it
)
2769 _PyObject_GC_UNTRACK(it
);
2770 Py_XDECREF(it
->it_seq
);
2771 PyObject_GC_Del(it
);
2775 listiter_traverse(listiterobject
*it
, visitproc visit
, void *arg
)
2777 Py_VISIT(it
->it_seq
);
2782 listiter_next(listiterobject
*it
)
2791 assert(PyList_Check(seq
));
2793 if (it
->it_index
< PyList_GET_SIZE(seq
)) {
2794 item
= PyList_GET_ITEM(seq
, it
->it_index
);
2806 listiter_len(listiterobject
*it
)
2810 len
= PyList_GET_SIZE(it
->it_seq
) - it
->it_index
;
2812 return PyInt_FromSsize_t(len
);
2814 return PyInt_FromLong(0);
2816 /*********************** List Reverse Iterator **************************/
2820 Py_ssize_t it_index
;
2821 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2822 } listreviterobject
;
2824 static PyObject
*list_reversed(PyListObject
*, PyObject
*);
2825 static void listreviter_dealloc(listreviterobject
*);
2826 static int listreviter_traverse(listreviterobject
*, visitproc
, void *);
2827 static PyObject
*listreviter_next(listreviterobject
*);
2828 static Py_ssize_t
listreviter_len(listreviterobject
*);
2830 static PySequenceMethods listreviter_as_sequence
= {
2831 (lenfunc
)listreviter_len
, /* sq_length */
2835 PyTypeObject PyListRevIter_Type
= {
2836 PyObject_HEAD_INIT(&PyType_Type
)
2838 "listreverseiterator", /* tp_name */
2839 sizeof(listreviterobject
), /* tp_basicsize */
2840 0, /* tp_itemsize */
2842 (destructor
)listreviter_dealloc
, /* tp_dealloc */
2848 0, /* tp_as_number */
2849 &listreviter_as_sequence
, /* tp_as_sequence */
2850 0, /* tp_as_mapping */
2854 PyObject_GenericGetAttr
, /* tp_getattro */
2855 0, /* tp_setattro */
2856 0, /* tp_as_buffer */
2857 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2859 (traverseproc
)listreviter_traverse
, /* tp_traverse */
2861 0, /* tp_richcompare */
2862 0, /* tp_weaklistoffset */
2863 PyObject_SelfIter
, /* tp_iter */
2864 (iternextfunc
)listreviter_next
, /* tp_iternext */
2869 list_reversed(PyListObject
*seq
, PyObject
*unused
)
2871 listreviterobject
*it
;
2873 it
= PyObject_GC_New(listreviterobject
, &PyListRevIter_Type
);
2876 assert(PyList_Check(seq
));
2877 it
->it_index
= PyList_GET_SIZE(seq
) - 1;
2880 PyObject_GC_Track(it
);
2881 return (PyObject
*)it
;
2885 listreviter_dealloc(listreviterobject
*it
)
2887 PyObject_GC_UnTrack(it
);
2888 Py_XDECREF(it
->it_seq
);
2889 PyObject_GC_Del(it
);
2893 listreviter_traverse(listreviterobject
*it
, visitproc visit
, void *arg
)
2895 Py_VISIT(it
->it_seq
);
2900 listreviter_next(listreviterobject
*it
)
2903 Py_ssize_t index
= it
->it_index
;
2904 PyListObject
*seq
= it
->it_seq
;
2906 if (index
>=0 && index
< PyList_GET_SIZE(seq
)) {
2907 item
= PyList_GET_ITEM(seq
, index
);
2921 listreviter_len(listreviterobject
*it
)
2923 Py_ssize_t len
= it
->it_index
+ 1;
2924 if (it
->it_seq
== NULL
|| PyList_GET_SIZE(it
->it_seq
) < len
)