Debian Codegraph @

src/perfect-hashing/frozen/random.h

raw
1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * 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,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_LETITGO_RANDOM_H
24 #define FROZEN_LETITGO_RANDOM_H
25
26 #include "frozen/bits/algorithms.h"
27 #include "frozen/bits/version.h"
28
29 #include <cstdint>
30 #include <type_traits>
31
32 namespace frozen {
33 template <class UIntType, UIntType a, UIntType c, UIntType m> class linear_congruential_engine {
34 static_assert(std::is_unsigned<UIntType>::value, "UIntType must be an unsigned integral type");
35
36 public:
37 using result_type = UIntType;
38 static constexpr result_type multiplier = a;
39 static constexpr result_type increment = c;
40 static constexpr result_type modulus = m;
41 static constexpr result_type default_seed = 1u;
42
43 linear_congruential_engine() = default;
44 constexpr linear_congruential_engine(result_type s) { seed(s); }
45
46 void
47 seed(result_type s = default_seed) {
48 state_ = s;
49 }
50 constexpr result_type
51 operator()() {
52 using uint_least_t = bits::select_uint_least_t<bits::log(a) + bits::log(m) + 4>;
53 uint_least_t tmp = static_cast<uint_least_t>(multiplier) * state_ + increment;
54
55 // the static cast below may end up doing a truncation
56 if (modulus != 0) state_ = static_cast<result_type>(tmp % modulus);
57 else state_ = static_cast<result_type>(tmp);
58 return state_;
59 }
60 constexpr void
61 discard(unsigned long long n) {
62 while (n--) operator()();
63 }
64 static constexpr result_type
65 min() {
66 return increment == 0u ? 1u : 0u;
67 }
68 static constexpr result_type
69 max() {
70 return modulus - 1u;
71 }
72 friend constexpr bool
73 operator==(linear_congruential_engine const &self, linear_congruential_engine const &other) {
74 return self.state_ == other.state_;
75 }
76 friend constexpr bool
77 operator!=(linear_congruential_engine const &self, linear_congruential_engine const &other) {
78 return !(self == other);
79 }
80
81 private:
82 result_type state_ = default_seed;
83 };
84
85 using minstd_rand0 = linear_congruential_engine<std::uint_fast32_t, 16807, 0, 2147483647>;
86 using minstd_rand = linear_congruential_engine<std::uint_fast32_t, 48271, 0, 2147483647>;
87
88 // This generator is used by default in unordered frozen containers
89 using default_prg_t = minstd_rand;
90
91 } // namespace frozen
92
93 #endif