Objects/intobject.c

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