ceph/src/rocksdb/util/heap_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5
   6 #include "util/heap.h"
   7
   8 #include <gtest/gtest.h>
   9
  10 #include <climits>
  11 #include <queue>
  12 #include <random>
  13 #include <utility>
  14
  15 #include "port/stack_trace.h"
  16
  17 #ifndef GFLAGS
  18 const int64_t FLAGS_iters = 100000;
  19 #else
  20 #include "util/gflags_compat.h"
  21 DEFINE_int64(iters, 100000, "number of pseudo-random operations in each test");
  22 #endif  // GFLAGS
  23
  24 /*
  25  * Compares the custom heap implementation in util/heap.h against
  26  * std::priority_queue on a pseudo-random sequence of operations.
  27  */
  28
  29 namespace ROCKSDB_NAMESPACE {
  30
  31 using HeapTestValue = uint64_t;
  32 using Params = std::tuple<size_t, HeapTestValue, int64_t>;
  33
  34 class HeapTest : public ::testing::TestWithParam<Params> {};
  35
  36 TEST_P(HeapTest, Test) {
  37   // This test performs the same pseudorandom sequence of operations on a
  38   // BinaryHeap and an std::priority_queue, comparing output.  The three
  39   // possible operations are insert, replace top and pop.
  40   //
  41   // Insert is chosen slightly more often than the others so that the size of
  42   // the heap slowly grows.  Once the size heats the MAX_HEAP_SIZE limit, we
  43   // disallow inserting until the heap becomes empty, testing the "draining"
  44   // scenario.
  45
  46   const auto MAX_HEAP_SIZE = std::get<0>(GetParam());
  47   const auto MAX_VALUE = std::get<1>(GetParam());
  48   const auto RNG_SEED = std::get<2>(GetParam());
  49
  50   BinaryHeap<HeapTestValue> heap;
  51   std::priority_queue<HeapTestValue> ref;
  52
  53   std::mt19937 rng(static_cast<unsigned int>(RNG_SEED));
  54   std::uniform_int_distribution<HeapTestValue> value_dist(0, MAX_VALUE);
  55   int ndrains = 0;
  56   bool draining = false;  // hit max size, draining until we empty the heap
  57   size_t size = 0;
  58   for (int64_t i = 0; i < FLAGS_iters; ++i) {
  59     if (size == 0) {
  60       draining = false;
  61     }
  62
  63     if (!draining && (size == 0 || std::bernoulli_distribution(0.4)(rng))) {
  64       // insert
  65       HeapTestValue val = value_dist(rng);
  66       heap.push(val);
  67       ref.push(val);
  68       ++size;
  69       if (size == MAX_HEAP_SIZE) {
  70         draining = true;
  71         ++ndrains;
  72       }
  73     } else if (std::bernoulli_distribution(0.5)(rng)) {
  74       // replace top
  75       HeapTestValue val = value_dist(rng);
  76       heap.replace_top(val);
  77       ref.pop();
  78       ref.push(val);
  79     } else {
  80       // pop
  81       assert(size > 0);
  82       heap.pop();
  83       ref.pop();
  84       --size;
  85     }
  86
  87     // After every operation, check that the public methods give the same
  88     // results
  89     assert((size == 0) == ref.empty());
  90     ASSERT_EQ(size == 0, heap.empty());
  91     if (size > 0) {
  92       ASSERT_EQ(ref.top(), heap.top());
  93     }
  94   }
  95
  96   // Probabilities should be set up to occasionally hit the max heap size and
  97   // drain it
  98   assert(ndrains > 0);
  99
 100   heap.clear();
 101   ASSERT_TRUE(heap.empty());
 102 }
 103
 104 // Basic test, MAX_VALUE = 3*MAX_HEAP_SIZE (occasional duplicates)
 105 INSTANTIATE_TEST_CASE_P(Basic, HeapTest,
 106                         ::testing::Values(Params(1000, 3000,
 107                                                  0x1b575cf05b708945)));
 108 // Mid-size heap with small values (many duplicates)
 109 INSTANTIATE_TEST_CASE_P(SmallValues, HeapTest,
 110                         ::testing::Values(Params(100, 10, 0x5ae213f7bd5dccd0)));
 111 // Small heap, large value range (no duplicates)
 112 INSTANTIATE_TEST_CASE_P(SmallHeap, HeapTest,
 113                         ::testing::Values(Params(10, ULLONG_MAX,
 114                                                  0x3e1fa8f4d01707cf)));
 115 // Two-element heap
 116 INSTANTIATE_TEST_CASE_P(TwoElementHeap, HeapTest,
 117                         ::testing::Values(Params(2, 5, 0x4b5e13ea988c6abc)));
 118 // One-element heap
 119 INSTANTIATE_TEST_CASE_P(OneElementHeap, HeapTest,
 120                         ::testing::Values(Params(1, 3, 0x176a1019ab0b612e)));
 121
 122 }  // namespace ROCKSDB_NAMESPACE
 123
 124 int main(int argc, char** argv) {
 125   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
 126   ::testing::InitGoogleTest(&argc, argv);
 127 #ifdef GFLAGS
 128   GFLAGS_NAMESPACE::ParseCommandLineFlags(&argc, &argv, true);
 129 #endif  // GFLAGS
 130   return RUN_ALL_TESTS();
 131 }