+++ /dev/null
-/* Range object implementation */\r
-\r
-#include "Python.h"\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- long start;\r
- long step;\r
- long len;\r
-} rangeobject;\r
-\r
-/* Return number of items in range (lo, hi, step). step != 0\r
- * required. The result always fits in an unsigned long.\r
- */\r
-static unsigned long\r
-get_len_of_range(long lo, long hi, long step)\r
-{\r
- /* -------------------------------------------------------------\r
- If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.\r
- Else for step > 0, if n values are in the range, the last one is\r
- lo + (n-1)*step, which must be <= hi-1. Rearranging,\r
- n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives\r
- the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so\r
- the RHS is non-negative and so truncation is the same as the\r
- floor. Letting M be the largest positive long, the worst case\r
- for the RHS numerator is hi=M, lo=-M-1, and then\r
- hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough\r
- precision to compute the RHS exactly. The analysis for step < 0\r
- is similar.\r
- ---------------------------------------------------------------*/\r
- assert(step != 0);\r
- if (step > 0 && lo < hi)\r
- return 1UL + (hi - 1UL - lo) / step;\r
- else if (step < 0 && lo > hi)\r
- return 1UL + (lo - 1UL - hi) / (0UL - step);\r
- else\r
- return 0UL;\r
-}\r
-\r
-/* Return a stop value suitable for reconstructing the xrange from\r
- * a (start, stop, step) triple. Used in range_repr and range_reduce.\r
- * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX].\r
- */\r
-static long\r
-get_stop_for_range(rangeobject *r)\r
-{\r
- long last;\r
-\r
- if (r->len == 0)\r
- return r->start;\r
-\r
- /* The tricky bit is avoiding overflow. We first compute the last entry in\r
- the xrange, start + (len - 1) * step, which is guaranteed to lie within\r
- the range of a long, and then add step to it. See the range_reverse\r
- comments for an explanation of the casts below.\r
- */\r
- last = (long)(r->start + (unsigned long)(r->len - 1) * r->step);\r
- if (r->step > 0)\r
- return last > LONG_MAX - r->step ? LONG_MAX : last + r->step;\r
- else\r
- return last < LONG_MIN - r->step ? LONG_MIN : last + r->step;\r
-}\r
-\r
-static PyObject *\r
-range_new(PyTypeObject *type, PyObject *args, PyObject *kw)\r
-{\r
- rangeobject *obj;\r
- long ilow = 0, ihigh = 0, istep = 1;\r
- unsigned long n;\r
-\r
- if (!_PyArg_NoKeywords("xrange()", kw))\r
- return NULL;\r
-\r
- if (PyTuple_Size(args) <= 1) {\r
- if (!PyArg_ParseTuple(args,\r
- "l;xrange() requires 1-3 int arguments",\r
- &ihigh))\r
- return NULL;\r
- }\r
- else {\r
- if (!PyArg_ParseTuple(args,\r
- "ll|l;xrange() requires 1-3 int arguments",\r
- &ilow, &ihigh, &istep))\r
- return NULL;\r
- }\r
- if (istep == 0) {\r
- PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero");\r
- return NULL;\r
- }\r
- n = get_len_of_range(ilow, ihigh, istep);\r
- if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) {\r
- PyErr_SetString(PyExc_OverflowError,\r
- "xrange() result has too many items");\r
- return NULL;\r
- }\r
-\r
- obj = PyObject_New(rangeobject, &PyRange_Type);\r
- if (obj == NULL)\r
- return NULL;\r
- obj->start = ilow;\r
- obj->len = (long)n;\r
- obj->step = istep;\r
- return (PyObject *) obj;\r
-}\r
-\r
-PyDoc_STRVAR(range_doc,\r
-"xrange(stop) -> xrange object\n\\r
-xrange(start, stop[, step]) -> xrange object\n\\r
-\n\\r
-Like range(), but instead of returning a list, returns an object that\n\\r
-generates the numbers in the range on demand. For looping, this is \n\\r
-slightly faster than range() and more memory efficient.");\r
-\r
-static PyObject *\r
-range_item(rangeobject *r, Py_ssize_t i)\r
-{\r
- if (i < 0 || i >= r->len) {\r
- PyErr_SetString(PyExc_IndexError,\r
- "xrange object index out of range");\r
- return NULL;\r
- }\r
- /* do calculation entirely using unsigned longs, to avoid\r
- undefined behaviour due to signed overflow. */\r
- return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step));\r
-}\r
-\r
-static Py_ssize_t\r
-range_length(rangeobject *r)\r
-{\r
- return (Py_ssize_t)(r->len);\r
-}\r
-\r
-static PyObject *\r
-range_repr(rangeobject *r)\r
-{\r
- PyObject *rtn;\r
-\r
- if (r->start == 0 && r->step == 1)\r
- rtn = PyString_FromFormat("xrange(%ld)",\r
- get_stop_for_range(r));\r
-\r
- else if (r->step == 1)\r
- rtn = PyString_FromFormat("xrange(%ld, %ld)",\r
- r->start,\r
- get_stop_for_range(r));\r
-\r
- else\r
- rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)",\r
- r->start,\r
- get_stop_for_range(r),\r
- r->step);\r
- return rtn;\r
-}\r
-\r
-/* Pickling support */\r
-static PyObject *\r
-range_reduce(rangeobject *r, PyObject *args)\r
-{\r
- return Py_BuildValue("(O(lll))", Py_TYPE(r),\r
- r->start,\r
- get_stop_for_range(r),\r
- r->step);\r
-}\r
-\r
-static PySequenceMethods range_as_sequence = {\r
- (lenfunc)range_length, /* sq_length */\r
- 0, /* sq_concat */\r
- 0, /* sq_repeat */\r
- (ssizeargfunc)range_item, /* sq_item */\r
- 0, /* sq_slice */\r
-};\r
-\r
-static PyObject * range_iter(PyObject *seq);\r
-static PyObject * range_reverse(PyObject *seq);\r
-\r
-PyDoc_STRVAR(reverse_doc,\r
-"Returns a reverse iterator.");\r
-\r
-static PyMethodDef range_methods[] = {\r
- {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},\r
- {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-PyTypeObject PyRange_Type = {\r
- PyObject_HEAD_INIT(&PyType_Type)\r
- 0, /* Number of items for varobject */\r
- "xrange", /* Name of this type */\r
- sizeof(rangeobject), /* Basic object size */\r
- 0, /* Item size for varobject */\r
- (destructor)PyObject_Del, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- (reprfunc)range_repr, /* tp_repr */\r
- 0, /* tp_as_number */\r
- &range_as_sequence, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT, /* tp_flags */\r
- range_doc, /* tp_doc */\r
- 0, /* tp_traverse */\r
- 0, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- range_iter, /* tp_iter */\r
- 0, /* tp_iternext */\r
- range_methods, /* tp_methods */\r
- 0, /* tp_members */\r
- 0, /* tp_getset */\r
- 0, /* tp_base */\r
- 0, /* tp_dict */\r
- 0, /* tp_descr_get */\r
- 0, /* tp_descr_set */\r
- 0, /* tp_dictoffset */\r
- 0, /* tp_init */\r
- 0, /* tp_alloc */\r
- range_new, /* tp_new */\r
-};\r
-\r
-/*********************** Xrange Iterator **************************/\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- long index;\r
- long start;\r
- long step;\r
- long len;\r
-} rangeiterobject;\r
-\r
-static PyObject *\r
-rangeiter_next(rangeiterobject *r)\r
-{\r
- if (r->index < r->len)\r
- return PyInt_FromLong(r->start + (r->index++) * r->step);\r
- return NULL;\r
-}\r
-\r
-static PyObject *\r
-rangeiter_len(rangeiterobject *r)\r
-{\r
- return PyInt_FromLong(r->len - r->index);\r
-}\r
-\r
-PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");\r
-\r
-static PyMethodDef rangeiter_methods[] = {\r
- {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-static PyTypeObject Pyrangeiter_Type = {\r
- PyObject_HEAD_INIT(&PyType_Type)\r
- 0, /* ob_size */\r
- "rangeiterator", /* tp_name */\r
- sizeof(rangeiterobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)PyObject_Del, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT, /* tp_flags */\r
- 0, /* tp_doc */\r
- 0, /* tp_traverse */\r
- 0, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- PyObject_SelfIter, /* tp_iter */\r
- (iternextfunc)rangeiter_next, /* tp_iternext */\r
- rangeiter_methods, /* tp_methods */\r
- 0,\r
-};\r
-\r
-static PyObject *\r
-range_iter(PyObject *seq)\r
-{\r
- rangeiterobject *it;\r
-\r
- if (!PyRange_Check(seq)) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);\r
- if (it == NULL)\r
- return NULL;\r
- it->index = 0;\r
- it->start = ((rangeobject *)seq)->start;\r
- it->step = ((rangeobject *)seq)->step;\r
- it->len = ((rangeobject *)seq)->len;\r
- return (PyObject *)it;\r
-}\r
-\r
-static PyObject *\r
-range_reverse(PyObject *seq)\r
-{\r
- rangeiterobject *it;\r
- long start, step, len;\r
-\r
- if (!PyRange_Check(seq)) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);\r
- if (it == NULL)\r
- return NULL;\r
-\r
- start = ((rangeobject *)seq)->start;\r
- step = ((rangeobject *)seq)->step;\r
- len = ((rangeobject *)seq)->len;\r
-\r
- it->index = 0;\r
- it->len = len;\r
- /* the casts below guard against signed overflow by turning it\r
- into unsigned overflow instead. The correctness of this\r
- code still depends on conversion from unsigned long to long\r
- wrapping modulo ULONG_MAX+1, which isn't guaranteed (see\r
- C99 6.3.1.3p3) but seems to hold in practice for all\r
- platforms we're likely to meet.\r
-\r
- If step == LONG_MIN then we still end up with LONG_MIN\r
- after negation; but this works out, since we've still got\r
- the correct value modulo ULONG_MAX+1, and the range_item\r
- calculation is also done modulo ULONG_MAX+1.\r
- */\r
- it->start = (long)(start + (unsigned long)(len-1) * step);\r
- it->step = (long)(0UL-step);\r
-\r
- return (PyObject *)it;\r
-}\r