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 Py_ssize_t quick_int_allocs;
  82 Py_ssize_t 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 (PyBytes_Check(format_spec))
1120                 return _PyInt_FormatAdvanced(self,
1121                                              PyBytes_AS_STRING(format_spec),
1122                                              PyBytes_GET_SIZE(format_spec));
1123         if (PyUnicode_Check(format_spec)) {
1124                 /* Convert format_spec to a str */
1125                 PyObject *result;
1126                 PyObject *str_spec = PyObject_Str(format_spec);
1127
1128                 if (str_spec == NULL)
1129                         return NULL;
1130
1131                 result = _PyInt_FormatAdvanced(self,
1132                                                PyBytes_AS_STRING(str_spec),
1133                                                PyBytes_GET_SIZE(str_spec));
1134
1135                 Py_DECREF(str_spec);
1136                 return result;
1137         }
1138         PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
1139         return NULL;
1140 }
1141
1142 static const unsigned char BitLengthTable[32] = {
1143         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
1144         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
1145 };
1146
1147 static PyObject *
1148 int_bit_length(PyIntObject *v)
1149 {
1150         unsigned long n;
1151         long r = 0;
1152
1153         if (v->ob_ival < 0)
1154                 /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
1155                 n = 0U-(unsigned long)v->ob_ival;
1156         else
1157                 n = (unsigned long)v->ob_ival;
1158
1159         while (n >= 32) {
1160                 r += 6;
1161                 n >>= 6;
1162         }
1163         r += (long)(BitLengthTable[n]);
1164         return PyInt_FromLong(r);
1165 }
1166
1167 PyDoc_STRVAR(int_bit_length_doc,
1168 "int.bit_length() -> int\n\
1169 \n\
1170 Number of bits necessary to represent self in binary.\n\
1171 >>> bin(37)\n\
1172 '0b100101'\n\
1173 >>> (37).bit_length()\n\
1174 6");
1175
1176 #if 0
1177 static PyObject *
1178 int_is_finite(PyObject *v)
1179 {
1180         Py_RETURN_TRUE;
1181 }
1182 #endif
1183
1184 static PyMethodDef int_methods[] = {
1185         {"conjugate",   (PyCFunction)int_int,   METH_NOARGS,
1186          "Returns self, the complex conjugate of any int."},
1187         {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS,
1188          int_bit_length_doc},
1189 #if 0
1190         {"is_finite",   (PyCFunction)int_is_finite,     METH_NOARGS,
1191          "Returns always True."},
1192 #endif
1193         {"__trunc__",   (PyCFunction)int_int,   METH_NOARGS,
1194          "Truncating an Integral returns itself."},
1195         {"__getnewargs__",      (PyCFunction)int_getnewargs,    METH_NOARGS},
1196         {"__format__", (PyCFunction)int__format__, METH_VARARGS},
1197         {NULL,          NULL}           /* sentinel */
1198 };
1199
1200 static PyGetSetDef int_getset[] = {
1201         {"real",
1202          (getter)int_int, (setter)NULL,
1203          "the real part of a complex number",
1204          NULL},
1205         {"imag",
1206          (getter)int_getN, (setter)NULL,
1207          "the imaginary part of a complex number",
1208          (void*)0},
1209         {"numerator",
1210          (getter)int_int, (setter)NULL,
1211          "the numerator of a rational number in lowest terms",
1212          NULL},
1213         {"denominator",
1214          (getter)int_getN, (setter)NULL,
1215          "the denominator of a rational number in lowest terms",
1216          (void*)1},
1217         {NULL}  /* Sentinel */
1218 };
1219
1220 PyDoc_STRVAR(int_doc,
1221 "int(x[, base]) -> integer\n\
1222 \n\
1223 Convert a string or number to an integer, if possible.  A floating point\n\
1224 argument will be truncated towards zero (this does not include a string\n\
1225 representation of a floating point number!)  When converting a string, use\n\
1226 the optional base.  It is an error to supply a base when converting a\n\
1227 non-string.  If base is zero, the proper base is guessed based on the\n\
1228 string content.  If the argument is outside the integer range a\n\
1229 long object will be returned instead.");
1230
1231 static PyNumberMethods int_as_number = {
1232         (binaryfunc)int_add,    /*nb_add*/
1233         (binaryfunc)int_sub,    /*nb_subtract*/
1234         (binaryfunc)int_mul,    /*nb_multiply*/
1235         (binaryfunc)int_classic_div, /*nb_divide*/
1236         (binaryfunc)int_mod,    /*nb_remainder*/
1237         (binaryfunc)int_divmod, /*nb_divmod*/
1238         (ternaryfunc)int_pow,   /*nb_power*/
1239         (unaryfunc)int_neg,     /*nb_negative*/
1240         (unaryfunc)int_int,     /*nb_positive*/
1241         (unaryfunc)int_abs,     /*nb_absolute*/
1242         (inquiry)int_nonzero,   /*nb_nonzero*/
1243         (unaryfunc)int_invert,  /*nb_invert*/
1244         (binaryfunc)int_lshift, /*nb_lshift*/
1245         (binaryfunc)int_rshift, /*nb_rshift*/
1246         (binaryfunc)int_and,    /*nb_and*/
1247         (binaryfunc)int_xor,    /*nb_xor*/
1248         (binaryfunc)int_or,     /*nb_or*/
1249         int_coerce,             /*nb_coerce*/
1250         (unaryfunc)int_int,     /*nb_int*/
1251         (unaryfunc)int_long,    /*nb_long*/
1252         (unaryfunc)int_float,   /*nb_float*/
1253         (unaryfunc)int_oct,     /*nb_oct*/
1254         (unaryfunc)int_hex,     /*nb_hex*/
1255         0,                      /*nb_inplace_add*/
1256         0,                      /*nb_inplace_subtract*/
1257         0,                      /*nb_inplace_multiply*/
1258         0,                      /*nb_inplace_divide*/
1259         0,                      /*nb_inplace_remainder*/
1260         0,                      /*nb_inplace_power*/
1261         0,                      /*nb_inplace_lshift*/
1262         0,                      /*nb_inplace_rshift*/
1263         0,                      /*nb_inplace_and*/
1264         0,                      /*nb_inplace_xor*/
1265         0,                      /*nb_inplace_or*/
1266         (binaryfunc)int_div,    /* nb_floor_divide */
1267         int_true_divide,        /* nb_true_divide */
1268         0,                      /* nb_inplace_floor_divide */
1269         0,                      /* nb_inplace_true_divide */
1270         (unaryfunc)int_int,     /* nb_index */
1271 };
1272
1273 PyTypeObject PyInt_Type = {
1274         PyVarObject_HEAD_INIT(&PyType_Type, 0)
1275         "int",
1276         sizeof(PyIntObject),
1277         0,
1278         (destructor)int_dealloc,                /* tp_dealloc */
1279         (printfunc)int_print,                   /* tp_print */
1280         0,                                      /* tp_getattr */
1281         0,                                      /* tp_setattr */
1282         (cmpfunc)int_compare,                   /* tp_compare */
1283         (reprfunc)int_repr,                     /* tp_repr */
1284         &int_as_number,                         /* tp_as_number */
1285         0,                                      /* tp_as_sequence */
1286         0,                                      /* tp_as_mapping */
1287         (hashfunc)int_hash,                     /* tp_hash */
1288         0,                                      /* tp_call */
1289         (reprfunc)int_repr,                     /* tp_str */
1290         PyObject_GenericGetAttr,                /* tp_getattro */
1291         0,                                      /* tp_setattro */
1292         0,                                      /* tp_as_buffer */
1293         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
1294                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS,  /* tp_flags */
1295         int_doc,                                /* tp_doc */
1296         0,                                      /* tp_traverse */
1297         0,                                      /* tp_clear */
1298         0,                                      /* tp_richcompare */
1299         0,                                      /* tp_weaklistoffset */
1300         0,                                      /* tp_iter */
1301         0,                                      /* tp_iternext */
1302         int_methods,                            /* tp_methods */
1303         0,                                      /* tp_members */
1304         int_getset,                             /* tp_getset */
1305         0,                                      /* tp_base */
1306         0,                                      /* tp_dict */
1307         0,                                      /* tp_descr_get */
1308         0,                                      /* tp_descr_set */
1309         0,                                      /* tp_dictoffset */
1310         0,                                      /* tp_init */
1311         0,                                      /* tp_alloc */
1312         int_new,                                /* tp_new */
1313         (freefunc)int_free,                     /* tp_free */
1314 };
1315
1316 int
1317 _PyInt_Init(void)
1318 {
1319         PyIntObject *v;
1320         int ival;
1321 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1322         for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
1323               if (!free_list && (free_list = fill_free_list()) == NULL)
1324                         return 0;
1325                 /* PyObject_New is inlined */
1326                 v = free_list;
1327                 free_list = (PyIntObject *)Py_TYPE(v);
1328                 PyObject_INIT(v, &PyInt_Type);
1329                 v->ob_ival = ival;
1330                 small_ints[ival + NSMALLNEGINTS] = v;
1331         }
1332 #endif
1333         return 1;
1334 }
1335
1336 int
1337 PyInt_ClearFreeList(void)
1338 {
1339         PyIntObject *p;
1340         PyIntBlock *list, *next;
1341         int i;
1342         int u;                  /* remaining unfreed ints per block */
1343         int freelist_size = 0;
1344
1345         list = block_list;
1346         block_list = NULL;
1347         free_list = NULL;
1348         while (list != NULL) {
1349                 u = 0;
1350                 for (i = 0, p = &list->objects[0];
1351                      i < N_INTOBJECTS;
1352                      i++, p++) {
1353                         if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1354                                 u++;
1355                 }
1356                 next = list->next;
1357                 if (u) {
1358                         list->next = block_list;
1359                         block_list = list;
1360                         for (i = 0, p = &list->objects[0];
1361                              i < N_INTOBJECTS;
1362                              i++, p++) {
1363                                 if (!PyInt_CheckExact(p) ||
1364                                     p->ob_refcnt == 0) {
1365                                         Py_TYPE(p) = (struct _typeobject *)
1366                                                 free_list;
1367                                         free_list = p;
1368                                 }
1369 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1370                                 else if (-NSMALLNEGINTS <= p->ob_ival &&
1371                                          p->ob_ival < NSMALLPOSINTS &&
1372                                          small_ints[p->ob_ival +
1373                                                     NSMALLNEGINTS] == NULL) {
1374                                         Py_INCREF(p);
1375                                         small_ints[p->ob_ival +
1376                                                    NSMALLNEGINTS] = p;
1377                                 }
1378 #endif
1379                         }
1380                 }
1381                 else {
1382                         PyMem_FREE(list);
1383                 }
1384                 freelist_size += u;
1385                 list = next;
1386         }
1387
1388         return freelist_size;
1389 }
1390
1391 void
1392 PyInt_Fini(void)
1393 {
1394         PyIntObject *p;
1395         PyIntBlock *list;
1396         int i;
1397         int u;                  /* total unfreed ints per block */
1398
1399 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
1400         PyIntObject **q;
1401
1402         i = NSMALLNEGINTS + NSMALLPOSINTS;
1403         q = small_ints;
1404         while (--i >= 0) {
1405                 Py_XDECREF(*q);
1406                 *q++ = NULL;
1407         }
1408 #endif
1409         u = PyInt_ClearFreeList();
1410         if (!Py_VerboseFlag)
1411                 return;
1412         fprintf(stderr, "# cleanup ints");
1413         if (!u) {
1414                 fprintf(stderr, "\n");
1415         }
1416         else {
1417                 fprintf(stderr,
1418                         ": %d unfreed int%s\n",
1419                         u, u == 1 ? "" : "s");
1420         }
1421         if (Py_VerboseFlag > 1) {
1422                 list = block_list;
1423                 while (list != NULL) {
1424                         for (i = 0, p = &list->objects[0];
1425                              i < N_INTOBJECTS;
1426                              i++, p++) {
1427                                 if (PyInt_CheckExact(p) && p->ob_refcnt != 0)
1428                                         /* XXX(twouters) cast refcount to
1429                                            long until %zd is universally
1430                                            available
1431                                          */
1432                                         fprintf(stderr,
1433                                 "#   <int at %p, refcnt=%ld, val=%ld>\n",
1434                                                 p, (long)p->ob_refcnt,
1435                                                 p->ob_ival);
1436                         }
1437                         list = list->next;
1438                 }
1439         }
1440 }