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 container_detail {
  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 //This function uses binary search to discover the
  98 //highest set bit of the integer
  99 inline std::size_t floor_log2 (std::size_t x)
 100 {
 101    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
 102    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
 103    BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true));
 104
 105    std::size_t n = x;
 106    std::size_t log2 = 0;
 107
 108    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
 109       std::size_t tmp = n >> shift;
 110       if (tmp)
 111          log2 += shift, n = tmp;
 112    }
 113
 114    return log2;
 115 }
 116
 117 } // namespace container_detail
 118 } // namespace container
 119 } // namespace boost
 120
 121 #include <boost/container/detail/config_end.hpp>
 122
 123 #endif