Fixing 65868 REGRESSION(r92610) caused by 65668 - Optimize floating elements lookup
authorhyatt@apple.com <hyatt@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Aug 2011 19:13:45 +0000 (19:13 +0000)
committerhyatt@apple.com <hyatt@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Aug 2011 19:13:45 +0000 (19:13 +0000)
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

PerformanceTests/ChangeLog
PerformanceTests/Layout/floats.html
Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/platform/PODIntervalTree.h
Source/WebCore/platform/PODRedBlackTree.h
Source/WebCore/rendering/RenderBlock.cpp
Source/WebCore/rendering/RenderBlock.h
Source/WebCore/rendering/RenderBlockLineLayout.cpp

index fb2b944..89c6302 100644 (file)
@@ -1,3 +1,12 @@
+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.
index 67805d8..52f95ba 100644 (file)
                 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
index ae47077..c740575 100644 (file)
@@ -1,3 +1,95 @@
+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
index aea7b21..1673d4b 100644 (file)
                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;
                };
index 5bf3de0..96233c5 100644 (file)
@@ -40,6 +40,32 @@ template<class T>
 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.
@@ -50,7 +76,14 @@ public:
     // 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>()
     {
@@ -80,7 +113,16 @@ public:
     {
         // 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.
@@ -112,7 +154,8 @@ private:
     // 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;
@@ -125,18 +168,17 @@ private:
         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)
index 83b2176..1c2cc84 100644 (file)
@@ -90,6 +90,10 @@ template<class T>
 struct ValueToString;
 #endif
 
+enum UninitializedTreeEnum {
+    UninitializedTree
+};
+
 template<class T>
 class PODRedBlackTree {
 public:
@@ -101,6 +105,19 @@ 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()
@@ -127,8 +144,28 @@ public:
 
     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);
     }
@@ -136,6 +173,7 @@ public:
     // 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);
@@ -144,10 +182,15 @@ public:
         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);
@@ -155,6 +198,7 @@ public:
 
     int size() const
     {
+        ASSERT(isInitialized());
         Counter counter;
         visitInorder(&counter);
         return counter.count();
@@ -168,6 +212,7 @@ public:
 
     virtual bool checkInvariants() const
     {
+        ASSERT(isInitialized());
         int blackCount;
         return checkInvariantsFromNode(m_root, &blackCount);
     }
@@ -177,7 +222,8 @@ public:
     // 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
index 2632dd5..370c225 100644 (file)
@@ -274,7 +274,7 @@ void RenderBlock::styleDidChange(StyleDifference diff, const RenderStyle* oldSty
     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()) {
@@ -1436,7 +1436,7 @@ void RenderBlock::addOverflowFromFloats()
     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;
@@ -2294,7 +2294,7 @@ void RenderBlock::repaintOverhangingFloats(bool paintAllDescendants)
     // 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;
@@ -2627,7 +2627,7 @@ void RenderBlock::paintFloats(PaintInfo& paintInfo, const LayoutPoint& paintOffs
     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;
@@ -2879,7 +2879,7 @@ GapRects RenderBlock::selectionGaps(RenderBlock* rootBlock, const LayoutPoint& r
             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;
@@ -3190,10 +3190,10 @@ RenderBlock::FloatingObject* RenderBlock::insertFloatingObject(RenderBox* o)
 
     // 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;
@@ -3224,8 +3224,7 @@ RenderBlock::FloatingObject* RenderBlock::insertFloatingObject(RenderBox* o)
     newObj->m_isDescendant = true;
     newObj->m_renderer = o;
 
-    m_floatingObjects->increaseObjectsCount(newObj->type());
-    m_floatingObjects->set().add(newObj);
+    m_floatingObjects->add(newObj);
     
     return newObj;
 }
@@ -3233,8 +3232,8 @@ RenderBlock::FloatingObject* RenderBlock::insertFloatingObject(RenderBox* o)
 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()) {
@@ -3259,8 +3258,7 @@ void RenderBlock::removeFloatingObject(RenderBox* o)
                 }
                 markLinesDirtyInBlockRange(0, logicalBottom);
             }
-            m_floatingObjects->decreaseObjectsCount(r->type());
-            floatingObjectSet.remove(it);
+            m_floatingObjects->remove(r);
             ASSERT(!r->m_originatingLine);
             delete r;
         }
@@ -3272,11 +3270,10 @@ void RenderBlock::removeFloatingObjectsBelow(FloatingObject* lastFloat, int logi
     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();
@@ -3288,7 +3285,7 @@ bool RenderBlock::positionNewFloats()
     if (!m_floatingObjects)
         return false;
 
-    FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
+    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     if (floatingObjectSet.isEmpty())
         return false;
 
@@ -3403,7 +3400,7 @@ bool RenderBlock::positionNewFloats()
         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())
@@ -3505,11 +3502,30 @@ bool RenderBlock::hasPercentHeightDescendant(RenderBox* descendant)
 }
 #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;
@@ -3517,23 +3533,8 @@ LayoutUnit RenderBlock::logicalLeftOffsetForLine(LayoutUnit logicalTop, LayoutUn
         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()) {
@@ -3553,24 +3554,9 @@ LayoutUnit RenderBlock::logicalRightOffsetForLine(LayoutUnit logicalTop, LayoutU
     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()) {
@@ -3595,7 +3581,7 @@ int RenderBlock::nextFloatLogicalBottomBelow(int logicalHeight) const
         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;
@@ -3612,7 +3598,7 @@ int RenderBlock::lowestFloatLogicalBottom(FloatingObject::Type floatType) const
     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;
@@ -3660,7 +3646,8 @@ void RenderBlock::addPositionedFloats()
         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;
     }
@@ -3668,6 +3655,9 @@ void RenderBlock::addPositionedFloats()
 
 void RenderBlock::clearFloats(BlockLayoutPass layoutPass)
 {
+    if (m_floatingObjects)
+        m_floatingObjects->setHorizontalWritingMode(isHorizontalWritingMode());
+
     // Clear our positioned floats boolean.
     m_hasPositionedFloats = false;
 
@@ -3686,10 +3676,10 @@ void RenderBlock::clearFloats(BlockLayoutPass layoutPass)
     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);
             }
@@ -3741,7 +3731,7 @@ void RenderBlock::clearFloats(BlockLayoutPass layoutPass)
         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;
@@ -3823,10 +3813,9 @@ int RenderBlock::addOverhangingFloats(RenderBlock* child, int logicalLeftOffset,
 
                 // 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() &&
@@ -3853,7 +3842,7 @@ bool RenderBlock::hasOverhangingFloat(RenderBox* renderer)
     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;
@@ -3869,7 +3858,7 @@ void RenderBlock::addIntrudingFloats(RenderBlock* prev, int logicalLeftOffset, i
 
     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;
@@ -3897,9 +3886,8 @@ void RenderBlock::addIntrudingFloats(RenderBlock* prev, int logicalLeftOffset, i
                 
                 // 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);
             }
         }
     }
@@ -3940,7 +3928,7 @@ void RenderBlock::markAllDescendantsWithFloatsForLayout(RenderBox* floatToRemove
 
 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()) {
@@ -4092,7 +4080,7 @@ bool RenderBlock::hitTestFloats(const HitTestRequest& request, HitTestResult& re
         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;
@@ -5699,7 +5687,7 @@ void RenderBlock::adjustForBorderFit(int x, int& left, int& right) const
         }
         
         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;
@@ -6443,6 +6431,7 @@ const char* RenderBlock::renderName() const
 inline void RenderBlock::FloatingObjects::clear()
 {
     m_set.clear();
+    m_placedFloatsTree.clear();
     m_leftObjectsCount = 0;
     m_rightObjectsCount = 0;
     m_positionedObjectsCount = 0;
@@ -6468,6 +6457,73 @@ inline void RenderBlock::FloatingObjects::decreaseObjectsCount(FloatingObject::T
         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);
@@ -6502,6 +6558,17 @@ void RenderBlock::showLineTreeAndMark(const InlineBox* markedBox1, const char* m
         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
index 6cdf20a..9b4f7fa 100644 (file)
@@ -24,6 +24,7 @@
 #define RenderBlock_h
 
 #include "GapRects.h"
+#include "PODIntervalTree.h"
 #include "RenderBox.h"
 #include "RenderLineBoxList.h"
 #include "RootInlineBox.h"
@@ -67,6 +68,11 @@ typedef unsigned TextRunFlags;
 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();
 
@@ -422,6 +428,9 @@ private:
             , m_shouldPaint(false)
             , m_isDescendant(false)
             , m_isPlaced(false)
+#ifndef NDEBUG
+            , m_isInPlacedTree(false)
+#endif
         {
             ASSERT(type != NoFloat);
             if (type == LeftFloat)
@@ -441,6 +450,9 @@ private:
             , m_shouldPaint(type != FloatPositioned)
             , m_isDescendant(false)
             , m_isPlaced(true)
+#ifndef NDEBUG
+            , m_isInPlacedTree(false)
+#endif
         {
         }
 
@@ -457,13 +469,18 @@ private:
         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;
@@ -473,6 +490,9 @@ private:
         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;
@@ -799,28 +819,77 @@ private:
     };
     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;
     
@@ -895,6 +964,16 @@ inline const RenderBlock* toRenderBlock(const RenderObject* object)
 // 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
index 3623670..61a527d 100644 (file)
@@ -1091,7 +1091,7 @@ void RenderBlock::layoutRunsAndFloatsInRange(LineLayoutState& layoutState, Inlin
         }
 
         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()) {
@@ -1172,7 +1172,7 @@ void RenderBlock::linkToEndLineIfNeeded(LineLayoutState& layoutState)
             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()) {
@@ -1491,7 +1491,7 @@ bool RenderBlock::matchedEndLine(LineLayoutState& layoutState, const InlineBidiR
 
         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;
@@ -1528,7 +1528,7 @@ bool RenderBlock::matchedEndLine(LineLayoutState& layoutState, const InlineBidiR
 
                 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;
@@ -2550,7 +2550,7 @@ bool RenderBlock::positionNewFloatOnLine(FloatingObject* newFloat, FloatingObjec
     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);
@@ -2575,7 +2575,12 @@ bool RenderBlock::positionNewFloatOnLine(FloatingObject* newFloat, FloatingObjec
             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);
         }
     }