Changeset 79817 in webkit


Ignore:
Timestamp:
Feb 27, 2011 7:51:19 AM (13 years ago)
Author:
benjamin.poulain@nokia.com
Message:

Eliminate DeprecatedPtrList from RenderBlock
https://bugs.webkit.org/show_bug.cgi?id=54972

Patch by Benjamin Poulain <ikipou@gmail.com> on 2011-02-27
Reviewed by Darin Adler.

Source/JavaScriptCore:

Add methods find() and contains() using an adaptor to ListHashSet.
Those method are like the one of HashSet, they allow to find objects
based on a different key than the one used to define the set.

Add convenience methods for direct access to the head and tail of the list.
Those methods are providing similar API/behavior as Vector.

  • wtf/ListHashSet.h:

(WTF::::first):
(WTF::::last):
(WTF::::removeLast):
(WTF::ListHashSetTranslatorAdapter::hash):
(WTF::ListHashSetTranslatorAdapter::equal):
(WTF::::find):
(WTF::::contains):

Source/WebCore:

Refactor RenderBlock to get rid of the DeprecatedPtrList.
The floating objects are stored in a ListHashSet.

Refactoring covered by existing test.

  • rendering/RenderBlock.cpp:

(WebCore::RenderBlock::~RenderBlock):
(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::positionNewFloatOnLine):
(WebCore::RenderBlock::logicalLeftOffsetForLine):
(WebCore::RenderBlock::logicalRightOffsetForLine):
(WebCore::RenderBlock::nextFloatLogicalBottomBelow):
(WebCore::RenderBlock::lowestFloatLogicalBottom):
(WebCore::RenderBlock::clearFloats):
(WebCore::RenderBlock::addOverhangingFloats):
(WebCore::RenderBlock::addIntrudingFloats):
(WebCore::RenderBlock::containsFloat):
(WebCore::RenderBlock::hitTestFloats):
(WebCore::RenderBlock::adjustForBorderFit):

  • rendering/RenderBlock.h:

(WebCore::RenderBlock::FloatingObjectHashFunctions::hash):
(WebCore::RenderBlock::FloatingObjectHashFunctions::equal):
(WebCore::RenderBlock::FloatingObjectHashTranslator::hash):
(WebCore::RenderBlock::FloatingObjectHashTranslator::equal):

  • rendering/RenderBlockLineLayout.cpp:

(WebCore::RenderBlock::layoutInlineChildren):
(WebCore::RenderBlock::matchedEndLine):

Location:
trunk/Source
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r79812 r79817  
     12011-02-27  Benjamin Poulain  <ikipou@gmail.com>
     2
     3        Reviewed by Darin Adler.
     4
     5        Eliminate DeprecatedPtrList from RenderBlock
     6        https://bugs.webkit.org/show_bug.cgi?id=54972
     7
     8        Add methods find() and contains() using an adaptor to ListHashSet.
     9        Those method are like the one of HashSet, they allow to find objects
     10        based on a different key than the one used to define the set.
     11
     12        Add convenience methods for direct access to the head and tail of the list.
     13        Those methods are providing similar API/behavior as Vector.
     14
     15        * wtf/ListHashSet.h:
     16        (WTF::::first):
     17        (WTF::::last):
     18        (WTF::::removeLast):
     19        (WTF::ListHashSetTranslatorAdapter::hash):
     20        (WTF::ListHashSetTranslatorAdapter::equal):
     21        (WTF::::find):
     22        (WTF::::contains):
     23
    1242011-02-26  Patrick Gansterer  <paroga@webkit.org>
    225
  • trunk/Source/JavaScriptCore/wtf/ListHashSet.h

    r76248 r79817  
    11/*
    22 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
     3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
    34 *
    45 * This library is free software; you can redistribute it and/or
     
    9192        const_iterator end() const;
    9293
     94        ValueType& first();
     95        const ValueType& first() const;
     96
     97        ValueType& last();
     98        const ValueType& last() const;
     99        void removeLast();
     100
    93101        iterator find(const ValueType&);
    94102        const_iterator find(const ValueType&) const;
    95103        bool contains(const ValueType&) const;
     104
     105        // An alternate version of find() that finds the object by hashing and comparing
     106        // with some other type, to avoid the cost of type conversion.
     107        // The HashTranslator interface is defined in HashSet.
     108        template<typename T, typename HashTranslator> iterator find(const T&);
     109        template<typename T, typename HashTranslator> const_iterator find(const T&) const;
     110        template<typename T, typename HashTranslator> bool contains(const T&) const;
    96111
    97112        // the return value is a pair of an iterator to the new value's location,
     
    443458
    444459    template<typename T, size_t inlineCapacity, typename U>
     460    inline T& ListHashSet<T, inlineCapacity, U>::first()
     461    {
     462        ASSERT(!isEmpty());
     463        return m_head->m_value;
     464    }
     465
     466    template<typename T, size_t inlineCapacity, typename U>
     467    inline const T& ListHashSet<T, inlineCapacity, U>::first() const
     468    {
     469        ASSERT(!isEmpty());
     470        return m_head->m_value;
     471    }
     472
     473    template<typename T, size_t inlineCapacity, typename U>
     474    inline T& ListHashSet<T, inlineCapacity, U>::last()
     475    {
     476        ASSERT(!isEmpty());
     477        return m_tail->m_value;
     478    }
     479
     480    template<typename T, size_t inlineCapacity, typename U>
     481    inline const T& ListHashSet<T, inlineCapacity, U>::last() const
     482    {
     483        ASSERT(!isEmpty());
     484        return m_tail->m_value;
     485    }
     486
     487    template<typename T, size_t inlineCapacity, typename U>
     488    inline void ListHashSet<T, inlineCapacity, U>::removeLast()
     489    {
     490        ASSERT(!isEmpty());
     491        m_impl.remove(m_tail);
     492        unlinkAndDelete(m_tail);
     493    }
     494
     495    template<typename T, size_t inlineCapacity, typename U>
    445496    inline typename ListHashSet<T, inlineCapacity, U>::iterator ListHashSet<T, inlineCapacity, U>::find(const ValueType& value)
    446497    {
     
    460511            return end();
    461512        return makeConstIterator(*it);
     513    }
     514
     515    template<typename ValueType, size_t inlineCapacity, typename T, typename Translator>
     516    struct ListHashSetTranslatorAdapter {
     517    private:
     518        typedef ListHashSetNode<ValueType, inlineCapacity> Node;
     519    public:
     520        static unsigned hash(const T& key) { return Translator::hash(key); }
     521        static bool equal(Node* const& a, const T& b) { return Translator::equal(a->m_value, b); }
     522    };
     523
     524    template<typename ValueType, size_t inlineCapacity, typename U>
     525    template<typename T, typename HashTranslator>
     526    inline typename ListHashSet<ValueType, inlineCapacity, U>::iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value)
     527    {
     528        typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
     529        ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value);
     530        if (it == m_impl.end())
     531            return end();
     532        return makeIterator(*it);
     533    }
     534
     535    template<typename ValueType, size_t inlineCapacity, typename U>
     536    template<typename T, typename HashTranslator>
     537    inline typename ListHashSet<ValueType, inlineCapacity, U>::const_iterator ListHashSet<ValueType, inlineCapacity, U>::find(const T& value) const
     538    {
     539        typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
     540        ImplTypeConstIterator it = m_impl.template find<T, Adapter>(value);
     541        if (it == m_impl.end())
     542            return end();
     543        return makeConstIterator(*it);
     544    }
     545
     546    template<typename ValueType, size_t inlineCapacity, typename U>
     547    template<typename T, typename HashTranslator>
     548    inline bool ListHashSet<ValueType, inlineCapacity, U>::contains(const T& value) const
     549    {
     550        typedef ListHashSetTranslatorAdapter<ValueType, inlineCapacity, T, HashTranslator> Adapter;
     551        return m_impl.template contains<T, Adapter>(value);
    462552    }
    463553
  • trunk/Source/WebCore/ChangeLog

    r79816 r79817  
     12011-02-27  Benjamin Poulain  <ikipou@gmail.com>
     2
     3        Reviewed by Darin Adler.
     4
     5        Eliminate DeprecatedPtrList from RenderBlock
     6        https://bugs.webkit.org/show_bug.cgi?id=54972
     7
     8        Refactor RenderBlock to get rid of the DeprecatedPtrList.
     9        The floating objects are stored in a ListHashSet.
     10
     11        Refactoring covered by existing test.
     12
     13        * rendering/RenderBlock.cpp:
     14        (WebCore::RenderBlock::~RenderBlock):
     15        (WebCore::RenderBlock::addOverflowFromFloats):
     16        (WebCore::RenderBlock::repaintOverhangingFloats):
     17        (WebCore::RenderBlock::paintFloats):
     18        (WebCore::RenderBlock::selectionGaps):
     19        (WebCore::RenderBlock::insertFloatingObject):
     20        (WebCore::RenderBlock::removeFloatingObject):
     21        (WebCore::RenderBlock::removeFloatingObjectsBelow):
     22        (WebCore::RenderBlock::positionNewFloats):
     23        (WebCore::RenderBlock::positionNewFloatOnLine):
     24        (WebCore::RenderBlock::logicalLeftOffsetForLine):
     25        (WebCore::RenderBlock::logicalRightOffsetForLine):
     26        (WebCore::RenderBlock::nextFloatLogicalBottomBelow):
     27        (WebCore::RenderBlock::lowestFloatLogicalBottom):
     28        (WebCore::RenderBlock::clearFloats):
     29        (WebCore::RenderBlock::addOverhangingFloats):
     30        (WebCore::RenderBlock::addIntrudingFloats):
     31        (WebCore::RenderBlock::containsFloat):
     32        (WebCore::RenderBlock::hitTestFloats):
     33        (WebCore::RenderBlock::adjustForBorderFit):
     34        * rendering/RenderBlock.h:
     35        (WebCore::RenderBlock::FloatingObjectHashFunctions::hash):
     36        (WebCore::RenderBlock::FloatingObjectHashFunctions::equal):
     37        (WebCore::RenderBlock::FloatingObjectHashTranslator::hash):
     38        (WebCore::RenderBlock::FloatingObjectHashTranslator::equal):
     39        * rendering/RenderBlockLineLayout.cpp:
     40        (WebCore::RenderBlock::layoutInlineChildren):
     41        (WebCore::RenderBlock::matchedEndLine):
     42
    1432011-02-26  Adam Barth  <abarth@webkit.org>
    244
  • trunk/Source/WebCore/rendering/RenderBlock.cpp

    r79734 r79817  
    123123RenderBlock::~RenderBlock()
    124124{
     125    if (m_floatingObjects)
     126        deleteAllValues(*m_floatingObjects);
    125127    delete m_floatingObjects;
    126128    delete m_positionedObjects;
     
    13801382    if (!m_floatingObjects)
    13811383        return;
    1382     FloatingObject* r;
    1383     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    1384     for (; (r = it.current()); ++it) {
     1384
     1385    FloatingObjectSetIterator end = m_floatingObjects->end();
     1386    for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     1387        FloatingObject* r = *it;
    13851388        if (r->m_isDescendant)
    13861389            addOverflowFromChild(r->m_renderer, IntSize(xPositionForFloatIncludingMargin(r), yPositionForFloatIncludingMargin(r)));
     
    21732176        if (!m_floatingObjects)
    21742177            return;
    2175        
    2176         FloatingObject* r;
    2177         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    21782178
    21792179        // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
    21802180        // in this block. Better yet would be to push extra state for the containers of other floats.
    21812181        view()->disableLayoutState();
    2182         for ( ; (r = it.current()); ++it) {
     2182        FloatingObjectSetIterator end = m_floatingObjects->end();
     2183        for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     2184            FloatingObject* r = *it;
    21832185            // Only repaint the object if it is overhanging, is not in its own layer, and
    21842186            // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
     
    25042506        return;
    25052507
    2506     FloatingObject* r;
    2507     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    2508     for (; (r = it.current()); ++it) {
     2508    FloatingObjectSetIterator end = m_floatingObjects->end();
     2509    for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     2510        FloatingObject* r = *it;
    25092511        // Only paint the object if our m_shouldPaint flag is set.
    25102512        if (r->m_shouldPaint && !r->m_renderer->hasSelfPaintingLayer()) {
     
    27562758                clipOutPositionedObjects(paintInfo, IntPoint(cb->x(), cb->y()), cb->m_positionedObjects); // FIXME: Not right for flipped writing modes.
    27572759        if (m_floatingObjects) {
    2758             for (DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects); it.current(); ++it) {
    2759                 FloatingObject* r = it.current();
     2760            FloatingObjectSetIterator end = m_floatingObjects->end();
     2761            for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     2762                FloatingObject* r = *it;
    27602763                IntRect floatBox = IntRect(offsetFromRootBlock.width() + xPositionForFloatIncludingMargin(r),
    27612764                                           offsetFromRootBlock.height() + yPositionForFloatIncludingMargin(r),
     
    30643067
    30653068    // Create the list of special objects if we don't aleady have one
    3066     if (!m_floatingObjects) {
    3067         m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
    3068         m_floatingObjects->setAutoDelete(true);
    3069     } else {
     3069    if (!m_floatingObjects)
     3070        m_floatingObjects = new FloatingObjectSet;
     3071    else {
    30703072        // Don't insert the object again if it's already in the list
    3071         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3072         FloatingObject* f;
    3073         while ( (f = it.current()) ) {
    3074             if (f->m_renderer == o)
    3075                 return f;
    3076             ++it;
    3077         }
     3073        FloatingObjectSetIterator it = m_floatingObjects->find<RenderBox*, FloatingObjectHashTranslator>(o);
     3074        if (it != m_floatingObjects->end())
     3075            return *it;
    30783076    }
    30793077
     
    31013099    newObj->m_renderer = o;
    31023100
    3103     m_floatingObjects->append(newObj);
     3101    m_floatingObjects->add(newObj);
    31043102   
    31053103    return newObj;
     
    31093107{
    31103108    if (m_floatingObjects) {
    3111         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3112         while (it.current()) {
    3113             if (it.current()->m_renderer == o) {
    3114                 if (childrenInline()) {
    3115                     int logicalTop = logicalTopForFloat(it.current());
    3116                     int logicalBottom = logicalBottomForFloat(it.current());
    3117                    
    3118                     // Fix for https://bugs.webkit.org/show_bug.cgi?id=54995.
    3119                     if (logicalBottom < 0 || logicalBottom < logicalTop || logicalTop == numeric_limits<int>::max())
    3120                         logicalBottom = numeric_limits<int>::max();
    3121                     else {
    3122                         // Special-case zero- and less-than-zero-height floats: those don't touch
    3123                         // the line that they're on, but it still needs to be dirtied. This is
    3124                         // accomplished by pretending they have a height of 1.
    3125                         logicalBottom = max(logicalBottom, logicalTop + 1);
    3126                     }
    3127                     markLinesDirtyInBlockRange(0, logicalBottom);
     3109        FloatingObjectSet::iterator it = m_floatingObjects->find<RenderBox*, FloatingObjectHashTranslator>(o);
     3110        if (it != m_floatingObjects->end()) {
     3111            FloatingObject* r = *it;
     3112            if (childrenInline()) {
     3113                int logicalTop = logicalTopForFloat(r);
     3114                int logicalBottom = logicalBottomForFloat(r);
     3115
     3116                // Fix for https://bugs.webkit.org/show_bug.cgi?id=54995.
     3117                if (logicalBottom < 0 || logicalBottom < logicalTop || logicalTop == numeric_limits<int>::max())
     3118                    logicalBottom = numeric_limits<int>::max();
     3119                else {
     3120                    // Special-case zero- and less-than-zero-height floats: those don't touch
     3121                    // the line that they're on, but it still needs to be dirtied. This is
     3122                    // accomplished by pretending they have a height of 1.
     3123                    logicalBottom = max(logicalBottom, logicalTop + 1);
    31283124                }
    3129                 m_floatingObjects->removeRef(it.current());
     3125                markLinesDirtyInBlockRange(0, logicalBottom);
    31303126            }
    3131             ++it;
     3127            m_floatingObjects->remove(it);
     3128            delete r;
    31323129        }
    31333130    }
     
    31423139    while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
    31433140        m_floatingObjects->removeLast();
     3141        delete curr;
    31443142        curr = m_floatingObjects->last();
    31453143    }
     
    31503148    if (!m_floatingObjects)
    31513149        return false;
    3152    
    3153     FloatingObject* floatingObject = m_floatingObjects->last();
     3150
     3151    if (m_floatingObjects->isEmpty())
     3152        return false;
    31543153
    31553154    // If all floats have already been positioned, then we have no work to do.
    3156     if (!floatingObject || floatingObject->isPlaced())
     3155    if (m_floatingObjects->last()->isPlaced())
    31573156        return false;
    31583157
     
    31603159    // already been positioned.  Then we'll be able to move forward, positioning all of
    31613160    // the new floats that need it.
    3162     FloatingObject* lastFloat = m_floatingObjects->getPrev();
    3163     while (lastFloat && !lastFloat->isPlaced()) {
    3164         floatingObject = m_floatingObjects->prev();
    3165         lastFloat = m_floatingObjects->getPrev();
     3161    FloatingObjectSetIterator it = m_floatingObjects->end();
     3162    --it; // Go to last item.
     3163    FloatingObjectSetIterator begin = m_floatingObjects->begin();
     3164    FloatingObject* lastPlacedFloatingObject = 0;
     3165    while (it != begin) {
     3166        --it;
     3167        if ((*it)->isPlaced()) {
     3168            lastPlacedFloatingObject = *it;
     3169            ++it;
     3170            break;
     3171        }
    31663172    }
    31673173
     
    31693175   
    31703176    // The float cannot start above the top position of the last positioned float.
    3171     if (lastFloat)
    3172         logicalTop = max(logicalTopForFloat(lastFloat), logicalTop);
    3173 
     3177    if (lastPlacedFloatingObject)
     3178        logicalTop = max(logicalTopForFloat(lastPlacedFloatingObject), logicalTop);
     3179
     3180    FloatingObjectSetIterator end = m_floatingObjects->end();
    31743181    // Now walk through the set of unpositioned floats and place them.
    3175     while (floatingObject) {
     3182    for (; it != end; ++it) {
     3183         FloatingObject* floatingObject = *it;
    31763184        // The containing block is responsible for positioning floats, so if we have floats in our
    31773185        // list that come from somewhere else, do not attempt to position them.
    3178         if (floatingObject->renderer()->containingBlock() != this) {
    3179             floatingObject = m_floatingObjects->next();
     3186        if (floatingObject->renderer()->containingBlock() != this)
    31803187            continue;
    3181         }
    31823188
    31833189        RenderBox* childBox = floatingObject->renderer();
     
    32613267        if (childBox->checkForRepaintDuringLayout())
    32623268            childBox->repaintDuringLayoutIfMoved(oldRect);
    3263 
    3264         floatingObject = m_floatingObjects->next();
    32653269    }
    32663270    return true;
     
    32733277        return didPosition;
    32743278   
     3279    ASSERT(m_floatingObjects->last() == newFloat);
     3280
    32753281    int floatLogicalTop = logicalTopForFloat(newFloat);
    32763282    int paginationStrut = newFloat->m_paginationStrut;
    3277     FloatingObject* f = m_floatingObjects->last();
    3278    
    3279     ASSERT(f == newFloat);
    3280 
     3283   
    32813284    if (floatLogicalTop - paginationStrut != logicalHeight())
    32823285        return didPosition;
    32833286
    3284     for (f = m_floatingObjects->prev(); f && f != lastFloatFromPreviousLine; f = m_floatingObjects->prev()) {
     3287    FloatingObjectSetIterator it = m_floatingObjects->end();
     3288    --it; // Last float is newFloat, skip that one.
     3289    FloatingObjectSetIterator begin = m_floatingObjects->begin();
     3290    while (it != begin) {
     3291        --it;
     3292        FloatingObject* f = *it;
     3293        if (f == lastFloatFromPreviousLine)
     3294            break;
    32853295        if (logicalTopForFloat(f) == logicalHeight()) {
    32863296            ASSERT(!f->m_paginationStrut);
     
    33883398        if (heightRemaining)
    33893399            *heightRemaining = 1;
    3390         FloatingObject* r;
    3391         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3392         for ( ; (r = it.current()); ++it) {
     3400
     3401        FloatingObjectSetIterator end = m_floatingObjects->end();
     3402        for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     3403            FloatingObject* r = *it;
    33933404            if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
    33943405                && r->type() == FloatingObject::FloatLeft
     
    34183429        if (heightRemaining)
    34193430            *heightRemaining = 1;
    3420         FloatingObject* r;
    3421         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3422         for ( ; (r = it.current()); ++it) {
     3431        FloatingObjectSetIterator end = m_floatingObjects->end();
     3432        for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     3433            FloatingObject* r = *it;
    34233434            if (r->isPlaced() && logicalTopForFloat(r) <= logicalTop && logicalBottomForFloat(r) > logicalTop
    34243435                && r->type() == FloatingObject::FloatRight
     
    34533464
    34543465    int bottom = INT_MAX;
    3455     FloatingObject* r;
    3456     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3457     for ( ; (r = it.current()); ++it) {
     3466    FloatingObjectSetIterator end = m_floatingObjects->end();
     3467    for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     3468        FloatingObject* r = *it;
    34583469        int floatBottom = logicalBottomForFloat(r);
    34593470        if (floatBottom > logicalHeight)
     
    34693480        return 0;
    34703481    int lowestFloatBottom = 0;
    3471     FloatingObject* r;
    3472     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3473     for ( ; (r = it.current()); ++it) {
     3482    FloatingObjectSetIterator end = m_floatingObjects->end();
     3483    for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     3484        FloatingObject* r = *it;
    34743485        if (r->isPlaced() && r->type() & floatType)
    34753486            lowestFloatBottom = max(lowestFloatBottom, logicalBottomForFloat(r));
     
    35103521    if (m_floatingObjects) {
    35113522        if (childrenInline()) {
    3512             m_floatingObjects->first();
    3513             while (FloatingObject* f = m_floatingObjects->take())
     3523            FloatingObjectSet::iterator end = m_floatingObjects->end();
     3524            for (FloatingObjectSet::iterator it = m_floatingObjects->begin(); it != end; ++it) {
     3525                FloatingObject* f = *it;
    35143526                floatMap.add(f->m_renderer, f);
     3527            }
    35153528        } else
    3516             m_floatingObjects->clear();
     3529            deleteAllValues(*m_floatingObjects);
     3530        m_floatingObjects->clear();
    35173531    }
    35183532
     
    35603574        int changeLogicalBottom = numeric_limits<int>::min();
    35613575        if (m_floatingObjects) {
    3562             for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
     3576            FloatingObjectSetIterator end = m_floatingObjects->end();
     3577            for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     3578                FloatingObject* f = *it;
    35633579                FloatingObject* oldFloatingObject = floatMap.get(f->m_renderer);
    35643580                int logicalBottom = logicalBottomForFloat(f);
     
    36063622    // Floats that will remain the child's responsibility to paint should factor into its
    36073623    // overflow.
    3608     DeprecatedPtrListIterator<FloatingObject> it(*child->m_floatingObjects);
    3609     for (FloatingObject* r; (r = it.current()); ++it) {
     3624    FloatingObjectSetIterator childEnd = child->m_floatingObjects->end();
     3625    for (FloatingObjectSetIterator childIt = child->m_floatingObjects->begin(); childIt != childEnd; ++childIt) {
     3626        FloatingObject* r = *childIt;
    36103627        int logicalBottom = child->logicalTop() + logicalBottomForFloat(r);
    36113628        lowestFloatLogicalBottom = max(lowestFloatLogicalBottom, logicalBottom);
     
    36313648
    36323649                // We create the floating object list lazily.
    3633                 if (!m_floatingObjects) {
    3634                     m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
    3635                     m_floatingObjects->setAutoDelete(true);
    3636                 }
    3637                 m_floatingObjects->append(floatingObj);
     3650                if (!m_floatingObjects)
     3651                    m_floatingObjects = new FloatingObjectSet;
     3652
     3653                m_floatingObjects->add(floatingObj);
    36383654            }
    36393655        } else {
     
    36643680
    36653681    logicalLeftOffset += (style()->isHorizontalWritingMode() ? marginLeft() : marginTop());
    3666                
    3667     DeprecatedPtrListIterator<FloatingObject> it(*prev->m_floatingObjects);
    3668     for (FloatingObject *r; (r = it.current()); ++it) {
     3682
     3683    FloatingObjectSetIterator prevEnd = prev->m_floatingObjects->end();
     3684    for (FloatingObjectSetIterator prevIt = prev->m_floatingObjects->begin(); prevIt != prevEnd; ++prevIt) {
     3685        FloatingObject* r = *prevIt;
    36693686        if (logicalBottomForFloat(r) > logicalTopOffset) {
    3670             // The object may already be in our list. Check for it up front to avoid
    3671             // creating duplicate entries.
    3672             FloatingObject* f = 0;
    3673             if (m_floatingObjects) {
    3674                 DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3675                 while ((f = it.current())) {
    3676                     if (f->m_renderer == r->m_renderer)
    3677                         break;
    3678                     ++it;
    3679                 }
    3680             }
    3681             if (!f) {
     3687            if (!m_floatingObjects || !m_floatingObjects->contains(r)) {
    36823688                int leftOffset = style()->isHorizontalWritingMode() ? logicalLeftOffset : logicalTopOffset;
    36833689                int topOffset = style()->isHorizontalWritingMode() ? logicalTopOffset : logicalLeftOffset;
     
    37013707               
    37023708                // We create the floating object list lazily.
    3703                 if (!m_floatingObjects) {
    3704                     m_floatingObjects = new DeprecatedPtrList<FloatingObject>;
    3705                     m_floatingObjects->setAutoDelete(true);
    3706                 }
    3707                 m_floatingObjects->append(floatingObj);
     3709                if (!m_floatingObjects)
     3710                    m_floatingObjects = new FloatingObjectSet;
     3711                m_floatingObjects->add(floatingObj);
    37083712            }
    37093713        }
     
    37173721}
    37183722
    3719 bool RenderBlock::containsFloat(RenderObject* o)
    3720 {
    3721     if (m_floatingObjects) {
    3722         DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3723         while (it.current()) {
    3724             if (it.current()->m_renderer == o)
    3725                 return true;
    3726             ++it;
    3727         }
    3728     }
    3729     return false;
     3723bool RenderBlock::containsFloat(RenderBox* renderer)
     3724{
     3725    return m_floatingObjects && m_floatingObjects->contains<RenderBox*, FloatingObjectHashTranslator>(renderer);
    37303726}
    37313727
     
    38853881    }
    38863882
    3887     FloatingObject* floatingObject;
    3888     DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    3889     for (it.toLast(); (floatingObject = it.current()); --it) {
     3883    FloatingObjectSetIterator begin = m_floatingObjects->begin();
     3884    for (FloatingObjectSetIterator it = m_floatingObjects->end(); it != begin;) {
     3885        --it;
     3886        FloatingObject* floatingObject = *it;
    38903887        if (floatingObject->m_shouldPaint && !floatingObject->m_renderer->hasSelfPaintingLayer()) {
    38913888            int xOffset = xPositionForFloatIncludingMargin(floatingObject) - floatingObject->m_renderer->x();
     
    55125509       
    55135510        if (m_floatingObjects) {
    5514             FloatingObject* r;
    5515             DeprecatedPtrListIterator<FloatingObject> it(*m_floatingObjects);
    5516             for (; (r = it.current()); ++it) {
     5511            FloatingObjectSetIterator end = m_floatingObjects->end();
     5512            for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     5513                FloatingObject* r = *it;
    55175514                // Only examine the object if our m_shouldPaint flag is set.
    55185515                if (r->m_shouldPaint) {
  • trunk/Source/WebCore/rendering/RenderBlock.h

    r79734 r79817  
    2424#define RenderBlock_h
    2525
    26 #include "DeprecatedPtrList.h"
    2726#include "GapRects.h"
    2827#include "RenderBox.h"
     
    9796   
    9897    bool containsFloats() { return m_floatingObjects && !m_floatingObjects->isEmpty(); }
    99     bool containsFloat(RenderObject*);
     98    bool containsFloat(RenderBox*);
    10099
    101100    int availableLogicalWidthForLine(int position, bool firstLine) const;
     
    703702    void adjustLinePositionForPagination(RootInlineBox*, int& deltaOffset); // Computes a deltaOffset value that put a line at the top of the next page if it doesn't fit on the current page.
    704703
     704    struct FloatingObjectHashFunctions {
     705        static unsigned hash(FloatingObject* key) { return DefaultHash<RenderBox*>::Hash::hash(key->m_renderer); }
     706        static bool equal(FloatingObject* a, FloatingObject* b) { return a->m_renderer == b->m_renderer; }
     707        static const bool safeToCompareToEmptyOrDeleted = true;
     708    };
     709    struct FloatingObjectHashTranslator {
     710        static unsigned hash(RenderBox* key) { return DefaultHash<RenderBox*>::Hash::hash(key); }
     711        static bool equal(FloatingObject* a, RenderBox* b) { return a->m_renderer == b; }
     712    };
     713    typedef ListHashSet<FloatingObject*, 4, FloatingObjectHashFunctions> FloatingObjectSet;
     714    typedef FloatingObjectSet::const_iterator FloatingObjectSetIterator;
     715    FloatingObjectSet* m_floatingObjects;
     716   
    705717    typedef PositionedObjectsListHashSet::const_iterator Iterator;
    706     DeprecatedPtrList<FloatingObject>* m_floatingObjects;
    707    
    708718    PositionedObjectsListHashSet* m_positionedObjects;
    709719
  • trunk/Source/WebCore/rendering/RenderBlockLineLayout.cpp

    r79694 r79817  
    619619        }
    620620
    621         FloatingObject* lastFloat = m_floatingObjects ? m_floatingObjects->last() : 0;
     621        FloatingObject* lastFloat = (m_floatingObjects && !m_floatingObjects->isEmpty()) ? m_floatingObjects->last() : 0;
    622622
    623623        LineMidpointState& lineMidpointState = resolver.midpointState();
     
    689689           
    690690            InlineIterator oldEnd = end;
    691             FloatingObject* lastFloatFromPreviousLine = m_floatingObjects ? m_floatingObjects->last() : 0;
     691            FloatingObject* lastFloatFromPreviousLine = (m_floatingObjects && !m_floatingObjects->isEmpty()) ? m_floatingObjects->last() : 0;
    692692            end = findNextLineBreak(resolver, firstLine, isLineEmpty, lineBreakIteratorInfo, previousLineBrokeCleanly, hyphenated, &clear, lastFloatFromPreviousLine);
    693693            if (resolver.position().atEnd()) {
     
    840840
    841841            if (m_floatingObjects && lastRootBox()) {
     842                FloatingObjectSetIterator it = m_floatingObjects->begin();
     843                FloatingObjectSetIterator end = m_floatingObjects->end();
    842844                if (lastFloat) {
    843                     for (FloatingObject* f = m_floatingObjects->last(); f != lastFloat; f = m_floatingObjects->prev()) {
    844                     }
    845                     m_floatingObjects->next();
    846                 } else
    847                     m_floatingObjects->first();
    848                 for (FloatingObject* f = m_floatingObjects->current(); f; f = m_floatingObjects->next()) {
     845                    FloatingObjectSetIterator lastFloatIterator = m_floatingObjects->find(lastFloat);
     846                    ASSERT(lastFloatIterator != end);
     847                    ++lastFloatIterator;
     848                    it = lastFloatIterator;
     849                }
     850                for (; it != end; ++it) {
     851                    FloatingObject* f = *it;
    849852                    lastRootBox()->floats().append(f->m_renderer);
    850853                    ASSERT(f->m_renderer == floats[floatIndex].object);
     
    854857                    floatIndex++;
    855858                }
    856                 lastFloat = m_floatingObjects->last();
     859                lastFloat = !m_floatingObjects->isEmpty() ? m_floatingObjects->last() : 0;
    857860            }
    858861
     
    917920                trailingFloatsLineBox->setBlockLogicalHeight(logicalHeight());
    918921            }
     922
     923            FloatingObjectSetIterator it = m_floatingObjects->begin();
     924            FloatingObjectSetIterator end = m_floatingObjects->end();
    919925            if (lastFloat) {
    920                 for (FloatingObject* f = m_floatingObjects->last(); f != lastFloat; f = m_floatingObjects->prev()) {
    921                 }
    922                 m_floatingObjects->next();
    923             } else
    924                 m_floatingObjects->first();
    925             for (FloatingObject* f = m_floatingObjects->current(); f; f = m_floatingObjects->next())
    926                 lastRootBox()->floats().append(f->m_renderer);
    927             lastFloat = m_floatingObjects->last();
     926                FloatingObjectSetIterator lastFloatIterator = m_floatingObjects->find(lastFloat);
     927                ASSERT(lastFloatIterator != end);
     928                ++lastFloatIterator;
     929                it = lastFloatIterator;
     930            }
     931            for (; it != end; ++it)
     932                lastRootBox()->floats().append((*it)->m_renderer);
     933            lastFloat = !m_floatingObjects->isEmpty() ? m_floatingObjects->last() : 0;
    928934        }
    929935        size_t floatCount = floats.size();
     
    11621168        int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
    11631169
    1164         for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
     1170        FloatingObjectSetIterator end = m_floatingObjects->end();
     1171        for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     1172            FloatingObject* f = *it;
    11651173            if (logicalBottomForFloat(f) >= logicalTop && logicalBottomForFloat(f) < logicalBottom)
    11661174                return false;
     
    11961204                int logicalBottom = lastLine->blockLogicalHeight() + abs(delta);
    11971205
    1198                 for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
     1206                FloatingObjectSetIterator end = m_floatingObjects->end();
     1207                for (FloatingObjectSetIterator it = m_floatingObjects->begin(); it != end; ++it) {
     1208                    FloatingObject* f = *it;
    11991209                    if (logicalBottomForFloat(f) >= logicalTop && logicalBottomForFloat(f) < logicalBottom)
    12001210                        return false;
Note: See TracChangeset for help on using the changeset viewer.