Diff
Modified: trunk/Source/WebCore/ChangeLog (254482 => 254483)
--- trunk/Source/WebCore/ChangeLog 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/ChangeLog 2020-01-14 03:18:09 UTC (rev 254483)
@@ -1,3 +1,50 @@
+2019-12-14 Darin Adler <da...@apple.com>
+
+ 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.
+
2020-01-13 Justin Fan <justin_...@apple.com>
[WebGL 2] Implement transform feedback and pass transform feedback conformance tests
Modified: trunk/Source/WebCore/html/HTMLMediaElement.cpp (254482 => 254483)
--- trunk/Source/WebCore/html/HTMLMediaElement.cpp 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/html/HTMLMediaElement.cpp 2020-01-14 03:18:09 UTC (rev 254483)
@@ -1635,9 +1635,8 @@
// The user agent must synchronously unset [the text track cue active] flag
// whenever ... the media element's readyState is changed back to HAVE_NOTHING.
- auto movieTimeInterval = m_cueData->cueTree.createInterval(movieTime, movieTime);
if (m_readyState != HAVE_NOTHING && m_player) {
- currentCues = m_cueData->cueTree.allOverlaps(movieTimeInterval);
+ currentCues = m_cueData->cueTree.allOverlaps({ movieTime, movieTime });
if (currentCues.size() > 1)
std::sort(currentCues.begin(), currentCues.end(), &compareCueInterval);
}
@@ -1707,7 +1706,7 @@
if (auto nearestEndingCue = std::min_element(currentCues.begin(), currentCues.end(), compareCueIntervalEndTime))
nextInterestingTime = nearestEndingCue->data()->endMediaTime();
- Optional<CueInterval> nextCue = m_cueData->cueTree.nextIntervalAfter(movieTimeInterval.high());
+ Optional<CueInterval> nextCue = m_cueData->cueTree.nextIntervalAfter(movieTime);
if (nextCue)
nextInterestingTime = std::min(nextInterestingTime, nextCue->low());
@@ -1996,7 +1995,7 @@
// zero-length cues.
MediaTime endTime = std::max(cue.startMediaTime(), cue.endMediaTime());
- CueInterval interval = m_cueData->cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
+ CueInterval interval(cue.startMediaTime(), endTime, &cue);
if (!m_cueData->cueTree.contains(interval))
m_cueData->cueTree.add(interval);
updateActiveTextTrackCues(currentMediaTime());
@@ -2011,7 +2010,7 @@
// zero-length cues.
MediaTime endTime = std::max(cue.startMediaTime(), cue.endMediaTime());
- CueInterval interval = m_cueData->cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
+ CueInterval interval(cue.startMediaTime(), endTime, &cue);
m_cueData->cueTree.remove(interval);
// Since the cue will be removed from the media element and likely the
Modified: trunk/Source/WebCore/html/HTMLMediaElement.h (254482 => 254483)
--- trunk/Source/WebCore/html/HTMLMediaElement.h 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/html/HTMLMediaElement.h 2020-01-14 03:18:09 UTC (rev 254483)
@@ -46,7 +46,6 @@
#if ENABLE(VIDEO_TRACK)
#include "AudioTrack.h"
#include "CaptionUserPreferences.h"
-#include "PODInterval.h"
#include "TextTrack.h"
#include "TextTrackCue.h"
#include "VTTCue.h"
@@ -105,6 +104,7 @@
class WebKitMediaKeys;
template<typename> class DOMPromiseDeferred;
+template<typename, typename> class PODInterval;
#if ENABLE(WIRELESS_PLAYBACK_TARGET)
class RemotePlayback;
Modified: trunk/Source/WebCore/html/shadow/MediaControlElements.cpp (254482 => 254483)
--- trunk/Source/WebCore/html/shadow/MediaControlElements.cpp 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/html/shadow/MediaControlElements.cpp 2020-01-14 03:18:09 UTC (rev 254483)
@@ -48,6 +48,7 @@
#include "Logging.h"
#include "MediaControls.h"
#include "MouseEvent.h"
+#include "PODInterval.h"
#include "Page.h"
#include "PageGroup.h"
#include "RenderLayer.h"
Modified: trunk/Source/WebCore/platform/PODInterval.h (254482 => 254483)
--- trunk/Source/WebCore/platform/PODInterval.h 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/platform/PODInterval.h 2020-01-14 03:18:09 UTC (rev 254483)
@@ -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,49 +32,53 @@
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.
+// 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.
//
-// 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.
-//
// 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)
+ 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);
+ }
+
+ bool overlaps(const PODIntervalBase& other) const
+ {
+ return overlaps(other.m_low, other.m_high);
+ }
+
+ 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))
, m_maxHigh(high)
{
}
- PODInterval(const T& low, const T& high, const UserData& data)
+#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)
@@ -80,57 +85,69 @@
, m_maxHigh(high)
{
}
+#endif
- PODInterval(const T& low, const T& high, UserData&& data)
- : m_low(low)
- , m_high(high)
- , m_data(WTFMove(data))
- , m_maxHigh(high)
+private:
+ T m_low;
+ T m_high;
+ UserData m_data { };
+ 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))
{
}
- const T& low() const { return m_low; }
- const T& high() const { return m_high; }
- const UserData& data() const { return m_data; }
+ PODInterval(const T& low, const T& high, const UserData& data)
+ : PODIntervalBase<T, UserData>(low, high, UserData { data })
+ {
+ }
- bool overlaps(const T& low, const T& high) const
+ bool operator<(const PODInterval& other) const
{
- if (this->high() < low)
+ if (Base::low() < other.Base::low())
+ return true;
+ if (other.Base::low() < Base::low())
return false;
- if (high < this->low())
+ if (Base::high() < other.Base::high())
+ return true;
+ if (other.Base::high() < Base::high())
return false;
- return true;
+ return Base::data() < other.Base::data();
}
- bool overlaps(const PODInterval& other) const
+ bool operator==(const PODInterval& other) const
{
- return overlaps(other.low(), other.high());
+ return Base::low() == other.Base::low()
+ && Base::high() == other.Base::high()
+ && Base::data() == other.Base::data();
}
- // 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
+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))
{
- 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
+ bool operator<(const PODInterval& other) const
{
- return (low() == other.low()
- && high() == other.high()
- && data() == other.data());
+ if (Base::low() < other.Base::low())
+ return true;
+ if (other.Base::low() < Base::low())
+ return false;
+ return Base::high() < other.Base::high();
}
- const T& maxHigh() const { return m_maxHigh; }
- void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
-
private:
- T m_low;
- T m_high;
- UserData m_data { };
- T m_maxHigh;
+ using Base = PODIntervalBase<T, WTF::WeakPtr<U>>;
};
#ifndef NDEBUG
Modified: trunk/Source/WebCore/platform/PODIntervalTree.h (254482 => 254483)
--- trunk/Source/WebCore/platform/PODIntervalTree.h 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/platform/PODIntervalTree.h 2020-01-14 03:18:09 UTC (rev 254483)
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2010 Google Inc. All rights reserved.
- * Copyright (C) 2019 Apple Inc. All rights reserved.
+ * Copyright (C) 2019-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
@@ -35,71 +35,31 @@
namespace WebCore {
-template <class T, class UserData>
-class PODIntervalSearchAdapter {
-public:
- typedef PODInterval<T, UserData> IntervalType;
-
- PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
- : m_result(result)
- , m_lowValue(lowValue)
- , m_highValue(highValue)
- {
- }
-
- const T& lowValue() const { return m_lowValue; }
- const T& highValue() const { return m_highValue; }
- void collectIfNeeded(const IntervalType& data) const
- {
- if (data.overlaps(m_lowValue, m_highValue))
- m_result.append(data);
- }
-
-private:
- Vector<IntervalType>& m_result;
- T m_lowValue;
- T m_highValue;
-};
-
struct PODIntervalNodeUpdater;
// An interval tree, which is a form of augmented red-black tree. It
// supports efficient (O(lg n)) insertion, removal and querying of
// intervals in the tree.
-template<class T, class UserData>
-class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true> {
+template<typename T, typename UserData> class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater> {
WTF_MAKE_FAST_ALLOCATED;
public:
- // Typedef to reduce typing when declaring intervals to be stored in
- // this tree.
- typedef PODInterval<T, UserData> IntervalType;
- typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
+ using IntervalType = PODInterval<T, UserData>;
+ class OverlapsSearchAdapter;
- // Returns all intervals in the tree which overlap the given query
- // interval. The returned intervals are sorted by increasing low
- // endpoint.
+ // Returns all intervals in the tree which overlap the given query interval, sorted by the < operator.
Vector<IntervalType> allOverlaps(const IntervalType& interval) const
{
Vector<IntervalType> result;
- IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
- allOverlapsWithAdapter<IntervalSearchAdapterType>(adapter);
+ OverlapsSearchAdapter adapter(result, interval);
+ allOverlapsWithAdapter(adapter);
return result;
}
- template <class AdapterType>
- void allOverlapsWithAdapter(AdapterType& adapter) const
+ template<typename AdapterType> void allOverlapsWithAdapter(AdapterType& adapter) const
{
- // Explicit dereference of "this" required because of
- // inheritance rules in template classes.
- searchForOverlapsFrom<AdapterType>(this->root(), adapter);
+ searchForOverlapsFrom(this->root(), adapter);
}
- // Helper to create interval objects.
- static IntervalType createInterval(const T& low, const T& high, UserData&& data = { })
- {
- return IntervalType(low, high, WTFMove(data));
- }
-
Optional<IntervalType> nextIntervalAfter(const T& point)
{
auto next = smallestNodeGreaterThanFrom(point, this->root());
@@ -116,20 +76,19 @@
return false;
if (!this->root())
return true;
- return checkInvariantsFromNode(this->root(), 0);
+ return checkInvariantsFromNode(this->root(), nullptr);
}
#endif
private:
- using Base = PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true>;
- typedef typename Base::Node IntervalNode;
+ using Base = PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater>;
+ using IntervalNode = typename Base::Node;
// Starting from the given node, adds all overlaps with the given
// interval to the result vector. The intervals are sorted by
// increasing low endpoint.
- template <class AdapterType>
- void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
+ template<typename AdapterType> void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
{
if (!node)
return;
@@ -219,6 +178,29 @@
};
+template<typename T, typename UserData> class PODIntervalTree<T, UserData>::OverlapsSearchAdapter {
+public:
+ using IntervalType = PODInterval<T, UserData>;
+
+ OverlapsSearchAdapter(Vector<IntervalType>& result, const IntervalType& interval)
+ : m_result(result)
+ , m_interval(interval)
+ {
+ }
+
+ const T& lowValue() const { return m_interval.low(); }
+ const T& highValue() const { return m_interval.high(); }
+ void collectIfNeeded(const IntervalType& data) const
+ {
+ if (data.overlaps(m_interval))
+ m_result.append(data);
+ }
+
+private:
+ Vector<IntervalType>& m_result;
+ const IntervalType& m_interval;
+};
+
struct PODIntervalNodeUpdater {
template<typename Node> static bool update(Node& node)
{
Modified: trunk/Source/WebCore/platform/PODRedBlackTree.h (254482 => 254483)
--- trunk/Source/WebCore/platform/PODRedBlackTree.h 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/platform/PODRedBlackTree.h 2020-01-14 03:18:09 UTC (rev 254483)
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2010 Google Inc. All rights reserved.
- * Copyright (C) 2019 Apple Inc. All rights reserved.
+ * Copyright (C) 2019-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
@@ -39,17 +39,6 @@
// In debug mode, printing of the data contained in the tree is
// enabled. This makes use of WTF::TextStream.
//
-// Note that when complex types are stored in this red/black tree, it
-// is possible that single invocations of the "<" and "==" operators
-// will be insufficient to describe the ordering of elements in the
-// tree during queries. As a concrete example, consider the case where
-// intervals are stored in the tree sorted by low endpoint. The "<"
-// operator on the Interval class only compares the low endpoint, but
-// the "==" operator takes into account the high endpoint as well.
-// This makes the necessary logic for querying and deletion somewhat
-// more complex. In order to properly handle such situations, the
-// template argument "needsFullOrderingComparisons" must be true.
-//
// This red-black tree is designed to be _augmented_; subclasses can
// add additional and summary information to each node to efficiently
// store and index more complex data structures. A concrete example is
@@ -70,13 +59,11 @@
#endif
// FIXME: The prefix "POD" here isn't correct; this tree works with non-POD types too.
-// FIXME: Remove the unusual needsFullOrderingComparisons feature by changing the interval tree to use full ordering, sorting based on low, high, and data.
-// FIXME: Would be worthwhile to implement this on top of WTF::RedBlackTree rather than keeping two separate class templates around.
+// FIXME: Extend WTF::RedBlackTree and implement this on top of it rather than keeping two quite similar class templates around.
namespace WebCore {
-template<typename T, typename NodeUpdaterType, bool needsFullOrderingComparisons>
-class PODRedBlackTree {
+template<typename T, typename NodeUpdaterType> class PODRedBlackTree {
WTF_MAKE_NONCOPYABLE(PODRedBlackTree);
public:
PODRedBlackTree() = default;
@@ -86,7 +73,6 @@
clear();
}
- // Clearing will delete the contents of the tree.
void clear()
{
if (!m_root)
@@ -101,7 +87,7 @@
void add(const T& data)
{
- insertNode(new Node(T { data }));
+ add(T { data });
}
void add(T&& data)
@@ -135,14 +121,13 @@
bool checkInvariants() const
{
int blackCount;
- return checkInvariantsFromNode(m_root, &blackCount);
+ return checkInvariantsFromNode(m_root, blackCount);
}
- // Dumps the tree's contents to the logging info stream for
- // debugging purposes.
+ // Dumps the tree's contents to the logging info stream for debugging purposes.
void dump() const
{
- dumpFromNode(m_root, 0);
+ dumpSubtree(m_root, 0);
}
// Turns on or off verbose debugging of the tree, causing many
@@ -158,14 +143,10 @@
protected:
enum Color { Red, Black };
- // The base Node class which is stored in the tree. Nodes are only
- // an internal concept; users of the tree deal only with the data
- // they store in it.
class Node {
WTF_MAKE_FAST_ALLOCATED;
WTF_MAKE_NONCOPYABLE(Node);
public:
- // Constructor. Newly-created nodes are colored red.
explicit Node(T&& data)
: m_data(WTFMove(data))
{
@@ -176,7 +157,7 @@
T& data() { return m_data; }
- void moveDataFrom(Node* src) { m_data = WTFMove(src->m_data); }
+ void moveDataFrom(Node& src) { m_data = WTFMove(src.m_data); }
Node* left() const { return m_left; }
void setLeft(Node* node) { m_left = node; }
@@ -199,7 +180,7 @@
Node* root() const { return m_root; }
private:
- // This is the hook that subclasses should use when
+ // The update function is the hook that subclasses should use when
// augmenting the red-black tree with additional per-node summary
// information. For example, in the case of an interval tree, this
// is used to compute the maximum endpoint of the subtree below the
@@ -206,31 +187,16 @@
// given node based on the values in the left and right children. It
// is guaranteed that this will be called in the correct order to
// properly update such summary information based only on the values
- // in the left and right children. This method should return true if
+ // in the left and right children. The function should return true if
// the node's summary information changed.
- bool updateNode(Node* node)
+ static bool updateNode(Node& node)
{
- return NodeUpdaterType::update(*node);
+ return NodeUpdaterType::update(node);
}
- //----------------------------------------------------------------------
- // Generic binary search tree operations
- //
-
- // Searches the tree for the given datum.
Node* treeSearch(const T& data) const
{
- if (needsFullOrderingComparisons)
- return treeSearchFullComparisons(m_root, data);
-
- return treeSearchNormal(m_root, data);
- }
-
- // Searches the tree using the normal comparison operations,
- // suitable for simple data types such as numbers.
- Node* treeSearchNormal(Node* current, const T& data) const
- {
- while (current) {
+ for (auto* current = m_root; current; ) {
if (current->data() == data)
return current;
if (data < current->data())
@@ -238,32 +204,12 @@
else
current = current->right();
}
- return 0;
+ return nullptr;
}
- // Searches the tree using multiple comparison operations, required
- // for data types with more complex behavior such as intervals.
- Node* treeSearchFullComparisons(Node* current, const T& data) const
- {
- if (!current)
- return 0;
- if (data < current->data())
- return treeSearchFullComparisons(current->left(), data);
- if (current->data() < data)
- return treeSearchFullComparisons(current->right(), data);
- if (data == current->data())
- return current;
-
- // We may need to traverse both the left and right subtrees.
- Node* result = treeSearchFullComparisons(current->left(), data);
- if (!result)
- result = treeSearchFullComparisons(current->right(), data);
- return result;
- }
-
void treeInsert(Node* z)
{
- Node* y = 0;
+ Node* y = nullptr;
Node* x = m_root;
while (x) {
y = x;
@@ -297,8 +243,7 @@
return y;
}
- // Finds the minimum element in the sub-tree rooted at the given
- // node.
+ // Finds the minimum element in the sub-tree rooted at the given node.
static Node* treeMinimum(Node* x)
{
while (x->left())
@@ -314,16 +259,6 @@
return y;
}
- // Helper for maintaining the augmented red-black tree.
- void propagateUpdates(Node* start)
- {
- bool shouldContinue = true;
- while (start && shouldContinue) {
- shouldContinue = updateNode(start);
- start = start->parent();
- }
- }
-
//----------------------------------------------------------------------
// Red-Black tree operations
//
@@ -356,11 +291,17 @@
x->setParent(y);
// Update nodes lowest to highest.
- updateNode(x);
- updateNode(y);
+ updateNode(*x);
+ updateNode(*y);
return y;
}
+ static void propagateUpdates(Node* start)
+ {
+ while (start && updateNode(*start))
+ start = start->parent();
+ }
+
// Right-rotates the subtree rooted at y.
// Returns the new root of the subtree (y's left child).
Node* rightRotate(Node* y)
@@ -389,8 +330,8 @@
y->setParent(x);
// Update nodes lowest to highest.
- updateNode(y);
- updateNode(x);
+ updateNode(*y);
+ updateNode(*x);
return x;
}
@@ -399,7 +340,7 @@
{
treeInsert(x);
x->setColor(Red);
- updateNode(x);
+ updateNode(*x);
logIfVerbose(" PODRedBlackTree::InsertNode");
@@ -415,9 +356,9 @@
x->parent()->setColor(Black);
y->setColor(Black);
x->parent()->parent()->setColor(Red);
- updateNode(x->parent());
+ updateNode(*x->parent());
x = x->parent()->parent();
- updateNode(x);
+ updateNode(*x);
updateStart = x->parent();
} else {
if (x == x->parent()->right()) {
@@ -442,9 +383,9 @@
x->parent()->setColor(Black);
y->setColor(Black);
x->parent()->parent()->setColor(Red);
- updateNode(x->parent());
+ updateNode(*x->parent());
x = x->parent()->parent();
- updateNode(x);
+ updateNode(*x);
updateStart = x->parent();
} else {
if (x == x->parent()->left()) {
@@ -469,8 +410,7 @@
}
// Restores the red-black property to the tree after splicing out
- // a node. Note that x may be null, which is why xParent must be
- // supplied.
+ // a node. Note that x may be null, which is why xParent must be supplied.
void deleteFixup(Node* x, Node* xParent)
{
while (x != m_root && (!x || x->color() == Black)) {
@@ -594,9 +534,9 @@
y->parent()->setRight(x);
}
if (y != z) {
- z->moveDataFrom(y);
+ z->moveDataFrom(*y);
// This node has changed location in the tree and must be updated.
- updateNode(z);
+ updateNode(*z);
// The parent and its parents may now be out of date.
propagateUpdates(z->parent());
}
@@ -618,11 +558,11 @@
// Returns in the "blackCount" parameter the number of black
// children along all paths to all leaves of the given node.
- bool checkInvariantsFromNode(Node* node, int* blackCount) const
+ bool checkInvariantsFromNode(Node* node, int& blackCount) const
{
// Base case is a leaf node.
if (!node) {
- *blackCount = 1;
+ blackCount = 1;
return true;
}
@@ -640,14 +580,13 @@
return false;
}
- // Every simple path to a leaf node contains the same number of
- // black nodes.
+ // Every simple path to a leaf node contains the same number of black nodes.
int leftCount = 0, rightCount = 0;
- bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
- bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
+ bool leftValid = checkInvariantsFromNode(node->left(), leftCount);
+ bool rightValid = checkInvariantsFromNode(node->right(), rightCount);
if (!leftValid || !rightValid)
return false;
- *blackCount = leftCount + (node->color() == Black ? 1 : 0);
+ blackCount = leftCount + (node->color() == Black ? 1 : 0);
return leftCount == rightCount;
}
@@ -665,8 +604,7 @@
#ifndef NDEBUG
- // Dumps the subtree rooted at the given node.
- void dumpFromNode(Node* node, int indentation) const
+ void dumpSubtree(Node* node, int indentation) const
{
StringBuilder builder;
for (int i = 0; i < indentation; i++)
@@ -681,16 +619,13 @@
}
LOG_ERROR("%s", builder.toString().utf8().data());
if (node) {
- dumpFromNode(node->left(), indentation + 2);
- dumpFromNode(node->right(), indentation + 2);
+ dumpSubtree(node->left(), indentation + 2);
+ dumpSubtree(node->right(), indentation + 2);
}
}
#endif
- //----------------------------------------------------------------------
- // Data members
-
Node* m_root { nullptr };
#ifndef NDEBUG
bool m_verboseDebugging { false };
Modified: trunk/Source/WebCore/rendering/FloatingObjects.h (254482 => 254483)
--- trunk/Source/WebCore/rendering/FloatingObjects.h 2020-01-14 03:15:36 UTC (rev 254482)
+++ trunk/Source/WebCore/rendering/FloatingObjects.h 2020-01-14 03:18:09 UTC (rev 254483)
@@ -23,7 +23,6 @@
#pragma once
-#include "PODInterval.h"
#include "RootInlineBox.h"
#include <wtf/ListHashSet.h>
#include <wtf/WeakPtr.h>
@@ -33,6 +32,7 @@
class RenderBlockFlow;
class RenderBox;
+template<typename, typename> class PODInterval;
template<typename, typename> class PODIntervalTree;
class FloatingObject {
