Unreviewed, rolling out r92610.
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Aug 2011 20:13:48 +0000 (20:13 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 8 Aug 2011 20:13:48 +0000 (20:13 +0000)
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).

Patch by Sheriff Bot <webkit.review.bot@gmail.com> on 2011-08-08

PerformanceTests:

* Layout/floats.html:

Source/WebCore:

* 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):

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