bpo-4356: Add key function support to the bisect module (GH-20556)

1 files changed, 73 insertions, 29 deletions

diff --git a/Modules/clinic/_bisectmodule.c.h b/Modules/clinic/_bisectmodule.c.h
index 07fc906..304e46c 100644
--- a/Modules/clinic/_bisectmodule.c.h
+++ b/Modules/clinic/_bisectmodule.c.h
@@ -3,7 +3,7 @@ preserve
 [clinic start generated code]*/
 
 PyDoc_STRVAR(_bisect_bisect_right__doc__,
-"bisect_right($module, /, a, x, lo=0, hi=None)\n"
+"bisect_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
 "--\n"
 "\n"
 "Return the index where to insert item x in list a, assuming a is sorted.\n"
@@ -20,20 +20,21 @@ PyDoc_STRVAR(_bisect_bisect_right__doc__,
 
 static Py_ssize_t
 _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
-                          Py_ssize_t lo, Py_ssize_t hi);
+                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
 
 static PyObject *
 _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
 {
     PyObject *return_value = NULL;
-    static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+    static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
     static _PyArg_Parser _parser = {NULL, _keywords, "bisect_right", 0};
-    PyObject *argsbuf[4];
+    PyObject *argsbuf[5];
     Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
     PyObject *a;
     PyObject *x;
     Py_ssize_t lo = 0;
     Py_ssize_t hi = -1;
+    PyObject *key = Py_None;
     Py_ssize_t _return_value;
 
     args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
@@ -62,11 +63,21 @@ _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
             goto skip_optional_pos;
         }
     }
-    if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
-        goto exit;
+    if (args[3]) {
+        if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+            goto exit;
+        }
+        if (!--noptargs) {
+            goto skip_optional_pos;
+        }
     }
 skip_optional_pos:
-    _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi);
+    if (!noptargs) {
+        goto skip_optional_kwonly;
+    }
+    key = args[4];
+skip_optional_kwonly:
+    _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi, key);
     if ((_return_value == -1) && PyErr_Occurred()) {
         goto exit;
     }
@@ -77,7 +88,7 @@ exit:
 }
 
 PyDoc_STRVAR(_bisect_insort_right__doc__,
-"insort_right($module, /, a, x, lo=0, hi=None)\n"
+"insort_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
 "--\n"
 "\n"
 "Insert item x in list a, and keep it sorted assuming a is sorted.\n"
@@ -92,20 +103,21 @@ PyDoc_STRVAR(_bisect_insort_right__doc__,
 
 static PyObject *
 _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
-                          Py_ssize_t lo, Py_ssize_t hi);
+                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
 
 static PyObject *
 _bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
 {
     PyObject *return_value = NULL;
-    static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+    static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
     static _PyArg_Parser _parser = {NULL, _keywords, "insort_right", 0};
-    PyObject *argsbuf[4];
+    PyObject *argsbuf[5];
     Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
     PyObject *a;
     PyObject *x;
     Py_ssize_t lo = 0;
     Py_ssize_t hi = -1;
+    PyObject *key = Py_None;
 
     args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
     if (!args) {
@@ -133,18 +145,28 @@ _bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
             goto skip_optional_pos;
         }
     }
-    if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
-        goto exit;
+    if (args[3]) {
+        if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+            goto exit;
+        }
+        if (!--noptargs) {
+            goto skip_optional_pos;
+        }
     }
 skip_optional_pos:
-    return_value = _bisect_insort_right_impl(module, a, x, lo, hi);
+    if (!noptargs) {
+        goto skip_optional_kwonly;
+    }
+    key = args[4];
+skip_optional_kwonly:
+    return_value = _bisect_insort_right_impl(module, a, x, lo, hi, key);
 
 exit:
     return return_value;
 }
 
 PyDoc_STRVAR(_bisect_bisect_left__doc__,
-"bisect_left($module, /, a, x, lo=0, hi=None)\n"
+"bisect_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
 "--\n"
 "\n"
 "Return the index where to insert item x in list a, assuming a is sorted.\n"
@@ -161,20 +183,21 @@ PyDoc_STRVAR(_bisect_bisect_left__doc__,
 
 static Py_ssize_t
 _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
-                         Py_ssize_t lo, Py_ssize_t hi);
+                         Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
 
 static PyObject *
 _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
 {
     PyObject *return_value = NULL;
-    static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+    static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
     static _PyArg_Parser _parser = {NULL, _keywords, "bisect_left", 0};
-    PyObject *argsbuf[4];
+    PyObject *argsbuf[5];
     Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
     PyObject *a;
     PyObject *x;
     Py_ssize_t lo = 0;
     Py_ssize_t hi = -1;
+    PyObject *key = Py_None;
     Py_ssize_t _return_value;
 
     args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
@@ -203,11 +226,21 @@ _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
             goto skip_optional_pos;
         }
     }
-    if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
-        goto exit;
+    if (args[3]) {
+        if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+            goto exit;
+        }
+        if (!--noptargs) {
+            goto skip_optional_pos;
+        }
     }
 skip_optional_pos:
-    _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi);
+    if (!noptargs) {
+        goto skip_optional_kwonly;
+    }
+    key = args[4];
+skip_optional_kwonly:
+    _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi, key);
     if ((_return_value == -1) && PyErr_Occurred()) {
         goto exit;
     }
@@ -218,7 +251,7 @@ exit:
 }
 
 PyDoc_STRVAR(_bisect_insort_left__doc__,
-"insort_left($module, /, a, x, lo=0, hi=None)\n"
+"insort_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
 "--\n"
 "\n"
 "Insert item x in list a, and keep it sorted assuming a is sorted.\n"
@@ -233,20 +266,21 @@ PyDoc_STRVAR(_bisect_insort_left__doc__,
 
 static PyObject *
 _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
-                         Py_ssize_t lo, Py_ssize_t hi);
+                         Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
 
 static PyObject *
 _bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
 {
     PyObject *return_value = NULL;
-    static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+    static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
     static _PyArg_Parser _parser = {NULL, _keywords, "insort_left", 0};
-    PyObject *argsbuf[4];
+    PyObject *argsbuf[5];
     Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
     PyObject *a;
     PyObject *x;
     Py_ssize_t lo = 0;
     Py_ssize_t hi = -1;
+    PyObject *key = Py_None;
 
     args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
     if (!args) {
@@ -274,13 +308,23 @@ _bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
             goto skip_optional_pos;
         }
     }
-    if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
-        goto exit;
+    if (args[3]) {
+        if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+            goto exit;
+        }
+        if (!--noptargs) {
+            goto skip_optional_pos;
+        }
     }
 skip_optional_pos:
-    return_value = _bisect_insort_left_impl(module, a, x, lo, hi);
+    if (!noptargs) {
+        goto skip_optional_kwonly;
+    }
+    key = args[4];
+skip_optional_kwonly:
+    return_value = _bisect_insort_left_impl(module, a, x, lo, hi, key);
 
 exit:
     return return_value;
 }
-/*[clinic end generated code: output=6cf46f205659f01a input=a9049054013a1b77]*/
+/*[clinic end generated code: output=b3a5be025aa4ed7e input=a9049054013a1b77]*/