]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |