blob: b05fe27d602999acdc3b51bbbb5c68ff991c4556 [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002/* List object implementation */
3
Guido van Rossumc0b618a1997-05-02 03:12:38 +00004#include "Python.h"
5
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00006#ifdef STDC_HEADERS
7#include <stddef.h>
8#else
9#include <sys/types.h> /* For size_t */
10#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000011
Guido van Rossuma46d51d1995-01-26 22:59:43 +000012static int
Fred Drakea2f55112000-07-09 15:16:51 +000013roundupsize(int n)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000014{
Tim Peters65b8b842001-05-26 05:28:40 +000015 unsigned int nbits = 0;
16 unsigned int n2 = (unsigned int)n >> 5;
17
18 /* Round up:
19 * If n < 256, to a multiple of 8.
20 * If n < 2048, to a multiple of 64.
21 * If n < 16384, to a multiple of 512.
22 * If n < 131072, to a multiple of 4096.
23 * If n < 1048576, to a multiple of 32768.
24 * If n < 8388608, to a multiple of 262144.
25 * If n < 67108864, to a multiple of 2097152.
26 * If n < 536870912, to a multiple of 16777216.
27 * ...
28 * If n < 2**(5+3*i), to a multiple of 2**(3*i).
29 *
30 * This over-allocates proportional to the list size, making room
31 * for additional growth. The over-allocation is mild, but is
32 * enough to give linear-time amortized behavior over a long
33 * sequence of appends() in the presence of a poorly-performing
34 * system realloc() (which is a reality, e.g., across all flavors
35 * of Windows, with Win9x behavior being particularly bad -- and
36 * we've still got address space fragmentation problems on Win9x
37 * even with this scheme, although it requires much longer lists to
38 * provoke them than it used to).
39 */
40 do {
41 n2 >>= 3;
42 nbits += 3;
43 } while (n2);
44 return ((n >> nbits) + 1) << nbits;
45 }
Guido van Rossuma46d51d1995-01-26 22:59:43 +000046
Guido van Rossuma27d1121997-08-25 18:36:23 +000047#define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))
Guido van Rossuma46d51d1995-01-26 22:59:43 +000048
Guido van Rossumc0b618a1997-05-02 03:12:38 +000049PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +000050PyList_New(int size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000051{
52 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +000053 PyListObject *op;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000054 size_t nbytes;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000055 if (size < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000056 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000057 return NULL;
58 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +000059 nbytes = size * sizeof(PyObject *);
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000060 /* Check for overflow */
Guido van Rossumc0b618a1997-05-02 03:12:38 +000061 if (nbytes / sizeof(PyObject *) != (size_t)size) {
62 return PyErr_NoMemory();
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000063 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +000064 op = PyObject_GC_New(PyListObject, &PyList_Type);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000065 if (op == NULL) {
Neil Schemenauere83c00e2001-08-29 23:54:21 +000066 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000067 }
68 if (size <= 0) {
69 op->ob_item = NULL;
70 }
71 else {
Guido van Rossumb18618d2000-05-03 23:44:39 +000072 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000073 if (op->ob_item == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000074 return PyErr_NoMemory();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000075 }
76 }
Neil Schemenauere83c00e2001-08-29 23:54:21 +000077 op->ob_size = size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000078 for (i = 0; i < size; i++)
79 op->ob_item[i] = NULL;
Neil Schemenauere83c00e2001-08-29 23:54:21 +000080 _PyObject_GC_TRACK(op);
Guido van Rossumc0b618a1997-05-02 03:12:38 +000081 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000082}
83
84int
Fred Drakea2f55112000-07-09 15:16:51 +000085PyList_Size(PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000086{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000087 if (!PyList_Check(op)) {
88 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000089 return -1;
90 }
91 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +000092 return ((PyListObject *)op) -> ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000093}
94
Guido van Rossumc0b618a1997-05-02 03:12:38 +000095static PyObject *indexerr;
Guido van Rossum929f1b81996-08-09 20:51:27 +000096
Guido van Rossumc0b618a1997-05-02 03:12:38 +000097PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +000098PyList_GetItem(PyObject *op, int i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000099{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000100 if (!PyList_Check(op)) {
101 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000102 return NULL;
103 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000104 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000105 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000106 indexerr = PyString_FromString(
107 "list index out of range");
108 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000109 return NULL;
110 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000111 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000112}
113
114int
Fred Drakea2f55112000-07-09 15:16:51 +0000115PyList_SetItem(register PyObject *op, register int i,
116 register PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000117{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000118 register PyObject *olditem;
119 register PyObject **p;
120 if (!PyList_Check(op)) {
121 Py_XDECREF(newitem);
122 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000123 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000124 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000125 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
126 Py_XDECREF(newitem);
127 PyErr_SetString(PyExc_IndexError,
128 "list assignment index out of range");
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000129 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000130 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000131 p = ((PyListObject *)op) -> ob_item + i;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000132 olditem = *p;
133 *p = newitem;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000134 Py_XDECREF(olditem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000135 return 0;
136}
137
138static int
Fred Drakea2f55112000-07-09 15:16:51 +0000139ins1(PyListObject *self, int where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000140{
141 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000142 PyObject **items;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000143 if (v == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000144 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000145 return -1;
146 }
Trent Micka5846642000-08-13 22:47:45 +0000147 if (self->ob_size == INT_MAX) {
148 PyErr_SetString(PyExc_OverflowError,
149 "cannot add more objects to list");
150 return -1;
151 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000152 items = self->ob_item;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000153 NRESIZE(items, PyObject *, self->ob_size+1);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000154 if (items == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000155 PyErr_NoMemory();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000156 return -1;
157 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000158 if (where < 0)
159 where = 0;
160 if (where > self->ob_size)
161 where = self->ob_size;
162 for (i = self->ob_size; --i >= where; )
163 items[i+1] = items[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000164 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000165 items[where] = v;
166 self->ob_item = items;
167 self->ob_size++;
168 return 0;
169}
170
171int
Fred Drakea2f55112000-07-09 15:16:51 +0000172PyList_Insert(PyObject *op, int where, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000173{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000174 if (!PyList_Check(op)) {
175 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000176 return -1;
177 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000178 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000179}
180
181int
Fred Drakea2f55112000-07-09 15:16:51 +0000182PyList_Append(PyObject *op, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000183{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000184 if (!PyList_Check(op)) {
185 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000186 return -1;
187 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000188 return ins1((PyListObject *)op,
189 (int) ((PyListObject *)op)->ob_size, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000190}
191
192/* Methods */
193
194static void
Fred Drakea2f55112000-07-09 15:16:51 +0000195list_dealloc(PyListObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000196{
197 int i;
Guido van Rossumd724b232000-03-13 16:01:29 +0000198 Py_TRASHCAN_SAFE_BEGIN(op)
Neil Schemenauere83c00e2001-08-29 23:54:21 +0000199 _PyObject_GC_UNTRACK(op);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000200 if (op->ob_item != NULL) {
Guido van Rossumfa717011999-06-09 15:19:34 +0000201 /* Do it backwards, for Christian Tismer.
202 There's a simple test case where somehow this reduces
203 thrashing when a *very* large list is created and
204 immediately deleted. */
205 i = op->ob_size;
206 while (--i >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000207 Py_XDECREF(op->ob_item[i]);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000208 }
Guido van Rossumb18618d2000-05-03 23:44:39 +0000209 PyMem_FREE(op->ob_item);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000210 }
Guido van Rossum9475a232001-10-05 20:51:39 +0000211 op->ob_type->tp_free((PyObject *)op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000212 Py_TRASHCAN_SAFE_END(op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000213}
214
Guido van Rossum90933611991-06-07 16:10:43 +0000215static int
Fred Drakea2f55112000-07-09 15:16:51 +0000216list_print(PyListObject *op, FILE *fp, int flags)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000217{
218 int i;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000219
220 i = Py_ReprEnter((PyObject*)op);
221 if (i != 0) {
222 if (i < 0)
223 return i;
224 fprintf(fp, "[...]");
225 return 0;
226 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000227 fprintf(fp, "[");
Guido van Rossum90933611991-06-07 16:10:43 +0000228 for (i = 0; i < op->ob_size; i++) {
229 if (i > 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000230 fprintf(fp, ", ");
Guido van Rossumfb376de1998-04-10 22:47:27 +0000231 if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
232 Py_ReprLeave((PyObject *)op);
Guido van Rossum90933611991-06-07 16:10:43 +0000233 return -1;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000234 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000235 }
236 fprintf(fp, "]");
Guido van Rossumfb376de1998-04-10 22:47:27 +0000237 Py_ReprLeave((PyObject *)op);
Guido van Rossum90933611991-06-07 16:10:43 +0000238 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000239}
240
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000241static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000242list_repr(PyListObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000243{
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000244 int i;
Tim Petersa7259592001-06-16 05:11:17 +0000245 PyObject *s, *temp;
246 PyObject *pieces = NULL, *result = NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000247
248 i = Py_ReprEnter((PyObject*)v);
249 if (i != 0) {
Tim Petersa7259592001-06-16 05:11:17 +0000250 return i > 0 ? PyString_FromString("[...]") : NULL;
Guido van Rossumfb376de1998-04-10 22:47:27 +0000251 }
Tim Petersa7259592001-06-16 05:11:17 +0000252
253 if (v->ob_size == 0) {
254 result = PyString_FromString("[]");
255 goto Done;
256 }
257
258 pieces = PyList_New(0);
259 if (pieces == NULL)
260 goto Done;
261
262 /* Do repr() on each element. Note that this may mutate the list,
263 so must refetch the list size on each iteration. */
264 for (i = 0; i < v->ob_size; ++i) {
265 int status;
266 s = PyObject_Repr(v->ob_item[i]);
267 if (s == NULL)
268 goto Done;
269 status = PyList_Append(pieces, s);
270 Py_DECREF(s); /* append created a new ref */
271 if (status < 0)
272 goto Done;
273 }
274
275 /* Add "[]" decorations to the first and last items. */
276 assert(PyList_GET_SIZE(pieces) > 0);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000277 s = PyString_FromString("[");
Tim Petersa7259592001-06-16 05:11:17 +0000278 if (s == NULL)
279 goto Done;
280 temp = PyList_GET_ITEM(pieces, 0);
281 PyString_ConcatAndDel(&s, temp);
282 PyList_SET_ITEM(pieces, 0, s);
283 if (s == NULL)
284 goto Done;
285
286 s = PyString_FromString("]");
287 if (s == NULL)
288 goto Done;
289 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
290 PyString_ConcatAndDel(&temp, s);
291 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
292 if (temp == NULL)
293 goto Done;
294
295 /* Paste them all together with ", " between. */
296 s = PyString_FromString(", ");
297 if (s == NULL)
298 goto Done;
299 result = _PyString_Join(s, pieces);
300 Py_DECREF(s);
301
302Done:
303 Py_XDECREF(pieces);
Guido van Rossumfb376de1998-04-10 22:47:27 +0000304 Py_ReprLeave((PyObject *)v);
Tim Petersa7259592001-06-16 05:11:17 +0000305 return result;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000306}
307
308static int
Fred Drakea2f55112000-07-09 15:16:51 +0000309list_length(PyListObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000310{
311 return a->ob_size;
312}
313
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000314
315
316static int
Fred Drakea2f55112000-07-09 15:16:51 +0000317list_contains(PyListObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000318{
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000319 int i;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000320
321 for (i = 0; i < a->ob_size; ++i) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000322 int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
323 Py_EQ);
324 if (cmp > 0)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000325 return 1;
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000326 else if (cmp < 0)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000327 return -1;
328 }
329 return 0;
330}
331
332
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000333static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000334list_item(PyListObject *a, int i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000335{
336 if (i < 0 || i >= a->ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000337 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000338 indexerr = PyString_FromString(
339 "list index out of range");
340 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000341 return NULL;
342 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000343 Py_INCREF(a->ob_item[i]);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000344 return a->ob_item[i];
345}
346
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000347static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000348list_slice(PyListObject *a, int ilow, int ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000349{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000350 PyListObject *np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000351 int i;
352 if (ilow < 0)
353 ilow = 0;
354 else if (ilow > a->ob_size)
355 ilow = a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000356 if (ihigh < ilow)
357 ihigh = ilow;
358 else if (ihigh > a->ob_size)
359 ihigh = a->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000360 np = (PyListObject *) PyList_New(ihigh - ilow);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000361 if (np == NULL)
362 return NULL;
363 for (i = ilow; i < ihigh; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000364 PyObject *v = a->ob_item[i];
365 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000366 np->ob_item[i - ilow] = v;
367 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000368 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000369}
370
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000371PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000372PyList_GetSlice(PyObject *a, int ilow, int ihigh)
Guido van Rossum234f9421993-06-17 12:35:49 +0000373{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000374 if (!PyList_Check(a)) {
375 PyErr_BadInternalCall();
Guido van Rossum234f9421993-06-17 12:35:49 +0000376 return NULL;
377 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000378 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000379}
380
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000381static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000382list_concat(PyListObject *a, PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000383{
384 int size;
385 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000386 PyListObject *np;
387 if (!PyList_Check(bb)) {
Fred Drakeb6a9ada2000-06-01 03:12:13 +0000388 PyErr_Format(PyExc_TypeError,
Fred Drake914a2ed2000-06-01 14:31:03 +0000389 "can only concatenate list (not \"%.200s\") to list",
390 bb->ob_type->tp_name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000391 return NULL;
392 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000393#define b ((PyListObject *)bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000394 size = a->ob_size + b->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000395 np = (PyListObject *) PyList_New(size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000396 if (np == NULL) {
Guido van Rossum90933611991-06-07 16:10:43 +0000397 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000398 }
399 for (i = 0; i < a->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000400 PyObject *v = a->ob_item[i];
401 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000402 np->ob_item[i] = v;
403 }
404 for (i = 0; i < b->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000405 PyObject *v = b->ob_item[i];
406 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000407 np->ob_item[i + a->ob_size] = v;
408 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000409 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000410#undef b
411}
412
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000413static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000414list_repeat(PyListObject *a, int n)
Guido van Rossumed98d481991-03-06 13:07:53 +0000415{
416 int i, j;
417 int size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000418 PyListObject *np;
419 PyObject **p;
Guido van Rossumed98d481991-03-06 13:07:53 +0000420 if (n < 0)
421 n = 0;
422 size = a->ob_size * n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000423 np = (PyListObject *) PyList_New(size);
Guido van Rossumed98d481991-03-06 13:07:53 +0000424 if (np == NULL)
425 return NULL;
426 p = np->ob_item;
427 for (i = 0; i < n; i++) {
428 for (j = 0; j < a->ob_size; j++) {
429 *p = a->ob_item[j];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000430 Py_INCREF(*p);
Guido van Rossumed98d481991-03-06 13:07:53 +0000431 p++;
432 }
433 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000434 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000435}
436
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000437static int
Fred Drakea2f55112000-07-09 15:16:51 +0000438list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000439{
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000440 /* Because [X]DECREF can recursively invoke list operations on
441 this list, we must postpone all [X]DECREF activity until
442 after the list is back in its canonical shape. Therefore
443 we must allocate an additional array, 'recycle', into which
444 we temporarily copy the items that are deleted from the
445 list. :-( */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000446 PyObject **recycle, **p;
447 PyObject **item;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000448 int n; /* Size of replacement list */
449 int d; /* Change in size */
450 int k; /* Loop index */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000451#define b ((PyListObject *)v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000452 if (v == NULL)
453 n = 0;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000454 else if (PyList_Check(v)) {
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000455 n = b->ob_size;
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000456 if (a == b) {
457 /* Special case "a[i:j] = a" -- copy b first */
458 int ret;
459 v = list_slice(b, 0, n);
460 ret = list_ass_slice(a, ilow, ihigh, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000461 Py_DECREF(v);
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000462 return ret;
463 }
464 }
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000465 else {
Fred Drakeb6a9ada2000-06-01 03:12:13 +0000466 PyErr_Format(PyExc_TypeError,
467 "must assign list (not \"%.200s\") to slice",
468 v->ob_type->tp_name);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000469 return -1;
470 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000471 if (ilow < 0)
472 ilow = 0;
473 else if (ilow > a->ob_size)
474 ilow = a->ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000475 if (ihigh < ilow)
476 ihigh = ilow;
477 else if (ihigh > a->ob_size)
478 ihigh = a->ob_size;
479 item = a->ob_item;
480 d = n - (ihigh-ilow);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000481 if (ihigh > ilow)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000482 p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000483 else
484 p = recycle = NULL;
485 if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000486 for (k = ilow; k < ihigh; k++)
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000487 *p++ = item[k];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000488 if (d < 0) {
489 for (/*k = ihigh*/; k < a->ob_size; k++)
490 item[k+d] = item[k];
491 a->ob_size += d;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000492 NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000493 a->ob_item = item;
494 }
495 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000496 else { /* Insert d items; recycle ihigh-ilow items */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000497 NRESIZE(item, PyObject *, a->ob_size + d);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000498 if (item == NULL) {
Guido van Rossumb18618d2000-05-03 23:44:39 +0000499 if (recycle != NULL)
500 PyMem_DEL(recycle);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000501 PyErr_NoMemory();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000502 return -1;
503 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000504 for (k = a->ob_size; --k >= ihigh; )
505 item[k+d] = item[k];
506 for (/*k = ihigh-1*/; k >= ilow; --k)
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000507 *p++ = item[k];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000508 a->ob_item = item;
509 a->ob_size += d;
510 }
511 for (k = 0; k < n; k++, ilow++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000512 PyObject *w = b->ob_item[k];
513 Py_XINCREF(w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000514 item[ilow] = w;
515 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000516 if (recycle) {
517 while (--p >= recycle)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000518 Py_XDECREF(*p);
519 PyMem_DEL(recycle);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000520 }
Tim Peters6d6c1a32001-08-02 04:15:00 +0000521 if (a->ob_size == 0 && a->ob_item != NULL) {
522 PyMem_FREE(a->ob_item);
523 a->ob_item = NULL;
524 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000525 return 0;
526#undef b
527}
528
Guido van Rossum234f9421993-06-17 12:35:49 +0000529int
Fred Drakea2f55112000-07-09 15:16:51 +0000530PyList_SetSlice(PyObject *a, int ilow, int ihigh, PyObject *v)
Guido van Rossum234f9421993-06-17 12:35:49 +0000531{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000532 if (!PyList_Check(a)) {
533 PyErr_BadInternalCall();
Guido van Rossum1fc238a1993-07-29 08:25:09 +0000534 return -1;
Guido van Rossum234f9421993-06-17 12:35:49 +0000535 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000536 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000537}
538
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000539static PyObject *
540list_inplace_repeat(PyListObject *self, int n)
541{
542 PyObject **items;
543 int size, i, j;
544
545
546 size = PyList_GET_SIZE(self);
547 if (size == 0) {
548 Py_INCREF(self);
549 return (PyObject *)self;
550 }
551
552 items = self->ob_item;
553
554 if (n < 1) {
555 self->ob_item = NULL;
556 self->ob_size = 0;
557 for (i = 0; i < size; i++)
558 Py_XDECREF(items[i]);
559 PyMem_DEL(items);
560 Py_INCREF(self);
561 return (PyObject *)self;
562 }
563
564 NRESIZE(items, PyObject*, size*n);
565 if (items == NULL) {
566 PyErr_NoMemory();
567 goto finally;
568 }
569 self->ob_item = items;
570 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
571 for (j = 0; j < size; j++) {
572 PyObject *o = PyList_GET_ITEM(self, j);
573 Py_INCREF(o);
574 PyList_SET_ITEM(self, self->ob_size++, o);
575 }
576 }
577 Py_INCREF(self);
578 return (PyObject *)self;
579 finally:
580 return NULL;
581}
582
Guido van Rossum4a450d01991-04-03 19:05:18 +0000583static int
Fred Drakea2f55112000-07-09 15:16:51 +0000584list_ass_item(PyListObject *a, int i, PyObject *v)
Guido van Rossum4a450d01991-04-03 19:05:18 +0000585{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000586 PyObject *old_value;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000587 if (i < 0 || i >= a->ob_size) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000588 PyErr_SetString(PyExc_IndexError,
589 "list assignment index out of range");
Guido van Rossum4a450d01991-04-03 19:05:18 +0000590 return -1;
591 }
592 if (v == NULL)
593 return list_ass_slice(a, i, i+1, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000594 Py_INCREF(v);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000595 old_value = a->ob_item[i];
Guido van Rossum4a450d01991-04-03 19:05:18 +0000596 a->ob_item[i] = v;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000597 Py_DECREF(old_value);
Guido van Rossum4a450d01991-04-03 19:05:18 +0000598 return 0;
599}
600
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000601static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000602ins(PyListObject *self, int where, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000603{
604 if (ins1(self, where, v) != 0)
605 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000606 Py_INCREF(Py_None);
607 return Py_None;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000608}
609
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000610static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000611listinsert(PyListObject *self, PyObject *args)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000612{
613 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000614 PyObject *v;
Guido van Rossumc00a9382000-02-24 21:48:29 +0000615 if (!PyArg_ParseTuple(args, "iO:insert", &i, &v))
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000616 return NULL;
Guido van Rossumbf80e541993-02-08 15:49:17 +0000617 return ins(self, i, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000618}
619
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000620static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000621listappend(PyListObject *self, PyObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000622{
Guido van Rossumbf80e541993-02-08 15:49:17 +0000623 return ins(self, (int) self->ob_size, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000624}
625
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000626static int
627listextend_internal(PyListObject *self, PyObject *b)
Barry Warsawdedf6d61998-10-09 16:37:25 +0000628{
Barry Warsawdedf6d61998-10-09 16:37:25 +0000629 PyObject **items;
630 int selflen = PyList_GET_SIZE(self);
631 int blen;
632 register int i;
633
Jeremy Hyltondb60bb52001-01-03 22:32:16 +0000634 if (PyObject_Size(b) == 0) {
Barry Warsawdedf6d61998-10-09 16:37:25 +0000635 /* short circuit when b is empty */
Jeremy Hyltondb60bb52001-01-03 22:32:16 +0000636 Py_DECREF(b);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000637 return 0;
Jeremy Hyltondb60bb52001-01-03 22:32:16 +0000638 }
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000639
Barry Warsawdedf6d61998-10-09 16:37:25 +0000640 if (self == (PyListObject*)b) {
641 /* as in list_ass_slice() we must special case the
642 * situation: a.extend(a)
643 *
644 * XXX: I think this way ought to be faster than using
645 * list_slice() the way list_ass_slice() does.
646 */
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000647 Py_DECREF(b);
Barry Warsawdedf6d61998-10-09 16:37:25 +0000648 b = PyList_New(selflen);
649 if (!b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000650 return -1;
Barry Warsawdedf6d61998-10-09 16:37:25 +0000651 for (i = 0; i < selflen; i++) {
652 PyObject *o = PyList_GET_ITEM(self, i);
653 Py_INCREF(o);
654 PyList_SET_ITEM(b, i, o);
655 }
656 }
Barry Warsawdedf6d61998-10-09 16:37:25 +0000657
Jeremy Hylton03657cf2000-07-12 13:05:33 +0000658 blen = PyObject_Size(b);
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000659
Barry Warsawdedf6d61998-10-09 16:37:25 +0000660 /* resize a using idiom */
661 items = self->ob_item;
662 NRESIZE(items, PyObject*, selflen + blen);
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000663 if (items == NULL) {
Barry Warsawdedf6d61998-10-09 16:37:25 +0000664 PyErr_NoMemory();
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000665 Py_DECREF(b);
666 return -1;
Barry Warsawdedf6d61998-10-09 16:37:25 +0000667 }
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000668
Barry Warsawdedf6d61998-10-09 16:37:25 +0000669 self->ob_item = items;
670
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000671 /* populate the end of self with b's items */
Barry Warsawdedf6d61998-10-09 16:37:25 +0000672 for (i = 0; i < blen; i++) {
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000673 PyObject *o = PySequence_Fast_GET_ITEM(b, i);
Barry Warsawdedf6d61998-10-09 16:37:25 +0000674 Py_INCREF(o);
675 PyList_SET_ITEM(self, self->ob_size++, o);
676 }
Andrew M. Kuchling74042d62000-06-18 18:43:14 +0000677 Py_DECREF(b);
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000678 return 0;
Barry Warsawdedf6d61998-10-09 16:37:25 +0000679}
680
681
682static PyObject *
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000683list_inplace_concat(PyListObject *self, PyObject *other)
684{
Tim Peters1af03e92001-05-26 19:37:54 +0000685 other = PySequence_Fast(other, "argument to += must be iterable");
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000686 if (!other)
687 return NULL;
688
689 if (listextend_internal(self, other) < 0)
690 return NULL;
691
692 Py_INCREF(self);
693 return (PyObject *)self;
694}
695
696static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +0000697listextend(PyListObject *self, PyObject *b)
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000698{
699
Tim Peters1af03e92001-05-26 19:37:54 +0000700 b = PySequence_Fast(b, "list.extend() argument must be iterable");
Thomas Wouterse289e0b2000-08-24 20:08:19 +0000701 if (!b)
702 return NULL;
703
704 if (listextend_internal(self, b) < 0)
705 return NULL;
706
707 Py_INCREF(Py_None);
708 return Py_None;
709}
710
711static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +0000712listpop(PyListObject *self, PyObject *args)
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000713{
714 int i = -1;
715 PyObject *v;
Guido van Rossumc00a9382000-02-24 21:48:29 +0000716 if (!PyArg_ParseTuple(args, "|i:pop", &i))
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +0000717 return NULL;
718 if (self->ob_size == 0) {
719 /* Special-case most common failure cause */
720 PyErr_SetString(PyExc_IndexError, "pop from empty list");
721 return NULL;
722 }
723 if (i < 0)
724 i += self->ob_size;
725 if (i < 0 || i >= self->ob_size) {
726 PyErr_SetString(PyExc_IndexError, "pop index out of range");
727 return NULL;
728 }
729 v = self->ob_item[i];
730 Py_INCREF(v);
731 if (list_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
732 Py_DECREF(v);
733 return NULL;
734 }
735 return v;
736}
737
Guido van Rossum3f236de1996-12-10 23:55:39 +0000738/* New quicksort implementation for arrays of object pointers.
739 Thanks to discussions with Tim Peters. */
740
741/* CMPERROR is returned by our comparison function when an error
742 occurred. This is the largest negative integer (0x80000000 on a
743 32-bit system). */
Guido van Rossum19700b61997-03-05 00:45:43 +0000744#define CMPERROR ( (int) ((unsigned int)1 << (8*sizeof(int) - 1)) )
Guido van Rossum3f236de1996-12-10 23:55:39 +0000745
746/* Comparison function. Takes care of calling a user-supplied
747 comparison function (any callable Python object). Calls the
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000748 standard comparison function, PyObject_Compare(), if the user-
749 supplied function is NULL. */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000750
751static int
Fred Drakea2f55112000-07-09 15:16:51 +0000752docompare(PyObject *x, PyObject *y, PyObject *compare)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000753{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000754 PyObject *args, *res;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000755 int i;
756
Guido van Rossumc8b6df91997-05-23 00:06:51 +0000757 if (compare == NULL) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +0000758 /* NOTE: we rely on the fact here that the sorting algorithm
759 only ever checks whether k<0, i.e., whether x<y. So we
760 invoke the rich comparison function with Py_LT ('<'), and
761 return -1 when it returns true and 0 when it returns
762 false. */
763 i = PyObject_RichCompareBool(x, y, Py_LT);
764 if (i < 0)
765 return CMPERROR;
766 else
767 return -i;
Guido van Rossumc8b6df91997-05-23 00:06:51 +0000768 }
Guido van Rossum3f236de1996-12-10 23:55:39 +0000769
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000770 args = Py_BuildValue("(OO)", x, y);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000771 if (args == NULL)
772 return CMPERROR;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000773 res = PyEval_CallObject(compare, args);
774 Py_DECREF(args);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000775 if (res == NULL)
776 return CMPERROR;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000777 if (!PyInt_Check(res)) {
778 Py_DECREF(res);
779 PyErr_SetString(PyExc_TypeError,
Guido van Rossum9bcd1d71999-04-19 17:44:39 +0000780 "comparison function must return int");
Guido van Rossum3f236de1996-12-10 23:55:39 +0000781 return CMPERROR;
782 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000783 i = PyInt_AsLong(res);
784 Py_DECREF(res);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000785 if (i < 0)
786 return -1;
787 if (i > 0)
788 return 1;
789 return 0;
790}
791
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000792/* MINSIZE is the smallest array that will get a full-blown samplesort
793 treatment; smaller arrays are sorted using binary insertion. It must
794 be at least 7 for the samplesort implementation to work. Binary
795 insertion does fewer compares, but can suffer O(N**2) data movement.
796 The more expensive compares, the larger MINSIZE should be. */
797#define MINSIZE 100
798
799/* MINPARTITIONSIZE is the smallest array slice samplesort will bother to
800 partition; smaller slices are passed to binarysort. It must be at
801 least 2, and no larger than MINSIZE. Setting it higher reduces the #
802 of compares slowly, but increases the amount of data movement quickly.
803 The value here was chosen assuming a compare costs ~25x more than
804 swapping a pair of memory-resident pointers -- but under that assumption,
805 changing the value by a few dozen more or less has aggregate effect
806 under 1%. So the value is crucial, but not touchy <wink>. */
807#define MINPARTITIONSIZE 40
808
809/* MAXMERGE is the largest number of elements we'll always merge into
810 a known-to-be sorted chunk via binary insertion, regardless of the
811 size of that chunk. Given a chunk of N sorted elements, and a group
812 of K unknowns, the largest K for which it's better to do insertion
813 (than a full-blown sort) is a complicated function of N and K mostly
814 involving the expected number of compares and data moves under each
815 approach, and the relative cost of those operations on a specific
816 architecure. The fixed value here is conservative, and should be a
817 clear win regardless of architecture or N. */
818#define MAXMERGE 15
Guido van Rossum3f236de1996-12-10 23:55:39 +0000819
Guido van Rossum3f236de1996-12-10 23:55:39 +0000820/* STACKSIZE is the size of our work stack. A rough estimate is that
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000821 this allows us to sort arrays of size N where
822 N / ln(N) = MINPARTITIONSIZE * 2**STACKSIZE, so 60 is more than enough
823 for arrays of size 2**64. Because we push the biggest partition
824 first, the worst case occurs when all subarrays are always partitioned
825 exactly in two. */
826#define STACKSIZE 60
Guido van Rossum3f236de1996-12-10 23:55:39 +0000827
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000828
829#define SETK(X,Y) if ((k = docompare(X,Y,compare))==CMPERROR) goto fail
830
831/* binarysort is the best method for sorting small arrays: it does
832 few compares, but can do data movement quadratic in the number of
833 elements.
Guido van Rossum42812581998-06-17 14:15:44 +0000834 [lo, hi) is a contiguous slice of a list, and is sorted via
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000835 binary insertion.
836 On entry, must have lo <= start <= hi, and that [lo, start) is already
837 sorted (pass start == lo if you don't know!).
838 If docompare complains (returns CMPERROR) return -1, else 0.
839 Even in case of error, the output slice will be some permutation of
840 the input (nothing is lost or duplicated).
841*/
Guido van Rossum3f236de1996-12-10 23:55:39 +0000842
843static int
Fred Drakea2f55112000-07-09 15:16:51 +0000844binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
845 /* compare -- comparison function object, or NULL for default */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000846{
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000847 /* assert lo <= start <= hi
848 assert [lo, start) is sorted */
849 register int k;
850 register PyObject **l, **p, **r;
851 register PyObject *pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000852
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000853 if (lo == start)
854 ++start;
855 for (; start < hi; ++start) {
856 /* set l to where *start belongs */
857 l = lo;
858 r = start;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000859 pivot = *r;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000860 do {
861 p = l + ((r - l) >> 1);
862 SETK(pivot, *p);
863 if (k < 0)
864 r = p;
865 else
866 l = p + 1;
867 } while (l < r);
868 /* Pivot should go at l -- slide over to make room.
869 Caution: using memmove is much slower under MSVC 5;
870 we're not usually moving many slots. */
871 for (p = start; p > l; --p)
872 *p = *(p-1);
873 *l = pivot;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000874 }
Guido van Rossum3f236de1996-12-10 23:55:39 +0000875 return 0;
Guido van Rossuma119c0d1998-05-29 17:56:32 +0000876
877 fail:
878 return -1;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000879}
880
881/* samplesortslice is the sorting workhorse.
Guido van Rossum42812581998-06-17 14:15:44 +0000882 [lo, hi) is a contiguous slice of a list, to be sorted in place.
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000883 On entry, must have lo <= hi,
884 If docompare complains (returns CMPERROR) return -1, else 0.
885 Even in case of error, the output slice will be some permutation of
886 the input (nothing is lost or duplicated).
887
888 samplesort is basically quicksort on steroids: a power of 2 close
889 to n/ln(n) is computed, and that many elements (less 1) are picked at
890 random from the array and sorted. These 2**k - 1 elements are then
891 used as preselected pivots for an equal number of quicksort
892 partitioning steps, partitioning the slice into 2**k chunks each of
893 size about ln(n). These small final chunks are then usually handled
894 by binarysort. Note that when k=1, this is roughly the same as an
895 ordinary quicksort using a random pivot, and when k=2 this is roughly
896 a median-of-3 quicksort. From that view, using k ~= lg(n/ln(n)) makes
897 this a "median of n/ln(n)" quicksort. You can also view it as a kind
898 of bucket sort, where 2**k-1 bucket boundaries are picked dynamically.
899
900 The large number of samples makes a quadratic-time case almost
901 impossible, and asymptotically drives the average-case number of
902 compares from quicksort's 2 N ln N (or 12/7 N ln N for the median-of-
903 3 variant) down to N lg N.
904
905 We also play lots of low-level tricks to cut the number of compares.
906
907 Very obscure: To avoid using extra memory, the PPs are stored in the
908 array and shuffled around as partitioning proceeds. At the start of a
909 partitioning step, we'll have 2**m-1 (for some m) PPs in sorted order,
910 adjacent (either on the left or the right!) to a chunk of X elements
911 that are to be partitioned: P X or X P. In either case we need to
912 shuffle things *in place* so that the 2**(m-1) smaller PPs are on the
913 left, followed by the PP to be used for this step (that's the middle
914 of the PPs), followed by X, followed by the 2**(m-1) larger PPs:
915 P X or X P -> Psmall pivot X Plarge
916 and the order of the PPs must not be altered. It can take a while
917 to realize this isn't trivial! It can take even longer <wink> to
918 understand why the simple code below works, using only 2**(m-1) swaps.
919 The key is that the order of the X elements isn't necessarily
920 preserved: X can end up as some cyclic permutation of its original
921 order. That's OK, because X is unsorted anyway. If the order of X
922 had to be preserved too, the simplest method I know of using O(1)
923 scratch storage requires len(X) + 2**(m-1) swaps, spread over 2 passes.
924 Since len(X) is typically several times larger than 2**(m-1), that
925 would slow things down.
926*/
927
928struct SamplesortStackNode {
929 /* Represents a slice of the array, from (& including) lo up
930 to (but excluding) hi. "extra" additional & adjacent elements
931 are pre-selected pivots (PPs), spanning [lo-extra, lo) if
932 extra > 0, or [hi, hi-extra) if extra < 0. The PPs are
933 already sorted, but nothing is known about the other elements
934 in [lo, hi). |extra| is always one less than a power of 2.
935 When extra is 0, we're out of PPs, and the slice must be
936 sorted by some other means. */
937 PyObject **lo;
938 PyObject **hi;
939 int extra;
940};
941
942/* The number of PPs we want is 2**k - 1, where 2**k is as close to
Guido van Rossum42812581998-06-17 14:15:44 +0000943 N / ln(N) as possible. So k ~= lg(N / ln(N)). Calling libm routines
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000944 is undesirable, so cutoff values are canned in the "cutoff" table
945 below: cutoff[i] is the smallest N such that k == CUTOFFBASE + i. */
946#define CUTOFFBASE 4
Guido van Rossum3aa23fd1999-01-14 19:01:53 +0000947static long cutoff[] = {
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000948 43, /* smallest N such that k == 4 */
949 106, /* etc */
950 250,
951 576,
952 1298,
953 2885,
954 6339,
955 13805,
956 29843,
957 64116,
958 137030,
959 291554,
960 617916,
961 1305130,
962 2748295,
963 5771662,
964 12091672,
965 25276798,
966 52734615,
967 109820537,
968 228324027,
969 473977813,
970 982548444, /* smallest N such that k == 26 */
971 2034159050 /* largest N that fits in signed 32-bit; k == 27 */
972};
973
974static int
Fred Drakea2f55112000-07-09 15:16:51 +0000975samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare)
976 /* compare -- comparison function object, or NULL for default */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +0000977{
978 register PyObject **l, **r;
979 register PyObject *tmp, *pivot;
980 register int k;
981 int n, extra, top, extraOnRight;
982 struct SamplesortStackNode stack[STACKSIZE];
983
984 /* assert lo <= hi */
985 n = hi - lo;
986
987 /* ----------------------------------------------------------
988 * Special cases
989 * --------------------------------------------------------*/
990 if (n < 2)
991 return 0;
992
993 /* Set r to the largest value such that [lo,r) is sorted.
994 This catches the already-sorted case, the all-the-same
995 case, and the appended-a-few-elements-to-a-sorted-list case.
996 If the array is unsorted, we're very likely to get out of
997 the loop fast, so the test is cheap if it doesn't pay off.
998 */
999 /* assert lo < hi */
1000 for (r = lo+1; r < hi; ++r) {
1001 SETK(*r, *(r-1));
1002 if (k < 0)
1003 break;
1004 }
1005 /* [lo,r) is sorted, [r,hi) unknown. Get out cheap if there are
1006 few unknowns, or few elements in total. */
1007 if (hi - r <= MAXMERGE || n < MINSIZE)
Guido van Rossum42812581998-06-17 14:15:44 +00001008 return binarysort(lo, hi, r, compare);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001009
1010 /* Check for the array already being reverse-sorted. Typical
1011 benchmark-driven silliness <wink>. */
1012 /* assert lo < hi */
1013 for (r = lo+1; r < hi; ++r) {
1014 SETK(*(r-1), *r);
1015 if (k < 0)
1016 break;
1017 }
1018 if (hi - r <= MAXMERGE) {
1019 /* Reverse the reversed prefix, then insert the tail */
1020 PyObject **originalr = r;
1021 l = lo;
1022 do {
1023 --r;
1024 tmp = *l; *l = *r; *r = tmp;
1025 ++l;
1026 } while (l < r);
Guido van Rossum42812581998-06-17 14:15:44 +00001027 return binarysort(lo, hi, originalr, compare);
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001028 }
1029
1030 /* ----------------------------------------------------------
1031 * Normal case setup: a large array without obvious pattern.
1032 * --------------------------------------------------------*/
1033
1034 /* extra := a power of 2 ~= n/ln(n), less 1.
1035 First find the smallest extra s.t. n < cutoff[extra] */
1036 for (extra = 0;
1037 extra < sizeof(cutoff) / sizeof(cutoff[0]);
1038 ++extra) {
1039 if (n < cutoff[extra])
1040 break;
1041 /* note that if we fall out of the loop, the value of
1042 extra still makes *sense*, but may be smaller than
1043 we would like (but the array has more than ~= 2**31
1044 elements in this case!) */
1045 }
1046 /* Now k == extra - 1 + CUTOFFBASE. The smallest value k can
1047 have is CUTOFFBASE-1, so
1048 assert MINSIZE >= 2**(CUTOFFBASE-1) - 1 */
1049 extra = (1 << (extra - 1 + CUTOFFBASE)) - 1;
1050 /* assert extra > 0 and n >= extra */
1051
1052 /* Swap that many values to the start of the array. The
1053 selection of elements is pseudo-random, but the same on
1054 every run (this is intentional! timing algorithm changes is
1055 a pain if timing varies across runs). */
1056 {
1057 unsigned int seed = n / extra; /* arbitrary */
1058 unsigned int i;
1059 for (i = 0; i < (unsigned)extra; ++i) {
1060 /* j := random int in [i, n) */
1061 unsigned int j;
1062 seed = seed * 69069 + 7;
1063 j = i + seed % (n - i);
1064 tmp = lo[i]; lo[i] = lo[j]; lo[j] = tmp;
1065 }
1066 }
1067
1068 /* Recursively sort the preselected pivots. */
Guido van Rossum42812581998-06-17 14:15:44 +00001069 if (samplesortslice(lo, lo + extra, compare) < 0)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001070 goto fail;
1071
1072 top = 0; /* index of available stack slot */
1073 lo += extra; /* point to first unknown */
1074 extraOnRight = 0; /* the PPs are at the left end */
1075
1076 /* ----------------------------------------------------------
1077 * Partition [lo, hi), and repeat until out of work.
1078 * --------------------------------------------------------*/
1079 for (;;) {
1080 /* assert lo <= hi, so n >= 0 */
1081 n = hi - lo;
1082
1083 /* We may not want, or may not be able, to partition:
1084 If n is small, it's quicker to insert.
1085 If extra is 0, we're out of pivots, and *must* use
1086 another method.
1087 */
1088 if (n < MINPARTITIONSIZE || extra == 0) {
1089 if (n >= MINSIZE) {
1090 /* assert extra == 0
1091 This is rare, since the average size
1092 of a final block is only about
1093 ln(original n). */
Guido van Rossum42812581998-06-17 14:15:44 +00001094 if (samplesortslice(lo, hi, compare) < 0)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001095 goto fail;
1096 }
1097 else {
1098 /* Binary insertion should be quicker,
1099 and we can take advantage of the PPs
1100 already being sorted. */
1101 if (extraOnRight && extra) {
1102 /* swap the PPs to the left end */
1103 k = extra;
1104 do {
1105 tmp = *lo;
1106 *lo = *hi;
1107 *hi = tmp;
1108 ++lo; ++hi;
1109 } while (--k);
1110 }
1111 if (binarysort(lo - extra, hi, lo,
Guido van Rossum42812581998-06-17 14:15:44 +00001112 compare) < 0)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001113 goto fail;
1114 }
1115
1116 /* Find another slice to work on. */
1117 if (--top < 0)
1118 break; /* no more -- done! */
1119 lo = stack[top].lo;
1120 hi = stack[top].hi;
1121 extra = stack[top].extra;
1122 extraOnRight = 0;
1123 if (extra < 0) {
1124 extraOnRight = 1;
1125 extra = -extra;
1126 }
1127 continue;
1128 }
1129
1130 /* Pretend the PPs are indexed 0, 1, ..., extra-1.
1131 Then our preselected pivot is at (extra-1)/2, and we
1132 want to move the PPs before that to the left end of
1133 the slice, and the PPs after that to the right end.
1134 The following section changes extra, lo, hi, and the
1135 slice such that:
1136 [lo-extra, lo) contains the smaller PPs.
1137 *lo == our PP.
1138 (lo, hi) contains the unknown elements.
1139 [hi, hi+extra) contains the larger PPs.
1140 */
1141 k = extra >>= 1; /* num PPs to move */
1142 if (extraOnRight) {
1143 /* Swap the smaller PPs to the left end.
1144 Note that this loop actually moves k+1 items:
1145 the last is our PP */
1146 do {
1147 tmp = *lo; *lo = *hi; *hi = tmp;
1148 ++lo; ++hi;
1149 } while (k--);
1150 }
1151 else {
1152 /* Swap the larger PPs to the right end. */
1153 while (k--) {
1154 --lo; --hi;
1155 tmp = *lo; *lo = *hi; *hi = tmp;
1156 }
1157 }
1158 --lo; /* *lo is now our PP */
1159 pivot = *lo;
1160
1161 /* Now an almost-ordinary quicksort partition step.
1162 Note that most of the time is spent here!
1163 Only odd thing is that we partition into < and >=,
1164 instead of the usual <= and >=. This helps when
1165 there are lots of duplicates of different values,
1166 because it eventually tends to make subfiles
1167 "pure" (all duplicates), and we special-case for
1168 duplicates later. */
1169 l = lo + 1;
1170 r = hi - 1;
1171 /* assert lo < l < r < hi (small n weeded out above) */
1172
1173 do {
1174 /* slide l right, looking for key >= pivot */
1175 do {
1176 SETK(*l, pivot);
1177 if (k < 0)
1178 ++l;
1179 else
1180 break;
1181 } while (l < r);
1182
1183 /* slide r left, looking for key < pivot */
1184 while (l < r) {
Guido van Rossum42812581998-06-17 14:15:44 +00001185 register PyObject *rval = *r--;
1186 SETK(rval, pivot);
1187 if (k < 0) {
1188 /* swap and advance */
1189 r[1] = *l;
1190 *l++ = rval;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001191 break;
Guido van Rossum42812581998-06-17 14:15:44 +00001192 }
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001193 }
1194
1195 } while (l < r);
1196
1197 /* assert lo < r <= l < hi
1198 assert r == l or r+1 == l
1199 everything to the left of l is < pivot, and
1200 everything to the right of r is >= pivot */
1201
1202 if (l == r) {
1203 SETK(*r, pivot);
1204 if (k < 0)
1205 ++l;
1206 else
1207 --r;
1208 }
1209 /* assert lo <= r and r+1 == l and l <= hi
1210 assert r == lo or a[r] < pivot
1211 assert a[lo] is pivot
1212 assert l == hi or a[l] >= pivot
1213 Swap the pivot into "the middle", so we can henceforth
1214 ignore it.
1215 */
1216 *lo = *r;
1217 *r = pivot;
1218
1219 /* The following is true now, & will be preserved:
1220 All in [lo,r) are < pivot
1221 All in [r,l) == pivot (& so can be ignored)
1222 All in [l,hi) are >= pivot */
1223
1224 /* Check for duplicates of the pivot. One compare is
1225 wasted if there are no duplicates, but can win big
1226 when there are.
1227 Tricky: we're sticking to "<" compares, so deduce
1228 equality indirectly. We know pivot <= *l, so they're
1229 equal iff not pivot < *l.
1230 */
1231 while (l < hi) {
1232 /* pivot <= *l known */
1233 SETK(pivot, *l);
1234 if (k < 0)
1235 break;
1236 else
1237 /* <= and not < implies == */
1238 ++l;
1239 }
1240
1241 /* assert lo <= r < l <= hi
1242 Partitions are [lo, r) and [l, hi) */
1243
1244 /* push fattest first; remember we still have extra PPs
1245 to the left of the left chunk and to the right of
1246 the right chunk! */
1247 /* assert top < STACKSIZE */
1248 if (r - lo <= hi - l) {
1249 /* second is bigger */
1250 stack[top].lo = l;
1251 stack[top].hi = hi;
1252 stack[top].extra = -extra;
1253 hi = r;
1254 extraOnRight = 0;
1255 }
1256 else {
1257 /* first is bigger */
1258 stack[top].lo = lo;
1259 stack[top].hi = r;
1260 stack[top].extra = extra;
1261 lo = l;
1262 extraOnRight = 1;
1263 }
1264 ++top;
1265
1266 } /* end of partitioning loop */
1267
1268 return 0;
1269
1270 fail:
1271 return -1;
1272}
Guido van Rossuma119c0d1998-05-29 17:56:32 +00001273
1274#undef SETK
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001275
1276staticforward PyTypeObject immutable_list_type;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001277
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001278static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00001279listsort(PyListObject *self, PyObject *args)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001280{
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001281 int err;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001282 PyObject *compare = NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +00001283 PyTypeObject *savetype;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001284
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001285 if (args != NULL) {
Guido van Rossumc00a9382000-02-24 21:48:29 +00001286 if (!PyArg_ParseTuple(args, "|O:sort", &compare))
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001287 return NULL;
1288 }
Tim Peters6d6c1a32001-08-02 04:15:00 +00001289 savetype = self->ob_type;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001290 self->ob_type = &immutable_list_type;
1291 err = samplesortslice(self->ob_item,
1292 self->ob_item + self->ob_size,
Guido van Rossum42812581998-06-17 14:15:44 +00001293 compare);
Tim Peters6d6c1a32001-08-02 04:15:00 +00001294 self->ob_type = savetype;
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001295 if (err < 0)
Guido van Rossum3f236de1996-12-10 23:55:39 +00001296 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001297 Py_INCREF(Py_None);
1298 return Py_None;
Guido van Rossum3f236de1996-12-10 23:55:39 +00001299}
1300
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001301int
Fred Drakea2f55112000-07-09 15:16:51 +00001302PyList_Sort(PyObject *v)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001303{
1304 if (v == NULL || !PyList_Check(v)) {
1305 PyErr_BadInternalCall();
1306 return -1;
1307 }
1308 v = listsort((PyListObject *)v, (PyObject *)NULL);
1309 if (v == NULL)
1310 return -1;
1311 Py_DECREF(v);
1312 return 0;
1313}
1314
Guido van Rossumb86c5492001-02-12 22:06:02 +00001315static void
1316_listreverse(PyListObject *self)
Guido van Rossumed98d481991-03-06 13:07:53 +00001317{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001318 register PyObject **p, **q;
1319 register PyObject *tmp;
Guido van Rossumed98d481991-03-06 13:07:53 +00001320
Guido van Rossumed98d481991-03-06 13:07:53 +00001321 if (self->ob_size > 1) {
1322 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
Guido van Rossumb86c5492001-02-12 22:06:02 +00001323 p < q;
1324 p++, q--)
1325 {
Guido van Rossumed98d481991-03-06 13:07:53 +00001326 tmp = *p;
1327 *p = *q;
1328 *q = tmp;
1329 }
1330 }
Guido van Rossumb86c5492001-02-12 22:06:02 +00001331}
1332
1333static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001334listreverse(PyListObject *self)
Guido van Rossumb86c5492001-02-12 22:06:02 +00001335{
Guido van Rossumb86c5492001-02-12 22:06:02 +00001336 _listreverse(self);
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001337 Py_INCREF(Py_None);
1338 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00001339}
1340
Guido van Rossum84c76f51990-10-30 13:32:20 +00001341int
Fred Drakea2f55112000-07-09 15:16:51 +00001342PyList_Reverse(PyObject *v)
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00001343{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001344 if (v == NULL || !PyList_Check(v)) {
1345 PyErr_BadInternalCall();
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00001346 return -1;
1347 }
Guido van Rossumb86c5492001-02-12 22:06:02 +00001348 _listreverse((PyListObject *)v);
Guido van Rossumb0fe3a91995-01-17 16:34:45 +00001349 return 0;
1350}
1351
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001352PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00001353PyList_AsTuple(PyObject *v)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001354{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001355 PyObject *w;
1356 PyObject **p;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001357 int n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001358 if (v == NULL || !PyList_Check(v)) {
1359 PyErr_BadInternalCall();
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001360 return NULL;
1361 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001362 n = ((PyListObject *)v)->ob_size;
1363 w = PyTuple_New(n);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001364 if (w == NULL)
1365 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001366 p = ((PyTupleObject *)w)->ob_item;
Thomas Wouters334fb892000-07-25 12:56:38 +00001367 memcpy((void *)p,
1368 (void *)((PyListObject *)v)->ob_item,
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001369 n*sizeof(PyObject *));
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001370 while (--n >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001371 Py_INCREF(*p);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001372 p++;
1373 }
1374 return w;
1375}
1376
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001377static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001378listindex(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00001379{
1380 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001381
Guido van Rossumed98d481991-03-06 13:07:53 +00001382 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001383 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1384 if (cmp > 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001385 return PyInt_FromLong((long)i);
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001386 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001387 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00001388 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001389 PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00001390 return NULL;
1391}
1392
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001393static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001394listcount(PyListObject *self, PyObject *v)
Guido van Rossume6f7d181991-10-20 20:20:40 +00001395{
1396 int count = 0;
1397 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001398
Guido van Rossume6f7d181991-10-20 20:20:40 +00001399 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001400 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1401 if (cmp > 0)
Guido van Rossume6f7d181991-10-20 20:20:40 +00001402 count++;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001403 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001404 return NULL;
Guido van Rossume6f7d181991-10-20 20:20:40 +00001405 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001406 return PyInt_FromLong((long)count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00001407}
1408
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001409static PyObject *
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001410listremove(PyListObject *self, PyObject *v)
Guido van Rossumed98d481991-03-06 13:07:53 +00001411{
1412 int i;
Guido van Rossum4aa24f92000-02-24 15:23:03 +00001413
Guido van Rossumed98d481991-03-06 13:07:53 +00001414 for (i = 0; i < self->ob_size; i++) {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001415 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1416 if (cmp > 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001417 if (list_ass_slice(self, i, i+1,
1418 (PyObject *)NULL) != 0)
Guido van Rossumed98d481991-03-06 13:07:53 +00001419 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001420 Py_INCREF(Py_None);
1421 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00001422 }
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001423 else if (cmp < 0)
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001424 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00001425 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001426 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00001427 return NULL;
1428}
1429
Jeremy Hylton8caad492000-06-23 14:18:11 +00001430static int
1431list_traverse(PyListObject *o, visitproc visit, void *arg)
1432{
1433 int i, err;
1434 PyObject *x;
1435
1436 for (i = o->ob_size; --i >= 0; ) {
1437 x = o->ob_item[i];
1438 if (x != NULL) {
1439 err = visit(x, arg);
1440 if (err)
1441 return err;
1442 }
1443 }
1444 return 0;
1445}
1446
1447static int
1448list_clear(PyListObject *lp)
1449{
1450 (void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
1451 return 0;
1452}
1453
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001454static PyObject *
1455list_richcompare(PyObject *v, PyObject *w, int op)
1456{
1457 PyListObject *vl, *wl;
1458 int i;
1459
1460 if (!PyList_Check(v) || !PyList_Check(w)) {
1461 Py_INCREF(Py_NotImplemented);
1462 return Py_NotImplemented;
1463 }
1464
1465 vl = (PyListObject *)v;
1466 wl = (PyListObject *)w;
1467
1468 if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
1469 /* Shortcut: if the lengths differ, the lists differ */
1470 PyObject *res;
1471 if (op == Py_EQ)
1472 res = Py_False;
1473 else
1474 res = Py_True;
1475 Py_INCREF(res);
1476 return res;
1477 }
1478
1479 /* Search for the first index where items are different */
1480 for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
1481 int k = PyObject_RichCompareBool(vl->ob_item[i],
1482 wl->ob_item[i], Py_EQ);
1483 if (k < 0)
1484 return NULL;
1485 if (!k)
1486 break;
1487 }
1488
1489 if (i >= vl->ob_size || i >= wl->ob_size) {
1490 /* No more items to compare -- compare sizes */
1491 int vs = vl->ob_size;
1492 int ws = wl->ob_size;
1493 int cmp;
1494 PyObject *res;
1495 switch (op) {
1496 case Py_LT: cmp = vs < ws; break;
Tim Peters6ee42342001-07-06 17:45:43 +00001497 case Py_LE: cmp = vs <= ws; break;
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001498 case Py_EQ: cmp = vs == ws; break;
1499 case Py_NE: cmp = vs != ws; break;
1500 case Py_GT: cmp = vs > ws; break;
1501 case Py_GE: cmp = vs >= ws; break;
1502 default: return NULL; /* cannot happen */
1503 }
1504 if (cmp)
1505 res = Py_True;
1506 else
1507 res = Py_False;
1508 Py_INCREF(res);
1509 return res;
1510 }
1511
1512 /* We have an item that differs -- shortcuts for EQ/NE */
1513 if (op == Py_EQ) {
1514 Py_INCREF(Py_False);
1515 return Py_False;
1516 }
1517 if (op == Py_NE) {
1518 Py_INCREF(Py_True);
1519 return Py_True;
1520 }
1521
1522 /* Compare the final item again using the proper operator */
1523 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
1524}
1525
Tim Peters6d6c1a32001-08-02 04:15:00 +00001526/* Adapted from newer code by Tim */
1527static int
1528list_fill(PyListObject *result, PyObject *v)
1529{
1530 PyObject *it; /* iter(v) */
1531 int n; /* guess for result list size */
1532 int i;
1533
1534 n = result->ob_size;
1535
1536 /* Special-case list(a_list), for speed. */
1537 if (PyList_Check(v)) {
1538 if (v == (PyObject *)result)
1539 return 0; /* source is destination, we're done */
1540 return list_ass_slice(result, 0, n, v);
1541 }
1542
1543 /* Empty previous contents */
1544 if (n != 0) {
1545 if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
1546 return -1;
1547 }
1548
1549 /* Get iterator. There may be some low-level efficiency to be gained
1550 * by caching the tp_iternext slot instead of using PyIter_Next()
1551 * later, but premature optimization is the root etc.
1552 */
1553 it = PyObject_GetIter(v);
1554 if (it == NULL)
1555 return -1;
1556
1557 /* Guess a result list size. */
1558 n = -1; /* unknown */
1559 if (PySequence_Check(v) &&
1560 v->ob_type->tp_as_sequence->sq_length) {
1561 n = PySequence_Size(v);
1562 if (n < 0)
1563 PyErr_Clear();
1564 }
1565 if (n < 0)
1566 n = 8; /* arbitrary */
1567 NRESIZE(result->ob_item, PyObject*, n);
1568 if (result->ob_item == NULL)
1569 goto error;
1570 for (i = 0; i < n; i++)
1571 result->ob_item[i] = NULL;
1572 result->ob_size = n;
1573
1574 /* Run iterator to exhaustion. */
1575 for (i = 0; ; i++) {
1576 PyObject *item = PyIter_Next(it);
1577 if (item == NULL) {
1578 if (PyErr_Occurred())
1579 goto error;
1580 break;
1581 }
1582 if (i < n)
1583 PyList_SET_ITEM(result, i, item); /* steals ref */
1584 else {
1585 int status = ins1(result, result->ob_size, item);
1586 Py_DECREF(item); /* append creates a new ref */
1587 if (status < 0)
1588 goto error;
1589 }
1590 }
1591
1592 /* Cut back result list if initial guess was too large. */
1593 if (i < n && result != NULL) {
1594 if (list_ass_slice(result, i, n, (PyObject *)NULL) != 0)
1595 goto error;
1596 }
1597 Py_DECREF(it);
1598 return 0;
1599
1600 error:
1601 Py_DECREF(it);
1602 return -1;
1603}
1604
1605static int
1606list_init(PyListObject *self, PyObject *args, PyObject *kw)
1607{
1608 PyObject *arg = NULL;
1609 static char *kwlist[] = {"sequence", 0};
1610
1611 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
1612 return -1;
1613 if (arg != NULL)
1614 return list_fill(self, arg);
1615 if (self->ob_size > 0)
1616 return list_ass_slice(self, 0, self->ob_size, (PyObject*)NULL);
1617 return 0;
1618}
1619
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00001620static char append_doc[] =
1621"L.append(object) -- append object to end";
Barry Warsawdedf6d61998-10-09 16:37:25 +00001622static char extend_doc[] =
1623"L.extend(list) -- extend list by appending list elements";
Guido van Rossum3dd7f3f1998-06-30 15:36:32 +00001624static char insert_doc[] =
1625"L.insert(index, object) -- insert object before index";
1626static char pop_doc[] =
1627"L.pop([index]) -> item -- remove and return item at index (default last)";
1628static char remove_doc[] =
1629"L.remove(value) -- remove first occurrence of value";
1630static char index_doc[] =
1631"L.index(value) -> integer -- return index of first occurrence of value";
1632static char count_doc[] =
1633"L.count(value) -> integer -- return number of occurrences of value";
1634static char reverse_doc[] =
1635"L.reverse() -- reverse *IN PLACE*";
1636static char sort_doc[] =
1637"L.sort([cmpfunc]) -- sort *IN PLACE*; if given, cmpfunc(x, y) -> -1, 0, 1";
1638
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001639static PyMethodDef list_methods[] = {
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001640 {"append", (PyCFunction)listappend, METH_O, append_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001641 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001642 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001643 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001644 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
1645 {"index", (PyCFunction)listindex, METH_O, index_doc},
1646 {"count", (PyCFunction)listcount, METH_O, count_doc},
1647 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001648 {"sort", (PyCFunction)listsort, METH_VARARGS, sort_doc},
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001649 {NULL, NULL} /* sentinel */
1650};
1651
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001652static PySequenceMethods list_as_sequence = {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001653 (inquiry)list_length, /* sq_length */
1654 (binaryfunc)list_concat, /* sq_concat */
1655 (intargfunc)list_repeat, /* sq_repeat */
1656 (intargfunc)list_item, /* sq_item */
1657 (intintargfunc)list_slice, /* sq_slice */
1658 (intobjargproc)list_ass_item, /* sq_ass_item */
1659 (intintobjargproc)list_ass_slice, /* sq_ass_slice */
1660 (objobjproc)list_contains, /* sq_contains */
1661 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
1662 (intargfunc)list_inplace_repeat, /* sq_inplace_repeat */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001663};
1664
Tim Peters6d6c1a32001-08-02 04:15:00 +00001665static char list_doc[] =
1666"list() -> new list\n"
1667"list(sequence) -> new list initialized from sequence's items";
1668
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001669PyTypeObject PyList_Type = {
1670 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001671 0,
1672 "list",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00001673 sizeof(PyListObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001674 0,
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001675 (destructor)list_dealloc, /* tp_dealloc */
1676 (printfunc)list_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001677 0, /* tp_getattr */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001678 0, /* tp_setattr */
1679 0, /* tp_compare */
1680 (reprfunc)list_repr, /* tp_repr */
1681 0, /* tp_as_number */
1682 &list_as_sequence, /* tp_as_sequence */
1683 0, /* tp_as_mapping */
1684 0, /* tp_hash */
1685 0, /* tp_call */
1686 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001687 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001688 0, /* tp_setattro */
1689 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00001690 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Tim Peters6d6c1a32001-08-02 04:15:00 +00001691 Py_TPFLAGS_BASETYPE, /* tp_flags */
1692 list_doc, /* tp_doc */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001693 (traverseproc)list_traverse, /* tp_traverse */
1694 (inquiry)list_clear, /* tp_clear */
1695 list_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001696 0, /* tp_weaklistoffset */
1697 0, /* tp_iter */
1698 0, /* tp_iternext */
1699 list_methods, /* tp_methods */
1700 0, /* tp_members */
1701 0, /* tp_getset */
1702 0, /* tp_base */
1703 0, /* tp_dict */
1704 0, /* tp_descr_get */
1705 0, /* tp_descr_set */
1706 0, /* tp_dictoffset */
1707 (initproc)list_init, /* tp_init */
1708 PyType_GenericAlloc, /* tp_alloc */
1709 PyType_GenericNew, /* tp_new */
Guido van Rossum9475a232001-10-05 20:51:39 +00001710 _PyObject_GC_Del, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001711};
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001712
1713
1714/* During a sort, we really can't have anyone modifying the list; it could
1715 cause core dumps. Thus, we substitute a dummy type that raises an
1716 explanatory exception when a modifying operation is used. Caveat:
1717 comparisons may behave differently; but I guess it's a bad idea anyway to
1718 compare a list that's being sorted... */
1719
1720static PyObject *
Fred Drakea2f55112000-07-09 15:16:51 +00001721immutable_list_op(void)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001722{
1723 PyErr_SetString(PyExc_TypeError,
1724 "a list cannot be modified while it is being sorted");
1725 return NULL;
1726}
1727
1728static PyMethodDef immutable_list_methods[] = {
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001729 {"append", (PyCFunction)immutable_list_op, METH_VARARGS},
1730 {"insert", (PyCFunction)immutable_list_op, METH_VARARGS},
Tim Peters52e07172001-08-30 06:15:32 +00001731 {"extend", (PyCFunction)immutable_list_op, METH_O},
1732 {"pop", (PyCFunction)immutable_list_op, METH_VARARGS},
Martin v. Löwise3eb1f22001-08-16 13:15:00 +00001733 {"remove", (PyCFunction)immutable_list_op, METH_VARARGS},
1734 {"index", (PyCFunction)listindex, METH_O},
1735 {"count", (PyCFunction)listcount, METH_O},
1736 {"reverse", (PyCFunction)immutable_list_op, METH_VARARGS},
1737 {"sort", (PyCFunction)immutable_list_op, METH_VARARGS},
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001738 {NULL, NULL} /* sentinel */
1739};
1740
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001741static int
Fred Drakea2f55112000-07-09 15:16:51 +00001742immutable_list_ass(void)
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001743{
1744 immutable_list_op();
1745 return -1;
1746}
1747
1748static PySequenceMethods immutable_list_as_sequence = {
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001749 (inquiry)list_length, /* sq_length */
1750 (binaryfunc)list_concat, /* sq_concat */
1751 (intargfunc)list_repeat, /* sq_repeat */
1752 (intargfunc)list_item, /* sq_item */
1753 (intintargfunc)list_slice, /* sq_slice */
1754 (intobjargproc)immutable_list_ass, /* sq_ass_item */
1755 (intintobjargproc)immutable_list_ass, /* sq_ass_slice */
1756 (objobjproc)list_contains, /* sq_contains */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001757};
1758
1759static PyTypeObject immutable_list_type = {
1760 PyObject_HEAD_INIT(&PyType_Type)
1761 0,
1762 "list (immutable, during sort)",
Neil Schemenauere83c00e2001-08-29 23:54:21 +00001763 sizeof(PyListObject),
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001764 0,
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001765 0, /* Cannot happen */ /* tp_dealloc */
1766 (printfunc)list_print, /* tp_print */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001767 0, /* tp_getattr */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001768 0, /* tp_setattr */
1769 0, /* Won't be called */ /* tp_compare */
1770 (reprfunc)list_repr, /* tp_repr */
1771 0, /* tp_as_number */
1772 &immutable_list_as_sequence, /* tp_as_sequence */
1773 0, /* tp_as_mapping */
1774 0, /* tp_hash */
1775 0, /* tp_call */
1776 0, /* tp_str */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001777 PyObject_GenericGetAttr, /* tp_getattro */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001778 0, /* tp_setattro */
1779 0, /* tp_as_buffer */
Neil Schemenauere83c00e2001-08-29 23:54:21 +00001780 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001781 list_doc, /* tp_doc */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001782 (traverseproc)list_traverse, /* tp_traverse */
1783 0, /* tp_clear */
1784 list_richcompare, /* tp_richcompare */
Tim Peters6d6c1a32001-08-02 04:15:00 +00001785 0, /* tp_weaklistoffset */
1786 0, /* tp_iter */
1787 0, /* tp_iternext */
1788 immutable_list_methods, /* tp_methods */
1789 0, /* tp_members */
1790 0, /* tp_getset */
1791 0, /* tp_base */
1792 0, /* tp_dict */
1793 0, /* tp_descr_get */
1794 0, /* tp_descr_set */
1795 0, /* tp_init */
Guido van Rossum65e1cea2001-01-17 22:11:59 +00001796 /* NOTE: This is *not* the standard list_type struct! */
Guido van Rossum4c4e7df1998-06-16 15:18:28 +00001797};