use simulated geometric process; update check-integrity test

Signed-off-by: Yuchen Liang <yuchenl3@andrew.cmu.edu>
cmu-db · Jan 11, 2025 · a84fa16 · a84fa16
1 parent 1ee6a50
commit a84fa16
Show file tree

Hide file tree

Showing 3 changed files with 18 additions and 28 deletions.
diff --git a/src/include/primer/skiplist.h b/src/include/primer/skiplist.h
@@ -109,13 +109,6 @@ class SkipList {
   /** @brief Number of elements in the skip list. */
   size_t size_{0};
 
-  /**
-   * @brief Geometric distribution for generating random level.
-   *
-   * Note: p=0.25 is a common choice for skip lists, also analyzed in Pugh's original paper.
-   */
-  std::geometric_distribution<uint32_t> dist_{0.25};
-
   /** @brief Random number generator. */
   std::mt19937 rng_{Seed};
 

diff --git a/src/primer/skiplist.cpp b/src/primer/skiplist.cpp
@@ -109,15 +109,17 @@ SKIPLIST_TEMPLATE_ARGUMENTS void SkipList<K, Compare, MaxHeight, Seed>::Print()
 
 /**
  * @brief Generate a random height. The height should be cappped at `MaxHeight`.
- *
- * Note: consider using `std::geometric_distribution` with the random number generator provided in header.
+ * Note: we implement/simulate the geometric process to ensure platform independence.
  */
 SKIPLIST_TEMPLATE_ARGUMENTS auto SkipList<K, Compare, MaxHeight, Seed>::RandomHeight() -> size_t {
-  // Note: `std::geometric_distribution` generates a random integer
-  // in the range [0,`std::numeric_limits<uint32_t>::max()`).
-  // Increment 1 and apply `std::min` so that the result is in the
-  // range of [1,`MaxHeight`).
-  UNIMPLEMENTED("TODO(P0): Add implementation.");
+  // Branching factor (1 in 4 chance), see Pugh's paper.
+  static constexpr unsigned int branching_factor = 4;
+  // Start with the minimum height
+  size_t height = 1;
+  while (height < MaxHeight && (rng_() % branching_factor == 0)) {
+    height++;
+  }
+  return height;
 }
 
 /**

diff --git a/test/primer/skiplist_test.cpp b/test/primer/skiplist_test.cpp
@@ -81,28 +81,23 @@ TEST(SkipListTest, IntegrityCheckTest) {
   InstrumentedSkipList<int> list;
 
   // All the keys we will insert into the skip list (1 to 20).
-  std::vector<int> keys = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
+  std::vector<int> keys = {12, 16, 2, 6, 15, 8, 13, 1, 11, 14, 0, 4, 19, 10, 9, 5, 7, 3, 17, 18};
 
   // Heights of the nodes in the skip list.
   // These will not change since we fixed the seed of the random number generator.
-  std::vector<uint32_t> heights = {3, 4, 1, 1, 2, 2, 2, 6, 1, 3, 3, 9, 3, 1, 1, 1, 2, 4, 5, 3};
+  std::vector<uint32_t> heights = {2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 1, 2, 3};
 
-  // Keys to insert in a shuffled order.
-  auto shuffled_keys = keys;
-  std::shuffle(shuffled_keys.begin(), shuffled_keys.end(), std::mt19937{0});
-
-  std::vector<uint32_t> shuffled_heights(20, 0);
-  for (size_t i = 0; i < 20; ++i) {
-    shuffled_heights[shuffled_keys[i]] = heights[i];
-  }
-
-  // Insert the keys in a shuffled order.
-  for (auto key : shuffled_keys) {
+  // Insert the keys
+  for (auto key : keys) {
     list.Insert(key);
   }
 
+  // Sort the keys
+  std::sort(keys.begin(), keys.end());
+
+  list.Print();
   // Check that we construct the skip list as expected.
-  list.CheckIntegrity(keys, shuffled_heights);
+  list.CheckIntegrity(keys, heights);
 }
 
 TEST(SkipListTest, InsertContainsTest1) {