michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * Reusable template meta-functions on types and compile-time values.  Meta-
michael@0:  * functions are placed inside the 'tl' namespace to avoid conflict with non-
michael@0:  * meta functions of the same name (e.g., mozilla::tl::FloorLog2 vs.
michael@0:  * mozilla::FloorLog2).
michael@0:  *
michael@0:  * When constexpr support becomes universal, we should probably use that instead
michael@0:  * of some of these templates, for simplicity.
michael@0:  */
michael@0: 
michael@0: #ifndef mozilla_TemplateLib_h
michael@0: #define mozilla_TemplateLib_h
michael@0: 
michael@0: #include <limits.h>
michael@0: #include <stddef.h>
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: namespace tl {
michael@0: 
michael@0: /** Compute min/max. */
michael@0: template<size_t I, size_t J>
michael@0: struct Min
michael@0: {
michael@0:     static const size_t value = I < J ? I : J;
michael@0: };
michael@0: template<size_t I, size_t J>
michael@0: struct Max
michael@0: {
michael@0:     static const size_t value = I > J ? I : J;
michael@0: };
michael@0: 
michael@0: /** Compute floor(log2(i)). */
michael@0: template<size_t I>
michael@0: struct FloorLog2
michael@0: {
michael@0:     static const size_t value = 1 + FloorLog2<I / 2>::value;
michael@0: };
michael@0: template<> struct FloorLog2<0> { /* Error */ };
michael@0: template<> struct FloorLog2<1> { static const size_t value = 0; };
michael@0: 
michael@0: /** Compute ceiling(log2(i)). */
michael@0: template<size_t I>
michael@0: struct CeilingLog2
michael@0: {
michael@0:     static const size_t value = FloorLog2<2 * I - 1>::value;
michael@0: };
michael@0: 
michael@0: /** Round up to the nearest power of 2. */
michael@0: template<size_t I>
michael@0: struct RoundUpPow2
michael@0: {
michael@0:     static const size_t value = size_t(1) << CeilingLog2<I>::value;
michael@0: };
michael@0: template<>
michael@0: struct RoundUpPow2<0>
michael@0: {
michael@0:     static const size_t value = 1;
michael@0: };
michael@0: 
michael@0: /** Compute the number of bits in the given unsigned type. */
michael@0: template<typename T>
michael@0: struct BitSize
michael@0: {
michael@0:     static const size_t value = sizeof(T) * CHAR_BIT;
michael@0: };
michael@0: 
michael@0: /**
michael@0:  * Produce an N-bit mask, where N <= BitSize<size_t>::value.  Handle the
michael@0:  * language-undefined edge case when N = BitSize<size_t>::value.
michael@0:  */
michael@0: template<size_t N>
michael@0: struct NBitMask
michael@0: {
michael@0:     // Assert the precondition.  On success this evaluates to 0.  Otherwise it
michael@0:     // triggers divide-by-zero at compile time: a guaranteed compile error in
michael@0:     // C++11, and usually one in C++98.  Add this value to |value| to assure
michael@0:     // its computation.
michael@0:     static const size_t checkPrecondition = 0 / size_t(N < BitSize<size_t>::value);
michael@0:     static const size_t value = (size_t(1) << N) - 1 + checkPrecondition;
michael@0: };
michael@0: template<>
michael@0: struct NBitMask<BitSize<size_t>::value>
michael@0: {
michael@0:     static const size_t value = size_t(-1);
michael@0: };
michael@0: 
michael@0: /**
michael@0:  * For the unsigned integral type size_t, compute a mask M for N such that
michael@0:  * for all X, !(X & M) implies X * N will not overflow (w.r.t size_t)
michael@0:  */
michael@0: template<size_t N>
michael@0: struct MulOverflowMask
michael@0: {
michael@0:     static const size_t value =
michael@0:       ~NBitMask<BitSize<size_t>::value - CeilingLog2<N>::value>::value;
michael@0: };
michael@0: template<> struct MulOverflowMask<0> { /* Error */ };
michael@0: template<> struct MulOverflowMask<1> { static const size_t value = 0; };
michael@0: 
michael@0: } // namespace tl
michael@0: 
michael@0: } // namespace mozilla
michael@0: 
michael@0: #endif /* mozilla_TemplateLib_h */