| 106 | |
| 107 | template <class Tag, side_t side> |
| 108 | static int |
| 109 | argbinsearch(const char *arr, const char *key, const char *sort, char *ret, |
| 110 | npy_intp arr_len, npy_intp key_len, npy_intp arr_str, |
| 111 | npy_intp key_str, npy_intp sort_str, npy_intp ret_str, |
| 112 | PyArrayObject *) |
| 113 | { |
| 114 | using T = typename Tag::type; |
| 115 | auto cmp = side_to_cmp<Tag, side>::value; |
| 116 | npy_intp min_idx = 0; |
| 117 | npy_intp max_idx = arr_len; |
| 118 | T last_key_val; |
| 119 | |
| 120 | if (key_len == 0) { |
| 121 | return 0; |
| 122 | } |
| 123 | last_key_val = *(const T *)key; |
| 124 | |
| 125 | for (; key_len > 0; key_len--, key += key_str, ret += ret_str) { |
| 126 | const T key_val = *(const T *)key; |
| 127 | /* |
| 128 | * Updating only one of the indices based on the previous key |
| 129 | * gives the search a big boost when keys are sorted, but slightly |
| 130 | * slows down things for purely random ones. |
| 131 | */ |
| 132 | if (cmp(last_key_val, key_val)) { |
| 133 | max_idx = arr_len; |
| 134 | } |
| 135 | else { |
| 136 | min_idx = 0; |
| 137 | max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len; |
| 138 | } |
| 139 | |
| 140 | last_key_val = key_val; |
| 141 | |
| 142 | while (min_idx < max_idx) { |
| 143 | const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1); |
| 144 | const npy_intp sort_idx = *(npy_intp *)(sort + mid_idx * sort_str); |
| 145 | T mid_val; |
| 146 | |
| 147 | if (sort_idx < 0 || sort_idx >= arr_len) { |
| 148 | return -1; |
| 149 | } |
| 150 | |
| 151 | mid_val = *(const T *)(arr + sort_idx * arr_str); |
| 152 | |
| 153 | if (cmp(mid_val, key_val)) { |
| 154 | min_idx = mid_idx + 1; |
| 155 | } |
| 156 | else { |
| 157 | max_idx = mid_idx; |
| 158 | } |
| 159 | } |
| 160 | *(npy_intp *)ret = min_idx; |
| 161 | } |
| 162 | return 0; |
| 163 | } |
| 164 | |
| 165 | /* |
no outgoing calls
no test coverage detected