blob: ae8721e653bf2bb941948234a80272ed29a80b5c [file] [log] [blame]
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001/* List object implementation */
2
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003#include "Python.h"
4
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00005#ifdef STDC_HEADERS
6#include <stddef.h>
7#else
8#include <sys/types.h> /* For size_t */
9#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000010
Tim Peters8d9eb102004-07-31 02:24:20 +000011/* 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.
23 */
Guido van Rossuma46d51d1995-01-26 22:59:43 +000024static int
Martin v. Löwis18e16552006-02-15 17:27:45 +000025list_resize(PyListObject *self, Py_ssize_t newsize)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000026{
Raymond Hettinger4bb95402004-02-13 11:36:39 +000027 PyObject **items;
Raymond Hettingera84f3ab2004-09-12 19:53:07 +000028 size_t new_allocated;
Martin v. Löwis18e16552006-02-15 17:27:45 +000029 Py_ssize_t allocated = self->allocated;
Tim Peters65b8b842001-05-26 05:28:40 +000030
Raymond Hettinger4bb95402004-02-13 11:36:39 +000031 /* Bypass realloc() when a previous overallocation is large enough
Raymond Hettingera84f3ab2004-09-12 19:53:07 +000032 to accommodate the newsize. If the newsize falls lower than half
33 the allocated size, then proceed with the realloc() to shrink the list.
Raymond Hettinger4bb95402004-02-13 11:36:39 +000034 */
Raymond Hettingera84f3ab2004-09-12 19:53:07 +000035 if (allocated >= newsize && newsize >= (allocated >> 1)) {
Raymond Hettingerc0aaa2d2004-07-29 23:31:29 +000036 assert(self->ob_item != NULL || newsize == 0);
Christian Heimes90aa7642007-12-19 02:45:37 +000037 Py_SIZE(self) = newsize;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000038 return 0;
39 }
40
41 /* This over-allocates proportional to the list size, making room
Tim Peters65b8b842001-05-26 05:28:40 +000042 * 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
Raymond Hettingerab517d22004-02-14 18:34:46 +000045 * system realloc().
46 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
Tim Peters65b8b842001-05-26 05:28:40 +000047 */
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +000048 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
49
50 /* check for integer overflow */
51 if (new_allocated > PY_SIZE_MAX - newsize) {
52 PyErr_NoMemory();
53 return -1;
54 } else {
55 new_allocated += newsize;
56 }
57
Raymond Hettingera84f3ab2004-09-12 19:53:07 +000058 if (newsize == 0)
59 new_allocated = 0;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000060 items = self->ob_item;
Raymond Hettingera84f3ab2004-09-12 19:53:07 +000061 if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))
62 PyMem_RESIZE(items, PyObject *, new_allocated);
Raymond Hettinger4bb95402004-02-13 11:36:39 +000063 else
64 items = NULL;
65 if (items == NULL) {
66 PyErr_NoMemory();
67 return -1;
68 }
69 self->ob_item = items;
Christian Heimes90aa7642007-12-19 02:45:37 +000070 Py_SIZE(self) = newsize;
Raymond Hettingera84f3ab2004-09-12 19:53:07 +000071 self->allocated = new_allocated;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000072 return 0;
73}
Guido van Rossuma46d51d1995-01-26 22:59:43 +000074
Christian Heimes77c02eb2008-02-09 02:18:51 +000075/* Debug statistic to compare allocations with reuse through the free list */
76#undef SHOW_ALLOC_COUNT
77#ifdef SHOW_ALLOC_COUNT
78static size_t count_alloc = 0;
79static size_t count_reuse = 0;
80
81static void
82show_alloc(void)
83{
Christian Heimes23daade02008-02-25 12:39:23 +000084 fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",
85 count_alloc);
86 fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T
87 "d\n", count_reuse);
Christian Heimes77c02eb2008-02-09 02:18:51 +000088 fprintf(stderr, "%.2f%% reuse rate\n\n",
89 (100.0*count_reuse/(count_alloc+count_reuse)));
90}
91#endif
92
Raymond Hettinger0468e412004-05-05 05:37:53 +000093/* Empty list reuse scheme to save calls to malloc and free */
Christian Heimes2202f872008-02-06 14:31:34 +000094#ifndef PyList_MAXFREELIST
95#define PyList_MAXFREELIST 80
96#endif
97static PyListObject *free_list[PyList_MAXFREELIST];
98static int numfree = 0;
Raymond Hettinger0468e412004-05-05 05:37:53 +000099
Raymond Hettingerfb09f0e2004-10-07 03:58:07 +0000100void
101PyList_Fini(void)
102{
103 PyListObject *op;
104
Christian Heimes2202f872008-02-06 14:31:34 +0000105 while (numfree) {
Christian Heimes77c02eb2008-02-09 02:18:51 +0000106 op = free_list[--numfree];
Raymond Hettingerfb09f0e2004-10-07 03:58:07 +0000107 assert(PyList_CheckExact(op));
108 PyObject_GC_Del(op);
109 }
110}
111
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000112PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000113PyList_New(Py_ssize_t size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000114{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000115 PyListObject *op;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000116 size_t nbytes;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000117#ifdef SHOW_ALLOC_COUNT
118 static int initialized = 0;
119 if (!initialized) {
120 Py_AtExit(show_alloc);
121 initialized = 1;
122 }
123#endif
Tim Peters3986d4e2004-07-29 02:28:42 +0000124
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000125 if (size < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000126 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000127 return NULL;
128 }
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +0000129 /* Check for overflow without an actual overflow,
130 * which can cause compiler to optimise out */
Mark Dickinson66f575b2010-02-14 12:53:32 +0000131 if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000132 return PyErr_NoMemory();
Mark Dickinson66f575b2010-02-14 12:53:32 +0000133 nbytes = size * sizeof(PyObject *);
Christian Heimes2202f872008-02-06 14:31:34 +0000134 if (numfree) {
135 numfree--;
136 op = free_list[numfree];
Raymond Hettinger0468e412004-05-05 05:37:53 +0000137 _Py_NewReference((PyObject *)op);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000138#ifdef SHOW_ALLOC_COUNT
139 count_reuse++;
140#endif
Raymond Hettinger0468e412004-05-05 05:37:53 +0000141 } else {
142 op = PyObject_GC_New(PyListObject, &PyList_Type);
143 if (op == NULL)
144 return NULL;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000145#ifdef SHOW_ALLOC_COUNT
146 count_alloc++;
147#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000148 }
Raymond Hettingerfdfe6182004-05-05 06:28:16 +0000149 if (size <= 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000150 op->ob_item = NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000151 else {
Guido van Rossumb18618d2000-05-03 23:44:39 +0000152 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000153 if (op->ob_item == NULL) {
154 Py_DECREF(op);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000155 return PyErr_NoMemory();
Thomas Wouters0e3f5912006-08-11 14:57:12 +0000156 }
Tim Peters3986d4e2004-07-29 02:28:42 +0000157 memset(op->ob_item, 0, nbytes);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000158 }
Christian Heimes90aa7642007-12-19 02:45:37 +0000159 Py_SIZE(op) = size;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000160 op->allocated = size;
Neil Schemenauere83c00e2001-08-29 23:54:21 +0000161 _PyObject_GC_TRACK(op);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000162 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000163}
164
Martin v. Löwis18e16552006-02-15 17:27:45 +0000165Py_ssize_t
Fred Drakea2f55112000-07-09 15:16:51 +0000166PyList_Size(PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000167{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000168 if (!PyList_Check(op)) {
169 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000170 return -1;
171 }
172 else
Christian Heimes90aa7642007-12-19 02:45:37 +0000173 return Py_SIZE(op);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000174}
175
Raymond Hettingerfdfe6182004-05-05 06:28:16 +0000176static PyObject *indexerr = NULL;
Guido van Rossum929f1b81996-08-09 20:51:27 +0000177
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000178PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000179PyList_GetItem(PyObject *op, Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000180{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000181 if (!PyList_Check(op)) {
182 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000183 return NULL;
184 }
Christian Heimes90aa7642007-12-19 02:45:37 +0000185 if (i < 0 || i >= Py_SIZE(op)) {
Benjamin Petersona0dfa822009-11-13 02:25:08 +0000186 if (indexerr == NULL) {
Neal Norwitz53cbdaa2007-08-23 21:42:55 +0000187 indexerr = PyUnicode_FromString(
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000188 "list index out of range");
Benjamin Petersona0dfa822009-11-13 02:25:08 +0000189 if (indexerr == NULL)
190 return NULL;
191 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000192 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000193 return NULL;
194 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000195 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000196}
197
198int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000199PyList_SetItem(register PyObject *op, register Py_ssize_t i,
Fred Drakea2f55112000-07-09 15:16:51 +0000200 register PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000201{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000202 register PyObject *olditem;
203 register PyObject **p;
204 if (!PyList_Check(op)) {
205 Py_XDECREF(newitem);
206 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000207 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000208 }
Christian Heimes90aa7642007-12-19 02:45:37 +0000209 if (i < 0 || i >= Py_SIZE(op)) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000210 Py_XDECREF(newitem);
211 PyErr_SetString(PyExc_IndexError,
212 "list assignment index out of range");
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000213 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000214 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000215 p = ((PyListObject *)op) -> ob_item + i;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000216 olditem = *p;
217 *p = newitem;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000218 Py_XDECREF(olditem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000219 return 0;
220}
221
222static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000223ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000224{
Christian Heimes90aa7642007-12-19 02:45:37 +0000225 Py_ssize_t i, n = Py_SIZE(self);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000226 PyObject **items;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000227 if (v == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000228 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000229 return -1;
230 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000231 if (n == PY_SSIZE_T_MAX) {
Trent Micka5846642000-08-13 22:47:45 +0000232 PyErr_SetString(PyExc_OverflowError,
233 "cannot add more objects to list");
234 return -1;
235 }
Tim Petersb38e2b62004-07-29 02:29:26 +0000236
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000237 if (list_resize(self, n+1) == -1)
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000238 return -1;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000239
Guido van Rossum3a3cca52003-04-14 20:58:14 +0000240 if (where < 0) {
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000241 where += n;
Guido van Rossum3a3cca52003-04-14 20:58:14 +0000242 if (where < 0)
243 where = 0;
244 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000245 if (where > n)
246 where = n;
247 items = self->ob_item;
248 for (i = n; --i >= where; )
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000249 items[i+1] = items[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000250 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000251 items[where] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000252 return 0;
253}
254
255int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000256PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000257{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000258 if (!PyList_Check(op)) {
259 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000260 return -1;
261 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000262 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000263}
264
Raymond Hettinger40a03822004-04-12 13:05:09 +0000265static int
266app1(PyListObject *self, PyObject *v)
267{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000268 Py_ssize_t n = PyList_GET_SIZE(self);
Raymond Hettinger40a03822004-04-12 13:05:09 +0000269
270 assert (v != NULL);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000271 if (n == PY_SSIZE_T_MAX) {
Raymond Hettinger40a03822004-04-12 13:05:09 +0000272 PyErr_SetString(PyExc_OverflowError,
273 "cannot add more objects to list");
274 return -1;
275 }
276
277 if (list_resize(self, n+1) == -1)
278 return -1;
279
280 Py_INCREF(v);
281 PyList_SET_ITEM(self, n, v);
282 return 0;
283}
284
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000285int
Fred Drakea2f55112000-07-09 15:16:51 +0000286PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000287{
Raymond Hettingerfdfe6182004-05-05 06:28:16 +0000288 if (PyList_Check(op) && (newitem != NULL))
289 return app1((PyListObject *)op, newitem);
290 PyErr_BadInternalCall();
291 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000292}
293
294/* Methods */
295
296static void
Fred Drakea2f55112000-07-09 15:16:51 +0000297list_dealloc(PyListObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000298{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000299 Py_ssize_t i;
Guido van Rossumff413af2002-03-28 20:34:59 +0000300 PyObject_GC_UnTrack(op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000301 Py_TRASHCAN_SAFE_BEGIN(op)
Jack Jansen7874d1f1995-01-19 12:09:27 +0000302 if (op->ob_item != NULL) {
Guido van Rossumfa717011999-06-09 15:19:34 +0000303 /* 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. */
Christian Heimes90aa7642007-12-19 02:45:37 +0000307 i = Py_SIZE(op);
Guido van Rossumfa717011999-06-09 15:19:34 +0000308 while (--i >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000309 Py_XDECREF(op->ob_item[i]);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000310 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000311 PyMem_FREE(op->ob_item);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000312 }
Christian Heimes2202f872008-02-06 14:31:34 +0000313 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
314 free_list[numfree++] = op;
Tim Petersb38e2b62004-07-29 02:29:26 +0000315 else
Christian Heimes90aa7642007-12-19 02:45:37 +0000316 Py_TYPE(op)->tp_free((PyObject *)op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000317 Py_TRASHCAN_SAFE_END(op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000318}
319
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000320static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000321list_repr(PyListObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000322{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000323 Py_ssize_t i;
Tim Petersa7259592001-06-16 05:11:17 +0000324 PyObject *s, *temp;
325 PyObject *pieces = NULL, *result = NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000326
327 i = Py_ReprEnter((PyObject*)v);
328 if (i != 0) {
Walter Dörwald1ab83302007-05-18 17:15:44 +0000329 return i > 0 ? PyUnicode_FromString("[...]") : NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000330 }
Tim Petersa7259592001-06-16 05:11:17 +0000331
Christian Heimes90aa7642007-12-19 02:45:37 +0000332 if (Py_SIZE(v) == 0) {
Walter Dörwald1ab83302007-05-18 17:15:44 +0000333 result = PyUnicode_FromString("[]");
Tim Petersa7259592001-06-16 05:11:17 +0000334 goto Done;
335 }
336
337 pieces = PyList_New(0);
338 if (pieces == NULL)
339 goto Done;
340
341 /* Do repr() on each element. Note that this may mutate the list,
342 so must refetch the list size on each iteration. */
Christian Heimes90aa7642007-12-19 02:45:37 +0000343 for (i = 0; i < Py_SIZE(v); ++i) {
Tim Petersa7259592001-06-16 05:11:17 +0000344 int status;
Thomas Wouters1b7f8912007-09-19 03:06:30 +0000345 if (Py_EnterRecursiveCall(" while getting the repr of a list"))
346 goto Done;
Tim Petersa7259592001-06-16 05:11:17 +0000347 s = PyObject_Repr(v->ob_item[i]);
Thomas Wouters1b7f8912007-09-19 03:06:30 +0000348 Py_LeaveRecursiveCall();
Tim Petersa7259592001-06-16 05:11:17 +0000349 if (s == NULL)
350 goto Done;
351 status = PyList_Append(pieces, s);
352 Py_DECREF(s); /* append created a new ref */
353 if (status < 0)
354 goto Done;
355 }
356
357 /* Add "[]" decorations to the first and last items. */
358 assert(PyList_GET_SIZE(pieces) > 0);
Walter Dörwald1ab83302007-05-18 17:15:44 +0000359 s = PyUnicode_FromString("[");
Tim Petersa7259592001-06-16 05:11:17 +0000360 if (s == NULL)
361 goto Done;
362 temp = PyList_GET_ITEM(pieces, 0);
Walter Dörwald1ab83302007-05-18 17:15:44 +0000363 PyUnicode_AppendAndDel(&s, temp);
Tim Petersa7259592001-06-16 05:11:17 +0000364 PyList_SET_ITEM(pieces, 0, s);
365 if (s == NULL)
366 goto Done;
367
Walter Dörwald1ab83302007-05-18 17:15:44 +0000368 s = PyUnicode_FromString("]");
Tim Petersa7259592001-06-16 05:11:17 +0000369 if (s == NULL)
370 goto Done;
371 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
Walter Dörwald1ab83302007-05-18 17:15:44 +0000372 PyUnicode_AppendAndDel(&temp, s);
Tim Petersa7259592001-06-16 05:11:17 +0000373 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
374 if (temp == NULL)
375 goto Done;
376
377 /* Paste them all together with ", " between. */
Walter Dörwald1ab83302007-05-18 17:15:44 +0000378 s = PyUnicode_FromString(", ");
Tim Petersa7259592001-06-16 05:11:17 +0000379 if (s == NULL)
380 goto Done;
Walter Dörwald1ab83302007-05-18 17:15:44 +0000381 result = PyUnicode_Join(s, pieces);
Tim Peters3b01a122002-07-19 02:35:45 +0000382 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +0000383
384Done:
385 Py_XDECREF(pieces);
Guido van Rossumfb376de1998-04-10 22:47:27 +0000386 Py_ReprLeave((PyObject *)v);
Tim Petersa7259592001-06-16 05:11:17 +0000387 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000388}
389
Martin v. Löwis18e16552006-02-15 17:27:45 +0000390static Py_ssize_t
Fred Drakea2f55112000-07-09 15:16:51 +0000391list_length(PyListObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000392{
Christian Heimes90aa7642007-12-19 02:45:37 +0000393 return Py_SIZE(a);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000394}
395
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000396static int
Fred Drakea2f55112000-07-09 15:16:51 +0000397list_contains(PyListObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000398{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000399 Py_ssize_t i;
400 int cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000401
Christian Heimes90aa7642007-12-19 02:45:37 +0000402 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
Raymond Hettingeraae59992002-09-05 14:23:49 +0000403 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000404 Py_EQ);
Neal Norwitzbb9c5f52002-09-05 21:32:55 +0000405 return cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000406}
407
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000408static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000409list_item(PyListObject *a, Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000410{
Christian Heimes90aa7642007-12-19 02:45:37 +0000411 if (i < 0 || i >= Py_SIZE(a)) {
Benjamin Petersona0dfa822009-11-13 02:25:08 +0000412 if (indexerr == NULL) {
Neal Norwitz53cbdaa2007-08-23 21:42:55 +0000413 indexerr = PyUnicode_FromString(
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000414 "list index out of range");
Benjamin Petersona0dfa822009-11-13 02:25:08 +0000415 if (indexerr == NULL)
416 return NULL;
417 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000418 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000419 return NULL;
420 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000421 Py_INCREF(a->ob_item[i]);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000422 return a->ob_item[i];
423}
424
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000425static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000426list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000427{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000428 PyListObject *np;
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000429 PyObject **src, **dest;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000430 Py_ssize_t i, len;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000431 if (ilow < 0)
432 ilow = 0;
Christian Heimes90aa7642007-12-19 02:45:37 +0000433 else if (ilow > Py_SIZE(a))
434 ilow = Py_SIZE(a);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000435 if (ihigh < ilow)
436 ihigh = ilow;
Christian Heimes90aa7642007-12-19 02:45:37 +0000437 else if (ihigh > Py_SIZE(a))
438 ihigh = Py_SIZE(a);
Raymond Hettinger99842b62004-03-08 05:56:15 +0000439 len = ihigh - ilow;
440 np = (PyListObject *) PyList_New(len);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000441 if (np == NULL)
442 return NULL;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000443
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000444 src = a->ob_item + ilow;
445 dest = np->ob_item;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000446 for (i = 0; i < len; i++) {
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000447 PyObject *v = src[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000448 Py_INCREF(v);
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000449 dest[i] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000450 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000451 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000452}
453
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000454PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000455PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum234f9421993-06-17 12:35:49 +0000456{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000457 if (!PyList_Check(a)) {
458 PyErr_BadInternalCall();
Guido van Rossum234f9421993-06-17 12:35:49 +0000459 return NULL;
460 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000461 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000462}
463
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000464static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000465list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000466{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000467 Py_ssize_t size;
468 Py_ssize_t i;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000469 PyObject **src, **dest;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000470 PyListObject *np;
471 if (!PyList_Check(bb)) {
Fred Drakeb6a9ada2000-06-01 03:12:13 +0000472 PyErr_Format(PyExc_TypeError,
Fred Drake914a2ed2000-06-01 14:31:03 +0000473 "can only concatenate list (not \"%.200s\") to list",
474 bb->ob_type->tp_name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000475 return NULL;
476 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000477#define b ((PyListObject *)bb)
Christian Heimes90aa7642007-12-19 02:45:37 +0000478 size = Py_SIZE(a) + Py_SIZE(b);
Guido van Rossuma5c0e6d2002-10-11 21:05:56 +0000479 if (size < 0)
480 return PyErr_NoMemory();
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000481 np = (PyListObject *) PyList_New(size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000482 if (np == NULL) {
Guido van Rossum90933611991-06-07 16:10:43 +0000483 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000484 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000485 src = a->ob_item;
486 dest = np->ob_item;
Christian Heimes90aa7642007-12-19 02:45:37 +0000487 for (i = 0; i < Py_SIZE(a); i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000488 PyObject *v = src[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000489 Py_INCREF(v);
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000490 dest[i] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000491 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000492 src = b->ob_item;
Christian Heimes90aa7642007-12-19 02:45:37 +0000493 dest = np->ob_item + Py_SIZE(a);
494 for (i = 0; i < Py_SIZE(b); i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000495 PyObject *v = src[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000496 Py_INCREF(v);
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000497 dest[i] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000498 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000499 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000500#undef b
501}
502
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000503static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000504list_repeat(PyListObject *a, Py_ssize_t n)
Guido van Rossumed98d481991-03-06 13:07:53 +0000505{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000506 Py_ssize_t i, j;
507 Py_ssize_t size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000508 PyListObject *np;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000509 PyObject **p, **items;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000510 PyObject *elem;
Guido van Rossumed98d481991-03-06 13:07:53 +0000511 if (n < 0)
512 n = 0;
Christian Heimes90aa7642007-12-19 02:45:37 +0000513 size = Py_SIZE(a) * n;
514 if (n && size/n != Py_SIZE(a))
Guido van Rossuma5c0e6d2002-10-11 21:05:56 +0000515 return PyErr_NoMemory();
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000516 if (size == 0)
Christian Heimesaf98da12008-01-27 15:18:18 +0000517 return PyList_New(0);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000518 np = (PyListObject *) PyList_New(size);
Guido van Rossumed98d481991-03-06 13:07:53 +0000519 if (np == NULL)
520 return NULL;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000521
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000522 items = np->ob_item;
Christian Heimes90aa7642007-12-19 02:45:37 +0000523 if (Py_SIZE(a) == 1) {
Raymond Hettinger6624e682003-05-21 05:58:46 +0000524 elem = a->ob_item[0];
525 for (i = 0; i < n; i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000526 items[i] = elem;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000527 Py_INCREF(elem);
528 }
529 return (PyObject *) np;
530 }
Guido van Rossumed98d481991-03-06 13:07:53 +0000531 p = np->ob_item;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000532 items = a->ob_item;
Guido van Rossumed98d481991-03-06 13:07:53 +0000533 for (i = 0; i < n; i++) {
Christian Heimes90aa7642007-12-19 02:45:37 +0000534 for (j = 0; j < Py_SIZE(a); j++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000535 *p = items[j];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000536 Py_INCREF(*p);
Guido van Rossumed98d481991-03-06 13:07:53 +0000537 p++;
538 }
539 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000540 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000541}
542
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000543static int
Armin Rigo93677f02004-07-29 12:40:23 +0000544list_clear(PyListObject *a)
545{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000546 Py_ssize_t i;
Armin Rigo93677f02004-07-29 12:40:23 +0000547 PyObject **item = a->ob_item;
548 if (item != NULL) {
549 /* Because XDECREF can recursively invoke operations on
550 this list, we make it empty first. */
Christian Heimes90aa7642007-12-19 02:45:37 +0000551 i = Py_SIZE(a);
552 Py_SIZE(a) = 0;
Armin Rigo93677f02004-07-29 12:40:23 +0000553 a->ob_item = NULL;
554 a->allocated = 0;
555 while (--i >= 0) {
556 Py_XDECREF(item[i]);
557 }
558 PyMem_FREE(item);
559 }
560 /* Never fails; the return value can be ignored.
561 Note that there is no guarantee that the list is actually empty
562 at this point, because XDECREF may have populated it again! */
563 return 0;
564}
565
Tim Peters8fc4a912004-07-31 21:53:19 +0000566/* a[ilow:ihigh] = v if v != NULL.
567 * del a[ilow:ihigh] if v == NULL.
568 *
569 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
570 * guaranteed the call cannot fail.
571 */
Armin Rigo93677f02004-07-29 12:40:23 +0000572static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000573list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000574{
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000575 /* Because [X]DECREF can recursively invoke list operations on
576 this list, we must postpone all [X]DECREF activity until
577 after the list is back in its canonical shape. Therefore
578 we must allocate an additional array, 'recycle', into which
579 we temporarily copy the items that are deleted from the
580 list. :-( */
Tim Peters73572222004-07-31 02:54:42 +0000581 PyObject *recycle_on_stack[8];
582 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000583 PyObject **item;
Raymond Hettingerf889e102004-03-09 08:04:33 +0000584 PyObject **vitem = NULL;
Michael W. Hudson5da854f2002-11-05 17:38:05 +0000585 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
Martin v. Löwis18e16552006-02-15 17:27:45 +0000586 Py_ssize_t n; /* # of elements in replacement list */
587 Py_ssize_t norig; /* # of elements in list getting replaced */
588 Py_ssize_t d; /* Change in size */
589 Py_ssize_t k;
Tim Peters8d9eb102004-07-31 02:24:20 +0000590 size_t s;
591 int result = -1; /* guilty until proved innocent */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000592#define b ((PyListObject *)v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000593 if (v == NULL)
594 n = 0;
Michael W. Hudson5da854f2002-11-05 17:38:05 +0000595 else {
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000596 if (a == b) {
597 /* Special case "a[i:j] = a" -- copy b first */
Christian Heimes90aa7642007-12-19 02:45:37 +0000598 v = list_slice(b, 0, Py_SIZE(b));
Martin v. Löwiscd12bfc2003-05-03 10:53:08 +0000599 if (v == NULL)
Tim Peters8d9eb102004-07-31 02:24:20 +0000600 return result;
601 result = list_ass_slice(a, ilow, ihigh, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000602 Py_DECREF(v);
Tim Peters8d9eb102004-07-31 02:24:20 +0000603 return result;
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000604 }
Raymond Hettingerf889e102004-03-09 08:04:33 +0000605 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
Michael W. Hudsonb4f49382003-08-14 17:04:28 +0000606 if(v_as_SF == NULL)
Tim Peters8d9eb102004-07-31 02:24:20 +0000607 goto Error;
Michael W. Hudsonb4f49382003-08-14 17:04:28 +0000608 n = PySequence_Fast_GET_SIZE(v_as_SF);
Raymond Hettinger42bec932004-03-12 16:38:17 +0000609 vitem = PySequence_Fast_ITEMS(v_as_SF);
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000610 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000611 if (ilow < 0)
612 ilow = 0;
Christian Heimes90aa7642007-12-19 02:45:37 +0000613 else if (ilow > Py_SIZE(a))
614 ilow = Py_SIZE(a);
Tim Peters8d9eb102004-07-31 02:24:20 +0000615
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000616 if (ihigh < ilow)
617 ihigh = ilow;
Christian Heimes90aa7642007-12-19 02:45:37 +0000618 else if (ihigh > Py_SIZE(a))
619 ihigh = Py_SIZE(a);
Armin Rigo93677f02004-07-29 12:40:23 +0000620
Tim Peters8d9eb102004-07-31 02:24:20 +0000621 norig = ihigh - ilow;
622 assert(norig >= 0);
623 d = n - norig;
Christian Heimes90aa7642007-12-19 02:45:37 +0000624 if (Py_SIZE(a) + d == 0) {
Armin Rigo93677f02004-07-29 12:40:23 +0000625 Py_XDECREF(v_as_SF);
626 return list_clear(a);
627 }
628 item = a->ob_item;
Tim Peters8d9eb102004-07-31 02:24:20 +0000629 /* recycle the items that we are about to remove */
630 s = norig * sizeof(PyObject *);
Tim Peters73572222004-07-31 02:54:42 +0000631 if (s > sizeof(recycle_on_stack)) {
Armin Rigo1dd04a02004-07-30 11:38:22 +0000632 recycle = (PyObject **)PyMem_MALLOC(s);
Martin v. Löwiscd12bfc2003-05-03 10:53:08 +0000633 if (recycle == NULL) {
634 PyErr_NoMemory();
Tim Peters8d9eb102004-07-31 02:24:20 +0000635 goto Error;
Martin v. Löwiscd12bfc2003-05-03 10:53:08 +0000636 }
637 }
Armin Rigo1dd04a02004-07-30 11:38:22 +0000638 memcpy(recycle, &item[ilow], s);
Tim Peters8d9eb102004-07-31 02:24:20 +0000639
Armin Rigo1dd04a02004-07-30 11:38:22 +0000640 if (d < 0) { /* Delete -d items */
641 memmove(&item[ihigh+d], &item[ihigh],
Christian Heimes90aa7642007-12-19 02:45:37 +0000642 (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
643 list_resize(a, Py_SIZE(a) + d);
Armin Rigo1dd04a02004-07-30 11:38:22 +0000644 item = a->ob_item;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000645 }
Armin Rigo1dd04a02004-07-30 11:38:22 +0000646 else if (d > 0) { /* Insert d items */
Christian Heimes90aa7642007-12-19 02:45:37 +0000647 k = Py_SIZE(a);
Tim Peters73572222004-07-31 02:54:42 +0000648 if (list_resize(a, k+d) < 0)
Tim Peters8d9eb102004-07-31 02:24:20 +0000649 goto Error;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000650 item = a->ob_item;
Raymond Hettingerf889e102004-03-09 08:04:33 +0000651 memmove(&item[ihigh+d], &item[ihigh],
Tim Peters73572222004-07-31 02:54:42 +0000652 (k - ihigh)*sizeof(PyObject *));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000653 }
654 for (k = 0; k < n; k++, ilow++) {
Raymond Hettingerf889e102004-03-09 08:04:33 +0000655 PyObject *w = vitem[k];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000656 Py_XINCREF(w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000657 item[ilow] = w;
658 }
Tim Peters73572222004-07-31 02:54:42 +0000659 for (k = norig - 1; k >= 0; --k)
660 Py_XDECREF(recycle[k]);
Tim Peters8d9eb102004-07-31 02:24:20 +0000661 result = 0;
662 Error:
Tim Peters73572222004-07-31 02:54:42 +0000663 if (recycle != recycle_on_stack)
Armin Rigo1dd04a02004-07-30 11:38:22 +0000664 PyMem_FREE(recycle);
Michael W. Hudson5da854f2002-11-05 17:38:05 +0000665 Py_XDECREF(v_as_SF);
Tim Peters8d9eb102004-07-31 02:24:20 +0000666 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000667#undef b
668}
669
Guido van Rossum234f9421993-06-17 12:35:49 +0000670int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000671PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum234f9421993-06-17 12:35:49 +0000672{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000673 if (!PyList_Check(a)) {
674 PyErr_BadInternalCall();
Guido van Rossum1fc238a1993-07-29 08:25:09 +0000675 return -1;
Guido van Rossum234f9421993-06-17 12:35:49 +0000676 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000677 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000678}
679
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000680static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000681list_inplace_repeat(PyListObject *self, Py_ssize_t n)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000682{
683 PyObject **items;
Christian Heimesaf98da12008-01-27 15:18:18 +0000684 Py_ssize_t size, i, j, p;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000685
686
687 size = PyList_GET_SIZE(self);
Christian Heimesaf98da12008-01-27 15:18:18 +0000688 if (size == 0 || n == 1) {
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000689 Py_INCREF(self);
690 return (PyObject *)self;
691 }
692
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000693 if (n < 1) {
Armin Rigo93677f02004-07-29 12:40:23 +0000694 (void)list_clear(self);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000695 Py_INCREF(self);
696 return (PyObject *)self;
697 }
698
Christian Heimesaf98da12008-01-27 15:18:18 +0000699 if (size > PY_SSIZE_T_MAX / n) {
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000700 return PyErr_NoMemory();
Christian Heimesaf98da12008-01-27 15:18:18 +0000701 }
702
703 if (list_resize(self, size*n) == -1)
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000704 return NULL;
705
706 p = size;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000707 items = self->ob_item;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000708 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
709 for (j = 0; j < size; j++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000710 PyObject *o = items[j];
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000711 Py_INCREF(o);
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000712 items[p++] = o;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000713 }
714 }
715 Py_INCREF(self);
716 return (PyObject *)self;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000717}
718
Guido van Rossum4a450d01991-04-03 19:05:18 +0000719static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000720list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
Guido van Rossum4a450d01991-04-03 19:05:18 +0000721{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000722 PyObject *old_value;
Christian Heimes90aa7642007-12-19 02:45:37 +0000723 if (i < 0 || i >= Py_SIZE(a)) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000724 PyErr_SetString(PyExc_IndexError,
725 "list assignment index out of range");
Guido van Rossum4a450d01991-04-03 19:05:18 +0000726 return -1;
727 }
728 if (v == NULL)
729 return list_ass_slice(a, i, i+1, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000730 Py_INCREF(v);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000731 old_value = a->ob_item[i];
Guido van Rossum4a450d01991-04-03 19:05:18 +0000732 a->ob_item[i] = v;
Tim Peters3b01a122002-07-19 02:35:45 +0000733 Py_DECREF(old_value);
Guido van Rossum4a450d01991-04-03 19:05:18 +0000734 return 0;
735}
736
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000737static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000738listinsert(PyListObject *self, PyObject *args)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000739{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000740 Py_ssize_t i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000741 PyObject *v;
Martin v. Löwis18e16552006-02-15 17:27:45 +0000742 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000743 return NULL;
Raymond Hettinger45d0b5c2004-04-12 17:21:03 +0000744 if (ins1(self, i, v) == 0)
745 Py_RETURN_NONE;
Raymond Hettinger501f02c2004-04-12 14:01:16 +0000746 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000747}
748
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000749static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000750listappend(PyListObject *self, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000751{
Raymond Hettinger45d0b5c2004-04-12 17:21:03 +0000752 if (app1(self, v) == 0)
753 Py_RETURN_NONE;
Raymond Hettinger501f02c2004-04-12 14:01:16 +0000754 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000755}
756
Barry Warsawdedf6d61998-10-09 16:37:25 +0000757static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000758listextend(PyListObject *self, PyObject *b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000759{
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000760 PyObject *it; /* iter(v) */
Martin v. Löwis18e16552006-02-15 17:27:45 +0000761 Py_ssize_t m; /* size of self */
762 Py_ssize_t n; /* guess for size of b */
763 Py_ssize_t mn; /* m + n */
764 Py_ssize_t i;
Raymond Hettinger57c45422004-03-11 09:48:18 +0000765 PyObject *(*iternext)(PyObject *);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000766
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000767 /* Special cases:
Tim Petersb38e2b62004-07-29 02:29:26 +0000768 1) lists and tuples which can use PySequence_Fast ops
769 2) extending self to self requires making a copy first
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000770 */
771 if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
Armin Rigo70d172d2004-03-20 22:19:23 +0000772 PyObject **src, **dest;
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000773 b = PySequence_Fast(b, "argument must be iterable");
774 if (!b)
775 return NULL;
Armin Rigo70d172d2004-03-20 22:19:23 +0000776 n = PySequence_Fast_GET_SIZE(b);
777 if (n == 0) {
778 /* short circuit when b is empty */
779 Py_DECREF(b);
780 Py_RETURN_NONE;
781 }
Christian Heimes90aa7642007-12-19 02:45:37 +0000782 m = Py_SIZE(self);
Armin Rigo70d172d2004-03-20 22:19:23 +0000783 if (list_resize(self, m + n) == -1) {
784 Py_DECREF(b);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000785 return NULL;
Armin Rigo70d172d2004-03-20 22:19:23 +0000786 }
787 /* note that we may still have self == b here for the
788 * situation a.extend(a), but the following code works
789 * in that case too. Just make sure to resize self
790 * before calling PySequence_Fast_ITEMS.
791 */
792 /* populate the end of self with b's items */
793 src = PySequence_Fast_ITEMS(b);
794 dest = self->ob_item + m;
795 for (i = 0; i < n; i++) {
796 PyObject *o = src[i];
797 Py_INCREF(o);
798 dest[i] = o;
799 }
800 Py_DECREF(b);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000801 Py_RETURN_NONE;
802 }
803
804 it = PyObject_GetIter(b);
805 if (it == NULL)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000806 return NULL;
Raymond Hettinger57c45422004-03-11 09:48:18 +0000807 iternext = *it->ob_type->tp_iternext;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000808
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000809 /* Guess a result list size. */
Christian Heimes255f53b2007-12-08 15:33:56 +0000810 n = _PyObject_LengthHint(b, 8);
Raymond Hettingere8364232009-02-02 22:55:09 +0000811 if (n == -1) {
812 Py_DECREF(it);
813 return NULL;
814 }
Christian Heimes90aa7642007-12-19 02:45:37 +0000815 m = Py_SIZE(self);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000816 mn = m + n;
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000817 if (mn >= m) {
818 /* Make room. */
819 if (list_resize(self, mn) == -1)
820 goto error;
821 /* Make the list sane again. */
Christian Heimes90aa7642007-12-19 02:45:37 +0000822 Py_SIZE(self) = m;
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000823 }
824 /* Else m + n overflowed; on the chance that n lied, and there really
825 * is enough room, ignore it. If n was telling the truth, we'll
826 * eventually run out of memory during the loop.
827 */
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000828
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000829 /* Run iterator to exhaustion. */
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000830 for (;;) {
Raymond Hettinger57c45422004-03-11 09:48:18 +0000831 PyObject *item = iternext(it);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000832 if (item == NULL) {
Raymond Hettinger57c45422004-03-11 09:48:18 +0000833 if (PyErr_Occurred()) {
834 if (PyErr_ExceptionMatches(PyExc_StopIteration))
835 PyErr_Clear();
836 else
837 goto error;
838 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000839 break;
840 }
Christian Heimes90aa7642007-12-19 02:45:37 +0000841 if (Py_SIZE(self) < self->allocated) {
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000842 /* steals ref */
Christian Heimes90aa7642007-12-19 02:45:37 +0000843 PyList_SET_ITEM(self, Py_SIZE(self), item);
844 ++Py_SIZE(self);
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000845 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000846 else {
Raymond Hettinger40a03822004-04-12 13:05:09 +0000847 int status = app1(self, item);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000848 Py_DECREF(item); /* append creates a new ref */
849 if (status < 0)
850 goto error;
851 }
852 }
853
854 /* Cut back result list if initial guess was too large. */
Christian Heimes90aa7642007-12-19 02:45:37 +0000855 if (Py_SIZE(self) < self->allocated)
856 list_resize(self, Py_SIZE(self)); /* shrinking can't fail */
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000857
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000858 Py_DECREF(it);
859 Py_RETURN_NONE;
860
861 error:
862 Py_DECREF(it);
863 return NULL;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000864}
865
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000866PyObject *
867_PyList_Extend(PyListObject *self, PyObject *b)
868{
869 return listextend(self, b);
870}
871
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000872static PyObject *
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000873list_inplace_concat(PyListObject *self, PyObject *other)
874{
875 PyObject *result;
876
877 result = listextend(self, other);
878 if (result == NULL)
879 return result;
880 Py_DECREF(result);
881 Py_INCREF(self);
882 return (PyObject *)self;
883}
884
885static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000886listpop(PyListObject *self, PyObject *args)
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000887{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000888 Py_ssize_t i = -1;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000889 PyObject *v;
Tim Peters8fc4a912004-07-31 21:53:19 +0000890 int status;
Raymond Hettinger9eb86b32004-02-17 11:36:16 +0000891
Thomas Wouters89f507f2006-12-13 04:49:30 +0000892 if (!PyArg_ParseTuple(args, "|n:pop", &i))
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000893 return NULL;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000894
Christian Heimes90aa7642007-12-19 02:45:37 +0000895 if (Py_SIZE(self) == 0) {
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000896 /* Special-case most common failure cause */
897 PyErr_SetString(PyExc_IndexError, "pop from empty list");
898 return NULL;
899 }
900 if (i < 0)
Christian Heimes90aa7642007-12-19 02:45:37 +0000901 i += Py_SIZE(self);
902 if (i < 0 || i >= Py_SIZE(self)) {
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000903 PyErr_SetString(PyExc_IndexError, "pop index out of range");
904 return NULL;
905 }
906 v = self->ob_item[i];
Christian Heimes90aa7642007-12-19 02:45:37 +0000907 if (i == Py_SIZE(self) - 1) {
908 status = list_resize(self, Py_SIZE(self) - 1);
Tim Peters8fc4a912004-07-31 21:53:19 +0000909 assert(status >= 0);
910 return v; /* and v now owns the reference the list had */
Raymond Hettingercb3e5802004-02-13 18:36:31 +0000911 }
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000912 Py_INCREF(v);
Tim Peters8fc4a912004-07-31 21:53:19 +0000913 status = list_ass_slice(self, i, i+1, (PyObject *)NULL);
914 assert(status >= 0);
915 /* Use status, so that in a release build compilers don't
916 * complain about the unused name.
917 */
Brett Cannon651dd522004-08-08 21:21:18 +0000918 (void) status;
919
920 return v;
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000921}
922
Tim Peters8e2e7ca2002-07-19 02:33:08 +0000923/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
924static void
925reverse_slice(PyObject **lo, PyObject **hi)
926{
927 assert(lo && hi);
928
929 --hi;
930 while (lo < hi) {
931 PyObject *t = *lo;
932 *lo = *hi;
933 *hi = t;
934 ++lo;
935 --hi;
936 }
937}
938
Tim Petersa64dc242002-08-01 02:13:36 +0000939/* Lots of code for an adaptive, stable, natural mergesort. There are many
940 * pieces to this algorithm; read listsort.txt for overviews and details.
941 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000942
Raymond Hettinger70b64fc2008-01-30 20:15:17 +0000943/* Comparison function: PyObject_RichCompareBool with Py_LT.
Tim Petersa64dc242002-08-01 02:13:36 +0000944 * Returns -1 on error, 1 if x < y, 0 if x >= y.
945 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000946
Raymond Hettinger70b64fc2008-01-30 20:15:17 +0000947#define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT))
Tim Peters66860f62002-08-04 17:47:26 +0000948
949/* Compare X to Y via "<". Goto "fail" if the comparison raises an
Tim Petersa8c974c2002-07-19 03:30:57 +0000950 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
951 started. It makes more sense in context <wink>. X and Y are PyObject*s.
952*/
Raymond Hettinger70b64fc2008-01-30 20:15:17 +0000953#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \
Tim Petersa8c974c2002-07-19 03:30:57 +0000954 if (k)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000955
956/* binarysort is the best method for sorting small arrays: it does
957 few compares, but can do data movement quadratic in the number of
958 elements.
Guido van Rossum42812581998-06-17 14:15:44 +0000959 [lo, hi) is a contiguous slice of a list, and is sorted via
Tim Petersa8c974c2002-07-19 03:30:57 +0000960 binary insertion. This sort is stable.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000961 On entry, must have lo <= start <= hi, and that [lo, start) is already
962 sorted (pass start == lo if you don't know!).
Tim Petersa8c974c2002-07-19 03:30:57 +0000963 If islt() complains return -1, else 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000964 Even in case of error, the output slice will be some permutation of
965 the input (nothing is lost or duplicated).
966*/
Guido van Rossum3f236de1996-12-10 23:55:39 +0000967static int
Raymond Hettinger70b64fc2008-01-30 20:15:17 +0000968binarysort(PyObject **lo, PyObject **hi, PyObject **start)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000969{
Martin v. Löwis18e16552006-02-15 17:27:45 +0000970 register Py_ssize_t k;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000971 register PyObject **l, **p, **r;
972 register PyObject *pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000973
Tim Petersa8c974c2002-07-19 03:30:57 +0000974 assert(lo <= start && start <= hi);
975 /* assert [lo, start) is sorted */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000976 if (lo == start)
977 ++start;
978 for (; start < hi; ++start) {
979 /* set l to where *start belongs */
980 l = lo;
981 r = start;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000982 pivot = *r;
Tim Peters0fe977c2002-07-19 06:12:32 +0000983 /* Invariants:
984 * pivot >= all in [lo, l).
985 * pivot < all in [r, start).
986 * The second is vacuously true at the start.
987 */
988 assert(l < r);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000989 do {
990 p = l + ((r - l) >> 1);
Tim Petersa8c974c2002-07-19 03:30:57 +0000991 IFLT(pivot, *p)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000992 r = p;
993 else
Tim Peters0fe977c2002-07-19 06:12:32 +0000994 l = p+1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000995 } while (l < r);
Tim Peters0fe977c2002-07-19 06:12:32 +0000996 assert(l == r);
997 /* The invariants still hold, so pivot >= all in [lo, l) and
998 pivot < all in [l, start), so pivot belongs at l. Note
999 that if there are elements equal to pivot, l points to the
1000 first slot after them -- that's why this sort is stable.
1001 Slide over to make room.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001002 Caution: using memmove is much slower under MSVC 5;
1003 we're not usually moving many slots. */
1004 for (p = start; p > l; --p)
1005 *p = *(p-1);
1006 *l = pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001007 }
Guido van Rossum3f236de1996-12-10 23:55:39 +00001008 return 0;
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001009
1010 fail:
1011 return -1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001012}
1013
Tim Petersa64dc242002-08-01 02:13:36 +00001014/*
1015Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1016is required on entry. "A run" is the longest ascending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001017
Tim Petersa64dc242002-08-01 02:13:36 +00001018 lo[0] <= lo[1] <= lo[2] <= ...
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001019
Tim Petersa64dc242002-08-01 02:13:36 +00001020or the longest descending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001021
Tim Petersa64dc242002-08-01 02:13:36 +00001022 lo[0] > lo[1] > lo[2] > ...
Tim Peters3b01a122002-07-19 02:35:45 +00001023
Tim Petersa64dc242002-08-01 02:13:36 +00001024Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1025For its intended use in a stable mergesort, the strictness of the defn of
1026"descending" is needed so that the caller can safely reverse a descending
1027sequence without violating stability (strict > ensures there are no equal
1028elements to get out of order).
1029
1030Returns -1 in case of error.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001031*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001032static Py_ssize_t
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001033count_run(PyObject **lo, PyObject **hi, int *descending)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001034{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001035 Py_ssize_t k;
1036 Py_ssize_t n;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001037
Tim Petersa64dc242002-08-01 02:13:36 +00001038 assert(lo < hi);
1039 *descending = 0;
1040 ++lo;
1041 if (lo == hi)
1042 return 1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001043
Tim Petersa64dc242002-08-01 02:13:36 +00001044 n = 2;
1045 IFLT(*lo, *(lo-1)) {
1046 *descending = 1;
1047 for (lo = lo+1; lo < hi; ++lo, ++n) {
1048 IFLT(*lo, *(lo-1))
1049 ;
1050 else
1051 break;
1052 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001053 }
Tim Petersa64dc242002-08-01 02:13:36 +00001054 else {
1055 for (lo = lo+1; lo < hi; ++lo, ++n) {
1056 IFLT(*lo, *(lo-1))
1057 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001058 }
1059 }
1060
Tim Petersa64dc242002-08-01 02:13:36 +00001061 return n;
1062fail:
1063 return -1;
1064}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001065
Tim Petersa64dc242002-08-01 02:13:36 +00001066/*
1067Locate the proper position of key in a sorted vector; if the vector contains
1068an element equal to key, return the position immediately to the left of
1069the leftmost equal element. [gallop_right() does the same except returns
1070the position to the right of the rightmost equal element (if any).]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001071
Tim Petersa64dc242002-08-01 02:13:36 +00001072"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001073
Tim Petersa64dc242002-08-01 02:13:36 +00001074"hint" is an index at which to begin the search, 0 <= hint < n. The closer
1075hint is to the final result, the faster this runs.
1076
1077The return value is the int k in 0..n such that
1078
1079 a[k-1] < key <= a[k]
1080
1081pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1082key belongs at index k; or, IOW, the first k elements of a should precede
1083key, and the last n-k should follow key.
1084
1085Returns -1 on error. See listsort.txt for info on the method.
1086*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001087static Py_ssize_t
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001088gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
Tim Petersa64dc242002-08-01 02:13:36 +00001089{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001090 Py_ssize_t ofs;
1091 Py_ssize_t lastofs;
1092 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001093
1094 assert(key && a && n > 0 && hint >= 0 && hint < n);
1095
1096 a += hint;
1097 lastofs = 0;
1098 ofs = 1;
1099 IFLT(*a, key) {
1100 /* a[hint] < key -- gallop right, until
1101 * a[hint + lastofs] < key <= a[hint + ofs]
1102 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001103 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
Tim Petersa64dc242002-08-01 02:13:36 +00001104 while (ofs < maxofs) {
1105 IFLT(a[ofs], key) {
1106 lastofs = ofs;
1107 ofs = (ofs << 1) + 1;
1108 if (ofs <= 0) /* int overflow */
1109 ofs = maxofs;
1110 }
1111 else /* key <= a[hint + ofs] */
1112 break;
1113 }
1114 if (ofs > maxofs)
1115 ofs = maxofs;
1116 /* Translate back to offsets relative to &a[0]. */
1117 lastofs += hint;
1118 ofs += hint;
1119 }
1120 else {
1121 /* key <= a[hint] -- gallop left, until
1122 * a[hint - ofs] < key <= a[hint - lastofs]
1123 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001124 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
Tim Petersa64dc242002-08-01 02:13:36 +00001125 while (ofs < maxofs) {
1126 IFLT(*(a-ofs), key)
1127 break;
1128 /* key <= a[hint - ofs] */
1129 lastofs = ofs;
1130 ofs = (ofs << 1) + 1;
1131 if (ofs <= 0) /* int overflow */
1132 ofs = maxofs;
1133 }
1134 if (ofs > maxofs)
1135 ofs = maxofs;
1136 /* Translate back to positive offsets relative to &a[0]. */
1137 k = lastofs;
1138 lastofs = hint - ofs;
1139 ofs = hint - k;
1140 }
1141 a -= hint;
1142
1143 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1144 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1145 * right of lastofs but no farther right than ofs. Do a binary
1146 * search, with invariant a[lastofs-1] < key <= a[ofs].
1147 */
1148 ++lastofs;
1149 while (lastofs < ofs) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001150 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001151
1152 IFLT(a[m], key)
1153 lastofs = m+1; /* a[m] < key */
1154 else
1155 ofs = m; /* key <= a[m] */
1156 }
1157 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1158 return ofs;
1159
1160fail:
1161 return -1;
1162}
1163
1164/*
1165Exactly like gallop_left(), except that if key already exists in a[0:n],
1166finds the position immediately to the right of the rightmost equal value.
1167
1168The return value is the int k in 0..n such that
1169
1170 a[k-1] <= key < a[k]
1171
1172or -1 if error.
1173
1174The code duplication is massive, but this is enough different given that
1175we're sticking to "<" comparisons that it's much harder to follow if
1176written as one routine with yet another "left or right?" flag.
1177*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001178static Py_ssize_t
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001179gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
Tim Petersa64dc242002-08-01 02:13:36 +00001180{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001181 Py_ssize_t ofs;
1182 Py_ssize_t lastofs;
1183 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001184
1185 assert(key && a && n > 0 && hint >= 0 && hint < n);
1186
1187 a += hint;
1188 lastofs = 0;
1189 ofs = 1;
1190 IFLT(key, *a) {
1191 /* key < a[hint] -- gallop left, until
1192 * a[hint - ofs] <= key < a[hint - lastofs]
1193 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001194 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
Tim Petersa64dc242002-08-01 02:13:36 +00001195 while (ofs < maxofs) {
1196 IFLT(key, *(a-ofs)) {
1197 lastofs = ofs;
1198 ofs = (ofs << 1) + 1;
1199 if (ofs <= 0) /* int overflow */
1200 ofs = maxofs;
1201 }
1202 else /* a[hint - ofs] <= key */
1203 break;
1204 }
1205 if (ofs > maxofs)
1206 ofs = maxofs;
1207 /* Translate back to positive offsets relative to &a[0]. */
1208 k = lastofs;
1209 lastofs = hint - ofs;
1210 ofs = hint - k;
1211 }
1212 else {
1213 /* a[hint] <= key -- gallop right, until
1214 * a[hint + lastofs] <= key < a[hint + ofs]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001215 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001216 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
Tim Petersa64dc242002-08-01 02:13:36 +00001217 while (ofs < maxofs) {
1218 IFLT(key, a[ofs])
1219 break;
1220 /* a[hint + ofs] <= key */
1221 lastofs = ofs;
1222 ofs = (ofs << 1) + 1;
1223 if (ofs <= 0) /* int overflow */
1224 ofs = maxofs;
1225 }
1226 if (ofs > maxofs)
1227 ofs = maxofs;
1228 /* Translate back to offsets relative to &a[0]. */
1229 lastofs += hint;
1230 ofs += hint;
1231 }
1232 a -= hint;
1233
1234 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1235 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1236 * right of lastofs but no farther right than ofs. Do a binary
1237 * search, with invariant a[lastofs-1] <= key < a[ofs].
1238 */
1239 ++lastofs;
1240 while (lastofs < ofs) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001241 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001242
1243 IFLT(key, a[m])
1244 ofs = m; /* key < a[m] */
1245 else
1246 lastofs = m+1; /* a[m] <= key */
1247 }
1248 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1249 return ofs;
1250
1251fail:
1252 return -1;
1253}
1254
1255/* The maximum number of entries in a MergeState's pending-runs stack.
1256 * This is enough to sort arrays of size up to about
1257 * 32 * phi ** MAX_MERGE_PENDING
1258 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1259 * with 2**64 elements.
1260 */
1261#define MAX_MERGE_PENDING 85
1262
Tim Peterse05f65a2002-08-10 05:21:15 +00001263/* When we get into galloping mode, we stay there until both runs win less
1264 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
Tim Petersa64dc242002-08-01 02:13:36 +00001265 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001266#define MIN_GALLOP 7
Tim Petersa64dc242002-08-01 02:13:36 +00001267
1268/* Avoid malloc for small temp arrays. */
1269#define MERGESTATE_TEMP_SIZE 256
1270
1271/* One MergeState exists on the stack per invocation of mergesort. It's just
1272 * a convenient way to pass state around among the helper functions.
1273 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001274struct s_slice {
1275 PyObject **base;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001276 Py_ssize_t len;
Tim Peterse05f65a2002-08-10 05:21:15 +00001277};
1278
Tim Petersa64dc242002-08-01 02:13:36 +00001279typedef struct s_MergeState {
Tim Peterse05f65a2002-08-10 05:21:15 +00001280 /* This controls when we get *into* galloping mode. It's initialized
1281 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1282 * random data, and lower for highly structured data.
1283 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001284 Py_ssize_t min_gallop;
Tim Peterse05f65a2002-08-10 05:21:15 +00001285
Tim Petersa64dc242002-08-01 02:13:36 +00001286 /* 'a' is temp storage to help with merges. It contains room for
1287 * alloced entries.
1288 */
1289 PyObject **a; /* may point to temparray below */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001290 Py_ssize_t alloced;
Tim Petersa64dc242002-08-01 02:13:36 +00001291
1292 /* A stack of n pending runs yet to be merged. Run #i starts at
1293 * address base[i] and extends for len[i] elements. It's always
1294 * true (so long as the indices are in bounds) that
1295 *
Tim Peterse05f65a2002-08-10 05:21:15 +00001296 * pending[i].base + pending[i].len == pending[i+1].base
Tim Petersa64dc242002-08-01 02:13:36 +00001297 *
1298 * so we could cut the storage for this, but it's a minor amount,
1299 * and keeping all the info explicit simplifies the code.
1300 */
1301 int n;
Tim Peterse05f65a2002-08-10 05:21:15 +00001302 struct s_slice pending[MAX_MERGE_PENDING];
Tim Petersa64dc242002-08-01 02:13:36 +00001303
1304 /* 'a' points to this when possible, rather than muck with malloc. */
1305 PyObject *temparray[MERGESTATE_TEMP_SIZE];
1306} MergeState;
1307
1308/* Conceptually a MergeState's constructor. */
1309static void
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001310merge_init(MergeState *ms)
Tim Petersa64dc242002-08-01 02:13:36 +00001311{
1312 assert(ms != NULL);
Tim Petersa64dc242002-08-01 02:13:36 +00001313 ms->a = ms->temparray;
1314 ms->alloced = MERGESTATE_TEMP_SIZE;
1315 ms->n = 0;
Tim Peterse05f65a2002-08-10 05:21:15 +00001316 ms->min_gallop = MIN_GALLOP;
Tim Petersa64dc242002-08-01 02:13:36 +00001317}
1318
1319/* Free all the temp memory owned by the MergeState. This must be called
1320 * when you're done with a MergeState, and may be called before then if
1321 * you want to free the temp memory early.
1322 */
1323static void
1324merge_freemem(MergeState *ms)
1325{
1326 assert(ms != NULL);
1327 if (ms->a != ms->temparray)
1328 PyMem_Free(ms->a);
1329 ms->a = ms->temparray;
1330 ms->alloced = MERGESTATE_TEMP_SIZE;
1331}
1332
1333/* Ensure enough temp memory for 'need' array slots is available.
1334 * Returns 0 on success and -1 if the memory can't be gotten.
1335 */
1336static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001337merge_getmem(MergeState *ms, Py_ssize_t need)
Tim Petersa64dc242002-08-01 02:13:36 +00001338{
1339 assert(ms != NULL);
1340 if (need <= ms->alloced)
1341 return 0;
1342 /* Don't realloc! That can cost cycles to copy the old data, but
1343 * we don't care what's in the block.
1344 */
1345 merge_freemem(ms);
Mark Dickinson66f575b2010-02-14 12:53:32 +00001346 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) {
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +00001347 PyErr_NoMemory();
1348 return -1;
1349 }
Tim Petersa64dc242002-08-01 02:13:36 +00001350 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));
1351 if (ms->a) {
1352 ms->alloced = need;
1353 return 0;
1354 }
1355 PyErr_NoMemory();
1356 merge_freemem(ms); /* reset to sane state */
1357 return -1;
1358}
1359#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1360 merge_getmem(MS, NEED))
1361
1362/* Merge the na elements starting at pa with the nb elements starting at pb
1363 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1364 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1365 * merge, and should have na <= nb. See listsort.txt for more info.
1366 * Return 0 if successful, -1 if error.
1367 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001368static Py_ssize_t
1369merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
1370 PyObject **pb, Py_ssize_t nb)
Tim Petersa64dc242002-08-01 02:13:36 +00001371{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001372 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001373 PyObject **dest;
1374 int result = -1; /* guilty until proved innocent */
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00001375 Py_ssize_t min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001376
1377 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1378 if (MERGE_GETMEM(ms, na) < 0)
1379 return -1;
1380 memcpy(ms->a, pa, na * sizeof(PyObject*));
1381 dest = pa;
1382 pa = ms->a;
1383
1384 *dest++ = *pb++;
1385 --nb;
1386 if (nb == 0)
1387 goto Succeed;
1388 if (na == 1)
1389 goto CopyB;
1390
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00001391 min_gallop = ms->min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001392 for (;;) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001393 Py_ssize_t acount = 0; /* # of times A won in a row */
1394 Py_ssize_t bcount = 0; /* # of times B won in a row */
Tim Petersa64dc242002-08-01 02:13:36 +00001395
1396 /* Do the straightforward thing until (if ever) one run
1397 * appears to win consistently.
1398 */
1399 for (;;) {
Tim Peterse05f65a2002-08-10 05:21:15 +00001400 assert(na > 1 && nb > 0);
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001401 k = ISLT(*pb, *pa);
Tim Petersa64dc242002-08-01 02:13:36 +00001402 if (k) {
1403 if (k < 0)
1404 goto Fail;
1405 *dest++ = *pb++;
1406 ++bcount;
1407 acount = 0;
1408 --nb;
1409 if (nb == 0)
1410 goto Succeed;
Tim Peterse05f65a2002-08-10 05:21:15 +00001411 if (bcount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001412 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001413 }
1414 else {
Tim Petersa64dc242002-08-01 02:13:36 +00001415 *dest++ = *pa++;
1416 ++acount;
1417 bcount = 0;
1418 --na;
1419 if (na == 1)
1420 goto CopyB;
Tim Peterse05f65a2002-08-10 05:21:15 +00001421 if (acount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001422 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001423 }
Tim Petersa64dc242002-08-01 02:13:36 +00001424 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001425
Tim Petersa64dc242002-08-01 02:13:36 +00001426 /* One run is winning so consistently that galloping may
1427 * be a huge win. So try that, and continue galloping until
1428 * (if ever) neither run appears to be winning consistently
1429 * anymore.
1430 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001431 ++min_gallop;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001432 do {
Tim Peterse05f65a2002-08-10 05:21:15 +00001433 assert(na > 1 && nb > 0);
1434 min_gallop -= min_gallop > 1;
1435 ms->min_gallop = min_gallop;
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001436 k = gallop_right(*pb, pa, na, 0);
Tim Petersa64dc242002-08-01 02:13:36 +00001437 acount = k;
1438 if (k) {
1439 if (k < 0)
1440 goto Fail;
1441 memcpy(dest, pa, k * sizeof(PyObject *));
1442 dest += k;
1443 pa += k;
1444 na -= k;
1445 if (na == 1)
1446 goto CopyB;
1447 /* na==0 is impossible now if the comparison
1448 * function is consistent, but we can't assume
1449 * that it is.
1450 */
1451 if (na == 0)
1452 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001453 }
Tim Petersa64dc242002-08-01 02:13:36 +00001454 *dest++ = *pb++;
1455 --nb;
1456 if (nb == 0)
1457 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001458
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001459 k = gallop_left(*pa, pb, nb, 0);
Tim Petersa64dc242002-08-01 02:13:36 +00001460 bcount = k;
1461 if (k) {
1462 if (k < 0)
1463 goto Fail;
1464 memmove(dest, pb, k * sizeof(PyObject *));
1465 dest += k;
1466 pb += k;
1467 nb -= k;
1468 if (nb == 0)
1469 goto Succeed;
1470 }
1471 *dest++ = *pa++;
1472 --na;
1473 if (na == 1)
1474 goto CopyB;
1475 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
Tim Peterse05f65a2002-08-10 05:21:15 +00001476 ++min_gallop; /* penalize it for leaving galloping mode */
1477 ms->min_gallop = min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001478 }
1479Succeed:
1480 result = 0;
1481Fail:
1482 if (na)
1483 memcpy(dest, pa, na * sizeof(PyObject*));
1484 return result;
1485CopyB:
1486 assert(na == 1 && nb > 0);
1487 /* The last element of pa belongs at the end of the merge. */
1488 memmove(dest, pb, nb * sizeof(PyObject *));
1489 dest[nb] = *pa;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001490 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001491}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001492
Tim Petersa64dc242002-08-01 02:13:36 +00001493/* Merge the na elements starting at pa with the nb elements starting at pb
1494 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1495 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1496 * merge, and should have na >= nb. See listsort.txt for more info.
1497 * Return 0 if successful, -1 if error.
1498 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001499static Py_ssize_t
1500merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb)
Tim Petersa64dc242002-08-01 02:13:36 +00001501{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001502 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001503 PyObject **dest;
1504 int result = -1; /* guilty until proved innocent */
1505 PyObject **basea;
1506 PyObject **baseb;
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00001507 Py_ssize_t min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001508
1509 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1510 if (MERGE_GETMEM(ms, nb) < 0)
1511 return -1;
1512 dest = pb + nb - 1;
1513 memcpy(ms->a, pb, nb * sizeof(PyObject*));
1514 basea = pa;
1515 baseb = ms->a;
1516 pb = ms->a + nb - 1;
1517 pa += na - 1;
1518
1519 *dest-- = *pa--;
1520 --na;
1521 if (na == 0)
1522 goto Succeed;
1523 if (nb == 1)
1524 goto CopyA;
1525
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00001526 min_gallop = ms->min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001527 for (;;) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001528 Py_ssize_t acount = 0; /* # of times A won in a row */
1529 Py_ssize_t bcount = 0; /* # of times B won in a row */
Tim Petersa64dc242002-08-01 02:13:36 +00001530
1531 /* Do the straightforward thing until (if ever) one run
1532 * appears to win consistently.
1533 */
1534 for (;;) {
Tim Peterse05f65a2002-08-10 05:21:15 +00001535 assert(na > 0 && nb > 1);
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001536 k = ISLT(*pb, *pa);
Tim Petersa64dc242002-08-01 02:13:36 +00001537 if (k) {
1538 if (k < 0)
1539 goto Fail;
1540 *dest-- = *pa--;
1541 ++acount;
1542 bcount = 0;
1543 --na;
1544 if (na == 0)
1545 goto Succeed;
Tim Peterse05f65a2002-08-10 05:21:15 +00001546 if (acount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001547 break;
1548 }
1549 else {
1550 *dest-- = *pb--;
1551 ++bcount;
1552 acount = 0;
1553 --nb;
1554 if (nb == 1)
1555 goto CopyA;
Tim Peterse05f65a2002-08-10 05:21:15 +00001556 if (bcount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001557 break;
1558 }
1559 }
1560
1561 /* One run is winning so consistently that galloping may
1562 * be a huge win. So try that, and continue galloping until
1563 * (if ever) neither run appears to be winning consistently
1564 * anymore.
1565 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001566 ++min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001567 do {
Tim Peterse05f65a2002-08-10 05:21:15 +00001568 assert(na > 0 && nb > 1);
1569 min_gallop -= min_gallop > 1;
1570 ms->min_gallop = min_gallop;
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001571 k = gallop_right(*pb, basea, na, na-1);
Tim Petersa64dc242002-08-01 02:13:36 +00001572 if (k < 0)
1573 goto Fail;
1574 k = na - k;
1575 acount = k;
1576 if (k) {
1577 dest -= k;
1578 pa -= k;
1579 memmove(dest+1, pa+1, k * sizeof(PyObject *));
1580 na -= k;
1581 if (na == 0)
1582 goto Succeed;
1583 }
1584 *dest-- = *pb--;
1585 --nb;
1586 if (nb == 1)
1587 goto CopyA;
1588
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001589 k = gallop_left(*pa, baseb, nb, nb-1);
Tim Petersa64dc242002-08-01 02:13:36 +00001590 if (k < 0)
1591 goto Fail;
1592 k = nb - k;
1593 bcount = k;
1594 if (k) {
1595 dest -= k;
1596 pb -= k;
1597 memcpy(dest+1, pb+1, k * sizeof(PyObject *));
1598 nb -= k;
1599 if (nb == 1)
1600 goto CopyA;
1601 /* nb==0 is impossible now if the comparison
1602 * function is consistent, but we can't assume
1603 * that it is.
1604 */
1605 if (nb == 0)
1606 goto Succeed;
1607 }
1608 *dest-- = *pa--;
1609 --na;
1610 if (na == 0)
1611 goto Succeed;
1612 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
Tim Peterse05f65a2002-08-10 05:21:15 +00001613 ++min_gallop; /* penalize it for leaving galloping mode */
1614 ms->min_gallop = min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001615 }
1616Succeed:
1617 result = 0;
1618Fail:
1619 if (nb)
1620 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
1621 return result;
1622CopyA:
1623 assert(nb == 1 && na > 0);
1624 /* The first element of pb belongs at the front of the merge. */
1625 dest -= na;
1626 pa -= na;
1627 memmove(dest+1, pa+1, na * sizeof(PyObject *));
1628 *dest = *pb;
1629 return 0;
1630}
1631
1632/* Merge the two runs at stack indices i and i+1.
1633 * Returns 0 on success, -1 on error.
1634 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001635static Py_ssize_t
1636merge_at(MergeState *ms, Py_ssize_t i)
Tim Petersa64dc242002-08-01 02:13:36 +00001637{
1638 PyObject **pa, **pb;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001639 Py_ssize_t na, nb;
1640 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001641
1642 assert(ms != NULL);
1643 assert(ms->n >= 2);
1644 assert(i >= 0);
1645 assert(i == ms->n - 2 || i == ms->n - 3);
1646
Tim Peterse05f65a2002-08-10 05:21:15 +00001647 pa = ms->pending[i].base;
1648 na = ms->pending[i].len;
1649 pb = ms->pending[i+1].base;
1650 nb = ms->pending[i+1].len;
Tim Petersa64dc242002-08-01 02:13:36 +00001651 assert(na > 0 && nb > 0);
1652 assert(pa + na == pb);
1653
1654 /* Record the length of the combined runs; if i is the 3rd-last
1655 * run now, also slide over the last run (which isn't involved
1656 * in this merge). The current run i+1 goes away in any case.
1657 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001658 ms->pending[i].len = na + nb;
1659 if (i == ms->n - 3)
1660 ms->pending[i+1] = ms->pending[i+2];
Tim Petersa64dc242002-08-01 02:13:36 +00001661 --ms->n;
1662
1663 /* Where does b start in a? Elements in a before that can be
1664 * ignored (already in place).
1665 */
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001666 k = gallop_right(*pb, pa, na, 0);
Tim Petersa64dc242002-08-01 02:13:36 +00001667 if (k < 0)
1668 return -1;
1669 pa += k;
1670 na -= k;
1671 if (na == 0)
1672 return 0;
1673
1674 /* Where does a end in b? Elements in b after that can be
1675 * ignored (already in place).
1676 */
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001677 nb = gallop_left(pa[na-1], pb, nb, nb-1);
Tim Petersa64dc242002-08-01 02:13:36 +00001678 if (nb <= 0)
1679 return nb;
1680
1681 /* Merge what remains of the runs, using a temp array with
1682 * min(na, nb) elements.
1683 */
1684 if (na <= nb)
1685 return merge_lo(ms, pa, na, pb, nb);
1686 else
1687 return merge_hi(ms, pa, na, pb, nb);
1688}
1689
1690/* Examine the stack of runs waiting to be merged, merging adjacent runs
1691 * until the stack invariants are re-established:
1692 *
1693 * 1. len[-3] > len[-2] + len[-1]
1694 * 2. len[-2] > len[-1]
1695 *
1696 * See listsort.txt for more info.
1697 *
1698 * Returns 0 on success, -1 on error.
1699 */
1700static int
1701merge_collapse(MergeState *ms)
1702{
Tim Peterse05f65a2002-08-10 05:21:15 +00001703 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001704
1705 assert(ms);
1706 while (ms->n > 1) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001707 Py_ssize_t n = ms->n - 2;
Tim Peterse05f65a2002-08-10 05:21:15 +00001708 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
1709 if (p[n-1].len < p[n+1].len)
Tim Petersa64dc242002-08-01 02:13:36 +00001710 --n;
1711 if (merge_at(ms, n) < 0)
1712 return -1;
1713 }
Tim Peterse05f65a2002-08-10 05:21:15 +00001714 else if (p[n].len <= p[n+1].len) {
Tim Petersa64dc242002-08-01 02:13:36 +00001715 if (merge_at(ms, n) < 0)
1716 return -1;
1717 }
1718 else
1719 break;
1720 }
1721 return 0;
1722}
1723
1724/* Regardless of invariants, merge all runs on the stack until only one
1725 * remains. This is used at the end of the mergesort.
1726 *
1727 * Returns 0 on success, -1 on error.
1728 */
1729static int
1730merge_force_collapse(MergeState *ms)
1731{
Tim Peterse05f65a2002-08-10 05:21:15 +00001732 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001733
1734 assert(ms);
1735 while (ms->n > 1) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001736 Py_ssize_t n = ms->n - 2;
Tim Peterse05f65a2002-08-10 05:21:15 +00001737 if (n > 0 && p[n-1].len < p[n+1].len)
Tim Petersa64dc242002-08-01 02:13:36 +00001738 --n;
1739 if (merge_at(ms, n) < 0)
1740 return -1;
1741 }
1742 return 0;
1743}
1744
1745/* Compute a good value for the minimum run length; natural runs shorter
1746 * than this are boosted artificially via binary insertion.
1747 *
1748 * If n < 64, return n (it's too small to bother with fancy stuff).
1749 * Else if n is an exact power of 2, return 32.
1750 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1751 * strictly less than, an exact power of 2.
1752 *
1753 * See listsort.txt for more info.
1754 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001755static Py_ssize_t
1756merge_compute_minrun(Py_ssize_t n)
Tim Petersa64dc242002-08-01 02:13:36 +00001757{
Martin v. Löwis18e16552006-02-15 17:27:45 +00001758 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
Tim Petersa64dc242002-08-01 02:13:36 +00001759
1760 assert(n >= 0);
1761 while (n >= 64) {
1762 r |= n & 1;
1763 n >>= 1;
1764 }
1765 return n + r;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001766}
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001767
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001768/* Special wrapper to support stable sorting using the decorate-sort-undecorate
Andrew M. Kuchling55be9ea2004-09-10 12:59:54 +00001769 pattern. Holds a key which is used for comparisons and the original record
Tim Petersb38e2b62004-07-29 02:29:26 +00001770 which is returned during the undecorate phase. By exposing only the key
1771 during comparisons, the underlying sort stability characteristics are left
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001772 unchanged. Also, the comparison function will only see the key instead of
1773 a full record. */
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001774
1775typedef struct {
1776 PyObject_HEAD
1777 PyObject *key;
1778 PyObject *value;
1779} sortwrapperobject;
1780
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001781PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key.");
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001782static PyObject *
1783sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int);
1784static void
1785sortwrapper_dealloc(sortwrapperobject *);
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001786
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001787PyTypeObject PySortWrapper_Type = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00001788 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001789 "sortwrapper", /* tp_name */
1790 sizeof(sortwrapperobject), /* tp_basicsize */
1791 0, /* tp_itemsize */
1792 /* methods */
1793 (destructor)sortwrapper_dealloc, /* tp_dealloc */
1794 0, /* tp_print */
1795 0, /* tp_getattr */
1796 0, /* tp_setattr */
Mark Dickinsone94c6792009-02-02 20:36:42 +00001797 0, /* tp_reserved */
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001798 0, /* tp_repr */
1799 0, /* tp_as_number */
1800 0, /* tp_as_sequence */
1801 0, /* tp_as_mapping */
1802 0, /* tp_hash */
1803 0, /* tp_call */
1804 0, /* tp_str */
1805 PyObject_GenericGetAttr, /* tp_getattro */
1806 0, /* tp_setattro */
1807 0, /* tp_as_buffer */
Guido van Rossum3cf5b1e2006-07-27 21:53:35 +00001808 Py_TPFLAGS_DEFAULT, /* tp_flags */
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001809 sortwrapper_doc, /* tp_doc */
1810 0, /* tp_traverse */
1811 0, /* tp_clear */
1812 (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */
1813};
1814
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001815
1816static PyObject *
1817sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
1818{
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001819 if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) {
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001820 PyErr_SetString(PyExc_TypeError,
1821 "expected a sortwrapperobject");
1822 return NULL;
1823 }
1824 return PyObject_RichCompare(a->key, b->key, op);
1825}
1826
1827static void
1828sortwrapper_dealloc(sortwrapperobject *so)
1829{
1830 Py_XDECREF(so->key);
1831 Py_XDECREF(so->value);
1832 PyObject_Del(so);
1833}
1834
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001835/* Returns a new reference to a sortwrapper.
1836 Consumes the references to the two underlying objects. */
1837
1838static PyObject *
1839build_sortwrapper(PyObject *key, PyObject *value)
1840{
1841 sortwrapperobject *so;
Tim Petersb38e2b62004-07-29 02:29:26 +00001842
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001843 so = PyObject_New(sortwrapperobject, &PySortWrapper_Type);
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001844 if (so == NULL)
1845 return NULL;
1846 so->key = key;
1847 so->value = value;
1848 return (PyObject *)so;
1849}
1850
1851/* Returns a new reference to the value underlying the wrapper. */
1852static PyObject *
1853sortwrapper_getvalue(PyObject *so)
1854{
1855 PyObject *value;
1856
Christian Heimesa22e8bd2007-11-29 22:35:39 +00001857 if (!PyObject_TypeCheck(so, &PySortWrapper_Type)) {
Tim Petersb38e2b62004-07-29 02:29:26 +00001858 PyErr_SetString(PyExc_TypeError,
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001859 "expected a sortwrapperobject");
1860 return NULL;
1861 }
1862 value = ((sortwrapperobject *)so)->value;
1863 Py_INCREF(value);
1864 return value;
1865}
1866
Tim Petersa64dc242002-08-01 02:13:36 +00001867/* An adaptive, stable, natural mergesort. See listsort.txt.
1868 * Returns Py_None on success, NULL on error. Even in case of error, the
1869 * list will be some permutation of its input state (nothing is lost or
1870 * duplicated).
1871 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001872static PyObject *
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001873listsort(PyListObject *self, PyObject *args, PyObject *kwds)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001874{
Tim Petersa64dc242002-08-01 02:13:36 +00001875 MergeState ms;
1876 PyObject **lo, **hi;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001877 Py_ssize_t nremaining;
1878 Py_ssize_t minrun;
1879 Py_ssize_t saved_ob_size, saved_allocated;
Tim Petersb9099c32002-11-12 22:08:10 +00001880 PyObject **saved_ob_item;
Armin Rigo93677f02004-07-29 12:40:23 +00001881 PyObject **final_ob_item;
Tim Petersa64dc242002-08-01 02:13:36 +00001882 PyObject *result = NULL; /* guilty until proved innocent */
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001883 int reverse = 0;
1884 PyObject *keyfunc = NULL;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001885 Py_ssize_t i;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001886 PyObject *key, *value, *kvpair;
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001887 static char *kwlist[] = {"key", "reverse", 0};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001888
Tim Petersa64dc242002-08-01 02:13:36 +00001889 assert(self != NULL);
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001890 assert (PyList_Check(self));
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001891 if (args != NULL) {
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001892 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort",
1893 kwlist, &keyfunc, &reverse))
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001894 return NULL;
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001895 if (Py_SIZE(args) > 0) {
1896 PyErr_SetString(PyExc_TypeError,
1897 "must use keyword argument for key function");
1898 return NULL;
1899 }
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001900 }
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001901 if (keyfunc == Py_None)
1902 keyfunc = NULL;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001903
Tim Petersb9099c32002-11-12 22:08:10 +00001904 /* The list is temporarily made empty, so that mutations performed
1905 * by comparison functions can't affect the slice of memory we're
1906 * sorting (allowing mutations during sorting is a core-dump
1907 * factory, since ob_item may change).
1908 */
Christian Heimes90aa7642007-12-19 02:45:37 +00001909 saved_ob_size = Py_SIZE(self);
Tim Petersb9099c32002-11-12 22:08:10 +00001910 saved_ob_item = self->ob_item;
Raymond Hettinger4bb95402004-02-13 11:36:39 +00001911 saved_allocated = self->allocated;
Christian Heimes90aa7642007-12-19 02:45:37 +00001912 Py_SIZE(self) = 0;
Tim Peters51b4ade2004-07-29 04:07:15 +00001913 self->ob_item = NULL;
Armin Rigo93677f02004-07-29 12:40:23 +00001914 self->allocated = -1; /* any operation will reset it to >= 0 */
Tim Peters330f9e92002-07-19 07:05:44 +00001915
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001916 if (keyfunc != NULL) {
1917 for (i=0 ; i < saved_ob_size ; i++) {
1918 value = saved_ob_item[i];
Tim Petersb38e2b62004-07-29 02:29:26 +00001919 key = PyObject_CallFunctionObjArgs(keyfunc, value,
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001920 NULL);
1921 if (key == NULL) {
1922 for (i=i-1 ; i>=0 ; i--) {
1923 kvpair = saved_ob_item[i];
1924 value = sortwrapper_getvalue(kvpair);
1925 saved_ob_item[i] = value;
1926 Py_DECREF(kvpair);
1927 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001928 goto dsu_fail;
1929 }
1930 kvpair = build_sortwrapper(key, value);
1931 if (kvpair == NULL)
1932 goto dsu_fail;
1933 saved_ob_item[i] = kvpair;
1934 }
1935 }
1936
1937 /* Reverse sort stability achieved by initially reversing the list,
1938 applying a stable forward sort, then reversing the final result. */
1939 if (reverse && saved_ob_size > 1)
1940 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
1941
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001942 merge_init(&ms);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001943
Tim Petersb9099c32002-11-12 22:08:10 +00001944 nremaining = saved_ob_size;
Tim Petersa64dc242002-08-01 02:13:36 +00001945 if (nremaining < 2)
1946 goto succeed;
Tim Peters330f9e92002-07-19 07:05:44 +00001947
Tim Petersa64dc242002-08-01 02:13:36 +00001948 /* March over the array once, left to right, finding natural runs,
1949 * and extending short natural runs to minrun elements.
1950 */
Tim Petersb9099c32002-11-12 22:08:10 +00001951 lo = saved_ob_item;
Tim Petersa64dc242002-08-01 02:13:36 +00001952 hi = lo + nremaining;
1953 minrun = merge_compute_minrun(nremaining);
1954 do {
1955 int descending;
Martin v. Löwis18e16552006-02-15 17:27:45 +00001956 Py_ssize_t n;
Tim Peters330f9e92002-07-19 07:05:44 +00001957
Tim Petersa64dc242002-08-01 02:13:36 +00001958 /* Identify next run. */
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001959 n = count_run(lo, hi, &descending);
Tim Petersa64dc242002-08-01 02:13:36 +00001960 if (n < 0)
1961 goto fail;
1962 if (descending)
1963 reverse_slice(lo, lo + n);
1964 /* If short, extend to min(minrun, nremaining). */
1965 if (n < minrun) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00001966 const Py_ssize_t force = nremaining <= minrun ?
Tim Petersa64dc242002-08-01 02:13:36 +00001967 nremaining : minrun;
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001968 if (binarysort(lo, lo + force, lo + n) < 0)
Tim Petersa64dc242002-08-01 02:13:36 +00001969 goto fail;
1970 n = force;
1971 }
1972 /* Push run onto pending-runs stack, and maybe merge. */
1973 assert(ms.n < MAX_MERGE_PENDING);
Tim Peterse05f65a2002-08-10 05:21:15 +00001974 ms.pending[ms.n].base = lo;
1975 ms.pending[ms.n].len = n;
Tim Petersa64dc242002-08-01 02:13:36 +00001976 ++ms.n;
1977 if (merge_collapse(&ms) < 0)
1978 goto fail;
1979 /* Advance to find next run. */
1980 lo += n;
1981 nremaining -= n;
1982 } while (nremaining);
1983 assert(lo == hi);
Tim Peters330f9e92002-07-19 07:05:44 +00001984
Tim Petersa64dc242002-08-01 02:13:36 +00001985 if (merge_force_collapse(&ms) < 0)
1986 goto fail;
1987 assert(ms.n == 1);
Tim Petersb9099c32002-11-12 22:08:10 +00001988 assert(ms.pending[0].base == saved_ob_item);
1989 assert(ms.pending[0].len == saved_ob_size);
Tim Petersa64dc242002-08-01 02:13:36 +00001990
1991succeed:
1992 result = Py_None;
Tim Peters330f9e92002-07-19 07:05:44 +00001993fail:
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001994 if (keyfunc != NULL) {
1995 for (i=0 ; i < saved_ob_size ; i++) {
1996 kvpair = saved_ob_item[i];
1997 value = sortwrapper_getvalue(kvpair);
1998 saved_ob_item[i] = value;
1999 Py_DECREF(kvpair);
2000 }
2001 }
2002
Armin Rigo93677f02004-07-29 12:40:23 +00002003 if (self->allocated != -1 && result != NULL) {
Tim Peters51b4ade2004-07-29 04:07:15 +00002004 /* The user mucked with the list during the sort,
2005 * and we don't already have another error to report.
2006 */
2007 PyErr_SetString(PyExc_ValueError, "list modified during sort");
2008 result = NULL;
Tim Petersb9099c32002-11-12 22:08:10 +00002009 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002010
2011 if (reverse && saved_ob_size > 1)
2012 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
2013
2014 merge_freemem(&ms);
2015
2016dsu_fail:
Armin Rigo93677f02004-07-29 12:40:23 +00002017 final_ob_item = self->ob_item;
Christian Heimes90aa7642007-12-19 02:45:37 +00002018 i = Py_SIZE(self);
2019 Py_SIZE(self) = saved_ob_size;
Tim Petersb9099c32002-11-12 22:08:10 +00002020 self->ob_item = saved_ob_item;
Raymond Hettinger4bb95402004-02-13 11:36:39 +00002021 self->allocated = saved_allocated;
Armin Rigo93677f02004-07-29 12:40:23 +00002022 if (final_ob_item != NULL) {
2023 /* we cannot use list_clear() for this because it does not
2024 guarantee that the list is really empty when it returns */
2025 while (--i >= 0) {
2026 Py_XDECREF(final_ob_item[i]);
2027 }
2028 PyMem_FREE(final_ob_item);
2029 }
Tim Petersa64dc242002-08-01 02:13:36 +00002030 Py_XINCREF(result);
2031 return result;
Guido van Rossum3f236de1996-12-10 23:55:39 +00002032}
Tim Peters330f9e92002-07-19 07:05:44 +00002033#undef IFLT
Tim Peters66860f62002-08-04 17:47:26 +00002034#undef ISLT
Tim Peters330f9e92002-07-19 07:05:44 +00002035
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002036int
Fred Drakea2f55112000-07-09 15:16:51 +00002037PyList_Sort(PyObject *v)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002038{
2039 if (v == NULL || !PyList_Check(v)) {
2040 PyErr_BadInternalCall();
2041 return -1;
2042 }
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002043 v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002044 if (v == NULL)
2045 return -1;
2046 Py_DECREF(v);
2047 return 0;
2048}
2049
Guido van Rossumb86c5492001-02-12 22:06:02 +00002050static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002051listreverse(PyListObject *self)
Guido van Rossumb86c5492001-02-12 22:06:02 +00002052{
Christian Heimes90aa7642007-12-19 02:45:37 +00002053 if (Py_SIZE(self) > 1)
2054 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
Raymond Hettinger45d0b5c2004-04-12 17:21:03 +00002055 Py_RETURN_NONE;
Guido van Rossumed98d481991-03-06 13:07:53 +00002056}
2057
Guido van Rossum84c76f51990-10-30 13:32:20 +00002058int
Fred Drakea2f55112000-07-09 15:16:51 +00002059PyList_Reverse(PyObject *v)
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002060{
Tim Peters6063e262002-08-08 01:06:39 +00002061 PyListObject *self = (PyListObject *)v;
2062
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002063 if (v == NULL || !PyList_Check(v)) {
2064 PyErr_BadInternalCall();
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002065 return -1;
2066 }
Christian Heimes90aa7642007-12-19 02:45:37 +00002067 if (Py_SIZE(self) > 1)
2068 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002069 return 0;
2070}
2071
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002072PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00002073PyList_AsTuple(PyObject *v)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002074{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002075 PyObject *w;
Christian Heimes2c181612007-12-17 20:04:13 +00002076 PyObject **p, **q;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002077 Py_ssize_t n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002078 if (v == NULL || !PyList_Check(v)) {
2079 PyErr_BadInternalCall();
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002080 return NULL;
2081 }
Christian Heimes90aa7642007-12-19 02:45:37 +00002082 n = Py_SIZE(v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002083 w = PyTuple_New(n);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002084 if (w == NULL)
2085 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002086 p = ((PyTupleObject *)w)->ob_item;
Christian Heimes2c181612007-12-17 20:04:13 +00002087 q = ((PyListObject *)v)->ob_item;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002088 while (--n >= 0) {
Christian Heimes2c181612007-12-17 20:04:13 +00002089 Py_INCREF(*q);
2090 *p = *q;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002091 p++;
Christian Heimes2c181612007-12-17 20:04:13 +00002092 q++;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002093 }
2094 return w;
2095}
2096
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002097static PyObject *
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002098listindex(PyListObject *self, PyObject *args)
Guido van Rossumed98d481991-03-06 13:07:53 +00002099{
Christian Heimes90aa7642007-12-19 02:45:37 +00002100 Py_ssize_t i, start=0, stop=Py_SIZE(self);
Benjamin Petersonf6489f92009-11-25 17:46:26 +00002101 PyObject *v, *format_tuple, *err_string;
2102 static PyObject *err_format = NULL;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002103
Walter Dörwalde8049bef2003-06-17 19:27:39 +00002104 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
2105 _PyEval_SliceIndex, &start,
2106 _PyEval_SliceIndex, &stop))
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002107 return NULL;
Guido van Rossum2743d872003-06-17 14:25:14 +00002108 if (start < 0) {
Christian Heimes90aa7642007-12-19 02:45:37 +00002109 start += Py_SIZE(self);
Guido van Rossum2743d872003-06-17 14:25:14 +00002110 if (start < 0)
2111 start = 0;
2112 }
2113 if (stop < 0) {
Christian Heimes90aa7642007-12-19 02:45:37 +00002114 stop += Py_SIZE(self);
Guido van Rossum2743d872003-06-17 14:25:14 +00002115 if (stop < 0)
2116 stop = 0;
2117 }
Christian Heimes90aa7642007-12-19 02:45:37 +00002118 for (i = start; i < stop && i < Py_SIZE(self); i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002119 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2120 if (cmp > 0)
Christian Heimes217cfd12007-12-02 14:31:20 +00002121 return PyLong_FromSsize_t(i);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002122 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00002123 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002124 }
Benjamin Petersonf6489f92009-11-25 17:46:26 +00002125 if (err_format == NULL) {
2126 err_format = PyUnicode_FromString("%r is not in list");
2127 if (err_format == NULL)
2128 return NULL;
2129 }
2130 format_tuple = PyTuple_Pack(1, v);
2131 if (format_tuple == NULL)
2132 return NULL;
2133 err_string = PyUnicode_Format(err_format, format_tuple);
2134 Py_DECREF(format_tuple);
2135 if (err_string == NULL)
2136 return NULL;
2137 PyErr_SetObject(PyExc_ValueError, err_string);
2138 Py_DECREF(err_string);
Guido van Rossumed98d481991-03-06 13:07:53 +00002139 return NULL;
2140}
2141
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002142static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002143listcount(PyListObject *self, PyObject *v)
Guido van Rossume6f7d181991-10-20 20:20:40 +00002144{
Martin v. Löwis18e16552006-02-15 17:27:45 +00002145 Py_ssize_t count = 0;
2146 Py_ssize_t i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002147
Christian Heimes90aa7642007-12-19 02:45:37 +00002148 for (i = 0; i < Py_SIZE(self); i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002149 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2150 if (cmp > 0)
Guido van Rossume6f7d181991-10-20 20:20:40 +00002151 count++;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002152 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00002153 return NULL;
Guido van Rossume6f7d181991-10-20 20:20:40 +00002154 }
Christian Heimes217cfd12007-12-02 14:31:20 +00002155 return PyLong_FromSsize_t(count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00002156}
2157
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002158static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002159listremove(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00002160{
Martin v. Löwis18e16552006-02-15 17:27:45 +00002161 Py_ssize_t i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002162
Christian Heimes90aa7642007-12-19 02:45:37 +00002163 for (i = 0; i < Py_SIZE(self); i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002164 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2165 if (cmp > 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002166 if (list_ass_slice(self, i, i+1,
Raymond Hettinger45d0b5c2004-04-12 17:21:03 +00002167 (PyObject *)NULL) == 0)
2168 Py_RETURN_NONE;
2169 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002170 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002171 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00002172 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002173 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002174 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00002175 return NULL;
2176}
2177
Jeremy Hylton8caad492000-06-23 14:18:11 +00002178static int
2179list_traverse(PyListObject *o, visitproc visit, void *arg)
2180{
Martin v. Löwis18e16552006-02-15 17:27:45 +00002181 Py_ssize_t i;
Jeremy Hylton8caad492000-06-23 14:18:11 +00002182
Christian Heimes90aa7642007-12-19 02:45:37 +00002183 for (i = Py_SIZE(o); --i >= 0; )
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002184 Py_VISIT(o->ob_item[i]);
Jeremy Hylton8caad492000-06-23 14:18:11 +00002185 return 0;
2186}
2187
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002188static PyObject *
2189list_richcompare(PyObject *v, PyObject *w, int op)
2190{
2191 PyListObject *vl, *wl;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002192 Py_ssize_t i;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002193
2194 if (!PyList_Check(v) || !PyList_Check(w)) {
2195 Py_INCREF(Py_NotImplemented);
2196 return Py_NotImplemented;
2197 }
2198
2199 vl = (PyListObject *)v;
2200 wl = (PyListObject *)w;
2201
Christian Heimes90aa7642007-12-19 02:45:37 +00002202 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002203 /* Shortcut: if the lengths differ, the lists differ */
2204 PyObject *res;
2205 if (op == Py_EQ)
2206 res = Py_False;
2207 else
2208 res = Py_True;
2209 Py_INCREF(res);
2210 return res;
2211 }
2212
2213 /* Search for the first index where items are different */
Christian Heimes90aa7642007-12-19 02:45:37 +00002214 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002215 int k = PyObject_RichCompareBool(vl->ob_item[i],
2216 wl->ob_item[i], Py_EQ);
2217 if (k < 0)
2218 return NULL;
2219 if (!k)
2220 break;
2221 }
2222
Christian Heimes90aa7642007-12-19 02:45:37 +00002223 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002224 /* No more items to compare -- compare sizes */
Christian Heimes90aa7642007-12-19 02:45:37 +00002225 Py_ssize_t vs = Py_SIZE(vl);
2226 Py_ssize_t ws = Py_SIZE(wl);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002227 int cmp;
2228 PyObject *res;
2229 switch (op) {
2230 case Py_LT: cmp = vs < ws; break;
Tim Peters6ee42342001-07-06 17:45:43 +00002231 case Py_LE: cmp = vs <= ws; break;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002232 case Py_EQ: cmp = vs == ws; break;
2233 case Py_NE: cmp = vs != ws; break;
2234 case Py_GT: cmp = vs > ws; break;
2235 case Py_GE: cmp = vs >= ws; break;
2236 default: return NULL; /* cannot happen */
2237 }
2238 if (cmp)
2239 res = Py_True;
2240 else
2241 res = Py_False;
2242 Py_INCREF(res);
2243 return res;
2244 }
2245
2246 /* We have an item that differs -- shortcuts for EQ/NE */
2247 if (op == Py_EQ) {
2248 Py_INCREF(Py_False);
2249 return Py_False;
2250 }
2251 if (op == Py_NE) {
2252 Py_INCREF(Py_True);
2253 return Py_True;
2254 }
2255
2256 /* Compare the final item again using the proper operator */
2257 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
2258}
2259
Tim Peters6d6c1a32001-08-02 04:15:00 +00002260static int
2261list_init(PyListObject *self, PyObject *args, PyObject *kw)
2262{
2263 PyObject *arg = NULL;
Martin v. Löwis15e62742006-02-27 16:46:16 +00002264 static char *kwlist[] = {"sequence", 0};
Tim Peters6d6c1a32001-08-02 04:15:00 +00002265
2266 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
2267 return -1;
Raymond Hettingerc0aaa2d2004-07-29 23:31:29 +00002268
2269 /* Verify list invariants established by PyType_GenericAlloc() */
Christian Heimes90aa7642007-12-19 02:45:37 +00002270 assert(0 <= Py_SIZE(self));
2271 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
Armin Rigoa37bbf22004-07-30 11:20:18 +00002272 assert(self->ob_item != NULL ||
2273 self->allocated == 0 || self->allocated == -1);
Raymond Hettingerc0aaa2d2004-07-29 23:31:29 +00002274
Raymond Hettinger90a39bf2004-02-15 03:57:00 +00002275 /* Empty previous contents */
Armin Rigo93677f02004-07-29 12:40:23 +00002276 if (self->ob_item != NULL) {
2277 (void)list_clear(self);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +00002278 }
2279 if (arg != NULL) {
2280 PyObject *rv = listextend(self, arg);
2281 if (rv == NULL)
2282 return -1;
2283 Py_DECREF(rv);
2284 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00002285 return 0;
2286}
2287
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002288static PyObject *
2289list_sizeof(PyListObject *self)
2290{
2291 Py_ssize_t res;
2292
2293 res = sizeof(PyListObject) + self->allocated * sizeof(void*);
2294 return PyLong_FromSsize_t(res);
2295}
2296
Raymond Hettinger1021c442003-11-07 15:38:09 +00002297static PyObject *list_iter(PyObject *seq);
2298static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
2299
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002300PyDoc_STRVAR(getitem_doc,
2301"x.__getitem__(y) <==> x[y]");
Raymond Hettinger1021c442003-11-07 15:38:09 +00002302PyDoc_STRVAR(reversed_doc,
2303"L.__reversed__() -- return a reverse iterator over the list");
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002304PyDoc_STRVAR(sizeof_doc,
2305"L.__sizeof__() -- size of L in memory, in bytes");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002306PyDoc_STRVAR(append_doc,
2307"L.append(object) -- append object to end");
2308PyDoc_STRVAR(extend_doc,
Raymond Hettingerf8bcfb12002-12-29 05:49:09 +00002309"L.extend(iterable) -- extend list by appending elements from the iterable");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002310PyDoc_STRVAR(insert_doc,
2311"L.insert(index, object) -- insert object before index");
2312PyDoc_STRVAR(pop_doc,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002313"L.pop([index]) -> item -- remove and return item at index (default last).\n"
2314"Raises IndexError if list is empty or index is out of range.");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002315PyDoc_STRVAR(remove_doc,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002316"L.remove(value) -- remove first occurrence of value.\n"
2317"Raises ValueError if the value is not present.");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002318PyDoc_STRVAR(index_doc,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002319"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
2320"Raises ValueError if the value is not present.");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002321PyDoc_STRVAR(count_doc,
2322"L.count(value) -> integer -- return number of occurrences of value");
2323PyDoc_STRVAR(reverse_doc,
2324"L.reverse() -- reverse *IN PLACE*");
2325PyDoc_STRVAR(sort_doc,
Benjamin Petersoncb9a5512008-09-30 02:08:36 +00002326"L.sort(key=None, reverse=False) -- stable sort *IN PLACE*");
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00002327
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002328static PyObject *list_subscript(PyListObject*, PyObject*);
2329
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002330static PyMethodDef list_methods[] = {
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002331 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
Raymond Hettinger1021c442003-11-07 15:38:09 +00002332 {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002333 {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002334 {"append", (PyCFunction)listappend, METH_O, append_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002335 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002336 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002337 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002338 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002339 {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002340 {"count", (PyCFunction)listcount, METH_O, count_doc},
2341 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002342 {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
Tim Petersa64dc242002-08-01 02:13:36 +00002343 {NULL, NULL} /* sentinel */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002344};
2345
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002346static PySequenceMethods list_as_sequence = {
Martin v. Löwis18e16552006-02-15 17:27:45 +00002347 (lenfunc)list_length, /* sq_length */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002348 (binaryfunc)list_concat, /* sq_concat */
Martin v. Löwis18e16552006-02-15 17:27:45 +00002349 (ssizeargfunc)list_repeat, /* sq_repeat */
2350 (ssizeargfunc)list_item, /* sq_item */
Thomas Woutersd2cf20e2007-08-30 22:57:53 +00002351 0, /* sq_slice */
Martin v. Löwis18e16552006-02-15 17:27:45 +00002352 (ssizeobjargproc)list_ass_item, /* sq_ass_item */
Thomas Woutersd2cf20e2007-08-30 22:57:53 +00002353 0, /* sq_ass_slice */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002354 (objobjproc)list_contains, /* sq_contains */
2355 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
Martin v. Löwis18e16552006-02-15 17:27:45 +00002356 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002357};
2358
Neal Norwitz2c2e8272002-06-14 02:04:18 +00002359PyDoc_STRVAR(list_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002360"list() -> new empty list\n"
2361"list(iterable) -> new list initialized from iterable's items");
Tim Peters6d6c1a32001-08-02 04:15:00 +00002362
Jeremy Hyltona4b4c3b2002-07-13 03:51:17 +00002363static PyObject *
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002364list_subscript(PyListObject* self, PyObject* item)
2365{
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00002366 if (PyIndex_Check(item)) {
2367 Py_ssize_t i;
2368 i = PyNumber_AsSsize_t(item, PyExc_IndexError);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002369 if (i == -1 && PyErr_Occurred())
2370 return NULL;
2371 if (i < 0)
2372 i += PyList_GET_SIZE(self);
2373 return list_item(self, i);
2374 }
2375 else if (PySlice_Check(item)) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00002376 Py_ssize_t start, stop, step, slicelength, cur, i;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002377 PyObject* result;
2378 PyObject* it;
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002379 PyObject **src, **dest;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002380
Christian Heimes90aa7642007-12-19 02:45:37 +00002381 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002382 &start, &stop, &step, &slicelength) < 0) {
2383 return NULL;
2384 }
2385
2386 if (slicelength <= 0) {
2387 return PyList_New(0);
2388 }
Thomas Woutersed03b412007-08-28 21:37:11 +00002389 else if (step == 1) {
2390 return list_slice(self, start, stop);
2391 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002392 else {
2393 result = PyList_New(slicelength);
2394 if (!result) return NULL;
2395
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002396 src = self->ob_item;
2397 dest = ((PyListObject *)result)->ob_item;
Tim Peters3b01a122002-07-19 02:35:45 +00002398 for (cur = start, i = 0; i < slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002399 cur += step, i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002400 it = src[cur];
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002401 Py_INCREF(it);
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002402 dest[i] = it;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002403 }
Tim Peters3b01a122002-07-19 02:35:45 +00002404
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002405 return result;
2406 }
2407 }
2408 else {
Thomas Wouters89f507f2006-12-13 04:49:30 +00002409 PyErr_Format(PyExc_TypeError,
2410 "list indices must be integers, not %.200s",
2411 item->ob_type->tp_name);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002412 return NULL;
2413 }
2414}
2415
Tim Peters3b01a122002-07-19 02:35:45 +00002416static int
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002417list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2418{
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00002419 if (PyIndex_Check(item)) {
2420 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002421 if (i == -1 && PyErr_Occurred())
2422 return -1;
2423 if (i < 0)
2424 i += PyList_GET_SIZE(self);
2425 return list_ass_item(self, i, value);
2426 }
2427 else if (PySlice_Check(item)) {
Martin v. Löwis18e16552006-02-15 17:27:45 +00002428 Py_ssize_t start, stop, step, slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002429
Christian Heimes90aa7642007-12-19 02:45:37 +00002430 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002431 &start, &stop, &step, &slicelength) < 0) {
2432 return -1;
2433 }
2434
Thomas Woutersed03b412007-08-28 21:37:11 +00002435 if (step == 1)
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002436 return list_ass_slice(self, start, stop, value);
2437
Thomas Woutersed03b412007-08-28 21:37:11 +00002438 /* Make sure s[5:2] = [..] inserts at the right place:
2439 before 5, not before 2. */
2440 if ((step < 0 && start < stop) ||
2441 (step > 0 && start > stop))
2442 stop = start;
2443
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002444 if (value == NULL) {
2445 /* delete slice */
Raymond Hettinger4bb95402004-02-13 11:36:39 +00002446 PyObject **garbage;
Mark Dickinsonbc099642010-01-29 17:27:24 +00002447 size_t cur;
2448 Py_ssize_t i;
Tim Peters3b01a122002-07-19 02:35:45 +00002449
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002450 if (slicelength <= 0)
2451 return 0;
2452
2453 if (step < 0) {
2454 stop = start + 1;
2455 start = stop + step*(slicelength - 1) - 1;
2456 step = -step;
2457 }
2458
Mark Dickinson66f575b2010-02-14 12:53:32 +00002459 assert((size_t)slicelength <=
2460 PY_SIZE_MAX / sizeof(PyObject*));
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +00002461
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002462 garbage = (PyObject**)
2463 PyMem_MALLOC(slicelength*sizeof(PyObject*));
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00002464 if (!garbage) {
2465 PyErr_NoMemory();
2466 return -1;
2467 }
Tim Peters3b01a122002-07-19 02:35:45 +00002468
Thomas Woutersed03b412007-08-28 21:37:11 +00002469 /* drawing pictures might help understand these for
2470 loops. Basically, we memmove the parts of the
2471 list that are *not* part of the slice: step-1
2472 items for each item that is part of the slice,
2473 and then tail end of the list that was not
2474 covered by the slice */
Guido van Rossum75a20b12002-06-11 12:22:28 +00002475 for (cur = start, i = 0;
Mark Dickinson66f575b2010-02-14 12:53:32 +00002476 cur < (size_t)stop;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002477 cur += step, i++) {
Thomas Woutersed03b412007-08-28 21:37:11 +00002478 Py_ssize_t lim = step - 1;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002479
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002480 garbage[i] = PyList_GET_ITEM(self, cur);
2481
Mark Dickinson66f575b2010-02-14 12:53:32 +00002482 if (cur + step >= (size_t)Py_SIZE(self)) {
Christian Heimes90aa7642007-12-19 02:45:37 +00002483 lim = Py_SIZE(self) - cur - 1;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002484 }
2485
Tim Petersb38e2b62004-07-29 02:29:26 +00002486 memmove(self->ob_item + cur - i,
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002487 self->ob_item + cur + 1,
2488 lim * sizeof(PyObject *));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002489 }
Thomas Woutersed03b412007-08-28 21:37:11 +00002490 cur = start + slicelength*step;
Mark Dickinson66f575b2010-02-14 12:53:32 +00002491 if (cur < (size_t)Py_SIZE(self)) {
Thomas Woutersed03b412007-08-28 21:37:11 +00002492 memmove(self->ob_item + cur - slicelength,
2493 self->ob_item + cur,
Christian Heimes90aa7642007-12-19 02:45:37 +00002494 (Py_SIZE(self) - cur) *
Thomas Woutersed03b412007-08-28 21:37:11 +00002495 sizeof(PyObject *));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002496 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002497
Christian Heimes90aa7642007-12-19 02:45:37 +00002498 Py_SIZE(self) -= slicelength;
2499 list_resize(self, Py_SIZE(self));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002500
2501 for (i = 0; i < slicelength; i++) {
2502 Py_DECREF(garbage[i]);
2503 }
2504 PyMem_FREE(garbage);
2505
2506 return 0;
2507 }
2508 else {
2509 /* assign slice */
Thomas Woutersed03b412007-08-28 21:37:11 +00002510 PyObject *ins, *seq;
2511 PyObject **garbage, **seqitems, **selfitems;
Martin v. Löwis18e16552006-02-15 17:27:45 +00002512 Py_ssize_t cur, i;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002513
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002514 /* protect against a[::-1] = a */
Tim Peters3b01a122002-07-19 02:35:45 +00002515 if (self == (PyListObject*)value) {
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002516 seq = list_slice((PyListObject*)value, 0,
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002517 PyList_GET_SIZE(value));
Tim Peters3b01a122002-07-19 02:35:45 +00002518 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002519 else {
Tim Petersb38e2b62004-07-29 02:29:26 +00002520 seq = PySequence_Fast(value,
Thomas Woutersed03b412007-08-28 21:37:11 +00002521 "must assign iterable "
2522 "to extended slice");
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002523 }
Thomas Wouters00ee7ba2006-08-21 19:07:27 +00002524 if (!seq)
2525 return -1;
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002526
2527 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2528 PyErr_Format(PyExc_ValueError,
Thomas Woutersed03b412007-08-28 21:37:11 +00002529 "attempt to assign sequence of "
2530 "size %zd to extended slice of "
2531 "size %zd",
Martin v. Löwise0e89f72006-02-16 06:59:22 +00002532 PySequence_Fast_GET_SIZE(seq),
2533 slicelength);
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002534 Py_DECREF(seq);
2535 return -1;
2536 }
2537
2538 if (!slicelength) {
2539 Py_DECREF(seq);
2540 return 0;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002541 }
2542
2543 garbage = (PyObject**)
2544 PyMem_MALLOC(slicelength*sizeof(PyObject*));
Thomas Wouters89f507f2006-12-13 04:49:30 +00002545 if (!garbage) {
2546 Py_DECREF(seq);
2547 PyErr_NoMemory();
2548 return -1;
2549 }
Tim Peters3b01a122002-07-19 02:35:45 +00002550
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002551 selfitems = self->ob_item;
Raymond Hettinger42bec932004-03-12 16:38:17 +00002552 seqitems = PySequence_Fast_ITEMS(seq);
Tim Peters3b01a122002-07-19 02:35:45 +00002553 for (cur = start, i = 0; i < slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002554 cur += step, i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002555 garbage[i] = selfitems[cur];
2556 ins = seqitems[i];
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002557 Py_INCREF(ins);
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002558 selfitems[cur] = ins;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002559 }
2560
2561 for (i = 0; i < slicelength; i++) {
2562 Py_DECREF(garbage[i]);
2563 }
Tim Peters3b01a122002-07-19 02:35:45 +00002564
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002565 PyMem_FREE(garbage);
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002566 Py_DECREF(seq);
Tim Peters3b01a122002-07-19 02:35:45 +00002567
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002568 return 0;
2569 }
Tim Peters3b01a122002-07-19 02:35:45 +00002570 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002571 else {
Thomas Wouters89f507f2006-12-13 04:49:30 +00002572 PyErr_Format(PyExc_TypeError,
2573 "list indices must be integers, not %.200s",
2574 item->ob_type->tp_name);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002575 return -1;
2576 }
2577}
2578
2579static PyMappingMethods list_as_mapping = {
Martin v. Löwis18e16552006-02-15 17:27:45 +00002580 (lenfunc)list_length,
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002581 (binaryfunc)list_subscript,
2582 (objobjargproc)list_ass_subscript
2583};
2584
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002585PyTypeObject PyList_Type = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002586 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002587 "list",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002588 sizeof(PyListObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002589 0,
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002590 (destructor)list_dealloc, /* tp_dealloc */
Guido van Rossum04dbf3b2007-08-07 19:51:00 +00002591 0, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002592 0, /* tp_getattr */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002593 0, /* tp_setattr */
Mark Dickinsone94c6792009-02-02 20:36:42 +00002594 0, /* tp_reserved */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002595 (reprfunc)list_repr, /* tp_repr */
2596 0, /* tp_as_number */
2597 &list_as_sequence, /* tp_as_sequence */
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002598 &list_as_mapping, /* tp_as_mapping */
Nick Coghland1abd252008-07-15 15:46:38 +00002599 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002600 0, /* tp_call */
2601 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002602 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002603 0, /* tp_setattro */
2604 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002605 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Thomas Wouters27d517b2007-02-25 20:39:11 +00002606 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002607 list_doc, /* tp_doc */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002608 (traverseproc)list_traverse, /* tp_traverse */
2609 (inquiry)list_clear, /* tp_clear */
2610 list_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002611 0, /* tp_weaklistoffset */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002612 list_iter, /* tp_iter */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002613 0, /* tp_iternext */
2614 list_methods, /* tp_methods */
2615 0, /* tp_members */
2616 0, /* tp_getset */
2617 0, /* tp_base */
2618 0, /* tp_dict */
2619 0, /* tp_descr_get */
2620 0, /* tp_descr_set */
2621 0, /* tp_dictoffset */
2622 (initproc)list_init, /* tp_init */
2623 PyType_GenericAlloc, /* tp_alloc */
2624 PyType_GenericNew, /* tp_new */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002625 PyObject_GC_Del, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002626};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002627
2628
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002629/*********************** List Iterator **************************/
2630
2631typedef struct {
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002632 PyObject_HEAD
2633 long it_index;
Guido van Rossum86103ae2002-07-16 20:07:32 +00002634 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002635} listiterobject;
2636
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002637static PyObject *list_iter(PyObject *);
2638static void listiter_dealloc(listiterobject *);
2639static int listiter_traverse(listiterobject *, visitproc, void *);
2640static PyObject *listiter_next(listiterobject *);
2641static PyObject *listiter_len(listiterobject *);
Raymond Hettinger435bf582004-03-18 22:43:10 +00002642
Armin Rigof5b3e362006-02-11 21:32:43 +00002643PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002644
2645static PyMethodDef listiter_methods[] = {
Armin Rigof5b3e362006-02-11 21:32:43 +00002646 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002647 {NULL, NULL} /* sentinel */
Raymond Hettinger435bf582004-03-18 22:43:10 +00002648};
2649
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002650PyTypeObject PyListIter_Type = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002651 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Christian Heimesf83be4e2007-11-28 09:44:38 +00002652 "list_iterator", /* tp_name */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002653 sizeof(listiterobject), /* tp_basicsize */
2654 0, /* tp_itemsize */
2655 /* methods */
2656 (destructor)listiter_dealloc, /* tp_dealloc */
2657 0, /* tp_print */
2658 0, /* tp_getattr */
2659 0, /* tp_setattr */
Mark Dickinsone94c6792009-02-02 20:36:42 +00002660 0, /* tp_reserved */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002661 0, /* tp_repr */
2662 0, /* tp_as_number */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002663 0, /* tp_as_sequence */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002664 0, /* tp_as_mapping */
2665 0, /* tp_hash */
2666 0, /* tp_call */
2667 0, /* tp_str */
2668 PyObject_GenericGetAttr, /* tp_getattro */
2669 0, /* tp_setattro */
2670 0, /* tp_as_buffer */
2671 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2672 0, /* tp_doc */
2673 (traverseproc)listiter_traverse, /* tp_traverse */
2674 0, /* tp_clear */
2675 0, /* tp_richcompare */
2676 0, /* tp_weaklistoffset */
Raymond Hettinger1da1dbf2003-03-17 19:46:11 +00002677 PyObject_SelfIter, /* tp_iter */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002678 (iternextfunc)listiter_next, /* tp_iternext */
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002679 listiter_methods, /* tp_methods */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002680 0, /* tp_members */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002681};
Raymond Hettinger1021c442003-11-07 15:38:09 +00002682
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002683
2684static PyObject *
2685list_iter(PyObject *seq)
2686{
2687 listiterobject *it;
2688
2689 if (!PyList_Check(seq)) {
2690 PyErr_BadInternalCall();
2691 return NULL;
2692 }
2693 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2694 if (it == NULL)
2695 return NULL;
2696 it->it_index = 0;
2697 Py_INCREF(seq);
2698 it->it_seq = (PyListObject *)seq;
2699 _PyObject_GC_TRACK(it);
2700 return (PyObject *)it;
2701}
2702
2703static void
2704listiter_dealloc(listiterobject *it)
2705{
2706 _PyObject_GC_UNTRACK(it);
2707 Py_XDECREF(it->it_seq);
2708 PyObject_GC_Del(it);
2709}
2710
2711static int
2712listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2713{
2714 Py_VISIT(it->it_seq);
2715 return 0;
2716}
2717
2718static PyObject *
2719listiter_next(listiterobject *it)
2720{
2721 PyListObject *seq;
2722 PyObject *item;
2723
2724 assert(it != NULL);
2725 seq = it->it_seq;
2726 if (seq == NULL)
2727 return NULL;
2728 assert(PyList_Check(seq));
2729
2730 if (it->it_index < PyList_GET_SIZE(seq)) {
2731 item = PyList_GET_ITEM(seq, it->it_index);
2732 ++it->it_index;
2733 Py_INCREF(item);
2734 return item;
2735 }
2736
2737 Py_DECREF(seq);
2738 it->it_seq = NULL;
2739 return NULL;
2740}
2741
2742static PyObject *
2743listiter_len(listiterobject *it)
2744{
2745 Py_ssize_t len;
2746 if (it->it_seq) {
2747 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
2748 if (len >= 0)
Christian Heimes217cfd12007-12-02 14:31:20 +00002749 return PyLong_FromSsize_t(len);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002750 }
Christian Heimes217cfd12007-12-02 14:31:20 +00002751 return PyLong_FromLong(0);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002752}
Raymond Hettinger1021c442003-11-07 15:38:09 +00002753/*********************** List Reverse Iterator **************************/
2754
2755typedef struct {
2756 PyObject_HEAD
Martin v. Löwiseb079f12006-02-16 14:32:27 +00002757 Py_ssize_t it_index;
Raymond Hettinger001f2282003-11-08 11:58:44 +00002758 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002759} listreviterobject;
2760
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002761static PyObject *list_reversed(PyListObject *, PyObject *);
2762static void listreviter_dealloc(listreviterobject *);
2763static int listreviter_traverse(listreviterobject *, visitproc, void *);
2764static PyObject *listreviter_next(listreviterobject *);
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002765static PyObject *listreviter_len(listreviterobject *);
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002766
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002767static PyMethodDef listreviter_methods[] = {
2768 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
2769 {NULL, NULL} /* sentinel */
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002770};
2771
Raymond Hettinger1021c442003-11-07 15:38:09 +00002772PyTypeObject PyListRevIter_Type = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +00002773 PyVarObject_HEAD_INIT(&PyType_Type, 0)
Christian Heimesf83be4e2007-11-28 09:44:38 +00002774 "list_reverseiterator", /* tp_name */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002775 sizeof(listreviterobject), /* tp_basicsize */
2776 0, /* tp_itemsize */
2777 /* methods */
2778 (destructor)listreviter_dealloc, /* tp_dealloc */
2779 0, /* tp_print */
2780 0, /* tp_getattr */
2781 0, /* tp_setattr */
Mark Dickinsone94c6792009-02-02 20:36:42 +00002782 0, /* tp_reserved */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002783 0, /* tp_repr */
2784 0, /* tp_as_number */
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002785 0, /* tp_as_sequence */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002786 0, /* tp_as_mapping */
2787 0, /* tp_hash */
2788 0, /* tp_call */
2789 0, /* tp_str */
2790 PyObject_GenericGetAttr, /* tp_getattro */
2791 0, /* tp_setattro */
2792 0, /* tp_as_buffer */
2793 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2794 0, /* tp_doc */
2795 (traverseproc)listreviter_traverse, /* tp_traverse */
2796 0, /* tp_clear */
2797 0, /* tp_richcompare */
2798 0, /* tp_weaklistoffset */
2799 PyObject_SelfIter, /* tp_iter */
2800 (iternextfunc)listreviter_next, /* tp_iternext */
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002801 listreviter_methods, /* tp_methods */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002802 0,
2803};
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002804
2805static PyObject *
2806list_reversed(PyListObject *seq, PyObject *unused)
2807{
2808 listreviterobject *it;
2809
2810 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
2811 if (it == NULL)
2812 return NULL;
2813 assert(PyList_Check(seq));
2814 it->it_index = PyList_GET_SIZE(seq) - 1;
2815 Py_INCREF(seq);
2816 it->it_seq = seq;
2817 PyObject_GC_Track(it);
2818 return (PyObject *)it;
2819}
2820
2821static void
2822listreviter_dealloc(listreviterobject *it)
2823{
2824 PyObject_GC_UnTrack(it);
2825 Py_XDECREF(it->it_seq);
2826 PyObject_GC_Del(it);
2827}
2828
2829static int
2830listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
2831{
2832 Py_VISIT(it->it_seq);
2833 return 0;
2834}
2835
2836static PyObject *
2837listreviter_next(listreviterobject *it)
2838{
2839 PyObject *item;
2840 Py_ssize_t index = it->it_index;
2841 PyListObject *seq = it->it_seq;
2842
2843 if (index>=0 && index < PyList_GET_SIZE(seq)) {
2844 item = PyList_GET_ITEM(seq, index);
2845 it->it_index--;
2846 Py_INCREF(item);
2847 return item;
2848 }
2849 it->it_index = -1;
2850 if (seq != NULL) {
2851 it->it_seq = NULL;
2852 Py_DECREF(seq);
2853 }
2854 return NULL;
2855}
2856
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002857static PyObject *
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002858listreviter_len(listreviterobject *it)
2859{
2860 Py_ssize_t len = it->it_index + 1;
2861 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002862 len = 0;
2863 return PyLong_FromSsize_t(len);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002864}
2865