blob: fd53c300cb638b2821180f1a9419070fdcc14e44 [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/* Tuple object implementation */
33
Guido van Rossum3f5da241990-12-20 15:06:42 +000034#include "allobjects.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000035
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000036#ifndef MAXSAVESIZE
37#define MAXSAVESIZE 20
38#endif
39
40#if MAXSAVESIZE > 0
41/* Entries 1 upto MAXSAVESIZE are free lists, entry 0 is the empty
42 tuple () of which at most one instance will be allocated.
43*/
Sjoerd Mullender615194a1993-11-01 13:46:50 +000044static tupleobject *free_tuples[MAXSAVESIZE];
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000045#endif
46#ifdef COUNT_ALLOCS
47int fast_tuple_allocs;
48int tuple_zero_allocs;
49#endif
50
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000051object *
52newtupleobject(size)
53 register int size;
54{
55 register int i;
56 register tupleobject *op;
57 if (size < 0) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +000058 err_badcall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000059 return NULL;
60 }
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000061#if MAXSAVESIZE > 0
Sjoerd Mullender615194a1993-11-01 13:46:50 +000062 if (size == 0 && free_tuples[0]) {
63 op = free_tuples[0];
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000064 INCREF(op);
65#ifdef COUNT_ALLOCS
66 tuple_zero_allocs++;
67#endif
68 return (object *) op;
69 }
Sjoerd Mullender615194a1993-11-01 13:46:50 +000070 if (0 < size && size < MAXSAVESIZE && (op = free_tuples[size]) != NULL) {
71 free_tuples[size] = (tupleobject *) op->ob_item[0];
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000072#ifdef COUNT_ALLOCS
73 fast_tuple_allocs++;
74#endif
75 } else
76#endif
77 {
78 op = (tupleobject *)
79 malloc(sizeof(tupleobject) + size * sizeof(object *));
80 if (op == NULL)
81 return err_nomem();
82 }
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000083 op->ob_type = &Tupletype;
84 op->ob_size = size;
85 for (i = 0; i < size; i++)
86 op->ob_item[i] = NULL;
Sjoerd Mullendera9c3c221993-10-11 12:54:31 +000087 NEWREF(op);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000088#if MAXSAVESIZE > 0
89 if (size == 0) {
Sjoerd Mullender615194a1993-11-01 13:46:50 +000090 free_tuples[0] = op;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000091 INCREF(op); /* extra INCREF so that this is never freed */
92 }
93#endif
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000094 return (object *) op;
95}
96
97int
98gettuplesize(op)
99 register object *op;
100{
101 if (!is_tupleobject(op)) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000102 err_badcall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000103 return -1;
104 }
105 else
106 return ((tupleobject *)op)->ob_size;
107}
108
109object *
110gettupleitem(op, i)
111 register object *op;
112 register int i;
113{
114 if (!is_tupleobject(op)) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000115 err_badcall();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000116 return NULL;
117 }
118 if (i < 0 || i >= ((tupleobject *)op) -> ob_size) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000119 err_setstr(IndexError, "tuple index out of range");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000120 return NULL;
121 }
122 return ((tupleobject *)op) -> ob_item[i];
123}
124
125int
126settupleitem(op, i, newitem)
127 register object *op;
128 register int i;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000129 object *newitem;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000130{
131 register object *olditem;
Guido van Rossum5fe60581995-03-09 12:12:50 +0000132 register object **p;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000133 if (!is_tupleobject(op)) {
Guido van Rossum12d12c51993-10-26 17:58:25 +0000134 XDECREF(newitem);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000135 err_badcall();
136 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000137 }
138 if (i < 0 || i >= ((tupleobject *)op) -> ob_size) {
Guido van Rossum12d12c51993-10-26 17:58:25 +0000139 XDECREF(newitem);
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000140 err_setstr(IndexError, "tuple assignment index out of range");
141 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000142 }
Guido van Rossum5fe60581995-03-09 12:12:50 +0000143 p = ((tupleobject *)op) -> ob_item + i;
144 olditem = *p;
145 *p = newitem;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000146 XDECREF(olditem);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000147 return 0;
148}
149
150/* Methods */
151
152static void
153tupledealloc(op)
154 register tupleobject *op;
155{
156 register int i;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000157 for (i = 0; i < op->ob_size; i++)
158 XDECREF(op->ob_item[i]);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000159#if MAXSAVESIZE > 0
160 if (0 < op->ob_size && op->ob_size < MAXSAVESIZE) {
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000161 op->ob_item[0] = (object *) free_tuples[op->ob_size];
162 free_tuples[op->ob_size] = op;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000163 } else
164#endif
165 free((ANY *)op);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000166}
167
Guido van Rossum49e85141991-06-07 22:59:30 +0000168static int
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000169tupleprint(op, fp, flags)
170 tupleobject *op;
171 FILE *fp;
172 int flags;
173{
174 int i;
175 fprintf(fp, "(");
Guido van Rossum49e85141991-06-07 22:59:30 +0000176 for (i = 0; i < op->ob_size; i++) {
177 if (i > 0)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000178 fprintf(fp, ", ");
Guido van Rossuma3d78fb1993-11-10 09:23:53 +0000179 if (printobject(op->ob_item[i], fp, 0) != 0)
Guido van Rossum49e85141991-06-07 22:59:30 +0000180 return -1;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000181 }
182 if (op->ob_size == 1)
183 fprintf(fp, ",");
184 fprintf(fp, ")");
Guido van Rossum49e85141991-06-07 22:59:30 +0000185 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000186}
187
Guido van Rossum234f9421993-06-17 12:35:49 +0000188static object *
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000189tuplerepr(v)
190 tupleobject *v;
191{
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000192 object *s, *comma;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000193 int i;
194 s = newstringobject("(");
195 comma = newstringobject(", ");
196 for (i = 0; i < v->ob_size && s != NULL; i++) {
197 if (i > 0)
198 joinstring(&s, comma);
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000199 joinstring_decref(&s, reprobject(v->ob_item[i]));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000200 }
201 DECREF(comma);
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000202 if (v->ob_size == 1)
203 joinstring_decref(&s, newstringobject(","));
204 joinstring_decref(&s, newstringobject(")"));
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000205 return s;
206}
207
208static int
209tuplecompare(v, w)
210 register tupleobject *v, *w;
211{
212 register int len =
213 (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
214 register int i;
215 for (i = 0; i < len; i++) {
216 int cmp = cmpobject(v->ob_item[i], w->ob_item[i]);
217 if (cmp != 0)
218 return cmp;
219 }
220 return v->ob_size - w->ob_size;
221}
222
Guido van Rossum9bfef441993-03-29 10:43:31 +0000223static long
224tuplehash(v)
225 tupleobject *v;
226{
227 register long x, y;
228 register int len = v->ob_size;
229 register object **p;
230 x = 0x345678L;
231 p = v->ob_item;
232 while (--len >= 0) {
233 y = hashobject(*p++);
234 if (y == -1)
235 return -1;
Guido van Rossum0969ad21996-12-16 17:55:46 +0000236 x = (1000003*x) ^ y;
Guido van Rossum9bfef441993-03-29 10:43:31 +0000237 }
238 x ^= v->ob_size;
239 if (x == -1)
240 x = -2;
241 return x;
242}
243
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000244static int
245tuplelength(a)
246 tupleobject *a;
247{
248 return a->ob_size;
249}
250
251static object *
252tupleitem(a, i)
253 register tupleobject *a;
254 register int i;
255{
256 if (i < 0 || i >= a->ob_size) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000257 err_setstr(IndexError, "tuple index out of range");
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000258 return NULL;
259 }
260 INCREF(a->ob_item[i]);
261 return a->ob_item[i];
262}
263
264static object *
265tupleslice(a, ilow, ihigh)
266 register tupleobject *a;
267 register int ilow, ihigh;
268{
269 register tupleobject *np;
270 register int i;
271 if (ilow < 0)
272 ilow = 0;
273 if (ihigh > a->ob_size)
274 ihigh = a->ob_size;
275 if (ihigh < ilow)
276 ihigh = ilow;
277 if (ilow == 0 && ihigh == a->ob_size) {
278 /* XXX can only do this if tuples are immutable! */
279 INCREF(a);
280 return (object *)a;
281 }
282 np = (tupleobject *)newtupleobject(ihigh - ilow);
283 if (np == NULL)
284 return NULL;
285 for (i = ilow; i < ihigh; i++) {
286 object *v = a->ob_item[i];
287 INCREF(v);
288 np->ob_item[i - ilow] = v;
289 }
290 return (object *)np;
291}
292
Guido van Rossum7c36ad71992-01-14 18:45:33 +0000293object *
294gettupleslice(op, i, j)
295 object *op;
296 int i, j;
297{
298 if (op == NULL || !is_tupleobject(op)) {
299 err_badcall();
300 return NULL;
301 }
302 return tupleslice((tupleobject *)op, i, j);
303}
304
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000305static object *
306tupleconcat(a, bb)
307 register tupleobject *a;
308 register object *bb;
309{
310 register int size;
311 register int i;
312 tupleobject *np;
313 if (!is_tupleobject(bb)) {
Guido van Rossum2a9096b1990-10-21 22:15:08 +0000314 err_badarg();
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000315 return NULL;
316 }
317#define b ((tupleobject *)bb)
318 size = a->ob_size + b->ob_size;
319 np = (tupleobject *) newtupleobject(size);
320 if (np == NULL) {
Guido van Rossum49e85141991-06-07 22:59:30 +0000321 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000322 }
323 for (i = 0; i < a->ob_size; i++) {
324 object *v = a->ob_item[i];
325 INCREF(v);
326 np->ob_item[i] = v;
327 }
328 for (i = 0; i < b->ob_size; i++) {
329 object *v = b->ob_item[i];
330 INCREF(v);
331 np->ob_item[i + a->ob_size] = v;
332 }
333 return (object *)np;
334#undef b
335}
336
Guido van Rossumb8393da1991-06-04 19:35:24 +0000337static object *
338tuplerepeat(a, n)
339 tupleobject *a;
340 int n;
341{
342 int i, j;
343 int size;
344 tupleobject *np;
345 object **p;
346 if (n < 0)
347 n = 0;
348 if (a->ob_size*n == a->ob_size) {
349 /* Since tuples are immutable, we can return a shared
350 copy in this case */
351 INCREF(a);
352 return (object *)a;
353 }
354 size = a->ob_size * n;
355 np = (tupleobject *) newtupleobject(size);
356 if (np == NULL)
357 return NULL;
358 p = np->ob_item;
359 for (i = 0; i < n; i++) {
360 for (j = 0; j < a->ob_size; j++) {
361 *p = a->ob_item[j];
362 INCREF(*p);
363 p++;
364 }
365 }
366 return (object *) np;
367}
368
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000369static sequence_methods tuple_as_sequence = {
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000370 (inquiry)tuplelength, /*sq_length*/
371 (binaryfunc)tupleconcat, /*sq_concat*/
372 (intargfunc)tuplerepeat, /*sq_repeat*/
373 (intargfunc)tupleitem, /*sq_item*/
374 (intintargfunc)tupleslice, /*sq_slice*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000375 0, /*sq_ass_item*/
376 0, /*sq_ass_slice*/
377};
378
379typeobject Tupletype = {
380 OB_HEAD_INIT(&Typetype)
381 0,
382 "tuple",
383 sizeof(tupleobject) - sizeof(object *),
384 sizeof(object *),
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000385 (destructor)tupledealloc, /*tp_dealloc*/
386 (printfunc)tupleprint, /*tp_print*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000387 0, /*tp_getattr*/
388 0, /*tp_setattr*/
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000389 (cmpfunc)tuplecompare, /*tp_compare*/
390 (reprfunc)tuplerepr, /*tp_repr*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000391 0, /*tp_as_number*/
392 &tuple_as_sequence, /*tp_as_sequence*/
393 0, /*tp_as_mapping*/
Guido van Rossum1d5735e1994-08-30 08:27:36 +0000394 (hashfunc)tuplehash, /*tp_hash*/
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000395};
Guido van Rossum12d12c51993-10-26 17:58:25 +0000396
397/* The following function breaks the notion that tuples are immutable:
398 it changes the size of a tuple. We get away with this only if there
399 is only one module referencing the object. You can also think of it
400 as creating a new tuple object and destroying the old one, only
401 more efficiently. In any case, don't use this if the tuple may
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000402 already be known to some other part of the code...
403 If last_is_sticky is set, the tuple will grow or shrink at the
404 front, otherwise it will grow or shrink at the end. */
Guido van Rossum12d12c51993-10-26 17:58:25 +0000405
406int
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000407resizetuple(pv, newsize, last_is_sticky)
Guido van Rossum12d12c51993-10-26 17:58:25 +0000408 object **pv;
409 int newsize;
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000410 int last_is_sticky;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000411{
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000412 register tupleobject *v;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000413 register tupleobject *sv;
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000414 int i;
415 int sizediff;
416
417 v = (tupleobject *) *pv;
Guido van Rossum055968c1995-08-04 04:05:10 +0000418 if (v == NULL || !is_tupleobject(v) || v->ob_refcnt != 1) {
Guido van Rossum12d12c51993-10-26 17:58:25 +0000419 *pv = 0;
420 DECREF(v);
421 err_badcall();
422 return -1;
423 }
Guido van Rossum055968c1995-08-04 04:05:10 +0000424 sizediff = newsize - v->ob_size;
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000425 if (sizediff == 0)
426 return 0;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000427 /* XXX UNREF/NEWREF interface should be more symmetrical */
Guido van Rossum441e4ab1996-05-23 22:46:51 +0000428#ifdef Py_REF_DEBUG
Guido van Rossum6f9e4331995-03-29 16:57:48 +0000429 --_Py_RefTotal;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000430#endif
431 UNREF(v);
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000432 if (last_is_sticky && sizediff < 0) {
433 /* shrinking: move entries to the front and zero moved entries */
434 for (i = 0; i < newsize; i++) {
435 XDECREF(v->ob_item[i]);
436 v->ob_item[i] = v->ob_item[i - sizediff];
437 v->ob_item[i - sizediff] = NULL;
438 }
439 }
440 for (i = newsize; i < v->ob_size; i++) {
441 XDECREF(v->ob_item[i]);
442 v->ob_item[i] = NULL;
443 }
444 sv = (tupleobject *)
Guido van Rossum12d12c51993-10-26 17:58:25 +0000445 realloc((char *)v,
446 sizeof(tupleobject) + newsize * sizeof(object *));
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000447 *pv = (object *) sv;
448 if (sv == NULL) {
Guido van Rossum12d12c51993-10-26 17:58:25 +0000449 DEL(v);
450 err_nomem();
451 return -1;
452 }
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000453 NEWREF(sv);
454 for (i = sv->ob_size; i < newsize; i++)
455 sv->ob_item[i] = NULL;
456 if (last_is_sticky && sizediff > 0) {
457 /* growing: move entries to the end and zero moved entries */
458 for (i = newsize - 1; i >= sizediff; i--) {
459 sv->ob_item[i] = sv->ob_item[i - sizediff];
460 sv->ob_item[i - sizediff] = NULL;
461 }
462 }
463 sv->ob_size = newsize;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000464 return 0;
465}