Python code coverage for Objects/tupleobject.c

#	count	content
1	n/a
2	n/a	/* Tuple object implementation */
3	n/a
4	n/a	#include "Python.h"
5	n/a	#include "accu.h"
6	n/a
7	n/a	/* Speed optimization to avoid frequent malloc/free of small tuples */
8	n/a	#ifndef PyTuple_MAXSAVESIZE
9	n/a	#define PyTuple_MAXSAVESIZE 20 /* Largest tuple to save on free list */
10	n/a	#endif
11	n/a	#ifndef PyTuple_MAXFREELIST
12	n/a	#define PyTuple_MAXFREELIST 2000 /* Maximum number of tuples of each size to save */
13	n/a	#endif
14	n/a
15	n/a	#if PyTuple_MAXSAVESIZE > 0
16	n/a	/* Entries 1 up to PyTuple_MAXSAVESIZE are free lists, entry 0 is the empty
17	n/a	tuple () of which at most one instance will be allocated.
18	n/a	*/
19	n/a	static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
20	n/a	static int numfree[PyTuple_MAXSAVESIZE];
21	n/a	#endif
22	n/a	#ifdef COUNT_ALLOCS
23	n/a	Py_ssize_t fast_tuple_allocs;
24	n/a	Py_ssize_t tuple_zero_allocs;
25	n/a	#endif
26	n/a
27	n/a	/* Debug statistic to count GC tracking of tuples.
28	n/a	Please note that tuples are only untracked when considered by the GC, and
29	n/a	many of them will be dead before. Therefore, a tracking rate close to 100%
30	n/a	does not necessarily prove that the heuristic is inefficient.
31	n/a	*/
32	n/a	#ifdef SHOW_TRACK_COUNT
33	n/a	static Py_ssize_t count_untracked = 0;
34	n/a	static Py_ssize_t count_tracked = 0;
35	n/a
36	n/a	static void
37	n/a	show_track(void)
38	n/a	{
39	n/a	PyObject xoptions, value;
40	n/a	_Py_IDENTIFIER(showalloccount);
41	n/a
42	n/a	xoptions = PySys_GetXOptions();
43	n/a	if (xoptions == NULL)
44	n/a	return;
45	n/a	value = _PyDict_GetItemId(xoptions, &PyId_showalloccount);
46	n/a	if (value != Py_True)
47	n/a	return;
48	n/a
49	n/a	fprintf(stderr, "Tuples created: %" PY_FORMAT_SIZE_T "d\n",
50	n/a	count_tracked + count_untracked);
51	n/a	fprintf(stderr, "Tuples tracked by the GC: %" PY_FORMAT_SIZE_T
52	n/a	"d\n", count_tracked);
53	n/a	fprintf(stderr, "%.2f%% tuple tracking rate\n\n",
54	n/a	(100.0*count_tracked/(count_untracked+count_tracked)));
55	n/a	}
56	n/a	#endif
57	n/a
58	n/a	/* Print summary info about the state of the optimized allocator */
59	n/a	void
60	n/a	_PyTuple_DebugMallocStats(FILE *out)
61	n/a	{
62	n/a	#if PyTuple_MAXSAVESIZE > 0
63	n/a	int i;
64	n/a	char buf[128];
65	n/a	for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
66	n/a	PyOS_snprintf(buf, sizeof(buf),
67	n/a	"free %d-sized PyTupleObject", i);
68	n/a	_PyDebugAllocatorStats(out,
69	n/a	buf,
70	n/a	numfree[i], _PyObject_VAR_SIZE(&PyTuple_Type, i));
71	n/a	}
72	n/a	#endif
73	n/a	}
74	n/a
75	n/a	PyObject *
76	n/a	PyTuple_New(Py_ssize_t size)
77	n/a	{
78	n/a	PyTupleObject *op;
79	n/a	Py_ssize_t i;
80	n/a	if (size < 0) {
81	n/a	PyErr_BadInternalCall();
82	n/a	return NULL;
83	n/a	}
84	n/a	#if PyTuple_MAXSAVESIZE > 0
85	n/a	if (size == 0 && free_list[0]) {
86	n/a	op = free_list[0];
87	n/a	Py_INCREF(op);
88	n/a	#ifdef COUNT_ALLOCS
89	n/a	tuple_zero_allocs++;
90	n/a	#endif
91	n/a	return (PyObject *) op;
92	n/a	}
93	n/a	if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
94	n/a	free_list[size] = (PyTupleObject *) op->ob_item[0];
95	n/a	numfree[size]--;
96	n/a	#ifdef COUNT_ALLOCS
97	n/a	fast_tuple_allocs++;
98	n/a	#endif
99	n/a	/* Inline PyObject_InitVar */
100	n/a	#ifdef Py_TRACE_REFS
101	n/a	Py_SIZE(op) = size;
102	n/a	Py_TYPE(op) = &PyTuple_Type;
103	n/a	#endif
104	n/a	_Py_NewReference((PyObject *)op);
105	n/a	}
106	n/a	else
107	n/a	#endif
108	n/a	{
109	n/a	/* Check for overflow */
110	n/a	if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
111	n/a	sizeof(PyObject )) / sizeof(PyObject )) {
112	n/a	return PyErr_NoMemory();
113	n/a	}
114	n/a	op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
115	n/a	if (op == NULL)
116	n/a	return NULL;
117	n/a	}
118	n/a	for (i=0; i < size; i++)
119	n/a	op->ob_item[i] = NULL;
120	n/a	#if PyTuple_MAXSAVESIZE > 0
121	n/a	if (size == 0) {
122	n/a	free_list[0] = op;
123	n/a	++numfree[0];
124	n/a	Py_INCREF(op); /* extra INCREF so that this is never freed */
125	n/a	}
126	n/a	#endif
127	n/a	#ifdef SHOW_TRACK_COUNT
128	n/a	count_tracked++;
129	n/a	#endif
130	n/a	_PyObject_GC_TRACK(op);
131	n/a	return (PyObject *) op;
132	n/a	}
133	n/a
134	n/a	Py_ssize_t
135	n/a	PyTuple_Size(PyObject *op)
136	n/a	{
137	n/a	if (!PyTuple_Check(op)) {
138	n/a	PyErr_BadInternalCall();
139	n/a	return -1;
140	n/a	}
141	n/a	else
142	n/a	return Py_SIZE(op);
143	n/a	}
144	n/a
145	n/a	PyObject *
146	n/a	PyTuple_GetItem(PyObject *op, Py_ssize_t i)
147	n/a	{
148	n/a	if (!PyTuple_Check(op)) {
149	n/a	PyErr_BadInternalCall();
150	n/a	return NULL;
151	n/a	}
152	n/a	if (i < 0 \|\| i >= Py_SIZE(op)) {
153	n/a	PyErr_SetString(PyExc_IndexError, "tuple index out of range");
154	n/a	return NULL;
155	n/a	}
156	n/a	return ((PyTupleObject *)op) -> ob_item[i];
157	n/a	}
158	n/a
159	n/a	int
160	n/a	PyTuple_SetItem(PyObject op, Py_ssize_t i, PyObject newitem)
161	n/a	{
162	n/a	PyObject **p;
163	n/a	if (!PyTuple_Check(op) \|\| op->ob_refcnt != 1) {
164	n/a	Py_XDECREF(newitem);
165	n/a	PyErr_BadInternalCall();
166	n/a	return -1;
167	n/a	}
168	n/a	if (i < 0 \|\| i >= Py_SIZE(op)) {
169	n/a	Py_XDECREF(newitem);
170	n/a	PyErr_SetString(PyExc_IndexError,
171	n/a	"tuple assignment index out of range");
172	n/a	return -1;
173	n/a	}
174	n/a	p = ((PyTupleObject *)op) -> ob_item + i;
175	n/a	Py_XSETREF(*p, newitem);
176	n/a	return 0;
177	n/a	}
178	n/a
179	n/a	void
180	n/a	_PyTuple_MaybeUntrack(PyObject *op)
181	n/a	{
182	n/a	PyTupleObject *t;
183	n/a	Py_ssize_t i, n;
184	n/a
185	n/a	if (!PyTuple_CheckExact(op) \|\| !_PyObject_GC_IS_TRACKED(op))
186	n/a	return;
187	n/a	t = (PyTupleObject *) op;
188	n/a	n = Py_SIZE(t);
189	n/a	for (i = 0; i < n; i++) {
190	n/a	PyObject *elt = PyTuple_GET_ITEM(t, i);
191	n/a	/* Tuple with NULL elements aren't
192	n/a	fully constructed, don't untrack
193	n/a	them yet. */
194	n/a	if (!elt \|\|
195	n/a	_PyObject_GC_MAY_BE_TRACKED(elt))
196	n/a	return;
197	n/a	}
198	n/a	#ifdef SHOW_TRACK_COUNT
199	n/a	count_tracked--;
200	n/a	count_untracked++;
201	n/a	#endif
202	n/a	_PyObject_GC_UNTRACK(op);
203	n/a	}
204	n/a
205	n/a	PyObject *
206	n/a	PyTuple_Pack(Py_ssize_t n, ...)
207	n/a	{
208	n/a	Py_ssize_t i;
209	n/a	PyObject *o;
210	n/a	PyObject *result;
211	n/a	PyObject **items;
212	n/a	va_list vargs;
213	n/a
214	n/a	va_start(vargs, n);
215	n/a	result = PyTuple_New(n);
216	n/a	if (result == NULL) {
217	n/a	va_end(vargs);
218	n/a	return NULL;
219	n/a	}
220	n/a	items = ((PyTupleObject *)result)->ob_item;
221	n/a	for (i = 0; i < n; i++) {
222	n/a	o = va_arg(vargs, PyObject *);
223	n/a	Py_INCREF(o);
224	n/a	items[i] = o;
225	n/a	}
226	n/a	va_end(vargs);
227	n/a	return result;
228	n/a	}
229	n/a
230	n/a
231	n/a	/* Methods */
232	n/a
233	n/a	static void
234	n/a	tupledealloc(PyTupleObject *op)
235	n/a	{
236	n/a	Py_ssize_t i;
237	n/a	Py_ssize_t len = Py_SIZE(op);
238	n/a	PyObject_GC_UnTrack(op);
239	n/a	Py_TRASHCAN_SAFE_BEGIN(op)
240	n/a	if (len > 0) {
241	n/a	i = len;
242	n/a	while (--i >= 0)
243	n/a	Py_XDECREF(op->ob_item[i]);
244	n/a	#if PyTuple_MAXSAVESIZE > 0
245	n/a	if (len < PyTuple_MAXSAVESIZE &&
246	n/a	numfree[len] < PyTuple_MAXFREELIST &&
247	n/a	Py_TYPE(op) == &PyTuple_Type)
248	n/a	{
249	n/a	op->ob_item[0] = (PyObject *) free_list[len];
250	n/a	numfree[len]++;
251	n/a	free_list[len] = op;
252	n/a	goto done; /* return */
253	n/a	}
254	n/a	#endif
255	n/a	}
256	n/a	Py_TYPE(op)->tp_free((PyObject *)op);
257	n/a	done:
258	n/a	Py_TRASHCAN_SAFE_END(op)
259	n/a	}
260	n/a
261	n/a	static PyObject *
262	n/a	tuplerepr(PyTupleObject *v)
263	n/a	{
264	n/a	Py_ssize_t i, n;
265	n/a	_PyUnicodeWriter writer;
266	n/a
267	n/a	n = Py_SIZE(v);
268	n/a	if (n == 0)
269	n/a	return PyUnicode_FromString("()");
270	n/a
271	n/a	/* While not mutable, it is still possible to end up with a cycle in a
272	n/a	tuple through an object that stores itself within a tuple (and thus
273	n/a	infinitely asks for the repr of itself). This should only be
274	n/a	possible within a type. */
275	n/a	i = Py_ReprEnter((PyObject *)v);
276	n/a	if (i != 0) {
277	n/a	return i > 0 ? PyUnicode_FromString("(...)") : NULL;
278	n/a	}
279	n/a
280	n/a	_PyUnicodeWriter_Init(&writer);
281	n/a	writer.overallocate = 1;
282	n/a	if (Py_SIZE(v) > 1) {
283	n/a	/* "(" + "1" + ", 2" * (len - 1) + ")" */
284	n/a	writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
285	n/a	}
286	n/a	else {
287	n/a	/* "(1,)" */
288	n/a	writer.min_length = 4;
289	n/a	}
290	n/a
291	n/a	if (_PyUnicodeWriter_WriteChar(&writer, '(') < 0)
292	n/a	goto error;
293	n/a
294	n/a	/* Do repr() on each element. */
295	n/a	for (i = 0; i < n; ++i) {
296	n/a	PyObject *s;
297	n/a
298	n/a	if (i > 0) {
299	n/a	if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
300	n/a	goto error;
301	n/a	}
302	n/a
303	n/a	if (Py_EnterRecursiveCall(" while getting the repr of a tuple"))
304	n/a	goto error;
305	n/a	s = PyObject_Repr(v->ob_item[i]);
306	n/a	Py_LeaveRecursiveCall();
307	n/a	if (s == NULL)
308	n/a	goto error;
309	n/a
310	n/a	if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
311	n/a	Py_DECREF(s);
312	n/a	goto error;
313	n/a	}
314	n/a	Py_DECREF(s);
315	n/a	}
316	n/a
317	n/a	writer.overallocate = 0;
318	n/a	if (n > 1) {
319	n/a	if (_PyUnicodeWriter_WriteChar(&writer, ')') < 0)
320	n/a	goto error;
321	n/a	}
322	n/a	else {
323	n/a	if (_PyUnicodeWriter_WriteASCIIString(&writer, ",)", 2) < 0)
324	n/a	goto error;
325	n/a	}
326	n/a
327	n/a	Py_ReprLeave((PyObject *)v);
328	n/a	return _PyUnicodeWriter_Finish(&writer);
329	n/a
330	n/a	error:
331	n/a	_PyUnicodeWriter_Dealloc(&writer);
332	n/a	Py_ReprLeave((PyObject *)v);
333	n/a	return NULL;
334	n/a	}
335	n/a
336	n/a	/* The addend 82520, was selected from the range(0, 1000000) for
337	n/a	generating the greatest number of prime multipliers for tuples
338	n/a	upto length eight:
339	n/a
340	n/a	1082527, 1165049, 1082531, 1165057, 1247581, 1330103, 1082533,
341	n/a	1330111, 1412633, 1165069, 1247599, 1495177, 1577699
342	n/a
343	n/a	Tests have shown that it's not worth to cache the hash value, see
344	n/a	issue #9685.
345	n/a	*/
346	n/a
347	n/a	static Py_hash_t
348	n/a	tuplehash(PyTupleObject *v)
349	n/a	{
350	n/a	Py_uhash_t x; /* Unsigned for defined overflow behavior. */
351	n/a	Py_hash_t y;
352	n/a	Py_ssize_t len = Py_SIZE(v);
353	n/a	PyObject **p;
354	n/a	Py_uhash_t mult = _PyHASH_MULTIPLIER;
355	n/a	x = 0x345678UL;
356	n/a	p = v->ob_item;
357	n/a	while (--len >= 0) {
358	n/a	y = PyObject_Hash(*p++);
359	n/a	if (y == -1)
360	n/a	return -1;
361	n/a	x = (x ^ y) * mult;
362	n/a	/* the cast might truncate len; that doesn't change hash stability */
363	n/a	mult += (Py_hash_t)(82520UL + len + len);
364	n/a	}
365	n/a	x += 97531UL;
366	n/a	if (x == (Py_uhash_t)-1)
367	n/a	x = -2;
368	n/a	return x;
369	n/a	}
370	n/a
371	n/a	static Py_ssize_t
372	n/a	tuplelength(PyTupleObject *a)
373	n/a	{
374	n/a	return Py_SIZE(a);
375	n/a	}
376	n/a
377	n/a	static int
378	n/a	tuplecontains(PyTupleObject a, PyObject el)
379	n/a	{
380	n/a	Py_ssize_t i;
381	n/a	int cmp;
382	n/a
383	n/a	for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
384	n/a	cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
385	n/a	Py_EQ);
386	n/a	return cmp;
387	n/a	}
388	n/a
389	n/a	static PyObject *
390	n/a	tupleitem(PyTupleObject *a, Py_ssize_t i)
391	n/a	{
392	n/a	if (i < 0 \|\| i >= Py_SIZE(a)) {
393	n/a	PyErr_SetString(PyExc_IndexError, "tuple index out of range");
394	n/a	return NULL;
395	n/a	}
396	n/a	Py_INCREF(a->ob_item[i]);
397	n/a	return a->ob_item[i];
398	n/a	}
399	n/a
400	n/a	static PyObject *
401	n/a	tupleslice(PyTupleObject *a, Py_ssize_t ilow,
402	n/a	Py_ssize_t ihigh)
403	n/a	{
404	n/a	PyTupleObject *np;
405	n/a	PyObject src, dest;
406	n/a	Py_ssize_t i;
407	n/a	Py_ssize_t len;
408	n/a	if (ilow < 0)
409	n/a	ilow = 0;
410	n/a	if (ihigh > Py_SIZE(a))
411	n/a	ihigh = Py_SIZE(a);
412	n/a	if (ihigh < ilow)
413	n/a	ihigh = ilow;
414	n/a	if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {
415	n/a	Py_INCREF(a);
416	n/a	return (PyObject *)a;
417	n/a	}
418	n/a	len = ihigh - ilow;
419	n/a	np = (PyTupleObject *)PyTuple_New(len);
420	n/a	if (np == NULL)
421	n/a	return NULL;
422	n/a	src = a->ob_item + ilow;
423	n/a	dest = np->ob_item;
424	n/a	for (i = 0; i < len; i++) {
425	n/a	PyObject *v = src[i];
426	n/a	Py_INCREF(v);
427	n/a	dest[i] = v;
428	n/a	}
429	n/a	return (PyObject *)np;
430	n/a	}
431	n/a
432	n/a	PyObject *
433	n/a	PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
434	n/a	{
435	n/a	if (op == NULL \|\| !PyTuple_Check(op)) {
436	n/a	PyErr_BadInternalCall();
437	n/a	return NULL;
438	n/a	}
439	n/a	return tupleslice((PyTupleObject *)op, i, j);
440	n/a	}
441	n/a
442	n/a	static PyObject *
443	n/a	tupleconcat(PyTupleObject a, PyObject bb)
444	n/a	{
445	n/a	Py_ssize_t size;
446	n/a	Py_ssize_t i;
447	n/a	PyObject src, dest;
448	n/a	PyTupleObject *np;
449	n/a	if (!PyTuple_Check(bb)) {
450	n/a	PyErr_Format(PyExc_TypeError,
451	n/a	"can only concatenate tuple (not \"%.200s\") to tuple",
452	n/a	Py_TYPE(bb)->tp_name);
453	n/a	return NULL;
454	n/a	}
455	n/a	#define b ((PyTupleObject *)bb)
456	n/a	if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))
457	n/a	return PyErr_NoMemory();
458	n/a	size = Py_SIZE(a) + Py_SIZE(b);
459	n/a	np = (PyTupleObject *) PyTuple_New(size);
460	n/a	if (np == NULL) {
461	n/a	return NULL;
462	n/a	}
463	n/a	src = a->ob_item;
464	n/a	dest = np->ob_item;
465	n/a	for (i = 0; i < Py_SIZE(a); i++) {
466	n/a	PyObject *v = src[i];
467	n/a	Py_INCREF(v);
468	n/a	dest[i] = v;
469	n/a	}
470	n/a	src = b->ob_item;
471	n/a	dest = np->ob_item + Py_SIZE(a);
472	n/a	for (i = 0; i < Py_SIZE(b); i++) {
473	n/a	PyObject *v = src[i];
474	n/a	Py_INCREF(v);
475	n/a	dest[i] = v;
476	n/a	}
477	n/a	return (PyObject *)np;
478	n/a	#undef b
479	n/a	}
480	n/a
481	n/a	static PyObject *
482	n/a	tuplerepeat(PyTupleObject *a, Py_ssize_t n)
483	n/a	{
484	n/a	Py_ssize_t i, j;
485	n/a	Py_ssize_t size;
486	n/a	PyTupleObject *np;
487	n/a	PyObject p, items;
488	n/a	if (n < 0)
489	n/a	n = 0;
490	n/a	if (Py_SIZE(a) == 0 \|\| n == 1) {
491	n/a	if (PyTuple_CheckExact(a)) {
492	n/a	/* Since tuples are immutable, we can return a shared
493	n/a	copy in this case */
494	n/a	Py_INCREF(a);
495	n/a	return (PyObject *)a;
496	n/a	}
497	n/a	if (Py_SIZE(a) == 0)
498	n/a	return PyTuple_New(0);
499	n/a	}
500	n/a	if (n > PY_SSIZE_T_MAX / Py_SIZE(a))
501	n/a	return PyErr_NoMemory();
502	n/a	size = Py_SIZE(a) * n;
503	n/a	np = (PyTupleObject *) PyTuple_New(size);
504	n/a	if (np == NULL)
505	n/a	return NULL;
506	n/a	p = np->ob_item;
507	n/a	items = a->ob_item;
508	n/a	for (i = 0; i < n; i++) {
509	n/a	for (j = 0; j < Py_SIZE(a); j++) {
510	n/a	*p = items[j];
511	n/a	Py_INCREF(*p);
512	n/a	p++;
513	n/a	}
514	n/a	}
515	n/a	return (PyObject *) np;
516	n/a	}
517	n/a
518	n/a	static PyObject *
519	n/a	tupleindex(PyTupleObject self, PyObject args)
520	n/a	{
521	n/a	Py_ssize_t i, start=0, stop=Py_SIZE(self);
522	n/a	PyObject *v;
523	n/a
524	n/a	if (!PyArg_ParseTuple(args, "O\|O&O&:index", &v,
525	n/a	_PyEval_SliceIndex, &start,
526	n/a	_PyEval_SliceIndex, &stop))
527	n/a	return NULL;
528	n/a	if (start < 0) {
529	n/a	start += Py_SIZE(self);
530	n/a	if (start < 0)
531	n/a	start = 0;
532	n/a	}
533	n/a	if (stop < 0) {
534	n/a	stop += Py_SIZE(self);
535	n/a	if (stop < 0)
536	n/a	stop = 0;
537	n/a	}
538	n/a	for (i = start; i < stop && i < Py_SIZE(self); i++) {
539	n/a	int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
540	n/a	if (cmp > 0)
541	n/a	return PyLong_FromSsize_t(i);
542	n/a	else if (cmp < 0)
543	n/a	return NULL;
544	n/a	}
545	n/a	PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");
546	n/a	return NULL;
547	n/a	}
548	n/a
549	n/a	static PyObject *
550	n/a	tuplecount(PyTupleObject self, PyObject v)
551	n/a	{
552	n/a	Py_ssize_t count = 0;
553	n/a	Py_ssize_t i;
554	n/a
555	n/a	for (i = 0; i < Py_SIZE(self); i++) {
556	n/a	int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
557	n/a	if (cmp > 0)
558	n/a	count++;
559	n/a	else if (cmp < 0)
560	n/a	return NULL;
561	n/a	}
562	n/a	return PyLong_FromSsize_t(count);
563	n/a	}
564	n/a
565	n/a	static int
566	n/a	tupletraverse(PyTupleObject o, visitproc visit, void arg)
567	n/a	{
568	n/a	Py_ssize_t i;
569	n/a
570	n/a	for (i = Py_SIZE(o); --i >= 0; )
571	n/a	Py_VISIT(o->ob_item[i]);
572	n/a	return 0;
573	n/a	}
574	n/a
575	n/a	static PyObject *
576	n/a	tuplerichcompare(PyObject v, PyObject w, int op)
577	n/a	{
578	n/a	PyTupleObject vt, wt;
579	n/a	Py_ssize_t i;
580	n/a	Py_ssize_t vlen, wlen;
581	n/a
582	n/a	if (!PyTuple_Check(v) \|\| !PyTuple_Check(w))
583	n/a	Py_RETURN_NOTIMPLEMENTED;
584	n/a
585	n/a	vt = (PyTupleObject *)v;
586	n/a	wt = (PyTupleObject *)w;
587	n/a
588	n/a	vlen = Py_SIZE(vt);
589	n/a	wlen = Py_SIZE(wt);
590	n/a
591	n/a	/* Note: the corresponding code for lists has an "early out" test
592	n/a	* here when op is EQ or NE and the lengths differ. That pays there,
593	n/a	* but Tim was unable to find any real code where EQ/NE tuple
594	n/a	* compares don't have the same length, so testing for it here would
595	n/a	* have cost without benefit.
596	n/a	*/
597	n/a
598	n/a	/* Search for the first index where items are different.
599	n/a	* Note that because tuples are immutable, it's safe to reuse
600	n/a	* vlen and wlen across the comparison calls.
601	n/a	*/
602	n/a	for (i = 0; i < vlen && i < wlen; i++) {
603	n/a	int k = PyObject_RichCompareBool(vt->ob_item[i],
604	n/a	wt->ob_item[i], Py_EQ);
605	n/a	if (k < 0)
606	n/a	return NULL;
607	n/a	if (!k)
608	n/a	break;
609	n/a	}
610	n/a
611	n/a	if (i >= vlen \|\| i >= wlen) {
612	n/a	/* No more items to compare -- compare sizes */
613	n/a	int cmp;
614	n/a	PyObject *res;
615	n/a	switch (op) {
616	n/a	case Py_LT: cmp = vlen < wlen; break;
617	n/a	case Py_LE: cmp = vlen <= wlen; break;
618	n/a	case Py_EQ: cmp = vlen == wlen; break;
619	n/a	case Py_NE: cmp = vlen != wlen; break;
620	n/a	case Py_GT: cmp = vlen > wlen; break;
621	n/a	case Py_GE: cmp = vlen >= wlen; break;
622	n/a	default: return NULL; /* cannot happen */
623	n/a	}
624	n/a	if (cmp)
625	n/a	res = Py_True;
626	n/a	else
627	n/a	res = Py_False;
628	n/a	Py_INCREF(res);
629	n/a	return res;
630	n/a	}
631	n/a
632	n/a	/* We have an item that differs -- shortcuts for EQ/NE */
633	n/a	if (op == Py_EQ) {
634	n/a	Py_RETURN_FALSE;
635	n/a	}
636	n/a	if (op == Py_NE) {
637	n/a	Py_RETURN_TRUE;
638	n/a	}
639	n/a
640	n/a	/* Compare the final item again using the proper operator */
641	n/a	return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
642	n/a	}
643	n/a
644	n/a	static PyObject *
645	n/a	tuple_subtype_new(PyTypeObject type, PyObject args, PyObject *kwds);
646	n/a
647	n/a	static PyObject *
648	n/a	tuple_new(PyTypeObject type, PyObject args, PyObject *kwds)
649	n/a	{
650	n/a	PyObject *arg = NULL;
651	n/a	static char *kwlist[] = {"sequence", 0};
652	n/a
653	n/a	if (type != &PyTuple_Type)
654	n/a	return tuple_subtype_new(type, args, kwds);
655	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "\|O:tuple", kwlist, &arg))
656	n/a	return NULL;
657	n/a
658	n/a	if (arg == NULL)
659	n/a	return PyTuple_New(0);
660	n/a	else
661	n/a	return PySequence_Tuple(arg);
662	n/a	}
663	n/a
664	n/a	static PyObject *
665	n/a	tuple_subtype_new(PyTypeObject type, PyObject args, PyObject *kwds)
666	n/a	{
667	n/a	PyObject tmp, newobj, *item;
668	n/a	Py_ssize_t i, n;
669	n/a
670	n/a	assert(PyType_IsSubtype(type, &PyTuple_Type));
671	n/a	tmp = tuple_new(&PyTuple_Type, args, kwds);
672	n/a	if (tmp == NULL)
673	n/a	return NULL;
674	n/a	assert(PyTuple_Check(tmp));
675	n/a	newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
676	n/a	if (newobj == NULL)
677	n/a	return NULL;
678	n/a	for (i = 0; i < n; i++) {
679	n/a	item = PyTuple_GET_ITEM(tmp, i);
680	n/a	Py_INCREF(item);
681	n/a	PyTuple_SET_ITEM(newobj, i, item);
682	n/a	}
683	n/a	Py_DECREF(tmp);
684	n/a	return newobj;
685	n/a	}
686	n/a
687	n/a	PyDoc_STRVAR(tuple_doc,
688	n/a	"tuple() -> empty tuple\n\
689	n/a	tuple(iterable) -> tuple initialized from iterable's items\n\
690	n/a	\n\
691	n/a	If the argument is a tuple, the return value is the same object.");
692	n/a
693	n/a	static PySequenceMethods tuple_as_sequence = {
694	n/a	(lenfunc)tuplelength, /* sq_length */
695	n/a	(binaryfunc)tupleconcat, /* sq_concat */
696	n/a	(ssizeargfunc)tuplerepeat, /* sq_repeat */
697	n/a	(ssizeargfunc)tupleitem, /* sq_item */
698	n/a	0, /* sq_slice */
699	n/a	0, /* sq_ass_item */
700	n/a	0, /* sq_ass_slice */
701	n/a	(objobjproc)tuplecontains, /* sq_contains */
702	n/a	};
703	n/a
704	n/a	static PyObject*
705	n/a	tuplesubscript(PyTupleObject* self, PyObject* item)
706	n/a	{
707	n/a	if (PyIndex_Check(item)) {
708	n/a	Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
709	n/a	if (i == -1 && PyErr_Occurred())
710	n/a	return NULL;
711	n/a	if (i < 0)
712	n/a	i += PyTuple_GET_SIZE(self);
713	n/a	return tupleitem(self, i);
714	n/a	}
715	n/a	else if (PySlice_Check(item)) {
716	n/a	Py_ssize_t start, stop, step, slicelength, cur, i;
717	n/a	PyObject* result;
718	n/a	PyObject* it;
719	n/a	PyObject src, dest;
720	n/a
721	n/a	if (PySlice_GetIndicesEx(item,
722	n/a	PyTuple_GET_SIZE(self),
723	n/a	&start, &stop, &step, &slicelength) < 0) {
724	n/a	return NULL;
725	n/a	}
726	n/a
727	n/a	if (slicelength <= 0) {
728	n/a	return PyTuple_New(0);
729	n/a	}
730	n/a	else if (start == 0 && step == 1 &&
731	n/a	slicelength == PyTuple_GET_SIZE(self) &&
732	n/a	PyTuple_CheckExact(self)) {
733	n/a	Py_INCREF(self);
734	n/a	return (PyObject *)self;
735	n/a	}
736	n/a	else {
737	n/a	result = PyTuple_New(slicelength);
738	n/a	if (!result) return NULL;
739	n/a
740	n/a	src = self->ob_item;
741	n/a	dest = ((PyTupleObject *)result)->ob_item;
742	n/a	for (cur = start, i = 0; i < slicelength;
743	n/a	cur += step, i++) {
744	n/a	it = src[cur];
745	n/a	Py_INCREF(it);
746	n/a	dest[i] = it;
747	n/a	}
748	n/a
749	n/a	return result;
750	n/a	}
751	n/a	}
752	n/a	else {
753	n/a	PyErr_Format(PyExc_TypeError,
754	n/a	"tuple indices must be integers or slices, not %.200s",
755	n/a	Py_TYPE(item)->tp_name);
756	n/a	return NULL;
757	n/a	}
758	n/a	}
759	n/a
760	n/a	static PyObject *
761	n/a	tuple_getnewargs(PyTupleObject *v)
762	n/a	{
763	n/a	return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));
764	n/a
765	n/a	}
766	n/a
767	n/a	PyDoc_STRVAR(index_doc,
768	n/a	"T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
769	n/a	"Raises ValueError if the value is not present."
770	n/a	);
771	n/a	PyDoc_STRVAR(count_doc,
772	n/a	"T.count(value) -> integer -- return number of occurrences of value");
773	n/a
774	n/a	static PyMethodDef tuple_methods[] = {
775	n/a	{"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},
776	n/a	{"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},
777	n/a	{"count", (PyCFunction)tuplecount, METH_O, count_doc},
778	n/a	{NULL, NULL} /* sentinel */
779	n/a	};
780	n/a
781	n/a	static PyMappingMethods tuple_as_mapping = {
782	n/a	(lenfunc)tuplelength,
783	n/a	(binaryfunc)tuplesubscript,
784	n/a	0
785	n/a	};
786	n/a
787	n/a	static PyObject tuple_iter(PyObject seq);
788	n/a
789	n/a	PyTypeObject PyTuple_Type = {
790	n/a	PyVarObject_HEAD_INIT(&PyType_Type, 0)
791	n/a	"tuple",
792	n/a	sizeof(PyTupleObject) - sizeof(PyObject *),
793	n/a	sizeof(PyObject *),
794	n/a	(destructor)tupledealloc, /* tp_dealloc */
795	n/a	0, /* tp_print */
796	n/a	0, /* tp_getattr */
797	n/a	0, /* tp_setattr */
798	n/a	0, /* tp_reserved */
799	n/a	(reprfunc)tuplerepr, /* tp_repr */
800	n/a	0, /* tp_as_number */
801	n/a	&tuple_as_sequence, /* tp_as_sequence */
802	n/a	&tuple_as_mapping, /* tp_as_mapping */
803	n/a	(hashfunc)tuplehash, /* tp_hash */
804	n/a	0, /* tp_call */
805	n/a	0, /* tp_str */
806	n/a	PyObject_GenericGetAttr, /* tp_getattro */
807	n/a	0, /* tp_setattro */
808	n/a	0, /* tp_as_buffer */
809	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
810	n/a	Py_TPFLAGS_BASETYPE \| Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */
811	n/a	tuple_doc, /* tp_doc */
812	n/a	(traverseproc)tupletraverse, /* tp_traverse */
813	n/a	0, /* tp_clear */
814	n/a	tuplerichcompare, /* tp_richcompare */
815	n/a	0, /* tp_weaklistoffset */
816	n/a	tuple_iter, /* tp_iter */
817	n/a	0, /* tp_iternext */
818	n/a	tuple_methods, /* tp_methods */
819	n/a	0, /* tp_members */
820	n/a	0, /* tp_getset */
821	n/a	0, /* tp_base */
822	n/a	0, /* tp_dict */
823	n/a	0, /* tp_descr_get */
824	n/a	0, /* tp_descr_set */
825	n/a	0, /* tp_dictoffset */
826	n/a	0, /* tp_init */
827	n/a	0, /* tp_alloc */
828	n/a	tuple_new, /* tp_new */
829	n/a	PyObject_GC_Del, /* tp_free */
830	n/a	};
831	n/a
832	n/a	/* The following function breaks the notion that tuples are immutable:
833	n/a	it changes the size of a tuple. We get away with this only if there
834	n/a	is only one module referencing the object. You can also think of it
835	n/a	as creating a new tuple object and destroying the old one, only more
836	n/a	efficiently. In any case, don't use this if the tuple may already be
837	n/a	known to some other part of the code. */
838	n/a
839	n/a	int
840	n/a	_PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
841	n/a	{
842	n/a	PyTupleObject *v;
843	n/a	PyTupleObject *sv;
844	n/a	Py_ssize_t i;
845	n/a	Py_ssize_t oldsize;
846	n/a
847	n/a	v = (PyTupleObject ) pv;
848	n/a	if (v == NULL \|\| Py_TYPE(v) != &PyTuple_Type \|\|
849	n/a	(Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
850	n/a	*pv = 0;
851	n/a	Py_XDECREF(v);
852	n/a	PyErr_BadInternalCall();
853	n/a	return -1;
854	n/a	}
855	n/a	oldsize = Py_SIZE(v);
856	n/a	if (oldsize == newsize)
857	n/a	return 0;
858	n/a
859	n/a	if (oldsize == 0) {
860	n/a	/* Empty tuples are often shared, so we should never
861	n/a	resize them in-place even if we do own the only
862	n/a	(current) reference */
863	n/a	Py_DECREF(v);
864	n/a	*pv = PyTuple_New(newsize);
865	n/a	return *pv == NULL ? -1 : 0;
866	n/a	}
867	n/a
868	n/a	/* XXX UNREF/NEWREF interface should be more symmetrical */
869	n/a	_Py_DEC_REFTOTAL;
870	n/a	if (_PyObject_GC_IS_TRACKED(v))
871	n/a	_PyObject_GC_UNTRACK(v);
872	n/a	_Py_ForgetReference((PyObject *) v);
873	n/a	/* DECREF items deleted by shrinkage */
874	n/a	for (i = newsize; i < oldsize; i++) {
875	n/a	Py_CLEAR(v->ob_item[i]);
876	n/a	}
877	n/a	sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
878	n/a	if (sv == NULL) {
879	n/a	*pv = NULL;
880	n/a	PyObject_GC_Del(v);
881	n/a	return -1;
882	n/a	}
883	n/a	_Py_NewReference((PyObject *) sv);
884	n/a	/* Zero out items added by growing */
885	n/a	if (newsize > oldsize)
886	n/a	memset(&sv->ob_item[oldsize], 0,
887	n/a	sizeof(sv->ob_item) (newsize - oldsize));
888	n/a	pv = (PyObject ) sv;
889	n/a	_PyObject_GC_TRACK(sv);
890	n/a	return 0;
891	n/a	}
892	n/a
893	n/a	int
894	n/a	PyTuple_ClearFreeList(void)
895	n/a	{
896	n/a	int freelist_size = 0;
897	n/a	#if PyTuple_MAXSAVESIZE > 0
898	n/a	int i;
899	n/a	for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
900	n/a	PyTupleObject p, q;
901	n/a	p = free_list[i];
902	n/a	freelist_size += numfree[i];
903	n/a	free_list[i] = NULL;
904	n/a	numfree[i] = 0;
905	n/a	while (p) {
906	n/a	q = p;
907	n/a	p = (PyTupleObject *)(p->ob_item[0]);
908	n/a	PyObject_GC_Del(q);
909	n/a	}
910	n/a	}
911	n/a	#endif
912	n/a	return freelist_size;
913	n/a	}
914	n/a
915	n/a	void
916	n/a	PyTuple_Fini(void)
917	n/a	{
918	n/a	#if PyTuple_MAXSAVESIZE > 0
919	n/a	/* empty tuples are used all over the place and applications may
920	n/a	* rely on the fact that an empty tuple is a singleton. */
921	n/a	Py_CLEAR(free_list[0]);
922	n/a
923	n/a	(void)PyTuple_ClearFreeList();
924	n/a	#endif
925	n/a	#ifdef SHOW_TRACK_COUNT
926	n/a	show_track();
927	n/a	#endif
928	n/a	}
929	n/a
930	n/a	/********************* Tuple Iterator ************************/
931	n/a
932	n/a	typedef struct {
933	n/a	PyObject_HEAD
934	n/a	Py_ssize_t it_index;
935	n/a	PyTupleObject it_seq; / Set to NULL when iterator is exhausted */
936	n/a	} tupleiterobject;
937	n/a
938	n/a	static void
939	n/a	tupleiter_dealloc(tupleiterobject *it)
940	n/a	{
941	n/a	_PyObject_GC_UNTRACK(it);
942	n/a	Py_XDECREF(it->it_seq);
943	n/a	PyObject_GC_Del(it);
944	n/a	}
945	n/a
946	n/a	static int
947	n/a	tupleiter_traverse(tupleiterobject it, visitproc visit, void arg)
948	n/a	{
949	n/a	Py_VISIT(it->it_seq);
950	n/a	return 0;
951	n/a	}
952	n/a
953	n/a	static PyObject *
954	n/a	tupleiter_next(tupleiterobject *it)
955	n/a	{
956	n/a	PyTupleObject *seq;
957	n/a	PyObject *item;
958	n/a
959	n/a	assert(it != NULL);
960	n/a	seq = it->it_seq;
961	n/a	if (seq == NULL)
962	n/a	return NULL;
963	n/a	assert(PyTuple_Check(seq));
964	n/a
965	n/a	if (it->it_index < PyTuple_GET_SIZE(seq)) {
966	n/a	item = PyTuple_GET_ITEM(seq, it->it_index);
967	n/a	++it->it_index;
968	n/a	Py_INCREF(item);
969	n/a	return item;
970	n/a	}
971	n/a
972	n/a	it->it_seq = NULL;
973	n/a	Py_DECREF(seq);
974	n/a	return NULL;
975	n/a	}
976	n/a
977	n/a	static PyObject *
978	n/a	tupleiter_len(tupleiterobject *it)
979	n/a	{
980	n/a	Py_ssize_t len = 0;
981	n/a	if (it->it_seq)
982	n/a	len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
983	n/a	return PyLong_FromSsize_t(len);
984	n/a	}
985	n/a
986	n/a	PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
987	n/a
988	n/a	static PyObject *
989	n/a	tupleiter_reduce(tupleiterobject *it)
990	n/a	{
991	n/a	if (it->it_seq)
992	n/a	return Py_BuildValue("N(O)n", _PyObject_GetBuiltin("iter"),
993	n/a	it->it_seq, it->it_index);
994	n/a	else
995	n/a	return Py_BuildValue("N(())", _PyObject_GetBuiltin("iter"));
996	n/a	}
997	n/a
998	n/a	static PyObject *
999	n/a	tupleiter_setstate(tupleiterobject it, PyObject state)
1000	n/a	{
1001	n/a	Py_ssize_t index = PyLong_AsSsize_t(state);
1002	n/a	if (index == -1 && PyErr_Occurred())
1003	n/a	return NULL;
1004	n/a	if (it->it_seq != NULL) {
1005	n/a	if (index < 0)
1006	n/a	index = 0;
1007	n/a	else if (index > PyTuple_GET_SIZE(it->it_seq))
1008	n/a	index = PyTuple_GET_SIZE(it->it_seq); /* exhausted iterator */
1009	n/a	it->it_index = index;
1010	n/a	}
1011	n/a	Py_RETURN_NONE;
1012	n/a	}
1013	n/a
1014	n/a	PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1015	n/a	PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
1016	n/a
1017	n/a	static PyMethodDef tupleiter_methods[] = {
1018	n/a	{"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
1019	n/a	{"__reduce__", (PyCFunction)tupleiter_reduce, METH_NOARGS, reduce_doc},
1020	n/a	{"__setstate__", (PyCFunction)tupleiter_setstate, METH_O, setstate_doc},
1021	n/a	{NULL, NULL} /* sentinel */
1022	n/a	};
1023	n/a
1024	n/a	PyTypeObject PyTupleIter_Type = {
1025	n/a	PyVarObject_HEAD_INIT(&PyType_Type, 0)
1026	n/a	"tuple_iterator", /* tp_name */
1027	n/a	sizeof(tupleiterobject), /* tp_basicsize */
1028	n/a	0, /* tp_itemsize */
1029	n/a	/* methods */
1030	n/a	(destructor)tupleiter_dealloc, /* tp_dealloc */
1031	n/a	0, /* tp_print */
1032	n/a	0, /* tp_getattr */
1033	n/a	0, /* tp_setattr */
1034	n/a	0, /* tp_reserved */
1035	n/a	0, /* tp_repr */
1036	n/a	0, /* tp_as_number */
1037	n/a	0, /* tp_as_sequence */
1038	n/a	0, /* tp_as_mapping */
1039	n/a	0, /* tp_hash */
1040	n/a	0, /* tp_call */
1041	n/a	0, /* tp_str */
1042	n/a	PyObject_GenericGetAttr, /* tp_getattro */
1043	n/a	0, /* tp_setattro */
1044	n/a	0, /* tp_as_buffer */
1045	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC,/* tp_flags */
1046	n/a	0, /* tp_doc */
1047	n/a	(traverseproc)tupleiter_traverse, /* tp_traverse */
1048	n/a	0, /* tp_clear */
1049	n/a	0, /* tp_richcompare */
1050	n/a	0, /* tp_weaklistoffset */
1051	n/a	PyObject_SelfIter, /* tp_iter */
1052	n/a	(iternextfunc)tupleiter_next, /* tp_iternext */
1053	n/a	tupleiter_methods, /* tp_methods */
1054	n/a	0,
1055	n/a	};
1056	n/a
1057	n/a	static PyObject *
1058	n/a	tuple_iter(PyObject *seq)
1059	n/a	{
1060	n/a	tupleiterobject *it;
1061	n/a
1062	n/a	if (!PyTuple_Check(seq)) {
1063	n/a	PyErr_BadInternalCall();
1064	n/a	return NULL;
1065	n/a	}
1066	n/a	it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1067	n/a	if (it == NULL)
1068	n/a	return NULL;
1069	n/a	it->it_index = 0;
1070	n/a	Py_INCREF(seq);
1071	n/a	it->it_seq = (PyTupleObject *)seq;
1072	n/a	_PyObject_GC_TRACK(it);
1073	n/a	return (PyObject *)it;
1074	n/a	}