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 #include <type_traits>
  23
  24 namespace mozilla {
  25
  26 namespace tl {
  27
  28 /** Compute min/max. */
  29 template <size_t Size, size_t... Rest>
  30 struct Min {
  31   static constexpr size_t value =
  32       Size < Min<Rest...>::value ? Size : Min<Rest...>::value;
  33 };
  34
  35 template <size_t Size>
  36 struct Min<Size> {
  37   static constexpr size_t value = Size;
  38 };
  39
  40 template <size_t Size, size_t... Rest>
  41 struct Max {
  42   static constexpr size_t value =
  43       Size > Max<Rest...>::value ? Size : Max<Rest...>::value;
  44 };
  45
  46 template <size_t Size>
  47 struct Max<Size> {
  48   static constexpr size_t value = Size;
  49 };
  50
  51 /** Compute floor(log2(i)). */
  52 template <size_t I>
  53 struct FloorLog2 {
  54   static const size_t value = 1 + FloorLog2<I / 2>::value;
  55 };
  56 template <>
  57 struct FloorLog2<0> { /* Error */
  58 };
  59 template <>
  60 struct FloorLog2<1> {
  61   static const size_t value = 0;
  62 };
  63
  64 /** Compute ceiling(log2(i)). */
  65 template <size_t I>
  66 struct CeilingLog2 {
  67   static const size_t value = FloorLog2<2 * I - 1>::value;
  68 };
  69
  70 /** Round up to the nearest power of 2. */
  71 template <size_t I>
  72 struct RoundUpPow2 {
  73   static const size_t value = size_t(1) << CeilingLog2<I>::value;
  74 };
  75 template <>
  76 struct RoundUpPow2<0> {
  77   static const size_t value = 1;
  78 };
  79
  80 /** Compute the number of bits in the given unsigned type. */
  81 template <typename T>
  82 struct BitSize {
  83   static const size_t value = sizeof(T) * CHAR_BIT;
  84 };
  85
  86 /**
  87  * Produce an N-bit mask, where N <= BitSize<size_t>::value.  Handle the
  88  * language-undefined edge case when N = BitSize<size_t>::value.
  89  */
  90 template <size_t N>
  91 struct NBitMask {
  92   // Assert the precondition.  On success this evaluates to 0.  Otherwise it
  93   // triggers divide-by-zero at compile time: a guaranteed compile error in
  94   // C++11, and usually one in C++98.  Add this value to |value| to assure
  95   // its computation.
  96   static const size_t checkPrecondition =
  97       0 / size_t(N < BitSize<size_t>::value);
  98   static const size_t value = (size_t(1) << N) - 1 + checkPrecondition;
  99 };
 100 template <>
 101 struct NBitMask<BitSize<size_t>::value> {
 102   static const size_t value = size_t(-1);
 103 };
 104
 105 /**
 106  * For the unsigned integral type size_t, compute a mask M for N such that
 107  * for all X, !(X & M) implies X * N will not overflow (w.r.t size_t)
 108  */
 109 template <size_t N>
 110 struct MulOverflowMask {
 111   static const size_t value =
 112       ~NBitMask<BitSize<size_t>::value - CeilingLog2<N>::value>::value;
 113 };
 114 template <>
 115 struct MulOverflowMask<0> { /* Error */
 116 };
 117 template <>
 118 struct MulOverflowMask<1> {
 119   static const size_t value = 0;
 120 };
 121
 122 }  // namespace tl
 123
 124 }  // namespace mozilla
 125
 126 #endif /* mozilla_TemplateLib_h */