LCOV - code coverage report
Current view: | top level - Modules - _bisectmodule.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 17 | 186 | 9.1 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 5 | 12 | 41.7 %
|  |  | Branches: | 3 | 104 | 2.9 %

               Branch data     Line data    Source code
           1                 :            : /* Bisection algorithms. Drop in replacement for bisect.py
           2                 :            :
           3                 :            : Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
           4                 :            : */
           5                 :            :
           6                 :            : #define PY_SSIZE_T_CLEAN
           7                 :            : #include "Python.h"
           8                 :            :
           9                 :            : /*[clinic input]
          10                 :            : module _bisect
          11                 :            : [clinic start generated code]*/
          12                 :            : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=4d56a2b2033b462b]*/
          13                 :            :
          14                 :            : #include "clinic/_bisectmodule.c.h"
          15                 :            :
          16                 :            : typedef struct {
          17                 :            :     PyObject *str_insert;
          18                 :            : } bisect_state;
          19                 :            :
          20                 :            : static inline bisect_state*
          21                 :          5 : get_bisect_state(PyObject *module)
          22                 :            : {
          23                 :          5 :     void *state = PyModule_GetState(module);
          24                 :            :     assert(state != NULL);
          25                 :          5 :     return (bisect_state *)state;
          26                 :            : }
          27                 :            :
          28                 :            : static ssizeargfunc
          29                 :          0 : get_sq_item(PyObject *s)
          30                 :            : {
          31                 :            :     // The parts of PySequence_GetItem that we only need to do once
          32                 :          0 :     PyTypeObject *tp = Py_TYPE(s);
          33                 :          0 :     PySequenceMethods *m = tp->tp_as_sequence;
          34   [ #  #  #  # ]:          0 :     if (m && m->sq_item) {
          35                 :          0 :         return m->sq_item;
          36                 :            :     }
          37                 :            :     const char *msg;
          38   [ #  #  #  # ]:          0 :     if (tp->tp_as_mapping && tp->tp_as_mapping->mp_subscript) {
          39                 :          0 :         msg = "%.200s is not a sequence";
          40                 :            :     }
          41                 :            :     else {
          42                 :          0 :         msg = "'%.200s' object does not support indexing";
          43                 :            :     }
          44                 :          0 :     PyErr_Format(PyExc_TypeError, msg, tp->tp_name);
          45                 :          0 :     return NULL;
          46                 :            : }
          47                 :            :
          48                 :            : static inline Py_ssize_t
          49                 :          0 : internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
          50                 :            :                       PyObject* key)
          51                 :            : {
          52                 :            :     PyObject *litem;
          53                 :            :     Py_ssize_t mid;
          54                 :            :     int res;
          55                 :            :
          56         [ #  # ]:          0 :     if (lo < 0) {
          57                 :          0 :         PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
          58                 :          0 :         return -1;
          59                 :            :     }
          60         [ #  # ]:          0 :     if (hi == -1) {
          61                 :          0 :         hi = PySequence_Size(list);
          62         [ #  # ]:          0 :         if (hi < 0)
          63                 :          0 :             return -1;
          64                 :            :     }
          65                 :          0 :     ssizeargfunc sq_item = get_sq_item(list);
          66         [ #  # ]:          0 :     if (sq_item == NULL) {
          67                 :          0 :         return -1;
          68                 :            :     }
          69         [ #  # ]:          0 :     if (Py_EnterRecursiveCall("in _bisect.bisect_right")) {
          70                 :          0 :         return -1;
          71                 :            :     }
          72                 :          0 :     PyTypeObject *tp = Py_TYPE(item);
          73                 :          0 :     richcmpfunc compare = tp->tp_richcompare;
          74         [ #  # ]:          0 :     while (lo < hi) {
          75                 :            :         /* The (size_t)cast ensures that the addition and subsequent division
          76                 :            :            are performed as unsigned operations, avoiding difficulties from
          77                 :            :            signed overflow.  (See issue 13496.) */
          78                 :          0 :         mid = ((size_t)lo + hi) / 2;
          79                 :            :         assert(mid >= 0);
          80                 :            :         // PySequence_GetItem, but we already checked the types.
          81                 :          0 :         litem = sq_item(list, mid);
          82                 :            :         assert((PyErr_Occurred() == NULL) ^ (litem == NULL));
          83         [ #  # ]:          0 :         if (litem == NULL) {
          84                 :          0 :             goto error;
          85                 :            :         }
          86         [ #  # ]:          0 :         if (key != Py_None) {
          87                 :          0 :             PyObject *newitem = PyObject_CallOneArg(key, litem);
          88         [ #  # ]:          0 :             if (newitem == NULL) {
          89                 :          0 :                 goto error;
          90                 :            :             }
          91                 :          0 :             Py_SETREF(litem, newitem);
          92                 :            :         }
          93                 :            :         /* if item < key(list[mid]):
          94                 :            :          *     hi = mid
          95                 :            :          * else:
          96                 :            :          *     lo = mid + 1
          97                 :            :          */
          98   [ #  #  #  # ]:          0 :         if (compare != NULL && Py_IS_TYPE(litem, tp)) {
          99                 :            :             // A fast path for comparing objects of the same type
         100                 :          0 :             PyObject *res_obj = compare(item, litem, Py_LT);
         101         [ #  # ]:          0 :             if (res_obj == Py_True) {
         102                 :          0 :                 Py_DECREF(res_obj);
         103                 :          0 :                 Py_DECREF(litem);
         104                 :          0 :                 hi = mid;
         105                 :          0 :                 continue;
         106                 :            :             }
         107         [ #  # ]:          0 :             if (res_obj == Py_False) {
         108                 :          0 :                 Py_DECREF(res_obj);
         109                 :          0 :                 Py_DECREF(litem);
         110                 :          0 :                 lo = mid + 1;
         111                 :          0 :                 continue;
         112                 :            :             }
         113         [ #  # ]:          0 :             if (res_obj == NULL) {
         114                 :          0 :                 goto error;
         115                 :            :             }
         116         [ #  # ]:          0 :             if (res_obj == Py_NotImplemented) {
         117                 :          0 :                 Py_DECREF(res_obj);
         118                 :          0 :                 compare = NULL;
         119                 :          0 :                 res = PyObject_RichCompareBool(item, litem, Py_LT);
         120                 :            :             }
         121                 :            :             else {
         122                 :          0 :                 res = PyObject_IsTrue(res_obj);
         123                 :          0 :                 Py_DECREF(res_obj);
         124                 :            :             }
         125                 :            :         }
         126                 :            :         else {
         127                 :            :             // A default path for comparing arbitrary objects
         128                 :          0 :             res = PyObject_RichCompareBool(item, litem, Py_LT);
         129                 :            :         }
         130         [ #  # ]:          0 :         if (res < 0) {
         131                 :          0 :             goto error;
         132                 :            :         }
         133                 :          0 :         Py_DECREF(litem);
         134         [ #  # ]:          0 :         if (res)
         135                 :          0 :             hi = mid;
         136                 :            :         else
         137                 :          0 :             lo = mid + 1;
         138                 :            :     }
         139                 :          0 :     Py_LeaveRecursiveCall();
         140                 :          0 :     return lo;
         141                 :          0 : error:
         142                 :          0 :     Py_LeaveRecursiveCall();
         143                 :          0 :     Py_XDECREF(litem);
         144                 :          0 :     return -1;
         145                 :            : }
         146                 :            :
         147                 :            : /*[clinic input]
         148                 :            : _bisect.bisect_right -> Py_ssize_t
         149                 :            :
         150                 :            :     a: object
         151                 :            :     x: object
         152                 :            :     lo: Py_ssize_t = 0
         153                 :            :     hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
         154                 :            :     *
         155                 :            :     key: object = None
         156                 :            :
         157                 :            : Return the index where to insert item x in list a, assuming a is sorted.
         158                 :            :
         159                 :            : The return value i is such that all e in a[:i] have e <= x, and all e in
         160                 :            : a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
         161                 :            : insert just after the rightmost x already there.
         162                 :            :
         163                 :            : Optional args lo (default 0) and hi (default len(a)) bound the
         164                 :            : slice of a to be searched.
         165                 :            : [clinic start generated code]*/
         166                 :            :
         167                 :            : static Py_ssize_t
         168                 :          0 : _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
         169                 :            :                           Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
         170                 :            : /*[clinic end generated code: output=3a4bc09cc7c8a73d input=40fcc5afa06ae593]*/
         171                 :            : {
         172                 :          0 :     return internal_bisect_right(a, x, lo, hi, key);
         173                 :            : }
         174                 :            :
         175                 :            : /*[clinic input]
         176                 :            : _bisect.insort_right
         177                 :            :
         178                 :            :     a: object
         179                 :            :     x: object
         180                 :            :     lo: Py_ssize_t = 0
         181                 :            :     hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
         182                 :            :     *
         183                 :            :     key: object = None
         184                 :            :
         185                 :            : Insert item x in list a, and keep it sorted assuming a is sorted.
         186                 :            :
         187                 :            : If x is already in a, insert it to the right of the rightmost x.
         188                 :            :
         189                 :            : Optional args lo (default 0) and hi (default len(a)) bound the
         190                 :            : slice of a to be searched.
         191                 :            : [clinic start generated code]*/
         192                 :            :
         193                 :            : static PyObject *
         194                 :          0 : _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
         195                 :            :                           Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
         196                 :            : /*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
         197                 :            : {
         198                 :            :     PyObject *result, *key_x;
         199                 :            :     Py_ssize_t index;
         200                 :            :
         201         [ #  # ]:          0 :     if (key == Py_None) {
         202                 :          0 :         index = internal_bisect_right(a, x, lo, hi, key);
         203                 :            :     } else {
         204                 :          0 :         key_x = PyObject_CallOneArg(key, x);
         205         [ #  # ]:          0 :         if (key_x == NULL) {
         206                 :          0 :             return NULL;
         207                 :            :         }
         208                 :          0 :         index = internal_bisect_right(a, key_x, lo, hi, key);
         209                 :          0 :         Py_DECREF(key_x);
         210                 :            :     }
         211         [ #  # ]:          0 :     if (index < 0)
         212                 :          0 :         return NULL;
         213         [ #  # ]:          0 :     if (PyList_CheckExact(a)) {
         214         [ #  # ]:          0 :         if (PyList_Insert(a, index, x) < 0)
         215                 :          0 :             return NULL;
         216                 :            :     }
         217                 :            :     else {
         218                 :          0 :         bisect_state *state = get_bisect_state(module);
         219                 :          0 :         result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
         220         [ #  # ]:          0 :         if (result == NULL)
         221                 :          0 :             return NULL;
         222                 :          0 :         Py_DECREF(result);
         223                 :            :     }
         224                 :            :
         225                 :          0 :     Py_RETURN_NONE;
         226                 :            : }
         227                 :            :
         228                 :            : static inline Py_ssize_t
         229                 :          0 : internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
         230                 :            :                      PyObject *key)
         231                 :            : {
         232                 :            :     PyObject *litem;
         233                 :            :     Py_ssize_t mid;
         234                 :            :     int res;
         235                 :            :
         236         [ #  # ]:          0 :     if (lo < 0) {
         237                 :          0 :         PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
         238                 :          0 :         return -1;
         239                 :            :     }
         240         [ #  # ]:          0 :     if (hi == -1) {
         241                 :          0 :         hi = PySequence_Size(list);
         242         [ #  # ]:          0 :         if (hi < 0)
         243                 :          0 :             return -1;
         244                 :            :     }
         245                 :          0 :     ssizeargfunc sq_item = get_sq_item(list);
         246         [ #  # ]:          0 :     if (sq_item == NULL) {
         247                 :          0 :         return -1;
         248                 :            :     }
         249         [ #  # ]:          0 :     if (Py_EnterRecursiveCall("in _bisect.bisect_left")) {
         250                 :          0 :         return -1;
         251                 :            :     }
         252                 :          0 :     PyTypeObject *tp = Py_TYPE(item);
         253                 :          0 :     richcmpfunc compare = tp->tp_richcompare;
         254         [ #  # ]:          0 :     while (lo < hi) {
         255                 :            :         /* The (size_t)cast ensures that the addition and subsequent division
         256                 :            :            are performed as unsigned operations, avoiding difficulties from
         257                 :            :            signed overflow.  (See issue 13496.) */
         258                 :          0 :         mid = ((size_t)lo + hi) / 2;
         259                 :            :         assert(mid >= 0);
         260                 :            :         // PySequence_GetItem, but we already checked the types.
         261                 :          0 :         litem = sq_item(list, mid);
         262                 :            :         assert((PyErr_Occurred() == NULL) ^ (litem == NULL));
         263         [ #  # ]:          0 :         if (litem == NULL) {
         264                 :          0 :             goto error;
         265                 :            :         }
         266         [ #  # ]:          0 :         if (key != Py_None) {
         267                 :          0 :             PyObject *newitem = PyObject_CallOneArg(key, litem);
         268         [ #  # ]:          0 :             if (newitem == NULL) {
         269                 :          0 :                 goto error;
         270                 :            :             }
         271                 :          0 :             Py_SETREF(litem, newitem);
         272                 :            :         }
         273                 :            :         /* if key(list[mid]) < item:
         274                 :            :          *     lo = mid + 1
         275                 :            :          * else:
         276                 :            :          *     hi = mid
         277                 :            :          */
         278   [ #  #  #  # ]:          0 :         if (compare != NULL && Py_IS_TYPE(litem, tp)) {
         279                 :            :             // A fast path for comparing objects of the same type
         280                 :          0 :             PyObject *res_obj = compare(litem, item, Py_LT);
         281         [ #  # ]:          0 :             if (res_obj == Py_True) {
         282                 :          0 :                 Py_DECREF(res_obj);
         283                 :          0 :                 Py_DECREF(litem);
         284                 :          0 :                 lo = mid + 1;
         285                 :          0 :                 continue;
         286                 :            :             }
         287         [ #  # ]:          0 :             if (res_obj == Py_False) {
         288                 :          0 :                 Py_DECREF(res_obj);
         289                 :          0 :                 Py_DECREF(litem);
         290                 :          0 :                 hi = mid;
         291                 :          0 :                 continue;
         292                 :            :             }
         293         [ #  # ]:          0 :             if (res_obj == NULL) {
         294                 :          0 :                 goto error;
         295                 :            :             }
         296         [ #  # ]:          0 :             if (res_obj == Py_NotImplemented) {
         297                 :          0 :                 Py_DECREF(res_obj);
         298                 :          0 :                 compare = NULL;
         299                 :          0 :                 res = PyObject_RichCompareBool(litem, item, Py_LT);
         300                 :            :             }
         301                 :            :             else {
         302                 :          0 :                 res = PyObject_IsTrue(res_obj);
         303                 :          0 :                 Py_DECREF(res_obj);
         304                 :            :             }
         305                 :            :         }
         306                 :            :         else {
         307                 :            :             // A default path for comparing arbitrary objects
         308                 :          0 :             res = PyObject_RichCompareBool(litem, item, Py_LT);
         309                 :            :         }
         310         [ #  # ]:          0 :         if (res < 0) {
         311                 :          0 :             goto error;
         312                 :            :         }
         313                 :          0 :         Py_DECREF(litem);
         314         [ #  # ]:          0 :         if (res)
         315                 :          0 :             lo = mid + 1;
         316                 :            :         else
         317                 :          0 :             hi = mid;
         318                 :            :     }
         319                 :          0 :     Py_LeaveRecursiveCall();
         320                 :          0 :     return lo;
         321                 :          0 : error:
         322                 :          0 :     Py_LeaveRecursiveCall();
         323                 :          0 :     Py_XDECREF(litem);
         324                 :          0 :     return -1;
         325                 :            : }
         326                 :            :
         327                 :            :
         328                 :            : /*[clinic input]
         329                 :            : _bisect.bisect_left -> Py_ssize_t
         330                 :            :
         331                 :            :     a: object
         332                 :            :     x: object
         333                 :            :     lo: Py_ssize_t = 0
         334                 :            :     hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
         335                 :            :     *
         336                 :            :     key: object = None
         337                 :            :
         338                 :            : Return the index where to insert item x in list a, assuming a is sorted.
         339                 :            :
         340                 :            : The return value i is such that all e in a[:i] have e < x, and all e in
         341                 :            : a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
         342                 :            : insert just before the leftmost x already there.
         343                 :            :
         344                 :            : Optional args lo (default 0) and hi (default len(a)) bound the
         345                 :            : slice of a to be searched.
         346                 :            : [clinic start generated code]*/
         347                 :            :
         348                 :            : static Py_ssize_t
         349                 :          0 : _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
         350                 :            :                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
         351                 :            : /*[clinic end generated code: output=70749d6e5cae9284 input=90dd35b50ceb05e3]*/
         352                 :            : {
         353                 :          0 :     return internal_bisect_left(a, x, lo, hi, key);
         354                 :            : }
         355                 :            :
         356                 :            :
         357                 :            : /*[clinic input]
         358                 :            : _bisect.insort_left
         359                 :            :
         360                 :            :     a: object
         361                 :            :     x: object
         362                 :            :     lo: Py_ssize_t = 0
         363                 :            :     hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
         364                 :            :     *
         365                 :            :     key: object = None
         366                 :            :
         367                 :            : Insert item x in list a, and keep it sorted assuming a is sorted.
         368                 :            :
         369                 :            : If x is already in a, insert it to the left of the leftmost x.
         370                 :            :
         371                 :            : Optional args lo (default 0) and hi (default len(a)) bound the
         372                 :            : slice of a to be searched.
         373                 :            : [clinic start generated code]*/
         374                 :            :
         375                 :            : static PyObject *
         376                 :          0 : _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
         377                 :            :                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
         378                 :            : /*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
         379                 :            : {
         380                 :            :     PyObject *result, *key_x;
         381                 :            :     Py_ssize_t index;
         382                 :            :
         383         [ #  # ]:          0 :     if (key == Py_None) {
         384                 :          0 :         index = internal_bisect_left(a, x, lo, hi, key);
         385                 :            :     } else {
         386                 :          0 :         key_x = PyObject_CallOneArg(key, x);
         387         [ #  # ]:          0 :         if (key_x == NULL) {
         388                 :          0 :             return NULL;
         389                 :            :         }
         390                 :          0 :         index = internal_bisect_left(a, key_x, lo, hi, key);
         391                 :          0 :         Py_DECREF(key_x);
         392                 :            :     }
         393         [ #  # ]:          0 :     if (index < 0)
         394                 :          0 :         return NULL;
         395         [ #  # ]:          0 :     if (PyList_CheckExact(a)) {
         396         [ #  # ]:          0 :         if (PyList_Insert(a, index, x) < 0)
         397                 :          0 :             return NULL;
         398                 :            :     } else {
         399                 :          0 :         bisect_state *state = get_bisect_state(module);
         400                 :          0 :         result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
         401         [ #  # ]:          0 :         if (result == NULL)
         402                 :          0 :             return NULL;
         403                 :          0 :         Py_DECREF(result);
         404                 :            :     }
         405                 :            :
         406                 :          0 :     Py_RETURN_NONE;
         407                 :            : }
         408                 :            :
         409                 :            : static PyMethodDef bisect_methods[] = {
         410                 :            :     _BISECT_BISECT_RIGHT_METHODDEF
         411                 :            :     _BISECT_INSORT_RIGHT_METHODDEF
         412                 :            :     _BISECT_BISECT_LEFT_METHODDEF
         413                 :            :     _BISECT_INSORT_LEFT_METHODDEF
         414                 :            :     {NULL, NULL} /* sentinel */
         415                 :            : };
         416                 :            :
         417                 :            : PyDoc_STRVAR(module_doc,
         418                 :            : "Bisection algorithms.\n\
         419                 :            : \n\
         420                 :            : This module provides support for maintaining a list in sorted order without\n\
         421                 :            : having to sort the list after each insertion. For long lists of items with\n\
         422                 :            : expensive comparison operations, this can be an improvement over the more\n\
         423                 :            : common approach.\n");
         424                 :            :
         425                 :            : static int
         426                 :          3 : bisect_clear(PyObject *module)
         427                 :            : {
         428                 :          3 :     bisect_state *state = get_bisect_state(module);
         429         [ +  + ]:          3 :     Py_CLEAR(state->str_insert);
         430                 :          3 :     return 0;
         431                 :            : }
         432                 :            :
         433                 :            : static void
         434                 :          2 : bisect_free(void *module)
         435                 :            : {
         436                 :          2 :     bisect_clear((PyObject *)module);
         437                 :          2 : }
         438                 :            :
         439                 :            : static int
         440                 :          2 : bisect_modexec(PyObject *m)
         441                 :            : {
         442                 :          2 :     bisect_state *state = get_bisect_state(m);
         443                 :          2 :     state->str_insert = PyUnicode_InternFromString("insert");
         444         [ -  + ]:          2 :     if (state->str_insert == NULL) {
         445                 :          0 :         return -1;
         446                 :            :     }
         447                 :          2 :     return 0;
         448                 :            : }
         449                 :            :
         450                 :            : static PyModuleDef_Slot bisect_slots[] = {
         451                 :            :     {Py_mod_exec, bisect_modexec},
         452                 :            :     {0, NULL}
         453                 :            : };
         454                 :            :
         455                 :            : static struct PyModuleDef _bisectmodule = {
         456                 :            :     PyModuleDef_HEAD_INIT,
         457                 :            :     .m_name = "_bisect",
         458                 :            :     .m_size = sizeof(bisect_state),
         459                 :            :     .m_doc = module_doc,
         460                 :            :     .m_methods = bisect_methods,
         461                 :            :     .m_slots = bisect_slots,
         462                 :            :     .m_clear = bisect_clear,
         463                 :            :     .m_free = bisect_free,
         464                 :            : };
         465                 :            :
         466                 :            : PyMODINIT_FUNC
         467                 :          2 : PyInit__bisect(void)
         468                 :            : {
         469                 :          2 :     return PyModuleDef_Init(&_bisectmodule);
         470                 :            : }

Generated by: LCOV version 1.14