Changeset 158698 in webkit


Ignore:
Timestamp:
Nov 5, 2013 3:45:43 PM (10 years ago)
Author:
Antti Koivisto
Message:

Factor index cache for NodeLists and HTMLCollections to a class
​https://bugs.webkit.org/show_bug.cgi?id=123823

Reviewed by Ryosuke Niwa.

Implement index cache class that can used by NodeLists and HTMLCollections that currently
each have implementations of their own.

This patch also implements ChildNodeList and LiveNodeList using CollectionIndexCache.
HTMLCollection is will be transitioned later.

  • GNUmakefile.list.am:
  • WebCore.vcxproj/WebCore.vcxproj:
  • WebCore.xcodeproj/project.pbxproj:
  • dom/ChildNodeList.cpp:

(WebCore::ChildNodeList::ChildNodeList):
(WebCore::ChildNodeList::length):
(WebCore::ChildNodeList::item):

The client calls to cache to for indexed and size access.

(WebCore::ChildNodeList::collectionFirst):
(WebCore::ChildNodeList::collectionLast):
(WebCore::ChildNodeList::collectionTraverseForward):
(WebCore::ChildNodeList::collectionTraverseBackward):

Cache calls back to these as needed to do the actual traversal.

(WebCore::ChildNodeList::invalidateCache):

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


Templated cache class itself.

(WebCore::::CollectionIndexCache):
(WebCore::::nodeCount):
(WebCore::::nodeBeforeCached):
(WebCore::::nodeAfterCached):
(WebCore::::nodeAt):
(WebCore::::invalidate):

  • dom/LiveNodeList.cpp:

(WebCore::firstMatchingElement):
(WebCore::nextMatchingElement):
(WebCore::traverseMatchingElementsForward):
(WebCore::LiveNodeList::collectionFirst):
(WebCore::LiveNodeList::collectionLast):
(WebCore::LiveNodeList::collectionTraverseForward):
(WebCore::LiveNodeList::collectionTraverseBackward):
(WebCore::LiveNodeList::length):
(WebCore::LiveNodeList::item):
(WebCore::LiveNodeList::invalidateCache):

  • dom/LiveNodeList.h:

(WebCore::LiveNodeList::LiveNodeList):

Location:
trunk/Source/WebCore
Files:
1 added
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r158697 r158698  
     12013-11-05  Antti Koivisto  <antti@apple.com>
     2
     3        Factor index cache for NodeLists and HTMLCollections to a class
     4        https://bugs.webkit.org/show_bug.cgi?id=123823
     5
     6        Reviewed by Ryosuke Niwa.
     7
     8        Implement index cache class that can used by NodeLists and HTMLCollections that currently
     9        each have implementations of their own.
     10       
     11        This patch also implements ChildNodeList and LiveNodeList using CollectionIndexCache.
     12        HTMLCollection is will be transitioned later.
     13
     14        * GNUmakefile.list.am:
     15        * WebCore.vcxproj/WebCore.vcxproj:
     16        * WebCore.xcodeproj/project.pbxproj:
     17        * dom/ChildNodeList.cpp:
     18        (WebCore::ChildNodeList::ChildNodeList):
     19        (WebCore::ChildNodeList::length):
     20        (WebCore::ChildNodeList::item):
     21       
     22            The client calls to cache to for indexed and size access.
     23
     24        (WebCore::ChildNodeList::collectionFirst):
     25        (WebCore::ChildNodeList::collectionLast):
     26        (WebCore::ChildNodeList::collectionTraverseForward):
     27        (WebCore::ChildNodeList::collectionTraverseBackward):
     28       
     29            Cache calls back to these as needed to do the actual traversal.
     30
     31        (WebCore::ChildNodeList::invalidateCache):
     32        * dom/ChildNodeList.h:
     33        * dom/CollectionIndexCache.h: Added.
     34       
     35            Templated cache class itself.
     36
     37        (WebCore::::CollectionIndexCache):
     38        (WebCore::::nodeCount):
     39        (WebCore::::nodeBeforeCached):
     40        (WebCore::::nodeAfterCached):
     41        (WebCore::::nodeAt):
     42        (WebCore::::invalidate):
     43        * dom/LiveNodeList.cpp:
     44        (WebCore::firstMatchingElement):
     45        (WebCore::nextMatchingElement):
     46        (WebCore::traverseMatchingElementsForward):
     47        (WebCore::LiveNodeList::collectionFirst):
     48        (WebCore::LiveNodeList::collectionLast):
     49        (WebCore::LiveNodeList::collectionTraverseForward):
     50        (WebCore::LiveNodeList::collectionTraverseBackward):
     51        (WebCore::LiveNodeList::length):
     52        (WebCore::LiveNodeList::item):
     53        (WebCore::LiveNodeList::invalidateCache):
     54        * dom/LiveNodeList.h:
     55        (WebCore::LiveNodeList::LiveNodeList):
     56
    1572013-11-05  Enrica Casucci  <enrica@apple.com>
    258

  • trunk/Source/WebCore/GNUmakefile.list.am

    r158656 r158698  
    27382738        Source/WebCore/dom/ClipboardEvent.h \
    27392739        Source/WebCore/dom/Clipboard.h \
     2740        Source/WebCore/dom/CollectionIndexCache.h \
    27402741        Source/WebCore/dom/Comment.cpp \
    27412742        Source/WebCore/dom/Comment.h \

  • trunk/Source/WebCore/WebCore.vcxproj/WebCore.vcxproj

    r158626 r158698  
    1 <?xml version="1.0" encoding="utf-8"?>
     1<?xml version="1.0" encoding="utf-8"?>
    22<Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
    33  <ItemGroup Label="ProjectConfigurations">
    … …  
    1984119841    <ClInclude Include="..\dom\ClipboardAccessPolicy.h" />
    1984219842    <ClInclude Include="..\dom\ClipboardEvent.h" />
     19843    <ClInclude Include="..\dom\CollectionIndexCache.h" />
    1984319844    <ClInclude Include="..\dom\Comment.h" />
    1984419845    <ClInclude Include="..\dom\CompositionEvent.h" />

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

    r158654 r158698  
    56905690                E1FF8F6D180DB5BE00132674 /* CryptoAlgorithmRegistry.h in Headers */ = {isa = PBXBuildFile; fileRef = E1FF8F6B180DB5BE00132674 /* CryptoAlgorithmRegistry.h */; };
    56915691                E401C27517CE53EC00C41A35 /* ElementIteratorAssertions.h in Headers */ = {isa = PBXBuildFile; fileRef = E401C27417CE53EC00C41A35 /* ElementIteratorAssertions.h */; };
     5692                E425A49A18292B840020CFCF /* CollectionIndexCache.h in Headers */ = {isa = PBXBuildFile; fileRef = E425A49918292B840020CFCF /* CollectionIndexCache.h */; };
    56925693                E4295FA412B0614E00D1ACE0 /* ResourceLoadPriority.h in Headers */ = {isa = PBXBuildFile; fileRef = E4295FA312B0614E00D1ACE0 /* ResourceLoadPriority.h */; settings = {ATTRIBUTES = (Private, ); }; };
    56935694                E43105B816750F0C00DB2FB8 /* NodeTraversal.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E43105B716750F0C00DB2FB8 /* NodeTraversal.cpp */; };
    … …  
    1275012751                E41EA038119836DB00710BC5 /* CSSPropertyNames.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CSSPropertyNames.cpp; sourceTree = "<group>"; };
    1275112752                E41EA0391198374900710BC5 /* CSSValueKeywords.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CSSValueKeywords.cpp; sourceTree = "<group>"; };
     12753                E425A49918292B840020CFCF /* CollectionIndexCache.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CollectionIndexCache.h; sourceTree = "<group>"; };
    1275212754                E4295FA312B0614E00D1ACE0 /* ResourceLoadPriority.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ResourceLoadPriority.h; sourceTree = "<group>"; };
    1275312755                E43105B716750F0C00DB2FB8 /* NodeTraversal.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NodeTraversal.cpp; sourceTree = "<group>"; };
    … …  
    2105821060                                85031B2A0A44EFC700F992E0 /* ClipboardEvent.h */,
    2105921061                                2D90660C0665D937006B6F1A /* ClipboardMac.mm */,
     21062                                E425A49918292B840020CFCF /* CollectionIndexCache.h */,
    2106021063                                6550B697099DF0270090D781 /* Comment.cpp */,
    2106121064                                6550B698099DF0270090D781 /* Comment.h */,
    … …  
    2330723310                                A80E7B0E0A19D606007FB8C5 /* JSHTMLStyleElement.h in Headers */,
    2330823311                                BCA169A30BFD55B40019CA76 /* JSHTMLTableCaptionElement.h in Headers */,
     23312                                E425A49A18292B840020CFCF /* CollectionIndexCache.h in Headers */,
    2330923313                                BC06EDE40BFD6D0D00856E9D /* JSHTMLTableCellElement.h in Headers */,
    2331023314                                BC06ED9E0BFD660600856E9D /* JSHTMLTableColElement.h in Headers */,

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

    r158569 r158698  
    33 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
    44 *           (C) 2001 Dirk Mueller (mueller@kde.org)
    5  * Copyright (C) 2004, 2007, 2008 Apple Inc. All rights reserved.
     5 * Copyright (C) 2004, 2007, 2008, 2013 Apple Inc. All rights reserved.
    66 *
    77 * This library is free software; you can redistribute it and/or
    … …  
    3636ChildNodeList::ChildNodeList(ContainerNode& parent)
    3737    : m_parent(parent)
    38     , m_cachedLength(0)
    39     , m_cachedLengthValid(false)
    40     , m_cachedCurrentPosition(0)
    41     , m_cachedCurrentNode(nullptr)
    4238{
    4339}
    … …  
    5046unsigned ChildNodeList::length() const
    5147{
    52     if (!m_cachedLengthValid) {
    53         m_cachedLength = m_parent->childNodeCount();
    54         m_cachedLengthValid = true;
    55     }
    56     return m_cachedLength;
    57 }
    58 
    59 static Node* childFromFirst(const ContainerNode& parent, unsigned delta)
    60 {
    61     Node* child = parent.firstChild();
    62     for (; delta && child; --delta)
    63         child = child->nextSibling();
    64     return child;
    65 }
    66 
    67 static Node* childFromLast(const ContainerNode& parent, unsigned delta)
    68 {
    69     Node* child = parent.lastChild();
    70     for (; delta; --delta)
    71         child = child->previousSibling();
    72     ASSERT(child);
    73     return child;
    74 }
    75 
    76 Node* ChildNodeList::nodeBeforeCached(unsigned index) const
    77 {
    78     ASSERT(m_cachedCurrentNode);
    79     ASSERT(index < m_cachedCurrentPosition);
    80     if (index < m_cachedCurrentPosition - index) {
    81         m_cachedCurrentNode = childFromFirst(m_parent.get(), index);
    82         m_cachedCurrentPosition = index;
    83         return m_cachedCurrentNode;
    84     }
    85     while (m_cachedCurrentNode && m_cachedCurrentPosition > index) {
    86         m_cachedCurrentNode = m_cachedCurrentNode->previousSibling();
    87         --m_cachedCurrentPosition;
    88     }
    89     return m_cachedCurrentNode;
    90 }
    91 
    92 Node* ChildNodeList::nodeAfterCached(unsigned index) const
    93 {
    94     ASSERT(m_cachedCurrentNode);
    95     ASSERT(index > m_cachedCurrentPosition);
    96     ASSERT(!m_cachedLengthValid || index < m_cachedLength);
    97     if (m_cachedLengthValid && m_cachedLength - index < index - m_cachedCurrentPosition) {
    98         m_cachedCurrentNode = childFromLast(m_parent.get(), m_cachedLength - index - 1);
    99         m_cachedCurrentPosition = index;
    100         return m_cachedCurrentNode;
    101     }
    102     while (m_cachedCurrentNode && m_cachedCurrentPosition < index) {
    103         m_cachedCurrentNode = m_cachedCurrentNode->nextSibling();
    104         ++m_cachedCurrentPosition;
    105     }
    106     if (!m_cachedCurrentNode && !m_cachedLengthValid) {
    107         m_cachedLength = m_cachedCurrentPosition;
    108         m_cachedLengthValid = true;
    109     }
    110     return m_cachedCurrentNode;
     48    return m_indexCache.nodeCount(*this);
    11149}
    11250
    11351Node* ChildNodeList::item(unsigned index) const
    11452{
    115     if (m_cachedLengthValid && index >= m_cachedLength)
    116         return nullptr;
    117     if (m_cachedCurrentNode) {
    118         if (index > m_cachedCurrentPosition)
    119             return nodeAfterCached(index);
    120         if (index < m_cachedCurrentPosition)
    121             return nodeBeforeCached(index);
    122         return m_cachedCurrentNode;
     53    return m_indexCache.nodeAt(*this, index);
     54}
     55
     56Node* ChildNodeList::collectionFirst() const
     57{
     58    return m_parent->firstChild();
     59}
     60
     61Node* ChildNodeList::collectionLast() const
     62{
     63    return m_parent->lastChild();
     64}
     65
     66Node* ChildNodeList::collectionTraverseForward(Node& current, unsigned count, unsigned& traversedCount) const
     67{
     68    ASSERT(count);
     69    Node* child = &current;
     70    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
     71        child = child->nextSibling();
     72        if (!child)
     73            return nullptr;
    12374    }
    124     if (m_cachedLengthValid && m_cachedLength - index < index)
    125         m_cachedCurrentNode = childFromLast(m_parent.get(), m_cachedLength - index - 1);
    126     else
    127         m_cachedCurrentNode = childFromFirst(m_parent.get(), index);
    128     m_cachedCurrentPosition = index;
    129     return m_cachedCurrentNode;
     75    return child;
     76}
     77
     78Node* ChildNodeList::collectionTraverseBackward(Node& current, unsigned count) const
     79{
     80    ASSERT(count);
     81    Node* child = &current;
     82    for (; count && child ; --count)
     83        child = child->previousSibling();
     84    return child;
    13085}
    13186
    … …  
    151106void ChildNodeList::invalidateCache()
    152107{
    153     m_cachedCurrentNode = nullptr;
    154     m_cachedLengthValid = false;
     108    m_indexCache.invalidate();
    155109}
    156110

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

    r158536 r158698  
    33 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
    44 *           (C) 2001 Dirk Mueller (mueller@kde.org)
    5  * Copyright (C) 2004, 2007 Apple Inc. All rights reserved.
     5 * Copyright (C) 2004, 2007, 2013 Apple Inc. All rights reserved.
    66 *
    77 * This library is free software; you can redistribute it and/or
    … …  
    2525#define ChildNodeList_h
    2626
     27#include "CollectionIndexCache.h"
    2728#include "NodeList.h"
    2829#include <wtf/Ref.h>
    … …  
    6869    void invalidateCache();
    6970
     71    // For CollectionIndexCache
     72    Node* collectionFirst() const;
     73    Node* collectionLast() const;
     74    Node* collectionTraverseForward(Node&, unsigned count, unsigned& traversedCount) const;
     75    Node* collectionTraverseBackward(Node&, unsigned count) const;
     76
    7077private:
    7178    explicit ChildNodeList(ContainerNode& parent);
    … …  
    7784    virtual bool isChildNodeList() const OVERRIDE { return true; }
    7885
    79     Node* nodeBeforeCached(unsigned) const;
    80     Node* nodeAfterCached(unsigned) const;
    81 
    8286    Ref<ContainerNode> m_parent;
    83     mutable unsigned m_cachedLength : 31;
    84     mutable unsigned m_cachedLengthValid : 1;
    85     mutable unsigned m_cachedCurrentPosition;
    86     mutable Node* m_cachedCurrentNode;
     87    mutable CollectionIndexCache<ChildNodeList, Node> m_indexCache;
    8788};
    8889

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

    r158663 r158698  
    33 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
    44 *           (C) 2001 Dirk Mueller (mueller@kde.org)
    5  * Copyright (C) 2004, 2006, 2007, 2008, 2010 Apple Inc. All rights reserved.
     5 * Copyright (C) 2004, 2006, 2007, 2008, 2010, 2013 Apple Inc. All rights reserved.
    66 *
    77 * This library is free software; you can redistribute it and/or
    … …  
    6868}
    6969
    70 ALWAYS_INLINE Element* LiveNodeList::itemBefore(Element* previous) const
     70template <class NodeListType>
     71inline Element* firstMatchingElement(const NodeListType* nodeList, ContainerNode& root)
    7172{
    72     Element* current;
    73     if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
    74         current = ElementTraversal::previous(previous, &rootNode());
    75     else
    76         current = ElementTraversal::lastWithin(&rootNode());
    77 
    78     return iterateForPreviousElement(current);
    79 }
    80 
    81 template <class NodeListType>
    82 inline Element* firstMatchingElement(const NodeListType* nodeList, ContainerNode* root)
    83 {
    84     Element* element = ElementTraversal::firstWithin(root);
     73    Element* element = ElementTraversal::firstWithin(&root);
    8574    while (element && !isMatchingElement(nodeList, element))
    86         element = ElementTraversal::next(element, root);
     75        element = ElementTraversal::next(element, &root);
    8776    return element;
    8877}
    8978
    9079template <class NodeListType>
    91 inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode* root)
     80inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
    9281{
    9382    do {
    94         current = ElementTraversal::next(current, root);
     83        current = ElementTraversal::next(current, &root);
    9584    } while (current && !isMatchingElement(nodeList, current));
    9685    return current;
    … …  
    9887
    9988template <class NodeListType>
    100 inline Element* traverseMatchingElementsForwardToOffset(const NodeListType* nodeList, unsigned offset, Element* currentElement, unsigned& currentOffset, ContainerNode* root)
     89inline Element* traverseMatchingElementsForward(const NodeListType* nodeList, Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root)
    10190{
    102     ASSERT_WITH_SECURITY_IMPLICATION(currentOffset < offset);
    103     while ((currentElement = nextMatchingElement(nodeList, currentElement, root))) {
    104         if (++currentOffset == offset)
    105             return currentElement;
     91    Element* element = &current;
     92    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
     93        element = nextMatchingElement(nodeList, element, root);
     94        if (!element)
     95            return nullptr;
    10696    }
    107     return 0;
     97    return element;
    10898}
    10999
    110 inline Element* LiveNodeList::traverseLiveNodeListFirstElement(ContainerNode* root) const
     100Element* LiveNodeList::collectionFirst() const
    111101{
     102    auto& root = rootNode();
    112103    if (type() == HTMLTagNodeListType)
    113104        return firstMatchingElement(static_cast<const HTMLTagNodeList*>(this), root);
    … …  
    117108}
    118109
    119 inline Element* LiveNodeList::traverseLiveNodeListForwardToOffset(unsigned offset, Element* currentElement, unsigned& currentOffset, ContainerNode* root) const
     110Element* LiveNodeList::collectionLast() const
    120111{
    121     if (type() == HTMLTagNodeListType)
    122         return traverseMatchingElementsForwardToOffset(static_cast<const HTMLTagNodeList*>(this), offset, currentElement, currentOffset, root);
    123     if (type() == ClassNodeListType)
    124         return traverseMatchingElementsForwardToOffset(static_cast<const ClassNodeList*>(this), offset, currentElement, currentOffset, root);
    125     return traverseMatchingElementsForwardToOffset(static_cast<const LiveNodeList*>(this), offset, currentElement, currentOffset, root);
     112    // FIXME: This should be optimized similarly to the forward case.
     113    return iterateForPreviousElement(ElementTraversal::lastWithin(&rootNode()));
    126114}
    127115
    128 bool ALWAYS_INLINE LiveNodeList::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
     116Element* LiveNodeList::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
    129117{
    130     ASSERT(isLengthCacheValid());
    131     unsigned distanceFromLastItem = cachedLength() - offset;
    132     if (!isElementCacheValid())
    133         return distanceFromLastItem < offset;
     118    auto& root = rootNode();
     119    if (type() == HTMLTagNodeListType)
     120        return traverseMatchingElementsForward(static_cast<const HTMLTagNodeList*>(this), current, count, traversedCount, root);
     121    if (type() == ClassNodeListType)
     122        return traverseMatchingElementsForward(static_cast<const ClassNodeList*>(this), current, count, traversedCount, root);
     123    return traverseMatchingElementsForward(static_cast<const LiveNodeList*>(this), current, count, traversedCount, root);
     124}
    134125
    135     return cachedElementOffset() < offset && distanceFromLastItem < offset - cachedElementOffset();
    136 }
    137    
    138 bool ALWAYS_INLINE LiveNodeList::isFirstItemCloserThanCachedItem(unsigned offset) const
     126Element* LiveNodeList::collectionTraverseBackward(Element& current, unsigned count) const
    139127{
    140     ASSERT(isElementCacheValid());
    141     if (cachedElementOffset() < offset)
    142         return false;
    143 
    144     unsigned distanceFromCachedItem = cachedElementOffset() - offset;
    145     return offset < distanceFromCachedItem;
     128    // FIXME: This should be optimized similarly to the forward case.
     129    auto& root = rootNode();
     130    Element* element = &current;
     131    for (; count && element ; --count)
     132        element = iterateForPreviousElement(ElementTraversal::previous(element, &root));
     133    return element;
    146134}
    147135
    148136unsigned LiveNodeList::length() const
    149137{
    150     if (isLengthCacheValid())
    151         return cachedLength();
    152 
    153     item(UINT_MAX);
    154     ASSERT(isLengthCacheValid());
    155    
    156     return cachedLength();
     138    return m_indexCache.nodeCount(*this);
    157139}
    158140
    159141Node* LiveNodeList::item(unsigned offset) const
    160142{
    161     if (isElementCacheValid() && cachedElementOffset() == offset)
    162         return cachedElement();
    163 
    164     if (isLengthCacheValid() && cachedLength() <= offset)
    165         return 0;
    166 
    167     ContainerNode& root = rootNode();
    168 
    169     if (isLengthCacheValid() && isLastItemCloserThanLastOrCachedItem(offset)) {
    170         Element* lastItem = itemBefore(0);
    171         ASSERT(lastItem);
    172         setCachedElement(*lastItem, cachedLength() - 1);
    173     } else if (!isElementCacheValid() || isFirstItemCloserThanCachedItem(offset)) {
    174         Element* firstItem = traverseLiveNodeListFirstElement(&root);
    175         if (!firstItem) {
    176             setLengthCache(0);
    177             return 0;
    178         }
    179         setCachedElement(*firstItem, 0);
    180         ASSERT(!cachedElementOffset());
    181     }
    182 
    183     if (cachedElementOffset() == offset)
    184         return cachedElement();
    185 
    186     return elementBeforeOrAfterCachedElement(offset, &root);
    187 }
    188 
    189 inline Element* LiveNodeList::elementBeforeOrAfterCachedElement(unsigned offset, ContainerNode* root) const
    190 {
    191     unsigned currentOffset = cachedElementOffset();
    192     Element* currentItem = cachedElement();
    193     ASSERT(currentItem);
    194     ASSERT(currentOffset != offset);
    195 
    196     if (offset < cachedElementOffset()) {
    197         while ((currentItem = itemBefore(currentItem))) {
    198             ASSERT(currentOffset);
    199             currentOffset--;
    200             if (currentOffset == offset) {
    201                 setCachedElement(*currentItem, currentOffset);
    202                 return currentItem;
    203             }
    204         }
    205         ASSERT_NOT_REACHED();
    206         return 0;
    207     }
    208 
    209     currentItem = traverseLiveNodeListForwardToOffset(offset, currentItem, currentOffset, root);
    210 
    211     if (!currentItem) {
    212         // Did not find the item. On plus side, we now know the length.
    213         setLengthCache(currentOffset + 1);
    214         return 0;
    215     }
    216     setCachedElement(*currentItem, currentOffset);
    217     return currentItem;
     143    return m_indexCache.nodeAt(*this, offset);
    218144}
    219145
    220146void LiveNodeList::invalidateCache() const
    221147{
    222     m_cachedElement = nullptr;
    223     m_isLengthCacheValid = false;
    224     m_isElementCacheValid = false;
     148    m_indexCache.invalidate();
    225149}
    226150

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

    r158665 r158698  
    33 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
    44 *           (C) 2001 Dirk Mueller (mueller@kde.org)
    5  * Copyright (C) 2004, 2006, 2007 Apple Inc. All rights reserved.
     5 * Copyright (C) 2004, 2006, 2007, 2013 Apple Inc. All rights reserved.
    66 *
    77 * This library is free software; you can redistribute it and/or
    … …  
    2525#define LiveNodeList_h
    2626
     27#include "CollectionIndexCache.h"
    2728#include "CollectionType.h"
    2829#include "Document.h"
    … …  
    5657    LiveNodeList(ContainerNode& ownerNode, Type type, NodeListInvalidationType invalidationType, NodeListRootType rootType = NodeListIsRootedAtNode)
    5758        : m_ownerNode(ownerNode)
    58         , m_cachedElement(nullptr)
    59         , m_isLengthCacheValid(false)
    60         , m_isElementCacheValid(false)
    6159        , m_rootType(rootType)
    6260        , m_invalidationType(invalidationType)
    … …  
    9290    void invalidateCache() const;
    9391
     92    // For CollectionIndexCache
     93    Element* collectionFirst() const;
     94    Element* collectionLast() const;
     95    Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
     96    Element* collectionTraverseBackward(Element&, unsigned count) const;
     97
    9498protected:
    9599    Document& document() const { return m_ownerNode->document(); }
    96100    ContainerNode& rootNode() const;
    97 
    98     ALWAYS_INLINE bool isElementCacheValid() const { return m_isElementCacheValid; }
    99     ALWAYS_INLINE Element* cachedElement() const { return m_cachedElement; }
    100     ALWAYS_INLINE unsigned cachedElementOffset() const { return m_cachedElementOffset; }
    101 
    102     ALWAYS_INLINE bool isLengthCacheValid() const { return m_isLengthCacheValid; }
    103     ALWAYS_INLINE unsigned cachedLength() const { return m_cachedLength; }
    104     ALWAYS_INLINE void setLengthCache(unsigned length) const
    105     {
    106         m_cachedLength = length;
    107         m_isLengthCacheValid = true;
    108     }
    109     ALWAYS_INLINE void setCachedElement(Element& element, unsigned offset) const
    110     {
    111         m_cachedElement = &element;
    112         m_cachedElementOffset = offset;
    113         m_isElementCacheValid = true;
    114     }
    115101
    116102    ALWAYS_INLINE NodeListRootType rootType() const { return static_cast<NodeListRootType>(m_rootType); }
    … …  
    119105    virtual bool isLiveNodeList() const OVERRIDE { return true; }
    120106
    121     Element* elementBeforeOrAfterCachedElement(unsigned offset, ContainerNode* root) const;
    122     Element* traverseLiveNodeListFirstElement(ContainerNode* root) const;
    123     Element* traverseLiveNodeListForwardToOffset(unsigned offset, Element* currentElement, unsigned& currentOffset, ContainerNode* root) const;
    124     bool isLastItemCloserThanLastOrCachedItem(unsigned offset) const;
    125     bool isFirstItemCloserThanCachedItem(unsigned offset) const;
    126107    Element* iterateForPreviousElement(Element* current) const;
    127     Element* itemBefore(Element* previousItem) const;
    128108
    129109    Ref<ContainerNode> m_ownerNode;
    130     mutable Element* m_cachedElement;
    131     mutable unsigned m_cachedLength;
    132     mutable unsigned m_cachedElementOffset;
    133     mutable unsigned m_isLengthCacheValid : 1;
    134     mutable unsigned m_isElementCacheValid : 1;
     110
     111    mutable CollectionIndexCache<LiveNodeList, Element> m_indexCache;
     112
    135113    const unsigned m_rootType : 2;
    136114    const unsigned m_invalidationType : 4;
Note: See TracChangeset for help on using the changeset viewer.