ceph/src/boost/boost/container/detail/math_functions.hpp

   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 dtl {
  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>
  46 inline 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>
  65 inline 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>
  74 inline 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>
  87 inline 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 template <typename Integer, bool Loop = true>
  98 struct upper_power_of_2_loop_ct
  99 {
 100
 101    template <Integer I, Integer P>
 102    struct apply
 103    {
 104       static const Integer value =
 105          upper_power_of_2_loop_ct<Integer, (I > P*2)>::template apply<I, P*2>::value;
 106    };
 107 };
 108
 109 template <typename Integer>
 110 struct upper_power_of_2_loop_ct<Integer, false>
 111 {
 112    template <Integer I, Integer P>
 113    struct apply
 114    {
 115       static const Integer value = P;
 116    };
 117 };
 118
 119 template <typename Integer, Integer I>
 120 struct upper_power_of_2_ct
 121 {
 122    static const Integer value = upper_power_of_2_loop_ct<Integer, (I > 1)>::template apply<I, 2>::value;
 123 };
 124
 125 //This function uses binary search to discover the
 126 //highest set bit of the integer
 127 inline std::size_t floor_log2 (std::size_t x)
 128 {
 129    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
 130    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
 131    BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
 132
 133    std::size_t n = x;
 134    std::size_t log2 = 0;
 135
 136    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
 137       std::size_t tmp = n >> shift;
 138       if (tmp)
 139          log2 += shift, n = tmp;
 140    }
 141
 142    return log2;
 143 }
 144
 145 template<std::size_t I1, std::size_t I2>
 146 struct gcd_ct
 147 {
 148    static const std::size_t Max = I1 > I2 ? I1 : I2;
 149    static const std::size_t Min = I1 < I2 ? I1 : I2;
 150    static const std::size_t value = gcd_ct<Min, Max % Min>::value;
 151 };
 152
 153 template<std::size_t I1>
 154 struct gcd_ct<I1, 0>
 155 {
 156    static const std::size_t value = I1;
 157 };
 158
 159 template<std::size_t I1>
 160 struct gcd_ct<0, I1>
 161 {
 162    static const std::size_t value = I1;
 163 };
 164
 165 template<std::size_t I1, std::size_t I2>
 166 struct lcm_ct
 167 {
 168    static const std::size_t value = I1 * I2 / gcd_ct<I1, I2>::value;
 169 };
 170
 171 } // namespace dtl
 172 } // namespace container
 173 } // namespace boost
 174
 175 #include <boost/container/detail/config_end.hpp>
 176
 177 #endif