Objects/intobject.c

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