diff options
Diffstat (limited to 'sortlib.cuh')
| -rw-r--r-- | sortlib.cuh | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/sortlib.cuh b/sortlib.cuh index ce40e0f..ca5525b 100644 --- a/sortlib.cuh +++ b/sortlib.cuh @@ -85,6 +85,49 @@ public: return last_known_point; } + __device__ __host__ const key_type *binary_search2(key_type *const start, + const key_type *end, + const key_type val) { + + // int step_limit = (int)fast_log(LENGTH); + key_type *last_known_point = start; + auto son = 0; + + for (int i = 0; i < STEP_LIMIT; i++) { + const auto next_level_start = start + (1 << (i + 1)) - 1; + + // printf("start: %ld, last: %ld\n", next_level_start - start, + // last_known_point - start); + + if (last_known_point > end) { + printf("%ld\n", last_known_point - start); + } + if (*last_known_point == val) { + return last_known_point; + } + + if (next_level_start > end) { + printf("%ld\n", next_level_start - start); + } + + // son = get_son_from_step(son, (*last_known_point > val)); + auto branch_selector = ((*last_known_point - val) >> MOVE_OFFSET); + // printf("tmp: %llu\n", tmp); + // printf("%llu %llu ", val, *last_known_point); + son = son * 2 + branch_selector; + // printf("%d\n", son); + // puts(tmp == 0 ? "1:left" : "1:right"); + // if (son < 0) son = 0; + /*printf("%d %d %d\n", (1 << (i + 1)), son, + -(int)((*last_known_point - val) >> brenchSelector));*/ + last_known_point = next_level_start + son; + if (last_known_point > end) { + printf("%p %ld\n", end, next_level_start - start); + } + } + return last_known_point; + } + /// Should be correct version __device__ __host__ double sample_cdf_custom_version(key_type *start, const key_type *end, key_type x) { |