memory/build/Utils.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 #ifndef Utils_h
   8 #define Utils_h
   9
  10 #include <type_traits>
  11
  12 #include "mozilla/CheckedInt.h"
  13 #include "mozilla/TemplateLib.h"
  14
  15 // Helper for log2 of powers of 2 at compile time.
  16 template <size_t N>
  17 struct Log2 : mozilla::tl::CeilingLog2<N> {
  18   using mozilla::tl::CeilingLog2<N>::value;
  19   static_assert(1ULL << value == N, "Number is not a power of 2");
  20 };
  21 #define LOG2(N) Log2<N>::value
  22
  23 enum class Order {
  24   eLess = -1,
  25   eEqual = 0,
  26   eGreater = 1,
  27 };
  28
  29 // Compare two integers. Returns whether the first integer is Less,
  30 // Equal or Greater than the second integer.
  31 template <typename T>
  32 Order CompareInt(T aValue1, T aValue2) {
  33   static_assert(std::is_integral_v<T>, "Type must be integral");
  34   if (aValue1 < aValue2) {
  35     return Order::eLess;
  36   }
  37   if (aValue1 > aValue2) {
  38     return Order::eGreater;
  39   }
  40   return Order::eEqual;
  41 }
  42
  43 // Compare two addresses. Returns whether the first address is Less,
  44 // Equal or Greater than the second address.
  45 template <typename T>
  46 Order CompareAddr(T* aAddr1, T* aAddr2) {
  47   return CompareInt(uintptr_t(aAddr1), uintptr_t(aAddr2));
  48 }
  49
  50 // Helper for (fast) comparison of fractions without involving divisions or
  51 // floats.
  52 class Fraction {
  53  public:
  54   explicit constexpr Fraction(size_t aNumerator, size_t aDenominator)
  55       : mNumerator(aNumerator), mDenominator(aDenominator) {}
  56
  57   MOZ_IMPLICIT constexpr Fraction(long double aValue)
  58       // We use an arbitrary power of two as denominator that provides enough
  59       // precision for our use case.
  60       : mNumerator(aValue * 4096), mDenominator(4096) {}
  61
  62   inline bool operator<(const Fraction& aOther) const {
  63 #ifndef MOZ_DEBUG
  64     // We are comparing A / B < C / D, with all A, B, C and D being positive
  65     // numbers. Multiplying both sides with B * D, we have:
  66     // (A * B * D) / B < (C * B * D) / D, which can then be simplified as
  67     // A * D < C * B. When can thus compare our fractions without actually
  68     // doing any division.
  69     // This however assumes the multiplied quantities are small enough not
  70     // to overflow the multiplication. We use CheckedInt on debug builds
  71     // to enforce the assumption.
  72     return mNumerator * aOther.mDenominator < aOther.mNumerator * mDenominator;
  73 #else
  74     mozilla::CheckedInt<size_t> numerator(mNumerator);
  75     mozilla::CheckedInt<size_t> denominator(mDenominator);
  76     // value() asserts when the multiplication overflowed.
  77     size_t lhs = (numerator * aOther.mDenominator).value();
  78     size_t rhs = (aOther.mNumerator * denominator).value();
  79     return lhs < rhs;
  80 #endif
  81   }
  82
  83   inline bool operator>(const Fraction& aOther) const { return aOther < *this; }
  84
  85   inline bool operator>=(const Fraction& aOther) const {
  86     return !(*this < aOther);
  87   }
  88
  89   inline bool operator<=(const Fraction& aOther) const {
  90     return !(*this > aOther);
  91   }
  92
  93   inline bool operator==(const Fraction& aOther) const {
  94 #ifndef MOZ_DEBUG
  95     // Same logic as operator<
  96     return mNumerator * aOther.mDenominator == aOther.mNumerator * mDenominator;
  97 #else
  98     mozilla::CheckedInt<size_t> numerator(mNumerator);
  99     mozilla::CheckedInt<size_t> denominator(mDenominator);
 100     size_t lhs = (numerator * aOther.mDenominator).value();
 101     size_t rhs = (aOther.mNumerator * denominator).value();
 102     return lhs == rhs;
 103 #endif
 104   }
 105
 106   inline bool operator!=(const Fraction& aOther) const {
 107     return !(*this == aOther);
 108   }
 109
 110  private:
 111   size_t mNumerator;
 112   size_t mDenominator;
 113 };
 114
 115 #endif