]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/util/random.h
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).
6 // Copyright (c) 2011 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.
15 #include "rocksdb/rocksdb_namespace.h"
17 namespace ROCKSDB_NAMESPACE
{
19 // A very simple random number generator. Not especially good at
20 // generating truly random bits, but good enough for our needs in this
25 M
= 2147483647L // 2^31-1
28 A
= 16807 // bits 14, 8, 7, 5, 2, 1, 0
33 static uint32_t GoodSeed(uint32_t s
) { return (s
& M
) != 0 ? (s
& M
) : 1; }
36 // This is the largest value that can be returned from Next()
37 enum : uint32_t { kMaxNext
= M
};
39 explicit Random(uint32_t s
) : seed_(GoodSeed(s
)) {}
41 void Reset(uint32_t s
) { seed_
= GoodSeed(s
); }
45 // seed_ = (seed_ * A) % M, where M = 2^31-1
47 // seed_ must not be zero or M, or else all subsequent computed values
48 // will be zero or M respectively. For all other values, seed_ will end
49 // up cycling through every number in [1,M-1]
50 uint64_t product
= seed_
* A
;
52 // Compute (product % M) using the fact that ((x << 31) % M) == x.
53 seed_
= static_cast<uint32_t>((product
>> 31) + (product
& M
));
54 // The first reduction may overflow by 1 bit, so we may need to
55 // repeat. mod == M is not possible; using > allows the faster
56 // sign-bit-based test.
63 // Returns a uniformly distributed value in the range [0..n-1]
65 uint32_t Uniform(int n
) { return Next() % n
; }
67 // Randomly returns true ~"1/n" of the time, and false otherwise.
69 bool OneIn(int n
) { return Uniform(n
) == 0; }
71 // "Optional" one-in-n, where 0 or negative always returns false
72 // (may or may not consume a random value)
73 bool OneInOpt(int n
) { return n
> 0 && OneIn(n
); }
75 // Returns random bool that is true for the given percentage of
76 // calls on average. Zero or less is always false and 100 or more
77 // is always true (may or may not consume a random value)
78 bool PercentTrue(int percentage
) {
79 return static_cast<int>(Uniform(100)) < percentage
;
82 // Skewed: pick "base" uniformly from range [0,max_log] and then
83 // return "base" random bits. The effect is to pick a number in the
84 // range [0,2^max_log-1] with exponential bias towards smaller numbers.
85 uint32_t Skewed(int max_log
) {
86 return Uniform(1 << Uniform(max_log
+ 1));
89 // Returns a random string of length "len"
90 std::string
RandomString(int len
);
92 // Generates a random string of len bytes using human-readable characters
93 std::string
HumanReadableString(int len
);
95 // Returns a Random instance for use by the current thread without
97 static Random
* GetTLSInstance();
100 // A good 32-bit random number generator based on std::mt19937.
101 // This exists in part to avoid compiler variance in warning about coercing
102 // uint_fast32_t from mt19937 to uint32_t.
105 std::mt19937 generator_
;
108 explicit Random32(uint32_t s
) : generator_(s
) {}
110 // Generates the next random number
111 uint32_t Next() { return static_cast<uint32_t>(generator_()); }
113 // Returns a uniformly distributed value in the range [0..n-1]
115 uint32_t Uniform(uint32_t n
) {
116 return static_cast<uint32_t>(
117 std::uniform_int_distribution
<std::mt19937::result_type
>(
118 0, n
- 1)(generator_
));
121 // Returns an *almost* uniformly distributed value in the range [0..n-1].
122 // Much faster than Uniform().
124 uint32_t Uniformish(uint32_t n
) {
125 // fastrange (without the header)
126 return static_cast<uint32_t>((uint64_t(generator_()) * uint64_t(n
)) >> 32);
129 // Randomly returns true ~"1/n" of the time, and false otherwise.
131 bool OneIn(uint32_t n
) { return Uniform(n
) == 0; }
133 // Skewed: pick "base" uniformly from range [0,max_log] and then
134 // return "base" random bits. The effect is to pick a number in the
135 // range [0,2^max_log-1] with exponential bias towards smaller numbers.
136 uint32_t Skewed(int max_log
) {
137 return Uniform(uint32_t{1} << Uniform(max_log
+ 1));
140 // Reset the seed of the generator to the given value
141 void Seed(uint32_t new_seed
) { generator_
.seed(new_seed
); }
144 // A good 64-bit random number generator based on std::mt19937_64
147 std::mt19937_64 generator_
;
150 explicit Random64(uint64_t s
) : generator_(s
) { }
152 // Generates the next random number
153 uint64_t Next() { return generator_(); }
155 // Returns a uniformly distributed value in the range [0..n-1]
157 uint64_t Uniform(uint64_t n
) {
158 return std::uniform_int_distribution
<uint64_t>(0, n
- 1)(generator_
);
161 // Randomly returns true ~"1/n" of the time, and false otherwise.
163 bool OneIn(uint64_t n
) { return Uniform(n
) == 0; }
165 // Skewed: pick "base" uniformly from range [0,max_log] and then
166 // return "base" random bits. The effect is to pick a number in the
167 // range [0,2^max_log-1] with exponential bias towards smaller numbers.
168 uint64_t Skewed(int max_log
) {
169 return Uniform(uint64_t(1) << Uniform(max_log
+ 1));
173 // A seeded replacement for removed std::random_shuffle
174 template <class RandomIt
>
175 void RandomShuffle(RandomIt first
, RandomIt last
, uint32_t seed
) {
176 std::mt19937
rng(seed
);
177 std::shuffle(first
, last
, rng
);
180 // A replacement for removed std::random_shuffle
181 template <class RandomIt
>
182 void RandomShuffle(RandomIt first
, RandomIt last
) {
183 RandomShuffle(first
, last
, std::random_device
{}());
186 } // namespace ROCKSDB_NAMESPACE