ceph/src/rocksdb/util/random_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 // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include "util/random.h"
  11
  12 #include <cstring>
  13 #include <vector>
  14
  15 #include "test_util/testharness.h"
  16
  17 using ROCKSDB_NAMESPACE::Random;
  18
  19 TEST(RandomTest, Uniform) {
  20   const int average = 20;
  21   for (uint32_t seed : {0, 1, 2, 37, 4096}) {
  22     Random r(seed);
  23     for (int range : {1, 2, 8, 12, 100}) {
  24       std::vector<int> counts(range, 0);
  25
  26       for (int i = 0; i < range * average; ++i) {
  27         ++counts.at(r.Uniform(range));
  28       }
  29       int max_variance = static_cast<int>(std::sqrt(range) * 2 + 4);
  30       for (int i = 0; i < range; ++i) {
  31         EXPECT_GE(counts[i], std::max(1, average - max_variance));
  32         EXPECT_LE(counts[i], average + max_variance + 1);
  33       }
  34     }
  35   }
  36 }
  37
  38 TEST(RandomTest, OneIn) {
  39   Random r(42);
  40   for (int range : {1, 2, 8, 12, 100, 1234}) {
  41     const int average = 100;
  42     int count = 0;
  43     for (int i = 0; i < average * range; ++i) {
  44       if (r.OneIn(range)) {
  45         ++count;
  46       }
  47     }
  48     if (range == 1) {
  49       EXPECT_EQ(count, average);
  50     } else {
  51       int max_variance = static_cast<int>(std::sqrt(average) * 1.5);
  52       EXPECT_GE(count, average - max_variance);
  53       EXPECT_LE(count, average + max_variance);
  54     }
  55   }
  56 }
  57
  58 TEST(RandomTest, OneInOpt) {
  59   Random r(42);
  60   for (int range : {-12, 0, 1, 2, 8, 12, 100, 1234}) {
  61     const int average = 100;
  62     int count = 0;
  63     for (int i = 0; i < average * range; ++i) {
  64       if (r.OneInOpt(range)) {
  65         ++count;
  66       }
  67     }
  68     if (range < 1) {
  69       EXPECT_EQ(count, 0);
  70     } else if (range == 1) {
  71       EXPECT_EQ(count, average);
  72     } else {
  73       int max_variance = static_cast<int>(std::sqrt(average) * 1.5);
  74       EXPECT_GE(count, average - max_variance);
  75       EXPECT_LE(count, average + max_variance);
  76     }
  77   }
  78 }
  79
  80 TEST(RandomTest, PercentTrue) {
  81   Random r(42);
  82   for (int pct : {-12, 0, 1, 2, 10, 50, 90, 98, 99, 100, 1234}) {
  83     const int samples = 10000;
  84
  85     int count = 0;
  86     for (int i = 0; i < samples; ++i) {
  87       if (r.PercentTrue(pct)) {
  88         ++count;
  89       }
  90     }
  91     if (pct <= 0) {
  92       EXPECT_EQ(count, 0);
  93     } else if (pct >= 100) {
  94       EXPECT_EQ(count, samples);
  95     } else {
  96       int est = (count * 100 + (samples / 2)) / samples;
  97       EXPECT_EQ(est, pct);
  98     }
  99   }
 100 }
 101
 102 int main(int argc, char** argv) {
 103   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
 104   ::testing::InitGoogleTest(&argc, argv);
 105
 106   return RUN_ALL_TESTS();
 107 }