DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (48f71175c999)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Reusable template meta-functions on types and compile-time values.  Meta-
 * functions are placed inside the 'tl' namespace to avoid conflict with non-
 * meta functions of the same name (e.g., mozilla::tl::FloorLog2 vs.
 * mozilla::FloorLog2).
 *
 * When constexpr support becomes universal, we should probably use that instead
 * of some of these templates, for simplicity.
 */

#ifndef mozilla_TemplateLib_h
#define mozilla_TemplateLib_h

#include <limits.h>
#include <stddef.h>

#include "mozilla/TypeTraits.h"

namespace mozilla {

namespace tl {

/** Compute min/max. */
template <size_t Size, size_t... Rest>
struct Min {
  static constexpr size_t value =
      Size < Min<Rest...>::value ? Size : Min<Rest...>::value;
};

template <size_t Size>
struct Min<Size> {
  static constexpr size_t value = Size;
};

template <size_t Size, size_t... Rest>
struct Max {
  static constexpr size_t value =
      Size > Max<Rest...>::value ? Size : Max<Rest...>::value;
};

template <size_t Size>
struct Max<Size> {
  static constexpr size_t value = Size;
};

/** Compute floor(log2(i)). */
template <size_t I>
struct FloorLog2 {
  static const size_t value = 1 + FloorLog2<I / 2>::value;
};
template <>
struct FloorLog2<0> { /* Error */
};
template <>
struct FloorLog2<1> {
  static const size_t value = 0;
};

/** Compute ceiling(log2(i)). */
template <size_t I>
struct CeilingLog2 {
  static const size_t value = FloorLog2<2 * I - 1>::value;
};

/** Round up to the nearest power of 2. */
template <size_t I>
struct RoundUpPow2 {
  static const size_t value = size_t(1) << CeilingLog2<I>::value;
};
template <>
struct RoundUpPow2<0> {
  static const size_t value = 1;
};

/** Compute the number of bits in the given unsigned type. */
template <typename T>
struct BitSize {
  static const size_t value = sizeof(T) * CHAR_BIT;
};

/**
 * Produce an N-bit mask, where N <= BitSize<size_t>::value.  Handle the
 * language-undefined edge case when N = BitSize<size_t>::value.
 */
template <size_t N>
struct NBitMask {
  // Assert the precondition.  On success this evaluates to 0.  Otherwise it
  // triggers divide-by-zero at compile time: a guaranteed compile error in
  // C++11, and usually one in C++98.  Add this value to |value| to assure
  // its computation.
  static const size_t checkPrecondition =
      0 / size_t(N < BitSize<size_t>::value);
  static const size_t value = (size_t(1) << N) - 1 + checkPrecondition;
};
template <>
struct NBitMask<BitSize<size_t>::value> {
  static const size_t value = size_t(-1);
};

/**
 * For the unsigned integral type size_t, compute a mask M for N such that
 * for all X, !(X & M) implies X * N will not overflow (w.r.t size_t)
 */
template <size_t N>
struct MulOverflowMask {
  static const size_t value =
      ~NBitMask<BitSize<size_t>::value - CeilingLog2<N>::value>::value;
};
template <>
struct MulOverflowMask<0> { /* Error */
};
template <>
struct MulOverflowMask<1> {
  static const size_t value = 0;
};

/**
 * And<bool...> computes the logical 'and' of its argument booleans.
 *
 * Examples:
 *   mozilla::t1::And<true, true>::value is true.
 *   mozilla::t1::And<true, false>::value is false.
 *   mozilla::t1::And<>::value is true.
 */

template <bool...>
struct And;

template <>
struct And<> : public TrueType {};

template <bool C1, bool... Cn>
struct And<C1, Cn...> : public Conditional<C1, And<Cn...>, FalseType>::Type {};

}  // namespace tl

}  // namespace mozilla

#endif /* mozilla_TemplateLib_h */