interprocess/detail/math_functions.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Stephen Cleary 2000.
0004 // (C) Copyright Ion Gaztanaga 2007-2012.
0005 //
0006 // Distributed under the Boost Software License, Version 1.0.
0007 //    (See accompanying file LICENSE_1_0.txt or copy at
0008 //    http://www.boost.org/LICENSE_1_0.txt)
0009 //
0010 // See http://www.boost.org/libs/interprocess for documentation.
0011 //
0012 // This file is a slightly modified file from Boost.Pool
0013 //
0014 //////////////////////////////////////////////////////////////////////////////
0015
0016 #ifndef BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP
0017 #define BOOST_INTERPROCESS_DETAIL_MATH_FUNCTIONS_HPP
0018
0019 #ifndef BOOST_CONFIG_HPP
0020 #  include <boost/config.hpp>
0021 #endif
0022 #
0023 #if defined(BOOST_HAS_PRAGMA_ONCE)
0024 #  pragma once
0025 #endif
0026
0027 #include <climits>
0028 #include <boost/static_assert.hpp>
0029
0030 namespace boost {
0031 namespace interprocess {
0032 namespace ipcdetail {
0033
0034 // Greatest common divisor and least common multiple
0035
0036 //
0037 // gcd is an algorithm that calculates the greatest common divisor of two
0038 //  integers, using Euclid's algorithm.
0039 //
0040 // Pre: A > 0 && B > 0
0041 // Recommended: A > B
0042 template <typename Integer>
0043 inline Integer gcd(Integer A, Integer B)
0044 {
0045    do
0046    {
0047       const Integer tmp(B);
0048       B = A % B;
0049       A = tmp;
0050    } while (B != 0);
0051
0052    return A;
0053 }
0054
0055 //
0056 // lcm is an algorithm that calculates the least common multiple of two
0057 //  integers.
0058 //
0059 // Pre: A > 0 && B > 0
0060 // Recommended: A > B
0061 template <typename Integer>
0062 inline Integer lcm(const Integer & A, const Integer & B)
0063 {
0064    Integer ret = A;
0065    ret /= gcd(A, B);
0066    ret *= B;
0067    return ret;
0068 }
0069
0070 template <typename Integer>
0071 inline Integer log2_ceil(const Integer & A)
0072 {
0073    Integer i = 0;
0074    Integer power_of_2 = 1;
0075
0076    while(power_of_2 < A){
0077       power_of_2 <<= 1;
0078       ++i;
0079    }
0080    return i;
0081 }
0082
0083 template <typename Integer>
0084 inline Integer upper_power_of_2(const Integer & A)
0085 {
0086    Integer power_of_2 = 1;
0087
0088    while(power_of_2 < A){
0089       power_of_2 <<= 1;
0090    }
0091    return power_of_2;
0092 }
0093
0094 //This function uses binary search to discover the
0095 //highest set bit of the integer
0096 inline std::size_t floor_log2 (std::size_t x)
0097 {
0098    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
0099    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
0100    BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
0101
0102    std::size_t n = x;
0103    std::size_t log2 = 0;
0104
0105    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
0106       std::size_t tmp = n >> shift;
0107       if (tmp)
0108          log2 += shift, n = tmp;
0109    }
0110
0111    return log2;
0112 }
0113
0114 } // namespace ipcdetail
0115 } // namespace interprocess
0116 } // namespace boost
0117
0118 #endif