← Back to branch summary

~malept/ubuntu/lucid/python2.6/dev-dependency-fix

« back to all changes in this revision

Viewing changes to Objects/rangeobject.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-02-13 12:51:00 UTC
  • Revision ID: james.westby@ubuntu.com-20090213125100-uufgcb9yeqzujpqw
Tags: upstream-2.6.1
Import upstream version 2.6.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
Objects/rangeobject.c
 
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
}