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 static PySequenceMethods range_as_sequence = {
 133         (lenfunc)range_length,  /* sq_length */
 134         0,                      /* sq_concat */
 135         0,                      /* sq_repeat */
 136         (ssizeargfunc)range_item, /* sq_item */
 137         0,                      /* sq_slice */
 138 };
 139
 140 static PyObject * range_iter(PyObject *seq);
 141 static PyObject * range_reverse(PyObject *seq);
 142
 143 PyDoc_STRVAR(reverse_doc,
 144 "Returns a reverse iterator.");
 145
 146 static PyMethodDef range_methods[] = {
 147         {"__reversed__",        (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
 148         {NULL,          NULL}           /* sentinel */
 149 };
 150
 151 PyTypeObject PyRange_Type = {
 152         PyObject_HEAD_INIT(&PyType_Type)
 153         0,                      /* Number of items for varobject */
 154         "xrange",               /* Name of this type */
 155         sizeof(rangeobject),    /* Basic object size */
 156         0,                      /* Item size for varobject */
 157         (destructor)PyObject_Del, /* tp_dealloc */
 158         0,                      /* tp_print */
 159         0,                      /* tp_getattr */
 160         0,                      /* tp_setattr */
 161         0,                      /* tp_compare */
 162         (reprfunc)range_repr,   /* tp_repr */
 163         0,                      /* tp_as_number */
 164         &range_as_sequence,     /* tp_as_sequence */
 165         0,                      /* tp_as_mapping */
 166         0,                      /* tp_hash */
 167         0,                      /* tp_call */
 168         0,                      /* tp_str */
 169         PyObject_GenericGetAttr,  /* tp_getattro */
 170         0,                      /* tp_setattro */
 171         0,                      /* tp_as_buffer */
 172         Py_TPFLAGS_DEFAULT,     /* tp_flags */
 173         range_doc,              /* tp_doc */
 174         0,                      /* tp_traverse */
 175         0,                      /* tp_clear */
 176         0,                      /* tp_richcompare */
 177         0,                      /* tp_weaklistoffset */
 178         range_iter,             /* tp_iter */
 179         0,                      /* tp_iternext */
 180         range_methods,          /* tp_methods */
 181         0,                      /* tp_members */
 182         0,                      /* tp_getset */
 183         0,                      /* tp_base */
 184         0,                      /* tp_dict */
 185         0,                      /* tp_descr_get */
 186         0,                      /* tp_descr_set */
 187         0,                      /* tp_dictoffset */
 188         0,                      /* tp_init */
 189         0,                      /* tp_alloc */
 190         range_new,              /* tp_new */
 191 };
 192
 193 /*********************** Xrange Iterator **************************/
 194
 195 typedef struct {
 196         PyObject_HEAD
 197         long    index;
 198         long    start;
 199         long    step;
 200         long    len;
 201 } rangeiterobject;
 202
 203 static PyObject *
 204 rangeiter_next(rangeiterobject *r)
 205 {
 206         if (r->index < r->len)
 207                 return PyInt_FromLong(r->start + (r->index++) * r->step);
 208         return NULL;
 209 }
 210
 211 static PyObject *
 212 rangeiter_len(rangeiterobject *r)
 213 {
 214         return PyInt_FromLong(r->len - r->index);
 215 }
 216
 217 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
 218
 219 static PyMethodDef rangeiter_methods[] = {
 220         {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc},
 221         {NULL,          NULL}           /* sentinel */
 222 };
 223
 224 static PyTypeObject Pyrangeiter_Type = {
 225         PyObject_HEAD_INIT(&PyType_Type)
 226         0,                                      /* ob_size */
 227         "rangeiterator",                        /* tp_name */
 228         sizeof(rangeiterobject),                /* tp_basicsize */
 229         0,                                      /* tp_itemsize */
 230         /* methods */
 231         (destructor)PyObject_Del,               /* tp_dealloc */
 232         0,                                      /* tp_print */
 233         0,                                      /* tp_getattr */
 234         0,                                      /* tp_setattr */
 235         0,                                      /* tp_compare */
 236         0,                                      /* tp_repr */
 237         0,                                      /* tp_as_number */
 238         0,                                      /* tp_as_sequence */
 239         0,                                      /* tp_as_mapping */
 240         0,                                      /* tp_hash */
 241         0,                                      /* tp_call */
 242         0,                                      /* tp_str */
 243         PyObject_GenericGetAttr,                /* tp_getattro */
 244         0,                                      /* tp_setattro */
 245         0,                                      /* tp_as_buffer */
 246         Py_TPFLAGS_DEFAULT,                     /* tp_flags */
 247         0,                                      /* tp_doc */
 248         0,                                      /* tp_traverse */
 249         0,                                      /* tp_clear */
 250         0,                                      /* tp_richcompare */
 251         0,                                      /* tp_weaklistoffset */
 252         PyObject_SelfIter,                      /* tp_iter */
 253         (iternextfunc)rangeiter_next,           /* tp_iternext */
 254         rangeiter_methods,                      /* tp_methods */
 255         0,
 256 };
 257
 258 static PyObject *
 259 range_iter(PyObject *seq)
 260 {
 261         rangeiterobject *it;
 262
 263         if (!PyRange_Check(seq)) {
 264                 PyErr_BadInternalCall();
 265                 return NULL;
 266         }
 267         it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
 268         if (it == NULL)
 269                 return NULL;
 270         it->index = 0;
 271         it->start = ((rangeobject *)seq)->start;
 272         it->step = ((rangeobject *)seq)->step;
 273         it->len = ((rangeobject *)seq)->len;
 274         return (PyObject *)it;
 275 }
 276
 277 static PyObject *
 278 range_reverse(PyObject *seq)
 279 {
 280         rangeiterobject *it;
 281         long start, step, len;
 282
 283         if (!PyRange_Check(seq)) {
 284                 PyErr_BadInternalCall();
 285                 return NULL;
 286         }
 287         it = PyObject_New(rangeiterobject, &Pyrangeiter_Type);
 288         if (it == NULL)
 289                 return NULL;
 290
 291         start = ((rangeobject *)seq)->start;
 292         step = ((rangeobject *)seq)->step;
 293         len = ((rangeobject *)seq)->len;
 294
 295         it->index = 0;
 296         it->start = start + (len-1) * step;
 297         it->step = -step;
 298         it->len = len;
 299
 300         return (PyObject *)it;
 301 }