| 2005 | } |
| 2006 | |
| 2007 | static npy_intp |
| 2008 | npy_gallop_left(const char *arr, const npy_intp size, const char *key, |
| 2009 | size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr) |
| 2010 | { |
| 2011 | npy_intp last_ofs, ofs, l, m, r; |
| 2012 | |
| 2013 | if (cmp(arr + (size - 1) * len, key, py_arr) < 0) { |
| 2014 | return size; |
| 2015 | } |
| 2016 | |
| 2017 | last_ofs = 0; |
| 2018 | ofs = 1; |
| 2019 | |
| 2020 | for (;;) { |
| 2021 | if (size <= ofs || ofs < 0) { |
| 2022 | ofs = size; |
| 2023 | break; |
| 2024 | } |
| 2025 | |
| 2026 | if (cmp(arr + (size - ofs - 1) * len, key, py_arr) < 0) { |
| 2027 | break; |
| 2028 | } |
| 2029 | else { |
| 2030 | last_ofs = ofs; |
| 2031 | ofs = (ofs << 1) + 1; |
| 2032 | } |
| 2033 | } |
| 2034 | |
| 2035 | /* now that arr[(size-ofs-1)*len] < key <= arr[(size-last_ofs-1)*len] */ |
| 2036 | l = size - ofs - 1; |
| 2037 | r = size - last_ofs - 1; |
| 2038 | |
| 2039 | while (l + 1 < r) { |
| 2040 | m = l + ((r - l) >> 1); |
| 2041 | |
| 2042 | if (cmp(arr + m * len, key, py_arr) < 0) { |
| 2043 | l = m; |
| 2044 | } |
| 2045 | else { |
| 2046 | r = m; |
| 2047 | } |
| 2048 | } |
| 2049 | |
| 2050 | /* now that arr[(r-1)*len] < key <= arr[r*len] */ |
| 2051 | return r; |
| 2052 | } |
| 2053 | |
| 2054 | static void |
| 2055 | npy_merge_left(char *p1, npy_intp l1, char *p2, npy_intp l2, char *p3, |