Branch data Line data Source code
# 1 : : // Copyright (c) 2011 The LevelDB Authors. All rights reserved. # 2 : : // Use of this source code is governed by a BSD-style license that can be # 3 : : // found in the LICENSE file. See the AUTHORS file for names of contributors. # 4 : : # 5 : : #ifndef STORAGE_LEVELDB_UTIL_RANDOM_H_ # 6 : : #define STORAGE_LEVELDB_UTIL_RANDOM_H_ # 7 : : # 8 : : #include <stdint.h> # 9 : : # 10 : : namespace leveldb { # 11 : : # 12 : : // A very simple random number generator. Not especially good at # 13 : : // generating truly random bits, but good enough for our needs in this # 14 : : // package. # 15 : : class Random { # 16 : : private: # 17 : : uint32_t seed_; # 18 : : # 19 : : public: # 20 : 5314 : explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { # 21 : : // Avoid bad seeds. # 22 [ - + ][ - + ]: 5314 : if (seed_ == 0 || seed_ == 2147483647L) { # 23 : 0 : seed_ = 1; # 24 : 0 : } # 25 : 5314 : } # 26 : 615895 : uint32_t Next() { # 27 : 615895 : static const uint32_t M = 2147483647L; // 2^31-1 # 28 : 615895 : static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0 # 29 : : // We are computing # 30 : : // seed_ = (seed_ * A) % M, where M = 2^31-1 # 31 : : // # 32 : : // seed_ must not be zero or M, or else all subsequent computed values # 33 : : // will be zero or M respectively. For all other values, seed_ will end # 34 : : // up cycling through every number in [1,M-1] # 35 : 615895 : uint64_t product = seed_ * A; # 36 : : # 37 : : // Compute (product % M) using the fact that ((x << 31) % M) == x. # 38 : 615895 : seed_ = static_cast<uint32_t>((product >> 31) + (product & M)); # 39 : : // The first reduction may overflow by 1 bit, so we may need to # 40 : : // repeat. mod == M is not possible; using > allows the faster # 41 : : // sign-bit-based test. # 42 [ - + ]: 615895 : if (seed_ > M) { # 43 : 0 : seed_ -= M; # 44 : 0 : } # 45 : 615895 : return seed_; # 46 : 615895 : } # 47 : : // Returns a uniformly distributed value in the range [0..n-1] # 48 : : // REQUIRES: n > 0 # 49 : 3170 : uint32_t Uniform(int n) { return Next() % n; } # 50 : : # 51 : : // Randomly returns true ~"1/n" of the time, and false otherwise. # 52 : : // REQUIRES: n > 0 # 53 : 0 : bool OneIn(int n) { return (Next() % n) == 0; } # 54 : : # 55 : : // Skewed: pick "base" uniformly from range [0,max_log] and then # 56 : : // return "base" random bits. The effect is to pick a number in the # 57 : : // range [0,2^max_log-1] with exponential bias towards smaller numbers. # 58 : 0 : uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } # 59 : : }; # 60 : : # 61 : : } // namespace leveldb # 62 : : # 63 : : #endif // STORAGE_LEVELDB_UTIL_RANDOM_H_