Objects/tupleobject.c

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