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