← Back to branch summary

~ubuntu-branches/ubuntu/maverick/python3.1/maverick

« back to all changes in this revision

Viewing changes to Objects/tupleobject.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-03-23 00:01:27 UTC
  • Revision ID: james.westby@ubuntu.com-20090323000127-5fstfxju4ufrhthq
Tags: upstream-3.1~a1+20090322
Import upstream version 3.1~a1+20090322

Show diffs side-by-side

added added

removed removed

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