| 2399 | } |
| 2400 | |
| 2401 | static npy_intp |
| 2402 | npy_agallop_left(const char *arr, const npy_intp *tosort, const npy_intp size, |
| 2403 | const char *key, size_t len, PyArray_CompareFunc *cmp, |
| 2404 | PyArrayObject *py_arr) |
| 2405 | { |
| 2406 | npy_intp last_ofs, ofs, l, m, r; |
| 2407 | |
| 2408 | if (cmp(arr + tosort[size - 1] * len, key, py_arr) < 0) { |
| 2409 | return size; |
| 2410 | } |
| 2411 | |
| 2412 | last_ofs = 0; |
| 2413 | ofs = 1; |
| 2414 | |
| 2415 | for (;;) { |
| 2416 | if (size <= ofs || ofs < 0) { |
| 2417 | ofs = size; |
| 2418 | break; |
| 2419 | } |
| 2420 | |
| 2421 | if (cmp(arr + tosort[size - ofs - 1] * len, key, py_arr) < 0) { |
| 2422 | break; |
| 2423 | } |
| 2424 | else { |
| 2425 | last_ofs = ofs; |
| 2426 | ofs = (ofs << 1) + 1; |
| 2427 | } |
| 2428 | } |
| 2429 | |
| 2430 | /* now that arr[tosort[size-ofs-1]*len] < key <= |
| 2431 | * arr[tosort[size-last_ofs-1]*len] */ |
| 2432 | l = size - ofs - 1; |
| 2433 | r = size - last_ofs - 1; |
| 2434 | |
| 2435 | while (l + 1 < r) { |
| 2436 | m = l + ((r - l) >> 1); |
| 2437 | |
| 2438 | if (cmp(arr + tosort[m] * len, key, py_arr) < 0) { |
| 2439 | l = m; |
| 2440 | } |
| 2441 | else { |
| 2442 | r = m; |
| 2443 | } |
| 2444 | } |
| 2445 | |
| 2446 | /* now that arr[tosort[r-1]*len] < key <= arr[tosort[r]*len] */ |
| 2447 | return r; |
| 2448 | } |
| 2449 | |
| 2450 | static npy_intp |
| 2451 | npy_agallop_right(const char *arr, const npy_intp *tosort, const npy_intp size, |