LEFT | RIGHT |
1 /* Range object implementation */ | 1 /* Range object implementation */ |
2 | 2 |
3 #include "Python.h" | 3 #include "Python.h" |
4 | 4 |
5 /* Support objects whose length is > PY_SSIZE_T_MAX. | 5 /* Support objects whose length is > PY_SSIZE_T_MAX. |
6 | 6 |
7 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. |
8 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 |
9 would presumably help perf. | 9 would presumably help perf. |
10 */ | 10 */ |
(...skipping 255 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
266 } | 266 } |
267 | 267 |
268 /* Pickling support */ | 268 /* Pickling support */ |
269 static PyObject * | 269 static PyObject * |
270 range_reduce(rangeobject *r, PyObject *args) | 270 range_reduce(rangeobject *r, PyObject *args) |
271 { | 271 { |
272 return Py_BuildValue("(O(OOO))", Py_TYPE(r), | 272 return Py_BuildValue("(O(OOO))", Py_TYPE(r), |
273 r->start, r->stop, r->step); | 273 r->start, r->stop, r->step); |
274 } | 274 } |
275 | 275 |
| 276 /* Assumes (PyLong_CheckExact(ob) || PyBool_Check(ob)) */ |
| 277 static int |
| 278 range_contains_long(rangeobject *r, PyObject *ob) |
| 279 { |
| 280 int cmp1, cmp2, cmp3; |
| 281 PyObject *tmp1 = NULL; |
| 282 PyObject *tmp2 = NULL; |
| 283 PyObject *zero = NULL; |
| 284 int result = -1; |
| 285 |
| 286 zero = PyLong_FromLong(0); |
| 287 if (zero == NULL) /* MemoryError in int(0) */ |
| 288 goto end; |
| 289 |
| 290 /* Check if the value can possibly be in the range. */ |
| 291 |
| 292 cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT); |
| 293 if (cmp1 == -1) |
| 294 goto end; |
| 295 if (cmp1 == 1) { /* positive steps: start <= ob < stop */ |
| 296 cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE); |
| 297 cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT); |
| 298 } |
| 299 else { /* negative steps: stop < ob <= start */ |
| 300 cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE); |
| 301 cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT); |
| 302 } |
| 303 |
| 304 if (cmp2 == -1 || cmp3 == -1) /* TypeError */ |
| 305 goto end; |
| 306 if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */ |
| 307 result = 0; |
| 308 goto end; |
| 309 } |
| 310 |
| 311 /* Check that the stride does not invalidate ob's membership. */ |
| 312 tmp1 = PyNumber_Subtract(ob, r->start); |
| 313 if (tmp1 == NULL) |
| 314 goto end; |
| 315 tmp2 = PyNumber_Remainder(tmp1, r->step); |
| 316 if (tmp2 == NULL) |
| 317 goto end; |
| 318 /* result = (int(ob) - start % step) == 0 */ |
| 319 result = PyObject_RichCompareBool(tmp2, zero, Py_EQ); |
| 320 end: |
| 321 Py_XDECREF(tmp1); |
| 322 Py_XDECREF(tmp2); |
| 323 Py_XDECREF(zero); |
| 324 return result; |
| 325 } |
| 326 |
276 static int | 327 static int |
277 range_contains(rangeobject *r, PyObject *ob) { | 328 range_contains(rangeobject *r, PyObject *ob) { |
278 if (PyLong_CheckExact(ob) || PyBool_Check(ob)) { | 329 if (PyLong_CheckExact(ob) || PyBool_Check(ob)) |
279 int cmp1, cmp2, cmp3; | 330 return range_contains_long(r, ob); |
280 PyObject *tmp1 = NULL; | 331 |
281 PyObject *tmp2 = NULL; | |
282 PyObject *zero = NULL; | |
283 int result = -1; | |
284 | |
285 zero = PyLong_FromLong(0); | |
286 if (zero == NULL) /* MemoryError in int(0) */ | |
287 goto end; | |
288 | |
289 /* Check if the value can possibly be in the range. */ | |
290 | |
291 cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT); | |
292 if (cmp1 == -1) | |
293 goto end; | |
294 if (cmp1 == 1) { /* positive steps: start <= ob < stop */ | |
295 cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE); | |
296 cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT); | |
297 } | |
298 else { /* negative steps: stop < ob <= start */ | |
299 cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE); | |
300 cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT); | |
301 } | |
302 | |
303 if (cmp2 == -1 || cmp3 == -1) /* TypeError */ | |
304 goto end; | |
305 if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */ | |
306 result = 0; | |
307 goto end; | |
308 } | |
309 | |
310 /* Check that the stride does not invalidate ob's membership. */ | |
311 tmp1 = PyNumber_Subtract(ob, r->start); | |
312 if (tmp1 == NULL) | |
313 goto end; | |
314 tmp2 = PyNumber_Remainder(tmp1, r->step); | |
315 if (tmp2 == NULL) | |
316 goto end; | |
317 /* result = (int(ob) - start % step) == 0 */ | |
318 result = PyObject_RichCompareBool(tmp2, zero, Py_EQ); | |
319 end: | |
320 Py_XDECREF(tmp1); | |
321 Py_XDECREF(tmp2); | |
322 Py_XDECREF(zero); | |
323 return result; | |
324 } | |
325 /* Fall back to iterative search. */ | |
326 return (int)_PySequence_IterSearch((PyObject*)r, ob, | 332 return (int)_PySequence_IterSearch((PyObject*)r, ob, |
327 PY_ITERSEARCH_CONTAINS); | 333 PY_ITERSEARCH_CONTAINS); |
328 } | 334 } |
329 | 335 |
330 static PyObject * | 336 static PyObject * |
331 range_count(rangeobject *r, PyObject *ob) | 337 range_count(rangeobject *r, PyObject *ob) |
332 { | 338 { |
| 339 if (PyLong_CheckExact(ob) || PyBool_Check(ob)) { |
| 340 if (range_contains_long(r, ob)) |
| 341 Py_RETURN_TRUE; |
| 342 else |
| 343 Py_RETURN_FALSE; |
| 344 } else { |
| 345 Py_ssize_t count; |
| 346 count = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_COUNT); |
| 347 if (count == -1) |
| 348 return NULL; |
| 349 return PyLong_FromSsize_t(count); |
| 350 } |
| 351 } |
| 352 |
| 353 static PyObject * |
| 354 range_index(rangeobject *r, PyObject *ob) |
| 355 { |
| 356 PyObject *idx, *tmp; |
333 int contains; | 357 int contains; |
334 | |
335 contains = range_contains(r, ob); | |
336 if (contains == -1) { | |
337 return NULL; | |
338 } | |
339 | |
340 if (contains) { | |
341 return PyLong_FromLong(1); | |
342 } | |
343 | |
344 return PyLong_FromLong(0); | |
345 } | |
346 | |
347 /* Helper function to handle negative indices. | |
348 * If n < 0, add the length of the range object. | |
349 * Always return a new reference. */ | |
350 static PyObject * | |
351 _normalize_idx(rangeobject *r, PyObject *n) | |
352 { | |
353 int cmp; | |
354 PyObject *zero, *len, *result; | |
355 | |
356 zero = PyLong_FromLong(0); | |
357 if (zero == NULL) { | |
358 return NULL; | |
359 } | |
360 | |
361 /* cmp = n < 0 */ | |
362 cmp = PyObject_RichCompareBool(n, zero, Py_LT); | |
363 Py_DECREF(zero); | |
364 if (cmp == -1) { | |
365 return NULL; | |
366 } | |
367 | |
368 if (cmp == 1) { | |
369 /* n < 0, so we add the length: */ | |
370 len = range_length_obj(r); | |
371 if (len == NULL) { | |
372 return NULL; | |
373 } | |
374 | |
375 /* result = n + len */ | |
376 result = PyNumber_Add(n, len); | |
377 Py_DECREF(len); | |
378 if (result == NULL) { | |
379 return NULL; | |
380 } | |
381 return result; | |
382 } | |
383 | |
384 /* the index is nonnegative, return it: */ | |
385 Py_INCREF(n); /* we have to return a new reference */ | |
386 return n; | |
387 } | |
388 | |
389 static PyObject * | |
390 range_index(rangeobject *r, PyObject *args) | |
391 { | |
392 PyObject *ob; | |
393 PyObject *start=NULL; | |
394 PyObject *stop=NULL; | |
395 PyObject *idx, *tmp, *zero, *len; | |
396 int contains, cmp1, cmp2; | |
397 PyObject *format_tuple, *err_string; | 358 PyObject *format_tuple, *err_string; |
398 static PyObject *err_format = NULL; | 359 static PyObject *err_format = NULL; |
399 | 360 |
400 if (!PyArg_ParseTuple(args, "O|O!O!:index", &ob, | 361 if (!PyLong_CheckExact(ob) && !PyBool_Check(ob)) { |
401 &PyLong_Type, &start, | 362 Py_ssize_t index; |
402 &PyLong_Type, &stop)) | 363 index = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_INDEX); |
403 return NULL; | 364 if (index == -1) |
404 | 365 return NULL; |
405 contains = range_contains(r, ob); | 366 return PyLong_FromSsize_t(index); |
406 if (contains == -1) { | 367 } |
407 return NULL; | 368 |
408 } | 369 contains = range_contains_long(r, ob); |
409 | 370 if (contains == -1) |
410 if (contains) { | 371 return NULL; |
411 tmp = PyNumber_Subtract(ob, r->start); | 372 |
412 if (tmp == NULL) { | 373 if (!contains) |
413 return NULL; | 374 goto value_error; |
414 } | 375 |
415 /* idx = (ob - r.start) // r.step */ | 376 tmp = PyNumber_Subtract(ob, r->start); |
416 idx = PyNumber_FloorDivide(tmp, r->step); | 377 if (tmp == NULL) |
417 Py_DECREF(tmp); | 378 return NULL; |
418 if (idx == NULL) { | 379 |
419 return NULL; | 380 /* idx = (ob - r.start) // r.step */ |
420 } | 381 idx = PyNumber_FloorDivide(tmp, r->step); |
421 | 382 Py_DECREF(tmp); |
422 /* We have the index, now check if start <= idx < stop: */ | 383 return idx; |
423 zero = PyLong_FromLong(0); | 384 |
424 if (zero == NULL) { | 385 value_error: |
425 Py_DECREF(idx); | 386 |
426 return NULL; | 387 /* object is not in the range */ |
427 } | |
428 if (start == NULL) { | |
429 start = zero; | |
430 } | |
431 | |
432 len = range_length_obj(r); | |
433 if (len == NULL) { | |
434 Py_DECREF(idx); | |
435 Py_DECREF(zero); | |
436 return NULL; | |
437 } | |
438 if (stop == NULL) { | |
439 stop = len; | |
440 } | |
441 | |
442 start = _normalize_idx(r, start); | |
443 Py_DECREF(zero); | |
444 if (start == NULL) { | |
445 Py_DECREF(idx); | |
446 Py_DECREF(len); | |
447 return NULL; | |
448 } | |
449 | |
450 stop = _normalize_idx(r, stop); | |
451 Py_DECREF(len); | |
452 if (stop == NULL) { | |
453 Py_DECREF(idx); | |
454 Py_DECREF(start); | |
455 return NULL; | |
456 } | |
457 | |
458 cmp1 = PyObject_RichCompareBool(start, idx, Py_LE); | |
459 cmp2 = PyObject_RichCompareBool(idx, stop, Py_LT); | |
460 Py_DECREF(start); | |
461 Py_DECREF(stop); | |
462 if (cmp1 == -1 || cmp2 == -1) { | |
463 Py_DECREF(idx); | |
464 return NULL; | |
465 } | |
466 | |
467 if (cmp1 == 1 && cmp2 == 1) { | |
468 /* start <= idx < stop */ | |
469 return idx; | |
470 } | |
471 else { | |
472 Py_DECREF(idx); | |
473 } | |
474 } | |
475 | |
476 /* else: object is not in the range: */ | |
477 if (err_format == NULL) { | 388 if (err_format == NULL) { |
478 err_format = PyUnicode_FromString("%r is not in range"); | 389 err_format = PyUnicode_FromString("%r is not in range"); |
479 if (err_format == NULL) | 390 if (err_format == NULL) |
480 return NULL; | 391 return NULL; |
481 } | 392 } |
482 format_tuple = PyTuple_Pack(1, ob); | 393 format_tuple = PyTuple_Pack(1, ob); |
483 if (format_tuple == NULL) | 394 if (format_tuple == NULL) |
484 return NULL; | 395 return NULL; |
485 err_string = PyUnicode_Format(err_format, format_tuple); | 396 err_string = PyUnicode_Format(err_format, format_tuple); |
486 Py_DECREF(format_tuple); | 397 Py_DECREF(format_tuple); |
(...skipping 22 matching lines...) Expand all Loading... |
509 "Returns a reverse iterator."); | 420 "Returns a reverse iterator."); |
510 | 421 |
511 PyDoc_STRVAR(count_doc, | 422 PyDoc_STRVAR(count_doc, |
512 "rangeobject.count(value) -> integer -- return number of occurrences of value"); | 423 "rangeobject.count(value) -> integer -- return number of occurrences of value"); |
513 | 424 |
514 PyDoc_STRVAR(index_doc, | 425 PyDoc_STRVAR(index_doc, |
515 "rangeobject.index(value, [start, [stop]]) -> integer -- return index of value.\
n" | 426 "rangeobject.index(value, [start, [stop]]) -> integer -- return index of value.\
n" |
516 "Raises ValueError if the value is not present."); | 427 "Raises ValueError if the value is not present."); |
517 | 428 |
518 static PyMethodDef range_methods[] = { | 429 static PyMethodDef range_methods[] = { |
519 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, | 430 {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc}, |
520 reverse_doc}, | 431 {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS}, |
521 {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS}, | 432 {"count", (PyCFunction)range_count, METH_O, count_doc}, |
522 {"count", (PyCFunction)range_count, METH_O, | 433 {"index", (PyCFunction)range_index, METH_O, index_doc}, |
523 count_doc}, | |
524 {"index", (PyCFunction)range_index, METH_VARARGS, | |
525 index_doc}, | |
526 {NULL, NULL} /* sentinel */ | 434 {NULL, NULL} /* sentinel */ |
527 }; | 435 }; |
528 | 436 |
529 PyTypeObject PyRange_Type = { | 437 PyTypeObject PyRange_Type = { |
530 PyVarObject_HEAD_INIT(&PyType_Type, 0) | 438 PyVarObject_HEAD_INIT(&PyType_Type, 0) |
531 "range", /* Name of this type */ | 439 "range", /* Name of this type */ |
532 sizeof(rangeobject), /* Basic object size */ | 440 sizeof(rangeobject), /* Basic object size */ |
533 0, /* Item size for varobject */ | 441 0, /* Item size for varobject */ |
534 (destructor)range_dealloc, /* tp_dealloc */ | 442 (destructor)range_dealloc, /* tp_dealloc */ |
535 0, /* tp_print */ | 443 0, /* tp_print */ |
(...skipping 452 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
988 it->index = PyLong_FromLong(0); | 896 it->index = PyLong_FromLong(0); |
989 if (!it->index) | 897 if (!it->index) |
990 goto create_failure; | 898 goto create_failure; |
991 | 899 |
992 return (PyObject *)it; | 900 return (PyObject *)it; |
993 | 901 |
994 create_failure: | 902 create_failure: |
995 Py_DECREF(it); | 903 Py_DECREF(it); |
996 return NULL; | 904 return NULL; |
997 } | 905 } |
LEFT | RIGHT |