boost/interprocess/detail/math_functions.hpp

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