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                 :       6539 :   explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) {
#      21                 :            :     // Avoid bad seeds.
#      22 [ -  + ][ -  + ]:       6539 :     if (seed_ == 0 || seed_ == 2147483647L) {
#      23                 :          0 :       seed_ = 1;
#      24                 :          0 :     }
#      25                 :       6539 :   }
#      26                 :     635180 :   uint32_t Next() {
#      27                 :     635180 :     static const uint32_t M = 2147483647L;  // 2^31-1
#      28                 :     635180 :     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                 :     635180 :     uint64_t product = seed_ * A;
#      36                 :            : 
#      37                 :            :     // Compute (product % M) using the fact that ((x << 31) % M) == x.
#      38                 :     635180 :     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         [ -  + ]:     635180 :     if (seed_ > M) {
#      43                 :          0 :       seed_ -= M;
#      44                 :          0 :     }
#      45                 :     635180 :     return seed_;
#      46                 :     635180 :   }
#      47                 :            :   // Returns a uniformly distributed value in the range [0..n-1]
#      48                 :            :   // REQUIRES: n > 0
#      49                 :       3712 :   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_