mfbt/TemplateLib.h

   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 */