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)46inline 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)65inline 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)74inline 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)87inline 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)99inline 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