ยปCore Development>Code coverage>Objects/tupleobject.c

Python code coverage for Objects/tupleobject.c

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