Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(185)
Issues Repositories
Recent Issues | Sign in with your Google Account to create issues and add comments

Delta Between Two Patch Sets: Objects/rangeobject.c

Issue 602: range: lean and mean (Closed) SVN Base: http://svn.python.org/view/*checkout*/python/branches/py3k/
Left Patch Set: use PyMemberDef Created 5 months, 1 week ago , Downloaded from: http://bugs.python.org/file10155/range_lean_and_mean2.patch
Right Patch Set: in response to reviews Created 5 months, 1 week ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
« Lib/test/test_range.py ('k') | no next file » | Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Hide Comments ('s')
LEFTRIGHT
1 /* Range object implementation */ 1 /* Range object implementation */
2 2
3 #include "Python.h" 3 #include "Python.h"
4 #include "structmember.h" 4 #include "structmember.h"
5 5
6 /* Support objects whose length is > PY_SSIZE_T_MAX. 6 /* Support objects whose length is > PY_SSIZE_T_MAX.
7 7
8 This could be sped up for small PyLongs if they fit in an Py_ssize_t. 8 This could be sped up for small PyLongs if they fit in an Py_ssize_t.
9 This only matters on Win64. Though we could use PY_LONG_LONG which 9 This only matters on Win64. Though we could use PY_LONG_LONG which
10 would presumably help perf. 10 would presumably help perf.
(...skipping 28 matching lines...) Show 10 above Show 10 below
39 PyErr_SetString(PyExc_ValueError, 39 PyErr_SetString(PyExc_ValueError,
40 "range() arg 3 must not be zero"); 40 "range() arg 3 must not be zero");
41 Py_CLEAR(step); 41 Py_CLEAR(step);
42 } 42 }
43 } 43 }
44 44
45 return step; 45 return step;
46 } 46 }
47 47
48 static PyObject* range_compute_length(PyObject *start, 48 static PyObject* range_compute_length(PyObject *start,
49 PyObject *stop, PyObject *step); 49 PyObject *stop, PyObject *step);
50 50
51 /* XXX(nnorwitz): should we error check if the user passes any empty ranges? 51 /* XXX(nnorwitz): should we error check if the user passes any empty ranges?
52 range(-10) 52 range(-10)
53 range(0, -5) 53 range(0, -5)
54 range(0, 5, -1) 54 range(0, 5, -1)
55 */ 55 */
56 static PyObject * 56 static PyObject *
57 range_new(PyTypeObject *type, PyObject *args, PyObject *kw) 57 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
58 { 58 {
59 rangeobject *obj = NULL; 59 rangeobject *obj = NULL;
(...skipping 42 matching lines...) Show 10 above Show 10 below
102 Py_XDECREF(start); 102 Py_XDECREF(start);
103 Py_XDECREF(stop); 103 Py_XDECREF(stop);
104 Py_XDECREF(step); 104 Py_XDECREF(step);
105 Py_XDECREF(length); 105 Py_XDECREF(length);
106 return NULL; 106 return NULL;
107 } 107 }
108 108
109 PyDoc_STRVAR(range_doc, 109 PyDoc_STRVAR(range_doc,
110 "range([start,] stop[, step]) -> range object\n\ 110 "range([start,] stop[, step]) -> range object\n\
111 \n\ 111 \n\
112 Returns a virtual sequence of numbers from start to stop by step."); 112 Return an arithmetic progression of numbers from start "
113 "to stop (exclusive) by step.");
113 114
114 static void 115 static void
115 range_dealloc(rangeobject *r) 116 range_dealloc(rangeobject *r)
116 { 117 {
117 Py_DECREF(r->start); 118 Py_DECREF(r->start);
118 Py_DECREF(r->stop); 119 Py_DECREF(r->stop);
119 Py_DECREF(r->step); 120 Py_DECREF(r->step);
120 Py_DECREF(r->length); 121 Py_DECREF(r->length);
121 PyObject_Del(r); 122 PyObject_Del(r);
122 } 123 }
123 124
GvR 2008/05/03 05:04:35 Hm. I didn't mean for you to delete the entire com
124 /* Return number of items in range (lo, hi, step), when arguments are
125 * PyInt or PyLong objects. step > 0 required. Return a value < 0 if
126 * & only if the true value is too large to fit in a signed long.
127 * Arguments MUST return 1 with either PyLong_Check() or
128 * PyLong_Check(). Return -1 when there is an error.
129 */
130 static PyObject * 125 static PyObject *
131 range_compute_length(PyObject *start, PyObject *stop, PyObject *step) 126 range_compute_length(PyObject *start, PyObject *stop, PyObject *step)
132 { 127 {
133 /* ------------------------------------------------------------- 128 /* -------------------------------------------------------------
134 Algorithm is equal to that of get_len_of_range(), but it operates 129 Algorithm is equal to that of get_len_of_range(), but it operates
135 on PyObjects (which are assumed to be PyLong or PyInt objects). 130 on PyObjects (which are assumed to be PyLong or PyInt objects).
136 ---------------------------------------------------------------*/ 131 ---------------------------------------------------------------*/
137 int cmp_result, cmp_call; 132 int cmp_result, cmp_call;
138 PyObject *lo, *hi; 133 PyObject *lo, *hi;
139 PyObject *diff = NULL; 134 PyObject *diff = NULL;
(...skipping 52 matching lines...) Show 10 above Show 10 below
192 187
193 Fail: 188 Fail:
194 Py_XDECREF(tmp2); 189 Py_XDECREF(tmp2);
195 Py_XDECREF(diff); 190 Py_XDECREF(diff);
196 Py_XDECREF(step); 191 Py_XDECREF(step);
197 Py_XDECREF(tmp1); 192 Py_XDECREF(tmp1);
198 Py_XDECREF(one); 193 Py_XDECREF(one);
199 return NULL; 194 return NULL;
200 } 195 }
201 196
202 static Py_ssize_t 197 static PyObject *
203 range_length(rangeobject *r) 198 range_length_hint(rangeobject *r)
204 { 199 {
205 return PyLong_AsSsize_t(r->length); 200 Py_INCREF(r->length);
206 } 201 return r->length;
202 }
203
204 PyDoc_STRVAR(range_length_hint_doc,
205 "__length_hint__() -> int\n"
206 "Return a estimate of len(list(range)).");
207 207
208 208
209 static PyObject * 209 static PyObject *
210 range_repr(rangeobject *r) 210 range_repr(rangeobject *r)
211 { 211 {
212 Py_ssize_t istep; 212 Py_ssize_t istep;
213 213
214 /* Check for special case values for printing. We don't always 214 /* Check for special case values for printing. We don't always
215 need the step value. We don't care about errors 215 need the step value. We don't care about errors
216 (it means overflow), so clear the errors. */ 216 (it means overflow), so clear the errors. */
217 istep = PyNumber_AsSsize_t(r->step, NULL); 217 istep = PyNumber_AsSsize_t(r->step, NULL);
218 if (istep != 1 || (istep == -1 && PyErr_Occurred())) { 218 if (istep != 1 || (istep == -1 && PyErr_Occurred())) {
219 PyErr_Clear(); 219 PyErr_Clear();
220 } 220 }
221 221
222 if (istep == 1) 222 if (istep == 1)
223 return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop); 223 return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
224 else 224 else
225 return PyUnicode_FromFormat("range(%R, %R, %R)", 225 return PyUnicode_FromFormat("range(%R, %R, %R)",
226 r->start, r->stop, r->step); 226 r->start, r->stop, r->step);
227 } 227 }
228 228
229 static PyMemberDef range_members[] = { 229 static PyMemberDef range_members[] = {
230 {"start", T_OBJECT, offsetof(rangeobject, start), READONLY}, 230 {"start", T_OBJECT, offsetof(rangeobject, start), READONLY},
231 {"stop", T_OBJECT, offsetof(rangeobject, stop), READONLY}, 231 {"stop", T_OBJECT, offsetof(rangeobject, stop), READONLY},
232 {"step", T_OBJECT, offsetof(rangeobject, step), READONLY}, 232 {"step", T_OBJECT, offsetof(rangeobject, step), READONLY},
233 {0} 233 {0}
234 }; 234 };
235 235
236 static PySequenceMethods range_as_sequence = {
237 (lenfunc)range_length, /* sq_length */
238 0, /* sq_concat */
239 0, /* sq_repeat */
240 0, /* sq_item */
241 0, /* sq_slice */
242 0, /* sq_ass_item */
243 0, /* sq_ass_slice */
244 0, /* sq_contains */
245 };
246
247 static PyObject * range_iter(PyObject *seq); 236 static PyObject * range_iter(PyObject *seq);
248 static PyObject * range_reverse(PyObject *seq); 237 static PyObject * range_reverse(PyObject *seq);
249 238
250 PyDoc_STRVAR(reverse_doc, 239 PyDoc_STRVAR(reverse_doc,
251 "Returns a reverse iterator."); 240 "Returns a reverse iterator.");
252 241
253 static PyMethodDef range_methods[] = { 242 static PyMethodDef range_methods[] = {
254 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, 243 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS,
255 reverse_doc}, 244 reverse_doc},
245 {"__length_hint__", (PyCFunction)range_length_hint, METH_NOARGS,
246 range_length_hint_doc},
256 {NULL, NULL} /* sentinel */ 247 {NULL, NULL} /* sentinel */
257 }; 248 };
258 249
259 PyTypeObject PyRange_Type = { 250 PyTypeObject PyRange_Type = {
260 PyVarObject_HEAD_INIT(&PyType_Type, 0) 251 PyVarObject_HEAD_INIT(&PyType_Type, 0)
261 "range", /* Name of this type */ 252 "range", /* Name of this type */
262 sizeof(rangeobject), /* Basic object size */ 253 sizeof(rangeobject), /* Basic object size */
263 0, /* Item size for varobject */ 254 0, /* Item size for varobject */
264 (destructor)range_dealloc, /* tp_dealloc */ 255 (destructor)range_dealloc, /* tp_dealloc */
265 0, /* tp_print */ 256 0, /* tp_print */
266 0, /* tp_getattr */ 257 0, /* tp_getattr */
267 0, /* tp_setattr */ 258 0, /* tp_setattr */
268 0, /* tp_compare */ 259 0, /* tp_compare */
269 (reprfunc)range_repr, /* tp_repr */ 260 (reprfunc)range_repr, /* tp_repr */
270 0, /* tp_as_number */ 261 0, /* tp_as_number */
271 &range_as_sequence, /* tp_as_sequence */ 262 0, /* tp_as_sequence */
272 0, /* tp_as_mapping */ 263 0, /* tp_as_mapping */
273 0, /* tp_hash */ 264 0, /* tp_hash */
274 0, /* tp_call */ 265 0, /* tp_call */
275 0, /* tp_str */ 266 0, /* tp_str */
276 PyObject_GenericGetAttr, /* tp_getattro */ 267 PyObject_GenericGetAttr, /* tp_getattro */
277 0, /* tp_setattro */ 268 0, /* tp_setattro */
278 0, /* tp_as_buffer */ 269 0, /* tp_as_buffer */
279 Py_TPFLAGS_DEFAULT, /* tp_flags */ 270 Py_TPFLAGS_DEFAULT, /* tp_flags */
280 range_doc, /* tp_doc */ 271 range_doc, /* tp_doc */
281 0, /* tp_traverse */ 272 0, /* tp_traverse */
282 0, /* tp_clear */ 273 0, /* tp_clear */
283 0, /* tp_richcompare */ 274 0, /* tp_richcompare */
284 0, /* tp_weaklistoffset */ 275 0, /* tp_weaklistoffset */
285 range_iter, /* tp_iter */ 276 range_iter, /* tp_iter */
286 0, /* tp_iternext */ 277 0, /* tp_iternext */
287 range_methods, /* tp_methods */ 278 range_methods, /* tp_methods */
288 range_members, /* tp_members */ 279 range_members, /* tp_members */
mvloewis 2008/05/02 20:17:20 Carrying forward from the previous patch set: this
289 0, /* tp_getset */ 280 0, /* tp_getset */
290 0, /* tp_base */ 281 0, /* tp_base */
291 0, /* tp_dict */ 282 0, /* tp_dict */
292 0, /* tp_descr_get */ 283 0, /* tp_descr_get */
293 0, /* tp_descr_set */ 284 0, /* tp_descr_set */
294 0, /* tp_dictoffset */ 285 0, /* tp_dictoffset */
295 0, /* tp_init */ 286 0, /* tp_init */
296 0, /* tp_alloc */ 287 0, /* tp_alloc */
297 range_new, /* tp_new */ 288 range_new, /* tp_new */
298 }; 289 };
(...skipping 25 matching lines...) Show 10 above Show 10 below
324 rangeiter_len(rangeiterobject *r) 315 rangeiter_len(rangeiterobject *r)
325 { 316 {
326 return PyLong_FromLong(r->len - r->index); 317 return PyLong_FromLong(r->len - r->index);
327 } 318 }
328 319
329 typedef struct { 320 typedef struct {
330 PyObject_HEAD 321 PyObject_HEAD
331 PyObject *index; 322 PyObject *index;
332 PyObject *start; 323 PyObject *start;
333 PyObject *step; 324 PyObject *step;
334 PyObject *len; 325 PyObject *length;
335 } longrangeiterobject; 326 } longrangeiterobject;
336 327
337 static PyObject * 328 static PyObject *
338 longrangeiter_len(longrangeiterobject *r, PyObject *no_args) 329 longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
339 { 330 {
340 return PyNumber_Subtract(r->len, r->index); 331 return PyNumber_Subtract(r->length, r->index);
341 } 332 }
342 333
343 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw); 334 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw);
344 335
345 PyDoc_STRVAR(length_hint_doc, 336 PyDoc_STRVAR(length_hint_doc,
346 "Private method returning an estimate of len(list(it))."); 337 "Private method returning an estimate of len(list(it)).");
347 338
348 static PyMethodDef rangeiter_methods[] = { 339 static PyMethodDef rangeiter_methods[] = {
349 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, 340 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
350 length_hint_doc}, 341 length_hint_doc},
(...skipping 107 matching lines...) Show 10 above Show 10 below
458 length_hint_doc}, 449 length_hint_doc},
459 {NULL, NULL} /* sentinel */ 450 {NULL, NULL} /* sentinel */
460 }; 451 };
461 452
462 static void 453 static void
463 longrangeiter_dealloc(longrangeiterobject *r) 454 longrangeiter_dealloc(longrangeiterobject *r)
464 { 455 {
465 Py_XDECREF(r->index); 456 Py_XDECREF(r->index);
466 Py_XDECREF(r->start); 457 Py_XDECREF(r->start);
467 Py_XDECREF(r->step); 458 Py_XDECREF(r->step);
468 Py_XDECREF(r->len); 459 Py_XDECREF(r->length);
469 PyObject_Del(r); 460 PyObject_Del(r);
470 } 461 }
471 462
472 static PyObject * 463 static PyObject *
473 longrangeiter_next(longrangeiterobject *r) 464 longrangeiter_next(longrangeiterobject *r)
474 { 465 {
475 PyObject *one, *product, *new_index, *result; 466 PyObject *one, *product, *new_index, *result;
476 if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1) 467 if (PyObject_RichCompareBool(r->index, r->length, Py_LT) != 1)
477 return NULL; 468 return NULL;
478 469
479 one = PyLong_FromLong(1); 470 one = PyLong_FromLong(1);
480 if (!one) 471 if (!one)
481 return NULL; 472 return NULL;
482 473
483 product = PyNumber_Multiply(r->index, r->step); 474 product = PyNumber_Multiply(r->index, r->step);
484 if (!product) { 475 if (!product) {
485 Py_DECREF(one); 476 Py_DECREF(one);
486 return NULL; 477 return NULL;
(...skipping 47 matching lines...) Show 10 above Show 10 below
534 (iternextfunc)longrangeiter_next, /* tp_iternext */ 525 (iternextfunc)longrangeiter_next, /* tp_iternext */
535 longrangeiter_methods, /* tp_methods */ 526 longrangeiter_methods, /* tp_methods */
536 0, 527 0,
537 }; 528 };
538 529
539 static PyObject * 530 static PyObject *
540 range_iter(PyObject *seq) 531 range_iter(PyObject *seq)
541 { 532 {
542 rangeobject *r = (rangeobject *)seq; 533 rangeobject *r = (rangeobject *)seq;
543 longrangeiterobject *it; 534 longrangeiterobject *it;
544 PyObject *tmp, *len;
545 long lstart, lstop, lstep; 535 long lstart, lstop, lstep;
546 536
547 assert(PyRange_Check(seq)); 537 assert(PyRange_Check(seq));
548 538
549 /* If all three fields convert to long, use the int version */ 539 /* If all three fields convert to long, use the int version */
550 lstart = PyLong_AsLong(r->start); 540 lstart = PyLong_AsLong(r->start);
551 if (lstart != -1 || !PyErr_Occurred()) { 541 if (lstart != -1 || !PyErr_Occurred()) {
552 lstop = PyLong_AsLong(r->stop); 542 lstop = PyLong_AsLong(r->stop);
553 if (lstop != -1 || !PyErr_Occurred()) { 543 if (lstop != -1 || !PyErr_Occurred()) {
554 lstep = PyLong_AsLong(r->step); 544 lstep = PyLong_AsLong(r->step);
555 if (lstep != -1 || !PyErr_Occurred()) 545 if (lstep != -1 || !PyErr_Occurred())
556 return int_range_iter(lstart, lstop, lstep); 546 return int_range_iter(lstart, lstop, lstep);
557 } 547 }
558 } 548 }
559 /* Some conversion failed, so there is an error set. Clear it, 549 /* Some conversion failed, so there is an error set. Clear it,
560 and try again with a long range. */ 550 and try again with a long range. */
561 PyErr_Clear(); 551 PyErr_Clear();
562 552
563 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type); 553 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
564 if (it == NULL) 554 if (it == NULL)
565 return NULL; 555 return NULL;
566 556
567 /* Do all initialization here, so we can DECREF on failure. */ 557 /* Do all initialization here, so we can DECREF on failure. */
568 it->start = r->start; 558 it->start = r->start;
569 it->step = r->step; 559 it->step = r->step;
570 Py_INCREF(it->start); 560 Py_INCREF(it->start);
571 Py_INCREF(it->step); 561 Py_INCREF(it->step);
572 562
573 it->len = it->index = NULL; 563 Py_INCREF(r->length);
574 564 it->length = r->length;
575 /* Calculate length: (r->stop - r->start) / r->step */
576 tmp = PyNumber_Subtract(r->stop, r->start);
577 if (!tmp)
578 goto create_failure;
579 len = PyNumber_FloorDivide(tmp, r->step);
580 Py_DECREF(tmp);
581 if (!len)
582 goto create_failure;
583 it->len = len;
584 it->index = PyLong_FromLong(0); 565 it->index = PyLong_FromLong(0);
585 if (!it->index) 566 if (!it->index)
586 goto create_failure; 567 goto create_failure;
587 568
588 return (PyObject *)it; 569 return (PyObject *)it;
589 570
590 create_failure: 571 create_failure:
591 Py_DECREF(it); 572 Py_DECREF(it);
592 return NULL; 573 return NULL;
593 } 574 }
(...skipping 30 matching lines...) Show 10 above Show 10 below
624 } 605 }
625 } 606 }
626 } 607 }
627 PyErr_Clear(); 608 PyErr_Clear();
628 609
629 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type); 610 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
630 if (it == NULL) 611 if (it == NULL)
631 return NULL; 612 return NULL;
632 613
633 /* start + (len - 1) * step */ 614 /* start + (len - 1) * step */
615 Py_INCREF(range->length);
634 len = range->length; 616 len = range->length;
mvloewis 2008/05/02 20:17:20 You need to INCREF, since you are a) going to DECR
635 617
636 one = PyLong_FromLong(1); 618 one = PyLong_FromLong(1);
637 if (!one) 619 if (!one)
638 goto create_failure; 620 goto create_failure;
639 621
640 diff = PyNumber_Subtract(len, one); 622 diff = PyNumber_Subtract(len, one);
641 Py_DECREF(one); 623 Py_DECREF(one);
642 if (!diff) 624 if (!diff)
643 goto create_failure; 625 goto create_failure;
644 626
645 product = PyNumber_Multiply(len, range->step); 627 product = PyNumber_Multiply(len, range->step);
646 if (!product) 628 if (!product)
647 goto create_failure; 629 goto create_failure;
648 630
649 sum = PyNumber_Add(range->start, product); 631 sum = PyNumber_Add(range->start, product);
650 Py_DECREF(product); 632 Py_DECREF(product);
651 it->start = sum; 633 it->start = sum;
652 if (!it->start) 634 if (!it->start)
653 goto create_failure; 635 goto create_failure;
654 it->step = PyNumber_Negative(range->step); 636 it->step = PyNumber_Negative(range->step);
655 if (!it->step) { 637 if (!it->step) {
656 Py_DECREF(it->start); 638 Py_DECREF(it->start);
657 PyObject_Del(it); 639 PyObject_Del(it);
658 return NULL; 640 return NULL;
659 } 641 }
660 642
661 /* Steal reference to len. */ 643 /* Steal reference to len. */
662 it->len = len; 644 it->length = len;
663 645
664 it->index = PyLong_FromLong(0); 646 it->index = PyLong_FromLong(0);
665 if (!it->index) { 647 if (!it->index) {
666 Py_DECREF(it); 648 Py_DECREF(it);
667 return NULL; 649 return NULL;
668 } 650 }
669 651
670 return (PyObject *)it; 652 return (PyObject *)it;
671 653
672 create_failure: 654 create_failure:
673 Py_XDECREF(len); 655 Py_XDECREF(len);
674 PyObject_Del(it); 656 PyObject_Del(it);
675 return NULL; 657 return NULL;
676 } 658 }
LEFTRIGHT
« Lib/test/test_range.py ('k') | no next file » | Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Toggle Comments ('s')

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld r338