1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 /* 8 * Reusable template meta-functions on types and compile-time values. Meta- 9 * functions are placed inside the 'tl' namespace to avoid conflict with non- 10 * meta functions of the same name (e.g., mozilla::tl::FloorLog2 vs. 11 * mozilla::FloorLog2). 12 * 13 * When constexpr support becomes universal, we should probably use that instead 14 * of some of these templates, for simplicity. 15 */ 16 17 #ifndef mozilla_TemplateLib_h 18 #define mozilla_TemplateLib_h 19 20 #include <limits.h> 21 #include <stddef.h> 22 23 #include "mozilla/TypeTraits.h" 24 25 namespace mozilla { 26 27 namespace tl { 28 29 /** Compute min/max. */ 30 template <size_t Size, size_t... Rest> 31 struct Min { 32 static constexpr size_t value = 33 Size < Min<Rest...>::value ? Size : Min<Rest...>::value; 34 }; 35 36 template <size_t Size> 37 struct Min<Size> { 38 static constexpr size_t value = Size; 39 }; 40 41 template <size_t Size, size_t... Rest> 42 struct Max { 43 static constexpr size_t value = 44 Size > Max<Rest...>::value ? Size : Max<Rest...>::value; 45 }; 46 47 template <size_t Size> 48 struct Max<Size> { 49 static constexpr size_t value = Size; 50 }; 51 52 /** Compute floor(log2(i)). */ 53 template <size_t I> 54 struct FloorLog2 { 55 static const size_t value = 1 + FloorLog2<I / 2>::value; 56 }; 57 template <> 58 struct FloorLog2<0> { /* Error */ 59 }; 60 template <> 61 struct FloorLog2<1> { 62 static const size_t value = 0; 63 }; 64 65 /** Compute ceiling(log2(i)). */ 66 template <size_t I> 67 struct CeilingLog2 { 68 static const size_t value = FloorLog2<2 * I - 1>::value; 69 }; 70 71 /** Round up to the nearest power of 2. */ 72 template <size_t I> 73 struct RoundUpPow2 { 74 static const size_t value = size_t(1) << CeilingLog2<I>::value; 75 }; 76 template <> 77 struct RoundUpPow2<0> { 78 static const size_t value = 1; 79 }; 80 81 /** Compute the number of bits in the given unsigned type. */ 82 template <typename T> 83 struct BitSize { 84 static const size_t value = sizeof(T) * CHAR_BIT; 85 }; 86 87 /** 88 * Produce an N-bit mask, where N <= BitSize<size_t>::value. Handle the 89 * language-undefined edge case when N = BitSize<size_t>::value. 90 */ 91 template <size_t N> 92 struct NBitMask { 93 // Assert the precondition. On success this evaluates to 0. Otherwise it 94 // triggers divide-by-zero at compile time: a guaranteed compile error in 95 // C++11, and usually one in C++98. Add this value to |value| to assure 96 // its computation. 97 static const size_t checkPrecondition = 98 0 / size_t(N < BitSize<size_t>::value); 99 static const size_t value = (size_t(1) << N) - 1 + checkPrecondition; 100 }; 101 template <> 102 struct NBitMask<BitSize<size_t>::value> { 103 static const size_t value = size_t(-1); 104 }; 105 106 /** 107 * For the unsigned integral type size_t, compute a mask M for N such that 108 * for all X, !(X & M) implies X * N will not overflow (w.r.t size_t) 109 */ 110 template <size_t N> 111 struct MulOverflowMask { 112 static const size_t value = 113 ~NBitMask<BitSize<size_t>::value - CeilingLog2<N>::value>::value; 114 }; 115 template <> 116 struct MulOverflowMask<0> { /* Error */ 117 }; 118 template <> 119 struct MulOverflowMask<1> { 120 static const size_t value = 0; 121 }; 122 123 /** 124 * And<bool...> computes the logical 'and' of its argument booleans. 125 * 126 * Examples: 127 * mozilla::t1::And<true, true>::value is true. 128 * mozilla::t1::And<true, false>::value is false. 129 * mozilla::t1::And<>::value is true. 130 */ 131 132 template <bool...> 133 struct And; 134 135 template <> 136 struct And<> : public TrueType {}; 137 138 template <bool C1, bool... Cn> 139 struct And<C1, Cn...> : public Conditional<C1, And<Cn...>, FalseType>::Type {}; 140 141 } // namespace tl 142 143 } // namespace mozilla 144 145 #endif /* mozilla_TemplateLib_h */ 146