blob: 815a1b9ea2d80b17f8c015aa05abcd145c25b6bb [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"
Antoine Pitrou0197ff92012-03-22 14:38:16 +01004#include "accu.h"
Guido van Rossumc0b618a1997-05-02 03:12:38 +00005
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00006#ifdef STDC_HEADERS
7#include <stddef.h>
8#else
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00009#include <sys/types.h> /* For size_t */
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000010#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000011
Tim Peters8d9eb102004-07-31 02:24:20 +000012/* Ensure ob_item has room for at least newsize elements, and set
13 * ob_size to newsize. If newsize > ob_size on entry, the content
14 * of the new slots at exit is undefined heap trash; it's the caller's
Ezio Melotti13925002011-03-16 11:05:33 +020015 * responsibility to overwrite them with sane values.
Tim Peters8d9eb102004-07-31 02:24:20 +000016 * The number of allocated elements may grow, shrink, or stay the same.
17 * Failure is impossible if newsize <= self.allocated on entry, although
18 * that partly relies on an assumption that the system realloc() never
19 * fails when passed a number of bytes <= the number of bytes last
20 * allocated (the C standard doesn't guarantee this, but it's hard to
21 * imagine a realloc implementation where it wouldn't be true).
22 * Note that self->ob_item may change, and even if newsize is less
23 * than ob_size on entry.
24 */
Guido van Rossuma46d51d1995-01-26 22:59:43 +000025static int
Martin v. Löwis18e16552006-02-15 17:27:45 +000026list_resize(PyListObject *self, Py_ssize_t newsize)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000027{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000028 PyObject **items;
29 size_t new_allocated;
30 Py_ssize_t allocated = self->allocated;
Tim Peters65b8b842001-05-26 05:28:40 +000031
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000032 /* Bypass realloc() when a previous overallocation is large enough
33 to accommodate the newsize. If the newsize falls lower than half
34 the allocated size, then proceed with the realloc() to shrink the list.
35 */
36 if (allocated >= newsize && newsize >= (allocated >> 1)) {
37 assert(self->ob_item != NULL || newsize == 0);
38 Py_SIZE(self) = newsize;
39 return 0;
40 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +000041
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000042 /* This over-allocates proportional to the list size, making room
43 * for additional growth. The over-allocation is mild, but is
44 * enough to give linear-time amortized behavior over a long
45 * sequence of appends() in the presence of a poorly-performing
46 * system realloc().
47 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
48 */
49 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +000050
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000051 /* check for integer overflow */
52 if (new_allocated > PY_SIZE_MAX - newsize) {
53 PyErr_NoMemory();
54 return -1;
55 } else {
56 new_allocated += newsize;
57 }
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +000058
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000059 if (newsize == 0)
60 new_allocated = 0;
61 items = self->ob_item;
Mark Dickinsonc0420fd2011-09-19 19:18:37 +010062 if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000063 PyMem_RESIZE(items, PyObject *, new_allocated);
64 else
65 items = NULL;
66 if (items == NULL) {
67 PyErr_NoMemory();
68 return -1;
69 }
70 self->ob_item = items;
71 Py_SIZE(self) = newsize;
72 self->allocated = new_allocated;
73 return 0;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000074}
Guido van Rossuma46d51d1995-01-26 22:59:43 +000075
Christian Heimes77c02eb2008-02-09 02:18:51 +000076/* Debug statistic to compare allocations with reuse through the free list */
77#undef SHOW_ALLOC_COUNT
78#ifdef SHOW_ALLOC_COUNT
79static size_t count_alloc = 0;
80static size_t count_reuse = 0;
81
82static void
83show_alloc(void)
84{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000085 fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",
86 count_alloc);
87 fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T
88 "d\n", count_reuse);
89 fprintf(stderr, "%.2f%% reuse rate\n\n",
90 (100.0*count_reuse/(count_alloc+count_reuse)));
Christian Heimes77c02eb2008-02-09 02:18:51 +000091}
92#endif
93
Raymond Hettinger0468e412004-05-05 05:37:53 +000094/* Empty list reuse scheme to save calls to malloc and free */
Christian Heimes2202f872008-02-06 14:31:34 +000095#ifndef PyList_MAXFREELIST
96#define PyList_MAXFREELIST 80
97#endif
98static PyListObject *free_list[PyList_MAXFREELIST];
99static int numfree = 0;
Raymond Hettinger0468e412004-05-05 05:37:53 +0000100
Antoine Pitrou9a812cb2011-11-15 00:00:12 +0100101int
102PyList_ClearFreeList(void)
Raymond Hettingerfb09f0e2004-10-07 03:58:07 +0000103{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000104 PyListObject *op;
Antoine Pitrou9a812cb2011-11-15 00:00:12 +0100105 int ret = numfree;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000106 while (numfree) {
107 op = free_list[--numfree];
108 assert(PyList_CheckExact(op));
109 PyObject_GC_Del(op);
110 }
Antoine Pitrou9a812cb2011-11-15 00:00:12 +0100111 return ret;
112}
113
114void
115PyList_Fini(void)
116{
117 PyList_ClearFreeList();
Raymond Hettingerfb09f0e2004-10-07 03:58:07 +0000118}
119
David Malcolm49526f42012-06-22 14:55:41 -0400120/* Print summary info about the state of the optimized allocator */
121void
122_PyList_DebugMallocStats(FILE *out)
123{
124 _PyDebugAllocatorStats(out,
125 "free PyListObject",
126 numfree, sizeof(PyListObject));
127}
128
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000129PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000130PyList_New(Py_ssize_t size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000131{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000132 PyListObject *op;
133 size_t nbytes;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000134#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000135 static int initialized = 0;
136 if (!initialized) {
137 Py_AtExit(show_alloc);
138 initialized = 1;
139 }
Christian Heimes77c02eb2008-02-09 02:18:51 +0000140#endif
Tim Peters3986d4e2004-07-29 02:28:42 +0000141
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000142 if (size < 0) {
143 PyErr_BadInternalCall();
144 return NULL;
145 }
146 /* Check for overflow without an actual overflow,
147 * which can cause compiler to optimise out */
148 if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
149 return PyErr_NoMemory();
150 nbytes = size * sizeof(PyObject *);
151 if (numfree) {
152 numfree--;
153 op = free_list[numfree];
154 _Py_NewReference((PyObject *)op);
Christian Heimes77c02eb2008-02-09 02:18:51 +0000155#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000156 count_reuse++;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000157#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000158 } else {
159 op = PyObject_GC_New(PyListObject, &PyList_Type);
160 if (op == NULL)
161 return NULL;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000162#ifdef SHOW_ALLOC_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000163 count_alloc++;
Christian Heimes77c02eb2008-02-09 02:18:51 +0000164#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000165 }
166 if (size <= 0)
167 op->ob_item = NULL;
168 else {
169 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
170 if (op->ob_item == NULL) {
171 Py_DECREF(op);
172 return PyErr_NoMemory();
173 }
174 memset(op->ob_item, 0, nbytes);
175 }
176 Py_SIZE(op) = size;
177 op->allocated = size;
178 _PyObject_GC_TRACK(op);
179 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000180}
181
Martin v. Löwis18e16552006-02-15 17:27:45 +0000182Py_ssize_t
Fred Drakea2f55112000-07-09 15:16:51 +0000183PyList_Size(PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000184{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000185 if (!PyList_Check(op)) {
186 PyErr_BadInternalCall();
187 return -1;
188 }
189 else
190 return Py_SIZE(op);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000191}
192
Raymond Hettingerfdfe6182004-05-05 06:28:16 +0000193static PyObject *indexerr = NULL;
Guido van Rossum929f1b81996-08-09 20:51:27 +0000194
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000195PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000196PyList_GetItem(PyObject *op, Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000197{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000198 if (!PyList_Check(op)) {
199 PyErr_BadInternalCall();
200 return NULL;
201 }
202 if (i < 0 || i >= Py_SIZE(op)) {
203 if (indexerr == NULL) {
204 indexerr = PyUnicode_FromString(
205 "list index out of range");
206 if (indexerr == NULL)
207 return NULL;
208 }
209 PyErr_SetObject(PyExc_IndexError, indexerr);
210 return NULL;
211 }
212 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000213}
214
215int
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200216PyList_SetItem(PyObject *op, Py_ssize_t i,
217 PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000218{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +0200219 PyObject *olditem;
220 PyObject **p;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000221 if (!PyList_Check(op)) {
222 Py_XDECREF(newitem);
223 PyErr_BadInternalCall();
224 return -1;
225 }
226 if (i < 0 || i >= Py_SIZE(op)) {
227 Py_XDECREF(newitem);
228 PyErr_SetString(PyExc_IndexError,
229 "list assignment index out of range");
230 return -1;
231 }
232 p = ((PyListObject *)op) -> ob_item + i;
233 olditem = *p;
234 *p = newitem;
235 Py_XDECREF(olditem);
236 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000237}
238
239static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000240ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000241{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000242 Py_ssize_t i, n = Py_SIZE(self);
243 PyObject **items;
244 if (v == NULL) {
245 PyErr_BadInternalCall();
246 return -1;
247 }
248 if (n == PY_SSIZE_T_MAX) {
249 PyErr_SetString(PyExc_OverflowError,
250 "cannot add more objects to list");
251 return -1;
252 }
Tim Petersb38e2b62004-07-29 02:29:26 +0000253
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000254 if (list_resize(self, n+1) == -1)
255 return -1;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000256
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000257 if (where < 0) {
258 where += n;
259 if (where < 0)
260 where = 0;
261 }
262 if (where > n)
263 where = n;
264 items = self->ob_item;
265 for (i = n; --i >= where; )
266 items[i+1] = items[i];
267 Py_INCREF(v);
268 items[where] = v;
269 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000270}
271
272int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000273PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000274{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000275 if (!PyList_Check(op)) {
276 PyErr_BadInternalCall();
277 return -1;
278 }
279 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000280}
281
Raymond Hettinger40a03822004-04-12 13:05:09 +0000282static int
283app1(PyListObject *self, PyObject *v)
284{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000285 Py_ssize_t n = PyList_GET_SIZE(self);
Raymond Hettinger40a03822004-04-12 13:05:09 +0000286
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000287 assert (v != NULL);
288 if (n == PY_SSIZE_T_MAX) {
289 PyErr_SetString(PyExc_OverflowError,
290 "cannot add more objects to list");
291 return -1;
292 }
Raymond Hettinger40a03822004-04-12 13:05:09 +0000293
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000294 if (list_resize(self, n+1) == -1)
295 return -1;
Raymond Hettinger40a03822004-04-12 13:05:09 +0000296
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000297 Py_INCREF(v);
298 PyList_SET_ITEM(self, n, v);
299 return 0;
Raymond Hettinger40a03822004-04-12 13:05:09 +0000300}
301
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000302int
Fred Drakea2f55112000-07-09 15:16:51 +0000303PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000304{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000305 if (PyList_Check(op) && (newitem != NULL))
306 return app1((PyListObject *)op, newitem);
307 PyErr_BadInternalCall();
308 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000309}
310
311/* Methods */
312
313static void
Fred Drakea2f55112000-07-09 15:16:51 +0000314list_dealloc(PyListObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000315{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000316 Py_ssize_t i;
317 PyObject_GC_UnTrack(op);
318 Py_TRASHCAN_SAFE_BEGIN(op)
319 if (op->ob_item != NULL) {
320 /* Do it backwards, for Christian Tismer.
321 There's a simple test case where somehow this reduces
322 thrashing when a *very* large list is created and
323 immediately deleted. */
324 i = Py_SIZE(op);
325 while (--i >= 0) {
326 Py_XDECREF(op->ob_item[i]);
327 }
328 PyMem_FREE(op->ob_item);
329 }
330 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
331 free_list[numfree++] = op;
332 else
333 Py_TYPE(op)->tp_free((PyObject *)op);
334 Py_TRASHCAN_SAFE_END(op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000335}
336
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000337static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000338list_repr(PyListObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000339{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000340 Py_ssize_t i;
Victor Stinner5c733472013-11-18 21:11:57 +0100341 PyObject *s;
Victor Stinner5c733472013-11-18 21:11:57 +0100342 _PyUnicodeWriter writer;
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200343
344 if (Py_SIZE(v) == 0) {
345 return PyUnicode_FromString("[]");
346 }
347
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000348 i = Py_ReprEnter((PyObject*)v);
349 if (i != 0) {
350 return i > 0 ? PyUnicode_FromString("[...]") : NULL;
351 }
Tim Petersa7259592001-06-16 05:11:17 +0000352
Victor Stinner5c733472013-11-18 21:11:57 +0100353 _PyUnicodeWriter_Init(&writer);
354 writer.overallocate = 1;
Victor Stinnerb8fb1972013-11-18 22:15:44 +0100355 /* "[" + "1" + ", 2" * (len - 1) + "]" */
356 writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
Tim Petersa7259592001-06-16 05:11:17 +0000357
Victor Stinner5c733472013-11-18 21:11:57 +0100358 if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200359 goto error;
Tim Petersa7259592001-06-16 05:11:17 +0000360
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000361 /* Do repr() on each element. Note that this may mutate the list,
362 so must refetch the list size on each iteration. */
363 for (i = 0; i < Py_SIZE(v); ++i) {
Victor Stinner5c733472013-11-18 21:11:57 +0100364 if (i > 0) {
Victor Stinner4a587072013-11-19 12:54:53 +0100365 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
Victor Stinner5c733472013-11-18 21:11:57 +0100366 goto error;
367 }
368
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000369 if (Py_EnterRecursiveCall(" while getting the repr of a list"))
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200370 goto error;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000371 s = PyObject_Repr(v->ob_item[i]);
372 Py_LeaveRecursiveCall();
Victor Stinner5c733472013-11-18 21:11:57 +0100373 if (s == NULL)
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200374 goto error;
Victor Stinner5c733472013-11-18 21:11:57 +0100375
376 if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
377 Py_DECREF(s);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200378 goto error;
Victor Stinner5c733472013-11-18 21:11:57 +0100379 }
380 Py_DECREF(s);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000381 }
Victor Stinner5c733472013-11-18 21:11:57 +0100382
Victor Stinner4d3f1092013-11-19 12:09:00 +0100383 writer.overallocate = 0;
Victor Stinner5c733472013-11-18 21:11:57 +0100384 if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200385 goto error;
Tim Petersa7259592001-06-16 05:11:17 +0000386
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000387 Py_ReprLeave((PyObject *)v);
Victor Stinner5c733472013-11-18 21:11:57 +0100388 return _PyUnicodeWriter_Finish(&writer);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200389
390error:
Victor Stinner5c733472013-11-18 21:11:57 +0100391 _PyUnicodeWriter_Dealloc(&writer);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200392 Py_ReprLeave((PyObject *)v);
393 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000394}
395
Martin v. Löwis18e16552006-02-15 17:27:45 +0000396static Py_ssize_t
Fred Drakea2f55112000-07-09 15:16:51 +0000397list_length(PyListObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000398{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000399 return Py_SIZE(a);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000400}
401
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000402static int
Fred Drakea2f55112000-07-09 15:16:51 +0000403list_contains(PyListObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000404{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000405 Py_ssize_t i;
406 int cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000407
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000408 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
409 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
410 Py_EQ);
411 return cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000412}
413
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000414static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000415list_item(PyListObject *a, Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000416{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000417 if (i < 0 || i >= Py_SIZE(a)) {
418 if (indexerr == NULL) {
419 indexerr = PyUnicode_FromString(
420 "list index out of range");
421 if (indexerr == NULL)
422 return NULL;
423 }
424 PyErr_SetObject(PyExc_IndexError, indexerr);
425 return NULL;
426 }
427 Py_INCREF(a->ob_item[i]);
428 return a->ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000429}
430
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000431static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000432list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000433{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000434 PyListObject *np;
435 PyObject **src, **dest;
436 Py_ssize_t i, len;
437 if (ilow < 0)
438 ilow = 0;
439 else if (ilow > Py_SIZE(a))
440 ilow = Py_SIZE(a);
441 if (ihigh < ilow)
442 ihigh = ilow;
443 else if (ihigh > Py_SIZE(a))
444 ihigh = Py_SIZE(a);
445 len = ihigh - ilow;
446 np = (PyListObject *) PyList_New(len);
447 if (np == NULL)
448 return NULL;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000449
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000450 src = a->ob_item + ilow;
451 dest = np->ob_item;
452 for (i = 0; i < len; i++) {
453 PyObject *v = src[i];
454 Py_INCREF(v);
455 dest[i] = v;
456 }
457 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000458}
459
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000460PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000461PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Guido van Rossum234f9421993-06-17 12:35:49 +0000462{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000463 if (!PyList_Check(a)) {
464 PyErr_BadInternalCall();
465 return NULL;
466 }
467 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000468}
469
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000470static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000471list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000472{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000473 Py_ssize_t size;
474 Py_ssize_t i;
475 PyObject **src, **dest;
476 PyListObject *np;
477 if (!PyList_Check(bb)) {
478 PyErr_Format(PyExc_TypeError,
479 "can only concatenate list (not \"%.200s\") to list",
480 bb->ob_type->tp_name);
481 return NULL;
482 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000483#define b ((PyListObject *)bb)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000484 size = Py_SIZE(a) + Py_SIZE(b);
485 if (size < 0)
486 return PyErr_NoMemory();
487 np = (PyListObject *) PyList_New(size);
488 if (np == NULL) {
489 return NULL;
490 }
491 src = a->ob_item;
492 dest = np->ob_item;
493 for (i = 0; i < Py_SIZE(a); i++) {
494 PyObject *v = src[i];
495 Py_INCREF(v);
496 dest[i] = v;
497 }
498 src = b->ob_item;
499 dest = np->ob_item + Py_SIZE(a);
500 for (i = 0; i < Py_SIZE(b); i++) {
501 PyObject *v = src[i];
502 Py_INCREF(v);
503 dest[i] = v;
504 }
505 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000506#undef b
507}
508
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000509static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000510list_repeat(PyListObject *a, Py_ssize_t n)
Guido van Rossumed98d481991-03-06 13:07:53 +0000511{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000512 Py_ssize_t i, j;
513 Py_ssize_t size;
514 PyListObject *np;
515 PyObject **p, **items;
516 PyObject *elem;
517 if (n < 0)
518 n = 0;
Mark Dickinsonc0420fd2011-09-19 19:18:37 +0100519 if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000520 return PyErr_NoMemory();
Mark Dickinsonc0420fd2011-09-19 19:18:37 +0100521 size = Py_SIZE(a) * n;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000522 if (size == 0)
523 return PyList_New(0);
524 np = (PyListObject *) PyList_New(size);
525 if (np == NULL)
526 return NULL;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000527
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000528 items = np->ob_item;
529 if (Py_SIZE(a) == 1) {
530 elem = a->ob_item[0];
531 for (i = 0; i < n; i++) {
532 items[i] = elem;
533 Py_INCREF(elem);
534 }
535 return (PyObject *) np;
536 }
537 p = np->ob_item;
538 items = a->ob_item;
539 for (i = 0; i < n; i++) {
540 for (j = 0; j < Py_SIZE(a); j++) {
541 *p = items[j];
542 Py_INCREF(*p);
543 p++;
544 }
545 }
546 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000547}
548
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000549static int
Armin Rigo93677f02004-07-29 12:40:23 +0000550list_clear(PyListObject *a)
551{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000552 Py_ssize_t i;
553 PyObject **item = a->ob_item;
554 if (item != NULL) {
555 /* Because XDECREF can recursively invoke operations on
556 this list, we make it empty first. */
557 i = Py_SIZE(a);
558 Py_SIZE(a) = 0;
559 a->ob_item = NULL;
560 a->allocated = 0;
561 while (--i >= 0) {
562 Py_XDECREF(item[i]);
563 }
564 PyMem_FREE(item);
565 }
566 /* Never fails; the return value can be ignored.
567 Note that there is no guarantee that the list is actually empty
568 at this point, because XDECREF may have populated it again! */
569 return 0;
Armin Rigo93677f02004-07-29 12:40:23 +0000570}
571
Tim Peters8fc4a912004-07-31 21:53:19 +0000572/* a[ilow:ihigh] = v if v != NULL.
573 * del a[ilow:ihigh] if v == NULL.
574 *
575 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
576 * guaranteed the call cannot fail.
577 */
Armin Rigo93677f02004-07-29 12:40:23 +0000578static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000579list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000580{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000581 /* Because [X]DECREF can recursively invoke list operations on
582 this list, we must postpone all [X]DECREF activity until
583 after the list is back in its canonical shape. Therefore
584 we must allocate an additional array, 'recycle', into which
585 we temporarily copy the items that are deleted from the
586 list. :-( */
587 PyObject *recycle_on_stack[8];
588 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
589 PyObject **item;
590 PyObject **vitem = NULL;
591 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
592 Py_ssize_t n; /* # of elements in replacement list */
593 Py_ssize_t norig; /* # of elements in list getting replaced */
594 Py_ssize_t d; /* Change in size */
595 Py_ssize_t k;
596 size_t s;
597 int result = -1; /* guilty until proved innocent */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000598#define b ((PyListObject *)v)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000599 if (v == NULL)
600 n = 0;
601 else {
602 if (a == b) {
603 /* Special case "a[i:j] = a" -- copy b first */
604 v = list_slice(b, 0, Py_SIZE(b));
605 if (v == NULL)
606 return result;
607 result = list_ass_slice(a, ilow, ihigh, v);
608 Py_DECREF(v);
609 return result;
610 }
611 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
612 if(v_as_SF == NULL)
613 goto Error;
614 n = PySequence_Fast_GET_SIZE(v_as_SF);
615 vitem = PySequence_Fast_ITEMS(v_as_SF);
616 }
617 if (ilow < 0)
618 ilow = 0;
619 else if (ilow > Py_SIZE(a))
620 ilow = Py_SIZE(a);
Tim Peters8d9eb102004-07-31 02:24:20 +0000621
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000622 if (ihigh < ilow)
623 ihigh = ilow;
624 else if (ihigh > Py_SIZE(a))
625 ihigh = Py_SIZE(a);
Armin Rigo93677f02004-07-29 12:40:23 +0000626
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000627 norig = ihigh - ilow;
628 assert(norig >= 0);
629 d = n - norig;
630 if (Py_SIZE(a) + d == 0) {
631 Py_XDECREF(v_as_SF);
632 return list_clear(a);
633 }
634 item = a->ob_item;
635 /* recycle the items that we are about to remove */
636 s = norig * sizeof(PyObject *);
Benjamin Peterson5a7d9232016-09-06 17:58:25 -0700637 /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */
638 if (s) {
639 if (s > sizeof(recycle_on_stack)) {
640 recycle = (PyObject **)PyMem_MALLOC(s);
641 if (recycle == NULL) {
642 PyErr_NoMemory();
643 goto Error;
644 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000645 }
Benjamin Peterson5a7d9232016-09-06 17:58:25 -0700646 memcpy(recycle, &item[ilow], s);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000647 }
Tim Peters8d9eb102004-07-31 02:24:20 +0000648
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000649 if (d < 0) { /* Delete -d items */
Victor Stinner2c40f642013-07-19 23:06:21 +0200650 Py_ssize_t tail;
651 tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
652 memmove(&item[ihigh+d], &item[ihigh], tail);
653 if (list_resize(a, Py_SIZE(a) + d) < 0) {
654 memmove(&item[ihigh], &item[ihigh+d], tail);
655 memcpy(&item[ilow], recycle, s);
656 goto Error;
657 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000658 item = a->ob_item;
659 }
660 else if (d > 0) { /* Insert d items */
661 k = Py_SIZE(a);
662 if (list_resize(a, k+d) < 0)
663 goto Error;
664 item = a->ob_item;
665 memmove(&item[ihigh+d], &item[ihigh],
666 (k - ihigh)*sizeof(PyObject *));
667 }
668 for (k = 0; k < n; k++, ilow++) {
669 PyObject *w = vitem[k];
670 Py_XINCREF(w);
671 item[ilow] = w;
672 }
673 for (k = norig - 1; k >= 0; --k)
674 Py_XDECREF(recycle[k]);
675 result = 0;
Tim Peters8d9eb102004-07-31 02:24:20 +0000676 Error:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000677 if (recycle != recycle_on_stack)
678 PyMem_FREE(recycle);
679 Py_XDECREF(v_as_SF);
680 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000681#undef b
682}
683
Guido van Rossum234f9421993-06-17 12:35:49 +0000684int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000685PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
Guido van Rossum234f9421993-06-17 12:35:49 +0000686{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000687 if (!PyList_Check(a)) {
688 PyErr_BadInternalCall();
689 return -1;
690 }
691 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000692}
693
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000694static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000695list_inplace_repeat(PyListObject *self, Py_ssize_t n)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000696{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000697 PyObject **items;
698 Py_ssize_t size, i, j, p;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000699
700
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000701 size = PyList_GET_SIZE(self);
702 if (size == 0 || n == 1) {
703 Py_INCREF(self);
704 return (PyObject *)self;
705 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000706
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000707 if (n < 1) {
708 (void)list_clear(self);
709 Py_INCREF(self);
710 return (PyObject *)self;
711 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000712
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000713 if (size > PY_SSIZE_T_MAX / n) {
714 return PyErr_NoMemory();
715 }
Christian Heimesaf98da12008-01-27 15:18:18 +0000716
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000717 if (list_resize(self, size*n) == -1)
718 return NULL;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000719
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000720 p = size;
721 items = self->ob_item;
722 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
723 for (j = 0; j < size; j++) {
724 PyObject *o = items[j];
725 Py_INCREF(o);
726 items[p++] = o;
727 }
728 }
729 Py_INCREF(self);
730 return (PyObject *)self;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000731}
732
Guido van Rossum4a450d01991-04-03 19:05:18 +0000733static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000734list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
Guido van Rossum4a450d01991-04-03 19:05:18 +0000735{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000736 PyObject *old_value;
737 if (i < 0 || i >= Py_SIZE(a)) {
738 PyErr_SetString(PyExc_IndexError,
739 "list assignment index out of range");
740 return -1;
741 }
742 if (v == NULL)
743 return list_ass_slice(a, i, i+1, v);
744 Py_INCREF(v);
745 old_value = a->ob_item[i];
746 a->ob_item[i] = v;
747 Py_DECREF(old_value);
748 return 0;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000749}
750
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000751static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000752listinsert(PyListObject *self, PyObject *args)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000753{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000754 Py_ssize_t i;
755 PyObject *v;
756 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
757 return NULL;
758 if (ins1(self, i, v) == 0)
759 Py_RETURN_NONE;
760 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000761}
762
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000763static PyObject *
Eli Benderskycbbaa962011-02-25 05:47:53 +0000764listclear(PyListObject *self)
765{
766 list_clear(self);
767 Py_RETURN_NONE;
768}
769
770static PyObject *
771listcopy(PyListObject *self)
772{
773 return list_slice(self, 0, Py_SIZE(self));
774}
775
776static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000777listappend(PyListObject *self, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000778{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000779 if (app1(self, v) == 0)
780 Py_RETURN_NONE;
781 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000782}
783
Barry Warsawdedf6d61998-10-09 16:37:25 +0000784static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000785listextend(PyListObject *self, PyObject *b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000786{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000787 PyObject *it; /* iter(v) */
788 Py_ssize_t m; /* size of self */
789 Py_ssize_t n; /* guess for size of b */
790 Py_ssize_t mn; /* m + n */
791 Py_ssize_t i;
792 PyObject *(*iternext)(PyObject *);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000793
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000794 /* Special cases:
795 1) lists and tuples which can use PySequence_Fast ops
796 2) extending self to self requires making a copy first
797 */
798 if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
799 PyObject **src, **dest;
800 b = PySequence_Fast(b, "argument must be iterable");
801 if (!b)
802 return NULL;
803 n = PySequence_Fast_GET_SIZE(b);
804 if (n == 0) {
805 /* short circuit when b is empty */
806 Py_DECREF(b);
807 Py_RETURN_NONE;
808 }
809 m = Py_SIZE(self);
810 if (list_resize(self, m + n) == -1) {
811 Py_DECREF(b);
812 return NULL;
813 }
814 /* note that we may still have self == b here for the
815 * situation a.extend(a), but the following code works
816 * in that case too. Just make sure to resize self
817 * before calling PySequence_Fast_ITEMS.
818 */
819 /* populate the end of self with b's items */
820 src = PySequence_Fast_ITEMS(b);
821 dest = self->ob_item + m;
822 for (i = 0; i < n; i++) {
823 PyObject *o = src[i];
824 Py_INCREF(o);
825 dest[i] = o;
826 }
827 Py_DECREF(b);
828 Py_RETURN_NONE;
829 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000830
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000831 it = PyObject_GetIter(b);
832 if (it == NULL)
833 return NULL;
834 iternext = *it->ob_type->tp_iternext;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000835
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000836 /* Guess a result list size. */
Armin Ronacheraa9a79d2012-10-06 14:03:24 +0200837 n = PyObject_LengthHint(b, 8);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000838 if (n == -1) {
839 Py_DECREF(it);
840 return NULL;
841 }
842 m = Py_SIZE(self);
843 mn = m + n;
844 if (mn >= m) {
845 /* Make room. */
846 if (list_resize(self, mn) == -1)
847 goto error;
848 /* Make the list sane again. */
849 Py_SIZE(self) = m;
850 }
851 /* Else m + n overflowed; on the chance that n lied, and there really
852 * is enough room, ignore it. If n was telling the truth, we'll
853 * eventually run out of memory during the loop.
854 */
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000855
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000856 /* Run iterator to exhaustion. */
857 for (;;) {
858 PyObject *item = iternext(it);
859 if (item == NULL) {
860 if (PyErr_Occurred()) {
861 if (PyErr_ExceptionMatches(PyExc_StopIteration))
862 PyErr_Clear();
863 else
864 goto error;
865 }
866 break;
867 }
868 if (Py_SIZE(self) < self->allocated) {
869 /* steals ref */
870 PyList_SET_ITEM(self, Py_SIZE(self), item);
871 ++Py_SIZE(self);
872 }
873 else {
874 int status = app1(self, item);
875 Py_DECREF(item); /* append creates a new ref */
876 if (status < 0)
877 goto error;
878 }
879 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000880
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000881 /* Cut back result list if initial guess was too large. */
Victor Stinner32fd6ea2013-07-16 21:45:58 +0200882 if (Py_SIZE(self) < self->allocated) {
883 if (list_resize(self, Py_SIZE(self)) < 0)
884 goto error;
885 }
Raymond Hettingeraa241e02004-09-26 19:24:20 +0000886
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000887 Py_DECREF(it);
888 Py_RETURN_NONE;
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000889
890 error:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000891 Py_DECREF(it);
892 return NULL;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000893}
894
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000895PyObject *
896_PyList_Extend(PyListObject *self, PyObject *b)
897{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000898 return listextend(self, b);
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000899}
900
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000901static PyObject *
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000902list_inplace_concat(PyListObject *self, PyObject *other)
903{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000904 PyObject *result;
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000905
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000906 result = listextend(self, other);
907 if (result == NULL)
908 return result;
909 Py_DECREF(result);
910 Py_INCREF(self);
911 return (PyObject *)self;
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000912}
913
914static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000915listpop(PyListObject *self, PyObject *args)
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000916{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000917 Py_ssize_t i = -1;
918 PyObject *v;
919 int status;
Raymond Hettinger9eb86b32004-02-17 11:36:16 +0000920
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000921 if (!PyArg_ParseTuple(args, "|n:pop", &i))
922 return NULL;
Thomas Wouters89f507f2006-12-13 04:49:30 +0000923
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000924 if (Py_SIZE(self) == 0) {
925 /* Special-case most common failure cause */
926 PyErr_SetString(PyExc_IndexError, "pop from empty list");
927 return NULL;
928 }
929 if (i < 0)
930 i += Py_SIZE(self);
931 if (i < 0 || i >= Py_SIZE(self)) {
932 PyErr_SetString(PyExc_IndexError, "pop index out of range");
933 return NULL;
934 }
935 v = self->ob_item[i];
936 if (i == Py_SIZE(self) - 1) {
937 status = list_resize(self, Py_SIZE(self) - 1);
Victor Stinnerb27cd3e2013-07-08 22:20:44 +0200938 if (status >= 0)
939 return v; /* and v now owns the reference the list had */
940 else
941 return NULL;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000942 }
943 Py_INCREF(v);
944 status = list_ass_slice(self, i, i+1, (PyObject *)NULL);
Victor Stinner095d99f2013-07-17 21:58:01 +0200945 if (status < 0) {
946 Py_DECREF(v);
947 return NULL;
948 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000949 return v;
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000950}
951
Tim Peters8e2e7ca2002-07-19 02:33:08 +0000952/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
953static void
954reverse_slice(PyObject **lo, PyObject **hi)
955{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000956 assert(lo && hi);
Tim Peters8e2e7ca2002-07-19 02:33:08 +0000957
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000958 --hi;
959 while (lo < hi) {
960 PyObject *t = *lo;
961 *lo = *hi;
962 *hi = t;
963 ++lo;
964 --hi;
965 }
Tim Peters8e2e7ca2002-07-19 02:33:08 +0000966}
967
Tim Petersa64dc242002-08-01 02:13:36 +0000968/* Lots of code for an adaptive, stable, natural mergesort. There are many
969 * pieces to this algorithm; read listsort.txt for overviews and details.
970 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000971
Daniel Stutzbach98338222010-12-02 21:55:33 +0000972/* A sortslice contains a pointer to an array of keys and a pointer to
973 * an array of corresponding values. In other words, keys[i]
974 * corresponds with values[i]. If values == NULL, then the keys are
975 * also the values.
976 *
977 * Several convenience routines are provided here, so that keys and
978 * values are always moved in sync.
979 */
980
981typedef struct {
982 PyObject **keys;
983 PyObject **values;
984} sortslice;
985
986Py_LOCAL_INLINE(void)
987sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
988{
989 s1->keys[i] = s2->keys[j];
990 if (s1->values != NULL)
991 s1->values[i] = s2->values[j];
992}
993
994Py_LOCAL_INLINE(void)
Benjamin Peterson9efdcca2010-12-03 01:44:10 +0000995sortslice_copy_incr(sortslice *dst, sortslice *src)
996{
Daniel Stutzbach98338222010-12-02 21:55:33 +0000997 *dst->keys++ = *src->keys++;
998 if (dst->values != NULL)
999 *dst->values++ = *src->values++;
1000}
1001
1002Py_LOCAL_INLINE(void)
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001003sortslice_copy_decr(sortslice *dst, sortslice *src)
1004{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001005 *dst->keys-- = *src->keys--;
1006 if (dst->values != NULL)
1007 *dst->values-- = *src->values--;
1008}
1009
1010
1011Py_LOCAL_INLINE(void)
1012sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001013 Py_ssize_t n)
1014{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001015 memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1016 if (s1->values != NULL)
1017 memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1018}
1019
1020Py_LOCAL_INLINE(void)
1021sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001022 Py_ssize_t n)
1023{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001024 memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
1025 if (s1->values != NULL)
1026 memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
1027}
1028
1029Py_LOCAL_INLINE(void)
Benjamin Peterson9efdcca2010-12-03 01:44:10 +00001030sortslice_advance(sortslice *slice, Py_ssize_t n)
1031{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001032 slice->keys += n;
1033 if (slice->values != NULL)
1034 slice->values += n;
1035}
1036
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001037/* Comparison function: PyObject_RichCompareBool with Py_LT.
Tim Petersa64dc242002-08-01 02:13:36 +00001038 * Returns -1 on error, 1 if x < y, 0 if x >= y.
1039 */
Guido van Rossum3f236de1996-12-10 23:55:39 +00001040
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001041#define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT))
Tim Peters66860f62002-08-04 17:47:26 +00001042
1043/* Compare X to Y via "<". Goto "fail" if the comparison raises an
Tim Petersa8c974c2002-07-19 03:30:57 +00001044 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
1045 started. It makes more sense in context <wink>. X and Y are PyObject*s.
1046*/
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001047#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001048 if (k)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001049
1050/* binarysort is the best method for sorting small arrays: it does
1051 few compares, but can do data movement quadratic in the number of
1052 elements.
Guido van Rossum42812581998-06-17 14:15:44 +00001053 [lo, hi) is a contiguous slice of a list, and is sorted via
Tim Petersa8c974c2002-07-19 03:30:57 +00001054 binary insertion. This sort is stable.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001055 On entry, must have lo <= start <= hi, and that [lo, start) is already
1056 sorted (pass start == lo if you don't know!).
Tim Petersa8c974c2002-07-19 03:30:57 +00001057 If islt() complains return -1, else 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001058 Even in case of error, the output slice will be some permutation of
1059 the input (nothing is lost or duplicated).
1060*/
Guido van Rossum3f236de1996-12-10 23:55:39 +00001061static int
Daniel Stutzbach98338222010-12-02 21:55:33 +00001062binarysort(sortslice lo, PyObject **hi, PyObject **start)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001063{
Antoine Pitrou9ed5f272013-08-13 20:18:52 +02001064 Py_ssize_t k;
1065 PyObject **l, **p, **r;
1066 PyObject *pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001067
Daniel Stutzbach98338222010-12-02 21:55:33 +00001068 assert(lo.keys <= start && start <= hi);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001069 /* assert [lo, start) is sorted */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001070 if (lo.keys == start)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001071 ++start;
1072 for (; start < hi; ++start) {
1073 /* set l to where *start belongs */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001074 l = lo.keys;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001075 r = start;
1076 pivot = *r;
1077 /* Invariants:
1078 * pivot >= all in [lo, l).
1079 * pivot < all in [r, start).
1080 * The second is vacuously true at the start.
1081 */
1082 assert(l < r);
1083 do {
1084 p = l + ((r - l) >> 1);
1085 IFLT(pivot, *p)
1086 r = p;
1087 else
1088 l = p+1;
1089 } while (l < r);
1090 assert(l == r);
1091 /* The invariants still hold, so pivot >= all in [lo, l) and
1092 pivot < all in [l, start), so pivot belongs at l. Note
1093 that if there are elements equal to pivot, l points to the
1094 first slot after them -- that's why this sort is stable.
1095 Slide over to make room.
1096 Caution: using memmove is much slower under MSVC 5;
1097 we're not usually moving many slots. */
1098 for (p = start; p > l; --p)
1099 *p = *(p-1);
1100 *l = pivot;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001101 if (lo.values != NULL) {
1102 Py_ssize_t offset = lo.values - lo.keys;
1103 p = start + offset;
1104 pivot = *p;
1105 l += offset;
1106 for (p = start + offset; p > l; --p)
1107 *p = *(p-1);
1108 *l = pivot;
1109 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001110 }
1111 return 0;
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001112
1113 fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001114 return -1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001115}
1116
Tim Petersa64dc242002-08-01 02:13:36 +00001117/*
1118Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
1119is required on entry. "A run" is the longest ascending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001120
Tim Petersa64dc242002-08-01 02:13:36 +00001121 lo[0] <= lo[1] <= lo[2] <= ...
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001122
Tim Petersa64dc242002-08-01 02:13:36 +00001123or the longest descending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001124
Tim Petersa64dc242002-08-01 02:13:36 +00001125 lo[0] > lo[1] > lo[2] > ...
Tim Peters3b01a122002-07-19 02:35:45 +00001126
Tim Petersa64dc242002-08-01 02:13:36 +00001127Boolean *descending is set to 0 in the former case, or to 1 in the latter.
1128For its intended use in a stable mergesort, the strictness of the defn of
1129"descending" is needed so that the caller can safely reverse a descending
1130sequence without violating stability (strict > ensures there are no equal
1131elements to get out of order).
1132
1133Returns -1 in case of error.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001134*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001135static Py_ssize_t
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001136count_run(PyObject **lo, PyObject **hi, int *descending)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001137{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001138 Py_ssize_t k;
1139 Py_ssize_t n;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001140
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001141 assert(lo < hi);
1142 *descending = 0;
1143 ++lo;
1144 if (lo == hi)
1145 return 1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001146
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001147 n = 2;
1148 IFLT(*lo, *(lo-1)) {
1149 *descending = 1;
1150 for (lo = lo+1; lo < hi; ++lo, ++n) {
1151 IFLT(*lo, *(lo-1))
1152 ;
1153 else
1154 break;
1155 }
1156 }
1157 else {
1158 for (lo = lo+1; lo < hi; ++lo, ++n) {
1159 IFLT(*lo, *(lo-1))
1160 break;
1161 }
1162 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001163
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001164 return n;
Tim Petersa64dc242002-08-01 02:13:36 +00001165fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001166 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001167}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001168
Tim Petersa64dc242002-08-01 02:13:36 +00001169/*
1170Locate the proper position of key in a sorted vector; if the vector contains
1171an element equal to key, return the position immediately to the left of
1172the leftmost equal element. [gallop_right() does the same except returns
1173the position to the right of the rightmost equal element (if any).]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001174
Tim Petersa64dc242002-08-01 02:13:36 +00001175"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001176
Tim Petersa64dc242002-08-01 02:13:36 +00001177"hint" is an index at which to begin the search, 0 <= hint < n. The closer
1178hint is to the final result, the faster this runs.
1179
1180The return value is the int k in 0..n such that
1181
1182 a[k-1] < key <= a[k]
1183
1184pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1185key belongs at index k; or, IOW, the first k elements of a should precede
1186key, and the last n-k should follow key.
1187
1188Returns -1 on error. See listsort.txt for info on the method.
1189*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001190static Py_ssize_t
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001191gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
Tim Petersa64dc242002-08-01 02:13:36 +00001192{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001193 Py_ssize_t ofs;
1194 Py_ssize_t lastofs;
1195 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001196
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001197 assert(key && a && n > 0 && hint >= 0 && hint < n);
Tim Petersa64dc242002-08-01 02:13:36 +00001198
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001199 a += hint;
1200 lastofs = 0;
1201 ofs = 1;
1202 IFLT(*a, key) {
1203 /* a[hint] < key -- gallop right, until
1204 * a[hint + lastofs] < key <= a[hint + ofs]
1205 */
1206 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1207 while (ofs < maxofs) {
1208 IFLT(a[ofs], key) {
1209 lastofs = ofs;
1210 ofs = (ofs << 1) + 1;
1211 if (ofs <= 0) /* int overflow */
1212 ofs = maxofs;
1213 }
1214 else /* key <= a[hint + ofs] */
1215 break;
1216 }
1217 if (ofs > maxofs)
1218 ofs = maxofs;
1219 /* Translate back to offsets relative to &a[0]. */
1220 lastofs += hint;
1221 ofs += hint;
1222 }
1223 else {
1224 /* key <= a[hint] -- gallop left, until
1225 * a[hint - ofs] < key <= a[hint - lastofs]
1226 */
1227 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1228 while (ofs < maxofs) {
1229 IFLT(*(a-ofs), key)
1230 break;
1231 /* key <= a[hint - ofs] */
1232 lastofs = ofs;
1233 ofs = (ofs << 1) + 1;
1234 if (ofs <= 0) /* int overflow */
1235 ofs = maxofs;
1236 }
1237 if (ofs > maxofs)
1238 ofs = maxofs;
1239 /* Translate back to positive offsets relative to &a[0]. */
1240 k = lastofs;
1241 lastofs = hint - ofs;
1242 ofs = hint - k;
1243 }
1244 a -= hint;
Tim Petersa64dc242002-08-01 02:13:36 +00001245
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001246 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1247 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1248 * right of lastofs but no farther right than ofs. Do a binary
1249 * search, with invariant a[lastofs-1] < key <= a[ofs].
1250 */
1251 ++lastofs;
1252 while (lastofs < ofs) {
1253 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001254
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001255 IFLT(a[m], key)
1256 lastofs = m+1; /* a[m] < key */
1257 else
1258 ofs = m; /* key <= a[m] */
1259 }
1260 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1261 return ofs;
Tim Petersa64dc242002-08-01 02:13:36 +00001262
1263fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001264 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001265}
1266
1267/*
1268Exactly like gallop_left(), except that if key already exists in a[0:n],
1269finds the position immediately to the right of the rightmost equal value.
1270
1271The return value is the int k in 0..n such that
1272
1273 a[k-1] <= key < a[k]
1274
1275or -1 if error.
1276
1277The code duplication is massive, but this is enough different given that
1278we're sticking to "<" comparisons that it's much harder to follow if
1279written as one routine with yet another "left or right?" flag.
1280*/
Martin v. Löwis18e16552006-02-15 17:27:45 +00001281static Py_ssize_t
Raymond Hettinger70b64fc2008-01-30 20:15:17 +00001282gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
Tim Petersa64dc242002-08-01 02:13:36 +00001283{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001284 Py_ssize_t ofs;
1285 Py_ssize_t lastofs;
1286 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001287
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001288 assert(key && a && n > 0 && hint >= 0 && hint < n);
Tim Petersa64dc242002-08-01 02:13:36 +00001289
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001290 a += hint;
1291 lastofs = 0;
1292 ofs = 1;
1293 IFLT(key, *a) {
1294 /* key < a[hint] -- gallop left, until
1295 * a[hint - ofs] <= key < a[hint - lastofs]
1296 */
1297 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
1298 while (ofs < maxofs) {
1299 IFLT(key, *(a-ofs)) {
1300 lastofs = ofs;
1301 ofs = (ofs << 1) + 1;
1302 if (ofs <= 0) /* int overflow */
1303 ofs = maxofs;
1304 }
1305 else /* a[hint - ofs] <= key */
1306 break;
1307 }
1308 if (ofs > maxofs)
1309 ofs = maxofs;
1310 /* Translate back to positive offsets relative to &a[0]. */
1311 k = lastofs;
1312 lastofs = hint - ofs;
1313 ofs = hint - k;
1314 }
1315 else {
1316 /* a[hint] <= key -- gallop right, until
1317 * a[hint + lastofs] <= key < a[hint + ofs]
1318 */
1319 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
1320 while (ofs < maxofs) {
1321 IFLT(key, a[ofs])
1322 break;
1323 /* a[hint + ofs] <= key */
1324 lastofs = ofs;
1325 ofs = (ofs << 1) + 1;
1326 if (ofs <= 0) /* int overflow */
1327 ofs = maxofs;
1328 }
1329 if (ofs > maxofs)
1330 ofs = maxofs;
1331 /* Translate back to offsets relative to &a[0]. */
1332 lastofs += hint;
1333 ofs += hint;
1334 }
1335 a -= hint;
Tim Petersa64dc242002-08-01 02:13:36 +00001336
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001337 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1338 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1339 * right of lastofs but no farther right than ofs. Do a binary
1340 * search, with invariant a[lastofs-1] <= key < a[ofs].
1341 */
1342 ++lastofs;
1343 while (lastofs < ofs) {
1344 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001345
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001346 IFLT(key, a[m])
1347 ofs = m; /* key < a[m] */
1348 else
1349 lastofs = m+1; /* a[m] <= key */
1350 }
1351 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1352 return ofs;
Tim Petersa64dc242002-08-01 02:13:36 +00001353
1354fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001355 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001356}
1357
1358/* The maximum number of entries in a MergeState's pending-runs stack.
1359 * This is enough to sort arrays of size up to about
1360 * 32 * phi ** MAX_MERGE_PENDING
1361 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1362 * with 2**64 elements.
1363 */
1364#define MAX_MERGE_PENDING 85
1365
Tim Peterse05f65a2002-08-10 05:21:15 +00001366/* When we get into galloping mode, we stay there until both runs win less
1367 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
Tim Petersa64dc242002-08-01 02:13:36 +00001368 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001369#define MIN_GALLOP 7
Tim Petersa64dc242002-08-01 02:13:36 +00001370
1371/* Avoid malloc for small temp arrays. */
1372#define MERGESTATE_TEMP_SIZE 256
1373
1374/* One MergeState exists on the stack per invocation of mergesort. It's just
1375 * a convenient way to pass state around among the helper functions.
1376 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001377struct s_slice {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001378 sortslice base;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001379 Py_ssize_t len;
Tim Peterse05f65a2002-08-10 05:21:15 +00001380};
1381
Tim Petersa64dc242002-08-01 02:13:36 +00001382typedef struct s_MergeState {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001383 /* This controls when we get *into* galloping mode. It's initialized
1384 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1385 * random data, and lower for highly structured data.
1386 */
1387 Py_ssize_t min_gallop;
Tim Peterse05f65a2002-08-10 05:21:15 +00001388
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001389 /* 'a' is temp storage to help with merges. It contains room for
1390 * alloced entries.
1391 */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001392 sortslice a; /* may point to temparray below */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001393 Py_ssize_t alloced;
Tim Petersa64dc242002-08-01 02:13:36 +00001394
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001395 /* A stack of n pending runs yet to be merged. Run #i starts at
1396 * address base[i] and extends for len[i] elements. It's always
1397 * true (so long as the indices are in bounds) that
1398 *
1399 * pending[i].base + pending[i].len == pending[i+1].base
1400 *
1401 * so we could cut the storage for this, but it's a minor amount,
1402 * and keeping all the info explicit simplifies the code.
1403 */
1404 int n;
1405 struct s_slice pending[MAX_MERGE_PENDING];
Tim Petersa64dc242002-08-01 02:13:36 +00001406
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001407 /* 'a' points to this when possible, rather than muck with malloc. */
1408 PyObject *temparray[MERGESTATE_TEMP_SIZE];
Tim Petersa64dc242002-08-01 02:13:36 +00001409} MergeState;
1410
1411/* Conceptually a MergeState's constructor. */
1412static void
Victor Stinner0fcab4a2011-01-04 12:59:15 +00001413merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc)
Tim Petersa64dc242002-08-01 02:13:36 +00001414{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001415 assert(ms != NULL);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001416 if (has_keyfunc) {
1417 /* The temporary space for merging will need at most half the list
1418 * size rounded up. Use the minimum possible space so we can use the
1419 * rest of temparray for other things. In particular, if there is
1420 * enough extra space, listsort() will use it to store the keys.
1421 */
1422 ms->alloced = (list_size + 1) / 2;
1423
1424 /* ms->alloced describes how many keys will be stored at
1425 ms->temparray, but we also need to store the values. Hence,
1426 ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
1427 if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
1428 ms->alloced = MERGESTATE_TEMP_SIZE / 2;
1429 ms->a.values = &ms->temparray[ms->alloced];
1430 }
1431 else {
1432 ms->alloced = MERGESTATE_TEMP_SIZE;
1433 ms->a.values = NULL;
1434 }
1435 ms->a.keys = ms->temparray;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001436 ms->n = 0;
1437 ms->min_gallop = MIN_GALLOP;
Tim Petersa64dc242002-08-01 02:13:36 +00001438}
1439
1440/* Free all the temp memory owned by the MergeState. This must be called
1441 * when you're done with a MergeState, and may be called before then if
1442 * you want to free the temp memory early.
1443 */
1444static void
1445merge_freemem(MergeState *ms)
1446{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001447 assert(ms != NULL);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001448 if (ms->a.keys != ms->temparray)
1449 PyMem_Free(ms->a.keys);
Tim Petersa64dc242002-08-01 02:13:36 +00001450}
1451
1452/* Ensure enough temp memory for 'need' array slots is available.
1453 * Returns 0 on success and -1 if the memory can't be gotten.
1454 */
1455static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001456merge_getmem(MergeState *ms, Py_ssize_t need)
Tim Petersa64dc242002-08-01 02:13:36 +00001457{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001458 int multiplier;
1459
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001460 assert(ms != NULL);
1461 if (need <= ms->alloced)
1462 return 0;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001463
1464 multiplier = ms->a.values != NULL ? 2 : 1;
1465
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001466 /* Don't realloc! That can cost cycles to copy the old data, but
1467 * we don't care what's in the block.
1468 */
1469 merge_freemem(ms);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001470 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001471 PyErr_NoMemory();
1472 return -1;
1473 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001474 ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need
1475 * sizeof(PyObject *));
1476 if (ms->a.keys != NULL) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001477 ms->alloced = need;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001478 if (ms->a.values != NULL)
1479 ms->a.values = &ms->a.keys[need];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001480 return 0;
1481 }
1482 PyErr_NoMemory();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001483 return -1;
Tim Petersa64dc242002-08-01 02:13:36 +00001484}
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001485#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1486 merge_getmem(MS, NEED))
Tim Petersa64dc242002-08-01 02:13:36 +00001487
Daniel Stutzbach98338222010-12-02 21:55:33 +00001488/* Merge the na elements starting at ssa with the nb elements starting at
1489 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
1490 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
1491 * should have na <= nb. See listsort.txt for more info. Return 0 if
1492 * successful, -1 if error.
Tim Petersa64dc242002-08-01 02:13:36 +00001493 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001494static Py_ssize_t
Daniel Stutzbach98338222010-12-02 21:55:33 +00001495merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
1496 sortslice ssb, Py_ssize_t nb)
Tim Petersa64dc242002-08-01 02:13:36 +00001497{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001498 Py_ssize_t k;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001499 sortslice dest;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001500 int result = -1; /* guilty until proved innocent */
1501 Py_ssize_t min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001502
Daniel Stutzbach98338222010-12-02 21:55:33 +00001503 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1504 assert(ssa.keys + na == ssb.keys);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001505 if (MERGE_GETMEM(ms, na) < 0)
1506 return -1;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001507 sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
1508 dest = ssa;
1509 ssa = ms->a;
Tim Petersa64dc242002-08-01 02:13:36 +00001510
Daniel Stutzbach98338222010-12-02 21:55:33 +00001511 sortslice_copy_incr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001512 --nb;
1513 if (nb == 0)
1514 goto Succeed;
1515 if (na == 1)
1516 goto CopyB;
Tim Petersa64dc242002-08-01 02:13:36 +00001517
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001518 min_gallop = ms->min_gallop;
1519 for (;;) {
1520 Py_ssize_t acount = 0; /* # of times A won in a row */
1521 Py_ssize_t bcount = 0; /* # of times B won in a row */
Tim Petersa64dc242002-08-01 02:13:36 +00001522
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001523 /* Do the straightforward thing until (if ever) one run
1524 * appears to win consistently.
1525 */
1526 for (;;) {
1527 assert(na > 1 && nb > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001528 k = ISLT(ssb.keys[0], ssa.keys[0]);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001529 if (k) {
1530 if (k < 0)
1531 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001532 sortslice_copy_incr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001533 ++bcount;
1534 acount = 0;
1535 --nb;
1536 if (nb == 0)
1537 goto Succeed;
1538 if (bcount >= min_gallop)
1539 break;
1540 }
1541 else {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001542 sortslice_copy_incr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001543 ++acount;
1544 bcount = 0;
1545 --na;
1546 if (na == 1)
1547 goto CopyB;
1548 if (acount >= min_gallop)
1549 break;
1550 }
1551 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001552
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001553 /* One run is winning so consistently that galloping may
1554 * be a huge win. So try that, and continue galloping until
1555 * (if ever) neither run appears to be winning consistently
1556 * anymore.
1557 */
1558 ++min_gallop;
1559 do {
1560 assert(na > 1 && nb > 0);
1561 min_gallop -= min_gallop > 1;
1562 ms->min_gallop = min_gallop;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001563 k = gallop_right(ssb.keys[0], ssa.keys, na, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001564 acount = k;
1565 if (k) {
1566 if (k < 0)
1567 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001568 sortslice_memcpy(&dest, 0, &ssa, 0, k);
1569 sortslice_advance(&dest, k);
1570 sortslice_advance(&ssa, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001571 na -= k;
1572 if (na == 1)
1573 goto CopyB;
1574 /* na==0 is impossible now if the comparison
1575 * function is consistent, but we can't assume
1576 * that it is.
1577 */
1578 if (na == 0)
1579 goto Succeed;
1580 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001581 sortslice_copy_incr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001582 --nb;
1583 if (nb == 0)
1584 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001585
Daniel Stutzbach98338222010-12-02 21:55:33 +00001586 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001587 bcount = k;
1588 if (k) {
1589 if (k < 0)
1590 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001591 sortslice_memmove(&dest, 0, &ssb, 0, k);
1592 sortslice_advance(&dest, k);
1593 sortslice_advance(&ssb, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001594 nb -= k;
1595 if (nb == 0)
1596 goto Succeed;
1597 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001598 sortslice_copy_incr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001599 --na;
1600 if (na == 1)
1601 goto CopyB;
1602 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1603 ++min_gallop; /* penalize it for leaving galloping mode */
1604 ms->min_gallop = min_gallop;
1605 }
Tim Petersa64dc242002-08-01 02:13:36 +00001606Succeed:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001607 result = 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001608Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001609 if (na)
Daniel Stutzbach98338222010-12-02 21:55:33 +00001610 sortslice_memcpy(&dest, 0, &ssa, 0, na);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001611 return result;
Tim Petersa64dc242002-08-01 02:13:36 +00001612CopyB:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001613 assert(na == 1 && nb > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001614 /* The last element of ssa belongs at the end of the merge. */
1615 sortslice_memmove(&dest, 0, &ssb, 0, nb);
1616 sortslice_copy(&dest, nb, &ssa, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001617 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001618}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001619
Daniel Stutzbach98338222010-12-02 21:55:33 +00001620/* Merge the na elements starting at pa with the nb elements starting at
1621 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
1622 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
1623 * should have na >= nb. See listsort.txt for more info. Return 0 if
1624 * successful, -1 if error.
Tim Petersa64dc242002-08-01 02:13:36 +00001625 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001626static Py_ssize_t
Daniel Stutzbach98338222010-12-02 21:55:33 +00001627merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
1628 sortslice ssb, Py_ssize_t nb)
Tim Petersa64dc242002-08-01 02:13:36 +00001629{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001630 Py_ssize_t k;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001631 sortslice dest, basea, baseb;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001632 int result = -1; /* guilty until proved innocent */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001633 Py_ssize_t min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001634
Daniel Stutzbach98338222010-12-02 21:55:33 +00001635 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
1636 assert(ssa.keys + na == ssb.keys);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001637 if (MERGE_GETMEM(ms, nb) < 0)
1638 return -1;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001639 dest = ssb;
1640 sortslice_advance(&dest, nb-1);
1641 sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
1642 basea = ssa;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001643 baseb = ms->a;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001644 ssb.keys = ms->a.keys + nb - 1;
1645 if (ssb.values != NULL)
1646 ssb.values = ms->a.values + nb - 1;
1647 sortslice_advance(&ssa, na - 1);
Tim Petersa64dc242002-08-01 02:13:36 +00001648
Daniel Stutzbach98338222010-12-02 21:55:33 +00001649 sortslice_copy_decr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001650 --na;
1651 if (na == 0)
1652 goto Succeed;
1653 if (nb == 1)
1654 goto CopyA;
Tim Petersa64dc242002-08-01 02:13:36 +00001655
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001656 min_gallop = ms->min_gallop;
1657 for (;;) {
1658 Py_ssize_t acount = 0; /* # of times A won in a row */
1659 Py_ssize_t bcount = 0; /* # of times B won in a row */
Tim Petersa64dc242002-08-01 02:13:36 +00001660
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001661 /* Do the straightforward thing until (if ever) one run
1662 * appears to win consistently.
1663 */
1664 for (;;) {
1665 assert(na > 0 && nb > 1);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001666 k = ISLT(ssb.keys[0], ssa.keys[0]);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001667 if (k) {
1668 if (k < 0)
1669 goto Fail;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001670 sortslice_copy_decr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001671 ++acount;
1672 bcount = 0;
1673 --na;
1674 if (na == 0)
1675 goto Succeed;
1676 if (acount >= min_gallop)
1677 break;
1678 }
1679 else {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001680 sortslice_copy_decr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001681 ++bcount;
1682 acount = 0;
1683 --nb;
1684 if (nb == 1)
1685 goto CopyA;
1686 if (bcount >= min_gallop)
1687 break;
1688 }
1689 }
Tim Petersa64dc242002-08-01 02:13:36 +00001690
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001691 /* One run is winning so consistently that galloping may
1692 * be a huge win. So try that, and continue galloping until
1693 * (if ever) neither run appears to be winning consistently
1694 * anymore.
1695 */
1696 ++min_gallop;
1697 do {
1698 assert(na > 0 && nb > 1);
1699 min_gallop -= min_gallop > 1;
1700 ms->min_gallop = min_gallop;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001701 k = gallop_right(ssb.keys[0], basea.keys, na, na-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001702 if (k < 0)
1703 goto Fail;
1704 k = na - k;
1705 acount = k;
1706 if (k) {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001707 sortslice_advance(&dest, -k);
1708 sortslice_advance(&ssa, -k);
1709 sortslice_memmove(&dest, 1, &ssa, 1, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001710 na -= k;
1711 if (na == 0)
1712 goto Succeed;
1713 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001714 sortslice_copy_decr(&dest, &ssb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001715 --nb;
1716 if (nb == 1)
1717 goto CopyA;
Tim Petersa64dc242002-08-01 02:13:36 +00001718
Daniel Stutzbach98338222010-12-02 21:55:33 +00001719 k = gallop_left(ssa.keys[0], baseb.keys, nb, nb-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001720 if (k < 0)
1721 goto Fail;
1722 k = nb - k;
1723 bcount = k;
1724 if (k) {
Daniel Stutzbach98338222010-12-02 21:55:33 +00001725 sortslice_advance(&dest, -k);
1726 sortslice_advance(&ssb, -k);
1727 sortslice_memcpy(&dest, 1, &ssb, 1, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001728 nb -= k;
1729 if (nb == 1)
1730 goto CopyA;
1731 /* nb==0 is impossible now if the comparison
1732 * function is consistent, but we can't assume
1733 * that it is.
1734 */
1735 if (nb == 0)
1736 goto Succeed;
1737 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001738 sortslice_copy_decr(&dest, &ssa);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001739 --na;
1740 if (na == 0)
1741 goto Succeed;
1742 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1743 ++min_gallop; /* penalize it for leaving galloping mode */
1744 ms->min_gallop = min_gallop;
1745 }
Tim Petersa64dc242002-08-01 02:13:36 +00001746Succeed:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001747 result = 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001748Fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001749 if (nb)
Daniel Stutzbach98338222010-12-02 21:55:33 +00001750 sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001751 return result;
Tim Petersa64dc242002-08-01 02:13:36 +00001752CopyA:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001753 assert(nb == 1 && na > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001754 /* The first element of ssb belongs at the front of the merge. */
1755 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
1756 sortslice_advance(&dest, -na);
1757 sortslice_advance(&ssa, -na);
1758 sortslice_copy(&dest, 0, &ssb, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001759 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001760}
1761
1762/* Merge the two runs at stack indices i and i+1.
1763 * Returns 0 on success, -1 on error.
1764 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001765static Py_ssize_t
1766merge_at(MergeState *ms, Py_ssize_t i)
Tim Petersa64dc242002-08-01 02:13:36 +00001767{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001768 sortslice ssa, ssb;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001769 Py_ssize_t na, nb;
1770 Py_ssize_t k;
Tim Petersa64dc242002-08-01 02:13:36 +00001771
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001772 assert(ms != NULL);
1773 assert(ms->n >= 2);
1774 assert(i >= 0);
1775 assert(i == ms->n - 2 || i == ms->n - 3);
Tim Petersa64dc242002-08-01 02:13:36 +00001776
Daniel Stutzbach98338222010-12-02 21:55:33 +00001777 ssa = ms->pending[i].base;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001778 na = ms->pending[i].len;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001779 ssb = ms->pending[i+1].base;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001780 nb = ms->pending[i+1].len;
1781 assert(na > 0 && nb > 0);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001782 assert(ssa.keys + na == ssb.keys);
Tim Petersa64dc242002-08-01 02:13:36 +00001783
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001784 /* Record the length of the combined runs; if i is the 3rd-last
1785 * run now, also slide over the last run (which isn't involved
1786 * in this merge). The current run i+1 goes away in any case.
1787 */
1788 ms->pending[i].len = na + nb;
1789 if (i == ms->n - 3)
1790 ms->pending[i+1] = ms->pending[i+2];
1791 --ms->n;
Tim Petersa64dc242002-08-01 02:13:36 +00001792
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001793 /* Where does b start in a? Elements in a before that can be
1794 * ignored (already in place).
1795 */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001796 k = gallop_right(*ssb.keys, ssa.keys, na, 0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001797 if (k < 0)
1798 return -1;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001799 sortslice_advance(&ssa, k);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001800 na -= k;
1801 if (na == 0)
1802 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001803
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001804 /* Where does a end in b? Elements in b after that can be
1805 * ignored (already in place).
1806 */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001807 nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001808 if (nb <= 0)
1809 return nb;
Tim Petersa64dc242002-08-01 02:13:36 +00001810
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001811 /* Merge what remains of the runs, using a temp array with
1812 * min(na, nb) elements.
1813 */
1814 if (na <= nb)
Daniel Stutzbach98338222010-12-02 21:55:33 +00001815 return merge_lo(ms, ssa, na, ssb, nb);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001816 else
Daniel Stutzbach98338222010-12-02 21:55:33 +00001817 return merge_hi(ms, ssa, na, ssb, nb);
Tim Petersa64dc242002-08-01 02:13:36 +00001818}
1819
1820/* Examine the stack of runs waiting to be merged, merging adjacent runs
1821 * until the stack invariants are re-established:
1822 *
1823 * 1. len[-3] > len[-2] + len[-1]
1824 * 2. len[-2] > len[-1]
1825 *
1826 * See listsort.txt for more info.
1827 *
1828 * Returns 0 on success, -1 on error.
1829 */
1830static int
1831merge_collapse(MergeState *ms)
1832{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001833 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001834
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001835 assert(ms);
1836 while (ms->n > 1) {
1837 Py_ssize_t n = ms->n - 2;
Benjamin Petersonb808d592015-02-25 10:12:26 -05001838 if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) ||
1839 (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001840 if (p[n-1].len < p[n+1].len)
1841 --n;
1842 if (merge_at(ms, n) < 0)
1843 return -1;
1844 }
1845 else if (p[n].len <= p[n+1].len) {
1846 if (merge_at(ms, n) < 0)
1847 return -1;
1848 }
1849 else
1850 break;
1851 }
1852 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001853}
1854
1855/* Regardless of invariants, merge all runs on the stack until only one
1856 * remains. This is used at the end of the mergesort.
1857 *
1858 * Returns 0 on success, -1 on error.
1859 */
1860static int
1861merge_force_collapse(MergeState *ms)
1862{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001863 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001864
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001865 assert(ms);
1866 while (ms->n > 1) {
1867 Py_ssize_t n = ms->n - 2;
1868 if (n > 0 && p[n-1].len < p[n+1].len)
1869 --n;
1870 if (merge_at(ms, n) < 0)
1871 return -1;
1872 }
1873 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001874}
1875
1876/* Compute a good value for the minimum run length; natural runs shorter
1877 * than this are boosted artificially via binary insertion.
1878 *
1879 * If n < 64, return n (it's too small to bother with fancy stuff).
1880 * Else if n is an exact power of 2, return 32.
1881 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1882 * strictly less than, an exact power of 2.
1883 *
1884 * See listsort.txt for more info.
1885 */
Martin v. Löwis18e16552006-02-15 17:27:45 +00001886static Py_ssize_t
1887merge_compute_minrun(Py_ssize_t n)
Tim Petersa64dc242002-08-01 02:13:36 +00001888{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001889 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
Tim Petersa64dc242002-08-01 02:13:36 +00001890
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001891 assert(n >= 0);
1892 while (n >= 64) {
1893 r |= n & 1;
1894 n >>= 1;
1895 }
1896 return n + r;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001897}
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001898
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001899static void
Daniel Stutzbach98338222010-12-02 21:55:33 +00001900reverse_sortslice(sortslice *s, Py_ssize_t n)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001901{
Daniel Stutzbach98338222010-12-02 21:55:33 +00001902 reverse_slice(s->keys, &s->keys[n]);
1903 if (s->values != NULL)
1904 reverse_slice(s->values, &s->values[n]);
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001905}
1906
Tim Petersa64dc242002-08-01 02:13:36 +00001907/* An adaptive, stable, natural mergesort. See listsort.txt.
1908 * Returns Py_None on success, NULL on error. Even in case of error, the
1909 * list will be some permutation of its input state (nothing is lost or
1910 * duplicated).
1911 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001912static PyObject *
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001913listsort(PyListObject *self, PyObject *args, PyObject *kwds)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001914{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001915 MergeState ms;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001916 Py_ssize_t nremaining;
1917 Py_ssize_t minrun;
Daniel Stutzbach98338222010-12-02 21:55:33 +00001918 sortslice lo;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001919 Py_ssize_t saved_ob_size, saved_allocated;
1920 PyObject **saved_ob_item;
1921 PyObject **final_ob_item;
1922 PyObject *result = NULL; /* guilty until proved innocent */
1923 int reverse = 0;
1924 PyObject *keyfunc = NULL;
1925 Py_ssize_t i;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001926 static char *kwlist[] = {"key", "reverse", 0};
Daniel Stutzbach98338222010-12-02 21:55:33 +00001927 PyObject **keys;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001928
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001929 assert(self != NULL);
1930 assert (PyList_Check(self));
1931 if (args != NULL) {
1932 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort",
1933 kwlist, &keyfunc, &reverse))
1934 return NULL;
1935 if (Py_SIZE(args) > 0) {
1936 PyErr_SetString(PyExc_TypeError,
1937 "must use keyword argument for key function");
1938 return NULL;
1939 }
1940 }
1941 if (keyfunc == Py_None)
1942 keyfunc = NULL;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001943
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001944 /* The list is temporarily made empty, so that mutations performed
1945 * by comparison functions can't affect the slice of memory we're
1946 * sorting (allowing mutations during sorting is a core-dump
1947 * factory, since ob_item may change).
1948 */
1949 saved_ob_size = Py_SIZE(self);
1950 saved_ob_item = self->ob_item;
1951 saved_allocated = self->allocated;
1952 Py_SIZE(self) = 0;
1953 self->ob_item = NULL;
1954 self->allocated = -1; /* any operation will reset it to >= 0 */
Tim Peters330f9e92002-07-19 07:05:44 +00001955
Daniel Stutzbach98338222010-12-02 21:55:33 +00001956 if (keyfunc == NULL) {
1957 keys = NULL;
1958 lo.keys = saved_ob_item;
1959 lo.values = NULL;
1960 }
1961 else {
1962 if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
1963 /* Leverage stack space we allocated but won't otherwise use */
1964 keys = &ms.temparray[saved_ob_size+1];
1965 else {
1966 keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);
Benjamin Peterson0823ffb2015-04-23 17:04:36 -04001967 if (keys == NULL) {
1968 PyErr_NoMemory();
1969 goto keyfunc_fail;
1970 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001971 }
Daniel Stutzbach98338222010-12-02 21:55:33 +00001972
1973 for (i = 0; i < saved_ob_size ; i++) {
1974 keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i],
1975 NULL);
1976 if (keys[i] == NULL) {
1977 for (i=i-1 ; i>=0 ; i--)
1978 Py_DECREF(keys[i]);
Benjamin Peterson4a42cd42014-03-15 12:21:28 -05001979 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
Daniel Stutzbach8eda5f72011-03-02 23:37:50 +00001980 PyMem_FREE(keys);
Daniel Stutzbach98338222010-12-02 21:55:33 +00001981 goto keyfunc_fail;
1982 }
1983 }
1984
1985 lo.keys = keys;
1986 lo.values = saved_ob_item;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001987 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001988
Daniel Stutzbach98338222010-12-02 21:55:33 +00001989 merge_init(&ms, saved_ob_size, keys != NULL);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001990
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001991 nremaining = saved_ob_size;
1992 if (nremaining < 2)
1993 goto succeed;
Tim Peters330f9e92002-07-19 07:05:44 +00001994
Benjamin Peterson05380642010-08-23 19:35:39 +00001995 /* Reverse sort stability achieved by initially reversing the list,
1996 applying a stable forward sort, then reversing the final result. */
Daniel Stutzbach98338222010-12-02 21:55:33 +00001997 if (reverse) {
1998 if (keys != NULL)
1999 reverse_slice(&keys[0], &keys[saved_ob_size]);
2000 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
2001 }
Benjamin Peterson05380642010-08-23 19:35:39 +00002002
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002003 /* March over the array once, left to right, finding natural runs,
2004 * and extending short natural runs to minrun elements.
2005 */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002006 minrun = merge_compute_minrun(nremaining);
2007 do {
2008 int descending;
2009 Py_ssize_t n;
Tim Peters330f9e92002-07-19 07:05:44 +00002010
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002011 /* Identify next run. */
Daniel Stutzbach98338222010-12-02 21:55:33 +00002012 n = count_run(lo.keys, lo.keys + nremaining, &descending);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002013 if (n < 0)
2014 goto fail;
2015 if (descending)
Daniel Stutzbach98338222010-12-02 21:55:33 +00002016 reverse_sortslice(&lo, n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002017 /* If short, extend to min(minrun, nremaining). */
2018 if (n < minrun) {
2019 const Py_ssize_t force = nremaining <= minrun ?
2020 nremaining : minrun;
Daniel Stutzbach98338222010-12-02 21:55:33 +00002021 if (binarysort(lo, lo.keys + force, lo.keys + n) < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002022 goto fail;
2023 n = force;
2024 }
2025 /* Push run onto pending-runs stack, and maybe merge. */
2026 assert(ms.n < MAX_MERGE_PENDING);
2027 ms.pending[ms.n].base = lo;
2028 ms.pending[ms.n].len = n;
2029 ++ms.n;
2030 if (merge_collapse(&ms) < 0)
2031 goto fail;
2032 /* Advance to find next run. */
Daniel Stutzbach98338222010-12-02 21:55:33 +00002033 sortslice_advance(&lo, n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002034 nremaining -= n;
2035 } while (nremaining);
Tim Peters330f9e92002-07-19 07:05:44 +00002036
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002037 if (merge_force_collapse(&ms) < 0)
2038 goto fail;
2039 assert(ms.n == 1);
Daniel Stutzbach98338222010-12-02 21:55:33 +00002040 assert(keys == NULL
2041 ? ms.pending[0].base.keys == saved_ob_item
2042 : ms.pending[0].base.keys == &keys[0]);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002043 assert(ms.pending[0].len == saved_ob_size);
Daniel Stutzbach98338222010-12-02 21:55:33 +00002044 lo = ms.pending[0].base;
Tim Petersa64dc242002-08-01 02:13:36 +00002045
2046succeed:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002047 result = Py_None;
Tim Peters330f9e92002-07-19 07:05:44 +00002048fail:
Daniel Stutzbach98338222010-12-02 21:55:33 +00002049 if (keys != NULL) {
2050 for (i = 0; i < saved_ob_size; i++)
2051 Py_DECREF(keys[i]);
Benjamin Petersonef87f8c2014-03-14 21:54:31 -05002052 if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
Daniel Stutzbach98338222010-12-02 21:55:33 +00002053 PyMem_FREE(keys);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002054 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002055
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002056 if (self->allocated != -1 && result != NULL) {
2057 /* The user mucked with the list during the sort,
2058 * and we don't already have another error to report.
2059 */
2060 PyErr_SetString(PyExc_ValueError, "list modified during sort");
2061 result = NULL;
2062 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002063
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002064 if (reverse && saved_ob_size > 1)
2065 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002066
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002067 merge_freemem(&ms);
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002068
Daniel Stutzbach98338222010-12-02 21:55:33 +00002069keyfunc_fail:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002070 final_ob_item = self->ob_item;
2071 i = Py_SIZE(self);
2072 Py_SIZE(self) = saved_ob_size;
2073 self->ob_item = saved_ob_item;
2074 self->allocated = saved_allocated;
2075 if (final_ob_item != NULL) {
2076 /* we cannot use list_clear() for this because it does not
2077 guarantee that the list is really empty when it returns */
2078 while (--i >= 0) {
2079 Py_XDECREF(final_ob_item[i]);
2080 }
2081 PyMem_FREE(final_ob_item);
2082 }
2083 Py_XINCREF(result);
2084 return result;
Guido van Rossum3f236de1996-12-10 23:55:39 +00002085}
Tim Peters330f9e92002-07-19 07:05:44 +00002086#undef IFLT
Tim Peters66860f62002-08-04 17:47:26 +00002087#undef ISLT
Tim Peters330f9e92002-07-19 07:05:44 +00002088
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002089int
Fred Drakea2f55112000-07-09 15:16:51 +00002090PyList_Sort(PyObject *v)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002091{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002092 if (v == NULL || !PyList_Check(v)) {
2093 PyErr_BadInternalCall();
2094 return -1;
2095 }
2096 v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
2097 if (v == NULL)
2098 return -1;
2099 Py_DECREF(v);
2100 return 0;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002101}
2102
Guido van Rossumb86c5492001-02-12 22:06:02 +00002103static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002104listreverse(PyListObject *self)
Guido van Rossumb86c5492001-02-12 22:06:02 +00002105{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002106 if (Py_SIZE(self) > 1)
2107 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2108 Py_RETURN_NONE;
Guido van Rossumed98d481991-03-06 13:07:53 +00002109}
2110
Guido van Rossum84c76f51990-10-30 13:32:20 +00002111int
Fred Drakea2f55112000-07-09 15:16:51 +00002112PyList_Reverse(PyObject *v)
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002113{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002114 PyListObject *self = (PyListObject *)v;
Tim Peters6063e262002-08-08 01:06:39 +00002115
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002116 if (v == NULL || !PyList_Check(v)) {
2117 PyErr_BadInternalCall();
2118 return -1;
2119 }
2120 if (Py_SIZE(self) > 1)
2121 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
2122 return 0;
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002123}
2124
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002125PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00002126PyList_AsTuple(PyObject *v)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002127{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002128 PyObject *w;
2129 PyObject **p, **q;
2130 Py_ssize_t n;
2131 if (v == NULL || !PyList_Check(v)) {
2132 PyErr_BadInternalCall();
2133 return NULL;
2134 }
2135 n = Py_SIZE(v);
2136 w = PyTuple_New(n);
2137 if (w == NULL)
2138 return NULL;
2139 p = ((PyTupleObject *)w)->ob_item;
2140 q = ((PyListObject *)v)->ob_item;
2141 while (--n >= 0) {
2142 Py_INCREF(*q);
2143 *p = *q;
2144 p++;
2145 q++;
2146 }
2147 return w;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002148}
2149
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002150static PyObject *
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002151listindex(PyListObject *self, PyObject *args)
Guido van Rossumed98d481991-03-06 13:07:53 +00002152{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002153 Py_ssize_t i, start=0, stop=Py_SIZE(self);
Amaury Forgeot d'Arc864741b2011-11-06 15:10:48 +01002154 PyObject *v;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002155
Petri Lehtinenebfaabd2011-11-06 21:02:39 +02002156 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
2157 _PyEval_SliceIndex, &start,
2158 _PyEval_SliceIndex, &stop))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002159 return NULL;
2160 if (start < 0) {
2161 start += Py_SIZE(self);
2162 if (start < 0)
2163 start = 0;
2164 }
2165 if (stop < 0) {
2166 stop += Py_SIZE(self);
2167 if (stop < 0)
2168 stop = 0;
2169 }
2170 for (i = start; i < stop && i < Py_SIZE(self); i++) {
2171 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2172 if (cmp > 0)
2173 return PyLong_FromSsize_t(i);
2174 else if (cmp < 0)
2175 return NULL;
2176 }
Amaury Forgeot d'Arc864741b2011-11-06 15:10:48 +01002177 PyErr_Format(PyExc_ValueError, "%R is not in list", v);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002178 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002179}
2180
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002181static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002182listcount(PyListObject *self, PyObject *v)
Guido van Rossume6f7d181991-10-20 20:20:40 +00002183{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002184 Py_ssize_t count = 0;
2185 Py_ssize_t i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002186
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002187 for (i = 0; i < Py_SIZE(self); i++) {
2188 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2189 if (cmp > 0)
2190 count++;
2191 else if (cmp < 0)
2192 return NULL;
2193 }
2194 return PyLong_FromSsize_t(count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00002195}
2196
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002197static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002198listremove(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00002199{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002200 Py_ssize_t i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002201
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002202 for (i = 0; i < Py_SIZE(self); i++) {
2203 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2204 if (cmp > 0) {
2205 if (list_ass_slice(self, i, i+1,
2206 (PyObject *)NULL) == 0)
2207 Py_RETURN_NONE;
2208 return NULL;
2209 }
2210 else if (cmp < 0)
2211 return NULL;
2212 }
2213 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
2214 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002215}
2216
Jeremy Hylton8caad492000-06-23 14:18:11 +00002217static int
2218list_traverse(PyListObject *o, visitproc visit, void *arg)
2219{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002220 Py_ssize_t i;
Jeremy Hylton8caad492000-06-23 14:18:11 +00002221
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002222 for (i = Py_SIZE(o); --i >= 0; )
2223 Py_VISIT(o->ob_item[i]);
2224 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +00002225}
2226
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002227static PyObject *
2228list_richcompare(PyObject *v, PyObject *w, int op)
2229{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002230 PyListObject *vl, *wl;
2231 Py_ssize_t i;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002232
Brian Curtindfc80e32011-08-10 20:28:54 -05002233 if (!PyList_Check(v) || !PyList_Check(w))
2234 Py_RETURN_NOTIMPLEMENTED;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002235
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002236 vl = (PyListObject *)v;
2237 wl = (PyListObject *)w;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002238
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002239 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
2240 /* Shortcut: if the lengths differ, the lists differ */
2241 PyObject *res;
2242 if (op == Py_EQ)
2243 res = Py_False;
2244 else
2245 res = Py_True;
2246 Py_INCREF(res);
2247 return res;
2248 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002249
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002250 /* Search for the first index where items are different */
2251 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
2252 int k = PyObject_RichCompareBool(vl->ob_item[i],
2253 wl->ob_item[i], Py_EQ);
2254 if (k < 0)
2255 return NULL;
2256 if (!k)
2257 break;
2258 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002259
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002260 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
2261 /* No more items to compare -- compare sizes */
2262 Py_ssize_t vs = Py_SIZE(vl);
2263 Py_ssize_t ws = Py_SIZE(wl);
2264 int cmp;
2265 PyObject *res;
2266 switch (op) {
2267 case Py_LT: cmp = vs < ws; break;
2268 case Py_LE: cmp = vs <= ws; break;
2269 case Py_EQ: cmp = vs == ws; break;
2270 case Py_NE: cmp = vs != ws; break;
2271 case Py_GT: cmp = vs > ws; break;
2272 case Py_GE: cmp = vs >= ws; break;
2273 default: return NULL; /* cannot happen */
2274 }
2275 if (cmp)
2276 res = Py_True;
2277 else
2278 res = Py_False;
2279 Py_INCREF(res);
2280 return res;
2281 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002282
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002283 /* We have an item that differs -- shortcuts for EQ/NE */
2284 if (op == Py_EQ) {
2285 Py_INCREF(Py_False);
2286 return Py_False;
2287 }
2288 if (op == Py_NE) {
2289 Py_INCREF(Py_True);
2290 return Py_True;
2291 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002292
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002293 /* Compare the final item again using the proper operator */
2294 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002295}
2296
Tim Peters6d6c1a32001-08-02 04:15:00 +00002297static int
2298list_init(PyListObject *self, PyObject *args, PyObject *kw)
2299{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002300 PyObject *arg = NULL;
2301 static char *kwlist[] = {"sequence", 0};
Tim Peters6d6c1a32001-08-02 04:15:00 +00002302
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002303 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
2304 return -1;
Raymond Hettingerc0aaa2d2004-07-29 23:31:29 +00002305
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002306 /* Verify list invariants established by PyType_GenericAlloc() */
2307 assert(0 <= Py_SIZE(self));
2308 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
2309 assert(self->ob_item != NULL ||
2310 self->allocated == 0 || self->allocated == -1);
Raymond Hettingerc0aaa2d2004-07-29 23:31:29 +00002311
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002312 /* Empty previous contents */
2313 if (self->ob_item != NULL) {
2314 (void)list_clear(self);
2315 }
2316 if (arg != NULL) {
2317 PyObject *rv = listextend(self, arg);
2318 if (rv == NULL)
2319 return -1;
2320 Py_DECREF(rv);
2321 }
2322 return 0;
Tim Peters6d6c1a32001-08-02 04:15:00 +00002323}
2324
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002325static PyObject *
2326list_sizeof(PyListObject *self)
2327{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002328 Py_ssize_t res;
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002329
Serhiy Storchaka5c4064e2015-12-19 20:05:25 +02002330 res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002331 return PyLong_FromSsize_t(res);
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002332}
2333
Raymond Hettinger1021c442003-11-07 15:38:09 +00002334static PyObject *list_iter(PyObject *seq);
2335static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
2336
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002337PyDoc_STRVAR(getitem_doc,
2338"x.__getitem__(y) <==> x[y]");
Raymond Hettinger1021c442003-11-07 15:38:09 +00002339PyDoc_STRVAR(reversed_doc,
2340"L.__reversed__() -- return a reverse iterator over the list");
Martin v. Löwis00709aa2008-06-04 14:18:43 +00002341PyDoc_STRVAR(sizeof_doc,
2342"L.__sizeof__() -- size of L in memory, in bytes");
Eli Benderskycbbaa962011-02-25 05:47:53 +00002343PyDoc_STRVAR(clear_doc,
2344"L.clear() -> None -- remove all items from L");
2345PyDoc_STRVAR(copy_doc,
2346"L.copy() -> list -- a shallow copy of L");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002347PyDoc_STRVAR(append_doc,
Georg Brandl388349a2011-10-08 18:32:40 +02002348"L.append(object) -> None -- append object to end");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002349PyDoc_STRVAR(extend_doc,
Georg Brandl388349a2011-10-08 18:32:40 +02002350"L.extend(iterable) -> None -- extend list by appending elements from the iterable");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002351PyDoc_STRVAR(insert_doc,
2352"L.insert(index, object) -- insert object before index");
2353PyDoc_STRVAR(pop_doc,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002354"L.pop([index]) -> item -- remove and return item at index (default last).\n"
2355"Raises IndexError if list is empty or index is out of range.");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002356PyDoc_STRVAR(remove_doc,
Georg Brandl388349a2011-10-08 18:32:40 +02002357"L.remove(value) -> None -- remove first occurrence of value.\n"
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002358"Raises ValueError if the value is not present.");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002359PyDoc_STRVAR(index_doc,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +00002360"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
2361"Raises ValueError if the value is not present.");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002362PyDoc_STRVAR(count_doc,
2363"L.count(value) -> integer -- return number of occurrences of value");
2364PyDoc_STRVAR(reverse_doc,
2365"L.reverse() -- reverse *IN PLACE*");
2366PyDoc_STRVAR(sort_doc,
Georg Brandl388349a2011-10-08 18:32:40 +02002367"L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*");
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00002368
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002369static PyObject *list_subscript(PyListObject*, PyObject*);
2370
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002371static PyMethodDef list_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002372 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
2373 {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
2374 {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
Eli Benderskycbbaa962011-02-25 05:47:53 +00002375 {"clear", (PyCFunction)listclear, METH_NOARGS, clear_doc},
2376 {"copy", (PyCFunction)listcopy, METH_NOARGS, copy_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002377 {"append", (PyCFunction)listappend, METH_O, append_doc},
2378 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
Eli Benderskycbbaa962011-02-25 05:47:53 +00002379 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002380 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
2381 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
2382 {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
2383 {"count", (PyCFunction)listcount, METH_O, count_doc},
2384 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
2385 {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
2386 {NULL, NULL} /* sentinel */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002387};
2388
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002389static PySequenceMethods list_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002390 (lenfunc)list_length, /* sq_length */
2391 (binaryfunc)list_concat, /* sq_concat */
2392 (ssizeargfunc)list_repeat, /* sq_repeat */
2393 (ssizeargfunc)list_item, /* sq_item */
2394 0, /* sq_slice */
2395 (ssizeobjargproc)list_ass_item, /* sq_ass_item */
2396 0, /* sq_ass_slice */
2397 (objobjproc)list_contains, /* sq_contains */
2398 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
2399 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002400};
2401
Neal Norwitz2c2e8272002-06-14 02:04:18 +00002402PyDoc_STRVAR(list_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +00002403"list() -> new empty list\n"
2404"list(iterable) -> new list initialized from iterable's items");
Tim Peters6d6c1a32001-08-02 04:15:00 +00002405
Jeremy Hyltona4b4c3b2002-07-13 03:51:17 +00002406static PyObject *
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002407list_subscript(PyListObject* self, PyObject* item)
2408{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002409 if (PyIndex_Check(item)) {
2410 Py_ssize_t i;
2411 i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2412 if (i == -1 && PyErr_Occurred())
2413 return NULL;
2414 if (i < 0)
2415 i += PyList_GET_SIZE(self);
2416 return list_item(self, i);
2417 }
2418 else if (PySlice_Check(item)) {
2419 Py_ssize_t start, stop, step, slicelength, cur, i;
2420 PyObject* result;
2421 PyObject* it;
2422 PyObject **src, **dest;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002423
Martin v. Löwis4d0d4712010-12-03 20:14:31 +00002424 if (PySlice_GetIndicesEx(item, Py_SIZE(self),
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002425 &start, &stop, &step, &slicelength) < 0) {
2426 return NULL;
2427 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002428
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002429 if (slicelength <= 0) {
2430 return PyList_New(0);
2431 }
2432 else if (step == 1) {
2433 return list_slice(self, start, stop);
2434 }
2435 else {
2436 result = PyList_New(slicelength);
2437 if (!result) return NULL;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002438
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002439 src = self->ob_item;
2440 dest = ((PyListObject *)result)->ob_item;
2441 for (cur = start, i = 0; i < slicelength;
Mark Dickinsonc7d93b72011-09-25 15:34:32 +01002442 cur += (size_t)step, i++) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002443 it = src[cur];
2444 Py_INCREF(it);
2445 dest[i] = it;
2446 }
Tim Peters3b01a122002-07-19 02:35:45 +00002447
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002448 return result;
2449 }
2450 }
2451 else {
2452 PyErr_Format(PyExc_TypeError,
Terry Jan Reedyffff1442014-08-02 01:30:37 -04002453 "list indices must be integers or slices, not %.200s",
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002454 item->ob_type->tp_name);
2455 return NULL;
2456 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002457}
2458
Tim Peters3b01a122002-07-19 02:35:45 +00002459static int
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002460list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2461{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002462 if (PyIndex_Check(item)) {
2463 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
2464 if (i == -1 && PyErr_Occurred())
2465 return -1;
2466 if (i < 0)
2467 i += PyList_GET_SIZE(self);
2468 return list_ass_item(self, i, value);
2469 }
2470 else if (PySlice_Check(item)) {
2471 Py_ssize_t start, stop, step, slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002472
Martin v. Löwis4d0d4712010-12-03 20:14:31 +00002473 if (PySlice_GetIndicesEx(item, Py_SIZE(self),
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002474 &start, &stop, &step, &slicelength) < 0) {
2475 return -1;
2476 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002477
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002478 if (step == 1)
2479 return list_ass_slice(self, start, stop, value);
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002480
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002481 /* Make sure s[5:2] = [..] inserts at the right place:
2482 before 5, not before 2. */
2483 if ((step < 0 && start < stop) ||
2484 (step > 0 && start > stop))
2485 stop = start;
Thomas Woutersed03b412007-08-28 21:37:11 +00002486
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002487 if (value == NULL) {
2488 /* delete slice */
2489 PyObject **garbage;
2490 size_t cur;
2491 Py_ssize_t i;
Victor Stinner35f28032013-11-21 12:16:35 +01002492 int res;
Tim Peters3b01a122002-07-19 02:35:45 +00002493
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002494 if (slicelength <= 0)
2495 return 0;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002496
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002497 if (step < 0) {
2498 stop = start + 1;
2499 start = stop + step*(slicelength - 1) - 1;
2500 step = -step;
2501 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002502
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002503 assert((size_t)slicelength <=
2504 PY_SIZE_MAX / sizeof(PyObject*));
Amaury Forgeot d'Arc9c74b142008-06-18 00:47:36 +00002505
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002506 garbage = (PyObject**)
2507 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2508 if (!garbage) {
2509 PyErr_NoMemory();
2510 return -1;
2511 }
Tim Peters3b01a122002-07-19 02:35:45 +00002512
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002513 /* drawing pictures might help understand these for
2514 loops. Basically, we memmove the parts of the
2515 list that are *not* part of the slice: step-1
2516 items for each item that is part of the slice,
2517 and then tail end of the list that was not
2518 covered by the slice */
2519 for (cur = start, i = 0;
2520 cur < (size_t)stop;
2521 cur += step, i++) {
2522 Py_ssize_t lim = step - 1;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002523
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002524 garbage[i] = PyList_GET_ITEM(self, cur);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002525
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002526 if (cur + step >= (size_t)Py_SIZE(self)) {
2527 lim = Py_SIZE(self) - cur - 1;
2528 }
Michael W. Hudson56796f62002-07-29 14:35:04 +00002529
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002530 memmove(self->ob_item + cur - i,
2531 self->ob_item + cur + 1,
2532 lim * sizeof(PyObject *));
2533 }
Mark Dickinsonc7d93b72011-09-25 15:34:32 +01002534 cur = start + (size_t)slicelength * step;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002535 if (cur < (size_t)Py_SIZE(self)) {
2536 memmove(self->ob_item + cur - slicelength,
2537 self->ob_item + cur,
2538 (Py_SIZE(self) - cur) *
2539 sizeof(PyObject *));
2540 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002541
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002542 Py_SIZE(self) -= slicelength;
Victor Stinner35f28032013-11-21 12:16:35 +01002543 res = list_resize(self, Py_SIZE(self));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002544
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002545 for (i = 0; i < slicelength; i++) {
2546 Py_DECREF(garbage[i]);
2547 }
2548 PyMem_FREE(garbage);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002549
Victor Stinner35f28032013-11-21 12:16:35 +01002550 return res;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002551 }
2552 else {
2553 /* assign slice */
2554 PyObject *ins, *seq;
2555 PyObject **garbage, **seqitems, **selfitems;
2556 Py_ssize_t cur, i;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002557
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002558 /* protect against a[::-1] = a */
2559 if (self == (PyListObject*)value) {
2560 seq = list_slice((PyListObject*)value, 0,
2561 PyList_GET_SIZE(value));
2562 }
2563 else {
2564 seq = PySequence_Fast(value,
2565 "must assign iterable "
2566 "to extended slice");
2567 }
2568 if (!seq)
2569 return -1;
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002570
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002571 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2572 PyErr_Format(PyExc_ValueError,
2573 "attempt to assign sequence of "
2574 "size %zd to extended slice of "
2575 "size %zd",
2576 PySequence_Fast_GET_SIZE(seq),
2577 slicelength);
2578 Py_DECREF(seq);
2579 return -1;
2580 }
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002581
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002582 if (!slicelength) {
2583 Py_DECREF(seq);
2584 return 0;
2585 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002586
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002587 garbage = (PyObject**)
2588 PyMem_MALLOC(slicelength*sizeof(PyObject*));
2589 if (!garbage) {
2590 Py_DECREF(seq);
2591 PyErr_NoMemory();
2592 return -1;
2593 }
Tim Peters3b01a122002-07-19 02:35:45 +00002594
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002595 selfitems = self->ob_item;
2596 seqitems = PySequence_Fast_ITEMS(seq);
2597 for (cur = start, i = 0; i < slicelength;
Mark Dickinsonc7d93b72011-09-25 15:34:32 +01002598 cur += (size_t)step, i++) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002599 garbage[i] = selfitems[cur];
2600 ins = seqitems[i];
2601 Py_INCREF(ins);
2602 selfitems[cur] = ins;
2603 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002604
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002605 for (i = 0; i < slicelength; i++) {
2606 Py_DECREF(garbage[i]);
2607 }
Tim Peters3b01a122002-07-19 02:35:45 +00002608
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002609 PyMem_FREE(garbage);
2610 Py_DECREF(seq);
Tim Peters3b01a122002-07-19 02:35:45 +00002611
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002612 return 0;
2613 }
2614 }
2615 else {
2616 PyErr_Format(PyExc_TypeError,
Terry Jan Reedyffff1442014-08-02 01:30:37 -04002617 "list indices must be integers or slices, not %.200s",
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002618 item->ob_type->tp_name);
2619 return -1;
2620 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002621}
2622
2623static PyMappingMethods list_as_mapping = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002624 (lenfunc)list_length,
2625 (binaryfunc)list_subscript,
2626 (objobjargproc)list_ass_subscript
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002627};
2628
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002629PyTypeObject PyList_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002630 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2631 "list",
2632 sizeof(PyListObject),
2633 0,
2634 (destructor)list_dealloc, /* tp_dealloc */
2635 0, /* tp_print */
2636 0, /* tp_getattr */
2637 0, /* tp_setattr */
2638 0, /* tp_reserved */
2639 (reprfunc)list_repr, /* tp_repr */
2640 0, /* tp_as_number */
2641 &list_as_sequence, /* tp_as_sequence */
2642 &list_as_mapping, /* tp_as_mapping */
Georg Brandl00da4e02010-10-18 07:32:48 +00002643 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002644 0, /* tp_call */
2645 0, /* tp_str */
2646 PyObject_GenericGetAttr, /* tp_getattro */
2647 0, /* tp_setattro */
2648 0, /* tp_as_buffer */
2649 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2650 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
2651 list_doc, /* tp_doc */
2652 (traverseproc)list_traverse, /* tp_traverse */
2653 (inquiry)list_clear, /* tp_clear */
2654 list_richcompare, /* tp_richcompare */
2655 0, /* tp_weaklistoffset */
2656 list_iter, /* tp_iter */
2657 0, /* tp_iternext */
2658 list_methods, /* tp_methods */
2659 0, /* tp_members */
2660 0, /* tp_getset */
2661 0, /* tp_base */
2662 0, /* tp_dict */
2663 0, /* tp_descr_get */
2664 0, /* tp_descr_set */
2665 0, /* tp_dictoffset */
2666 (initproc)list_init, /* tp_init */
2667 PyType_GenericAlloc, /* tp_alloc */
2668 PyType_GenericNew, /* tp_new */
2669 PyObject_GC_Del, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002670};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002671
2672
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002673/*********************** List Iterator **************************/
2674
2675typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002676 PyObject_HEAD
Victor Stinner7660b882013-06-24 23:59:24 +02002677 Py_ssize_t it_index;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002678 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002679} listiterobject;
2680
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002681static PyObject *list_iter(PyObject *);
2682static void listiter_dealloc(listiterobject *);
2683static int listiter_traverse(listiterobject *, visitproc, void *);
2684static PyObject *listiter_next(listiterobject *);
2685static PyObject *listiter_len(listiterobject *);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002686static PyObject *listiter_reduce_general(void *_it, int forward);
2687static PyObject *listiter_reduce(listiterobject *);
2688static PyObject *listiter_setstate(listiterobject *, PyObject *state);
Raymond Hettinger435bf582004-03-18 22:43:10 +00002689
Armin Rigof5b3e362006-02-11 21:32:43 +00002690PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002691PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
2692PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00002693
2694static PyMethodDef listiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002695 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002696 {"__reduce__", (PyCFunction)listiter_reduce, METH_NOARGS, reduce_doc},
2697 {"__setstate__", (PyCFunction)listiter_setstate, METH_O, setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002698 {NULL, NULL} /* sentinel */
Raymond Hettinger435bf582004-03-18 22:43:10 +00002699};
2700
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002701PyTypeObject PyListIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002702 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2703 "list_iterator", /* tp_name */
2704 sizeof(listiterobject), /* tp_basicsize */
2705 0, /* tp_itemsize */
2706 /* methods */
2707 (destructor)listiter_dealloc, /* tp_dealloc */
2708 0, /* tp_print */
2709 0, /* tp_getattr */
2710 0, /* tp_setattr */
2711 0, /* tp_reserved */
2712 0, /* tp_repr */
2713 0, /* tp_as_number */
2714 0, /* tp_as_sequence */
2715 0, /* tp_as_mapping */
2716 0, /* tp_hash */
2717 0, /* tp_call */
2718 0, /* tp_str */
2719 PyObject_GenericGetAttr, /* tp_getattro */
2720 0, /* tp_setattro */
2721 0, /* tp_as_buffer */
2722 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2723 0, /* tp_doc */
2724 (traverseproc)listiter_traverse, /* tp_traverse */
2725 0, /* tp_clear */
2726 0, /* tp_richcompare */
2727 0, /* tp_weaklistoffset */
2728 PyObject_SelfIter, /* tp_iter */
2729 (iternextfunc)listiter_next, /* tp_iternext */
2730 listiter_methods, /* tp_methods */
2731 0, /* tp_members */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002732};
Raymond Hettinger1021c442003-11-07 15:38:09 +00002733
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002734
2735static PyObject *
2736list_iter(PyObject *seq)
2737{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002738 listiterobject *it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002739
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002740 if (!PyList_Check(seq)) {
2741 PyErr_BadInternalCall();
2742 return NULL;
2743 }
2744 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2745 if (it == NULL)
2746 return NULL;
2747 it->it_index = 0;
2748 Py_INCREF(seq);
2749 it->it_seq = (PyListObject *)seq;
2750 _PyObject_GC_TRACK(it);
2751 return (PyObject *)it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002752}
2753
2754static void
2755listiter_dealloc(listiterobject *it)
2756{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002757 _PyObject_GC_UNTRACK(it);
2758 Py_XDECREF(it->it_seq);
2759 PyObject_GC_Del(it);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002760}
2761
2762static int
2763listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2764{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002765 Py_VISIT(it->it_seq);
2766 return 0;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002767}
2768
2769static PyObject *
2770listiter_next(listiterobject *it)
2771{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002772 PyListObject *seq;
2773 PyObject *item;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002774
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002775 assert(it != NULL);
2776 seq = it->it_seq;
2777 if (seq == NULL)
2778 return NULL;
2779 assert(PyList_Check(seq));
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002780
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002781 if (it->it_index < PyList_GET_SIZE(seq)) {
2782 item = PyList_GET_ITEM(seq, it->it_index);
2783 ++it->it_index;
2784 Py_INCREF(item);
2785 return item;
2786 }
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002787
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002788 it->it_seq = NULL;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03002789 Py_DECREF(seq);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002790 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002791}
2792
2793static PyObject *
2794listiter_len(listiterobject *it)
2795{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002796 Py_ssize_t len;
2797 if (it->it_seq) {
2798 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
2799 if (len >= 0)
2800 return PyLong_FromSsize_t(len);
2801 }
2802 return PyLong_FromLong(0);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002803}
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002804
2805static PyObject *
2806listiter_reduce(listiterobject *it)
2807{
2808 return listiter_reduce_general(it, 1);
2809}
2810
2811static PyObject *
2812listiter_setstate(listiterobject *it, PyObject *state)
2813{
Victor Stinner7660b882013-06-24 23:59:24 +02002814 Py_ssize_t index = PyLong_AsSsize_t(state);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002815 if (index == -1 && PyErr_Occurred())
2816 return NULL;
2817 if (it->it_seq != NULL) {
2818 if (index < 0)
2819 index = 0;
Kristján Valur Jónsson25dded02014-03-05 13:47:57 +00002820 else if (index > PyList_GET_SIZE(it->it_seq))
2821 index = PyList_GET_SIZE(it->it_seq); /* iterator exhausted */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002822 it->it_index = index;
2823 }
2824 Py_RETURN_NONE;
2825}
2826
Raymond Hettinger1021c442003-11-07 15:38:09 +00002827/*********************** List Reverse Iterator **************************/
2828
2829typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002830 PyObject_HEAD
2831 Py_ssize_t it_index;
2832 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002833} listreviterobject;
2834
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002835static PyObject *list_reversed(PyListObject *, PyObject *);
2836static void listreviter_dealloc(listreviterobject *);
2837static int listreviter_traverse(listreviterobject *, visitproc, void *);
2838static PyObject *listreviter_next(listreviterobject *);
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002839static PyObject *listreviter_len(listreviterobject *);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002840static PyObject *listreviter_reduce(listreviterobject *);
2841static PyObject *listreviter_setstate(listreviterobject *, PyObject *);
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002842
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002843static PyMethodDef listreviter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002844 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002845 {"__reduce__", (PyCFunction)listreviter_reduce, METH_NOARGS, reduce_doc},
2846 {"__setstate__", (PyCFunction)listreviter_setstate, METH_O, setstate_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002847 {NULL, NULL} /* sentinel */
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002848};
2849
Raymond Hettinger1021c442003-11-07 15:38:09 +00002850PyTypeObject PyListRevIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002851 PyVarObject_HEAD_INIT(&PyType_Type, 0)
2852 "list_reverseiterator", /* tp_name */
2853 sizeof(listreviterobject), /* tp_basicsize */
2854 0, /* tp_itemsize */
2855 /* methods */
2856 (destructor)listreviter_dealloc, /* tp_dealloc */
2857 0, /* tp_print */
2858 0, /* tp_getattr */
2859 0, /* tp_setattr */
2860 0, /* tp_reserved */
2861 0, /* tp_repr */
2862 0, /* tp_as_number */
2863 0, /* tp_as_sequence */
2864 0, /* tp_as_mapping */
2865 0, /* tp_hash */
2866 0, /* tp_call */
2867 0, /* tp_str */
2868 PyObject_GenericGetAttr, /* tp_getattro */
2869 0, /* tp_setattro */
2870 0, /* tp_as_buffer */
2871 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2872 0, /* tp_doc */
2873 (traverseproc)listreviter_traverse, /* tp_traverse */
2874 0, /* tp_clear */
2875 0, /* tp_richcompare */
2876 0, /* tp_weaklistoffset */
2877 PyObject_SelfIter, /* tp_iter */
2878 (iternextfunc)listreviter_next, /* tp_iternext */
2879 listreviter_methods, /* tp_methods */
2880 0,
Raymond Hettinger1021c442003-11-07 15:38:09 +00002881};
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002882
2883static PyObject *
2884list_reversed(PyListObject *seq, PyObject *unused)
2885{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002886 listreviterobject *it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002887
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002888 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
2889 if (it == NULL)
2890 return NULL;
2891 assert(PyList_Check(seq));
2892 it->it_index = PyList_GET_SIZE(seq) - 1;
2893 Py_INCREF(seq);
2894 it->it_seq = seq;
2895 PyObject_GC_Track(it);
2896 return (PyObject *)it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002897}
2898
2899static void
2900listreviter_dealloc(listreviterobject *it)
2901{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002902 PyObject_GC_UnTrack(it);
2903 Py_XDECREF(it->it_seq);
2904 PyObject_GC_Del(it);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002905}
2906
2907static int
2908listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
2909{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002910 Py_VISIT(it->it_seq);
2911 return 0;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002912}
2913
2914static PyObject *
2915listreviter_next(listreviterobject *it)
2916{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002917 PyObject *item;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03002918 Py_ssize_t index;
2919 PyListObject *seq;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002920
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03002921 assert(it != NULL);
2922 seq = it->it_seq;
2923 if (seq == NULL) {
2924 return NULL;
2925 }
2926 assert(PyList_Check(seq));
2927
2928 index = it->it_index;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002929 if (index>=0 && index < PyList_GET_SIZE(seq)) {
2930 item = PyList_GET_ITEM(seq, index);
2931 it->it_index--;
2932 Py_INCREF(item);
2933 return item;
2934 }
2935 it->it_index = -1;
Serhiy Storchakafbb1c5e2016-03-30 20:40:02 +03002936 it->it_seq = NULL;
2937 Py_DECREF(seq);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002938 return NULL;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002939}
2940
Raymond Hettingerf5b64112008-12-02 21:33:45 +00002941static PyObject *
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002942listreviter_len(listreviterobject *it)
2943{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002944 Py_ssize_t len = it->it_index + 1;
2945 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
2946 len = 0;
2947 return PyLong_FromSsize_t(len);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002948}
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002949
2950static PyObject *
2951listreviter_reduce(listreviterobject *it)
2952{
2953 return listiter_reduce_general(it, 0);
2954}
2955
2956static PyObject *
2957listreviter_setstate(listreviterobject *it, PyObject *state)
2958{
2959 Py_ssize_t index = PyLong_AsSsize_t(state);
2960 if (index == -1 && PyErr_Occurred())
2961 return NULL;
2962 if (it->it_seq != NULL) {
2963 if (index < -1)
2964 index = -1;
2965 else if (index > PyList_GET_SIZE(it->it_seq) - 1)
2966 index = PyList_GET_SIZE(it->it_seq) - 1;
2967 it->it_index = index;
2968 }
2969 Py_RETURN_NONE;
2970}
2971
2972/* common pickling support */
2973
2974static PyObject *
2975listiter_reduce_general(void *_it, int forward)
2976{
2977 PyObject *list;
2978
2979 /* the objects are not the same, index is of different types! */
2980 if (forward) {
2981 listiterobject *it = (listiterobject *)_it;
2982 if (it->it_seq)
Victor Stinner7660b882013-06-24 23:59:24 +02002983 return Py_BuildValue("N(O)n", _PyObject_GetBuiltin("iter"),
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002984 it->it_seq, it->it_index);
2985 } else {
2986 listreviterobject *it = (listreviterobject *)_it;
2987 if (it->it_seq)
Antoine Pitroua7013882012-04-05 00:04:20 +02002988 return Py_BuildValue("N(O)n", _PyObject_GetBuiltin("reversed"),
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002989 it->it_seq, it->it_index);
2990 }
2991 /* empty iterator, create an empty list */
2992 list = PyList_New(0);
2993 if (list == NULL)
2994 return NULL;
Antoine Pitroua7013882012-04-05 00:04:20 +02002995 return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002996}