source: vendor/python/2.5/Objects/rangeobject.c@ 3298

Last change on this file since 3298 was 3225, checked in by bird, 19 years ago

Python 2.5
File size: 7.9 KB
RevLine 
[3225]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/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 */
16static long
17get_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
41static PyObject *
42range_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
86PyDoc_STRVAR(range_doc,
87"xrange([start,] stop[, step]) -> xrange object\n\
88\n\
89Like range(), but instead of returning a list, returns an object that\n\
90generates the numbers in the range on demand. For looping, this is \n\
91slightly faster than range() and more memory efficient.");
92
93static PyObject *
94range_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->len) * r->step);
102}
103
104static Py_ssize_t
105range_length(rangeobject *r)
106{
107 return (Py_ssize_t)(r->len);
108}
109
110static PyObject *
111range_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
132static PySequenceMethods range_as_sequence = {
133 (lenfunc)range_length, /* sq_length */
134 0, /* sq_concat */
135 0, /* sq_repeat */
136 (ssizeargfunc)range_item, /* sq_item */
137 0, /* sq_slice */
138};
139
140static PyObject * range_iter(PyObject *seq);
141static PyObject * range_reverse(PyObject *seq);
142
143PyDoc_STRVAR(reverse_doc,
144"Returns a reverse iterator.");
145
146static PyMethodDef range_methods[] = {
147 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
148 {NULL, NULL} /* sentinel */
149};
150
151PyTypeObject PyRange_Type = {
152 PyObject_HEAD_INIT(&PyType_Type)
153 0, /* Number of items for varobject */
154 "xrange", /* Name of this type */
155 sizeof(rangeobject), /* Basic object size */
156 0, /* Item size for varobject */
157 (destructor)PyObject_Del, /* tp_dealloc */
158 0, /* tp_print */
159 0, /* tp_getattr */
160 0, /* tp_setattr */
161 0, /* tp_compare */
162 (reprfunc)range_repr, /* tp_repr */
163 0, /* tp_as_number */
164 &range_as_sequence, /* tp_as_sequence */
165 0, /* tp_as_mapping */
166 0, /* tp_hash */
167 0, /* tp_call */
168 0, /* tp_str */
169 PyObject_GenericGetAttr, /* tp_getattro */
170 0, /* tp_setattro */
171 0, /* tp_as_buffer */
172 Py_TPFLAGS_DEFAULT, /* tp_flags */
173 range_doc, /* tp_doc */
174 0, /* tp_traverse */
175 0, /* tp_clear */
176 0, /* tp_richcompare */
177 0, /* tp_weaklistoffset */
178 range_iter, /* tp_iter */
179 0, /* tp_iternext */
180 range_methods, /* tp_methods */
181 0, /* tp_members */
182 0, /* tp_getset */
183 0, /* tp_base */
184 0, /* tp_dict */
185 0, /* tp_descr_get */
186 0, /* tp_descr_set */
187 0, /* tp_dictoffset */
188 0, /* tp_init */
189 0, /* tp_alloc */
190 range_new, /* tp_new */
191};
192
193/*********************** Xrange Iterator **************************/
194
195typedef struct {
196 PyObject_HEAD
197 long index;
198 long start;
199 long step;
200 long len;
201} rangeiterobject;
202
203static PyObject *
204rangeiter_next(rangeiterobject *r)
205{
206 if (r->index < r->len)
207 return PyInt_FromLong(r->start + (r->index++) * r->step);
208 return NULL;
209}
210
211static PyObject *
212rangeiter_len(rangeiterobject *r)
213{
214 return PyInt_FromLong(r->len - r->index);
215}
216
217PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
218
219static PyMethodDef rangeiter_methods[] = {
220 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
221 {NULL, NULL} /* sentinel */
222};
223
224static PyTypeObject Pyrangeiter_Type = {
225 PyObject_HEAD_INIT(&PyType_Type)
226 0, /* ob_size */
227 "rangeiterator", /* tp_name */
228 sizeof(rangeiterobject), /* tp_basicsize */
229 0, /* tp_itemsize */
230 /* methods */
231 (destructor)PyObject_Del, /* tp_dealloc */
232 0, /* tp_print */
233 0, /* tp_getattr */
234 0, /* tp_setattr */
235 0, /* tp_compare */
236 0, /* tp_repr */
237 0, /* tp_as_number */
238 0, /* tp_as_sequence */
239 0, /* tp_as_mapping */
240 0, /* tp_hash */
241 0, /* tp_call */
242 0, /* tp_str */
243 PyObject_GenericGetAttr, /* tp_getattro */
244 0, /* tp_setattro */
245 0, /* tp_as_buffer */
246 Py_TPFLAGS_DEFAULT, /* tp_flags */
247 0, /* tp_doc */
248 0, /* tp_traverse */
249 0, /* tp_clear */
250 0, /* tp_richcompare */
251 0, /* tp_weaklistoffset */
252 PyObject_SelfIter, /* tp_iter */
253 (iternextfunc)rangeiter_next, /* tp_iternext */
254 rangeiter_methods, /* tp_methods */
255 0,
256};
257
258static PyObject *
259range_iter(PyObject *seq)
260{
261 rangeiterobject *it;
262
263 if (!PyRange_Check(seq)) {
264 PyErr_BadInternalCall();
265 return NULL;
266 }
267 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
268 if (it == NULL)
269 return NULL;
270 it->index = 0;
271 it->start = ((rangeobject *)seq)->start;
272 it->step = ((rangeobject *)seq)->step;
273 it->len = ((rangeobject *)seq)->len;
274 return (PyObject *)it;
275}
276
277static PyObject *
278range_reverse(PyObject *seq)
279{
280 rangeiterobject *it;
281 long start, step, len;
282
283 if (!PyRange_Check(seq)) {
284 PyErr_BadInternalCall();
285 return NULL;
286 }
287 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
288 if (it == NULL)
289 return NULL;
290
291 start = ((rangeobject *)seq)->start;
292 step = ((rangeobject *)seq)->step;
293 len = ((rangeobject *)seq)->len;
294
295 it->index = 0;
296 it->start = start + (len-1) * step;
297 it->step = -step;
298 it->len = len;
299
300 return (PyObject *)it;
301}
Note: See TracBrowser for help on using the repository browser.