intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 254 insertions, 0 deletions

diff --git a/contrib/tools/python3/src/Modules/_bisectmodule.c b/contrib/tools/python3/src/Modules/_bisectmodule.c
new file mode 100644
index 00000000000..82d800d9a87
--- /dev/null
+++ b/contrib/tools/python3/src/Modules/_bisectmodule.c
@@ -0,0 +1,254 @@
+/* Bisection algorithms. Drop in replacement for bisect.py
+
+Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
+*/
+
+#define PY_SSIZE_T_CLEAN
+#include "Python.h"
+
+/*[clinic input]
+module _bisect
+[clinic start generated code]*/
+/*[clinic end generated code: output=da39a3ee5e6b4b0d input=4d56a2b2033b462b]*/
+
+#include "clinic/_bisectmodule.c.h"
+
+_Py_IDENTIFIER(insert);
+
+static inline Py_ssize_t
+internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
+{
+    PyObject *litem;
+    Py_ssize_t mid;
+    int res;
+
+    if (lo < 0) {
+        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
+        return -1;
+    }
+    if (hi == -1) {
+        hi = PySequence_Size(list);
+        if (hi < 0)
+            return -1;
+    }
+    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;
+        res = PyObject_RichCompareBool(item, litem, Py_LT);
+        Py_DECREF(litem);
+        if (res < 0)
+            return -1;
+        if (res)
+            hi = mid;
+        else
+            lo = mid + 1;
+    }
+    return lo;
+}
+
+/*[clinic input]
+_bisect.bisect_right -> Py_ssize_t
+
+    a: object
+    x: object
+    lo: Py_ssize_t = 0
+    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+
+Return the index where to insert item x in list a, assuming a is sorted.
+
+The return value i is such that all e in a[:i] have e <= x, and all e in
+a[i:] have e > x.  So if x already appears in the list, i points just
+beyond the rightmost x already there
+
+Optional args lo (default 0) and hi (default len(a)) bound the
+slice of a to be searched.
+[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)
+/*[clinic end generated code: output=419e150cf1d2a235 input=e72212b282c83375]*/
+{
+    return internal_bisect_right(a, x, lo, hi);
+}
+
+/*[clinic input]
+_bisect.insort_right
+
+    a: object
+    x: object
+    lo: Py_ssize_t = 0
+    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+
+Insert item x in list a, and keep it sorted assuming a is sorted.
+
+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.
+[clinic start generated code]*/
+
+static PyObject *
+_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
+                          Py_ssize_t lo, Py_ssize_t hi)
+/*[clinic end generated code: output=c2caa3d4cd02035a input=d1c45bfa68182669]*/
+{
+    PyObject *result;
+    Py_ssize_t index = internal_bisect_right(a, x, lo, hi);
+    if (index < 0)
+        return NULL;
+    if (PyList_CheckExact(a)) {
+        if (PyList_Insert(a, index, x) < 0)
+            return NULL;
+    }
+    else {
+        result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x);
+        if (result == NULL)
+            return NULL;
+        Py_DECREF(result);
+    }
+
+    Py_RETURN_NONE;
+}
+
+static inline Py_ssize_t
+internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
+{
+    PyObject *litem;
+    Py_ssize_t mid;
+    int res;
+
+    if (lo < 0) {
+        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
+        return -1;
+    }
+    if (hi == -1) {
+        hi = PySequence_Size(list);
+        if (hi < 0)
+            return -1;
+    }
+    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;
+        res = PyObject_RichCompareBool(litem, item, Py_LT);
+        Py_DECREF(litem);
+        if (res < 0)
+            return -1;
+        if (res)
+            lo = mid + 1;
+        else
+            hi = mid;
+    }
+    return lo;
+}
+
+
+/*[clinic input]
+_bisect.bisect_left -> Py_ssize_t
+
+    a: object
+    x: object
+    lo: Py_ssize_t = 0
+    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+
+Return the index where to insert item x in list a, assuming a is sorted.
+
+The return value i is such that all e in a[:i] have e < x, and all e in
+a[i:] have e >= x.  So if x already appears in the list, i points 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.
+[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)
+/*[clinic end generated code: output=af82168bc2856f24 input=2bd90f34afe5609f]*/
+{
+    return internal_bisect_left(a, x, lo, hi);
+}
+
+
+/*[clinic input]
+_bisect.insort_left
+
+    a: object
+    x: object
+    lo: Py_ssize_t = 0
+    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+
+Insert item x in list a, and keep it sorted assuming a is sorted.
+
+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.
+[clinic start generated code]*/
+
+static PyObject *
+_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
+                         Py_ssize_t lo, Py_ssize_t hi)
+/*[clinic end generated code: output=9e8356c0844a182b input=bc4583308bce00cc]*/
+{
+    PyObject *result;
+    Py_ssize_t index = internal_bisect_left(a, x, lo, hi);
+    if (index < 0)
+        return NULL;
+    if (PyList_CheckExact(a)) {
+        if (PyList_Insert(a, index, x) < 0)
+            return NULL;
+    } else {
+        result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x);
+        if (result == NULL)
+            return NULL;
+        Py_DECREF(result);
+    }
+
+    Py_RETURN_NONE;
+}
+
+static PyMethodDef bisect_methods[] = {
+    _BISECT_BISECT_RIGHT_METHODDEF
+    _BISECT_INSORT_RIGHT_METHODDEF
+    _BISECT_BISECT_LEFT_METHODDEF
+    _BISECT_INSORT_LEFT_METHODDEF
+    {NULL, NULL} /* sentinel */
+};
+
+PyDoc_STRVAR(module_doc,
+"Bisection algorithms.\n\
+\n\
+This module provides support for maintaining a list in sorted order without\n\
+having to sort the list after each insertion. For long lists of items with\n\
+expensive comparison operations, this can be an improvement over the more\n\
+common approach.\n");
+
+
+static struct PyModuleDef _bisectmodule = {
+    PyModuleDef_HEAD_INIT,
+    "_bisect",
+    module_doc,
+    -1,
+    bisect_methods,
+    NULL,
+    NULL,
+    NULL,
+    NULL
+};
+
+PyMODINIT_FUNC
+PyInit__bisect(void)
+{
+    return PyModule_Create(&_bisectmodule);
+}