| 58 | */ |
| 59 | template <class Tag, side_t side> |
| 60 | static void |
| 61 | binsearch(const char *arr, const char *key, char *ret, npy_intp arr_len, |
| 62 | npy_intp key_len, npy_intp arr_str, npy_intp key_str, |
| 63 | npy_intp ret_str, PyArrayObject *) |
| 64 | { |
| 65 | using T = typename Tag::type; |
| 66 | auto cmp = side_to_cmp<Tag, side>::value; |
| 67 | npy_intp min_idx = 0; |
| 68 | npy_intp max_idx = arr_len; |
| 69 | T last_key_val; |
| 70 | |
| 71 | if (key_len == 0) { |
| 72 | return; |
| 73 | } |
| 74 | last_key_val = *(const T *)key; |
| 75 | |
| 76 | for (; key_len > 0; key_len--, key += key_str, ret += ret_str) { |
| 77 | const T key_val = *(const T *)key; |
| 78 | /* |
| 79 | * Updating only one of the indices based on the previous key |
| 80 | * gives the search a big boost when keys are sorted, but slightly |
| 81 | * slows down things for purely random ones. |
| 82 | */ |
| 83 | if (cmp(last_key_val, key_val)) { |
| 84 | max_idx = arr_len; |
| 85 | } |
| 86 | else { |
| 87 | min_idx = 0; |
| 88 | max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len; |
| 89 | } |
| 90 | |
| 91 | last_key_val = key_val; |
| 92 | |
| 93 | while (min_idx < max_idx) { |
| 94 | const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1); |
| 95 | const T mid_val = *(const T *)(arr + mid_idx * arr_str); |
| 96 | if (cmp(mid_val, key_val)) { |
| 97 | min_idx = mid_idx + 1; |
| 98 | } |
| 99 | else { |
| 100 | max_idx = mid_idx; |
| 101 | } |
| 102 | } |
| 103 | *(npy_intp *)ret = min_idx; |
| 104 | } |
| 105 | } |
| 106 | |
| 107 | template <class Tag, side_t side> |
| 108 | static int |
no outgoing calls
no test coverage detected