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         PyObject *x;
 442
 443         for (i = o->ob_size; --i >= 0; ) {
 444                 x = o->ob_item[i];
 445                 if (x != NULL) {
 446                         int err = visit(x, arg);
 447                         if (err)
 448                                 return err;
 449                 }
 450         }
 451         return 0;
 452 }
 453
 454 static PyObject *
 455 tuplerichcompare(PyObject *v, PyObject *w, int op)
 456 {
 457         PyTupleObject *vt, *wt;
 458         Py_ssize_t i;
 459         Py_ssize_t vlen, wlen;
 460
 461         if (!PyTuple_Check(v) || !PyTuple_Check(w)) {
 462                 Py_INCREF(Py_NotImplemented);
 463                 return Py_NotImplemented;
 464         }
 465
 466         vt = (PyTupleObject *)v;
 467         wt = (PyTupleObject *)w;
 468
 469         vlen = vt->ob_size;
 470         wlen = wt->ob_size;
 471
 472         /* Note:  the corresponding code for lists has an "early out" test
 473          * here when op is EQ or NE and the lengths differ.  That pays there,
 474          * but Tim was unable to find any real code where EQ/NE tuple
 475          * compares don't have the same length, so testing for it here would
 476          * have cost without benefit.
 477          */
 478
 479         /* Search for the first index where items are different.
 480          * Note that because tuples are immutable, it's safe to reuse
 481          * vlen and wlen across the comparison calls.
 482          */
 483         for (i = 0; i < vlen && i < wlen; i++) {
 484                 int k = PyObject_RichCompareBool(vt->ob_item[i],
 485                                                  wt->ob_item[i], Py_EQ);
 486                 if (k < 0)
 487                         return NULL;
 488                 if (!k)
 489                         break;
 490         }
 491
 492         if (i >= vlen || i >= wlen) {
 493                 /* No more items to compare -- compare sizes */
 494                 int cmp;
 495                 PyObject *res;
 496                 switch (op) {
 497                 case Py_LT: cmp = vlen <  wlen; break;
 498                 case Py_LE: cmp = vlen <= wlen; break;
 499                 case Py_EQ: cmp = vlen == wlen; break;
 500                 case Py_NE: cmp = vlen != wlen; break;
 501                 case Py_GT: cmp = vlen >  wlen; break;
 502                 case Py_GE: cmp = vlen >= wlen; break;
 503                 default: return NULL; /* cannot happen */
 504                 }
 505                 if (cmp)
 506                         res = Py_True;
 507                 else
 508                         res = Py_False;
 509                 Py_INCREF(res);
 510                 return res;
 511         }
 512
 513         /* We have an item that differs -- shortcuts for EQ/NE */
 514         if (op == Py_EQ) {
 515                 Py_INCREF(Py_False);
 516                 return Py_False;
 517         }
 518         if (op == Py_NE) {
 519                 Py_INCREF(Py_True);
 520                 return Py_True;
 521         }
 522
 523         /* Compare the final item again using the proper operator */
 524         return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
 525 }
 526
 527 static PyObject *
 528 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
 529
 530 static PyObject *
 531 tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 532 {
 533         PyObject *arg = NULL;
 534         static char *kwlist[] = {"sequence", 0};
 535
 536         if (type != &PyTuple_Type)
 537                 return tuple_subtype_new(type, args, kwds);
 538         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))
 539                 return NULL;
 540
 541         if (arg == NULL)
 542                 return PyTuple_New(0);
 543         else
 544                 return PySequence_Tuple(arg);
 545 }
 546
 547 static PyObject *
 548 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 549 {
 550         PyObject *tmp, *new, *item;
 551         Py_ssize_t i, n;
 552
 553         assert(PyType_IsSubtype(type, &PyTuple_Type));
 554         tmp = tuple_new(&PyTuple_Type, args, kwds);
 555         if (tmp == NULL)
 556                 return NULL;
 557         assert(PyTuple_Check(tmp));
 558         new = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
 559         if (new == NULL)
 560                 return NULL;
 561         for (i = 0; i < n; i++) {
 562                 item = PyTuple_GET_ITEM(tmp, i);
 563                 Py_INCREF(item);
 564                 PyTuple_SET_ITEM(new, i, item);
 565         }
 566         Py_DECREF(tmp);
 567         return new;
 568 }
 569
 570 PyDoc_STRVAR(tuple_doc,
 571 "tuple() -> an empty tuple\n"
 572 "tuple(sequence) -> tuple initialized from sequence's items\n"
 573 "\n"
 574 "If the argument is a tuple, the return value is the same object.");
 575
 576 static PySequenceMethods tuple_as_sequence = {
 577         (lenfunc)tuplelength,                   /* sq_length */
 578         (binaryfunc)tupleconcat,                /* sq_concat */
 579         (ssizeargfunc)tuplerepeat,              /* sq_repeat */
 580         (ssizeargfunc)tupleitem,                /* sq_item */
 581         (ssizessizeargfunc)tupleslice,          /* sq_slice */
 582         0,                                      /* sq_ass_item */
 583         0,                                      /* sq_ass_slice */
 584         (objobjproc)tuplecontains,              /* sq_contains */
 585 };
 586
 587 #define HASINDEX(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_HAVE_INDEX)
 588
 589 static PyObject*
 590 tuplesubscript(PyTupleObject* self, PyObject* item)
 591 {
 592         PyNumberMethods *nb = item->ob_type->tp_as_number;
 593         if (nb != NULL && HASINDEX(item) && nb->nb_index != NULL) {
 594                 Py_ssize_t i = nb->nb_index(item);
 595                 if (i == -1 && PyErr_Occurred())
 596                         return NULL;
 597                 if (i < 0)
 598                         i += PyTuple_GET_SIZE(self);
 599                 return tupleitem(self, i);
 600         }
 601         else if (PySlice_Check(item)) {
 602                 Py_ssize_t start, stop, step, slicelength, cur, i;
 603                 PyObject* result;
 604                 PyObject* it;
 605                 PyObject **src, **dest;
 606
 607                 if (PySlice_GetIndicesEx((PySliceObject*)item,
 608                                  PyTuple_GET_SIZE(self),
 609                                  &start, &stop, &step, &slicelength) < 0) {
 610                         return NULL;
 611                 }
 612
 613                 if (slicelength <= 0) {
 614                         return PyTuple_New(0);
 615                 }
 616                 else {
 617                         result = PyTuple_New(slicelength);
 618                         if (!result) return NULL;
 619
 620                         src = self->ob_item;
 621                         dest = ((PyTupleObject *)result)->ob_item;
 622                         for (cur = start, i = 0; i < slicelength;
 623                              cur += step, i++) {
 624                                 it = src[cur];
 625                                 Py_INCREF(it);
 626                                 dest[i] = it;
 627                         }
 628
 629                         return result;
 630                 }
 631         }
 632         else {
 633                 PyErr_SetString(PyExc_TypeError,
 634                                 "tuple indices must be integers");
 635                 return NULL;
 636         }
 637 }
 638
 639 static PyObject *
 640 tuple_getnewargs(PyTupleObject *v)
 641 {
 642         return Py_BuildValue("(N)", tupleslice(v, 0, v->ob_size));
 643
 644 }
 645
 646 static PyMethodDef tuple_methods[] = {
 647         {"__getnewargs__",      (PyCFunction)tuple_getnewargs,  METH_NOARGS},
 648         {NULL,          NULL}           /* sentinel */
 649 };
 650
 651 static PyMappingMethods tuple_as_mapping = {
 652         (lenfunc)tuplelength,
 653         (binaryfunc)tuplesubscript,
 654         0
 655 };
 656
 657 static PyObject *tuple_iter(PyObject *seq);
 658
 659 PyTypeObject PyTuple_Type = {
 660         PyObject_HEAD_INIT(&PyType_Type)
 661         0,
 662         "tuple",
 663         sizeof(PyTupleObject) - sizeof(PyObject *),
 664         sizeof(PyObject *),
 665         (destructor)tupledealloc,               /* tp_dealloc */
 666         (printfunc)tupleprint,                  /* tp_print */
 667         0,                                      /* tp_getattr */
 668         0,                                      /* tp_setattr */
 669         0,                                      /* tp_compare */
 670         (reprfunc)tuplerepr,                    /* tp_repr */
 671         0,                                      /* tp_as_number */
 672         &tuple_as_sequence,                     /* tp_as_sequence */
 673         &tuple_as_mapping,                      /* tp_as_mapping */
 674         (hashfunc)tuplehash,                    /* tp_hash */
 675         0,                                      /* tp_call */
 676         0,                                      /* tp_str */
 677         PyObject_GenericGetAttr,                /* tp_getattro */
 678         0,                                      /* tp_setattro */
 679         0,                                      /* tp_as_buffer */
 680         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
 681                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
 682         tuple_doc,                              /* tp_doc */
 683         (traverseproc)tupletraverse,            /* tp_traverse */
 684         0,                                      /* tp_clear */
 685         tuplerichcompare,                       /* tp_richcompare */
 686         0,                                      /* tp_weaklistoffset */
 687         tuple_iter,                             /* tp_iter */
 688         0,                                      /* tp_iternext */
 689         tuple_methods,                          /* tp_methods */
 690         0,                                      /* tp_members */
 691         0,                                      /* tp_getset */
 692         0,                                      /* tp_base */
 693         0,                                      /* tp_dict */
 694         0,                                      /* tp_descr_get */
 695         0,                                      /* tp_descr_set */
 696         0,                                      /* tp_dictoffset */
 697         0,                                      /* tp_init */
 698         0,                                      /* tp_alloc */
 699         tuple_new,                              /* tp_new */
 700         PyObject_GC_Del,                        /* tp_free */
 701 };
 702
 703 /* The following function breaks the notion that tuples are immutable:
 704    it changes the size of a tuple.  We get away with this only if there
 705    is only one module referencing the object.  You can also think of it
 706    as creating a new tuple object and destroying the old one, only more
 707    efficiently.  In any case, don't use this if the tuple may already be
 708    known to some other part of the code. */
 709
 710 int
 711 _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
 712 {
 713         register PyTupleObject *v;
 714         register PyTupleObject *sv;
 715         Py_ssize_t i;
 716         Py_ssize_t oldsize;
 717
 718         v = (PyTupleObject *) *pv;
 719         if (v == NULL || v->ob_type != &PyTuple_Type ||
 720             (v->ob_size != 0 && v->ob_refcnt != 1)) {
 721                 *pv = 0;
 722                 Py_XDECREF(v);
 723                 PyErr_BadInternalCall();
 724                 return -1;
 725         }
 726         oldsize = v->ob_size;
 727         if (oldsize == newsize)
 728                 return 0;
 729
 730         if (oldsize == 0) {
 731                 /* Empty tuples are often shared, so we should never
 732                    resize them in-place even if we do own the only
 733                    (current) reference */
 734                 Py_DECREF(v);
 735                 *pv = PyTuple_New(newsize);
 736                 return *pv == NULL ? -1 : 0;
 737         }
 738
 739         /* XXX UNREF/NEWREF interface should be more symmetrical */
 740         _Py_DEC_REFTOTAL;
 741         _PyObject_GC_UNTRACK(v);
 742         _Py_ForgetReference((PyObject *) v);
 743         /* DECREF items deleted by shrinkage */
 744         for (i = newsize; i < oldsize; i++) {
 745                 Py_XDECREF(v->ob_item[i]);
 746                 v->ob_item[i] = NULL;
 747         }
 748         sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
 749         if (sv == NULL) {
 750                 *pv = NULL;
 751                 PyObject_GC_Del(v);
 752                 return -1;
 753         }
 754         _Py_NewReference((PyObject *) sv);
 755         /* Zero out items added by growing */
 756         if (newsize > oldsize)
 757                 memset(&sv->ob_item[oldsize], 0,
 758                        sizeof(*sv->ob_item) * (newsize - oldsize));
 759         *pv = (PyObject *) sv;
 760         _PyObject_GC_TRACK(sv);
 761         return 0;
 762 }
 763
 764 void
 765 PyTuple_Fini(void)
 766 {
 767 #if MAXSAVESIZE > 0
 768         int i;
 769
 770         Py_XDECREF(free_tuples[0]);
 771         free_tuples[0] = NULL;
 772
 773         for (i = 1; i < MAXSAVESIZE; i++) {
 774                 PyTupleObject *p, *q;
 775                 p = free_tuples[i];
 776                 free_tuples[i] = NULL;
 777                 while (p) {
 778                         q = p;
 779                         p = (PyTupleObject *)(p->ob_item[0]);
 780                         PyObject_GC_Del(q);
 781                 }
 782         }
 783 #endif
 784 }
 785
 786 /*********************** Tuple Iterator **************************/
 787
 788 typedef struct {
 789         PyObject_HEAD
 790         long it_index;
 791         PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
 792 } tupleiterobject;
 793
 794 PyTypeObject PyTupleIter_Type;
 795
 796 static PyObject *
 797 tuple_iter(PyObject *seq)
 798 {
 799         tupleiterobject *it;
 800
 801         if (!PyTuple_Check(seq)) {
 802                 PyErr_BadInternalCall();
 803                 return NULL;
 804         }
 805         it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
 806         if (it == NULL)
 807                 return NULL;
 808         it->it_index = 0;
 809         Py_INCREF(seq);
 810         it->it_seq = (PyTupleObject *)seq;
 811         _PyObject_GC_TRACK(it);
 812         return (PyObject *)it;
 813 }
 814
 815 static void
 816 tupleiter_dealloc(tupleiterobject *it)
 817 {
 818         _PyObject_GC_UNTRACK(it);
 819         Py_XDECREF(it->it_seq);
 820         PyObject_GC_Del(it);
 821 }
 822
 823 static int
 824 tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
 825 {
 826         if (it->it_seq == NULL)
 827                 return 0;
 828         return visit((PyObject *)it->it_seq, arg);
 829 }
 830
 831 static PyObject *
 832 tupleiter_next(tupleiterobject *it)
 833 {
 834         PyTupleObject *seq;
 835         PyObject *item;
 836
 837         assert(it != NULL);
 838         seq = it->it_seq;
 839         if (seq == NULL)
 840                 return NULL;
 841         assert(PyTuple_Check(seq));
 842
 843         if (it->it_index < PyTuple_GET_SIZE(seq)) {
 844                 item = PyTuple_GET_ITEM(seq, it->it_index);
 845                 ++it->it_index;
 846                 Py_INCREF(item);
 847                 return item;
 848         }
 849
 850         Py_DECREF(seq);
 851         it->it_seq = NULL;
 852         return NULL;
 853 }
 854
 855 static PyObject *
 856 tupleiter_len(tupleiterobject *it)
 857 {
 858         Py_ssize_t len = 0;
 859         if (it->it_seq)
 860                 len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
 861         return PyInt_FromSsize_t(len);
 862 }
 863
 864 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
 865
 866 static PyMethodDef tupleiter_methods[] = {
 867         {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
 868         {NULL,          NULL}           /* sentinel */
 869 };
 870
 871 PyTypeObject PyTupleIter_Type = {
 872         PyObject_HEAD_INIT(&PyType_Type)
 873         0,                                      /* ob_size */
 874         "tupleiterator",                        /* tp_name */
 875         sizeof(tupleiterobject),                /* tp_basicsize */
 876         0,                                      /* tp_itemsize */
 877         /* methods */
 878         (destructor)tupleiter_dealloc,          /* tp_dealloc */
 879         0,                                      /* tp_print */
 880         0,                                      /* tp_getattr */
 881         0,                                      /* tp_setattr */
 882         0,                                      /* tp_compare */
 883         0,                                      /* tp_repr */
 884         0,                                      /* tp_as_number */
 885         0,                                      /* tp_as_sequence */
 886         0,                                      /* tp_as_mapping */
 887         0,                                      /* tp_hash */
 888         0,                                      /* tp_call */
 889         0,                                      /* tp_str */
 890         PyObject_GenericGetAttr,                /* tp_getattro */
 891         0,                                      /* tp_setattro */
 892         0,                                      /* tp_as_buffer */
 893         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
 894         0,                                      /* tp_doc */
 895         (traverseproc)tupleiter_traverse,       /* tp_traverse */
 896         0,                                      /* tp_clear */
 897         0,                                      /* tp_richcompare */
 898         0,                                      /* tp_weaklistoffset */
 899         PyObject_SelfIter,                      /* tp_iter */
 900         (iternextfunc)tupleiter_next,           /* tp_iternext */
 901         tupleiter_methods,                      /* tp_methods */
 902         0,
 903 };