1 2 /* Integer object implementation */ 3 4 #include "Python.h" 5 #include <ctype.h> 6 #include <float.h> 7 8 static PyObject *int_int(PyIntObject *v); 9 10 long 11 PyInt_GetMax(void) 12 { 13 return LONG_MAX; /* To initialize sys.maxint */ 14 } 15 16 /* Integers are quite normal objects, to make object handling uniform. 17 (Using odd pointers to represent integers would save much space 18 but require extra checks for this special case throughout the code.) 19 Since a typical Python program spends much of its time allocating 20 and deallocating integers, these operations should be very fast. 21 Therefore we use a dedicated allocation scheme with a much lower 22 overhead (in space and time) than straight malloc(): a simple 23 dedicated free list, filled when necessary with memory from malloc(). 24 25 block_list is a singly-linked list of all PyIntBlocks ever allocated, 26 linked via their next members. PyIntBlocks are never returned to the 27 system before shutdown (PyInt_Fini). 28 29 free_list is a singly-linked list of available PyIntObjects, linked 30 via abuse of their ob_type members. 31 */ 32 33 #define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */ 34 #define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */ 35 #define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject)) 36 37 struct _intblock { 38 struct _intblock *next; 39 PyIntObject objects[N_INTOBJECTS]; 40 }; 41 42 typedef struct _intblock PyIntBlock; 43 44 static PyIntBlock *block_list = NULL; 45 static PyIntObject *free_list = NULL; 46 47 static PyIntObject * 48 fill_free_list(void) 49 { 50 PyIntObject *p, *q; 51 /* Python's object allocator isn't appropriate for large blocks. */ 52 p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock)); 53 if (p == NULL) 54 return (PyIntObject *) PyErr_NoMemory(); 55 ((PyIntBlock *)p)->next = block_list; 56 block_list = (PyIntBlock *)p; 57 /* Link the int objects together, from rear to front, then return 58 the address of the last int object in the block. */ 59 p = &((PyIntBlock *)p)->objects[0]; 60 q = p + N_INTOBJECTS; 61 while (--q > p) 62 Py_TYPE(q) = (struct _typeobject *)(q-1); 63 Py_TYPE(q) = NULL; 64 return p + N_INTOBJECTS - 1; 65 } 66 67 #ifndef NSMALLPOSINTS 68 #define NSMALLPOSINTS 257 69 #endif 70 #ifndef NSMALLNEGINTS 71 #define NSMALLNEGINTS 5 72 #endif 73 #if NSMALLNEGINTS + NSMALLPOSINTS > 0 74 /* References to small integers are saved in this array so that they 75 can be shared. 76 The integers that are saved are those in the range 77 -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive). 78 */ 79 static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS]; 80 #endif 81 #ifdef COUNT_ALLOCS 82 Py_ssize_t quick_int_allocs; 83 Py_ssize_t quick_neg_int_allocs; 84 #endif 85 86 PyObject * 87 PyInt_FromLong(long ival) 88 { 89 register PyIntObject *v; 90 #if NSMALLNEGINTS + NSMALLPOSINTS > 0 91 if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { 92 v = small_ints[ival + NSMALLNEGINTS]; 93 Py_INCREF(v); 94 #ifdef COUNT_ALLOCS 95 if (ival >= 0) 96 quick_int_allocs++; 97 else 98 quick_neg_int_allocs++; 99 #endif 100 return (PyObject *) v; 101 } 102 #endif 103 if (free_list == NULL) { 104 if ((free_list = fill_free_list()) == NULL) 105 return NULL; 106 } 107 /* Inline PyObject_New */ 108 v = free_list; 109 free_list = (PyIntObject *)Py_TYPE(v); 110 PyObject_INIT(v, &PyInt_Type); 111 v->ob_ival = ival; 112 return (PyObject *) v; 113 } 114 115 PyObject * 116 PyInt_FromSize_t(size_t ival) 117 { 118 if (ival <= LONG_MAX) 119 return PyInt_FromLong((long)ival); 120 return _PyLong_FromSize_t(ival); 121 } 122 123 PyObject * 124 PyInt_FromSsize_t(Py_ssize_t ival) 125 { 126 if (ival >= LONG_MIN && ival <= LONG_MAX) 127 return PyInt_FromLong((long)ival); 128 return _PyLong_FromSsize_t(ival); 129 } 130 131 static void 132 int_dealloc(PyIntObject *v) 133 { 134 if (PyInt_CheckExact(v)) { 135 Py_TYPE(v) = (struct _typeobject *)free_list; 136 free_list = v; 137 } 138 else 139 Py_TYPE(v)->tp_free((PyObject *)v); 140 } 141 142 static void 143 int_free(PyIntObject *v) 144 { 145 Py_TYPE(v) = (struct _typeobject *)free_list; 146 free_list = v; 147 } 148 149 long 150 PyInt_AsLong(register PyObject *op) 151 { 152 PyNumberMethods *nb; 153 PyIntObject *io; 154 long val; 155 156 if (op && PyInt_Check(op)) 157 return PyInt_AS_LONG((PyIntObject*) op); 158 159 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL || 160 nb->nb_int == NULL) { 161 PyErr_SetString(PyExc_TypeError, "an integer is required"); 162 return -1; 163 } 164 165 io = (PyIntObject*) (*nb->nb_int) (op); 166 if (io == NULL) 167 return -1; 168 if (!PyInt_Check(io)) { 169 if (PyLong_Check(io)) { 170 /* got a long? => retry int conversion */ 171 val = PyLong_AsLong((PyObject *)io); 172 Py_DECREF(io); 173 if ((val == -1) && PyErr_Occurred()) 174 return -1; 175 return val; 176 } 177 else 178 { 179 Py_DECREF(io); 180 PyErr_SetString(PyExc_TypeError, 181 "__int__ method should return an integer"); 182 return -1; 183 } 184 } 185 186 val = PyInt_AS_LONG(io); 187 Py_DECREF(io); 188 189 return val; 190 } 191 192 Py_ssize_t 193 PyInt_AsSsize_t(register PyObject *op) 194 { 195 #if SIZEOF_SIZE_T != SIZEOF_LONG 196 PyNumberMethods *nb; 197 PyIntObject *io; 198 Py_ssize_t val; 199 #endif 200 201 if (op == NULL) { 202 PyErr_SetString(PyExc_TypeError, "an integer is required"); 203 return -1; 204 } 205 206 if (PyInt_Check(op)) 207 return PyInt_AS_LONG((PyIntObject*) op); 208 if (PyLong_Check(op)) 209 return _PyLong_AsSsize_t(op); 210 #if SIZEOF_SIZE_T == SIZEOF_LONG 211 return PyInt_AsLong(op); 212 #else 213 214 if ((nb = Py_TYPE(op)->tp_as_number) == NULL || 215 (nb->nb_int == NULL && nb->nb_long == 0)) { 216 PyErr_SetString(PyExc_TypeError, "an integer is required"); 217 return -1; 218 } 219 220 if (nb->nb_long != 0) 221 io = (PyIntObject*) (*nb->nb_long) (op); 222 else 223 io = (PyIntObject*) (*nb->nb_int) (op); 224 if (io == NULL) 225 return -1; 226 if (!PyInt_Check(io)) { 227 if (PyLong_Check(io)) { 228 /* got a long? => retry int conversion */ 229 val = _PyLong_AsSsize_t((PyObject *)io); 230 Py_DECREF(io); 231 if ((val == -1) && PyErr_Occurred()) 232 return -1; 233 return val; 234 } 235 else 236 { 237 Py_DECREF(io); 238 PyErr_SetString(PyExc_TypeError, 239 "__int__ method should return an integer"); 240 return -1; 241 } 242 } 243 244 val = PyInt_AS_LONG(io); 245 Py_DECREF(io); 246 247 return val; 248 #endif 249 } 250 251 unsigned long 252 PyInt_AsUnsignedLongMask(register PyObject *op) 253 { 254 PyNumberMethods *nb; 255 PyIntObject *io; 256 unsigned long val; 257 258 if (op && PyInt_Check(op)) 259 return PyInt_AS_LONG((PyIntObject*) op); 260 if (op && PyLong_Check(op)) 261 return PyLong_AsUnsignedLongMask(op); 262 263 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL || 264 nb->nb_int == NULL) { 265 PyErr_SetString(PyExc_TypeError, "an integer is required"); 266 return (unsigned long)-1; 267 } 268 269 io = (PyIntObject*) (*nb->nb_int) (op); 270 if (io == NULL) 271 return (unsigned long)-1; 272 if (!PyInt_Check(io)) { 273 if (PyLong_Check(io)) { 274 val = PyLong_AsUnsignedLongMask((PyObject *)io); 275 Py_DECREF(io); 276 if (PyErr_Occurred()) 277 return (unsigned long)-1; 278 return val; 279 } 280 else 281 { 282 Py_DECREF(io); 283 PyErr_SetString(PyExc_TypeError, 284 "__int__ method should return an integer"); 285 return (unsigned long)-1; 286 } 287 } 288 289 val = PyInt_AS_LONG(io); 290 Py_DECREF(io); 291 292 return val; 293 } 294 295 #ifdef HAVE_LONG_LONG 296 unsigned PY_LONG_LONG 297 PyInt_AsUnsignedLongLongMask(register PyObject *op) 298 { 299 PyNumberMethods *nb; 300 PyIntObject *io; 301 unsigned PY_LONG_LONG val; 302 303 if (op && PyInt_Check(op)) 304 return PyInt_AS_LONG((PyIntObject*) op); 305 if (op && PyLong_Check(op)) 306 return PyLong_AsUnsignedLongLongMask(op); 307 308 if (op == NULL || (nb = Py_TYPE(op)->tp_as_number) == NULL || 309 nb->nb_int == NULL) { 310 PyErr_SetString(PyExc_TypeError, "an integer is required"); 311 return (unsigned PY_LONG_LONG)-1; 312 } 313 314 io = (PyIntObject*) (*nb->nb_int) (op); 315 if (io == NULL) 316 return (unsigned PY_LONG_LONG)-1; 317 if (!PyInt_Check(io)) { 318 if (PyLong_Check(io)) { 319 val = PyLong_AsUnsignedLongLongMask((PyObject *)io); 320 Py_DECREF(io); 321 if (PyErr_Occurred()) 322 return (unsigned PY_LONG_LONG)-1; 323 return val; 324 } 325 else 326 { 327 Py_DECREF(io); 328 PyErr_SetString(PyExc_TypeError, 329 "__int__ method should return an integer"); 330 return (unsigned PY_LONG_LONG)-1; 331 } 332 } 333 334 val = PyInt_AS_LONG(io); 335 Py_DECREF(io); 336 337 return val; 338 } 339 #endif 340 341 PyObject * 342 PyInt_FromString(char *s, char **pend, int base) 343 { 344 char *end; 345 long x; 346 Py_ssize_t slen; 347 PyObject *sobj, *srepr; 348 349 if ((base != 0 && base < 2) || base > 36) { 350 PyErr_SetString(PyExc_ValueError, 351 "int() base must be >= 2 and <= 36"); 352 return NULL; 353 } 354 355 while (*s && isspace(Py_CHARMASK(*s))) 356 s++; 357 errno = 0; 358 if (base == 0 && s[0] == '0') { 359 x = (long) PyOS_strtoul(s, &end, base); 360 if (x < 0) 361 return PyLong_FromString(s, pend, base); 362 } 363 else 364 x = PyOS_strtol(s, &end, base); 365 if (end == s || !isalnum(Py_CHARMASK(end[-1]))) 366 goto bad; 367 while (*end && isspace(Py_CHARMASK(*end))) 368 end++; 369 if (*end != '\0') { 370 bad: 371 slen = strlen(s) < 200 ? strlen(s) : 200; 372 sobj = PyString_FromStringAndSize(s, slen); 373 if (sobj == NULL) 374 return NULL; 375 srepr = PyObject_Repr(sobj); 376 Py_DECREF(sobj); 377 if (srepr == NULL) 378 return NULL; 379 PyErr_Format(PyExc_ValueError, 380 "invalid literal for int() with base %d: %s", 381 base, PyString_AS_STRING(srepr)); 382 Py_DECREF(srepr); 383 return NULL; 384 } 385 else if (errno != 0) 386 return PyLong_FromString(s, pend, base); 387 if (pend) 388 *pend = end; 389 return PyInt_FromLong(x); 390 } 391 392 #ifdef Py_USING_UNICODE 393 PyObject * 394 PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base) 395 { 396 PyObject *result; 397 char *buffer = (char *)PyMem_MALLOC(length+1); 398 399 if (buffer == NULL) 400 return PyErr_NoMemory(); 401 402 if (PyUnicode_EncodeDecimal(s, length, buffer, NULL)) { 403 PyMem_FREE(buffer); 404 return NULL; 405 } 406 result = PyInt_FromString(buffer, NULL, base); 407 PyMem_FREE(buffer); 408 return result; 409 } 410 #endif 411 412 /* Methods */ 413 414 /* Integers are seen as the "smallest" of all numeric types and thus 415 don't have any knowledge about conversion of other types to 416 integers. */ 417 418 #define CONVERT_TO_LONG(obj, lng) \ 419 if (PyInt_Check(obj)) { \ 420 lng = PyInt_AS_LONG(obj); \ 421 } \ 422 else { \ 423 Py_INCREF(Py_NotImplemented); \ 424 return Py_NotImplemented; \ 425 } 426 427 /* ARGSUSED */ 428 static int 429 int_print(PyIntObject *v, FILE *fp, int flags) 430 /* flags -- not used but required by interface */ 431 { 432 long int_val = v->ob_ival; 433 Py_BEGIN_ALLOW_THREADS 434 fprintf(fp, "%ld", int_val); 435 Py_END_ALLOW_THREADS 436 return 0; 437 } 438 439 static int 440 int_compare(PyIntObject *v, PyIntObject *w) 441 { 442 register long i = v->ob_ival; 443 register long j = w->ob_ival; 444 return (i < j) ? -1 : (i > j) ? 1 : 0; 445 } 446 447 static long 448 int_hash(PyIntObject *v) 449 { 450 /* XXX If this is changed, you also need to change the way 451 Python's long, float and complex types are hashed. */ 452 long x = v -> ob_ival; 453 if (x == -1) 454 x = -2; 455 return x; 456 } 457 458 static PyObject * 459 int_add(PyIntObject *v, PyIntObject *w) 460 { 461 register long a, b, x; 462 CONVERT_TO_LONG(v, a); 463 CONVERT_TO_LONG(w, b); 464 /* casts in the line below avoid undefined behaviour on overflow */ 465 x = (long)((unsigned long)a + b); 466 if ((x^a) >= 0 || (x^b) >= 0) 467 return PyInt_FromLong(x); 468 return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w); 469 } 470 471 static PyObject * 472 int_sub(PyIntObject *v, PyIntObject *w) 473 { 474 register long a, b, x; 475 CONVERT_TO_LONG(v, a); 476 CONVERT_TO_LONG(w, b); 477 /* casts in the line below avoid undefined behaviour on overflow */ 478 x = (long)((unsigned long)a - b); 479 if ((x^a) >= 0 || (x^~b) >= 0) 480 return PyInt_FromLong(x); 481 return PyLong_Type.tp_as_number->nb_subtract((PyObject *)v, 482 (PyObject *)w); 483 } 484 485 /* 486 Integer overflow checking for * is painful: Python tried a couple ways, but 487 they didn't work on all platforms, or failed in endcases (a product of 488 -sys.maxint-1 has been a particular pain). 489 490 Here's another way: 491 492 The native long product x*y is either exactly right or *way* off, being 493 just the last n bits of the true product, where n is the number of bits 494 in a long (the delivered product is the true product plus i*2**n for 495 some integer i). 496 497 The native double product (double)x * (double)y is subject to three 498 rounding errors: on a sizeof(long)==8 box, each cast to double can lose 499 info, and even on a sizeof(long)==4 box, the multiplication can lose info. 500 But, unlike the native long product, it's not in *range* trouble: even 501 if sizeof(long)==32 (256-bit longs), the product easily fits in the 502 dynamic range of a double. So the leading 50 (or so) bits of the double 503 product are correct. 504 505 We check these two ways against each other, and declare victory if they're 506 approximately the same. Else, because the native long product is the only 507 one that can lose catastrophic amounts of information, it's the native long 508 product that must have overflowed. 509 */ 510 511 static PyObject * 512 int_mul(PyObject *v, PyObject *w) 513 { 514 long a, b; 515 long longprod; /* a*b in native long arithmetic */ 516 double doubled_longprod; /* (double)longprod */ 517 double doubleprod; /* (double)a * (double)b */ 518 519 CONVERT_TO_LONG(v, a); 520 CONVERT_TO_LONG(w, b); 521 /* casts in the next line avoid undefined behaviour on overflow */ 522 longprod = (long)((unsigned long)a * b); 523 doubleprod = (double)a * (double)b; 524 doubled_longprod = (double)longprod; 525 526 /* Fast path for normal case: small multiplicands, and no info 527 is lost in either method. */ 528 if (doubled_longprod == doubleprod) 529 return PyInt_FromLong(longprod); 530 531 /* Somebody somewhere lost info. Close enough, or way off? Note 532 that a != 0 and b != 0 (else doubled_longprod == doubleprod == 0). 533 The difference either is or isn't significant compared to the 534 true value (of which doubleprod is a good approximation). 535 */ 536 { 537 const double diff = doubled_longprod - doubleprod; 538 const double absdiff = diff >= 0.0 ? diff : -diff; 539 const double absprod = doubleprod >= 0.0 ? doubleprod : 540 -doubleprod; 541 /* absdiff/absprod <= 1/32 iff 542 32 * absdiff <= absprod -- 5 good bits is "close enough" */ 543 if (32.0 * absdiff <= absprod) 544 return PyInt_FromLong(longprod); 545 else 546 return PyLong_Type.tp_as_number->nb_multiply(v, w); 547 } 548 } 549 550 /* Integer overflow checking for unary negation: on a 2's-complement 551 * box, -x overflows iff x is the most negative long. In this case we 552 * get -x == x. However, -x is undefined (by C) if x /is/ the most 553 * negative long (it's a signed overflow case), and some compilers care. 554 * So we cast x to unsigned long first. However, then other compilers 555 * warn about applying unary minus to an unsigned operand. Hence the 556 * weird "0-". 557 */ 558 #define UNARY_NEG_WOULD_OVERFLOW(x) \ 559 ((x) < 0 && (unsigned long)(x) == 0-(unsigned long)(x)) 560 561 /* Return type of i_divmod */ 562 enum divmod_result { 563 DIVMOD_OK, /* Correct result */ 564 DIVMOD_OVERFLOW, /* Overflow, try again using longs */ 565 DIVMOD_ERROR /* Exception raised */ 566 }; 567 568 static enum divmod_result 569 i_divmod(register long x, register long y, 570 long *p_xdivy, long *p_xmody) 571 { 572 long xdivy, xmody; 573 574 if (y == 0) { 575 PyErr_SetString(PyExc_ZeroDivisionError, 576 "integer division or modulo by zero"); 577 return DIVMOD_ERROR; 578 } 579 /* (-sys.maxint-1)/-1 is the only overflow case. */ 580 if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x)) 581 return DIVMOD_OVERFLOW; 582 xdivy = x / y; 583 /* xdiv*y can overflow on platforms where x/y gives floor(x/y) 584 * for x and y with differing signs. (This is unusual 585 * behaviour, and C99 prohibits it, but it's allowed by C89; 586 * for an example of overflow, take x = LONG_MIN, y = 5 or x = 587 * LONG_MAX, y = -5.) However, x - xdivy*y is always 588 * representable as a long, since it lies strictly between 589 * -abs(y) and abs(y). We add casts to avoid intermediate 590 * overflow. 591 */ 592 xmody = (long)(x - (unsigned long)xdivy * y); 593 /* If the signs of x and y differ, and the remainder is non-0, 594 * C89 doesn't define whether xdivy is now the floor or the 595 * ceiling of the infinitely precise quotient. We want the floor, 596 * and we have it iff the remainder's sign matches y's. 597 */ 598 if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) { 599 xmody += y; 600 --xdivy; 601 assert(xmody && ((y ^ xmody) >= 0)); 602 } 603 *p_xdivy = xdivy; 604 *p_xmody = xmody; 605 return DIVMOD_OK; 606 } 607 608 static PyObject * 609 int_div(PyIntObject *x, PyIntObject *y) 610 { 611 long xi, yi; 612 long d, m; 613 CONVERT_TO_LONG(x, xi); 614 CONVERT_TO_LONG(y, yi); 615 switch (i_divmod(xi, yi, &d, &m)) { 616 case DIVMOD_OK: 617 return PyInt_FromLong(d); 618 case DIVMOD_OVERFLOW: 619 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x, 620 (PyObject *)y); 621 default: 622 return NULL; 623 } 624 } 625 626 static PyObject * 627 int_classic_div(PyIntObject *x, PyIntObject *y) 628 { 629 long xi, yi; 630 long d, m; 631 CONVERT_TO_LONG(x, xi); 632 CONVERT_TO_LONG(y, yi); 633 if (Py_DivisionWarningFlag && 634 PyErr_Warn(PyExc_DeprecationWarning, "classic int division") < 0) 635 return NULL; 636 switch (i_divmod(xi, yi, &d, &m)) { 637 case DIVMOD_OK: 638 return PyInt_FromLong(d); 639 case DIVMOD_OVERFLOW: 640 return PyLong_Type.tp_as_number->nb_divide((PyObject *)x, 641 (PyObject *)y); 642 default: 643 return NULL; 644 } 645 } 646 647 static PyObject * 648 int_true_divide(PyIntObject *x, PyIntObject *y) 649 { 650 long xi, yi; 651 /* If they aren't both ints, give someone else a chance. In 652 particular, this lets int/long get handled by longs, which 653 underflows to 0 gracefully if the long is too big to convert 654 to float. */ 655 CONVERT_TO_LONG(x, xi); 656 CONVERT_TO_LONG(y, yi); 657 if (yi == 0) { 658 PyErr_SetString(PyExc_ZeroDivisionError, 659 "division by zero"); 660 return NULL; 661 } 662 if (xi == 0) 663 return PyFloat_FromDouble(yi < 0 ? -0.0 : 0.0); 664 665 #define WIDTH_OF_ULONG (CHAR_BIT*SIZEOF_LONG) 666 #if DBL_MANT_DIG < WIDTH_OF_ULONG 667 if ((xi >= 0 ? 0UL + xi : 0UL - xi) >> DBL_MANT_DIG || 668 (yi >= 0 ? 0UL + yi : 0UL - yi) >> DBL_MANT_DIG) 669 /* Large x or y. Use long integer arithmetic. */ 670 return PyLong_Type.tp_as_number->nb_true_divide( 671 (PyObject *)x, (PyObject *)y); 672 else 673 #endif 674 /* Both ints can be exactly represented as doubles. Do a 675 floating-point division. */ 676 return PyFloat_FromDouble((double)xi / (double)yi); 677 } 678 679 static PyObject * 680 int_mod(PyIntObject *x, PyIntObject *y) 681 { 682 long xi, yi; 683 long d, m; 684 CONVERT_TO_LONG(x, xi); 685 CONVERT_TO_LONG(y, yi); 686 switch (i_divmod(xi, yi, &d, &m)) { 687 case DIVMOD_OK: 688 return PyInt_FromLong(m); 689 case DIVMOD_OVERFLOW: 690 return PyLong_Type.tp_as_number->nb_remainder((PyObject *)x, 691 (PyObject *)y); 692 default: 693 return NULL; 694 } 695 } 696 697 static PyObject * 698 int_divmod(PyIntObject *x, PyIntObject *y) 699 { 700 long xi, yi; 701 long d, m; 702 CONVERT_TO_LONG(x, xi); 703 CONVERT_TO_LONG(y, yi); 704 switch (i_divmod(xi, yi, &d, &m)) { 705 case DIVMOD_OK: 706 return Py_BuildValue("(ll)", d, m); 707 case DIVMOD_OVERFLOW: 708 return PyLong_Type.tp_as_number->nb_divmod((PyObject *)x, 709 (PyObject *)y); 710 default: 711 return NULL; 712 } 713 } 714 715 static PyObject * 716 int_pow(PyIntObject *v, PyIntObject *w, PyIntObject *z) 717 { 718 register long iv, iw, iz=0, ix, temp, prev; 719 CONVERT_TO_LONG(v, iv); 720 CONVERT_TO_LONG(w, iw); 721 if (iw < 0) { 722 if ((PyObject *)z != Py_None) { 723 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument " 724 "cannot be negative when 3rd argument specified"); 725 return NULL; 726 } 727 /* Return a float. This works because we know that 728 this calls float_pow() which converts its 729 arguments to double. */ 730 return PyFloat_Type.tp_as_number->nb_power( 731 (PyObject *)v, (PyObject *)w, (PyObject *)z); 732 } 733 if ((PyObject *)z != Py_None) { 734 CONVERT_TO_LONG(z, iz); 735 if (iz == 0) { 736 PyErr_SetString(PyExc_ValueError, 737 "pow() 3rd argument cannot be 0"); 738 return NULL; 739 } 740 } 741 /* 742 * XXX: The original exponentiation code stopped looping 743 * when temp hit zero; this code will continue onwards 744 * unnecessarily, but at least it won't cause any errors. 745 * Hopefully the speed improvement from the fast exponentiation 746 * will compensate for the slight inefficiency. 747 * XXX: Better handling of overflows is desperately needed. 748 */ 749 temp = iv; 750 ix = 1; 751 while (iw > 0) { 752 prev = ix; /* Save value for overflow check */ 753 if (iw & 1) { 754 ix = ix*temp; 755 if (temp == 0) 756 break; /* Avoid ix / 0 */ 757 if (ix / temp != prev) { 758 return PyLong_Type.tp_as_number->nb_power( 759 (PyObject *)v, 760 (PyObject *)w, 761 (PyObject *)z); 762 } 763 } 764 iw >>= 1; /* Shift exponent down by 1 bit */ 765 if (iw==0) break; 766 prev = temp; 767 temp *= temp; /* Square the value of temp */ 768 if (prev != 0 && temp / prev != prev) { 769 return PyLong_Type.tp_as_number->nb_power( 770 (PyObject *)v, (PyObject *)w, (PyObject *)z); 771 } 772 if (iz) { 773 /* If we did a multiplication, perform a modulo */ 774 ix = ix % iz; 775 temp = temp % iz; 776 } 777 } 778 if (iz) { 779 long div, mod; 780 switch (i_divmod(ix, iz, &div, &mod)) { 781 case DIVMOD_OK: 782 ix = mod; 783 break; 784 case DIVMOD_OVERFLOW: 785 return PyLong_Type.tp_as_number->nb_power( 786 (PyObject *)v, (PyObject *)w, (PyObject *)z); 787 default: 788 return NULL; 789 } 790 } 791 return PyInt_FromLong(ix); 792 } 793 794 static PyObject * 795 int_neg(PyIntObject *v) 796 { 797 register long a; 798 a = v->ob_ival; 799 /* check for overflow */ 800 if (UNARY_NEG_WOULD_OVERFLOW(a)) { 801 PyObject *o = PyLong_FromLong(a); 802 if (o != NULL) { 803 PyObject *result = PyNumber_Negative(o); 804 Py_DECREF(o); 805 return result; 806 } 807 return NULL; 808 } 809 return PyInt_FromLong(-a); 810 } 811 812 static PyObject * 813 int_abs(PyIntObject *v) 814 { 815 if (v->ob_ival >= 0) 816 return int_int(v); 817 else 818 return int_neg(v); 819 } 820 821 static int 822 int_nonzero(PyIntObject *v) 823 { 824 return v->ob_ival != 0; 825 } 826 827 static PyObject * 828 int_invert(PyIntObject *v) 829 { 830 return PyInt_FromLong(~v->ob_ival); 831 } 832 833 static PyObject * 834 int_lshift(PyIntObject *v, PyIntObject *w) 835 { 836 long a, b, c; 837 PyObject *vv, *ww, *result; 838 839 CONVERT_TO_LONG(v, a); 840 CONVERT_TO_LONG(w, b); 841 if (b < 0) { 842 PyErr_SetString(PyExc_ValueError, "negative shift count"); 843 return NULL; 844 } 845 if (a == 0 || b == 0) 846 return int_int(v); 847 if (b >= LONG_BIT) { 848 vv = PyLong_FromLong(PyInt_AS_LONG(v)); 849 if (vv == NULL) 850 return NULL; 851 ww = PyLong_FromLong(PyInt_AS_LONG(w)); 852 if (ww == NULL) { 853 Py_DECREF(vv); 854 return NULL; 855 } 856 result = PyNumber_Lshift(vv, ww); 857 Py_DECREF(vv); 858 Py_DECREF(ww); 859 return result; 860 } 861 c = a << b; 862 if (a != Py_ARITHMETIC_RIGHT_SHIFT(long, c, b)) { 863 vv = PyLong_FromLong(PyInt_AS_LONG(v)); 864 if (vv == NULL) 865 return NULL; 866 ww = PyLong_FromLong(PyInt_AS_LONG(w)); 867 if (ww == NULL) { 868 Py_DECREF(vv); 869 return NULL; 870 } 871 result = PyNumber_Lshift(vv, ww); 872 Py_DECREF(vv); 873 Py_DECREF(ww); 874 return result; 875 } 876 return PyInt_FromLong(c); 877 } 878 879 static PyObject * 880 int_rshift(PyIntObject *v, PyIntObject *w) 881 { 882 register long a, b; 883 CONVERT_TO_LONG(v, a); 884 CONVERT_TO_LONG(w, b); 885 if (b < 0) { 886 PyErr_SetString(PyExc_ValueError, "negative shift count"); 887 return NULL; 888 } 889 if (a == 0 || b == 0) 890 return int_int(v); 891 if (b >= LONG_BIT) { 892 if (a < 0) 893 a = -1; 894 else 895 a = 0; 896 } 897 else { 898 a = Py_ARITHMETIC_RIGHT_SHIFT(long, a, b); 899 } 900 return PyInt_FromLong(a); 901 } 902 903 static PyObject * 904 int_and(PyIntObject *v, PyIntObject *w) 905 { 906 register long a, b; 907 CONVERT_TO_LONG(v, a); 908 CONVERT_TO_LONG(w, b); 909 return PyInt_FromLong(a & b); 910 } 911 912 static PyObject * 913 int_xor(PyIntObject *v, PyIntObject *w) 914 { 915 register long a, b; 916 CONVERT_TO_LONG(v, a); 917 CONVERT_TO_LONG(w, b); 918 return PyInt_FromLong(a ^ b); 919 } 920 921 static PyObject * 922 int_or(PyIntObject *v, PyIntObject *w) 923 { 924 register long a, b; 925 CONVERT_TO_LONG(v, a); 926 CONVERT_TO_LONG(w, b); 927 return PyInt_FromLong(a | b); 928 } 929 930 static int 931 int_coerce(PyObject **pv, PyObject **pw) 932 { 933 if (PyInt_Check(*pw)) { 934 Py_INCREF(*pv); 935 Py_INCREF(*pw); 936 return 0; 937 } 938 return 1; /* Can't do it */ 939 } 940 941 static PyObject * 942 int_int(PyIntObject *v) 943 { 944 if (PyInt_CheckExact(v)) 945 Py_INCREF(v); 946 else 947 v = (PyIntObject *)PyInt_FromLong(v->ob_ival); 948 return (PyObject *)v; 949 } 950 951 static PyObject * 952 int_long(PyIntObject *v) 953 { 954 return PyLong_FromLong((v -> ob_ival)); 955 } 956 957 static const unsigned char BitLengthTable[32] = { 958 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 959 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 960 }; 961 962 static int 963 bits_in_ulong(unsigned long d) 964 { 965 int d_bits = 0; 966 while (d >= 32) { 967 d_bits += 6; 968 d >>= 6; 969 } 970 d_bits += (int)BitLengthTable[d]; 971 return d_bits; 972 } 973 974 #if 8*SIZEOF_LONG-1 <= DBL_MANT_DIG 975 /* Every Python int can be exactly represented as a float. */ 976 977 static PyObject * 978 int_float(PyIntObject *v) 979 { 980 return PyFloat_FromDouble((double)(v -> ob_ival)); 981 } 982 983 #else 984 /* Here not all Python ints are exactly representable as floats, so we may 985 have to round. We do this manually, since the C standards don't specify 986 whether converting an integer to a float rounds up or down */ 987 988 static PyObject * 989 int_float(PyIntObject *v) 990 { 991 unsigned long abs_ival, lsb; 992 int round_up; 993 994 if (v->ob_ival < 0) 995 abs_ival = 0U-(unsigned long)v->ob_ival; 996 else 997 abs_ival = (unsigned long)v->ob_ival; 998 if (abs_ival < (1L << DBL_MANT_DIG)) 999 /* small integer; no need to round */ 1000 return PyFloat_FromDouble((double)v->ob_ival); 1001 1002 /* Round abs_ival to MANT_DIG significant bits, using the 1003 round-half-to-even rule. abs_ival & lsb picks out the 'rounding' 1004 bit: the first bit after the most significant MANT_DIG bits of 1005 abs_ival. We round up if this bit is set, provided that either: 1006 1007 (1) abs_ival isn't exactly halfway between two floats, in which 1008 case at least one of the bits following the rounding bit must be 1009 set; i.e., abs_ival & lsb-1 != 0, or: 1010 1011 (2) the resulting rounded value has least significant bit 0; or 1012 in other words the bit above the rounding bit is set (this is the 1013 'to-even' bit of round-half-to-even); i.e., abs_ival & 2*lsb != 0 1014 1015 The condition "(1) or (2)" equates to abs_ival & 3*lsb-1 != 0. */ 1016 1017 lsb = 1L << (bits_in_ulong(abs_ival)-DBL_MANT_DIG-1); 1018 round_up = (abs_ival & lsb) && (abs_ival & (3*lsb-1)); 1019 abs_ival &= -2*lsb; 1020 if (round_up) 1021 abs_ival += 2*lsb; 1022 return PyFloat_FromDouble(v->ob_ival < 0 ? 1023 -(double)abs_ival : 1024 (double)abs_ival); 1025 } 1026 1027 #endif 1028 1029 static PyObject * 1030 int_oct(PyIntObject *v) 1031 { 1032 return _PyInt_Format(v, 8, 0); 1033 } 1034 1035 static PyObject * 1036 int_hex(PyIntObject *v) 1037 { 1038 return _PyInt_Format(v, 16, 0); 1039 } 1040 1041 static PyObject * 1042 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds); 1043 1044 static PyObject * 1045 int_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 1046 { 1047 PyObject *x = NULL; 1048 int base = -909; 1049 static char *kwlist[] = {"x", "base", 0}; 1050 1051 if (type != &PyInt_Type) 1052 return int_subtype_new(type, args, kwds); /* Wimp out */ 1053 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist, 1054 &x, &base)) 1055 return NULL; 1056 if (x == NULL) 1057 return PyInt_FromLong(0L); 1058 if (base == -909) 1059 return PyNumber_Int(x); 1060 if (PyString_Check(x)) { 1061 /* Since PyInt_FromString doesn't have a length parameter, 1062 * check here for possible NULs in the string. */ 1063 char *string = PyString_AS_STRING(x); 1064 if (strlen(string) != PyString_Size(x)) { 1065 /* create a repr() of the input string, 1066 * just like PyInt_FromString does */ 1067 PyObject *srepr; 1068 srepr = PyObject_Repr(x); 1069 if (srepr == NULL) 1070 return NULL; 1071 PyErr_Format(PyExc_ValueError, 1072 "invalid literal for int() with base %d: %s", 1073 base, PyString_AS_STRING(srepr)); 1074 Py_DECREF(srepr); 1075 return NULL; 1076 } 1077 return PyInt_FromString(string, NULL, base); 1078 } 1079 #ifdef Py_USING_UNICODE 1080 if (PyUnicode_Check(x)) 1081 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(x), 1082 PyUnicode_GET_SIZE(x), 1083 base); 1084 #endif 1085 PyErr_SetString(PyExc_TypeError, 1086 "int() can't convert non-string with explicit base"); 1087 return NULL; 1088 } 1089 1090 /* Wimpy, slow approach to tp_new calls for subtypes of int: 1091 first create a regular int from whatever arguments we got, 1092 then allocate a subtype instance and initialize its ob_ival 1093 from the regular int. The regular int is then thrown away. 1094 */ 1095 static PyObject * 1096 int_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 1097 { 1098 PyObject *tmp, *newobj; 1099 long ival; 1100 1101 assert(PyType_IsSubtype(type, &PyInt_Type)); 1102 tmp = int_new(&PyInt_Type, args, kwds); 1103 if (tmp == NULL) 1104 return NULL; 1105 if (!PyInt_Check(tmp)) { 1106 ival = PyLong_AsLong(tmp); 1107 if (ival == -1 && PyErr_Occurred()) { 1108 Py_DECREF(tmp); 1109 return NULL; 1110 } 1111 } else { 1112 ival = ((PyIntObject *)tmp)->ob_ival; 1113 } 1114 1115 newobj = type->tp_alloc(type, 0); 1116 if (newobj == NULL) { 1117 Py_DECREF(tmp); 1118 return NULL; 1119 } 1120 ((PyIntObject *)newobj)->ob_ival = ival; 1121 Py_DECREF(tmp); 1122 return newobj; 1123 } 1124 1125 static PyObject * 1126 int_getnewargs(PyIntObject *v) 1127 { 1128 return Py_BuildValue("(l)", v->ob_ival); 1129 } 1130 1131 static PyObject * 1132 int_get0(PyIntObject *v, void *context) { 1133 return PyInt_FromLong(0L); 1134 } 1135 1136 static PyObject * 1137 int_get1(PyIntObject *v, void *context) { 1138 return PyInt_FromLong(1L); 1139 } 1140 1141 /* Convert an integer to a decimal string. On many platforms, this 1142 will be significantly faster than the general arbitrary-base 1143 conversion machinery in _PyInt_Format, thanks to optimization 1144 opportunities offered by division by a compile-time constant. */ 1145 static PyObject * 1146 int_to_decimal_string(PyIntObject *v) { 1147 char buf[sizeof(long)*CHAR_BIT/3+6], *p, *bufend; 1148 long n = v->ob_ival; 1149 unsigned long absn; 1150 p = bufend = buf + sizeof(buf); 1151 absn = n < 0 ? 0UL - n : n; 1152 do { 1153 *--p = '0' + (char)(absn % 10); 1154 absn /= 10; 1155 } while (absn); 1156 if (n < 0) 1157 *--p = '-'; 1158 return PyString_FromStringAndSize(p, bufend - p); 1159 } 1160 1161 /* Convert an integer to the given base. Returns a string. 1162 If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'. 1163 If newstyle is zero, then use the pre-2.6 behavior of octal having 1164 a leading "0" */ 1165 PyAPI_FUNC(PyObject*) 1166 _PyInt_Format(PyIntObject *v, int base, int newstyle) 1167 { 1168 /* There are no doubt many, many ways to optimize this, using code 1169 similar to _PyLong_Format */ 1170 long n = v->ob_ival; 1171 int negative = n < 0; 1172 int is_zero = n == 0; 1173 1174 /* For the reasoning behind this size, see 1175 http://c-faq.com/misc/hexio.html. Then, add a few bytes for 1176 the possible sign and prefix "0[box]" */ 1177 char buf[sizeof(n)*CHAR_BIT+6]; 1178 1179 /* Start by pointing to the end of the buffer. We fill in from 1180 the back forward. */ 1181 char* p = &buf[sizeof(buf)]; 1182 1183 assert(base >= 2 && base <= 36); 1184 1185 /* Special case base 10, for speed */ 1186 if (base == 10) 1187 return int_to_decimal_string(v); 1188 1189 do { 1190 /* I'd use i_divmod, except it doesn't produce the results 1191 I want when n is negative. So just duplicate the salient 1192 part here. */ 1193 long div = n / base; 1194 long mod = n - div * base; 1195 1196 /* convert abs(mod) to the right character in [0-9, a-z] */ 1197 char cdigit = (char)(mod < 0 ? -mod : mod); 1198 cdigit += (cdigit < 10) ? '0' : 'a'-10; 1199 *--p = cdigit; 1200 1201 n = div; 1202 } while(n); 1203 1204 if (base == 2) { 1205 *--p = 'b'; 1206 *--p = '0'; 1207 } 1208 else if (base == 8) { 1209 if (newstyle) { 1210 *--p = 'o'; 1211 *--p = '0'; 1212 } 1213 else 1214 if (!is_zero) 1215 *--p = '0'; 1216 } 1217 else if (base == 16) { 1218 *--p = 'x'; 1219 *--p = '0'; 1220 } 1221 else { 1222 *--p = '#'; 1223 *--p = '0' + base%10; 1224 if (base > 10) 1225 *--p = '0' + base/10; 1226 } 1227 if (negative) 1228 *--p = '-'; 1229 1230 return PyString_FromStringAndSize(p, &buf[sizeof(buf)] - p); 1231 } 1232 1233 static PyObject * 1234 int__format__(PyObject *self, PyObject *args) 1235 { 1236 PyObject *format_spec; 1237 1238 if (!PyArg_ParseTuple(args, "O:__format__", &format_spec)) 1239 return NULL; 1240 if (PyBytes_Check(format_spec)) 1241 return _PyInt_FormatAdvanced(self, 1242 PyBytes_AS_STRING(format_spec), 1243 PyBytes_GET_SIZE(format_spec)); 1244 if (PyUnicode_Check(format_spec)) { 1245 /* Convert format_spec to a str */ 1246 PyObject *result; 1247 PyObject *str_spec = PyObject_Str(format_spec); 1248 1249 if (str_spec == NULL) 1250 return NULL; 1251 1252 result = _PyInt_FormatAdvanced(self, 1253 PyBytes_AS_STRING(str_spec), 1254 PyBytes_GET_SIZE(str_spec)); 1255 1256 Py_DECREF(str_spec); 1257 return result; 1258 } 1259 PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode"); 1260 return NULL; 1261 } 1262 1263 static PyObject * 1264 int_bit_length(PyIntObject *v) 1265 { 1266 unsigned long n; 1267 1268 if (v->ob_ival < 0) 1269 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */ 1270 n = 0U-(unsigned long)v->ob_ival; 1271 else 1272 n = (unsigned long)v->ob_ival; 1273 1274 return PyInt_FromLong(bits_in_ulong(n)); 1275 } 1276 1277 PyDoc_STRVAR(int_bit_length_doc, 1278 "int.bit_length() -> int\n\ 1279 \n\ 1280 Number of bits necessary to represent self in binary.\n\ 1281 >>> bin(37)\n\ 1282 '0b100101'\n\ 1283 >>> (37).bit_length()\n\ 1284 6"); 1285 1286 #if 0 1287 static PyObject * 1288 int_is_finite(PyObject *v) 1289 { 1290 Py_RETURN_TRUE; 1291 } 1292 #endif 1293 1294 static PyMethodDef int_methods[] = { 1295 {"conjugate", (PyCFunction)int_int, METH_NOARGS, 1296 "Returns self, the complex conjugate of any int."}, 1297 {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS, 1298 int_bit_length_doc}, 1299 #if 0 1300 {"is_finite", (PyCFunction)int_is_finite, METH_NOARGS, 1301 "Returns always True."}, 1302 #endif 1303 {"__trunc__", (PyCFunction)int_int, METH_NOARGS, 1304 "Truncating an Integral returns itself."}, 1305 {"__getnewargs__", (PyCFunction)int_getnewargs, METH_NOARGS}, 1306 {"__format__", (PyCFunction)int__format__, METH_VARARGS}, 1307 {NULL, NULL} /* sentinel */ 1308 }; 1309 1310 static PyGetSetDef int_getset[] = { 1311 {"real", 1312 (getter)int_int, (setter)NULL, 1313 "the real part of a complex number", 1314 NULL}, 1315 {"imag", 1316 (getter)int_get0, (setter)NULL, 1317 "the imaginary part of a complex number", 1318 NULL}, 1319 {"numerator", 1320 (getter)int_int, (setter)NULL, 1321 "the numerator of a rational number in lowest terms", 1322 NULL}, 1323 {"denominator", 1324 (getter)int_get1, (setter)NULL, 1325 "the denominator of a rational number in lowest terms", 1326 NULL}, 1327 {NULL} /* Sentinel */ 1328 }; 1329 1330 PyDoc_STRVAR(int_doc, 1331 "int(x[, base]) -> integer\n\ 1332 \n\ 1333 Convert a string or number to an integer, if possible. A floating point\n\ 1334 argument will be truncated towards zero (this does not include a string\n\ 1335 representation of a floating point number!) When converting a string, use\n\ 1336 the optional base. It is an error to supply a base when converting a\n\ 1337 non-string. If base is zero, the proper base is guessed based on the\n\ 1338 string content. If the argument is outside the integer range a\n\ 1339 long object will be returned instead."); 1340 1341 static PyNumberMethods int_as_number = { 1342 (binaryfunc)int_add, /*nb_add*/ 1343 (binaryfunc)int_sub, /*nb_subtract*/ 1344 (binaryfunc)int_mul, /*nb_multiply*/ 1345 (binaryfunc)int_classic_div, /*nb_divide*/ 1346 (binaryfunc)int_mod, /*nb_remainder*/ 1347 (binaryfunc)int_divmod, /*nb_divmod*/ 1348 (ternaryfunc)int_pow, /*nb_power*/ 1349 (unaryfunc)int_neg, /*nb_negative*/ 1350 (unaryfunc)int_int, /*nb_positive*/ 1351 (unaryfunc)int_abs, /*nb_absolute*/ 1352 (inquiry)int_nonzero, /*nb_nonzero*/ 1353 (unaryfunc)int_invert, /*nb_invert*/ 1354 (binaryfunc)int_lshift, /*nb_lshift*/ 1355 (binaryfunc)int_rshift, /*nb_rshift*/ 1356 (binaryfunc)int_and, /*nb_and*/ 1357 (binaryfunc)int_xor, /*nb_xor*/ 1358 (binaryfunc)int_or, /*nb_or*/ 1359 int_coerce, /*nb_coerce*/ 1360 (unaryfunc)int_int, /*nb_int*/ 1361 (unaryfunc)int_long, /*nb_long*/ 1362 (unaryfunc)int_float, /*nb_float*/ 1363 (unaryfunc)int_oct, /*nb_oct*/ 1364 (unaryfunc)int_hex, /*nb_hex*/ 1365 0, /*nb_inplace_add*/ 1366 0, /*nb_inplace_subtract*/ 1367 0, /*nb_inplace_multiply*/ 1368 0, /*nb_inplace_divide*/ 1369 0, /*nb_inplace_remainder*/ 1370 0, /*nb_inplace_power*/ 1371 0, /*nb_inplace_lshift*/ 1372 0, /*nb_inplace_rshift*/ 1373 0, /*nb_inplace_and*/ 1374 0, /*nb_inplace_xor*/ 1375 0, /*nb_inplace_or*/ 1376 (binaryfunc)int_div, /* nb_floor_divide */ 1377 (binaryfunc)int_true_divide, /* nb_true_divide */ 1378 0, /* nb_inplace_floor_divide */ 1379 0, /* nb_inplace_true_divide */ 1380 (unaryfunc)int_int, /* nb_index */ 1381 }; 1382 1383 PyTypeObject PyInt_Type = { 1384 PyVarObject_HEAD_INIT(&PyType_Type, 0) 1385 "int", 1386 sizeof(PyIntObject), 1387 0, 1388 (destructor)int_dealloc, /* tp_dealloc */ 1389 (printfunc)int_print, /* tp_print */ 1390 0, /* tp_getattr */ 1391 0, /* tp_setattr */ 1392 (cmpfunc)int_compare, /* tp_compare */ 1393 (reprfunc)int_to_decimal_string, /* tp_repr */ 1394 &int_as_number, /* tp_as_number */ 1395 0, /* tp_as_sequence */ 1396 0, /* tp_as_mapping */ 1397 (hashfunc)int_hash, /* tp_hash */ 1398 0, /* tp_call */ 1399 (reprfunc)int_to_decimal_string, /* tp_str */ 1400 PyObject_GenericGetAttr, /* tp_getattro */ 1401 0, /* tp_setattro */ 1402 0, /* tp_as_buffer */ 1403 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES | 1404 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS, /* tp_flags */ 1405 int_doc, /* tp_doc */ 1406 0, /* tp_traverse */ 1407 0, /* tp_clear */ 1408 0, /* tp_richcompare */ 1409 0, /* tp_weaklistoffset */ 1410 0, /* tp_iter */ 1411 0, /* tp_iternext */ 1412 int_methods, /* tp_methods */ 1413 0, /* tp_members */ 1414 int_getset, /* tp_getset */ 1415 0, /* tp_base */ 1416 0, /* tp_dict */ 1417 0, /* tp_descr_get */ 1418 0, /* tp_descr_set */ 1419 0, /* tp_dictoffset */ 1420 0, /* tp_init */ 1421 0, /* tp_alloc */ 1422 int_new, /* tp_new */ 1423 (freefunc)int_free, /* tp_free */ 1424 }; 1425 1426 int 1427 _PyInt_Init(void) 1428 { 1429 PyIntObject *v; 1430 int ival; 1431 #if NSMALLNEGINTS + NSMALLPOSINTS > 0 1432 for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) { 1433 if (!free_list && (free_list = fill_free_list()) == NULL) 1434 return 0; 1435 /* PyObject_New is inlined */ 1436 v = free_list; 1437 free_list = (PyIntObject *)Py_TYPE(v); 1438 PyObject_INIT(v, &PyInt_Type); 1439 v->ob_ival = ival; 1440 small_ints[ival + NSMALLNEGINTS] = v; 1441 } 1442 #endif 1443 return 1; 1444 } 1445 1446 int 1447 PyInt_ClearFreeList(void) 1448 { 1449 PyIntObject *p; 1450 PyIntBlock *list, *next; 1451 int i; 1452 int u; /* remaining unfreed ints per block */ 1453 int freelist_size = 0; 1454 1455 list = block_list; 1456 block_list = NULL; 1457 free_list = NULL; 1458 while (list != NULL) { 1459 u = 0; 1460 for (i = 0, p = &list->objects[0]; 1461 i < N_INTOBJECTS; 1462 i++, p++) { 1463 if (PyInt_CheckExact(p) && p->ob_refcnt != 0) 1464 u++; 1465 } 1466 next = list->next; 1467 if (u) { 1468 list->next = block_list; 1469 block_list = list; 1470 for (i = 0, p = &list->objects[0]; 1471 i < N_INTOBJECTS; 1472 i++, p++) { 1473 if (!PyInt_CheckExact(p) || 1474 p->ob_refcnt == 0) { 1475 Py_TYPE(p) = (struct _typeobject *) 1476 free_list; 1477 free_list = p; 1478 } 1479 #if NSMALLNEGINTS + NSMALLPOSINTS > 0 1480 else if (-NSMALLNEGINTS <= p->ob_ival && 1481 p->ob_ival < NSMALLPOSINTS && 1482 small_ints[p->ob_ival + 1483 NSMALLNEGINTS] == NULL) { 1484 Py_INCREF(p); 1485 small_ints[p->ob_ival + 1486 NSMALLNEGINTS] = p; 1487 } 1488 #endif 1489 } 1490 } 1491 else { 1492 PyMem_FREE(list); 1493 } 1494 freelist_size += u; 1495 list = next; 1496 } 1497 1498 return freelist_size; 1499 } 1500 1501 void 1502 PyInt_Fini(void) 1503 { 1504 PyIntObject *p; 1505 PyIntBlock *list; 1506 int i; 1507 int u; /* total unfreed ints per block */ 1508 1509 #if NSMALLNEGINTS + NSMALLPOSINTS > 0 1510 PyIntObject **q; 1511 1512 i = NSMALLNEGINTS + NSMALLPOSINTS; 1513 q = small_ints; 1514 while (--i >= 0) { 1515 Py_XDECREF(*q); 1516 *q++ = NULL; 1517 } 1518 #endif 1519 u = PyInt_ClearFreeList(); 1520 if (!Py_VerboseFlag) 1521 return; 1522 fprintf(stderr, "# cleanup ints"); 1523 if (!u) { 1524 fprintf(stderr, "\n"); 1525 } 1526 else { 1527 fprintf(stderr, 1528 ": %d unfreed int%s\n", 1529 u, u == 1 ? "" : "s"); 1530 } 1531 if (Py_VerboseFlag > 1) { 1532 list = block_list; 1533 while (list != NULL) { 1534 for (i = 0, p = &list->objects[0]; 1535 i < N_INTOBJECTS; 1536 i++, p++) { 1537 if (PyInt_CheckExact(p) && p->ob_refcnt != 0) 1538 /* XXX(twouters) cast refcount to 1539 long until %zd is universally 1540 available 1541 */ 1542 fprintf(stderr, 1543 "# <int at %p, refcnt=%ld, val=%ld>\n", 1544 p, (long)p->ob_refcnt, 1545 p->ob_ival); 1546 } 1547 list = list->next; 1548 } 1549 } 1550 } 1551
