Move libcds 1.6.0 from SVN
[libcds.git] / cds / int_algo.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_INT_ALGO_H
4 #define __CDS_INT_ALGO_H
5
6 #include <cds/bitop.h>
7
8 namespace cds { namespace beans {
9
10     /// Returns largest previous integer for <tt>log2( n )</tt>
11     static inline size_t log2floor( size_t n )
12     {
13         return n ? cds::bitop::MSBnz( n ) : 0;
14     }
15
16     /// Returns smallest following integer for <tt>log2( n )</tt>
17     static inline size_t log2ceil( size_t n )
18     {
19         size_t i = log2floor( n );
20         return size_t( 1 << i ) < n ? i + 1 : i;
21     }
22
23     /// Returns largest previous power of 2 for \p n
24     /**
25         Examples:
26         \code
27         floor2(0) == 1   // !!!
28         floor2(1) == 1
29         floor2(2) == 2
30         floor2(3) == 2
31         floor2(4) == 4
32         floor2(15) == 8
33         floor2(16) == 16
34         floor2(17) == 16
35         \endcode
36     */
37     static inline size_t floor2( size_t n )
38     {
39         return size_t(1) << log2floor( n );
40     }
41
42     /// Returns smallest following power of 2 for \p n
43     /**
44         Examples:
45         \code
46         ceil2(0) == 1   // !!!
47         ceil2(1) == 1
48         ceil2(2) == 2
49         ceil2(3) == 4
50         ceil2(4) == 4
51         ceil2(15) == 16
52         ceil2(16) == 16
53         ceil2(17) == 32
54         \endcode
55     */
56     static inline size_t ceil2( size_t n )
57     {
58         return size_t(1) << log2ceil( n );
59     }
60
61     /// Checks if \p n is power of 2
62     CDS_CONSTEXPR static inline bool is_power2( size_t n ) CDS_NOEXCEPT
63     {
64         return (n & (n - 1)) == 0 && n;
65     }
66
67     /// Returns binary logarithm of \p n if \p n is power of two, otherwise returns 0
68     static inline size_t log2( size_t n )
69     {
70         return is_power2(n) ? log2floor(n) : 0;
71     }
72 }}   // namespace cds::beans
73
74 #endif  // #ifndef __CDS_INT_ALGO_H