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