source: trunk/essentials/dev-lang/python/Objects/intobject.c@ 3298

Last change on this file since 3298 was 3225, checked in by bird, 19 years ago

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