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