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 int size)
  28 {
  29         register PyTupleObject *op;
  30         int 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                 int 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 int
  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 int 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 int 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(int n, ...)
 135 {
 136         int 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 int i;
 163         register int 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         int 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         int 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 int 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                 mult += 82520L + len + len;
 282         }
 283         x += 97531L;
 284         if (x == -1)
 285                 x = -2;
 286         return x;
 287 }
 288
 289 static int
 290 tuplelength(PyTupleObject *a)
 291 {
 292         return a->ob_size;
 293 }
 294
 295 static int
 296 tuplecontains(PyTupleObject *a, PyObject *el)
 297 {
 298         int i, cmp;
 299
 300         for (i = 0, cmp = 0 ; cmp == 0 && i < a->ob_size; ++i)
 301                 cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
 302                                                    Py_EQ);
 303         return cmp;
 304 }
 305
 306 static PyObject *
 307 tupleitem(register PyTupleObject *a, register int i)
 308 {
 309         if (i < 0 || i >= a->ob_size) {
 310                 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
 311                 return NULL;
 312         }
 313         Py_INCREF(a->ob_item[i]);
 314         return a->ob_item[i];
 315 }
 316
 317 static PyObject *
 318 tupleslice(register PyTupleObject *a, register int ilow, register int ihigh)
 319 {
 320         register PyTupleObject *np;
 321         PyObject **src, **dest;
 322         register int i;
 323         int len;
 324         if (ilow < 0)
 325                 ilow = 0;
 326         if (ihigh > a->ob_size)
 327                 ihigh = a->ob_size;
 328         if (ihigh < ilow)
 329                 ihigh = ilow;
 330         if (ilow == 0 && ihigh == a->ob_size && PyTuple_CheckExact(a)) {
 331                 Py_INCREF(a);
 332                 return (PyObject *)a;
 333         }
 334         len = ihigh - ilow;
 335         np = (PyTupleObject *)PyTuple_New(len);
 336         if (np == NULL)
 337                 return NULL;
 338         src = a->ob_item + ilow;
 339         dest = np->ob_item;
 340         for (i = 0; i < len; i++) {
 341                 PyObject *v = src[i];
 342                 Py_INCREF(v);
 343                 dest[i] = v;
 344         }
 345         return (PyObject *)np;
 346 }
 347
 348 PyObject *
 349 PyTuple_GetSlice(PyObject *op, int i, int j)
 350 {
 351         if (op == NULL || !PyTuple_Check(op)) {
 352                 PyErr_BadInternalCall();
 353                 return NULL;
 354         }
 355         return tupleslice((PyTupleObject *)op, i, j);
 356 }
 357
 358 static PyObject *
 359 tupleconcat(register PyTupleObject *a, register PyObject *bb)
 360 {
 361         register int size;
 362         register int i;
 363         PyObject **src, **dest;
 364         PyTupleObject *np;
 365         if (!PyTuple_Check(bb)) {
 366                 PyErr_Format(PyExc_TypeError,
 367                      "can only concatenate tuple (not \"%.200s\") to tuple",
 368                              bb->ob_type->tp_name);
 369                 return NULL;
 370         }
 371 #define b ((PyTupleObject *)bb)
 372         size = a->ob_size + b->ob_size;
 373         if (size < 0)
 374                 return PyErr_NoMemory();
 375         np = (PyTupleObject *) PyTuple_New(size);
 376         if (np == NULL) {
 377                 return NULL;
 378         }
 379         src = a->ob_item;
 380         dest = np->ob_item;
 381         for (i = 0; i < a->ob_size; i++) {
 382                 PyObject *v = src[i];
 383                 Py_INCREF(v);
 384                 dest[i] = v;
 385         }
 386         src = b->ob_item;
 387         dest = np->ob_item + a->ob_size;
 388         for (i = 0; i < b->ob_size; i++) {
 389                 PyObject *v = src[i];
 390                 Py_INCREF(v);
 391                 dest[i] = v;
 392         }
 393         return (PyObject *)np;
 394 #undef b
 395 }
 396
 397 static PyObject *
 398 tuplerepeat(PyTupleObject *a, int n)
 399 {
 400         int i, j;
 401         int size;
 402         PyTupleObject *np;
 403         PyObject **p, **items;
 404         if (n < 0)
 405                 n = 0;
 406         if (a->ob_size == 0 || n == 1) {
 407                 if (PyTuple_CheckExact(a)) {
 408                         /* Since tuples are immutable, we can return a shared
 409                            copy in this case */
 410                         Py_INCREF(a);
 411                         return (PyObject *)a;
 412                 }
 413                 if (a->ob_size == 0)
 414                         return PyTuple_New(0);
 415         }
 416         size = a->ob_size * n;
 417         if (size/a->ob_size != n)
 418                 return PyErr_NoMemory();
 419         np = (PyTupleObject *) PyTuple_New(size);
 420         if (np == NULL)
 421                 return NULL;
 422         p = np->ob_item;
 423         items = a->ob_item;
 424         for (i = 0; i < n; i++) {
 425                 for (j = 0; j < a->ob_size; j++) {
 426                         *p = items[j];
 427                         Py_INCREF(*p);
 428                         p++;
 429                 }
 430         }
 431         return (PyObject *) np;
 432 }
 433
 434 static int
 435 tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
 436 {
 437         int i, err;
 438         PyObject *x;
 439
 440         for (i = o->ob_size; --i >= 0; ) {
 441                 x = o->ob_item[i];
 442                 if (x != NULL) {
 443                         err = visit(x, arg);
 444                         if (err)
 445                                 return err;
 446                 }
 447         }
 448         return 0;
 449 }
 450
 451 static PyObject *
 452 tuplerichcompare(PyObject *v, PyObject *w, int op)
 453 {
 454         PyTupleObject *vt, *wt;
 455         int i;
 456         int vlen, wlen;
 457
 458         if (!PyTuple_Check(v) || !PyTuple_Check(w)) {
 459                 Py_INCREF(Py_NotImplemented);
 460                 return Py_NotImplemented;
 461         }
 462
 463         vt = (PyTupleObject *)v;
 464         wt = (PyTupleObject *)w;
 465
 466         vlen = vt->ob_size;
 467         wlen = wt->ob_size;
 468
 469         /* Note:  the corresponding code for lists has an "early out" test
 470          * here when op is EQ or NE and the lengths differ.  That pays there,
 471          * but Tim was unable to find any real code where EQ/NE tuple
 472          * compares don't have the same length, so testing for it here would
 473          * have cost without benefit.
 474          */
 475
 476         /* Search for the first index where items are different.
 477          * Note that because tuples are immutable, it's safe to reuse
 478          * vlen and wlen across the comparison calls.
 479          */
 480         for (i = 0; i < vlen && i < wlen; i++) {
 481                 int k = PyObject_RichCompareBool(vt->ob_item[i],
 482                                                  wt->ob_item[i], Py_EQ);
 483                 if (k < 0)
 484                         return NULL;
 485                 if (!k)
 486                         break;
 487         }
 488
 489         if (i >= vlen || i >= wlen) {
 490                 /* No more items to compare -- compare sizes */
 491                 int cmp;
 492                 PyObject *res;
 493                 switch (op) {
 494                 case Py_LT: cmp = vlen <  wlen; break;
 495                 case Py_LE: cmp = vlen <= wlen; break;
 496                 case Py_EQ: cmp = vlen == wlen; break;
 497                 case Py_NE: cmp = vlen != wlen; break;
 498                 case Py_GT: cmp = vlen >  wlen; break;
 499                 case Py_GE: cmp = vlen >= wlen; break;
 500                 default: return NULL; /* cannot happen */
 501                 }
 502                 if (cmp)
 503                         res = Py_True;
 504                 else
 505                         res = Py_False;
 506                 Py_INCREF(res);
 507                 return res;
 508         }
 509
 510         /* We have an item that differs -- shortcuts for EQ/NE */
 511         if (op == Py_EQ) {
 512                 Py_INCREF(Py_False);
 513                 return Py_False;
 514         }
 515         if (op == Py_NE) {
 516                 Py_INCREF(Py_True);
 517                 return Py_True;
 518         }
 519
 520         /* Compare the final item again using the proper operator */
 521         return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
 522 }
 523
 524 static PyObject *
 525 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
 526
 527 static PyObject *
 528 tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 529 {
 530         PyObject *arg = NULL;
 531         static const char *kwlist[] = {"sequence", 0};
 532
 533         if (type != &PyTuple_Type)
 534                 return tuple_subtype_new(type, args, kwds);
 535         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))
 536                 return NULL;
 537
 538         if (arg == NULL)
 539                 return PyTuple_New(0);
 540         else
 541                 return PySequence_Tuple(arg);
 542 }
 543
 544 static PyObject *
 545 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 546 {
 547         PyObject *tmp, *new, *item;
 548         int i, n;
 549
 550         assert(PyType_IsSubtype(type, &PyTuple_Type));
 551         tmp = tuple_new(&PyTuple_Type, args, kwds);
 552         if (tmp == NULL)
 553                 return NULL;
 554         assert(PyTuple_Check(tmp));
 555         new = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
 556         if (new == NULL)
 557                 return NULL;
 558         for (i = 0; i < n; i++) {
 559                 item = PyTuple_GET_ITEM(tmp, i);
 560                 Py_INCREF(item);
 561                 PyTuple_SET_ITEM(new, i, item);
 562         }
 563         Py_DECREF(tmp);
 564         return new;
 565 }
 566
 567 PyDoc_STRVAR(tuple_doc,
 568 "tuple() -> an empty tuple\n"
 569 "tuple(sequence) -> tuple initialized from sequence's items\n"
 570 "\n"
 571 "If the argument is a tuple, the return value is the same object.");
 572
 573 static PySequenceMethods tuple_as_sequence = {
 574         (inquiry)tuplelength,                   /* sq_length */
 575         (binaryfunc)tupleconcat,                /* sq_concat */
 576         (intargfunc)tuplerepeat,                /* sq_repeat */
 577         (intargfunc)tupleitem,                  /* sq_item */
 578         (intintargfunc)tupleslice,              /* sq_slice */
 579         0,                                      /* sq_ass_item */
 580         0,                                      /* sq_ass_slice */
 581         (objobjproc)tuplecontains,              /* sq_contains */
 582 };
 583
 584 static PyObject*
 585 tuplesubscript(PyTupleObject* self, PyObject* item)
 586 {
 587         if (PyInt_Check(item)) {
 588                 long i = PyInt_AS_LONG(item);
 589                 if (i < 0)
 590                         i += PyTuple_GET_SIZE(self);
 591                 return tupleitem(self, i);
 592         }
 593         else if (PyLong_Check(item)) {
 594                 long i = PyLong_AsLong(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                 int 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
 619                         src = self->ob_item;
 620                         dest = ((PyTupleObject *)result)->ob_item;
 621                         for (cur = start, i = 0; i < slicelength;
 622                              cur += step, i++) {
 623                                 it = src[cur];
 624                                 Py_INCREF(it);
 625                                 dest[i] = it;
 626                         }
 627
 628                         return result;
 629                 }
 630         }
 631         else {
 632                 PyErr_SetString(PyExc_TypeError,
 633                                 "tuple indices must be integers");
 634                 return NULL;
 635         }
 636 }
 637
 638 static PyObject *
 639 tuple_getnewargs(PyTupleObject *v)
 640 {
 641         return Py_BuildValue("(N)", tupleslice(v, 0, v->ob_size));
 642
 643 }
 644
 645 static PyMethodDef tuple_methods[] = {
 646         {"__getnewargs__",      (PyCFunction)tuple_getnewargs,  METH_NOARGS},
 647         {NULL,          NULL}           /* sentinel */
 648 };
 649
 650 static PyMappingMethods tuple_as_mapping = {
 651         (inquiry)tuplelength,
 652         (binaryfunc)tuplesubscript,
 653         0
 654 };
 655
 656 static PyObject *tuple_iter(PyObject *seq);
 657
 658 PyTypeObject PyTuple_Type = {
 659         PyObject_HEAD_INIT(&PyType_Type)
 660         0,
 661         "tuple",
 662         sizeof(PyTupleObject) - sizeof(PyObject *),
 663         sizeof(PyObject *),
 664         (destructor)tupledealloc,               /* tp_dealloc */
 665         (printfunc)tupleprint,                  /* tp_print */
 666         0,                                      /* tp_getattr */
 667         0,                                      /* tp_setattr */
 668         0,                                      /* tp_compare */
 669         (reprfunc)tuplerepr,                    /* tp_repr */
 670         0,                                      /* tp_as_number */
 671         &tuple_as_sequence,                     /* tp_as_sequence */
 672         &tuple_as_mapping,                      /* tp_as_mapping */
 673         (hashfunc)tuplehash,                    /* tp_hash */
 674         0,                                      /* tp_call */
 675         0,                                      /* tp_str */
 676         PyObject_GenericGetAttr,                /* tp_getattro */
 677         0,                                      /* tp_setattro */
 678         0,                                      /* tp_as_buffer */
 679         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
 680                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
 681         tuple_doc,                              /* tp_doc */
 682         (traverseproc)tupletraverse,            /* tp_traverse */
 683         0,                                      /* tp_clear */
 684         tuplerichcompare,                       /* tp_richcompare */
 685         0,                                      /* tp_weaklistoffset */
 686         tuple_iter,                             /* tp_iter */
 687         0,                                      /* tp_iternext */
 688         tuple_methods,                          /* tp_methods */
 689         0,                                      /* tp_members */
 690         0,                                      /* tp_getset */
 691         0,                                      /* tp_base */
 692         0,                                      /* tp_dict */
 693         0,                                      /* tp_descr_get */
 694         0,                                      /* tp_descr_set */
 695         0,                                      /* tp_dictoffset */
 696         0,                                      /* tp_init */
 697         0,                                      /* tp_alloc */
 698         tuple_new,                              /* tp_new */
 699         PyObject_GC_Del,                        /* tp_free */
 700 };
 701
 702 /* The following function breaks the notion that tuples are immutable:
 703    it changes the size of a tuple.  We get away with this only if there
 704    is only one module referencing the object.  You can also think of it
 705    as creating a new tuple object and destroying the old one, only more
 706    efficiently.  In any case, don't use this if the tuple may already be
 707    known to some other part of the code. */
 708
 709 int
 710 _PyTuple_Resize(PyObject **pv, int newsize)
 711 {
 712         register PyTupleObject *v;
 713         register PyTupleObject *sv;
 714         int i;
 715         int oldsize;
 716
 717         v = (PyTupleObject *) *pv;
 718         if (v == NULL || v->ob_type != &PyTuple_Type ||
 719             (v->ob_size != 0 && v->ob_refcnt != 1)) {
 720                 *pv = 0;
 721                 Py_XDECREF(v);
 722                 PyErr_BadInternalCall();
 723                 return -1;
 724         }
 725         oldsize = v->ob_size;
 726         if (oldsize == newsize)
 727                 return 0;
 728
 729         if (oldsize == 0) {
 730                 /* Empty tuples are often shared, so we should never
 731                    resize them in-place even if we do own the only
 732                    (current) reference */
 733                 Py_DECREF(v);
 734                 *pv = PyTuple_New(newsize);
 735                 return *pv == NULL ? -1 : 0;
 736         }
 737
 738         /* XXX UNREF/NEWREF interface should be more symmetrical */
 739         _Py_DEC_REFTOTAL;
 740         _PyObject_GC_UNTRACK(v);
 741         _Py_ForgetReference((PyObject *) v);
 742         /* DECREF items deleted by shrinkage */
 743         for (i = newsize; i < oldsize; i++) {
 744                 Py_XDECREF(v->ob_item[i]);
 745                 v->ob_item[i] = NULL;
 746         }
 747         sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
 748         if (sv == NULL) {
 749                 *pv = NULL;
 750                 PyObject_GC_Del(v);
 751                 return -1;
 752         }
 753         _Py_NewReference((PyObject *) sv);
 754         /* Zero out items added by growing */
 755         if (newsize > oldsize)
 756                 memset(&sv->ob_item[oldsize], 0,
 757                        sizeof(*sv->ob_item) * (newsize - oldsize));
 758         *pv = (PyObject *) sv;
 759         _PyObject_GC_TRACK(sv);
 760         return 0;
 761 }
 762
 763 void
 764 PyTuple_Fini(void)
 765 {
 766 #if MAXSAVESIZE > 0
 767         int i;
 768
 769         Py_XDECREF(free_tuples[0]);
 770         free_tuples[0] = NULL;
 771
 772         for (i = 1; i < MAXSAVESIZE; i++) {
 773                 PyTupleObject *p, *q;
 774                 p = free_tuples[i];
 775                 free_tuples[i] = NULL;
 776                 while (p) {
 777                         q = p;
 778                         p = (PyTupleObject *)(p->ob_item[0]);
 779                         PyObject_GC_Del(q);
 780                 }
 781         }
 782 #endif
 783 }
 784
 785 /*********************** Tuple Iterator **************************/
 786
 787 typedef struct {
 788         PyObject_HEAD
 789         long it_index;
 790         PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
 791 } tupleiterobject;
 792
 793 PyTypeObject PyTupleIter_Type;
 794
 795 static PyObject *
 796 tuple_iter(PyObject *seq)
 797 {
 798         tupleiterobject *it;
 799
 800         if (!PyTuple_Check(seq)) {
 801                 PyErr_BadInternalCall();
 802                 return NULL;
 803         }
 804         it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
 805         if (it == NULL)
 806                 return NULL;
 807         it->it_index = 0;
 808         Py_INCREF(seq);
 809         it->it_seq = (PyTupleObject *)seq;
 810         _PyObject_GC_TRACK(it);
 811         return (PyObject *)it;
 812 }
 813
 814 static void
 815 tupleiter_dealloc(tupleiterobject *it)
 816 {
 817         _PyObject_GC_UNTRACK(it);
 818         Py_XDECREF(it->it_seq);
 819         PyObject_GC_Del(it);
 820 }
 821
 822 static int
 823 tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
 824 {
 825         if (it->it_seq == NULL)
 826                 return 0;
 827         return visit((PyObject *)it->it_seq, arg);
 828 }
 829
 830 static PyObject *
 831 tupleiter_next(tupleiterobject *it)
 832 {
 833         PyTupleObject *seq;
 834         PyObject *item;
 835
 836         assert(it != NULL);
 837         seq = it->it_seq;
 838         if (seq == NULL)
 839                 return NULL;
 840         assert(PyTuple_Check(seq));
 841
 842         if (it->it_index < PyTuple_GET_SIZE(seq)) {
 843                 item = PyTuple_GET_ITEM(seq, it->it_index);
 844                 ++it->it_index;
 845                 Py_INCREF(item);
 846                 return item;
 847         }
 848
 849         Py_DECREF(seq);
 850         it->it_seq = NULL;
 851         return NULL;
 852 }
 853
 854 static PyObject *
 855 tupleiter_len(tupleiterobject *it)
 856 {
 857         int len = 0;
 858         if (it->it_seq)
 859                 len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
 860         return PyInt_FromLong(len);
 861 }
 862
 863 PyDoc_STRVAR(length_cue_doc, "Private method returning an estimate of len(list(it)).");
 864
 865 static PyMethodDef tupleiter_methods[] = {
 866         {"_length_cue", (PyCFunction)tupleiter_len, METH_NOARGS, length_cue_doc},
 867         {NULL,          NULL}           /* sentinel */
 868 };
 869
 870 PyTypeObject PyTupleIter_Type = {
 871         PyObject_HEAD_INIT(&PyType_Type)
 872         0,                                      /* ob_size */
 873         "tupleiterator",                        /* tp_name */
 874         sizeof(tupleiterobject),                /* tp_basicsize */
 875         0,                                      /* tp_itemsize */
 876         /* methods */
 877         (destructor)tupleiter_dealloc,          /* tp_dealloc */
 878         0,                                      /* tp_print */
 879         0,                                      /* tp_getattr */
 880         0,                                      /* tp_setattr */
 881         0,                                      /* tp_compare */
 882         0,                                      /* tp_repr */
 883         0,                                      /* tp_as_number */
 884         0,                                      /* tp_as_sequence */
 885         0,                                      /* tp_as_mapping */
 886         0,                                      /* tp_hash */
 887         0,                                      /* tp_call */
 888         0,                                      /* tp_str */
 889         PyObject_GenericGetAttr,                /* tp_getattro */
 890         0,                                      /* tp_setattro */
 891         0,                                      /* tp_as_buffer */
 892         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
 893         0,                                      /* tp_doc */
 894         (traverseproc)tupleiter_traverse,       /* tp_traverse */
 895         0,                                      /* tp_clear */
 896         0,                                      /* tp_richcompare */
 897         0,                                      /* tp_weaklistoffset */
 898         PyObject_SelfIter,                      /* tp_iter */
 899         (iternextfunc)tupleiter_next,           /* tp_iternext */
 900         tupleiter_methods,                      /* tp_methods */
 901         0,
 902 };