| 2448 | } |
| 2449 | |
| 2450 | static npy_intp |
| 2451 | npy_agallop_right(const char *arr, const npy_intp *tosort, const npy_intp size, |
| 2452 | const char *key, size_t len, PyArray_CompareFunc *cmp, |
| 2453 | PyArrayObject *py_arr) |
| 2454 | { |
| 2455 | npy_intp last_ofs, ofs, m; |
| 2456 | |
| 2457 | if (cmp(key, arr + tosort[0] * len, py_arr) < 0) { |
| 2458 | return 0; |
| 2459 | } |
| 2460 | |
| 2461 | last_ofs = 0; |
| 2462 | ofs = 1; |
| 2463 | |
| 2464 | for (;;) { |
| 2465 | if (size <= ofs || ofs < 0) { |
| 2466 | ofs = size; /* arr[ofs] is never accessed */ |
| 2467 | break; |
| 2468 | } |
| 2469 | |
| 2470 | if (cmp(key, arr + tosort[ofs] * len, py_arr) < 0) { |
| 2471 | break; |
| 2472 | } |
| 2473 | else { |
| 2474 | last_ofs = ofs; |
| 2475 | /* ofs = 1, 3, 7, 15... */ |
| 2476 | ofs = (ofs << 1) + 1; |
| 2477 | } |
| 2478 | } |
| 2479 | |
| 2480 | /* now that arr[tosort[last_ofs]*len] <= key < arr[tosort[ofs]*len] */ |
| 2481 | while (last_ofs + 1 < ofs) { |
| 2482 | m = last_ofs + ((ofs - last_ofs) >> 1); |
| 2483 | |
| 2484 | if (cmp(key, arr + tosort[m] * len, py_arr) < 0) { |
| 2485 | ofs = m; |
| 2486 | } |
| 2487 | else { |
| 2488 | last_ofs = m; |
| 2489 | } |
| 2490 | } |
| 2491 | |
| 2492 | /* now that arr[tosort[ofs-1]*len] <= key < arr[tosort[ofs]*len] */ |
| 2493 | return ofs; |
| 2494 | } |
| 2495 | |
| 2496 | static void |
| 2497 | npy_amerge_left(char *arr, npy_intp *p1, npy_intp l1, npy_intp *p2, |