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
get_len_of_range(long lo,long hi,long step)16 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 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);
36 else
37 return 0UL;
38 }
39
40 static PyObject *
range_new(PyTypeObject * type,PyObject * args,PyObject * kw)41 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
42 {
43 rangeobject *obj;
44 long ilow = 0, ihigh = 0, istep = 1;
45 unsigned long n;
46
47 if (!_PyArg_NoKeywords("xrange()", kw))
48 return NULL;
49
50 if (PyTuple_Size(args) <= 1) {
51 if (!PyArg_ParseTuple(args,
52 "l;xrange() requires 1-3 int arguments",
53 &ihigh))
54 return NULL;
55 }
56 else {
57 if (!PyArg_ParseTuple(args,
58 "ll|l;xrange() requires 1-3 int arguments",
59 &ilow, &ihigh, &istep))
60 return NULL;
61 }
62 if (istep == 0) {
63 PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");
64 return NULL;
65 }
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");
70 return NULL;
71 }
72
73 obj = PyObject_New(rangeobject, &PyRange_Type);
74 if (obj == NULL)
75 return NULL;
76 obj->start = ilow;
77 obj->len = (long)n;
78 obj->step = istep;
79 return (PyObject *) obj;
80 }
81
82 PyDoc_STRVAR(range_doc,
83 "xrange([start,] stop[, step]) -> xrange object\n\
84 \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.");
88
89 static PyObject *
range_item(rangeobject * r,Py_ssize_t i)90 range_item(rangeobject *r, Py_ssize_t i)
91 {
92 if (i < 0 || i >= r->len) {
93 PyErr_SetString(PyExc_IndexError,
94 "xrange object index out of range");
95 return NULL;
96 }
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));
100 }
101
102 static Py_ssize_t
range_length(rangeobject * r)103 range_length(rangeobject *r)
104 {
105 return (Py_ssize_t)(r->len);
106 }
107
108 static PyObject *
range_repr(rangeobject * r)109 range_repr(rangeobject *r)
110 {
111 PyObject *rtn;
112
113 if (r->start == 0 && r->step == 1)
114 rtn = PyString_FromFormat("xrange(%ld)",
115 r->start + r->len * r->step);
116
117 else if (r->step == 1)
118 rtn = PyString_FromFormat("xrange(%ld, %ld)",
119 r->start,
120 r->start + r->len * r->step);
121
122 else
123 rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",
124 r->start,
125 r->start + r->len * r->step,
126 r->step);
127 return rtn;
128 }
129
130 /* Pickling support */
131 static PyObject *
range_reduce(rangeobject * r,PyObject * args)132 range_reduce(rangeobject *r, PyObject *args)
133 {
134 return Py_BuildValue("(O(iii))", Py_TYPE(r),
135 r->start,
136 r->start + r->len * r->step,
137 r->step);
138 }
139
140 static PySequenceMethods range_as_sequence = {
141 (lenfunc)range_length, /* sq_length */
142 0, /* sq_concat */
143 0, /* sq_repeat */
144 (ssizeargfunc)range_item, /* sq_item */
145 0, /* sq_slice */
146 };
147
148 static PyObject * range_iter(PyObject *seq);
149 static PyObject * range_reverse(PyObject *seq);
150
151 PyDoc_STRVAR(reverse_doc,
152 "Returns a reverse iterator.");
153
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 */
158 };
159
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 */
167 0, /* tp_print */
168 0, /* tp_getattr */
169 0, /* tp_setattr */
170 0, /* tp_compare */
171 (reprfunc)range_repr, /* tp_repr */
172 0, /* tp_as_number */
173 &range_as_sequence, /* tp_as_sequence */
174 0, /* tp_as_mapping */
175 0, /* tp_hash */
176 0, /* tp_call */
177 0, /* tp_str */
178 PyObject_GenericGetAttr, /* tp_getattro */
179 0, /* tp_setattro */
180 0, /* tp_as_buffer */
181 Py_TPFLAGS_DEFAULT, /* tp_flags */
182 range_doc, /* tp_doc */
183 0, /* tp_traverse */
184 0, /* tp_clear */
185 0, /* tp_richcompare */
186 0, /* tp_weaklistoffset */
187 range_iter, /* tp_iter */
188 0, /* tp_iternext */
189 range_methods, /* tp_methods */
190 0, /* tp_members */
191 0, /* tp_getset */
192 0, /* tp_base */
193 0, /* tp_dict */
194 0, /* tp_descr_get */
195 0, /* tp_descr_set */
196 0, /* tp_dictoffset */
197 0, /* tp_init */
198 0, /* tp_alloc */
199 range_new, /* tp_new */
200 };
201
202 /*********************** Xrange Iterator **************************/
203
204 typedef struct {
205 PyObject_HEAD
206 long index;
207 long start;
208 long step;
209 long len;
210 } rangeiterobject;
211
212 static PyObject *
rangeiter_next(rangeiterobject * r)213 rangeiter_next(rangeiterobject *r)
214 {
215 if (r->index < r->len)
216 return PyInt_FromLong(r->start + (r->index++) * r->step);
217 return NULL;
218 }
219
220 static PyObject *
rangeiter_len(rangeiterobject * r)221 rangeiter_len(rangeiterobject *r)
222 {
223 return PyInt_FromLong(r->len - r->index);
224 }
225
226 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
227
228 static PyMethodDef rangeiter_methods[] = {
229 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
230 {NULL, NULL} /* sentinel */
231 };
232
233 static PyTypeObject Pyrangeiter_Type = {
234 PyObject_HEAD_INIT(&PyType_Type)
235 0, /* ob_size */
236 "rangeiterator", /* tp_name */
237 sizeof(rangeiterobject), /* tp_basicsize */
238 0, /* tp_itemsize */
239 /* methods */
240 (destructor)PyObject_Del, /* tp_dealloc */
241 0, /* tp_print */
242 0, /* tp_getattr */
243 0, /* tp_setattr */
244 0, /* tp_compare */
245 0, /* tp_repr */
246 0, /* tp_as_number */
247 0, /* tp_as_sequence */
248 0, /* tp_as_mapping */
249 0, /* tp_hash */
250 0, /* tp_call */
251 0, /* tp_str */
252 PyObject_GenericGetAttr, /* tp_getattro */
253 0, /* tp_setattro */
254 0, /* tp_as_buffer */
255 Py_TPFLAGS_DEFAULT, /* tp_flags */
256 0, /* tp_doc */
257 0, /* tp_traverse */
258 0, /* tp_clear */
259 0, /* tp_richcompare */
260 0, /* tp_weaklistoffset */
261 PyObject_SelfIter, /* tp_iter */
262 (iternextfunc)rangeiter_next, /* tp_iternext */
263 rangeiter_methods, /* tp_methods */
264 0,
265 };
266
267 static PyObject *
range_iter(PyObject * seq)268 range_iter(PyObject *seq)
269 {
270 rangeiterobject *it;
271
272 if (!PyRange_Check(seq)) {
273 PyErr_BadInternalCall();
274 return NULL;
275 }
276 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
277 if (it == NULL)
278 return NULL;
279 it->index = 0;
280 it->start = ((rangeobject *)seq)->start;
281 it->step = ((rangeobject *)seq)->step;
282 it->len = ((rangeobject *)seq)->len;
283 return (PyObject *)it;
284 }
285
286 static PyObject *
range_reverse(PyObject * seq)287 range_reverse(PyObject *seq)
288 {
289 rangeiterobject *it;
290 long start, step, len;
291
292 if (!PyRange_Check(seq)) {
293 PyErr_BadInternalCall();
294 return NULL;
295 }
296 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
297 if (it == NULL)
298 return NULL;
299
300 start = ((rangeobject *)seq)->start;
301 step = ((rangeobject *)seq)->step;
302 len = ((rangeobject *)seq)->len;
303
304 it->index = 0;
305 it->len = 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.
312
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.
317 */
318 it->start = (long)(start + (unsigned long)(len-1) * step);
319 it->step = (long)(0UL-step);
320
321 return (PyObject *)it;
322 }
323