Diff
Modified: trunk/Source/WebCore/ChangeLog (166459 => 166460)
--- trunk/Source/WebCore/ChangeLog 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/ChangeLog 2014-03-30 08:32:13 UTC (rev 166460)
@@ -1,3 +1,82 @@
+2014-03-29 Antti Koivisto <an...@apple.com>
+
+ 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.
+
2014-03-29 Commit Queue <commit-qu...@webkit.org>
Unreviewed, rolling out r166434.
Modified: trunk/Source/WebCore/dom/ChildNodeList.cpp (166459 => 166460)
--- trunk/Source/WebCore/dom/ChildNodeList.cpp 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/dom/ChildNodeList.cpp 2014-03-30 08:32:13 UTC (rev 166460)
@@ -35,6 +35,7 @@
ChildNodeList::ChildNodeList(ContainerNode& parent)
: m_parent(parent)
+ , m_indexCache(*this)
{
}
@@ -53,7 +54,7 @@
return m_indexCache.nodeAt(*this, index);
}
-Node* ChildNodeList::collectionFirst() const
+Node* ChildNodeList::collectionBegin() const
{
return m_parent->firstChild();
}
@@ -63,25 +64,21 @@
return m_parent->lastChild();
}
-Node* ChildNodeList::collectionTraverseForward(Node& current, unsigned count, unsigned& traversedCount) const
+void ChildNodeList::collectionTraverseForward(Node*& current, unsigned count, unsigned& traversedCount) const
{
ASSERT(count);
- Node* child = ¤t;
for (traversedCount = 0; traversedCount < count; ++traversedCount) {
- child = child->nextSibling();
- if (!child)
- return nullptr;
+ current = current->nextSibling();
+ if (!current)
+ return;
}
- return child;
}
-Node* ChildNodeList::collectionTraverseBackward(Node& current, unsigned count) const
+void ChildNodeList::collectionTraverseBackward(Node*& current, unsigned count) const
{
ASSERT(count);
- Node* child = ¤t;
- for (; count && child ; --count)
- child = child->previousSibling();
- return child;
+ for (; count && current ; --count)
+ current = current->previousSibling();
}
Node* ChildNodeList::namedItem(const AtomicString& name) const
@@ -103,7 +100,7 @@
void ChildNodeList::invalidateCache()
{
- m_indexCache.invalidate();
+ m_indexCache.invalidate(*this);
}
} // namespace WebCore
Modified: trunk/Source/WebCore/dom/ChildNodeList.h (166459 => 166460)
--- trunk/Source/WebCore/dom/ChildNodeList.h 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/dom/ChildNodeList.h 2014-03-30 08:32:13 UTC (rev 166460)
@@ -70,10 +70,11 @@
void invalidateCache();
// For CollectionIndexCache
- Node* collectionFirst() const;
+ Node* collectionBegin() const;
Node* collectionLast() const;
- Node* collectionTraverseForward(Node&, unsigned count, unsigned& traversedCount) const;
- Node* collectionTraverseBackward(Node&, unsigned count) const;
+ Node* collectionEnd() const { return nullptr; }
+ void collectionTraverseForward(Node*&, unsigned count, unsigned& traversedCount) const;
+ void collectionTraverseBackward(Node*&, unsigned count) const;
bool collectionCanTraverseBackward() const { return true; }
void willValidateIndexCache() const { }
@@ -88,7 +89,7 @@
virtual bool isChildNodeList() const override { return true; }
Ref<ContainerNode> m_parent;
- mutable CollectionIndexCache<ChildNodeList, Node> m_indexCache;
+ mutable CollectionIndexCache<ChildNodeList, Node*> m_indexCache;
};
} // namespace WebCore
Modified: trunk/Source/WebCore/dom/CollectionIndexCache.h (166459 => 166460)
--- trunk/Source/WebCore/dom/CollectionIndexCache.h 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/dom/CollectionIndexCache.h 2014-03-30 08:32:13 UTC (rev 166460)
@@ -32,25 +32,26 @@
void reportExtraMemoryCostForCollectionIndexCache(size_t);
-template <class Collection, class NodeType>
+template <class Collection, class Iterator>
class CollectionIndexCache {
public:
- CollectionIndexCache();
+ explicit CollectionIndexCache(const Collection&);
+ typedef typename std::iterator_traits<Iterator>::value_type NodeType;
+
unsigned nodeCount(const Collection&);
NodeType* nodeAt(const Collection&, unsigned index);
- bool hasValidCache() const { return m_currentNode || m_nodeCountValid || m_listValid; }
- void invalidate();
+ bool hasValidCache(const Collection& collection) const { return m_current != collection.collectionEnd() || m_nodeCountValid || m_listValid; }
+ void invalidate(const Collection&);
size_t memoryCost() { return m_cachedList.capacity() * sizeof(NodeType*); }
private:
-
unsigned computeNodeCountUpdatingListCache(const Collection&);
- NodeType* nodeBeforeCached(const Collection&, unsigned);
- NodeType* nodeAfterCached(const Collection&, unsigned);
+ NodeType* traverseBackwardTo(const Collection&, unsigned);
+ NodeType* traverseForwardTo(const Collection&, unsigned);
- NodeType* m_currentNode;
+ Iterator m_current;
unsigned m_currentIndex;
unsigned m_nodeCount;
Vector<NodeType*> m_cachedList;
@@ -58,9 +59,9 @@
bool m_listValid : 1;
};
-template <class Collection, class NodeType>
-inline CollectionIndexCache<Collection, NodeType>::CollectionIndexCache()
- : m_currentNode(nullptr)
+template <class Collection, class Iterator>
+inline CollectionIndexCache<Collection, Iterator>::CollectionIndexCache(const Collection& collection)
+ : m_current(collection.collectionEnd())
, m_currentIndex(0)
, m_nodeCount(0)
, m_nodeCountValid(false)
@@ -68,11 +69,11 @@
{
}
-template <class Collection, class NodeType>
-inline unsigned CollectionIndexCache<Collection, NodeType>::nodeCount(const Collection& collection)
+template <class Collection, class Iterator>
+inline unsigned CollectionIndexCache<Collection, Iterator>::nodeCount(const Collection& collection)
{
if (!m_nodeCountValid) {
- if (!hasValidCache())
+ if (!hasValidCache(collection))
collection.willValidateIndexCache();
m_nodeCount = computeNodeCountUpdatingListCache(collection);
m_nodeCountValid = true;
@@ -81,20 +82,20 @@
return m_nodeCount;
}
-template <class Collection, class NodeType>
-unsigned CollectionIndexCache<Collection, NodeType>::computeNodeCountUpdatingListCache(const Collection& collection)
+template <class Collection, class Iterator>
+unsigned CollectionIndexCache<Collection, Iterator>::computeNodeCountUpdatingListCache(const Collection& collection)
{
- NodeType* first = collection.collectionFirst();
- if (!first)
+ auto current = collection.collectionBegin();
+ auto end = collection.collectionEnd();
+ if (current == end)
return 0;
unsigned oldCapacity = m_cachedList.capacity();
- NodeType* currentNode = first;
- while (currentNode) {
- m_cachedList.append(currentNode);
+ while (current != end) {
+ m_cachedList.append(&*current);
unsigned traversed;
- currentNode = collection.collectionTraverseForward(*currentNode, 1, traversed);
- ASSERT(traversed == (currentNode ? 1 : 0));
+ collection.collectionTraverseForward(current, 1, traversed);
+ ASSERT(traversed == (current != end ? 1 : 0));
}
m_listValid = true;
@@ -104,67 +105,67 @@
return m_cachedList.size();
}
-template <class Collection, class NodeType>
-inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeBeforeCached(const Collection& collection, unsigned index)
+template <class Collection, class Iterator>
+inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseBackwardTo(const Collection& collection, unsigned index)
{
- ASSERT(m_currentNode);
+ ASSERT(m_current != collection.collectionEnd());
ASSERT(index < m_currentIndex);
bool firstIsCloser = index < m_currentIndex - index;
if (firstIsCloser || !collection.collectionCanTraverseBackward()) {
- m_currentNode = collection.collectionFirst();
+ m_current = collection.collectionBegin();
m_currentIndex = 0;
if (index)
- m_currentNode = collection.collectionTraverseForward(*m_currentNode, index, m_currentIndex);
- ASSERT(m_currentNode);
- return m_currentNode;
+ collection.collectionTraverseForward(m_current, index, m_currentIndex);
+ ASSERT(m_current != collection.collectionEnd());
+ return &*m_current;
}
- m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_currentIndex - index);
+ collection.collectionTraverseBackward(m_current, m_currentIndex - index);
m_currentIndex = index;
- ASSERT(m_currentNode);
- return m_currentNode;
+ ASSERT(m_current != collection.collectionEnd());
+ return &*m_current;
}
-template <class Collection, class NodeType>
-inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAfterCached(const Collection& collection, unsigned index)
+template <class Collection, class Iterator>
+inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseForwardTo(const Collection& collection, unsigned index)
{
- ASSERT(m_currentNode);
+ ASSERT(m_current != collection.collectionEnd());
ASSERT(index > m_currentIndex);
ASSERT(!m_nodeCountValid || index < m_nodeCount);
bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index - m_currentIndex;
if (lastIsCloser && collection.collectionCanTraverseBackward()) {
- ASSERT(hasValidCache());
- m_currentNode = collection.collectionLast();
+ ASSERT(hasValidCache(collection));
+ m_current = collection.collectionLast();
if (index < m_nodeCount - 1)
- m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_nodeCount - index - 1);
+ collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1);
m_currentIndex = index;
- ASSERT(m_currentNode);
- return m_currentNode;
+ ASSERT(m_current != collection.collectionEnd());
+ return &*m_current;
}
- if (!hasValidCache())
+ if (!hasValidCache(collection))
collection.willValidateIndexCache();
unsigned traversedCount;
- m_currentNode = collection.collectionTraverseForward(*m_currentNode, index - m_currentIndex, traversedCount);
+ collection.collectionTraverseForward(m_current, index - m_currentIndex, traversedCount);
m_currentIndex = m_currentIndex + traversedCount;
- ASSERT(m_currentNode || m_currentIndex < index);
-
- if (!m_currentNode && !m_nodeCountValid) {
+ if (m_current == collection.collectionEnd()) {
+ ASSERT(m_currentIndex < index);
// Failed to find the index but at least we now know the size.
m_nodeCount = m_currentIndex + 1;
m_nodeCountValid = true;
+ return nullptr;
}
- ASSERT(hasValidCache());
- return m_currentNode;
+ ASSERT(hasValidCache(collection));
+ return &*m_current;
}
-template <class Collection, class NodeType>
-inline NodeType* CollectionIndexCache<Collection, NodeType>::nodeAt(const Collection& collection, unsigned index)
+template <class Collection, class Iterator>
+inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::nodeAt(const Collection& collection, unsigned index)
{
if (m_nodeCountValid && index >= m_nodeCount)
return nullptr;
@@ -172,47 +173,49 @@
if (m_listValid)
return m_cachedList[index];
- if (m_currentNode) {
+ auto end = collection.collectionEnd();
+ if (m_current != end) {
if (index > m_currentIndex)
- return nodeAfterCached(collection, index);
+ return traverseForwardTo(collection, index);
if (index < m_currentIndex)
- return nodeBeforeCached(collection, index);
- return m_currentNode;
+ return traverseBackwardTo(collection, index);
+ return &*m_current;
}
bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index;
if (lastIsCloser && collection.collectionCanTraverseBackward()) {
- ASSERT(hasValidCache());
- m_currentNode = collection.collectionLast();
+ ASSERT(hasValidCache(collection));
+ m_current = collection.collectionLast();
if (index < m_nodeCount - 1)
- m_currentNode = collection.collectionTraverseBackward(*m_currentNode, m_nodeCount - index - 1);
+ collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1);
m_currentIndex = index;
- ASSERT(m_currentNode);
- return m_currentNode;
+ ASSERT(m_current != end);
+ return &*m_current;
}
- if (!hasValidCache())
+ if (!hasValidCache(collection))
collection.willValidateIndexCache();
- m_currentNode = collection.collectionFirst();
+ m_current = collection.collectionBegin();
m_currentIndex = 0;
- if (index && m_currentNode) {
- m_currentNode = collection.collectionTraverseForward(*m_currentNode, index, m_currentIndex);
- ASSERT(m_currentNode || m_currentIndex < index);
+ if (index && m_current != end) {
+ collection.collectionTraverseForward(m_current, index, m_currentIndex);
+ ASSERT(m_current != end || m_currentIndex < index);
}
- if (!m_currentNode && !m_nodeCountValid) {
+ if (m_current == end) {
// Failed to find the index but at least we now know the size.
m_nodeCount = m_currentIndex + 1;
m_nodeCountValid = true;
+ return nullptr;
}
- ASSERT(hasValidCache());
- return m_currentNode;
+ ASSERT(hasValidCache(collection));
+ return &*m_current;
}
-template <class Collection, class NodeType>
-void CollectionIndexCache<Collection, NodeType>::invalidate()
+template <class Collection, class Iterator>
+void CollectionIndexCache<Collection, Iterator>::invalidate(const Collection& collection)
{
- m_currentNode = nullptr;
+ m_current = collection.collectionEnd();
m_nodeCountValid = false;
m_listValid = false;
m_cachedList.shrink(0);
Modified: trunk/Source/WebCore/dom/ElementDescendantIterator.h (166459 => 166460)
--- trunk/Source/WebCore/dom/ElementDescendantIterator.h 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/dom/ElementDescendantIterator.h 2014-03-30 08:32:13 UTC (rev 166460)
@@ -39,6 +39,7 @@
explicit ElementDescendantIterator(Element* current);
ElementDescendantIterator& operator++();
+ ElementDescendantIterator& operator--();
Element& operator*();
Element* operator->();
@@ -82,6 +83,7 @@
ElementDescendantIteratorAdapter(ContainerNode& root);
ElementDescendantIterator begin();
ElementDescendantIterator end();
+ ElementDescendantIterator last();
private:
ContainerNode& m_root;
@@ -92,6 +94,7 @@
ElementDescendantConstIteratorAdapter(const ContainerNode& root);
ElementDescendantConstIterator begin() const;
ElementDescendantConstIterator end() const;
+ ElementDescendantConstIterator last() const;
private:
const ContainerNode& m_root;
@@ -144,6 +147,40 @@
return *this;
}
+ALWAYS_INLINE ElementDescendantIterator& ElementDescendantIterator::operator--()
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+
+ Element* previousSibling = ElementTraversal::previousSibling(m_current);
+
+ if (!previousSibling) {
+ m_current = m_current->parentElement();
+ // The stack optimizes for forward traversal only, this just maintains consistency.
+ if (m_current->nextSibling() == m_ancestorSiblingStack.last())
+ m_ancestorSiblingStack.removeLast();
+ return *this;
+ }
+
+ Element* deepestSibling = previousSibling;
+ while (Element* lastChild = ElementTraversal::lastChild(deepestSibling))
+ deepestSibling = lastChild;
+ ASSERT(deepestSibling);
+
+ if (deepestSibling != previousSibling)
+ m_ancestorSiblingStack.append(m_current);
+
+ m_current = deepestSibling;
+
+#if !ASSERT_DISABLED
+ // Drop the assertion when the iterator reaches the end.
+ if (!m_current)
+ m_assertions.dropEventDispatchAssertion();
+#endif
+
+ return *this;
+}
+
inline Element& ElementDescendantIterator::operator*()
{
ASSERT(m_current);
@@ -255,6 +292,11 @@
return ElementDescendantIterator();
}
+inline ElementDescendantIterator ElementDescendantIteratorAdapter::last()
+{
+ return ElementDescendantIterator(ElementTraversal::lastWithin(&m_root));
+}
+
// ElementDescendantConstIteratorAdapter
inline ElementDescendantConstIteratorAdapter::ElementDescendantConstIteratorAdapter(const ContainerNode& root)
@@ -272,6 +314,11 @@
return ElementDescendantConstIterator();
}
+inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::last() const
+{
+ return ElementDescendantConstIterator(ElementTraversal::lastWithin(&m_root));
+}
+
// Standalone functions
inline ElementDescendantIteratorAdapter elementDescendants(ContainerNode& root)
@@ -286,4 +333,12 @@
}
+namespace std {
+template <> struct iterator_traits<WebCore::ElementDescendantIterator> {
+ typedef WebCore::Element value_type;
+};
+template <> struct iterator_traits<WebCore::ElementDescendantConstIterator> {
+ typedef const WebCore::Element value_type;
+};
+}
#endif
Modified: trunk/Source/WebCore/dom/LiveNodeList.h (166459 => 166460)
--- trunk/Source/WebCore/dom/LiveNodeList.h 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/dom/LiveNodeList.h 2014-03-30 08:32:13 UTC (rev 166460)
@@ -27,7 +27,7 @@
#include "CollectionIndexCache.h"
#include "CollectionType.h"
#include "Document.h"
-#include "ElementTraversal.h"
+#include "ElementDescendantIterator.h"
#include "HTMLNames.h"
#include "NodeList.h"
#include <wtf/Forward.h>
@@ -69,8 +69,6 @@
ContainerNode& rootNode() const;
- Element* iterateForPreviousElement(Element* current) const;
-
Ref<ContainerNode> m_ownerNode;
const unsigned m_invalidationType;
@@ -86,10 +84,11 @@
virtual Node* item(unsigned offset) const override final;
// For CollectionIndexCache
- Element* collectionFirst() const;
- Element* collectionLast() const;
- Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
- Element* collectionTraverseBackward(Element&, unsigned count) const;
+ ElementDescendantIterator collectionBegin() const;
+ ElementDescendantIterator collectionLast() const;
+ ElementDescendantIterator collectionEnd() const { return ElementDescendantIterator(); }
+ void collectionTraverseForward(ElementDescendantIterator&, unsigned count, unsigned& traversedCount) const;
+ void collectionTraverseBackward(ElementDescendantIterator&, unsigned count) const;
bool collectionCanTraverseBackward() const { return true; }
void willValidateIndexCache() const;
@@ -102,7 +101,7 @@
private:
ContainerNode& rootNode() const;
- mutable CollectionIndexCache<NodeListType, Element> m_indexCache;
+ mutable CollectionIndexCache<NodeListType, ElementDescendantIterator> m_indexCache;
};
ALWAYS_INLINE bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
@@ -132,13 +131,15 @@
template <class NodeListType>
CachedLiveNodeList<NodeListType>::CachedLiveNodeList(ContainerNode& ownerNode, NodeListInvalidationType invalidationType)
: LiveNodeList(ownerNode, invalidationType)
+ , m_indexCache(static_cast<NodeListType&>(*this))
{
}
template <class NodeListType>
CachedLiveNodeList<NodeListType>::~CachedLiveNodeList()
{
- if (m_indexCache.hasValidCache())
+ auto& nodeList = static_cast<const NodeListType&>(*this);
+ if (m_indexCache.hasValidCache(nodeList))
document().unregisterNodeListForInvalidation(*this);
}
@@ -152,68 +153,61 @@
}
template <class NodeListType>
-Element* CachedLiveNodeList<NodeListType>::collectionFirst() const
+ElementDescendantIterator CachedLiveNodeList<NodeListType>::collectionBegin() const
{
- auto& root = rootNode();
- Element* element = ElementTraversal::firstWithin(&root);
- while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
- element = ElementTraversal::next(element, &root);
- return element;
+ auto& nodeList = static_cast<const NodeListType&>(*this);
+ auto descendants = elementDescendants(rootNode());
+ auto end = descendants.end();
+ for (auto it = descendants.begin(); it != end; ++it) {
+ if (nodeList.nodeMatches(&*it))
+ return it;
+ }
+ return end;
}
template <class NodeListType>
-Element* CachedLiveNodeList<NodeListType>::collectionLast() const
+ElementDescendantIterator CachedLiveNodeList<NodeListType>::collectionLast() const
{
- auto& root = rootNode();
- Element* element = ElementTraversal::lastWithin(&root);
- while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
- element = ElementTraversal::previous(element, &root);
- return element;
+ auto& nodeList = static_cast<const NodeListType&>(*this);
+ auto descendants = elementDescendants(rootNode());
+ auto end = descendants.end();
+ for (auto it = descendants.last(); it != end; --it) {
+ if (nodeList.nodeMatches(&*it))
+ return it;
+ }
+ return end;
}
template <class NodeListType>
-inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
+void CachedLiveNodeList<NodeListType>::collectionTraverseForward(ElementDescendantIterator& current, unsigned count, unsigned& traversedCount) const
{
- do {
- current = ElementTraversal::next(current, &root);
- } while (current && !static_cast<const NodeListType*>(nodeList)->nodeMatches(current));
- return current;
-}
-
-template <class NodeListType>
-Element* CachedLiveNodeList<NodeListType>::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
-{
- auto& root = rootNode();
- Element* element = ¤t;
+ auto& nodeList = static_cast<const NodeListType&>(*this);
+ ASSERT(nodeList.nodeMatches(&*current));
+ auto end = collectionEnd();
for (traversedCount = 0; traversedCount < count; ++traversedCount) {
- element = nextMatchingElement(static_cast<const NodeListType*>(this), element, root);
- if (!element)
- return nullptr;
+ do {
+ ++current;
+ if (current == end)
+ return;
+ } while (!nodeList.nodeMatches(&*current));
}
- return element;
}
template <class NodeListType>
-inline Element* previousMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
+void CachedLiveNodeList<NodeListType>::collectionTraverseBackward(ElementDescendantIterator& current, unsigned count) const
{
- do {
- current = ElementTraversal::previous(current, &root);
- } while (current && !nodeList->nodeMatches(current));
- return current;
-}
-
-template <class NodeListType>
-Element* CachedLiveNodeList<NodeListType>::collectionTraverseBackward(Element& current, unsigned count) const
-{
- auto& root = rootNode();
- Element* element = ¤t;
+ auto& nodeList = static_cast<const NodeListType&>(*this);
+ ASSERT(nodeList.nodeMatches(&*current));
+ auto end = collectionEnd();
for (; count; --count) {
- element = previousMatchingElement(static_cast<const NodeListType*>(this), element, root);
- if (!element)
- return nullptr;
+ do {
+ --current;
+ if (current == end)
+ return;
+ } while (!nodeList.nodeMatches(&*current));
}
- return element;
}
+
template <class NodeListType>
void CachedLiveNodeList<NodeListType>::willValidateIndexCache() const
{
@@ -223,10 +217,11 @@
template <class NodeListType>
void CachedLiveNodeList<NodeListType>::invalidateCache(Document& document) const
{
- if (!m_indexCache.hasValidCache())
+ auto& nodeList = static_cast<const NodeListType&>(*this);
+ if (!m_indexCache.hasValidCache(nodeList))
return;
- document.unregisterNodeListForInvalidation(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
- m_indexCache.invalidate();
+ document.unregisterNodeListForInvalidation(const_cast<NodeListType&>(nodeList));
+ m_indexCache.invalidate(nodeList);
}
template <class NodeListType>
Modified: trunk/Source/WebCore/html/HTMLCollection.cpp (166459 => 166460)
--- trunk/Source/WebCore/html/HTMLCollection.cpp 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/html/HTMLCollection.cpp 2014-03-30 08:32:13 UTC (rev 166460)
@@ -133,6 +133,7 @@
HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType)
: m_ownerNode(ownerNode)
+ , m_indexCache(*this)
, m_collectionType(type)
, m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
, m_rootType(rootTypeFromCollectionType(type))
@@ -151,7 +152,7 @@
HTMLCollection::~HTMLCollection()
{
- if (m_indexCache.hasValidCache())
+ if (m_indexCache.hasValidCache(*this))
document().unregisterCollection(*this);
if (hasNamedElementCache())
document().collectionWillClearIdNameMap(*this);
@@ -330,7 +331,7 @@
return element;
}
-Element* HTMLCollection::collectionFirst() const
+Element* HTMLCollection::collectionBegin() const
{
return firstElement(rootNode());
}
@@ -343,31 +344,29 @@
return iterateForPreviousElement(last);
}
-Element* HTMLCollection::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
+void HTMLCollection::collectionTraverseForward(Element*& current, unsigned count, unsigned& traversedCount) const
{
- return traverseForward(current, count, traversedCount, rootNode());
+ current = traverseForward(*current, count, traversedCount, rootNode());
}
-Element* HTMLCollection::collectionTraverseBackward(Element& current, unsigned count) const
+void HTMLCollection::collectionTraverseBackward(Element*& current, unsigned count) const
{
// FIXME: This should be optimized similarly to the forward case.
auto& root = rootNode();
- Element* element = ¤t;
if (m_shouldOnlyIncludeDirectChildren) {
- for (; count && element ; --count)
- element = iterateForPreviousElement(ElementTraversal::previousSibling(element));
- return element;
+ for (; count && current ; --count)
+ current = iterateForPreviousElement(ElementTraversal::previousSibling(current));
+ return;
}
- for (; count && element ; --count)
- element = iterateForPreviousElement(ElementTraversal::previous(element, &root));
- return element;
+ for (; count && current ; --count)
+ current = iterateForPreviousElement(ElementTraversal::previous(current, &root));
}
void HTMLCollection::invalidateCache(Document& document) const
{
- if (m_indexCache.hasValidCache()) {
+ if (m_indexCache.hasValidCache(*this)) {
document.unregisterCollection(const_cast<HTMLCollection&>(*this));
- m_indexCache.invalidate();
+ m_indexCache.invalidate(*this);
}
if (hasNamedElementCache())
invalidateNamedElementCache(document);
Modified: trunk/Source/WebCore/html/HTMLCollection.h (166459 => 166460)
--- trunk/Source/WebCore/html/HTMLCollection.h 2014-03-30 06:01:08 UTC (rev 166459)
+++ trunk/Source/WebCore/html/HTMLCollection.h 2014-03-30 08:32:13 UTC (rev 166460)
@@ -118,10 +118,11 @@
virtual void invalidateCache(Document&) const;
// For CollectionIndexCache
- Element* collectionFirst() const;
+ Element* collectionBegin() const;
Element* collectionLast() const;
- Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
- Element* collectionTraverseBackward(Element&, unsigned count) const;
+ Element* collectionEnd() const { return nullptr; }
+ void collectionTraverseForward(Element*&, unsigned count, unsigned& traversedCount) const;
+ void collectionTraverseBackward(Element*&, unsigned count) const;
bool collectionCanTraverseBackward() const { return !m_usesCustomForwardOnlyTraversal; }
void willValidateIndexCache() const { document().registerCollection(const_cast<HTMLCollection&>(*this)); }
@@ -164,7 +165,7 @@
Ref<ContainerNode> m_ownerNode;
- mutable CollectionIndexCache<HTMLCollection, Element> m_indexCache;
+ mutable CollectionIndexCache<HTMLCollection, Element*> m_indexCache;
mutable std::unique_ptr<CollectionNamedElementCache> m_namedElementCache;
const unsigned m_collectionType : 5;