← Back to branch summary

~twpol/dcplusplus/trunk

« back to all changes in this revision

Viewing changes to boost/boost/interprocess/detail/math_functions.hpp

  • Committer: James Ross
  • Date: 2010-07-05 00:03:18 UTC
  • mfrom: (1524.1.650 dcplusplus)
  • Revision ID: silver@warwickcompsoc.co.uk-20100705000318-awwqm8ocpp5m47yz
Merged to trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/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
 
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