2023-05-01 19:50

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

1 files changed, 43 insertions, 1 deletions

diff --git a/sortlib.cuh b/sortlib.cuh
index f9bc7d7..ce40e0f 100644
--- a/sortlib.cuh
+++ b/sortlib.cuh
@@ -116,7 +116,7 @@ public:
     // printf("tmp: %llu %lf %lu\n", *it - *it_prev, tmp, prev_real_location);
   }
 
-  // First version
+  /// First version
   __device__ __host__ key_type *
   original_binary_search(key_type *start, const key_type *end, key_type &val) {
     auto begin = start;
@@ -164,4 +164,46 @@ public:
 __global__ void testCustomCalculation(size_t length) {
   CustomSort(length, sizeof(long) * 8).testCalculation();
 }
+
+class FactorySort {
+
+public:
+  __device__ __host__ static const key_type *
+  cudaBinarySearch(key_type *start, const key_type *end, const key_type val) {
+    auto begin = start;
+    key_type *last_known_point = begin;
+    assert(begin < end);
+    while (begin <= end) {
+      auto mid = begin + (end - begin) / 2;
+      auto mid_val = *mid;
+      if (val == mid_val) {
+        return mid;
+      } else if (val > mid_val) {
+        begin = mid + 1;
+      } else {
+        end = mid - 1;
+      }
+      last_known_point = begin;
+    }
+    return last_known_point;
+  }
+
+  __device__ __host__ double static sample_cdf(key_type *begin, long length,
+                                               key_type x) {
+    // printf("%f\n", x);
+    auto end = begin + length;
+    auto it = cudaBinarySearch(begin, end, x);
+    if (it == end) {
+      return 1;
+    }
+    if (it == begin) {
+      return 0;
+    }
+    auto it_prev = it - 1;
+    return (double(it_prev - begin) +
+            (x - (double)*it_prev) / (double)(*it - *it_prev)) /
+           double(length - 1);
+  }
+};
+
 #endif // LOCKFREE_SORTLIB_CUH