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