Changeset 166460 in webkit


Ignore:
Timestamp:
Mar 30, 2014 1:32:13 AM (10 years ago)
Author:
Antti Koivisto
Message:

LiveNodeLists should use ElementDescendantIterator
​https://bugs.webkit.org/show_bug.cgi?id=130931

Reviewed by Andreas Kling.

Make LiveNodeList traversal use the common DOM tree iterator.

  • dom/ChildNodeList.cpp:

(WebCore::ChildNodeList::ChildNodeList):
(WebCore::ChildNodeList::collectionBegin):
(WebCore::ChildNodeList::collectionTraverseForward):
(WebCore::ChildNodeList::collectionTraverseBackward):
(WebCore::ChildNodeList::invalidateCache):
(WebCore::ChildNodeList::collectionFirst): Deleted.

Iterator for ChildNodeList is still just Node*.

  • dom/ChildNodeList.h:
  • dom/CollectionIndexCache.h:

(WebCore::CollectionIndexCache::hasValidCache):
(WebCore::Iterator>::CollectionIndexCache):
(WebCore::Iterator>::nodeCount):
(WebCore::Iterator>::computeNodeCountUpdatingListCache):
(WebCore::Iterator>::traverseBackwardTo):
(WebCore::Iterator>::traverseForwardTo):
(WebCore::Iterator>::nodeAt):
(WebCore::Iterator>::invalidate):

Make CollectionIndexCache iterator based instead of using NodeType*. The iterator type may
still be a Node* though.

(WebCore::NodeType>::CollectionIndexCache): Deleted.
(WebCore::NodeType>::nodeCount): Deleted.
(WebCore::NodeType>::computeNodeCountUpdatingListCache): Deleted.
(WebCore::NodeType>::nodeBeforeCached): Deleted.
(WebCore::NodeType>::nodeAfterCached): Deleted.
(WebCore::NodeType>::nodeAt): Deleted.
(WebCore::NodeType>::invalidate): Deleted.

  • dom/ElementDescendantIterator.h:

(WebCore::ElementDescendantIterator::operator--):

Add backward iteration support.

(WebCore::ElementDescendantIteratorAdapter::last):
(WebCore::ElementDescendantConstIteratorAdapter::last):

Add a way to get the last item.
Provide std::iterator_traits so we can extract the type.

  • dom/LiveNodeList.h:

(WebCore::CachedLiveNodeList::collectionEnd):
(WebCore::CachedLiveNodeList<NodeListType>::CachedLiveNodeList):
(WebCore::CachedLiveNodeList<NodeListType>::~CachedLiveNodeList):
(WebCore::CachedLiveNodeList<NodeListType>::collectionBegin):
(WebCore::CachedLiveNodeList<NodeListType>::collectionLast):
(WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseForward):
(WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseBackward):
(WebCore::CachedLiveNodeList<NodeListType>::invalidateCache):
(WebCore::CachedLiveNodeList<NodeListType>::collectionFirst): Deleted.

Make LiveNodeList traversal use ElementDescendantIterator.

(WebCore::nextMatchingElement): Deleted.
(WebCore::previousMatchingElement): Deleted.

  • html/HTMLCollection.cpp:

(WebCore::HTMLCollection::HTMLCollection):
(WebCore::HTMLCollection::~HTMLCollection):
(WebCore::HTMLCollection::collectionBegin):
(WebCore::HTMLCollection::collectionTraverseForward):
(WebCore::HTMLCollection::collectionTraverseBackward):
(WebCore::HTMLCollection::invalidateCache):
(WebCore::HTMLCollection::collectionFirst): Deleted.

  • html/HTMLCollection.h:

(WebCore::HTMLCollection::collectionEnd):

HTMLCollection still uses Element* as iterator for now.

Location:
trunk/Source/WebCore
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r166459 r166460  
     12014-03-29  Antti Koivisto  <antti@apple.com>
     2
     3        LiveNodeLists should use ElementDescendantIterator
     4        https://bugs.webkit.org/show_bug.cgi?id=130931
     5
     6        Reviewed by Andreas Kling.
     7       
     8        Make LiveNodeList traversal use the common DOM tree iterator.
     9
     10        * dom/ChildNodeList.cpp:
     11        (WebCore::ChildNodeList::ChildNodeList):
     12        (WebCore::ChildNodeList::collectionBegin):
     13        (WebCore::ChildNodeList::collectionTraverseForward):
     14        (WebCore::ChildNodeList::collectionTraverseBackward):
     15        (WebCore::ChildNodeList::invalidateCache):
     16        (WebCore::ChildNodeList::collectionFirst): Deleted.
     17       
     18            Iterator for ChildNodeList is still just Node*.
     19
     20        * dom/ChildNodeList.h:
     21        * dom/CollectionIndexCache.h:
     22        (WebCore::CollectionIndexCache::hasValidCache):
     23        (WebCore::Iterator>::CollectionIndexCache):
     24        (WebCore::Iterator>::nodeCount):
     25        (WebCore::Iterator>::computeNodeCountUpdatingListCache):
     26        (WebCore::Iterator>::traverseBackwardTo):
     27        (WebCore::Iterator>::traverseForwardTo):
     28        (WebCore::Iterator>::nodeAt):
     29        (WebCore::Iterator>::invalidate):
     30       
     31            Make CollectionIndexCache iterator based instead of using NodeType*. The iterator type may
     32            still be a Node* though.
     33
     34        (WebCore::NodeType>::CollectionIndexCache): Deleted.
     35        (WebCore::NodeType>::nodeCount): Deleted.
     36        (WebCore::NodeType>::computeNodeCountUpdatingListCache): Deleted.
     37        (WebCore::NodeType>::nodeBeforeCached): Deleted.
     38        (WebCore::NodeType>::nodeAfterCached): Deleted.
     39        (WebCore::NodeType>::nodeAt): Deleted.
     40        (WebCore::NodeType>::invalidate): Deleted.
     41        * dom/ElementDescendantIterator.h:
     42        (WebCore::ElementDescendantIterator::operator--):
     43       
     44            Add backward iteration support.
     45
     46        (WebCore::ElementDescendantIteratorAdapter::last):
     47        (WebCore::ElementDescendantConstIteratorAdapter::last):
     48       
     49            Add a way to get the last item.
     50            Provide std::iterator_traits so we can extract the type.
     51
     52        * dom/LiveNodeList.h:
     53        (WebCore::CachedLiveNodeList::collectionEnd):
     54        (WebCore::CachedLiveNodeList<NodeListType>::CachedLiveNodeList):
     55        (WebCore::CachedLiveNodeList<NodeListType>::~CachedLiveNodeList):
     56        (WebCore::CachedLiveNodeList<NodeListType>::collectionBegin):
     57        (WebCore::CachedLiveNodeList<NodeListType>::collectionLast):
     58        (WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseForward):
     59        (WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseBackward):
     60        (WebCore::CachedLiveNodeList<NodeListType>::invalidateCache):
     61        (WebCore::CachedLiveNodeList<NodeListType>::collectionFirst): Deleted.
     62       
     63            Make LiveNodeList traversal use ElementDescendantIterator.
     64
     65        (WebCore::nextMatchingElement): Deleted.
     66        (WebCore::previousMatchingElement): Deleted.
     67        * html/HTMLCollection.cpp:
     68        (WebCore::HTMLCollection::HTMLCollection):
     69        (WebCore::HTMLCollection::~HTMLCollection):
     70        (WebCore::HTMLCollection::collectionBegin):
     71        (WebCore::HTMLCollection::collectionTraverseForward):
     72        (WebCore::HTMLCollection::collectionTraverseBackward):
     73        (WebCore::HTMLCollection::invalidateCache):
     74        (WebCore::HTMLCollection::collectionFirst): Deleted.
     75        * html/HTMLCollection.h:
     76        (WebCore::HTMLCollection::collectionEnd):
     77       
     78            HTMLCollection still uses Element* as iterator for now.
     79
    1802014-03-29  Commit Queue  <commit-queue@webkit.org>
    281

  • trunk/Source/WebCore/dom/ChildNodeList.cpp

    r161196 r166460  
    3636ChildNodeList::ChildNodeList(ContainerNode& parent)
    3737    : m_parent(parent)
     38    , m_indexCache(*this)
    3839{
    3940}
    … …  
    5455}
    5556
    56 Node* ChildNodeList::collectionFirst() const
     57Node* ChildNodeList::collectionBegin() const
    5758{
    5859    return m_parent->firstChild();
    … …  
    6465}
    6566
    66 Node* ChildNodeList::collectionTraverseForward(Node& current, unsigned count, unsigned& traversedCount) const
     67void ChildNodeList::collectionTraverseForward(Node*& current, unsigned count, unsigned& traversedCount) const
    6768{
    6869    ASSERT(count);
    69     Node* child = &current;
    7070    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
    71         child = child->nextSibling();
    72         if (!child)
    73             return nullptr;
     71        current = current->nextSibling();
     72        if (!current)
     73            return;
    7474    }
    75     return child;
    7675}
    7776
    78 Node* ChildNodeList::collectionTraverseBackward(Node& current, unsigned count) const
     77void ChildNodeList::collectionTraverseBackward(Node*& current, unsigned count) const
    7978{
    8079    ASSERT(count);
    81     Node* child = &current;
    82     for (; count && child ; --count)
    83         child = child->previousSibling();
    84     return child;
     80    for (; count && current ; --count)
     81        current = current->previousSibling();
    8582}
    8683
    … …  
    104101void ChildNodeList::invalidateCache()
    105102{
    106     m_indexCache.invalidate();
     103    m_indexCache.invalidate(*this);
    107104}
    108105

  • trunk/Source/WebCore/dom/ChildNodeList.h

    r165103 r166460  
    7171
    7272    // For CollectionIndexCache
    73     Node* collectionFirst() const;
     73    Node* collectionBegin() const;
    7474    Node* collectionLast() const;
    75     Node* collectionTraverseForward(Node&, unsigned count, unsigned& traversedCount) const;
    76     Node* collectionTraverseBackward(Node&, unsigned count) const;
     75    Node* collectionEnd() const { return nullptr; }
     76    void collectionTraverseForward(Node*&, unsigned count, unsigned& traversedCount) const;
     77    void collectionTraverseBackward(Node*&, unsigned count) const;
    7778    bool collectionCanTraverseBackward() const { return true; }
    7879    void willValidateIndexCache() const { }
    … …  
    8990
    9091    Ref<ContainerNode> m_parent;
    91     mutable CollectionIndexCache<ChildNodeList, Node> m_indexCache;
     92    mutable CollectionIndexCache<ChildNodeList, Node*> m_indexCache;
    9293};
    9394

  • trunk/Source/WebCore/dom/CollectionIndexCache.h

    r165103 r166460  
    3333void reportExtraMemoryCostForCollectionIndexCache(size_t);
    3434
    35 template <class Collection, class NodeType>
     35template <class Collection, class Iterator>
    3636class CollectionIndexCache {
    3737public:
    38     CollectionIndexCache();
     38    explicit CollectionIndexCache(const Collection&);
     39
     40    typedef typename std::iterator_traits<Iterator>::value_type NodeType;
    3941
    4042    unsigned nodeCount(const Collection&);
    4143    NodeType* nodeAt(const Collection&, unsigned index);
    4244
    43     bool hasValidCache() const { return m_currentNode || m_nodeCountValid || m_listValid; }
    44     void invalidate();
     45    bool hasValidCache(const Collection& collection) const { return m_current != collection.collectionEnd() || m_nodeCountValid || m_listValid; }
     46    void invalidate(const Collection&);
    4547    size_t memoryCost() { return m_cachedList.capacity() * sizeof(NodeType*); }
    4648
    4749private:
    48 
    4950    unsigned computeNodeCountUpdatingListCache(const Collection&);
    50     NodeType* nodeBeforeCached(const Collection&, unsigned);
    51     NodeType* nodeAfterCached(const Collection&, unsigned);
    52 
    53     NodeType* m_currentNode;
     51    NodeType* traverseBackwardTo(const Collection&, unsigned);
     52    NodeType* traverseForwardTo(const Collection&, unsigned);
     53
     54    Iterator m_current;
    5455    unsigned m_currentIndex;
    5556    unsigned m_nodeCount;
    … …  
    5960};
    6061
    61 template <class Collection, class NodeType>
    62 inline CollectionIndexCache<Collection, NodeType>::CollectionIndexCache()
    63     : m_currentNode(nullptr)
     62template <class Collection, class Iterator>
     63inline CollectionIndexCache<Collection, Iterator>::CollectionIndexCache(const Collection& collection)
     64    : m_current(collection.collectionEnd())
    6465    , m_currentIndex(0)
    6566    , m_nodeCount(0)
    … …  
    6970}
    7071
    71 template <class Collection, class NodeType>
    72 inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Collection& collection)
     72template <class Collection, class Iterator>
     73inline unsigned CollectionIndexCache<Collection, Iterator>::nodeCount(const Collection& collection)
    7374{
    7475    if (!m_nodeCountValid) {
    75         if (!hasValidCache())
     76        if (!hasValidCache(collection))
    7677            collection.willValidateIndexCache();
    7778        m_nodeCount = computeNodeCountUpdatingListCache(collection);
    … …  
    8283}
    8384
    84 template <class Collection, class NodeType>
    85 unsigned CollectionIndexCache<Collection, NodeType>::computeNodeCountUpdatingListCache(const Collection& collection)
    86 {
    87     NodeType* first = collection.collectionFirst();
    88     if (!first)
     85template <class Collection, class Iterator>
     86unsigned CollectionIndexCache<Collection, Iterator>::computeNodeCountUpdatingListCache(const Collection& collection)
     87{
     88    auto current = collection.collectionBegin();
     89    auto end = collection.collectionEnd();
     90    if (current == end)
    8991        return 0;
    9092
    9193    unsigned oldCapacity = m_cachedList.capacity();
    92     NodeType* currentNode = first;
    93     while (currentNode) {
    94         m_cachedList.append(currentNode);
     94    while (current != end) {
     95        m_cachedList.append(&*current);
    9596        unsigned traversed;
    96         currentNode = collection.collectionTraverseForward(*currentNode, 1, traversed);
    97         ASSERT(traversed == (currentNode ? 1 : 0));
     97        collection.collectionTraverseForward(current, 1, traversed);
     98        ASSERT(traversed == (current != end ? 1 : 0));
    9899    }
    99100    m_listValid = true;
    … …  
    105106}
    106107
    107 template <class Collection, class NodeType>
    108 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCached(const Collection& collection, unsigned index)
    109 {
    110     ASSERT(m_currentNode);
     108template <class Collection, class Iterator>
     109inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseBackwardTo(const Collection& collection, unsigned index)
     110{
     111    ASSERT(m_current != collection.collectionEnd());
    111112    ASSERT(index < m_currentIndex);
    112113
    113114    bool firstIsCloser = index < m_currentIndex - index;
    114115    if (firstIsCloser || !collection.collectionCanTraverseBackward()) {
    115         m_currentNode = collection.collectionFirst();
     116        m_current = collection.collectionBegin();
    116117        m_currentIndex = 0;
    117118        if (index)
    118             m_currentNode = collection.collectionTraverseForward(*m_currentNode, index, m_currentIndex);
    119         ASSERT(m_currentNode);
    120         return m_currentNode;
    121     }
    122 
    123     m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_currentIndex - index);
     119            collection.collectionTraverseForward(m_current, index, m_currentIndex);
     120        ASSERT(m_current != collection.collectionEnd());
     121        return &*m_current;
     122    }
     123
     124    collection.collectionTraverseBackward(m_current, m_currentIndex - index);
    124125    m_currentIndex = index;
    125126
    126     ASSERT(m_currentNode);
    127     return m_currentNode;
    128 }
    129 
    130 template <class Collection, class NodeType>
    131 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCached(const Collection& collection, unsigned index)
    132 {
    133     ASSERT(m_currentNode);
     127    ASSERT(m_current != collection.collectionEnd());
     128    return &*m_current;
     129}
     130
     131template <class Collection, class Iterator>
     132inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseForwardTo(const Collection& collection, unsigned index)
     133{
     134    ASSERT(m_current != collection.collectionEnd());
    134135    ASSERT(index > m_currentIndex);
    135136    ASSERT(!m_nodeCountValid || index < m_nodeCount);
    … …  
    137138    bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index - m_currentIndex;
    138139    if (lastIsCloser && collection.collectionCanTraverseBackward()) {
    139         ASSERT(hasValidCache());
    140         m_currentNode = collection.collectionLast();
     140        ASSERT(hasValidCache(collection));
     141        m_current = collection.collectionLast();
    141142        if (index < m_nodeCount - 1)
    142             m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_nodeCount - index - 1);
     143            collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1);
    143144        m_currentIndex = index;
    144         ASSERT(m_currentNode);
    145         return m_currentNode;
    146     }
    147 
    148     if (!hasValidCache())
     145        ASSERT(m_current != collection.collectionEnd());
     146        return &*m_current;
     147    }
     148
     149    if (!hasValidCache(collection))
    149150        collection.willValidateIndexCache();
    150151
    151152    unsigned traversedCount;
    152     m_currentNode = collection.collectionTraverseForward(*m_currentNode, index - m_currentIndex, traversedCount);
     153    collection.collectionTraverseForward(m_current, index - m_currentIndex, traversedCount);
    153154    m_currentIndex = m_currentIndex + traversedCount;
    154155
    155     ASSERT(m_currentNode ||  m_currentIndex < index);
    156 
    157     if (!m_currentNode && !m_nodeCountValid) {
     156    if (m_current == collection.collectionEnd()) {
     157        ASSERT(m_currentIndex < index);
    158158        // Failed to find the index but at least we now know the size.
    159159        m_nodeCount = m_currentIndex + 1;
    160160        m_nodeCountValid = true;
    161     }
    162     ASSERT(hasValidCache());
    163     return m_currentNode;
    164 }
    165 
    166 template <class Collection, class NodeType>
    167 inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collection& collection, unsigned index)
     161        return nullptr;
     162    }
     163    ASSERT(hasValidCache(collection));
     164    return &*m_current;
     165}
     166
     167template <class Collection, class Iterator>
     168inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::nodeAt(const Collection& collection, unsigned index)
    168169{
    169170    if (m_nodeCountValid && index >= m_nodeCount)
    … …  
    173174        return m_cachedList[index];
    174175
    175     if (m_currentNode) {
     176    auto end = collection.collectionEnd();
     177    if (m_current != end) {
    176178        if (index > m_currentIndex)
    177             return nodeAfterCached(collection, index);
     179            return traverseForwardTo(collection, index);
    178180        if (index < m_currentIndex)
    179             return nodeBeforeCached(collection, index);
    180         return m_currentNode;
     181            return traverseBackwardTo(collection, index);
     182        return &*m_current;
    181183    }
    182184
    183185    bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index;
    184186    if (lastIsCloser && collection.collectionCanTraverseBackward()) {
    185         ASSERT(hasValidCache());
    186         m_currentNode = collection.collectionLast();
     187        ASSERT(hasValidCache(collection));
     188        m_current = collection.collectionLast();
    187189        if (index < m_nodeCount - 1)
    188             m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_nodeCount - index - 1);
     190            collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1);
    189191        m_currentIndex = index;
    190         ASSERT(m_currentNode);
    191         return m_currentNode;
    192     }
    193 
    194     if (!hasValidCache())
     192        ASSERT(m_current != end);
     193        return &*m_current;
     194    }
     195
     196    if (!hasValidCache(collection))
    195197        collection.willValidateIndexCache();
    196198
    197     m_currentNode = collection.collectionFirst();
     199    m_current = collection.collectionBegin();
    198200    m_currentIndex = 0;
    199     if (index && m_currentNode) {
    200         m_currentNode = collection.collectionTraverseForward(*m_currentNode, index, m_currentIndex);
    201         ASSERT(m_currentNode || m_currentIndex < index);
    202     }
    203     if (!m_currentNode && !m_nodeCountValid) {
     201    if (index && m_current != end) {
     202        collection.collectionTraverseForward(m_current, index, m_currentIndex);
     203        ASSERT(m_current != end || m_currentIndex < index);
     204    }
     205    if (m_current == end) {
    204206        // Failed to find the index but at least we now know the size.
    205207        m_nodeCount = m_currentIndex + 1;
    206208        m_nodeCountValid = true;
    207     }
    208     ASSERT(hasValidCache());
    209     return m_currentNode;
    210 }
    211 
    212 template <class Collection, class NodeType>
    213 void CollectionIndexCache<Collection, NodeType>::invalidate()
    214 {
    215     m_currentNode = nullptr;
     209        return nullptr;
     210    }
     211    ASSERT(hasValidCache(collection));
     212    return &*m_current;
     213}
     214
     215template <class Collection, class Iterator>
     216void CollectionIndexCache<Collection, Iterator>::invalidate(const Collection& collection)
     217{
     218    m_current = collection.collectionEnd();
    216219    m_nodeCountValid = false;
    217220    m_listValid = false;

  • trunk/Source/WebCore/dom/ElementDescendantIterator.h

    r165822 r166460  
    4040
    4141    ElementDescendantIterator& operator++();
     42    ElementDescendantIterator& operator--();
    4243
    4344    Element& operator*();
    … …  
    8384    ElementDescendantIterator begin();
    8485    ElementDescendantIterator end();
     86    ElementDescendantIterator last();
    8587
    8688private:
    … …  
    9395    ElementDescendantConstIterator begin() const;
    9496    ElementDescendantConstIterator end() const;
     97    ElementDescendantConstIterator last() const;
    9598
    9699private:
    … …  
    145148}
    146149
     150ALWAYS_INLINE ElementDescendantIterator& ElementDescendantIterator::operator--()
     151{
     152    ASSERT(m_current);
     153    ASSERT(!m_assertions.domTreeHasMutated());
     154
     155    Element* previousSibling = ElementTraversal::previousSibling(m_current);
     156
     157    if (!previousSibling) {
     158        m_current = m_current->parentElement();
     159        // The stack optimizes for forward traversal only, this just maintains consistency.
     160        if (m_current->nextSibling() == m_ancestorSiblingStack.last())
     161            m_ancestorSiblingStack.removeLast();
     162        return *this;
     163    }
     164
     165    Element* deepestSibling = previousSibling;
     166    while (Element* lastChild = ElementTraversal::lastChild(deepestSibling))
     167        deepestSibling = lastChild;
     168    ASSERT(deepestSibling);
     169
     170    if (deepestSibling != previousSibling)
     171        m_ancestorSiblingStack.append(m_current);
     172
     173    m_current = deepestSibling;
     174
     175#if !ASSERT_DISABLED
     176    // Drop the assertion when the iterator reaches the end.
     177    if (!m_current)
     178        m_assertions.dropEventDispatchAssertion();
     179#endif
     180
     181    return *this;
     182}
     183
    147184inline Element& ElementDescendantIterator::operator*()
    148185{
    … …  
    256293}
    257294
     295inline ElementDescendantIterator ElementDescendantIteratorAdapter::last()
     296{
     297    return ElementDescendantIterator(ElementTraversal::lastWithin(&m_root));
     298}
     299
    258300// ElementDescendantConstIteratorAdapter
    259301
    … …  
    273315}
    274316
     317inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::last() const
     318{
     319    return ElementDescendantConstIterator(ElementTraversal::lastWithin(&m_root));
     320}
     321
    275322// Standalone functions
    276323
    … …  
    287334}
    288335
    289 #endif
     336namespace std {
     337template <> struct iterator_traits<WebCore::ElementDescendantIterator> {
     338    typedef WebCore::Element value_type;
     339};
     340template <> struct iterator_traits<WebCore::ElementDescendantConstIterator> {
     341    typedef const WebCore::Element value_type;
     342};
     343}
     344#endif

  • trunk/Source/WebCore/dom/LiveNodeList.h

    r166407 r166460  
    2828#include "CollectionType.h"
    2929#include "Document.h"
    30 #include "ElementTraversal.h"
     30#include "ElementDescendantIterator.h"
    3131#include "HTMLNames.h"
    3232#include "NodeList.h"
    … …  
    7070    ContainerNode& rootNode() const;
    7171
    72     Element* iterateForPreviousElement(Element* current) const;
    73 
    7472    Ref<ContainerNode> m_ownerNode;
    7573
    … …  
    8785
    8886    // For CollectionIndexCache
    89     Element* collectionFirst() const;
    90     Element* collectionLast() const;
    91     Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
    92     Element* collectionTraverseBackward(Element&, unsigned count) const;
     87    ElementDescendantIterator collectionBegin() const;
     88    ElementDescendantIterator collectionLast() const;
     89    ElementDescendantIterator collectionEnd() const { return ElementDescendantIterator(); }
     90    void collectionTraverseForward(ElementDescendantIterator&, unsigned count, unsigned& traversedCount) const;
     91    void collectionTraverseBackward(ElementDescendantIterator&, unsigned count) const;
    9392    bool collectionCanTraverseBackward() const { return true; }
    9493    void willValidateIndexCache() const;
    … …  
    103102    ContainerNode& rootNode() const;
    104103
    105     mutable CollectionIndexCache<NodeListType, Element> m_indexCache;
     104    mutable CollectionIndexCache<NodeListType, ElementDescendantIterator> m_indexCache;
    106105};
    107106
    … …  
    133132CachedLiveNodeList<NodeListType>::CachedLiveNodeList(ContainerNode& ownerNode, NodeListInvalidationType invalidationType)
    134133    : LiveNodeList(ownerNode, invalidationType)
     134    , m_indexCache(static_cast<NodeListType&>(*this))
    135135{
    136136}
    … …  
    139139CachedLiveNodeList<NodeListType>::~CachedLiveNodeList()
    140140{
    141     if (m_indexCache.hasValidCache())
     141    auto& nodeList = static_cast<const NodeListType&>(*this);
     142    if (m_indexCache.hasValidCache(nodeList))
    142143        document().unregisterNodeListForInvalidation(*this);
    143144}
    … …  
    153154
    154155template <class NodeListType>
    155 Element* CachedLiveNodeList<NodeListType>::collectionFirst() const
    156 {
    157     auto& root = rootNode();
    158     Element* element = ElementTraversal::firstWithin(&root);
    159     while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
    160         element = ElementTraversal::next(element, &root);
    161     return element;
    162 }
    163 
    164 template <class NodeListType>
    165 Element* CachedLiveNodeList<NodeListType>::collectionLast() const
    166 {
    167     auto& root = rootNode();
    168     Element* element = ElementTraversal::lastWithin(&root);
    169     while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
    170         element = ElementTraversal::previous(element, &root);
    171     return element;
    172 }
    173 
    174 template <class NodeListType>
    175 inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
    176 {
    177     do {
    178         current = ElementTraversal::next(current, &root);
    179     } while (current && !static_cast<const NodeListType*>(nodeList)->nodeMatches(current));
    180     return current;
    181 }
    182 
    183 template <class NodeListType>
    184 Element* CachedLiveNodeList<NodeListType>::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
    185 {
    186     auto& root = rootNode();
    187     Element* element = &current;
     156ElementDescendantIterator CachedLiveNodeList<NodeListType>::collectionBegin() const
     157{
     158    auto& nodeList = static_cast<const NodeListType&>(*this);
     159    auto descendants = elementDescendants(rootNode());
     160    auto end = descendants.end();
     161    for (auto it = descendants.begin(); it != end; ++it) {
     162        if (nodeList.nodeMatches(&*it))
     163            return it;
     164    }
     165    return end;
     166}
     167
     168template <class NodeListType>
     169ElementDescendantIterator CachedLiveNodeList<NodeListType>::collectionLast() const
     170{
     171    auto& nodeList = static_cast<const NodeListType&>(*this);
     172    auto descendants = elementDescendants(rootNode());
     173    auto end = descendants.end();
     174    for (auto it = descendants.last(); it != end; --it) {
     175        if (nodeList.nodeMatches(&*it))
     176            return it;
     177    }
     178    return end;
     179}
     180
     181template <class NodeListType>
     182void CachedLiveNodeList<NodeListType>::collectionTraverseForward(ElementDescendantIterator& current, unsigned count, unsigned& traversedCount) const
     183{
     184    auto& nodeList = static_cast<const NodeListType&>(*this);
     185    ASSERT(nodeList.nodeMatches(&*current));
     186    auto end = collectionEnd();
    188187    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
    189         element = nextMatchingElement(static_cast<const NodeListType*>(this), element, root);
    190         if (!element)
    191             return nullptr;
    192     }
    193     return element;
    194 }
    195 
    196 template <class NodeListType>
    197 inline Element* previousMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
    198 {
    199     do {
    200         current = ElementTraversal::previous(current, &root);
    201     } while (current && !nodeList->nodeMatches(current));
    202     return current;
    203 }
    204 
    205 template <class NodeListType>
    206 Element* CachedLiveNodeList<NodeListType>::collectionTraverseBackward(Element& current, unsigned count) const
    207 {
    208     auto& root = rootNode();
    209     Element* element = &current;
     188        do {
     189            ++current;
     190            if (current == end)
     191                return;
     192        } while (!nodeList.nodeMatches(&*current));
     193    }
     194}
     195
     196template <class NodeListType>
     197void CachedLiveNodeList<NodeListType>::collectionTraverseBackward(ElementDescendantIterator& current, unsigned count) const
     198{
     199    auto& nodeList = static_cast<const NodeListType&>(*this);
     200    ASSERT(nodeList.nodeMatches(&*current));
     201    auto end = collectionEnd();
    210202    for (; count; --count) {
    211         element = previousMatchingElement(static_cast<const NodeListType*>(this), element, root);
    212         if (!element)
    213             return nullptr;
    214     }
    215     return element;
    216 }
     203        do {
     204            --current;
     205            if (current == end)
     206                return;
     207        } while (!nodeList.nodeMatches(&*current));
     208    }
     209}
     210
    217211template <class NodeListType>
    218212void CachedLiveNodeList<NodeListType>::willValidateIndexCache() const
    … …  
    224218void CachedLiveNodeList<NodeListType>::invalidateCache(Document& document) const
    225219{
    226     if (!m_indexCache.hasValidCache())
     220    auto& nodeList = static_cast<const NodeListType&>(*this);
     221    if (!m_indexCache.hasValidCache(nodeList))
    227222        return;
    228     document.unregisterNodeListForInvalidation(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
    229     m_indexCache.invalidate();
     223    document.unregisterNodeListForInvalidation(const_cast<NodeListType&>(nodeList));
     224    m_indexCache.invalidate(nodeList);
    230225}
    231226

  • trunk/Source/WebCore/html/HTMLCollection.cpp

    r166407 r166460  
    134134HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType)
    135135    : m_ownerNode(ownerNode)
     136    , m_indexCache(*this)
    136137    , m_collectionType(type)
    137138    , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
    … …  
    152153HTMLCollection::~HTMLCollection()
    153154{
    154     if (m_indexCache.hasValidCache())
     155    if (m_indexCache.hasValidCache(*this))
    155156        document().unregisterCollection(*this);
    156157    if (hasNamedElementCache())
    … …  
    331332}
    332333
    333 Element* HTMLCollection::collectionFirst() const
     334Element* HTMLCollection::collectionBegin() const
    334335{
    335336    return firstElement(rootNode());
    … …  
    344345}
    345346
    346 Element* HTMLCollection::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
    347 {
    348     return traverseForward(current, count, traversedCount, rootNode());
    349 }
    350 
    351 Element* HTMLCollection::collectionTraverseBackward(Element& current, unsigned count) const
     347void HTMLCollection::collectionTraverseForward(Element*& current, unsigned count, unsigned& traversedCount) const
     348{
     349    current = traverseForward(*current, count, traversedCount, rootNode());
     350}
     351
     352void HTMLCollection::collectionTraverseBackward(Element*& current, unsigned count) const
    352353{
    353354    // FIXME: This should be optimized similarly to the forward case.
    354355    auto& root = rootNode();
    355     Element* element = &current;
    356356    if (m_shouldOnlyIncludeDirectChildren) {
    357         for (; count && element ; --count)
    358             element = iterateForPreviousElement(ElementTraversal::previousSibling(element));
    359         return element;
    360     }
    361     for (; count && element ; --count)
    362         element = iterateForPreviousElement(ElementTraversal::previous(element, &root));
    363     return element;
     357        for (; count && current ; --count)
     358            current = iterateForPreviousElement(ElementTraversal::previousSibling(current));
     359        return;
     360    }
     361    for (; count && current ; --count)
     362        current = iterateForPreviousElement(ElementTraversal::previous(current, &root));
    364363}
    365364
    366365void HTMLCollection::invalidateCache(Document& document) const
    367366{
    368     if (m_indexCache.hasValidCache()) {
     367    if (m_indexCache.hasValidCache(*this)) {
    369368        document.unregisterCollection(const_cast<HTMLCollection&>(*this));
    370         m_indexCache.invalidate();
     369        m_indexCache.invalidate(*this);
    371370    }
    372371    if (hasNamedElementCache())

  • trunk/Source/WebCore/html/HTMLCollection.h

    r166407 r166460  
    119119
    120120    // For CollectionIndexCache
    121     Element* collectionFirst() const;
     121    Element* collectionBegin() const;
    122122    Element* collectionLast() const;
    123     Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
    124     Element* collectionTraverseBackward(Element&, unsigned count) const;
     123    Element* collectionEnd() const { return nullptr; }
     124    void collectionTraverseForward(Element*&, unsigned count, unsigned& traversedCount) const;
     125    void collectionTraverseBackward(Element*&, unsigned count) const;
    125126    bool collectionCanTraverseBackward() const { return !m_usesCustomForwardOnlyTraversal; }
    126127    void willValidateIndexCache() const { document().registerCollection(const_cast<HTMLCollection&>(*this)); }
    … …  
    165166    Ref<ContainerNode> m_ownerNode;
    166167
    167     mutable CollectionIndexCache<HTMLCollection, Element> m_indexCache;
     168    mutable CollectionIndexCache<HTMLCollection, Element*> m_indexCache;
    168169    mutable std::unique_ptr<CollectionNamedElementCache> m_namedElementCache;
    169170
Note: See TracChangeset for help on using the changeset viewer.