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 container_detail {
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 //This function uses binary search to discover the
98 //highest set bit of the integer
floor_log2(std::size_t x)99 inline std::size_t floor_log2 (std::size_t x)
100 {
101    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
102    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
103    BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
104 
105    std::size_t n = x;
106    std::size_t log2 = 0;
107 
108    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
109       std::size_t tmp = n >> shift;
110       if (tmp)
111          log2 += shift, n = tmp;
112    }
113 
114    return log2;
115 }
116 
117 } // namespace container_detail
118 } // namespace container
119 } // namespace boost
120 
121 #include <boost/container/detail/config_end.hpp>
122 
123 #endif
124