1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Stephen Cleary 2000. 4 // (C) Copyright Ion Gaztanaga 2007-2012. 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/interprocess for documentation. 11 // 12 // This file is a slightly modified file from Boost.Pool 13 // 14 ////////////////////////////////////////////////////////////////////////////// 15 16 #ifndef BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP 17 #define BOOST_INTERPROCESS_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 <climits> 28 #include <boost/static_assert.hpp> 29 30 namespace boost { 31 namespace interprocess { 32 namespace ipcdetail { 33 34 // Greatest common divisor and least common multiple 35 36 // 37 // gcd is an algorithm that calculates the greatest common divisor of two 38 // integers, using Euclid's algorithm. 39 // 40 // Pre: A > 0 && B > 0 41 // Recommended: A > B 42 template <typename Integer> gcd(Integer A,Integer B)43inline Integer gcd(Integer A, Integer B) 44 { 45 do 46 { 47 const Integer tmp(B); 48 B = A % B; 49 A = tmp; 50 } while (B != 0); 51 52 return A; 53 } 54 55 // 56 // lcm is an algorithm that calculates the least common multiple of two 57 // integers. 58 // 59 // Pre: A > 0 && B > 0 60 // Recommended: A > B 61 template <typename Integer> lcm(const Integer & A,const Integer & B)62inline Integer lcm(const Integer & A, const Integer & B) 63 { 64 Integer ret = A; 65 ret /= gcd(A, B); 66 ret *= B; 67 return ret; 68 } 69 70 template <typename Integer> log2_ceil(const Integer & A)71inline Integer log2_ceil(const Integer & A) 72 { 73 Integer i = 0; 74 Integer power_of_2 = 1; 75 76 while(power_of_2 < A){ 77 power_of_2 <<= 1; 78 ++i; 79 } 80 return i; 81 } 82 83 template <typename Integer> upper_power_of_2(const Integer & A)84inline Integer upper_power_of_2(const Integer & A) 85 { 86 Integer power_of_2 = 1; 87 88 while(power_of_2 < A){ 89 power_of_2 <<= 1; 90 } 91 return power_of_2; 92 } 93 94 //This function uses binary search to discover the 95 //highest set bit of the integer floor_log2(std::size_t x)96inline std::size_t floor_log2 (std::size_t x) 97 { 98 const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT; 99 const bool Size_t_Bits_Power_2= !(Bits & (Bits-1)); 100 BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true)); 101 102 std::size_t n = x; 103 std::size_t log2 = 0; 104 105 for(std::size_t shift = Bits >> 1; shift; shift >>= 1){ 106 std::size_t tmp = n >> shift; 107 if (tmp) 108 log2 += shift, n = tmp; 109 } 110 111 return log2; 112 } 113 114 } // namespace ipcdetail 115 } // namespace interprocess 116 } // namespace boost 117 118 #endif 119