container/detail/math_functions.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Stephen Cleary 2000.
0004 // (C) Copyright Ion Gaztanaga 2007-2013.
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/container for documentation.
0011 //
0012 // This file is a slightly modified file from Boost.Pool
0013 //
0014 //////////////////////////////////////////////////////////////////////////////
0015
0016 #ifndef BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP
0017 #define BOOST_CONTAINER_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 <boost/container/detail/config_begin.hpp>
0028 #include <boost/container/detail/workaround.hpp>
0029
0030 #include <climits>
0031
0032 namespace boost {
0033 namespace container {
0034 namespace dtl {
0035
0036 // Greatest common divisor and least common multiple
0037
0038 //
0039 // gcd is an algorithm that calculates the greatest common divisor of two
0040 //  integers, using Euclid's algorithm.
0041 //
0042 // Pre: A > 0 && B > 0
0043 // Recommended: A > B
0044 template <typename Integer>
0045 inline Integer gcd(Integer A, Integer B)
0046 {
0047    do
0048    {
0049       const Integer tmp(B);
0050       B = A % B;
0051       A = tmp;
0052    } while (B != 0);
0053
0054    return A;
0055 }
0056
0057 //
0058 // lcm is an algorithm that calculates the least common multiple of two
0059 //  integers.
0060 //
0061 // Pre: A > 0 && B > 0
0062 // Recommended: A > B
0063 template <typename Integer>
0064 inline Integer lcm(const Integer & A, const Integer & B)
0065 {
0066    Integer ret = A;
0067    ret /= gcd(A, B);
0068    ret *= B;
0069    return ret;
0070 }
0071
0072 template <typename Integer>
0073 inline Integer log2_ceil(const Integer & A)
0074 {
0075    Integer i = 0;
0076    Integer power_of_2 = 1;
0077
0078    while(power_of_2 < A){
0079       power_of_2 <<= 1;
0080       ++i;
0081    }
0082    return i;
0083 }
0084
0085 template <typename Integer>
0086 inline Integer upper_power_of_2(const Integer & A)
0087 {
0088    Integer power_of_2 = 1;
0089
0090    while(power_of_2 < A){
0091       power_of_2 <<= 1;
0092    }
0093    return power_of_2;
0094 }
0095
0096 template <typename Integer, bool Loop = true>
0097 struct upper_power_of_2_loop_ct
0098 {
0099
0100    template <Integer I, Integer P>
0101    struct apply
0102    {
0103       BOOST_STATIC_CONSTEXPR Integer value =
0104          upper_power_of_2_loop_ct<Integer, (I > P*2)>::template apply<I, P*2>::value;
0105    };
0106 };
0107
0108 template <typename Integer>
0109 struct upper_power_of_2_loop_ct<Integer, false>
0110 {
0111    template <Integer I, Integer P>
0112    struct apply
0113    {
0114       BOOST_STATIC_CONSTEXPR Integer value = P;
0115    };
0116 };
0117
0118 template <typename Integer, Integer I>
0119 struct upper_power_of_2_ct
0120 {
0121    BOOST_STATIC_CONSTEXPR Integer value = upper_power_of_2_loop_ct<Integer, (I > 1)>::template apply<I, 2>::value;
0122 };
0123
0124 //This function uses binary search to discover the
0125 //highest set bit of the integer
0126 inline std::size_t floor_log2 (std::size_t x)
0127 {
0128    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
0129    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
0130    BOOST_CONTAINER_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
0131
0132    std::size_t n = x;
0133    std::size_t log2 = 0;
0134
0135    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
0136       std::size_t tmp = n >> shift;
0137       if (tmp)
0138          log2 += shift, n = tmp;
0139    }
0140
0141    return log2;
0142 }
0143
0144 template<std::size_t I1, std::size_t I2>
0145 struct gcd_ct
0146 {
0147    BOOST_STATIC_CONSTEXPR std::size_t Max = I1 > I2 ? I1 : I2;
0148    BOOST_STATIC_CONSTEXPR std::size_t Min = I1 < I2 ? I1 : I2;
0149    BOOST_STATIC_CONSTEXPR std::size_t value = gcd_ct<Min, Max % Min>::value;
0150 };
0151
0152 template<std::size_t I1>
0153 struct gcd_ct<I1, 0>
0154 {
0155    BOOST_STATIC_CONSTEXPR std::size_t value = I1;
0156 };
0157
0158 template<std::size_t I1>
0159 struct gcd_ct<0, I1>
0160 {
0161    BOOST_STATIC_CONSTEXPR std::size_t value = I1;
0162 };
0163
0164 template<std::size_t I1, std::size_t I2>
0165 struct lcm_ct
0166 {
0167    BOOST_STATIC_CONSTEXPR std::size_t value = I1 * I2 / gcd_ct<I1, I2>::value;
0168 };
0169
0170 } // namespace dtl
0171 } // namespace container
0172 } // namespace boost
0173
0174 #include <boost/container/detail/config_end.hpp>
0175
0176 #endif