Changeset 92610 in webkit


Ignore:
Timestamp:
Aug 8, 2011 11:09:19 AM (13 years ago)
Author:
commit-queue@webkit.org
Message:

Optimize floating elements lookup
​https://bugs.webkit.org/show_bug.cgi?id=65668

PerformanceTests:

Patch by Alexandru Chiculita <Alexandru Chiculita> on 2011-08-08
Reviewed by David 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 <Alexandru Chiculita> on 2011-08-08
Reviewed by David 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):

Location:
trunk
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/PerformanceTests/ChangeLog

    r92444 r92610  
     12011-08-08  Alexandru Chiculita  <achicu@adobe.com>
     2
     3        Optimize floating elements lookup
     4        https://bugs.webkit.org/show_bug.cgi?id=65668
     5
     6        Reviewed by David Hyatt.
     7
     8        * Layout/floats.html: Added the nested divs, so that we can test the propagation impact of the floats tree.
     9
    1102011-08-04  Alexandru Chiculita  <achicu@adobe.com>
    211

  • trunk/PerformanceTests/Layout/floats.html

    r92444 r92610  
    3131            }
    3232
    33             function createSet(width, height)
     33            function createSet(width, height, nested)
    3434            {
    3535                var container = createElement("div", document.body, "container");
    … …  
    3737                    for (var x = 0; x < width; ++x)
    3838                        createElement("div", container, "float", "float" + x + "_" + y);
     39
     40                    var nestedContainer = container;
     41                    for ( ; nested > 0; --nested)
     42                        nestedContainer = createElement("div", nestedContainer, "nested", "nested" + x + "_" + nested);
     43                   
    3944                    createElement("div", container, "float-end", "end" + x)
    4045                }
    … …  
    4853            }
    4954
    50             function test(width, height)
     55            function test(width, height, nested)
    5156            {
     57                nested = nested || 0;
     58
    5259                document.getElementById("test_panel").style.display = "none";
    5360                document.getElementById("framerate_panel").style.display = "block";
    5461
    55                 createSet(width, height);
     62                createSet(width, height, nested);
    5663                var updates = 0;
    5764                var startTime = new Date();
    … …  
    9299            <button onclick="test(50, 100)">50 by 100</button>
    93100            <button onclick="test(100, 100)">100 by 100</button>
     101            <p>Nested divs:</p>
     102            <button onclick="test(2, 100, 100)">2 by 100, 100 nested</button>
     103            <button onclick="test(20, 100, 100)">20 by 100, 100 nested</button>
     104            <button onclick="test(50, 100, 100)">50 by 100, 100 nested</button>
     105            <button onclick="test(100, 100, 100)">100 by 100, 100 nested</button>
    94106        </div>
    95107    </body>

  • trunk/Source/WebCore/ChangeLog

    r92607 r92610  
     12011-08-08  Alexandru Chiculita  <achicu@adobe.com>
     2
     3        Optimize floating elements lookup
     4        https://bugs.webkit.org/show_bug.cgi?id=65668
     5
     6        Added an interval tree in the FloatingObjects structure. Also added new mechanisms to make
     7        sure the tree is updated correctly when a float is repositioned.
     8
     9        Changed the PODIntervalTree to support giving a search adapter that can be implemented by the
     10        client. I'm not adding a different bug for that because PODIntervalTree is not used anywhere else
     11        and would be hard to test that the change is not breaking anything.
     12
     13        Reviewed by David Hyatt.
     14
     15        No new tests, just a refactor on the floating objects data structure.
     16
     17        * WebCore.xcodeproj/project.pbxproj:
     18        * platform/PODIntervalTree.h:
     19        (WebCore::PODIntervalSearchAdapter::PODIntervalSearchAdapter):
     20        (WebCore::PODIntervalSearchAdapter::lowValue):
     21        (WebCore::PODIntervalSearchAdapter::highValue):
     22        (WebCore::PODIntervalSearchAdapter::collectIfNeeded):
     23        (WebCore::PODIntervalTree::PODIntervalTree):
     24        (WebCore::PODIntervalTree::allOverlaps):
     25        (WebCore::PODIntervalTree::allOverlapsWithAdapter):
     26        (WebCore::PODIntervalTree::searchForOverlapsFrom):
     27        * platform/PODRedBlackTree.h:
     28        (WebCore::PODRedBlackTree::PODRedBlackTree):
     29        (WebCore::PODRedBlackTree::clear):
     30        (WebCore::PODRedBlackTree::isInitialized):
     31        (WebCore::PODRedBlackTree::initIfNeeded):
     32        (WebCore::PODRedBlackTree::add):
     33        (WebCore::PODRedBlackTree::remove):
     34        (WebCore::PODRedBlackTree::contains):
     35        (WebCore::PODRedBlackTree::visitInorder):
     36        (WebCore::PODRedBlackTree::size):
     37        (WebCore::PODRedBlackTree::checkInvariants):
     38        (WebCore::PODRedBlackTree::dump):
     39        * rendering/RenderBlock.cpp:
     40        (WebCore::RenderBlock::styleDidChange):
     41        (WebCore::RenderBlock::addOverflowFromFloats):
     42        (WebCore::RenderBlock::repaintOverhangingFloats):
     43        (WebCore::RenderBlock::paintFloats):
     44        (WebCore::RenderBlock::selectionGaps):
     45        (WebCore::RenderBlock::insertFloatingObject):
     46        (WebCore::RenderBlock::removeFloatingObject):
     47        (WebCore::RenderBlock::removeFloatingObjectsBelow):
     48        (WebCore::RenderBlock::positionNewFloats):
     49        (WebCore::::collectIfNeeded):
     50        (WebCore::RenderBlock::logicalLeftOffsetForLine):
     51        (WebCore::RenderBlock::logicalRightOffsetForLine):
     52        (WebCore::RenderBlock::nextFloatLogicalBottomBelow):
     53        (WebCore::RenderBlock::lowestFloatLogicalBottom):
     54        (WebCore::RenderBlock::addPositionedFloats):
     55        (WebCore::RenderBlock::clearFloats):
     56        (WebCore::RenderBlock::addOverhangingFloats):
     57        (WebCore::RenderBlock::hasOverhangingFloat):
     58        (WebCore::RenderBlock::addIntrudingFloats):
     59        (WebCore::RenderBlock::markSiblingsWithFloatsForLayout):
     60        (WebCore::RenderBlock::hitTestFloats):
     61        (WebCore::RenderBlock::adjustForBorderFit):
     62        (WebCore::RenderBlock::FloatingObjects::clear):
     63        (WebCore::RenderBlock::FloatingObjects::intervalForFloatingObject):
     64        (WebCore::RenderBlock::FloatingObjects::addPlacedObject):
     65        (WebCore::RenderBlock::FloatingObjects::removePlacedObject):
     66        (WebCore::RenderBlock::FloatingObjects::add):
     67        (WebCore::RenderBlock::FloatingObjects::remove):
     68        (WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTree):
     69        (WebCore::::string):
     70        * rendering/RenderBlock.h:
     71        (WebCore::RenderBlock::FloatingObject::FloatingObject):
     72        (WebCore::RenderBlock::FloatingObject::setX):
     73        (WebCore::RenderBlock::FloatingObject::setY):
     74        (WebCore::RenderBlock::FloatingObject::setWidth):
     75        (WebCore::RenderBlock::FloatingObject::setHeight):
     76        (WebCore::RenderBlock::FloatingObject::setFrameRect):
     77        (WebCore::RenderBlock::FloatingObject::isInPlacedTree):
     78        (WebCore::RenderBlock::FloatingObject::setIsInPlacedTree):
     79        (WebCore::RenderBlock::FloatIntervalSearchAdapter::FloatIntervalSearchAdapter):
     80        (WebCore::RenderBlock::FloatIntervalSearchAdapter::lowValue):
     81        (WebCore::RenderBlock::FloatIntervalSearchAdapter::highValue):
     82        (WebCore::RenderBlock::FloatingObjects::FloatingObjects):
     83        (WebCore::RenderBlock::FloatingObjects::setHorizontalWritingMode):
     84        (WebCore::RenderBlock::FloatingObjects::set):
     85        (WebCore::RenderBlock::FloatingObjects::placedFloatsTree):
     86        (WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTreeIfNeeded):
     87        * rendering/RenderBlockLineLayout.cpp:
     88        (WebCore::RenderBlock::layoutRunsAndFloatsInRange):
     89        (WebCore::RenderBlock::linkToEndLineIfNeeded):
     90        (WebCore::RenderBlock::matchedEndLine):
     91        (WebCore::RenderBlock::positionNewFloatOnLine):
     92
    1932011-08-08  Alexei Svitkine  <asvitkine@chromium.org>
    294

  • trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r92592 r92610  
    13371337                508CCA4F13CF106B003151F3 /* RenderFlowThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 508CCA4D13CF106B003151F3 /* RenderFlowThread.h */; };
    13381338                508CCA5013CF106B003151F3 /* RenderFlowThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 508CCA4E13CF106B003151F3 /* RenderFlowThread.cpp */; };
     1339                5097C5A313EABA7E002DE4AF /* PODArena.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C59F13EABA7E002DE4AF /* PODArena.h */; settings = {ATTRIBUTES = (Private, ); }; };
     1340                5097C5A413EABA7E002DE4AF /* PODInterval.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C5A013EABA7E002DE4AF /* PODInterval.h */; settings = {ATTRIBUTES = (Private, ); }; };
     1341                5097C5A513EABA7E002DE4AF /* PODIntervalTree.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C5A113EABA7E002DE4AF /* PODIntervalTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
     1342                5097C5A613EABA7E002DE4AF /* PODRedBlackTree.h in Headers */ = {isa = PBXBuildFile; fileRef = 5097C5A213EABA7E002DE4AF /* PODRedBlackTree.h */; settings = {ATTRIBUTES = (Private, ); }; };
    13391343                50E566D6139E38C500214433 /* CSSWrapShapes.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 501BAAB11395114B00F7ACEB /* CSSWrapShapes.cpp */; };
    13401344                510184690B08602A004A825F /* CachedPage.h in Headers */ = {isa = PBXBuildFile; fileRef = 510184670B08602A004A825F /* CachedPage.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    79387942                508CCA4D13CF106B003151F3 /* RenderFlowThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderFlowThread.h; sourceTree = "<group>"; };
    79397943                508CCA4E13CF106B003151F3 /* RenderFlowThread.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderFlowThread.cpp; sourceTree = "<group>"; };
     7944                5097C59F13EABA7E002DE4AF /* PODArena.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODArena.h; sourceTree = "<group>"; };
     7945                5097C5A013EABA7E002DE4AF /* PODInterval.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODInterval.h; sourceTree = "<group>"; };
     7946                5097C5A113EABA7E002DE4AF /* PODIntervalTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODIntervalTree.h; sourceTree = "<group>"; };
     7947                5097C5A213EABA7E002DE4AF /* PODRedBlackTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODRedBlackTree.h; sourceTree = "<group>"; };
    79407948                510184670B08602A004A825F /* CachedPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CachedPage.h; sourceTree = "<group>"; };
    79417949                510184680B08602A004A825F /* CachedPage.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CachedPage.cpp; sourceTree = "<group>"; };
    … …  
    1900919017                        isa = PBXGroup;
    1901019018                        children = (
     19019                                5097C59F13EABA7E002DE4AF /* PODArena.h */,
     19020                                5097C5A013EABA7E002DE4AF /* PODInterval.h */,
     19021                                5097C5A113EABA7E002DE4AF /* PODIntervalTree.h */,
     19022                                5097C5A213EABA7E002DE4AF /* PODRedBlackTree.h */,
    1901119023                                49E912A40EFAC8E6009D0CAF /* animation */,
    1901219024                                FD31604012B026A300C1A359 /* audio */,
    … …  
    2335523367                                977E2E0F12F0FC9C00C13379 /* XSSAuditor.h in Headers */,
    2335623368                                FD537353137B651800008DCE /* ZeroPole.h in Headers */,
     23369                                5097C5A313EABA7E002DE4AF /* PODArena.h in Headers */,
     23370                                5097C5A413EABA7E002DE4AF /* PODInterval.h in Headers */,
     23371                                5097C5A513EABA7E002DE4AF /* PODIntervalTree.h in Headers */,
     23372                                5097C5A613EABA7E002DE4AF /* PODRedBlackTree.h in Headers */,
    2335723373                        );
    2335823374                        runOnlyForDeploymentPostprocessing = 0;

  • trunk/Source/WebCore/platform/PODIntervalTree.h

    r92363 r92610  
    4141#endif
    4242
     43template <class T, class UserData = void*>
     44class PODIntervalSearchAdapter {
     45public:
     46    typedef PODInterval<T, UserData> IntervalType;
     47   
     48    PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
     49        : m_result(result)
     50        , m_lowValue(lowValue)
     51        , m_highValue(highValue)
     52    {
     53    }
     54   
     55    const T& lowValue() const { return m_lowValue; }
     56    const T& highValue() const { return m_highValue; }
     57    void collectIfNeeded(const IntervalType& data) const
     58    {
     59        if (data.overlaps(m_lowValue, m_highValue))
     60            m_result.append(data);
     61    }
     62
     63private:
     64    Vector<IntervalType>& m_result;
     65    T m_lowValue;
     66    T m_highValue;
     67};
     68
    4369// An interval tree, which is a form of augmented red-black tree. It
    4470// supports efficient (O(lg n)) insertion, removal and querying of
    … …  
    5177    // this tree.
    5278    typedef PODInterval<T, UserData> IntervalType;
    53 
     79    typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
     80
     81    PODIntervalTree(UninitializedTreeEnum unitializedTree)
     82        : PODRedBlackTree<IntervalType>(unitializedTree)
     83    {
     84        init();
     85    }
     86   
    5487    PODIntervalTree()
    5588        : PODRedBlackTree<IntervalType>()
    … …  
    81114        // Explicit dereference of "this" required because of
    82115        // inheritance rules in template classes.
    83         searchForOverlapsFrom(this->root(), interval, result);
     116        IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
     117        searchForOverlapsFrom<IntervalSearchAdapterType>(this->root(), adapter);
     118    }
     119   
     120    template <class AdapterType>
     121    void allOverlapsWithAdapter(AdapterType& adapter) const
     122    {
     123        // Explicit dereference of "this" required because of
     124        // inheritance rules in template classes.
     125        searchForOverlapsFrom<AdapterType>(this->root(), adapter);
    84126    }
    85127
    … …  
    113155    // interval to the result vector. The intervals are sorted by
    114156    // increasing low endpoint.
    115     void searchForOverlapsFrom(IntervalNode* node, const IntervalType& interval, Vector<IntervalType>& res) const
     157    template <class AdapterType>
     158    void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
    116159    {
    117160        if (!node)
    … …  
    126169            // This is phrased this way to avoid the need for operator
    127170            // <= on type T.
    128             && !(left->data().maxHigh() < interval.low()))
    129             searchForOverlapsFrom(left, interval, res);
     171            && !(left->data().maxHigh() < adapter.lowValue()))
     172            searchForOverlapsFrom<AdapterType>(left, adapter);
    130173
    131174        // Check for overlap with current node.
    132         if (node->data().overlaps(interval))
    133             res.append(node->data());
     175        adapter.collectIfNeeded(node->data());
    134176
    135177        // See whether we need to traverse the right subtree.
    136178        // This is phrased this way to avoid the need for operator <=
    137179        // on type T.
    138         if (!(interval.high() < node->data().low()))
    139             searchForOverlapsFrom(node->right(), interval, res);
     180        if (!(adapter.highValue() < node->data().low()))
     181            searchForOverlapsFrom<AdapterType>(node->right(), adapter);
    140182    }
    141183

  • trunk/Source/WebCore/platform/PODRedBlackTree.h

    r92363 r92610  
    9191#endif
    9292
     93enum UninitializedTreeEnum {
     94    UninitializedTree
     95};
     96
    9397template<class T>
    9498class PODRedBlackTree {
    … …  
    102106    };
    103107
     108    // Constructs a new red-black tree without allocating an arena.
     109    // isInitialized will return false in this case. initIfNeeded can be used
     110    // to init the structure. This constructor is usefull for creating
     111    // lazy initialized tree.
     112    PODRedBlackTree(UninitializedTreeEnum)
     113        : m_root(0)
     114        , m_needsFullOrderingComparisons(false)
     115#ifndef NDEBUG
     116        , m_verboseDebugging(false)
     117#endif
     118    {
     119    }
     120
    104121    // Constructs a new red-black tree, allocating temporary objects
    105122    // from a newly constructed PODArena.
    … …  
    128145    virtual ~PODRedBlackTree() { }
    129146
     147    // Clearing will delete the contents of the tree. After this call
     148    // isInitialized will return false.
     149    void clear()
     150    {
     151        m_arena = 0;
     152        m_root = 0;
     153    }
     154   
     155    bool isInitialized() const
     156    {
     157        return m_arena;
     158    }
     159   
     160    void initIfNeeded()
     161    {
     162        if (!m_arena)
     163            m_arena = PODArena::create();
     164    }
     165
    130166    void add(const T& data)
    131167    {
     168        ASSERT(isInitialized());
    132169        Node* node = m_arena->allocateObject<Node, T>(data);
    133170        insertNode(node);
    … …  
    137174    bool remove(const T& data)
    138175    {
     176        ASSERT(isInitialized());
    139177        Node* node = treeSearch(data);
    140178        if (node) {
    … …  
    145183    }
    146184
    147     bool contains(const T& data) const { return treeSearch(data); }
     185    bool contains(const T& data) const
     186    {
     187        ASSERT(isInitialized());
     188        return treeSearch(data);
     189    }
    148190
    149191    void visitInorder(Visitor* visitor) const
    150192    {
     193        ASSERT(isInitialized());
    151194        if (!m_root)
    152195            return;
    … …  
    156199    int size() const
    157200    {
     201        ASSERT(isInitialized());
    158202        Counter counter;
    159203        visitInorder(&counter);
    … …  
    169213    virtual bool checkInvariants() const
    170214    {
     215        ASSERT(isInitialized());
    171216        int blackCount;
    172217        return checkInvariantsFromNode(m_root, &blackCount);
    … …  
    178223    void dump() const
    179224    {
    180         dumpFromNode(m_root, 0);
     225        if (m_arena)
     226            dumpFromNode(m_root, 0);
    181227    }
    182228

  • trunk/Source/WebCore/rendering/RenderBlock.cpp

    r92438 r92610  
    275275    if (diff == StyleDifferenceLayout && s_canPropagateFloatIntoSibling && !canPropagateFloatIntoSibling && hasOverhangingFloats()) {
    276276        RenderBlock* parentBlock = this;
    277         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     277        const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    278278        FloatingObjectSetIterator end = floatingObjectSet.end();
    279279
    … …  
    14371437        return;
    14381438
    1439     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     1439    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    14401440    FloatingObjectSetIterator end = floatingObjectSet.end();
    14411441    for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    22952295    // in this block. Better yet would be to push extra state for the containers of other floats.
    22962296    LayoutStateDisabler layoutStateDisabler(view());
    2297     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     2297    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    22982298    FloatingObjectSetIterator end = floatingObjectSet.end();
    22992299    for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    26282628        return;
    26292629
    2630     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     2630    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    26312631    FloatingObjectSetIterator end = floatingObjectSet.end();
    26322632    for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    28802880                clipOutPositionedObjects(paintInfo, IntPoint(cb->x(), cb->y()), cb->m_positionedObjects.get()); // FIXME: Not right for flipped writing modes.
    28812881        if (m_floatingObjects) {
    2882             FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     2882            const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    28832883            FloatingObjectSetIterator end = floatingObjectSet.end();
    28842884            for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    31913191    // Create the list of special objects if we don't aleady have one
    31923192    if (!m_floatingObjects)
    3193         m_floatingObjects = adoptPtr(new FloatingObjects);
     3193        m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
    31943194    else {
    31953195        // Don't insert the object again if it's already in the list
    3196         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3196        const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    31973197        FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
    31983198        if (it != floatingObjectSet.end())
    … …  
    32253225    newObj->m_renderer = o;
    32263226
    3227     m_floatingObjects->increaseObjectsCount(newObj->type());
    3228     m_floatingObjects->set().add(newObj);
     3227    m_floatingObjects->add(newObj);
    32293228   
    32303229    return newObj;
    … …  
    32343233{
    32353234    if (m_floatingObjects) {
    3236         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    3237         FloatingObjectSet::iterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
     3235        const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3236        FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(o);
    32383237        if (it != floatingObjectSet.end()) {
    32393238            FloatingObject* r = *it;
    … …  
    32603259                markLinesDirtyInBlockRange(0, logicalBottom);
    32613260            }
    3262             m_floatingObjects->decreaseObjectsCount(r->type());
    3263             floatingObjectSet.remove(it);
     3261            m_floatingObjects->remove(r);
    32643262            ASSERT(!r->m_originatingLine);
    32653263            delete r;
    … …  
    32733271        return;
    32743272   
    3275     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3273    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    32763274    FloatingObject* curr = floatingObjectSet.last();
    32773275    while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
    3278         m_floatingObjects->decreaseObjectsCount(curr->type());
    3279         floatingObjectSet.removeLast();
     3276        m_floatingObjects->remove(curr);
    32803277        ASSERT(!curr->m_originatingLine);
    32813278        delete curr;
    … …  
    32893286        return false;
    32903287
    3291     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3288    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    32923289    if (floatingObjectSet.isEmpty())
    32933290        return false;
    … …  
    34043401        setLogicalHeightForFloat(floatingObject, logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
    34053402
    3406         floatingObject->setIsPlaced();
     3403        m_floatingObjects->addPlacedObject(floatingObject);
    34073404
    34083405        // If the child moved, we have to repaint it.
    … …  
    35063503#endif
    35073504
    3508 // FIXME: The logicalLeftOffsetForLine/logicalRightOffsetForLine functions are very slow if there are many floats
    3509 // present. We need to add a structure to floating objects to represent "lines" of floats.  Then instead of checking
    3510 // each float individually, we'd just walk backwards through the "lines" and stop when we hit a line that is fully above
    3511 // the vertical offset that we'd like to check.  Computing the "lines" would be rather complicated, but could replace the left
    3512 // objects and right objects count hack that is currently used here.
     3505template <RenderBlock::FloatingObject::Type FloatTypeValue>
     3506inline void RenderBlock::FloatIntervalSearchAdapter<FloatTypeValue>::collectIfNeeded(const IntervalType& interval) const
     3507{
     3508    const FloatingObject* r = interval.data();
     3509    if (r->type() == FloatTypeValue && interval.low() <= m_value && m_value < interval.high()) {
     3510        // All the objects returned from the tree should be already placed.
     3511        ASSERT(r->isPlaced() && m_renderer->logicalTopForFloat(r) <= m_value && m_renderer->logicalBottomForFloat(r) > m_value);
     3512
     3513        if (FloatTypeValue == FloatingObject::FloatLeft
     3514            && m_renderer->logicalRightForFloat(r) > m_offset) {
     3515            m_offset = m_renderer->logicalRightForFloat(r);
     3516            if (m_heightRemaining)
     3517                *m_heightRemaining = m_renderer->logicalBottomForFloat(r) - m_value;
     3518        }
     3519
     3520        if (FloatTypeValue == FloatingObject::FloatRight
     3521            && m_renderer->logicalLeftForFloat(r) < m_offset) {
     3522            m_offset = m_renderer->logicalLeftForFloat(r);
     3523            if (m_heightRemaining)
     3524                *m_heightRemaining = m_renderer->logicalBottomForFloat(r) - m_value;
     3525        }
     3526    }
     3527}
     3528
    35133529LayoutUnit RenderBlock::logicalLeftOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, bool applyTextIndent, LayoutUnit* heightRemaining) const
    35143530{
    … …  
    35183534            *heightRemaining = 1;
    35193535
    3520         // We know the list is non-empty, since we have "left" objects to search for.
    3521         // Therefore we can assume that begin != end, and that we can do at least one
    3522         // decrement.
    3523         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    3524         FloatingObjectSetIterator begin = floatingObjectSet.begin();
    3525         FloatingObjectSetIterator it = floatingObjectSet.end();
    3526         do {
    3527             --it;
    3528             FloatingObject* r = *it;
    3529             if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
    3530                 && r->type() == FloatingObject::FloatLeft
    3531                 && logicalRightForFloat(r) > left) {
    3532                 left = max(left, logicalRightForFloat(r));
    3533                 if (heightRemaining)
    3534                     *heightRemaining = logicalBottomForFloat(r) - logicalTop;
    3535             }
    3536         } while (it != begin);
     3536        FloatIntervalSearchAdapter<FloatingObject::FloatLeft> adapter(this, logicalTop, left, heightRemaining);
     3537        m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
    35373538    }
    35383539
    … …  
    35543555        if (heightRemaining)
    35553556            *heightRemaining = 1;
    3556            
    3557         // We know the list is non-empty, since we have "right" objects to search for.
    3558         // Therefore we can assume that begin != end, and that we can do at least one
    3559         // decrement.
    3560         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    3561         FloatingObjectSetIterator begin = floatingObjectSet.begin();
    3562         FloatingObjectSetIterator it = floatingObjectSet.end();
    3563         do {
    3564             --it;
    3565             FloatingObject* r = *it;
    3566             if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
    3567                 && r->type() == FloatingObject::FloatRight
    3568                 && logicalLeftForFloat(r) < right) {
    3569                 right = min(right, logicalLeftForFloat(r));
    3570                 if (heightRemaining)
    3571                     *heightRemaining = logicalBottomForFloat(r) - logicalTop;
    3572             }
    3573         } while (it != begin);
     3557
     3558        FloatIntervalSearchAdapter<FloatingObject::FloatRight> adapter(this, logicalTop, right, heightRemaining);
     3559        m_floatingObjects->placedFloatsTree().allOverlapsWithAdapter(adapter);
    35743560    }
    35753561   
    … …  
    35963582
    35973583    int bottom = INT_MAX;
    3598     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3584    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    35993585    FloatingObjectSetIterator end = floatingObjectSet.end();
    36003586    for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    36133599        return 0;
    36143600    int lowestFloatBottom = 0;
    3615     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3601    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    36163602    FloatingObjectSetIterator end = floatingObjectSet.end();
    36173603    for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    36613647        setLogicalTopForFloat(floatingObject, logicalTopForChild(positionedObject) - marginBeforeForChild(positionedObject));
    36623648        setLogicalHeightForFloat(floatingObject, logicalHeightForChild(positionedObject) + marginBeforeForChild(positionedObject) + marginAfterForChild(positionedObject));
    3663         floatingObject->setIsPlaced(true);
     3649
     3650        m_floatingObjects->addPlacedObject(floatingObject);
    36643651       
    36653652        m_hasPositionedFloats = true;
    … …  
    36693656void RenderBlock::clearFloats(BlockLayoutPass layoutPass)
    36703657{
     3658    if (m_floatingObjects)
     3659        m_floatingObjects->setHorizontalWritingMode(isHorizontalWritingMode());
     3660
    36713661    // Clear our positioned floats boolean.
    36723662    m_hasPositionedFloats = false;
    … …  
    36873677
    36883678    if (m_floatingObjects) {
    3689         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3679        const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    36903680        if (childrenInline()) {
    3691             FloatingObjectSet::iterator end = floatingObjectSet.end();
    3692             for (FloatingObjectSet::iterator it = floatingObjectSet.begin(); it != end; ++it) {
     3681            FloatingObjectSetIterator end = floatingObjectSet.end();
     3682            for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    36933683                FloatingObject* f = *it;
    36943684                floatMap.add(f->m_renderer, f);
    … …  
    37423732        int changeLogicalBottom = numeric_limits<int>::min();
    37433733        if (m_floatingObjects) {
    3744             FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3734            const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    37453735            FloatingObjectSetIterator end = floatingObjectSet.end();
    37463736            for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    38243814                // We create the floating object list lazily.
    38253815                if (!m_floatingObjects)
    3826                     m_floatingObjects = adoptPtr(new FloatingObjects);
    3827 
    3828                 m_floatingObjects->increaseObjectsCount(floatingObj->type());
    3829                 m_floatingObjects->set().add(floatingObj);
     3816                    m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
     3817
     3818                m_floatingObjects->add(floatingObj);
    38303819            }
    38313820        } else {
    … …  
    38543843        return false;
    38553844
    3856     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3845    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    38573846    FloatingObjectSetIterator it = floatingObjectSet.find<RenderBox*, FloatingObjectHashTranslator>(renderer);
    38583847    if (it == floatingObjectSet.end())
    … …  
    38703859    logicalLeftOffset += (isHorizontalWritingMode() ? marginLeft() : marginTop());
    38713860
    3872     FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
     3861    const FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
    38733862    FloatingObjectSetIterator prevEnd = prevSet.end();
    38743863    for (FloatingObjectSetIterator prevIt = prevSet.begin(); prevIt != prevEnd; ++prevIt) {
    … …  
    38983887                // We create the floating object list lazily.
    38993888                if (!m_floatingObjects)
    3900                     m_floatingObjects = adoptPtr(new FloatingObjects);
    3901                 m_floatingObjects->increaseObjectsCount(floatingObj->type());
    3902                 m_floatingObjects->set().add(floatingObj);
     3889                    m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
     3890                m_floatingObjects->add(floatingObj);
    39033891            }
    39043892        }
    … …  
    39413929void RenderBlock::markSiblingsWithFloatsForLayout()
    39423930{
    3943     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     3931    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    39443932    FloatingObjectSetIterator end = floatingObjectSet.end();
    39453933    for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    40934081    }
    40944082
    4095     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     4083    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    40964084    FloatingObjectSetIterator begin = floatingObjectSet.begin();
    40974085    for (FloatingObjectSetIterator it = floatingObjectSet.end(); it != begin;) {
    … …  
    57005688       
    57015689        if (m_floatingObjects) {
    5702             FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     5690            const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    57035691            FloatingObjectSetIterator end = floatingObjectSet.end();
    57045692            for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    64446432{
    64456433    m_set.clear();
     6434    m_placedFloatsTree.clear();
    64466435    m_leftObjectsCount = 0;
    64476436    m_rightObjectsCount = 0;
    … …  
    64696458}
    64706459
     6460inline RenderBlock::FloatingObjectInterval RenderBlock::FloatingObjects::intervalForFloatingObject(FloatingObject* floatingObject)
     6461{
     6462    if (m_horizontalWritingMode)
     6463        return RenderBlock::FloatingObjectInterval(floatingObject->y(), floatingObject->maxY(), floatingObject);
     6464    return RenderBlock::FloatingObjectInterval(floatingObject->x(), floatingObject->maxX(), floatingObject);
     6465}
     6466
     6467void RenderBlock::FloatingObjects::addPlacedObject(FloatingObject* floatingObject)
     6468{
     6469    ASSERT(!floatingObject->isInPlacedTree());
     6470
     6471    floatingObject->setIsPlaced(true);
     6472    if (m_placedFloatsTree.isInitialized())
     6473        m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
     6474
     6475#ifndef NDEBUG
     6476    floatingObject->setIsInPlacedTree(true);     
     6477#endif
     6478}
     6479
     6480void RenderBlock::FloatingObjects::removePlacedObject(FloatingObject* floatingObject)
     6481{
     6482    ASSERT(floatingObject->isPlaced() && floatingObject->isInPlacedTree());
     6483
     6484    if (m_placedFloatsTree.isInitialized()) {
     6485        bool removed = m_placedFloatsTree.remove(intervalForFloatingObject(floatingObject));
     6486        ASSERT_UNUSED(removed, removed);
     6487    }
     6488   
     6489    floatingObject->setIsPlaced(false);
     6490#ifndef NDEBUG
     6491    floatingObject->setIsInPlacedTree(false);
     6492#endif
     6493}
     6494
     6495inline void RenderBlock::FloatingObjects::add(FloatingObject* floatingObject)
     6496{
     6497    increaseObjectsCount(floatingObject->type());
     6498    m_set.add(floatingObject);
     6499    if (floatingObject->isPlaced())
     6500        addPlacedObject(floatingObject);
     6501}
     6502
     6503inline void RenderBlock::FloatingObjects::remove(FloatingObject* floatingObject)
     6504{
     6505    decreaseObjectsCount(floatingObject->type());
     6506    m_set.remove(floatingObject);
     6507    ASSERT(floatingObject->isPlaced() || !floatingObject->isInPlacedTree());
     6508    if (floatingObject->isPlaced())
     6509        removePlacedObject(floatingObject);
     6510}
     6511
     6512void RenderBlock::FloatingObjects::computePlacedFloatsTree()
     6513{
     6514    ASSERT(!m_placedFloatsTree.isInitialized());
     6515    if (m_set.isEmpty())
     6516        return;
     6517    m_placedFloatsTree.initIfNeeded();
     6518    FloatingObjectSetIterator it = m_set.begin();
     6519    FloatingObjectSetIterator end = m_set.end();
     6520    for (; it != end; ++it) {
     6521        FloatingObject* floatingObject = *it;
     6522        if (floatingObject->isPlaced())
     6523            m_placedFloatsTree.add(intervalForFloatingObject(floatingObject));
     6524    }
     6525}
     6526
    64716527TextRun RenderBlock::constructTextRun(RenderObject* context, const Font& font, const UChar* characters, int length, RenderStyle* style, TextRun::ExpansionBehavior expansion, TextRunFlags flags)
    64726528{
    … …  
    65036559}
    65046560
     6561// These helpers are only used by the PODIntervalTree for debugging purposes.
     6562String ValueToString<int>::string(const int value)
     6563{
     6564    return String::number(value);
     6565}
     6566
     6567String ValueToString<RenderBlock::FloatingObject*>::string(const RenderBlock::FloatingObject* floatingObject)
     6568{
     6569    return String::format("%p (%dx%d %dx%d)", floatingObject, floatingObject->x(), floatingObject->y(), floatingObject->maxX(), floatingObject->maxY());
     6570}
     6571
    65056572#endif
    65066573

  • trunk/Source/WebCore/rendering/RenderBlock.h

    r92438 r92610  
    2525
    2626#include "GapRects.h"
     27#include "PODIntervalTree.h"
    2728#include "RenderBox.h"
    2829#include "RenderLineBoxList.h"
    … …  
    6869public:
    6970    friend class LineLayoutState;
     71#ifndef NDEBUG
     72    // Used by the PODIntervalTree for debugging the FloatingObject.
     73    template <class> friend struct ValueToString;
     74#endif
     75
    7076    RenderBlock(Node*);
    7177    virtual ~RenderBlock();
    … …  
    423429            , m_isDescendant(false)
    424430            , m_isPlaced(false)
     431#ifndef NDEBUG
     432            , m_isInPlacedTree(false)
     433#endif
    425434        {
    426435            ASSERT(type != NoFloat);
    … …  
    442451            , m_isDescendant(false)
    443452            , m_isPlaced(true)
     453#ifndef NDEBUG
     454            , m_isInPlacedTree(false)
     455#endif
    444456        {
    445457        }
    … …  
    458470        int height() const { return m_frameRect.height(); }
    459471
    460         void setX(int x) { m_frameRect.setX(x); }
    461         void setY(int y) { m_frameRect.setY(y); }
    462         void setWidth(int width) { m_frameRect.setWidth(width); }
    463         void setHeight(int height) { m_frameRect.setHeight(height); }
     472        void setX(int x) { ASSERT(!isInPlacedTree()); m_frameRect.setX(x); }
     473        void setY(int y) { ASSERT(!isInPlacedTree()); m_frameRect.setY(y); }
     474        void setWidth(int width) { ASSERT(!isInPlacedTree()); m_frameRect.setWidth(width); }
     475        void setHeight(int height) { ASSERT(!isInPlacedTree()); m_frameRect.setHeight(height); }
    464476
    465477        const IntRect& frameRect() const { ASSERT(isPlaced()); return m_frameRect; }
    466         void setFrameRect(const IntRect& frameRect) { m_frameRect = frameRect; }
     478        void setFrameRect(const IntRect& frameRect) { ASSERT(!isInPlacedTree()); m_frameRect = frameRect; }
     479
     480#ifndef NDEBUG
     481        bool isInPlacedTree() const { return m_isInPlacedTree; }
     482        void setIsInPlacedTree(bool value) { m_isInPlacedTree = value; }
     483#endif
    467484
    468485        RenderBox* m_renderer;
    … …  
    474491        bool m_isDescendant : 1;
    475492        bool m_isPlaced : 1;
     493#ifndef NDEBUG
     494        bool m_isInPlacedTree : 1;
     495#endif
    476496    };
    477497
    … …  
    800820    typedef ListHashSet<FloatingObject*, 4, FloatingObjectHashFunctions> FloatingObjectSet;
    801821    typedef FloatingObjectSet::const_iterator FloatingObjectSetIterator;
     822    typedef PODInterval<LayoutUnit, FloatingObject*> FloatingObjectInterval;
     823    typedef PODIntervalTree<LayoutUnit, FloatingObject*> FloatingObjectTree;
     824   
     825    template <FloatingObject::Type FloatTypeValue>
     826    class FloatIntervalSearchAdapter {
     827    public:
     828        typedef FloatingObjectInterval IntervalType;
     829       
     830        FloatIntervalSearchAdapter(const RenderBlock* renderer, LayoutUnit value, LayoutUnit& offset, LayoutUnit* heightRemaining)
     831            : m_renderer(renderer)
     832            , m_value(value)
     833            , m_offset(offset)
     834            , m_heightRemaining(heightRemaining)
     835        {
     836        }
     837       
     838        inline LayoutUnit lowValue() const { return m_value; }
     839        inline LayoutUnit highValue() const { return m_value; }
     840        void collectIfNeeded(const IntervalType&) const;
     841
     842    private:
     843        const RenderBlock* m_renderer;
     844        LayoutUnit m_value;
     845        LayoutUnit& m_offset;
     846        LayoutUnit* m_heightRemaining;
     847    };
     848
    802849    class FloatingObjects {
    803850    public:
    804         FloatingObjects()
    805             : m_leftObjectsCount(0)
     851        FloatingObjects(bool horizontalWritingMode)
     852            : m_placedFloatsTree(UninitializedTree)
     853            , m_leftObjectsCount(0)
    806854            , m_rightObjectsCount(0)
    807855            , m_positionedObjectsCount(0)
     856            , m_horizontalWritingMode(horizontalWritingMode)
    808857        {
    809858        }
    810859
    811860        void clear();
    812         void increaseObjectsCount(FloatingObject::Type);
    813         void decreaseObjectsCount(FloatingObject::Type);
     861        void add(FloatingObject*);
     862        void remove(FloatingObject*);
     863        void addPlacedObject(FloatingObject*);
     864        void removePlacedObject(FloatingObject*);
     865        void setHorizontalWritingMode(bool b = true) { m_horizontalWritingMode = b; }
     866
    814867        bool hasLeftObjects() const { return m_leftObjectsCount > 0; }
    815868        bool hasRightObjects() const { return m_rightObjectsCount > 0; }
    816869        bool hasPositionedObjects() const { return m_positionedObjectsCount > 0; }
    817         FloatingObjectSet& set() { return m_set; }
    818 
     870        const FloatingObjectSet& set() const { return m_set; }
     871        const FloatingObjectTree& placedFloatsTree()
     872        {
     873            computePlacedFloatsTreeIfNeeded();
     874            return m_placedFloatsTree;
     875        }
    819876    private:
     877        void computePlacedFloatsTree();
     878        inline void computePlacedFloatsTreeIfNeeded()
     879        {
     880            if (!m_placedFloatsTree.isInitialized())
     881                computePlacedFloatsTree();
     882        }
     883        void increaseObjectsCount(FloatingObject::Type);
     884        void decreaseObjectsCount(FloatingObject::Type);
     885        FloatingObjectInterval intervalForFloatingObject(FloatingObject*);
     886
    820887        FloatingObjectSet m_set;
     888        FloatingObjectTree m_placedFloatsTree;
    821889        unsigned m_leftObjectsCount;
    822890        unsigned m_rightObjectsCount;
    823891        unsigned m_positionedObjectsCount;
     892        bool m_horizontalWritingMode;
    824893    };
    825894    OwnPtr<FloatingObjects> m_floatingObjects;
    … …  
    896965void toRenderBlock(const RenderBlock*);
    897966
     967#ifndef NDEBUG
     968// These structures are used by PODIntervalTree for debugging purposes.
     969template <> struct ValueToString<int> {
     970    static String string(const int value);
     971};
     972template<> struct ValueToString<RenderBlock::FloatingObject*> {
     973    static String string(const RenderBlock::FloatingObject*);
     974};
     975#endif
     976
    898977} // namespace WebCore
    899978

  • trunk/Source/WebCore/rendering/RenderBlockLineLayout.cpp

    r92207 r92610  
    10921092
    10931093        if (m_floatingObjects && lastRootBox()) {
    1094             FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     1094            const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    10951095            FloatingObjectSetIterator it = floatingObjectSet.begin();
    10961096            FloatingObjectSetIterator end = floatingObjectSet.end();
    … …  
    11731173        }
    11741174
    1175         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     1175        const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    11761176        FloatingObjectSetIterator it = floatingObjectSet.begin();
    11771177        FloatingObjectSetIterator end = floatingObjectSet.end();
    … …  
    14921492        int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
    14931493
    1494         FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     1494        const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    14951495        FloatingObjectSetIterator end = floatingObjectSet.end();
    14961496        for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    15291529                int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
    15301530
    1531                 FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     1531                const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    15321532                FloatingObjectSetIterator end = floatingObjectSet.end();
    15331533                for (FloatingObjectSetIterator it = floatingObjectSet.begin(); it != end; ++it) {
    … …  
    25512551        return true;
    25522552
    2553     FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
     2553    const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
    25542554    ASSERT(floatingObjectSet.last() == newFloat);
    25552555
    … …  
    25762576                toRenderBlock(o)->setChildNeedsLayout(true, false);
    25772577            o->layoutIfNeeded();
     2578            m_floatingObjects->removePlacedObject(f);
    25782579            setLogicalTopForFloat(f, logicalTopForFloat(f) + f->m_paginationStrut);
     2580            m_floatingObjects->addPlacedObject(f);
    25792581        }
    25802582    }
Note: See TracChangeset for help on using the changeset viewer.