feat(exp): Add expt_0503

Signed-off-by: KunoiSayami <[email protected]>

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) {