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