blob: 9368e897ccb8b8162da18f960a6ea32c1079c4f8 [file] [log] [blame]
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001/* List object implementation */
2
Guido van Rossumc0b618a1997-05-02 03:12:38 +00003#include "Python.h"
4
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00005#ifdef STDC_HEADERS
6#include <stddef.h>
7#else
8#include <sys/types.h> /* For size_t */
9#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000010
Guido van Rossuma46d51d1995-01-26 22:59:43 +000011static int
Raymond Hettingerd4ff7412004-03-15 09:01:31 +000012list_resize(PyListObject *self, int newsize)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000013{
Raymond Hettinger4bb95402004-02-13 11:36:39 +000014 PyObject **items;
15 size_t _new_size;
Tim Peters65b8b842001-05-26 05:28:40 +000016
Raymond Hettinger4bb95402004-02-13 11:36:39 +000017 /* Bypass realloc() when a previous overallocation is large enough
18 to accommodate the newsize. If the newsize is 16 smaller than the
19 current size, then proceed with the realloc() to shrink the list.
20 */
21
22 if (self->allocated >= newsize &&
23 self->ob_size < newsize + 16 &&
24 self->ob_item != NULL) {
25 self->ob_size = newsize;
26 return 0;
27 }
28
29 /* This over-allocates proportional to the list size, making room
Tim Peters65b8b842001-05-26 05:28:40 +000030 * for additional growth. The over-allocation is mild, but is
31 * enough to give linear-time amortized behavior over a long
32 * sequence of appends() in the presence of a poorly-performing
Raymond Hettingerab517d22004-02-14 18:34:46 +000033 * system realloc().
34 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
Tim Peters65b8b842001-05-26 05:28:40 +000035 */
Raymond Hettingerd4ff7412004-03-15 09:01:31 +000036 _new_size = (newsize >> 3) + (self->ob_size < 8 ? 3 : 6) + newsize;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000037 items = self->ob_item;
38 if (_new_size <= ((~(size_t)0) / sizeof(PyObject *)))
39 PyMem_RESIZE(items, PyObject *, _new_size);
40 else
41 items = NULL;
42 if (items == NULL) {
43 PyErr_NoMemory();
44 return -1;
45 }
46 self->ob_item = items;
47 self->ob_size = newsize;
48 self->allocated = _new_size;
49 return 0;
50}
Guido van Rossuma46d51d1995-01-26 22:59:43 +000051
Guido van Rossumc0b618a1997-05-02 03:12:38 +000052PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +000053PyList_New(int size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000054{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000055 PyListObject *op;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000056 size_t nbytes;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000057 if (size < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000058 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000059 return NULL;
60 }
Tim Peters7049d812004-01-18 20:31:02 +000061 nbytes = size * sizeof(PyObject *);
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000062 /* Check for overflow */
Tim Peters7049d812004-01-18 20:31:02 +000063 if (nbytes / sizeof(PyObject *) != (size_t)size) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000064 return PyErr_NoMemory();
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000065 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +000066 op = PyObject_GC_New(PyListObject, &PyList_Type);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000067 if (op == NULL) {
Neil Schemenauere83c00e2001-08-29 23:54:21 +000068 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000069 }
70 if (size <= 0) {
71 op->ob_item = NULL;
72 }
73 else {
Guido van Rossumb18618d2000-05-03 23:44:39 +000074 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000075 if (op->ob_item == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000076 return PyErr_NoMemory();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000077 }
Tim Peters7049d812004-01-18 20:31:02 +000078 memset(op->ob_item, 0, sizeof(*op->ob_item) * size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000079 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +000080 op->ob_size = size;
Raymond Hettinger4bb95402004-02-13 11:36:39 +000081 op->allocated = size;
Neil Schemenauere83c00e2001-08-29 23:54:21 +000082 _PyObject_GC_TRACK(op);
Guido van Rossumc0b618a1997-05-02 03:12:38 +000083 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000084}
85
86int
Fred Drakea2f55112000-07-09 15:16:51 +000087PyList_Size(PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000088{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000089 if (!PyList_Check(op)) {
90 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000091 return -1;
92 }
93 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +000094 return ((PyListObject *)op) -> ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000095}
96
Guido van Rossumc0b618a1997-05-02 03:12:38 +000097static PyObject *indexerr;
Guido van Rossum929f1b81996-08-09 20:51:27 +000098
Guido van Rossumc0b618a1997-05-02 03:12:38 +000099PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000100PyList_GetItem(PyObject *op, int i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000101{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000102 if (!PyList_Check(op)) {
103 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000104 return NULL;
105 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000106 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000107 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000108 indexerr = PyString_FromString(
109 "list index out of range");
110 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000111 return NULL;
112 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000113 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000114}
115
116int
Fred Drakea2f55112000-07-09 15:16:51 +0000117PyList_SetItem(register PyObject *op, register int i,
118 register PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000119{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000120 register PyObject *olditem;
121 register PyObject **p;
122 if (!PyList_Check(op)) {
123 Py_XDECREF(newitem);
124 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000125 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000126 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000127 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
128 Py_XDECREF(newitem);
129 PyErr_SetString(PyExc_IndexError,
130 "list assignment index out of range");
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000131 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000132 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000133 p = ((PyListObject *)op) -> ob_item + i;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000134 olditem = *p;
135 *p = newitem;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000136 Py_XDECREF(olditem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000137 return 0;
138}
139
140static int
Fred Drakea2f55112000-07-09 15:16:51 +0000141ins1(PyListObject *self, int where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000142{
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000143 int i, n = self->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000144 PyObject **items;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000145 if (v == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000146 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000147 return -1;
148 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000149 if (n == INT_MAX) {
Trent Micka5846642000-08-13 22:47:45 +0000150 PyErr_SetString(PyExc_OverflowError,
151 "cannot add more objects to list");
152 return -1;
153 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000154
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000155 if (list_resize(self, n+1) == -1)
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000156 return -1;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000157
Guido van Rossum3a3cca52003-04-14 20:58:14 +0000158 if (where < 0) {
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000159 where += n;
Guido van Rossum3a3cca52003-04-14 20:58:14 +0000160 if (where < 0)
161 where = 0;
162 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000163 if (where > n)
164 where = n;
165 items = self->ob_item;
166 for (i = n; --i >= where; )
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000167 items[i+1] = items[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000168 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000169 items[where] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000170 return 0;
171}
172
173int
Fred Drakea2f55112000-07-09 15:16:51 +0000174PyList_Insert(PyObject *op, int where, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000175{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000176 if (!PyList_Check(op)) {
177 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000178 return -1;
179 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000180 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000181}
182
Raymond Hettinger40a03822004-04-12 13:05:09 +0000183static int
184app1(PyListObject *self, PyObject *v)
185{
186 int n = PyList_GET_SIZE(self);
187
188 assert (v != NULL);
189 if (n == INT_MAX) {
190 PyErr_SetString(PyExc_OverflowError,
191 "cannot add more objects to list");
192 return -1;
193 }
194
195 if (list_resize(self, n+1) == -1)
196 return -1;
197
198 Py_INCREF(v);
199 PyList_SET_ITEM(self, n, v);
200 return 0;
201}
202
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000203int
Fred Drakea2f55112000-07-09 15:16:51 +0000204PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000205{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000206 if (!PyList_Check(op)) {
207 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000208 return -1;
209 }
Raymond Hettinger40a03822004-04-12 13:05:09 +0000210 if (newitem == NULL) {
211 PyErr_BadInternalCall();
212 return -1;
213 }
214 return app1((PyListObject *)op, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000215}
216
217/* Methods */
218
219static void
Fred Drakea2f55112000-07-09 15:16:51 +0000220list_dealloc(PyListObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000221{
222 int i;
Guido van Rossumff413af2002-03-28 20:34:59 +0000223 PyObject_GC_UnTrack(op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000224 Py_TRASHCAN_SAFE_BEGIN(op)
Jack Jansen7874d1f1995-01-19 12:09:27 +0000225 if (op->ob_item != NULL) {
Guido van Rossumfa717011999-06-09 15:19:34 +0000226 /* Do it backwards, for Christian Tismer.
227 There's a simple test case where somehow this reduces
228 thrashing when a *very* large list is created and
229 immediately deleted. */
230 i = op->ob_size;
231 while (--i >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000232 Py_XDECREF(op->ob_item[i]);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000233 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000234 PyMem_FREE(op->ob_item);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000235 }
Guido van Rossum9475a232001-10-05 20:51:39 +0000236 op->ob_type->tp_free((PyObject *)op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000237 Py_TRASHCAN_SAFE_END(op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000238}
239
Guido van Rossum90933611991-06-07 16:10:43 +0000240static int
Fred Drakea2f55112000-07-09 15:16:51 +0000241list_print(PyListObject *op, FILE *fp, int flags)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000242{
243 int i;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000244
245 i = Py_ReprEnter((PyObject*)op);
246 if (i != 0) {
247 if (i < 0)
248 return i;
249 fprintf(fp, "[...]");
250 return 0;
251 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000252 fprintf(fp, "[");
Guido van Rossum90933611991-06-07 16:10:43 +0000253 for (i = 0; i < op->ob_size; i++) {
254 if (i > 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000255 fprintf(fp, ", ");
Guido van Rossumfb376de1998-04-10 22:47:27 +0000256 if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
257 Py_ReprLeave((PyObject *)op);
Guido van Rossum90933611991-06-07 16:10:43 +0000258 return -1;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000259 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000260 }
261 fprintf(fp, "]");
Guido van Rossumfb376de1998-04-10 22:47:27 +0000262 Py_ReprLeave((PyObject *)op);
Guido van Rossum90933611991-06-07 16:10:43 +0000263 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000264}
265
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000266static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000267list_repr(PyListObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000268{
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000269 int i;
Tim Petersa7259592001-06-16 05:11:17 +0000270 PyObject *s, *temp;
271 PyObject *pieces = NULL, *result = NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000272
273 i = Py_ReprEnter((PyObject*)v);
274 if (i != 0) {
Tim Petersa7259592001-06-16 05:11:17 +0000275 return i > 0 ? PyString_FromString("[...]") : NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000276 }
Tim Petersa7259592001-06-16 05:11:17 +0000277
278 if (v->ob_size == 0) {
279 result = PyString_FromString("[]");
280 goto Done;
281 }
282
283 pieces = PyList_New(0);
284 if (pieces == NULL)
285 goto Done;
286
287 /* Do repr() on each element. Note that this may mutate the list,
288 so must refetch the list size on each iteration. */
289 for (i = 0; i < v->ob_size; ++i) {
290 int status;
291 s = PyObject_Repr(v->ob_item[i]);
292 if (s == NULL)
293 goto Done;
294 status = PyList_Append(pieces, s);
295 Py_DECREF(s); /* append created a new ref */
296 if (status < 0)
297 goto Done;
298 }
299
300 /* Add "[]" decorations to the first and last items. */
301 assert(PyList_GET_SIZE(pieces) > 0);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000302 s = PyString_FromString("[");
Tim Petersa7259592001-06-16 05:11:17 +0000303 if (s == NULL)
304 goto Done;
305 temp = PyList_GET_ITEM(pieces, 0);
306 PyString_ConcatAndDel(&s, temp);
307 PyList_SET_ITEM(pieces, 0, s);
308 if (s == NULL)
309 goto Done;
310
311 s = PyString_FromString("]");
312 if (s == NULL)
313 goto Done;
314 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
315 PyString_ConcatAndDel(&temp, s);
316 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
317 if (temp == NULL)
318 goto Done;
319
320 /* Paste them all together with ", " between. */
321 s = PyString_FromString(", ");
322 if (s == NULL)
323 goto Done;
324 result = _PyString_Join(s, pieces);
Tim Peters3b01a122002-07-19 02:35:45 +0000325 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +0000326
327Done:
328 Py_XDECREF(pieces);
Guido van Rossumfb376de1998-04-10 22:47:27 +0000329 Py_ReprLeave((PyObject *)v);
Tim Petersa7259592001-06-16 05:11:17 +0000330 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000331}
332
333static int
Fred Drakea2f55112000-07-09 15:16:51 +0000334list_length(PyListObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000335{
336 return a->ob_size;
337}
338
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000339static int
Fred Drakea2f55112000-07-09 15:16:51 +0000340list_contains(PyListObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000341{
Raymond Hettingeraae59992002-09-05 14:23:49 +0000342 int i, cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000343
Raymond Hettingeraae59992002-09-05 14:23:49 +0000344 for (i = 0, cmp = 0 ; cmp == 0 && i < a->ob_size; ++i)
345 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000346 Py_EQ);
Neal Norwitzbb9c5f52002-09-05 21:32:55 +0000347 return cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000348}
349
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000350static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000351list_item(PyListObject *a, int i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000352{
353 if (i < 0 || i >= a->ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000354 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000355 indexerr = PyString_FromString(
356 "list index out of range");
357 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000358 return NULL;
359 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000360 Py_INCREF(a->ob_item[i]);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000361 return a->ob_item[i];
362}
363
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000364static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000365list_slice(PyListObject *a, int ilow, int ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000366{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000367 PyListObject *np;
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000368 PyObject **src, **dest;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000369 int i, len;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000370 if (ilow < 0)
371 ilow = 0;
372 else if (ilow > a->ob_size)
373 ilow = a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000374 if (ihigh < ilow)
375 ihigh = ilow;
376 else if (ihigh > a->ob_size)
377 ihigh = a->ob_size;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000378 len = ihigh - ilow;
379 np = (PyListObject *) PyList_New(len);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000380 if (np == NULL)
381 return NULL;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000382
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000383 src = a->ob_item + ilow;
384 dest = np->ob_item;
Raymond Hettinger99842b62004-03-08 05:56:15 +0000385 for (i = 0; i < len; i++) {
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000386 PyObject *v = src[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000387 Py_INCREF(v);
Raymond Hettingerb7d05db2004-03-08 07:25:05 +0000388 dest[i] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000389 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000390 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000391}
392
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000393PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000394PyList_GetSlice(PyObject *a, int ilow, int ihigh)
Guido van Rossum234f9421993-06-17 12:35:49 +0000395{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000396 if (!PyList_Check(a)) {
397 PyErr_BadInternalCall();
Guido van Rossum234f9421993-06-17 12:35:49 +0000398 return NULL;
399 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000400 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000401}
402
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000403static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000404list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000405{
406 int size;
407 int i;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000408 PyObject **src, **dest;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000409 PyListObject *np;
410 if (!PyList_Check(bb)) {
Fred Drakeb6a9ada2000-06-01 03:12:13 +0000411 PyErr_Format(PyExc_TypeError,
Fred Drake914a2ed2000-06-01 14:31:03 +0000412 "can only concatenate list (not \"%.200s\") to list",
413 bb->ob_type->tp_name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000414 return NULL;
415 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000416#define b ((PyListObject *)bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000417 size = a->ob_size + b->ob_size;
Guido van Rossuma5c0e6d2002-10-11 21:05:56 +0000418 if (size < 0)
419 return PyErr_NoMemory();
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000420 np = (PyListObject *) PyList_New(size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000421 if (np == NULL) {
Guido van Rossum90933611991-06-07 16:10:43 +0000422 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000423 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000424 src = a->ob_item;
425 dest = np->ob_item;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000426 for (i = 0; i < a->ob_size; i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000427 PyObject *v = src[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000428 Py_INCREF(v);
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000429 dest[i] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000430 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000431 src = b->ob_item;
432 dest = np->ob_item + a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000433 for (i = 0; i < b->ob_size; i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000434 PyObject *v = src[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000435 Py_INCREF(v);
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000436 dest[i] = v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000437 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000438 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000439#undef b
440}
441
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000442static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000443list_repeat(PyListObject *a, int n)
Guido van Rossumed98d481991-03-06 13:07:53 +0000444{
445 int i, j;
446 int size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000447 PyListObject *np;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000448 PyObject **p, **items;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000449 PyObject *elem;
Guido van Rossumed98d481991-03-06 13:07:53 +0000450 if (n < 0)
451 n = 0;
452 size = a->ob_size * n;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000453 if (size == 0)
454 return PyList_New(0);
Guido van Rossumbfa5a142002-10-11 23:39:35 +0000455 if (n && size/n != a->ob_size)
Guido van Rossuma5c0e6d2002-10-11 21:05:56 +0000456 return PyErr_NoMemory();
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000457 np = (PyListObject *) PyList_New(size);
Guido van Rossumed98d481991-03-06 13:07:53 +0000458 if (np == NULL)
459 return NULL;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000460
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000461 items = np->ob_item;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000462 if (a->ob_size == 1) {
463 elem = a->ob_item[0];
464 for (i = 0; i < n; i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000465 items[i] = elem;
Raymond Hettinger6624e682003-05-21 05:58:46 +0000466 Py_INCREF(elem);
467 }
468 return (PyObject *) np;
469 }
Guido van Rossumed98d481991-03-06 13:07:53 +0000470 p = np->ob_item;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000471 items = a->ob_item;
Guido van Rossumed98d481991-03-06 13:07:53 +0000472 for (i = 0; i < n; i++) {
473 for (j = 0; j < a->ob_size; j++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000474 *p = items[j];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000475 Py_INCREF(*p);
Guido van Rossumed98d481991-03-06 13:07:53 +0000476 p++;
477 }
478 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000479 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000480}
481
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000482static int
Fred Drakea2f55112000-07-09 15:16:51 +0000483list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000484{
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000485 /* Because [X]DECREF can recursively invoke list operations on
486 this list, we must postpone all [X]DECREF activity until
487 after the list is back in its canonical shape. Therefore
488 we must allocate an additional array, 'recycle', into which
489 we temporarily copy the items that are deleted from the
490 list. :-( */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000491 PyObject **recycle, **p;
492 PyObject **item;
Raymond Hettingerf889e102004-03-09 08:04:33 +0000493 PyObject **vitem = NULL;
Michael W. Hudson5da854f2002-11-05 17:38:05 +0000494 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000495 int n; /* Size of replacement list */
496 int d; /* Change in size */
497 int k; /* Loop index */
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000498 int s;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000499#define b ((PyListObject *)v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000500 if (v == NULL)
501 n = 0;
Michael W. Hudson5da854f2002-11-05 17:38:05 +0000502 else {
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000503 if (a == b) {
504 /* Special case "a[i:j] = a" -- copy b first */
505 int ret;
Michael W. Hudsonda0a0672003-08-15 12:06:41 +0000506 v = list_slice(b, 0, b->ob_size);
Martin v. Löwiscd12bfc2003-05-03 10:53:08 +0000507 if (v == NULL)
508 return -1;
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000509 ret = list_ass_slice(a, ilow, ihigh, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000510 Py_DECREF(v);
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000511 return ret;
512 }
Raymond Hettingerf889e102004-03-09 08:04:33 +0000513 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
Michael W. Hudsonb4f49382003-08-14 17:04:28 +0000514 if(v_as_SF == NULL)
515 return -1;
516 n = PySequence_Fast_GET_SIZE(v_as_SF);
Raymond Hettinger42bec932004-03-12 16:38:17 +0000517 vitem = PySequence_Fast_ITEMS(v_as_SF);
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000518 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000519 if (ilow < 0)
520 ilow = 0;
521 else if (ilow > a->ob_size)
522 ilow = a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000523 if (ihigh < ilow)
524 ihigh = ilow;
525 else if (ihigh > a->ob_size)
526 ihigh = a->ob_size;
527 item = a->ob_item;
528 d = n - (ihigh-ilow);
Martin v. Löwiscd12bfc2003-05-03 10:53:08 +0000529 if (ihigh > ilow) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000530 p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
Martin v. Löwiscd12bfc2003-05-03 10:53:08 +0000531 if (recycle == NULL) {
532 PyErr_NoMemory();
533 return -1;
534 }
535 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000536 else
537 p = recycle = NULL;
538 if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
Raymond Hettinger66d31f82004-03-10 11:44:04 +0000539 memcpy(p, &item[ilow], (ihigh - ilow)*sizeof(PyObject *));
Raymond Hettingerf889e102004-03-09 08:04:33 +0000540 p += ihigh - ilow;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000541 if (d < 0) {
Raymond Hettingerf889e102004-03-09 08:04:33 +0000542 memmove(&item[ihigh+d], &item[ihigh],
543 (a->ob_size - ihigh)*sizeof(PyObject *));
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000544 list_resize(a, a->ob_size + d);
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000545 item = a->ob_item;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000546 }
547 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000548 else { /* Insert d items; recycle ihigh-ilow items */
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000549 s = a->ob_size;
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000550 if (list_resize(a, s+d) == -1) {
Guido van Rossumb18618d2000-05-03 23:44:39 +0000551 if (recycle != NULL)
552 PyMem_DEL(recycle);
Raymond Hettinger2731ae42004-02-14 03:07:21 +0000553 return -1;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000554 }
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000555 item = a->ob_item;
Raymond Hettingerf889e102004-03-09 08:04:33 +0000556 memmove(&item[ihigh+d], &item[ihigh],
557 (s - ihigh)*sizeof(PyObject *));
Raymond Hettinger66d31f82004-03-10 11:44:04 +0000558 memcpy(p, &item[ilow], (ihigh - ilow)*sizeof(PyObject *));
Raymond Hettingerf889e102004-03-09 08:04:33 +0000559 p += ihigh - ilow;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000560 }
561 for (k = 0; k < n; k++, ilow++) {
Raymond Hettingerf889e102004-03-09 08:04:33 +0000562 PyObject *w = vitem[k];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000563 Py_XINCREF(w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000564 item[ilow] = w;
565 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000566 if (recycle) {
567 while (--p >= recycle)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000568 Py_XDECREF(*p);
569 PyMem_DEL(recycle);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000570 }
Tim Peters6d6c1a32001-08-02 04:15:00 +0000571 if (a->ob_size == 0 && a->ob_item != NULL) {
572 PyMem_FREE(a->ob_item);
573 a->ob_item = NULL;
574 }
Michael W. Hudson5da854f2002-11-05 17:38:05 +0000575 Py_XDECREF(v_as_SF);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000576 return 0;
577#undef b
578}
579
Guido van Rossum234f9421993-06-17 12:35:49 +0000580int
Fred Drakea2f55112000-07-09 15:16:51 +0000581PyList_SetSlice(PyObject *a, int ilow, int ihigh, PyObject *v)
Guido van Rossum234f9421993-06-17 12:35:49 +0000582{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000583 if (!PyList_Check(a)) {
584 PyErr_BadInternalCall();
Guido van Rossum1fc238a1993-07-29 08:25:09 +0000585 return -1;
Guido van Rossum234f9421993-06-17 12:35:49 +0000586 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000587 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000588}
589
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000590static PyObject *
591list_inplace_repeat(PyListObject *self, int n)
592{
593 PyObject **items;
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000594 int size, i, j, p;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000595
596
597 size = PyList_GET_SIZE(self);
598 if (size == 0) {
599 Py_INCREF(self);
600 return (PyObject *)self;
601 }
602
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000603 if (n < 1) {
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000604 items = self->ob_item;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000605 self->ob_item = NULL;
606 self->ob_size = 0;
607 for (i = 0; i < size; i++)
608 Py_XDECREF(items[i]);
609 PyMem_DEL(items);
610 Py_INCREF(self);
611 return (PyObject *)self;
612 }
613
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000614 if (list_resize(self, size*n) == -1)
Raymond Hettinger4bb95402004-02-13 11:36:39 +0000615 return NULL;
616
617 p = size;
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000618 items = self->ob_item;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000619 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
620 for (j = 0; j < size; j++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000621 PyObject *o = items[j];
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000622 Py_INCREF(o);
Raymond Hettingera6366fe2004-03-09 13:05:22 +0000623 items[p++] = o;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000624 }
625 }
626 Py_INCREF(self);
627 return (PyObject *)self;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000628}
629
Guido van Rossum4a450d01991-04-03 19:05:18 +0000630static int
Fred Drakea2f55112000-07-09 15:16:51 +0000631list_ass_item(PyListObject *a, int i, PyObject *v)
Guido van Rossum4a450d01991-04-03 19:05:18 +0000632{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000633 PyObject *old_value;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000634 if (i < 0 || i >= a->ob_size) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000635 PyErr_SetString(PyExc_IndexError,
636 "list assignment index out of range");
Guido van Rossum4a450d01991-04-03 19:05:18 +0000637 return -1;
638 }
639 if (v == NULL)
640 return list_ass_slice(a, i, i+1, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000641 Py_INCREF(v);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000642 old_value = a->ob_item[i];
Guido van Rossum4a450d01991-04-03 19:05:18 +0000643 a->ob_item[i] = v;
Tim Peters3b01a122002-07-19 02:35:45 +0000644 Py_DECREF(old_value);
Guido van Rossum4a450d01991-04-03 19:05:18 +0000645 return 0;
646}
647
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000648static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000649ins(PyListObject *self, int where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000650{
651 if (ins1(self, where, v) != 0)
652 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000653 Py_INCREF(Py_None);
654 return Py_None;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000655}
656
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000657static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000658listinsert(PyListObject *self, PyObject *args)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000659{
660 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000661 PyObject *v;
Guido van Rossumc00a9382000-02-24 21:48:29 +0000662 if (!PyArg_ParseTuple(args, "iO:insert", &i, &v))
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000663 return NULL;
Guido van Rossumbf80e541993-02-08 15:49:17 +0000664 return ins(self, i, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000665}
666
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000667static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000668listappend(PyListObject *self, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000669{
Guido van Rossumbf80e541993-02-08 15:49:17 +0000670 return ins(self, (int) self->ob_size, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000671}
672
Barry Warsawdedf6d61998-10-09 16:37:25 +0000673static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000674listextend(PyListObject *self, PyObject *b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000675{
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000676 PyObject *it; /* iter(v) */
677 int m; /* size of self */
678 int n; /* guess for size of b */
679 int mn; /* m + n */
680 int i;
Raymond Hettinger57c45422004-03-11 09:48:18 +0000681 PyObject *(*iternext)(PyObject *);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000682
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000683 /* Special cases:
684 1) lists and tuples which can use PySequence_Fast ops
685 2) extending self to self requires making a copy first
686 */
687 if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
Armin Rigo70d172d2004-03-20 22:19:23 +0000688 PyObject **src, **dest;
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000689 b = PySequence_Fast(b, "argument must be iterable");
690 if (!b)
691 return NULL;
Armin Rigo70d172d2004-03-20 22:19:23 +0000692 n = PySequence_Fast_GET_SIZE(b);
693 if (n == 0) {
694 /* short circuit when b is empty */
695 Py_DECREF(b);
696 Py_RETURN_NONE;
697 }
698 m = self->ob_size;
699 if (list_resize(self, m + n) == -1) {
700 Py_DECREF(b);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000701 return NULL;
Armin Rigo70d172d2004-03-20 22:19:23 +0000702 }
703 /* note that we may still have self == b here for the
704 * situation a.extend(a), but the following code works
705 * in that case too. Just make sure to resize self
706 * before calling PySequence_Fast_ITEMS.
707 */
708 /* populate the end of self with b's items */
709 src = PySequence_Fast_ITEMS(b);
710 dest = self->ob_item + m;
711 for (i = 0; i < n; i++) {
712 PyObject *o = src[i];
713 Py_INCREF(o);
714 dest[i] = o;
715 }
716 Py_DECREF(b);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000717 Py_RETURN_NONE;
718 }
719
720 it = PyObject_GetIter(b);
721 if (it == NULL)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000722 return NULL;
Raymond Hettinger57c45422004-03-11 09:48:18 +0000723 iternext = *it->ob_type->tp_iternext;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000724
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000725 /* Guess a result list size. */
726 n = PyObject_Size(b);
727 if (n < 0) {
728 PyErr_Clear();
729 n = 8; /* arbitrary */
730 }
731 m = self->ob_size;
732 mn = m + n;
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000733 if (list_resize(self, mn) == -1)
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000734 goto error;
735 memset(&(self->ob_item[m]), 0, sizeof(*self->ob_item) * n);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000736
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000737 /* Run iterator to exhaustion. */
738 for (i = m; ; i++) {
Raymond Hettinger57c45422004-03-11 09:48:18 +0000739 PyObject *item = iternext(it);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000740 if (item == NULL) {
Raymond Hettinger57c45422004-03-11 09:48:18 +0000741 if (PyErr_Occurred()) {
742 if (PyErr_ExceptionMatches(PyExc_StopIteration))
743 PyErr_Clear();
744 else
745 goto error;
746 }
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000747 break;
748 }
749 if (i < mn)
750 PyList_SET_ITEM(self, i, item); /* steals ref */
751 else {
Raymond Hettinger40a03822004-04-12 13:05:09 +0000752 int status = app1(self, item);
Raymond Hettinger90a39bf2004-02-15 03:57:00 +0000753 Py_DECREF(item); /* append creates a new ref */
754 if (status < 0)
755 goto error;
756 }
757 }
758
759 /* Cut back result list if initial guess was too large. */
760 if (i < mn && self != NULL) {
761 if (list_ass_slice(self, i, mn, (PyObject *)NULL) != 0)
762 goto error;
763 }
764 Py_DECREF(it);
765 Py_RETURN_NONE;
766
767 error:
768 Py_DECREF(it);
769 return NULL;
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000770}
771
Raymond Hettinger8ca92ae2004-03-11 09:13:12 +0000772PyObject *
773_PyList_Extend(PyListObject *self, PyObject *b)
774{
775 return listextend(self, b);
776}
777
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000778static PyObject *
Raymond Hettinger97bc6182004-03-11 07:34:19 +0000779list_inplace_concat(PyListObject *self, PyObject *other)
780{
781 PyObject *result;
782
783 result = listextend(self, other);
784 if (result == NULL)
785 return result;
786 Py_DECREF(result);
787 Py_INCREF(self);
788 return (PyObject *)self;
789}
790
791static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000792listpop(PyListObject *self, PyObject *args)
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000793{
794 int i = -1;
Raymond Hettinger9eb86b32004-02-17 11:36:16 +0000795 PyObject *v, *arg = NULL;
796
797 if (!PyArg_UnpackTuple(args, "pop", 0, 1, &arg))
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000798 return NULL;
Raymond Hettinger9eb86b32004-02-17 11:36:16 +0000799 if (arg != NULL) {
800 if (PyInt_Check(arg))
801 i = (int)(PyInt_AS_LONG((PyIntObject*) arg));
Raymond Hettingerfa6c6f82004-02-19 06:12:06 +0000802 else if (!PyArg_ParseTuple(args, "|i:pop", &i))
803 return NULL;
Raymond Hettinger9eb86b32004-02-17 11:36:16 +0000804 }
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000805 if (self->ob_size == 0) {
806 /* Special-case most common failure cause */
807 PyErr_SetString(PyExc_IndexError, "pop from empty list");
808 return NULL;
809 }
810 if (i < 0)
811 i += self->ob_size;
812 if (i < 0 || i >= self->ob_size) {
813 PyErr_SetString(PyExc_IndexError, "pop index out of range");
814 return NULL;
815 }
816 v = self->ob_item[i];
Raymond Hettingercb3e5802004-02-13 18:36:31 +0000817 if (i == self->ob_size - 1) {
Raymond Hettingerd4ff7412004-03-15 09:01:31 +0000818 if (list_resize(self, self->ob_size - 1) == -1)
Raymond Hettingercb3e5802004-02-13 18:36:31 +0000819 return NULL;
820 return v;
821 }
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000822 Py_INCREF(v);
823 if (list_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
824 Py_DECREF(v);
825 return NULL;
826 }
827 return v;
828}
829
Tim Peters8e2e7ca2002-07-19 02:33:08 +0000830/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
831static void
832reverse_slice(PyObject **lo, PyObject **hi)
833{
834 assert(lo && hi);
835
836 --hi;
837 while (lo < hi) {
838 PyObject *t = *lo;
839 *lo = *hi;
840 *hi = t;
841 ++lo;
842 --hi;
843 }
844}
845
Tim Petersa64dc242002-08-01 02:13:36 +0000846/* Lots of code for an adaptive, stable, natural mergesort. There are many
847 * pieces to this algorithm; read listsort.txt for overviews and details.
848 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000849
Guido van Rossum3f236de1996-12-10 23:55:39 +0000850/* Comparison function. Takes care of calling a user-supplied
Tim Peters66860f62002-08-04 17:47:26 +0000851 * comparison function (any callable Python object), which must not be
852 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
853 * with Py_LT if you know it's NULL).
Tim Petersa64dc242002-08-01 02:13:36 +0000854 * Returns -1 on error, 1 if x < y, 0 if x >= y.
855 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000856static int
Tim Petersa8c974c2002-07-19 03:30:57 +0000857islt(PyObject *x, PyObject *y, PyObject *compare)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000858{
Tim Petersf2a04732002-07-11 21:46:16 +0000859 PyObject *res;
860 PyObject *args;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000861 int i;
862
Tim Peters66860f62002-08-04 17:47:26 +0000863 assert(compare != NULL);
Tim Petersa8c974c2002-07-19 03:30:57 +0000864 /* Call the user's comparison function and translate the 3-way
865 * result into true or false (or error).
866 */
Tim Petersf2a04732002-07-11 21:46:16 +0000867 args = PyTuple_New(2);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000868 if (args == NULL)
Tim Petersa8c974c2002-07-19 03:30:57 +0000869 return -1;
Tim Petersf2a04732002-07-11 21:46:16 +0000870 Py_INCREF(x);
871 Py_INCREF(y);
872 PyTuple_SET_ITEM(args, 0, x);
873 PyTuple_SET_ITEM(args, 1, y);
Tim Peters58cf3612002-07-15 05:16:13 +0000874 res = PyObject_Call(compare, args, NULL);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000875 Py_DECREF(args);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000876 if (res == NULL)
Tim Petersa8c974c2002-07-19 03:30:57 +0000877 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000878 if (!PyInt_Check(res)) {
879 Py_DECREF(res);
880 PyErr_SetString(PyExc_TypeError,
Guido van Rossum9bcd1d71999-04-19 17:44:39 +0000881 "comparison function must return int");
Tim Petersa8c974c2002-07-19 03:30:57 +0000882 return -1;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000883 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000884 i = PyInt_AsLong(res);
885 Py_DECREF(res);
Tim Petersa8c974c2002-07-19 03:30:57 +0000886 return i < 0;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000887}
888
Tim Peters66860f62002-08-04 17:47:26 +0000889/* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
890 * islt. This avoids a layer of function call in the usual case, and
891 * sorting does many comparisons.
892 * Returns -1 on error, 1 if x < y, 0 if x >= y.
893 */
894#define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
895 PyObject_RichCompareBool(X, Y, Py_LT) : \
896 islt(X, Y, COMPARE))
897
898/* Compare X to Y via "<". Goto "fail" if the comparison raises an
Tim Petersa8c974c2002-07-19 03:30:57 +0000899 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
900 started. It makes more sense in context <wink>. X and Y are PyObject*s.
901*/
Tim Peters66860f62002-08-04 17:47:26 +0000902#define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
Tim Petersa8c974c2002-07-19 03:30:57 +0000903 if (k)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000904
905/* binarysort is the best method for sorting small arrays: it does
906 few compares, but can do data movement quadratic in the number of
907 elements.
Guido van Rossum42812581998-06-17 14:15:44 +0000908 [lo, hi) is a contiguous slice of a list, and is sorted via
Tim Petersa8c974c2002-07-19 03:30:57 +0000909 binary insertion. This sort is stable.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000910 On entry, must have lo <= start <= hi, and that [lo, start) is already
911 sorted (pass start == lo if you don't know!).
Tim Petersa8c974c2002-07-19 03:30:57 +0000912 If islt() complains return -1, else 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000913 Even in case of error, the output slice will be some permutation of
914 the input (nothing is lost or duplicated).
915*/
Guido van Rossum3f236de1996-12-10 23:55:39 +0000916static int
Fred Drakea2f55112000-07-09 15:16:51 +0000917binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
918 /* compare -- comparison function object, or NULL for default */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000919{
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000920 register int k;
921 register PyObject **l, **p, **r;
922 register PyObject *pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000923
Tim Petersa8c974c2002-07-19 03:30:57 +0000924 assert(lo <= start && start <= hi);
925 /* assert [lo, start) is sorted */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000926 if (lo == start)
927 ++start;
928 for (; start < hi; ++start) {
929 /* set l to where *start belongs */
930 l = lo;
931 r = start;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000932 pivot = *r;
Tim Peters0fe977c2002-07-19 06:12:32 +0000933 /* Invariants:
934 * pivot >= all in [lo, l).
935 * pivot < all in [r, start).
936 * The second is vacuously true at the start.
937 */
938 assert(l < r);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000939 do {
940 p = l + ((r - l) >> 1);
Tim Petersa8c974c2002-07-19 03:30:57 +0000941 IFLT(pivot, *p)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000942 r = p;
943 else
Tim Peters0fe977c2002-07-19 06:12:32 +0000944 l = p+1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000945 } while (l < r);
Tim Peters0fe977c2002-07-19 06:12:32 +0000946 assert(l == r);
947 /* The invariants still hold, so pivot >= all in [lo, l) and
948 pivot < all in [l, start), so pivot belongs at l. Note
949 that if there are elements equal to pivot, l points to the
950 first slot after them -- that's why this sort is stable.
951 Slide over to make room.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000952 Caution: using memmove is much slower under MSVC 5;
953 we're not usually moving many slots. */
954 for (p = start; p > l; --p)
955 *p = *(p-1);
956 *l = pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000957 }
Guido van Rossum3f236de1996-12-10 23:55:39 +0000958 return 0;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000959
960 fail:
961 return -1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000962}
963
Tim Petersa64dc242002-08-01 02:13:36 +0000964/*
965Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
966is required on entry. "A run" is the longest ascending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000967
Tim Petersa64dc242002-08-01 02:13:36 +0000968 lo[0] <= lo[1] <= lo[2] <= ...
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000969
Tim Petersa64dc242002-08-01 02:13:36 +0000970or the longest descending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000971
Tim Petersa64dc242002-08-01 02:13:36 +0000972 lo[0] > lo[1] > lo[2] > ...
Tim Peters3b01a122002-07-19 02:35:45 +0000973
Tim Petersa64dc242002-08-01 02:13:36 +0000974Boolean *descending is set to 0 in the former case, or to 1 in the latter.
975For its intended use in a stable mergesort, the strictness of the defn of
976"descending" is needed so that the caller can safely reverse a descending
977sequence without violating stability (strict > ensures there are no equal
978elements to get out of order).
979
980Returns -1 in case of error.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000981*/
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000982static int
Tim Petersa64dc242002-08-01 02:13:36 +0000983count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000984{
Tim Petersa64dc242002-08-01 02:13:36 +0000985 int k;
986 int n;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000987
Tim Petersa64dc242002-08-01 02:13:36 +0000988 assert(lo < hi);
989 *descending = 0;
990 ++lo;
991 if (lo == hi)
992 return 1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000993
Tim Petersa64dc242002-08-01 02:13:36 +0000994 n = 2;
995 IFLT(*lo, *(lo-1)) {
996 *descending = 1;
997 for (lo = lo+1; lo < hi; ++lo, ++n) {
998 IFLT(*lo, *(lo-1))
999 ;
1000 else
1001 break;
1002 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001003 }
Tim Petersa64dc242002-08-01 02:13:36 +00001004 else {
1005 for (lo = lo+1; lo < hi; ++lo, ++n) {
1006 IFLT(*lo, *(lo-1))
1007 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001008 }
1009 }
1010
Tim Petersa64dc242002-08-01 02:13:36 +00001011 return n;
1012fail:
1013 return -1;
1014}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001015
Tim Petersa64dc242002-08-01 02:13:36 +00001016/*
1017Locate the proper position of key in a sorted vector; if the vector contains
1018an element equal to key, return the position immediately to the left of
1019the leftmost equal element. [gallop_right() does the same except returns
1020the position to the right of the rightmost equal element (if any).]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001021
Tim Petersa64dc242002-08-01 02:13:36 +00001022"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001023
Tim Petersa64dc242002-08-01 02:13:36 +00001024"hint" is an index at which to begin the search, 0 <= hint < n. The closer
1025hint is to the final result, the faster this runs.
1026
1027The return value is the int k in 0..n such that
1028
1029 a[k-1] < key <= a[k]
1030
1031pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
1032key belongs at index k; or, IOW, the first k elements of a should precede
1033key, and the last n-k should follow key.
1034
1035Returns -1 on error. See listsort.txt for info on the method.
1036*/
1037static int
1038gallop_left(PyObject *key, PyObject **a, int n, int hint, PyObject *compare)
1039{
1040 int ofs;
1041 int lastofs;
1042 int k;
1043
1044 assert(key && a && n > 0 && hint >= 0 && hint < n);
1045
1046 a += hint;
1047 lastofs = 0;
1048 ofs = 1;
1049 IFLT(*a, key) {
1050 /* a[hint] < key -- gallop right, until
1051 * a[hint + lastofs] < key <= a[hint + ofs]
1052 */
1053 const int maxofs = n - hint; /* &a[n-1] is highest */
1054 while (ofs < maxofs) {
1055 IFLT(a[ofs], key) {
1056 lastofs = ofs;
1057 ofs = (ofs << 1) + 1;
1058 if (ofs <= 0) /* int overflow */
1059 ofs = maxofs;
1060 }
1061 else /* key <= a[hint + ofs] */
1062 break;
1063 }
1064 if (ofs > maxofs)
1065 ofs = maxofs;
1066 /* Translate back to offsets relative to &a[0]. */
1067 lastofs += hint;
1068 ofs += hint;
1069 }
1070 else {
1071 /* key <= a[hint] -- gallop left, until
1072 * a[hint - ofs] < key <= a[hint - lastofs]
1073 */
1074 const int maxofs = hint + 1; /* &a[0] is lowest */
1075 while (ofs < maxofs) {
1076 IFLT(*(a-ofs), key)
1077 break;
1078 /* key <= a[hint - ofs] */
1079 lastofs = ofs;
1080 ofs = (ofs << 1) + 1;
1081 if (ofs <= 0) /* int overflow */
1082 ofs = maxofs;
1083 }
1084 if (ofs > maxofs)
1085 ofs = maxofs;
1086 /* Translate back to positive offsets relative to &a[0]. */
1087 k = lastofs;
1088 lastofs = hint - ofs;
1089 ofs = hint - k;
1090 }
1091 a -= hint;
1092
1093 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1094 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1095 * right of lastofs but no farther right than ofs. Do a binary
1096 * search, with invariant a[lastofs-1] < key <= a[ofs].
1097 */
1098 ++lastofs;
1099 while (lastofs < ofs) {
1100 int m = lastofs + ((ofs - lastofs) >> 1);
1101
1102 IFLT(a[m], key)
1103 lastofs = m+1; /* a[m] < key */
1104 else
1105 ofs = m; /* key <= a[m] */
1106 }
1107 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1108 return ofs;
1109
1110fail:
1111 return -1;
1112}
1113
1114/*
1115Exactly like gallop_left(), except that if key already exists in a[0:n],
1116finds the position immediately to the right of the rightmost equal value.
1117
1118The return value is the int k in 0..n such that
1119
1120 a[k-1] <= key < a[k]
1121
1122or -1 if error.
1123
1124The code duplication is massive, but this is enough different given that
1125we're sticking to "<" comparisons that it's much harder to follow if
1126written as one routine with yet another "left or right?" flag.
1127*/
1128static int
1129gallop_right(PyObject *key, PyObject **a, int n, int hint, PyObject *compare)
1130{
1131 int ofs;
1132 int lastofs;
1133 int k;
1134
1135 assert(key && a && n > 0 && hint >= 0 && hint < n);
1136
1137 a += hint;
1138 lastofs = 0;
1139 ofs = 1;
1140 IFLT(key, *a) {
1141 /* key < a[hint] -- gallop left, until
1142 * a[hint - ofs] <= key < a[hint - lastofs]
1143 */
1144 const int maxofs = hint + 1; /* &a[0] is lowest */
1145 while (ofs < maxofs) {
1146 IFLT(key, *(a-ofs)) {
1147 lastofs = ofs;
1148 ofs = (ofs << 1) + 1;
1149 if (ofs <= 0) /* int overflow */
1150 ofs = maxofs;
1151 }
1152 else /* a[hint - ofs] <= key */
1153 break;
1154 }
1155 if (ofs > maxofs)
1156 ofs = maxofs;
1157 /* Translate back to positive offsets relative to &a[0]. */
1158 k = lastofs;
1159 lastofs = hint - ofs;
1160 ofs = hint - k;
1161 }
1162 else {
1163 /* a[hint] <= key -- gallop right, until
1164 * a[hint + lastofs] <= key < a[hint + ofs]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001165 */
Tim Petersa64dc242002-08-01 02:13:36 +00001166 const int maxofs = n - hint; /* &a[n-1] is highest */
1167 while (ofs < maxofs) {
1168 IFLT(key, a[ofs])
1169 break;
1170 /* a[hint + ofs] <= key */
1171 lastofs = ofs;
1172 ofs = (ofs << 1) + 1;
1173 if (ofs <= 0) /* int overflow */
1174 ofs = maxofs;
1175 }
1176 if (ofs > maxofs)
1177 ofs = maxofs;
1178 /* Translate back to offsets relative to &a[0]. */
1179 lastofs += hint;
1180 ofs += hint;
1181 }
1182 a -= hint;
1183
1184 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1185 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1186 * right of lastofs but no farther right than ofs. Do a binary
1187 * search, with invariant a[lastofs-1] <= key < a[ofs].
1188 */
1189 ++lastofs;
1190 while (lastofs < ofs) {
1191 int m = lastofs + ((ofs - lastofs) >> 1);
1192
1193 IFLT(key, a[m])
1194 ofs = m; /* key < a[m] */
1195 else
1196 lastofs = m+1; /* a[m] <= key */
1197 }
1198 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1199 return ofs;
1200
1201fail:
1202 return -1;
1203}
1204
1205/* The maximum number of entries in a MergeState's pending-runs stack.
1206 * This is enough to sort arrays of size up to about
1207 * 32 * phi ** MAX_MERGE_PENDING
1208 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1209 * with 2**64 elements.
1210 */
1211#define MAX_MERGE_PENDING 85
1212
Tim Peterse05f65a2002-08-10 05:21:15 +00001213/* When we get into galloping mode, we stay there until both runs win less
1214 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
Tim Petersa64dc242002-08-01 02:13:36 +00001215 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001216#define MIN_GALLOP 7
Tim Petersa64dc242002-08-01 02:13:36 +00001217
1218/* Avoid malloc for small temp arrays. */
1219#define MERGESTATE_TEMP_SIZE 256
1220
1221/* One MergeState exists on the stack per invocation of mergesort. It's just
1222 * a convenient way to pass state around among the helper functions.
1223 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001224struct s_slice {
1225 PyObject **base;
1226 int len;
1227};
1228
Tim Petersa64dc242002-08-01 02:13:36 +00001229typedef struct s_MergeState {
1230 /* The user-supplied comparison function. or NULL if none given. */
1231 PyObject *compare;
1232
Tim Peterse05f65a2002-08-10 05:21:15 +00001233 /* This controls when we get *into* galloping mode. It's initialized
1234 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
1235 * random data, and lower for highly structured data.
1236 */
1237 int min_gallop;
1238
Tim Petersa64dc242002-08-01 02:13:36 +00001239 /* 'a' is temp storage to help with merges. It contains room for
1240 * alloced entries.
1241 */
1242 PyObject **a; /* may point to temparray below */
1243 int alloced;
1244
1245 /* A stack of n pending runs yet to be merged. Run #i starts at
1246 * address base[i] and extends for len[i] elements. It's always
1247 * true (so long as the indices are in bounds) that
1248 *
Tim Peterse05f65a2002-08-10 05:21:15 +00001249 * pending[i].base + pending[i].len == pending[i+1].base
Tim Petersa64dc242002-08-01 02:13:36 +00001250 *
1251 * so we could cut the storage for this, but it's a minor amount,
1252 * and keeping all the info explicit simplifies the code.
1253 */
1254 int n;
Tim Peterse05f65a2002-08-10 05:21:15 +00001255 struct s_slice pending[MAX_MERGE_PENDING];
Tim Petersa64dc242002-08-01 02:13:36 +00001256
1257 /* 'a' points to this when possible, rather than muck with malloc. */
1258 PyObject *temparray[MERGESTATE_TEMP_SIZE];
1259} MergeState;
1260
1261/* Conceptually a MergeState's constructor. */
1262static void
1263merge_init(MergeState *ms, PyObject *compare)
1264{
1265 assert(ms != NULL);
1266 ms->compare = compare;
1267 ms->a = ms->temparray;
1268 ms->alloced = MERGESTATE_TEMP_SIZE;
1269 ms->n = 0;
Tim Peterse05f65a2002-08-10 05:21:15 +00001270 ms->min_gallop = MIN_GALLOP;
Tim Petersa64dc242002-08-01 02:13:36 +00001271}
1272
1273/* Free all the temp memory owned by the MergeState. This must be called
1274 * when you're done with a MergeState, and may be called before then if
1275 * you want to free the temp memory early.
1276 */
1277static void
1278merge_freemem(MergeState *ms)
1279{
1280 assert(ms != NULL);
1281 if (ms->a != ms->temparray)
1282 PyMem_Free(ms->a);
1283 ms->a = ms->temparray;
1284 ms->alloced = MERGESTATE_TEMP_SIZE;
1285}
1286
1287/* Ensure enough temp memory for 'need' array slots is available.
1288 * Returns 0 on success and -1 if the memory can't be gotten.
1289 */
1290static int
1291merge_getmem(MergeState *ms, int need)
1292{
1293 assert(ms != NULL);
1294 if (need <= ms->alloced)
1295 return 0;
1296 /* Don't realloc! That can cost cycles to copy the old data, but
1297 * we don't care what's in the block.
1298 */
1299 merge_freemem(ms);
1300 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));
1301 if (ms->a) {
1302 ms->alloced = need;
1303 return 0;
1304 }
1305 PyErr_NoMemory();
1306 merge_freemem(ms); /* reset to sane state */
1307 return -1;
1308}
1309#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1310 merge_getmem(MS, NEED))
1311
1312/* Merge the na elements starting at pa with the nb elements starting at pb
1313 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1314 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1315 * merge, and should have na <= nb. See listsort.txt for more info.
1316 * Return 0 if successful, -1 if error.
1317 */
1318static int
1319merge_lo(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb)
1320{
1321 int k;
1322 PyObject *compare;
1323 PyObject **dest;
1324 int result = -1; /* guilty until proved innocent */
Tim Peterse05f65a2002-08-10 05:21:15 +00001325 int min_gallop = ms->min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001326
1327 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1328 if (MERGE_GETMEM(ms, na) < 0)
1329 return -1;
1330 memcpy(ms->a, pa, na * sizeof(PyObject*));
1331 dest = pa;
1332 pa = ms->a;
1333
1334 *dest++ = *pb++;
1335 --nb;
1336 if (nb == 0)
1337 goto Succeed;
1338 if (na == 1)
1339 goto CopyB;
1340
1341 compare = ms->compare;
1342 for (;;) {
1343 int acount = 0; /* # of times A won in a row */
1344 int bcount = 0; /* # of times B won in a row */
1345
1346 /* Do the straightforward thing until (if ever) one run
1347 * appears to win consistently.
1348 */
1349 for (;;) {
Tim Peterse05f65a2002-08-10 05:21:15 +00001350 assert(na > 1 && nb > 0);
Tim Peters66860f62002-08-04 17:47:26 +00001351 k = ISLT(*pb, *pa, compare);
Tim Petersa64dc242002-08-01 02:13:36 +00001352 if (k) {
1353 if (k < 0)
1354 goto Fail;
1355 *dest++ = *pb++;
1356 ++bcount;
1357 acount = 0;
1358 --nb;
1359 if (nb == 0)
1360 goto Succeed;
Tim Peterse05f65a2002-08-10 05:21:15 +00001361 if (bcount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001362 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001363 }
1364 else {
Tim Petersa64dc242002-08-01 02:13:36 +00001365 *dest++ = *pa++;
1366 ++acount;
1367 bcount = 0;
1368 --na;
1369 if (na == 1)
1370 goto CopyB;
Tim Peterse05f65a2002-08-10 05:21:15 +00001371 if (acount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001372 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001373 }
Tim Petersa64dc242002-08-01 02:13:36 +00001374 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001375
Tim Petersa64dc242002-08-01 02:13:36 +00001376 /* One run is winning so consistently that galloping may
1377 * be a huge win. So try that, and continue galloping until
1378 * (if ever) neither run appears to be winning consistently
1379 * anymore.
1380 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001381 ++min_gallop;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001382 do {
Tim Peterse05f65a2002-08-10 05:21:15 +00001383 assert(na > 1 && nb > 0);
1384 min_gallop -= min_gallop > 1;
1385 ms->min_gallop = min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001386 k = gallop_right(*pb, pa, na, 0, compare);
1387 acount = k;
1388 if (k) {
1389 if (k < 0)
1390 goto Fail;
1391 memcpy(dest, pa, k * sizeof(PyObject *));
1392 dest += k;
1393 pa += k;
1394 na -= k;
1395 if (na == 1)
1396 goto CopyB;
1397 /* na==0 is impossible now if the comparison
1398 * function is consistent, but we can't assume
1399 * that it is.
1400 */
1401 if (na == 0)
1402 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001403 }
Tim Petersa64dc242002-08-01 02:13:36 +00001404 *dest++ = *pb++;
1405 --nb;
1406 if (nb == 0)
1407 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001408
Tim Petersa64dc242002-08-01 02:13:36 +00001409 k = gallop_left(*pa, pb, nb, 0, compare);
1410 bcount = k;
1411 if (k) {
1412 if (k < 0)
1413 goto Fail;
1414 memmove(dest, pb, k * sizeof(PyObject *));
1415 dest += k;
1416 pb += k;
1417 nb -= k;
1418 if (nb == 0)
1419 goto Succeed;
1420 }
1421 *dest++ = *pa++;
1422 --na;
1423 if (na == 1)
1424 goto CopyB;
1425 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
Tim Peterse05f65a2002-08-10 05:21:15 +00001426 ++min_gallop; /* penalize it for leaving galloping mode */
1427 ms->min_gallop = min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001428 }
1429Succeed:
1430 result = 0;
1431Fail:
1432 if (na)
1433 memcpy(dest, pa, na * sizeof(PyObject*));
1434 return result;
1435CopyB:
1436 assert(na == 1 && nb > 0);
1437 /* The last element of pa belongs at the end of the merge. */
1438 memmove(dest, pb, nb * sizeof(PyObject *));
1439 dest[nb] = *pa;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001440 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001441}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001442
Tim Petersa64dc242002-08-01 02:13:36 +00001443/* Merge the na elements starting at pa with the nb elements starting at pb
1444 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1445 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1446 * merge, and should have na >= nb. See listsort.txt for more info.
1447 * Return 0 if successful, -1 if error.
1448 */
1449static int
1450merge_hi(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb)
1451{
1452 int k;
1453 PyObject *compare;
1454 PyObject **dest;
1455 int result = -1; /* guilty until proved innocent */
1456 PyObject **basea;
1457 PyObject **baseb;
Tim Peterse05f65a2002-08-10 05:21:15 +00001458 int min_gallop = ms->min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001459
1460 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1461 if (MERGE_GETMEM(ms, nb) < 0)
1462 return -1;
1463 dest = pb + nb - 1;
1464 memcpy(ms->a, pb, nb * sizeof(PyObject*));
1465 basea = pa;
1466 baseb = ms->a;
1467 pb = ms->a + nb - 1;
1468 pa += na - 1;
1469
1470 *dest-- = *pa--;
1471 --na;
1472 if (na == 0)
1473 goto Succeed;
1474 if (nb == 1)
1475 goto CopyA;
1476
1477 compare = ms->compare;
1478 for (;;) {
1479 int acount = 0; /* # of times A won in a row */
1480 int bcount = 0; /* # of times B won in a row */
1481
1482 /* Do the straightforward thing until (if ever) one run
1483 * appears to win consistently.
1484 */
1485 for (;;) {
Tim Peterse05f65a2002-08-10 05:21:15 +00001486 assert(na > 0 && nb > 1);
Tim Peters66860f62002-08-04 17:47:26 +00001487 k = ISLT(*pb, *pa, compare);
Tim Petersa64dc242002-08-01 02:13:36 +00001488 if (k) {
1489 if (k < 0)
1490 goto Fail;
1491 *dest-- = *pa--;
1492 ++acount;
1493 bcount = 0;
1494 --na;
1495 if (na == 0)
1496 goto Succeed;
Tim Peterse05f65a2002-08-10 05:21:15 +00001497 if (acount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001498 break;
1499 }
1500 else {
1501 *dest-- = *pb--;
1502 ++bcount;
1503 acount = 0;
1504 --nb;
1505 if (nb == 1)
1506 goto CopyA;
Tim Peterse05f65a2002-08-10 05:21:15 +00001507 if (bcount >= min_gallop)
Tim Petersa64dc242002-08-01 02:13:36 +00001508 break;
1509 }
1510 }
1511
1512 /* One run is winning so consistently that galloping may
1513 * be a huge win. So try that, and continue galloping until
1514 * (if ever) neither run appears to be winning consistently
1515 * anymore.
1516 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001517 ++min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001518 do {
Tim Peterse05f65a2002-08-10 05:21:15 +00001519 assert(na > 0 && nb > 1);
1520 min_gallop -= min_gallop > 1;
1521 ms->min_gallop = min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001522 k = gallop_right(*pb, basea, na, na-1, compare);
1523 if (k < 0)
1524 goto Fail;
1525 k = na - k;
1526 acount = k;
1527 if (k) {
1528 dest -= k;
1529 pa -= k;
1530 memmove(dest+1, pa+1, k * sizeof(PyObject *));
1531 na -= k;
1532 if (na == 0)
1533 goto Succeed;
1534 }
1535 *dest-- = *pb--;
1536 --nb;
1537 if (nb == 1)
1538 goto CopyA;
1539
1540 k = gallop_left(*pa, baseb, nb, nb-1, compare);
1541 if (k < 0)
1542 goto Fail;
1543 k = nb - k;
1544 bcount = k;
1545 if (k) {
1546 dest -= k;
1547 pb -= k;
1548 memcpy(dest+1, pb+1, k * sizeof(PyObject *));
1549 nb -= k;
1550 if (nb == 1)
1551 goto CopyA;
1552 /* nb==0 is impossible now if the comparison
1553 * function is consistent, but we can't assume
1554 * that it is.
1555 */
1556 if (nb == 0)
1557 goto Succeed;
1558 }
1559 *dest-- = *pa--;
1560 --na;
1561 if (na == 0)
1562 goto Succeed;
1563 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
Tim Peterse05f65a2002-08-10 05:21:15 +00001564 ++min_gallop; /* penalize it for leaving galloping mode */
1565 ms->min_gallop = min_gallop;
Tim Petersa64dc242002-08-01 02:13:36 +00001566 }
1567Succeed:
1568 result = 0;
1569Fail:
1570 if (nb)
1571 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
1572 return result;
1573CopyA:
1574 assert(nb == 1 && na > 0);
1575 /* The first element of pb belongs at the front of the merge. */
1576 dest -= na;
1577 pa -= na;
1578 memmove(dest+1, pa+1, na * sizeof(PyObject *));
1579 *dest = *pb;
1580 return 0;
1581}
1582
1583/* Merge the two runs at stack indices i and i+1.
1584 * Returns 0 on success, -1 on error.
1585 */
1586static int
1587merge_at(MergeState *ms, int i)
1588{
1589 PyObject **pa, **pb;
1590 int na, nb;
1591 int k;
1592 PyObject *compare;
1593
1594 assert(ms != NULL);
1595 assert(ms->n >= 2);
1596 assert(i >= 0);
1597 assert(i == ms->n - 2 || i == ms->n - 3);
1598
Tim Peterse05f65a2002-08-10 05:21:15 +00001599 pa = ms->pending[i].base;
1600 na = ms->pending[i].len;
1601 pb = ms->pending[i+1].base;
1602 nb = ms->pending[i+1].len;
Tim Petersa64dc242002-08-01 02:13:36 +00001603 assert(na > 0 && nb > 0);
1604 assert(pa + na == pb);
1605
1606 /* Record the length of the combined runs; if i is the 3rd-last
1607 * run now, also slide over the last run (which isn't involved
1608 * in this merge). The current run i+1 goes away in any case.
1609 */
Tim Peterse05f65a2002-08-10 05:21:15 +00001610 ms->pending[i].len = na + nb;
1611 if (i == ms->n - 3)
1612 ms->pending[i+1] = ms->pending[i+2];
Tim Petersa64dc242002-08-01 02:13:36 +00001613 --ms->n;
1614
1615 /* Where does b start in a? Elements in a before that can be
1616 * ignored (already in place).
1617 */
1618 compare = ms->compare;
1619 k = gallop_right(*pb, pa, na, 0, compare);
1620 if (k < 0)
1621 return -1;
1622 pa += k;
1623 na -= k;
1624 if (na == 0)
1625 return 0;
1626
1627 /* Where does a end in b? Elements in b after that can be
1628 * ignored (already in place).
1629 */
1630 nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);
1631 if (nb <= 0)
1632 return nb;
1633
1634 /* Merge what remains of the runs, using a temp array with
1635 * min(na, nb) elements.
1636 */
1637 if (na <= nb)
1638 return merge_lo(ms, pa, na, pb, nb);
1639 else
1640 return merge_hi(ms, pa, na, pb, nb);
1641}
1642
1643/* Examine the stack of runs waiting to be merged, merging adjacent runs
1644 * until the stack invariants are re-established:
1645 *
1646 * 1. len[-3] > len[-2] + len[-1]
1647 * 2. len[-2] > len[-1]
1648 *
1649 * See listsort.txt for more info.
1650 *
1651 * Returns 0 on success, -1 on error.
1652 */
1653static int
1654merge_collapse(MergeState *ms)
1655{
Tim Peterse05f65a2002-08-10 05:21:15 +00001656 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001657
1658 assert(ms);
1659 while (ms->n > 1) {
1660 int n = ms->n - 2;
Tim Peterse05f65a2002-08-10 05:21:15 +00001661 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
1662 if (p[n-1].len < p[n+1].len)
Tim Petersa64dc242002-08-01 02:13:36 +00001663 --n;
1664 if (merge_at(ms, n) < 0)
1665 return -1;
1666 }
Tim Peterse05f65a2002-08-10 05:21:15 +00001667 else if (p[n].len <= p[n+1].len) {
Tim Petersa64dc242002-08-01 02:13:36 +00001668 if (merge_at(ms, n) < 0)
1669 return -1;
1670 }
1671 else
1672 break;
1673 }
1674 return 0;
1675}
1676
1677/* Regardless of invariants, merge all runs on the stack until only one
1678 * remains. This is used at the end of the mergesort.
1679 *
1680 * Returns 0 on success, -1 on error.
1681 */
1682static int
1683merge_force_collapse(MergeState *ms)
1684{
Tim Peterse05f65a2002-08-10 05:21:15 +00001685 struct s_slice *p = ms->pending;
Tim Petersa64dc242002-08-01 02:13:36 +00001686
1687 assert(ms);
1688 while (ms->n > 1) {
1689 int n = ms->n - 2;
Tim Peterse05f65a2002-08-10 05:21:15 +00001690 if (n > 0 && p[n-1].len < p[n+1].len)
Tim Petersa64dc242002-08-01 02:13:36 +00001691 --n;
1692 if (merge_at(ms, n) < 0)
1693 return -1;
1694 }
1695 return 0;
1696}
1697
1698/* Compute a good value for the minimum run length; natural runs shorter
1699 * than this are boosted artificially via binary insertion.
1700 *
1701 * If n < 64, return n (it's too small to bother with fancy stuff).
1702 * Else if n is an exact power of 2, return 32.
1703 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1704 * strictly less than, an exact power of 2.
1705 *
1706 * See listsort.txt for more info.
1707 */
1708static int
1709merge_compute_minrun(int n)
1710{
1711 int r = 0; /* becomes 1 if any 1 bits are shifted off */
1712
1713 assert(n >= 0);
1714 while (n >= 64) {
1715 r |= n & 1;
1716 n >>= 1;
1717 }
1718 return n + r;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001719}
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001720
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001721/* Special wrapper to support stable sorting using the decorate-sort-undecorate
1722 pattern. Holds a key which is used for comparisions and the original record
1723 which is returned during the undecorate phase. By exposing only the key
1724 during comparisons, the underlying sort stability characteristics are left
1725 unchanged. Also, if a custom comparison function is used, it will only see
1726 the key instead of a full record. */
1727
1728typedef struct {
1729 PyObject_HEAD
1730 PyObject *key;
1731 PyObject *value;
1732} sortwrapperobject;
1733
1734static PyTypeObject sortwrapper_type;
1735
1736static PyObject *
1737sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
1738{
1739 if (!PyObject_TypeCheck(b, &sortwrapper_type)) {
1740 PyErr_SetString(PyExc_TypeError,
1741 "expected a sortwrapperobject");
1742 return NULL;
1743 }
1744 return PyObject_RichCompare(a->key, b->key, op);
1745}
1746
1747static void
1748sortwrapper_dealloc(sortwrapperobject *so)
1749{
1750 Py_XDECREF(so->key);
1751 Py_XDECREF(so->value);
1752 PyObject_Del(so);
1753}
1754
1755PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key.");
1756
1757static PyTypeObject sortwrapper_type = {
1758 PyObject_HEAD_INIT(&PyType_Type)
1759 0, /* ob_size */
1760 "sortwrapper", /* tp_name */
1761 sizeof(sortwrapperobject), /* tp_basicsize */
1762 0, /* tp_itemsize */
1763 /* methods */
1764 (destructor)sortwrapper_dealloc, /* tp_dealloc */
1765 0, /* tp_print */
1766 0, /* tp_getattr */
1767 0, /* tp_setattr */
1768 0, /* tp_compare */
1769 0, /* tp_repr */
1770 0, /* tp_as_number */
1771 0, /* tp_as_sequence */
1772 0, /* tp_as_mapping */
1773 0, /* tp_hash */
1774 0, /* tp_call */
1775 0, /* tp_str */
1776 PyObject_GenericGetAttr, /* tp_getattro */
1777 0, /* tp_setattro */
1778 0, /* tp_as_buffer */
1779 Py_TPFLAGS_DEFAULT |
1780 Py_TPFLAGS_HAVE_RICHCOMPARE, /* tp_flags */
1781 sortwrapper_doc, /* tp_doc */
1782 0, /* tp_traverse */
1783 0, /* tp_clear */
1784 (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */
1785};
1786
1787/* Returns a new reference to a sortwrapper.
1788 Consumes the references to the two underlying objects. */
1789
1790static PyObject *
1791build_sortwrapper(PyObject *key, PyObject *value)
1792{
1793 sortwrapperobject *so;
1794
1795 so = PyObject_New(sortwrapperobject, &sortwrapper_type);
1796 if (so == NULL)
1797 return NULL;
1798 so->key = key;
1799 so->value = value;
1800 return (PyObject *)so;
1801}
1802
1803/* Returns a new reference to the value underlying the wrapper. */
1804static PyObject *
1805sortwrapper_getvalue(PyObject *so)
1806{
1807 PyObject *value;
1808
1809 if (!PyObject_TypeCheck(so, &sortwrapper_type)) {
1810 PyErr_SetString(PyExc_TypeError,
1811 "expected a sortwrapperobject");
1812 return NULL;
1813 }
1814 value = ((sortwrapperobject *)so)->value;
1815 Py_INCREF(value);
1816 return value;
1817}
1818
1819/* Wrapper for user specified cmp functions in combination with a
1820 specified key function. Makes sure the cmp function is presented
1821 with the actual key instead of the sortwrapper */
1822
1823typedef struct {
1824 PyObject_HEAD
1825 PyObject *func;
1826} cmpwrapperobject;
1827
1828static void
1829cmpwrapper_dealloc(cmpwrapperobject *co)
1830{
1831 Py_XDECREF(co->func);
1832 PyObject_Del(co);
1833}
1834
1835static PyObject *
1836cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds)
1837{
1838 PyObject *x, *y, *xx, *yy;
1839
1840 if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y))
1841 return NULL;
1842 if (!PyObject_TypeCheck(x, &sortwrapper_type) ||
Raymond Hettingerae4a2992003-10-16 17:16:30 +00001843 !PyObject_TypeCheck(y, &sortwrapper_type)) {
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001844 PyErr_SetString(PyExc_TypeError,
1845 "expected a sortwrapperobject");
1846 return NULL;
1847 }
1848 xx = ((sortwrapperobject *)x)->key;
1849 yy = ((sortwrapperobject *)y)->key;
1850 return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL);
1851}
1852
1853PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys.");
1854
1855static PyTypeObject cmpwrapper_type = {
1856 PyObject_HEAD_INIT(&PyType_Type)
1857 0, /* ob_size */
1858 "cmpwrapper", /* tp_name */
1859 sizeof(cmpwrapperobject), /* tp_basicsize */
1860 0, /* tp_itemsize */
1861 /* methods */
1862 (destructor)cmpwrapper_dealloc, /* tp_dealloc */
1863 0, /* tp_print */
1864 0, /* tp_getattr */
1865 0, /* tp_setattr */
1866 0, /* tp_compare */
1867 0, /* tp_repr */
1868 0, /* tp_as_number */
1869 0, /* tp_as_sequence */
1870 0, /* tp_as_mapping */
1871 0, /* tp_hash */
1872 (ternaryfunc)cmpwrapper_call, /* tp_call */
1873 0, /* tp_str */
1874 PyObject_GenericGetAttr, /* tp_getattro */
1875 0, /* tp_setattro */
1876 0, /* tp_as_buffer */
1877 Py_TPFLAGS_DEFAULT, /* tp_flags */
1878 cmpwrapper_doc, /* tp_doc */
1879};
1880
1881static PyObject *
1882build_cmpwrapper(PyObject *cmpfunc)
1883{
1884 cmpwrapperobject *co;
1885
1886 co = PyObject_New(cmpwrapperobject, &cmpwrapper_type);
1887 if (co == NULL)
1888 return NULL;
1889 Py_INCREF(cmpfunc);
1890 co->func = cmpfunc;
1891 return (PyObject *)co;
1892}
1893
Tim Petersa64dc242002-08-01 02:13:36 +00001894/* An adaptive, stable, natural mergesort. See listsort.txt.
1895 * Returns Py_None on success, NULL on error. Even in case of error, the
1896 * list will be some permutation of its input state (nothing is lost or
1897 * duplicated).
1898 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001899static PyObject *
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001900listsort(PyListObject *self, PyObject *args, PyObject *kwds)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001901{
Tim Petersa64dc242002-08-01 02:13:36 +00001902 MergeState ms;
1903 PyObject **lo, **hi;
1904 int nremaining;
1905 int minrun;
Raymond Hettinger4bb95402004-02-13 11:36:39 +00001906 int saved_ob_size, saved_allocated;
Tim Petersb9099c32002-11-12 22:08:10 +00001907 PyObject **saved_ob_item;
1908 PyObject **empty_ob_item;
Tim Petersa64dc242002-08-01 02:13:36 +00001909 PyObject *compare = NULL;
1910 PyObject *result = NULL; /* guilty until proved innocent */
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001911 int reverse = 0;
1912 PyObject *keyfunc = NULL;
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001913 int i;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001914 PyObject *key, *value, *kvpair;
1915 static char *kwlist[] = {"cmp", "key", "reverse", 0};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001916
Tim Petersa64dc242002-08-01 02:13:36 +00001917 assert(self != NULL);
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001918 assert (PyList_Check(self));
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001919 if (args != NULL) {
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001920 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",
1921 kwlist, &compare, &keyfunc, &reverse))
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001922 return NULL;
1923 }
Skip Montanaro4abd5f02003-01-02 20:51:08 +00001924 if (compare == Py_None)
1925 compare = NULL;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001926 if (keyfunc == Py_None)
1927 keyfunc = NULL;
1928 if (compare != NULL && keyfunc != NULL) {
1929 compare = build_cmpwrapper(compare);
1930 if (compare == NULL)
Hye-Shik Chang19cb1932003-12-10 07:31:08 +00001931 return NULL;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00001932 } else
1933 Py_XINCREF(compare);
1934
Tim Petersb9099c32002-11-12 22:08:10 +00001935 /* The list is temporarily made empty, so that mutations performed
1936 * by comparison functions can't affect the slice of memory we're
1937 * sorting (allowing mutations during sorting is a core-dump
1938 * factory, since ob_item may change).
1939 */
1940 saved_ob_size = self->ob_size;
1941 saved_ob_item = self->ob_item;
Raymond Hettinger4bb95402004-02-13 11:36:39 +00001942 saved_allocated = self->allocated;
Tim Petersb9099c32002-11-12 22:08:10 +00001943 self->ob_size = 0;
Tim Peters7049d812004-01-18 20:31:02 +00001944 self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0);
Raymond Hettinger4bb95402004-02-13 11:36:39 +00001945 self->allocated = 0;
Tim Peters330f9e92002-07-19 07:05:44 +00001946
Michael W. Hudson1df0f652003-12-04 11:25:46 +00001947 if (keyfunc != NULL) {
1948 for (i=0 ; i < saved_ob_size ; i++) {
1949 value = saved_ob_item[i];
1950 key = PyObject_CallFunctionObjArgs(keyfunc, value,
1951 NULL);
1952 if (key == NULL) {
1953 for (i=i-1 ; i>=0 ; i--) {
1954 kvpair = saved_ob_item[i];
1955 value = sortwrapper_getvalue(kvpair);
1956 saved_ob_item[i] = value;
1957 Py_DECREF(kvpair);
1958 }
1959 if (self->ob_item != empty_ob_item
1960 || self->ob_size) {
1961 /* If the list changed *as well* we
1962 have two errors. We let the first
1963 one "win", but we shouldn't let
1964 what's in the list currently
1965 leak. */
1966 (void)list_ass_slice(
1967 self, 0, self->ob_size,
1968 (PyObject *)NULL);
1969 }
1970
1971 goto dsu_fail;
1972 }
1973 kvpair = build_sortwrapper(key, value);
1974 if (kvpair == NULL)
1975 goto dsu_fail;
1976 saved_ob_item[i] = kvpair;
1977 }
1978 }
1979
1980 /* Reverse sort stability achieved by initially reversing the list,
1981 applying a stable forward sort, then reversing the final result. */
1982 if (reverse && saved_ob_size > 1)
1983 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
1984
1985 merge_init(&ms, compare);
1986
Tim Petersb9099c32002-11-12 22:08:10 +00001987 nremaining = saved_ob_size;
Tim Petersa64dc242002-08-01 02:13:36 +00001988 if (nremaining < 2)
1989 goto succeed;
Tim Peters330f9e92002-07-19 07:05:44 +00001990
Tim Petersa64dc242002-08-01 02:13:36 +00001991 /* March over the array once, left to right, finding natural runs,
1992 * and extending short natural runs to minrun elements.
1993 */
Tim Petersb9099c32002-11-12 22:08:10 +00001994 lo = saved_ob_item;
Tim Petersa64dc242002-08-01 02:13:36 +00001995 hi = lo + nremaining;
1996 minrun = merge_compute_minrun(nremaining);
1997 do {
1998 int descending;
1999 int n;
Tim Peters330f9e92002-07-19 07:05:44 +00002000
Tim Petersa64dc242002-08-01 02:13:36 +00002001 /* Identify next run. */
2002 n = count_run(lo, hi, compare, &descending);
2003 if (n < 0)
2004 goto fail;
2005 if (descending)
2006 reverse_slice(lo, lo + n);
2007 /* If short, extend to min(minrun, nremaining). */
2008 if (n < minrun) {
2009 const int force = nremaining <= minrun ?
2010 nremaining : minrun;
2011 if (binarysort(lo, lo + force, lo + n, compare) < 0)
2012 goto fail;
2013 n = force;
2014 }
2015 /* Push run onto pending-runs stack, and maybe merge. */
2016 assert(ms.n < MAX_MERGE_PENDING);
Tim Peterse05f65a2002-08-10 05:21:15 +00002017 ms.pending[ms.n].base = lo;
2018 ms.pending[ms.n].len = n;
Tim Petersa64dc242002-08-01 02:13:36 +00002019 ++ms.n;
2020 if (merge_collapse(&ms) < 0)
2021 goto fail;
2022 /* Advance to find next run. */
2023 lo += n;
2024 nremaining -= n;
2025 } while (nremaining);
2026 assert(lo == hi);
Tim Peters330f9e92002-07-19 07:05:44 +00002027
Tim Petersa64dc242002-08-01 02:13:36 +00002028 if (merge_force_collapse(&ms) < 0)
2029 goto fail;
2030 assert(ms.n == 1);
Tim Petersb9099c32002-11-12 22:08:10 +00002031 assert(ms.pending[0].base == saved_ob_item);
2032 assert(ms.pending[0].len == saved_ob_size);
Tim Petersa64dc242002-08-01 02:13:36 +00002033
2034succeed:
2035 result = Py_None;
Tim Peters330f9e92002-07-19 07:05:44 +00002036fail:
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002037 if (keyfunc != NULL) {
2038 for (i=0 ; i < saved_ob_size ; i++) {
2039 kvpair = saved_ob_item[i];
2040 value = sortwrapper_getvalue(kvpair);
2041 saved_ob_item[i] = value;
2042 Py_DECREF(kvpair);
2043 }
2044 }
2045
Tim Petersb9099c32002-11-12 22:08:10 +00002046 if (self->ob_item != empty_ob_item || self->ob_size) {
2047 /* The user mucked with the list during the sort. */
2048 (void)list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL);
2049 if (result != NULL) {
2050 PyErr_SetString(PyExc_ValueError,
2051 "list modified during sort");
2052 result = NULL;
2053 }
2054 }
Michael W. Hudson1df0f652003-12-04 11:25:46 +00002055
2056 if (reverse && saved_ob_size > 1)
2057 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
2058
2059 merge_freemem(&ms);
2060
2061dsu_fail:
Tim Petersb9099c32002-11-12 22:08:10 +00002062 if (self->ob_item == empty_ob_item)
2063 PyMem_FREE(empty_ob_item);
2064 self->ob_size = saved_ob_size;
2065 self->ob_item = saved_ob_item;
Raymond Hettinger4bb95402004-02-13 11:36:39 +00002066 self->allocated = saved_allocated;
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002067 Py_XDECREF(compare);
Tim Petersa64dc242002-08-01 02:13:36 +00002068 Py_XINCREF(result);
2069 return result;
Guido van Rossum3f236de1996-12-10 23:55:39 +00002070}
Tim Peters330f9e92002-07-19 07:05:44 +00002071#undef IFLT
Tim Peters66860f62002-08-04 17:47:26 +00002072#undef ISLT
Tim Peters330f9e92002-07-19 07:05:44 +00002073
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002074int
Fred Drakea2f55112000-07-09 15:16:51 +00002075PyList_Sort(PyObject *v)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002076{
2077 if (v == NULL || !PyList_Check(v)) {
2078 PyErr_BadInternalCall();
2079 return -1;
2080 }
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002081 v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002082 if (v == NULL)
2083 return -1;
2084 Py_DECREF(v);
2085 return 0;
2086}
2087
Guido van Rossumb86c5492001-02-12 22:06:02 +00002088static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002089listreverse(PyListObject *self)
Guido van Rossumb86c5492001-02-12 22:06:02 +00002090{
Tim Peters326b4482002-07-19 04:04:16 +00002091 if (self->ob_size > 1)
2092 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002093 Py_INCREF(Py_None);
2094 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00002095}
2096
Guido van Rossum84c76f51990-10-30 13:32:20 +00002097int
Fred Drakea2f55112000-07-09 15:16:51 +00002098PyList_Reverse(PyObject *v)
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002099{
Tim Peters6063e262002-08-08 01:06:39 +00002100 PyListObject *self = (PyListObject *)v;
2101
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002102 if (v == NULL || !PyList_Check(v)) {
2103 PyErr_BadInternalCall();
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002104 return -1;
2105 }
Tim Peters6063e262002-08-08 01:06:39 +00002106 if (self->ob_size > 1)
2107 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00002108 return 0;
2109}
2110
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002111PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00002112PyList_AsTuple(PyObject *v)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002113{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002114 PyObject *w;
2115 PyObject **p;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002116 int n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002117 if (v == NULL || !PyList_Check(v)) {
2118 PyErr_BadInternalCall();
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002119 return NULL;
2120 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002121 n = ((PyListObject *)v)->ob_size;
2122 w = PyTuple_New(n);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002123 if (w == NULL)
2124 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002125 p = ((PyTupleObject *)w)->ob_item;
Thomas Wouters334fb892000-07-25 12:56:38 +00002126 memcpy((void *)p,
2127 (void *)((PyListObject *)v)->ob_item,
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002128 n*sizeof(PyObject *));
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002129 while (--n >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002130 Py_INCREF(*p);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00002131 p++;
2132 }
2133 return w;
2134}
2135
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002136static PyObject *
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002137listindex(PyListObject *self, PyObject *args)
Guido van Rossumed98d481991-03-06 13:07:53 +00002138{
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002139 int i, start=0, stop=self->ob_size;
2140 PyObject *v;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002141
Walter Dörwalde8049bef2003-06-17 19:27:39 +00002142 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
2143 _PyEval_SliceIndex, &start,
2144 _PyEval_SliceIndex, &stop))
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002145 return NULL;
Guido van Rossum2743d872003-06-17 14:25:14 +00002146 if (start < 0) {
2147 start += self->ob_size;
2148 if (start < 0)
2149 start = 0;
2150 }
2151 if (stop < 0) {
2152 stop += self->ob_size;
2153 if (stop < 0)
2154 stop = 0;
2155 }
2156 else if (stop > self->ob_size)
2157 stop = self->ob_size;
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002158 for (i = start; i < stop; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002159 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2160 if (cmp > 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002161 return PyInt_FromLong((long)i);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002162 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00002163 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002164 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002165 PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00002166 return NULL;
2167}
2168
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002169static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002170listcount(PyListObject *self, PyObject *v)
Guido van Rossume6f7d181991-10-20 20:20:40 +00002171{
2172 int count = 0;
2173 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002174
Guido van Rossume6f7d181991-10-20 20:20:40 +00002175 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002176 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2177 if (cmp > 0)
Guido van Rossume6f7d181991-10-20 20:20:40 +00002178 count++;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002179 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00002180 return NULL;
Guido van Rossume6f7d181991-10-20 20:20:40 +00002181 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002182 return PyInt_FromLong((long)count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00002183}
2184
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002185static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002186listremove(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00002187{
2188 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00002189
Guido van Rossumed98d481991-03-06 13:07:53 +00002190 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002191 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
2192 if (cmp > 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002193 if (list_ass_slice(self, i, i+1,
2194 (PyObject *)NULL) != 0)
Guido van Rossumed98d481991-03-06 13:07:53 +00002195 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002196 Py_INCREF(Py_None);
2197 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00002198 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002199 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00002200 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00002201 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002202 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00002203 return NULL;
2204}
2205
Jeremy Hylton8caad492000-06-23 14:18:11 +00002206static int
2207list_traverse(PyListObject *o, visitproc visit, void *arg)
2208{
2209 int i, err;
2210 PyObject *x;
2211
2212 for (i = o->ob_size; --i >= 0; ) {
2213 x = o->ob_item[i];
2214 if (x != NULL) {
2215 err = visit(x, arg);
2216 if (err)
2217 return err;
2218 }
2219 }
2220 return 0;
2221}
2222
2223static int
2224list_clear(PyListObject *lp)
2225{
2226 (void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
2227 return 0;
2228}
2229
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002230static PyObject *
2231list_richcompare(PyObject *v, PyObject *w, int op)
2232{
2233 PyListObject *vl, *wl;
2234 int i;
2235
2236 if (!PyList_Check(v) || !PyList_Check(w)) {
2237 Py_INCREF(Py_NotImplemented);
2238 return Py_NotImplemented;
2239 }
2240
2241 vl = (PyListObject *)v;
2242 wl = (PyListObject *)w;
2243
2244 if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
2245 /* Shortcut: if the lengths differ, the lists differ */
2246 PyObject *res;
2247 if (op == Py_EQ)
2248 res = Py_False;
2249 else
2250 res = Py_True;
2251 Py_INCREF(res);
2252 return res;
2253 }
2254
2255 /* Search for the first index where items are different */
2256 for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
2257 int k = PyObject_RichCompareBool(vl->ob_item[i],
2258 wl->ob_item[i], Py_EQ);
2259 if (k < 0)
2260 return NULL;
2261 if (!k)
2262 break;
2263 }
2264
2265 if (i >= vl->ob_size || i >= wl->ob_size) {
2266 /* No more items to compare -- compare sizes */
2267 int vs = vl->ob_size;
2268 int ws = wl->ob_size;
2269 int cmp;
2270 PyObject *res;
2271 switch (op) {
2272 case Py_LT: cmp = vs < ws; break;
Tim Peters6ee42342001-07-06 17:45:43 +00002273 case Py_LE: cmp = vs <= ws; break;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002274 case Py_EQ: cmp = vs == ws; break;
2275 case Py_NE: cmp = vs != ws; break;
2276 case Py_GT: cmp = vs > ws; break;
2277 case Py_GE: cmp = vs >= ws; break;
2278 default: return NULL; /* cannot happen */
2279 }
2280 if (cmp)
2281 res = Py_True;
2282 else
2283 res = Py_False;
2284 Py_INCREF(res);
2285 return res;
2286 }
2287
2288 /* We have an item that differs -- shortcuts for EQ/NE */
2289 if (op == Py_EQ) {
2290 Py_INCREF(Py_False);
2291 return Py_False;
2292 }
2293 if (op == Py_NE) {
2294 Py_INCREF(Py_True);
2295 return Py_True;
2296 }
2297
2298 /* Compare the final item again using the proper operator */
2299 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
2300}
2301
Tim Peters6d6c1a32001-08-02 04:15:00 +00002302static int
2303list_init(PyListObject *self, PyObject *args, PyObject *kw)
2304{
2305 PyObject *arg = NULL;
2306 static char *kwlist[] = {"sequence", 0};
2307
2308 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
2309 return -1;
Raymond Hettinger90a39bf2004-02-15 03:57:00 +00002310 /* Empty previous contents */
2311 if (self->ob_size != 0) {
2312 if (list_ass_slice(self, 0, self->ob_size, (PyObject *)NULL) != 0)
2313 return -1;
2314 }
2315 if (arg != NULL) {
2316 PyObject *rv = listextend(self, arg);
2317 if (rv == NULL)
2318 return -1;
2319 Py_DECREF(rv);
2320 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00002321 return 0;
2322}
2323
Guido van Rossumdbb53d92001-12-03 16:32:18 +00002324static long
2325list_nohash(PyObject *self)
2326{
2327 PyErr_SetString(PyExc_TypeError, "list objects are unhashable");
2328 return -1;
2329}
2330
Raymond Hettinger1021c442003-11-07 15:38:09 +00002331static PyObject *list_iter(PyObject *seq);
2332static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
2333
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002334PyDoc_STRVAR(getitem_doc,
2335"x.__getitem__(y) <==> x[y]");
Raymond Hettinger1021c442003-11-07 15:38:09 +00002336PyDoc_STRVAR(reversed_doc,
2337"L.__reversed__() -- return a reverse iterator over the list");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002338PyDoc_STRVAR(append_doc,
2339"L.append(object) -- append object to end");
2340PyDoc_STRVAR(extend_doc,
Raymond Hettingerf8bcfb12002-12-29 05:49:09 +00002341"L.extend(iterable) -- extend list by appending elements from the iterable");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002342PyDoc_STRVAR(insert_doc,
2343"L.insert(index, object) -- insert object before index");
2344PyDoc_STRVAR(pop_doc,
2345"L.pop([index]) -> item -- remove and return item at index (default last)");
2346PyDoc_STRVAR(remove_doc,
2347"L.remove(value) -- remove first occurrence of value");
2348PyDoc_STRVAR(index_doc,
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002349"L.index(value, [start, [stop]]) -> integer -- return first index of value");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002350PyDoc_STRVAR(count_doc,
2351"L.count(value) -> integer -- return number of occurrences of value");
2352PyDoc_STRVAR(reverse_doc,
2353"L.reverse() -- reverse *IN PLACE*");
2354PyDoc_STRVAR(sort_doc,
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002355"L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
2356cmp(x, y) -> -1, 0, 1");
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00002357
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002358static PyObject *list_subscript(PyListObject*, PyObject*);
2359
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002360static PyMethodDef list_methods[] = {
Raymond Hettinger8f5cdaa2003-12-13 11:26:12 +00002361 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
Raymond Hettinger1021c442003-11-07 15:38:09 +00002362 {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002363 {"append", (PyCFunction)listappend, METH_O, append_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002364 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002365 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002366 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002367 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
Raymond Hettingerd05abde2003-06-17 05:05:49 +00002368 {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002369 {"count", (PyCFunction)listcount, METH_O, count_doc},
2370 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
Raymond Hettinger42b1ba32003-10-16 03:41:09 +00002371 {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
Tim Petersa64dc242002-08-01 02:13:36 +00002372 {NULL, NULL} /* sentinel */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002373};
2374
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002375static PySequenceMethods list_as_sequence = {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002376 (inquiry)list_length, /* sq_length */
2377 (binaryfunc)list_concat, /* sq_concat */
2378 (intargfunc)list_repeat, /* sq_repeat */
2379 (intargfunc)list_item, /* sq_item */
2380 (intintargfunc)list_slice, /* sq_slice */
2381 (intobjargproc)list_ass_item, /* sq_ass_item */
2382 (intintobjargproc)list_ass_slice, /* sq_ass_slice */
2383 (objobjproc)list_contains, /* sq_contains */
2384 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
2385 (intargfunc)list_inplace_repeat, /* sq_inplace_repeat */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002386};
2387
Neal Norwitz2c2e8272002-06-14 02:04:18 +00002388PyDoc_STRVAR(list_doc,
Tim Peters6d6c1a32001-08-02 04:15:00 +00002389"list() -> new list\n"
Neal Norwitz2c2e8272002-06-14 02:04:18 +00002390"list(sequence) -> new list initialized from sequence's items");
Tim Peters6d6c1a32001-08-02 04:15:00 +00002391
Jeremy Hyltona4b4c3b2002-07-13 03:51:17 +00002392static PyObject *
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002393list_subscript(PyListObject* self, PyObject* item)
2394{
2395 if (PyInt_Check(item)) {
2396 long i = PyInt_AS_LONG(item);
2397 if (i < 0)
2398 i += PyList_GET_SIZE(self);
2399 return list_item(self, i);
2400 }
2401 else if (PyLong_Check(item)) {
2402 long i = PyLong_AsLong(item);
2403 if (i == -1 && PyErr_Occurred())
2404 return NULL;
2405 if (i < 0)
2406 i += PyList_GET_SIZE(self);
2407 return list_item(self, i);
2408 }
2409 else if (PySlice_Check(item)) {
2410 int start, stop, step, slicelength, cur, i;
2411 PyObject* result;
2412 PyObject* it;
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002413 PyObject **src, **dest;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002414
2415 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2416 &start, &stop, &step, &slicelength) < 0) {
2417 return NULL;
2418 }
2419
2420 if (slicelength <= 0) {
2421 return PyList_New(0);
2422 }
2423 else {
2424 result = PyList_New(slicelength);
2425 if (!result) return NULL;
2426
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002427 src = self->ob_item;
2428 dest = ((PyListObject *)result)->ob_item;
Tim Peters3b01a122002-07-19 02:35:45 +00002429 for (cur = start, i = 0; i < slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002430 cur += step, i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002431 it = src[cur];
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002432 Py_INCREF(it);
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002433 dest[i] = it;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002434 }
Tim Peters3b01a122002-07-19 02:35:45 +00002435
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002436 return result;
2437 }
2438 }
2439 else {
2440 PyErr_SetString(PyExc_TypeError,
2441 "list indices must be integers");
2442 return NULL;
2443 }
2444}
2445
Tim Peters3b01a122002-07-19 02:35:45 +00002446static int
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002447list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2448{
2449 if (PyInt_Check(item)) {
2450 long i = PyInt_AS_LONG(item);
2451 if (i < 0)
2452 i += PyList_GET_SIZE(self);
2453 return list_ass_item(self, i, value);
2454 }
2455 else if (PyLong_Check(item)) {
2456 long i = PyLong_AsLong(item);
2457 if (i == -1 && PyErr_Occurred())
2458 return -1;
2459 if (i < 0)
2460 i += PyList_GET_SIZE(self);
2461 return list_ass_item(self, i, value);
2462 }
2463 else if (PySlice_Check(item)) {
2464 int start, stop, step, slicelength;
2465
2466 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2467 &start, &stop, &step, &slicelength) < 0) {
2468 return -1;
2469 }
2470
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002471 /* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
2472 if (step == 1 && ((PySliceObject*)item)->step == Py_None)
2473 return list_ass_slice(self, start, stop, value);
2474
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002475 if (value == NULL) {
2476 /* delete slice */
Raymond Hettinger4bb95402004-02-13 11:36:39 +00002477 PyObject **garbage;
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002478 int cur, i;
Tim Peters3b01a122002-07-19 02:35:45 +00002479
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002480 if (slicelength <= 0)
2481 return 0;
2482
2483 if (step < 0) {
2484 stop = start + 1;
2485 start = stop + step*(slicelength - 1) - 1;
2486 step = -step;
2487 }
2488
2489 garbage = (PyObject**)
2490 PyMem_MALLOC(slicelength*sizeof(PyObject*));
Tim Peters3b01a122002-07-19 02:35:45 +00002491
2492 /* drawing pictures might help
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002493 understand these for loops */
Guido van Rossum75a20b12002-06-11 12:22:28 +00002494 for (cur = start, i = 0;
2495 cur < stop;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002496 cur += step, i++) {
2497 int lim = step;
2498
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002499 garbage[i] = PyList_GET_ITEM(self, cur);
2500
Michael W. Hudson56796f62002-07-29 14:35:04 +00002501 if (cur + step >= self->ob_size) {
2502 lim = self->ob_size - cur - 1;
2503 }
2504
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002505 memmove(self->ob_item + cur - i,
2506 self->ob_item + cur + 1,
2507 lim * sizeof(PyObject *));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002508 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002509
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002510 for (cur = start + slicelength*step + 1;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002511 cur < self->ob_size; cur++) {
2512 PyList_SET_ITEM(self, cur - slicelength,
2513 PyList_GET_ITEM(self, cur));
2514 }
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002515
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002516 self->ob_size -= slicelength;
Raymond Hettingerd4ff7412004-03-15 09:01:31 +00002517 list_resize(self, self->ob_size);
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002518
2519 for (i = 0; i < slicelength; i++) {
2520 Py_DECREF(garbage[i]);
2521 }
2522 PyMem_FREE(garbage);
2523
2524 return 0;
2525 }
2526 else {
2527 /* assign slice */
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002528 PyObject **garbage, *ins, *seq, **seqitems, **selfitems;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002529 int cur, i;
2530
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002531 /* protect against a[::-1] = a */
Tim Peters3b01a122002-07-19 02:35:45 +00002532 if (self == (PyListObject*)value) {
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002533 seq = list_slice((PyListObject*)value, 0,
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002534 PyList_GET_SIZE(value));
Tim Peters3b01a122002-07-19 02:35:45 +00002535 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002536 else {
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002537 seq = PySequence_Fast(value,
2538 "must assign iterable to extended slice");
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002539 if (!seq)
2540 return -1;
2541 }
2542
2543 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
2544 PyErr_Format(PyExc_ValueError,
2545 "attempt to assign sequence of size %d to extended slice of size %d",
2546 PySequence_Fast_GET_SIZE(seq),
2547 slicelength);
2548 Py_DECREF(seq);
2549 return -1;
2550 }
2551
2552 if (!slicelength) {
2553 Py_DECREF(seq);
2554 return 0;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002555 }
2556
2557 garbage = (PyObject**)
2558 PyMem_MALLOC(slicelength*sizeof(PyObject*));
Tim Peters3b01a122002-07-19 02:35:45 +00002559
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002560 selfitems = self->ob_item;
Raymond Hettinger42bec932004-03-12 16:38:17 +00002561 seqitems = PySequence_Fast_ITEMS(seq);
Tim Peters3b01a122002-07-19 02:35:45 +00002562 for (cur = start, i = 0; i < slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002563 cur += step, i++) {
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002564 garbage[i] = selfitems[cur];
2565 ins = seqitems[i];
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002566 Py_INCREF(ins);
Raymond Hettingera6366fe2004-03-09 13:05:22 +00002567 selfitems[cur] = ins;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002568 }
2569
2570 for (i = 0; i < slicelength; i++) {
2571 Py_DECREF(garbage[i]);
2572 }
Tim Peters3b01a122002-07-19 02:35:45 +00002573
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002574 PyMem_FREE(garbage);
Michael W. Hudsona69c0302002-12-05 21:32:32 +00002575 Py_DECREF(seq);
Tim Peters3b01a122002-07-19 02:35:45 +00002576
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002577 return 0;
2578 }
Tim Peters3b01a122002-07-19 02:35:45 +00002579 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002580 else {
Tim Peters3b01a122002-07-19 02:35:45 +00002581 PyErr_SetString(PyExc_TypeError,
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002582 "list indices must be integers");
2583 return -1;
2584 }
2585}
2586
2587static PyMappingMethods list_as_mapping = {
2588 (inquiry)list_length,
2589 (binaryfunc)list_subscript,
2590 (objobjargproc)list_ass_subscript
2591};
2592
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002593PyTypeObject PyList_Type = {
2594 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002595 0,
2596 "list",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002597 sizeof(PyListObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002598 0,
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002599 (destructor)list_dealloc, /* tp_dealloc */
2600 (printfunc)list_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002601 0, /* tp_getattr */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002602 0, /* tp_setattr */
2603 0, /* tp_compare */
2604 (reprfunc)list_repr, /* tp_repr */
2605 0, /* tp_as_number */
2606 &list_as_sequence, /* tp_as_sequence */
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002607 &list_as_mapping, /* tp_as_mapping */
Guido van Rossumdbb53d92001-12-03 16:32:18 +00002608 list_nohash, /* tp_hash */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002609 0, /* tp_call */
2610 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002611 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002612 0, /* tp_setattro */
2613 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002614 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Tim Peters6d6c1a32001-08-02 04:15:00 +00002615 Py_TPFLAGS_BASETYPE, /* tp_flags */
2616 list_doc, /* tp_doc */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002617 (traverseproc)list_traverse, /* tp_traverse */
2618 (inquiry)list_clear, /* tp_clear */
2619 list_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002620 0, /* tp_weaklistoffset */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002621 list_iter, /* tp_iter */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002622 0, /* tp_iternext */
2623 list_methods, /* tp_methods */
2624 0, /* tp_members */
2625 0, /* tp_getset */
2626 0, /* tp_base */
2627 0, /* tp_dict */
2628 0, /* tp_descr_get */
2629 0, /* tp_descr_set */
2630 0, /* tp_dictoffset */
2631 (initproc)list_init, /* tp_init */
2632 PyType_GenericAlloc, /* tp_alloc */
2633 PyType_GenericNew, /* tp_new */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002634 PyObject_GC_Del, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002635};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002636
2637
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002638/*********************** List Iterator **************************/
2639
2640typedef struct {
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002641 PyObject_HEAD
2642 long it_index;
Guido van Rossum86103ae2002-07-16 20:07:32 +00002643 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002644} listiterobject;
2645
2646PyTypeObject PyListIter_Type;
2647
Guido van Rossum5086e492002-07-16 15:56:52 +00002648static PyObject *
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002649list_iter(PyObject *seq)
2650{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002651 listiterobject *it;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002652
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002653 if (!PyList_Check(seq)) {
2654 PyErr_BadInternalCall();
2655 return NULL;
2656 }
2657 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2658 if (it == NULL)
2659 return NULL;
2660 it->it_index = 0;
2661 Py_INCREF(seq);
2662 it->it_seq = (PyListObject *)seq;
2663 _PyObject_GC_TRACK(it);
2664 return (PyObject *)it;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002665}
2666
2667static void
2668listiter_dealloc(listiterobject *it)
2669{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002670 _PyObject_GC_UNTRACK(it);
Guido van Rossum86103ae2002-07-16 20:07:32 +00002671 Py_XDECREF(it->it_seq);
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002672 PyObject_GC_Del(it);
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002673}
2674
2675static int
2676listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2677{
Guido van Rossum86103ae2002-07-16 20:07:32 +00002678 if (it->it_seq == NULL)
2679 return 0;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002680 return visit((PyObject *)it->it_seq, arg);
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002681}
2682
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002683static PyObject *
Tim Peters93b2cc42002-06-01 05:22:55 +00002684listiter_next(listiterobject *it)
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002685{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002686 PyListObject *seq;
2687 PyObject *item;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002688
Tim Peters93b2cc42002-06-01 05:22:55 +00002689 assert(it != NULL);
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002690 seq = it->it_seq;
Guido van Rossum86103ae2002-07-16 20:07:32 +00002691 if (seq == NULL)
2692 return NULL;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002693 assert(PyList_Check(seq));
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002694
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002695 if (it->it_index < PyList_GET_SIZE(seq)) {
Tim Peters93b2cc42002-06-01 05:22:55 +00002696 item = PyList_GET_ITEM(seq, it->it_index);
2697 ++it->it_index;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002698 Py_INCREF(item);
2699 return item;
2700 }
Guido van Rossum86103ae2002-07-16 20:07:32 +00002701
2702 Py_DECREF(seq);
2703 it->it_seq = NULL;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002704 return NULL;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002705}
2706
Raymond Hettinger435bf582004-03-18 22:43:10 +00002707static int
2708listiter_len(listiterobject *it)
2709{
Raymond Hettinger40a03822004-04-12 13:05:09 +00002710 int len;
2711 if (it->it_seq) {
2712 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
2713 if (len >= 0)
2714 return len;
2715 }
Raymond Hettinger435bf582004-03-18 22:43:10 +00002716 return 0;
2717}
2718
2719static PySequenceMethods listiter_as_sequence = {
2720 (inquiry)listiter_len, /* sq_length */
2721 0, /* sq_concat */
2722};
2723
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002724PyTypeObject PyListIter_Type = {
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002725 PyObject_HEAD_INIT(&PyType_Type)
2726 0, /* ob_size */
2727 "listiterator", /* tp_name */
2728 sizeof(listiterobject), /* tp_basicsize */
2729 0, /* tp_itemsize */
2730 /* methods */
2731 (destructor)listiter_dealloc, /* tp_dealloc */
2732 0, /* tp_print */
2733 0, /* tp_getattr */
2734 0, /* tp_setattr */
2735 0, /* tp_compare */
2736 0, /* tp_repr */
2737 0, /* tp_as_number */
Raymond Hettinger435bf582004-03-18 22:43:10 +00002738 &listiter_as_sequence, /* tp_as_sequence */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002739 0, /* tp_as_mapping */
2740 0, /* tp_hash */
2741 0, /* tp_call */
2742 0, /* tp_str */
2743 PyObject_GenericGetAttr, /* tp_getattro */
2744 0, /* tp_setattro */
2745 0, /* tp_as_buffer */
2746 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2747 0, /* tp_doc */
2748 (traverseproc)listiter_traverse, /* tp_traverse */
2749 0, /* tp_clear */
2750 0, /* tp_richcompare */
2751 0, /* tp_weaklistoffset */
Raymond Hettinger1da1dbf2003-03-17 19:46:11 +00002752 PyObject_SelfIter, /* tp_iter */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002753 (iternextfunc)listiter_next, /* tp_iternext */
Guido van Rossum86103ae2002-07-16 20:07:32 +00002754 0, /* tp_methods */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002755 0, /* tp_members */
2756 0, /* tp_getset */
2757 0, /* tp_base */
2758 0, /* tp_dict */
2759 0, /* tp_descr_get */
2760 0, /* tp_descr_set */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002761};
Raymond Hettinger1021c442003-11-07 15:38:09 +00002762
2763/*********************** List Reverse Iterator **************************/
2764
2765typedef struct {
2766 PyObject_HEAD
2767 long it_index;
Raymond Hettinger001f2282003-11-08 11:58:44 +00002768 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002769} listreviterobject;
2770
2771PyTypeObject PyListRevIter_Type;
2772
2773static PyObject *
2774list_reversed(PyListObject *seq, PyObject *unused)
2775{
2776 listreviterobject *it;
2777
2778 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
2779 if (it == NULL)
2780 return NULL;
2781 assert(PyList_Check(seq));
2782 it->it_index = PyList_GET_SIZE(seq) - 1;
2783 Py_INCREF(seq);
2784 it->it_seq = seq;
2785 PyObject_GC_Track(it);
2786 return (PyObject *)it;
2787}
2788
2789static void
2790listreviter_dealloc(listreviterobject *it)
2791{
2792 PyObject_GC_UnTrack(it);
2793 Py_XDECREF(it->it_seq);
2794 PyObject_GC_Del(it);
2795}
2796
2797static int
2798listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
2799{
2800 if (it->it_seq == NULL)
2801 return 0;
2802 return visit((PyObject *)it->it_seq, arg);
2803}
2804
2805static PyObject *
2806listreviter_next(listreviterobject *it)
2807{
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002808 PyObject *item;
2809 long index = it->it_index;
2810 PyListObject *seq = it->it_seq;
Raymond Hettinger1021c442003-11-07 15:38:09 +00002811
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002812 if (index>=0 && index < PyList_GET_SIZE(seq)) {
2813 item = PyList_GET_ITEM(seq, index);
Raymond Hettinger1021c442003-11-07 15:38:09 +00002814 it->it_index--;
2815 Py_INCREF(item);
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002816 return item;
Raymond Hettinger1021c442003-11-07 15:38:09 +00002817 }
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002818 it->it_index = -1;
2819 if (seq != NULL) {
2820 it->it_seq = NULL;
2821 Py_DECREF(seq);
2822 }
2823 return NULL;
Raymond Hettinger1021c442003-11-07 15:38:09 +00002824}
2825
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002826static int
2827listreviter_len(listreviterobject *it)
2828{
Raymond Hettinger40a03822004-04-12 13:05:09 +00002829 int len = it->it_index + 1;
2830 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
2831 return 0;
2832 return len;
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002833}
2834
2835static PySequenceMethods listreviter_as_sequence = {
2836 (inquiry)listreviter_len, /* sq_length */
2837 0, /* sq_concat */
2838};
2839
Raymond Hettinger1021c442003-11-07 15:38:09 +00002840PyTypeObject PyListRevIter_Type = {
2841 PyObject_HEAD_INIT(&PyType_Type)
2842 0, /* ob_size */
2843 "listreverseiterator", /* tp_name */
2844 sizeof(listreviterobject), /* tp_basicsize */
2845 0, /* tp_itemsize */
2846 /* methods */
2847 (destructor)listreviter_dealloc, /* tp_dealloc */
2848 0, /* tp_print */
2849 0, /* tp_getattr */
2850 0, /* tp_setattr */
2851 0, /* tp_compare */
2852 0, /* tp_repr */
2853 0, /* tp_as_number */
Raymond Hettingeref9bf402004-03-10 10:10:42 +00002854 &listreviter_as_sequence, /* tp_as_sequence */
Raymond Hettinger1021c442003-11-07 15:38:09 +00002855 0, /* tp_as_mapping */
2856 0, /* tp_hash */
2857 0, /* tp_call */
2858 0, /* tp_str */
2859 PyObject_GenericGetAttr, /* tp_getattro */
2860 0, /* tp_setattro */
2861 0, /* tp_as_buffer */
2862 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2863 0, /* tp_doc */
2864 (traverseproc)listreviter_traverse, /* tp_traverse */
2865 0, /* tp_clear */
2866 0, /* tp_richcompare */
2867 0, /* tp_weaklistoffset */
2868 PyObject_SelfIter, /* tp_iter */
2869 (iternextfunc)listreviter_next, /* tp_iternext */
2870 0,
2871};