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

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