diff options
Diffstat (limited to 'contrib/tools/python3/src/Modules/_bisectmodule.c')
| -rw-r--r-- | contrib/tools/python3/src/Modules/_bisectmodule.c | 177 |
1 files changed, 157 insertions, 20 deletions
diff --git a/contrib/tools/python3/src/Modules/_bisectmodule.c b/contrib/tools/python3/src/Modules/_bisectmodule.c index 0caa92b2dc6..0773bbd1919 100644 --- a/contrib/tools/python3/src/Modules/_bisectmodule.c +++ b/contrib/tools/python3/src/Modules/_bisectmodule.c @@ -25,6 +25,26 @@ get_bisect_state(PyObject *module) return (bisect_state *)state; } +static ssizeargfunc +get_sq_item(PyObject *s) +{ + // The parts of PySequence_GetItem that we only need to do once + PyTypeObject *tp = Py_TYPE(s); + PySequenceMethods *m = tp->tp_as_sequence; + if (m && m->sq_item) { + return m->sq_item; + } + const char *msg; + if (tp->tp_as_mapping && tp->tp_as_mapping->mp_subscript) { + msg = "%.200s is not a sequence"; + } + else { + msg = "'%.200s' object does not support indexing"; + } + PyErr_Format(PyExc_TypeError, msg, tp->tp_name); + return NULL; +} + static inline Py_ssize_t internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi, PyObject* key) @@ -42,32 +62,86 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t if (hi < 0) return -1; } + ssizeargfunc sq_item = get_sq_item(list); + if (sq_item == NULL) { + return -1; + } + if (Py_EnterRecursiveCall("in _bisect.bisect_right")) { + return -1; + } + PyTypeObject *tp = Py_TYPE(item); + richcmpfunc compare = tp->tp_richcompare; while (lo < hi) { /* The (size_t)cast ensures that the addition and subsequent division are performed as unsigned operations, avoiding difficulties from signed overflow. (See issue 13496.) */ mid = ((size_t)lo + hi) / 2; - litem = PySequence_GetItem(list, mid); - if (litem == NULL) - return -1; + assert(mid >= 0); + // PySequence_GetItem, but we already checked the types. + litem = sq_item(list, mid); + assert((PyErr_Occurred() == NULL) ^ (litem == NULL)); + if (litem == NULL) { + goto error; + } if (key != Py_None) { PyObject *newitem = PyObject_CallOneArg(key, litem); if (newitem == NULL) { - Py_DECREF(litem); - return -1; + goto error; } Py_SETREF(litem, newitem); } - res = PyObject_RichCompareBool(item, litem, Py_LT); + /* if item < key(list[mid]): + * hi = mid + * else: + * lo = mid + 1 + */ + if (compare != NULL && Py_IS_TYPE(litem, tp)) { + // A fast path for comparing objects of the same type + PyObject *res_obj = compare(item, litem, Py_LT); + if (res_obj == Py_True) { + Py_DECREF(res_obj); + Py_DECREF(litem); + hi = mid; + continue; + } + if (res_obj == Py_False) { + Py_DECREF(res_obj); + Py_DECREF(litem); + lo = mid + 1; + continue; + } + if (res_obj == NULL) { + goto error; + } + if (res_obj == Py_NotImplemented) { + Py_DECREF(res_obj); + compare = NULL; + res = PyObject_RichCompareBool(item, litem, Py_LT); + } + else { + res = PyObject_IsTrue(res_obj); + Py_DECREF(res_obj); + } + } + else { + // A default path for comparing arbitrary objects + res = PyObject_RichCompareBool(item, litem, Py_LT); + } + if (res < 0) { + goto error; + } Py_DECREF(litem); - if (res < 0) - return -1; if (res) hi = mid; else lo = mid + 1; } + Py_LeaveRecursiveCall(); return lo; +error: + Py_LeaveRecursiveCall(); + Py_XDECREF(litem); + return -1; } /*[clinic input] @@ -88,12 +162,14 @@ insert just after the rightmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. + +A custom key function can be supplied to customize the sort order. [clinic start generated code]*/ static Py_ssize_t _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x, Py_ssize_t lo, Py_ssize_t hi, PyObject *key) -/*[clinic end generated code: output=3a4bc09cc7c8a73d input=40fcc5afa06ae593]*/ +/*[clinic end generated code: output=3a4bc09cc7c8a73d input=43071869772dd53a]*/ { return internal_bisect_right(a, x, lo, hi, key); } @@ -114,12 +190,14 @@ If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. + +A custom key function can be supplied to customize the sort order. [clinic start generated code]*/ static PyObject * _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x, Py_ssize_t lo, Py_ssize_t hi, PyObject *key) -/*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/ +/*[clinic end generated code: output=ac3bf26d07aedda2 input=f60777d2b6ddb239]*/ { PyObject *result, *key_x; Py_ssize_t index; @@ -168,32 +246,86 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h if (hi < 0) return -1; } + ssizeargfunc sq_item = get_sq_item(list); + if (sq_item == NULL) { + return -1; + } + if (Py_EnterRecursiveCall("in _bisect.bisect_left")) { + return -1; + } + PyTypeObject *tp = Py_TYPE(item); + richcmpfunc compare = tp->tp_richcompare; while (lo < hi) { /* The (size_t)cast ensures that the addition and subsequent division are performed as unsigned operations, avoiding difficulties from signed overflow. (See issue 13496.) */ mid = ((size_t)lo + hi) / 2; - litem = PySequence_GetItem(list, mid); - if (litem == NULL) - return -1; + assert(mid >= 0); + // PySequence_GetItem, but we already checked the types. + litem = sq_item(list, mid); + assert((PyErr_Occurred() == NULL) ^ (litem == NULL)); + if (litem == NULL) { + goto error; + } if (key != Py_None) { PyObject *newitem = PyObject_CallOneArg(key, litem); if (newitem == NULL) { - Py_DECREF(litem); - return -1; + goto error; } Py_SETREF(litem, newitem); } - res = PyObject_RichCompareBool(litem, item, Py_LT); + /* if key(list[mid]) < item: + * lo = mid + 1 + * else: + * hi = mid + */ + if (compare != NULL && Py_IS_TYPE(litem, tp)) { + // A fast path for comparing objects of the same type + PyObject *res_obj = compare(litem, item, Py_LT); + if (res_obj == Py_True) { + Py_DECREF(res_obj); + Py_DECREF(litem); + lo = mid + 1; + continue; + } + if (res_obj == Py_False) { + Py_DECREF(res_obj); + Py_DECREF(litem); + hi = mid; + continue; + } + if (res_obj == NULL) { + goto error; + } + if (res_obj == Py_NotImplemented) { + Py_DECREF(res_obj); + compare = NULL; + res = PyObject_RichCompareBool(litem, item, Py_LT); + } + else { + res = PyObject_IsTrue(res_obj); + Py_DECREF(res_obj); + } + } + else { + // A default path for comparing arbitrary objects + res = PyObject_RichCompareBool(litem, item, Py_LT); + } + if (res < 0) { + goto error; + } Py_DECREF(litem); - if (res < 0) - return -1; if (res) lo = mid + 1; else hi = mid; } + Py_LeaveRecursiveCall(); return lo; +error: + Py_LeaveRecursiveCall(); + Py_XDECREF(litem); + return -1; } @@ -215,12 +347,14 @@ insert just before the leftmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. + +A custom key function can be supplied to customize the sort order. [clinic start generated code]*/ static Py_ssize_t _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x, Py_ssize_t lo, Py_ssize_t hi, PyObject *key) -/*[clinic end generated code: output=70749d6e5cae9284 input=90dd35b50ceb05e3]*/ +/*[clinic end generated code: output=70749d6e5cae9284 input=f29c4fe7f9b797c7]*/ { return internal_bisect_left(a, x, lo, hi, key); } @@ -242,12 +376,14 @@ If x is already in a, insert it to the left of the leftmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. + +A custom key function can be supplied to customize the sort order. [clinic start generated code]*/ static PyObject * _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x, Py_ssize_t lo, Py_ssize_t hi, PyObject *key) -/*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/ +/*[clinic end generated code: output=b1d33e5e7ffff11e input=0a700a82edbd472c]*/ { PyObject *result, *key_x; Py_ssize_t index; @@ -321,6 +457,7 @@ bisect_modexec(PyObject *m) static PyModuleDef_Slot bisect_slots[] = { {Py_mod_exec, bisect_modexec}, + {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED}, {0, NULL} }; |