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