cds/numtraits.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_NUMERIC_TRAITS_H
   4 #define __CDS_NUMERIC_TRAITS_H
   5
   6 /*
   7     Filename: numtraits.h
   8     Created 2007.04.22 by Maxim.Khiszinsky
   9
  10     Description:
  11         Various numeric constants and algorithms
  12         Many algorithms are static (compile-time)
  13         Result of static algorithm is the constant (enum) called "result".
  14
  15     Editions:
  16         2007.04.22  Maxim.Khiszinsky    Created
  17         2007.07.20  Maxim.Khiszinsky    Added functions: exponent2, exp2Ceil
  18 */
  19
  20 namespace cds {
  21     /// Some helper compile-time tricks
  22     namespace beans {
  23
  24         // @cond details
  25         namespace details {
  26             template <int N, int MOD> struct Exponent2Helper;
  27             template <int N> struct Exponent2Helper< N, 0 > {
  28                 enum { result = Exponent2Helper< N / 2, N % 2 >::result + 1 };
  29             };
  30             template <> struct Exponent2Helper< 1, 0 > {
  31                 enum { result = 0 };
  32             };
  33         }
  34         // @endcond
  35
  36         /*! Compile-time computing of log2(N)
  37
  38             If N = 2**k for some natural k then Exponent2<N>::result = k
  39             If N != 2**k for any natural k then compile-time error has been encountered
  40         */
  41         template <int N> struct Exponent2 {
  42             enum {
  43                 native    = N,
  44                 base    = 2,
  45                 result    = details::Exponent2Helper< N / 2, N % 2 >::result + 1
  46             };
  47         };
  48         //@cond details
  49         template <> struct Exponent2<1> {
  50             enum {
  51                 native    = 1,
  52                 base    = 2,
  53                 result    = 0
  54             };
  55         };
  56         //@endcond
  57
  58         //TODO - deprecated. Use is_power2 from int_algo.h
  59         /// A tricky runtime algorithm to ensure that @p n is power of 2
  60         static inline bool isExp2( size_t n )
  61         {
  62             return(n & (n - 1)) == 0 && n;
  63         }
  64
  65         //TODO: deprecated. Use log2 from int_algo.h
  66         /// Runtime algorithm to compute log2( @p nTest ). If @p nTest is not power of two then -1 returns
  67         static inline int exponent2( size_t nTest )
  68         {
  69             int nExp = -1;
  70             size_t nMask = 1;
  71             for ( size_t n = 0; n < CDS_BUILD_BITS; n++ ) {
  72                 if ( nTest & nMask ) {
  73                     if ( nExp == -1 )
  74                         nExp = (int) n;
  75                     else
  76                         return -1    ;    // nTest íå ÿâëÿåòñÿ ñòåïåíüþ äâîéêè
  77                 }
  78                 nMask = nMask << 1;
  79             }
  80             return nExp;
  81         }
  82
  83         /// Returns @a N: 2**N is nearest to @p nNumber, 2**N < nNumber
  84         static inline size_t exp2Ceil( size_t nNumber )
  85         {
  86             static_assert( sizeof(size_t) == (CDS_BUILD_BITS / 8), "Internal assumption error" );
  87
  88             size_t nExp = 0;
  89             size_t nBit = CDS_BUILD_BITS - 1;
  90 #if CDS_BUILD_BITS == 32
  91             size_t nMask = 0x80000000;
  92 #else
  93             size_t nMask = 0x8000000000000000;
  94 #endif
  95             while ( nMask != 0 ) {
  96                 if ( nNumber & nMask ) {
  97                     nExp = nBit;
  98                     break;
  99                 }
 100                 nMask = nMask >> 1;
 101                 --nBit;
 102             }
 103             if ( ( nNumber % ( ((size_t) 1) << nExp )) > ( ((size_t) 1) << (nExp - 1)) )
 104                 ++nExp;
 105             return nExp;
 106         }
 107
 108         /* ExponentN< int BASE, int N >
 109             Exponent
 110             If N = BASE**k then the algorithm returns k
 111             Else compile-time error is encountered
 112         */
 113         //@cond details
 114         namespace details {
 115             template <int N, int BASE, int MOD> struct ExponentNHelper;
 116             template <int N, int BASE> struct ExponentNHelper< N, BASE, 0 > {
 117                 enum { result = ExponentNHelper< N / BASE, BASE, N % BASE >::result + 1 };
 118             };
 119             template <int BASE> struct ExponentNHelper< 1, BASE, 0 > {
 120                 enum { result = 0 };
 121             };
 122         }
 123         //@endcond
 124
 125         /// Compile-time computing log(@p N) based @p BASE. Result in @a Exponent<BASE, N>::result
 126         template <int BASE, int N> struct ExponentN {
 127             enum {
 128                 native    = N,
 129                 base    = BASE,
 130                 result    = details::ExponentNHelper< N / BASE, BASE, N % BASE >::result + 1
 131             };
 132         };
 133         //@cond
 134         template <int BASE> struct ExponentN< BASE, 1 > {
 135             enum {
 136                 native    = 1,
 137                 base    = BASE,
 138                 result    = 0
 139             };
 140         };
 141         template <int BASE> struct ExponentN< BASE, 0 >;
 142         //@endcond
 143
 144         //@cond none
 145         template <int N> struct Power2 {
 146             enum {
 147                 exponent = N,
 148                 result = 1 << N
 149             };
 150         };
 151         template <> struct Power2<0> {
 152             enum {
 153                 exponent = 0,
 154                 result = 1
 155             };
 156         };
 157         //@endcond
 158
 159         //@cond none
 160         template <int BASE, int N > struct PowerN {
 161             enum {
 162                 exponent = N,
 163                 base     = BASE,
 164                 result = PowerN< BASE, N - 1 >::result * BASE
 165             };
 166         };
 167         template <int BASE> struct PowerN<BASE, 0> {
 168             enum {
 169                 exponent = 0,
 170                 base     = BASE,
 171                 result     = 1
 172             };
 173         };
 174         //@endcond
 175
 176         //@cond none
 177         namespace details {
 178             template <int N, int ALIGN, int MOD> struct NearestCeilHelper {
 179                 enum { result = N + ALIGN - MOD };
 180             };
 181             template <int N, int ALIGN> struct NearestCeilHelper< N, ALIGN, 0> {
 182                 enum { result = N };
 183             };
 184         }
 185         template <int N, int ALIGN> struct NearestCeil {
 186             enum {
 187                 native    = N,
 188                 align    = ALIGN,
 189                 result    = details::NearestCeilHelper< N, ALIGN, N % ALIGN >::result
 190             };
 191         };
 192         //@endcond
 193
 194         //@cond none
 195         template <typename T, int ALIGN> struct AlignedSize {
 196             typedef T    NativeType;
 197             enum {
 198                 nativeSize    = sizeof(T),
 199                 result        = NearestCeil< sizeof(T), ALIGN >::result,
 200                 alignBytes    = result - nativeSize,
 201                 alignedSize = result
 202             };
 203         };
 204         //@endcond
 205
 206         //@cond none
 207         namespace details {
 208             template < int N1, int N2, bool LESS > struct Max;
 209             template < int N1, int N2 >
 210             struct Max< N1, N2, true > {
 211                 enum { result = N2  };
 212             };
 213
 214             template < int N1, int N2 >
 215             struct Max< N1, N2, false > {
 216                 enum { result = N1  };
 217             };
 218
 219             template < int N1, int N2, bool LESS > struct Min;
 220             template < int N1, int N2 >
 221             struct Min< N1, N2, true > {
 222                 enum { result = N1  };
 223             };
 224
 225             template < int N1, int N2 >
 226             struct Min< N1, N2, false > {
 227                 enum { result = N2  };
 228             };
 229         }
 230         //@endcond
 231
 232         /// Returns max(N1, N2) as Max<N1,N2>::result
 233         template <int N1, int N2>
 234         struct Max {
 235             enum { result = details::Max< N1, N2, N1 < N2 >::result  };
 236         };
 237
 238         /// Returns min(N1, N2) as Min<N1,N2>::result
 239         template <int N1, int N2>
 240         struct Min {
 241             enum { result = details::Min< N1, N2, N1 < N2 >::result  };
 242         };
 243
 244     }    // namespace beans
 245 }    // namespace cds
 246
 247 #endif    // __CDS_NUMERIC_TRAITS_H