rangeobject.c revision ca56dd4767617a2f5e946130de4beb06442a5cd5
112d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum/* Range object implementation */ 212d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum 3c0b618a2ccfb0fc39e07ee96dc09da77fbcce1b1Guido van Rossum#include "Python.h" 4efafcea2805436c12fd6544d9bff355cfac061d8Thomas Wouters 512d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossumtypedef struct { 6c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_HEAD 7c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long start; 8c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long step; 9c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long len; 1012d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum} rangeobject; 1112d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum 12009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson/* Return number of items in range (lo, hi, step). step != 0 13009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson * required. The result always fits in an unsigned long. 14c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger */ 15009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinsonstatic unsigned long 16c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettingerget_len_of_range(long lo, long hi, long step) 17c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger{ 18009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson /* ------------------------------------------------------------- 19009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty. 20009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson Else for step > 0, if n values are in the range, the last one is 21009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson lo + (n-1)*step, which must be <= hi-1. Rearranging, 22009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives 23009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so 24009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson the RHS is non-negative and so truncation is the same as the 25009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson floor. Letting M be the largest positive long, the worst case 26009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson for the RHS numerator is hi=M, lo=-M-1, and then 27009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough 28009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson precision to compute the RHS exactly. The analysis for step < 0 29009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson is similar. 30009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson ---------------------------------------------------------------*/ 31009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson assert(step != 0); 32009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson if (step > 0 && lo < hi) 33ca56dd4767617a2f5e946130de4beb06442a5cd5Martin Panter return 1UL + (hi - 1UL - lo) / step; 34009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson else if (step < 0 && lo > hi) 35ca56dd4767617a2f5e946130de4beb06442a5cd5Martin Panter return 1UL + (lo - 1UL - hi) / (0UL - step); 36009ae861f2a3ffcc3d6586fb1bcfdbd99547855aMark Dickinson else 37ca56dd4767617a2f5e946130de4beb06442a5cd5Martin Panter return 0UL; 38c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger} 39c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger 40218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson/* Return a stop value suitable for reconstructing the xrange from 41218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson * a (start, stop, step) triple. Used in range_repr and range_reduce. 42218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX]. 43218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson */ 44218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinsonstatic long 45218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinsonget_stop_for_range(rangeobject *r) 46218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson{ 47218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson long last; 48218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson 49218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson if (r->len == 0) 50218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson return r->start; 51218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson 52218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson /* The tricky bit is avoiding overflow. We first compute the last entry in 53218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson the xrange, start + (len - 1) * step, which is guaranteed to lie within 54218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson the range of a long, and then add step to it. See the range_reverse 55218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson comments for an explanation of the casts below. 56218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson */ 57218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson last = (long)(r->start + (unsigned long)(r->len - 1) * r->step); 58218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson if (r->step > 0) 59218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson return last > LONG_MAX - r->step ? LONG_MAX : last + r->step; 60218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson else 61218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson return last < LONG_MIN - r->step ? LONG_MIN : last + r->step; 62218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson} 63218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson 64c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettingerstatic PyObject * 65c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettingerrange_new(PyTypeObject *type, PyObject *args, PyObject *kw) 66c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger{ 67c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rangeobject *obj; 68c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long ilow = 0, ihigh = 0, istep = 1; 69c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou unsigned long n; 70c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 71c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (!_PyArg_NoKeywords("xrange()", kw)) 72c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 73c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 74c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (PyTuple_Size(args) <= 1) { 75c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (!PyArg_ParseTuple(args, 76c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "l;xrange() requires 1-3 int arguments", 77c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou &ihigh)) 78c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 79c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 80c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else { 81c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (!PyArg_ParseTuple(args, 82c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "ll|l;xrange() requires 1-3 int arguments", 83c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou &ilow, &ihigh, &istep)) 84c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 85c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 86c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (istep == 0) { 87c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero"); 88c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 89c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 90c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou n = get_len_of_range(ilow, ihigh, istep); 91c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) { 92c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyErr_SetString(PyExc_OverflowError, 93c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "xrange() result has too many items"); 94c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 95c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 96c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 97c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou obj = PyObject_New(rangeobject, &PyRange_Type); 98c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (obj == NULL) 99c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 100c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou obj->start = ilow; 101c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou obj->len = (long)n; 102c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou obj->step = istep; 103c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (PyObject *) obj; 104c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger} 105c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger 10614f8b4cfcb98de74b9c6e9316539be9e2a5cd31fMartin v. LöwisPyDoc_STRVAR(range_doc, 107ad4b0001794e47368b0997183b30b1171eab2790Chris Jerdonek"xrange(stop) -> xrange object\n\ 108ad4b0001794e47368b0997183b30b1171eab2790Chris Jerdonekxrange(start, stop[, step]) -> xrange object\n\ 109c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger\n\ 110c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond HettingerLike range(), but instead of returning a list, returns an object that\n\ 111d2bef8256bf7ce6bea7a80074cbd021b5af154afRaymond Hettingergenerates the numbers in the range on demand. For looping, this is \n\ 112d2bef8256bf7ce6bea7a80074cbd021b5af154afRaymond Hettingerslightly faster than range() and more memory efficient."); 113c4c453f5ae0a245aa0dd59431c323911c47f2735Raymond Hettinger 114c0b618a2ccfb0fc39e07ee96dc09da77fbcce1b1Guido van Rossumstatic PyObject * 11518e165558b24d29e7e0ca501842b9236589b012aMartin v. Löwisrange_item(rangeobject *r, Py_ssize_t i) 11612d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum{ 117c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (i < 0 || i >= r->len) { 118c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyErr_SetString(PyExc_IndexError, 119c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "xrange object index out of range"); 120c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 121c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 122c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* do calculation entirely using unsigned longs, to avoid 123c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou undefined behaviour due to signed overflow. */ 124c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step)); 12512d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum} 12612d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum 12718e165558b24d29e7e0ca501842b9236589b012aMartin v. Löwisstatic Py_ssize_t 12845cfbcccc287ae52656737466ca071ca18f603c7Fred Drakerange_length(rangeobject *r) 12912d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum{ 130c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (Py_ssize_t)(r->len); 1317d6aa51b56c6337ad5b1cb880f7c075290777f51Guido van Rossum} 1327d6aa51b56c6337ad5b1cb880f7c075290777f51Guido van Rossum 133c0b618a2ccfb0fc39e07ee96dc09da77fbcce1b1Guido van Rossumstatic PyObject * 13445cfbcccc287ae52656737466ca071ca18f603c7Fred Drakerange_repr(rangeobject *r) 13512d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum{ 136c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject *rtn; 137c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 138c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (r->start == 0 && r->step == 1) 139c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rtn = PyString_FromFormat("xrange(%ld)", 140218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson get_stop_for_range(r)); 141c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 142c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else if (r->step == 1) 143c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rtn = PyString_FromFormat("xrange(%ld, %ld)", 144c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou r->start, 145218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson get_stop_for_range(r)); 146c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 147c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou else 148c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)", 149c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou r->start, 150218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson get_stop_for_range(r), 151c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou r->step); 152c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return rtn; 153efafcea2805436c12fd6544d9bff355cfac061d8Thomas Wouters} 154efafcea2805436c12fd6544d9bff355cfac061d8Thomas Wouters 1551f2f61a78f80933a3e703df1ab08f14e70ea87d5Alexandre Vassalotti/* Pickling support */ 1561f2f61a78f80933a3e703df1ab08f14e70ea87d5Alexandre Vassalottistatic PyObject * 157602d8db2bc5ddc9a2de2843df92db53365478b3dAlexandre Vassalottirange_reduce(rangeobject *r, PyObject *args) 1581f2f61a78f80933a3e703df1ab08f14e70ea87d5Alexandre Vassalotti{ 159218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson return Py_BuildValue("(O(lll))", Py_TYPE(r), 160c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou r->start, 161218a8ab5eb6233cab176e69c1109d5b65cd04fbeMark Dickinson get_stop_for_range(r), 162c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou r->step); 1631f2f61a78f80933a3e703df1ab08f14e70ea87d5Alexandre Vassalotti} 1641f2f61a78f80933a3e703df1ab08f14e70ea87d5Alexandre Vassalotti 165c0b618a2ccfb0fc39e07ee96dc09da77fbcce1b1Guido van Rossumstatic PySequenceMethods range_as_sequence = { 166c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (lenfunc)range_length, /* sq_length */ 167c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* sq_concat */ 168c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* sq_repeat */ 169c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (ssizeargfunc)range_item, /* sq_item */ 170c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* sq_slice */ 17112d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum}; 17212d12c5faf4d770160b7975b54e8f9b12694e012Guido van Rossum 173938ace69a0e112424a2f426a4881d1fd1fc922d2Jeremy Hyltonstatic PyObject * range_iter(PyObject *seq); 17485c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettingerstatic PyObject * range_reverse(PyObject *seq); 17585c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettinger 17685c20a41dfcec04d161ad7da7260e7b94c62d228Raymond HettingerPyDoc_STRVAR(reverse_doc, 17785c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettinger"Returns a reverse iterator."); 17885c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettinger 17985c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettingerstatic PyMethodDef range_methods[] = { 180c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc}, 181c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS}, 182c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou {NULL, NULL} /* sentinel */ 18385c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettinger}; 18448165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger 185c0b618a2ccfb0fc39e07ee96dc09da77fbcce1b1Guido van RossumPyTypeObject PyRange_Type = { 186c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_HEAD_INIT(&PyType_Type) 187c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* Number of items for varobject */ 188c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "xrange", /* Name of this type */ 189c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou sizeof(rangeobject), /* Basic object size */ 190c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* Item size for varobject */ 191c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (destructor)PyObject_Del, /* tp_dealloc */ 192c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_print */ 193c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_getattr */ 194c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_setattr */ 195c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_compare */ 196c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (reprfunc)range_repr, /* tp_repr */ 197c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_number */ 198c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou &range_as_sequence, /* tp_as_sequence */ 199c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_mapping */ 200c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_hash */ 201c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_call */ 202c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_str */ 203c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_GenericGetAttr, /* tp_getattro */ 204c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_setattro */ 205c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_buffer */ 206c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou Py_TPFLAGS_DEFAULT, /* tp_flags */ 207c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou range_doc, /* tp_doc */ 208c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_traverse */ 209c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_clear */ 210c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_richcompare */ 211c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_weaklistoffset */ 212c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou range_iter, /* tp_iter */ 213c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_iternext */ 214c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou range_methods, /* tp_methods */ 215c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_members */ 216c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_getset */ 217c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_base */ 218c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_dict */ 219c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_descr_get */ 220c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_descr_set */ 221c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_dictoffset */ 222c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_init */ 223c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_alloc */ 224c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou range_new, /* tp_new */ 22548165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger}; 22648165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger 22748165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger/*********************** Xrange Iterator **************************/ 22848165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger 22948165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettingertypedef struct { 230c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_HEAD 231c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long index; 232c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long start; 233c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long step; 234c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long len; 23548165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger} rangeiterobject; 23648165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger 23785c20a41dfcec04d161ad7da7260e7b94c62d228Raymond Hettingerstatic PyObject * 23848165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettingerrangeiter_next(rangeiterobject *r) 23948165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger{ 240c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (r->index < r->len) 241c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyInt_FromLong(r->start + (r->index++) * r->step); 242c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 24348165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger} 24448165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger 2456b27cda64386195cd07dfb686e9486f1c4bc3159Raymond Hettingerstatic PyObject * 246ef9bf4031a2f9ec674817274c93a90e0f21db114Raymond Hettingerrangeiter_len(rangeiterobject *r) 247ef9bf4031a2f9ec674817274c93a90e0f21db114Raymond Hettinger{ 248c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return PyInt_FromLong(r->len - r->index); 249ef9bf4031a2f9ec674817274c93a90e0f21db114Raymond Hettinger} 250ef9bf4031a2f9ec674817274c93a90e0f21db114Raymond Hettinger 251f5b3e36493da275334e29afdbd238863697dca35Armin RigoPyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 252ef9bf4031a2f9ec674817274c93a90e0f21db114Raymond Hettinger 2536b27cda64386195cd07dfb686e9486f1c4bc3159Raymond Hettingerstatic PyMethodDef rangeiter_methods[] = { 254c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc}, 255c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou {NULL, NULL} /* sentinel */ 2566b27cda64386195cd07dfb686e9486f1c4bc3159Raymond Hettinger}; 257ef9bf4031a2f9ec674817274c93a90e0f21db114Raymond Hettinger 25856f46f8d8c1af1cf150df61f5aeafa40ca0b18e5Neal Norwitzstatic PyTypeObject Pyrangeiter_Type = { 259c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_HEAD_INIT(&PyType_Type) 260c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* ob_size */ 261c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou "rangeiterator", /* tp_name */ 262c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou sizeof(rangeiterobject), /* tp_basicsize */ 263c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_itemsize */ 264c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* methods */ 265c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (destructor)PyObject_Del, /* tp_dealloc */ 266c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_print */ 267c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_getattr */ 268c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_setattr */ 269c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_compare */ 270c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_repr */ 271c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_number */ 272c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_sequence */ 273c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_mapping */ 274c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_hash */ 275c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_call */ 276c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_str */ 277c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_GenericGetAttr, /* tp_getattro */ 278c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_setattro */ 279c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_as_buffer */ 280c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou Py_TPFLAGS_DEFAULT, /* tp_flags */ 281c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_doc */ 282c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_traverse */ 283c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_clear */ 284c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_richcompare */ 285c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, /* tp_weaklistoffset */ 286c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyObject_SelfIter, /* tp_iter */ 287c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou (iternextfunc)rangeiter_next, /* tp_iternext */ 288c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rangeiter_methods, /* tp_methods */ 289c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 0, 29048165d40cbe4280ba4c668798200548a22bce3ddRaymond Hettinger}; 29172d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwis 29272d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwisstatic PyObject * 29372d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwisrange_iter(PyObject *seq) 29472d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwis{ 295c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rangeiterobject *it; 296c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 297c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (!PyRange_Check(seq)) { 298c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyErr_BadInternalCall(); 299c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 300c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 301c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); 302c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (it == NULL) 303c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 304c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->index = 0; 305c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->start = ((rangeobject *)seq)->start; 306c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->step = ((rangeobject *)seq)->step; 307c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->len = ((rangeobject *)seq)->len; 308c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (PyObject *)it; 30972d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwis} 31072d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwis 31172d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwisstatic PyObject * 31272d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwisrange_reverse(PyObject *seq) 31372d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwis{ 314c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou rangeiterobject *it; 315c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou long start, step, len; 316c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 317c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (!PyRange_Check(seq)) { 318c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou PyErr_BadInternalCall(); 319c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 320c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou } 321c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); 322c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou if (it == NULL) 323c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return NULL; 324c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 325c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou start = ((rangeobject *)seq)->start; 326c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou step = ((rangeobject *)seq)->step; 327c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou len = ((rangeobject *)seq)->len; 328c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 329c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->index = 0; 330c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->len = len; 331c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou /* the casts below guard against signed overflow by turning it 332c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou into unsigned overflow instead. The correctness of this 333c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou code still depends on conversion from unsigned long to long 334c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou wrapping modulo ULONG_MAX+1, which isn't guaranteed (see 335c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou C99 6.3.1.3p3) but seems to hold in practice for all 336c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou platforms we're likely to meet. 337c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 338c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou If step == LONG_MIN then we still end up with LONG_MIN 339c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou after negation; but this works out, since we've still got 340c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou the correct value modulo ULONG_MAX+1, and the range_item 341c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou calculation is also done modulo ULONG_MAX+1. 342c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou */ 343c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->start = (long)(start + (unsigned long)(len-1) * step); 344c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou it->step = (long)(0UL-step); 345c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou 346c83ea137d7e717f764e2f31fc2544f522de7d857Antoine Pitrou return (PyObject *)it; 34772d206776d34bcc38abbf16aa93c2d25ebec4df9Martin v. Löwis} 348