AppPkg/Applications/Python/Python-2.7.2/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 }