From 6bf0a5cb5034a7e684dcc3500e841785237ce2dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 19:32:43 +0200 Subject: Adding upstream version 1:115.7.0. Signed-off-by: Daniel Baumann --- dom/media/Intervals.h | 762 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 762 insertions(+) create mode 100644 dom/media/Intervals.h (limited to 'dom/media/Intervals.h') diff --git a/dom/media/Intervals.h b/dom/media/Intervals.h new file mode 100644 index 0000000000..ecda90d350 --- /dev/null +++ b/dom/media/Intervals.h @@ -0,0 +1,762 @@ +/* -*- 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/. */ + +#ifndef DOM_MEDIA_INTERVALS_H_ +#define DOM_MEDIA_INTERVALS_H_ + +#include +#include + +#include "nsTArray.h" +#include "nsString.h" +#include "nsPrintfCString.h" + +// Specialization for nsTArray CopyChooser. +namespace mozilla::media { +template +class IntervalSet; +class TimeUnit; +} // namespace mozilla::media + +template +struct nsTArray_RelocationStrategy> { + typedef nsTArray_RelocateUsingMoveConstructor> + Type; +}; + +namespace mozilla::media { + +/* Interval defines an interval between two points. Unlike a traditional + interval [A,B] where A <= x <= B, the upper boundary B is exclusive: A <= x < + B (e.g [A,B[ or [A,B) depending on where you're living) It provides basic + interval arithmetic and fuzzy edges. The type T must provides a default + constructor and +, -, <, <= and == operators. + */ +template +class Interval { + public: + typedef Interval SelfType; + + Interval() : mStart(T()), mEnd(T()), mFuzz(T()) {} + + template + Interval(StartArg&& aStart, EndArg&& aEnd) + : mStart(aStart), mEnd(aEnd), mFuzz() { + MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd, "Invalid Interval"); + } + + template + Interval(StartArg&& aStart, EndArg&& aEnd, FuzzArg&& aFuzz) + : mStart(aStart), mEnd(aEnd), mFuzz(aFuzz) { + MOZ_DIAGNOSTIC_ASSERT(mStart <= mEnd, "Invalid Interval"); + } + + Interval(const SelfType& aOther) + : mStart(aOther.mStart), mEnd(aOther.mEnd), mFuzz(aOther.mFuzz) {} + + Interval(SelfType&& aOther) + : mStart(std::move(aOther.mStart)), + mEnd(std::move(aOther.mEnd)), + mFuzz(std::move(aOther.mFuzz)) {} + + SelfType& operator=(const SelfType& aOther) { + mStart = aOther.mStart; + mEnd = aOther.mEnd; + mFuzz = aOther.mFuzz; + return *this; + } + + SelfType& operator=(SelfType&& aOther) { + MOZ_ASSERT(&aOther != this, "self-moves are prohibited"); + this->~Interval(); + new (this) Interval(std::move(aOther)); + return *this; + } + + // Basic interval arithmetic operator definition. + SelfType operator+(const SelfType& aOther) const { + return SelfType(mStart + aOther.mStart, mEnd + aOther.mEnd, + mFuzz + aOther.mFuzz); + } + + SelfType operator+(const T& aVal) const { + return SelfType(mStart + aVal, mEnd + aVal, mFuzz); + } + + SelfType operator-(const SelfType& aOther) const { + return SelfType(mStart - aOther.mEnd, mEnd - aOther.mStart, + mFuzz + aOther.mFuzz); + } + + SelfType operator-(const T& aVal) const { + return SelfType(mStart - aVal, mEnd - aVal, mFuzz); + } + + SelfType& operator+=(const SelfType& aOther) { + mStart += aOther.mStart; + mEnd += aOther.mEnd; + mFuzz += aOther.mFuzz; + return *this; + } + + SelfType& operator+=(const T& aVal) { + mStart += aVal; + mEnd += aVal; + return *this; + } + + SelfType& operator-=(const SelfType& aOther) { + mStart -= aOther.mStart; + mEnd -= aOther.mEnd; + mFuzz += aOther.mFuzz; + return *this; + } + + SelfType& operator-=(const T& aVal) { + mStart -= aVal; + mEnd -= aVal; + return *this; + } + + bool operator==(const SelfType& aOther) const { + return mStart == aOther.mStart && mEnd == aOther.mEnd; + } + + bool operator!=(const SelfType& aOther) const { return !(*this == aOther); } + + bool Contains(const T& aX) const { + return mStart - mFuzz <= aX && aX < mEnd + mFuzz; + } + + bool ContainsStrict(const T& aX) const { return mStart <= aX && aX < mEnd; } + + bool ContainsWithStrictEnd(const T& aX) const { + return mStart - mFuzz <= aX && aX < mEnd; + } + + bool Contains(const SelfType& aOther) const { + return (mStart - mFuzz <= aOther.mStart + aOther.mFuzz) && + (aOther.mEnd - aOther.mFuzz <= mEnd + mFuzz); + } + + bool ContainsStrict(const SelfType& aOther) const { + return mStart <= aOther.mStart && aOther.mEnd <= mEnd; + } + + bool ContainsWithStrictEnd(const SelfType& aOther) const { + return (mStart - mFuzz <= aOther.mStart + aOther.mFuzz) && + aOther.mEnd <= mEnd; + } + + bool Intersects(const SelfType& aOther) const { + return (mStart - mFuzz < aOther.mEnd + aOther.mFuzz) && + (aOther.mStart - aOther.mFuzz < mEnd + mFuzz); + } + + bool IntersectsStrict(const SelfType& aOther) const { + return mStart < aOther.mEnd && aOther.mStart < mEnd; + } + + // Same as Intersects, but including the boundaries. + bool Touches(const SelfType& aOther) const { + return (mStart - mFuzz <= aOther.mEnd + aOther.mFuzz) && + (aOther.mStart - aOther.mFuzz <= mEnd + mFuzz); + } + + // Returns true if aOther is strictly to the right of this and contiguous. + // This operation isn't commutative. + bool Contiguous(const SelfType& aOther) const { + return mEnd <= aOther.mStart && + aOther.mStart - mEnd <= mFuzz + aOther.mFuzz; + } + + bool RightOf(const SelfType& aOther) const { + return aOther.mEnd - aOther.mFuzz <= mStart + mFuzz; + } + + bool LeftOf(const SelfType& aOther) const { + return mEnd - mFuzz <= aOther.mStart + aOther.mFuzz; + } + + SelfType Span(const SelfType& aOther) const { + if (IsEmpty()) { + return aOther; + } + SelfType result(*this); + if (aOther.mStart < mStart) { + result.mStart = aOther.mStart; + } + if (mEnd < aOther.mEnd) { + result.mEnd = aOther.mEnd; + } + if (mFuzz < aOther.mFuzz) { + result.mFuzz = aOther.mFuzz; + } + return result; + } + + SelfType Intersection(const SelfType& aOther) const { + const T& s = std::max(mStart, aOther.mStart); + const T& e = std::min(mEnd, aOther.mEnd); + const T& f = std::max(mFuzz, aOther.mFuzz); + if (s < e) { + return SelfType(s, e, f); + } + // Return an empty interval. + return SelfType(); + } + + T Length() const { return mEnd - mStart; } + + bool IsEmpty() const { return mStart == mEnd; } + + void SetFuzz(const T& aFuzz) { mFuzz = aFuzz; } + + // Returns true if the two intervals intersect with this being on the right + // of aOther + bool TouchesOnRight(const SelfType& aOther) const { + return aOther.mStart <= mStart && + (mStart - mFuzz <= aOther.mEnd + aOther.mFuzz) && + (aOther.mStart - aOther.mFuzz <= mEnd + mFuzz); + } + + // Returns true if the two intervals intersect with this being on the right + // of aOther, ignoring fuzz. + bool TouchesOnRightStrict(const SelfType& aOther) const { + return aOther.mStart <= mStart && mStart <= aOther.mEnd; + } + + nsCString ToString() const { + if constexpr (std::is_same_v) { + return nsPrintfCString("[%s, %s](%s)", mStart.ToString().get(), + mEnd.ToString().get(), mFuzz.ToString().get()); + } else if constexpr (std::is_same_v) { + return nsPrintfCString("[%lf, %lf](%lf)", mStart, mEnd, mFuzz); + } + } + + T mStart; + T mEnd; + T mFuzz; +}; + +// An IntervalSet in a collection of Intervals. The IntervalSet is always +// normalized. +template +class IntervalSet { + public: + typedef IntervalSet SelfType; + typedef Interval ElemType; + typedef AutoTArray ContainerType; + typedef typename ContainerType::index_type IndexType; + + IntervalSet() = default; + virtual ~IntervalSet() = default; + + IntervalSet(const SelfType& aOther) : mIntervals(aOther.mIntervals.Clone()) {} + + IntervalSet(SelfType&& aOther) { + mIntervals.AppendElements(std::move(aOther.mIntervals)); + } + + explicit IntervalSet(const ElemType& aOther) { + if (!aOther.IsEmpty()) { + mIntervals.AppendElement(aOther); + } + } + + explicit IntervalSet(ElemType&& aOther) { + if (!aOther.IsEmpty()) { + mIntervals.AppendElement(std::move(aOther)); + } + } + + bool operator==(const SelfType& aOther) const { + return mIntervals == aOther.mIntervals; + } + + bool operator!=(const SelfType& aOther) const { + return mIntervals != aOther.mIntervals; + } + + SelfType& operator=(const SelfType& aOther) { + mIntervals = aOther.mIntervals.Clone(); + return *this; + } + + SelfType& operator=(SelfType&& aOther) { + MOZ_ASSERT(&aOther != this, "self-moves are prohibited"); + this->~IntervalSet(); + new (this) IntervalSet(std::move(aOther)); + return *this; + } + + SelfType& operator=(const ElemType& aInterval) { + mIntervals.Clear(); + if (!aInterval.IsEmpty()) { + mIntervals.AppendElement(aInterval); + } + return *this; + } + + SelfType& operator=(ElemType&& aInterval) { + mIntervals.Clear(); + if (!aInterval.IsEmpty()) { + mIntervals.AppendElement(std::move(aInterval)); + } + return *this; + } + + SelfType& Add(const SelfType& aIntervals) { + if (aIntervals.mIntervals.Length() == 1) { + Add(aIntervals.mIntervals[0]); + } else { + mIntervals.AppendElements(aIntervals.mIntervals); + Normalize(); + } + return *this; + } + + SelfType& Add(const ElemType& aInterval) { + if (aInterval.IsEmpty()) { + return *this; + } + if (mIntervals.IsEmpty()) { + mIntervals.AppendElement(aInterval); + return *this; + } + ElemType& last = mIntervals.LastElement(); + if (aInterval.TouchesOnRight(last)) { + last = last.Span(aInterval); + return *this; + } + // Most of our actual usage is adding an interval that will be outside the + // range. We can speed up normalization here. + if (aInterval.RightOf(last)) { + mIntervals.AppendElement(aInterval); + return *this; + } + + ContainerType normalized; + ElemType current(aInterval); + IndexType i = 0; + for (; i < mIntervals.Length(); i++) { + ElemType& interval = mIntervals[i]; + if (current.Touches(interval)) { + current = current.Span(interval); + } else if (current.LeftOf(interval)) { + break; + } else { + normalized.AppendElement(std::move(interval)); + } + } + normalized.AppendElement(std::move(current)); + for (; i < mIntervals.Length(); i++) { + normalized.AppendElement(std::move(mIntervals[i])); + } + mIntervals.Clear(); + mIntervals.AppendElements(std::move(normalized)); + + return *this; + } + + SelfType& operator+=(const SelfType& aIntervals) { + Add(aIntervals); + return *this; + } + + SelfType& operator+=(const ElemType& aInterval) { + Add(aInterval); + return *this; + } + + SelfType operator+(const SelfType& aIntervals) const { + SelfType intervals(*this); + intervals.Add(aIntervals); + return intervals; + } + + SelfType operator+(const ElemType& aInterval) const { + SelfType intervals(*this); + intervals.Add(aInterval); + return intervals; + } + + friend SelfType operator+(const ElemType& aInterval, + const SelfType& aIntervals) { + SelfType intervals; + intervals.Add(aInterval); + intervals.Add(aIntervals); + return intervals; + } + + // Excludes an interval from an IntervalSet. + SelfType& operator-=(const ElemType& aInterval) { + if (aInterval.IsEmpty() || mIntervals.IsEmpty()) { + return *this; + } + if (mIntervals.Length() == 1 && + mIntervals[0].TouchesOnRightStrict(aInterval)) { + // Fast path when we're removing from the front of a set with a + // single interval. This is common for the buffered time ranges + // we see on Twitch. + if (aInterval.mEnd >= mIntervals[0].mEnd) { + mIntervals.RemoveElementAt(0); + } else { + mIntervals[0].mStart = aInterval.mEnd; + mIntervals[0].mFuzz = std::max(mIntervals[0].mFuzz, aInterval.mFuzz); + } + return *this; + } + + // General case performed by inverting aInterval within the bounds of + // mIntervals and then doing the intersection. + T firstEnd = std::max(mIntervals[0].mStart, aInterval.mStart); + T secondStart = std::min(mIntervals.LastElement().mEnd, aInterval.mEnd); + ElemType startInterval(mIntervals[0].mStart, firstEnd); + ElemType endInterval(secondStart, mIntervals.LastElement().mEnd); + SelfType intervals(std::move(startInterval)); + intervals += std::move(endInterval); + return Intersection(intervals); + } + + SelfType& operator-=(const SelfType& aIntervals) { + for (const auto& interval : aIntervals.mIntervals) { + *this -= interval; + } + return *this; + } + + SelfType operator-(const SelfType& aInterval) const { + SelfType intervals(*this); + intervals -= aInterval; + return intervals; + } + + SelfType operator-(const ElemType& aInterval) const { + SelfType intervals(*this); + intervals -= aInterval; + return intervals; + } + + // Mutate this IntervalSet to be the union of this and aOther. + SelfType& Union(const SelfType& aOther) { + Add(aOther); + return *this; + } + + SelfType& Union(const ElemType& aInterval) { + Add(aInterval); + return *this; + } + + // Mutate this TimeRange to be the intersection of this and aOther. + SelfType& Intersection(const SelfType& aOther) { + ContainerType intersection; + + // Ensure the intersection has enough capacity to store the upper bound on + // the intersection size. This ensures that we don't spend time reallocating + // the storage as we append, at the expense of extra memory. + intersection.SetCapacity(std::max(aOther.Length(), mIntervals.Length())); + + const ContainerType& other = aOther.mIntervals; + IndexType i = 0, j = 0; + for (; i < mIntervals.Length() && j < other.Length();) { + if (mIntervals[i].IntersectsStrict(other[j])) { + intersection.AppendElement(mIntervals[i].Intersection(other[j])); + } + if (mIntervals[i].mEnd < other[j].mEnd) { + i++; + } else { + j++; + } + } + mIntervals = std::move(intersection); + return *this; + } + + SelfType& Intersection(const ElemType& aInterval) { + SelfType intervals(aInterval); + return Intersection(intervals); + } + + const ElemType& operator[](IndexType aIndex) const { + return mIntervals[aIndex]; + } + + // Returns the start boundary of the first interval. Or a default constructed + // T if IntervalSet is empty (and aExists if provided will be set to false). + T GetStart(bool* aExists = nullptr) const { + bool exists = !mIntervals.IsEmpty(); + + if (aExists) { + *aExists = exists; + } + + if (exists) { + return mIntervals[0].mStart; + } else { + return T(); + } + } + + // Returns the end boundary of the last interval. Or a default constructed T + // if IntervalSet is empty (and aExists if provided will be set to false). + T GetEnd(bool* aExists = nullptr) const { + bool exists = !mIntervals.IsEmpty(); + if (aExists) { + *aExists = exists; + } + + if (exists) { + return mIntervals.LastElement().mEnd; + } else { + return T(); + } + } + + IndexType Length() const { return mIntervals.Length(); } + + bool IsEmpty() const { return mIntervals.IsEmpty(); } + + T Start(IndexType aIndex) const { return mIntervals[aIndex].mStart; } + + T Start(IndexType aIndex, bool& aExists) const { + aExists = aIndex < mIntervals.Length(); + + if (aExists) { + return mIntervals[aIndex].mStart; + } else { + return T(); + } + } + + T End(IndexType aIndex) const { return mIntervals[aIndex].mEnd; } + + T End(IndexType aIndex, bool& aExists) const { + aExists = aIndex < mIntervals.Length(); + + if (aExists) { + return mIntervals[aIndex].mEnd; + } else { + return T(); + } + } + + bool Contains(const ElemType& aInterval) const { + for (const auto& interval : mIntervals) { + if (interval.Contains(aInterval)) { + return true; + } + } + return false; + } + + bool ContainsStrict(const ElemType& aInterval) const { + for (const auto& interval : mIntervals) { + if (interval.ContainsStrict(aInterval)) { + return true; + } + } + return false; + } + + bool Contains(const T& aX) const { + for (const auto& interval : mIntervals) { + if (interval.Contains(aX)) { + return true; + } + } + return false; + } + + bool ContainsStrict(const T& aX) const { + for (const auto& interval : mIntervals) { + if (interval.ContainsStrict(aX)) { + return true; + } + } + return false; + } + + bool ContainsWithStrictEnd(const T& aX) const { + for (const auto& interval : mIntervals) { + if (interval.ContainsWithStrictEnd(aX)) { + return true; + } + } + return false; + } + + bool ContainsWithStrictEnd(const ElemType& aInterval) const { + for (const auto& interval : mIntervals) { + if (interval.ContainsWithStrictEnd(aInterval)) { + return true; + } + } + return false; + } + + bool Intersects(const ElemType& aInterval) const { + for (const auto& interval : mIntervals) { + if (interval.Intersects(aInterval)) { + return true; + } + } + return false; + } + + bool IntersectsStrict(const ElemType& aInterval) const { + for (const auto& interval : mIntervals) { + if (interval.IntersectsStrict(aInterval)) { + return true; + } + } + return false; + } + + // Returns if there's any intersection between this and aOther. + bool IntersectsStrict(const SelfType& aOther) const { + const ContainerType& other = aOther.mIntervals; + IndexType i = 0, j = 0; + for (; i < mIntervals.Length() && j < other.Length();) { + if (mIntervals[i].IntersectsStrict(other[j])) { + return true; + } + if (mIntervals[i].mEnd < other[j].mEnd) { + i++; + } else { + j++; + } + } + return false; + } + + bool IntersectsWithStrictEnd(const ElemType& aInterval) const { + for (const auto& interval : mIntervals) { + if (interval.IntersectsWithStrictEnd(aInterval)) { + return true; + } + } + return false; + } + + // Shift all values by aOffset. + SelfType& Shift(const T& aOffset) { + for (auto& interval : mIntervals) { + interval.mStart = interval.mStart + aOffset; + interval.mEnd = interval.mEnd + aOffset; + } + return *this; + } + + void SetFuzz(const T& aFuzz) { + for (auto& interval : mIntervals) { + interval.SetFuzz(aFuzz); + } + MergeOverlappingIntervals(); + } + + static const IndexType NoIndex = IndexType(-1); + + IndexType Find(const T& aValue) const { + for (IndexType i = 0; i < mIntervals.Length(); i++) { + if (mIntervals[i].Contains(aValue)) { + return i; + } + } + return NoIndex; + } + + // Methods for range-based for loops. + typename ContainerType::iterator begin() { return mIntervals.begin(); } + + typename ContainerType::const_iterator begin() const { + return mIntervals.begin(); + } + + typename ContainerType::iterator end() { return mIntervals.end(); } + + typename ContainerType::const_iterator end() const { + return mIntervals.end(); + } + + ElemType& LastInterval() { + MOZ_ASSERT(!mIntervals.IsEmpty()); + return mIntervals.LastElement(); + } + + const ElemType& LastInterval() const { + MOZ_ASSERT(!mIntervals.IsEmpty()); + return mIntervals.LastElement(); + } + + void Clear() { mIntervals.Clear(); } + + protected: + ContainerType mIntervals; + + private: + void Normalize() { + if (mIntervals.Length() < 2) { + return; + } + mIntervals.Sort(CompareIntervals()); + MergeOverlappingIntervals(); + } + + void MergeOverlappingIntervals() { + if (mIntervals.Length() < 2) { + return; + } + + // This merges the intervals in place. + IndexType read = 0; + IndexType write = 0; + while (read < mIntervals.Length()) { + ElemType current(mIntervals[read]); + read++; + while (read < mIntervals.Length() && current.Touches(mIntervals[read])) { + current = current.Span(mIntervals[read]); + read++; + } + mIntervals[write] = current; + write++; + } + mIntervals.SetLength(write); + } + + struct CompareIntervals { + bool Equals(const ElemType& aT1, const ElemType& aT2) const { + return aT1.mStart == aT2.mStart && aT1.mEnd == aT2.mEnd; + } + + bool LessThan(const ElemType& aT1, const ElemType& aT2) const { + return aT1.mStart - aT1.mFuzz < aT2.mStart + aT2.mFuzz; + } + }; +}; + +// clang doesn't allow for this to be defined inline of IntervalSet. +template +IntervalSet Union(const IntervalSet& aIntervals1, + const IntervalSet& aIntervals2) { + IntervalSet intervals(aIntervals1); + intervals.Union(aIntervals2); + return intervals; +} + +template +IntervalSet Intersection(const IntervalSet& aIntervals1, + const IntervalSet& aIntervals2) { + IntervalSet intersection(aIntervals1); + intersection.Intersection(aIntervals2); + return intersection; +} + +} // namespace mozilla::media + +#endif // DOM_MEDIA_INTERVALS_H_ -- cgit v1.2.3