Objects/rangeobject.c

   1
   2 /* Range object implementation */
   3
   4 #include "Python.h"
   5 #include "structmember.h"
   6 #include <string.h>
   7
   8 typedef struct {
   9         PyObject_HEAD
  10         long    start;
  11         long    step;
  12         long    len;
  13         int     reps;
  14         long    totlen;
  15 } rangeobject;
  16
  17 static int
  18 long_mul(long i, long j, long *kk)
  19 {
  20         PyObject *a;
  21         PyObject *b;
  22         PyObject *c;
  23
  24         if ((a = PyInt_FromLong(i)) == NULL)
  25                 return 0;
  26
  27         if ((b = PyInt_FromLong(j)) == NULL)
  28                 return 0;
  29
  30         c = PyNumber_Multiply(a, b);
  31
  32         Py_DECREF(a);
  33         Py_DECREF(b);
  34
  35         if (c == NULL)
  36                 return 0;
  37
  38         *kk = PyInt_AS_LONG(c);
  39         Py_DECREF(c);
  40
  41         if (*kk > INT_MAX) {
  42                 PyErr_SetString(PyExc_OverflowError,
  43                                 "integer multiplication");
  44                 return 0;
  45         }
  46         else
  47                 return 1;
  48 }
  49
  50 PyObject *
  51 PyRange_New(long start, long len, long step, int reps)
  52 {
  53         long totlen = -1;
  54         rangeobject *obj = PyObject_NEW(rangeobject, &PyRange_Type);
  55
  56         if (obj == NULL)
  57                 return NULL;
  58
  59         if (len == 0 || reps <= 0) {
  60                 start = 0;
  61                 len = 0;
  62                 step = 1;
  63                 reps = 1;
  64                 totlen = 0;
  65         }
  66         else {
  67                 long last = start + (len - 1) * step;
  68                 if ((step > 0) ?
  69                     (last > (PyInt_GetMax() - step))
  70                     :(last < (-1 - PyInt_GetMax() - step))) {
  71                         PyErr_SetString(PyExc_OverflowError,
  72                                         "integer addition");
  73                         return NULL;
  74                 }
  75                 if (! long_mul(len, (long) reps, &totlen)) {
  76                         if(!PyErr_ExceptionMatches(PyExc_OverflowError))
  77                                 return NULL;
  78                         PyErr_Clear();
  79                         totlen = -1;
  80                 }
  81         }
  82
  83         obj->start = start;
  84         obj->len   = len;
  85         obj->step  = step;
  86         obj->reps  = reps;
  87         obj->totlen = totlen;
  88
  89         return (PyObject *) obj;
  90 }
  91
  92 static void
  93 range_dealloc(rangeobject *r)
  94 {
  95         PyObject_DEL(r);
  96 }
  97
  98 static PyObject *
  99 range_item(rangeobject *r, int i)
 100 {
 101         if (i < 0 || i >= r->totlen)
 102                 if (r->totlen!=-1) {
 103                         PyErr_SetString(PyExc_IndexError,
 104                                 "xrange object index out of range");
 105                         return NULL;
 106                 }
 107
 108         return PyInt_FromLong(r->start + (i % r->len) * r->step);
 109 }
 110
 111 static int
 112 range_length(rangeobject *r)
 113 {
 114         if (r->totlen == -1)
 115                 PyErr_SetString(PyExc_OverflowError,
 116                                 "xrange object has too many items");
 117         return r->totlen;
 118 }
 119
 120 static PyObject *
 121 range_repr(rangeobject *r)
 122 {
 123         /* buffers must be big enough to hold 3 longs + an int +
 124          * a bit of "(xrange(...) * ...)" text.
 125          */
 126         char buf1[250];
 127         char buf2[250];
 128
 129         if (r->start == 0 && r->step == 1)
 130                 sprintf(buf1, "xrange(%ld)", r->start + r->len * r->step);
 131
 132         else if (r->step == 1)
 133                 sprintf(buf1, "xrange(%ld, %ld)",
 134                         r->start,
 135                         r->start + r->len * r->step);
 136
 137         else
 138                 sprintf(buf1, "xrange(%ld, %ld, %ld)",
 139                         r->start,
 140                         r->start + r->len * r->step,
 141                         r->step);
 142
 143         if (r->reps != 1)
 144                 sprintf(buf2, "(%s * %d)", buf1, r->reps);
 145
 146         return PyString_FromString(r->reps == 1 ? buf1 : buf2);
 147 }
 148
 149 static PyObject *
 150 range_concat(rangeobject *r, PyObject *obj)
 151 {
 152         PyErr_SetString(PyExc_TypeError, "cannot concatenate xrange objects");
 153         return NULL;
 154 }
 155
 156 static PyObject *
 157 range_repeat(rangeobject *r, int n)
 158 {
 159         long lreps = 0;
 160
 161         if (n <= 0)
 162                 return (PyObject *) PyRange_New(0, 0, 1, 1);
 163
 164         else if (n == 1) {
 165                 Py_INCREF(r);
 166                 return (PyObject *) r;
 167         }
 168
 169         else if (! long_mul((long) r->reps, (long) n, &lreps))
 170                 return NULL;
 171
 172         else
 173                 return (PyObject *) PyRange_New(
 174                                                 r->start,
 175                                                 r->len,
 176                                                 r->step,
 177                                                 (int) lreps);
 178 }
 179
 180 static int
 181 range_compare(rangeobject *r1, rangeobject *r2)
 182 {
 183         if (r1->start != r2->start)
 184                 return r1->start - r2->start;
 185
 186         else if (r1->step != r2->step)
 187                 return r1->step - r2->step;
 188
 189         else if (r1->len != r2->len)
 190                 return r1->len - r2->len;
 191
 192         else
 193                 return r1->reps - r2->reps;
 194 }
 195
 196 static PyObject *
 197 range_slice(rangeobject *r, int low, int high)
 198 {
 199         if (r->reps != 1) {
 200                 PyErr_SetString(PyExc_TypeError,
 201                                 "cannot slice a replicated xrange");
 202                 return NULL;
 203         }
 204         if (low < 0)
 205                 low = 0;
 206         else if (low > r->len)
 207                 low = r->len;
 208         if (high < 0)
 209                 high = 0;
 210         if (high < low)
 211                 high = low;
 212         else if (high > r->len)
 213                 high = r->len;
 214
 215         if (low == 0 && high == r->len) {
 216                 Py_INCREF(r);
 217                 return (PyObject *) r;
 218         }
 219
 220         return (PyObject *) PyRange_New(
 221                                 low * r->step + r->start,
 222                                 high - low,
 223                                 r->step,
 224                                 1);
 225 }
 226
 227 static PyObject *
 228 range_tolist(rangeobject *self, PyObject *args)
 229 {
 230         PyObject *thelist;
 231         int j;
 232
 233         if (! PyArg_ParseTuple(args, ":tolist"))
 234                 return NULL;
 235
 236         if (self->totlen == -1)
 237                 return PyErr_NoMemory();
 238
 239         if ((thelist = PyList_New(self->totlen)) == NULL)
 240                 return NULL;
 241
 242         for (j = 0; j < self->totlen; ++j)
 243                 if ((PyList_SetItem(thelist, j, (PyObject *) PyInt_FromLong(
 244                         self->start + (j % self->len) * self->step))) < 0)
 245                         return NULL;
 246
 247         return thelist;
 248 }
 249
 250 static PyObject *
 251 range_getattr(rangeobject *r, char *name)
 252 {
 253         PyObject *result;
 254
 255         static PyMethodDef range_methods[] = {
 256                 {"tolist",      (PyCFunction)range_tolist, METH_VARARGS,
 257                  "tolist() -> list\n"
 258                  "Return a list object with the same values."},
 259                 {NULL,          NULL}
 260         };
 261         static struct memberlist range_members[] = {
 262                 {"step",  T_LONG, offsetof(rangeobject, step), RO},
 263                 {"start", T_LONG, offsetof(rangeobject, start), RO},
 264                 {"stop",  T_LONG, 0, RO},
 265                 {NULL, 0, 0, 0}
 266         };
 267
 268         result = Py_FindMethod(range_methods, (PyObject *) r, name);
 269         if (result == NULL) {
 270                 PyErr_Clear();
 271                 if (strcmp("stop", name) == 0)
 272                         result = PyInt_FromLong(r->start + (r->len * r->step));
 273                 else
 274                         result = PyMember_Get((char *)r, range_members, name);
 275         }
 276         return result;
 277 }
 278
 279 static int
 280 range_contains(rangeobject *r, PyObject *obj)
 281 {
 282         long num = PyInt_AsLong(obj);
 283
 284         if (num < 0 && PyErr_Occurred())
 285                 return -1;
 286
 287         if (r->step > 0) {
 288                 if ((num < r->start) || ((num - r->start) % r->step))
 289                         return 0;
 290                 if (num >= (r->start + (r->len * r->step)))
 291                         return 0;
 292         }
 293         else {
 294                 if ((num > r->start) || ((num - r->start) % r->step))
 295                         return 0;
 296                 if (num <= (r->start + (r->len * r->step)))
 297                         return 0;
 298         }
 299         return 1;
 300 }
 301
 302 static PySequenceMethods range_as_sequence = {
 303         (inquiry)range_length,  /*sq_length*/
 304         (binaryfunc)range_concat, /*sq_concat*/
 305         (intargfunc)range_repeat, /*sq_repeat*/
 306         (intargfunc)range_item, /*sq_item*/
 307         (intintargfunc)range_slice, /*sq_slice*/
 308         0,                      /*sq_ass_item*/
 309         0,                      /*sq_ass_slice*/
 310         (objobjproc)range_contains, /*sq_contains*/
 311 };
 312
 313 PyTypeObject PyRange_Type = {
 314         PyObject_HEAD_INIT(&PyType_Type)
 315         0,                      /* Number of items for varobject */
 316         "xrange",               /* Name of this type */
 317         sizeof(rangeobject),    /* Basic object size */
 318         0,                      /* Item size for varobject */
 319         (destructor)range_dealloc, /*tp_dealloc*/
 320         0,                      /*tp_print*/
 321         (getattrfunc)range_getattr, /*tp_getattr*/
 322         0,                      /*tp_setattr*/
 323         (cmpfunc)range_compare, /*tp_compare*/
 324         (reprfunc)range_repr,   /*tp_repr*/
 325         0,                      /*tp_as_number*/
 326         &range_as_sequence,     /*tp_as_sequence*/
 327         0,                      /*tp_as_mapping*/
 328         0,                      /*tp_hash*/
 329         0,                      /*tp_call*/
 330         0,                      /*tp_str*/
 331         0,                      /*tp_getattro*/
 332         0,                      /*tp_setattro*/
 333         0,                      /*tp_as_buffer*/
 334         Py_TPFLAGS_DEFAULT,     /*tp_flags*/
 335 };