| 1960 | } |
| 1961 | |
| 1962 | static npy_intp |
| 1963 | npy_gallop_right(const char *arr, const npy_intp size, const char *key, |
| 1964 | size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr) |
| 1965 | { |
| 1966 | npy_intp last_ofs, ofs, m; |
| 1967 | |
| 1968 | if (cmp(key, arr, py_arr) < 0) { |
| 1969 | return 0; |
| 1970 | } |
| 1971 | |
| 1972 | last_ofs = 0; |
| 1973 | ofs = 1; |
| 1974 | |
| 1975 | for (;;) { |
| 1976 | if (size <= ofs || ofs < 0) { |
| 1977 | ofs = size; /* arr[ofs] is never accessed */ |
| 1978 | break; |
| 1979 | } |
| 1980 | |
| 1981 | if (cmp(key, arr + ofs * len, py_arr) < 0) { |
| 1982 | break; |
| 1983 | } |
| 1984 | else { |
| 1985 | last_ofs = ofs; |
| 1986 | /* ofs = 1, 3, 7, 15... */ |
| 1987 | ofs = (ofs << 1) + 1; |
| 1988 | } |
| 1989 | } |
| 1990 | |
| 1991 | /* now that arr[last_ofs*len] <= key < arr[ofs*len] */ |
| 1992 | while (last_ofs + 1 < ofs) { |
| 1993 | m = last_ofs + ((ofs - last_ofs) >> 1); |
| 1994 | |
| 1995 | if (cmp(key, arr + m * len, py_arr) < 0) { |
| 1996 | ofs = m; |
| 1997 | } |
| 1998 | else { |
| 1999 | last_ofs = m; |
| 2000 | } |
| 2001 | } |
| 2002 | |
| 2003 | /* now that arr[(ofs-1)*len] <= key < arr[ofs*len] */ |
| 2004 | return ofs; |
| 2005 | } |
| 2006 | |
| 2007 | static npy_intp |
| 2008 | npy_gallop_left(const char *arr, const npy_intp size, const char *key, |