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