1 /* Range object implementation */
12 /* Return number of items in range (lo, hi, step). step != 0
13 * required. The result always fits in an unsigned long.
16 get_len_of_range(long lo
, long hi
, long step
)
18 /* -------------------------------------------------------------
19 If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
20 Else for step > 0, if n values are in the range, the last one is
21 lo + (n-1)*step, which must be <= hi-1. Rearranging,
22 n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
23 the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so
24 the RHS is non-negative and so truncation is the same as the
25 floor. Letting M be the largest positive long, the worst case
26 for the RHS numerator is hi=M, lo=-M-1, and then
27 hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough
28 precision to compute the RHS exactly. The analysis for step < 0
30 ---------------------------------------------------------------*/
32 if (step
> 0 && lo
< hi
)
33 return 1UL + (hi
- 1UL - lo
) / step
;
34 else if (step
< 0 && lo
> hi
)
35 return 1UL + (lo
- 1UL - hi
) / (0UL - step
);
41 range_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kw
)
44 long ilow
= 0, ihigh
= 0, istep
= 1;
47 if (!_PyArg_NoKeywords("xrange()", kw
))
50 if (PyTuple_Size(args
) <= 1) {
51 if (!PyArg_ParseTuple(args
,
52 "l;xrange() requires 1-3 int arguments",
57 if (!PyArg_ParseTuple(args
,
58 "ll|l;xrange() requires 1-3 int arguments",
59 &ilow
, &ihigh
, &istep
))
63 PyErr_SetString(PyExc_ValueError
, "xrange() arg 3 must not be zero");
66 n
= get_len_of_range(ilow
, ihigh
, istep
);
67 if (n
> (unsigned long)LONG_MAX
|| (long)n
> PY_SSIZE_T_MAX
) {
68 PyErr_SetString(PyExc_OverflowError
,
69 "xrange() result has too many items");
73 obj
= PyObject_New(rangeobject
, &PyRange_Type
);
79 return (PyObject
*) obj
;
82 PyDoc_STRVAR(range_doc
,
83 "xrange([start,] stop[, step]) -> xrange object\n\
85 Like range(), but instead of returning a list, returns an object that\n\
86 generates the numbers in the range on demand. For looping, this is \n\
87 slightly faster than range() and more memory efficient.");
90 range_item(rangeobject
*r
, Py_ssize_t i
)
92 if (i
< 0 || i
>= r
->len
) {
93 PyErr_SetString(PyExc_IndexError
,
94 "xrange object index out of range");
97 /* do calculation entirely using unsigned longs, to avoid
98 undefined behaviour due to signed overflow. */
99 return PyInt_FromLong((long)(r
->start
+ (unsigned long)i
* r
->step
));
103 range_length(rangeobject
*r
)
105 return (Py_ssize_t
)(r
->len
);
109 range_repr(rangeobject
*r
)
113 if (r
->start
== 0 && r
->step
== 1)
114 rtn
= PyString_FromFormat("xrange(%ld)",
115 r
->start
+ r
->len
* r
->step
);
117 else if (r
->step
== 1)
118 rtn
= PyString_FromFormat("xrange(%ld, %ld)",
120 r
->start
+ r
->len
* r
->step
);
123 rtn
= PyString_FromFormat("xrange(%ld, %ld, %ld)",
125 r
->start
+ r
->len
* r
->step
,
130 /* Pickling support */
132 range_reduce(rangeobject
*r
, PyObject
*args
)
134 return Py_BuildValue("(O(iii))", Py_TYPE(r
),
136 r
->start
+ r
->len
* r
->step
,
140 static PySequenceMethods range_as_sequence
= {
141 (lenfunc
)range_length
, /* sq_length */
144 (ssizeargfunc
)range_item
, /* sq_item */
148 static PyObject
* range_iter(PyObject
*seq
);
149 static PyObject
* range_reverse(PyObject
*seq
);
151 PyDoc_STRVAR(reverse_doc
,
152 "Returns a reverse iterator.");
154 static PyMethodDef range_methods
[] = {
155 {"__reversed__", (PyCFunction
)range_reverse
, METH_NOARGS
, reverse_doc
},
156 {"__reduce__", (PyCFunction
)range_reduce
, METH_VARARGS
},
157 {NULL
, NULL
} /* sentinel */
160 PyTypeObject PyRange_Type
= {
161 PyObject_HEAD_INIT(&PyType_Type
)
162 0, /* Number of items for varobject */
163 "xrange", /* Name of this type */
164 sizeof(rangeobject
), /* Basic object size */
165 0, /* Item size for varobject */
166 (destructor
)PyObject_Del
, /* tp_dealloc */
171 (reprfunc
)range_repr
, /* tp_repr */
172 0, /* tp_as_number */
173 &range_as_sequence
, /* tp_as_sequence */
174 0, /* tp_as_mapping */
178 PyObject_GenericGetAttr
, /* tp_getattro */
180 0, /* tp_as_buffer */
181 Py_TPFLAGS_DEFAULT
, /* tp_flags */
182 range_doc
, /* tp_doc */
185 0, /* tp_richcompare */
186 0, /* tp_weaklistoffset */
187 range_iter
, /* tp_iter */
189 range_methods
, /* tp_methods */
194 0, /* tp_descr_get */
195 0, /* tp_descr_set */
196 0, /* tp_dictoffset */
199 range_new
, /* tp_new */
202 /*********************** Xrange Iterator **************************/
213 rangeiter_next(rangeiterobject
*r
)
215 if (r
->index
< r
->len
)
216 return PyInt_FromLong(r
->start
+ (r
->index
++) * r
->step
);
221 rangeiter_len(rangeiterobject
*r
)
223 return PyInt_FromLong(r
->len
- r
->index
);
226 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
228 static PyMethodDef rangeiter_methods
[] = {
229 {"__length_hint__", (PyCFunction
)rangeiter_len
, METH_NOARGS
, length_hint_doc
},
230 {NULL
, NULL
} /* sentinel */
233 static PyTypeObject Pyrangeiter_Type
= {
234 PyObject_HEAD_INIT(&PyType_Type
)
236 "rangeiterator", /* tp_name */
237 sizeof(rangeiterobject
), /* tp_basicsize */
240 (destructor
)PyObject_Del
, /* tp_dealloc */
246 0, /* tp_as_number */
247 0, /* tp_as_sequence */
248 0, /* tp_as_mapping */
252 PyObject_GenericGetAttr
, /* tp_getattro */
254 0, /* tp_as_buffer */
255 Py_TPFLAGS_DEFAULT
, /* tp_flags */
259 0, /* tp_richcompare */
260 0, /* tp_weaklistoffset */
261 PyObject_SelfIter
, /* tp_iter */
262 (iternextfunc
)rangeiter_next
, /* tp_iternext */
263 rangeiter_methods
, /* tp_methods */
268 range_iter(PyObject
*seq
)
272 if (!PyRange_Check(seq
)) {
273 PyErr_BadInternalCall();
276 it
= PyObject_New(rangeiterobject
, &Pyrangeiter_Type
);
280 it
->start
= ((rangeobject
*)seq
)->start
;
281 it
->step
= ((rangeobject
*)seq
)->step
;
282 it
->len
= ((rangeobject
*)seq
)->len
;
283 return (PyObject
*)it
;
287 range_reverse(PyObject
*seq
)
290 long start
, step
, len
;
292 if (!PyRange_Check(seq
)) {
293 PyErr_BadInternalCall();
296 it
= PyObject_New(rangeiterobject
, &Pyrangeiter_Type
);
300 start
= ((rangeobject
*)seq
)->start
;
301 step
= ((rangeobject
*)seq
)->step
;
302 len
= ((rangeobject
*)seq
)->len
;
306 /* the casts below guard against signed overflow by turning it
307 into unsigned overflow instead. The correctness of this
308 code still depends on conversion from unsigned long to long
309 wrapping modulo ULONG_MAX+1, which isn't guaranteed (see
310 C99 6.3.1.3p3) but seems to hold in practice for all
311 platforms we're likely to meet.
313 If step == LONG_MIN then we still end up with LONG_MIN
314 after negation; but this works out, since we've still got
315 the correct value modulo ULONG_MAX+1, and the range_item
316 calculation is also done modulo ULONG_MAX+1.
318 it
->start
= (long)(start
+ (unsigned long)(len
-1) * step
);
319 it
->step
= (long)(0UL-step
);
321 return (PyObject
*)it
;