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