From 60aad7b836a83c963d20c6f16448529fc9aafaab Mon Sep 17 00:00:00 2001 From: "rniwa@webkit.org" Date: Fri, 29 Jun 2012 18:58:31 +0000 Subject: [PATCH] Share the same cache in HTMLCollection and DynamicNodeLists https://bugs.webkit.org/show_bug.cgi?id=90118 Reviewed by Anders Carlsson. This patch introduces two new base classes DynamicNodeListCacheBase and HTMLCollectionCacheBase to share the cache object between DynamicNodeList and HTMLCollection. HTMLCollectionCacheBase inherits from DynamicNodeListCacheBase and contains extra caches and bit flags for HTMLCollection. DynamicNodeList::Cache and HTMLCollection::Cache had been removed and flattened into these two classes for the easy inheritance. In DynamicNodeList, we have a very straight forward one-to-one mapping from old Caches member variables: m_caches.lastItem -> cachedItem() m_caches.lastItemOffset -> cachedItemOffset() m_caches.cachedLength -> cachedLength() m_caches.isItemCacheValid -> isItemCacheValid() m_caches.isLengthCacheValid -> isLengthCacheValid() m_caches.type -> removed because it was never used. m_caches.rootedAtDocument -> isRootedAtDocument() m_caches.shouldInvalidateOnAttributeChange -> shouldInvalidateOnAttributeChange() In HTMLCollection, there is one semantic change in the way item cache is managed. Previously, we only had m_cache.current which was used as both cachedItem() and isItemCacheValid() (not valid when current is null). There are some asymmetric code changes due to one-to-many relationship. Also, all method names have been updated to use that of DynamicNodeList terminology. Thus we have the following correspondence: m_cache.current -> cachedItem() / isItemCacheValid() m_cache.position -> cachedItemOffset() m_cache.length -> cachedLength() m_cache.elementsArrayPosition -> cachedElementsArrayOffset() m_cache.hasLength -> isLengthCacheValid() m_cache.hasNameCache -> hasNameCache() / setHasNameCache() m_cache.idCache -> idCache() / addIdCache() m_cache.nameCache -> idCache() / addNameCache() In addition, we had to rename HTMLCollection::clearCache to invalidateCache to avoid the name collision with HTMLCollectionCacheBase::clearCache. * dom/ChildNodeList.cpp: (WebCore::ChildNodeList::length): (WebCore::ChildNodeList::item): * dom/DynamicNodeList.cpp: (WebCore::DynamicSubtreeNodeList::length): (WebCore::DynamicSubtreeNodeList::itemForwardsFromCurrent): (WebCore::DynamicSubtreeNodeList::itemBackwardsFromCurrent): (WebCore::DynamicSubtreeNodeList::item): * dom/DynamicNodeList.h: (DynamicNodeListCacheBase): (WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): (WebCore::DynamicNodeListCacheBase::isRootedAtDocument): (WebCore::DynamicNodeListCacheBase::shouldInvalidateOnAttributeChange): (WebCore::DynamicNodeListCacheBase::isItemCacheValid): (WebCore::DynamicNodeListCacheBase::cachedItem): (WebCore::DynamicNodeListCacheBase::cachedItemOffset): (WebCore::DynamicNodeListCacheBase::isLengthCacheValid): (WebCore::DynamicNodeListCacheBase::cachedLength): (WebCore::DynamicNodeListCacheBase::setLengthCache): (WebCore::DynamicNodeListCacheBase::setItemCache): (WebCore::DynamicNodeListCacheBase::clearCache): (WebCore): (WebCore::DynamicNodeList::DynamicNodeList): (WebCore::DynamicNodeList::invalidateCache): (WebCore::DynamicNodeList::rootNode): (DynamicNodeList): * html/HTMLAllCollection.cpp: (WebCore::HTMLAllCollection::namedItemWithIndex): * html/HTMLCollection.cpp: (WebCore::HTMLCollection::HTMLCollection): (WebCore::HTMLCollection::invalidateCacheIfNeeded): (WebCore::HTMLCollection::invalidateCache): (WebCore::HTMLCollection::isAcceptableElement): (WebCore::HTMLCollection::itemAfter): (WebCore::HTMLCollection::length): (WebCore::HTMLCollection::item): (WebCore::HTMLCollection::checkForNameMatch): (WebCore::HTMLCollection::namedItem): (WebCore::HTMLCollection::updateNameCache): (WebCore::HTMLCollection::hasNamedItem): (WebCore::HTMLCollection::namedItems): (WebCore::HTMLCollectionCacheBase::append): * html/HTMLCollection.h: (HTMLCollectionCacheBase): (WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase): (WebCore::HTMLCollectionCacheBase::type): (WebCore::HTMLCollectionCacheBase::clearCache): (WebCore::HTMLCollectionCacheBase::setItemCache): (WebCore::HTMLCollectionCacheBase::cachedElementsArrayOffset): (WebCore::HTMLCollectionCacheBase::includeChildren): (WebCore::HTMLCollectionCacheBase::cacheTreeVersion): (WebCore::HTMLCollectionCacheBase::idCache): (WebCore::HTMLCollectionCacheBase::nameCache): (WebCore::HTMLCollectionCacheBase::appendIdCache): (WebCore::HTMLCollectionCacheBase::appendNameCache): (WebCore::HTMLCollectionCacheBase::hasNameCache): (WebCore::HTMLCollectionCacheBase::setHasNameCache): (WebCore): (WebCore::HTMLCollection::isEmpty): (WebCore::HTMLCollection::hasExactlyOneItem): (WebCore::HTMLCollection::base): (HTMLCollection): * html/HTMLFormCollection.cpp: (WebCore::HTMLFormCollection::item): (WebCore::HTMLFormCollection::updateNameCache): * html/HTMLNameCollection.cpp: (WebCore::HTMLNameCollection::itemAfter): * html/HTMLNameCollection.h: (HTMLNameCollection): * html/HTMLSelectElement.cpp: (WebCore::HTMLSelectElement::invalidateSelectedItems): * html/HTMLTableRowsCollection.cpp: (WebCore::HTMLTableRowsCollection::itemAfter): * html/HTMLTableRowsCollection.h: (HTMLTableRowsCollection): git-svn-id: http://svn.webkit.org/repository/webkit/trunk@121580 268f45cc-cd09-0410-ab3c-d52691b4dbfc --- Source/WebCore/ChangeLog | 116 +++++++++++++++++++++++ Source/WebCore/dom/ChildNodeList.cpp | 33 +++---- Source/WebCore/dom/DynamicNodeList.cpp | 27 +++--- Source/WebCore/dom/DynamicNodeList.h | 112 +++++++++++++--------- Source/WebCore/html/HTMLAllCollection.cpp | 14 +-- Source/WebCore/html/HTMLCollection.cpp | 85 ++++++++--------- Source/WebCore/html/HTMLCollection.h | 119 +++++++++++++++--------- Source/WebCore/html/HTMLFormCollection.cpp | 35 +++---- Source/WebCore/html/HTMLNameCollection.cpp | 2 +- Source/WebCore/html/HTMLNameCollection.h | 2 +- Source/WebCore/html/HTMLSelectElement.cpp | 2 +- Source/WebCore/html/HTMLTableRowsCollection.cpp | 4 +- Source/WebCore/html/HTMLTableRowsCollection.h | 2 +- 13 files changed, 352 insertions(+), 201 deletions(-) diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog index d8c6a6a..caa1213 100644 --- a/Source/WebCore/ChangeLog +++ b/Source/WebCore/ChangeLog @@ -1,3 +1,119 @@ +2012-06-29 Ryosuke Niwa + + Share the same cache in HTMLCollection and DynamicNodeLists + https://bugs.webkit.org/show_bug.cgi?id=90118 + + Reviewed by Anders Carlsson. + + This patch introduces two new base classes DynamicNodeListCacheBase and HTMLCollectionCacheBase to share + the cache object between DynamicNodeList and HTMLCollection. HTMLCollectionCacheBase inherits from + DynamicNodeListCacheBase and contains extra caches and bit flags for HTMLCollection. DynamicNodeList::Cache + and HTMLCollection::Cache had been removed and flattened into these two classes for the easy inheritance. + + In DynamicNodeList, we have a very straight forward one-to-one mapping from old Caches member variables: + + m_caches.lastItem -> cachedItem() + m_caches.lastItemOffset -> cachedItemOffset() + m_caches.cachedLength -> cachedLength() + m_caches.isItemCacheValid -> isItemCacheValid() + m_caches.isLengthCacheValid -> isLengthCacheValid() + m_caches.type -> removed because it was never used. + m_caches.rootedAtDocument -> isRootedAtDocument() + m_caches.shouldInvalidateOnAttributeChange -> shouldInvalidateOnAttributeChange() + + In HTMLCollection, there is one semantic change in the way item cache is managed. Previously, we only had + m_cache.current which was used as both cachedItem() and isItemCacheValid() (not valid when current is null). + There are some asymmetric code changes due to one-to-many relationship. Also, all method names have been updated + to use that of DynamicNodeList terminology. Thus we have the following correspondence: + + m_cache.current -> cachedItem() / isItemCacheValid() + m_cache.position -> cachedItemOffset() + m_cache.length -> cachedLength() + m_cache.elementsArrayPosition -> cachedElementsArrayOffset() + m_cache.hasLength -> isLengthCacheValid() + m_cache.hasNameCache -> hasNameCache() / setHasNameCache() + m_cache.idCache -> idCache() / addIdCache() + m_cache.nameCache -> idCache() / addNameCache() + + In addition, we had to rename HTMLCollection::clearCache to invalidateCache to avoid the name collision with + HTMLCollectionCacheBase::clearCache. + + * dom/ChildNodeList.cpp: + (WebCore::ChildNodeList::length): + (WebCore::ChildNodeList::item): + * dom/DynamicNodeList.cpp: + (WebCore::DynamicSubtreeNodeList::length): + (WebCore::DynamicSubtreeNodeList::itemForwardsFromCurrent): + (WebCore::DynamicSubtreeNodeList::itemBackwardsFromCurrent): + (WebCore::DynamicSubtreeNodeList::item): + * dom/DynamicNodeList.h: + (DynamicNodeListCacheBase): + (WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): + (WebCore::DynamicNodeListCacheBase::isRootedAtDocument): + (WebCore::DynamicNodeListCacheBase::shouldInvalidateOnAttributeChange): + (WebCore::DynamicNodeListCacheBase::isItemCacheValid): + (WebCore::DynamicNodeListCacheBase::cachedItem): + (WebCore::DynamicNodeListCacheBase::cachedItemOffset): + (WebCore::DynamicNodeListCacheBase::isLengthCacheValid): + (WebCore::DynamicNodeListCacheBase::cachedLength): + (WebCore::DynamicNodeListCacheBase::setLengthCache): + (WebCore::DynamicNodeListCacheBase::setItemCache): + (WebCore::DynamicNodeListCacheBase::clearCache): + (WebCore): + (WebCore::DynamicNodeList::DynamicNodeList): + (WebCore::DynamicNodeList::invalidateCache): + (WebCore::DynamicNodeList::rootNode): + (DynamicNodeList): + * html/HTMLAllCollection.cpp: + (WebCore::HTMLAllCollection::namedItemWithIndex): + * html/HTMLCollection.cpp: + (WebCore::HTMLCollection::HTMLCollection): + (WebCore::HTMLCollection::invalidateCacheIfNeeded): + (WebCore::HTMLCollection::invalidateCache): + (WebCore::HTMLCollection::isAcceptableElement): + (WebCore::HTMLCollection::itemAfter): + (WebCore::HTMLCollection::length): + (WebCore::HTMLCollection::item): + (WebCore::HTMLCollection::checkForNameMatch): + (WebCore::HTMLCollection::namedItem): + (WebCore::HTMLCollection::updateNameCache): + (WebCore::HTMLCollection::hasNamedItem): + (WebCore::HTMLCollection::namedItems): + (WebCore::HTMLCollectionCacheBase::append): + * html/HTMLCollection.h: + (HTMLCollectionCacheBase): + (WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase): + (WebCore::HTMLCollectionCacheBase::type): + (WebCore::HTMLCollectionCacheBase::clearCache): + (WebCore::HTMLCollectionCacheBase::setItemCache): + (WebCore::HTMLCollectionCacheBase::cachedElementsArrayOffset): + (WebCore::HTMLCollectionCacheBase::includeChildren): + (WebCore::HTMLCollectionCacheBase::cacheTreeVersion): + (WebCore::HTMLCollectionCacheBase::idCache): + (WebCore::HTMLCollectionCacheBase::nameCache): + (WebCore::HTMLCollectionCacheBase::appendIdCache): + (WebCore::HTMLCollectionCacheBase::appendNameCache): + (WebCore::HTMLCollectionCacheBase::hasNameCache): + (WebCore::HTMLCollectionCacheBase::setHasNameCache): + (WebCore): + (WebCore::HTMLCollection::isEmpty): + (WebCore::HTMLCollection::hasExactlyOneItem): + (WebCore::HTMLCollection::base): + (HTMLCollection): + * html/HTMLFormCollection.cpp: + (WebCore::HTMLFormCollection::item): + (WebCore::HTMLFormCollection::updateNameCache): + * html/HTMLNameCollection.cpp: + (WebCore::HTMLNameCollection::itemAfter): + * html/HTMLNameCollection.h: + (HTMLNameCollection): + * html/HTMLSelectElement.cpp: + (WebCore::HTMLSelectElement::invalidateSelectedItems): + * html/HTMLTableRowsCollection.cpp: + (WebCore::HTMLTableRowsCollection::itemAfter): + * html/HTMLTableRowsCollection.h: + (HTMLTableRowsCollection): + 2012-06-29 Tony Chang Unreviewed, rolling out r121572. diff --git a/Source/WebCore/dom/ChildNodeList.cpp b/Source/WebCore/dom/ChildNodeList.cpp index 449fb82..4b50bc8 100644 --- a/Source/WebCore/dom/ChildNodeList.cpp +++ b/Source/WebCore/dom/ChildNodeList.cpp @@ -39,15 +39,14 @@ ChildNodeList::~ChildNodeList() unsigned ChildNodeList::length() const { - if (m_caches.isLengthCacheValid) - return m_caches.cachedLength; + if (isLengthCacheValid()) + return cachedLength(); unsigned len = 0; for (Node* n = rootNode()->firstChild(); n; n = n->nextSibling()) len++; - m_caches.cachedLength = len; - m_caches.isLengthCacheValid = true; + setLengthCache(len); return len; } @@ -57,27 +56,27 @@ Node* ChildNodeList::item(unsigned index) const unsigned int pos = 0; Node* n = rootNode()->firstChild(); - if (m_caches.isItemCacheValid) { - if (index == m_caches.lastItemOffset) - return m_caches.lastItem; - - int diff = index - m_caches.lastItemOffset; + if (isItemCacheValid()) { + if (index == cachedItemOffset()) + return cachedItem(); + + int diff = index - cachedItemOffset(); unsigned dist = abs(diff); if (dist < index) { - n = m_caches.lastItem; - pos = m_caches.lastItemOffset; + n = cachedItem(); + pos = cachedItemOffset(); } } - if (m_caches.isLengthCacheValid) { - if (index >= m_caches.cachedLength) + if (isLengthCacheValid()) { + if (index >= cachedLength()) return 0; int diff = index - pos; unsigned dist = abs(diff); - if (dist > m_caches.cachedLength - 1 - index) { + if (dist > cachedLength() - 1 - index) { n = rootNode()->lastChild(); - pos = m_caches.cachedLength - 1; + pos = cachedLength() - 1; } } @@ -94,9 +93,7 @@ Node* ChildNodeList::item(unsigned index) const } if (n) { - m_caches.lastItem = n; - m_caches.lastItemOffset = pos; - m_caches.isItemCacheValid = true; + setItemCache(n, pos); return n; } diff --git a/Source/WebCore/dom/DynamicNodeList.cpp b/Source/WebCore/dom/DynamicNodeList.cpp index d169a6c..b97125c 100644 --- a/Source/WebCore/dom/DynamicNodeList.cpp +++ b/Source/WebCore/dom/DynamicNodeList.cpp @@ -34,8 +34,8 @@ DynamicSubtreeNodeList::~DynamicSubtreeNodeList() unsigned DynamicSubtreeNodeList::length() const { - if (m_caches.isLengthCacheValid) - return m_caches.cachedLength; + if (isLengthCacheValid()) + return cachedLength(); unsigned length = 0; Node* rootNode = this->rootNode(); @@ -43,8 +43,7 @@ unsigned DynamicSubtreeNodeList::length() const for (Node* n = rootNode->firstChild(); n; n = n->traverseNextNode(rootNode)) length += n->isElementNode() && nodeMatches(static_cast(n)); - m_caches.cachedLength = length; - m_caches.isLengthCacheValid = true; + setLengthCache(length); return length; } @@ -56,9 +55,7 @@ Node* DynamicSubtreeNodeList::itemForwardsFromCurrent(Node* start, unsigned offs for (Node* n = start; n; n = n->traverseNextNode(rootNode)) { if (n->isElementNode() && nodeMatches(static_cast(n))) { if (!remainingOffset) { - m_caches.lastItem = n; - m_caches.lastItemOffset = offset; - m_caches.isItemCacheValid = true; + setItemCache(n, offset); return n; } --remainingOffset; @@ -75,9 +72,7 @@ Node* DynamicSubtreeNodeList::itemBackwardsFromCurrent(Node* start, unsigned off for (Node* n = start; n; n = n->traversePreviousNode(rootNode)) { if (n->isElementNode() && nodeMatches(static_cast(n))) { if (!remainingOffset) { - m_caches.lastItem = n; - m_caches.lastItemOffset = offset; - m_caches.isItemCacheValid = true; + setItemCache(n, offset); return n; } ++remainingOffset; @@ -91,12 +86,12 @@ Node* DynamicSubtreeNodeList::item(unsigned offset) const { int remainingOffset = offset; Node* start = rootNode()->firstChild(); - if (m_caches.isItemCacheValid) { - if (offset == m_caches.lastItemOffset) - return m_caches.lastItem; - if (offset > m_caches.lastItemOffset || m_caches.lastItemOffset - offset < offset) { - start = m_caches.lastItem; - remainingOffset -= m_caches.lastItemOffset; + if (isItemCacheValid()) { + if (offset == cachedItemOffset()) + return cachedItem(); + if (offset > cachedItemOffset() || cachedItemOffset() - offset < offset) { + start = cachedItem(); + remainingOffset -= cachedItemOffset(); } } diff --git a/Source/WebCore/dom/DynamicNodeList.h b/Source/WebCore/dom/DynamicNodeList.h index 8b33e0d..83b2ed3 100644 --- a/Source/WebCore/dom/DynamicNodeList.h +++ b/Source/WebCore/dom/DynamicNodeList.h @@ -34,7 +34,68 @@ namespace WebCore { class Element; class Node; -class DynamicNodeList : public NodeList { +class DynamicNodeListCacheBase { +public: + enum RootType { + RootedAtNode, + RootedAtDocument, + }; + + enum InvalidationType { + AlwaysInvalidate, + DoNotInvalidateOnAttributeChange, + }; + + DynamicNodeListCacheBase(RootType rootType, InvalidationType invalidationType) + : m_rootedAtDocument(rootType == RootedAtDocument) + , m_shouldInvalidateOnAttributeChange(invalidationType == AlwaysInvalidate) + { + clearCache(); + } + +public: + ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootedAtDocument; } + ALWAYS_INLINE bool shouldInvalidateOnAttributeChange() const { return m_shouldInvalidateOnAttributeChange; } + +protected: + ALWAYS_INLINE bool isItemCacheValid() const { return m_isItemCacheValid; } + ALWAYS_INLINE Node* cachedItem() const { return m_cachedItem; } + ALWAYS_INLINE unsigned cachedItemOffset() const { return m_cachedItemOffset; } + + ALWAYS_INLINE bool isLengthCacheValid() const { return m_isLengthCacheValid; } + ALWAYS_INLINE unsigned cachedLength() const { return m_cachedLength; } + ALWAYS_INLINE void setLengthCache(unsigned length) const + { + m_cachedLength = length; + m_isLengthCacheValid = true; + } + ALWAYS_INLINE void setItemCache(Node* item, unsigned offset) const + { + m_cachedItem = item; + m_cachedItemOffset = offset; + m_isItemCacheValid = true; + } + + void clearCache() const + { + m_cachedItem = 0; + m_isLengthCacheValid = false; + m_isItemCacheValid = false; + } + +private: + mutable Node* m_cachedItem; + mutable unsigned m_cachedLength; + mutable unsigned m_cachedItemOffset; + mutable unsigned m_isLengthCacheValid : 1; + mutable unsigned m_isItemCacheValid : 1; + + // From DynamicNodeList + const unsigned m_rootedAtDocument : 1; + const unsigned m_shouldInvalidateOnAttributeChange : 1; +}; + +class DynamicNodeList : public NodeList, public DynamicNodeListCacheBase { public: enum NodeListType { ChildNodeListType, @@ -45,17 +106,9 @@ public: LabelsNodeListType, MicroDataItemListType, }; - enum RootType { - RootedAtNode, - RootedAtDocument, - }; - enum InvalidationType { - AlwaysInvalidate, - DoNotInvalidateOnAttributeChange, - }; DynamicNodeList(PassRefPtr ownerNode, RootType rootType, InvalidationType invalidationType) - : m_ownerNode(ownerNode) - , m_caches(rootType, invalidationType) + : DynamicNodeListCacheBase(rootType, invalidationType) + , m_ownerNode(ownerNode) { } virtual ~DynamicNodeList() { } @@ -66,52 +119,21 @@ public: // Other methods (not part of DOM) Node* ownerNode() const { return m_ownerNode.get(); } - bool isRootedAtDocument() const { return m_caches.rootedAtDocument; } - bool shouldInvalidateOnAttributeChange() const { return m_caches.shouldInvalidateOnAttributeChange; } - void invalidateCache() { m_caches.reset(); } + void invalidateCache() { clearCache(); } protected: Node* rootNode() const { - if (m_caches.rootedAtDocument && m_ownerNode->inDocument()) + if (isRootedAtDocument() && m_ownerNode->inDocument()) return m_ownerNode->document(); return m_ownerNode.get(); } Document* document() const { return m_ownerNode->document(); } virtual bool nodeMatches(Element*) const = 0; - struct Caches { - Caches(RootType rootType, InvalidationType invalidationType) - : rootedAtDocument(rootType == RootedAtDocument) - , shouldInvalidateOnAttributeChange(invalidationType == AlwaysInvalidate) - { - reset(); - } - - void reset() - { - lastItem = 0; - isLengthCacheValid = false; - isItemCacheValid = false; - } - - Node* lastItem; - unsigned cachedLength; - unsigned lastItemOffset; - unsigned isLengthCacheValid : 1; - unsigned isItemCacheValid : 1; - - // Following flags should belong in DynamicSubtreeNode but are here for bit-packing. - unsigned type : 4; - unsigned rootedAtDocument : 1; - unsigned shouldInvalidateOnAttributeChange : 1; - }; - - RefPtr m_ownerNode; - mutable Caches m_caches; - private: virtual bool isDynamicNodeList() const OVERRIDE { return true; } + RefPtr m_ownerNode; }; class DynamicSubtreeNodeList : public DynamicNodeList { diff --git a/Source/WebCore/html/HTMLAllCollection.cpp b/Source/WebCore/html/HTMLAllCollection.cpp index ea7ae97..6bbe9b0 100644 --- a/Source/WebCore/html/HTMLAllCollection.cpp +++ b/Source/WebCore/html/HTMLAllCollection.cpp @@ -49,15 +49,15 @@ Node* HTMLAllCollection::namedItemWithIndex(const AtomicString& name, unsigned i invalidateCacheIfNeeded(); updateNameCache(); - if (Vector* idCache = m_cache.idCache.get(name.impl())) { - if (index < idCache->size()) - return idCache->at(index); - index -= idCache->size(); + if (Vector* cache = idCache(name)) { + if (index < cache->size()) + return cache->at(index); + index -= cache->size(); } - if (Vector* nameCache = m_cache.nameCache.get(name.impl())) { - if (index < nameCache->size()) - return nameCache->at(index); + if (Vector* cache = nameCache(name)) { + if (index < cache->size()) + return cache->at(index); } return 0; diff --git a/Source/WebCore/html/HTMLCollection.cpp b/Source/WebCore/html/HTMLCollection.cpp index 97746dc..19604e1 100644 --- a/Source/WebCore/html/HTMLCollection.cpp +++ b/Source/WebCore/html/HTMLCollection.cpp @@ -71,12 +71,10 @@ static bool shouldIncludeChildren(CollectionType type) } HTMLCollection::HTMLCollection(Node* base, CollectionType type) - : m_includeChildren(shouldIncludeChildren(type)) - , m_type(type) + : HTMLCollectionCacheBase(type, shouldIncludeChildren(type)) , m_base(base) { ASSERT(m_base); - m_cache.clear(); } PassOwnPtr HTMLCollection::create(Node* base, CollectionType type) @@ -92,24 +90,23 @@ void HTMLCollection::invalidateCacheIfNeeded() const { uint64_t docversion = static_cast(m_base->document())->domTreeVersion(); - if (m_cache.version == docversion) + if (cacheTreeVersion() == docversion) return; - m_cache.clear(); - m_cache.version = docversion; + clearCache(docversion); } -void HTMLCollection::clearCache() +void HTMLCollection::invalidateCache() { - m_cache.clear(); + clearCache(static_cast(m_base->document())->domTreeVersion()); } inline bool HTMLCollection::isAcceptableElement(Element* element) const { - if (!element->isHTMLElement() && !(m_type == DocAll || m_type == NodeChildren)) + if (!element->isHTMLElement() && !(type() == DocAll || type() == NodeChildren)) return false; - switch (m_type) { + switch (type()) { case DocImages: return element->hasLocalName(imgTag); case DocScripts: @@ -166,15 +163,15 @@ static Node* nextNodeOrSibling(Node* base, Node* node, bool includeChildren) return includeChildren ? node->traverseNextNode(base) : node->traverseNextSibling(base); } -Element* HTMLCollection::itemAfter(Element* previous) const +Element* HTMLCollection::itemAfter(Node* previous) const { Node* current; if (!previous) current = m_base->firstChild(); else - current = nextNodeOrSibling(m_base, previous, m_includeChildren); + current = nextNodeOrSibling(m_base, previous, includeChildren()); - for (; current; current = nextNodeOrSibling(m_base, current, m_includeChildren)) { + for (; current; current = nextNodeOrSibling(m_base, current, includeChildren())) { if (!current->isElementNode()) continue; Element* element = static_cast(current); @@ -198,32 +195,28 @@ unsigned HTMLCollection::calcLength() const unsigned HTMLCollection::length() const { invalidateCacheIfNeeded(); - if (!m_cache.hasLength) { - m_cache.length = calcLength(); - m_cache.hasLength = true; - } - return m_cache.length; + if (!isLengthCacheValid()) + setLengthCache(calcLength()); + return cachedLength(); } Node* HTMLCollection::item(unsigned index) const { invalidateCacheIfNeeded(); - if (m_cache.current && m_cache.position == index) - return m_cache.current; - if (m_cache.hasLength && m_cache.length <= index) + if (isItemCacheValid() && cachedItemOffset() == index) + return cachedItem(); + if (isLengthCacheValid() && cachedLength() <= index) return 0; - if (!m_cache.current || m_cache.position > index) { - m_cache.current = itemAfter(0); - m_cache.position = 0; - if (!m_cache.current) + if (!isItemCacheValid() || cachedItemOffset() > index) { + setItemCache(itemAfter(0), 0); + if (!cachedItem()) return 0; } - Element* e = m_cache.current; - for (unsigned pos = m_cache.position; e && pos < index; pos++) + Node* e = cachedItem(); + for (unsigned pos = cachedItemOffset(); e && pos < index; pos++) e = itemAfter(e); - m_cache.current = e; - m_cache.position = index; - return m_cache.current; + setItemCache(e, index); + return cachedItem(); } static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element) @@ -248,7 +241,7 @@ bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const A if (!checkName) return e->getIdAttribute() == name; - if (m_type == DocAll && !nameShouldBeVisibleInDocumentAll(e)) + if (type() == DocAll && !nameShouldBeVisibleInDocumentAll(e)) return false; return e->getNameAttribute() == name && e->getIdAttribute() != name; @@ -266,8 +259,7 @@ Node* HTMLCollection::namedItem(const AtomicString& name) const unsigned i = 0; for (Element* e = itemAfter(0); e; e = itemAfter(e)) { if (checkForNameMatch(e, /* checkName */ false, name)) { - m_cache.current = e; - m_cache.position = i; + setItemCache(e, i); return e; } i++; @@ -276,8 +268,7 @@ Node* HTMLCollection::namedItem(const AtomicString& name) const i = 0; for (Element* e = itemAfter(0); e; e = itemAfter(e)) { if (checkForNameMatch(e, /* checkName */ true, name)) { - m_cache.current = e; - m_cache.position = i; + setItemCache(e, i); return e; } i++; @@ -288,7 +279,7 @@ Node* HTMLCollection::namedItem(const AtomicString& name) const void HTMLCollection::updateNameCache() const { - if (m_cache.hasNameCache) + if (hasNameCache()) return; for (Element* element = itemAfter(0); element; element = itemAfter(element)) { @@ -298,12 +289,12 @@ void HTMLCollection::updateNameCache() const const AtomicString& idAttrVal = e->getIdAttribute(); const AtomicString& nameAttrVal = e->getNameAttribute(); if (!idAttrVal.isEmpty()) - append(m_cache.idCache, idAttrVal, e); - if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (m_type != DocAll || nameShouldBeVisibleInDocumentAll(e))) - append(m_cache.nameCache, nameAttrVal, e); + appendIdCache(idAttrVal, e); + if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(e))) + appendNameCache(nameAttrVal, e); } - m_cache.hasNameCache = true; + setHasNameCache(); } bool HTMLCollection::hasNamedItem(const AtomicString& name) const @@ -314,13 +305,13 @@ bool HTMLCollection::hasNamedItem(const AtomicString& name) const invalidateCacheIfNeeded(); updateNameCache(); - if (Vector* idCache = m_cache.idCache.get(name.impl())) { - if (!idCache->isEmpty()) + if (Vector* cache = idCache(name)) { + if (!cache->isEmpty()) return true; } - if (Vector* nameCache = m_cache.nameCache.get(name.impl())) { - if (!nameCache->isEmpty()) + if (Vector* cache = nameCache(name)) { + if (!cache->isEmpty()) return true; } @@ -336,8 +327,8 @@ void HTMLCollection::namedItems(const AtomicString& name, Vector >& invalidateCacheIfNeeded(); updateNameCache(); - Vector* idResults = m_cache.idCache.get(name.impl()); - Vector* nameResults = m_cache.nameCache.get(name.impl()); + Vector* idResults = idCache(name); + Vector* nameResults = nameCache(name); for (unsigned i = 0; idResults && i < idResults->size(); ++i) result.append(idResults->at(i)); @@ -351,7 +342,7 @@ PassRefPtr HTMLCollection::tags(const String& name) return m_base->getElementsByTagName(name); } -void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element) +void HTMLCollectionCacheBase::append(NodeCacheMap& map, const AtomicString& key, Element* element) { OwnPtr >& vector = map.add(key.impl(), nullptr).iterator->second; if (!vector) diff --git a/Source/WebCore/html/HTMLCollection.h b/Source/WebCore/html/HTMLCollection.h index 10b4d8c..1d85c9d 100644 --- a/Source/WebCore/html/HTMLCollection.h +++ b/Source/WebCore/html/HTMLCollection.h @@ -25,6 +25,7 @@ #include "Node.h" #include "CollectionType.h" +#include "DynamicNodeList.h" #include #include #include @@ -36,7 +37,71 @@ class Document; class Element; class NodeList; -class HTMLCollection { +class HTMLCollectionCacheBase : public DynamicNodeListCacheBase { +public: + HTMLCollectionCacheBase(CollectionType type, bool includeChildren) + : DynamicNodeListCacheBase(RootedAtNode, AlwaysInvalidate) // These two flags are never used + , m_cachedElementsArrayOffset(0) + , m_cacheTreeVersion(0) + , m_hasNameCache(false) + , m_type(type) + , m_includeChildren(includeChildren) + { + ASSERT(m_type == type); + } + + CollectionType type() const { return static_cast(m_type); } + +protected: + void clearCache(uint64_t currentDomTreeVersion) const + { + DynamicNodeListCacheBase::clearCache(); + m_idCache.clear(); + m_nameCache.clear(); + m_cachedElementsArrayOffset = 0; + m_cacheTreeVersion = currentDomTreeVersion; + m_hasNameCache = false; + } + + using DynamicNodeListCacheBase::setItemCache; + void setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const + { + setItemCache(item, offset); + m_cachedElementsArrayOffset = elementsArrayOffset; + } + unsigned cachedElementsArrayOffset() const { return m_cachedElementsArrayOffset; } + + bool includeChildren() const { return m_includeChildren; } + uint64_t cacheTreeVersion() const { return m_cacheTreeVersion; } + + typedef HashMap > > NodeCacheMap; + Vector* idCache(const AtomicString& name) const { return m_idCache.get(name.impl()); } + Vector* nameCache(const AtomicString& name) const { return m_nameCache.get(name.impl()); } + void appendIdCache(const AtomicString& name, Element* element) const { append(m_idCache, name, element); } + void appendNameCache(const AtomicString& name, Element* element) const { append(m_nameCache, name, element); } + + bool hasNameCache() const { return m_hasNameCache; } + void setHasNameCache() const { m_hasNameCache = true; } + +private: + using DynamicNodeListCacheBase::isRootedAtDocument; + using DynamicNodeListCacheBase::shouldInvalidateOnAttributeChange; + using DynamicNodeListCacheBase::clearCache; + + static void append(NodeCacheMap&, const AtomicString&, Element*); + + mutable NodeCacheMap m_idCache; + mutable NodeCacheMap m_nameCache; + mutable unsigned m_cachedElementsArrayOffset; + mutable uint64_t m_cacheTreeVersion; + + // FIXME: Move these bit flags to DynamicNodeListCacheBase to pack them better. + mutable unsigned m_hasNameCache : 1; + const unsigned m_type : 5; // CollectionType + const unsigned m_includeChildren : 1; +}; + +class HTMLCollection : public HTMLCollectionCacheBase { public: static PassOwnPtr create(Node* base, CollectionType); virtual ~HTMLCollection(); @@ -56,58 +121,31 @@ public: bool isEmpty() const { invalidateCacheIfNeeded(); - if (m_cache.hasLength) - return !m_cache.length; - return !m_cache.current && !item(0); + if (isLengthCacheValid()) + return !cachedLength(); + if (isItemCacheValid()) + return !cachedItem(); + return !item(0); } bool hasExactlyOneItem() const { invalidateCacheIfNeeded(); - if (m_cache.hasLength) - return m_cache.length == 1; - if (m_cache.current) - return !m_cache.position && !item(1); + if (isLengthCacheValid()) + return cachedLength() == 1; + if (isItemCacheValid()) + return cachedItem() && !cachedItemOffset() && !item(1); return item(0) && !item(1); } Node* base() const { return m_base; } - CollectionType type() const { return static_cast(m_type); } - void clearCache(); + void invalidateCache(); void invalidateCacheIfNeeded() const; protected: HTMLCollection(Node* base, CollectionType); virtual void updateNameCache() const; - virtual Element* itemAfter(Element*) const; - - typedef HashMap > > NodeCacheMap; - static void append(NodeCacheMap&, const AtomicString&, Element*); - - mutable struct { - NodeCacheMap idCache; - NodeCacheMap nameCache; - uint64_t version; - Element* current; - unsigned position; - unsigned length; - int elementsArrayPosition; - bool hasLength; - bool hasNameCache; - - void clear() - { - idCache.clear(); - nameCache.clear(); - version = 0; - current = 0; - position = 0; - length = 0; - elementsArrayPosition = 0; - hasLength = false; - hasNameCache = false; - } - } m_cache; + virtual Element* itemAfter(Node*) const; private: bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const; @@ -116,9 +154,6 @@ private: bool isAcceptableElement(Element*) const; - bool m_includeChildren : 1; - unsigned m_type : 5; // CollectionType - Node* m_base; }; diff --git a/Source/WebCore/html/HTMLFormCollection.cpp b/Source/WebCore/html/HTMLFormCollection.cpp index 3aa2b8d..ad0aa16 100644 --- a/Source/WebCore/html/HTMLFormCollection.cpp +++ b/Source/WebCore/html/HTMLFormCollection.cpp @@ -84,28 +84,23 @@ Node* HTMLFormCollection::item(unsigned index) const { invalidateCacheIfNeeded(); - if (m_cache.current && m_cache.position == index) - return m_cache.current; + if (isItemCacheValid() && cachedItemOffset() == index) + return cachedItem(); - if (m_cache.hasLength && m_cache.length <= index) + if (isLengthCacheValid() && cachedLength() <= index) return 0; - if (!m_cache.current || m_cache.position > index) { - m_cache.current = 0; - m_cache.position = 0; - m_cache.elementsArrayPosition = 0; - } + if (!isItemCacheValid() || cachedItemOffset() > index) + setItemCache(0, 0, 0); const Vector& elementsArray = formControlElements(); - unsigned currentIndex = m_cache.position; - - for (unsigned i = m_cache.elementsArrayPosition; i < elementsArray.size(); i++) { + unsigned currentIndex = cachedItemOffset(); + + for (unsigned i = cachedElementsArrayOffset(); i < elementsArray.size(); i++) { if (elementsArray[i]->isEnumeratable()) { HTMLElement* element = toHTMLElement(elementsArray[i]); if (index == currentIndex) { - m_cache.position = index; - m_cache.current = element; - m_cache.elementsArrayPosition = i; + setItemCache(element, index, i); return element; } @@ -156,7 +151,7 @@ Node* HTMLFormCollection::namedItem(const AtomicString& name) const void HTMLFormCollection::updateNameCache() const { - if (m_cache.hasNameCache) + if (hasNameCache()) return; HashSet foundInputElements; @@ -170,11 +165,11 @@ void HTMLFormCollection::updateNameCache() const const AtomicString& idAttrVal = element->getIdAttribute(); const AtomicString& nameAttrVal = element->getNameAttribute(); if (!idAttrVal.isEmpty()) { - append(m_cache.idCache, idAttrVal, element); + appendIdCache(idAttrVal, element); foundInputElements.add(idAttrVal.impl()); } if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal) { - append(m_cache.nameCache, nameAttrVal, element); + appendNameCache(nameAttrVal, element); foundInputElements.add(nameAttrVal.impl()); } } @@ -187,13 +182,13 @@ void HTMLFormCollection::updateNameCache() const const AtomicString& idAttrVal = element->getIdAttribute(); const AtomicString& nameAttrVal = element->getNameAttribute(); if (!idAttrVal.isEmpty() && !foundInputElements.contains(idAttrVal.impl())) - append(m_cache.idCache, idAttrVal, element); + appendIdCache(idAttrVal, element); if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && !foundInputElements.contains(nameAttrVal.impl())) - append(m_cache.nameCache, nameAttrVal, element); + appendNameCache(nameAttrVal, element); } } - m_cache.hasNameCache = true; + setHasNameCache(); } } diff --git a/Source/WebCore/html/HTMLNameCollection.cpp b/Source/WebCore/html/HTMLNameCollection.cpp index 280c800..b05e42b 100644 --- a/Source/WebCore/html/HTMLNameCollection.cpp +++ b/Source/WebCore/html/HTMLNameCollection.cpp @@ -38,7 +38,7 @@ HTMLNameCollection::HTMLNameCollection(Document* document, CollectionType type, { } -Element* HTMLNameCollection::itemAfter(Element* previous) const +Element* HTMLNameCollection::itemAfter(Node* previous) const { ASSERT(previous != base()); diff --git a/Source/WebCore/html/HTMLNameCollection.h b/Source/WebCore/html/HTMLNameCollection.h index f844657..db0cdf1 100644 --- a/Source/WebCore/html/HTMLNameCollection.h +++ b/Source/WebCore/html/HTMLNameCollection.h @@ -41,7 +41,7 @@ public: private: HTMLNameCollection(Document*, CollectionType, const AtomicString& name); - virtual Element* itemAfter(Element*) const OVERRIDE; + virtual Element* itemAfter(Node*) const OVERRIDE; AtomicString m_name; }; diff --git a/Source/WebCore/html/HTMLSelectElement.cpp b/Source/WebCore/html/HTMLSelectElement.cpp index 3666799..9936719 100644 --- a/Source/WebCore/html/HTMLSelectElement.cpp +++ b/Source/WebCore/html/HTMLSelectElement.cpp @@ -710,7 +710,7 @@ const Vector& HTMLSelectElement::listItems() const void HTMLSelectElement::invalidateSelectedItems() { if (m_selectedOptionsCollection) - m_selectedOptionsCollection->clearCache(); + m_selectedOptionsCollection->invalidateCache(); } void HTMLSelectElement::setRecalcListItems() diff --git a/Source/WebCore/html/HTMLTableRowsCollection.cpp b/Source/WebCore/html/HTMLTableRowsCollection.cpp index df8998d..8041034 100644 --- a/Source/WebCore/html/HTMLTableRowsCollection.cpp +++ b/Source/WebCore/html/HTMLTableRowsCollection.cpp @@ -161,9 +161,9 @@ PassOwnPtr HTMLTableRowsCollection::create(HTMLTableEle return adoptPtr(new HTMLTableRowsCollection(table)); } -Element* HTMLTableRowsCollection::itemAfter(Element* previous) const +Element* HTMLTableRowsCollection::itemAfter(Node* previous) const { - ASSERT(!previous || previous->hasLocalName(trTag)); + ASSERT(!previous || (previous->isHTMLElement() && toHTMLElement(previous)->hasLocalName(trTag))); return rowAfter(static_cast(base()), static_cast(previous)); } diff --git a/Source/WebCore/html/HTMLTableRowsCollection.h b/Source/WebCore/html/HTMLTableRowsCollection.h index 11fb8d1..dfe53e5 100644 --- a/Source/WebCore/html/HTMLTableRowsCollection.h +++ b/Source/WebCore/html/HTMLTableRowsCollection.h @@ -46,7 +46,7 @@ public: private: HTMLTableRowsCollection(HTMLTableElement*); - virtual Element* itemAfter(Element*) const; + virtual Element* itemAfter(Node*) const OVERRIDE; }; } // namespace -- 2.7.4