blob: e99eda06f18e46881cc294d718c76bca9a9e523b [file] [log] [blame]
Guido van Rossumf70e43a1991-02-19 12:39:46 +00001
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00002/* Tuple object implementation */
3
Guido van Rossumc0b618a1997-05-02 03:12:38 +00004#include "Python.h"
Antoine Pitrou0197ff92012-03-22 14:38:16 +01005#include "accu.h"
Guido van Rossum85a5fbb1990-10-14 12:07:46 +00006
Guido van Rossum5ce78f82000-04-21 21:15:05 +00007/* Speed optimization to avoid frequent malloc/free of small tuples */
Christian Heimes2202f872008-02-06 14:31:34 +00008#ifndef PyTuple_MAXSAVESIZE
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00009#define PyTuple_MAXSAVESIZE 20 /* Largest tuple to save on free list */
Guido van Rossum5ce78f82000-04-21 21:15:05 +000010#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000011#ifndef PyTuple_MAXFREELIST
Christian Heimes2202f872008-02-06 14:31:34 +000012#define PyTuple_MAXFREELIST 2000 /* Maximum number of tuples of each size to save */
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000013#endif
14
Christian Heimes2202f872008-02-06 14:31:34 +000015#if PyTuple_MAXSAVESIZE > 0
16/* Entries 1 up to PyTuple_MAXSAVESIZE are free lists, entry 0 is the empty
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000017 tuple () of which at most one instance will be allocated.
18*/
Christian Heimes2202f872008-02-06 14:31:34 +000019static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
20static int numfree[PyTuple_MAXSAVESIZE];
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000021#endif
22#ifdef COUNT_ALLOCS
Benjamin Petersona4a37fe2009-01-11 17:13:55 +000023Py_ssize_t fast_tuple_allocs;
24Py_ssize_t tuple_zero_allocs;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000025#endif
26
Antoine Pitrou3a652b12009-03-23 18:52:06 +000027/* Debug statistic to count GC tracking of tuples.
28 Please note that tuples are only untracked when considered by the GC, and
29 many of them will be dead before. Therefore, a tracking rate close to 100%
30 does not necessarily prove that the heuristic is inefficient.
31*/
32#ifdef SHOW_TRACK_COUNT
33static Py_ssize_t count_untracked = 0;
34static Py_ssize_t count_tracked = 0;
35
36static void
37show_track(void)
38{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000039 fprintf(stderr, "Tuples created: %" PY_FORMAT_SIZE_T "d\n",
40 count_tracked + count_untracked);
41 fprintf(stderr, "Tuples tracked by the GC: %" PY_FORMAT_SIZE_T
42 "d\n", count_tracked);
43 fprintf(stderr, "%.2f%% tuple tracking rate\n\n",
44 (100.0*count_tracked/(count_untracked+count_tracked)));
Antoine Pitrou3a652b12009-03-23 18:52:06 +000045}
46#endif
47
48
Guido van Rossumc0b618a1997-05-02 03:12:38 +000049PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +000050PyTuple_New(register Py_ssize_t size)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +000051{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000052 register PyTupleObject *op;
53 Py_ssize_t i;
54 if (size < 0) {
55 PyErr_BadInternalCall();
56 return NULL;
57 }
Christian Heimes2202f872008-02-06 14:31:34 +000058#if PyTuple_MAXSAVESIZE > 0
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000059 if (size == 0 && free_list[0]) {
60 op = free_list[0];
61 Py_INCREF(op);
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000062#ifdef COUNT_ALLOCS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000063 tuple_zero_allocs++;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000064#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000065 return (PyObject *) op;
66 }
67 if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
68 free_list[size] = (PyTupleObject *) op->ob_item[0];
69 numfree[size]--;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000070#ifdef COUNT_ALLOCS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000071 fast_tuple_allocs++;
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000072#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000073 /* Inline PyObject_InitVar */
Guido van Rossum68055ce1998-12-11 14:56:38 +000074#ifdef Py_TRACE_REFS
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000075 Py_SIZE(op) = size;
76 Py_TYPE(op) = &PyTuple_Type;
Guido van Rossum68055ce1998-12-11 14:56:38 +000077#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000078 _Py_NewReference((PyObject *)op);
79 }
80 else
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +000081#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000082 {
83 Py_ssize_t nbytes = size * sizeof(PyObject *);
84 /* Check for overflow */
85 if (nbytes / sizeof(PyObject *) != (size_t)size ||
86 (nbytes > PY_SSIZE_T_MAX - sizeof(PyTupleObject) - sizeof(PyObject *)))
87 {
88 return PyErr_NoMemory();
89 }
90 nbytes += sizeof(PyTupleObject) - sizeof(PyObject *);
Neal Norwitz3ce5d922008-08-24 07:08:55 +000091
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000092 op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
93 if (op == NULL)
94 return NULL;
95 }
96 for (i=0; i < size; i++)
97 op->ob_item[i] = NULL;
Christian Heimes2202f872008-02-06 14:31:34 +000098#if PyTuple_MAXSAVESIZE > 0
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000099 if (size == 0) {
100 free_list[0] = op;
101 ++numfree[0];
102 Py_INCREF(op); /* extra INCREF so that this is never freed */
103 }
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000104#endif
Antoine Pitrouacc5d6b2009-03-23 19:19:54 +0000105#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000106 count_tracked++;
Antoine Pitrouacc5d6b2009-03-23 19:19:54 +0000107#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000108 _PyObject_GC_TRACK(op);
109 return (PyObject *) op;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000110}
111
Martin v. Löwis18e16552006-02-15 17:27:45 +0000112Py_ssize_t
Fred Drakeba096332000-07-09 07:04:36 +0000113PyTuple_Size(register PyObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000114{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000115 if (!PyTuple_Check(op)) {
116 PyErr_BadInternalCall();
117 return -1;
118 }
119 else
120 return Py_SIZE(op);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000121}
122
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000123PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000124PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000125{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000126 if (!PyTuple_Check(op)) {
127 PyErr_BadInternalCall();
128 return NULL;
129 }
130 if (i < 0 || i >= Py_SIZE(op)) {
131 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
132 return NULL;
133 }
134 return ((PyTupleObject *)op) -> ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000135}
136
137int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000138PyTuple_SetItem(register PyObject *op, register Py_ssize_t i, PyObject *newitem)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000139{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000140 register PyObject *olditem;
141 register PyObject **p;
142 if (!PyTuple_Check(op) || op->ob_refcnt != 1) {
143 Py_XDECREF(newitem);
144 PyErr_BadInternalCall();
145 return -1;
146 }
147 if (i < 0 || i >= Py_SIZE(op)) {
148 Py_XDECREF(newitem);
149 PyErr_SetString(PyExc_IndexError,
150 "tuple assignment index out of range");
151 return -1;
152 }
153 p = ((PyTupleObject *)op) -> ob_item + i;
154 olditem = *p;
155 *p = newitem;
156 Py_XDECREF(olditem);
157 return 0;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000158}
159
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000160void
161_PyTuple_MaybeUntrack(PyObject *op)
162{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000163 PyTupleObject *t;
164 Py_ssize_t i, n;
165
166 if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
167 return;
168 t = (PyTupleObject *) op;
169 n = Py_SIZE(t);
170 for (i = 0; i < n; i++) {
171 PyObject *elt = PyTuple_GET_ITEM(t, i);
172 /* Tuple with NULL elements aren't
173 fully constructed, don't untrack
174 them yet. */
175 if (!elt ||
176 _PyObject_GC_MAY_BE_TRACKED(elt))
177 return;
178 }
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000179#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000180 count_tracked--;
181 count_untracked++;
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000182#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000183 _PyObject_GC_UNTRACK(op);
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000184}
185
Raymond Hettingercb2da432003-10-12 18:24:34 +0000186PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000187PyTuple_Pack(Py_ssize_t n, ...)
Raymond Hettingercb2da432003-10-12 18:24:34 +0000188{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000189 Py_ssize_t i;
190 PyObject *o;
191 PyObject *result;
192 PyObject **items;
193 va_list vargs;
Raymond Hettingercb2da432003-10-12 18:24:34 +0000194
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000195 va_start(vargs, n);
196 result = PyTuple_New(n);
197 if (result == NULL)
198 return NULL;
199 items = ((PyTupleObject *)result)->ob_item;
200 for (i = 0; i < n; i++) {
201 o = va_arg(vargs, PyObject *);
202 Py_INCREF(o);
203 items[i] = o;
204 }
205 va_end(vargs);
206 return result;
Raymond Hettingercb2da432003-10-12 18:24:34 +0000207}
208
209
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000210/* Methods */
211
212static void
Fred Drakeba096332000-07-09 07:04:36 +0000213tupledealloc(register PyTupleObject *op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000214{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000215 register Py_ssize_t i;
216 register Py_ssize_t len = Py_SIZE(op);
217 PyObject_GC_UnTrack(op);
218 Py_TRASHCAN_SAFE_BEGIN(op)
219 if (len > 0) {
220 i = len;
221 while (--i >= 0)
222 Py_XDECREF(op->ob_item[i]);
Christian Heimes2202f872008-02-06 14:31:34 +0000223#if PyTuple_MAXSAVESIZE > 0
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000224 if (len < PyTuple_MAXSAVESIZE &&
225 numfree[len] < PyTuple_MAXFREELIST &&
226 Py_TYPE(op) == &PyTuple_Type)
227 {
228 op->ob_item[0] = (PyObject *) free_list[len];
229 numfree[len]++;
230 free_list[len] = op;
231 goto done; /* return */
232 }
Sjoerd Mullender842d2cc1993-10-15 16:18:48 +0000233#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000234 }
235 Py_TYPE(op)->tp_free((PyObject *)op);
Guido van Rossumd724b232000-03-13 16:01:29 +0000236done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000237 Py_TRASHCAN_SAFE_END(op)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000238}
239
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000240static PyObject *
Fred Drakeba096332000-07-09 07:04:36 +0000241tuplerepr(PyTupleObject *v)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000242{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000243 Py_ssize_t i, n;
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200244 PyObject *s = NULL;
245 _PyAccu acc;
246 static PyObject *sep = NULL;
Tim Petersa7259592001-06-16 05:11:17 +0000247
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000248 n = Py_SIZE(v);
249 if (n == 0)
250 return PyUnicode_FromString("()");
Tim Petersa7259592001-06-16 05:11:17 +0000251
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200252 if (sep == NULL) {
253 sep = PyUnicode_FromString(", ");
254 if (sep == NULL)
255 return NULL;
256 }
257
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000258 /* While not mutable, it is still possible to end up with a cycle in a
259 tuple through an object that stores itself within a tuple (and thus
260 infinitely asks for the repr of itself). This should only be
261 possible within a type. */
262 i = Py_ReprEnter((PyObject *)v);
263 if (i != 0) {
264 return i > 0 ? PyUnicode_FromString("(...)") : NULL;
265 }
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000266
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200267 if (_PyAccu_Init(&acc))
268 goto error;
269
270 s = PyUnicode_FromString("(");
271 if (s == NULL || _PyAccu_Accumulate(&acc, s))
272 goto error;
273 Py_CLEAR(s);
Tim Petersa7259592001-06-16 05:11:17 +0000274
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000275 /* Do repr() on each element. */
276 for (i = 0; i < n; ++i) {
277 if (Py_EnterRecursiveCall(" while getting the repr of a tuple"))
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200278 goto error;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000279 s = PyObject_Repr(v->ob_item[i]);
280 Py_LeaveRecursiveCall();
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200281 if (i > 0 && _PyAccu_Accumulate(&acc, sep))
282 goto error;
283 if (s == NULL || _PyAccu_Accumulate(&acc, s))
284 goto error;
285 Py_CLEAR(s);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000286 }
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200287 if (n > 1)
288 s = PyUnicode_FromString(")");
289 else
290 s = PyUnicode_FromString(",)");
291 if (s == NULL || _PyAccu_Accumulate(&acc, s))
292 goto error;
293 Py_CLEAR(s);
Tim Petersa7259592001-06-16 05:11:17 +0000294
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000295 Py_ReprLeave((PyObject *)v);
Antoine Pitroueeb7eea2011-10-06 18:57:27 +0200296 return _PyAccu_Finish(&acc);
297
298error:
299 _PyAccu_Destroy(&acc);
300 Py_XDECREF(s);
301 Py_ReprLeave((PyObject *)v);
302 return NULL;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000303}
304
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000305/* The addend 82520, was selected from the range(0, 1000000) for
306 generating the greatest number of prime multipliers for tuples
Raymond Hettinger4ec44e82004-06-04 06:35:20 +0000307 upto length eight:
308
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000309 1082527, 1165049, 1082531, 1165057, 1247581, 1330103, 1082533,
Raymond Hettinger4ec44e82004-06-04 06:35:20 +0000310 1330111, 1412633, 1165069, 1247599, 1495177, 1577699
311*/
312
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000313static Py_hash_t
Fred Drakeba096332000-07-09 07:04:36 +0000314tuplehash(PyTupleObject *v)
Guido van Rossum9bfef441993-03-29 10:43:31 +0000315{
Benjamin Peterson8f67d082010-10-17 20:54:53 +0000316 register Py_hash_t x, y;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000317 register Py_ssize_t len = Py_SIZE(v);
318 register PyObject **p;
Gregory P. Smith63e6c322012-01-14 15:31:34 -0800319 Py_hash_t mult = _PyHASH_MULTIPLIER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000320 x = 0x345678L;
321 p = v->ob_item;
322 while (--len >= 0) {
323 y = PyObject_Hash(*p++);
324 if (y == -1)
325 return -1;
326 x = (x ^ y) * mult;
327 /* the cast might truncate len; that doesn't change hash stability */
Benjamin Peterson8035bc52010-10-23 16:20:50 +0000328 mult += (Py_hash_t)(82520L + len + len);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000329 }
330 x += 97531L;
331 if (x == -1)
332 x = -2;
333 return x;
Guido van Rossum9bfef441993-03-29 10:43:31 +0000334}
335
Martin v. Löwis18e16552006-02-15 17:27:45 +0000336static Py_ssize_t
Fred Drakeba096332000-07-09 07:04:36 +0000337tuplelength(PyTupleObject *a)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000338{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000339 return Py_SIZE(a);
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000340}
341
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000342static int
Fred Drakeba096332000-07-09 07:04:36 +0000343tuplecontains(PyTupleObject *a, PyObject *el)
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000344{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000345 Py_ssize_t i;
346 int cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000347
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000348 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
349 cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
350 Py_EQ);
351 return cmp;
Jeremy Hylton37b1a262000-04-27 21:41:03 +0000352}
353
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000354static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000355tupleitem(register PyTupleObject *a, register Py_ssize_t i)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000356{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000357 if (i < 0 || i >= Py_SIZE(a)) {
358 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
359 return NULL;
360 }
361 Py_INCREF(a->ob_item[i]);
362 return a->ob_item[i];
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000363}
364
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000365static PyObject *
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000366tupleslice(register PyTupleObject *a, register Py_ssize_t ilow,
367 register Py_ssize_t ihigh)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000368{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000369 register PyTupleObject *np;
370 PyObject **src, **dest;
371 register Py_ssize_t i;
372 Py_ssize_t len;
373 if (ilow < 0)
374 ilow = 0;
375 if (ihigh > Py_SIZE(a))
376 ihigh = Py_SIZE(a);
377 if (ihigh < ilow)
378 ihigh = ilow;
379 if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {
380 Py_INCREF(a);
381 return (PyObject *)a;
382 }
383 len = ihigh - ilow;
384 np = (PyTupleObject *)PyTuple_New(len);
385 if (np == NULL)
386 return NULL;
387 src = a->ob_item + ilow;
388 dest = np->ob_item;
389 for (i = 0; i < len; i++) {
390 PyObject *v = src[i];
391 Py_INCREF(v);
392 dest[i] = v;
393 }
394 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000395}
396
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000397PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000398PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
Guido van Rossum7c36ad71992-01-14 18:45:33 +0000399{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000400 if (op == NULL || !PyTuple_Check(op)) {
401 PyErr_BadInternalCall();
402 return NULL;
403 }
404 return tupleslice((PyTupleObject *)op, i, j);
Guido van Rossum7c36ad71992-01-14 18:45:33 +0000405}
406
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000407static PyObject *
Fred Drakeba096332000-07-09 07:04:36 +0000408tupleconcat(register PyTupleObject *a, register PyObject *bb)
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000409{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000410 register Py_ssize_t size;
411 register Py_ssize_t i;
412 PyObject **src, **dest;
413 PyTupleObject *np;
414 if (!PyTuple_Check(bb)) {
415 PyErr_Format(PyExc_TypeError,
416 "can only concatenate tuple (not \"%.200s\") to tuple",
417 Py_TYPE(bb)->tp_name);
418 return NULL;
419 }
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000420#define b ((PyTupleObject *)bb)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000421 size = Py_SIZE(a) + Py_SIZE(b);
422 if (size < 0)
423 return PyErr_NoMemory();
424 np = (PyTupleObject *) PyTuple_New(size);
425 if (np == NULL) {
426 return NULL;
427 }
428 src = a->ob_item;
429 dest = np->ob_item;
430 for (i = 0; i < Py_SIZE(a); i++) {
431 PyObject *v = src[i];
432 Py_INCREF(v);
433 dest[i] = v;
434 }
435 src = b->ob_item;
436 dest = np->ob_item + Py_SIZE(a);
437 for (i = 0; i < Py_SIZE(b); i++) {
438 PyObject *v = src[i];
439 Py_INCREF(v);
440 dest[i] = v;
441 }
442 return (PyObject *)np;
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000443#undef b
444}
445
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000446static PyObject *
Martin v. Löwis18e16552006-02-15 17:27:45 +0000447tuplerepeat(PyTupleObject *a, Py_ssize_t n)
Guido van Rossumb8393da1991-06-04 19:35:24 +0000448{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000449 Py_ssize_t i, j;
450 Py_ssize_t size;
451 PyTupleObject *np;
452 PyObject **p, **items;
453 if (n < 0)
454 n = 0;
455 if (Py_SIZE(a) == 0 || n == 1) {
456 if (PyTuple_CheckExact(a)) {
457 /* Since tuples are immutable, we can return a shared
458 copy in this case */
459 Py_INCREF(a);
460 return (PyObject *)a;
461 }
462 if (Py_SIZE(a) == 0)
463 return PyTuple_New(0);
464 }
465 size = Py_SIZE(a) * n;
466 if (size/Py_SIZE(a) != n)
467 return PyErr_NoMemory();
468 np = (PyTupleObject *) PyTuple_New(size);
469 if (np == NULL)
470 return NULL;
471 p = np->ob_item;
472 items = a->ob_item;
473 for (i = 0; i < n; i++) {
474 for (j = 0; j < Py_SIZE(a); j++) {
475 *p = items[j];
476 Py_INCREF(*p);
477 p++;
478 }
479 }
480 return (PyObject *) np;
Guido van Rossumb8393da1991-06-04 19:35:24 +0000481}
482
Raymond Hettinger65baa342008-02-07 00:41:02 +0000483static PyObject *
484tupleindex(PyTupleObject *self, PyObject *args)
485{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000486 Py_ssize_t i, start=0, stop=Py_SIZE(self);
Petri Lehtinenebfaabd2011-11-06 21:02:39 +0200487 PyObject *v;
Raymond Hettinger65baa342008-02-07 00:41:02 +0000488
Petri Lehtinenebfaabd2011-11-06 21:02:39 +0200489 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
490 _PyEval_SliceIndex, &start,
491 _PyEval_SliceIndex, &stop))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000492 return NULL;
493 if (start < 0) {
494 start += Py_SIZE(self);
495 if (start < 0)
496 start = 0;
497 }
498 if (stop < 0) {
499 stop += Py_SIZE(self);
500 if (stop < 0)
501 stop = 0;
502 }
503 for (i = start; i < stop && i < Py_SIZE(self); i++) {
504 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
505 if (cmp > 0)
506 return PyLong_FromSsize_t(i);
507 else if (cmp < 0)
508 return NULL;
509 }
510 PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");
511 return NULL;
Raymond Hettinger65baa342008-02-07 00:41:02 +0000512}
513
514static PyObject *
515tuplecount(PyTupleObject *self, PyObject *v)
516{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000517 Py_ssize_t count = 0;
518 Py_ssize_t i;
Raymond Hettinger65baa342008-02-07 00:41:02 +0000519
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000520 for (i = 0; i < Py_SIZE(self); i++) {
521 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
522 if (cmp > 0)
523 count++;
524 else if (cmp < 0)
525 return NULL;
526 }
527 return PyLong_FromSsize_t(count);
Raymond Hettinger65baa342008-02-07 00:41:02 +0000528}
529
Jeremy Hylton8caad492000-06-23 14:18:11 +0000530static int
531tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
532{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000533 Py_ssize_t i;
Jeremy Hylton8caad492000-06-23 14:18:11 +0000534
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000535 for (i = Py_SIZE(o); --i >= 0; )
536 Py_VISIT(o->ob_item[i]);
537 return 0;
Jeremy Hylton8caad492000-06-23 14:18:11 +0000538}
539
Guido van Rossumf77bc622001-01-18 00:00:53 +0000540static PyObject *
541tuplerichcompare(PyObject *v, PyObject *w, int op)
542{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000543 PyTupleObject *vt, *wt;
544 Py_ssize_t i;
545 Py_ssize_t vlen, wlen;
Guido van Rossumf77bc622001-01-18 00:00:53 +0000546
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000547 if (!PyTuple_Check(v) || !PyTuple_Check(w)) {
548 Py_INCREF(Py_NotImplemented);
549 return Py_NotImplemented;
550 }
Guido van Rossumf77bc622001-01-18 00:00:53 +0000551
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000552 vt = (PyTupleObject *)v;
553 wt = (PyTupleObject *)w;
Guido van Rossumf77bc622001-01-18 00:00:53 +0000554
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000555 vlen = Py_SIZE(vt);
556 wlen = Py_SIZE(wt);
Guido van Rossumf77bc622001-01-18 00:00:53 +0000557
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000558 /* Note: the corresponding code for lists has an "early out" test
559 * here when op is EQ or NE and the lengths differ. That pays there,
560 * but Tim was unable to find any real code where EQ/NE tuple
561 * compares don't have the same length, so testing for it here would
562 * have cost without benefit.
563 */
Tim Petersd7ed3bf2001-05-15 20:12:59 +0000564
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000565 /* Search for the first index where items are different.
566 * Note that because tuples are immutable, it's safe to reuse
567 * vlen and wlen across the comparison calls.
568 */
569 for (i = 0; i < vlen && i < wlen; i++) {
570 int k = PyObject_RichCompareBool(vt->ob_item[i],
571 wt->ob_item[i], Py_EQ);
572 if (k < 0)
573 return NULL;
574 if (!k)
575 break;
576 }
Guido van Rossumf77bc622001-01-18 00:00:53 +0000577
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000578 if (i >= vlen || i >= wlen) {
579 /* No more items to compare -- compare sizes */
580 int cmp;
581 PyObject *res;
582 switch (op) {
583 case Py_LT: cmp = vlen < wlen; break;
584 case Py_LE: cmp = vlen <= wlen; break;
585 case Py_EQ: cmp = vlen == wlen; break;
586 case Py_NE: cmp = vlen != wlen; break;
587 case Py_GT: cmp = vlen > wlen; break;
588 case Py_GE: cmp = vlen >= wlen; break;
589 default: return NULL; /* cannot happen */
590 }
591 if (cmp)
592 res = Py_True;
593 else
594 res = Py_False;
595 Py_INCREF(res);
596 return res;
597 }
Guido van Rossumf77bc622001-01-18 00:00:53 +0000598
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000599 /* We have an item that differs -- shortcuts for EQ/NE */
600 if (op == Py_EQ) {
601 Py_INCREF(Py_False);
602 return Py_False;
603 }
604 if (op == Py_NE) {
605 Py_INCREF(Py_True);
606 return Py_True;
607 }
Guido van Rossumf77bc622001-01-18 00:00:53 +0000608
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000609 /* Compare the final item again using the proper operator */
610 return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
Guido van Rossumf77bc622001-01-18 00:00:53 +0000611}
612
Jeremy Hylton938ace62002-07-17 16:30:39 +0000613static PyObject *
Guido van Rossumae960af2001-08-30 03:11:59 +0000614tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
615
Tim Peters6d6c1a32001-08-02 04:15:00 +0000616static PyObject *
617tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
618{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000619 PyObject *arg = NULL;
620 static char *kwlist[] = {"sequence", 0};
Tim Peters6d6c1a32001-08-02 04:15:00 +0000621
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000622 if (type != &PyTuple_Type)
623 return tuple_subtype_new(type, args, kwds);
624 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))
625 return NULL;
Tim Peters6d6c1a32001-08-02 04:15:00 +0000626
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000627 if (arg == NULL)
628 return PyTuple_New(0);
629 else
630 return PySequence_Tuple(arg);
Tim Peters6d6c1a32001-08-02 04:15:00 +0000631}
632
Guido van Rossumae960af2001-08-30 03:11:59 +0000633static PyObject *
634tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
635{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000636 PyObject *tmp, *newobj, *item;
637 Py_ssize_t i, n;
Guido van Rossumae960af2001-08-30 03:11:59 +0000638
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000639 assert(PyType_IsSubtype(type, &PyTuple_Type));
640 tmp = tuple_new(&PyTuple_Type, args, kwds);
641 if (tmp == NULL)
642 return NULL;
643 assert(PyTuple_Check(tmp));
644 newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
645 if (newobj == NULL)
646 return NULL;
647 for (i = 0; i < n; i++) {
648 item = PyTuple_GET_ITEM(tmp, i);
649 Py_INCREF(item);
650 PyTuple_SET_ITEM(newobj, i, item);
651 }
652 Py_DECREF(tmp);
653 return newobj;
Guido van Rossumae960af2001-08-30 03:11:59 +0000654}
655
Martin v. Löwis14f8b4c2002-06-13 20:33:02 +0000656PyDoc_STRVAR(tuple_doc,
Ezio Melotti7f807b72010-03-01 04:08:34 +0000657"tuple() -> empty tuple\n\
658tuple(iterable) -> tuple initialized from iterable's items\n\
659\n\
660If the argument is a tuple, the return value is the same object.");
Tim Peters6d6c1a32001-08-02 04:15:00 +0000661
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000662static PySequenceMethods tuple_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000663 (lenfunc)tuplelength, /* sq_length */
664 (binaryfunc)tupleconcat, /* sq_concat */
665 (ssizeargfunc)tuplerepeat, /* sq_repeat */
666 (ssizeargfunc)tupleitem, /* sq_item */
667 0, /* sq_slice */
668 0, /* sq_ass_item */
669 0, /* sq_ass_slice */
670 (objobjproc)tuplecontains, /* sq_contains */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000671};
672
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000673static PyObject*
674tuplesubscript(PyTupleObject* self, PyObject* item)
675{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000676 if (PyIndex_Check(item)) {
677 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
678 if (i == -1 && PyErr_Occurred())
679 return NULL;
680 if (i < 0)
681 i += PyTuple_GET_SIZE(self);
682 return tupleitem(self, i);
683 }
684 else if (PySlice_Check(item)) {
685 Py_ssize_t start, stop, step, slicelength, cur, i;
686 PyObject* result;
687 PyObject* it;
688 PyObject **src, **dest;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000689
Martin v. Löwis4d0d4712010-12-03 20:14:31 +0000690 if (PySlice_GetIndicesEx(item,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000691 PyTuple_GET_SIZE(self),
692 &start, &stop, &step, &slicelength) < 0) {
693 return NULL;
694 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000695
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000696 if (slicelength <= 0) {
697 return PyTuple_New(0);
698 }
699 else if (start == 0 && step == 1 &&
700 slicelength == PyTuple_GET_SIZE(self) &&
701 PyTuple_CheckExact(self)) {
702 Py_INCREF(self);
703 return (PyObject *)self;
704 }
705 else {
706 result = PyTuple_New(slicelength);
707 if (!result) return NULL;
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000708
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000709 src = self->ob_item;
710 dest = ((PyTupleObject *)result)->ob_item;
711 for (cur = start, i = 0; i < slicelength;
712 cur += step, i++) {
713 it = src[cur];
714 Py_INCREF(it);
715 dest[i] = it;
716 }
717
718 return result;
719 }
720 }
721 else {
722 PyErr_Format(PyExc_TypeError,
723 "tuple indices must be integers, not %.200s",
724 Py_TYPE(item)->tp_name);
725 return NULL;
726 }
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000727}
728
Guido van Rossum5d9113d2003-01-29 17:58:45 +0000729static PyObject *
730tuple_getnewargs(PyTupleObject *v)
731{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000732 return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));
733
Guido van Rossum5d9113d2003-01-29 17:58:45 +0000734}
735
Amaury Forgeot d'Arc35c86582008-06-17 21:11:29 +0000736static PyObject *
737tuple_sizeof(PyTupleObject *self)
738{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000739 Py_ssize_t res;
Amaury Forgeot d'Arc35c86582008-06-17 21:11:29 +0000740
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000741 res = PyTuple_Type.tp_basicsize + Py_SIZE(self) * sizeof(PyObject *);
742 return PyLong_FromSsize_t(res);
Amaury Forgeot d'Arc35c86582008-06-17 21:11:29 +0000743}
744
Raymond Hettinger65baa342008-02-07 00:41:02 +0000745PyDoc_STRVAR(index_doc,
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000746"T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
747"Raises ValueError if the value is not present."
748);
Raymond Hettinger65baa342008-02-07 00:41:02 +0000749PyDoc_STRVAR(count_doc,
750"T.count(value) -> integer -- return number of occurrences of value");
Amaury Forgeot d'Arc35c86582008-06-17 21:11:29 +0000751PyDoc_STRVAR(sizeof_doc,
752"T.__sizeof__() -- size of T in memory, in bytes");
Raymond Hettinger65baa342008-02-07 00:41:02 +0000753
Guido van Rossum5d9113d2003-01-29 17:58:45 +0000754static PyMethodDef tuple_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000755 {"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},
756 {"__sizeof__", (PyCFunction)tuple_sizeof, METH_NOARGS, sizeof_doc},
757 {"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},
758 {"count", (PyCFunction)tuplecount, METH_O, count_doc},
759 {NULL, NULL} /* sentinel */
Guido van Rossum5d9113d2003-01-29 17:58:45 +0000760};
761
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000762static PyMappingMethods tuple_as_mapping = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000763 (lenfunc)tuplelength,
764 (binaryfunc)tuplesubscript,
765 0
Michael W. Hudson5efaf7e2002-06-11 10:55:12 +0000766};
767
Raymond Hettinger48923c52002-08-09 01:30:17 +0000768static PyObject *tuple_iter(PyObject *seq);
769
Guido van Rossumc0b618a1997-05-02 03:12:38 +0000770PyTypeObject PyTuple_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000771 PyVarObject_HEAD_INIT(&PyType_Type, 0)
772 "tuple",
773 sizeof(PyTupleObject) - sizeof(PyObject *),
774 sizeof(PyObject *),
775 (destructor)tupledealloc, /* tp_dealloc */
776 0, /* tp_print */
777 0, /* tp_getattr */
778 0, /* tp_setattr */
779 0, /* tp_reserved */
780 (reprfunc)tuplerepr, /* tp_repr */
781 0, /* tp_as_number */
782 &tuple_as_sequence, /* tp_as_sequence */
783 &tuple_as_mapping, /* tp_as_mapping */
784 (hashfunc)tuplehash, /* tp_hash */
785 0, /* tp_call */
786 0, /* tp_str */
787 PyObject_GenericGetAttr, /* tp_getattro */
788 0, /* tp_setattro */
789 0, /* tp_as_buffer */
790 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
791 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */
792 tuple_doc, /* tp_doc */
793 (traverseproc)tupletraverse, /* tp_traverse */
794 0, /* tp_clear */
795 tuplerichcompare, /* tp_richcompare */
796 0, /* tp_weaklistoffset */
797 tuple_iter, /* tp_iter */
798 0, /* tp_iternext */
799 tuple_methods, /* tp_methods */
800 0, /* tp_members */
801 0, /* tp_getset */
802 0, /* tp_base */
803 0, /* tp_dict */
804 0, /* tp_descr_get */
805 0, /* tp_descr_set */
806 0, /* tp_dictoffset */
807 0, /* tp_init */
808 0, /* tp_alloc */
809 tuple_new, /* tp_new */
810 PyObject_GC_Del, /* tp_free */
Guido van Rossum85a5fbb1990-10-14 12:07:46 +0000811};
Guido van Rossum12d12c51993-10-26 17:58:25 +0000812
813/* The following function breaks the notion that tuples are immutable:
814 it changes the size of a tuple. We get away with this only if there
815 is only one module referencing the object. You can also think of it
Neil Schemenauer08b53e62000-10-05 19:36:49 +0000816 as creating a new tuple object and destroying the old one, only more
817 efficiently. In any case, don't use this if the tuple may already be
Tim Peters4324aa32001-05-28 22:30:08 +0000818 known to some other part of the code. */
Guido van Rossum12d12c51993-10-26 17:58:25 +0000819
820int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000821_PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
Guido van Rossum12d12c51993-10-26 17:58:25 +0000822{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000823 register PyTupleObject *v;
824 register PyTupleObject *sv;
825 Py_ssize_t i;
826 Py_ssize_t oldsize;
Sjoerd Mullender615194a1993-11-01 13:46:50 +0000827
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000828 v = (PyTupleObject *) *pv;
829 if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||
830 (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
831 *pv = 0;
832 Py_XDECREF(v);
833 PyErr_BadInternalCall();
834 return -1;
835 }
836 oldsize = Py_SIZE(v);
837 if (oldsize == newsize)
838 return 0;
Neil Schemenauer08b53e62000-10-05 19:36:49 +0000839
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000840 if (oldsize == 0) {
841 /* Empty tuples are often shared, so we should never
842 resize them in-place even if we do own the only
843 (current) reference */
844 Py_DECREF(v);
845 *pv = PyTuple_New(newsize);
846 return *pv == NULL ? -1 : 0;
847 }
Thomas Wouters6a922372001-05-28 13:11:02 +0000848
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000849 /* XXX UNREF/NEWREF interface should be more symmetrical */
850 _Py_DEC_REFTOTAL;
851 if (_PyObject_GC_IS_TRACKED(v))
852 _PyObject_GC_UNTRACK(v);
853 _Py_ForgetReference((PyObject *) v);
854 /* DECREF items deleted by shrinkage */
855 for (i = newsize; i < oldsize; i++) {
856 Py_XDECREF(v->ob_item[i]);
857 v->ob_item[i] = NULL;
858 }
859 sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
860 if (sv == NULL) {
861 *pv = NULL;
862 PyObject_GC_Del(v);
863 return -1;
864 }
865 _Py_NewReference((PyObject *) sv);
866 /* Zero out items added by growing */
867 if (newsize > oldsize)
868 memset(&sv->ob_item[oldsize], 0,
869 sizeof(*sv->ob_item) * (newsize - oldsize));
870 *pv = (PyObject *) sv;
871 _PyObject_GC_TRACK(sv);
872 return 0;
Guido van Rossum12d12c51993-10-26 17:58:25 +0000873}
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000874
Christian Heimesa156e092008-02-16 07:38:31 +0000875int
876PyTuple_ClearFreeList(void)
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000877{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000878 int freelist_size = 0;
Christian Heimes2202f872008-02-06 14:31:34 +0000879#if PyTuple_MAXSAVESIZE > 0
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000880 int i;
881 for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
882 PyTupleObject *p, *q;
883 p = free_list[i];
884 freelist_size += numfree[i];
885 free_list[i] = NULL;
886 numfree[i] = 0;
887 while (p) {
888 q = p;
889 p = (PyTupleObject *)(p->ob_item[0]);
890 PyObject_GC_Del(q);
891 }
892 }
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000893#endif
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000894 return freelist_size;
Christian Heimesa156e092008-02-16 07:38:31 +0000895}
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000896
Christian Heimesa156e092008-02-16 07:38:31 +0000897void
898PyTuple_Fini(void)
899{
900#if PyTuple_MAXSAVESIZE > 0
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000901 /* empty tuples are used all over the place and applications may
902 * rely on the fact that an empty tuple is a singleton. */
903 Py_XDECREF(free_list[0]);
904 free_list[0] = NULL;
Christian Heimesa156e092008-02-16 07:38:31 +0000905
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000906 (void)PyTuple_ClearFreeList();
Christian Heimesa156e092008-02-16 07:38:31 +0000907#endif
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000908#ifdef SHOW_TRACK_COUNT
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000909 show_track();
Antoine Pitrou3a652b12009-03-23 18:52:06 +0000910#endif
Guido van Rossumfbbd57e1997-08-05 02:16:08 +0000911}
Raymond Hettinger48923c52002-08-09 01:30:17 +0000912
913/*********************** Tuple Iterator **************************/
914
915typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000916 PyObject_HEAD
917 long it_index;
918 PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
Raymond Hettinger48923c52002-08-09 01:30:17 +0000919} tupleiterobject;
920
Raymond Hettinger48923c52002-08-09 01:30:17 +0000921static void
922tupleiter_dealloc(tupleiterobject *it)
923{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000924 _PyObject_GC_UNTRACK(it);
925 Py_XDECREF(it->it_seq);
926 PyObject_GC_Del(it);
Raymond Hettinger48923c52002-08-09 01:30:17 +0000927}
928
929static int
930tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
931{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000932 Py_VISIT(it->it_seq);
933 return 0;
Raymond Hettinger48923c52002-08-09 01:30:17 +0000934}
935
Raymond Hettinger48923c52002-08-09 01:30:17 +0000936static PyObject *
937tupleiter_next(tupleiterobject *it)
938{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000939 PyTupleObject *seq;
940 PyObject *item;
Raymond Hettinger48923c52002-08-09 01:30:17 +0000941
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000942 assert(it != NULL);
943 seq = it->it_seq;
944 if (seq == NULL)
945 return NULL;
946 assert(PyTuple_Check(seq));
Raymond Hettinger48923c52002-08-09 01:30:17 +0000947
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000948 if (it->it_index < PyTuple_GET_SIZE(seq)) {
949 item = PyTuple_GET_ITEM(seq, it->it_index);
950 ++it->it_index;
951 Py_INCREF(item);
952 return item;
953 }
Raymond Hettinger48923c52002-08-09 01:30:17 +0000954
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000955 Py_DECREF(seq);
956 it->it_seq = NULL;
957 return NULL;
Raymond Hettinger48923c52002-08-09 01:30:17 +0000958}
959
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000960static PyObject *
Raymond Hettinger435bf582004-03-18 22:43:10 +0000961tupleiter_len(tupleiterobject *it)
962{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000963 Py_ssize_t len = 0;
964 if (it->it_seq)
965 len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
966 return PyLong_FromSsize_t(len);
Raymond Hettinger435bf582004-03-18 22:43:10 +0000967}
968
Armin Rigof5b3e362006-02-11 21:32:43 +0000969PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +0000970
971static PyMethodDef tupleiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000972 {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
973 {NULL, NULL} /* sentinel */
Raymond Hettinger435bf582004-03-18 22:43:10 +0000974};
975
Raymond Hettinger48923c52002-08-09 01:30:17 +0000976PyTypeObject PyTupleIter_Type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000977 PyVarObject_HEAD_INIT(&PyType_Type, 0)
978 "tuple_iterator", /* tp_name */
979 sizeof(tupleiterobject), /* tp_basicsize */
980 0, /* tp_itemsize */
981 /* methods */
982 (destructor)tupleiter_dealloc, /* tp_dealloc */
983 0, /* tp_print */
984 0, /* tp_getattr */
985 0, /* tp_setattr */
986 0, /* tp_reserved */
987 0, /* tp_repr */
988 0, /* tp_as_number */
989 0, /* tp_as_sequence */
990 0, /* tp_as_mapping */
991 0, /* tp_hash */
992 0, /* tp_call */
993 0, /* tp_str */
994 PyObject_GenericGetAttr, /* tp_getattro */
995 0, /* tp_setattro */
996 0, /* tp_as_buffer */
997 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
998 0, /* tp_doc */
999 (traverseproc)tupleiter_traverse, /* tp_traverse */
1000 0, /* tp_clear */
1001 0, /* tp_richcompare */
1002 0, /* tp_weaklistoffset */
1003 PyObject_SelfIter, /* tp_iter */
1004 (iternextfunc)tupleiter_next, /* tp_iternext */
1005 tupleiter_methods, /* tp_methods */
1006 0,
Raymond Hettinger48923c52002-08-09 01:30:17 +00001007};
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001008
1009static PyObject *
1010tuple_iter(PyObject *seq)
1011{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001012 tupleiterobject *it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001013
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001014 if (!PyTuple_Check(seq)) {
1015 PyErr_BadInternalCall();
1016 return NULL;
1017 }
1018 it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1019 if (it == NULL)
1020 return NULL;
1021 it->it_index = 0;
1022 Py_INCREF(seq);
1023 it->it_seq = (PyTupleObject *)seq;
1024 _PyObject_GC_TRACK(it);
1025 return (PyObject *)it;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001026}