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 Py_SIZE(self
) = 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);
50 /* check for integer overflow */
51 if (new_allocated
> PY_SIZE_MAX
- newsize
) {
55 new_allocated
+= newsize
;
60 items
= self
->ob_item
;
61 if (new_allocated
<= ((~(size_t)0) / sizeof(PyObject
*)))
62 PyMem_RESIZE(items
, PyObject
*, new_allocated
);
69 self
->ob_item
= items
;
70 Py_SIZE(self
) = newsize
;
71 self
->allocated
= new_allocated
;
75 /* Debug statistic to compare allocations with reuse through the free list */
76 #undef SHOW_ALLOC_COUNT
77 #ifdef SHOW_ALLOC_COUNT
78 static size_t count_alloc
= 0;
79 static size_t count_reuse
= 0;
84 fprintf(stderr
, "List allocations: %" PY_FORMAT_SIZE_T
"d\n",
86 fprintf(stderr
, "List reuse through freelist: %" PY_FORMAT_SIZE_T
88 fprintf(stderr
, "%.2f%% reuse rate\n\n",
89 (100.0*count_reuse
/(count_alloc
+count_reuse
)));
93 /* Empty list reuse scheme to save calls to malloc and free */
94 #ifndef PyList_MAXFREELIST
95 #define PyList_MAXFREELIST 80
97 static PyListObject
*free_list
[PyList_MAXFREELIST
];
98 static int numfree
= 0;
106 op
= free_list
[--numfree
];
107 assert(PyList_CheckExact(op
));
113 PyList_New(Py_ssize_t size
)
117 #ifdef SHOW_ALLOC_COUNT
118 static int initialized
= 0;
120 Py_AtExit(show_alloc
);
126 PyErr_BadInternalCall();
129 nbytes
= size
* sizeof(PyObject
*);
130 /* Check for overflow without an actual overflow,
131 * which can cause compiler to optimise out */
132 if (size
> PY_SIZE_MAX
/ sizeof(PyObject
*))
133 return PyErr_NoMemory();
136 op
= free_list
[numfree
];
137 _Py_NewReference((PyObject
*)op
);
138 #ifdef SHOW_ALLOC_COUNT
142 op
= PyObject_GC_New(PyListObject
, &PyList_Type
);
145 #ifdef SHOW_ALLOC_COUNT
152 op
->ob_item
= (PyObject
**) PyMem_MALLOC(nbytes
);
153 if (op
->ob_item
== NULL
) {
155 return PyErr_NoMemory();
157 memset(op
->ob_item
, 0, nbytes
);
160 op
->allocated
= size
;
161 _PyObject_GC_TRACK(op
);
162 return (PyObject
*) op
;
166 PyList_Size(PyObject
*op
)
168 if (!PyList_Check(op
)) {
169 PyErr_BadInternalCall();
176 static PyObject
*indexerr
= NULL
;
179 PyList_GetItem(PyObject
*op
, Py_ssize_t i
)
181 if (!PyList_Check(op
)) {
182 PyErr_BadInternalCall();
185 if (i
< 0 || i
>= Py_SIZE(op
)) {
186 if (indexerr
== NULL
)
187 indexerr
= PyString_FromString(
188 "list index out of range");
189 PyErr_SetObject(PyExc_IndexError
, indexerr
);
192 return ((PyListObject
*)op
) -> ob_item
[i
];
196 PyList_SetItem(register PyObject
*op
, register Py_ssize_t i
,
197 register PyObject
*newitem
)
199 register PyObject
*olditem
;
200 register PyObject
**p
;
201 if (!PyList_Check(op
)) {
203 PyErr_BadInternalCall();
206 if (i
< 0 || i
>= Py_SIZE(op
)) {
208 PyErr_SetString(PyExc_IndexError
,
209 "list assignment index out of range");
212 p
= ((PyListObject
*)op
) -> ob_item
+ i
;
220 ins1(PyListObject
*self
, Py_ssize_t where
, PyObject
*v
)
222 Py_ssize_t i
, n
= Py_SIZE(self
);
225 PyErr_BadInternalCall();
228 if (n
== PY_SSIZE_T_MAX
) {
229 PyErr_SetString(PyExc_OverflowError
,
230 "cannot add more objects to list");
234 if (list_resize(self
, n
+1) == -1)
244 items
= self
->ob_item
;
245 for (i
= n
; --i
>= where
; )
246 items
[i
+1] = items
[i
];
253 PyList_Insert(PyObject
*op
, Py_ssize_t where
, PyObject
*newitem
)
255 if (!PyList_Check(op
)) {
256 PyErr_BadInternalCall();
259 return ins1((PyListObject
*)op
, where
, newitem
);
263 app1(PyListObject
*self
, PyObject
*v
)
265 Py_ssize_t n
= PyList_GET_SIZE(self
);
268 if (n
== PY_SSIZE_T_MAX
) {
269 PyErr_SetString(PyExc_OverflowError
,
270 "cannot add more objects to list");
274 if (list_resize(self
, n
+1) == -1)
278 PyList_SET_ITEM(self
, n
, v
);
283 PyList_Append(PyObject
*op
, PyObject
*newitem
)
285 if (PyList_Check(op
) && (newitem
!= NULL
))
286 return app1((PyListObject
*)op
, newitem
);
287 PyErr_BadInternalCall();
294 list_dealloc(PyListObject
*op
)
297 PyObject_GC_UnTrack(op
);
298 Py_TRASHCAN_SAFE_BEGIN(op
)
299 if (op
->ob_item
!= NULL
) {
300 /* Do it backwards, for Christian Tismer.
301 There's a simple test case where somehow this reduces
302 thrashing when a *very* large list is created and
303 immediately deleted. */
306 Py_XDECREF(op
->ob_item
[i
]);
308 PyMem_FREE(op
->ob_item
);
310 if (numfree
< PyList_MAXFREELIST
&& PyList_CheckExact(op
))
311 free_list
[numfree
++] = op
;
313 Py_TYPE(op
)->tp_free((PyObject
*)op
);
314 Py_TRASHCAN_SAFE_END(op
)
318 list_print(PyListObject
*op
, FILE *fp
, int flags
)
324 rc
= Py_ReprEnter((PyObject
*)op
);
328 Py_BEGIN_ALLOW_THREADS
329 fprintf(fp
, "[...]");
333 Py_BEGIN_ALLOW_THREADS
336 for (i
= 0; i
< Py_SIZE(op
); i
++) {
337 item
= op
->ob_item
[i
];
340 Py_BEGIN_ALLOW_THREADS
344 if (PyObject_Print(item
, fp
, 0) != 0) {
346 Py_ReprLeave((PyObject
*)op
);
351 Py_BEGIN_ALLOW_THREADS
354 Py_ReprLeave((PyObject
*)op
);
359 list_repr(PyListObject
*v
)
363 PyObject
*pieces
= NULL
, *result
= NULL
;
365 i
= Py_ReprEnter((PyObject
*)v
);
367 return i
> 0 ? PyString_FromString("[...]") : NULL
;
370 if (Py_SIZE(v
) == 0) {
371 result
= PyString_FromString("[]");
375 pieces
= PyList_New(0);
379 /* Do repr() on each element. Note that this may mutate the list,
380 so must refetch the list size on each iteration. */
381 for (i
= 0; i
< Py_SIZE(v
); ++i
) {
383 if (Py_EnterRecursiveCall(" while getting the repr of a list"))
385 s
= PyObject_Repr(v
->ob_item
[i
]);
386 Py_LeaveRecursiveCall();
389 status
= PyList_Append(pieces
, s
);
390 Py_DECREF(s
); /* append created a new ref */
395 /* Add "[]" decorations to the first and last items. */
396 assert(PyList_GET_SIZE(pieces
) > 0);
397 s
= PyString_FromString("[");
400 temp
= PyList_GET_ITEM(pieces
, 0);
401 PyString_ConcatAndDel(&s
, temp
);
402 PyList_SET_ITEM(pieces
, 0, s
);
406 s
= PyString_FromString("]");
409 temp
= PyList_GET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1);
410 PyString_ConcatAndDel(&temp
, s
);
411 PyList_SET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1, temp
);
415 /* Paste them all together with ", " between. */
416 s
= PyString_FromString(", ");
419 result
= _PyString_Join(s
, pieces
);
424 Py_ReprLeave((PyObject
*)v
);
429 list_length(PyListObject
*a
)
435 list_contains(PyListObject
*a
, PyObject
*el
)
440 for (i
= 0, cmp
= 0 ; cmp
== 0 && i
< Py_SIZE(a
); ++i
)
441 cmp
= PyObject_RichCompareBool(el
, PyList_GET_ITEM(a
, i
),
447 list_item(PyListObject
*a
, Py_ssize_t i
)
449 if (i
< 0 || i
>= Py_SIZE(a
)) {
450 if (indexerr
== NULL
)
451 indexerr
= PyString_FromString(
452 "list index out of range");
453 PyErr_SetObject(PyExc_IndexError
, indexerr
);
456 Py_INCREF(a
->ob_item
[i
]);
457 return a
->ob_item
[i
];
461 list_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
464 PyObject
**src
, **dest
;
468 else if (ilow
> Py_SIZE(a
))
472 else if (ihigh
> Py_SIZE(a
))
475 np
= (PyListObject
*) PyList_New(len
);
479 src
= a
->ob_item
+ ilow
;
481 for (i
= 0; i
< len
; i
++) {
482 PyObject
*v
= src
[i
];
486 return (PyObject
*)np
;
490 PyList_GetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
492 if (!PyList_Check(a
)) {
493 PyErr_BadInternalCall();
496 return list_slice((PyListObject
*)a
, ilow
, ihigh
);
500 list_concat(PyListObject
*a
, PyObject
*bb
)
504 PyObject
**src
, **dest
;
506 if (!PyList_Check(bb
)) {
507 PyErr_Format(PyExc_TypeError
,
508 "can only concatenate list (not \"%.200s\") to list",
509 bb
->ob_type
->tp_name
);
512 #define b ((PyListObject *)bb)
513 size
= Py_SIZE(a
) + Py_SIZE(b
);
515 return PyErr_NoMemory();
516 np
= (PyListObject
*) PyList_New(size
);
522 for (i
= 0; i
< Py_SIZE(a
); i
++) {
523 PyObject
*v
= src
[i
];
528 dest
= np
->ob_item
+ Py_SIZE(a
);
529 for (i
= 0; i
< Py_SIZE(b
); i
++) {
530 PyObject
*v
= src
[i
];
534 return (PyObject
*)np
;
539 list_repeat(PyListObject
*a
, Py_ssize_t n
)
544 PyObject
**p
, **items
;
548 size
= Py_SIZE(a
) * n
;
549 if (n
&& size
/n
!= Py_SIZE(a
))
550 return PyErr_NoMemory();
552 return PyList_New(0);
553 np
= (PyListObject
*) PyList_New(size
);
558 if (Py_SIZE(a
) == 1) {
559 elem
= a
->ob_item
[0];
560 for (i
= 0; i
< n
; i
++) {
564 return (PyObject
*) np
;
568 for (i
= 0; i
< n
; i
++) {
569 for (j
= 0; j
< Py_SIZE(a
); j
++) {
575 return (PyObject
*) np
;
579 list_clear(PyListObject
*a
)
582 PyObject
**item
= a
->ob_item
;
584 /* Because XDECREF can recursively invoke operations on
585 this list, we make it empty first. */
595 /* Never fails; the return value can be ignored.
596 Note that there is no guarantee that the list is actually empty
597 at this point, because XDECREF may have populated it again! */
601 /* a[ilow:ihigh] = v if v != NULL.
602 * del a[ilow:ihigh] if v == NULL.
604 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
605 * guaranteed the call cannot fail.
608 list_ass_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
610 /* Because [X]DECREF can recursively invoke list operations on
611 this list, we must postpone all [X]DECREF activity until
612 after the list is back in its canonical shape. Therefore
613 we must allocate an additional array, 'recycle', into which
614 we temporarily copy the items that are deleted from the
616 PyObject
*recycle_on_stack
[8];
617 PyObject
**recycle
= recycle_on_stack
; /* will allocate more if needed */
619 PyObject
**vitem
= NULL
;
620 PyObject
*v_as_SF
= NULL
; /* PySequence_Fast(v) */
621 Py_ssize_t n
; /* # of elements in replacement list */
622 Py_ssize_t norig
; /* # of elements in list getting replaced */
623 Py_ssize_t d
; /* Change in size */
626 int result
= -1; /* guilty until proved innocent */
627 #define b ((PyListObject *)v)
632 /* Special case "a[i:j] = a" -- copy b first */
633 v
= list_slice(b
, 0, Py_SIZE(b
));
636 result
= list_ass_slice(a
, ilow
, ihigh
, v
);
640 v_as_SF
= PySequence_Fast(v
, "can only assign an iterable");
643 n
= PySequence_Fast_GET_SIZE(v_as_SF
);
644 vitem
= PySequence_Fast_ITEMS(v_as_SF
);
648 else if (ilow
> Py_SIZE(a
))
653 else if (ihigh
> Py_SIZE(a
))
656 norig
= ihigh
- ilow
;
659 if (Py_SIZE(a
) + d
== 0) {
661 return list_clear(a
);
664 /* recycle the items that we are about to remove */
665 s
= norig
* sizeof(PyObject
*);
666 if (s
> sizeof(recycle_on_stack
)) {
667 recycle
= (PyObject
**)PyMem_MALLOC(s
);
668 if (recycle
== NULL
) {
673 memcpy(recycle
, &item
[ilow
], s
);
675 if (d
< 0) { /* Delete -d items */
676 memmove(&item
[ihigh
+d
], &item
[ihigh
],
677 (Py_SIZE(a
) - ihigh
)*sizeof(PyObject
*));
678 list_resize(a
, Py_SIZE(a
) + d
);
681 else if (d
> 0) { /* Insert d items */
683 if (list_resize(a
, k
+d
) < 0)
686 memmove(&item
[ihigh
+d
], &item
[ihigh
],
687 (k
- ihigh
)*sizeof(PyObject
*));
689 for (k
= 0; k
< n
; k
++, ilow
++) {
690 PyObject
*w
= vitem
[k
];
694 for (k
= norig
- 1; k
>= 0; --k
)
695 Py_XDECREF(recycle
[k
]);
698 if (recycle
!= recycle_on_stack
)
706 PyList_SetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
708 if (!PyList_Check(a
)) {
709 PyErr_BadInternalCall();
712 return list_ass_slice((PyListObject
*)a
, ilow
, ihigh
, v
);
716 list_inplace_repeat(PyListObject
*self
, Py_ssize_t n
)
719 Py_ssize_t size
, i
, j
, p
;
722 size
= PyList_GET_SIZE(self
);
723 if (size
== 0 || n
== 1) {
725 return (PyObject
*)self
;
729 (void)list_clear(self
);
731 return (PyObject
*)self
;
734 if (size
> PY_SSIZE_T_MAX
/ n
) {
735 return PyErr_NoMemory();
738 if (list_resize(self
, size
*n
) == -1)
742 items
= self
->ob_item
;
743 for (i
= 1; i
< n
; i
++) { /* Start counting at 1, not 0 */
744 for (j
= 0; j
< size
; j
++) {
745 PyObject
*o
= items
[j
];
751 return (PyObject
*)self
;
755 list_ass_item(PyListObject
*a
, Py_ssize_t i
, PyObject
*v
)
758 if (i
< 0 || i
>= Py_SIZE(a
)) {
759 PyErr_SetString(PyExc_IndexError
,
760 "list assignment index out of range");
764 return list_ass_slice(a
, i
, i
+1, v
);
766 old_value
= a
->ob_item
[i
];
768 Py_DECREF(old_value
);
773 listinsert(PyListObject
*self
, PyObject
*args
)
777 if (!PyArg_ParseTuple(args
, "nO:insert", &i
, &v
))
779 if (ins1(self
, i
, v
) == 0)
785 listappend(PyListObject
*self
, PyObject
*v
)
787 if (app1(self
, v
) == 0)
793 listextend(PyListObject
*self
, PyObject
*b
)
795 PyObject
*it
; /* iter(v) */
796 Py_ssize_t m
; /* size of self */
797 Py_ssize_t n
; /* guess for size of b */
798 Py_ssize_t mn
; /* m + n */
800 PyObject
*(*iternext
)(PyObject
*);
803 1) lists and tuples which can use PySequence_Fast ops
804 2) extending self to self requires making a copy first
806 if (PyList_CheckExact(b
) || PyTuple_CheckExact(b
) || (PyObject
*)self
== b
) {
807 PyObject
**src
, **dest
;
808 b
= PySequence_Fast(b
, "argument must be iterable");
811 n
= PySequence_Fast_GET_SIZE(b
);
813 /* short circuit when b is empty */
818 if (list_resize(self
, m
+ n
) == -1) {
822 /* note that we may still have self == b here for the
823 * situation a.extend(a), but the following code works
824 * in that case too. Just make sure to resize self
825 * before calling PySequence_Fast_ITEMS.
827 /* populate the end of self with b's items */
828 src
= PySequence_Fast_ITEMS(b
);
829 dest
= self
->ob_item
+ m
;
830 for (i
= 0; i
< n
; i
++) {
831 PyObject
*o
= src
[i
];
839 it
= PyObject_GetIter(b
);
842 iternext
= *it
->ob_type
->tp_iternext
;
844 /* Guess a result list size. */
845 n
= _PyObject_LengthHint(b
, 8);
854 if (list_resize(self
, mn
) == -1)
856 /* Make the list sane again. */
859 /* Else m + n overflowed; on the chance that n lied, and there really
860 * is enough room, ignore it. If n was telling the truth, we'll
861 * eventually run out of memory during the loop.
864 /* Run iterator to exhaustion. */
866 PyObject
*item
= iternext(it
);
868 if (PyErr_Occurred()) {
869 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
876 if (Py_SIZE(self
) < self
->allocated
) {
878 PyList_SET_ITEM(self
, Py_SIZE(self
), item
);
882 int status
= app1(self
, item
);
883 Py_DECREF(item
); /* append creates a new ref */
889 /* Cut back result list if initial guess was too large. */
890 if (Py_SIZE(self
) < self
->allocated
)
891 list_resize(self
, Py_SIZE(self
)); /* shrinking can't fail */
902 _PyList_Extend(PyListObject
*self
, PyObject
*b
)
904 return listextend(self
, b
);
908 list_inplace_concat(PyListObject
*self
, PyObject
*other
)
912 result
= listextend(self
, other
);
917 return (PyObject
*)self
;
921 listpop(PyListObject
*self
, PyObject
*args
)
927 if (!PyArg_ParseTuple(args
, "|n:pop", &i
))
930 if (Py_SIZE(self
) == 0) {
931 /* Special-case most common failure cause */
932 PyErr_SetString(PyExc_IndexError
, "pop from empty list");
937 if (i
< 0 || i
>= Py_SIZE(self
)) {
938 PyErr_SetString(PyExc_IndexError
, "pop index out of range");
941 v
= self
->ob_item
[i
];
942 if (i
== Py_SIZE(self
) - 1) {
943 status
= list_resize(self
, Py_SIZE(self
) - 1);
945 return v
; /* and v now owns the reference the list had */
948 status
= list_ass_slice(self
, i
, i
+1, (PyObject
*)NULL
);
950 /* Use status, so that in a release build compilers don't
951 * complain about the unused name.
958 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
960 reverse_slice(PyObject
**lo
, PyObject
**hi
)
974 /* Lots of code for an adaptive, stable, natural mergesort. There are many
975 * pieces to this algorithm; read listsort.txt for overviews and details.
978 /* Comparison function. Takes care of calling a user-supplied
979 * comparison function (any callable Python object), which must not be
980 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
981 * with Py_LT if you know it's NULL).
982 * Returns -1 on error, 1 if x < y, 0 if x >= y.
985 islt(PyObject
*x
, PyObject
*y
, PyObject
*compare
)
991 assert(compare
!= NULL
);
992 /* Call the user's comparison function and translate the 3-way
993 * result into true or false (or error).
995 args
= PyTuple_New(2);
1000 PyTuple_SET_ITEM(args
, 0, x
);
1001 PyTuple_SET_ITEM(args
, 1, y
);
1002 res
= PyObject_Call(compare
, args
, NULL
);
1006 if (!PyInt_Check(res
)) {
1007 PyErr_Format(PyExc_TypeError
,
1008 "comparison function must return int, not %.200s",
1009 res
->ob_type
->tp_name
);
1013 i
= PyInt_AsLong(res
);
1018 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
1019 * islt. This avoids a layer of function call in the usual case, and
1020 * sorting does many comparisons.
1021 * Returns -1 on error, 1 if x < y, 0 if x >= y.
1023 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
1024 PyObject_RichCompareBool(X, Y, Py_LT) : \
1025 islt(X, Y, COMPARE))
1027 /* Compare X to Y via "<". Goto "fail" if the comparison raises an
1028 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
1029 started. It makes more sense in context <wink>. X and Y are PyObject*s.
1031 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
1034 /* binarysort is the best method for sorting small arrays: it does
1035 few compares, but can do data movement quadratic in the number of
1037 [lo, hi) is a contiguous slice of a list, and is sorted via
1038 binary insertion. This sort is stable.
1039 On entry, must have lo <= start <= hi, and that [lo, start) is already
1040 sorted (pass start == lo if you don't know!).
1041 If islt() complains return -1, else 0.
1042 Even in case of error, the output slice will be some permutation of
1043 the input (nothing is lost or duplicated).
1046 binarysort(PyObject
**lo
, PyObject
**hi
, PyObject
**start
, PyObject
*compare
)
1047 /* compare -- comparison function object, or NULL for default */
1049 register Py_ssize_t k
;
1050 register PyObject
**l
, **p
, **r
;
1051 register PyObject
*pivot
;
1053 assert(lo
<= start
&& start
<= hi
);
1054 /* assert [lo, start) is sorted */
1057 for (; start
< hi
; ++start
) {
1058 /* set l to where *start belongs */
1063 * pivot >= all in [lo, l).
1064 * pivot < all in [r, start).
1065 * The second is vacuously true at the start.
1069 p
= l
+ ((r
- l
) >> 1);
1076 /* The invariants still hold, so pivot >= all in [lo, l) and
1077 pivot < all in [l, start), so pivot belongs at l. Note
1078 that if there are elements equal to pivot, l points to the
1079 first slot after them -- that's why this sort is stable.
1080 Slide over to make room.
1081 Caution: using memmove is much slower under MSVC 5;
1082 we're not usually moving many slots. */
1083 for (p
= start
; p
> l
; --p
)
1094 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1095 is required on entry. "A run" is the longest ascending sequence, with
1097 lo[0] <= lo[1] <= lo[2] <= ...
1099 or the longest descending sequence, with
1101 lo[0] > lo[1] > lo[2] > ...
1103 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1104 For its intended use in a stable mergesort, the strictness of the defn of
1105 "descending" is needed so that the caller can safely reverse a descending
1106 sequence without violating stability (strict > ensures there are no equal
1107 elements to get out of order).
1109 Returns -1 in case of error.
1112 count_run(PyObject
**lo
, PyObject
**hi
, PyObject
*compare
, int *descending
)
1124 IFLT(*lo
, *(lo
-1)) {
1126 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1134 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1146 Locate the proper position of key in a sorted vector; if the vector contains
1147 an element equal to key, return the position immediately to the left of
1148 the leftmost equal element. [gallop_right() does the same except returns
1149 the position to the right of the rightmost equal element (if any).]
1151 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
1153 "hint" is an index at which to begin the search, 0 <= hint < n. The closer
1154 hint is to the final result, the faster this runs.
1156 The return value is the int k in 0..n such that
1158 a[k-1] < key <= a[k]
1160 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1161 key belongs at index k; or, IOW, the first k elements of a should precede
1162 key, and the last n-k should follow key.
1164 Returns -1 on error. See listsort.txt for info on the method.
1167 gallop_left(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1173 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1179 /* a[hint] < key -- gallop right, until
1180 * a[hint + lastofs] < key <= a[hint + ofs]
1182 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1183 while (ofs
< maxofs
) {
1186 ofs
= (ofs
<< 1) + 1;
1187 if (ofs
<= 0) /* int overflow */
1190 else /* key <= a[hint + ofs] */
1195 /* Translate back to offsets relative to &a[0]. */
1200 /* key <= a[hint] -- gallop left, until
1201 * a[hint - ofs] < key <= a[hint - lastofs]
1203 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1204 while (ofs
< maxofs
) {
1207 /* key <= a[hint - ofs] */
1209 ofs
= (ofs
<< 1) + 1;
1210 if (ofs
<= 0) /* int overflow */
1215 /* Translate back to positive offsets relative to &a[0]. */
1217 lastofs
= hint
- ofs
;
1222 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1223 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1224 * right of lastofs but no farther right than ofs. Do a binary
1225 * search, with invariant a[lastofs-1] < key <= a[ofs].
1228 while (lastofs
< ofs
) {
1229 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1232 lastofs
= m
+1; /* a[m] < key */
1234 ofs
= m
; /* key <= a[m] */
1236 assert(lastofs
== ofs
); /* so a[ofs-1] < key <= a[ofs] */
1244 Exactly like gallop_left(), except that if key already exists in a[0:n],
1245 finds the position immediately to the right of the rightmost equal value.
1247 The return value is the int k in 0..n such that
1249 a[k-1] <= key < a[k]
1253 The code duplication is massive, but this is enough different given that
1254 we're sticking to "<" comparisons that it's much harder to follow if
1255 written as one routine with yet another "left or right?" flag.
1258 gallop_right(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1264 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1270 /* key < a[hint] -- gallop left, until
1271 * a[hint - ofs] <= key < a[hint - lastofs]
1273 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1274 while (ofs
< maxofs
) {
1275 IFLT(key
, *(a
-ofs
)) {
1277 ofs
= (ofs
<< 1) + 1;
1278 if (ofs
<= 0) /* int overflow */
1281 else /* a[hint - ofs] <= key */
1286 /* Translate back to positive offsets relative to &a[0]. */
1288 lastofs
= hint
- ofs
;
1292 /* a[hint] <= key -- gallop right, until
1293 * a[hint + lastofs] <= key < a[hint + ofs]
1295 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1296 while (ofs
< maxofs
) {
1299 /* a[hint + ofs] <= key */
1301 ofs
= (ofs
<< 1) + 1;
1302 if (ofs
<= 0) /* int overflow */
1307 /* Translate back to offsets relative to &a[0]. */
1313 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1314 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1315 * right of lastofs but no farther right than ofs. Do a binary
1316 * search, with invariant a[lastofs-1] <= key < a[ofs].
1319 while (lastofs
< ofs
) {
1320 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1323 ofs
= m
; /* key < a[m] */
1325 lastofs
= m
+1; /* a[m] <= key */
1327 assert(lastofs
== ofs
); /* so a[ofs-1] <= key < a[ofs] */
1334 /* The maximum number of entries in a MergeState's pending-runs stack.
1335 * This is enough to sort arrays of size up to about
1336 * 32 * phi ** MAX_MERGE_PENDING
1337 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1338 * with 2**64 elements.
1340 #define MAX_MERGE_PENDING 85
1342 /* When we get into galloping mode, we stay there until both runs win less
1343 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1345 #define MIN_GALLOP 7
1347 /* Avoid malloc for small temp arrays. */
1348 #define MERGESTATE_TEMP_SIZE 256
1350 /* One MergeState exists on the stack per invocation of mergesort. It's just
1351 * a convenient way to pass state around among the helper functions.
1358 typedef struct s_MergeState
{
1359 /* The user-supplied comparison function. or NULL if none given. */
1362 /* This controls when we get *into* galloping mode. It's initialized
1363 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1364 * random data, and lower for highly structured data.
1366 Py_ssize_t min_gallop
;
1368 /* 'a' is temp storage to help with merges. It contains room for
1371 PyObject
**a
; /* may point to temparray below */
1374 /* A stack of n pending runs yet to be merged. Run #i starts at
1375 * address base[i] and extends for len[i] elements. It's always
1376 * true (so long as the indices are in bounds) that
1378 * pending[i].base + pending[i].len == pending[i+1].base
1380 * so we could cut the storage for this, but it's a minor amount,
1381 * and keeping all the info explicit simplifies the code.
1384 struct s_slice pending
[MAX_MERGE_PENDING
];
1386 /* 'a' points to this when possible, rather than muck with malloc. */
1387 PyObject
*temparray
[MERGESTATE_TEMP_SIZE
];
1390 /* Conceptually a MergeState's constructor. */
1392 merge_init(MergeState
*ms
, PyObject
*compare
)
1395 ms
->compare
= compare
;
1396 ms
->a
= ms
->temparray
;
1397 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1399 ms
->min_gallop
= MIN_GALLOP
;
1402 /* Free all the temp memory owned by the MergeState. This must be called
1403 * when you're done with a MergeState, and may be called before then if
1404 * you want to free the temp memory early.
1407 merge_freemem(MergeState
*ms
)
1410 if (ms
->a
!= ms
->temparray
)
1412 ms
->a
= ms
->temparray
;
1413 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1416 /* Ensure enough temp memory for 'need' array slots is available.
1417 * Returns 0 on success and -1 if the memory can't be gotten.
1420 merge_getmem(MergeState
*ms
, Py_ssize_t need
)
1423 if (need
<= ms
->alloced
)
1425 /* Don't realloc! That can cost cycles to copy the old data, but
1426 * we don't care what's in the block.
1429 if (need
> PY_SSIZE_T_MAX
/ sizeof(PyObject
*)) {
1433 ms
->a
= (PyObject
**)PyMem_Malloc(need
* sizeof(PyObject
*));
1439 merge_freemem(ms
); /* reset to sane state */
1442 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1443 merge_getmem(MS, NEED))
1445 /* Merge the na elements starting at pa with the nb elements starting at pb
1446 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1447 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1448 * merge, and should have na <= nb. See listsort.txt for more info.
1449 * Return 0 if successful, -1 if error.
1452 merge_lo(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
,
1453 PyObject
**pb
, Py_ssize_t nb
)
1458 int result
= -1; /* guilty until proved innocent */
1459 Py_ssize_t min_gallop
;
1461 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1462 if (MERGE_GETMEM(ms
, na
) < 0)
1464 memcpy(ms
->a
, pa
, na
* sizeof(PyObject
*));
1475 min_gallop
= ms
->min_gallop
;
1476 compare
= ms
->compare
;
1478 Py_ssize_t acount
= 0; /* # of times A won in a row */
1479 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1481 /* Do the straightforward thing until (if ever) one run
1482 * appears to win consistently.
1485 assert(na
> 1 && nb
> 0);
1486 k
= ISLT(*pb
, *pa
, compare
);
1496 if (bcount
>= min_gallop
)
1506 if (acount
>= min_gallop
)
1511 /* One run is winning so consistently that galloping may
1512 * be a huge win. So try that, and continue galloping until
1513 * (if ever) neither run appears to be winning consistently
1518 assert(na
> 1 && nb
> 0);
1519 min_gallop
-= min_gallop
> 1;
1520 ms
->min_gallop
= min_gallop
;
1521 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1526 memcpy(dest
, pa
, k
* sizeof(PyObject
*));
1532 /* na==0 is impossible now if the comparison
1533 * function is consistent, but we can't assume
1544 k
= gallop_left(*pa
, pb
, nb
, 0, compare
);
1549 memmove(dest
, pb
, k
* sizeof(PyObject
*));
1560 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1561 ++min_gallop
; /* penalize it for leaving galloping mode */
1562 ms
->min_gallop
= min_gallop
;
1568 memcpy(dest
, pa
, na
* sizeof(PyObject
*));
1571 assert(na
== 1 && nb
> 0);
1572 /* The last element of pa belongs at the end of the merge. */
1573 memmove(dest
, pb
, nb
* sizeof(PyObject
*));
1578 /* Merge the na elements starting at pa with the nb elements starting at pb
1579 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1580 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1581 * merge, and should have na >= nb. See listsort.txt for more info.
1582 * Return 0 if successful, -1 if error.
1585 merge_hi(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
, PyObject
**pb
, Py_ssize_t nb
)
1590 int result
= -1; /* guilty until proved innocent */
1593 Py_ssize_t min_gallop
;
1595 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1596 if (MERGE_GETMEM(ms
, nb
) < 0)
1599 memcpy(ms
->a
, pb
, nb
* sizeof(PyObject
*));
1602 pb
= ms
->a
+ nb
- 1;
1612 min_gallop
= ms
->min_gallop
;
1613 compare
= ms
->compare
;
1615 Py_ssize_t acount
= 0; /* # of times A won in a row */
1616 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1618 /* Do the straightforward thing until (if ever) one run
1619 * appears to win consistently.
1622 assert(na
> 0 && nb
> 1);
1623 k
= ISLT(*pb
, *pa
, compare
);
1633 if (acount
>= min_gallop
)
1643 if (bcount
>= min_gallop
)
1648 /* One run is winning so consistently that galloping may
1649 * be a huge win. So try that, and continue galloping until
1650 * (if ever) neither run appears to be winning consistently
1655 assert(na
> 0 && nb
> 1);
1656 min_gallop
-= min_gallop
> 1;
1657 ms
->min_gallop
= min_gallop
;
1658 k
= gallop_right(*pb
, basea
, na
, na
-1, compare
);
1666 memmove(dest
+1, pa
+1, k
* sizeof(PyObject
*));
1676 k
= gallop_left(*pa
, baseb
, nb
, nb
-1, compare
);
1684 memcpy(dest
+1, pb
+1, k
* sizeof(PyObject
*));
1688 /* nb==0 is impossible now if the comparison
1689 * function is consistent, but we can't assume
1699 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1700 ++min_gallop
; /* penalize it for leaving galloping mode */
1701 ms
->min_gallop
= min_gallop
;
1707 memcpy(dest
-(nb
-1), baseb
, nb
* sizeof(PyObject
*));
1710 assert(nb
== 1 && na
> 0);
1711 /* The first element of pb belongs at the front of the merge. */
1714 memmove(dest
+1, pa
+1, na
* sizeof(PyObject
*));
1719 /* Merge the two runs at stack indices i and i+1.
1720 * Returns 0 on success, -1 on error.
1723 merge_at(MergeState
*ms
, Py_ssize_t i
)
1725 PyObject
**pa
, **pb
;
1733 assert(i
== ms
->n
- 2 || i
== ms
->n
- 3);
1735 pa
= ms
->pending
[i
].base
;
1736 na
= ms
->pending
[i
].len
;
1737 pb
= ms
->pending
[i
+1].base
;
1738 nb
= ms
->pending
[i
+1].len
;
1739 assert(na
> 0 && nb
> 0);
1740 assert(pa
+ na
== pb
);
1742 /* Record the length of the combined runs; if i is the 3rd-last
1743 * run now, also slide over the last run (which isn't involved
1744 * in this merge). The current run i+1 goes away in any case.
1746 ms
->pending
[i
].len
= na
+ nb
;
1748 ms
->pending
[i
+1] = ms
->pending
[i
+2];
1751 /* Where does b start in a? Elements in a before that can be
1752 * ignored (already in place).
1754 compare
= ms
->compare
;
1755 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1763 /* Where does a end in b? Elements in b after that can be
1764 * ignored (already in place).
1766 nb
= gallop_left(pa
[na
-1], pb
, nb
, nb
-1, compare
);
1770 /* Merge what remains of the runs, using a temp array with
1771 * min(na, nb) elements.
1774 return merge_lo(ms
, pa
, na
, pb
, nb
);
1776 return merge_hi(ms
, pa
, na
, pb
, nb
);
1779 /* Examine the stack of runs waiting to be merged, merging adjacent runs
1780 * until the stack invariants are re-established:
1782 * 1. len[-3] > len[-2] + len[-1]
1783 * 2. len[-2] > len[-1]
1785 * See listsort.txt for more info.
1787 * Returns 0 on success, -1 on error.
1790 merge_collapse(MergeState
*ms
)
1792 struct s_slice
*p
= ms
->pending
;
1796 Py_ssize_t n
= ms
->n
- 2;
1797 if (n
> 0 && p
[n
-1].len
<= p
[n
].len
+ p
[n
+1].len
) {
1798 if (p
[n
-1].len
< p
[n
+1].len
)
1800 if (merge_at(ms
, n
) < 0)
1803 else if (p
[n
].len
<= p
[n
+1].len
) {
1804 if (merge_at(ms
, n
) < 0)
1813 /* Regardless of invariants, merge all runs on the stack until only one
1814 * remains. This is used at the end of the mergesort.
1816 * Returns 0 on success, -1 on error.
1819 merge_force_collapse(MergeState
*ms
)
1821 struct s_slice
*p
= ms
->pending
;
1825 Py_ssize_t n
= ms
->n
- 2;
1826 if (n
> 0 && p
[n
-1].len
< p
[n
+1].len
)
1828 if (merge_at(ms
, n
) < 0)
1834 /* Compute a good value for the minimum run length; natural runs shorter
1835 * than this are boosted artificially via binary insertion.
1837 * If n < 64, return n (it's too small to bother with fancy stuff).
1838 * Else if n is an exact power of 2, return 32.
1839 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1840 * strictly less than, an exact power of 2.
1842 * See listsort.txt for more info.
1845 merge_compute_minrun(Py_ssize_t n
)
1847 Py_ssize_t r
= 0; /* becomes 1 if any 1 bits are shifted off */
1857 /* Special wrapper to support stable sorting using the decorate-sort-undecorate
1858 pattern. Holds a key which is used for comparisons and the original record
1859 which is returned during the undecorate phase. By exposing only the key
1860 during comparisons, the underlying sort stability characteristics are left
1861 unchanged. Also, if a custom comparison function is used, it will only see
1862 the key instead of a full record. */
1868 } sortwrapperobject
;
1870 PyDoc_STRVAR(sortwrapper_doc
, "Object wrapper with a custom sort key.");
1872 sortwrapper_richcompare(sortwrapperobject
*, sortwrapperobject
*, int);
1874 sortwrapper_dealloc(sortwrapperobject
*);
1876 static PyTypeObject sortwrapper_type
= {
1877 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
1878 "sortwrapper", /* tp_name */
1879 sizeof(sortwrapperobject
), /* tp_basicsize */
1880 0, /* tp_itemsize */
1882 (destructor
)sortwrapper_dealloc
, /* tp_dealloc */
1888 0, /* tp_as_number */
1889 0, /* tp_as_sequence */
1890 0, /* tp_as_mapping */
1894 PyObject_GenericGetAttr
, /* tp_getattro */
1895 0, /* tp_setattro */
1896 0, /* tp_as_buffer */
1897 Py_TPFLAGS_DEFAULT
|
1898 Py_TPFLAGS_HAVE_RICHCOMPARE
, /* tp_flags */
1899 sortwrapper_doc
, /* tp_doc */
1900 0, /* tp_traverse */
1902 (richcmpfunc
)sortwrapper_richcompare
, /* tp_richcompare */
1907 sortwrapper_richcompare(sortwrapperobject
*a
, sortwrapperobject
*b
, int op
)
1909 if (!PyObject_TypeCheck(b
, &sortwrapper_type
)) {
1910 PyErr_SetString(PyExc_TypeError
,
1911 "expected a sortwrapperobject");
1914 return PyObject_RichCompare(a
->key
, b
->key
, op
);
1918 sortwrapper_dealloc(sortwrapperobject
*so
)
1920 Py_XDECREF(so
->key
);
1921 Py_XDECREF(so
->value
);
1925 /* Returns a new reference to a sortwrapper.
1926 Consumes the references to the two underlying objects. */
1929 build_sortwrapper(PyObject
*key
, PyObject
*value
)
1931 sortwrapperobject
*so
;
1933 so
= PyObject_New(sortwrapperobject
, &sortwrapper_type
);
1938 return (PyObject
*)so
;
1941 /* Returns a new reference to the value underlying the wrapper. */
1943 sortwrapper_getvalue(PyObject
*so
)
1947 if (!PyObject_TypeCheck(so
, &sortwrapper_type
)) {
1948 PyErr_SetString(PyExc_TypeError
,
1949 "expected a sortwrapperobject");
1952 value
= ((sortwrapperobject
*)so
)->value
;
1957 /* Wrapper for user specified cmp functions in combination with a
1958 specified key function. Makes sure the cmp function is presented
1959 with the actual key instead of the sortwrapper */
1967 cmpwrapper_dealloc(cmpwrapperobject
*co
)
1969 Py_XDECREF(co
->func
);
1974 cmpwrapper_call(cmpwrapperobject
*co
, PyObject
*args
, PyObject
*kwds
)
1976 PyObject
*x
, *y
, *xx
, *yy
;
1978 if (!PyArg_UnpackTuple(args
, "", 2, 2, &x
, &y
))
1980 if (!PyObject_TypeCheck(x
, &sortwrapper_type
) ||
1981 !PyObject_TypeCheck(y
, &sortwrapper_type
)) {
1982 PyErr_SetString(PyExc_TypeError
,
1983 "expected a sortwrapperobject");
1986 xx
= ((sortwrapperobject
*)x
)->key
;
1987 yy
= ((sortwrapperobject
*)y
)->key
;
1988 return PyObject_CallFunctionObjArgs(co
->func
, xx
, yy
, NULL
);
1991 PyDoc_STRVAR(cmpwrapper_doc
, "cmp() wrapper for sort with custom keys.");
1993 static PyTypeObject cmpwrapper_type
= {
1994 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
1995 "cmpwrapper", /* tp_name */
1996 sizeof(cmpwrapperobject
), /* tp_basicsize */
1997 0, /* tp_itemsize */
1999 (destructor
)cmpwrapper_dealloc
, /* tp_dealloc */
2005 0, /* tp_as_number */
2006 0, /* tp_as_sequence */
2007 0, /* tp_as_mapping */
2009 (ternaryfunc
)cmpwrapper_call
, /* tp_call */
2011 PyObject_GenericGetAttr
, /* tp_getattro */
2012 0, /* tp_setattro */
2013 0, /* tp_as_buffer */
2014 Py_TPFLAGS_DEFAULT
, /* tp_flags */
2015 cmpwrapper_doc
, /* tp_doc */
2019 build_cmpwrapper(PyObject
*cmpfunc
)
2021 cmpwrapperobject
*co
;
2023 co
= PyObject_New(cmpwrapperobject
, &cmpwrapper_type
);
2028 return (PyObject
*)co
;
2031 /* An adaptive, stable, natural mergesort. See listsort.txt.
2032 * Returns Py_None on success, NULL on error. Even in case of error, the
2033 * list will be some permutation of its input state (nothing is lost or
2037 listsort(PyListObject
*self
, PyObject
*args
, PyObject
*kwds
)
2040 PyObject
**lo
, **hi
;
2041 Py_ssize_t nremaining
;
2043 Py_ssize_t saved_ob_size
, saved_allocated
;
2044 PyObject
**saved_ob_item
;
2045 PyObject
**final_ob_item
;
2046 PyObject
*compare
= NULL
;
2047 PyObject
*result
= NULL
; /* guilty until proved innocent */
2049 PyObject
*keyfunc
= NULL
;
2051 PyObject
*key
, *value
, *kvpair
;
2052 static char *kwlist
[] = {"cmp", "key", "reverse", 0};
2054 assert(self
!= NULL
);
2055 assert (PyList_Check(self
));
2057 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|OOi:sort",
2058 kwlist
, &compare
, &keyfunc
, &reverse
))
2061 if (compare
== Py_None
)
2063 if (compare
!= NULL
&&
2064 PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0)
2066 if (keyfunc
== Py_None
)
2068 if (compare
!= NULL
&& keyfunc
!= NULL
) {
2069 compare
= build_cmpwrapper(compare
);
2070 if (compare
== NULL
)
2073 Py_XINCREF(compare
);
2075 /* The list is temporarily made empty, so that mutations performed
2076 * by comparison functions can't affect the slice of memory we're
2077 * sorting (allowing mutations during sorting is a core-dump
2078 * factory, since ob_item may change).
2080 saved_ob_size
= Py_SIZE(self
);
2081 saved_ob_item
= self
->ob_item
;
2082 saved_allocated
= self
->allocated
;
2084 self
->ob_item
= NULL
;
2085 self
->allocated
= -1; /* any operation will reset it to >= 0 */
2087 if (keyfunc
!= NULL
) {
2088 for (i
=0 ; i
< saved_ob_size
; i
++) {
2089 value
= saved_ob_item
[i
];
2090 key
= PyObject_CallFunctionObjArgs(keyfunc
, value
,
2093 for (i
=i
-1 ; i
>=0 ; i
--) {
2094 kvpair
= saved_ob_item
[i
];
2095 value
= sortwrapper_getvalue(kvpair
);
2096 saved_ob_item
[i
] = value
;
2101 kvpair
= build_sortwrapper(key
, value
);
2104 saved_ob_item
[i
] = kvpair
;
2108 /* Reverse sort stability achieved by initially reversing the list,
2109 applying a stable forward sort, then reversing the final result. */
2110 if (reverse
&& saved_ob_size
> 1)
2111 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2113 merge_init(&ms
, compare
);
2115 nremaining
= saved_ob_size
;
2119 /* March over the array once, left to right, finding natural runs,
2120 * and extending short natural runs to minrun elements.
2123 hi
= lo
+ nremaining
;
2124 minrun
= merge_compute_minrun(nremaining
);
2129 /* Identify next run. */
2130 n
= count_run(lo
, hi
, compare
, &descending
);
2134 reverse_slice(lo
, lo
+ n
);
2135 /* If short, extend to min(minrun, nremaining). */
2137 const Py_ssize_t force
= nremaining
<= minrun
?
2138 nremaining
: minrun
;
2139 if (binarysort(lo
, lo
+ force
, lo
+ n
, compare
) < 0)
2143 /* Push run onto pending-runs stack, and maybe merge. */
2144 assert(ms
.n
< MAX_MERGE_PENDING
);
2145 ms
.pending
[ms
.n
].base
= lo
;
2146 ms
.pending
[ms
.n
].len
= n
;
2148 if (merge_collapse(&ms
) < 0)
2150 /* Advance to find next run. */
2153 } while (nremaining
);
2156 if (merge_force_collapse(&ms
) < 0)
2159 assert(ms
.pending
[0].base
== saved_ob_item
);
2160 assert(ms
.pending
[0].len
== saved_ob_size
);
2165 if (keyfunc
!= NULL
) {
2166 for (i
=0 ; i
< saved_ob_size
; i
++) {
2167 kvpair
= saved_ob_item
[i
];
2168 value
= sortwrapper_getvalue(kvpair
);
2169 saved_ob_item
[i
] = value
;
2174 if (self
->allocated
!= -1 && result
!= NULL
) {
2175 /* The user mucked with the list during the sort,
2176 * and we don't already have another error to report.
2178 PyErr_SetString(PyExc_ValueError
, "list modified during sort");
2182 if (reverse
&& saved_ob_size
> 1)
2183 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2188 final_ob_item
= self
->ob_item
;
2190 Py_SIZE(self
) = saved_ob_size
;
2191 self
->ob_item
= saved_ob_item
;
2192 self
->allocated
= saved_allocated
;
2193 if (final_ob_item
!= NULL
) {
2194 /* we cannot use list_clear() for this because it does not
2195 guarantee that the list is really empty when it returns */
2197 Py_XDECREF(final_ob_item
[i
]);
2199 PyMem_FREE(final_ob_item
);
2201 Py_XDECREF(compare
);
2209 PyList_Sort(PyObject
*v
)
2211 if (v
== NULL
|| !PyList_Check(v
)) {
2212 PyErr_BadInternalCall();
2215 v
= listsort((PyListObject
*)v
, (PyObject
*)NULL
, (PyObject
*)NULL
);
2223 listreverse(PyListObject
*self
)
2225 if (Py_SIZE(self
) > 1)
2226 reverse_slice(self
->ob_item
, self
->ob_item
+ Py_SIZE(self
));
2231 PyList_Reverse(PyObject
*v
)
2233 PyListObject
*self
= (PyListObject
*)v
;
2235 if (v
== NULL
|| !PyList_Check(v
)) {
2236 PyErr_BadInternalCall();
2239 if (Py_SIZE(self
) > 1)
2240 reverse_slice(self
->ob_item
, self
->ob_item
+ Py_SIZE(self
));
2245 PyList_AsTuple(PyObject
*v
)
2250 if (v
== NULL
|| !PyList_Check(v
)) {
2251 PyErr_BadInternalCall();
2258 p
= ((PyTupleObject
*)w
)->ob_item
;
2259 q
= ((PyListObject
*)v
)->ob_item
;
2270 listindex(PyListObject
*self
, PyObject
*args
)
2272 Py_ssize_t i
, start
=0, stop
=Py_SIZE(self
);
2275 if (!PyArg_ParseTuple(args
, "O|O&O&:index", &v
,
2276 _PyEval_SliceIndex
, &start
,
2277 _PyEval_SliceIndex
, &stop
))
2280 start
+= Py_SIZE(self
);
2285 stop
+= Py_SIZE(self
);
2289 for (i
= start
; i
< stop
&& i
< Py_SIZE(self
); i
++) {
2290 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2292 return PyInt_FromSsize_t(i
);
2296 PyErr_SetString(PyExc_ValueError
, "list.index(x): x not in list");
2301 listcount(PyListObject
*self
, PyObject
*v
)
2303 Py_ssize_t count
= 0;
2306 for (i
= 0; i
< Py_SIZE(self
); i
++) {
2307 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2313 return PyInt_FromSsize_t(count
);
2317 listremove(PyListObject
*self
, PyObject
*v
)
2321 for (i
= 0; i
< Py_SIZE(self
); i
++) {
2322 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2324 if (list_ass_slice(self
, i
, i
+1,
2325 (PyObject
*)NULL
) == 0)
2332 PyErr_SetString(PyExc_ValueError
, "list.remove(x): x not in list");
2337 list_traverse(PyListObject
*o
, visitproc visit
, void *arg
)
2341 for (i
= Py_SIZE(o
); --i
>= 0; )
2342 Py_VISIT(o
->ob_item
[i
]);
2347 list_richcompare(PyObject
*v
, PyObject
*w
, int op
)
2349 PyListObject
*vl
, *wl
;
2352 if (!PyList_Check(v
) || !PyList_Check(w
)) {
2353 Py_INCREF(Py_NotImplemented
);
2354 return Py_NotImplemented
;
2357 vl
= (PyListObject
*)v
;
2358 wl
= (PyListObject
*)w
;
2360 if (Py_SIZE(vl
) != Py_SIZE(wl
) && (op
== Py_EQ
|| op
== Py_NE
)) {
2361 /* Shortcut: if the lengths differ, the lists differ */
2371 /* Search for the first index where items are different */
2372 for (i
= 0; i
< Py_SIZE(vl
) && i
< Py_SIZE(wl
); i
++) {
2373 int k
= PyObject_RichCompareBool(vl
->ob_item
[i
],
2374 wl
->ob_item
[i
], Py_EQ
);
2381 if (i
>= Py_SIZE(vl
) || i
>= Py_SIZE(wl
)) {
2382 /* No more items to compare -- compare sizes */
2383 Py_ssize_t vs
= Py_SIZE(vl
);
2384 Py_ssize_t ws
= Py_SIZE(wl
);
2388 case Py_LT
: cmp
= vs
< ws
; break;
2389 case Py_LE
: cmp
= vs
<= ws
; break;
2390 case Py_EQ
: cmp
= vs
== ws
; break;
2391 case Py_NE
: cmp
= vs
!= ws
; break;
2392 case Py_GT
: cmp
= vs
> ws
; break;
2393 case Py_GE
: cmp
= vs
>= ws
; break;
2394 default: return NULL
; /* cannot happen */
2404 /* We have an item that differs -- shortcuts for EQ/NE */
2406 Py_INCREF(Py_False
);
2414 /* Compare the final item again using the proper operator */
2415 return PyObject_RichCompare(vl
->ob_item
[i
], wl
->ob_item
[i
], op
);
2419 list_init(PyListObject
*self
, PyObject
*args
, PyObject
*kw
)
2421 PyObject
*arg
= NULL
;
2422 static char *kwlist
[] = {"sequence", 0};
2424 if (!PyArg_ParseTupleAndKeywords(args
, kw
, "|O:list", kwlist
, &arg
))
2427 /* Verify list invariants established by PyType_GenericAlloc() */
2428 assert(0 <= Py_SIZE(self
));
2429 assert(Py_SIZE(self
) <= self
->allocated
|| self
->allocated
== -1);
2430 assert(self
->ob_item
!= NULL
||
2431 self
->allocated
== 0 || self
->allocated
== -1);
2433 /* Empty previous contents */
2434 if (self
->ob_item
!= NULL
) {
2435 (void)list_clear(self
);
2438 PyObject
*rv
= listextend(self
, arg
);
2447 list_sizeof(PyListObject
*self
)
2451 res
= sizeof(PyListObject
) + self
->allocated
* sizeof(void*);
2452 return PyInt_FromSsize_t(res
);
2455 static PyObject
*list_iter(PyObject
*seq
);
2456 static PyObject
*list_reversed(PyListObject
* seq
, PyObject
* unused
);
2458 PyDoc_STRVAR(getitem_doc
,
2459 "x.__getitem__(y) <==> x[y]");
2460 PyDoc_STRVAR(reversed_doc
,
2461 "L.__reversed__() -- return a reverse iterator over the list");
2462 PyDoc_STRVAR(sizeof_doc
,
2463 "L.__sizeof__() -- size of L in memory, in bytes");
2464 PyDoc_STRVAR(append_doc
,
2465 "L.append(object) -- append object to end");
2466 PyDoc_STRVAR(extend_doc
,
2467 "L.extend(iterable) -- extend list by appending elements from the iterable");
2468 PyDoc_STRVAR(insert_doc
,
2469 "L.insert(index, object) -- insert object before index");
2470 PyDoc_STRVAR(pop_doc
,
2471 "L.pop([index]) -> item -- remove and return item at index (default last).\n"
2472 "Raises IndexError if list is empty or index is out of range.");
2473 PyDoc_STRVAR(remove_doc
,
2474 "L.remove(value) -- remove first occurrence of value.\n"
2475 "Raises ValueError if the value is not present.");
2476 PyDoc_STRVAR(index_doc
,
2477 "L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
2478 "Raises ValueError if the value is not present.");
2479 PyDoc_STRVAR(count_doc
,
2480 "L.count(value) -> integer -- return number of occurrences of value");
2481 PyDoc_STRVAR(reverse_doc
,
2482 "L.reverse() -- reverse *IN PLACE*");
2483 PyDoc_STRVAR(sort_doc
,
2484 "L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
2485 cmp(x, y) -> -1, 0, 1");
2487 static PyObject
*list_subscript(PyListObject
*, PyObject
*);
2489 static PyMethodDef list_methods
[] = {
2490 {"__getitem__", (PyCFunction
)list_subscript
, METH_O
|METH_COEXIST
, getitem_doc
},
2491 {"__reversed__",(PyCFunction
)list_reversed
, METH_NOARGS
, reversed_doc
},
2492 {"__sizeof__", (PyCFunction
)list_sizeof
, METH_NOARGS
, sizeof_doc
},
2493 {"append", (PyCFunction
)listappend
, METH_O
, append_doc
},
2494 {"insert", (PyCFunction
)listinsert
, METH_VARARGS
, insert_doc
},
2495 {"extend", (PyCFunction
)listextend
, METH_O
, extend_doc
},
2496 {"pop", (PyCFunction
)listpop
, METH_VARARGS
, pop_doc
},
2497 {"remove", (PyCFunction
)listremove
, METH_O
, remove_doc
},
2498 {"index", (PyCFunction
)listindex
, METH_VARARGS
, index_doc
},
2499 {"count", (PyCFunction
)listcount
, METH_O
, count_doc
},
2500 {"reverse", (PyCFunction
)listreverse
, METH_NOARGS
, reverse_doc
},
2501 {"sort", (PyCFunction
)listsort
, METH_VARARGS
| METH_KEYWORDS
, sort_doc
},
2502 {NULL
, NULL
} /* sentinel */
2505 static PySequenceMethods list_as_sequence
= {
2506 (lenfunc
)list_length
, /* sq_length */
2507 (binaryfunc
)list_concat
, /* sq_concat */
2508 (ssizeargfunc
)list_repeat
, /* sq_repeat */
2509 (ssizeargfunc
)list_item
, /* sq_item */
2510 (ssizessizeargfunc
)list_slice
, /* sq_slice */
2511 (ssizeobjargproc
)list_ass_item
, /* sq_ass_item */
2512 (ssizessizeobjargproc
)list_ass_slice
, /* sq_ass_slice */
2513 (objobjproc
)list_contains
, /* sq_contains */
2514 (binaryfunc
)list_inplace_concat
, /* sq_inplace_concat */
2515 (ssizeargfunc
)list_inplace_repeat
, /* sq_inplace_repeat */
2518 PyDoc_STRVAR(list_doc
,
2519 "list() -> new list\n"
2520 "list(sequence) -> new list initialized from sequence's items");
2524 list_subscript(PyListObject
* self
, PyObject
* item
)
2526 if (PyIndex_Check(item
)) {
2528 i
= PyNumber_AsSsize_t(item
, PyExc_IndexError
);
2529 if (i
== -1 && PyErr_Occurred())
2532 i
+= PyList_GET_SIZE(self
);
2533 return list_item(self
, i
);
2535 else if (PySlice_Check(item
)) {
2536 Py_ssize_t start
, stop
, step
, slicelength
, cur
, i
;
2539 PyObject
**src
, **dest
;
2541 if (PySlice_GetIndicesEx((PySliceObject
*)item
, Py_SIZE(self
),
2542 &start
, &stop
, &step
, &slicelength
) < 0) {
2546 if (slicelength
<= 0) {
2547 return PyList_New(0);
2549 else if (step
== 1) {
2550 return list_slice(self
, start
, stop
);
2553 result
= PyList_New(slicelength
);
2554 if (!result
) return NULL
;
2556 src
= self
->ob_item
;
2557 dest
= ((PyListObject
*)result
)->ob_item
;
2558 for (cur
= start
, i
= 0; i
< slicelength
;
2569 PyErr_Format(PyExc_TypeError
,
2570 "list indices must be integers, not %.200s",
2571 item
->ob_type
->tp_name
);
2577 list_ass_subscript(PyListObject
* self
, PyObject
* item
, PyObject
* value
)
2579 if (PyIndex_Check(item
)) {
2580 Py_ssize_t i
= PyNumber_AsSsize_t(item
, PyExc_IndexError
);
2581 if (i
== -1 && PyErr_Occurred())
2584 i
+= PyList_GET_SIZE(self
);
2585 return list_ass_item(self
, i
, value
);
2587 else if (PySlice_Check(item
)) {
2588 Py_ssize_t start
, stop
, step
, slicelength
;
2590 if (PySlice_GetIndicesEx((PySliceObject
*)item
, Py_SIZE(self
),
2591 &start
, &stop
, &step
, &slicelength
) < 0) {
2596 return list_ass_slice(self
, start
, stop
, value
);
2598 /* Make sure s[5:2] = [..] inserts at the right place:
2599 before 5, not before 2. */
2600 if ((step
< 0 && start
< stop
) ||
2601 (step
> 0 && start
> stop
))
2604 if (value
== NULL
) {
2609 if (slicelength
<= 0)
2614 start
= stop
+ step
*(slicelength
- 1) - 1;
2618 assert(slicelength
<= PY_SIZE_MAX
/ sizeof(PyObject
*));
2620 garbage
= (PyObject
**)
2621 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2627 /* drawing pictures might help understand these for
2628 loops. Basically, we memmove the parts of the
2629 list that are *not* part of the slice: step-1
2630 items for each item that is part of the slice,
2631 and then tail end of the list that was not
2632 covered by the slice */
2633 for (cur
= start
, i
= 0;
2636 Py_ssize_t lim
= step
- 1;
2638 garbage
[i
] = PyList_GET_ITEM(self
, cur
);
2640 if (cur
+ step
>= Py_SIZE(self
)) {
2641 lim
= Py_SIZE(self
) - cur
- 1;
2644 memmove(self
->ob_item
+ cur
- i
,
2645 self
->ob_item
+ cur
+ 1,
2646 lim
* sizeof(PyObject
*));
2648 cur
= start
+ slicelength
*step
;
2649 if (cur
< Py_SIZE(self
)) {
2650 memmove(self
->ob_item
+ cur
- slicelength
,
2651 self
->ob_item
+ cur
,
2652 (Py_SIZE(self
) - cur
) *
2653 sizeof(PyObject
*));
2656 Py_SIZE(self
) -= slicelength
;
2657 list_resize(self
, Py_SIZE(self
));
2659 for (i
= 0; i
< slicelength
; i
++) {
2660 Py_DECREF(garbage
[i
]);
2662 PyMem_FREE(garbage
);
2668 PyObject
*ins
, *seq
;
2669 PyObject
**garbage
, **seqitems
, **selfitems
;
2672 /* protect against a[::-1] = a */
2673 if (self
== (PyListObject
*)value
) {
2674 seq
= list_slice((PyListObject
*)value
, 0,
2675 PyList_GET_SIZE(value
));
2678 seq
= PySequence_Fast(value
,
2679 "must assign iterable "
2680 "to extended slice");
2685 if (PySequence_Fast_GET_SIZE(seq
) != slicelength
) {
2686 PyErr_Format(PyExc_ValueError
,
2687 "attempt to assign sequence of "
2688 "size %zd to extended slice of "
2690 PySequence_Fast_GET_SIZE(seq
),
2701 garbage
= (PyObject
**)
2702 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2709 selfitems
= self
->ob_item
;
2710 seqitems
= PySequence_Fast_ITEMS(seq
);
2711 for (cur
= start
, i
= 0; i
< slicelength
;
2713 garbage
[i
] = selfitems
[cur
];
2716 selfitems
[cur
] = ins
;
2719 for (i
= 0; i
< slicelength
; i
++) {
2720 Py_DECREF(garbage
[i
]);
2723 PyMem_FREE(garbage
);
2730 PyErr_Format(PyExc_TypeError
,
2731 "list indices must be integers, not %.200s",
2732 item
->ob_type
->tp_name
);
2737 static PyMappingMethods list_as_mapping
= {
2738 (lenfunc
)list_length
,
2739 (binaryfunc
)list_subscript
,
2740 (objobjargproc
)list_ass_subscript
2743 PyTypeObject PyList_Type
= {
2744 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2746 sizeof(PyListObject
),
2748 (destructor
)list_dealloc
, /* tp_dealloc */
2749 (printfunc
)list_print
, /* tp_print */
2753 (reprfunc
)list_repr
, /* tp_repr */
2754 0, /* tp_as_number */
2755 &list_as_sequence
, /* tp_as_sequence */
2756 &list_as_mapping
, /* tp_as_mapping */
2757 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
2760 PyObject_GenericGetAttr
, /* tp_getattro */
2761 0, /* tp_setattro */
2762 0, /* tp_as_buffer */
2763 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2764 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_LIST_SUBCLASS
, /* tp_flags */
2765 list_doc
, /* tp_doc */
2766 (traverseproc
)list_traverse
, /* tp_traverse */
2767 (inquiry
)list_clear
, /* tp_clear */
2768 list_richcompare
, /* tp_richcompare */
2769 0, /* tp_weaklistoffset */
2770 list_iter
, /* tp_iter */
2771 0, /* tp_iternext */
2772 list_methods
, /* tp_methods */
2777 0, /* tp_descr_get */
2778 0, /* tp_descr_set */
2779 0, /* tp_dictoffset */
2780 (initproc
)list_init
, /* tp_init */
2781 PyType_GenericAlloc
, /* tp_alloc */
2782 PyType_GenericNew
, /* tp_new */
2783 PyObject_GC_Del
, /* tp_free */
2787 /*********************** List Iterator **************************/
2792 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2795 static PyObject
*list_iter(PyObject
*);
2796 static void listiter_dealloc(listiterobject
*);
2797 static int listiter_traverse(listiterobject
*, visitproc
, void *);
2798 static PyObject
*listiter_next(listiterobject
*);
2799 static PyObject
*listiter_len(listiterobject
*);
2801 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
2803 static PyMethodDef listiter_methods
[] = {
2804 {"__length_hint__", (PyCFunction
)listiter_len
, METH_NOARGS
, length_hint_doc
},
2805 {NULL
, NULL
} /* sentinel */
2808 PyTypeObject PyListIter_Type
= {
2809 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2810 "listiterator", /* tp_name */
2811 sizeof(listiterobject
), /* tp_basicsize */
2812 0, /* tp_itemsize */
2814 (destructor
)listiter_dealloc
, /* tp_dealloc */
2820 0, /* tp_as_number */
2821 0, /* tp_as_sequence */
2822 0, /* tp_as_mapping */
2826 PyObject_GenericGetAttr
, /* tp_getattro */
2827 0, /* tp_setattro */
2828 0, /* tp_as_buffer */
2829 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2831 (traverseproc
)listiter_traverse
, /* tp_traverse */
2833 0, /* tp_richcompare */
2834 0, /* tp_weaklistoffset */
2835 PyObject_SelfIter
, /* tp_iter */
2836 (iternextfunc
)listiter_next
, /* tp_iternext */
2837 listiter_methods
, /* tp_methods */
2843 list_iter(PyObject
*seq
)
2847 if (!PyList_Check(seq
)) {
2848 PyErr_BadInternalCall();
2851 it
= PyObject_GC_New(listiterobject
, &PyListIter_Type
);
2856 it
->it_seq
= (PyListObject
*)seq
;
2857 _PyObject_GC_TRACK(it
);
2858 return (PyObject
*)it
;
2862 listiter_dealloc(listiterobject
*it
)
2864 _PyObject_GC_UNTRACK(it
);
2865 Py_XDECREF(it
->it_seq
);
2866 PyObject_GC_Del(it
);
2870 listiter_traverse(listiterobject
*it
, visitproc visit
, void *arg
)
2872 Py_VISIT(it
->it_seq
);
2877 listiter_next(listiterobject
*it
)
2886 assert(PyList_Check(seq
));
2888 if (it
->it_index
< PyList_GET_SIZE(seq
)) {
2889 item
= PyList_GET_ITEM(seq
, it
->it_index
);
2901 listiter_len(listiterobject
*it
)
2905 len
= PyList_GET_SIZE(it
->it_seq
) - it
->it_index
;
2907 return PyInt_FromSsize_t(len
);
2909 return PyInt_FromLong(0);
2911 /*********************** List Reverse Iterator **************************/
2915 Py_ssize_t it_index
;
2916 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2917 } listreviterobject
;
2919 static PyObject
*list_reversed(PyListObject
*, PyObject
*);
2920 static void listreviter_dealloc(listreviterobject
*);
2921 static int listreviter_traverse(listreviterobject
*, visitproc
, void *);
2922 static PyObject
*listreviter_next(listreviterobject
*);
2923 static PyObject
*listreviter_len(listreviterobject
*);
2925 static PyMethodDef listreviter_methods
[] = {
2926 {"__length_hint__", (PyCFunction
)listreviter_len
, METH_NOARGS
, length_hint_doc
},
2927 {NULL
, NULL
} /* sentinel */
2930 PyTypeObject PyListRevIter_Type
= {
2931 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2932 "listreverseiterator", /* tp_name */
2933 sizeof(listreviterobject
), /* tp_basicsize */
2934 0, /* tp_itemsize */
2936 (destructor
)listreviter_dealloc
, /* tp_dealloc */
2942 0, /* tp_as_number */
2943 0, /* tp_as_sequence */
2944 0, /* tp_as_mapping */
2948 PyObject_GenericGetAttr
, /* tp_getattro */
2949 0, /* tp_setattro */
2950 0, /* tp_as_buffer */
2951 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2953 (traverseproc
)listreviter_traverse
, /* tp_traverse */
2955 0, /* tp_richcompare */
2956 0, /* tp_weaklistoffset */
2957 PyObject_SelfIter
, /* tp_iter */
2958 (iternextfunc
)listreviter_next
, /* tp_iternext */
2959 listreviter_methods
, /* tp_methods */
2964 list_reversed(PyListObject
*seq
, PyObject
*unused
)
2966 listreviterobject
*it
;
2968 it
= PyObject_GC_New(listreviterobject
, &PyListRevIter_Type
);
2971 assert(PyList_Check(seq
));
2972 it
->it_index
= PyList_GET_SIZE(seq
) - 1;
2975 PyObject_GC_Track(it
);
2976 return (PyObject
*)it
;
2980 listreviter_dealloc(listreviterobject
*it
)
2982 PyObject_GC_UnTrack(it
);
2983 Py_XDECREF(it
->it_seq
);
2984 PyObject_GC_Del(it
);
2988 listreviter_traverse(listreviterobject
*it
, visitproc visit
, void *arg
)
2990 Py_VISIT(it
->it_seq
);
2995 listreviter_next(listreviterobject
*it
)
2998 Py_ssize_t index
= it
->it_index
;
2999 PyListObject
*seq
= it
->it_seq
;
3001 if (index
>=0 && index
< PyList_GET_SIZE(seq
)) {
3002 item
= PyList_GET_ITEM(seq
, index
);
3016 listreviter_len(listreviterobject
*it
)
3018 Py_ssize_t len
= it
->it_index
+ 1;
3019 if (it
->it_seq
== NULL
|| PyList_GET_SIZE(it
->it_seq
) < len
)
3021 return PyLong_FromSsize_t(len
);