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