Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(20)
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: address more concerns Created 5 months, 1 week ago , Downloaded from: http://bugs.python.org/file10183/range_lean_and_mean5.patch
Right Patch Set: Created 5 months, 2 weeks ago , Downloaded from: http://bugs.python.org/file10152/range_lean_and_mean.patch
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"
5 4
6 /* Support objects whose length is > PY_SSIZE_T_MAX. 5 /* Support objects whose length is > PY_SSIZE_T_MAX.
7 6
8 This could be sped up for small PyLongs if they fit in an Py_ssize_t. 7 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 8 This only matters on Win64. Though we could use PY_LONG_LONG which
10 would presumably help perf. 9 would presumably help perf.
11 */ 10 */
12 11
13 typedef struct { 12 typedef struct {
14 PyObject_HEAD 13 PyObject_HEAD
15 PyObject *start; 14 PyObject *start;
16 PyObject *stop; 15 PyObject *stop;
17 PyObject *step; 16 PyObject *step;
18 PyObject *length; 17 PyObject *length;
mvloewis 2008/05/02 05:43:57 What is the purpose of caching the length in the r
GvR 2008/05/02 13:52:47 On 2008/05/02 05:43:57, mvloewis wrote: > What is
Benjamin 2008/05/02 16:56:18 On 2008/05/02 05:43:57, mvloewis wrote: > What is
19 } rangeobject; 18 } rangeobject;
20 19
21 /* Helper function for validating step. Always returns a new reference or 20 /* Helper function for validating step. Always returns a new reference or
22 NULL on error. 21 NULL on error.
23 */ 22 */
24 static PyObject * 23 static PyObject *
25 validate_step(PyObject *step) 24 validate_step(PyObject *step)
26 { 25 {
27 /* No step specified, use a step of 1. */ 26 /* No step specified, use a step of 1. */
28 if (!step) 27 if (!step)
(...skipping 10 matching lines...) Show
39 PyErr_SetString(PyExc_ValueError, 38 PyErr_SetString(PyExc_ValueError,
40 "range() arg 3 must not be zero"); 39 "range() arg 3 must not be zero");
41 Py_CLEAR(step); 40 Py_CLEAR(step);
42 } 41 }
43 } 42 }
44 43
45 return step; 44 return step;
46 } 45 }
47 46
48 static PyObject* range_compute_length(PyObject *start, 47 static PyObject* range_compute_length(PyObject *start,
49 PyObject *stop, PyObject *step); 48 PyObject *stop, PyObject *step);
GvR 2008/05/02 13:52:47 This line is indented one space too many.
50 49
51 /* XXX(nnorwitz): should we error check if the user passes any empty ranges? 50 /* XXX(nnorwitz): should we error check if the user passes any empty ranges?
52 range(-10) 51 range(-10)
53 range(0, -5) 52 range(0, -5)
54 range(0, 5, -1) 53 range(0, 5, -1)
55 */ 54 */
56 static PyObject * 55 static PyObject *
57 range_new(PyTypeObject *type, PyObject *args, PyObject *kw) 56 range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
58 { 57 {
59 rangeobject *obj = NULL; 58 rangeobject *obj = NULL;
(...skipping 42 matching lines...) Show 10 above Show 10 below
102 Py_XDECREF(start); 101 Py_XDECREF(start);
103 Py_XDECREF(stop); 102 Py_XDECREF(stop);
104 Py_XDECREF(step); 103 Py_XDECREF(step);
105 Py_XDECREF(length); 104 Py_XDECREF(length);
106 return NULL; 105 return NULL;
107 } 106 }
108 107
109 PyDoc_STRVAR(range_doc, 108 PyDoc_STRVAR(range_doc,
110 "range([start,] stop[, step]) -> range object\n\ 109 "range([start,] stop[, step]) -> range object\n\
111 \n\ 110 \n\
112 Return an arithmetic progression of numbers from start " 111 Returns a virtual sequence of numbers from start to stop by step.");
GvR 2008/05/02 13:52:47 I really don't want to use the word sequence here.
113 "to stop (exclusive) by step.");
114 112
115 static void 113 static void
116 range_dealloc(rangeobject *r) 114 range_dealloc(rangeobject *r)
117 { 115 {
118 Py_DECREF(r->start); 116 Py_DECREF(r->start);
119 Py_DECREF(r->stop); 117 Py_DECREF(r->stop);
120 Py_DECREF(r->step); 118 Py_DECREF(r->step);
121 Py_DECREF(r->length); 119 Py_DECREF(r->length);
122 PyObject_Del(r); 120 PyObject_Del(r);
123 } 121 }
124 122
125 /*Return number of items in range (lo, hi, step), when arguments are 123 /* Return number of items in range (lo, hi, step), when arguments are
126 * PyLong objects. step > 0 required. Return a PyLong with the length. 124 * PyInt or PyLong objects. step > 0 required. Return a value < 0 if
127 * Return NULL when there is an error.*/ 125 * & only if the true value is too large to fit in a signed long.
126 * Arguments MUST return 1 with either PyLong_Check() or
127 * PyLong_Check(). Return -1 when there is an error.
GvR 2008/05/02 13:52:47 Not your fault, but this comment still references
128 */
128 static PyObject * 129 static PyObject *
129 range_compute_length(PyObject *start, PyObject *stop, PyObject *step) 130 range_compute_length(PyObject *start, PyObject *stop, PyObject *step)
130 { 131 {
131 /* ------------------------------------------------------------- 132 /* -------------------------------------------------------------
132 Algorithm is equal to that of get_len_of_range(), but it operates 133 Algorithm is equal to that of get_len_of_range(), but it operates
133 on PyObjects (which are assumed to be PyLong or PyInt objects). 134 on PyObjects (which are assumed to be PyLong or PyInt objects).
134 ---------------------------------------------------------------*/ 135 ---------------------------------------------------------------*/
135 int cmp_result, cmp_call; 136 int cmp_result, cmp_call;
136 PyObject *lo, *hi; 137 PyObject *lo, *hi;
137 PyObject *diff = NULL; 138 PyObject *diff = NULL;
(...skipping 79 matching lines...) Show 10 above Show 10 below
217 PyErr_Clear(); 218 PyErr_Clear();
218 } 219 }
219 220
220 if (istep == 1) 221 if (istep == 1)
221 return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop); 222 return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
222 else 223 else
223 return PyUnicode_FromFormat("range(%R, %R, %R)", 224 return PyUnicode_FromFormat("range(%R, %R, %R)",
224 r->start, r->stop, r->step); 225 r->start, r->stop, r->step);
225 } 226 }
226 227
227 static PyMemberDef range_members[] = { 228 static PyObject *
228 {"start", T_OBJECT, offsetof(rangeobject, start), READONLY}, 229 range_getstart(rangeobject *obj)
229 {"stop", T_OBJECT, offsetof(rangeobject, stop), READONLY}, 230 {
230 {"step", T_OBJECT, offsetof(rangeobject, step), READONLY}, 231 return obj->start;
231 {0} 232 }
233
234 static PyObject *
235 range_getstop(rangeobject *obj)
236 {
237 return obj->stop;
238 }
239
240 static PyObject *
241 range_getstep(rangeobject *obj)
242 {
243 return obj->step;
244 }
245
246 static PyGetSetDef range_getset[] = {
247 {"start", (getter)range_getstart, NULL, "The start of the range"},
248 {"stop", (getter)range_getstop, NULL, "Where the range stops."},
249 {"step", (getter)range_getstep, NULL, "How much the range jumps."},
250 {0},
251 };
252
253 static PySequenceMethods range_as_sequence = {
254 (lenfunc)range_length, /* sq_length */
GvR 2008/05/02 13:52:47 The latest discussion on the list suggests to remo
255 0, /* sq_concat */
256 0, /* sq_repeat */
257 0, /* sq_item */
258 0, /* sq_slice */
259 0, /* sq_ass_item */
260 0, /* sq_ass_slice */
261 0, /* sq_contains */
232 }; 262 };
233 263
234 static PyObject * range_iter(PyObject *seq); 264 static PyObject * range_iter(PyObject *seq);
235 static PyObject * range_reverse(PyObject *seq); 265 static PyObject * range_reverse(PyObject *seq);
236 266
237 PyDoc_STRVAR(reverse_doc, 267 PyDoc_STRVAR(reverse_doc,
238 "Returns a reverse iterator."); 268 "Returns a reverse iterator.");
239
240 static PySequenceMethods range_as_sequence = {
241 (lenfunc)range_length, /* sq_length */
242 0, /* sq_concat */
243 0, /* sq_repeat */
244 0, /* sq_item */
245 0, /* sq_slice */
246 0, /* sq_ass_item */
247 0, /* sq_ass_slice */
248 0, /* sq_contains */
249 0, /* sq_inplace_concat */
250 0, /* sq_inplace_repeat */
251 };
252 269
253 static PyMethodDef range_methods[] = { 270 static PyMethodDef range_methods[] = {
254 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, 271 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS,
255 reverse_doc}, 272 reverse_doc},
256 {NULL, NULL} /* sentinel */ 273 {NULL, NULL} /* sentinel */
257 }; 274 };
258 275
259 PyTypeObject PyRange_Type = { 276 PyTypeObject PyRange_Type = {
260 PyVarObject_HEAD_INIT(&PyType_Type, 0) 277 PyVarObject_HEAD_INIT(&PyType_Type, 0)
261 "range", /* Name of this type */ 278 "range", /* Name of this type */
262 sizeof(rangeobject), /* Basic object size */ 279 sizeof(rangeobject), /* Basic object size */
263 0, /* Item size for varobject */ 280 0, /* Item size for varobject */
264 (destructor)range_dealloc, /* tp_dealloc */ 281 (destructor)range_dealloc, /* tp_dealloc */
265 0, /* tp_print */ 282 0, /* tp_print */
266 0, /* tp_getattr */ 283 0, /* tp_getattr */
267 0, /* tp_setattr */ 284 0, /* tp_setattr */
268 0, /* tp_compare */ 285 0, /* tp_compare */
269 (reprfunc)range_repr, /* tp_repr */ 286 (reprfunc)range_repr, /* tp_repr */
270 0, /* tp_as_number */ 287 0, /* tp_as_number */
271 &range_as_sequence, /* tp_as_sequence */ 288 &range_as_sequence, /* tp_as_sequence */
272 0, /* tp_as_mapping */ 289 0, /* tp_as_mapping */
273 0, /* tp_hash */ 290 0, /* tp_hash */
274 0, /* tp_call */ 291 0, /* tp_call */
275 0, /* tp_str */ 292 0, /* tp_str */
276 PyObject_GenericGetAttr, /* tp_getattro */ 293 PyObject_GenericGetAttr, /* tp_getattro */
277 0, /* tp_setattro */ 294 0, /* tp_setattro */
278 0, /* tp_as_buffer */ 295 0, /* tp_as_buffer */
279 Py_TPFLAGS_DEFAULT, /* tp_flags */ 296 Py_TPFLAGS_DEFAULT, /* tp_flags */
280 range_doc, /* tp_doc */ 297 range_doc, /* tp_doc */
281 0, /* tp_traverse */ 298 0, /* tp_traverse */
282 0, /* tp_clear */ 299 0, /* tp_clear */
283 0, /* tp_richcompare */ 300 0, /* tp_richcompare */
284 0, /* tp_weaklistoffset */ 301 0, /* tp_weaklistoffset */
285 range_iter, /* tp_iter */ 302 range_iter, /* tp_iter */
286 0, /* tp_iternext */ 303 0, /* tp_iternext */
287 range_methods, /* tp_methods */ 304 range_methods, /* tp_methods */
288 range_members, /* tp_members */ 305 0, /* tp_members */
289 0, /* tp_getset */ 306 range_getset, /* tp_getset */
GvR 2008/05/02 13:52:47 Please use spaces to indent the comment.
290 0, /* tp_base */ 307 0, /* tp_base */
291 0, /* tp_dict */ 308 0, /* tp_dict */
292 0, /* tp_descr_get */ 309 0, /* tp_descr_get */
293 0, /* tp_descr_set */ 310 0, /* tp_descr_set */
294 0, /* tp_dictoffset */ 311 0, /* tp_dictoffset */
295 0, /* tp_init */ 312 0, /* tp_init */
296 0, /* tp_alloc */ 313 0, /* tp_alloc */
297 range_new, /* tp_new */ 314 range_new, /* tp_new */
298 }; 315 };
299 316
(...skipping 24 matching lines...) Show 10 above Show 10 below
324 rangeiter_len(rangeiterobject *r) 341 rangeiter_len(rangeiterobject *r)
325 { 342 {
326 return PyLong_FromLong(r->len - r->index); 343 return PyLong_FromLong(r->len - r->index);
327 } 344 }
328 345
329 typedef struct { 346 typedef struct {
330 PyObject_HEAD 347 PyObject_HEAD
331 PyObject *index; 348 PyObject *index;
332 PyObject *start; 349 PyObject *start;
333 PyObject *step; 350 PyObject *step;
334 PyObject *length; 351 PyObject *len;
335 } longrangeiterobject; 352 } longrangeiterobject;
336 353
337 static PyObject * 354 static PyObject *
338 longrangeiter_len(longrangeiterobject *r, PyObject *no_args) 355 longrangeiter_len(longrangeiterobject *r, PyObject *no_args)
339 { 356 {
340 return PyNumber_Subtract(r->length, r->index); 357 return PyNumber_Subtract(r->len, r->index);
341 } 358 }
342 359
343 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw); 360 static PyObject *rangeiter_new(PyTypeObject *, PyObject *args, PyObject *kw);
344 361
345 PyDoc_STRVAR(length_hint_doc, 362 PyDoc_STRVAR(length_hint_doc,
346 "Private method returning an estimate of len(list(it))."); 363 "Private method returning an estimate of len(list(it)).");
347 364
348 static PyMethodDef rangeiter_methods[] = { 365 static PyMethodDef rangeiter_methods[] = {
349 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, 366 {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
350 length_hint_doc}, 367 length_hint_doc},
(...skipping 107 matching lines...) Show 10 above Show 10 below
458 length_hint_doc}, 475 length_hint_doc},
459 {NULL, NULL} /* sentinel */ 476 {NULL, NULL} /* sentinel */
460 }; 477 };
461 478
462 static void 479 static void
463 longrangeiter_dealloc(longrangeiterobject *r) 480 longrangeiter_dealloc(longrangeiterobject *r)
464 { 481 {
465 Py_XDECREF(r->index); 482 Py_XDECREF(r->index);
466 Py_XDECREF(r->start); 483 Py_XDECREF(r->start);
467 Py_XDECREF(r->step); 484 Py_XDECREF(r->step);
468 Py_XDECREF(r->length); 485 Py_XDECREF(r->len);
469 PyObject_Del(r); 486 PyObject_Del(r);
470 } 487 }
471 488
472 static PyObject * 489 static PyObject *
473 longrangeiter_next(longrangeiterobject *r) 490 longrangeiter_next(longrangeiterobject *r)
474 { 491 {
475 PyObject *one, *product, *new_index, *result; 492 PyObject *one, *product, *new_index, *result;
476 if (PyObject_RichCompareBool(r->index, r->length, Py_LT) != 1) 493 if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
477 return NULL; 494 return NULL;
478 495
479 one = PyLong_FromLong(1); 496 one = PyLong_FromLong(1);
480 if (!one) 497 if (!one)
481 return NULL; 498 return NULL;
482 499
483 product = PyNumber_Multiply(r->index, r->step); 500 product = PyNumber_Multiply(r->index, r->step);
484 if (!product) { 501 if (!product) {
485 Py_DECREF(one); 502 Py_DECREF(one);
486 return NULL; 503 return NULL;
(...skipping 47 matching lines...) Show 10 above Show 10 below
534 (iternextfunc)longrangeiter_next, /* tp_iternext */ 551 (iternextfunc)longrangeiter_next, /* tp_iternext */
535 longrangeiter_methods, /* tp_methods */ 552 longrangeiter_methods, /* tp_methods */
536 0, 553 0,
537 }; 554 };
538 555
539 static PyObject * 556 static PyObject *
540 range_iter(PyObject *seq) 557 range_iter(PyObject *seq)
541 { 558 {
542 rangeobject *r = (rangeobject *)seq; 559 rangeobject *r = (rangeobject *)seq;
543 longrangeiterobject *it; 560 longrangeiterobject *it;
561 PyObject *tmp, *len;
544 long lstart, lstop, lstep; 562 long lstart, lstop, lstep;
545 563
546 assert(PyRange_Check(seq)); 564 assert(PyRange_Check(seq));
547 565
548 /* If all three fields convert to long, use the int version */ 566 /* If all three fields convert to long, use the int version */
549 lstart = PyLong_AsLong(r->start); 567 lstart = PyLong_AsLong(r->start);
550 if (lstart != -1 || !PyErr_Occurred()) { 568 if (lstart != -1 || !PyErr_Occurred()) {
551 lstop = PyLong_AsLong(r->stop); 569 lstop = PyLong_AsLong(r->stop);
552 if (lstop != -1 || !PyErr_Occurred()) { 570 if (lstop != -1 || !PyErr_Occurred()) {
553 lstep = PyLong_AsLong(r->step); 571 lstep = PyLong_AsLong(r->step);
554 if (lstep != -1 || !PyErr_Occurred()) 572 if (lstep != -1 || !PyErr_Occurred())
555 return int_range_iter(lstart, lstop, lstep); 573 return int_range_iter(lstart, lstop, lstep);
556 } 574 }
557 } 575 }
558 /* Some conversion failed, so there is an error set. Clear it, 576 /* Some conversion failed, so there is an error set. Clear it,
559 and try again with a long range. */ 577 and try again with a long range. */
560 PyErr_Clear(); 578 PyErr_Clear();
561 579
562 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type); 580 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
563 if (it == NULL) 581 if (it == NULL)
564 return NULL; 582 return NULL;
565 583
566 /* Do all initialization here, so we can DECREF on failure. */ 584 /* Do all initialization here, so we can DECREF on failure. */
567 it->start = r->start; 585 it->start = r->start;
568 it->step = r->step; 586 it->step = r->step;
569 Py_INCREF(it->start); 587 Py_INCREF(it->start);
570 Py_INCREF(it->step); 588 Py_INCREF(it->step);
571 589
572 Py_INCREF(r->length); 590 it->len = it->index = NULL;
573 it->length = r->length; 591
592 /* Calculate length: (r->stop - r->start) / r->step */
593 tmp = PyNumber_Subtract(r->stop, r->start);
594 if (!tmp)
595 goto create_failure;
596 len = PyNumber_FloorDivide(tmp, r->step);
597 Py_DECREF(tmp);
598 if (!len)
599 goto create_failure;
600 it->len = len;
574 it->index = PyLong_FromLong(0); 601 it->index = PyLong_FromLong(0);
575 if (it->index == NULL) 602 if (!it->index)
576 goto create_failure; 603 goto create_failure;
577 604
578 return (PyObject *)it; 605 return (PyObject *)it;
579 606
580 create_failure: 607 create_failure:
581 Py_DECREF(it); 608 Py_DECREF(it);
582 return NULL; 609 return NULL;
583 } 610 }
584 611
585 static PyObject * 612 static PyObject *
(...skipping 28 matching lines...) Show 10 above Show 10 below
614 } 641 }
615 } 642 }
616 } 643 }
617 PyErr_Clear(); 644 PyErr_Clear();
618 645
619 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type); 646 it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
620 if (it == NULL) 647 if (it == NULL)
621 return NULL; 648 return NULL;
622 649
623 /* start + (len - 1) * step */ 650 /* start + (len - 1) * step */
624 Py_INCREF(range->length);
625 len = range->length; 651 len = range->length;
626 652
627 one = PyLong_FromLong(1); 653 one = PyLong_FromLong(1);
628 if (!one) 654 if (!one)
629 goto create_failure; 655 goto create_failure;
630 656
631 diff = PyNumber_Subtract(len, one); 657 diff = PyNumber_Subtract(len, one);
632 Py_DECREF(one); 658 Py_DECREF(one);
633 if (!diff) 659 if (!diff)
634 goto create_failure; 660 goto create_failure;
635 661
636 product = PyNumber_Multiply(len, range->step); 662 product = PyNumber_Multiply(len, range->step);
637 if (!product) 663 if (!product)
638 goto create_failure; 664 goto create_failure;
639 665
640 sum = PyNumber_Add(range->start, product); 666 sum = PyNumber_Add(range->start, product);
641 Py_DECREF(product); 667 Py_DECREF(product);
642 it->start = sum; 668 it->start = sum;
643 if (!it->start) 669 if (!it->start)
644 goto create_failure; 670 goto create_failure;
645 it->step = PyNumber_Negative(range->step); 671 it->step = PyNumber_Negative(range->step);
646 if (!it->step) { 672 if (!it->step) {
647 Py_DECREF(it->start); 673 Py_DECREF(it->start);
648 PyObject_Del(it); 674 PyObject_Del(it);
649 return NULL; 675 return NULL;
650 } 676 }
651 677
652 /* Steal reference to len. */ 678 /* Steal reference to len. */
653 it->length = len; 679 it->len = len;
654 680
655 it->index = PyLong_FromLong(0); 681 it->index = PyLong_FromLong(0);
656 if (!it->index) { 682 if (!it->index) {
657 Py_DECREF(it); 683 Py_DECREF(it);
658 return NULL; 684 return NULL;
659 } 685 }
660 686
661 return (PyObject *)it; 687 return (PyObject *)it;
662 688
663 create_failure: 689 create_failure:
664 Py_XDECREF(len); 690 Py_XDECREF(len);
665 PyObject_Del(it); 691 PyObject_Del(it);
666 return NULL; 692 return NULL;
667 } 693 }
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