| 213 | |
| 214 | template <side_t side> |
| 215 | static int |
| 216 | npy_argbinsearch(const char *arr, const char *key, const char *sort, char *ret, |
| 217 | npy_intp arr_len, npy_intp key_len, npy_intp arr_str, |
| 218 | npy_intp key_str, npy_intp sort_str, npy_intp ret_str, |
| 219 | PyArrayObject *cmp) |
| 220 | { |
| 221 | using Cmp = typename side_to_generic_cmp<side>::type; |
| 222 | PyArray_CompareFunc *compare = PyArray_DESCR(cmp)->f->compare; |
| 223 | npy_intp min_idx = 0; |
| 224 | npy_intp max_idx = arr_len; |
| 225 | const char *last_key = key; |
| 226 | |
| 227 | for (; key_len > 0; key_len--, key += key_str, ret += ret_str) { |
| 228 | /* |
| 229 | * Updating only one of the indices based on the previous key |
| 230 | * gives the search a big boost when keys are sorted, but slightly |
| 231 | * slows down things for purely random ones. |
| 232 | */ |
| 233 | if (Cmp{}(compare(last_key, key, cmp), 0)) { |
| 234 | max_idx = arr_len; |
| 235 | } |
| 236 | else { |
| 237 | min_idx = 0; |
| 238 | max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len; |
| 239 | } |
| 240 | |
| 241 | last_key = key; |
| 242 | |
| 243 | while (min_idx < max_idx) { |
| 244 | const npy_intp mid_idx = min_idx + ((max_idx - min_idx) >> 1); |
| 245 | const npy_intp sort_idx = *(npy_intp *)(sort + mid_idx * sort_str); |
| 246 | const char *arr_ptr; |
| 247 | |
| 248 | if (sort_idx < 0 || sort_idx >= arr_len) { |
| 249 | return -1; |
| 250 | } |
| 251 | |
| 252 | arr_ptr = arr + sort_idx * arr_str; |
| 253 | |
| 254 | if (Cmp{}(compare(arr_ptr, key, cmp), 0)) { |
| 255 | min_idx = mid_idx + 1; |
| 256 | } |
| 257 | else { |
| 258 | max_idx = mid_idx; |
| 259 | } |
| 260 | } |
| 261 | *(npy_intp *)ret = min_idx; |
| 262 | } |
| 263 | return 0; |
| 264 | } |
| 265 | |
| 266 | /* |
| 267 | ***************************************************************************** |
nothing calls this directly
no test coverage detected