dom/media/doctor/RollingNumber.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 mozilla_RollingNumber_h_
   8 #define mozilla_RollingNumber_h_
   9
  10 #include "mozilla/Assertions.h"
  11 #include "mozilla/Attributes.h"
  12 #include <limits>
  13
  14 namespace mozilla {
  15
  16 // Unsigned number suited to index elements in a never-ending queue, as
  17 // order-comparison behaves nicely around the overflow.
  18 //
  19 // Additive operators work the same as for the underlying value type, but
  20 // expect "small" jumps, as should normally happen when manipulating indices.
  21 //
  22 // Comparison functions are different, they keep the ordering based on the
  23 // distance between numbers, modulo the value type range:
  24 // If the distance is less than half the range of the value type, the usual
  25 // ordering stays.
  26 // 0 < 1, 2^23 < 2^24
  27 // However if the distance is more than half the range, we assume that we are
  28 // continuing along the queue, and therefore consider the smaller number to
  29 // actually be greater!
  30 // uint(-1) < 0.
  31 //
  32 // The expected usage is to always work on nearby rolling numbers: slowly
  33 // incrementing/decrementing them, and translating&comparing them within a
  34 // small window.
  35 // To enforce this usage during development, debug-build assertions catch API
  36 // calls involving distances of more than a *quarter* of the type range.
  37 // In non-debug builds, all APIs will still work as consistently as possible
  38 // without crashing, but performing operations on "distant" nunbers could lead
  39 // to unexpected results.
  40 template <typename T>
  41 class RollingNumber {
  42   static_assert(!std::numeric_limits<T>::is_signed,
  43                 "RollingNumber only accepts unsigned number types");
  44
  45  public:
  46   using ValueType = T;
  47
  48   RollingNumber() : mIndex(0) {}
  49
  50   explicit RollingNumber(ValueType aIndex) : mIndex(aIndex) {}
  51
  52   RollingNumber(const RollingNumber&) = default;
  53   RollingNumber& operator=(const RollingNumber&) = default;
  54
  55   ValueType Value() const { return mIndex; }
  56
  57   // Normal increments/decrements.
  58
  59   RollingNumber& operator++() {
  60     ++mIndex;
  61     return *this;
  62   }
  63
  64   RollingNumber operator++(int) { return RollingNumber{mIndex++}; }
  65
  66   RollingNumber& operator--() {
  67     --mIndex;
  68     return *this;
  69   }
  70
  71   RollingNumber operator--(int) { return RollingNumber{mIndex--}; }
  72
  73   RollingNumber& operator+=(const ValueType& aIncrement) {
  74     MOZ_ASSERT(aIncrement <= MaxDiff);
  75     mIndex += aIncrement;
  76     return *this;
  77   }
  78
  79   RollingNumber operator+(const ValueType& aIncrement) const {
  80     RollingNumber n = *this;
  81     return n += aIncrement;
  82   }
  83
  84   RollingNumber& operator-=(const ValueType& aDecrement) {
  85     MOZ_ASSERT(aDecrement <= MaxDiff);
  86     mIndex -= aDecrement;
  87     return *this;
  88   }
  89
  90   // Translate a RollingNumber by a negative value.
  91   RollingNumber operator-(const ValueType& aDecrement) const {
  92     RollingNumber n = *this;
  93     return n -= aDecrement;
  94   }
  95
  96   // Distance between two RollingNumbers, giving a value.
  97   ValueType operator-(const RollingNumber& aOther) const {
  98     ValueType diff = mIndex - aOther.mIndex;
  99     MOZ_ASSERT(diff <= MaxDiff);
 100     return diff;
 101   }
 102
 103   // Normal (in)equality operators.
 104
 105   bool operator==(const RollingNumber& aOther) const {
 106     return mIndex == aOther.mIndex;
 107   }
 108   bool operator!=(const RollingNumber& aOther) const {
 109     return !(*this == aOther);
 110   }
 111
 112   // Modified comparison operators.
 113
 114   bool operator<(const RollingNumber& aOther) const {
 115     const T& a = mIndex;
 116     const T& b = aOther.mIndex;
 117     // static_cast needed because of possible integer promotion
 118     // (e.g., from uint8_t to int, which would make the test useless).
 119     const bool lessThanOther = static_cast<ValueType>(a - b) > MidWay;
 120     MOZ_ASSERT((lessThanOther ? (b - a) : (a - b)) <= MaxDiff);
 121     return lessThanOther;
 122   }
 123
 124   bool operator<=(const RollingNumber& aOther) const {
 125     const T& a = mIndex;
 126     const T& b = aOther.mIndex;
 127     const bool lessishThanOther = static_cast<ValueType>(b - a) <= MidWay;
 128     MOZ_ASSERT((lessishThanOther ? (b - a) : (a - b)) <= MaxDiff);
 129     return lessishThanOther;
 130   }
 131
 132   bool operator>=(const RollingNumber& aOther) const {
 133     const T& a = mIndex;
 134     const T& b = aOther.mIndex;
 135     const bool greaterishThanOther = static_cast<ValueType>(a - b) <= MidWay;
 136     MOZ_ASSERT((greaterishThanOther ? (a - b) : (b - a)) <= MaxDiff);
 137     return greaterishThanOther;
 138   }
 139
 140   bool operator>(const RollingNumber& aOther) const {
 141     const T& a = mIndex;
 142     const T& b = aOther.mIndex;
 143     const bool greaterThanOther = static_cast<ValueType>(b - a) > MidWay;
 144     MOZ_ASSERT((greaterThanOther ? (a - b) : (b - a)) <= MaxDiff);
 145     return greaterThanOther;
 146   }
 147
 148  private:
 149   // MidWay is used to split the type range in two, to decide how two numbers
 150   // are ordered.
 151   static const T MidWay = std::numeric_limits<T>::max() / 2;
 152 #ifdef DEBUG
 153   // MaxDiff is the expected maximum difference between two numbers, either
 154   // during comparisons, or when adding/subtracting.
 155   // This is only used during debugging, to highlight algorithmic issues.
 156   static const T MaxDiff = std::numeric_limits<T>::max() / 4;
 157 #endif
 158   ValueType mIndex;
 159 };
 160
 161 }  // namespace mozilla
 162
 163 #endif  // mozilla_RollingNumber_h_