blob: 8bec8afc7072af2ac366d5a80509d1909d5b89ff [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001/***********************************************************
Guido van Rossum6610ad91995-01-04 19:07:38 +00002Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
3The Netherlands.
Guido van Rossumf70e43a1991-02-19 12:39:46 +00004
5 All Rights Reserved
6
Guido van Rossumd266eb41996-10-25 14:44:06 +00007Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
Guido van Rossumf70e43a1991-02-19 12:39:46 +00009provided that the above copyright notice appear in all copies and that
Guido van Rossumd266eb41996-10-25 14:44:06 +000010both that copyright notice and this permission notice appear in
Guido van Rossumf70e43a1991-02-19 12:39:46 +000011supporting documentation, and that the names of Stichting Mathematisch
Guido van Rossumd266eb41996-10-25 14:44:06 +000012Centrum or CWI or Corporation for National Research Initiatives or
13CNRI not be used in advertising or publicity pertaining to
14distribution of the software without specific, written prior
15permission.
Guido van Rossumf70e43a1991-02-19 12:39:46 +000016
Guido van Rossumd266eb41996-10-25 14:44:06 +000017While CWI is the initial source for this software, a modified version
18is made available by the Corporation for National Research Initiatives
19(CNRI) at the Internet address ftp://ftp.python.org.
20
21STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
22REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
23MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
24CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
25DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
26PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
27TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
28PERFORMANCE OF THIS SOFTWARE.
Guido van Rossumf70e43a1991-02-19 12:39:46 +000029
30******************************************************************/
31
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000032/* List object implementation */
33
Guido van Rossumc0b618a1997-05-02 03:12:38 +000034#include "Python.h"
35
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000036#ifdef STDC_HEADERS
37#include <stddef.h>
38#else
39#include <sys/types.h> /* For size_t */
40#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000041
Guido van Rossumc0b618a1997-05-02 03:12:38 +000042#define ROUNDUP(n, PyTryBlock) \
43 ((((n)+(PyTryBlock)-1)/(PyTryBlock))*(PyTryBlock))
Guido van Rossuma46d51d1995-01-26 22:59:43 +000044
45static int
Guido van Rossuma27d1121997-08-25 18:36:23 +000046roundupsize(n)
Guido van Rossuma46d51d1995-01-26 22:59:43 +000047 int n;
48{
49 if (n < 500)
50 return ROUNDUP(n, 10);
51 else
52 return ROUNDUP(n, 100);
53}
54
Guido van Rossuma27d1121997-08-25 18:36:23 +000055#define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))
Guido van Rossuma46d51d1995-01-26 22:59:43 +000056
Guido van Rossumc0b618a1997-05-02 03:12:38 +000057PyObject *
58PyList_New(size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000059 int size;
60{
61 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +000062 PyListObject *op;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +000063 size_t nbytes;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000064 if (size < 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000065 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000066 return NULL;
67 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +000068 nbytes = size * sizeof(PyObject *);
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000069 /* Check for overflow */
Guido van Rossumc0b618a1997-05-02 03:12:38 +000070 if (nbytes / sizeof(PyObject *) != (size_t)size) {
71 return PyErr_NoMemory();
Guido van Rossum1e28e5e1992-08-19 16:46:30 +000072 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +000073 op = (PyListObject *) malloc(sizeof(PyListObject));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000074 if (op == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000075 return PyErr_NoMemory();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000076 }
77 if (size <= 0) {
78 op->ob_item = NULL;
79 }
80 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +000081 op->ob_item = (PyObject **) malloc(nbytes);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000082 if (op->ob_item == NULL) {
83 free((ANY *)op);
Guido van Rossumc0b618a1997-05-02 03:12:38 +000084 return PyErr_NoMemory();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000085 }
86 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +000087 op->ob_type = &PyList_Type;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000088 op->ob_size = size;
89 for (i = 0; i < size; i++)
90 op->ob_item[i] = NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +000091 _Py_NewReference(op);
92 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000093}
94
95int
Guido van Rossumc0b618a1997-05-02 03:12:38 +000096PyList_Size(op)
97 PyObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000098{
Guido van Rossumc0b618a1997-05-02 03:12:38 +000099 if (!PyList_Check(op)) {
100 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000101 return -1;
102 }
103 else
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000104 return ((PyListObject *)op) -> ob_size;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000105}
106
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000107static PyObject *indexerr;
Guido van Rossum929f1b81996-08-09 20:51:27 +0000108
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000109PyObject *
110PyList_GetItem(op, i)
111 PyObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000112 int i;
113{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000114 if (!PyList_Check(op)) {
115 PyErr_BadInternalCall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000116 return NULL;
117 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000118 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000119 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000120 indexerr = PyString_FromString(
121 "list index out of range");
122 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000123 return NULL;
124 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000125 return ((PyListObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000126}
127
128int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000129PyList_SetItem(op, i, newitem)
130 register PyObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000131 register int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000132 register PyObject *newitem;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000133{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000134 register PyObject *olditem;
135 register PyObject **p;
136 if (!PyList_Check(op)) {
137 Py_XDECREF(newitem);
138 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000139 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000140 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000141 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
142 Py_XDECREF(newitem);
143 PyErr_SetString(PyExc_IndexError,
144 "list assignment index out of range");
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000145 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000146 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000147 p = ((PyListObject *)op) -> ob_item + i;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000148 olditem = *p;
149 *p = newitem;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000150 Py_XDECREF(olditem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000151 return 0;
152}
153
154static int
155ins1(self, where, v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000156 PyListObject *self;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000157 int where;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000158 PyObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000159{
160 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000161 PyObject **items;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000162 if (v == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000163 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000164 return -1;
165 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000166 items = self->ob_item;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000167 NRESIZE(items, PyObject *, self->ob_size+1);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000168 if (items == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000169 PyErr_NoMemory();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000170 return -1;
171 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000172 if (where < 0)
173 where = 0;
174 if (where > self->ob_size)
175 where = self->ob_size;
176 for (i = self->ob_size; --i >= where; )
177 items[i+1] = items[i];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000178 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000179 items[where] = v;
180 self->ob_item = items;
181 self->ob_size++;
182 return 0;
183}
184
185int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000186PyList_Insert(op, where, newitem)
187 PyObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000188 int where;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000189 PyObject *newitem;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000190{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000191 if (!PyList_Check(op)) {
192 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000193 return -1;
194 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000195 return ins1((PyListObject *)op, where, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000196}
197
198int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000199PyList_Append(op, newitem)
200 PyObject *op;
201 PyObject *newitem;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000202{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000203 if (!PyList_Check(op)) {
204 PyErr_BadInternalCall();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000205 return -1;
206 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000207 return ins1((PyListObject *)op,
208 (int) ((PyListObject *)op)->ob_size, newitem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000209}
210
211/* Methods */
212
213static void
214list_dealloc(op)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000215 PyListObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000216{
217 int i;
Jack Jansen7874d1f1995-01-19 12:09:27 +0000218 if (op->ob_item != NULL) {
219 for (i = 0; i < op->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000220 Py_XDECREF(op->ob_item[i]);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000221 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000222 free((ANY *)op->ob_item);
Jack Jansen7874d1f1995-01-19 12:09:27 +0000223 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000224 free((ANY *)op);
225}
226
Guido van Rossum90933611991-06-07 16:10:43 +0000227static int
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000228list_print(op, fp, flags)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000229 PyListObject *op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000230 FILE *fp;
231 int flags;
232{
233 int i;
234 fprintf(fp, "[");
Guido van Rossum90933611991-06-07 16:10:43 +0000235 for (i = 0; i < op->ob_size; i++) {
236 if (i > 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000237 fprintf(fp, ", ");
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000238 if (PyObject_Print(op->ob_item[i], fp, 0) != 0)
Guido van Rossum90933611991-06-07 16:10:43 +0000239 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000240 }
241 fprintf(fp, "]");
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 *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000246list_repr(v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000247 PyListObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000248{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000249 PyObject *s, *comma;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000250 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000251 s = PyString_FromString("[");
252 comma = PyString_FromString(", ");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000253 for (i = 0; i < v->ob_size && s != NULL; i++) {
254 if (i > 0)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000255 PyString_Concat(&s, comma);
256 PyString_ConcatAndDel(&s, PyObject_Repr(v->ob_item[i]));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000257 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000258 Py_XDECREF(comma);
259 PyString_ConcatAndDel(&s, PyString_FromString("]"));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000260 return s;
261}
262
263static int
264list_compare(v, w)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000265 PyListObject *v, *w;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000266{
267 int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
268 int i;
269 for (i = 0; i < len; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000270 int cmp = PyObject_Compare(v->ob_item[i], w->ob_item[i]);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000271 if (cmp != 0)
272 return cmp;
273 }
274 return v->ob_size - w->ob_size;
275}
276
277static int
278list_length(a)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000279 PyListObject *a;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000280{
281 return a->ob_size;
282}
283
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000284static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000285list_item(a, i)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000286 PyListObject *a;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000287 int i;
288{
289 if (i < 0 || i >= a->ob_size) {
Guido van Rossum929f1b81996-08-09 20:51:27 +0000290 if (indexerr == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000291 indexerr = PyString_FromString(
292 "list index out of range");
293 PyErr_SetObject(PyExc_IndexError, indexerr);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000294 return NULL;
295 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000296 Py_INCREF(a->ob_item[i]);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000297 return a->ob_item[i];
298}
299
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000300static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000301list_slice(a, ilow, ihigh)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000302 PyListObject *a;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000303 int ilow, ihigh;
304{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000305 PyListObject *np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000306 int i;
307 if (ilow < 0)
308 ilow = 0;
309 else if (ilow > a->ob_size)
310 ilow = a->ob_size;
311 if (ihigh < 0)
312 ihigh = 0;
313 if (ihigh < ilow)
314 ihigh = ilow;
315 else if (ihigh > a->ob_size)
316 ihigh = a->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000317 np = (PyListObject *) PyList_New(ihigh - ilow);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000318 if (np == NULL)
319 return NULL;
320 for (i = ilow; i < ihigh; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000321 PyObject *v = a->ob_item[i];
322 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000323 np->ob_item[i - ilow] = v;
324 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000325 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000326}
327
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000328PyObject *
329PyList_GetSlice(a, ilow, ihigh)
330 PyObject *a;
Guido van Rossum234f9421993-06-17 12:35:49 +0000331 int ilow, ihigh;
332{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000333 if (!PyList_Check(a)) {
334 PyErr_BadInternalCall();
Guido van Rossum234f9421993-06-17 12:35:49 +0000335 return NULL;
336 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000337 return list_slice((PyListObject *)a, ilow, ihigh);
Guido van Rossum234f9421993-06-17 12:35:49 +0000338}
339
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000340static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000341list_concat(a, bb)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000342 PyListObject *a;
343 PyObject *bb;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000344{
345 int size;
346 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000347 PyListObject *np;
348 if (!PyList_Check(bb)) {
349 PyErr_BadArgument();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000350 return NULL;
351 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000352#define b ((PyListObject *)bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000353 size = a->ob_size + b->ob_size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000354 np = (PyListObject *) PyList_New(size);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000355 if (np == NULL) {
Guido van Rossum90933611991-06-07 16:10:43 +0000356 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000357 }
358 for (i = 0; i < a->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000359 PyObject *v = a->ob_item[i];
360 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000361 np->ob_item[i] = v;
362 }
363 for (i = 0; i < b->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000364 PyObject *v = b->ob_item[i];
365 Py_INCREF(v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000366 np->ob_item[i + a->ob_size] = v;
367 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000368 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000369#undef b
370}
371
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000372static PyObject *
Guido van Rossumed98d481991-03-06 13:07:53 +0000373list_repeat(a, n)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000374 PyListObject *a;
Guido van Rossumed98d481991-03-06 13:07:53 +0000375 int n;
376{
377 int i, j;
378 int size;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000379 PyListObject *np;
380 PyObject **p;
Guido van Rossumed98d481991-03-06 13:07:53 +0000381 if (n < 0)
382 n = 0;
383 size = a->ob_size * n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000384 np = (PyListObject *) PyList_New(size);
Guido van Rossumed98d481991-03-06 13:07:53 +0000385 if (np == NULL)
386 return NULL;
387 p = np->ob_item;
388 for (i = 0; i < n; i++) {
389 for (j = 0; j < a->ob_size; j++) {
390 *p = a->ob_item[j];
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000391 Py_INCREF(*p);
Guido van Rossumed98d481991-03-06 13:07:53 +0000392 p++;
393 }
394 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000395 return (PyObject *) np;
Guido van Rossumed98d481991-03-06 13:07:53 +0000396}
397
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000398static int
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000399list_ass_slice(a, ilow, ihigh, v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000400 PyListObject *a;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000401 int ilow, ihigh;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000402 PyObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000403{
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000404 /* Because [X]DECREF can recursively invoke list operations on
405 this list, we must postpone all [X]DECREF activity until
406 after the list is back in its canonical shape. Therefore
407 we must allocate an additional array, 'recycle', into which
408 we temporarily copy the items that are deleted from the
409 list. :-( */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000410 PyObject **recycle, **p;
411 PyObject **item;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000412 int n; /* Size of replacement list */
413 int d; /* Change in size */
414 int k; /* Loop index */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000415#define b ((PyListObject *)v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000416 if (v == NULL)
417 n = 0;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000418 else if (PyList_Check(v)) {
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000419 n = b->ob_size;
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000420 if (a == b) {
421 /* Special case "a[i:j] = a" -- copy b first */
422 int ret;
423 v = list_slice(b, 0, n);
424 ret = list_ass_slice(a, ilow, ihigh, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000425 Py_DECREF(v);
Guido van Rossum32dffaa1991-12-24 13:27:34 +0000426 return ret;
427 }
428 }
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000429 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000430 PyErr_BadArgument();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000431 return -1;
432 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000433 if (ilow < 0)
434 ilow = 0;
435 else if (ilow > a->ob_size)
436 ilow = a->ob_size;
437 if (ihigh < 0)
438 ihigh = 0;
439 if (ihigh < ilow)
440 ihigh = ilow;
441 else if (ihigh > a->ob_size)
442 ihigh = a->ob_size;
443 item = a->ob_item;
444 d = n - (ihigh-ilow);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000445 if (ihigh > ilow)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000446 p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000447 else
448 p = recycle = NULL;
449 if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000450 for (k = ilow; k < ihigh; k++)
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000451 *p++ = item[k];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000452 if (d < 0) {
453 for (/*k = ihigh*/; k < a->ob_size; k++)
454 item[k+d] = item[k];
455 a->ob_size += d;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000456 NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000457 a->ob_item = item;
458 }
459 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000460 else { /* Insert d items; recycle ihigh-ilow items */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000461 NRESIZE(item, PyObject *, a->ob_size + d);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000462 if (item == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000463 PyMem_XDEL(recycle);
464 PyErr_NoMemory();
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000465 return -1;
466 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000467 for (k = a->ob_size; --k >= ihigh; )
468 item[k+d] = item[k];
469 for (/*k = ihigh-1*/; k >= ilow; --k)
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000470 *p++ = item[k];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000471 a->ob_item = item;
472 a->ob_size += d;
473 }
474 for (k = 0; k < n; k++, ilow++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000475 PyObject *w = b->ob_item[k];
476 Py_XINCREF(w);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000477 item[ilow] = w;
478 }
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000479 if (recycle) {
480 while (--p >= recycle)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000481 Py_XDECREF(*p);
482 PyMem_DEL(recycle);
Guido van Rossumae7bf1a1995-01-17 10:21:11 +0000483 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000484 return 0;
485#undef b
486}
487
Guido van Rossum234f9421993-06-17 12:35:49 +0000488int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000489PyList_SetSlice(a, ilow, ihigh, v)
490 PyObject *a;
Guido van Rossum234f9421993-06-17 12:35:49 +0000491 int ilow, ihigh;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000492 PyObject *v;
Guido van Rossum234f9421993-06-17 12:35:49 +0000493{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000494 if (!PyList_Check(a)) {
495 PyErr_BadInternalCall();
Guido van Rossum1fc238a1993-07-29 08:25:09 +0000496 return -1;
Guido van Rossum234f9421993-06-17 12:35:49 +0000497 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000498 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
Guido van Rossum234f9421993-06-17 12:35:49 +0000499}
500
Guido van Rossum4a450d01991-04-03 19:05:18 +0000501static int
502list_ass_item(a, i, v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000503 PyListObject *a;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000504 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000505 PyObject *v;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000506{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000507 PyObject *old_value;
Guido van Rossum4a450d01991-04-03 19:05:18 +0000508 if (i < 0 || i >= a->ob_size) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000509 PyErr_SetString(PyExc_IndexError,
510 "list assignment index out of range");
Guido van Rossum4a450d01991-04-03 19:05:18 +0000511 return -1;
512 }
513 if (v == NULL)
514 return list_ass_slice(a, i, i+1, v);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000515 Py_INCREF(v);
Guido van Rossumd7047b31995-01-02 19:07:15 +0000516 old_value = a->ob_item[i];
Guido van Rossum4a450d01991-04-03 19:05:18 +0000517 a->ob_item[i] = v;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000518 Py_DECREF(old_value);
Guido van Rossum4a450d01991-04-03 19:05:18 +0000519 return 0;
520}
521
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000522static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000523ins(self, where, v)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000524 PyListObject *self;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000525 int where;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000526 PyObject *v;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000527{
528 if (ins1(self, where, v) != 0)
529 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000530 Py_INCREF(Py_None);
531 return Py_None;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000532}
533
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000534static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000535listinsert(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000536 PyListObject *self;
537 PyObject *args;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000538{
539 int i;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000540 PyObject *v;
541 if (!PyArg_Parse(args, "(iO)", &i, &v))
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000542 return NULL;
Guido van Rossumbf80e541993-02-08 15:49:17 +0000543 return ins(self, i, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000544}
545
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000546static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000547listappend(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000548 PyListObject *self;
549 PyObject *args;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000550{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000551 PyObject *v;
552 if (!PyArg_Parse(args, "O", &v))
Guido van Rossumbf80e541993-02-08 15:49:17 +0000553 return NULL;
554 return ins(self, (int) self->ob_size, v);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000555}
556
Guido van Rossum3f236de1996-12-10 23:55:39 +0000557#define NEWSORT
558
559#ifdef NEWSORT
560
561/* New quicksort implementation for arrays of object pointers.
562 Thanks to discussions with Tim Peters. */
563
564/* CMPERROR is returned by our comparison function when an error
565 occurred. This is the largest negative integer (0x80000000 on a
566 32-bit system). */
Guido van Rossum19700b61997-03-05 00:45:43 +0000567#define CMPERROR ( (int) ((unsigned int)1 << (8*sizeof(int) - 1)) )
Guido van Rossum3f236de1996-12-10 23:55:39 +0000568
569/* Comparison function. Takes care of calling a user-supplied
570 comparison function (any callable Python object). Calls the
571 standard comparison function, cmpobject(), if the user-supplied
572 function is NULL. */
573
574static int
575docompare(x, y, compare)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000576 PyObject *x;
577 PyObject *y;
578 PyObject *compare;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000579{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000580 PyObject *args, *res;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000581 int i;
582
Guido van Rossumc8b6df91997-05-23 00:06:51 +0000583 if (compare == NULL) {
584 i = PyObject_Compare(x, y);
585 if (i && PyErr_Occurred())
586 i = CMPERROR;
587 return i;
588 }
Guido van Rossum3f236de1996-12-10 23:55:39 +0000589
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000590 args = Py_BuildValue("(OO)", x, y);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000591 if (args == NULL)
592 return CMPERROR;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000593 res = PyEval_CallObject(compare, args);
594 Py_DECREF(args);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000595 if (res == NULL)
596 return CMPERROR;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000597 if (!PyInt_Check(res)) {
598 Py_DECREF(res);
599 PyErr_SetString(PyExc_TypeError,
600 "comparison function should return int");
Guido van Rossum3f236de1996-12-10 23:55:39 +0000601 return CMPERROR;
602 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000603 i = PyInt_AsLong(res);
604 Py_DECREF(res);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000605 if (i < 0)
606 return -1;
607 if (i > 0)
608 return 1;
609 return 0;
610}
611
612/* Straight insertion sort. More efficient for sorting small arrays. */
613
614static int
615insertionsort(array, size, compare)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000616 PyObject **array; /* Start of array to sort */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000617 int size; /* Number of elements to sort */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000618 PyObject *compare;/* Comparison function object, or NULL for default */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000619{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000620 register PyObject **a = array;
621 register PyObject **end = array+size;
622 register PyObject **p;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000623
Guido van Rossum3176bb11996-12-11 23:57:39 +0000624 for (p = a+1; p < end; p++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000625 register PyObject *key = *p;
626 register PyObject **q = p;
Guido van Rossum3176bb11996-12-11 23:57:39 +0000627 while (--q >= a) {
628 register int k = docompare(*q, key, compare);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000629 if (k == CMPERROR)
630 return -1;
631 if (k <= 0)
632 break;
Guido van Rossum3176bb11996-12-11 23:57:39 +0000633 *(q+1) = *q;
634 *q = key; /* For consistency */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000635 }
636 }
637
638 return 0;
639}
640
641/* MINSIZE is the smallest array we care to partition; smaller arrays
Guido van Rossumcc15b421996-12-16 03:32:39 +0000642 are sorted using a straight insertion sort (above). It must be at
643 least 2 for the quicksort implementation to work. Assuming that
644 comparisons are more expensive than everything else (and this is a
645 good assumption for Python), it should be 10, which is the cutoff
646 point: quicksort requires more comparisons than insertion sort for
647 smaller arrays. */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000648#define MINSIZE 10
649
650/* STACKSIZE is the size of our work stack. A rough estimate is that
651 this allows us to sort arrays of MINSIZE * 2**STACKSIZE, or large
652 enough. (Because of the way we push the biggest partition first,
653 the worst case occurs when all subarrays are always partitioned
654 exactly in two.) */
655#define STACKSIZE 64
656
657/* Quicksort algorithm. Return -1 if an exception occurred; in this
658 case we leave the array partly sorted but otherwise in good health
659 (i.e. no items have been removed or duplicated). */
660
661static int
662quicksort(array, size, compare)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000663 PyObject **array; /* Start of array to sort */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000664 int size; /* Number of elements to sort */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000665 PyObject *compare;/* Comparison function object, or NULL for default */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000666{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000667 register PyObject *tmp, *pivot;
668 register PyObject **lo, **hi, **l, **r;
Guido van Rossum3176bb11996-12-11 23:57:39 +0000669 int top, k, n, n2;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000670 PyObject **lostack[STACKSIZE];
671 PyObject **histack[STACKSIZE];
Guido van Rossum3f236de1996-12-10 23:55:39 +0000672
673 /* Start out with the whole array on the work stack */
Guido van Rossum3176bb11996-12-11 23:57:39 +0000674 lostack[0] = array;
675 histack[0] = array+size;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000676 top = 1;
677
678 /* Repeat until the work stack is empty */
679 while (--top >= 0) {
Guido van Rossum3176bb11996-12-11 23:57:39 +0000680 lo = lostack[top];
681 hi = histack[top];
Guido van Rossum3f236de1996-12-10 23:55:39 +0000682
683 /* If it's a small one, use straight insertion sort */
Guido van Rossum3176bb11996-12-11 23:57:39 +0000684 n = hi - lo;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000685 if (n < MINSIZE) {
Guido van Rossum24e62e21997-12-10 15:14:24 +0000686 /*
687 * skip it. The insertion sort at the end will
688 * catch these
689 */
Guido van Rossum3f236de1996-12-10 23:55:39 +0000690 continue;
691 }
692
Guido van Rossum3176bb11996-12-11 23:57:39 +0000693 /* Choose median of first, middle and last item as pivot */
694
695 l = lo + (n>>1); /* Middle */
696 r = hi - 1; /* Last */
Guido van Rossum24e62e21997-12-10 15:14:24 +0000697
698 k = docompare(*l, *lo, compare);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000699 if (k == CMPERROR)
700 return -1;
701 if (k < 0)
Guido van Rossum3176bb11996-12-11 23:57:39 +0000702 { tmp = *lo; *lo = *l; *l = tmp; }
Guido van Rossum24e62e21997-12-10 15:14:24 +0000703
Guido van Rossum3176bb11996-12-11 23:57:39 +0000704 k = docompare(*r, *l, compare);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000705 if (k == CMPERROR)
706 return -1;
707 if (k < 0)
Guido van Rossum3176bb11996-12-11 23:57:39 +0000708 { tmp = *r; *r = *l; *l = tmp; }
Guido van Rossum24e62e21997-12-10 15:14:24 +0000709
710 k = docompare(*l, *lo, compare);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000711 if (k == CMPERROR)
712 return -1;
713 if (k < 0)
Guido van Rossum24e62e21997-12-10 15:14:24 +0000714 { tmp = *l; *l = *lo; *lo = tmp; }
715 pivot = *l;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000716
717 /* Partition the array */
Guido van Rossum24e62e21997-12-10 15:14:24 +0000718 l = lo+1;
719 r = hi-2;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000720 for (;;) {
721 /* Move left index to element > pivot */
Guido van Rossum044b9dc1998-02-25 17:50:03 +0000722 while (l < hi) {
Guido van Rossum24e62e21997-12-10 15:14:24 +0000723 k = docompare(*l, pivot, compare);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000724 if (k == CMPERROR)
725 return -1;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000726 if (k >= 0)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000727 break;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000728 l++;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000729 }
730 /* Move right index to element < pivot */
Guido van Rossum044b9dc1998-02-25 17:50:03 +0000731 while (r >= lo) {
Guido van Rossum24e62e21997-12-10 15:14:24 +0000732 k = docompare(pivot, *r, compare);
Guido van Rossum3f236de1996-12-10 23:55:39 +0000733 if (k == CMPERROR)
734 return -1;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000735 if (k >= 0)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000736 break;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000737 r--;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000738 }
Guido van Rossum24e62e21997-12-10 15:14:24 +0000739
Guido van Rossum3f236de1996-12-10 23:55:39 +0000740 /* If they met, we're through */
Guido van Rossum24e62e21997-12-10 15:14:24 +0000741 if (l < r) {
742 /* Swap elements and continue */
743 tmp = *l; *l = *r; *r = tmp;
744 l++; r--;
745 }
746 else if (l == r) {
747 l++; r--;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000748 break;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000749 }
750
751 if (l > r)
752 break;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000753 }
754
Guido van Rossum3f236de1996-12-10 23:55:39 +0000755
756 /* We have now reached the following conditions:
Guido van Rossum3176bb11996-12-11 23:57:39 +0000757 lo <= r < l <= hi
758 all x in [lo,r) are <= pivot
759 all x in [r,l) are == pivot
760 all x in [l,hi) are >= pivot
761 The partitions are [lo,r) and [l,hi)
Guido van Rossum3f236de1996-12-10 23:55:39 +0000762 */
763
764 /* Push biggest partition first */
Guido van Rossum3176bb11996-12-11 23:57:39 +0000765 n = r - lo;
766 n2 = hi - l;
767 if (n > n2) {
Guido van Rossum3f236de1996-12-10 23:55:39 +0000768 /* First one is bigger */
Guido van Rossum24e62e21997-12-10 15:14:24 +0000769 if (n > MINSIZE) {
Guido van Rossum3176bb11996-12-11 23:57:39 +0000770 lostack[top] = lo;
771 histack[top++] = r;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000772 if (n2 > MINSIZE) {
Guido van Rossum3176bb11996-12-11 23:57:39 +0000773 lostack[top] = l;
774 histack[top++] = hi;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000775 }
776 }
777 } else {
778 /* Second one is bigger */
Guido van Rossum24e62e21997-12-10 15:14:24 +0000779 if (n2 > MINSIZE) {
Guido van Rossum3176bb11996-12-11 23:57:39 +0000780 lostack[top] = l;
781 histack[top++] = hi;
Guido van Rossum24e62e21997-12-10 15:14:24 +0000782 if (n > MINSIZE) {
Guido van Rossum3176bb11996-12-11 23:57:39 +0000783 lostack[top] = lo;
784 histack[top++] = r;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000785 }
786 }
787 }
788
789 /* Should assert top < STACKSIZE-1 */
790 }
Guido van Rossum24e62e21997-12-10 15:14:24 +0000791
792 /*
793 * Ouch - even if I screwed up the quicksort above, the
794 * insertionsort below will cover up the problem - just a
795 * performance hit would be noticable.
796 */
797
798 /* insertionsort is pretty fast on the partially sorted list */
799
800 if (insertionsort(array, size, compare) < 0)
801 return -1;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000802
803 /* Succes */
804 return 0;
805}
806
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000807static PyObject *
Guido van Rossum3f236de1996-12-10 23:55:39 +0000808listsort(self, compare)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000809 PyListObject *self;
810 PyObject *compare;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000811{
812 /* XXX Don't you *dare* changing the list's length in compare()! */
813 if (quicksort(self->ob_item, self->ob_size, compare) < 0)
814 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000815 Py_INCREF(Py_None);
816 return Py_None;
Guido van Rossum3f236de1996-12-10 23:55:39 +0000817}
818
819#else /* !NEWSORT */
820
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000821static PyObject *comparefunc;
Guido van Rossume10a19e1992-08-03 19:05:37 +0000822
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000823static int
824cmp(v, w)
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000825 const ANY *v, *w;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000826{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000827 PyObject *t, *res;
Guido van Rossume10a19e1992-08-03 19:05:37 +0000828 long i;
829
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000830 if (PyErr_Occurred())
Guido van Rossume10a19e1992-08-03 19:05:37 +0000831 return 0;
832
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000833 if (comparefunc == NULL)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000834 return PyObject_Compare(* (PyObject **) v, * (PyObject **) w);
Guido van Rossume10a19e1992-08-03 19:05:37 +0000835
836 /* Call the user-supplied comparison function */
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000837 t = Py_BuildValue("(OO)", * (PyObject **) v, * (PyObject **) w);
Guido van Rossume10a19e1992-08-03 19:05:37 +0000838 if (t == NULL)
839 return 0;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000840 res = PyEval_CallObject(comparefunc, t);
841 Py_DECREF(t);
Guido van Rossume10a19e1992-08-03 19:05:37 +0000842 if (res == NULL)
843 return 0;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000844 if (!PyInt_Check(res)) {
845 PyErr_SetString(PyExc_TypeError,
846 "comparison function should return int");
Guido van Rossume10a19e1992-08-03 19:05:37 +0000847 i = 0;
848 }
849 else {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000850 i = PyInt_AsLong(res);
Guido van Rossume10a19e1992-08-03 19:05:37 +0000851 if (i < 0)
852 i = -1;
853 else if (i > 0)
854 i = 1;
855 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000856 Py_DECREF(res);
Guido van Rossume10a19e1992-08-03 19:05:37 +0000857 return (int) i;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000858}
859
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000860static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000861listsort(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000862 PyListObject *self;
863 PyObject *args;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000864{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000865 PyObject *save_comparefunc;
Guido van Rossume10a19e1992-08-03 19:05:37 +0000866 if (self->ob_size <= 1) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000867 Py_INCREF(Py_None);
868 return Py_None;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000869 }
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000870 save_comparefunc = comparefunc;
871 comparefunc = args;
872 if (comparefunc != NULL) {
Guido van Rossume10a19e1992-08-03 19:05:37 +0000873 /* Test the comparison function for obvious errors */
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000874 (void) cmp((ANY *)&self->ob_item[0], (ANY *)&self->ob_item[1]);
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000875 if (PyErr_Occurred()) {
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000876 comparefunc = save_comparefunc;
Guido van Rossume10a19e1992-08-03 19:05:37 +0000877 return NULL;
878 }
879 }
880 qsort((char *)self->ob_item,
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000881 (int) self->ob_size, sizeof(PyObject *), cmp);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000882 comparefunc = save_comparefunc;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000883 if (PyErr_Occurred())
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000884 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000885 Py_INCREF(Py_None);
886 return Py_None;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000887}
888
Guido van Rossum3f236de1996-12-10 23:55:39 +0000889#endif
890
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000891static PyObject *
Guido van Rossumed98d481991-03-06 13:07:53 +0000892listreverse(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000893 PyListObject *self;
894 PyObject *args;
Guido van Rossumed98d481991-03-06 13:07:53 +0000895{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000896 register PyObject **p, **q;
897 register PyObject *tmp;
Guido van Rossumed98d481991-03-06 13:07:53 +0000898
899 if (args != NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000900 PyErr_BadArgument();
Guido van Rossumed98d481991-03-06 13:07:53 +0000901 return NULL;
902 }
903
904 if (self->ob_size > 1) {
905 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
906 p < q; p++, q--) {
907 tmp = *p;
908 *p = *q;
909 *q = tmp;
910 }
911 }
912
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000913 Py_INCREF(Py_None);
914 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +0000915}
916
Guido van Rossum84c76f51990-10-30 13:32:20 +0000917int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000918PyList_Reverse(v)
919 PyObject *v;
Guido van Rossumb0fe3a91995-01-17 16:34:45 +0000920{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000921 if (v == NULL || !PyList_Check(v)) {
922 PyErr_BadInternalCall();
Guido van Rossumb0fe3a91995-01-17 16:34:45 +0000923 return -1;
924 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000925 v = listreverse((PyListObject *)v, (PyObject *)NULL);
Guido van Rossumb0fe3a91995-01-17 16:34:45 +0000926 if (v == NULL)
927 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000928 Py_DECREF(v);
Guido van Rossumb0fe3a91995-01-17 16:34:45 +0000929 return 0;
930}
931
932int
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000933PyList_Sort(v)
934 PyObject *v;
Guido van Rossum84c76f51990-10-30 13:32:20 +0000935{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000936 if (v == NULL || !PyList_Check(v)) {
937 PyErr_BadInternalCall();
Guido van Rossum84c76f51990-10-30 13:32:20 +0000938 return -1;
939 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000940 v = listsort((PyListObject *)v, (PyObject *)NULL);
Guido van Rossum84c76f51990-10-30 13:32:20 +0000941 if (v == NULL)
942 return -1;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000943 Py_DECREF(v);
Guido van Rossum84c76f51990-10-30 13:32:20 +0000944 return 0;
945}
946
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000947PyObject *
948PyList_AsTuple(v)
949 PyObject *v;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000950{
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000951 PyObject *w;
952 PyObject **p;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000953 int n;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000954 if (v == NULL || !PyList_Check(v)) {
955 PyErr_BadInternalCall();
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000956 return NULL;
957 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000958 n = ((PyListObject *)v)->ob_size;
959 w = PyTuple_New(n);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000960 if (w == NULL)
961 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000962 p = ((PyTupleObject *)w)->ob_item;
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000963 memcpy((ANY *)p,
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000964 (ANY *)((PyListObject *)v)->ob_item,
965 n*sizeof(PyObject *));
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000966 while (--n >= 0) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000967 Py_INCREF(*p);
Guido van Rossum6cd2fe01994-08-29 12:45:32 +0000968 p++;
969 }
970 return w;
971}
972
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000973static PyObject *
Guido van Rossumed98d481991-03-06 13:07:53 +0000974listindex(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000975 PyListObject *self;
976 PyObject *args;
Guido van Rossumed98d481991-03-06 13:07:53 +0000977{
978 int i;
979
980 if (args == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000981 PyErr_BadArgument();
Guido van Rossumed98d481991-03-06 13:07:53 +0000982 return NULL;
983 }
984 for (i = 0; i < self->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000985 if (PyObject_Compare(self->ob_item[i], args) == 0)
986 return PyInt_FromLong((long)i);
Guido van Rossumc8b6df91997-05-23 00:06:51 +0000987 if (PyErr_Occurred())
988 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +0000989 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000990 PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +0000991 return NULL;
992}
993
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000994static PyObject *
Guido van Rossume6f7d181991-10-20 20:20:40 +0000995listcount(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000996 PyListObject *self;
997 PyObject *args;
Guido van Rossume6f7d181991-10-20 20:20:40 +0000998{
999 int count = 0;
1000 int i;
1001
1002 if (args == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001003 PyErr_BadArgument();
Guido van Rossume6f7d181991-10-20 20:20:40 +00001004 return NULL;
1005 }
1006 for (i = 0; i < self->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001007 if (PyObject_Compare(self->ob_item[i], args) == 0)
Guido van Rossume6f7d181991-10-20 20:20:40 +00001008 count++;
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001009 if (PyErr_Occurred())
1010 return NULL;
Guido van Rossume6f7d181991-10-20 20:20:40 +00001011 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001012 return PyInt_FromLong((long)count);
Guido van Rossume6f7d181991-10-20 20:20:40 +00001013}
1014
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001015static PyObject *
Guido van Rossumed98d481991-03-06 13:07:53 +00001016listremove(self, args)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001017 PyListObject *self;
1018 PyObject *args;
Guido van Rossumed98d481991-03-06 13:07:53 +00001019{
1020 int i;
1021
1022 if (args == NULL) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001023 PyErr_BadArgument();
Guido van Rossumed98d481991-03-06 13:07:53 +00001024 return NULL;
1025 }
1026 for (i = 0; i < self->ob_size; i++) {
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001027 if (PyObject_Compare(self->ob_item[i], args) == 0) {
1028 if (list_ass_slice(self, i, i+1,
1029 (PyObject *)NULL) != 0)
Guido van Rossumed98d481991-03-06 13:07:53 +00001030 return NULL;
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001031 Py_INCREF(Py_None);
1032 return Py_None;
Guido van Rossumed98d481991-03-06 13:07:53 +00001033 }
Guido van Rossumc8b6df91997-05-23 00:06:51 +00001034 if (PyErr_Occurred())
1035 return NULL;
Guido van Rossumed98d481991-03-06 13:07:53 +00001036 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001037 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
Guido van Rossumed98d481991-03-06 13:07:53 +00001038 return NULL;
1039}
1040
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001041static PyMethodDef list_methods[] = {
1042 {"append", (PyCFunction)listappend},
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001043 {"insert", (PyCFunction)listinsert},
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001044 {"remove", (PyCFunction)listremove},
Guido van Rossum5d8123f1997-07-13 03:58:01 +00001045 {"index", (PyCFunction)listindex},
1046 {"count", (PyCFunction)listcount},
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001047 {"reverse", (PyCFunction)listreverse},
Guido van Rossum5d8123f1997-07-13 03:58:01 +00001048 {"sort", (PyCFunction)listsort, 0},
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001049 {NULL, NULL} /* sentinel */
1050};
1051
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001052static PyObject *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001053list_getattr(f, name)
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001054 PyListObject *f;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001055 char *name;
1056{
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001057 return Py_FindMethod(list_methods, (PyObject *)f, name);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001058}
1059
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001060static PySequenceMethods list_as_sequence = {
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001061 (inquiry)list_length, /*sq_length*/
1062 (binaryfunc)list_concat, /*sq_concat*/
1063 (intargfunc)list_repeat, /*sq_repeat*/
1064 (intargfunc)list_item, /*sq_item*/
1065 (intintargfunc)list_slice, /*sq_slice*/
1066 (intobjargproc)list_ass_item, /*sq_ass_item*/
1067 (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001068};
1069
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001070PyTypeObject PyList_Type = {
1071 PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001072 0,
1073 "list",
Guido van Rossumc0b618a1997-05-02 03:12:38 +00001074 sizeof(PyListObject),
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001075 0,
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001076 (destructor)list_dealloc, /*tp_dealloc*/
1077 (printfunc)list_print, /*tp_print*/
1078 (getattrfunc)list_getattr, /*tp_getattr*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001079 0, /*tp_setattr*/
Guido van Rossum6cd2fe01994-08-29 12:45:32 +00001080 (cmpfunc)list_compare, /*tp_compare*/
1081 (reprfunc)list_repr, /*tp_repr*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00001082 0, /*tp_as_number*/
1083 &list_as_sequence, /*tp_as_sequence*/
1084 0, /*tp_as_mapping*/
1085};