https://bugs.webkit.org/show_bug.cgi?id=65871
PerformanceTests:
Patch by Alexandru Chiculita <achicu@adobe.com> on 2011-08-09
Reviewed by Dave Hyatt.
* Layout/floats.html: Added the nested divs, so that we can test the propagation impact of the floats tree.
Source/WebCore:
Added an interval tree in the FloatingObjects structure. Also added new mechanisms to make
sure the tree is updated correctly when a float is repositioned.
Changed the PODIntervalTree to support giving a search adapter that can be implemented by the
client. I'm not adding a different bug for that because PODIntervalTree is not used anywhere else
and would be hard to test that the change is not breaking anything.
Patch by Alexandru Chiculita <achicu@adobe.com> on 2011-08-09
Reviewed by Dave Hyatt.
No new tests, just a refactor on the floating objects data structure.
* WebCore.xcodeproj/project.pbxproj:
* platform/PODIntervalTree.h:
(WebCore::PODIntervalSearchAdapter::PODIntervalSearchAdapter):
(WebCore::PODIntervalSearchAdapter::lowValue):
(WebCore::PODIntervalSearchAdapter::highValue):
(WebCore::PODIntervalSearchAdapter::collectIfNeeded):
(WebCore::PODIntervalTree::PODIntervalTree):
(WebCore::PODIntervalTree::allOverlaps):
(WebCore::PODIntervalTree::allOverlapsWithAdapter):
(WebCore::PODIntervalTree::searchForOverlapsFrom):
* platform/PODRedBlackTree.h:
(WebCore::PODRedBlackTree::PODRedBlackTree):
(WebCore::PODRedBlackTree::clear):
(WebCore::PODRedBlackTree::isInitialized):
(WebCore::PODRedBlackTree::initIfNeeded):
(WebCore::PODRedBlackTree::add):
(WebCore::PODRedBlackTree::remove):
(WebCore::PODRedBlackTree::contains):
(WebCore::PODRedBlackTree::visitInorder):
(WebCore::PODRedBlackTree::size):
(WebCore::PODRedBlackTree::checkInvariants):
(WebCore::PODRedBlackTree::dump):
* rendering/RenderBlock.cpp:
(WebCore::RenderBlock::styleDidChange):
(WebCore::RenderBlock::addOverflowFromFloats):
(WebCore::RenderBlock::repaintOverhangingFloats):
(WebCore::RenderBlock::paintFloats):
(WebCore::RenderBlock::selectionGaps):
(WebCore::RenderBlock::insertFloatingObject):
(WebCore::RenderBlock::removeFloatingObject):
(WebCore::RenderBlock::removeFloatingObjectsBelow):
(WebCore::RenderBlock::positionNewFloats):
(WebCore::::collectIfNeeded):
(WebCore::RenderBlock::logicalLeftOffsetForLine):
(WebCore::RenderBlock::logicalRightOffsetForLine):
(WebCore::RenderBlock::nextFloatLogicalBottomBelow):
(WebCore::RenderBlock::lowestFloatLogicalBottom):
(WebCore::RenderBlock::addPositionedFloats):
(WebCore::RenderBlock::clearFloats):
(WebCore::RenderBlock::addOverhangingFloats):
(WebCore::RenderBlock::hasOverhangingFloat):
(WebCore::RenderBlock::addIntrudingFloats):
(WebCore::RenderBlock::markSiblingsWithFloatsForLayout):
(WebCore::RenderBlock::hitTestFloats):
(WebCore::RenderBlock::adjustForBorderFit):
(WebCore::RenderBlock::FloatingObjects::clear):
(WebCore::RenderBlock::FloatingObjects::intervalForFloatingObject):
(WebCore::RenderBlock::FloatingObjects::addPlacedObject):
(WebCore::RenderBlock::FloatingObjects::removePlacedObject):
(WebCore::RenderBlock::FloatingObjects::add):
(WebCore::RenderBlock::FloatingObjects::remove):
(WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTree):
(WebCore::::string):
* rendering/RenderBlock.h:
(WebCore::RenderBlock::FloatingObject::FloatingObject):
(WebCore::RenderBlock::FloatingObject::setX):
(WebCore::RenderBlock::FloatingObject::setY):
(WebCore::RenderBlock::FloatingObject::setWidth):
(WebCore::RenderBlock::FloatingObject::setHeight):
(WebCore::RenderBlock::FloatingObject::setFrameRect):
(WebCore::RenderBlock::FloatingObject::isInPlacedTree):
(WebCore::RenderBlock::FloatingObject::setIsInPlacedTree):
(WebCore::RenderBlock::FloatIntervalSearchAdapter::FloatIntervalSearchAdapter):
(WebCore::RenderBlock::FloatIntervalSearchAdapter::lowValue):
(WebCore::RenderBlock::FloatIntervalSearchAdapter::highValue):
(WebCore::RenderBlock::FloatingObjects::FloatingObjects):
(WebCore::RenderBlock::FloatingObjects::setHorizontalWritingMode):
(WebCore::RenderBlock::FloatingObjects::set):
(WebCore::RenderBlock::FloatingObjects::placedFloatsTree):
(WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTreeIfNeeded):
* rendering/RenderBlockLineLayout.cpp:
(WebCore::RenderBlock::layoutRunsAndFloatsInRange):
(WebCore::RenderBlock::linkToEndLineIfNeeded):
(WebCore::RenderBlock::matchedEndLine):
(WebCore::RenderBlock::positionNewFloatOnLine):
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@92696
268f45cc-cd09-0410-ab3c-
d52691b4dbfc
+2011-08-09 Alexandru Chiculita <achicu@adobe.com>
+
+ Fixing 65868 REGRESSION(r92610) caused by 65668 - Optimize floating elements lookup
+ https://bugs.webkit.org/show_bug.cgi?id=65871
+
+ Reviewed by Dave Hyatt.
+
+ * Layout/floats.html: Added the nested divs, so that we can test the propagation impact of the floats tree.
+
2011-08-08 Sheriff Bot <webkit.review.bot@gmail.com>
Unreviewed, rolling out r92610.
return el;
}
- function createSet(width, height)
+ function createSet(width, height, nested)
{
var container = createElement("div", document.body, "container");
for (var y = 0; y < height; ++y) {
for (var x = 0; x < width; ++x)
createElement("div", container, "float", "float" + x + "_" + y);
+
+ var nestedContainer = container;
+ for ( ; nested > 0; --nested)
+ nestedContainer = createElement("div", nestedContainer, "nested", "nested" + x + "_" + nested);
+
createElement("div", container, "float-end", "end" + x)
}
}
return str1;
}
- function test(width, height)
+ function test(width, height, nested)
{
+ nested = nested || 0;
+
document.getElementById("test_panel").style.display = "none";
document.getElementById("framerate_panel").style.display = "block";
- createSet(width, height);
+ createSet(width, height, nested);
var updates = 0;
var startTime = new Date();
<button onclick="test(20, 100)">20 by 100</button>
<button onclick="test(50, 100)">50 by 100</button>
<button onclick="test(100, 100)">100 by 100</button>
+ <p>Nested divs:</p>
+ <button onclick="test(2, 100, 100)">2 by 100, 100 nested</button>
+ <button onclick="test(20, 100, 100)">20 by 100, 100 nested</button>
+ <button onclick="test(50, 100, 100)">50 by 100, 100 nested</button>
+ <button onclick="test(100, 100, 100)">100 by 100, 100 nested</button>
</div>
</body>
</html>
\ No newline at end of file
+2011-08-09 Alexandru Chiculita <achicu@adobe.com>
+
+ Fixing 65868 REGRESSION(r92610) caused by 65668 - Optimize floating elements lookup
+ https://bugs.webkit.org/show_bug.cgi?id=65871
+
+ Added an interval tree in the FloatingObjects structure. Also added new mechanisms to make
+ sure the tree is updated correctly when a float is repositioned.
+
+ Changed the PODIntervalTree to support giving a search adapter that can be implemented by the
+ client. I'm not adding a different bug for that because PODIntervalTree is not used anywhere else
+ and would be hard to test that the change is not breaking anything.
+
+ Reviewed by Dave Hyatt.
+
+ No new tests, just a refactor on the floating objects data structure.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * platform/PODIntervalTree.h:
+ (WebCore::PODIntervalSearchAdapter::PODIntervalSearchAdapter):
+ (WebCore::PODIntervalSearchAdapter::lowValue):
+ (WebCore::PODIntervalSearchAdapter::highValue):
+ (WebCore::PODIntervalSearchAdapter::collectIfNeeded):
+ (WebCore::PODIntervalTree::PODIntervalTree):
+ (WebCore::PODIntervalTree::allOverlaps):
+ (WebCore::PODIntervalTree::allOverlapsWithAdapter):
+ (WebCore::PODIntervalTree::searchForOverlapsFrom):
+ * platform/PODRedBlackTree.h:
+ (WebCore::PODRedBlackTree::PODRedBlackTree):
+ (WebCore::PODRedBlackTree::clear):
+ (WebCore::PODRedBlackTree::isInitialized):
+ (WebCore::PODRedBlackTree::initIfNeeded):
+ (WebCore::PODRedBlackTree::add):
+ (WebCore::PODRedBlackTree::remove):
+ (WebCore::PODRedBlackTree::contains):
+ (WebCore::PODRedBlackTree::visitInorder):
+ (WebCore::PODRedBlackTree::size):
+ (WebCore::PODRedBlackTree::checkInvariants):
+ (WebCore::PODRedBlackTree::dump):
+ * rendering/RenderBlock.cpp:
+ (WebCore::RenderBlock::styleDidChange):
+ (WebCore::RenderBlock::addOverflowFromFloats):
+ (WebCore::RenderBlock::repaintOverhangingFloats):
+ (WebCore::RenderBlock::paintFloats):
+ (WebCore::RenderBlock::selectionGaps):
+ (WebCore::RenderBlock::insertFloatingObject):
+ (WebCore::RenderBlock::removeFloatingObject):
+ (WebCore::RenderBlock::removeFloatingObjectsBelow):
+ (WebCore::RenderBlock::positionNewFloats):
+ (WebCore::::collectIfNeeded):
+ (WebCore::RenderBlock::logicalLeftOffsetForLine):
+ (WebCore::RenderBlock::logicalRightOffsetForLine):
+ (WebCore::RenderBlock::nextFloatLogicalBottomBelow):
+ (WebCore::RenderBlock::lowestFloatLogicalBottom):
+ (WebCore::RenderBlock::addPositionedFloats):
+ (WebCore::RenderBlock::clearFloats):
+ (WebCore::RenderBlock::addOverhangingFloats):
+ (WebCore::RenderBlock::hasOverhangingFloat):
+ (WebCore::RenderBlock::addIntrudingFloats):
+ (WebCore::RenderBlock::markSiblingsWithFloatsForLayout):
+ (WebCore::RenderBlock::hitTestFloats):
+ (WebCore::RenderBlock::adjustForBorderFit):
+ (WebCore::RenderBlock::FloatingObjects::clear):
+ (WebCore::RenderBlock::FloatingObjects::intervalForFloatingObject):
+ (WebCore::RenderBlock::FloatingObjects::addPlacedObject):
+ (WebCore::RenderBlock::FloatingObjects::removePlacedObject):
+ (WebCore::RenderBlock::FloatingObjects::add):
+ (WebCore::RenderBlock::FloatingObjects::remove):
+ (WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTree):
+ (WebCore::::string):
+ * rendering/RenderBlock.h:
+ (WebCore::RenderBlock::FloatingObject::FloatingObject):
+ (WebCore::RenderBlock::FloatingObject::setX):
+ (WebCore::RenderBlock::FloatingObject::setY):
+ (WebCore::RenderBlock::FloatingObject::setWidth):
+ (WebCore::RenderBlock::FloatingObject::setHeight):
+ (WebCore::RenderBlock::FloatingObject::setFrameRect):
+ (WebCore::RenderBlock::FloatingObject::isInPlacedTree):
+ (WebCore::RenderBlock::FloatingObject::setIsInPlacedTree):
+ (WebCore::RenderBlock::FloatIntervalSearchAdapter::FloatIntervalSearchAdapter):
+ (WebCore::RenderBlock::FloatIntervalSearchAdapter::lowValue):
+ (WebCore::RenderBlock::FloatIntervalSearchAdapter::highValue):
+ (WebCore::RenderBlock::FloatingObjects::FloatingObjects):
+ (WebCore::RenderBlock::FloatingObjects::setHorizontalWritingMode):
+ (WebCore::RenderBlock::FloatingObjects::set):
+ (WebCore::RenderBlock::FloatingObjects::placedFloatsTree):
+ (WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTreeIfNeeded):
+ * rendering/RenderBlockLineLayout.cpp:
+ (WebCore::RenderBlock::layoutRunsAndFloatsInRange):
+ (WebCore::RenderBlock::linkToEndLineIfNeeded):
+ (WebCore::RenderBlock::matchedEndLine):
+ (WebCore::RenderBlock::positionNewFloatOnLine):
+
2011-08-08 Ryosuke Niwa <rniwa@webkit.org>
Repeated copy and paste result in nested font elements
BCB773620C17853D00132BA4 /* JSNodeFilterCondition.h in Headers */ = {isa = PBXBuildFile; fileRef = BCB7735F0C17853D00132BA4 /* JSNodeFilterCondition.h */; };
BCB773630C17853D00132BA4 /* JSNodeFilterCustom.cpp in Sources */ = {isa = PBXBuildFile; fileRef = BCB773600C17853D00132BA4 /* JSNodeFilterCustom.cpp */; };
BCB92D4F1293550B00C8387F /* FontBaseline.h in Headers */ = {isa = PBXBuildFile; fileRef = BCB92D4E1293550B00C8387F /* FontBaseline.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ BCBB8AB813F1AFB000734DF0 /* PODArena.h in Headers */ = {isa = PBXBuildFile; fileRef = BCBB8AB413F1AFB000734DF0 /* PODArena.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ BCBB8AB913F1AFB000734DF0 /* PODInterval.h in Headers */ = {isa = PBXBuildFile; fileRef = BCBB8AB513F1AFB000734DF0 /* PODInterval.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ BCBB8ABA13F1AFB000734DF0 /* PODIntervalTree.h in Headers */ = {isa = PBXBuildFile; fileRef = BCBB8AB613F1AFB000734DF0 /* PODIntervalTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ BCBB8ABB13F1AFB000734DF0 /* PODRedBlackTree.h in Headers */ = {isa = PBXBuildFile; fileRef = BCBB8AB713F1AFB000734DF0 /* PODRedBlackTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
BCBD21AB0E417AD400A070F2 /* KURLHash.h in Headers */ = {isa = PBXBuildFile; fileRef = BCBD21AA0E417AD400A070F2 /* KURLHash.h */; settings = {ATTRIBUTES = (Private, ); }; };
BCBFB53C0DCD29CF0019B3E5 /* JSDOMWindowShell.cpp in Sources */ = {isa = PBXBuildFile; fileRef = BCBFB53A0DCD29CF0019B3E5 /* JSDOMWindowShell.cpp */; };
BCBFB53D0DCD29CF0019B3E5 /* JSDOMWindowShell.h in Headers */ = {isa = PBXBuildFile; fileRef = BCBFB53B0DCD29CF0019B3E5 /* JSDOMWindowShell.h */; settings = {ATTRIBUTES = (Private, ); }; };
BCB7735F0C17853D00132BA4 /* JSNodeFilterCondition.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = JSNodeFilterCondition.h; sourceTree = "<group>"; };
BCB773600C17853D00132BA4 /* JSNodeFilterCustom.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = JSNodeFilterCustom.cpp; sourceTree = "<group>"; };
BCB92D4E1293550B00C8387F /* FontBaseline.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FontBaseline.h; sourceTree = "<group>"; };
+ BCBB8AB413F1AFB000734DF0 /* PODArena.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODArena.h; sourceTree = "<group>"; };
+ BCBB8AB513F1AFB000734DF0 /* PODInterval.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODInterval.h; sourceTree = "<group>"; };
+ BCBB8AB613F1AFB000734DF0 /* PODIntervalTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODIntervalTree.h; sourceTree = "<group>"; };
+ BCBB8AB713F1AFB000734DF0 /* PODRedBlackTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODRedBlackTree.h; sourceTree = "<group>"; };
BCBD21AA0E417AD400A070F2 /* KURLHash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = KURLHash.h; sourceTree = "<group>"; };
BCBFB53A0DCD29CF0019B3E5 /* JSDOMWindowShell.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSDOMWindowShell.cpp; sourceTree = "<group>"; };
BCBFB53B0DCD29CF0019B3E5 /* JSDOMWindowShell.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSDOMWindowShell.h; sourceTree = "<group>"; };
1AD8F81A11CAB9E900E93E54 /* PlatformStrategies.cpp */,
1AD8F81911CAB9E900E93E54 /* PlatformStrategies.h */,
935C476A09AC4D4F00A6AAB4 /* PlatformWheelEvent.h */,
+ BCBB8AB413F1AFB000734DF0 /* PODArena.h */,
+ BCBB8AB513F1AFB000734DF0 /* PODInterval.h */,
+ BCBB8AB613F1AFB000734DF0 /* PODIntervalTree.h */,
+ BCBB8AB713F1AFB000734DF0 /* PODRedBlackTree.h */,
0668E1890ADD9624004128E0 /* PopupMenu.h */,
ABC128760B33AA6D00C693D5 /* PopupMenuClient.h */,
BC3BE12A0E98092F00835588 /* PopupMenuStyle.h */,
977E2E0F12F0FC9C00C13379 /* XSSAuditor.h in Headers */,
FD537353137B651800008DCE /* ZeroPole.h in Headers */,
59DE790613F16C8C0007FCDF /* JavaMethodJSC.h in Headers */,
+ BCBB8AB813F1AFB000734DF0 /* PODArena.h in Headers */,
+ BCBB8AB913F1AFB000734DF0 /* PODInterval.h in Headers */,
+ BCBB8ABA13F1AFB000734DF0 /* PODIntervalTree.h in Headers */,
+ BCBB8ABB13F1AFB000734DF0 /* PODRedBlackTree.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
struct ValueToString;
#endif
+template <class T, class UserData = void*>
+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;
+};
+
// 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.
// Typedef to reduce typing when declaring intervals to be stored in
// this tree.
typedef PODInterval<T, UserData> IntervalType;
+ typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
+ PODIntervalTree(UninitializedTreeEnum unitializedTree)
+ : PODRedBlackTree<IntervalType>(unitializedTree)
+ {
+ init();
+ }
+
PODIntervalTree()
: PODRedBlackTree<IntervalType>()
{
{
// Explicit dereference of "this" required because of
// inheritance rules in template classes.
- searchForOverlapsFrom(this->root(), interval, result);
+ IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
+ searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter);
+ }
+
+ template <class AdapterType>
+ void allOverlapsWithAdapter(AdapterType& adapter) const
+ {
+ // Explicit dereference of "this" required because of
+ // inheritance rules in template classes.
+ searchForOverlapsFrom<AdapterType>(this->root(), adapter);
}
// Helper to create interval objects.
// Starting from the given node, adds all overlaps with the given
// interval to the result vector. The intervals are sorted by
// increasing low endpoint.
- void searchForOverlapsFrom(IntervalNode* node, const IntervalType& interval, Vector<IntervalType>& res) const
+ template <class AdapterType>
+ void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
{
if (!node)
return;
if (left
// This is phrased this way to avoid the need for operator
// <= on type T.
- && !(left->data().maxHigh() < interval.low()))
- searchForOverlapsFrom(left, interval, res);
+ && !(left->data().maxHigh() < adapter.lowValue()))
+ searchForOverlapsFrom<AdapterType>(left, adapter);
// Check for overlap with current node.
- if (node->data().overlaps(interval))
- res.append(node->data());
+ adapter.collectIfNeeded(node->data());
// See whether we need to traverse the right subtree.
// This is phrased this way to avoid the need for operator <=
// on type T.
- if (!(interval.high() < node->data().low()))
- searchForOverlapsFrom(node->right(), interval, res);
+ if (!(adapter.highValue() < node->data().low()))
+ searchForOverlapsFrom<AdapterType>(node->right(), adapter);
}
virtual bool updateNode(IntervalNode* node)
struct ValueToString;
#endif
+enum UninitializedTreeEnum {
+ UninitializedTree
+};
+
template<class T>
class PODRedBlackTree {
public:
virtual ~Visitor() { }
};
+ // Constructs a new red-black tree without allocating an arena.
+ // isInitialized will return false in this case. initIfNeeded can be used
+ // to init the structure. This constructor is usefull for creating
+ // lazy initialized tree.
+ PODRedBlackTree(UninitializedTreeEnum)
+ : m_root(0)
+ , m_needsFullOrderingComparisons(false)
+#ifndef NDEBUG
+ , m_verboseDebugging(false)
+#endif
+ {
+ }
+
// Constructs a new red-black tree, allocating temporary objects
// from a newly constructed PODArena.
PODRedBlackTree()
virtual ~PODRedBlackTree() { }
+ // Clearing will delete the contents of the tree. After this call
+ // isInitialized will return false.
+ void clear()
+ {
+ m_arena = 0;
+ m_root = 0;
+ }
+
+ bool isInitialized() const
+ {
+ return m_arena;
+ }
+
+ void initIfNeeded()
+ {
+ if (!m_arena)
+ m_arena = PODArena::create();
+ }
+
void add(const T& data)
{
+ ASSERT(isInitialized());
Node* node = m_arena->allocateObject<Node, T>(data);
insertNode(node);
}
// Returns true if the datum was found in the tree.
bool remove(const T& data)
{
+ ASSERT(isInitialized());
Node* node = treeSearch(data);
if (node) {
deleteNode(node);
return false;
}
- bool contains(const T& data) const { return treeSearch(data); }
+ bool contains(const T& data) const
+ {
+ ASSERT(isInitialized());
+ return treeSearch(data);
+ }
void visitInorder(Visitor* visitor) const
{
+ ASSERT(isInitialized());
if (!m_root)
return;
visitInorderImpl(m_root, visitor);
int size() const
{
+ ASSERT(isInitialized());
Counter counter;
visitInorder(&counter);
return counter.count();
virtual bool checkInvariants() const
{
+ ASSERT(isInitialized());
int blackCount;
return checkInvariantsFromNode(m_root, &blackCount);
}
// debugging purposes.
void dump() const
{
- dumpFromNode(m_root, 0);
+ if (m_arena)
+ dumpFromNode(m_root, 0);
}
// Turns on or off verbose debugging of the tree, causing many
bool canPropagateFloatIntoSibling = !isFloatingOrPositioned() && !avoidsFloats();
if (diff == StyleDifferenceLayout && s_canPropagateFloatIntoSibling && !canPropagateFloatIntoSibling && hasOverhangingFloats()) {
RenderBlock* parentBlock = this;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (RenderObject* curr = parent(); curr && !curr->isRenderView(); curr = curr->parent()) {
if (!m_floatingObjects)
return;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
// FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
// in this block. Better yet would be to push extra state for the containers of other floats.
LayoutStateDisabler layoutStateDisabler(view());
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
if (!m_floatingObjects)
return;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
for (RenderBlock* cb = containingBlock(); cb && !cb->isRenderView(); cb = cb->containingBlock())
clipOutPositionedObjects(paintInfo, IntPoint(cb->x(), cb->y()), cb->m_positionedObjects.get()); // FIXME: Not right for flipped writing modes.
if (m_floatingObjects) {
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
// Create the list of special objects if we don't aleady have one
if (!m_floatingObjects)
- m_floatingObjects = adoptPtr(new FloatingObjects);
+ m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
else {
// Don't insert the object again if it's already in the list
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
if (it != floatingObjectSet.end())
return *it;
newObj->m_isDescendant = true;
newObj->m_renderer = o;
- m_floatingObjects->increaseObjectsCount(newObj->type());
- m_floatingObjects->set().add(newObj);
+ m_floatingObjects->add(newObj);
return newObj;
}
void RenderBlock::removeFloatingObject(RenderBox* o)
{
if (m_floatingObjects) {
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
- FloatingObjectSet::iterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
if (it != floatingObjectSet.end()) {
FloatingObject* r = *it;
if (childrenInline()) {
}
markLinesDirtyInBlockRange(0, logicalBottom);
}
- m_floatingObjects->decreaseObjectsCount(r->type());
- floatingObjectSet.remove(it);
+ m_floatingObjects->remove(r);
ASSERT(!r->m_originatingLine);
delete r;
}
if (!m_floatingObjects)
return;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObject* curr = floatingObjectSet.last();
while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
- m_floatingObjects->decreaseObjectsCount(curr->type());
- floatingObjectSet.removeLast();
+ m_floatingObjects->remove(curr);
ASSERT(!curr->m_originatingLine);
delete curr;
curr = floatingObjectSet.last();
if (!m_floatingObjects)
return false;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
if (floatingObjectSet.isEmpty())
return false;
setLogicalTopForFloat(floatingObject, logicalTop);
setLogicalHeightForFloat(floatingObject, logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
- floatingObject->setIsPlaced();
+ m_floatingObjects->addPlacedObject(floatingObject);
// If the child moved, we have to repaint it.
if (childBox->checkForRepaintDuringLayout())
}
#endif
-// FIXME: The logicalLeftOffsetForLine/logicalRightOffsetForLine functions are very slow if there are many floats
-// present. We need to add a structure to floating objects to represent "lines" of floats. Then instead of checking
-// each float individually, we'd just walk backwards through the "lines" and stop when we hit a line that is fully above
-// the vertical offset that we'd like to check. Computing the "lines" would be rather complicated, but could replace the left
-// objects and right objects count hack that is currently used here.
+template <RenderBlock::FloatingObject::Type FloatTypeValue>
+inline void RenderBlock::FloatIntervalSearchAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval) const
+{
+ const FloatingObject* r = interval.data();
+ if (r->type() == FloatTypeValue && interval.low() <= m_value && m_value < interval.high()) {
+ // All the objects returned from the tree should be already placed.
+ ASSERT(r->isPlaced() && m_renderer->logicalTopForFloat(r) <= m_value && m_renderer->logicalBottomForFloat(r) > m_value);
+
+ if (FloatTypeValue == FloatingObject::FloatLeft
+ && m_renderer->logicalRightForFloat(r) > m_offset) {
+ m_offset = m_renderer->logicalRightForFloat(r);
+ if (m_heightRemaining)
+ *m_heightRemaining = m_renderer->logicalBottomForFloat(r) - m_value;
+ }
+
+ if (FloatTypeValue == FloatingObject::FloatRight
+ && m_renderer->logicalLeftForFloat(r) < m_offset) {
+ m_offset = m_renderer->logicalLeftForFloat(r);
+ if (m_heightRemaining)
+ *m_heightRemaining = m_renderer->logicalBottomForFloat(r) - m_value;
+ }
+ }
+}
+
LayoutUnit RenderBlock::logicalLeftOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, bool applyTextIndent, LayoutUnit* heightRemaining) const
{
LayoutUnit left = fixedOffset;
if (heightRemaining)
*heightRemaining = 1;
- // We know the list is non-empty, since we have "left" objects to search for.
- // Therefore we can assume that begin != end, and that we can do at least one
- // decrement.
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
- FloatingObjectSetIterator begin = floatingObjectSet.begin();
- FloatingObjectSetIterator it = floatingObjectSet.end();
- do {
- --it;
- FloatingObject* r = *it;
- if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
- && r->type() == FloatingObject::FloatLeft
- && logicalRightForFloat(r) > left) {
- left = max(left, logicalRightForFloat(r));
- if (heightRemaining)
- *heightRemaining = logicalBottomForFloat(r) - logicalTop;
- }
- } while (it != begin);
+ FloatIntervalSearchAdapter<FloatingObject::FloatLeft> adapter(this, logicalTop, left, heightRemaining);
+ m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
}
if (applyTextIndent && style()->isLeftToRightDirection()) {
if (m_floatingObjects && m_floatingObjects->hasRightObjects()) {
if (heightRemaining)
*heightRemaining = 1;
-
- // We know the list is non-empty, since we have "right" objects to search for.
- // Therefore we can assume that begin != end, and that we can do at least one
- // decrement.
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
- FloatingObjectSetIterator begin = floatingObjectSet.begin();
- FloatingObjectSetIterator it = floatingObjectSet.end();
- do {
- --it;
- FloatingObject* r = *it;
- if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
- && r->type() == FloatingObject::FloatRight
- && logicalLeftForFloat(r) < right) {
- right = min(right, logicalLeftForFloat(r));
- if (heightRemaining)
- *heightRemaining = logicalBottomForFloat(r) - logicalTop;
- }
- } while (it != begin);
+
+ FloatIntervalSearchAdapter<FloatingObject::FloatRight> adapter(this, logicalTop, right, heightRemaining);
+ m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
}
if (applyTextIndent && !style()->isLeftToRightDirection()) {
return 0;
int bottom = INT_MAX;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
if (!m_floatingObjects)
return 0;
int lowestFloatBottom = 0;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
setLogicalLeftForFloat(floatingObject, logicalLeftForChild(positionedObject) - marginLogicalLeftForChild(positionedObject));
setLogicalTopForFloat(floatingObject, logicalTopForChild(positionedObject) - marginBeforeForChild(positionedObject));
setLogicalHeightForFloat(floatingObject, logicalHeightForChild(positionedObject) + marginBeforeForChild(positionedObject) + marginAfterForChild(positionedObject));
- floatingObject->setIsPlaced(true);
+
+ m_floatingObjects->addPlacedObject(floatingObject);
m_hasPositionedFloats = true;
}
void RenderBlock::clearFloats(BlockLayoutPass layoutPass)
{
+ if (m_floatingObjects)
+ m_floatingObjects->setHorizontalWritingMode(isHorizontalWritingMode());
+
// Clear our positioned floats boolean.
m_hasPositionedFloats = false;
RendererToFloatInfoMap floatMap;
if (m_floatingObjects) {
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
if (childrenInline()) {
- FloatingObjectSet::iterator end = floatingObjectSet.end();
- for (FloatingObjectSet::iterator it = floatingObjectSet.begin(); it != end; ++it) {
+ FloatingObjectSetIterator end = floatingObjectSet.end();
+ for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* f = *it;
floatMap.add(f->m_renderer, f);
}
int changeLogicalTop = numeric_limits<int>::max();
int changeLogicalBottom = numeric_limits<int>::min();
if (m_floatingObjects) {
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* f = *it;
// We create the floating object list lazily.
if (!m_floatingObjects)
- m_floatingObjects = adoptPtr(new FloatingObjects);
+ m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
- m_floatingObjects->increaseObjectsCount(floatingObj->type());
- m_floatingObjects->set().add(floatingObj);
+ m_floatingObjects->add(floatingObj);
}
} else {
if (makeChildPaintOtherFloats && !r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer() &&
if (!m_floatingObjects || hasColumns() || !parent())
return false;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(renderer);
if (it == floatingObjectSet.end())
return false;
logicalLeftOffset += (isHorizontalWritingMode() ? marginLeft() : marginTop());
- FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
+ const FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
FloatingObjectSetIterator prevEnd = prevSet.end();
for (FloatingObjectSetIterator prevIt = prevSet.begin(); prevIt != prevEnd; ++prevIt) {
FloatingObject* r = *prevIt;
// We create the floating object list lazily.
if (!m_floatingObjects)
- m_floatingObjects = adoptPtr(new FloatingObjects);
- m_floatingObjects->increaseObjectsCount(floatingObj->type());
- m_floatingObjects->set().add(floatingObj);
+ m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
+ m_floatingObjects->add(floatingObj);
}
}
}
void RenderBlock::markSiblingsWithFloatsForLayout()
{
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
if (logicalBottomForFloat(*it) > logicalHeight()) {
adjustedLocation += toSize(toRenderView(this)->frameView()->scrollPosition());
}
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator begin = floatingObjectSet.begin();
for (FloatingObjectSetIterator it = floatingObjectSet.end(); it != begin;) {
--it;
}
if (m_floatingObjects) {
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
inline void RenderBlock::FloatingObjects::clear()
{
m_set.clear();
+ m_placedFloatsTree.clear();
m_leftObjectsCount = 0;
m_rightObjectsCount = 0;
m_positionedObjectsCount = 0;
m_positionedObjectsCount--;
}
+inline RenderBlock::FloatingObjectInterval RenderBlock::FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
+{
+ if (m_horizontalWritingMode)
+ return RenderBlock::FloatingObjectInterval(floatingObject->y(), floatingObject->maxY(), floatingObject);
+ return RenderBlock::FloatingObjectInterval(floatingObject->x(), floatingObject->maxX(), floatingObject);
+}
+
+void RenderBlock::FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
+{
+ ASSERT(!floatingObject->isInPlacedTree());
+
+ floatingObject->setIsPlaced(true);
+ if (m_placedFloatsTree.isInitialized())
+ m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
+
+#ifndef NDEBUG
+ floatingObject->setIsInPlacedTree(true);
+#endif
+}
+
+void RenderBlock::FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
+{
+ ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
+
+ if (m_placedFloatsTree.isInitialized()) {
+ bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
+ ASSERT_UNUSED(removed, removed);
+ }
+
+ floatingObject->setIsPlaced(false);
+#ifndef NDEBUG
+ floatingObject->setIsInPlacedTree(false);
+#endif
+}
+
+inline void RenderBlock::FloatingObjects::add(FloatingObject* floatingObject)
+{
+ increaseObjectsCount(floatingObject->type());
+ m_set.add(floatingObject);
+ if (floatingObject->isPlaced())
+ addPlacedObject(floatingObject);
+}
+
+inline void RenderBlock::FloatingObjects::remove(FloatingObject* floatingObject)
+{
+ decreaseObjectsCount(floatingObject->type());
+ m_set.remove(floatingObject);
+ ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
+ if (floatingObject->isPlaced())
+ removePlacedObject(floatingObject);
+}
+
+void RenderBlock::FloatingObjects::computePlacedFloatsTree()
+{
+ ASSERT(!m_placedFloatsTree.isInitialized());
+ if (m_set.isEmpty())
+ return;
+ m_placedFloatsTree.initIfNeeded();
+ FloatingObjectSetIterator it = m_set.begin();
+ FloatingObjectSetIterator end = m_set.end();
+ for (; it != end; ++it) {
+ FloatingObject* floatingObject = *it;
+ if (floatingObject->isPlaced())
+ m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
+ }
+}
+
TextRun RenderBlock::constructTextRun(RenderObject* context, const Font& font, const UChar* characters, int length, RenderStyle* style, TextRun::ExpansionBehavior expansion, TextRunFlags flags)
{
ASSERT(style);
root->showLineTreeAndMark(markedBox1, markedLabel1, markedBox2, markedLabel2, obj, 1);
}
+// These helpers are only used by the PODIntervalTree for debugging purposes.
+String ValueToString<int>::string(const int value)
+{
+ return String::number(value);
+}
+
+String ValueToString<RenderBlock::FloatingObject*>::string(const RenderBlock::FloatingObject* floatingObject)
+{
+ return String::format("%p (%dx%d %dx%d)", floatingObject, floatingObject->x(), floatingObject->y(), floatingObject->maxX(), floatingObject->maxY());
+}
+
#endif
} // namespace WebCore
#define RenderBlock_h
#include "GapRects.h"
+#include "PODIntervalTree.h"
#include "RenderBox.h"
#include "RenderLineBoxList.h"
#include "RootInlineBox.h"
class RenderBlock : public RenderBox {
public:
friend class LineLayoutState;
+#ifndef NDEBUG
+ // Used by the PODIntervalTree for debugging the FloatingObject.
+ template <class> friend struct ValueToString;
+#endif
+
RenderBlock(Node*);
virtual ~RenderBlock();
, m_shouldPaint(false)
, m_isDescendant(false)
, m_isPlaced(false)
+#ifndef NDEBUG
+ , m_isInPlacedTree(false)
+#endif
{
ASSERT(type != NoFloat);
if (type == LeftFloat)
, m_shouldPaint(type != FloatPositioned)
, m_isDescendant(false)
, m_isPlaced(true)
+#ifndef NDEBUG
+ , m_isInPlacedTree(false)
+#endif
{
}
int width() const { return m_frameRect.width(); }
int height() const { return m_frameRect.height(); }
- void setX(int x) { m_frameRect.setX(x); }
- void setY(int y) { m_frameRect.setY(y); }
- void setWidth(int width) { m_frameRect.setWidth(width); }
- void setHeight(int height) { m_frameRect.setHeight(height); }
+ void setX(int x) { ASSERT(!isInPlacedTree()); m_frameRect.setX(x); }
+ void setY(int y) { ASSERT(!isInPlacedTree()); m_frameRect.setY(y); }
+ void setWidth(int width) { ASSERT(!isInPlacedTree()); m_frameRect.setWidth(width); }
+ void setHeight(int height) { ASSERT(!isInPlacedTree()); m_frameRect.setHeight(height); }
const IntRect& frameRect() const { ASSERT(isPlaced()); return m_frameRect; }
- void setFrameRect(const IntRect& frameRect) { m_frameRect = frameRect; }
+ void setFrameRect(const IntRect& frameRect) { ASSERT(!isInPlacedTree()); m_frameRect = frameRect; }
+
+#ifndef NDEBUG
+ bool isInPlacedTree() const { return m_isInPlacedTree; }
+ void setIsInPlacedTree(bool value) { m_isInPlacedTree = value; }
+#endif
RenderBox* m_renderer;
RootInlineBox* m_originatingLine;
bool m_shouldPaint : 1;
bool m_isDescendant : 1;
bool m_isPlaced : 1;
+#ifndef NDEBUG
+ bool m_isInPlacedTree : 1;
+#endif
};
IntPoint flipFloatForWritingMode(const FloatingObject*, const IntPoint&) const;
};
typedef ListHashSet<FloatingObject*, 4, FloatingObjectHashFunctions> FloatingObjectSet;
typedef FloatingObjectSet::const_iterator FloatingObjectSetIterator;
+ typedef PODInterval<LayoutUnit, FloatingObject*> FloatingObjectInterval;
+ typedef PODIntervalTree<LayoutUnit, FloatingObject*> FloatingObjectTree;
+
+ template <FloatingObject::Type FloatTypeValue>
+ class FloatIntervalSearchAdapter {
+ public:
+ typedef FloatingObjectInterval IntervalType;
+
+ FloatIntervalSearchAdapter(const RenderBlock* renderer, LayoutUnit value, LayoutUnit& offset, LayoutUnit* heightRemaining)
+ : m_renderer(renderer)
+ , m_value(value)
+ , m_offset(offset)
+ , m_heightRemaining(heightRemaining)
+ {
+ }
+
+ inline LayoutUnit lowValue() const { return m_value; }
+ inline LayoutUnit highValue() const { return m_value; }
+ void collectIfNeeded(const IntervalType&) const;
+
+ private:
+ const RenderBlock* m_renderer;
+ LayoutUnit m_value;
+ LayoutUnit& m_offset;
+ LayoutUnit* m_heightRemaining;
+ };
+
class FloatingObjects {
public:
- FloatingObjects()
- : m_leftObjectsCount(0)
+ FloatingObjects(bool horizontalWritingMode)
+ : m_placedFloatsTree(UninitializedTree)
+ , m_leftObjectsCount(0)
, m_rightObjectsCount(0)
, m_positionedObjectsCount(0)
+ , m_horizontalWritingMode(horizontalWritingMode)
{
}
void clear();
- void increaseObjectsCount(FloatingObject::Type);
- void decreaseObjectsCount(FloatingObject::Type);
+ void add(FloatingObject*);
+ void remove(FloatingObject*);
+ void addPlacedObject(FloatingObject*);
+ void removePlacedObject(FloatingObject*);
+ void setHorizontalWritingMode(bool b = true) { m_horizontalWritingMode = b; }
+
bool hasLeftObjects() const { return m_leftObjectsCount > 0; }
bool hasRightObjects() const { return m_rightObjectsCount > 0; }
bool hasPositionedObjects() const { return m_positionedObjectsCount > 0; }
- FloatingObjectSet& set() { return m_set; }
-
+ const FloatingObjectSet& set() const { return m_set; }
+ const FloatingObjectTree& placedFloatsTree()
+ {
+ computePlacedFloatsTreeIfNeeded();
+ return m_placedFloatsTree;
+ }
private:
+ void computePlacedFloatsTree();
+ inline void computePlacedFloatsTreeIfNeeded()
+ {
+ if (!m_placedFloatsTree.isInitialized())
+ computePlacedFloatsTree();
+ }
+ void increaseObjectsCount(FloatingObject::Type);
+ void decreaseObjectsCount(FloatingObject::Type);
+ FloatingObjectInterval intervalForFloatingObject(FloatingObject*);
+
FloatingObjectSet m_set;
+ FloatingObjectTree m_placedFloatsTree;
unsigned m_leftObjectsCount;
unsigned m_rightObjectsCount;
unsigned m_positionedObjectsCount;
+ bool m_horizontalWritingMode;
};
OwnPtr<FloatingObjects> m_floatingObjects;
// This will catch anyone doing an unnecessary cast.
void toRenderBlock(const RenderBlock*);
+#ifndef NDEBUG
+// These structures are used by PODIntervalTree for debugging purposes.
+template <> struct ValueToString<int> {
+ static String string(const int value);
+};
+template<> struct ValueToString<RenderBlock::FloatingObject*> {
+ static String string(const RenderBlock::FloatingObject*);
+};
+#endif
+
} // namespace WebCore
#endif // RenderBlock_h
}
if (m_floatingObjects && lastRootBox()) {
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.begin();
FloatingObjectSetIterator end = floatingObjectSet.end();
if (layoutState.lastFloat()) {
trailingFloatsLineBox->setBlockLogicalHeight(logicalHeight());
}
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.begin();
FloatingObjectSetIterator end = floatingObjectSet.end();
if (layoutState.lastFloat()) {
int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* f = *it;
int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* f = *it;
if (!newFloat->m_paginationStrut)
return true;
- FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
ASSERT(floatingObjectSet.last() == newFloat);
int floatLogicalTop = logicalTopForFloat(newFloat);
if (o->isRenderBlock())
toRenderBlock(o)->setChildNeedsLayout(true, false);
o->layoutIfNeeded();
- setLogicalTopForFloat(f, logicalTopForFloat(f) + f->m_paginationStrut);
+ // Save the old logical top before calling removePlacedObject which will set
+ // isPlaced to false. Otherwise it will trigger an assert in logicalTopForFloat.
+ LayoutUnit oldLogicalTop = logicalTopForFloat(f);
+ m_floatingObjects->removePlacedObject(f);
+ setLogicalTopForFloat(f, oldLogicalTop + f->m_paginationStrut);
+ m_floatingObjects->addPlacedObject(f);
}
}
git://git.webkit.org / WebKit-https.git / commitdiff