blob: 743951c5d3a77354f60d66ab539ffcc73e4e8823 [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001/***********************************************************
2Copyright 1991 by Stichting Mathematisch Centrum, Amsterdam, The
3Netherlands.
4
5 All Rights Reserved
6
7Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
9provided that the above copyright notice appear in all copies and that
10both that copyright notice and this permission notice appear in
11supporting documentation, and that the names of Stichting Mathematisch
12Centrum or CWI not be used in advertising or publicity pertaining to
13distribution of the software without specific, written prior permission.
14
15STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
16THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
17FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
18FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
20ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
21OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22
23******************************************************************/
24
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000025/* List object implementation */
26
Guido van Rossum3f5da241990-12-20 15:06:42 +000027#include "allobjects.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000028
29object *
30newlistobject(size)
31 int size;
32{
33 int i;
34 listobject *op;
35 if (size < 0) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +000036 err_badcall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000037 return NULL;
38 }
39 op = (listobject *) malloc(sizeof(listobject));
40 if (op == NULL) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +000041 return err_nomem();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000042 }
43 if (size <= 0) {
44 op->ob_item = NULL;
45 }
46 else {
47 op->ob_item = (object **) malloc(size * sizeof(object *));
48 if (op->ob_item == NULL) {
49 free((ANY *)op);
Guido van Rossum2a9096b1990-10-21 22:15:08 +000050 return err_nomem();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000051 }
52 }
53 NEWREF(op);
54 op->ob_type = &Listtype;
55 op->ob_size = size;
56 for (i = 0; i < size; i++)
57 op->ob_item[i] = NULL;
58 return (object *) op;
59}
60
61int
62getlistsize(op)
63 object *op;
64{
65 if (!is_listobject(op)) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +000066 err_badcall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000067 return -1;
68 }
69 else
70 return ((listobject *)op) -> ob_size;
71}
72
73object *
74getlistitem(op, i)
75 object *op;
76 int i;
77{
78 if (!is_listobject(op)) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +000079 err_badcall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000080 return NULL;
81 }
82 if (i < 0 || i >= ((listobject *)op) -> ob_size) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +000083 err_setstr(IndexError, "list index out of range");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000084 return NULL;
85 }
86 return ((listobject *)op) -> ob_item[i];
87}
88
89int
90setlistitem(op, i, newitem)
91 register object *op;
92 register int i;
93 register object *newitem;
94{
95 register object *olditem;
96 if (!is_listobject(op)) {
97 if (newitem != NULL)
98 DECREF(newitem);
Guido van Rossum2a9096b1990-10-21 22:15:08 +000099 err_badcall();
100 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000101 }
102 if (i < 0 || i >= ((listobject *)op) -> ob_size) {
103 if (newitem != NULL)
104 DECREF(newitem);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000105 err_setstr(IndexError, "list assignment index out of range");
106 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000107 }
108 olditem = ((listobject *)op) -> ob_item[i];
109 ((listobject *)op) -> ob_item[i] = newitem;
110 if (olditem != NULL)
111 DECREF(olditem);
112 return 0;
113}
114
115static int
116ins1(self, where, v)
117 listobject *self;
118 int where;
119 object *v;
120{
121 int i;
122 object **items;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000123 if (v == NULL) {
124 err_badcall();
125 return -1;
126 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000127 items = self->ob_item;
128 RESIZE(items, object *, self->ob_size+1);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000129 if (items == NULL) {
130 err_nomem();
131 return -1;
132 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000133 if (where < 0)
134 where = 0;
135 if (where > self->ob_size)
136 where = self->ob_size;
137 for (i = self->ob_size; --i >= where; )
138 items[i+1] = items[i];
139 INCREF(v);
140 items[where] = v;
141 self->ob_item = items;
142 self->ob_size++;
143 return 0;
144}
145
146int
147inslistitem(op, where, newitem)
148 object *op;
149 int where;
150 object *newitem;
151{
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000152 if (!is_listobject(op)) {
153 err_badcall();
154 return -1;
155 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000156 return ins1((listobject *)op, where, newitem);
157}
158
159int
160addlistitem(op, newitem)
161 object *op;
162 object *newitem;
163{
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000164 if (!is_listobject(op)) {
165 err_badcall();
166 return -1;
167 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000168 return ins1((listobject *)op,
169 (int) ((listobject *)op)->ob_size, newitem);
170}
171
172/* Methods */
173
174static void
175list_dealloc(op)
176 listobject *op;
177{
178 int i;
179 for (i = 0; i < op->ob_size; i++) {
180 if (op->ob_item[i] != NULL)
181 DECREF(op->ob_item[i]);
182 }
183 if (op->ob_item != NULL)
184 free((ANY *)op->ob_item);
185 free((ANY *)op);
186}
187
188static void
189list_print(op, fp, flags)
190 listobject *op;
191 FILE *fp;
192 int flags;
193{
194 int i;
195 fprintf(fp, "[");
196 for (i = 0; i < op->ob_size && !StopPrint; i++) {
197 if (i > 0) {
198 fprintf(fp, ", ");
199 }
200 printobject(op->ob_item[i], fp, flags);
201 }
202 fprintf(fp, "]");
203}
204
205object *
206list_repr(v)
207 listobject *v;
208{
209 object *s, *t, *comma;
210 int i;
211 s = newstringobject("[");
212 comma = newstringobject(", ");
213 for (i = 0; i < v->ob_size && s != NULL; i++) {
214 if (i > 0)
215 joinstring(&s, comma);
216 t = reprobject(v->ob_item[i]);
217 joinstring(&s, t);
218 DECREF(t);
219 }
220 DECREF(comma);
221 t = newstringobject("]");
222 joinstring(&s, t);
223 DECREF(t);
224 return s;
225}
226
227static int
228list_compare(v, w)
229 listobject *v, *w;
230{
231 int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
232 int i;
233 for (i = 0; i < len; i++) {
234 int cmp = cmpobject(v->ob_item[i], w->ob_item[i]);
235 if (cmp != 0)
236 return cmp;
237 }
238 return v->ob_size - w->ob_size;
239}
240
241static int
242list_length(a)
243 listobject *a;
244{
245 return a->ob_size;
246}
247
248static object *
249list_item(a, i)
250 listobject *a;
251 int i;
252{
253 if (i < 0 || i >= a->ob_size) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000254 err_setstr(IndexError, "list index out of range");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000255 return NULL;
256 }
257 INCREF(a->ob_item[i]);
258 return a->ob_item[i];
259}
260
261static object *
262list_slice(a, ilow, ihigh)
263 listobject *a;
264 int ilow, ihigh;
265{
266 listobject *np;
267 int i;
268 if (ilow < 0)
269 ilow = 0;
270 else if (ilow > a->ob_size)
271 ilow = a->ob_size;
272 if (ihigh < 0)
273 ihigh = 0;
274 if (ihigh < ilow)
275 ihigh = ilow;
276 else if (ihigh > a->ob_size)
277 ihigh = a->ob_size;
278 np = (listobject *) newlistobject(ihigh - ilow);
279 if (np == NULL)
280 return NULL;
281 for (i = ilow; i < ihigh; i++) {
282 object *v = a->ob_item[i];
283 INCREF(v);
284 np->ob_item[i - ilow] = v;
285 }
286 return (object *)np;
287}
288
289static object *
290list_concat(a, bb)
291 listobject *a;
292 object *bb;
293{
294 int size;
295 int i;
296 listobject *np;
297 if (!is_listobject(bb)) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000298 err_badarg();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000299 return NULL;
300 }
301#define b ((listobject *)bb)
302 size = a->ob_size + b->ob_size;
303 np = (listobject *) newlistobject(size);
304 if (np == NULL) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000305 return err_nomem();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000306 }
307 for (i = 0; i < a->ob_size; i++) {
308 object *v = a->ob_item[i];
309 INCREF(v);
310 np->ob_item[i] = v;
311 }
312 for (i = 0; i < b->ob_size; i++) {
313 object *v = b->ob_item[i];
314 INCREF(v);
315 np->ob_item[i + a->ob_size] = v;
316 }
317 return (object *)np;
318#undef b
319}
320
Guido van Rossumed98d481991-03-06 13:07:53 +0000321static object *
322list_repeat(a, n)
323 listobject *a;
324 int n;
325{
326 int i, j;
327 int size;
328 listobject *np;
329 object **p;
330 if (n < 0)
331 n = 0;
332 size = a->ob_size * n;
333 np = (listobject *) newlistobject(size);
334 if (np == NULL)
335 return NULL;
336 p = np->ob_item;
337 for (i = 0; i < n; i++) {
338 for (j = 0; j < a->ob_size; j++) {
339 *p = a->ob_item[j];
340 INCREF(*p);
341 p++;
342 }
343 }
344 return (object *) np;
345}
346
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000347static int
348list_ass_item(a, i, v)
349 listobject *a;
350 int i;
351 object *v;
352{
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000353 if (i < 0 || i >= a->ob_size) {
354 err_setstr(IndexError, "list assignment index out of range");
355 return -1;
356 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000357 if (v == NULL)
358 return list_ass_slice(a, i, i+1, v);
359 INCREF(v);
360 DECREF(a->ob_item[i]);
361 a->ob_item[i] = v;
362 return 0;
363}
364
365static int
366list_ass_slice(a, ilow, ihigh, v)
367 listobject *a;
368 int ilow, ihigh;
369 object *v;
370{
371 object **item;
372 int n; /* Size of replacement list */
373 int d; /* Change in size */
374 int k; /* Loop index */
375#define b ((listobject *)v)
376 if (v == NULL)
377 n = 0;
378 else if (is_listobject(v))
379 n = b->ob_size;
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000380 else {
381 err_badarg();
382 return -1;
383 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000384 if (ilow < 0)
385 ilow = 0;
386 else if (ilow > a->ob_size)
387 ilow = a->ob_size;
388 if (ihigh < 0)
389 ihigh = 0;
390 if (ihigh < ilow)
391 ihigh = ilow;
392 else if (ihigh > a->ob_size)
393 ihigh = a->ob_size;
394 item = a->ob_item;
395 d = n - (ihigh-ilow);
396 if (d <= 0) { /* Delete -d items; DECREF ihigh-ilow items */
397 for (k = ilow; k < ihigh; k++)
398 DECREF(item[k]);
399 if (d < 0) {
400 for (/*k = ihigh*/; k < a->ob_size; k++)
401 item[k+d] = item[k];
402 a->ob_size += d;
403 RESIZE(item, object *, a->ob_size); /* Can't fail */
404 a->ob_item = item;
405 }
406 }
407 else { /* Insert d items; DECREF ihigh-ilow items */
408 RESIZE(item, object *, a->ob_size + d);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000409 if (item == NULL) {
410 err_nomem();
411 return -1;
412 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000413 for (k = a->ob_size; --k >= ihigh; )
414 item[k+d] = item[k];
415 for (/*k = ihigh-1*/; k >= ilow; --k)
416 DECREF(item[k]);
417 a->ob_item = item;
418 a->ob_size += d;
419 }
420 for (k = 0; k < n; k++, ilow++) {
421 object *w = b->ob_item[k];
422 INCREF(w);
423 item[ilow] = w;
424 }
425 return 0;
426#undef b
427}
428
429static object *
430ins(self, where, v)
431 listobject *self;
432 int where;
433 object *v;
434{
435 if (ins1(self, where, v) != 0)
436 return NULL;
437 INCREF(None);
438 return None;
439}
440
441static object *
442listinsert(self, args)
443 listobject *self;
444 object *args;
445{
446 int i;
447 if (args == NULL || !is_tupleobject(args) || gettuplesize(args) != 2) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000448 err_badarg();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000449 return NULL;
450 }
451 if (!getintarg(gettupleitem(args, 0), &i))
452 return NULL;
453 return ins(self, i, gettupleitem(args, 1));
454}
455
456static object *
457listappend(self, args)
458 listobject *self;
459 object *args;
460{
461 return ins(self, (int) self->ob_size, args);
462}
463
464static int
465cmp(v, w)
466 char *v, *w;
467{
468 return cmpobject(* (object **) v, * (object **) w);
469}
470
471static object *
472listsort(self, args)
473 listobject *self;
474 object *args;
475{
476 if (args != NULL) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000477 err_badarg();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000478 return NULL;
479 }
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000480 err_clear();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000481 if (self->ob_size > 1)
482 qsort((char *)self->ob_item,
483 (int) self->ob_size, sizeof(object *), cmp);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000484 if (err_occurred())
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000485 return NULL;
486 INCREF(None);
487 return None;
488}
489
Guido van Rossumed98d481991-03-06 13:07:53 +0000490static object *
491listreverse(self, args)
492 listobject *self;
493 object *args;
494{
495 register object **p, **q;
496 register object *tmp;
497
498 if (args != NULL) {
499 err_badarg();
500 return NULL;
501 }
502
503 if (self->ob_size > 1) {
504 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
505 p < q; p++, q--) {
506 tmp = *p;
507 *p = *q;
508 *q = tmp;
509 }
510 }
511
512 INCREF(None);
513 return None;
514}
515
Guido van Rossum84c76f51990-10-30 13:32:20 +0000516int
517sortlist(v)
518 object *v;
519{
520 if (v == NULL || !is_listobject(v)) {
521 err_badcall();
522 return -1;
523 }
524 v = listsort((listobject *)v, (object *)NULL);
525 if (v == NULL)
526 return -1;
527 DECREF(v);
528 return 0;
529}
530
Guido van Rossumed98d481991-03-06 13:07:53 +0000531static object *
532listindex(self, args)
533 listobject *self;
534 object *args;
535{
536 int i;
537
538 if (args == NULL) {
539 err_badarg();
540 return NULL;
541 }
542 for (i = 0; i < self->ob_size; i++) {
543 if (cmpobject(self->ob_item[i], args) == 0)
544 return newintobject(i);
545 }
546 err_setstr(RuntimeError, "list.index(x): x not in list");
547 return NULL;
548}
549
550static object *
551listremove(self, args)
552 listobject *self;
553 object *args;
554{
555 int i;
556
557 if (args == NULL) {
558 err_badarg();
559 return NULL;
560 }
561 for (i = 0; i < self->ob_size; i++) {
562 if (cmpobject(self->ob_item[i], args) == 0) {
563 if (list_ass_slice(self, i, i+1, (object *)NULL) != 0)
564 return NULL;
565 INCREF(None);
566 return None;
567 }
568
569 }
570 err_setstr(RuntimeError, "list.remove(x): x not in list");
571 return NULL;
572}
573
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000574static struct methodlist list_methods[] = {
575 {"append", listappend},
Guido van Rossumed98d481991-03-06 13:07:53 +0000576 {"index", listindex},
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000577 {"insert", listinsert},
578 {"sort", listsort},
Guido van Rossumed98d481991-03-06 13:07:53 +0000579 {"remove", listremove},
580 {"reverse", listreverse},
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000581 {NULL, NULL} /* sentinel */
582};
583
584static object *
585list_getattr(f, name)
586 listobject *f;
587 char *name;
588{
589 return findmethod(list_methods, (object *)f, name);
590}
591
592static sequence_methods list_as_sequence = {
593 list_length, /*sq_length*/
594 list_concat, /*sq_concat*/
Guido van Rossumed98d481991-03-06 13:07:53 +0000595 list_repeat, /*sq_repeat*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000596 list_item, /*sq_item*/
597 list_slice, /*sq_slice*/
598 list_ass_item, /*sq_ass_item*/
599 list_ass_slice, /*sq_ass_slice*/
600};
601
602typeobject Listtype = {
603 OB_HEAD_INIT(&Typetype)
604 0,
605 "list",
606 sizeof(listobject),
607 0,
608 list_dealloc, /*tp_dealloc*/
609 list_print, /*tp_print*/
610 list_getattr, /*tp_getattr*/
611 0, /*tp_setattr*/
612 list_compare, /*tp_compare*/
613 list_repr, /*tp_repr*/
614 0, /*tp_as_number*/
615 &list_as_sequence, /*tp_as_sequence*/
616 0, /*tp_as_mapping*/
617};