Remove the "needsFullOrderingComparisons" feature from PODRedBlackTree
https://bugs.webkit.org/show_bug.cgi?id=205238
Reviewed by Sam Weinig.
* html/HTMLMediaElement.cpp:
(WebCore::HTMLMediaElement::updateActiveTextTrackCues): Simplified code and
eliminate uses of the createInterval function to construct PODInterval objects.
(WebCore::HTMLMediaElement::textTrackAddCue): Ditto.
(WebCore::HTMLMediaElement::textTrackRemoveCue): Ditto.
* html/HTMLMediaElement.h: Removed unnecessary include of PODInterval.h.
* html/shadow/MediaControlElements.cpp: Added include of PODInterval.h.
* platform/PODInterval.h: Changed operator< to compare low, high, and user
data, not just low and high so it's consistent with operator== and we
can use it to search a tree. Added a partial specialization for WeakPtr
since a WeakPtr's value can change (to null) so it can't be used for
ordering and equality checks; luckily the clients don't need to use it
that way; they build an interval tree but never search for anything or
remove anything from the tree.
* platform/PODIntervalTree.h: Make the search adapter used to find overlaps
a member class instead of a top level class template and simplified it a bit.
Removed the unneeded createInterval function. Stopped passing true for
"needsFullOrderingComparisons" since it's not needed any more due to the
changes to PODInterval.
* platform/PODRedBlackTree.h: Removed the "needsFullOrderingComparisons"
template argument for the PODRedBlackTree class template.
(WebCore::PODRedBlackTree::Node::moveDataFrom): Take a reference (why not,
since this always requires a non-null pointer).
(WebCore::PODRedBlackTree::updateNode): Ditto.
(WebCore::PODRedBlackTree::treeSearch const): Merged the three search
functions into a single one since we don't need the peculiar
"full comparisons" mode.
(WebCore::PODRedBlackTree::propagateUpdates): Simplified logic to remove
the boolean local variable.
(WebCore::PODRedBlackTree::dumpSubtree const): Renamed from dumpFromNode
since the comment said "dumps the subtree". Also removed the comment now
that the function name says what it said.
* rendering/FloatingObjects.h: Removed unnecessary include of PODInterval.h.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@254483 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/WebCore/platform/PODInterval.h b/Source/WebCore/platform/PODInterval.h
index 96e047b..3a9fe66 100644
--- a/Source/WebCore/platform/PODInterval.h
+++ b/Source/WebCore/platform/PODInterval.h
@@ -1,5 +1,6 @@
/*
* Copyright (C) 2010 Google Inc. All rights reserved.
+ * Copyright (C) 2020 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -31,57 +32,43 @@
namespace WebCore {
-// Class representing a closed interval which can hold arbitrary
-// endpoints and a piece of user
-// data. An important characteristic for the algorithms we use is that
-// if two intervals have identical endpoints but different user data,
-// they are not considered to be equal. This situation can arise when
-// representing the vertical extents of bounding boxes of overlapping
-// triangles, where the pointer to the triangle is the user data of
-// the interval.
+// Class template representing a closed interval which can hold arbitrary
+// endpoints and a piece of user data. Ordering and equality are defined
+// including the UserData, except in the special case of WeakPtr.
//
-// *Note* that the destructors of type T and UserData will *not* be
-// called by this class. They must not allocate any memory that is
-// required to be cleaned up in their destructors.
-//
-// The following constructors and operators must be implemented on
-// type T:
-//
-// - Copy constructor
-// - operator<
-// - operator==
-// - operator=
-//
-// The UserData type must support a copy constructor and assignment
-// operator.
+// Both the T and UserData types must support a copy constructor, operator<,
+// operator==, and operator=, except that this does not depend on operator<
+// or operator== for WeakPtr.
//
// In debug mode, printing of intervals and the data they contain is
// enabled. This uses WTF::TextStream.
//
-// Note that this class requires a copy constructor and assignment
-// operator in order to be stored in the red-black tree.
+// Note that this class supplies a copy constructor and assignment
+// operator in order so it can be stored in the red-black tree.
// FIXME: The prefix "POD" here isn't correct; this works with non-POD types.
-template<class T, class UserData>
-class PODInterval {
+template<class T, class UserData> class PODIntervalBase {
public:
- PODInterval(const T& low, const T& high)
- : m_low(low)
- , m_high(high)
- , m_maxHigh(high)
+ const T& low() const { return m_low; }
+ const T& high() const { return m_high; }
+ const UserData& data() const { return m_data; }
+
+ bool overlaps(const T& low, const T& high) const
{
+ return !(m_high < low || high < m_low);
}
- PODInterval(const T& low, const T& high, const UserData& data)
- : m_low(low)
- , m_high(high)
- , m_data(data)
- , m_maxHigh(high)
+ bool overlaps(const PODIntervalBase& other) const
{
+ return overlaps(other.m_low, other.m_high);
}
- PODInterval(const T& low, const T& high, UserData&& data)
+ const T& maxHigh() const { return m_maxHigh; }
+ void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
+
+protected:
+ PODIntervalBase(const T& low, const T& high, UserData&& data)
: m_low(low)
, m_high(high)
, m_data(WTFMove(data))
@@ -89,42 +76,16 @@
{
}
- const T& low() const { return m_low; }
- const T& high() const { return m_high; }
- const UserData& data() const { return m_data; }
-
- bool overlaps(const T& low, const T& high) const
+#if COMPILER(MSVC)
+ // Work around an MSVC bug.
+ PODIntervalBase(const T& low, const T& high, const UserData& data)
+ : m_low(low)
+ , m_high(high)
+ , m_data(data)
+ , m_maxHigh(high)
{
- if (this->high() < low)
- return false;
- if (high < this->low())
- return false;
- return true;
}
-
- bool overlaps(const PODInterval& other) const
- {
- return overlaps(other.low(), other.high());
- }
-
- // Returns true if this interval is "less" than the other. The
- // comparison is performed on the low endpoints of the intervals.
- bool operator<(const PODInterval& other) const
- {
- return low() < other.low();
- }
-
- // Returns true if this interval is strictly equal to the other,
- // including comparison of the user data.
- bool operator==(const PODInterval& other) const
- {
- return (low() == other.low()
- && high() == other.high()
- && data() == other.data());
- }
-
- const T& maxHigh() const { return m_maxHigh; }
- void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
+#endif
private:
T m_low;
@@ -133,6 +94,62 @@
T m_maxHigh;
};
+template<class T, class UserData> class PODInterval : public PODIntervalBase<T, UserData> {
+public:
+ PODInterval(const T& low, const T& high, UserData&& data = { })
+ : PODIntervalBase<T, UserData>(low, high, WTFMove(data))
+ {
+ }
+
+ PODInterval(const T& low, const T& high, const UserData& data)
+ : PODIntervalBase<T, UserData>(low, high, UserData { data })
+ {
+ }
+
+ bool operator<(const PODInterval& other) const
+ {
+ if (Base::low() < other.Base::low())
+ return true;
+ if (other.Base::low() < Base::low())
+ return false;
+ if (Base::high() < other.Base::high())
+ return true;
+ if (other.Base::high() < Base::high())
+ return false;
+ return Base::data() < other.Base::data();
+ }
+
+ bool operator==(const PODInterval& other) const
+ {
+ return Base::low() == other.Base::low()
+ && Base::high() == other.Base::high()
+ && Base::data() == other.Base::data();
+ }
+
+private:
+ using Base = PODIntervalBase<T, UserData>;
+};
+
+template<class T, class U> class PODInterval<T, WTF::WeakPtr<U>> : public PODIntervalBase<T, WTF::WeakPtr<U>> {
+public:
+ PODInterval(const T& low, const T& high, WTF::WeakPtr<U>&& data)
+ : PODIntervalBase<T, WTF::WeakPtr<U>>(low, high, WTFMove(data))
+ {
+ }
+
+ bool operator<(const PODInterval& other) const
+ {
+ if (Base::low() < other.Base::low())
+ return true;
+ if (other.Base::low() < Base::low())
+ return false;
+ return Base::high() < other.Base::high();
+ }
+
+private:
+ using Base = PODIntervalBase<T, WTF::WeakPtr<U>>;
+};
+
#ifndef NDEBUG
template<class T, class UserData>
