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