/Users/deen/code/yugabyte-db/src/yb/rocksdb/util/random.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | |
24 | | #ifndef YB_ROCKSDB_UTIL_RANDOM_H |
25 | | #define YB_ROCKSDB_UTIL_RANDOM_H |
26 | | |
27 | | #include <stdint.h> |
28 | | #include <random> |
29 | | |
30 | | #include "yb/util/slice.h" |
31 | | |
32 | | namespace rocksdb { |
33 | | |
34 | | // A very simple random number generator. Not especially good at |
35 | | // generating truly random bits, but good enough for our needs in this |
36 | | // package. |
37 | | class Random { |
38 | | private: |
39 | | enum : uint32_t { |
40 | | M = 2147483647L // 2^31-1 |
41 | | }; |
42 | | enum : uint64_t { |
43 | | A = 16807 // bits 14, 8, 7, 5, 2, 1, 0 |
44 | | }; |
45 | | |
46 | | uint32_t seed_; |
47 | | |
48 | 1.53M | static uint32_t GoodSeed(uint32_t s) { return (s & M) != 0 ? (s & M)1.53M : 1834 ; } |
49 | | |
50 | | public: |
51 | | // This is the largest value that can be returned from Next() |
52 | | enum : uint32_t { kMaxNext = M }; |
53 | | |
54 | 1.53M | explicit Random(uint32_t s) : seed_(GoodSeed(s)) {} |
55 | | |
56 | 548 | void Reset(uint32_t s) { seed_ = GoodSeed(s); } |
57 | | |
58 | 4.50G | uint32_t Next() { |
59 | | // We are computing |
60 | | // seed_ = (seed_ * A) % M, where M = 2^31-1 |
61 | | // |
62 | | // seed_ must not be zero or M, or else all subsequent computed values |
63 | | // will be zero or M respectively. For all other values, seed_ will end |
64 | | // up cycling through every number in [1,M-1] |
65 | 4.50G | uint64_t product = seed_ * A; |
66 | | |
67 | | // Compute (product % M) using the fact that ((x << 31) % M) == x. |
68 | 4.50G | seed_ = static_cast<uint32_t>((product >> 31) + (product & M)); |
69 | | // The first reduction may overflow by 1 bit, so we may need to |
70 | | // repeat. mod == M is not possible; using > allows the faster |
71 | | // sign-bit-based test. |
72 | 4.50G | if (seed_ > M) { |
73 | 20.1k | seed_ -= M; |
74 | 20.1k | } |
75 | 4.50G | return seed_; |
76 | 4.50G | } |
77 | | |
78 | | // Returns a uniformly distributed value in the range [0..n-1] |
79 | | // REQUIRES: n > 0 |
80 | 3.91G | uint32_t Uniform(int n) { return Next() % n; } |
81 | | |
82 | | // Randomly returns true ~"1/n" of the time, and false otherwise. |
83 | | // REQUIRES: n > 0 |
84 | 7.15M | bool OneIn(int n) { return (Next() % n) == 0; } |
85 | | |
86 | | // Skewed: pick "base" uniformly from range [0,max_log] and then |
87 | | // return "base" random bits. The effect is to pick a number in the |
88 | | // range [0,2^max_log-1] with exponential bias towards smaller numbers. |
89 | | uint32_t Skewed(int max_log) { |
90 | | return Uniform(1 << Uniform(max_log + 1)); |
91 | | } |
92 | | |
93 | | // Returns a Random instance for use by the current thread without |
94 | | // additional locking |
95 | | static Random* GetTLSInstance(); |
96 | | }; |
97 | | |
98 | | // A simple 64bit random number generator based on std::mt19937_64 |
99 | | class Random64 { |
100 | | private: |
101 | | std::mt19937_64 generator_; |
102 | | |
103 | | public: |
104 | 437k | explicit Random64(uint64_t s) : generator_(s) { } |
105 | | |
106 | | // Generates the next random number |
107 | 1.50k | uint64_t Next() { return generator_(); } |
108 | | |
109 | | // Returns a uniformly distributed value in the range [0..n-1] |
110 | | // REQUIRES: n > 0 |
111 | 437k | uint64_t Uniform(uint64_t n) { |
112 | 437k | return std::uniform_int_distribution<uint64_t>(0, n - 1)(generator_); |
113 | 437k | } |
114 | | |
115 | | // Randomly returns true ~"1/n" of the time, and false otherwise. |
116 | | // REQUIRES: n > 0 |
117 | 0 | bool OneIn(uint64_t n) { return Uniform(n) == 0; } |
118 | | |
119 | | // Skewed: pick "base" uniformly from range [0,max_log] and then |
120 | | // return "base" random bits. The effect is to pick a number in the |
121 | | // range [0,2^max_log-1] with exponential bias towards smaller numbers. |
122 | 0 | uint64_t Skewed(int max_log) { |
123 | 0 | return Uniform(1 << Uniform(max_log + 1)); |
124 | 0 | } |
125 | | }; |
126 | | |
127 | | // Store in *dst a random string of length "len" and return a Slice that |
128 | | // references the generated data. |
129 | | Slice RandomString(Random* rnd, int len, std::string* dst); |
130 | | |
131 | 6.41M | inline std::string RandomString(Random* rnd, int len) { |
132 | 6.41M | std::string r; |
133 | 6.41M | RandomString(rnd, len, &r); |
134 | 6.41M | return r; |
135 | 6.41M | } |
136 | | |
137 | | // Store in *dst a string of length "len" that will compress to |
138 | | // "N*compressed_fraction" bytes and return a Slice that references |
139 | | // the generated data. |
140 | | Slice CompressibleString(Random* rnd, double compressed_fraction, int len, std::string* dst); |
141 | | |
142 | | } // namespace rocksdb |
143 | | |
144 | | #endif // YB_ROCKSDB_UTIL_RANDOM_H |