+2011-08-08 Sheriff Bot <webkit.review.bot@gmail.com>
+
+ Unreviewed, rolling out r92610.
+ http://trac.webkit.org/changeset/92610
+ https://bugs.webkit.org/show_bug.cgi?id=65868
+
+ Caused assertion failures when running fast/multicol tests
+ (Requested by andersca on #webkit).
+
+ * Layout/floats.html:
+
2011-08-08 Alexandru Chiculita <achicu@adobe.com>
Optimize floating elements lookup
return el;
}
- function createSet(width, height, nested)
+ function createSet(width, height)
{
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, nested)
+ function test(width, height)
{
- nested = nested || 0;
-
document.getElementById("test_panel").style.display = "none";
document.getElementById("framerate_panel").style.display = "block";
- createSet(width, height, nested);
+ createSet(width, height);
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-08 Sheriff Bot <webkit.review.bot@gmail.com>
+
+ Unreviewed, rolling out r92610.
+ http://trac.webkit.org/changeset/92610
+ https://bugs.webkit.org/show_bug.cgi?id=65868
+
+ Caused assertion failures when running fast/multicol tests
+ (Requested by andersca on #webkit).
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * platform/PODIntervalTree.h:
+ (WebCore::PODIntervalTree::allOverlaps):
+ (WebCore::PODIntervalTree::searchForOverlapsFrom):
+ * platform/PODRedBlackTree.h:
+ (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::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):
+ * 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::FloatingObjects::FloatingObjects):
+ (WebCore::RenderBlock::FloatingObjects::set):
+ * rendering/RenderBlockLineLayout.cpp:
+ (WebCore::RenderBlock::layoutRunsAndFloatsInRange):
+ (WebCore::RenderBlock::linkToEndLineIfNeeded):
+ (WebCore::RenderBlock::matchedEndLine):
+ (WebCore::RenderBlock::positionNewFloatOnLine):
+
2011-08-08 Emil A Eklund <eae@chromium.org>
Rename absoluteQuadsForRange and InlineTextBox::selectionRect to local*
501BAAA913950E2C00F7ACEB /* WindRule.h in Headers */ = {isa = PBXBuildFile; fileRef = 501BAAA813950E2C00F7ACEB /* WindRule.h */; settings = {ATTRIBUTES = (Private, ); }; };
508CCA4F13CF106B003151F3 /* RenderFlowThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 508CCA4D13CF106B003151F3 /* RenderFlowThread.h */; };
508CCA5013CF106B003151F3 /* RenderFlowThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 508CCA4E13CF106B003151F3 /* RenderFlowThread.cpp */; };
- 5097C5A313EABA7E002DE4AF /* PODArena.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C59F13EABA7E002DE4AF /* PODArena.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 5097C5A413EABA7E002DE4AF /* PODInterval.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C5A013EABA7E002DE4AF /* PODInterval.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 5097C5A513EABA7E002DE4AF /* PODIntervalTree.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C5A113EABA7E002DE4AF /* PODIntervalTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 5097C5A613EABA7E002DE4AF /* PODRedBlackTree.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C5A213EABA7E002DE4AF /* PODRedBlackTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
50E566D6139E38C500214433 /* CSSWrapShapes.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 501BAAB11395114B00F7ACEB /* CSSWrapShapes.cpp */; };
510184690B08602A004A825F /* CachedPage.h in Headers */ = {isa = PBXBuildFile; fileRef = 510184670B08602A004A825F /* CachedPage.h */; settings = {ATTRIBUTES = (Private, ); }; };
5101846A0B08602A004A825F /* CachedPage.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 510184680B08602A004A825F /* CachedPage.cpp */; };
501BAAB11395114B00F7ACEB /* CSSWrapShapes.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CSSWrapShapes.cpp; sourceTree = "<group>"; };
508CCA4D13CF106B003151F3 /* RenderFlowThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderFlowThread.h; sourceTree = "<group>"; };
508CCA4E13CF106B003151F3 /* RenderFlowThread.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderFlowThread.cpp; sourceTree = "<group>"; };
- 5097C59F13EABA7E002DE4AF /* PODArena.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODArena.h; sourceTree = "<group>"; };
- 5097C5A013EABA7E002DE4AF /* PODInterval.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODInterval.h; sourceTree = "<group>"; };
- 5097C5A113EABA7E002DE4AF /* PODIntervalTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODIntervalTree.h; sourceTree = "<group>"; };
- 5097C5A213EABA7E002DE4AF /* PODRedBlackTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODRedBlackTree.h; sourceTree = "<group>"; };
510184670B08602A004A825F /* CachedPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CachedPage.h; sourceTree = "<group>"; };
510184680B08602A004A825F /* CachedPage.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CachedPage.cpp; sourceTree = "<group>"; };
510D4A2D103165EE0049EA54 /* SocketStreamErrorBase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SocketStreamErrorBase.cpp; sourceTree = "<group>"; };
BCF1A5BA097832090061A123 /* platform */ = {
isa = PBXGroup;
children = (
- 5097C59F13EABA7E002DE4AF /* PODArena.h */,
- 5097C5A013EABA7E002DE4AF /* PODInterval.h */,
- 5097C5A113EABA7E002DE4AF /* PODIntervalTree.h */,
- 5097C5A213EABA7E002DE4AF /* PODRedBlackTree.h */,
49E912A40EFAC8E6009D0CAF /* animation */,
FD31604012B026A300C1A359 /* audio */,
1AE42F670AA4B8CB00C8612D /* cf */,
E1BE512E0CF6C512002EA959 /* XSLTUnicodeSort.h in Headers */,
977E2E0F12F0FC9C00C13379 /* XSSAuditor.h in Headers */,
FD537353137B651800008DCE /* ZeroPole.h in Headers */,
- 5097C5A313EABA7E002DE4AF /* PODArena.h in Headers */,
- 5097C5A413EABA7E002DE4AF /* PODInterval.h in Headers */,
- 5097C5A513EABA7E002DE4AF /* PODIntervalTree.h in Headers */,
- 5097C5A613EABA7E002DE4AF /* 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.
- 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);
+ searchForOverlapsFrom(this->root(), interval, result);
}
// 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.
- template <class AdapterType>
- void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
+ void searchForOverlapsFrom(IntervalNode* node, const IntervalType& interval, Vector<IntervalType>& res) const
{
if (!node)
return;
if (left
// This is phrased this way to avoid the need for operator
// <= on type T.
- && !(left->data().maxHigh() < adapter.lowValue()))
- searchForOverlapsFrom<AdapterType>(left, adapter);
+ && !(left->data().maxHigh() < interval.low()))
+ searchForOverlapsFrom(left, interval, res);
// Check for overlap with current node.
- adapter.collectIfNeeded(node->data());
+ if (node->data().overlaps(interval))
+ res.append(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 (!(adapter.highValue() < node->data().low()))
- searchForOverlapsFrom<AdapterType>(node->right(), adapter);
+ if (!(interval.high() < node->data().low()))
+ searchForOverlapsFrom(node->right(), interval, res);
}
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
- {
- ASSERT(isInitialized());
- return treeSearch(data);
- }
+ bool contains(const T& data) const { 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
{
- if (m_arena)
- dumpFromNode(m_root, 0);
+ 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;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (RenderObject* curr = parent(); curr && !curr->isRenderView(); curr = curr->parent()) {
if (!m_floatingObjects)
return;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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());
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator end = floatingObjectSet.end();
for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
FloatingObject* r = *it;
if (!m_floatingObjects)
return;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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) {
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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(isHorizontalWritingMode()));
+ m_floatingObjects = adoptPtr(new FloatingObjects);
else {
// Don't insert the object again if it's already in the list
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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->add(newObj);
+ m_floatingObjects->increaseObjectsCount(newObj->type());
+ m_floatingObjects->set().add(newObj);
return newObj;
}
void RenderBlock::removeFloatingObject(RenderBox* o)
{
if (m_floatingObjects) {
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
- FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet::iterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
if (it != floatingObjectSet.end()) {
FloatingObject* r = *it;
if (childrenInline()) {
}
markLinesDirtyInBlockRange(0, logicalBottom);
}
- m_floatingObjects->remove(r);
+ m_floatingObjects->decreaseObjectsCount(r->type());
+ floatingObjectSet.remove(it);
ASSERT(!r->m_originatingLine);
delete r;
}
if (!m_floatingObjects)
return;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObject* curr = floatingObjectSet.last();
while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
- m_floatingObjects->remove(curr);
+ m_floatingObjects->decreaseObjectsCount(curr->type());
+ floatingObjectSet.removeLast();
ASSERT(!curr->m_originatingLine);
delete curr;
curr = floatingObjectSet.last();
if (!m_floatingObjects)
return false;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
if (floatingObjectSet.isEmpty())
return false;
setLogicalTopForFloat(floatingObject, logicalTop);
setLogicalHeightForFloat(floatingObject, logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
- m_floatingObjects->addPlacedObject(floatingObject);
+ floatingObject->setIsPlaced();
// If the child moved, we have to repaint it.
if (childBox->checkForRepaintDuringLayout())
}
#endif
-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;
- }
- }
-}
-
+// 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.
LayoutUnit RenderBlock::logicalLeftOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, bool applyTextIndent, LayoutUnit* heightRemaining) const
{
LayoutUnit left = fixedOffset;
if (heightRemaining)
*heightRemaining = 1;
- FloatIntervalSearchAdapter<FloatingObject::FloatLeft> adapter(this, logicalTop, left, heightRemaining);
- m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
+ // 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);
}
if (applyTextIndent && style()->isLeftToRightDirection()) {
if (m_floatingObjects && m_floatingObjects->hasRightObjects()) {
if (heightRemaining)
*heightRemaining = 1;
-
- FloatIntervalSearchAdapter<FloatingObject::FloatRight> adapter(this, logicalTop, right, heightRemaining);
- m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
+
+ // 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);
}
if (applyTextIndent && !style()->isLeftToRightDirection()) {
return 0;
int bottom = INT_MAX;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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));
-
- m_floatingObjects->addPlacedObject(floatingObject);
+ floatingObject->setIsPlaced(true);
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) {
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
if (childrenInline()) {
- FloatingObjectSetIterator end = floatingObjectSet.end();
- for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
+ FloatingObjectSet::iterator end = floatingObjectSet.end();
+ for (FloatingObjectSet::iterator 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) {
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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(isHorizontalWritingMode()));
+ m_floatingObjects = adoptPtr(new FloatingObjects);
- m_floatingObjects->add(floatingObj);
+ m_floatingObjects->increaseObjectsCount(floatingObj->type());
+ m_floatingObjects->set().add(floatingObj);
}
} else {
if (makeChildPaintOtherFloats && !r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer() &&
if (!m_floatingObjects || hasColumns() || !parent())
return false;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(renderer);
if (it == floatingObjectSet.end())
return false;
logicalLeftOffset += (isHorizontalWritingMode() ? marginLeft() : marginTop());
- const FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
+ 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(isHorizontalWritingMode()));
- m_floatingObjects->add(floatingObj);
+ m_floatingObjects = adoptPtr(new FloatingObjects);
+ m_floatingObjects->increaseObjectsCount(floatingObj->type());
+ m_floatingObjects->set().add(floatingObj);
}
}
}
void RenderBlock::markSiblingsWithFloatsForLayout()
{
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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());
}
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator begin = floatingObjectSet.begin();
for (FloatingObjectSetIterator it = floatingObjectSet.end(); it != begin;) {
--it;
}
if (m_floatingObjects) {
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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) { 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); }
+ 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); }
const IntRect& frameRect() const { ASSERT(isPlaced()); return m_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
+ void setFrameRect(const IntRect& frameRect) { m_frameRect = frameRect; }
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(bool horizontalWritingMode)
- : m_placedFloatsTree(UninitializedTree)
- , m_leftObjectsCount(0)
+ FloatingObjects()
+ : m_leftObjectsCount(0)
, m_rightObjectsCount(0)
, m_positionedObjectsCount(0)
- , m_horizontalWritingMode(horizontalWritingMode)
{
}
void clear();
- void add(FloatingObject*);
- void remove(FloatingObject*);
- void addPlacedObject(FloatingObject*);
- void removePlacedObject(FloatingObject*);
- void setHorizontalWritingMode(bool b = true) { m_horizontalWritingMode = b; }
-
+ void increaseObjectsCount(FloatingObject::Type);
+ void decreaseObjectsCount(FloatingObject::Type);
bool hasLeftObjects() const { return m_leftObjectsCount > 0; }
bool hasRightObjects() const { return m_rightObjectsCount > 0; }
bool hasPositionedObjects() const { return m_positionedObjectsCount > 0; }
- 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& set() { return m_set; }
+ private:
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()) {
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.begin();
FloatingObjectSetIterator end = floatingObjectSet.end();
if (layoutState.lastFloat()) {
trailingFloatsLineBox->setBlockLogicalHeight(logicalHeight());
}
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
FloatingObjectSetIterator it = floatingObjectSet.begin();
FloatingObjectSetIterator end = floatingObjectSet.end();
if (layoutState.lastFloat()) {
int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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);
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ 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;
- const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+ FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
ASSERT(floatingObjectSet.last() == newFloat);
int floatLogicalTop = logicalTopForFloat(newFloat);
if (o->isRenderBlock())
toRenderBlock(o)->setChildNeedsLayout(true, false);
o->layoutIfNeeded();
- m_floatingObjects->removePlacedObject(f);
setLogicalTopForFloat(f, logicalTopForFloat(f) + f->m_paginationStrut);
- m_floatingObjects->addPlacedObject(f);
}
}
git://git.webkit.org / WebKit-https.git / commitdiff