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 * responsibility 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
<= (PY_SIZE_MAX
/ 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 /* Check for overflow without an actual overflow,
130 * which can cause compiler to optimise out */
131 if ((size_t)size
> PY_SIZE_MAX
/ sizeof(PyObject
*))
132 return PyErr_NoMemory();
133 nbytes
= size
* sizeof(PyObject
*);
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 if (indexerr
== NULL
)
192 PyErr_SetObject(PyExc_IndexError
, indexerr
);
195 return ((PyListObject
*)op
) -> ob_item
[i
];
199 PyList_SetItem(register PyObject
*op
, register Py_ssize_t i
,
200 register PyObject
*newitem
)
202 register PyObject
*olditem
;
203 register PyObject
**p
;
204 if (!PyList_Check(op
)) {
206 PyErr_BadInternalCall();
209 if (i
< 0 || i
>= Py_SIZE(op
)) {
211 PyErr_SetString(PyExc_IndexError
,
212 "list assignment index out of range");
215 p
= ((PyListObject
*)op
) -> ob_item
+ i
;
223 ins1(PyListObject
*self
, Py_ssize_t where
, PyObject
*v
)
225 Py_ssize_t i
, n
= Py_SIZE(self
);
228 PyErr_BadInternalCall();
231 if (n
== PY_SSIZE_T_MAX
) {
232 PyErr_SetString(PyExc_OverflowError
,
233 "cannot add more objects to list");
237 if (list_resize(self
, n
+1) == -1)
247 items
= self
->ob_item
;
248 for (i
= n
; --i
>= where
; )
249 items
[i
+1] = items
[i
];
256 PyList_Insert(PyObject
*op
, Py_ssize_t where
, PyObject
*newitem
)
258 if (!PyList_Check(op
)) {
259 PyErr_BadInternalCall();
262 return ins1((PyListObject
*)op
, where
, newitem
);
266 app1(PyListObject
*self
, PyObject
*v
)
268 Py_ssize_t n
= PyList_GET_SIZE(self
);
271 if (n
== PY_SSIZE_T_MAX
) {
272 PyErr_SetString(PyExc_OverflowError
,
273 "cannot add more objects to list");
277 if (list_resize(self
, n
+1) == -1)
281 PyList_SET_ITEM(self
, n
, v
);
286 PyList_Append(PyObject
*op
, PyObject
*newitem
)
288 if (PyList_Check(op
) && (newitem
!= NULL
))
289 return app1((PyListObject
*)op
, newitem
);
290 PyErr_BadInternalCall();
297 list_dealloc(PyListObject
*op
)
300 PyObject_GC_UnTrack(op
);
301 Py_TRASHCAN_SAFE_BEGIN(op
)
302 if (op
->ob_item
!= NULL
) {
303 /* Do it backwards, for Christian Tismer.
304 There's a simple test case where somehow this reduces
305 thrashing when a *very* large list is created and
306 immediately deleted. */
309 Py_XDECREF(op
->ob_item
[i
]);
311 PyMem_FREE(op
->ob_item
);
313 if (numfree
< PyList_MAXFREELIST
&& PyList_CheckExact(op
))
314 free_list
[numfree
++] = op
;
316 Py_TYPE(op
)->tp_free((PyObject
*)op
);
317 Py_TRASHCAN_SAFE_END(op
)
321 list_print(PyListObject
*op
, FILE *fp
, int flags
)
327 rc
= Py_ReprEnter((PyObject
*)op
);
331 Py_BEGIN_ALLOW_THREADS
332 fprintf(fp
, "[...]");
336 Py_BEGIN_ALLOW_THREADS
339 for (i
= 0; i
< Py_SIZE(op
); i
++) {
340 item
= op
->ob_item
[i
];
343 Py_BEGIN_ALLOW_THREADS
347 if (PyObject_Print(item
, fp
, 0) != 0) {
349 Py_ReprLeave((PyObject
*)op
);
354 Py_BEGIN_ALLOW_THREADS
357 Py_ReprLeave((PyObject
*)op
);
362 list_repr(PyListObject
*v
)
366 PyObject
*pieces
= NULL
, *result
= NULL
;
368 i
= Py_ReprEnter((PyObject
*)v
);
370 return i
> 0 ? PyString_FromString("[...]") : NULL
;
373 if (Py_SIZE(v
) == 0) {
374 result
= PyString_FromString("[]");
378 pieces
= PyList_New(0);
382 /* Do repr() on each element. Note that this may mutate the list,
383 so must refetch the list size on each iteration. */
384 for (i
= 0; i
< Py_SIZE(v
); ++i
) {
386 if (Py_EnterRecursiveCall(" while getting the repr of a list"))
388 s
= PyObject_Repr(v
->ob_item
[i
]);
389 Py_LeaveRecursiveCall();
392 status
= PyList_Append(pieces
, s
);
393 Py_DECREF(s
); /* append created a new ref */
398 /* Add "[]" decorations to the first and last items. */
399 assert(PyList_GET_SIZE(pieces
) > 0);
400 s
= PyString_FromString("[");
403 temp
= PyList_GET_ITEM(pieces
, 0);
404 PyString_ConcatAndDel(&s
, temp
);
405 PyList_SET_ITEM(pieces
, 0, s
);
409 s
= PyString_FromString("]");
412 temp
= PyList_GET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1);
413 PyString_ConcatAndDel(&temp
, s
);
414 PyList_SET_ITEM(pieces
, PyList_GET_SIZE(pieces
) - 1, temp
);
418 /* Paste them all together with ", " between. */
419 s
= PyString_FromString(", ");
422 result
= _PyString_Join(s
, pieces
);
427 Py_ReprLeave((PyObject
*)v
);
432 list_length(PyListObject
*a
)
438 list_contains(PyListObject
*a
, PyObject
*el
)
443 for (i
= 0, cmp
= 0 ; cmp
== 0 && i
< Py_SIZE(a
); ++i
)
444 cmp
= PyObject_RichCompareBool(el
, PyList_GET_ITEM(a
, i
),
450 list_item(PyListObject
*a
, Py_ssize_t i
)
452 if (i
< 0 || i
>= Py_SIZE(a
)) {
453 if (indexerr
== NULL
) {
454 indexerr
= PyString_FromString(
455 "list index out of range");
456 if (indexerr
== NULL
)
459 PyErr_SetObject(PyExc_IndexError
, indexerr
);
462 Py_INCREF(a
->ob_item
[i
]);
463 return a
->ob_item
[i
];
467 list_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
470 PyObject
**src
, **dest
;
474 else if (ilow
> Py_SIZE(a
))
478 else if (ihigh
> Py_SIZE(a
))
481 np
= (PyListObject
*) PyList_New(len
);
485 src
= a
->ob_item
+ ilow
;
487 for (i
= 0; i
< len
; i
++) {
488 PyObject
*v
= src
[i
];
492 return (PyObject
*)np
;
496 PyList_GetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
)
498 if (!PyList_Check(a
)) {
499 PyErr_BadInternalCall();
502 return list_slice((PyListObject
*)a
, ilow
, ihigh
);
506 list_concat(PyListObject
*a
, PyObject
*bb
)
510 PyObject
**src
, **dest
;
512 if (!PyList_Check(bb
)) {
513 PyErr_Format(PyExc_TypeError
,
514 "can only concatenate list (not \"%.200s\") to list",
515 bb
->ob_type
->tp_name
);
518 #define b ((PyListObject *)bb)
519 size
= Py_SIZE(a
) + Py_SIZE(b
);
521 return PyErr_NoMemory();
522 np
= (PyListObject
*) PyList_New(size
);
528 for (i
= 0; i
< Py_SIZE(a
); i
++) {
529 PyObject
*v
= src
[i
];
534 dest
= np
->ob_item
+ Py_SIZE(a
);
535 for (i
= 0; i
< Py_SIZE(b
); i
++) {
536 PyObject
*v
= src
[i
];
540 return (PyObject
*)np
;
545 list_repeat(PyListObject
*a
, Py_ssize_t n
)
550 PyObject
**p
, **items
;
554 if (n
> 0 && Py_SIZE(a
) > PY_SSIZE_T_MAX
/ n
)
555 return PyErr_NoMemory();
556 size
= Py_SIZE(a
) * n
;
558 return PyList_New(0);
559 np
= (PyListObject
*) PyList_New(size
);
564 if (Py_SIZE(a
) == 1) {
565 elem
= a
->ob_item
[0];
566 for (i
= 0; i
< n
; i
++) {
570 return (PyObject
*) np
;
574 for (i
= 0; i
< n
; i
++) {
575 for (j
= 0; j
< Py_SIZE(a
); j
++) {
581 return (PyObject
*) np
;
585 list_clear(PyListObject
*a
)
588 PyObject
**item
= a
->ob_item
;
590 /* Because XDECREF can recursively invoke operations on
591 this list, we make it empty first. */
601 /* Never fails; the return value can be ignored.
602 Note that there is no guarantee that the list is actually empty
603 at this point, because XDECREF may have populated it again! */
607 /* a[ilow:ihigh] = v if v != NULL.
608 * del a[ilow:ihigh] if v == NULL.
610 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
611 * guaranteed the call cannot fail.
614 list_ass_slice(PyListObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
616 /* Because [X]DECREF can recursively invoke list operations on
617 this list, we must postpone all [X]DECREF activity until
618 after the list is back in its canonical shape. Therefore
619 we must allocate an additional array, 'recycle', into which
620 we temporarily copy the items that are deleted from the
622 PyObject
*recycle_on_stack
[8];
623 PyObject
**recycle
= recycle_on_stack
; /* will allocate more if needed */
625 PyObject
**vitem
= NULL
;
626 PyObject
*v_as_SF
= NULL
; /* PySequence_Fast(v) */
627 Py_ssize_t n
; /* # of elements in replacement list */
628 Py_ssize_t norig
; /* # of elements in list getting replaced */
629 Py_ssize_t d
; /* Change in size */
632 int result
= -1; /* guilty until proved innocent */
633 #define b ((PyListObject *)v)
638 /* Special case "a[i:j] = a" -- copy b first */
639 v
= list_slice(b
, 0, Py_SIZE(b
));
642 result
= list_ass_slice(a
, ilow
, ihigh
, v
);
646 v_as_SF
= PySequence_Fast(v
, "can only assign an iterable");
649 n
= PySequence_Fast_GET_SIZE(v_as_SF
);
650 vitem
= PySequence_Fast_ITEMS(v_as_SF
);
654 else if (ilow
> Py_SIZE(a
))
659 else if (ihigh
> Py_SIZE(a
))
662 norig
= ihigh
- ilow
;
665 if (Py_SIZE(a
) + d
== 0) {
667 return list_clear(a
);
670 /* recycle the items that we are about to remove */
671 s
= norig
* sizeof(PyObject
*);
672 if (s
> sizeof(recycle_on_stack
)) {
673 recycle
= (PyObject
**)PyMem_MALLOC(s
);
674 if (recycle
== NULL
) {
679 memcpy(recycle
, &item
[ilow
], s
);
681 if (d
< 0) { /* Delete -d items */
682 memmove(&item
[ihigh
+d
], &item
[ihigh
],
683 (Py_SIZE(a
) - ihigh
)*sizeof(PyObject
*));
684 list_resize(a
, Py_SIZE(a
) + d
);
687 else if (d
> 0) { /* Insert d items */
689 if (list_resize(a
, k
+d
) < 0)
692 memmove(&item
[ihigh
+d
], &item
[ihigh
],
693 (k
- ihigh
)*sizeof(PyObject
*));
695 for (k
= 0; k
< n
; k
++, ilow
++) {
696 PyObject
*w
= vitem
[k
];
700 for (k
= norig
- 1; k
>= 0; --k
)
701 Py_XDECREF(recycle
[k
]);
704 if (recycle
!= recycle_on_stack
)
712 PyList_SetSlice(PyObject
*a
, Py_ssize_t ilow
, Py_ssize_t ihigh
, PyObject
*v
)
714 if (!PyList_Check(a
)) {
715 PyErr_BadInternalCall();
718 return list_ass_slice((PyListObject
*)a
, ilow
, ihigh
, v
);
722 list_inplace_repeat(PyListObject
*self
, Py_ssize_t n
)
725 Py_ssize_t size
, i
, j
, p
;
728 size
= PyList_GET_SIZE(self
);
729 if (size
== 0 || n
== 1) {
731 return (PyObject
*)self
;
735 (void)list_clear(self
);
737 return (PyObject
*)self
;
740 if (size
> PY_SSIZE_T_MAX
/ n
) {
741 return PyErr_NoMemory();
744 if (list_resize(self
, size
*n
) == -1)
748 items
= self
->ob_item
;
749 for (i
= 1; i
< n
; i
++) { /* Start counting at 1, not 0 */
750 for (j
= 0; j
< size
; j
++) {
751 PyObject
*o
= items
[j
];
757 return (PyObject
*)self
;
761 list_ass_item(PyListObject
*a
, Py_ssize_t i
, PyObject
*v
)
764 if (i
< 0 || i
>= Py_SIZE(a
)) {
765 PyErr_SetString(PyExc_IndexError
,
766 "list assignment index out of range");
770 return list_ass_slice(a
, i
, i
+1, v
);
772 old_value
= a
->ob_item
[i
];
774 Py_DECREF(old_value
);
779 listinsert(PyListObject
*self
, PyObject
*args
)
783 if (!PyArg_ParseTuple(args
, "nO:insert", &i
, &v
))
785 if (ins1(self
, i
, v
) == 0)
791 listappend(PyListObject
*self
, PyObject
*v
)
793 if (app1(self
, v
) == 0)
799 listextend(PyListObject
*self
, PyObject
*b
)
801 PyObject
*it
; /* iter(v) */
802 Py_ssize_t m
; /* size of self */
803 Py_ssize_t n
; /* guess for size of b */
804 Py_ssize_t mn
; /* m + n */
806 PyObject
*(*iternext
)(PyObject
*);
809 1) lists and tuples which can use PySequence_Fast ops
810 2) extending self to self requires making a copy first
812 if (PyList_CheckExact(b
) || PyTuple_CheckExact(b
) || (PyObject
*)self
== b
) {
813 PyObject
**src
, **dest
;
814 b
= PySequence_Fast(b
, "argument must be iterable");
817 n
= PySequence_Fast_GET_SIZE(b
);
819 /* short circuit when b is empty */
824 if (list_resize(self
, m
+ n
) == -1) {
828 /* note that we may still have self == b here for the
829 * situation a.extend(a), but the following code works
830 * in that case too. Just make sure to resize self
831 * before calling PySequence_Fast_ITEMS.
833 /* populate the end of self with b's items */
834 src
= PySequence_Fast_ITEMS(b
);
835 dest
= self
->ob_item
+ m
;
836 for (i
= 0; i
< n
; i
++) {
837 PyObject
*o
= src
[i
];
845 it
= PyObject_GetIter(b
);
848 iternext
= *it
->ob_type
->tp_iternext
;
850 /* Guess a result list size. */
851 n
= _PyObject_LengthHint(b
, 8);
860 if (list_resize(self
, mn
) == -1)
862 /* Make the list sane again. */
865 /* Else m + n overflowed; on the chance that n lied, and there really
866 * is enough room, ignore it. If n was telling the truth, we'll
867 * eventually run out of memory during the loop.
870 /* Run iterator to exhaustion. */
872 PyObject
*item
= iternext(it
);
874 if (PyErr_Occurred()) {
875 if (PyErr_ExceptionMatches(PyExc_StopIteration
))
882 if (Py_SIZE(self
) < self
->allocated
) {
884 PyList_SET_ITEM(self
, Py_SIZE(self
), item
);
888 int status
= app1(self
, item
);
889 Py_DECREF(item
); /* append creates a new ref */
895 /* Cut back result list if initial guess was too large. */
896 if (Py_SIZE(self
) < self
->allocated
)
897 list_resize(self
, Py_SIZE(self
)); /* shrinking can't fail */
908 _PyList_Extend(PyListObject
*self
, PyObject
*b
)
910 return listextend(self
, b
);
914 list_inplace_concat(PyListObject
*self
, PyObject
*other
)
918 result
= listextend(self
, other
);
923 return (PyObject
*)self
;
927 listpop(PyListObject
*self
, PyObject
*args
)
933 if (!PyArg_ParseTuple(args
, "|n:pop", &i
))
936 if (Py_SIZE(self
) == 0) {
937 /* Special-case most common failure cause */
938 PyErr_SetString(PyExc_IndexError
, "pop from empty list");
943 if (i
< 0 || i
>= Py_SIZE(self
)) {
944 PyErr_SetString(PyExc_IndexError
, "pop index out of range");
947 v
= self
->ob_item
[i
];
948 if (i
== Py_SIZE(self
) - 1) {
949 status
= list_resize(self
, Py_SIZE(self
) - 1);
951 return v
; /* and v now owns the reference the list had */
954 status
= list_ass_slice(self
, i
, i
+1, (PyObject
*)NULL
);
956 /* Use status, so that in a release build compilers don't
957 * complain about the unused name.
964 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
966 reverse_slice(PyObject
**lo
, PyObject
**hi
)
980 /* Lots of code for an adaptive, stable, natural mergesort. There are many
981 * pieces to this algorithm; read listsort.txt for overviews and details.
984 /* Comparison function. Takes care of calling a user-supplied
985 * comparison function (any callable Python object), which must not be
986 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
987 * with Py_LT if you know it's NULL).
988 * Returns -1 on error, 1 if x < y, 0 if x >= y.
991 islt(PyObject
*x
, PyObject
*y
, PyObject
*compare
)
997 assert(compare
!= NULL
);
998 /* Call the user's comparison function and translate the 3-way
999 * result into true or false (or error).
1001 args
= PyTuple_New(2);
1006 PyTuple_SET_ITEM(args
, 0, x
);
1007 PyTuple_SET_ITEM(args
, 1, y
);
1008 res
= PyObject_Call(compare
, args
, NULL
);
1012 if (!PyInt_Check(res
)) {
1013 PyErr_Format(PyExc_TypeError
,
1014 "comparison function must return int, not %.200s",
1015 res
->ob_type
->tp_name
);
1019 i
= PyInt_AsLong(res
);
1024 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
1025 * islt. This avoids a layer of function call in the usual case, and
1026 * sorting does many comparisons.
1027 * Returns -1 on error, 1 if x < y, 0 if x >= y.
1029 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
1030 PyObject_RichCompareBool(X, Y, Py_LT) : \
1031 islt(X, Y, COMPARE))
1033 /* Compare X to Y via "<". Goto "fail" if the comparison raises an
1034 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
1035 started. It makes more sense in context <wink>. X and Y are PyObject*s.
1037 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
1040 /* binarysort is the best method for sorting small arrays: it does
1041 few compares, but can do data movement quadratic in the number of
1043 [lo, hi) is a contiguous slice of a list, and is sorted via
1044 binary insertion. This sort is stable.
1045 On entry, must have lo <= start <= hi, and that [lo, start) is already
1046 sorted (pass start == lo if you don't know!).
1047 If islt() complains return -1, else 0.
1048 Even in case of error, the output slice will be some permutation of
1049 the input (nothing is lost or duplicated).
1052 binarysort(PyObject
**lo
, PyObject
**hi
, PyObject
**start
, PyObject
*compare
)
1053 /* compare -- comparison function object, or NULL for default */
1055 register Py_ssize_t k
;
1056 register PyObject
**l
, **p
, **r
;
1057 register PyObject
*pivot
;
1059 assert(lo
<= start
&& start
<= hi
);
1060 /* assert [lo, start) is sorted */
1063 for (; start
< hi
; ++start
) {
1064 /* set l to where *start belongs */
1069 * pivot >= all in [lo, l).
1070 * pivot < all in [r, start).
1071 * The second is vacuously true at the start.
1075 p
= l
+ ((r
- l
) >> 1);
1082 /* The invariants still hold, so pivot >= all in [lo, l) and
1083 pivot < all in [l, start), so pivot belongs at l. Note
1084 that if there are elements equal to pivot, l points to the
1085 first slot after them -- that's why this sort is stable.
1086 Slide over to make room.
1087 Caution: using memmove is much slower under MSVC 5;
1088 we're not usually moving many slots. */
1089 for (p
= start
; p
> l
; --p
)
1100 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1101 is required on entry. "A run" is the longest ascending sequence, with
1103 lo[0] <= lo[1] <= lo[2] <= ...
1105 or the longest descending sequence, with
1107 lo[0] > lo[1] > lo[2] > ...
1109 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1110 For its intended use in a stable mergesort, the strictness of the defn of
1111 "descending" is needed so that the caller can safely reverse a descending
1112 sequence without violating stability (strict > ensures there are no equal
1113 elements to get out of order).
1115 Returns -1 in case of error.
1118 count_run(PyObject
**lo
, PyObject
**hi
, PyObject
*compare
, int *descending
)
1130 IFLT(*lo
, *(lo
-1)) {
1132 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1140 for (lo
= lo
+1; lo
< hi
; ++lo
, ++n
) {
1152 Locate the proper position of key in a sorted vector; if the vector contains
1153 an element equal to key, return the position immediately to the left of
1154 the leftmost equal element. [gallop_right() does the same except returns
1155 the position to the right of the rightmost equal element (if any).]
1157 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
1159 "hint" is an index at which to begin the search, 0 <= hint < n. The closer
1160 hint is to the final result, the faster this runs.
1162 The return value is the int k in 0..n such that
1164 a[k-1] < key <= a[k]
1166 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1167 key belongs at index k; or, IOW, the first k elements of a should precede
1168 key, and the last n-k should follow key.
1170 Returns -1 on error. See listsort.txt for info on the method.
1173 gallop_left(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1179 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1185 /* a[hint] < key -- gallop right, until
1186 * a[hint + lastofs] < key <= a[hint + ofs]
1188 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1189 while (ofs
< maxofs
) {
1192 ofs
= (ofs
<< 1) + 1;
1193 if (ofs
<= 0) /* int overflow */
1196 else /* key <= a[hint + ofs] */
1201 /* Translate back to offsets relative to &a[0]. */
1206 /* key <= a[hint] -- gallop left, until
1207 * a[hint - ofs] < key <= a[hint - lastofs]
1209 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1210 while (ofs
< maxofs
) {
1213 /* key <= a[hint - ofs] */
1215 ofs
= (ofs
<< 1) + 1;
1216 if (ofs
<= 0) /* int overflow */
1221 /* Translate back to positive offsets relative to &a[0]. */
1223 lastofs
= hint
- ofs
;
1228 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1229 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1230 * right of lastofs but no farther right than ofs. Do a binary
1231 * search, with invariant a[lastofs-1] < key <= a[ofs].
1234 while (lastofs
< ofs
) {
1235 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1238 lastofs
= m
+1; /* a[m] < key */
1240 ofs
= m
; /* key <= a[m] */
1242 assert(lastofs
== ofs
); /* so a[ofs-1] < key <= a[ofs] */
1250 Exactly like gallop_left(), except that if key already exists in a[0:n],
1251 finds the position immediately to the right of the rightmost equal value.
1253 The return value is the int k in 0..n such that
1255 a[k-1] <= key < a[k]
1259 The code duplication is massive, but this is enough different given that
1260 we're sticking to "<" comparisons that it's much harder to follow if
1261 written as one routine with yet another "left or right?" flag.
1264 gallop_right(PyObject
*key
, PyObject
**a
, Py_ssize_t n
, Py_ssize_t hint
, PyObject
*compare
)
1270 assert(key
&& a
&& n
> 0 && hint
>= 0 && hint
< n
);
1276 /* key < a[hint] -- gallop left, until
1277 * a[hint - ofs] <= key < a[hint - lastofs]
1279 const Py_ssize_t maxofs
= hint
+ 1; /* &a[0] is lowest */
1280 while (ofs
< maxofs
) {
1281 IFLT(key
, *(a
-ofs
)) {
1283 ofs
= (ofs
<< 1) + 1;
1284 if (ofs
<= 0) /* int overflow */
1287 else /* a[hint - ofs] <= key */
1292 /* Translate back to positive offsets relative to &a[0]. */
1294 lastofs
= hint
- ofs
;
1298 /* a[hint] <= key -- gallop right, until
1299 * a[hint + lastofs] <= key < a[hint + ofs]
1301 const Py_ssize_t maxofs
= n
- hint
; /* &a[n-1] is highest */
1302 while (ofs
< maxofs
) {
1305 /* a[hint + ofs] <= key */
1307 ofs
= (ofs
<< 1) + 1;
1308 if (ofs
<= 0) /* int overflow */
1313 /* Translate back to offsets relative to &a[0]. */
1319 assert(-1 <= lastofs
&& lastofs
< ofs
&& ofs
<= n
);
1320 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1321 * right of lastofs but no farther right than ofs. Do a binary
1322 * search, with invariant a[lastofs-1] <= key < a[ofs].
1325 while (lastofs
< ofs
) {
1326 Py_ssize_t m
= lastofs
+ ((ofs
- lastofs
) >> 1);
1329 ofs
= m
; /* key < a[m] */
1331 lastofs
= m
+1; /* a[m] <= key */
1333 assert(lastofs
== ofs
); /* so a[ofs-1] <= key < a[ofs] */
1340 /* The maximum number of entries in a MergeState's pending-runs stack.
1341 * This is enough to sort arrays of size up to about
1342 * 32 * phi ** MAX_MERGE_PENDING
1343 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1344 * with 2**64 elements.
1346 #define MAX_MERGE_PENDING 85
1348 /* When we get into galloping mode, we stay there until both runs win less
1349 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
1351 #define MIN_GALLOP 7
1353 /* Avoid malloc for small temp arrays. */
1354 #define MERGESTATE_TEMP_SIZE 256
1356 /* One MergeState exists on the stack per invocation of mergesort. It's just
1357 * a convenient way to pass state around among the helper functions.
1364 typedef struct s_MergeState
{
1365 /* The user-supplied comparison function. or NULL if none given. */
1368 /* This controls when we get *into* galloping mode. It's initialized
1369 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1370 * random data, and lower for highly structured data.
1372 Py_ssize_t min_gallop
;
1374 /* 'a' is temp storage to help with merges. It contains room for
1377 PyObject
**a
; /* may point to temparray below */
1380 /* A stack of n pending runs yet to be merged. Run #i starts at
1381 * address base[i] and extends for len[i] elements. It's always
1382 * true (so long as the indices are in bounds) that
1384 * pending[i].base + pending[i].len == pending[i+1].base
1386 * so we could cut the storage for this, but it's a minor amount,
1387 * and keeping all the info explicit simplifies the code.
1390 struct s_slice pending
[MAX_MERGE_PENDING
];
1392 /* 'a' points to this when possible, rather than muck with malloc. */
1393 PyObject
*temparray
[MERGESTATE_TEMP_SIZE
];
1396 /* Conceptually a MergeState's constructor. */
1398 merge_init(MergeState
*ms
, PyObject
*compare
)
1401 ms
->compare
= compare
;
1402 ms
->a
= ms
->temparray
;
1403 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1405 ms
->min_gallop
= MIN_GALLOP
;
1408 /* Free all the temp memory owned by the MergeState. This must be called
1409 * when you're done with a MergeState, and may be called before then if
1410 * you want to free the temp memory early.
1413 merge_freemem(MergeState
*ms
)
1416 if (ms
->a
!= ms
->temparray
)
1418 ms
->a
= ms
->temparray
;
1419 ms
->alloced
= MERGESTATE_TEMP_SIZE
;
1422 /* Ensure enough temp memory for 'need' array slots is available.
1423 * Returns 0 on success and -1 if the memory can't be gotten.
1426 merge_getmem(MergeState
*ms
, Py_ssize_t need
)
1429 if (need
<= ms
->alloced
)
1431 /* Don't realloc! That can cost cycles to copy the old data, but
1432 * we don't care what's in the block.
1435 if ((size_t)need
> PY_SSIZE_T_MAX
/ sizeof(PyObject
*)) {
1439 ms
->a
= (PyObject
**)PyMem_Malloc(need
* sizeof(PyObject
*));
1445 merge_freemem(ms
); /* reset to sane state */
1448 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1449 merge_getmem(MS, NEED))
1451 /* Merge the na elements starting at pa with the nb elements starting at pb
1452 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1453 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1454 * merge, and should have na <= nb. See listsort.txt for more info.
1455 * Return 0 if successful, -1 if error.
1458 merge_lo(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
,
1459 PyObject
**pb
, Py_ssize_t nb
)
1464 int result
= -1; /* guilty until proved innocent */
1465 Py_ssize_t min_gallop
;
1467 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1468 if (MERGE_GETMEM(ms
, na
) < 0)
1470 memcpy(ms
->a
, pa
, na
* sizeof(PyObject
*));
1481 min_gallop
= ms
->min_gallop
;
1482 compare
= ms
->compare
;
1484 Py_ssize_t acount
= 0; /* # of times A won in a row */
1485 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1487 /* Do the straightforward thing until (if ever) one run
1488 * appears to win consistently.
1491 assert(na
> 1 && nb
> 0);
1492 k
= ISLT(*pb
, *pa
, compare
);
1502 if (bcount
>= min_gallop
)
1512 if (acount
>= min_gallop
)
1517 /* One run is winning so consistently that galloping may
1518 * be a huge win. So try that, and continue galloping until
1519 * (if ever) neither run appears to be winning consistently
1524 assert(na
> 1 && nb
> 0);
1525 min_gallop
-= min_gallop
> 1;
1526 ms
->min_gallop
= min_gallop
;
1527 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1532 memcpy(dest
, pa
, k
* sizeof(PyObject
*));
1538 /* na==0 is impossible now if the comparison
1539 * function is consistent, but we can't assume
1550 k
= gallop_left(*pa
, pb
, nb
, 0, compare
);
1555 memmove(dest
, pb
, k
* sizeof(PyObject
*));
1566 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1567 ++min_gallop
; /* penalize it for leaving galloping mode */
1568 ms
->min_gallop
= min_gallop
;
1574 memcpy(dest
, pa
, na
* sizeof(PyObject
*));
1577 assert(na
== 1 && nb
> 0);
1578 /* The last element of pa belongs at the end of the merge. */
1579 memmove(dest
, pb
, nb
* sizeof(PyObject
*));
1584 /* Merge the na elements starting at pa with the nb elements starting at pb
1585 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1586 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1587 * merge, and should have na >= nb. See listsort.txt for more info.
1588 * Return 0 if successful, -1 if error.
1591 merge_hi(MergeState
*ms
, PyObject
**pa
, Py_ssize_t na
, PyObject
**pb
, Py_ssize_t nb
)
1596 int result
= -1; /* guilty until proved innocent */
1599 Py_ssize_t min_gallop
;
1601 assert(ms
&& pa
&& pb
&& na
> 0 && nb
> 0 && pa
+ na
== pb
);
1602 if (MERGE_GETMEM(ms
, nb
) < 0)
1605 memcpy(ms
->a
, pb
, nb
* sizeof(PyObject
*));
1608 pb
= ms
->a
+ nb
- 1;
1618 min_gallop
= ms
->min_gallop
;
1619 compare
= ms
->compare
;
1621 Py_ssize_t acount
= 0; /* # of times A won in a row */
1622 Py_ssize_t bcount
= 0; /* # of times B won in a row */
1624 /* Do the straightforward thing until (if ever) one run
1625 * appears to win consistently.
1628 assert(na
> 0 && nb
> 1);
1629 k
= ISLT(*pb
, *pa
, compare
);
1639 if (acount
>= min_gallop
)
1649 if (bcount
>= min_gallop
)
1654 /* One run is winning so consistently that galloping may
1655 * be a huge win. So try that, and continue galloping until
1656 * (if ever) neither run appears to be winning consistently
1661 assert(na
> 0 && nb
> 1);
1662 min_gallop
-= min_gallop
> 1;
1663 ms
->min_gallop
= min_gallop
;
1664 k
= gallop_right(*pb
, basea
, na
, na
-1, compare
);
1672 memmove(dest
+1, pa
+1, k
* sizeof(PyObject
*));
1682 k
= gallop_left(*pa
, baseb
, nb
, nb
-1, compare
);
1690 memcpy(dest
+1, pb
+1, k
* sizeof(PyObject
*));
1694 /* nb==0 is impossible now if the comparison
1695 * function is consistent, but we can't assume
1705 } while (acount
>= MIN_GALLOP
|| bcount
>= MIN_GALLOP
);
1706 ++min_gallop
; /* penalize it for leaving galloping mode */
1707 ms
->min_gallop
= min_gallop
;
1713 memcpy(dest
-(nb
-1), baseb
, nb
* sizeof(PyObject
*));
1716 assert(nb
== 1 && na
> 0);
1717 /* The first element of pb belongs at the front of the merge. */
1720 memmove(dest
+1, pa
+1, na
* sizeof(PyObject
*));
1725 /* Merge the two runs at stack indices i and i+1.
1726 * Returns 0 on success, -1 on error.
1729 merge_at(MergeState
*ms
, Py_ssize_t i
)
1731 PyObject
**pa
, **pb
;
1739 assert(i
== ms
->n
- 2 || i
== ms
->n
- 3);
1741 pa
= ms
->pending
[i
].base
;
1742 na
= ms
->pending
[i
].len
;
1743 pb
= ms
->pending
[i
+1].base
;
1744 nb
= ms
->pending
[i
+1].len
;
1745 assert(na
> 0 && nb
> 0);
1746 assert(pa
+ na
== pb
);
1748 /* Record the length of the combined runs; if i is the 3rd-last
1749 * run now, also slide over the last run (which isn't involved
1750 * in this merge). The current run i+1 goes away in any case.
1752 ms
->pending
[i
].len
= na
+ nb
;
1754 ms
->pending
[i
+1] = ms
->pending
[i
+2];
1757 /* Where does b start in a? Elements in a before that can be
1758 * ignored (already in place).
1760 compare
= ms
->compare
;
1761 k
= gallop_right(*pb
, pa
, na
, 0, compare
);
1769 /* Where does a end in b? Elements in b after that can be
1770 * ignored (already in place).
1772 nb
= gallop_left(pa
[na
-1], pb
, nb
, nb
-1, compare
);
1776 /* Merge what remains of the runs, using a temp array with
1777 * min(na, nb) elements.
1780 return merge_lo(ms
, pa
, na
, pb
, nb
);
1782 return merge_hi(ms
, pa
, na
, pb
, nb
);
1785 /* Examine the stack of runs waiting to be merged, merging adjacent runs
1786 * until the stack invariants are re-established:
1788 * 1. len[-3] > len[-2] + len[-1]
1789 * 2. len[-2] > len[-1]
1791 * See listsort.txt for more info.
1793 * Returns 0 on success, -1 on error.
1796 merge_collapse(MergeState
*ms
)
1798 struct s_slice
*p
= ms
->pending
;
1802 Py_ssize_t n
= ms
->n
- 2;
1803 if ((n
> 0 && p
[n
-1].len
<= p
[n
].len
+ p
[n
+1].len
) ||
1804 (n
> 1 && p
[n
-2].len
<= p
[n
-1].len
+ p
[n
].len
)) {
1805 if (p
[n
-1].len
< p
[n
+1].len
)
1807 if (merge_at(ms
, n
) < 0)
1810 else if (p
[n
].len
<= p
[n
+1].len
) {
1811 if (merge_at(ms
, n
) < 0)
1820 /* Regardless of invariants, merge all runs on the stack until only one
1821 * remains. This is used at the end of the mergesort.
1823 * Returns 0 on success, -1 on error.
1826 merge_force_collapse(MergeState
*ms
)
1828 struct s_slice
*p
= ms
->pending
;
1832 Py_ssize_t n
= ms
->n
- 2;
1833 if (n
> 0 && p
[n
-1].len
< p
[n
+1].len
)
1835 if (merge_at(ms
, n
) < 0)
1841 /* Compute a good value for the minimum run length; natural runs shorter
1842 * than this are boosted artificially via binary insertion.
1844 * If n < 64, return n (it's too small to bother with fancy stuff).
1845 * Else if n is an exact power of 2, return 32.
1846 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1847 * strictly less than, an exact power of 2.
1849 * See listsort.txt for more info.
1852 merge_compute_minrun(Py_ssize_t n
)
1854 Py_ssize_t r
= 0; /* becomes 1 if any 1 bits are shifted off */
1864 /* Special wrapper to support stable sorting using the decorate-sort-undecorate
1865 pattern. Holds a key which is used for comparisons and the original record
1866 which is returned during the undecorate phase. By exposing only the key
1867 during comparisons, the underlying sort stability characteristics are left
1868 unchanged. Also, if a custom comparison function is used, it will only see
1869 the key instead of a full record. */
1875 } sortwrapperobject
;
1877 PyDoc_STRVAR(sortwrapper_doc
, "Object wrapper with a custom sort key.");
1879 sortwrapper_richcompare(sortwrapperobject
*, sortwrapperobject
*, int);
1881 sortwrapper_dealloc(sortwrapperobject
*);
1883 static PyTypeObject sortwrapper_type
= {
1884 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
1885 "sortwrapper", /* tp_name */
1886 sizeof(sortwrapperobject
), /* tp_basicsize */
1887 0, /* tp_itemsize */
1889 (destructor
)sortwrapper_dealloc
, /* tp_dealloc */
1895 0, /* tp_as_number */
1896 0, /* tp_as_sequence */
1897 0, /* tp_as_mapping */
1901 PyObject_GenericGetAttr
, /* tp_getattro */
1902 0, /* tp_setattro */
1903 0, /* tp_as_buffer */
1904 Py_TPFLAGS_DEFAULT
|
1905 Py_TPFLAGS_HAVE_RICHCOMPARE
, /* tp_flags */
1906 sortwrapper_doc
, /* tp_doc */
1907 0, /* tp_traverse */
1909 (richcmpfunc
)sortwrapper_richcompare
, /* tp_richcompare */
1914 sortwrapper_richcompare(sortwrapperobject
*a
, sortwrapperobject
*b
, int op
)
1916 if (!PyObject_TypeCheck(b
, &sortwrapper_type
)) {
1917 PyErr_SetString(PyExc_TypeError
,
1918 "expected a sortwrapperobject");
1921 return PyObject_RichCompare(a
->key
, b
->key
, op
);
1925 sortwrapper_dealloc(sortwrapperobject
*so
)
1927 Py_XDECREF(so
->key
);
1928 Py_XDECREF(so
->value
);
1932 /* Returns a new reference to a sortwrapper.
1933 Consumes the references to the two underlying objects. */
1936 build_sortwrapper(PyObject
*key
, PyObject
*value
)
1938 sortwrapperobject
*so
;
1940 so
= PyObject_New(sortwrapperobject
, &sortwrapper_type
);
1945 return (PyObject
*)so
;
1948 /* Returns a new reference to the value underlying the wrapper. */
1950 sortwrapper_getvalue(PyObject
*so
)
1954 if (!PyObject_TypeCheck(so
, &sortwrapper_type
)) {
1955 PyErr_SetString(PyExc_TypeError
,
1956 "expected a sortwrapperobject");
1959 value
= ((sortwrapperobject
*)so
)->value
;
1964 /* Wrapper for user specified cmp functions in combination with a
1965 specified key function. Makes sure the cmp function is presented
1966 with the actual key instead of the sortwrapper */
1974 cmpwrapper_dealloc(cmpwrapperobject
*co
)
1976 Py_XDECREF(co
->func
);
1981 cmpwrapper_call(cmpwrapperobject
*co
, PyObject
*args
, PyObject
*kwds
)
1983 PyObject
*x
, *y
, *xx
, *yy
;
1985 if (!PyArg_UnpackTuple(args
, "", 2, 2, &x
, &y
))
1987 if (!PyObject_TypeCheck(x
, &sortwrapper_type
) ||
1988 !PyObject_TypeCheck(y
, &sortwrapper_type
)) {
1989 PyErr_SetString(PyExc_TypeError
,
1990 "expected a sortwrapperobject");
1993 xx
= ((sortwrapperobject
*)x
)->key
;
1994 yy
= ((sortwrapperobject
*)y
)->key
;
1995 return PyObject_CallFunctionObjArgs(co
->func
, xx
, yy
, NULL
);
1998 PyDoc_STRVAR(cmpwrapper_doc
, "cmp() wrapper for sort with custom keys.");
2000 static PyTypeObject cmpwrapper_type
= {
2001 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2002 "cmpwrapper", /* tp_name */
2003 sizeof(cmpwrapperobject
), /* tp_basicsize */
2004 0, /* tp_itemsize */
2006 (destructor
)cmpwrapper_dealloc
, /* tp_dealloc */
2012 0, /* tp_as_number */
2013 0, /* tp_as_sequence */
2014 0, /* tp_as_mapping */
2016 (ternaryfunc
)cmpwrapper_call
, /* tp_call */
2018 PyObject_GenericGetAttr
, /* tp_getattro */
2019 0, /* tp_setattro */
2020 0, /* tp_as_buffer */
2021 Py_TPFLAGS_DEFAULT
, /* tp_flags */
2022 cmpwrapper_doc
, /* tp_doc */
2026 build_cmpwrapper(PyObject
*cmpfunc
)
2028 cmpwrapperobject
*co
;
2030 co
= PyObject_New(cmpwrapperobject
, &cmpwrapper_type
);
2035 return (PyObject
*)co
;
2038 /* An adaptive, stable, natural mergesort. See listsort.txt.
2039 * Returns Py_None on success, NULL on error. Even in case of error, the
2040 * list will be some permutation of its input state (nothing is lost or
2044 listsort(PyListObject
*self
, PyObject
*args
, PyObject
*kwds
)
2047 PyObject
**lo
, **hi
;
2048 Py_ssize_t nremaining
;
2050 Py_ssize_t saved_ob_size
, saved_allocated
;
2051 PyObject
**saved_ob_item
;
2052 PyObject
**final_ob_item
;
2053 PyObject
*compare
= NULL
;
2054 PyObject
*result
= NULL
; /* guilty until proved innocent */
2056 PyObject
*keyfunc
= NULL
;
2058 PyObject
*key
, *value
, *kvpair
;
2059 static char *kwlist
[] = {"cmp", "key", "reverse", 0};
2061 assert(self
!= NULL
);
2062 assert (PyList_Check(self
));
2064 if (!PyArg_ParseTupleAndKeywords(args
, kwds
, "|OOi:sort",
2065 kwlist
, &compare
, &keyfunc
, &reverse
))
2068 if (compare
== Py_None
)
2070 if (compare
!= NULL
&&
2071 PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0)
2073 if (keyfunc
== Py_None
)
2075 if (compare
!= NULL
&& keyfunc
!= NULL
) {
2076 compare
= build_cmpwrapper(compare
);
2077 if (compare
== NULL
)
2080 Py_XINCREF(compare
);
2082 /* The list is temporarily made empty, so that mutations performed
2083 * by comparison functions can't affect the slice of memory we're
2084 * sorting (allowing mutations during sorting is a core-dump
2085 * factory, since ob_item may change).
2087 saved_ob_size
= Py_SIZE(self
);
2088 saved_ob_item
= self
->ob_item
;
2089 saved_allocated
= self
->allocated
;
2091 self
->ob_item
= NULL
;
2092 self
->allocated
= -1; /* any operation will reset it to >= 0 */
2094 if (keyfunc
!= NULL
) {
2095 for (i
=0 ; i
< saved_ob_size
; i
++) {
2096 value
= saved_ob_item
[i
];
2097 key
= PyObject_CallFunctionObjArgs(keyfunc
, value
,
2100 for (i
=i
-1 ; i
>=0 ; i
--) {
2101 kvpair
= saved_ob_item
[i
];
2102 value
= sortwrapper_getvalue(kvpair
);
2103 saved_ob_item
[i
] = value
;
2108 kvpair
= build_sortwrapper(key
, value
);
2111 saved_ob_item
[i
] = kvpair
;
2115 /* Reverse sort stability achieved by initially reversing the list,
2116 applying a stable forward sort, then reversing the final result. */
2117 if (reverse
&& saved_ob_size
> 1)
2118 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2120 merge_init(&ms
, compare
);
2122 nremaining
= saved_ob_size
;
2126 /* March over the array once, left to right, finding natural runs,
2127 * and extending short natural runs to minrun elements.
2130 hi
= lo
+ nremaining
;
2131 minrun
= merge_compute_minrun(nremaining
);
2136 /* Identify next run. */
2137 n
= count_run(lo
, hi
, compare
, &descending
);
2141 reverse_slice(lo
, lo
+ n
);
2142 /* If short, extend to min(minrun, nremaining). */
2144 const Py_ssize_t force
= nremaining
<= minrun
?
2145 nremaining
: minrun
;
2146 if (binarysort(lo
, lo
+ force
, lo
+ n
, compare
) < 0)
2150 /* Push run onto pending-runs stack, and maybe merge. */
2151 assert(ms
.n
< MAX_MERGE_PENDING
);
2152 ms
.pending
[ms
.n
].base
= lo
;
2153 ms
.pending
[ms
.n
].len
= n
;
2155 if (merge_collapse(&ms
) < 0)
2157 /* Advance to find next run. */
2160 } while (nremaining
);
2163 if (merge_force_collapse(&ms
) < 0)
2166 assert(ms
.pending
[0].base
== saved_ob_item
);
2167 assert(ms
.pending
[0].len
== saved_ob_size
);
2172 if (keyfunc
!= NULL
) {
2173 for (i
=0 ; i
< saved_ob_size
; i
++) {
2174 kvpair
= saved_ob_item
[i
];
2175 value
= sortwrapper_getvalue(kvpair
);
2176 saved_ob_item
[i
] = value
;
2181 if (self
->allocated
!= -1 && result
!= NULL
) {
2182 /* The user mucked with the list during the sort,
2183 * and we don't already have another error to report.
2185 PyErr_SetString(PyExc_ValueError
, "list modified during sort");
2189 if (reverse
&& saved_ob_size
> 1)
2190 reverse_slice(saved_ob_item
, saved_ob_item
+ saved_ob_size
);
2195 final_ob_item
= self
->ob_item
;
2197 Py_SIZE(self
) = saved_ob_size
;
2198 self
->ob_item
= saved_ob_item
;
2199 self
->allocated
= saved_allocated
;
2200 if (final_ob_item
!= NULL
) {
2201 /* we cannot use list_clear() for this because it does not
2202 guarantee that the list is really empty when it returns */
2204 Py_XDECREF(final_ob_item
[i
]);
2206 PyMem_FREE(final_ob_item
);
2208 Py_XDECREF(compare
);
2216 PyList_Sort(PyObject
*v
)
2218 if (v
== NULL
|| !PyList_Check(v
)) {
2219 PyErr_BadInternalCall();
2222 v
= listsort((PyListObject
*)v
, (PyObject
*)NULL
, (PyObject
*)NULL
);
2230 listreverse(PyListObject
*self
)
2232 if (Py_SIZE(self
) > 1)
2233 reverse_slice(self
->ob_item
, self
->ob_item
+ Py_SIZE(self
));
2238 PyList_Reverse(PyObject
*v
)
2240 PyListObject
*self
= (PyListObject
*)v
;
2242 if (v
== NULL
|| !PyList_Check(v
)) {
2243 PyErr_BadInternalCall();
2246 if (Py_SIZE(self
) > 1)
2247 reverse_slice(self
->ob_item
, self
->ob_item
+ Py_SIZE(self
));
2252 PyList_AsTuple(PyObject
*v
)
2257 if (v
== NULL
|| !PyList_Check(v
)) {
2258 PyErr_BadInternalCall();
2265 p
= ((PyTupleObject
*)w
)->ob_item
;
2266 q
= ((PyListObject
*)v
)->ob_item
;
2277 listindex(PyListObject
*self
, PyObject
*args
)
2279 Py_ssize_t i
, start
=0, stop
=Py_SIZE(self
);
2280 PyObject
*v
, *format_tuple
, *err_string
;
2281 static PyObject
*err_format
= NULL
;
2283 if (!PyArg_ParseTuple(args
, "O|O&O&:index", &v
,
2284 _PyEval_SliceIndex
, &start
,
2285 _PyEval_SliceIndex
, &stop
))
2288 start
+= Py_SIZE(self
);
2293 stop
+= Py_SIZE(self
);
2297 for (i
= start
; i
< stop
&& i
< Py_SIZE(self
); i
++) {
2298 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2300 return PyInt_FromSsize_t(i
);
2304 if (err_format
== NULL
) {
2305 err_format
= PyString_FromString("%r is not in list");
2306 if (err_format
== NULL
)
2309 format_tuple
= PyTuple_Pack(1, v
);
2310 if (format_tuple
== NULL
)
2312 err_string
= PyString_Format(err_format
, format_tuple
);
2313 Py_DECREF(format_tuple
);
2314 if (err_string
== NULL
)
2316 PyErr_SetObject(PyExc_ValueError
, err_string
);
2317 Py_DECREF(err_string
);
2322 listcount(PyListObject
*self
, PyObject
*v
)
2324 Py_ssize_t count
= 0;
2327 for (i
= 0; i
< Py_SIZE(self
); i
++) {
2328 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2334 return PyInt_FromSsize_t(count
);
2338 listremove(PyListObject
*self
, PyObject
*v
)
2342 for (i
= 0; i
< Py_SIZE(self
); i
++) {
2343 int cmp
= PyObject_RichCompareBool(self
->ob_item
[i
], v
, Py_EQ
);
2345 if (list_ass_slice(self
, i
, i
+1,
2346 (PyObject
*)NULL
) == 0)
2353 PyErr_SetString(PyExc_ValueError
, "list.remove(x): x not in list");
2358 list_traverse(PyListObject
*o
, visitproc visit
, void *arg
)
2362 for (i
= Py_SIZE(o
); --i
>= 0; )
2363 Py_VISIT(o
->ob_item
[i
]);
2368 list_richcompare(PyObject
*v
, PyObject
*w
, int op
)
2370 PyListObject
*vl
, *wl
;
2373 if (!PyList_Check(v
) || !PyList_Check(w
)) {
2374 Py_INCREF(Py_NotImplemented
);
2375 return Py_NotImplemented
;
2378 vl
= (PyListObject
*)v
;
2379 wl
= (PyListObject
*)w
;
2381 if (Py_SIZE(vl
) != Py_SIZE(wl
) && (op
== Py_EQ
|| op
== Py_NE
)) {
2382 /* Shortcut: if the lengths differ, the lists differ */
2392 /* Search for the first index where items are different */
2393 for (i
= 0; i
< Py_SIZE(vl
) && i
< Py_SIZE(wl
); i
++) {
2394 int k
= PyObject_RichCompareBool(vl
->ob_item
[i
],
2395 wl
->ob_item
[i
], Py_EQ
);
2402 if (i
>= Py_SIZE(vl
) || i
>= Py_SIZE(wl
)) {
2403 /* No more items to compare -- compare sizes */
2404 Py_ssize_t vs
= Py_SIZE(vl
);
2405 Py_ssize_t ws
= Py_SIZE(wl
);
2409 case Py_LT
: cmp
= vs
< ws
; break;
2410 case Py_LE
: cmp
= vs
<= ws
; break;
2411 case Py_EQ
: cmp
= vs
== ws
; break;
2412 case Py_NE
: cmp
= vs
!= ws
; break;
2413 case Py_GT
: cmp
= vs
> ws
; break;
2414 case Py_GE
: cmp
= vs
>= ws
; break;
2415 default: return NULL
; /* cannot happen */
2425 /* We have an item that differs -- shortcuts for EQ/NE */
2427 Py_INCREF(Py_False
);
2435 /* Compare the final item again using the proper operator */
2436 return PyObject_RichCompare(vl
->ob_item
[i
], wl
->ob_item
[i
], op
);
2440 list_init(PyListObject
*self
, PyObject
*args
, PyObject
*kw
)
2442 PyObject
*arg
= NULL
;
2443 static char *kwlist
[] = {"sequence", 0};
2445 if (!PyArg_ParseTupleAndKeywords(args
, kw
, "|O:list", kwlist
, &arg
))
2448 /* Verify list invariants established by PyType_GenericAlloc() */
2449 assert(0 <= Py_SIZE(self
));
2450 assert(Py_SIZE(self
) <= self
->allocated
|| self
->allocated
== -1);
2451 assert(self
->ob_item
!= NULL
||
2452 self
->allocated
== 0 || self
->allocated
== -1);
2454 /* Empty previous contents */
2455 if (self
->ob_item
!= NULL
) {
2456 (void)list_clear(self
);
2459 PyObject
*rv
= listextend(self
, arg
);
2468 list_sizeof(PyListObject
*self
)
2472 res
= sizeof(PyListObject
) + self
->allocated
* sizeof(void*);
2473 return PyInt_FromSsize_t(res
);
2476 static PyObject
*list_iter(PyObject
*seq
);
2477 static PyObject
*list_reversed(PyListObject
* seq
, PyObject
* unused
);
2479 PyDoc_STRVAR(getitem_doc
,
2480 "x.__getitem__(y) <==> x[y]");
2481 PyDoc_STRVAR(reversed_doc
,
2482 "L.__reversed__() -- return a reverse iterator over the list");
2483 PyDoc_STRVAR(sizeof_doc
,
2484 "L.__sizeof__() -- size of L in memory, in bytes");
2485 PyDoc_STRVAR(append_doc
,
2486 "L.append(object) -- append object to end");
2487 PyDoc_STRVAR(extend_doc
,
2488 "L.extend(iterable) -- extend list by appending elements from the iterable");
2489 PyDoc_STRVAR(insert_doc
,
2490 "L.insert(index, object) -- insert object before index");
2491 PyDoc_STRVAR(pop_doc
,
2492 "L.pop([index]) -> item -- remove and return item at index (default last).\n"
2493 "Raises IndexError if list is empty or index is out of range.");
2494 PyDoc_STRVAR(remove_doc
,
2495 "L.remove(value) -- remove first occurrence of value.\n"
2496 "Raises ValueError if the value is not present.");
2497 PyDoc_STRVAR(index_doc
,
2498 "L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
2499 "Raises ValueError if the value is not present.");
2500 PyDoc_STRVAR(count_doc
,
2501 "L.count(value) -> integer -- return number of occurrences of value");
2502 PyDoc_STRVAR(reverse_doc
,
2503 "L.reverse() -- reverse *IN PLACE*");
2504 PyDoc_STRVAR(sort_doc
,
2505 "L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
2506 cmp(x, y) -> -1, 0, 1");
2508 static PyObject
*list_subscript(PyListObject
*, PyObject
*);
2510 static PyMethodDef list_methods
[] = {
2511 {"__getitem__", (PyCFunction
)list_subscript
, METH_O
|METH_COEXIST
, getitem_doc
},
2512 {"__reversed__",(PyCFunction
)list_reversed
, METH_NOARGS
, reversed_doc
},
2513 {"__sizeof__", (PyCFunction
)list_sizeof
, METH_NOARGS
, sizeof_doc
},
2514 {"append", (PyCFunction
)listappend
, METH_O
, append_doc
},
2515 {"insert", (PyCFunction
)listinsert
, METH_VARARGS
, insert_doc
},
2516 {"extend", (PyCFunction
)listextend
, METH_O
, extend_doc
},
2517 {"pop", (PyCFunction
)listpop
, METH_VARARGS
, pop_doc
},
2518 {"remove", (PyCFunction
)listremove
, METH_O
, remove_doc
},
2519 {"index", (PyCFunction
)listindex
, METH_VARARGS
, index_doc
},
2520 {"count", (PyCFunction
)listcount
, METH_O
, count_doc
},
2521 {"reverse", (PyCFunction
)listreverse
, METH_NOARGS
, reverse_doc
},
2522 {"sort", (PyCFunction
)listsort
, METH_VARARGS
| METH_KEYWORDS
, sort_doc
},
2523 {NULL
, NULL
} /* sentinel */
2526 static PySequenceMethods list_as_sequence
= {
2527 (lenfunc
)list_length
, /* sq_length */
2528 (binaryfunc
)list_concat
, /* sq_concat */
2529 (ssizeargfunc
)list_repeat
, /* sq_repeat */
2530 (ssizeargfunc
)list_item
, /* sq_item */
2531 (ssizessizeargfunc
)list_slice
, /* sq_slice */
2532 (ssizeobjargproc
)list_ass_item
, /* sq_ass_item */
2533 (ssizessizeobjargproc
)list_ass_slice
, /* sq_ass_slice */
2534 (objobjproc
)list_contains
, /* sq_contains */
2535 (binaryfunc
)list_inplace_concat
, /* sq_inplace_concat */
2536 (ssizeargfunc
)list_inplace_repeat
, /* sq_inplace_repeat */
2539 PyDoc_STRVAR(list_doc
,
2540 "list() -> new empty list\n"
2541 "list(iterable) -> new list initialized from iterable's items");
2545 list_subscript(PyListObject
* self
, PyObject
* item
)
2547 if (PyIndex_Check(item
)) {
2549 i
= PyNumber_AsSsize_t(item
, PyExc_IndexError
);
2550 if (i
== -1 && PyErr_Occurred())
2553 i
+= PyList_GET_SIZE(self
);
2554 return list_item(self
, i
);
2556 else if (PySlice_Check(item
)) {
2557 Py_ssize_t start
, stop
, step
, slicelength
, cur
, i
;
2560 PyObject
**src
, **dest
;
2562 if (PySlice_GetIndicesEx((PySliceObject
*)item
, Py_SIZE(self
),
2563 &start
, &stop
, &step
, &slicelength
) < 0) {
2567 if (slicelength
<= 0) {
2568 return PyList_New(0);
2570 else if (step
== 1) {
2571 return list_slice(self
, start
, stop
);
2574 result
= PyList_New(slicelength
);
2575 if (!result
) return NULL
;
2577 src
= self
->ob_item
;
2578 dest
= ((PyListObject
*)result
)->ob_item
;
2579 for (cur
= start
, i
= 0; i
< slicelength
;
2590 PyErr_Format(PyExc_TypeError
,
2591 "list indices must be integers, not %.200s",
2592 item
->ob_type
->tp_name
);
2598 list_ass_subscript(PyListObject
* self
, PyObject
* item
, PyObject
* value
)
2600 if (PyIndex_Check(item
)) {
2601 Py_ssize_t i
= PyNumber_AsSsize_t(item
, PyExc_IndexError
);
2602 if (i
== -1 && PyErr_Occurred())
2605 i
+= PyList_GET_SIZE(self
);
2606 return list_ass_item(self
, i
, value
);
2608 else if (PySlice_Check(item
)) {
2609 Py_ssize_t start
, stop
, step
, slicelength
;
2611 if (PySlice_GetIndicesEx((PySliceObject
*)item
, Py_SIZE(self
),
2612 &start
, &stop
, &step
, &slicelength
) < 0) {
2617 return list_ass_slice(self
, start
, stop
, value
);
2619 /* Make sure s[5:2] = [..] inserts at the right place:
2620 before 5, not before 2. */
2621 if ((step
< 0 && start
< stop
) ||
2622 (step
> 0 && start
> stop
))
2625 if (value
== NULL
) {
2631 if (slicelength
<= 0)
2636 start
= stop
+ step
*(slicelength
- 1) - 1;
2640 assert((size_t)slicelength
<=
2641 PY_SIZE_MAX
/ sizeof(PyObject
*));
2643 garbage
= (PyObject
**)
2644 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2650 /* drawing pictures might help understand these for
2651 loops. Basically, we memmove the parts of the
2652 list that are *not* part of the slice: step-1
2653 items for each item that is part of the slice,
2654 and then tail end of the list that was not
2655 covered by the slice */
2656 for (cur
= start
, i
= 0;
2659 Py_ssize_t lim
= step
- 1;
2661 garbage
[i
] = PyList_GET_ITEM(self
, cur
);
2663 if (cur
+ step
>= (size_t)Py_SIZE(self
)) {
2664 lim
= Py_SIZE(self
) - cur
- 1;
2667 memmove(self
->ob_item
+ cur
- i
,
2668 self
->ob_item
+ cur
+ 1,
2669 lim
* sizeof(PyObject
*));
2671 cur
= start
+ slicelength
*step
;
2672 if (cur
< (size_t)Py_SIZE(self
)) {
2673 memmove(self
->ob_item
+ cur
- slicelength
,
2674 self
->ob_item
+ cur
,
2675 (Py_SIZE(self
) - cur
) *
2676 sizeof(PyObject
*));
2679 Py_SIZE(self
) -= slicelength
;
2680 list_resize(self
, Py_SIZE(self
));
2682 for (i
= 0; i
< slicelength
; i
++) {
2683 Py_DECREF(garbage
[i
]);
2685 PyMem_FREE(garbage
);
2691 PyObject
*ins
, *seq
;
2692 PyObject
**garbage
, **seqitems
, **selfitems
;
2695 /* protect against a[::-1] = a */
2696 if (self
== (PyListObject
*)value
) {
2697 seq
= list_slice((PyListObject
*)value
, 0,
2698 PyList_GET_SIZE(value
));
2701 seq
= PySequence_Fast(value
,
2702 "must assign iterable "
2703 "to extended slice");
2708 if (PySequence_Fast_GET_SIZE(seq
) != slicelength
) {
2709 PyErr_Format(PyExc_ValueError
,
2710 "attempt to assign sequence of "
2711 "size %zd to extended slice of "
2713 PySequence_Fast_GET_SIZE(seq
),
2724 garbage
= (PyObject
**)
2725 PyMem_MALLOC(slicelength
*sizeof(PyObject
*));
2732 selfitems
= self
->ob_item
;
2733 seqitems
= PySequence_Fast_ITEMS(seq
);
2734 for (cur
= start
, i
= 0; i
< slicelength
;
2736 garbage
[i
] = selfitems
[cur
];
2739 selfitems
[cur
] = ins
;
2742 for (i
= 0; i
< slicelength
; i
++) {
2743 Py_DECREF(garbage
[i
]);
2746 PyMem_FREE(garbage
);
2753 PyErr_Format(PyExc_TypeError
,
2754 "list indices must be integers, not %.200s",
2755 item
->ob_type
->tp_name
);
2760 static PyMappingMethods list_as_mapping
= {
2761 (lenfunc
)list_length
,
2762 (binaryfunc
)list_subscript
,
2763 (objobjargproc
)list_ass_subscript
2766 PyTypeObject PyList_Type
= {
2767 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2769 sizeof(PyListObject
),
2771 (destructor
)list_dealloc
, /* tp_dealloc */
2772 (printfunc
)list_print
, /* tp_print */
2776 (reprfunc
)list_repr
, /* tp_repr */
2777 0, /* tp_as_number */
2778 &list_as_sequence
, /* tp_as_sequence */
2779 &list_as_mapping
, /* tp_as_mapping */
2780 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
2783 PyObject_GenericGetAttr
, /* tp_getattro */
2784 0, /* tp_setattro */
2785 0, /* tp_as_buffer */
2786 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
|
2787 Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_LIST_SUBCLASS
, /* tp_flags */
2788 list_doc
, /* tp_doc */
2789 (traverseproc
)list_traverse
, /* tp_traverse */
2790 (inquiry
)list_clear
, /* tp_clear */
2791 list_richcompare
, /* tp_richcompare */
2792 0, /* tp_weaklistoffset */
2793 list_iter
, /* tp_iter */
2794 0, /* tp_iternext */
2795 list_methods
, /* tp_methods */
2800 0, /* tp_descr_get */
2801 0, /* tp_descr_set */
2802 0, /* tp_dictoffset */
2803 (initproc
)list_init
, /* tp_init */
2804 PyType_GenericAlloc
, /* tp_alloc */
2805 PyType_GenericNew
, /* tp_new */
2806 PyObject_GC_Del
, /* tp_free */
2810 /*********************** List Iterator **************************/
2815 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2818 static PyObject
*list_iter(PyObject
*);
2819 static void listiter_dealloc(listiterobject
*);
2820 static int listiter_traverse(listiterobject
*, visitproc
, void *);
2821 static PyObject
*listiter_next(listiterobject
*);
2822 static PyObject
*listiter_len(listiterobject
*);
2824 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
2826 static PyMethodDef listiter_methods
[] = {
2827 {"__length_hint__", (PyCFunction
)listiter_len
, METH_NOARGS
, length_hint_doc
},
2828 {NULL
, NULL
} /* sentinel */
2831 PyTypeObject PyListIter_Type
= {
2832 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2833 "listiterator", /* tp_name */
2834 sizeof(listiterobject
), /* tp_basicsize */
2835 0, /* tp_itemsize */
2837 (destructor
)listiter_dealloc
, /* tp_dealloc */
2843 0, /* tp_as_number */
2844 0, /* tp_as_sequence */
2845 0, /* tp_as_mapping */
2849 PyObject_GenericGetAttr
, /* tp_getattro */
2850 0, /* tp_setattro */
2851 0, /* tp_as_buffer */
2852 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2854 (traverseproc
)listiter_traverse
, /* tp_traverse */
2856 0, /* tp_richcompare */
2857 0, /* tp_weaklistoffset */
2858 PyObject_SelfIter
, /* tp_iter */
2859 (iternextfunc
)listiter_next
, /* tp_iternext */
2860 listiter_methods
, /* tp_methods */
2866 list_iter(PyObject
*seq
)
2870 if (!PyList_Check(seq
)) {
2871 PyErr_BadInternalCall();
2874 it
= PyObject_GC_New(listiterobject
, &PyListIter_Type
);
2879 it
->it_seq
= (PyListObject
*)seq
;
2880 _PyObject_GC_TRACK(it
);
2881 return (PyObject
*)it
;
2885 listiter_dealloc(listiterobject
*it
)
2887 _PyObject_GC_UNTRACK(it
);
2888 Py_XDECREF(it
->it_seq
);
2889 PyObject_GC_Del(it
);
2893 listiter_traverse(listiterobject
*it
, visitproc visit
, void *arg
)
2895 Py_VISIT(it
->it_seq
);
2900 listiter_next(listiterobject
*it
)
2909 assert(PyList_Check(seq
));
2911 if (it
->it_index
< PyList_GET_SIZE(seq
)) {
2912 item
= PyList_GET_ITEM(seq
, it
->it_index
);
2924 listiter_len(listiterobject
*it
)
2928 len
= PyList_GET_SIZE(it
->it_seq
) - it
->it_index
;
2930 return PyInt_FromSsize_t(len
);
2932 return PyInt_FromLong(0);
2934 /*********************** List Reverse Iterator **************************/
2938 Py_ssize_t it_index
;
2939 PyListObject
*it_seq
; /* Set to NULL when iterator is exhausted */
2940 } listreviterobject
;
2942 static PyObject
*list_reversed(PyListObject
*, PyObject
*);
2943 static void listreviter_dealloc(listreviterobject
*);
2944 static int listreviter_traverse(listreviterobject
*, visitproc
, void *);
2945 static PyObject
*listreviter_next(listreviterobject
*);
2946 static PyObject
*listreviter_len(listreviterobject
*);
2948 static PyMethodDef listreviter_methods
[] = {
2949 {"__length_hint__", (PyCFunction
)listreviter_len
, METH_NOARGS
, length_hint_doc
},
2950 {NULL
, NULL
} /* sentinel */
2953 PyTypeObject PyListRevIter_Type
= {
2954 PyVarObject_HEAD_INIT(&PyType_Type
, 0)
2955 "listreverseiterator", /* tp_name */
2956 sizeof(listreviterobject
), /* tp_basicsize */
2957 0, /* tp_itemsize */
2959 (destructor
)listreviter_dealloc
, /* tp_dealloc */
2965 0, /* tp_as_number */
2966 0, /* tp_as_sequence */
2967 0, /* tp_as_mapping */
2971 PyObject_GenericGetAttr
, /* tp_getattro */
2972 0, /* tp_setattro */
2973 0, /* tp_as_buffer */
2974 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
2976 (traverseproc
)listreviter_traverse
, /* tp_traverse */
2978 0, /* tp_richcompare */
2979 0, /* tp_weaklistoffset */
2980 PyObject_SelfIter
, /* tp_iter */
2981 (iternextfunc
)listreviter_next
, /* tp_iternext */
2982 listreviter_methods
, /* tp_methods */
2987 list_reversed(PyListObject
*seq
, PyObject
*unused
)
2989 listreviterobject
*it
;
2991 it
= PyObject_GC_New(listreviterobject
, &PyListRevIter_Type
);
2994 assert(PyList_Check(seq
));
2995 it
->it_index
= PyList_GET_SIZE(seq
) - 1;
2998 PyObject_GC_Track(it
);
2999 return (PyObject
*)it
;
3003 listreviter_dealloc(listreviterobject
*it
)
3005 PyObject_GC_UnTrack(it
);
3006 Py_XDECREF(it
->it_seq
);
3007 PyObject_GC_Del(it
);
3011 listreviter_traverse(listreviterobject
*it
, visitproc visit
, void *arg
)
3013 Py_VISIT(it
->it_seq
);
3018 listreviter_next(listreviterobject
*it
)
3021 Py_ssize_t index
= it
->it_index
;
3022 PyListObject
*seq
= it
->it_seq
;
3024 if (index
>=0 && index
< PyList_GET_SIZE(seq
)) {
3025 item
= PyList_GET_ITEM(seq
, index
);
3039 listreviter_len(listreviterobject
*it
)
3041 Py_ssize_t len
= it
->it_index
+ 1;
3042 if (it
->it_seq
== NULL
|| PyList_GET_SIZE(it
->it_seq
) < len
)
3044 return PyLong_FromSsize_t(len
);