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