1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Stephen Cleary 2000.
4 // (C) Copyright Ion Gaztanaga 2007-2013.
5 //
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // See http://www.boost.org/libs/container for documentation.
11 //
12 // This file is a slightly modified file from Boost.Pool
13 //
14 //////////////////////////////////////////////////////////////////////////////
15
16 #ifndef BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP
17 #define BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP
18
19 #ifndef BOOST_CONFIG_HPP
20 # include <boost/config.hpp>
21 #endif
22
23 #if defined(BOOST_HAS_PRAGMA_ONCE)
24 # pragma once
25 #endif
26
27 #include <boost/container/detail/config_begin.hpp>
28 #include <boost/container/detail/workaround.hpp>
29
30 #include <climits>
31 #include <boost/static_assert.hpp>
32
33 namespace boost {
34 namespace container {
35 namespace dtl {
36
37 // Greatest common divisor and least common multiple
38
39 //
40 // gcd is an algorithm that calculates the greatest common divisor of two
41 // integers, using Euclid's algorithm.
42 //
43 // Pre: A > 0 && B > 0
44 // Recommended: A > B
45 template <typename Integer>
gcd(Integer A,Integer B)46 inline Integer gcd(Integer A, Integer B)
47 {
48 do
49 {
50 const Integer tmp(B);
51 B = A % B;
52 A = tmp;
53 } while (B != 0);
54
55 return A;
56 }
57
58 //
59 // lcm is an algorithm that calculates the least common multiple of two
60 // integers.
61 //
62 // Pre: A > 0 && B > 0
63 // Recommended: A > B
64 template <typename Integer>
lcm(const Integer & A,const Integer & B)65 inline Integer lcm(const Integer & A, const Integer & B)
66 {
67 Integer ret = A;
68 ret /= gcd(A, B);
69 ret *= B;
70 return ret;
71 }
72
73 template <typename Integer>
log2_ceil(const Integer & A)74 inline Integer log2_ceil(const Integer & A)
75 {
76 Integer i = 0;
77 Integer power_of_2 = 1;
78
79 while(power_of_2 < A){
80 power_of_2 <<= 1;
81 ++i;
82 }
83 return i;
84 }
85
86 template <typename Integer>
upper_power_of_2(const Integer & A)87 inline Integer upper_power_of_2(const Integer & A)
88 {
89 Integer power_of_2 = 1;
90
91 while(power_of_2 < A){
92 power_of_2 <<= 1;
93 }
94 return power_of_2;
95 }
96
97 template <typename Integer, bool Loop = true>
98 struct upper_power_of_2_loop_ct
99 {
100
101 template <Integer I, Integer P>
102 struct apply
103 {
104 static const Integer value =
105 upper_power_of_2_loop_ct<Integer, (I > P*2)>::template apply<I, P*2>::value;
106 };
107 };
108
109 template <typename Integer>
110 struct upper_power_of_2_loop_ct<Integer, false>
111 {
112 template <Integer I, Integer P>
113 struct apply
114 {
115 static const Integer value = P;
116 };
117 };
118
119 template <typename Integer, Integer I>
120 struct upper_power_of_2_ct
121 {
122 static const Integer value = upper_power_of_2_loop_ct<Integer, (I > 1)>::template apply<I, 2>::value;
123 };
124
125 //This function uses binary search to discover the
126 //highest set bit of the integer
floor_log2(std::size_t x)127 inline std::size_t floor_log2 (std::size_t x)
128 {
129 const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
130 const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
131 BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
132
133 std::size_t n = x;
134 std::size_t log2 = 0;
135
136 for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
137 std::size_t tmp = n >> shift;
138 if (tmp)
139 log2 += shift, n = tmp;
140 }
141
142 return log2;
143 }
144
145 template<std::size_t I1, std::size_t I2>
146 struct gcd_ct
147 {
148 static const std::size_t Max = I1 > I2 ? I1 : I2;
149 static const std::size_t Min = I1 < I2 ? I1 : I2;
150 static const std::size_t value = gcd_ct<Min, Max % Min>::value;
151 };
152
153 template<std::size_t I1>
154 struct gcd_ct<I1, 0>
155 {
156 static const std::size_t value = I1;
157 };
158
159 template<std::size_t I1>
160 struct gcd_ct<0, I1>
161 {
162 static const std::size_t value = I1;
163 };
164
165 template<std::size_t I1, std::size_t I2>
166 struct lcm_ct
167 {
168 static const std::size_t value = I1 * I2 / gcd_ct<I1, I2>::value;
169 };
170
171 } // namespace dtl
172 } // namespace container
173 } // namespace boost
174
175 #include <boost/container/detail/config_end.hpp>
176
177 #endif
178