blob: 1ff12d2181c9e3491da6444453a71e517ee9e96d [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
Fred Drakea2f55112000-07-09 15:16:51 +000012roundupsize(int n)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000013{
Tim Peters65b8b842001-05-26 05:28:40 +000014 unsigned int nbits = 0;
15 unsigned int n2 = (unsigned int)n >> 5;
16
Tim Peters3b01a122002-07-19 02:35:45 +000017 /* Round up:
Tim Peters65b8b842001-05-26 05:28:40 +000018 * If n < 256, to a multiple of 8.
19 * If n < 2048, to a multiple of 64.
20 * If n < 16384, to a multiple of 512.
21 * If n < 131072, to a multiple of 4096.
22 * If n < 1048576, to a multiple of 32768.
23 * If n < 8388608, to a multiple of 262144.
24 * If n < 67108864, to a multiple of 2097152.
25 * If n < 536870912, to a multiple of 16777216.
26 * ...
27 * If n < 2**(5+3*i), to a multiple of 2**(3*i).
28 *
29 * This over-allocates proportional to the list size, making room
30 * 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
33 * system realloc() (which is a reality, e.g., across all flavors
34 * of Windows, with Win9x behavior being particularly bad -- and
35 * we've still got address space fragmentation problems on Win9x
36 * even with this scheme, although it requires much longer lists to
37 * provoke them than it used to).
38 */
39 do {
40 n2 >>= 3;
41 nbits += 3;
42 } while (n2);
43 return ((n >> nbits) + 1) << nbits;
44 }
Guido van Rossuma46d51d1995-01-26 22:59:43 +000045
Neal Norwitzd4e5be52002-05-22 23:19:17 +000046#define NRESIZE(var, type, nitems) \
47do { \
48 size_t _new_size = roundupsize(nitems); \
49 if (_new_size <= ((~(size_t)0) / sizeof(type))) \
50 PyMem_RESIZE(var, type, _new_size); \
51 else \
52 var = NULL; \
53} while (0)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000054
Guido van Rossumc0b618a1997-05-02 03:12:38 +000055PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +000056PyList_New(int size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000057{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000058 PyListObject *op;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000059 size_t nbytes;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000060 if (size < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000061 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000062 return NULL;
63 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +000064 nbytes = size * sizeof(PyObject *);
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000065 /* Check for overflow */
Guido van Rossumc0b618a1997-05-02 03:12:38 +000066 if (nbytes / sizeof(PyObject *) != (size_t)size) {
67 return PyErr_NoMemory();
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000068 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +000069 op = PyObject_GC_New(PyListObject, &PyList_Type);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000070 if (op == NULL) {
Neil Schemenauere83c00e2001-08-29 23:54:21 +000071 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000072 }
73 if (size <= 0) {
74 op->ob_item = NULL;
75 }
76 else {
Guido van Rossumb18618d2000-05-03 23:44:39 +000077 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000078 if (op->ob_item == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000079 return PyErr_NoMemory();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000080 }
Neal Norwitz35fc7602002-06-13 21:11:11 +000081 memset(op->ob_item, 0, sizeof(*op->ob_item) * size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000082 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +000083 op->ob_size = size;
Neil Schemenauere83c00e2001-08-29 23:54:21 +000084 _PyObject_GC_TRACK(op);
Guido van Rossumc0b618a1997-05-02 03:12:38 +000085 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000086}
87
88int
Fred Drakea2f55112000-07-09 15:16:51 +000089PyList_Size(PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000090{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000091 if (!PyList_Check(op)) {
92 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000093 return -1;
94 }
95 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +000096 return ((PyListObject *)op) -> ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000097}
98
Guido van Rossumc0b618a1997-05-02 03:12:38 +000099static PyObject *indexerr;
Guido van Rossum929f1b81996-08-09 20:51:27 +0000100
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000101PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000102PyList_GetItem(PyObject *op, int i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000103{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000104 if (!PyList_Check(op)) {
105 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000106 return NULL;
107 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000108 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000109 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000110 indexerr = PyString_FromString(
111 "list index out of range");
112 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000113 return NULL;
114 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000115 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000116}
117
118int
Fred Drakea2f55112000-07-09 15:16:51 +0000119PyList_SetItem(register PyObject *op, register int i,
120 register PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000121{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000122 register PyObject *olditem;
123 register PyObject **p;
124 if (!PyList_Check(op)) {
125 Py_XDECREF(newitem);
126 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000127 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000128 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000129 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
130 Py_XDECREF(newitem);
131 PyErr_SetString(PyExc_IndexError,
132 "list assignment index out of range");
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000133 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000134 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000135 p = ((PyListObject *)op) -> ob_item + i;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000136 olditem = *p;
137 *p = newitem;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000138 Py_XDECREF(olditem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000139 return 0;
140}
141
142static int
Fred Drakea2f55112000-07-09 15:16:51 +0000143ins1(PyListObject *self, int where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000144{
145 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000146 PyObject **items;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000147 if (v == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000148 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000149 return -1;
150 }
Trent Micka5846642000-08-13 22:47:45 +0000151 if (self->ob_size == INT_MAX) {
152 PyErr_SetString(PyExc_OverflowError,
153 "cannot add more objects to list");
154 return -1;
155 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000156 items = self->ob_item;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000157 NRESIZE(items, PyObject *, self->ob_size+1);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000158 if (items == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000159 PyErr_NoMemory();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000160 return -1;
161 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000162 if (where < 0)
163 where = 0;
164 if (where > self->ob_size)
165 where = self->ob_size;
166 for (i = self->ob_size; --i >= where; )
167 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;
170 self->ob_item = items;
171 self->ob_size++;
172 return 0;
173}
174
175int
Fred Drakea2f55112000-07-09 15:16:51 +0000176PyList_Insert(PyObject *op, int where, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000177{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000178 if (!PyList_Check(op)) {
179 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000180 return -1;
181 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000182 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000183}
184
185int
Fred Drakea2f55112000-07-09 15:16:51 +0000186PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000187{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000188 if (!PyList_Check(op)) {
189 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000190 return -1;
191 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000192 return ins1((PyListObject *)op,
193 (int) ((PyListObject *)op)->ob_size, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000194}
195
196/* Methods */
197
198static void
Fred Drakea2f55112000-07-09 15:16:51 +0000199list_dealloc(PyListObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000200{
201 int i;
Guido van Rossumff413af2002-03-28 20:34:59 +0000202 PyObject_GC_UnTrack(op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000203 Py_TRASHCAN_SAFE_BEGIN(op)
Jack Jansen7874d1f1995-01-19 12:09:27 +0000204 if (op->ob_item != NULL) {
Guido van Rossumfa717011999-06-09 15:19:34 +0000205 /* Do it backwards, for Christian Tismer.
206 There's a simple test case where somehow this reduces
207 thrashing when a *very* large list is created and
208 immediately deleted. */
209 i = op->ob_size;
210 while (--i >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000211 Py_XDECREF(op->ob_item[i]);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000212 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000213 PyMem_FREE(op->ob_item);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000214 }
Guido van Rossum9475a232001-10-05 20:51:39 +0000215 op->ob_type->tp_free((PyObject *)op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000216 Py_TRASHCAN_SAFE_END(op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000217}
218
Guido van Rossum90933611991-06-07 16:10:43 +0000219static int
Fred Drakea2f55112000-07-09 15:16:51 +0000220list_print(PyListObject *op, FILE *fp, int flags)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000221{
222 int i;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000223
224 i = Py_ReprEnter((PyObject*)op);
225 if (i != 0) {
226 if (i < 0)
227 return i;
228 fprintf(fp, "[...]");
229 return 0;
230 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000231 fprintf(fp, "[");
Guido van Rossum90933611991-06-07 16:10:43 +0000232 for (i = 0; i < op->ob_size; i++) {
233 if (i > 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000234 fprintf(fp, ", ");
Guido van Rossumfb376de1998-04-10 22:47:27 +0000235 if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
236 Py_ReprLeave((PyObject *)op);
Guido van Rossum90933611991-06-07 16:10:43 +0000237 return -1;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000238 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000239 }
240 fprintf(fp, "]");
Guido van Rossumfb376de1998-04-10 22:47:27 +0000241 Py_ReprLeave((PyObject *)op);
Guido van Rossum90933611991-06-07 16:10:43 +0000242 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000243}
244
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000245static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000246list_repr(PyListObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000247{
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000248 int i;
Tim Petersa7259592001-06-16 05:11:17 +0000249 PyObject *s, *temp;
250 PyObject *pieces = NULL, *result = NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000251
252 i = Py_ReprEnter((PyObject*)v);
253 if (i != 0) {
Tim Petersa7259592001-06-16 05:11:17 +0000254 return i > 0 ? PyString_FromString("[...]") : NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000255 }
Tim Petersa7259592001-06-16 05:11:17 +0000256
257 if (v->ob_size == 0) {
258 result = PyString_FromString("[]");
259 goto Done;
260 }
261
262 pieces = PyList_New(0);
263 if (pieces == NULL)
264 goto Done;
265
266 /* Do repr() on each element. Note that this may mutate the list,
267 so must refetch the list size on each iteration. */
268 for (i = 0; i < v->ob_size; ++i) {
269 int status;
270 s = PyObject_Repr(v->ob_item[i]);
271 if (s == NULL)
272 goto Done;
273 status = PyList_Append(pieces, s);
274 Py_DECREF(s); /* append created a new ref */
275 if (status < 0)
276 goto Done;
277 }
278
279 /* Add "[]" decorations to the first and last items. */
280 assert(PyList_GET_SIZE(pieces) > 0);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000281 s = PyString_FromString("[");
Tim Petersa7259592001-06-16 05:11:17 +0000282 if (s == NULL)
283 goto Done;
284 temp = PyList_GET_ITEM(pieces, 0);
285 PyString_ConcatAndDel(&s, temp);
286 PyList_SET_ITEM(pieces, 0, s);
287 if (s == NULL)
288 goto Done;
289
290 s = PyString_FromString("]");
291 if (s == NULL)
292 goto Done;
293 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
294 PyString_ConcatAndDel(&temp, s);
295 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
296 if (temp == NULL)
297 goto Done;
298
299 /* Paste them all together with ", " between. */
300 s = PyString_FromString(", ");
301 if (s == NULL)
302 goto Done;
303 result = _PyString_Join(s, pieces);
Tim Peters3b01a122002-07-19 02:35:45 +0000304 Py_DECREF(s);
Tim Petersa7259592001-06-16 05:11:17 +0000305
306Done:
307 Py_XDECREF(pieces);
Guido van Rossumfb376de1998-04-10 22:47:27 +0000308 Py_ReprLeave((PyObject *)v);
Tim Petersa7259592001-06-16 05:11:17 +0000309 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000310}
311
312static int
Fred Drakea2f55112000-07-09 15:16:51 +0000313list_length(PyListObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000314{
315 return a->ob_size;
316}
317
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000318
319
320static int
Fred Drakea2f55112000-07-09 15:16:51 +0000321list_contains(PyListObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000322{
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000323 int i;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000324
325 for (i = 0; i < a->ob_size; ++i) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000326 int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
327 Py_EQ);
328 if (cmp > 0)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000329 return 1;
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000330 else if (cmp < 0)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000331 return -1;
332 }
333 return 0;
334}
335
336
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000337static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000338list_item(PyListObject *a, int i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000339{
340 if (i < 0 || i >= a->ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000341 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000342 indexerr = PyString_FromString(
343 "list index out of range");
344 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000345 return NULL;
346 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000347 Py_INCREF(a->ob_item[i]);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000348 return a->ob_item[i];
349}
350
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000351static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000352list_slice(PyListObject *a, int ilow, int ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000353{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000354 PyListObject *np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000355 int i;
356 if (ilow < 0)
357 ilow = 0;
358 else if (ilow > a->ob_size)
359 ilow = a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000360 if (ihigh < ilow)
361 ihigh = ilow;
362 else if (ihigh > a->ob_size)
363 ihigh = a->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000364 np = (PyListObject *) PyList_New(ihigh - ilow);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000365 if (np == NULL)
366 return NULL;
367 for (i = ilow; i < ihigh; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000368 PyObject *v = a->ob_item[i];
369 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000370 np->ob_item[i - ilow] = v;
371 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000372 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000373}
374
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000375PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000376PyList_GetSlice(PyObject *a, int ilow, int ihigh)
Guido van Rossum234f9421993-06-17 12:35:49 +0000377{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000378 if (!PyList_Check(a)) {
379 PyErr_BadInternalCall();
Guido van Rossum234f9421993-06-17 12:35:49 +0000380 return NULL;
381 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000382 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000383}
384
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000385static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000386list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000387{
388 int size;
389 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000390 PyListObject *np;
391 if (!PyList_Check(bb)) {
Fred Drakeb6a9ada2000-06-01 03:12:13 +0000392 PyErr_Format(PyExc_TypeError,
Fred Drake914a2ed2000-06-01 14:31:03 +0000393 "can only concatenate list (not \"%.200s\") to list",
394 bb->ob_type->tp_name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000395 return NULL;
396 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000397#define b ((PyListObject *)bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000398 size = a->ob_size + b->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000399 np = (PyListObject *) PyList_New(size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000400 if (np == NULL) {
Guido van Rossum90933611991-06-07 16:10:43 +0000401 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000402 }
403 for (i = 0; i < a->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000404 PyObject *v = a->ob_item[i];
405 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000406 np->ob_item[i] = v;
407 }
408 for (i = 0; i < b->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000409 PyObject *v = b->ob_item[i];
410 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000411 np->ob_item[i + a->ob_size] = v;
412 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000413 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000414#undef b
415}
416
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000417static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000418list_repeat(PyListObject *a, int n)
Guido van Rossumed98d481991-03-06 13:07:53 +0000419{
420 int i, j;
421 int size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000422 PyListObject *np;
423 PyObject **p;
Guido van Rossumed98d481991-03-06 13:07:53 +0000424 if (n < 0)
425 n = 0;
426 size = a->ob_size * n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000427 np = (PyListObject *) PyList_New(size);
Guido van Rossumed98d481991-03-06 13:07:53 +0000428 if (np == NULL)
429 return NULL;
430 p = np->ob_item;
431 for (i = 0; i < n; i++) {
432 for (j = 0; j < a->ob_size; j++) {
433 *p = a->ob_item[j];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000434 Py_INCREF(*p);
Guido van Rossumed98d481991-03-06 13:07:53 +0000435 p++;
436 }
437 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000438 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000439}
440
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000441static int
Fred Drakea2f55112000-07-09 15:16:51 +0000442list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000443{
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000444 /* Because [X]DECREF can recursively invoke list operations on
445 this list, we must postpone all [X]DECREF activity until
446 after the list is back in its canonical shape. Therefore
447 we must allocate an additional array, 'recycle', into which
448 we temporarily copy the items that are deleted from the
449 list. :-( */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000450 PyObject **recycle, **p;
451 PyObject **item;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000452 int n; /* Size of replacement list */
453 int d; /* Change in size */
454 int k; /* Loop index */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000455#define b ((PyListObject *)v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000456 if (v == NULL)
457 n = 0;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000458 else if (PyList_Check(v)) {
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000459 n = b->ob_size;
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000460 if (a == b) {
461 /* Special case "a[i:j] = a" -- copy b first */
462 int ret;
463 v = list_slice(b, 0, n);
464 ret = list_ass_slice(a, ilow, ihigh, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000465 Py_DECREF(v);
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000466 return ret;
467 }
468 }
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000469 else {
Fred Drakeb6a9ada2000-06-01 03:12:13 +0000470 PyErr_Format(PyExc_TypeError,
471 "must assign list (not \"%.200s\") to slice",
472 v->ob_type->tp_name);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000473 return -1;
474 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000475 if (ilow < 0)
476 ilow = 0;
477 else if (ilow > a->ob_size)
478 ilow = a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000479 if (ihigh < ilow)
480 ihigh = ilow;
481 else if (ihigh > a->ob_size)
482 ihigh = a->ob_size;
483 item = a->ob_item;
484 d = n - (ihigh-ilow);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000485 if (ihigh > ilow)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000486 p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000487 else
488 p = recycle = NULL;
489 if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000490 for (k = ilow; k < ihigh; k++)
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000491 *p++ = item[k];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000492 if (d < 0) {
493 for (/*k = ihigh*/; k < a->ob_size; k++)
494 item[k+d] = item[k];
495 a->ob_size += d;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000496 NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000497 a->ob_item = item;
498 }
499 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000500 else { /* Insert d items; recycle ihigh-ilow items */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000501 NRESIZE(item, PyObject *, a->ob_size + d);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000502 if (item == NULL) {
Guido van Rossumb18618d2000-05-03 23:44:39 +0000503 if (recycle != NULL)
504 PyMem_DEL(recycle);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000505 PyErr_NoMemory();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000506 return -1;
507 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000508 for (k = a->ob_size; --k >= ihigh; )
509 item[k+d] = item[k];
510 for (/*k = ihigh-1*/; k >= ilow; --k)
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000511 *p++ = item[k];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000512 a->ob_item = item;
513 a->ob_size += d;
514 }
515 for (k = 0; k < n; k++, ilow++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000516 PyObject *w = b->ob_item[k];
517 Py_XINCREF(w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000518 item[ilow] = w;
519 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000520 if (recycle) {
521 while (--p >= recycle)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000522 Py_XDECREF(*p);
523 PyMem_DEL(recycle);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000524 }
Tim Peters6d6c1a32001-08-02 04:15:00 +0000525 if (a->ob_size == 0 && a->ob_item != NULL) {
526 PyMem_FREE(a->ob_item);
527 a->ob_item = NULL;
528 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000529 return 0;
530#undef b
531}
532
Guido van Rossum234f9421993-06-17 12:35:49 +0000533int
Fred Drakea2f55112000-07-09 15:16:51 +0000534PyList_SetSlice(PyObject *a, int ilow, int ihigh, PyObject *v)
Guido van Rossum234f9421993-06-17 12:35:49 +0000535{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000536 if (!PyList_Check(a)) {
537 PyErr_BadInternalCall();
Guido van Rossum1fc238a1993-07-29 08:25:09 +0000538 return -1;
Guido van Rossum234f9421993-06-17 12:35:49 +0000539 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000540 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000541}
542
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000543static PyObject *
544list_inplace_repeat(PyListObject *self, int n)
545{
546 PyObject **items;
547 int size, i, j;
548
549
550 size = PyList_GET_SIZE(self);
551 if (size == 0) {
552 Py_INCREF(self);
553 return (PyObject *)self;
554 }
555
556 items = self->ob_item;
557
558 if (n < 1) {
559 self->ob_item = NULL;
560 self->ob_size = 0;
561 for (i = 0; i < size; i++)
562 Py_XDECREF(items[i]);
563 PyMem_DEL(items);
564 Py_INCREF(self);
565 return (PyObject *)self;
566 }
567
568 NRESIZE(items, PyObject*, size*n);
569 if (items == NULL) {
570 PyErr_NoMemory();
571 goto finally;
572 }
573 self->ob_item = items;
574 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
575 for (j = 0; j < size; j++) {
576 PyObject *o = PyList_GET_ITEM(self, j);
577 Py_INCREF(o);
578 PyList_SET_ITEM(self, self->ob_size++, o);
579 }
580 }
581 Py_INCREF(self);
582 return (PyObject *)self;
583 finally:
584 return NULL;
585}
586
Guido van Rossum4a450d01991-04-03 19:05:18 +0000587static int
Fred Drakea2f55112000-07-09 15:16:51 +0000588list_ass_item(PyListObject *a, int i, PyObject *v)
Guido van Rossum4a450d01991-04-03 19:05:18 +0000589{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000590 PyObject *old_value;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000591 if (i < 0 || i >= a->ob_size) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000592 PyErr_SetString(PyExc_IndexError,
593 "list assignment index out of range");
Guido van Rossum4a450d01991-04-03 19:05:18 +0000594 return -1;
595 }
596 if (v == NULL)
597 return list_ass_slice(a, i, i+1, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000598 Py_INCREF(v);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000599 old_value = a->ob_item[i];
Guido van Rossum4a450d01991-04-03 19:05:18 +0000600 a->ob_item[i] = v;
Tim Peters3b01a122002-07-19 02:35:45 +0000601 Py_DECREF(old_value);
Guido van Rossum4a450d01991-04-03 19:05:18 +0000602 return 0;
603}
604
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000605static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000606ins(PyListObject *self, int where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000607{
608 if (ins1(self, where, v) != 0)
609 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000610 Py_INCREF(Py_None);
611 return Py_None;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000612}
613
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000614static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000615listinsert(PyListObject *self, PyObject *args)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000616{
617 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000618 PyObject *v;
Guido van Rossumc00a9382000-02-24 21:48:29 +0000619 if (!PyArg_ParseTuple(args, "iO:insert", &i, &v))
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000620 return NULL;
Guido van Rossumbf80e541993-02-08 15:49:17 +0000621 return ins(self, i, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000622}
623
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000624static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000625listappend(PyListObject *self, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000626{
Guido van Rossumbf80e541993-02-08 15:49:17 +0000627 return ins(self, (int) self->ob_size, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000628}
629
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000630static int
631listextend_internal(PyListObject *self, PyObject *b)
Barry Warsawdedf6d61998-10-09 16:37:25 +0000632{
Barry Warsawdedf6d61998-10-09 16:37:25 +0000633 PyObject **items;
634 int selflen = PyList_GET_SIZE(self);
635 int blen;
636 register int i;
637
Jeremy Hyltondb60bb52001-01-03 22:32:16 +0000638 if (PyObject_Size(b) == 0) {
Barry Warsawdedf6d61998-10-09 16:37:25 +0000639 /* short circuit when b is empty */
Jeremy Hyltondb60bb52001-01-03 22:32:16 +0000640 Py_DECREF(b);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000641 return 0;
Jeremy Hyltondb60bb52001-01-03 22:32:16 +0000642 }
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000643
Barry Warsawdedf6d61998-10-09 16:37:25 +0000644 if (self == (PyListObject*)b) {
645 /* as in list_ass_slice() we must special case the
646 * situation: a.extend(a)
647 *
648 * XXX: I think this way ought to be faster than using
649 * list_slice() the way list_ass_slice() does.
650 */
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000651 Py_DECREF(b);
Barry Warsawdedf6d61998-10-09 16:37:25 +0000652 b = PyList_New(selflen);
653 if (!b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000654 return -1;
Barry Warsawdedf6d61998-10-09 16:37:25 +0000655 for (i = 0; i < selflen; i++) {
656 PyObject *o = PyList_GET_ITEM(self, i);
657 Py_INCREF(o);
658 PyList_SET_ITEM(b, i, o);
659 }
660 }
Barry Warsawdedf6d61998-10-09 16:37:25 +0000661
Jeremy Hylton03657cf2000-07-12 13:05:33 +0000662 blen = PyObject_Size(b);
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000663
Barry Warsawdedf6d61998-10-09 16:37:25 +0000664 /* resize a using idiom */
665 items = self->ob_item;
666 NRESIZE(items, PyObject*, selflen + blen);
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000667 if (items == NULL) {
Barry Warsawdedf6d61998-10-09 16:37:25 +0000668 PyErr_NoMemory();
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000669 Py_DECREF(b);
670 return -1;
Barry Warsawdedf6d61998-10-09 16:37:25 +0000671 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000672
Barry Warsawdedf6d61998-10-09 16:37:25 +0000673 self->ob_item = items;
674
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000675 /* populate the end of self with b's items */
Barry Warsawdedf6d61998-10-09 16:37:25 +0000676 for (i = 0; i < blen; i++) {
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000677 PyObject *o = PySequence_Fast_GET_ITEM(b, i);
Barry Warsawdedf6d61998-10-09 16:37:25 +0000678 Py_INCREF(o);
679 PyList_SET_ITEM(self, self->ob_size++, o);
680 }
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000681 Py_DECREF(b);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000682 return 0;
Barry Warsawdedf6d61998-10-09 16:37:25 +0000683}
684
685
686static PyObject *
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000687list_inplace_concat(PyListObject *self, PyObject *other)
688{
Tim Peters1af03e92001-05-26 19:37:54 +0000689 other = PySequence_Fast(other, "argument to += must be iterable");
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000690 if (!other)
691 return NULL;
692
693 if (listextend_internal(self, other) < 0)
694 return NULL;
695
696 Py_INCREF(self);
697 return (PyObject *)self;
698}
699
700static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000701listextend(PyListObject *self, PyObject *b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000702{
703
Tim Peters1af03e92001-05-26 19:37:54 +0000704 b = PySequence_Fast(b, "list.extend() argument must be iterable");
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000705 if (!b)
706 return NULL;
707
708 if (listextend_internal(self, b) < 0)
709 return NULL;
710
711 Py_INCREF(Py_None);
712 return Py_None;
713}
714
715static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000716listpop(PyListObject *self, PyObject *args)
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000717{
718 int i = -1;
719 PyObject *v;
Guido van Rossumc00a9382000-02-24 21:48:29 +0000720 if (!PyArg_ParseTuple(args, "|i:pop", &i))
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000721 return NULL;
722 if (self->ob_size == 0) {
723 /* Special-case most common failure cause */
724 PyErr_SetString(PyExc_IndexError, "pop from empty list");
725 return NULL;
726 }
727 if (i < 0)
728 i += self->ob_size;
729 if (i < 0 || i >= self->ob_size) {
730 PyErr_SetString(PyExc_IndexError, "pop index out of range");
731 return NULL;
732 }
733 v = self->ob_item[i];
734 Py_INCREF(v);
735 if (list_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
736 Py_DECREF(v);
737 return NULL;
738 }
739 return v;
740}
741
Tim Peters8e2e7ca2002-07-19 02:33:08 +0000742/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
743static void
744reverse_slice(PyObject **lo, PyObject **hi)
745{
746 assert(lo && hi);
747
748 --hi;
749 while (lo < hi) {
750 PyObject *t = *lo;
751 *lo = *hi;
752 *hi = t;
753 ++lo;
754 --hi;
755 }
756}
757
Tim Petersa64dc242002-08-01 02:13:36 +0000758/* Lots of code for an adaptive, stable, natural mergesort. There are many
759 * pieces to this algorithm; read listsort.txt for overviews and details.
760 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000761
Guido van Rossum3f236de1996-12-10 23:55:39 +0000762/* Comparison function. Takes care of calling a user-supplied
Tim Petersa64dc242002-08-01 02:13:36 +0000763 * comparison function (any callable Python object). Calls the
764 * standard comparison function, PyObject_RichCompareBool(), if the user-
765 * supplied function is NULL.
766 * Returns -1 on error, 1 if x < y, 0 if x >= y.
767 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000768static int
Tim Petersa8c974c2002-07-19 03:30:57 +0000769islt(PyObject *x, PyObject *y, PyObject *compare)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000770{
Tim Petersf2a04732002-07-11 21:46:16 +0000771 PyObject *res;
772 PyObject *args;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000773 int i;
774
Tim Petersa8c974c2002-07-19 03:30:57 +0000775 if (compare == NULL)
776 return PyObject_RichCompareBool(x, y, Py_LT);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000777
Tim Petersa8c974c2002-07-19 03:30:57 +0000778 /* Call the user's comparison function and translate the 3-way
779 * result into true or false (or error).
780 */
Tim Petersf2a04732002-07-11 21:46:16 +0000781 args = PyTuple_New(2);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000782 if (args == NULL)
Tim Petersa8c974c2002-07-19 03:30:57 +0000783 return -1;
Tim Petersf2a04732002-07-11 21:46:16 +0000784 Py_INCREF(x);
785 Py_INCREF(y);
786 PyTuple_SET_ITEM(args, 0, x);
787 PyTuple_SET_ITEM(args, 1, y);
Tim Peters58cf3612002-07-15 05:16:13 +0000788 res = PyObject_Call(compare, args, NULL);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000789 Py_DECREF(args);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000790 if (res == NULL)
Tim Petersa8c974c2002-07-19 03:30:57 +0000791 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000792 if (!PyInt_Check(res)) {
793 Py_DECREF(res);
794 PyErr_SetString(PyExc_TypeError,
Guido van Rossum9bcd1d71999-04-19 17:44:39 +0000795 "comparison function must return int");
Tim Petersa8c974c2002-07-19 03:30:57 +0000796 return -1;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000797 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000798 i = PyInt_AsLong(res);
799 Py_DECREF(res);
Tim Petersa8c974c2002-07-19 03:30:57 +0000800 return i < 0;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000801}
802
Tim Petersa8c974c2002-07-19 03:30:57 +0000803/* Compare X to Y via islt(). Goto "fail" if the comparison raises an
804 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
805 started. It makes more sense in context <wink>. X and Y are PyObject*s.
806*/
807#define IFLT(X, Y) if ((k = islt(X, Y, compare)) < 0) goto fail; \
808 if (k)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000809
810/* binarysort is the best method for sorting small arrays: it does
811 few compares, but can do data movement quadratic in the number of
812 elements.
Guido van Rossum42812581998-06-17 14:15:44 +0000813 [lo, hi) is a contiguous slice of a list, and is sorted via
Tim Petersa8c974c2002-07-19 03:30:57 +0000814 binary insertion. This sort is stable.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000815 On entry, must have lo <= start <= hi, and that [lo, start) is already
816 sorted (pass start == lo if you don't know!).
Tim Petersa8c974c2002-07-19 03:30:57 +0000817 If islt() complains return -1, else 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000818 Even in case of error, the output slice will be some permutation of
819 the input (nothing is lost or duplicated).
820*/
Guido van Rossum3f236de1996-12-10 23:55:39 +0000821static int
Fred Drakea2f55112000-07-09 15:16:51 +0000822binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
823 /* compare -- comparison function object, or NULL for default */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000824{
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000825 register int k;
826 register PyObject **l, **p, **r;
827 register PyObject *pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000828
Tim Petersa8c974c2002-07-19 03:30:57 +0000829 assert(lo <= start && start <= hi);
830 /* assert [lo, start) is sorted */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000831 if (lo == start)
832 ++start;
833 for (; start < hi; ++start) {
834 /* set l to where *start belongs */
835 l = lo;
836 r = start;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000837 pivot = *r;
Tim Peters0fe977c2002-07-19 06:12:32 +0000838 /* Invariants:
839 * pivot >= all in [lo, l).
840 * pivot < all in [r, start).
841 * The second is vacuously true at the start.
842 */
843 assert(l < r);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000844 do {
845 p = l + ((r - l) >> 1);
Tim Petersa8c974c2002-07-19 03:30:57 +0000846 IFLT(pivot, *p)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000847 r = p;
848 else
Tim Peters0fe977c2002-07-19 06:12:32 +0000849 l = p+1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000850 } while (l < r);
Tim Peters0fe977c2002-07-19 06:12:32 +0000851 assert(l == r);
852 /* The invariants still hold, so pivot >= all in [lo, l) and
853 pivot < all in [l, start), so pivot belongs at l. Note
854 that if there are elements equal to pivot, l points to the
855 first slot after them -- that's why this sort is stable.
856 Slide over to make room.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000857 Caution: using memmove is much slower under MSVC 5;
858 we're not usually moving many slots. */
859 for (p = start; p > l; --p)
860 *p = *(p-1);
861 *l = pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000862 }
Guido van Rossum3f236de1996-12-10 23:55:39 +0000863 return 0;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000864
865 fail:
866 return -1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000867}
868
Tim Petersa64dc242002-08-01 02:13:36 +0000869/*
870Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
871is required on entry. "A run" is the longest ascending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000872
Tim Petersa64dc242002-08-01 02:13:36 +0000873 lo[0] <= lo[1] <= lo[2] <= ...
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000874
Tim Petersa64dc242002-08-01 02:13:36 +0000875or the longest descending sequence, with
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000876
Tim Petersa64dc242002-08-01 02:13:36 +0000877 lo[0] > lo[1] > lo[2] > ...
Tim Peters3b01a122002-07-19 02:35:45 +0000878
Tim Petersa64dc242002-08-01 02:13:36 +0000879Boolean *descending is set to 0 in the former case, or to 1 in the latter.
880For its intended use in a stable mergesort, the strictness of the defn of
881"descending" is needed so that the caller can safely reverse a descending
882sequence without violating stability (strict > ensures there are no equal
883elements to get out of order).
884
885Returns -1 in case of error.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000886*/
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000887static int
Tim Petersa64dc242002-08-01 02:13:36 +0000888count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000889{
Tim Petersa64dc242002-08-01 02:13:36 +0000890 int k;
891 int n;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000892
Tim Petersa64dc242002-08-01 02:13:36 +0000893 assert(lo < hi);
894 *descending = 0;
895 ++lo;
896 if (lo == hi)
897 return 1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000898
Tim Petersa64dc242002-08-01 02:13:36 +0000899 n = 2;
900 IFLT(*lo, *(lo-1)) {
901 *descending = 1;
902 for (lo = lo+1; lo < hi; ++lo, ++n) {
903 IFLT(*lo, *(lo-1))
904 ;
905 else
906 break;
907 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000908 }
Tim Petersa64dc242002-08-01 02:13:36 +0000909 else {
910 for (lo = lo+1; lo < hi; ++lo, ++n) {
911 IFLT(*lo, *(lo-1))
912 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000913 }
914 }
915
Tim Petersa64dc242002-08-01 02:13:36 +0000916 return n;
917fail:
918 return -1;
919}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000920
Tim Petersa64dc242002-08-01 02:13:36 +0000921/*
922Locate the proper position of key in a sorted vector; if the vector contains
923an element equal to key, return the position immediately to the left of
924the leftmost equal element. [gallop_right() does the same except returns
925the position to the right of the rightmost equal element (if any).]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000926
Tim Petersa64dc242002-08-01 02:13:36 +0000927"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000928
Tim Petersa64dc242002-08-01 02:13:36 +0000929"hint" is an index at which to begin the search, 0 <= hint < n. The closer
930hint is to the final result, the faster this runs.
931
932The return value is the int k in 0..n such that
933
934 a[k-1] < key <= a[k]
935
936pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
937key belongs at index k; or, IOW, the first k elements of a should precede
938key, and the last n-k should follow key.
939
940Returns -1 on error. See listsort.txt for info on the method.
941*/
942static int
943gallop_left(PyObject *key, PyObject **a, int n, int hint, PyObject *compare)
944{
945 int ofs;
946 int lastofs;
947 int k;
948
949 assert(key && a && n > 0 && hint >= 0 && hint < n);
950
951 a += hint;
952 lastofs = 0;
953 ofs = 1;
954 IFLT(*a, key) {
955 /* a[hint] < key -- gallop right, until
956 * a[hint + lastofs] < key <= a[hint + ofs]
957 */
958 const int maxofs = n - hint; /* &a[n-1] is highest */
959 while (ofs < maxofs) {
960 IFLT(a[ofs], key) {
961 lastofs = ofs;
962 ofs = (ofs << 1) + 1;
963 if (ofs <= 0) /* int overflow */
964 ofs = maxofs;
965 }
966 else /* key <= a[hint + ofs] */
967 break;
968 }
969 if (ofs > maxofs)
970 ofs = maxofs;
971 /* Translate back to offsets relative to &a[0]. */
972 lastofs += hint;
973 ofs += hint;
974 }
975 else {
976 /* key <= a[hint] -- gallop left, until
977 * a[hint - ofs] < key <= a[hint - lastofs]
978 */
979 const int maxofs = hint + 1; /* &a[0] is lowest */
980 while (ofs < maxofs) {
981 IFLT(*(a-ofs), key)
982 break;
983 /* key <= a[hint - ofs] */
984 lastofs = ofs;
985 ofs = (ofs << 1) + 1;
986 if (ofs <= 0) /* int overflow */
987 ofs = maxofs;
988 }
989 if (ofs > maxofs)
990 ofs = maxofs;
991 /* Translate back to positive offsets relative to &a[0]. */
992 k = lastofs;
993 lastofs = hint - ofs;
994 ofs = hint - k;
995 }
996 a -= hint;
997
998 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
999 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
1000 * right of lastofs but no farther right than ofs. Do a binary
1001 * search, with invariant a[lastofs-1] < key <= a[ofs].
1002 */
1003 ++lastofs;
1004 while (lastofs < ofs) {
1005 int m = lastofs + ((ofs - lastofs) >> 1);
1006
1007 IFLT(a[m], key)
1008 lastofs = m+1; /* a[m] < key */
1009 else
1010 ofs = m; /* key <= a[m] */
1011 }
1012 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
1013 return ofs;
1014
1015fail:
1016 return -1;
1017}
1018
1019/*
1020Exactly like gallop_left(), except that if key already exists in a[0:n],
1021finds the position immediately to the right of the rightmost equal value.
1022
1023The return value is the int k in 0..n such that
1024
1025 a[k-1] <= key < a[k]
1026
1027or -1 if error.
1028
1029The code duplication is massive, but this is enough different given that
1030we're sticking to "<" comparisons that it's much harder to follow if
1031written as one routine with yet another "left or right?" flag.
1032*/
1033static int
1034gallop_right(PyObject *key, PyObject **a, int n, int hint, PyObject *compare)
1035{
1036 int ofs;
1037 int lastofs;
1038 int k;
1039
1040 assert(key && a && n > 0 && hint >= 0 && hint < n);
1041
1042 a += hint;
1043 lastofs = 0;
1044 ofs = 1;
1045 IFLT(key, *a) {
1046 /* key < a[hint] -- gallop left, until
1047 * a[hint - ofs] <= key < a[hint - lastofs]
1048 */
1049 const int maxofs = hint + 1; /* &a[0] is lowest */
1050 while (ofs < maxofs) {
1051 IFLT(key, *(a-ofs)) {
1052 lastofs = ofs;
1053 ofs = (ofs << 1) + 1;
1054 if (ofs <= 0) /* int overflow */
1055 ofs = maxofs;
1056 }
1057 else /* a[hint - ofs] <= key */
1058 break;
1059 }
1060 if (ofs > maxofs)
1061 ofs = maxofs;
1062 /* Translate back to positive offsets relative to &a[0]. */
1063 k = lastofs;
1064 lastofs = hint - ofs;
1065 ofs = hint - k;
1066 }
1067 else {
1068 /* a[hint] <= key -- gallop right, until
1069 * a[hint + lastofs] <= key < a[hint + ofs]
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001070 */
Tim Petersa64dc242002-08-01 02:13:36 +00001071 const int maxofs = n - hint; /* &a[n-1] is highest */
1072 while (ofs < maxofs) {
1073 IFLT(key, a[ofs])
1074 break;
1075 /* a[hint + ofs] <= key */
1076 lastofs = ofs;
1077 ofs = (ofs << 1) + 1;
1078 if (ofs <= 0) /* int overflow */
1079 ofs = maxofs;
1080 }
1081 if (ofs > maxofs)
1082 ofs = maxofs;
1083 /* Translate back to offsets relative to &a[0]. */
1084 lastofs += hint;
1085 ofs += hint;
1086 }
1087 a -= hint;
1088
1089 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
1090 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
1091 * right of lastofs but no farther right than ofs. Do a binary
1092 * search, with invariant a[lastofs-1] <= key < a[ofs].
1093 */
1094 ++lastofs;
1095 while (lastofs < ofs) {
1096 int m = lastofs + ((ofs - lastofs) >> 1);
1097
1098 IFLT(key, a[m])
1099 ofs = m; /* key < a[m] */
1100 else
1101 lastofs = m+1; /* a[m] <= key */
1102 }
1103 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
1104 return ofs;
1105
1106fail:
1107 return -1;
1108}
1109
1110/* The maximum number of entries in a MergeState's pending-runs stack.
1111 * This is enough to sort arrays of size up to about
1112 * 32 * phi ** MAX_MERGE_PENDING
1113 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
1114 * with 2**64 elements.
1115 */
1116#define MAX_MERGE_PENDING 85
1117
1118/* If a run wins MIN_GALLOP times in a row, we switch to galloping mode,
1119 * and stay there until both runs win less often than MIN_GALLOP
1120 * consecutive times. See listsort.txt for more info.
1121 */
1122#define MIN_GALLOP 8
1123
1124/* Avoid malloc for small temp arrays. */
1125#define MERGESTATE_TEMP_SIZE 256
1126
1127/* One MergeState exists on the stack per invocation of mergesort. It's just
1128 * a convenient way to pass state around among the helper functions.
1129 */
1130typedef struct s_MergeState {
1131 /* The user-supplied comparison function. or NULL if none given. */
1132 PyObject *compare;
1133
1134 /* 'a' is temp storage to help with merges. It contains room for
1135 * alloced entries.
1136 */
1137 PyObject **a; /* may point to temparray below */
1138 int alloced;
1139
1140 /* A stack of n pending runs yet to be merged. Run #i starts at
1141 * address base[i] and extends for len[i] elements. It's always
1142 * true (so long as the indices are in bounds) that
1143 *
1144 * base[i] + len[i] == base[i+1]
1145 *
1146 * so we could cut the storage for this, but it's a minor amount,
1147 * and keeping all the info explicit simplifies the code.
1148 */
1149 int n;
1150 PyObject **base[MAX_MERGE_PENDING];
1151 int len[MAX_MERGE_PENDING];
1152
1153 /* 'a' points to this when possible, rather than muck with malloc. */
1154 PyObject *temparray[MERGESTATE_TEMP_SIZE];
1155} MergeState;
1156
1157/* Conceptually a MergeState's constructor. */
1158static void
1159merge_init(MergeState *ms, PyObject *compare)
1160{
1161 assert(ms != NULL);
1162 ms->compare = compare;
1163 ms->a = ms->temparray;
1164 ms->alloced = MERGESTATE_TEMP_SIZE;
1165 ms->n = 0;
1166}
1167
1168/* Free all the temp memory owned by the MergeState. This must be called
1169 * when you're done with a MergeState, and may be called before then if
1170 * you want to free the temp memory early.
1171 */
1172static void
1173merge_freemem(MergeState *ms)
1174{
1175 assert(ms != NULL);
1176 if (ms->a != ms->temparray)
1177 PyMem_Free(ms->a);
1178 ms->a = ms->temparray;
1179 ms->alloced = MERGESTATE_TEMP_SIZE;
1180}
1181
1182/* Ensure enough temp memory for 'need' array slots is available.
1183 * Returns 0 on success and -1 if the memory can't be gotten.
1184 */
1185static int
1186merge_getmem(MergeState *ms, int need)
1187{
1188 assert(ms != NULL);
1189 if (need <= ms->alloced)
1190 return 0;
1191 /* Don't realloc! That can cost cycles to copy the old data, but
1192 * we don't care what's in the block.
1193 */
1194 merge_freemem(ms);
1195 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));
1196 if (ms->a) {
1197 ms->alloced = need;
1198 return 0;
1199 }
1200 PyErr_NoMemory();
1201 merge_freemem(ms); /* reset to sane state */
1202 return -1;
1203}
1204#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
1205 merge_getmem(MS, NEED))
1206
1207/* Merge the na elements starting at pa with the nb elements starting at pb
1208 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1209 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1210 * merge, and should have na <= nb. See listsort.txt for more info.
1211 * Return 0 if successful, -1 if error.
1212 */
1213static int
1214merge_lo(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb)
1215{
1216 int k;
1217 PyObject *compare;
1218 PyObject **dest;
1219 int result = -1; /* guilty until proved innocent */
1220
1221 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1222 if (MERGE_GETMEM(ms, na) < 0)
1223 return -1;
1224 memcpy(ms->a, pa, na * sizeof(PyObject*));
1225 dest = pa;
1226 pa = ms->a;
1227
1228 *dest++ = *pb++;
1229 --nb;
1230 if (nb == 0)
1231 goto Succeed;
1232 if (na == 1)
1233 goto CopyB;
1234
1235 compare = ms->compare;
1236 for (;;) {
1237 int acount = 0; /* # of times A won in a row */
1238 int bcount = 0; /* # of times B won in a row */
1239
1240 /* Do the straightforward thing until (if ever) one run
1241 * appears to win consistently.
1242 */
1243 for (;;) {
1244 k = islt(*pb, *pa, compare);
1245 if (k) {
1246 if (k < 0)
1247 goto Fail;
1248 *dest++ = *pb++;
1249 ++bcount;
1250 acount = 0;
1251 --nb;
1252 if (nb == 0)
1253 goto Succeed;
1254 if (bcount >= MIN_GALLOP)
1255 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001256 }
1257 else {
Tim Petersa64dc242002-08-01 02:13:36 +00001258 *dest++ = *pa++;
1259 ++acount;
1260 bcount = 0;
1261 --na;
1262 if (na == 1)
1263 goto CopyB;
1264 if (acount >= MIN_GALLOP)
1265 break;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001266 }
Tim Petersa64dc242002-08-01 02:13:36 +00001267 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001268
Tim Petersa64dc242002-08-01 02:13:36 +00001269 /* One run is winning so consistently that galloping may
1270 * be a huge win. So try that, and continue galloping until
1271 * (if ever) neither run appears to be winning consistently
1272 * anymore.
1273 */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001274 do {
Tim Petersa64dc242002-08-01 02:13:36 +00001275 k = gallop_right(*pb, pa, na, 0, compare);
1276 acount = k;
1277 if (k) {
1278 if (k < 0)
1279 goto Fail;
1280 memcpy(dest, pa, k * sizeof(PyObject *));
1281 dest += k;
1282 pa += k;
1283 na -= k;
1284 if (na == 1)
1285 goto CopyB;
1286 /* na==0 is impossible now if the comparison
1287 * function is consistent, but we can't assume
1288 * that it is.
1289 */
1290 if (na == 0)
1291 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001292 }
Tim Petersa64dc242002-08-01 02:13:36 +00001293 *dest++ = *pb++;
1294 --nb;
1295 if (nb == 0)
1296 goto Succeed;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001297
Tim Petersa64dc242002-08-01 02:13:36 +00001298 k = gallop_left(*pa, pb, nb, 0, compare);
1299 bcount = k;
1300 if (k) {
1301 if (k < 0)
1302 goto Fail;
1303 memmove(dest, pb, k * sizeof(PyObject *));
1304 dest += k;
1305 pb += k;
1306 nb -= k;
1307 if (nb == 0)
1308 goto Succeed;
1309 }
1310 *dest++ = *pa++;
1311 --na;
1312 if (na == 1)
1313 goto CopyB;
1314 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1315 }
1316Succeed:
1317 result = 0;
1318Fail:
1319 if (na)
1320 memcpy(dest, pa, na * sizeof(PyObject*));
1321 return result;
1322CopyB:
1323 assert(na == 1 && nb > 0);
1324 /* The last element of pa belongs at the end of the merge. */
1325 memmove(dest, pb, nb * sizeof(PyObject *));
1326 dest[nb] = *pa;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001327 return 0;
Tim Petersa64dc242002-08-01 02:13:36 +00001328}
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001329
Tim Petersa64dc242002-08-01 02:13:36 +00001330/* Merge the na elements starting at pa with the nb elements starting at pb
1331 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.
1332 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
1333 * merge, and should have na >= nb. See listsort.txt for more info.
1334 * Return 0 if successful, -1 if error.
1335 */
1336static int
1337merge_hi(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb)
1338{
1339 int k;
1340 PyObject *compare;
1341 PyObject **dest;
1342 int result = -1; /* guilty until proved innocent */
1343 PyObject **basea;
1344 PyObject **baseb;
1345
1346 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
1347 if (MERGE_GETMEM(ms, nb) < 0)
1348 return -1;
1349 dest = pb + nb - 1;
1350 memcpy(ms->a, pb, nb * sizeof(PyObject*));
1351 basea = pa;
1352 baseb = ms->a;
1353 pb = ms->a + nb - 1;
1354 pa += na - 1;
1355
1356 *dest-- = *pa--;
1357 --na;
1358 if (na == 0)
1359 goto Succeed;
1360 if (nb == 1)
1361 goto CopyA;
1362
1363 compare = ms->compare;
1364 for (;;) {
1365 int acount = 0; /* # of times A won in a row */
1366 int bcount = 0; /* # of times B won in a row */
1367
1368 /* Do the straightforward thing until (if ever) one run
1369 * appears to win consistently.
1370 */
1371 for (;;) {
1372 k = islt(*pb, *pa, compare);
1373 if (k) {
1374 if (k < 0)
1375 goto Fail;
1376 *dest-- = *pa--;
1377 ++acount;
1378 bcount = 0;
1379 --na;
1380 if (na == 0)
1381 goto Succeed;
1382 if (acount >= MIN_GALLOP)
1383 break;
1384 }
1385 else {
1386 *dest-- = *pb--;
1387 ++bcount;
1388 acount = 0;
1389 --nb;
1390 if (nb == 1)
1391 goto CopyA;
1392 if (bcount >= MIN_GALLOP)
1393 break;
1394 }
1395 }
1396
1397 /* One run is winning so consistently that galloping may
1398 * be a huge win. So try that, and continue galloping until
1399 * (if ever) neither run appears to be winning consistently
1400 * anymore.
1401 */
1402 do {
1403 k = gallop_right(*pb, basea, na, na-1, compare);
1404 if (k < 0)
1405 goto Fail;
1406 k = na - k;
1407 acount = k;
1408 if (k) {
1409 dest -= k;
1410 pa -= k;
1411 memmove(dest+1, pa+1, k * sizeof(PyObject *));
1412 na -= k;
1413 if (na == 0)
1414 goto Succeed;
1415 }
1416 *dest-- = *pb--;
1417 --nb;
1418 if (nb == 1)
1419 goto CopyA;
1420
1421 k = gallop_left(*pa, baseb, nb, nb-1, compare);
1422 if (k < 0)
1423 goto Fail;
1424 k = nb - k;
1425 bcount = k;
1426 if (k) {
1427 dest -= k;
1428 pb -= k;
1429 memcpy(dest+1, pb+1, k * sizeof(PyObject *));
1430 nb -= k;
1431 if (nb == 1)
1432 goto CopyA;
1433 /* nb==0 is impossible now if the comparison
1434 * function is consistent, but we can't assume
1435 * that it is.
1436 */
1437 if (nb == 0)
1438 goto Succeed;
1439 }
1440 *dest-- = *pa--;
1441 --na;
1442 if (na == 0)
1443 goto Succeed;
1444 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
1445 }
1446Succeed:
1447 result = 0;
1448Fail:
1449 if (nb)
1450 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
1451 return result;
1452CopyA:
1453 assert(nb == 1 && na > 0);
1454 /* The first element of pb belongs at the front of the merge. */
1455 dest -= na;
1456 pa -= na;
1457 memmove(dest+1, pa+1, na * sizeof(PyObject *));
1458 *dest = *pb;
1459 return 0;
1460}
1461
1462/* Merge the two runs at stack indices i and i+1.
1463 * Returns 0 on success, -1 on error.
1464 */
1465static int
1466merge_at(MergeState *ms, int i)
1467{
1468 PyObject **pa, **pb;
1469 int na, nb;
1470 int k;
1471 PyObject *compare;
1472
1473 assert(ms != NULL);
1474 assert(ms->n >= 2);
1475 assert(i >= 0);
1476 assert(i == ms->n - 2 || i == ms->n - 3);
1477
1478 pa = ms->base[i];
1479 pb = ms->base[i+1];
1480 na = ms->len[i];
1481 nb = ms->len[i+1];
1482 assert(na > 0 && nb > 0);
1483 assert(pa + na == pb);
1484
1485 /* Record the length of the combined runs; if i is the 3rd-last
1486 * run now, also slide over the last run (which isn't involved
1487 * in this merge). The current run i+1 goes away in any case.
1488 */
1489 if (i == ms->n - 3) {
1490 ms->len[i+1] = ms->len[i+2];
1491 ms->base[i+1] = ms->base[i+2];
1492 }
1493 ms->len[i] = na + nb;
1494 --ms->n;
1495
1496 /* Where does b start in a? Elements in a before that can be
1497 * ignored (already in place).
1498 */
1499 compare = ms->compare;
1500 k = gallop_right(*pb, pa, na, 0, compare);
1501 if (k < 0)
1502 return -1;
1503 pa += k;
1504 na -= k;
1505 if (na == 0)
1506 return 0;
1507
1508 /* Where does a end in b? Elements in b after that can be
1509 * ignored (already in place).
1510 */
1511 nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);
1512 if (nb <= 0)
1513 return nb;
1514
1515 /* Merge what remains of the runs, using a temp array with
1516 * min(na, nb) elements.
1517 */
1518 if (na <= nb)
1519 return merge_lo(ms, pa, na, pb, nb);
1520 else
1521 return merge_hi(ms, pa, na, pb, nb);
1522}
1523
1524/* Examine the stack of runs waiting to be merged, merging adjacent runs
1525 * until the stack invariants are re-established:
1526 *
1527 * 1. len[-3] > len[-2] + len[-1]
1528 * 2. len[-2] > len[-1]
1529 *
1530 * See listsort.txt for more info.
1531 *
1532 * Returns 0 on success, -1 on error.
1533 */
1534static int
1535merge_collapse(MergeState *ms)
1536{
1537 int *len = ms->len;
1538
1539 assert(ms);
1540 while (ms->n > 1) {
1541 int n = ms->n - 2;
1542 if (n > 0 && len[n-1] <= len[n] + len[n+1]) {
1543 if (len[n-1] < len[n+1])
1544 --n;
1545 if (merge_at(ms, n) < 0)
1546 return -1;
1547 }
1548 else if (len[n] <= len[n+1]) {
1549 if (merge_at(ms, n) < 0)
1550 return -1;
1551 }
1552 else
1553 break;
1554 }
1555 return 0;
1556}
1557
1558/* Regardless of invariants, merge all runs on the stack until only one
1559 * remains. This is used at the end of the mergesort.
1560 *
1561 * Returns 0 on success, -1 on error.
1562 */
1563static int
1564merge_force_collapse(MergeState *ms)
1565{
1566 int *len = ms->len;
1567
1568 assert(ms);
1569 while (ms->n > 1) {
1570 int n = ms->n - 2;
1571 if (n > 0 && len[n-1] < len[n+1])
1572 --n;
1573 if (merge_at(ms, n) < 0)
1574 return -1;
1575 }
1576 return 0;
1577}
1578
1579/* Compute a good value for the minimum run length; natural runs shorter
1580 * than this are boosted artificially via binary insertion.
1581 *
1582 * If n < 64, return n (it's too small to bother with fancy stuff).
1583 * Else if n is an exact power of 2, return 32.
1584 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
1585 * strictly less than, an exact power of 2.
1586 *
1587 * See listsort.txt for more info.
1588 */
1589static int
1590merge_compute_minrun(int n)
1591{
1592 int r = 0; /* becomes 1 if any 1 bits are shifted off */
1593
1594 assert(n >= 0);
1595 while (n >= 64) {
1596 r |= n & 1;
1597 n >>= 1;
1598 }
1599 return n + r;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001600}
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001601
Jeremy Hylton938ace62002-07-17 16:30:39 +00001602static PyTypeObject immutable_list_type;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001603
Tim Petersa64dc242002-08-01 02:13:36 +00001604/* An adaptive, stable, natural mergesort. See listsort.txt.
1605 * Returns Py_None on success, NULL on error. Even in case of error, the
1606 * list will be some permutation of its input state (nothing is lost or
1607 * duplicated).
1608 */
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001609static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00001610listsort(PyListObject *self, PyObject *args)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001611{
Tim Petersa64dc242002-08-01 02:13:36 +00001612 MergeState ms;
1613 PyObject **lo, **hi;
1614 int nremaining;
1615 int minrun;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001616 PyTypeObject *savetype;
Tim Petersa64dc242002-08-01 02:13:36 +00001617 PyObject *compare = NULL;
1618 PyObject *result = NULL; /* guilty until proved innocent */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001619
Tim Petersa64dc242002-08-01 02:13:36 +00001620 assert(self != NULL);
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001621 if (args != NULL) {
Tim Petersa64dc242002-08-01 02:13:36 +00001622 if (!PyArg_ParseTuple(args, "|O:msort", &compare))
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001623 return NULL;
1624 }
Tim Petersa64dc242002-08-01 02:13:36 +00001625 merge_init(&ms, compare);
Tim Peters330f9e92002-07-19 07:05:44 +00001626
Tim Peters6d6c1a32001-08-02 04:15:00 +00001627 savetype = self->ob_type;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001628 self->ob_type = &immutable_list_type;
Tim Peters330f9e92002-07-19 07:05:44 +00001629
Tim Petersa64dc242002-08-01 02:13:36 +00001630 nremaining = self->ob_size;
1631 if (nremaining < 2)
1632 goto succeed;
Tim Peters330f9e92002-07-19 07:05:44 +00001633
Tim Petersa64dc242002-08-01 02:13:36 +00001634 /* March over the array once, left to right, finding natural runs,
1635 * and extending short natural runs to minrun elements.
1636 */
1637 lo = self->ob_item;
1638 hi = lo + nremaining;
1639 minrun = merge_compute_minrun(nremaining);
1640 do {
1641 int descending;
1642 int n;
Tim Peters330f9e92002-07-19 07:05:44 +00001643
Tim Petersa64dc242002-08-01 02:13:36 +00001644 /* Identify next run. */
1645 n = count_run(lo, hi, compare, &descending);
1646 if (n < 0)
1647 goto fail;
1648 if (descending)
1649 reverse_slice(lo, lo + n);
1650 /* If short, extend to min(minrun, nremaining). */
1651 if (n < minrun) {
1652 const int force = nremaining <= minrun ?
1653 nremaining : minrun;
1654 if (binarysort(lo, lo + force, lo + n, compare) < 0)
1655 goto fail;
1656 n = force;
1657 }
1658 /* Push run onto pending-runs stack, and maybe merge. */
1659 assert(ms.n < MAX_MERGE_PENDING);
1660 ms.base[ms.n] = lo;
1661 ms.len[ms.n] = n;
1662 ++ms.n;
1663 if (merge_collapse(&ms) < 0)
1664 goto fail;
1665 /* Advance to find next run. */
1666 lo += n;
1667 nremaining -= n;
1668 } while (nremaining);
1669 assert(lo == hi);
Tim Peters330f9e92002-07-19 07:05:44 +00001670
Tim Petersa64dc242002-08-01 02:13:36 +00001671 if (merge_force_collapse(&ms) < 0)
1672 goto fail;
1673 assert(ms.n == 1);
1674 assert(ms.base[0] == self->ob_item);
1675 assert(ms.len[0] == self->ob_size);
1676
1677succeed:
1678 result = Py_None;
Tim Peters330f9e92002-07-19 07:05:44 +00001679fail:
1680 self->ob_type = savetype;
Tim Petersa64dc242002-08-01 02:13:36 +00001681 merge_freemem(&ms);
1682 Py_XINCREF(result);
1683 return result;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001684}
Tim Peters330f9e92002-07-19 07:05:44 +00001685#undef IFLT
1686
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001687int
Fred Drakea2f55112000-07-09 15:16:51 +00001688PyList_Sort(PyObject *v)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001689{
1690 if (v == NULL || !PyList_Check(v)) {
1691 PyErr_BadInternalCall();
1692 return -1;
1693 }
1694 v = listsort((PyListObject *)v, (PyObject *)NULL);
1695 if (v == NULL)
1696 return -1;
1697 Py_DECREF(v);
1698 return 0;
1699}
1700
Guido van Rossumb86c5492001-02-12 22:06:02 +00001701static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001702listreverse(PyListObject *self)
Guido van Rossumb86c5492001-02-12 22:06:02 +00001703{
Tim Peters326b4482002-07-19 04:04:16 +00001704 if (self->ob_size > 1)
1705 reverse_slice(self->ob_item, self->ob_item + self->ob_size);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001706 Py_INCREF(Py_None);
1707 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00001708}
1709
Guido van Rossum84c76f51990-10-30 13:32:20 +00001710int
Fred Drakea2f55112000-07-09 15:16:51 +00001711PyList_Reverse(PyObject *v)
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00001712{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001713 if (v == NULL || !PyList_Check(v)) {
1714 PyErr_BadInternalCall();
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00001715 return -1;
1716 }
Tim Peters8e2e7ca2002-07-19 02:33:08 +00001717 listreverse((PyListObject *)v);
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00001718 return 0;
1719}
1720
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001721PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00001722PyList_AsTuple(PyObject *v)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001723{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001724 PyObject *w;
1725 PyObject **p;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001726 int n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001727 if (v == NULL || !PyList_Check(v)) {
1728 PyErr_BadInternalCall();
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001729 return NULL;
1730 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001731 n = ((PyListObject *)v)->ob_size;
1732 w = PyTuple_New(n);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001733 if (w == NULL)
1734 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001735 p = ((PyTupleObject *)w)->ob_item;
Thomas Wouters334fb892000-07-25 12:56:38 +00001736 memcpy((void *)p,
1737 (void *)((PyListObject *)v)->ob_item,
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001738 n*sizeof(PyObject *));
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001739 while (--n >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001740 Py_INCREF(*p);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001741 p++;
1742 }
1743 return w;
1744}
1745
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001746static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001747listindex(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00001748{
1749 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001750
Guido van Rossumed98d481991-03-06 13:07:53 +00001751 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001752 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1753 if (cmp > 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001754 return PyInt_FromLong((long)i);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001755 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001756 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00001757 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001758 PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00001759 return NULL;
1760}
1761
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001762static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001763listcount(PyListObject *self, PyObject *v)
Guido van Rossume6f7d181991-10-20 20:20:40 +00001764{
1765 int count = 0;
1766 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001767
Guido van Rossume6f7d181991-10-20 20:20:40 +00001768 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001769 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1770 if (cmp > 0)
Guido van Rossume6f7d181991-10-20 20:20:40 +00001771 count++;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001772 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001773 return NULL;
Guido van Rossume6f7d181991-10-20 20:20:40 +00001774 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001775 return PyInt_FromLong((long)count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00001776}
1777
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001778static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001779listremove(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00001780{
1781 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001782
Guido van Rossumed98d481991-03-06 13:07:53 +00001783 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001784 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1785 if (cmp > 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001786 if (list_ass_slice(self, i, i+1,
1787 (PyObject *)NULL) != 0)
Guido van Rossumed98d481991-03-06 13:07:53 +00001788 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001789 Py_INCREF(Py_None);
1790 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00001791 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001792 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001793 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00001794 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001795 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00001796 return NULL;
1797}
1798
Jeremy Hylton8caad492000-06-23 14:18:11 +00001799static int
1800list_traverse(PyListObject *o, visitproc visit, void *arg)
1801{
1802 int i, err;
1803 PyObject *x;
1804
1805 for (i = o->ob_size; --i >= 0; ) {
1806 x = o->ob_item[i];
1807 if (x != NULL) {
1808 err = visit(x, arg);
1809 if (err)
1810 return err;
1811 }
1812 }
1813 return 0;
1814}
1815
1816static int
1817list_clear(PyListObject *lp)
1818{
1819 (void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
1820 return 0;
1821}
1822
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001823static PyObject *
1824list_richcompare(PyObject *v, PyObject *w, int op)
1825{
1826 PyListObject *vl, *wl;
1827 int i;
1828
1829 if (!PyList_Check(v) || !PyList_Check(w)) {
1830 Py_INCREF(Py_NotImplemented);
1831 return Py_NotImplemented;
1832 }
1833
1834 vl = (PyListObject *)v;
1835 wl = (PyListObject *)w;
1836
1837 if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
1838 /* Shortcut: if the lengths differ, the lists differ */
1839 PyObject *res;
1840 if (op == Py_EQ)
1841 res = Py_False;
1842 else
1843 res = Py_True;
1844 Py_INCREF(res);
1845 return res;
1846 }
1847
1848 /* Search for the first index where items are different */
1849 for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
1850 int k = PyObject_RichCompareBool(vl->ob_item[i],
1851 wl->ob_item[i], Py_EQ);
1852 if (k < 0)
1853 return NULL;
1854 if (!k)
1855 break;
1856 }
1857
1858 if (i >= vl->ob_size || i >= wl->ob_size) {
1859 /* No more items to compare -- compare sizes */
1860 int vs = vl->ob_size;
1861 int ws = wl->ob_size;
1862 int cmp;
1863 PyObject *res;
1864 switch (op) {
1865 case Py_LT: cmp = vs < ws; break;
Tim Peters6ee42342001-07-06 17:45:43 +00001866 case Py_LE: cmp = vs <= ws; break;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001867 case Py_EQ: cmp = vs == ws; break;
1868 case Py_NE: cmp = vs != ws; break;
1869 case Py_GT: cmp = vs > ws; break;
1870 case Py_GE: cmp = vs >= ws; break;
1871 default: return NULL; /* cannot happen */
1872 }
1873 if (cmp)
1874 res = Py_True;
1875 else
1876 res = Py_False;
1877 Py_INCREF(res);
1878 return res;
1879 }
1880
1881 /* We have an item that differs -- shortcuts for EQ/NE */
1882 if (op == Py_EQ) {
1883 Py_INCREF(Py_False);
1884 return Py_False;
1885 }
1886 if (op == Py_NE) {
1887 Py_INCREF(Py_True);
1888 return Py_True;
1889 }
1890
1891 /* Compare the final item again using the proper operator */
1892 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
1893}
1894
Tim Peters6d6c1a32001-08-02 04:15:00 +00001895/* Adapted from newer code by Tim */
1896static int
1897list_fill(PyListObject *result, PyObject *v)
1898{
1899 PyObject *it; /* iter(v) */
1900 int n; /* guess for result list size */
1901 int i;
1902
1903 n = result->ob_size;
1904
1905 /* Special-case list(a_list), for speed. */
1906 if (PyList_Check(v)) {
1907 if (v == (PyObject *)result)
1908 return 0; /* source is destination, we're done */
1909 return list_ass_slice(result, 0, n, v);
1910 }
1911
1912 /* Empty previous contents */
1913 if (n != 0) {
1914 if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
1915 return -1;
1916 }
1917
1918 /* Get iterator. There may be some low-level efficiency to be gained
1919 * by caching the tp_iternext slot instead of using PyIter_Next()
1920 * later, but premature optimization is the root etc.
1921 */
1922 it = PyObject_GetIter(v);
1923 if (it == NULL)
1924 return -1;
1925
1926 /* Guess a result list size. */
1927 n = -1; /* unknown */
1928 if (PySequence_Check(v) &&
1929 v->ob_type->tp_as_sequence->sq_length) {
1930 n = PySequence_Size(v);
1931 if (n < 0)
1932 PyErr_Clear();
1933 }
1934 if (n < 0)
1935 n = 8; /* arbitrary */
1936 NRESIZE(result->ob_item, PyObject*, n);
Neal Norwitzd4e5be52002-05-22 23:19:17 +00001937 if (result->ob_item == NULL) {
1938 PyErr_NoMemory();
Tim Peters6d6c1a32001-08-02 04:15:00 +00001939 goto error;
Neal Norwitzd4e5be52002-05-22 23:19:17 +00001940 }
Neal Norwitz35fc7602002-06-13 21:11:11 +00001941 memset(result->ob_item, 0, sizeof(*result->ob_item) * n);
Tim Peters6d6c1a32001-08-02 04:15:00 +00001942 result->ob_size = n;
1943
1944 /* Run iterator to exhaustion. */
1945 for (i = 0; ; i++) {
1946 PyObject *item = PyIter_Next(it);
1947 if (item == NULL) {
1948 if (PyErr_Occurred())
1949 goto error;
1950 break;
1951 }
1952 if (i < n)
1953 PyList_SET_ITEM(result, i, item); /* steals ref */
1954 else {
1955 int status = ins1(result, result->ob_size, item);
1956 Py_DECREF(item); /* append creates a new ref */
1957 if (status < 0)
1958 goto error;
1959 }
1960 }
1961
1962 /* Cut back result list if initial guess was too large. */
1963 if (i < n && result != NULL) {
1964 if (list_ass_slice(result, i, n, (PyObject *)NULL) != 0)
1965 goto error;
1966 }
1967 Py_DECREF(it);
1968 return 0;
1969
1970 error:
1971 Py_DECREF(it);
1972 return -1;
1973}
1974
1975static int
1976list_init(PyListObject *self, PyObject *args, PyObject *kw)
1977{
1978 PyObject *arg = NULL;
1979 static char *kwlist[] = {"sequence", 0};
1980
1981 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
1982 return -1;
1983 if (arg != NULL)
1984 return list_fill(self, arg);
1985 if (self->ob_size > 0)
1986 return list_ass_slice(self, 0, self->ob_size, (PyObject*)NULL);
1987 return 0;
1988}
1989
Guido van Rossumdbb53d92001-12-03 16:32:18 +00001990static long
1991list_nohash(PyObject *self)
1992{
1993 PyErr_SetString(PyExc_TypeError, "list objects are unhashable");
1994 return -1;
1995}
1996
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00001997PyDoc_STRVAR(append_doc,
1998"L.append(object) -- append object to end");
1999PyDoc_STRVAR(extend_doc,
Martin v. Löwis673c0a22002-07-28 16:35:57 +00002000"L.extend(sequence) -- extend list by appending sequence elements");
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +00002001PyDoc_STRVAR(insert_doc,
2002"L.insert(index, object) -- insert object before index");
2003PyDoc_STRVAR(pop_doc,
2004"L.pop([index]) -> item -- remove and return item at index (default last)");
2005PyDoc_STRVAR(remove_doc,
2006"L.remove(value) -- remove first occurrence of value");
2007PyDoc_STRVAR(index_doc,
2008"L.index(value) -> integer -- return index of first occurrence of value");
2009PyDoc_STRVAR(count_doc,
2010"L.count(value) -> integer -- return number of occurrences of value");
2011PyDoc_STRVAR(reverse_doc,
2012"L.reverse() -- reverse *IN PLACE*");
2013PyDoc_STRVAR(sort_doc,
Tim Petersa64dc242002-08-01 02:13:36 +00002014"L.sort([cmpfunc]) -- stable sort *IN PLACE*; cmpfunc(x, y) -> -1, 0, 1");
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00002015
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002016static PyMethodDef list_methods[] = {
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002017 {"append", (PyCFunction)listappend, METH_O, append_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002018 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002019 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002020 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002021 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
2022 {"index", (PyCFunction)listindex, METH_O, index_doc},
2023 {"count", (PyCFunction)listcount, METH_O, count_doc},
2024 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002025 {"sort", (PyCFunction)listsort, METH_VARARGS, sort_doc},
Tim Petersa64dc242002-08-01 02:13:36 +00002026 {NULL, NULL} /* sentinel */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002027};
2028
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002029static PySequenceMethods list_as_sequence = {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002030 (inquiry)list_length, /* sq_length */
2031 (binaryfunc)list_concat, /* sq_concat */
2032 (intargfunc)list_repeat, /* sq_repeat */
2033 (intargfunc)list_item, /* sq_item */
2034 (intintargfunc)list_slice, /* sq_slice */
2035 (intobjargproc)list_ass_item, /* sq_ass_item */
2036 (intintobjargproc)list_ass_slice, /* sq_ass_slice */
2037 (objobjproc)list_contains, /* sq_contains */
2038 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
2039 (intargfunc)list_inplace_repeat, /* sq_inplace_repeat */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002040};
2041
Neal Norwitz2c2e8272002-06-14 02:04:18 +00002042PyDoc_STRVAR(list_doc,
Tim Peters6d6c1a32001-08-02 04:15:00 +00002043"list() -> new list\n"
Neal Norwitz2c2e8272002-06-14 02:04:18 +00002044"list(sequence) -> new list initialized from sequence's items");
Tim Peters6d6c1a32001-08-02 04:15:00 +00002045
Jeremy Hyltona4b4c3b2002-07-13 03:51:17 +00002046static PyObject *list_iter(PyObject *seq);
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002047
Jeremy Hyltona4b4c3b2002-07-13 03:51:17 +00002048static PyObject *
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002049list_subscript(PyListObject* self, PyObject* item)
2050{
2051 if (PyInt_Check(item)) {
2052 long i = PyInt_AS_LONG(item);
2053 if (i < 0)
2054 i += PyList_GET_SIZE(self);
2055 return list_item(self, i);
2056 }
2057 else if (PyLong_Check(item)) {
2058 long i = PyLong_AsLong(item);
2059 if (i == -1 && PyErr_Occurred())
2060 return NULL;
2061 if (i < 0)
2062 i += PyList_GET_SIZE(self);
2063 return list_item(self, i);
2064 }
2065 else if (PySlice_Check(item)) {
2066 int start, stop, step, slicelength, cur, i;
2067 PyObject* result;
2068 PyObject* it;
2069
2070 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2071 &start, &stop, &step, &slicelength) < 0) {
2072 return NULL;
2073 }
2074
2075 if (slicelength <= 0) {
2076 return PyList_New(0);
2077 }
2078 else {
2079 result = PyList_New(slicelength);
2080 if (!result) return NULL;
2081
Tim Peters3b01a122002-07-19 02:35:45 +00002082 for (cur = start, i = 0; i < slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002083 cur += step, i++) {
2084 it = PyList_GET_ITEM(self, cur);
2085 Py_INCREF(it);
2086 PyList_SET_ITEM(result, i, it);
2087 }
Tim Peters3b01a122002-07-19 02:35:45 +00002088
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002089 return result;
2090 }
2091 }
2092 else {
2093 PyErr_SetString(PyExc_TypeError,
2094 "list indices must be integers");
2095 return NULL;
2096 }
2097}
2098
Tim Peters3b01a122002-07-19 02:35:45 +00002099static int
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002100list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
2101{
2102 if (PyInt_Check(item)) {
2103 long i = PyInt_AS_LONG(item);
2104 if (i < 0)
2105 i += PyList_GET_SIZE(self);
2106 return list_ass_item(self, i, value);
2107 }
2108 else if (PyLong_Check(item)) {
2109 long i = PyLong_AsLong(item);
2110 if (i == -1 && PyErr_Occurred())
2111 return -1;
2112 if (i < 0)
2113 i += PyList_GET_SIZE(self);
2114 return list_ass_item(self, i, value);
2115 }
2116 else if (PySlice_Check(item)) {
2117 int start, stop, step, slicelength;
2118
2119 if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
2120 &start, &stop, &step, &slicelength) < 0) {
2121 return -1;
2122 }
2123
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002124 /* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
2125 if (step == 1 && ((PySliceObject*)item)->step == Py_None)
2126 return list_ass_slice(self, start, stop, value);
2127
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002128 if (value == NULL) {
2129 /* delete slice */
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002130 PyObject **garbage, **it;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002131 int cur, i, j;
Tim Peters3b01a122002-07-19 02:35:45 +00002132
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002133 if (slicelength <= 0)
2134 return 0;
2135
2136 if (step < 0) {
2137 stop = start + 1;
2138 start = stop + step*(slicelength - 1) - 1;
2139 step = -step;
2140 }
2141
2142 garbage = (PyObject**)
2143 PyMem_MALLOC(slicelength*sizeof(PyObject*));
Tim Peters3b01a122002-07-19 02:35:45 +00002144
2145 /* drawing pictures might help
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002146 understand these for loops */
Guido van Rossum75a20b12002-06-11 12:22:28 +00002147 for (cur = start, i = 0;
2148 cur < stop;
Michael W. Hudson56796f62002-07-29 14:35:04 +00002149 cur += step, i++) {
2150 int lim = step;
2151
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002152 garbage[i] = PyList_GET_ITEM(self, cur);
2153
Michael W. Hudson56796f62002-07-29 14:35:04 +00002154 if (cur + step >= self->ob_size) {
2155 lim = self->ob_size - cur - 1;
2156 }
2157
2158 for (j = 0; j < lim; j++) {
Tim Peters3b01a122002-07-19 02:35:45 +00002159 PyList_SET_ITEM(self, cur + j - i,
Guido van Rossum75a20b12002-06-11 12:22:28 +00002160 PyList_GET_ITEM(self,
2161 cur + j + 1));
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002162 }
2163 }
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002164 for (cur = start + slicelength*step + 1;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002165 cur < self->ob_size; cur++) {
2166 PyList_SET_ITEM(self, cur - slicelength,
2167 PyList_GET_ITEM(self, cur));
2168 }
2169 self->ob_size -= slicelength;
Michael W. Hudson9c14bad2002-06-19 15:44:15 +00002170 it = self->ob_item;
2171 NRESIZE(it, PyObject*, self->ob_size);
2172 self->ob_item = it;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002173
2174 for (i = 0; i < slicelength; i++) {
2175 Py_DECREF(garbage[i]);
2176 }
2177 PyMem_FREE(garbage);
2178
2179 return 0;
2180 }
2181 else {
2182 /* assign slice */
2183 PyObject **garbage, *ins;
2184 int cur, i;
2185
2186 if (!PyList_Check(value)) {
2187 PyErr_Format(PyExc_TypeError,
2188 "must assign list (not \"%.200s\") to slice",
2189 value->ob_type->tp_name);
2190 return -1;
2191 }
2192
2193 if (PyList_GET_SIZE(value) != slicelength) {
2194 PyErr_Format(PyExc_ValueError,
2195 "attempt to assign list of size %d to extended slice of size %d",
2196 PyList_Size(value), slicelength);
2197 return -1;
2198 }
2199
2200 if (!slicelength)
2201 return 0;
2202
2203 /* protect against a[::-1] = a */
Tim Peters3b01a122002-07-19 02:35:45 +00002204 if (self == (PyListObject*)value) {
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002205 value = list_slice((PyListObject*)value, 0,
2206 PyList_GET_SIZE(value));
Tim Peters3b01a122002-07-19 02:35:45 +00002207 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002208 else {
2209 Py_INCREF(value);
2210 }
2211
2212 garbage = (PyObject**)
2213 PyMem_MALLOC(slicelength*sizeof(PyObject*));
Tim Peters3b01a122002-07-19 02:35:45 +00002214
2215 for (cur = start, i = 0; i < slicelength;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002216 cur += step, i++) {
2217 garbage[i] = PyList_GET_ITEM(self, cur);
Tim Peters3b01a122002-07-19 02:35:45 +00002218
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002219 ins = PyList_GET_ITEM(value, i);
2220 Py_INCREF(ins);
2221 PyList_SET_ITEM(self, cur, ins);
2222 }
2223
2224 for (i = 0; i < slicelength; i++) {
2225 Py_DECREF(garbage[i]);
2226 }
Tim Peters3b01a122002-07-19 02:35:45 +00002227
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002228 PyMem_FREE(garbage);
2229 Py_DECREF(value);
Tim Peters3b01a122002-07-19 02:35:45 +00002230
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002231 return 0;
2232 }
Tim Peters3b01a122002-07-19 02:35:45 +00002233 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002234 else {
Tim Peters3b01a122002-07-19 02:35:45 +00002235 PyErr_SetString(PyExc_TypeError,
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002236 "list indices must be integers");
2237 return -1;
2238 }
2239}
2240
2241static PyMappingMethods list_as_mapping = {
2242 (inquiry)list_length,
2243 (binaryfunc)list_subscript,
2244 (objobjargproc)list_ass_subscript
2245};
2246
Guido van Rossumc0b618a1997-05-02 03:12:38 +00002247PyTypeObject PyList_Type = {
2248 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002249 0,
2250 "list",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002251 sizeof(PyListObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002252 0,
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002253 (destructor)list_dealloc, /* tp_dealloc */
2254 (printfunc)list_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002255 0, /* tp_getattr */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002256 0, /* tp_setattr */
2257 0, /* tp_compare */
2258 (reprfunc)list_repr, /* tp_repr */
2259 0, /* tp_as_number */
2260 &list_as_sequence, /* tp_as_sequence */
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +00002261 &list_as_mapping, /* tp_as_mapping */
Guido van Rossumdbb53d92001-12-03 16:32:18 +00002262 list_nohash, /* tp_hash */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002263 0, /* tp_call */
2264 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002265 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002266 0, /* tp_setattro */
2267 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002268 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Tim Peters6d6c1a32001-08-02 04:15:00 +00002269 Py_TPFLAGS_BASETYPE, /* tp_flags */
2270 list_doc, /* tp_doc */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002271 (traverseproc)list_traverse, /* tp_traverse */
2272 (inquiry)list_clear, /* tp_clear */
2273 list_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002274 0, /* tp_weaklistoffset */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002275 list_iter, /* tp_iter */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002276 0, /* tp_iternext */
2277 list_methods, /* tp_methods */
2278 0, /* tp_members */
2279 0, /* tp_getset */
2280 0, /* tp_base */
2281 0, /* tp_dict */
2282 0, /* tp_descr_get */
2283 0, /* tp_descr_set */
2284 0, /* tp_dictoffset */
2285 (initproc)list_init, /* tp_init */
2286 PyType_GenericAlloc, /* tp_alloc */
2287 PyType_GenericNew, /* tp_new */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002288 PyObject_GC_Del, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002289};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002290
2291
2292/* During a sort, we really can't have anyone modifying the list; it could
2293 cause core dumps. Thus, we substitute a dummy type that raises an
2294 explanatory exception when a modifying operation is used. Caveat:
2295 comparisons may behave differently; but I guess it's a bad idea anyway to
2296 compare a list that's being sorted... */
2297
2298static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00002299immutable_list_op(void)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002300{
2301 PyErr_SetString(PyExc_TypeError,
2302 "a list cannot be modified while it is being sorted");
2303 return NULL;
2304}
2305
2306static PyMethodDef immutable_list_methods[] = {
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002307 {"append", (PyCFunction)immutable_list_op, METH_VARARGS},
2308 {"insert", (PyCFunction)immutable_list_op, METH_VARARGS},
Tim Peters52e07172001-08-30 06:15:32 +00002309 {"extend", (PyCFunction)immutable_list_op, METH_O},
2310 {"pop", (PyCFunction)immutable_list_op, METH_VARARGS},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00002311 {"remove", (PyCFunction)immutable_list_op, METH_VARARGS},
2312 {"index", (PyCFunction)listindex, METH_O},
2313 {"count", (PyCFunction)listcount, METH_O},
2314 {"reverse", (PyCFunction)immutable_list_op, METH_VARARGS},
2315 {"sort", (PyCFunction)immutable_list_op, METH_VARARGS},
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002316 {NULL, NULL} /* sentinel */
2317};
2318
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002319static int
Fred Drakea2f55112000-07-09 15:16:51 +00002320immutable_list_ass(void)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002321{
2322 immutable_list_op();
2323 return -1;
2324}
2325
2326static PySequenceMethods immutable_list_as_sequence = {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002327 (inquiry)list_length, /* sq_length */
2328 (binaryfunc)list_concat, /* sq_concat */
2329 (intargfunc)list_repeat, /* sq_repeat */
2330 (intargfunc)list_item, /* sq_item */
2331 (intintargfunc)list_slice, /* sq_slice */
2332 (intobjargproc)immutable_list_ass, /* sq_ass_item */
2333 (intintobjargproc)immutable_list_ass, /* sq_ass_slice */
2334 (objobjproc)list_contains, /* sq_contains */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002335};
2336
2337static PyTypeObject immutable_list_type = {
2338 PyObject_HEAD_INIT(&PyType_Type)
2339 0,
2340 "list (immutable, during sort)",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002341 sizeof(PyListObject),
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002342 0,
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002343 0, /* Cannot happen */ /* tp_dealloc */
2344 (printfunc)list_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002345 0, /* tp_getattr */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002346 0, /* tp_setattr */
2347 0, /* Won't be called */ /* tp_compare */
2348 (reprfunc)list_repr, /* tp_repr */
2349 0, /* tp_as_number */
2350 &immutable_list_as_sequence, /* tp_as_sequence */
2351 0, /* tp_as_mapping */
Guido van Rossumdbb53d92001-12-03 16:32:18 +00002352 list_nohash, /* tp_hash */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002353 0, /* tp_call */
2354 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002355 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002356 0, /* tp_setattro */
2357 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00002358 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002359 list_doc, /* tp_doc */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002360 (traverseproc)list_traverse, /* tp_traverse */
2361 0, /* tp_clear */
2362 list_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00002363 0, /* tp_weaklistoffset */
2364 0, /* tp_iter */
2365 0, /* tp_iternext */
2366 immutable_list_methods, /* tp_methods */
2367 0, /* tp_members */
2368 0, /* tp_getset */
2369 0, /* tp_base */
2370 0, /* tp_dict */
2371 0, /* tp_descr_get */
2372 0, /* tp_descr_set */
2373 0, /* tp_init */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00002374 /* NOTE: This is *not* the standard list_type struct! */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00002375};
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002376
2377
2378/*********************** List Iterator **************************/
2379
2380typedef struct {
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002381 PyObject_HEAD
2382 long it_index;
Guido van Rossum86103ae2002-07-16 20:07:32 +00002383 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002384} listiterobject;
2385
2386PyTypeObject PyListIter_Type;
2387
Guido van Rossum5086e492002-07-16 15:56:52 +00002388static PyObject *
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002389list_iter(PyObject *seq)
2390{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002391 listiterobject *it;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002392
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002393 if (!PyList_Check(seq)) {
2394 PyErr_BadInternalCall();
2395 return NULL;
2396 }
2397 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
2398 if (it == NULL)
2399 return NULL;
2400 it->it_index = 0;
2401 Py_INCREF(seq);
2402 it->it_seq = (PyListObject *)seq;
2403 _PyObject_GC_TRACK(it);
2404 return (PyObject *)it;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002405}
2406
2407static void
2408listiter_dealloc(listiterobject *it)
2409{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002410 _PyObject_GC_UNTRACK(it);
Guido van Rossum86103ae2002-07-16 20:07:32 +00002411 Py_XDECREF(it->it_seq);
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002412 PyObject_GC_Del(it);
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002413}
2414
2415static int
2416listiter_traverse(listiterobject *it, visitproc visit, void *arg)
2417{
Guido van Rossum86103ae2002-07-16 20:07:32 +00002418 if (it->it_seq == NULL)
2419 return 0;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002420 return visit((PyObject *)it->it_seq, arg);
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002421}
2422
2423
2424static PyObject *
2425listiter_getiter(PyObject *it)
2426{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002427 Py_INCREF(it);
2428 return it;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002429}
2430
2431static PyObject *
Tim Peters93b2cc42002-06-01 05:22:55 +00002432listiter_next(listiterobject *it)
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002433{
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002434 PyListObject *seq;
2435 PyObject *item;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002436
Tim Peters93b2cc42002-06-01 05:22:55 +00002437 assert(it != NULL);
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002438 seq = it->it_seq;
Guido van Rossum86103ae2002-07-16 20:07:32 +00002439 if (seq == NULL)
2440 return NULL;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002441 assert(PyList_Check(seq));
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002442
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002443 if (it->it_index < PyList_GET_SIZE(seq)) {
Tim Peters93b2cc42002-06-01 05:22:55 +00002444 item = PyList_GET_ITEM(seq, it->it_index);
2445 ++it->it_index;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002446 Py_INCREF(item);
2447 return item;
2448 }
Guido van Rossum86103ae2002-07-16 20:07:32 +00002449
2450 Py_DECREF(seq);
2451 it->it_seq = NULL;
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002452 return NULL;
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002453}
2454
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002455PyTypeObject PyListIter_Type = {
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002456 PyObject_HEAD_INIT(&PyType_Type)
2457 0, /* ob_size */
2458 "listiterator", /* tp_name */
2459 sizeof(listiterobject), /* tp_basicsize */
2460 0, /* tp_itemsize */
2461 /* methods */
2462 (destructor)listiter_dealloc, /* tp_dealloc */
2463 0, /* tp_print */
2464 0, /* tp_getattr */
2465 0, /* tp_setattr */
2466 0, /* tp_compare */
2467 0, /* tp_repr */
2468 0, /* tp_as_number */
2469 0, /* tp_as_sequence */
2470 0, /* tp_as_mapping */
2471 0, /* tp_hash */
2472 0, /* tp_call */
2473 0, /* tp_str */
2474 PyObject_GenericGetAttr, /* tp_getattro */
2475 0, /* tp_setattro */
2476 0, /* tp_as_buffer */
2477 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
2478 0, /* tp_doc */
2479 (traverseproc)listiter_traverse, /* tp_traverse */
2480 0, /* tp_clear */
2481 0, /* tp_richcompare */
2482 0, /* tp_weaklistoffset */
2483 (getiterfunc)listiter_getiter, /* tp_iter */
2484 (iternextfunc)listiter_next, /* tp_iternext */
Guido van Rossum86103ae2002-07-16 20:07:32 +00002485 0, /* tp_methods */
Guido van Rossum6b6272c2002-07-16 20:10:23 +00002486 0, /* tp_members */
2487 0, /* tp_getset */
2488 0, /* tp_base */
2489 0, /* tp_dict */
2490 0, /* tp_descr_get */
2491 0, /* tp_descr_set */
Raymond Hettinger14bd6de2002-05-31 21:40:38 +00002492};