Changeset 388 for python/vendor/current/Objects/rangeobject.c
- Timestamp:
- Mar 19, 2014, 11:11:30 AM (11 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
python/vendor/current/Objects/rangeobject.c
r2 r388 4 4 5 5 typedef struct { 6 7 longstart;8 longstep;9 longlen;6 PyObject_HEAD 7 long start; 8 long step; 9 long len; 10 10 } rangeobject; 11 11 … … 31 31 assert(step != 0); 32 32 if (step > 0 && lo < hi) 33 33 return 1UL + (hi - 1UL - lo) / step; 34 34 else if (step < 0 && lo > hi) 35 35 return 1UL + (lo - 1UL - hi) / (0UL - step); 36 36 else 37 return 0UL; 37 return 0UL; 38 } 39 40 /* Return a stop value suitable for reconstructing the xrange from 41 * a (start, stop, step) triple. Used in range_repr and range_reduce. 42 * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX]. 43 */ 44 static long 45 get_stop_for_range(rangeobject *r) 46 { 47 long last; 48 49 if (r->len == 0) 50 return r->start; 51 52 /* The tricky bit is avoiding overflow. We first compute the last entry in 53 the xrange, start + (len - 1) * step, which is guaranteed to lie within 54 the range of a long, and then add step to it. See the range_reverse 55 comments for an explanation of the casts below. 56 */ 57 last = (long)(r->start + (unsigned long)(r->len - 1) * r->step); 58 if (r->step > 0) 59 return last > LONG_MAX - r->step ? LONG_MAX : last + r->step; 60 else 61 return last < LONG_MIN - r->step ? LONG_MIN : last + r->step; 38 62 } 39 63 … … 41 65 range_new(PyTypeObject *type, PyObject *args, PyObject *kw) 42 66 { 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 67 rangeobject *obj; 68 long ilow = 0, ihigh = 0, istep = 1; 69 unsigned long n; 70 71 if (!_PyArg_NoKeywords("xrange()", kw)) 72 return NULL; 73 74 if (PyTuple_Size(args) <= 1) { 75 if (!PyArg_ParseTuple(args, 76 "l;xrange() requires 1-3 int arguments", 77 &ihigh)) 78 return NULL; 79 } 80 else { 81 if (!PyArg_ParseTuple(args, 82 "ll|l;xrange() requires 1-3 int arguments", 83 &ilow, &ihigh, &istep)) 84 return NULL; 85 } 86 if (istep == 0) { 87 PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero"); 88 return NULL; 89 } 90 n = get_len_of_range(ilow, ihigh, istep); 91 if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) { 92 PyErr_SetString(PyExc_OverflowError, 93 "xrange() result has too many items"); 94 return NULL; 95 } 96 97 obj = PyObject_New(rangeobject, &PyRange_Type); 98 if (obj == NULL) 99 return NULL; 100 obj->start = ilow; 101 obj->len = (long)n; 102 obj->step = istep; 103 return (PyObject *) obj; 80 104 } 81 105 82 106 PyDoc_STRVAR(range_doc, 83 "xrange([start,] stop[, step]) -> xrange object\n\ 107 "xrange(stop) -> xrange object\n\ 108 xrange(start, stop[, step]) -> xrange object\n\ 84 109 \n\ 85 110 Like range(), but instead of returning a list, returns an object that\n\ … … 90 115 range_item(rangeobject *r, Py_ssize_t i) 91 116 { 92 93 94 95 96 97 98 99 117 if (i < 0 || i >= r->len) { 118 PyErr_SetString(PyExc_IndexError, 119 "xrange object index out of range"); 120 return NULL; 121 } 122 /* do calculation entirely using unsigned longs, to avoid 123 undefined behaviour due to signed overflow. */ 124 return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step)); 100 125 } 101 126 … … 103 128 range_length(rangeobject *r) 104 129 { 105 130 return (Py_ssize_t)(r->len); 106 131 } 107 132 … … 109 134 range_repr(rangeobject *r) 110 135 { 111 112 113 114 115 r->start + r->len * r->step);116 117 118 119 120 r->start + r->len * r->step);121 122 123 124 125 r->start + r->len * r->step,126 127 136 PyObject *rtn; 137 138 if (r->start == 0 && r->step == 1) 139 rtn = PyString_FromFormat("xrange(%ld)", 140 get_stop_for_range(r)); 141 142 else if (r->step == 1) 143 rtn = PyString_FromFormat("xrange(%ld, %ld)", 144 r->start, 145 get_stop_for_range(r)); 146 147 else 148 rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)", 149 r->start, 150 get_stop_for_range(r), 151 r->step); 152 return rtn; 128 153 } 129 154 … … 132 157 range_reduce(rangeobject *r, PyObject *args) 133 158 { 134 return Py_BuildValue("(O(iii))", Py_TYPE(r),135 136 r->start + r->len * r->step,137 159 return Py_BuildValue("(O(lll))", Py_TYPE(r), 160 r->start, 161 get_stop_for_range(r), 162 r->step); 138 163 } 139 164 140 165 static PySequenceMethods range_as_sequence = { 141 (lenfunc)range_length,/* sq_length */142 0,/* sq_concat */143 0,/* sq_repeat */144 145 0,/* sq_slice */166 (lenfunc)range_length, /* sq_length */ 167 0, /* sq_concat */ 168 0, /* sq_repeat */ 169 (ssizeargfunc)range_item, /* sq_item */ 170 0, /* sq_slice */ 146 171 }; 147 172 … … 153 178 154 179 static PyMethodDef range_methods[] = { 155 {"__reversed__",(PyCFunction)range_reverse, METH_NOARGS, reverse_doc},156 {"__reduce__",(PyCFunction)range_reduce, METH_VARARGS},157 {NULL, NULL}/* sentinel */180 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc}, 181 {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS}, 182 {NULL, NULL} /* sentinel */ 158 183 }; 159 184 160 185 PyTypeObject PyRange_Type = { 161 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 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 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 */186 PyObject_HEAD_INIT(&PyType_Type) 187 0, /* Number of items for varobject */ 188 "xrange", /* Name of this type */ 189 sizeof(rangeobject), /* Basic object size */ 190 0, /* Item size for varobject */ 191 (destructor)PyObject_Del, /* tp_dealloc */ 192 0, /* tp_print */ 193 0, /* tp_getattr */ 194 0, /* tp_setattr */ 195 0, /* tp_compare */ 196 (reprfunc)range_repr, /* tp_repr */ 197 0, /* tp_as_number */ 198 &range_as_sequence, /* tp_as_sequence */ 199 0, /* tp_as_mapping */ 200 0, /* tp_hash */ 201 0, /* tp_call */ 202 0, /* tp_str */ 203 PyObject_GenericGetAttr, /* tp_getattro */ 204 0, /* tp_setattro */ 205 0, /* tp_as_buffer */ 206 Py_TPFLAGS_DEFAULT, /* tp_flags */ 207 range_doc, /* tp_doc */ 208 0, /* tp_traverse */ 209 0, /* tp_clear */ 210 0, /* tp_richcompare */ 211 0, /* tp_weaklistoffset */ 212 range_iter, /* tp_iter */ 213 0, /* tp_iternext */ 214 range_methods, /* tp_methods */ 215 0, /* tp_members */ 216 0, /* tp_getset */ 217 0, /* tp_base */ 218 0, /* tp_dict */ 219 0, /* tp_descr_get */ 220 0, /* tp_descr_set */ 221 0, /* tp_dictoffset */ 222 0, /* tp_init */ 223 0, /* tp_alloc */ 224 range_new, /* tp_new */ 200 225 }; 201 226 … … 203 228 204 229 typedef struct { 205 206 longindex;207 longstart;208 longstep;209 longlen;230 PyObject_HEAD 231 long index; 232 long start; 233 long step; 234 long len; 210 235 } rangeiterobject; 211 236 … … 213 238 rangeiter_next(rangeiterobject *r) 214 239 { 215 216 217 240 if (r->index < r->len) 241 return PyInt_FromLong(r->start + (r->index++) * r->step); 242 return NULL; 218 243 } 219 244 … … 221 246 rangeiter_len(rangeiterobject *r) 222 247 { 223 248 return PyInt_FromLong(r->len - r->index); 224 249 } 225 250 … … 227 252 228 253 static PyMethodDef rangeiter_methods[] = { 229 230 {NULL, NULL}/* sentinel */254 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc}, 255 {NULL, NULL} /* sentinel */ 231 256 }; 232 257 233 258 static PyTypeObject Pyrangeiter_Type = { 234 235 236 237 238 239 240 (destructor)PyObject_Del,/* tp_dealloc */241 242 243 244 245 246 247 0,/* tp_as_sequence */248 249 250 251 252 253 254 255 Py_TPFLAGS_DEFAULT,/* tp_flags */256 257 0,/* tp_traverse */258 259 260 261 PyObject_SelfIter,/* tp_iter */262 (iternextfunc)rangeiter_next,/* tp_iternext */263 rangeiter_methods,/* tp_methods */264 259 PyObject_HEAD_INIT(&PyType_Type) 260 0, /* ob_size */ 261 "rangeiterator", /* tp_name */ 262 sizeof(rangeiterobject), /* tp_basicsize */ 263 0, /* tp_itemsize */ 264 /* methods */ 265 (destructor)PyObject_Del, /* tp_dealloc */ 266 0, /* tp_print */ 267 0, /* tp_getattr */ 268 0, /* tp_setattr */ 269 0, /* tp_compare */ 270 0, /* tp_repr */ 271 0, /* tp_as_number */ 272 0, /* tp_as_sequence */ 273 0, /* tp_as_mapping */ 274 0, /* tp_hash */ 275 0, /* tp_call */ 276 0, /* tp_str */ 277 PyObject_GenericGetAttr, /* tp_getattro */ 278 0, /* tp_setattro */ 279 0, /* tp_as_buffer */ 280 Py_TPFLAGS_DEFAULT, /* tp_flags */ 281 0, /* tp_doc */ 282 0, /* tp_traverse */ 283 0, /* tp_clear */ 284 0, /* tp_richcompare */ 285 0, /* tp_weaklistoffset */ 286 PyObject_SelfIter, /* tp_iter */ 287 (iternextfunc)rangeiter_next, /* tp_iternext */ 288 rangeiter_methods, /* tp_methods */ 289 0, 265 290 }; 266 291 … … 268 293 range_iter(PyObject *seq) 269 294 { 270 271 272 273 274 275 276 277 278 279 280 281 282 283 295 rangeiterobject *it; 296 297 if (!PyRange_Check(seq)) { 298 PyErr_BadInternalCall(); 299 return NULL; 300 } 301 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); 302 if (it == NULL) 303 return NULL; 304 it->index = 0; 305 it->start = ((rangeobject *)seq)->start; 306 it->step = ((rangeobject *)seq)->step; 307 it->len = ((rangeobject *)seq)->len; 308 return (PyObject *)it; 284 309 } 285 310 … … 287 312 range_reverse(PyObject *seq) 288 313 { 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 } 314 rangeiterobject *it; 315 long start, step, len; 316 317 if (!PyRange_Check(seq)) { 318 PyErr_BadInternalCall(); 319 return NULL; 320 } 321 it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); 322 if (it == NULL) 323 return NULL; 324 325 start = ((rangeobject *)seq)->start; 326 step = ((rangeobject *)seq)->step; 327 len = ((rangeobject *)seq)->len; 328 329 it->index = 0; 330 it->len = len; 331 /* the casts below guard against signed overflow by turning it 332 into unsigned overflow instead. The correctness of this 333 code still depends on conversion from unsigned long to long 334 wrapping modulo ULONG_MAX+1, which isn't guaranteed (see 335 C99 6.3.1.3p3) but seems to hold in practice for all 336 platforms we're likely to meet. 337 338 If step == LONG_MIN then we still end up with LONG_MIN 339 after negation; but this works out, since we've still got 340 the correct value modulo ULONG_MAX+1, and the range_item 341 calculation is also done modulo ULONG_MAX+1. 342 */ 343 it->start = (long)(start + (unsigned long)(len-1) * step); 344 it->step = (long)(0UL-step); 345 346 return (PyObject *)it; 347 }
Note:
See TracChangeset
for help on using the changeset viewer.