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