|
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/xrange (lo, hi, step). step > 0 |
|
13 * required. Return a value < 0 if & only if the true value is too |
|
14 * large to fit in a signed long. |
|
15 */ |
|
16 static long |
|
17 get_len_of_range(long lo, long hi, long step) |
|
18 { |
|
19 /* ------------------------------------------------------------- |
|
20 If lo >= hi, the range is empty. |
|
21 Else if n values are in the range, the last one is |
|
22 lo + (n-1)*step, which must be <= hi-1. Rearranging, |
|
23 n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives |
|
24 the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so |
|
25 the RHS is non-negative and so truncation is the same as the |
|
26 floor. Letting M be the largest positive long, the worst case |
|
27 for the RHS numerator is hi=M, lo=-M-1, and then |
|
28 hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough |
|
29 precision to compute the RHS exactly. |
|
30 ---------------------------------------------------------------*/ |
|
31 long n = 0; |
|
32 if (lo < hi) { |
|
33 unsigned long uhi = (unsigned long)hi; |
|
34 unsigned long ulo = (unsigned long)lo; |
|
35 unsigned long diff = uhi - ulo - 1; |
|
36 n = (long)(diff / (unsigned long)step + 1); |
|
37 } |
|
38 return n; |
|
39 } |
|
40 |
|
41 static PyObject * |
|
42 range_new(PyTypeObject *type, PyObject *args, PyObject *kw) |
|
43 { |
|
44 rangeobject *obj; |
|
45 long ilow = 0, ihigh = 0, istep = 1; |
|
46 long n; |
|
47 |
|
48 if (!_PyArg_NoKeywords("xrange()", kw)) |
|
49 return NULL; |
|
50 |
|
51 if (PyTuple_Size(args) <= 1) { |
|
52 if (!PyArg_ParseTuple(args, |
|
53 "l;xrange() requires 1-3 int arguments", |
|
54 &ihigh)) |
|
55 return NULL; |
|
56 } |
|
57 else { |
|
58 if (!PyArg_ParseTuple(args, |
|
59 "ll|l;xrange() requires 1-3 int arguments", |
|
60 &ilow, &ihigh, &istep)) |
|
61 return NULL; |
|
62 } |
|
63 if (istep == 0) { |
|
64 PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero"); |
|
65 return NULL; |
|
66 } |
|
67 if (istep > 0) |
|
68 n = get_len_of_range(ilow, ihigh, istep); |
|
69 else |
|
70 n = get_len_of_range(ihigh, ilow, -istep); |
|
71 if (n < 0) { |
|
72 PyErr_SetString(PyExc_OverflowError, |
|
73 "xrange() result has too many items"); |
|
74 return NULL; |
|
75 } |
|
76 |
|
77 obj = PyObject_New(rangeobject, &PyRange_Type); |
|
78 if (obj == NULL) |
|
79 return NULL; |
|
80 obj->start = ilow; |
|
81 obj->len = n; |
|
82 obj->step = istep; |
|
83 return (PyObject *) obj; |
|
84 } |
|
85 |
|
86 PyDoc_STRVAR(range_doc, |
|
87 "xrange([start,] stop[, step]) -> xrange object\n\ |
|
88 \n\ |
|
89 Like range(), but instead of returning a list, returns an object that\n\ |
|
90 generates the numbers in the range on demand. For looping, this is \n\ |
|
91 slightly faster than range() and more memory efficient."); |
|
92 |
|
93 static PyObject * |
|
94 range_item(rangeobject *r, Py_ssize_t i) |
|
95 { |
|
96 if (i < 0 || i >= r->len) { |
|
97 PyErr_SetString(PyExc_IndexError, |
|
98 "xrange object index out of range"); |
|
99 return NULL; |
|
100 } |
|
101 return PyInt_FromSsize_t(r->start + i * r->step); |
|
102 } |
|
103 |
|
104 static Py_ssize_t |
|
105 range_length(rangeobject *r) |
|
106 { |
|
107 return (Py_ssize_t)(r->len); |
|
108 } |
|
109 |
|
110 static PyObject * |
|
111 range_repr(rangeobject *r) |
|
112 { |
|
113 PyObject *rtn; |
|
114 |
|
115 if (r->start == 0 && r->step == 1) |
|
116 rtn = PyString_FromFormat("xrange(%ld)", |
|
117 r->start + r->len * r->step); |
|
118 |
|
119 else if (r->step == 1) |
|
120 rtn = PyString_FromFormat("xrange(%ld, %ld)", |
|
121 r->start, |
|
122 r->start + r->len * r->step); |
|
123 |
|
124 else |
|
125 rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)", |
|
126 r->start, |
|
127 r->start + r->len * r->step, |
|
128 r->step); |
|
129 return rtn; |
|
130 } |
|
131 |
|
132 /* Pickling support */ |
|
133 static PyObject * |
|
134 range_reduce(rangeobject *r, PyObject *args) |
|
135 { |
|
136 return Py_BuildValue("(O(iii))", Py_TYPE(r), |
|
137 r->start, |
|
138 r->start + r->len * r->step, |
|
139 r->step); |
|
140 } |
|
141 |
|
142 static PySequenceMethods range_as_sequence = { |
|
143 (lenfunc)range_length, /* sq_length */ |
|
144 0, /* sq_concat */ |
|
145 0, /* sq_repeat */ |
|
146 (ssizeargfunc)range_item, /* sq_item */ |
|
147 0, /* sq_slice */ |
|
148 }; |
|
149 |
|
150 static PyObject * range_iter(PyObject *seq); |
|
151 static PyObject * range_reverse(PyObject *seq); |
|
152 |
|
153 PyDoc_STRVAR(reverse_doc, |
|
154 "Returns a reverse iterator."); |
|
155 |
|
156 static PyMethodDef range_methods[] = { |
|
157 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc}, |
|
158 {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS}, |
|
159 {NULL, NULL} /* sentinel */ |
|
160 }; |
|
161 |
|
162 PyTypeObject PyRange_Type = { |
|
163 PyObject_HEAD_INIT(&PyType_Type) |
|
164 0, /* Number of items for varobject */ |
|
165 "xrange", /* Name of this type */ |
|
166 sizeof(rangeobject), /* Basic object size */ |
|
167 0, /* Item size for varobject */ |
|
168 (destructor)PyObject_Del, /* tp_dealloc */ |
|
169 0, /* tp_print */ |
|
170 0, /* tp_getattr */ |
|
171 0, /* tp_setattr */ |
|
172 0, /* tp_compare */ |
|
173 (reprfunc)range_repr, /* tp_repr */ |
|
174 0, /* tp_as_number */ |
|
175 &range_as_sequence, /* tp_as_sequence */ |
|
176 0, /* tp_as_mapping */ |
|
177 0, /* tp_hash */ |
|
178 0, /* tp_call */ |
|
179 0, /* tp_str */ |
|
180 PyObject_GenericGetAttr, /* tp_getattro */ |
|
181 0, /* tp_setattro */ |
|
182 0, /* tp_as_buffer */ |
|
183 Py_TPFLAGS_DEFAULT, /* tp_flags */ |
|
184 range_doc, /* tp_doc */ |
|
185 0, /* tp_traverse */ |
|
186 0, /* tp_clear */ |
|
187 0, /* tp_richcompare */ |
|
188 0, /* tp_weaklistoffset */ |
|
189 range_iter, /* tp_iter */ |
|
190 0, /* tp_iternext */ |
|
191 range_methods, /* tp_methods */ |
|
192 0, /* tp_members */ |
|
193 0, /* tp_getset */ |
|
194 0, /* tp_base */ |
|
195 0, /* tp_dict */ |
|
196 0, /* tp_descr_get */ |
|
197 0, /* tp_descr_set */ |
|
198 0, /* tp_dictoffset */ |
|
199 0, /* tp_init */ |
|
200 0, /* tp_alloc */ |
|
201 range_new, /* tp_new */ |
|
202 }; |
|
203 |
|
204 /*********************** Xrange Iterator **************************/ |
|
205 |
|
206 typedef struct { |
|
207 PyObject_HEAD |
|
208 long index; |
|
209 long start; |
|
210 long step; |
|
211 long len; |
|
212 } rangeiterobject; |
|
213 |
|
214 static PyObject * |
|
215 rangeiter_next(rangeiterobject *r) |
|
216 { |
|
217 if (r->index < r->len) |
|
218 return PyInt_FromLong(r->start + (r->index++) * r->step); |
|
219 return NULL; |
|
220 } |
|
221 |
|
222 static PyObject * |
|
223 rangeiter_len(rangeiterobject *r) |
|
224 { |
|
225 return PyInt_FromLong(r->len - r->index); |
|
226 } |
|
227 |
|
228 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); |
|
229 |
|
230 static PyMethodDef rangeiter_methods[] = { |
|
231 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc}, |
|
232 {NULL, NULL} /* sentinel */ |
|
233 }; |
|
234 |
|
235 static PyTypeObject Pyrangeiter_Type = { |
|
236 PyObject_HEAD_INIT(&PyType_Type) |
|
237 0, /* ob_size */ |
|
238 "rangeiterator", /* tp_name */ |
|
239 sizeof(rangeiterobject), /* tp_basicsize */ |
|
240 0, /* tp_itemsize */ |
|
241 /* methods */ |
|
242 (destructor)PyObject_Del, /* tp_dealloc */ |
|
243 0, /* tp_print */ |
|
244 0, /* tp_getattr */ |
|
245 0, /* tp_setattr */ |
|
246 0, /* tp_compare */ |
|
247 0, /* tp_repr */ |
|
248 0, /* tp_as_number */ |
|
249 0, /* tp_as_sequence */ |
|
250 0, /* tp_as_mapping */ |
|
251 0, /* tp_hash */ |
|
252 0, /* tp_call */ |
|
253 0, /* tp_str */ |
|
254 PyObject_GenericGetAttr, /* tp_getattro */ |
|
255 0, /* tp_setattro */ |
|
256 0, /* tp_as_buffer */ |
|
257 Py_TPFLAGS_DEFAULT, /* tp_flags */ |
|
258 0, /* tp_doc */ |
|
259 0, /* tp_traverse */ |
|
260 0, /* tp_clear */ |
|
261 0, /* tp_richcompare */ |
|
262 0, /* tp_weaklistoffset */ |
|
263 PyObject_SelfIter, /* tp_iter */ |
|
264 (iternextfunc)rangeiter_next, /* tp_iternext */ |
|
265 rangeiter_methods, /* tp_methods */ |
|
266 0, |
|
267 }; |
|
268 |
|
269 static PyObject * |
|
270 range_iter(PyObject *seq) |
|
271 { |
|
272 rangeiterobject *it; |
|
273 |
|
274 if (!PyRange_Check(seq)) { |
|
275 PyErr_BadInternalCall(); |
|
276 return NULL; |
|
277 } |
|
278 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); |
|
279 if (it == NULL) |
|
280 return NULL; |
|
281 it->index = 0; |
|
282 it->start = ((rangeobject *)seq)->start; |
|
283 it->step = ((rangeobject *)seq)->step; |
|
284 it->len = ((rangeobject *)seq)->len; |
|
285 return (PyObject *)it; |
|
286 } |
|
287 |
|
288 static PyObject * |
|
289 range_reverse(PyObject *seq) |
|
290 { |
|
291 rangeiterobject *it; |
|
292 long start, step, len; |
|
293 |
|
294 if (!PyRange_Check(seq)) { |
|
295 PyErr_BadInternalCall(); |
|
296 return NULL; |
|
297 } |
|
298 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); |
|
299 if (it == NULL) |
|
300 return NULL; |
|
301 |
|
302 start = ((rangeobject *)seq)->start; |
|
303 step = ((rangeobject *)seq)->step; |
|
304 len = ((rangeobject *)seq)->len; |
|
305 |
|
306 it->index = 0; |
|
307 it->start = start + (len-1) * step; |
|
308 it->step = -step; |
|
309 it->len = len; |
|
310 |
|
311 return (PyObject *)it; |
|
312 } |