Line data Source code
1 : /* Range object implementation */
2 :
3 : #include "Python.h"
4 :
5 : typedef struct {
6 : PyObject_HEAD
7 : long start;
8 : long step;
9 : long len;
10 : } rangeobject;
11 :
12 : /* Return number of items in range (lo, hi, step). step != 0
13 : * required. The result always fits in an unsigned long.
14 : */
15 : static unsigned long
16 663 : get_len_of_range(long lo, long hi, long step)
17 : {
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
29 : is similar.
30 : ---------------------------------------------------------------*/
31 : assert(step != 0);
32 663 : if (step > 0 && lo < hi)
33 663 : return 1UL + (hi - 1UL - lo) / step;
34 0 : else if (step < 0 && lo > hi)
35 0 : return 1UL + (lo - 1UL - hi) / (0UL - step);
36 : else
37 0 : return 0UL;
38 : }
39 :
40 : /* Return a stop value suitable for reconstructing the xrange from
41 : * a (start, stop, step) triple. Used in range_repr and range_reduce.
42 : * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX].
43 : */
44 : static long
45 0 : get_stop_for_range(rangeobject *r)
46 : {
47 : long last;
48 :
49 0 : if (r->len == 0)
50 0 : return r->start;
51 :
52 : /* The tricky bit is avoiding overflow. We first compute the last entry in
53 : the xrange, start + (len - 1) * step, which is guaranteed to lie within
54 : the range of a long, and then add step to it. See the range_reverse
55 : comments for an explanation of the casts below.
56 : */
57 0 : last = (long)(r->start + (unsigned long)(r->len - 1) * r->step);
58 0 : if (r->step > 0)
59 0 : return last > LONG_MAX - r->step ? LONG_MAX : last + r->step;
60 : else
61 0 : return last < LONG_MIN - r->step ? LONG_MIN : last + r->step;
62 : }
63 :
64 : static PyObject *
65 663 : range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
66 : {
67 : rangeobject *obj;
68 663 : long ilow = 0, ihigh = 0, istep = 1;
69 : unsigned long n;
70 :
71 663 : if (!_PyArg_NoKeywords("xrange()", kw))
72 0 : return NULL;
73 :
74 663 : if (PyTuple_Size(args) <= 1) {
75 663 : if (!PyArg_ParseTuple(args,
76 : "l;xrange() requires 1-3 int arguments",
77 : &ihigh))
78 0 : return NULL;
79 : }
80 : else {
81 0 : if (!PyArg_ParseTuple(args,
82 : "ll|l;xrange() requires 1-3 int arguments",
83 : &ilow, &ihigh, &istep))
84 0 : return NULL;
85 : }
86 663 : if (istep == 0) {
87 0 : PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
88 0 : return NULL;
89 : }
90 663 : n = get_len_of_range(ilow, ihigh, istep);
91 663 : if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) {
92 0 : PyErr_SetString(PyExc_OverflowError,
93 : "xrange() result has too many items");
94 0 : return NULL;
95 : }
96 :
97 663 : obj = PyObject_New(rangeobject, &PyRange_Type);
98 663 : if (obj == NULL)
99 0 : return NULL;
100 663 : obj->start = ilow;
101 663 : obj->len = (long)n;
102 663 : obj->step = istep;
103 663 : return (PyObject *) obj;
104 : }
105 :
106 : PyDoc_STRVAR(range_doc,
107 : "xrange(stop) -> xrange object\n\
108 : xrange(start, stop[, step]) -> xrange object\n\
109 : \n\
110 : Like range(), but instead of returning a list, returns an object that\n\
111 : generates the numbers in the range on demand. For looping, this is \n\
112 : slightly faster than range() and more memory efficient.");
113 :
114 : static PyObject *
115 0 : range_item(rangeobject *r, Py_ssize_t i)
116 : {
117 0 : if (i < 0 || i >= r->len) {
118 0 : PyErr_SetString(PyExc_IndexError,
119 : "xrange object index out of range");
120 0 : return NULL;
121 : }
122 : /* do calculation entirely using unsigned longs, to avoid
123 : undefined behaviour due to signed overflow. */
124 0 : return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step));
125 : }
126 :
127 : static Py_ssize_t
128 3 : range_length(rangeobject *r)
129 : {
130 3 : return (Py_ssize_t)(r->len);
131 : }
132 :
133 : static PyObject *
134 0 : range_repr(rangeobject *r)
135 : {
136 : PyObject *rtn;
137 :
138 0 : if (r->start == 0 && r->step == 1)
139 0 : rtn = PyString_FromFormat("xrange(%ld)",
140 : get_stop_for_range(r));
141 :
142 0 : else if (r->step == 1)
143 0 : rtn = PyString_FromFormat("xrange(%ld, %ld)",
144 : r->start,
145 : get_stop_for_range(r));
146 :
147 : else
148 0 : rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",
149 : r->start,
150 : get_stop_for_range(r),
151 : r->step);
152 0 : return rtn;
153 : }
154 :
155 : /* Pickling support */
156 : static PyObject *
157 0 : range_reduce(rangeobject *r, PyObject *args)
158 : {
159 0 : return Py_BuildValue("(O(lll))", Py_TYPE(r),
160 : r->start,
161 : get_stop_for_range(r),
162 : r->step);
163 : }
164 :
165 : static PySequenceMethods range_as_sequence = {
166 : (lenfunc)range_length, /* sq_length */
167 : 0, /* sq_concat */
168 : 0, /* sq_repeat */
169 : (ssizeargfunc)range_item, /* sq_item */
170 : 0, /* sq_slice */
171 : };
172 :
173 : static PyObject * range_iter(PyObject *seq);
174 : static PyObject * range_reverse(PyObject *seq);
175 :
176 : PyDoc_STRVAR(reverse_doc,
177 : "Returns a reverse iterator.");
178 :
179 : static PyMethodDef range_methods[] = {
180 : {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
181 : {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS},
182 : {NULL, NULL} /* sentinel */
183 : };
184 :
185 : PyTypeObject PyRange_Type = {
186 : PyObject_HEAD_INIT(&PyType_Type)
187 : 0, /* Number of items for varobject */
188 : "xrange", /* Name of this type */
189 : sizeof(rangeobject), /* Basic object size */
190 : 0, /* Item size for varobject */
191 : (destructor)PyObject_Del, /* tp_dealloc */
192 : 0, /* tp_print */
193 : 0, /* tp_getattr */
194 : 0, /* tp_setattr */
195 : 0, /* tp_compare */
196 : (reprfunc)range_repr, /* tp_repr */
197 : 0, /* tp_as_number */
198 : &range_as_sequence, /* tp_as_sequence */
199 : 0, /* tp_as_mapping */
200 : 0, /* tp_hash */
201 : 0, /* tp_call */
202 : 0, /* tp_str */
203 : PyObject_GenericGetAttr, /* tp_getattro */
204 : 0, /* tp_setattro */
205 : 0, /* tp_as_buffer */
206 : Py_TPFLAGS_DEFAULT, /* tp_flags */
207 : range_doc, /* tp_doc */
208 : 0, /* tp_traverse */
209 : 0, /* tp_clear */
210 : 0, /* tp_richcompare */
211 : 0, /* tp_weaklistoffset */
212 : range_iter, /* tp_iter */
213 : 0, /* tp_iternext */
214 : range_methods, /* tp_methods */
215 : 0, /* tp_members */
216 : 0, /* tp_getset */
217 : 0, /* tp_base */
218 : 0, /* tp_dict */
219 : 0, /* tp_descr_get */
220 : 0, /* tp_descr_set */
221 : 0, /* tp_dictoffset */
222 : 0, /* tp_init */
223 : 0, /* tp_alloc */
224 : range_new, /* tp_new */
225 : };
226 :
227 : /*********************** Xrange Iterator **************************/
228 :
229 : typedef struct {
230 : PyObject_HEAD
231 : long index;
232 : long start;
233 : long step;
234 : long len;
235 : } rangeiterobject;
236 :
237 : static PyObject *
238 2724 : rangeiter_next(rangeiterobject *r)
239 : {
240 2724 : if (r->index < r->len)
241 2061 : return PyInt_FromLong(r->start + (r->index++) * r->step);
242 663 : return NULL;
243 : }
244 :
245 : static PyObject *
246 0 : rangeiter_len(rangeiterobject *r)
247 : {
248 0 : return PyInt_FromLong(r->len - r->index);
249 : }
250 :
251 : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
252 :
253 : static PyMethodDef rangeiter_methods[] = {
254 : {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
255 : {NULL, NULL} /* sentinel */
256 : };
257 :
258 : static PyTypeObject Pyrangeiter_Type = {
259 : PyObject_HEAD_INIT(&PyType_Type)
260 : 0, /* ob_size */
261 : "rangeiterator", /* tp_name */
262 : sizeof(rangeiterobject), /* tp_basicsize */
263 : 0, /* tp_itemsize */
264 : /* methods */
265 : (destructor)PyObject_Del, /* tp_dealloc */
266 : 0, /* tp_print */
267 : 0, /* tp_getattr */
268 : 0, /* tp_setattr */
269 : 0, /* tp_compare */
270 : 0, /* tp_repr */
271 : 0, /* tp_as_number */
272 : 0, /* tp_as_sequence */
273 : 0, /* tp_as_mapping */
274 : 0, /* tp_hash */
275 : 0, /* tp_call */
276 : 0, /* tp_str */
277 : PyObject_GenericGetAttr, /* tp_getattro */
278 : 0, /* tp_setattro */
279 : 0, /* tp_as_buffer */
280 : Py_TPFLAGS_DEFAULT, /* tp_flags */
281 : 0, /* tp_doc */
282 : 0, /* tp_traverse */
283 : 0, /* tp_clear */
284 : 0, /* tp_richcompare */
285 : 0, /* tp_weaklistoffset */
286 : PyObject_SelfIter, /* tp_iter */
287 : (iternextfunc)rangeiter_next, /* tp_iternext */
288 : rangeiter_methods, /* tp_methods */
289 : 0,
290 : };
291 :
292 : static PyObject *
293 663 : range_iter(PyObject *seq)
294 : {
295 : rangeiterobject *it;
296 :
297 663 : if (!PyRange_Check(seq)) {
298 0 : PyErr_BadInternalCall();
299 0 : return NULL;
300 : }
301 663 : it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
302 663 : if (it == NULL)
303 0 : return NULL;
304 663 : it->index = 0;
305 663 : it->start = ((rangeobject *)seq)->start;
306 663 : it->step = ((rangeobject *)seq)->step;
307 663 : it->len = ((rangeobject *)seq)->len;
308 663 : return (PyObject *)it;
309 : }
310 :
311 : static PyObject *
312 0 : range_reverse(PyObject *seq)
313 : {
314 : rangeiterobject *it;
315 : long start, step, len;
316 :
317 0 : if (!PyRange_Check(seq)) {
318 0 : PyErr_BadInternalCall();
319 0 : return NULL;
320 : }
321 0 : it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
322 0 : if (it == NULL)
323 0 : return NULL;
324 :
325 0 : start = ((rangeobject *)seq)->start;
326 0 : step = ((rangeobject *)seq)->step;
327 0 : len = ((rangeobject *)seq)->len;
328 :
329 0 : it->index = 0;
330 0 : it->len = len;
331 : /* the casts below guard against signed overflow by turning it
332 : into unsigned overflow instead. The correctness of this
333 : code still depends on conversion from unsigned long to long
334 : wrapping modulo ULONG_MAX+1, which isn't guaranteed (see
335 : C99 6.3.1.3p3) but seems to hold in practice for all
336 : platforms we're likely to meet.
337 :
338 : If step == LONG_MIN then we still end up with LONG_MIN
339 : after negation; but this works out, since we've still got
340 : the correct value modulo ULONG_MAX+1, and the range_item
341 : calculation is also done modulo ULONG_MAX+1.
342 : */
343 0 : it->start = (long)(start + (unsigned long)(len-1) * step);
344 0 : it->step = (long)(0UL-step);
345 :
346 0 : return (PyObject *)it;
347 : }
|
