ceph/src/include/random.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2017 SUSE LINUX GmbH
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13 */
  14
  15 #ifndef CEPH_RANDOM_H
  16 #define CEPH_RANDOM_H 1
  17
  18 #include <mutex>
  19 #include <random>
  20 #include <type_traits>
  21 #include <boost/optional.hpp>
  22
  23 // Basic random number facility (see N3551 for inspiration):
  24 namespace ceph::util {
  25
  26 inline namespace version_1_0_3 {
  27
  28 namespace detail {
  29
  30 template <typename T0, typename T1>
  31 using larger_of = typename std::conditional<
  32                     sizeof(T0) >= sizeof(T1),
  33                     T0, T1>
  34                   ::type;
  35
  36 // avoid mixing floating point and integers:
  37 template <typename NumberT0, typename NumberT1>
  38 using has_compatible_numeric_types =
  39             std::disjunction<
  40                 std::conjunction<
  41                     std::is_floating_point<NumberT0>, std::is_floating_point<NumberT1>
  42                 >,
  43                 std::conjunction<
  44                     std::is_integral<NumberT0>, std::is_integral<NumberT1>
  45                 >
  46             >;
  47
  48
  49 // Select the larger of type compatible numeric types:
  50 template <typename NumberT0, typename NumberT1>
  51 using select_number_t = std::enable_if_t<detail::has_compatible_numeric_types<NumberT0, NumberT1>::value,
  52                                          detail::larger_of<NumberT0, NumberT1>>;
  53
  54 } // namespace detail
  55
  56 namespace detail {
  57
  58 // Choose default distribution for appropriate types:
  59 template <typename NumberT,
  60           bool IsIntegral>
  61 struct select_distribution
  62 {
  63  using type = std::uniform_int_distribution<NumberT>;
  64 };
  65
  66 template <typename NumberT>
  67 struct select_distribution<NumberT, false>
  68 {
  69  using type = std::uniform_real_distribution<NumberT>;
  70 };
  71
  72 template <typename NumberT>
  73 using default_distribution = typename
  74     select_distribution<NumberT, std::is_integral<NumberT>::value>::type;
  75
  76 } // namespace detail
  77
  78 namespace detail {
  79
  80 template <typename EngineT>
  81 EngineT& engine();
  82
  83 template <typename MutexT, typename EngineT,
  84           typename SeedT = typename EngineT::result_type>
  85 void randomize_rng(const SeedT seed, MutexT& m, EngineT& e)
  86 {
  87   std::lock_guard<MutexT> lg(m);
  88   e.seed(seed);
  89 }
  90
  91 template <typename MutexT, typename EngineT>
  92 void randomize_rng(MutexT& m, EngineT& e)
  93 {
  94   std::random_device rd;
  95
  96   std::lock_guard<MutexT> lg(m);
  97   e.seed(rd());
  98 }
  99
 100 template <typename EngineT = std::default_random_engine,
 101           typename SeedT = typename EngineT::result_type>
 102 void randomize_rng(const SeedT n)
 103 {
 104   detail::engine<EngineT>().seed(n);
 105 }
 106
 107 template <typename EngineT = std::default_random_engine>
 108 void randomize_rng()
 109 {
 110   std::random_device rd;
 111   detail::engine<EngineT>().seed(rd());
 112 }
 113
 114 template <typename EngineT>
 115 EngineT& engine()
 116 {
 117   thread_local boost::optional<EngineT> rng_engine;
 118
 119   if (!rng_engine) {
 120     rng_engine.emplace(EngineT());
 121     randomize_rng<EngineT>();
 122   }
 123
 124   return *rng_engine;
 125 }
 126
 127 } // namespace detail
 128
 129 namespace detail {
 130
 131 template <typename NumberT,
 132           typename DistributionT = detail::default_distribution<NumberT>,
 133           typename EngineT>
 134 NumberT generate_random_number(const NumberT min, const NumberT max,
 135                                EngineT& e)
 136 {
 137   DistributionT d { min, max };
 138
 139   using param_type = typename DistributionT::param_type;
 140   return d(e, param_type { min, max });
 141 }
 142
 143 template <typename NumberT,
 144           typename MutexT,
 145           typename DistributionT = detail::default_distribution<NumberT>,
 146           typename EngineT>
 147 NumberT generate_random_number(const NumberT min, const NumberT max,
 148                                MutexT& m, EngineT& e)
 149 {
 150   DistributionT d { min, max };
 151
 152   using param_type = typename DistributionT::param_type;
 153
 154   std::lock_guard<MutexT> lg(m);
 155   return d(e, param_type { min, max });
 156 }
 157
 158 template <typename NumberT,
 159           typename DistributionT = detail::default_distribution<NumberT>,
 160           typename EngineT>
 161 NumberT generate_random_number(const NumberT min, const NumberT max)
 162 {
 163   return detail::generate_random_number<NumberT, DistributionT, EngineT>
 164           (min, max, detail::engine<EngineT>());
 165 }
 166
 167 template <typename MutexT,
 168           typename EngineT,
 169           typename NumberT = int,
 170           typename DistributionT = detail::default_distribution<NumberT>>
 171 NumberT generate_random_number(MutexT& m, EngineT& e)
 172 {
 173   return detail::generate_random_number<NumberT, MutexT, DistributionT, EngineT>
 174           (0, std::numeric_limits<NumberT>::max(), m, e);
 175 }
 176
 177 template <typename NumberT, typename MutexT, typename EngineT>
 178 NumberT generate_random_number(const NumberT max, MutexT& m, EngineT& e)
 179 {
 180   return generate_random_number<NumberT>(0, max, m, e);
 181 }
 182
 183 } // namespace detail
 184
 185 template <typename EngineT = std::default_random_engine>
 186 void randomize_rng()
 187 {
 188   detail::randomize_rng<EngineT>();
 189 }
 190
 191 template <typename NumberT = int,
 192           typename DistributionT = detail::default_distribution<NumberT>,
 193           typename EngineT = std::default_random_engine>
 194 NumberT generate_random_number()
 195 {
 196   return detail::generate_random_number<NumberT, DistributionT, EngineT>
 197           (0, std::numeric_limits<NumberT>::max());
 198 }
 199
 200 template <typename NumberT0, typename NumberT1,
 201           typename NumberT = detail::select_number_t<NumberT0, NumberT1>
 202          >
 203 NumberT generate_random_number(const NumberT0 min, const NumberT1 max)
 204 {
 205   return detail::generate_random_number<NumberT,
 206                                         detail::default_distribution<NumberT>,
 207                                         std::default_random_engine>
 208                                        (static_cast<NumberT>(min), static_cast<NumberT>(max));
 209 }
 210
 211 template <typename NumberT0, typename NumberT1,
 212           typename DistributionT,
 213           typename EngineT,
 214           typename NumberT = detail::select_number_t<NumberT0, NumberT1>
 215                  >
 216 NumberT generate_random_number(const NumberT min, const NumberT max,
 217                                EngineT& e)
 218 {
 219  return detail::generate_random_number<NumberT,
 220                        DistributionT,
 221                        EngineT>(static_cast<NumberT>(min), static_cast<NumberT>(max), e);
 222 }
 223
 224 template <typename NumberT>
 225 NumberT generate_random_number(const NumberT max)
 226 {
 227  return generate_random_number<NumberT>(0, max);
 228 }
 229
 230 // Function object:
 231 template <typename NumberT>
 232 class random_number_generator final
 233 {
 234   std::mutex l;
 235   std::random_device rd;
 236   std::default_random_engine e;
 237
 238   using seed_type = typename decltype(e)::result_type;
 239
 240   public:
 241   using number_type         = NumberT;
 242   using random_engine_type  = decltype(e);
 243   using random_device_type  = decltype(rd);
 244
 245   public:
 246   random_device_type& random_device() noexcept { return rd; }
 247   random_engine_type& random_engine() noexcept { return e; }
 248
 249   public:
 250   random_number_generator() {
 251     detail::randomize_rng(l, e);
 252   }
 253
 254   explicit random_number_generator(const seed_type seed) {
 255     detail::randomize_rng(seed, l, e);
 256   }
 257
 258   random_number_generator(random_number_generator&& rhs)
 259    : e(std::move(rhs.e))
 260   {}
 261
 262   public:
 263   random_number_generator(const random_number_generator&)            = delete;
 264   random_number_generator& operator=(const random_number_generator&) = delete;
 265
 266   public:
 267   NumberT operator()() {
 268     return detail::generate_random_number(l, e);
 269   }
 270
 271   NumberT operator()(const NumberT max) {
 272     return detail::generate_random_number<NumberT>(max, l, e);
 273   }
 274
 275   NumberT operator()(const NumberT min, const NumberT max) {
 276     return detail::generate_random_number<NumberT>(min, max, l, e);
 277   }
 278
 279   public:
 280   void seed(const seed_type n) {
 281     detail::randomize_rng(n, l, e);
 282   }
 283 };
 284
 285 template <typename NumberT>
 286 random_number_generator(const NumberT max) -> random_number_generator<NumberT>;
 287
 288 } // inline namespace version_*
 289
 290 } // namespace ceph::util
 291
 292 #endif