source: python/trunk/Objects/rangeobject.c@ 389

Last change on this file since 389 was 2, checked in by Yuri Dario, 15 years ago

Initial import for vendor code.
  • Property svn:eol-style set to native
File size: 8.9 KB
Line 
1/* Range object implementation */
2
3#include "Python.h"
4
5typedef 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 */
15static unsigned long
16get_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
40static PyObject *
41range_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
82PyDoc_STRVAR(range_doc,
83"xrange([start,] stop[, step]) -> xrange object\n\
84\n\
85Like range(), but instead of returning a list, returns an object that\n\
86generates the numbers in the range on demand. For looping, this is \n\
87slightly faster than range() and more memory efficient.");
88
89static PyObject *
90range_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
102static Py_ssize_t
103range_length(rangeobject *r)
104{
105 return (Py_ssize_t)(r->len);
106}
107
108static PyObject *
109range_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 */
131static PyObject *
132range_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
140static 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
148static PyObject * range_iter(PyObject *seq);
149static PyObject * range_reverse(PyObject *seq);
150
151PyDoc_STRVAR(reverse_doc,
152"Returns a reverse iterator.");
153
154static 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
160PyTypeObject 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
204typedef struct {
205 PyObject_HEAD
206 long index;
207 long start;
208 long step;
209 long len;
210} rangeiterobject;
211
212static PyObject *
213rangeiter_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
220static PyObject *
221rangeiter_len(rangeiterobject *r)
222{
223 return PyInt_FromLong(r->len - r->index);
224}
225
226PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
227
228static PyMethodDef rangeiter_methods[] = {
229 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
230 {NULL, NULL} /* sentinel */
231};
232
233static 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
267static PyObject *
268range_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
286static PyObject *
287range_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}
Note: See TracBrowser for help on using the repository browser.