diff options
Diffstat (limited to 'Source/WebCore/dom')
-rw-r--r-- | Source/WebCore/dom/Attr.cpp | 2 | ||||
-rw-r--r-- | Source/WebCore/dom/CharacterData.cpp | 1 | ||||
-rw-r--r-- | Source/WebCore/dom/ChildNodeList.cpp | 17 | ||||
-rw-r--r-- | Source/WebCore/dom/ChildNodeList.h | 8 | ||||
-rw-r--r-- | Source/WebCore/dom/ContainerNode.cpp | 47 | ||||
-rw-r--r-- | Source/WebCore/dom/ContainerNode.h | 11 | ||||
-rw-r--r-- | Source/WebCore/dom/Document.cpp | 11 | ||||
-rw-r--r-- | Source/WebCore/dom/Document.h | 5 | ||||
-rw-r--r-- | Source/WebCore/dom/DocumentOrderedMap.cpp | 2 | ||||
-rw-r--r-- | Source/WebCore/dom/DynamicNodeList.cpp | 46 | ||||
-rw-r--r-- | Source/WebCore/dom/DynamicNodeList.h | 8 | ||||
-rw-r--r-- | Source/WebCore/dom/Node.cpp | 253 | ||||
-rw-r--r-- | Source/WebCore/dom/Node.h | 79 | ||||
-rw-r--r-- | Source/WebCore/dom/NodeRareData.h | 22 | ||||
-rw-r--r-- | Source/WebCore/dom/SelectorNodeList.cpp | 16 | ||||
-rw-r--r-- | Source/WebCore/dom/TagNodeList.cpp | 35 | ||||
-rw-r--r-- | Source/WebCore/dom/TagNodeList.h | 49 | ||||
-rw-r--r-- | Source/WebCore/dom/Text.cpp | 2 | ||||
-rw-r--r-- | Source/WebCore/dom/Text.h | 5 | ||||
-rw-r--r-- | Source/WebCore/dom/TreeScope.cpp | 4 |
20 files changed, 464 insertions, 159 deletions
diff --git a/Source/WebCore/dom/Attr.cpp b/Source/WebCore/dom/Attr.cpp index e3ae348..346a819 100644 --- a/Source/WebCore/dom/Attr.cpp +++ b/Source/WebCore/dom/Attr.cpp @@ -69,6 +69,8 @@ void Attr::createTextChild() textNode->setParent(this); setFirstChild(textNode.get()); setLastChild(textNode.get()); + textNode->updateNextNode(); + textNode->updatePreviousNode(); } } diff --git a/Source/WebCore/dom/CharacterData.cpp b/Source/WebCore/dom/CharacterData.cpp index b4af02d..78f57d0 100644 --- a/Source/WebCore/dom/CharacterData.cpp +++ b/Source/WebCore/dom/CharacterData.cpp @@ -189,6 +189,7 @@ void CharacterData::updateRenderer(unsigned offsetOfReplacedData, unsigned lengt void CharacterData::dispatchModifiedEvent(StringImpl* oldData) { + updatePrevNextNodesInSubtree(); if (parentNode()) parentNode()->childrenChanged(); if (document()->hasListenerType(Document::DOMCHARACTERDATAMODIFIED_LISTENER)) diff --git a/Source/WebCore/dom/ChildNodeList.cpp b/Source/WebCore/dom/ChildNodeList.cpp index 3328c7c..253537c 100644 --- a/Source/WebCore/dom/ChildNodeList.cpp +++ b/Source/WebCore/dom/ChildNodeList.cpp @@ -27,19 +27,27 @@ namespace WebCore { -ChildNodeList::ChildNodeList(PassRefPtr<Node> rootNode, DynamicNodeList::Caches* info) - : DynamicNodeList(rootNode, info) +ChildNodeList::ChildNodeList(PassRefPtr<Node> rootNode) + : DynamicNodeList(rootNode) { } +ChildNodeList::~ChildNodeList() +{ + m_rootNode->removeCachedChildNodeList(this); +} + unsigned ChildNodeList::length() const { if (m_caches->isLengthCacheValid) return m_caches->cachedLength; unsigned len = 0; - for (Node* n = m_rootNode->firstChild(); n; n = n->nextSibling()) + Vector<Node* >& cachedNodes = m_caches->cachedNodes; + for (Node* n = m_rootNode->firstChild(); n; n = n->nextSibling()) { + cachedNodes.append(n); len++; + } m_caches->cachedLength = len; m_caches->isLengthCacheValid = true; @@ -49,6 +57,9 @@ unsigned ChildNodeList::length() const Node* ChildNodeList::item(unsigned index) const { + if (m_caches->isLengthCacheValid && index < m_caches->cachedLength) + return m_caches->cachedNodes[index]; + unsigned int pos = 0; Node* n = m_rootNode->firstChild(); diff --git a/Source/WebCore/dom/ChildNodeList.h b/Source/WebCore/dom/ChildNodeList.h index f38106d..df3d67b 100644 --- a/Source/WebCore/dom/ChildNodeList.h +++ b/Source/WebCore/dom/ChildNodeList.h @@ -31,16 +31,18 @@ namespace WebCore { class ChildNodeList : public DynamicNodeList { public: - static PassRefPtr<ChildNodeList> create(PassRefPtr<Node> rootNode, Caches* caches) + static PassRefPtr<ChildNodeList> create(PassRefPtr<Node> rootNode) { - return adoptRef(new ChildNodeList(rootNode, caches)); + return adoptRef(new ChildNodeList(rootNode)); } + virtual ~ChildNodeList(); + virtual unsigned length() const; virtual Node* item(unsigned index) const; protected: - ChildNodeList(PassRefPtr<Node> rootNode, Caches*); + ChildNodeList(PassRefPtr<Node> rootNode); virtual bool nodeMatches(Element*) const; }; diff --git a/Source/WebCore/dom/ContainerNode.cpp b/Source/WebCore/dom/ContainerNode.cpp index 2d22fa9..5574aa5 100644 --- a/Source/WebCore/dom/ContainerNode.cpp +++ b/Source/WebCore/dom/ContainerNode.cpp @@ -3,6 +3,7 @@ * (C) 1999 Antti Koivisto (koivisto@kde.org) * (C) 2001 Dirk Mueller (mueller@kde.org) * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved. + * Copyright (C) 2012 The Linux Foundation All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -74,6 +75,7 @@ static void collectTargetNodes(Node* node, NodeVector& nodes) void ContainerNode::removeAllChildren() { removeAllChildrenInContainer<Node, ContainerNode>(this); + updateNextNode(); } void ContainerNode::takeAllChildrenFrom(ContainerNode* oldParent) @@ -208,6 +210,8 @@ void ContainerNode::insertBeforeCommon(Node* nextChild, Node* newChild) newChild->setParent(this); newChild->setPreviousSibling(prev); newChild->setNextSibling(nextChild); + newChild->updatePreviousNode(); + newChild->lastDescendantNode(true)->updateNextNode(); allowEventDispatch(); } @@ -335,6 +339,9 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce child->setParent(this); child->setPreviousSibling(prev.get()); child->setNextSibling(next); + child->updatePreviousNode(); + child->lastDescendantNode(true)->updateNextNode(); + allowEventDispatch(); childrenChanged(false, prev.get(), next, 1); @@ -362,12 +369,13 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce void ContainerNode::willRemove() { - Vector<RefPtr<Node>, 10> nodes; - nodes.reserveInitialCapacity(childNodeCount()); - for (Node* n = m_lastChild; n; n = n->previousSibling()) - nodes.append(n); - for (; nodes.size(); nodes.removeLast()) - nodes.last().get()->willRemove(); + Node* next; + Node* child = m_firstChild; + while (child) { + next = child->nextSibling(); + child->willRemove(); + child = next; + } Node::willRemove(); } @@ -468,6 +476,8 @@ void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node* ol if (oldChild->attached()) oldChild->detach(); + Node* previousNode = oldChild->traversePreviousNodeFastPath(); + if (nextChild) nextChild->setPreviousSibling(previousChild); if (previousChild) @@ -480,6 +490,10 @@ void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node* ol oldChild->setPreviousSibling(0); oldChild->setNextSibling(0); oldChild->setParent(0); + oldChild->setPreviousNode(0); + oldChild->lastDescendantNode(true)->setNextNode(0); + if (previousNode) + previousNode->updateNextNode(); allowEventDispatch(); } @@ -530,6 +544,8 @@ void ContainerNode::removeChildren() n->setPreviousSibling(0); n->setNextSibling(0); n->setParent(0); + n->lastDescendantNode(true)->setNextNode(0); + n->setPreviousNode(0); m_firstChild = next; if (n == m_lastChild) @@ -552,6 +568,7 @@ void ContainerNode::removeChildren() removedChild->detach(); } + updateNextNode(); allowEventDispatch(); // Dispatch a single post-removal mutation event denoting a modified subtree. @@ -621,6 +638,8 @@ bool ContainerNode::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec, bo } else m_firstChild = child; m_lastChild = child; + child->updatePreviousNode(); + child->lastDescendantNode(true)->updateNextNode(); allowEventDispatch(); // Send notification about the children change. @@ -658,6 +677,10 @@ void ContainerNode::parserAddChild(PassRefPtr<Node> newChild) Node* last = m_lastChild; // FIXME: This method should take a PassRefPtr. appendChildToContainer<Node, ContainerNode>(newChild.get(), this); + if (last) + last->updateNextNode(); + newChild->updatePreviousNode(); + newChild->lastDescendantNode(true)->updateNextNode(); allowEventDispatch(); // FIXME: Why doesn't this use notifyChildInserted(newChild) instead? @@ -1070,8 +1093,12 @@ static void dispatchChildInsertionEvents(Node* child) // dispatch the DOMNodeInsertedIntoDocument event to all descendants if (c->inDocument() && document->hasListenerType(Document::DOMNODEINSERTEDINTODOCUMENT_LISTENER)) { - for (; c; c = c->traverseNextNode(child)) + Node* last = child->lastDescendantNode(true); + for (; c; c = c->traverseNextNodeFastPath()) { c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeInsertedIntoDocumentEvent, false)); + if (last == c) + break; + } } } @@ -1092,8 +1119,12 @@ static void dispatchChildRemovalEvents(Node* child) // dispatch the DOMNodeRemovedFromDocument event to all descendants if (c->inDocument() && document->hasListenerType(Document::DOMNODEREMOVEDFROMDOCUMENT_LISTENER)) { - for (; c; c = c->traverseNextNode(child)) + Node* last = c->lastDescendantNode(true); + for (; c; c = c->traverseNextNodeFastPath()) { c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedFromDocumentEvent, false)); + if (last == c) + break; + } } } diff --git a/Source/WebCore/dom/ContainerNode.h b/Source/WebCore/dom/ContainerNode.h index 76eb1bd..ee8252e 100644 --- a/Source/WebCore/dom/ContainerNode.h +++ b/Source/WebCore/dom/ContainerNode.h @@ -170,6 +170,17 @@ inline Node* Node::lastChild() const return toContainerNode(this)->lastChild(); } +inline RenderObject* Node::previousRenderer() +{ + // FIXME: We should have the same O(N^2) avoidance as nextRenderer does + // however, when I tried adding it, several tests failed. + for (Node* n = previousSibling(); n; n = n->previousSibling()) { + if (n->renderer()) + return n->renderer(); + } + return 0; +} + } // namespace WebCore #endif // ContainerNode_h diff --git a/Source/WebCore/dom/Document.cpp b/Source/WebCore/dom/Document.cpp index e338c8e..60ecdb9 100644 --- a/Source/WebCore/dom/Document.cpp +++ b/Source/WebCore/dom/Document.cpp @@ -7,7 +7,7 @@ * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/) * Copyright (C) 2008, 2009 Google Inc. All rights reserved. * Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies) - * Copyright (c) 2011, 2012 Code Aurora Forum. All rights reserved + * Copyright (c) 2011, 2012 The Linux Foundation All rights reserved * Copyright (C) 2011, 2012 Sony Ericsson Mobile Communications AB * Copyright (C) 2012 Sony Mobile Communcations AB * @@ -1816,7 +1816,7 @@ void Document::removeAllEventListeners() if (DOMWindow* domWindow = this->domWindow()) domWindow->removeAllEventListeners(); - for (Node* node = firstChild(); node; node = node->traverseNextNode()) + for (Node* node = firstChild(); node; node = node->traverseNextNodeFastPath()) node->removeAllEventListeners(); } @@ -3848,11 +3848,12 @@ static inline bool isValidNameASCII(const UChar* characters, unsigned length) bool Document::isValidName(const String& name) { - unsigned length = name.length(); - if (!length) + if (name.isEmpty()) return false; - const UChar* characters = name.characters(); + StringImpl* impl = name.impl(); + const UChar* characters = impl->characters(); + unsigned length = impl->length(); return isValidNameASCII(characters, length) || isValidNameNonASCII(characters, length); } diff --git a/Source/WebCore/dom/Document.h b/Source/WebCore/dom/Document.h index 685e3b7..44f3f93 100644 --- a/Source/WebCore/dom/Document.h +++ b/Source/WebCore/dom/Document.h @@ -6,7 +6,7 @@ * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/) * Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies) - * Copyright (c) 2011, 2012 Code Aurora Forum. All rights reserved + * Copyright (c) 2011, 2012 The Linux Foundation All rights reserved * Copyright (C) 2011, 2012 Sony Ericsson Mobile Communications AB * Copyright (C) 2012 Sony Mobile Communcations AB * @@ -1429,8 +1429,11 @@ inline Node::Node(Document* document, ConstructionType type) : m_document(document) , m_previous(0) , m_next(0) + , m_prefetch(0) , m_renderer(0) , m_nodeFlags(type) + , m_previousNode(0) + , m_nextNode(0) { if (m_document) m_document->guardRef(); diff --git a/Source/WebCore/dom/DocumentOrderedMap.cpp b/Source/WebCore/dom/DocumentOrderedMap.cpp index 47268c4..73a0843 100644 --- a/Source/WebCore/dom/DocumentOrderedMap.cpp +++ b/Source/WebCore/dom/DocumentOrderedMap.cpp @@ -117,7 +117,7 @@ inline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope* if (m_duplicateCounts.contains(key)) { // We know there's at least one node that matches; iterate to find the first one. - for (Node* node = scope->firstChild(); node; node = node->traverseNextNode()) { + for (Node* node = scope->firstChild(); node; node = node->traverseNextNodeFastPath()) { if (!node->isElementNode()) continue; element = static_cast<Element*>(node); diff --git a/Source/WebCore/dom/DynamicNodeList.cpp b/Source/WebCore/dom/DynamicNodeList.cpp index 23664e8..bba1678 100644 --- a/Source/WebCore/dom/DynamicNodeList.cpp +++ b/Source/WebCore/dom/DynamicNodeList.cpp @@ -3,6 +3,7 @@ * (C) 1999 Antti Koivisto (koivisto@kde.org) * (C) 2001 Dirk Mueller (mueller@kde.org) * Copyright (C) 2004, 2006, 2007, 2008, 2010 Apple Inc. All rights reserved. + * Copyright (C) 2012 The Linux Foundation All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -56,8 +57,18 @@ unsigned DynamicNodeList::length() const unsigned length = 0; - for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNode(m_rootNode.get())) - length += n->isElementNode() && nodeMatches(static_cast<Element*>(n)); + Node* lastNode = m_rootNode->lastDescendantNode(); + Vector<Node* >& cachedNodes = m_caches->cachedNodes; + for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNodeFastPath()) { + if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) { + if (length >= cachedNodes.size()) + cachedNodes.resize(length + 1); + cachedNodes.data()[length] = n; + length ++; + } + if (n == lastNode) + break; + } m_caches->cachedLength = length; m_caches->isLengthCacheValid = true; @@ -68,7 +79,9 @@ unsigned DynamicNodeList::length() const Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const { ASSERT(remainingOffset >= 0); - for (Node* n = start; n; n = n->traverseNextNode(m_rootNode.get())) { + if (!m_caches->lastDecendantOfRoot) + m_caches->lastDecendantOfRoot = m_rootNode->lastDescendantNode(); + for (Node* n = start; n; n = n->traverseNextNodeFastPath()) { if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) { if (!remainingOffset) { m_caches->lastItem = n; @@ -78,6 +91,8 @@ Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int } --remainingOffset; } + if (n == m_caches->lastDecendantOfRoot) + break; } return 0; // no matching node in this subtree @@ -103,6 +118,14 @@ Node* DynamicNodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, in Node* DynamicNodeList::item(unsigned offset) const { + Node* result; + Vector<Node* >& cachedNodes = m_caches->cachedNodes; + if (offset < cachedNodes.size()) { + result = cachedNodes[offset]; + if (result) + return result; + } + int remainingOffset = offset; Node* start = m_rootNode->firstChild(); if (m_caches->isItemCacheValid) { @@ -115,8 +138,16 @@ Node* DynamicNodeList::item(unsigned offset) const } if (remainingOffset < 0) - return itemBackwardsFromCurrent(start, offset, remainingOffset); - return itemForwardsFromCurrent(start, offset, remainingOffset); + result = itemBackwardsFromCurrent(start, offset, remainingOffset); + else + result = itemForwardsFromCurrent(start, offset, remainingOffset); + + if (result) { + if (offset >= cachedNodes.size()) + cachedNodes.resize(offset + 1); + cachedNodes.data()[offset] = result; + } + return result; } Node* DynamicNodeList::itemWithName(const AtomicString& elementId) const @@ -159,6 +190,7 @@ void DynamicNodeList::invalidateCache() DynamicNodeList::Caches::Caches() : lastItem(0) + , lastDecendantOfRoot(0) , isLengthCacheValid(false) , isItemCacheValid(false) { @@ -172,8 +204,10 @@ PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create() void DynamicNodeList::Caches::reset() { lastItem = 0; + lastDecendantOfRoot = 0; isLengthCacheValid = false; - isItemCacheValid = false; + isItemCacheValid = false; + cachedNodes.clear(); } } // namespace WebCore diff --git a/Source/WebCore/dom/DynamicNodeList.h b/Source/WebCore/dom/DynamicNodeList.h index 9c8f3cc..c8b6ca2 100644 --- a/Source/WebCore/dom/DynamicNodeList.h +++ b/Source/WebCore/dom/DynamicNodeList.h @@ -28,6 +28,12 @@ #include <wtf/RefCounted.h> #include <wtf/Forward.h> #include <wtf/RefPtr.h> +#include <wtf/Vector.h> + +namespace WTF { + // Properties in Vector can be initialized with memset and moved using memcpy. + template<> struct VectorTraits<WebCore::Node*> : SimpleClassVectorTraits { }; +} namespace WebCore { @@ -42,9 +48,11 @@ namespace WebCore { unsigned cachedLength; Node* lastItem; + Node* lastDecendantOfRoot; unsigned lastItemOffset; bool isLengthCacheValid : 1; bool isItemCacheValid : 1; + Vector<Node* > cachedNodes; protected: Caches(); }; diff --git a/Source/WebCore/dom/Node.cpp b/Source/WebCore/dom/Node.cpp index da4312c..1e56278 100644 --- a/Source/WebCore/dom/Node.cpp +++ b/Source/WebCore/dom/Node.cpp @@ -5,6 +5,7 @@ * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies) * Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/) + * Copyright (C) 2012 The Linux Foundation All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -130,6 +131,8 @@ namespace WebCore { using namespace HTMLNames; +const int Node::cPrefetchTargetDepth = 7; + bool Node::isSupported(const String& feature, const String& version) { return DOMImplementation::hasFeature(feature, version); @@ -409,6 +412,8 @@ Node::~Node() m_previous->setNextSibling(0); if (m_next) m_next->setPreviousSibling(0); + m_nextNode = 0; + m_previousNode = 0; if (m_document) m_document->guardDeref(); @@ -517,9 +522,12 @@ void Node::setTreeScopeRecursively(TreeScope* newTreeScope) if (currentDocument && currentDocument != newDocument) currentDocument->incDOMTreeVersion(); - for (Node* node = this; node; node = node->traverseNextNode(this)) { + Node* last = this->lastDescendantNode(true); + for (Node* node = this; node; node = node->traverseNextNodeFastPath()) { node->setTreeScope(newTreeScope); // FIXME: Once shadow scopes are landed, update parent scope, etc. + if (last == node) + break; } } @@ -548,18 +556,22 @@ NodeRareData* Node::createRareData() Element* Node::shadowHost() const { - return toElement(getFlag(IsShadowRootFlag) ? parent() : 0); + return toElement(isShadowRoot() ? parent() : 0); } void Node::setShadowHost(Element* host) { ASSERT(!parentNode() && !isSVGShadowRoot()); if (host) - setFlag(IsShadowRootFlag); + setFlag(IsShadowRootOrSVGShadowRootFlag); else - clearFlag(IsShadowRootFlag); + clearFlag(IsShadowRootOrSVGShadowRootFlag); setParent(host); + updatePreviousNode(); + lastDescendantNode(true)->updateNextNode(); + if (host) + host->updateNextNode(); } InputElement* Node::toInputElement() @@ -607,14 +619,13 @@ void Node::setNodeValue(const String& /*nodeValue*/, ExceptionCode& ec) PassRefPtr<NodeList> Node::childNodes() { - NodeRareData* data = ensureRareData(); - if (!data->nodeLists()) { - data->setNodeLists(NodeListsNodeData::create()); - if (document()) - document()->addNodeListCache(); - } + NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this); + if (data->m_childNodeListCache) + return PassRefPtr<ChildNodeList>(data->m_childNodeListCache); - return ChildNodeList::create(this, data->nodeLists()->m_childNodeListCaches.get()); + RefPtr<ChildNodeList> childNodeList = ChildNodeList::create(this); + data->m_childNodeListCache = childNodeList.get(); + return childNodeList.release(); } Node *Node::lastDescendant() const @@ -862,12 +873,15 @@ void Node::setDocumentRecursively(Document* newDocument) { ASSERT(document() != newDocument); - for (Node* node = this; node; node = node->traverseNextNode(this)) { + Node* last = this->lastDescendantNode(true); + for (Node* node = this; node; node = node->traverseNextNodeFastPath()) { node->setDocument(newDocument); - if (!node->isElementNode()) - continue; - if (Node* shadow = shadowRoot(node)) - shadow->setDocumentRecursively(newDocument); + if (node->isElementNode()) { + if (Node* shadow = shadowRoot(node)) + shadow->setDocumentRecursively(newDocument); + } + if (node == last) + break; } } @@ -911,12 +925,15 @@ void Node::setNeedsStyleRecalc(StyleChangeType changeType) void Node::lazyAttach(ShouldSetAttached shouldSetAttached) { - for (Node* n = this; n; n = n->traverseNextNode(this)) { + Node* last = this->lastDescendantNode(true); + for (Node* n = this; n; n = n->traverseNextNodeFastPath()) { if (n->firstChild()) n->setChildNeedsStyleRecalc(); n->setStyleChange(FullStyleChange); if (shouldSetAttached == SetAttached) n->setAttached(); + if (n == last) + break; } markAncestorsWithChildNeedsStyleRecalc(); } @@ -1092,7 +1109,7 @@ void Node::removeCachedNameNodeList(NameNodeList* list, const String& nodeName) data->m_nameNodeListCache.remove(nodeName); } -void Node::removeCachedTagNodeList(TagNodeList* list, const QualifiedName& name) +void Node::removeCachedTagNodeList(TagNodeList* list, const AtomicString& name) { ASSERT(rareData()); ASSERT(rareData()->nodeLists()); @@ -1103,6 +1120,17 @@ void Node::removeCachedTagNodeList(TagNodeList* list, const QualifiedName& name) data->m_tagNodeListCache.remove(name.impl()); } +void Node::removeCachedTagNodeListNS(TagNodeListNS* list, const QualifiedName& name) +{ + ASSERT(rareData()); + ASSERT(rareData()->nodeLists()); + ASSERT_UNUSED(list, list->hasOwnCaches()); + + NodeListsNodeData* data = rareData()->nodeLists(); + ASSERT_UNUSED(list, list == data->m_tagNodeListCacheNS.get(name.impl())); + data->m_tagNodeListCacheNS.remove(name.impl()); +} + void Node::removeCachedLabelsNodeList(DynamicNodeList* list) { ASSERT(rareData()); @@ -1113,14 +1141,27 @@ void Node::removeCachedLabelsNodeList(DynamicNodeList* list) data->m_labelsNodeListCache = 0; } +void Node::removeCachedChildNodeList(DynamicNodeList* list) +{ + ASSERT(rareData()); + ASSERT(rareData()->nodeLists()); + ASSERT_UNUSED(list, list->hasOwnCaches()); + + NodeListsNodeData* data = rareData()->nodeLists(); + data->m_childNodeListCache = 0; +} + Node* Node::traverseNextNode(const Node* stayWithin) const { - if (firstChild()) - return firstChild(); + prefetchTarget(); + Node* fc = firstChild(); + if (fc) + return fc; if (this == stayWithin) return 0; - if (nextSibling()) - return nextSibling(); + Node* ns = nextSibling(); + if (ns) + return ns; const Node *n = this; while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin)) n = n->parentNode(); @@ -1129,15 +1170,54 @@ Node* Node::traverseNextNode(const Node* stayWithin) const return 0; } +Node* Node::lastDescendantNode(bool includeThis) const +{ + Node* n = lastChild(); + if (!n && includeThis) + return const_cast<Node*>(this); + + Node* p = n; + while(n) { + p = n; + n = n->lastChild(); + } + return p; +} + +void Node::updatePrevNextNodesInSubtree() +{ + Node* n = firstChild(); + Node* next; + while(n) { + next = n->traverseNextNode(this); + if (next) { + n->setNextNode(next); + next->setPreviousNode(n); + } else { + next = n->traverseNextNode(); + n->setNextNode(next); + if (next) + next->setPreviousNode(n); + break; + } + n = next; + } + updateNextNode(); +} + Node* Node::traverseNextSibling(const Node* stayWithin) const { if (this == stayWithin) return 0; - if (nextSibling()) - return nextSibling(); + prefetchTarget(); + Node* ns = nextSibling(); + if (ns) + return ns; const Node *n = this; - while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin)) + while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin)) { + n->prefetchTarget(); n = n->parentNode(); + } if (n) return n->nextSibling(); return 0; @@ -1157,10 +1237,11 @@ Node* Node::traversePreviousNode(const Node* stayWithin) const { if (this == stayWithin) return 0; - if (previousSibling()) { - Node *n = previousSibling(); - while (n->lastChild()) - n = n->lastChild(); + Node *n = previousSibling(); + if (n) { + Node* lastChild; + while ((lastChild = n->lastChild())) + n = lastChild; return n; } return parentNode(); @@ -1168,12 +1249,12 @@ Node* Node::traversePreviousNode(const Node* stayWithin) const Node* Node::traversePreviousNodePostOrder(const Node* stayWithin) const { - if (lastChild()) - return lastChild(); + if (Node* lc = lastChild()) + return lc; if (this == stayWithin) return 0; - if (previousSibling()) - return previousSibling(); + if (Node* ps = previousSibling()) + return ps; const Node *n = this; while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin)) n = n->parentNode(); @@ -1186,8 +1267,8 @@ Node* Node::traversePreviousSiblingPostOrder(const Node* stayWithin) const { if (this == stayWithin) return 0; - if (previousSibling()) - return previousSibling(); + if (Node* ps = previousSibling()) + return ps; const Node *n = this; while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin)) n = n->parentNode(); @@ -1333,14 +1414,20 @@ void Node::attach() // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached). // If this node got a renderer it may be the previousRenderer() of sibling text nodes and thus affect the // result of Text::rendererIsNeeded() for those nodes. - if (renderer()) { + RenderObject* renderer = this->renderer(); + if (renderer) { for (Node* next = nextSibling(); next; next = next->nextSibling()) { if (next->renderer()) break; if (!next->attached()) break; // Assume this means none of the following siblings are attached. - if (next->isTextNode()) + if (next->isTextNode()) { + static_cast<Text*>(next)->setPreviousRenderer(renderer); next->createRendererIfNeeded(); + if (next->renderer()) + renderer = next->renderer(); + static_cast<Text*>(next)->setPreviousRenderer(0); + } } } @@ -1366,23 +1453,7 @@ void Node::detach() if (inActiveChain()) doc->activeChainNodeDetached(this); - clearFlag(IsActiveFlag); - clearFlag(IsHoveredFlag); - clearFlag(InActiveChainFlag); - clearFlag(IsAttachedFlag); - - clearFlag(InDetachFlag); -} - -RenderObject* Node::previousRenderer() -{ - // FIXME: We should have the same O(N^2) avoidance as nextRenderer does - // however, when I tried adding it, several tests failed. - for (Node* n = previousSibling(); n; n = n->previousSibling()) { - if (n->renderer()) - return n->renderer(); - } - return 0; + clearFlag(NodeDetachClearFlags); } RenderObject* Node::nextRenderer() @@ -1697,44 +1768,45 @@ bool Node::inSameContainingBlockFlowElement(Node *n) PassRefPtr<NodeList> Node::getElementsByTagName(const AtomicString& name) { - return getElementsByTagNameNS(starAtom, name); + if (name.isNull()) + return 0; + + NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this); + + AtomicString localNameAtom = document()->isHTMLDocument() ? name.lower() : name; + + pair<NodeListsNodeData::TagNodeListCache::iterator, bool> result = data->m_tagNodeListCache.add(localNameAtom.impl(), 0); + if (!result.second) + return PassRefPtr<TagNodeList>(result.first->second); + + RefPtr<TagNodeList> list = TagNodeList::create(this, localNameAtom); + result.first->second = list.get(); + return list.release(); } PassRefPtr<NodeList> Node::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName) { if (localName.isNull()) return 0; - - NodeRareData* data = ensureRareData(); - if (!data->nodeLists()) { - data->setNodeLists(NodeListsNodeData::create()); - document()->addNodeListCache(); - } - String name = localName; - if (document()->isHTMLDocument()) - name = localName.lower(); - - AtomicString localNameAtom = name; - - pair<NodeListsNodeData::TagNodeListCache::iterator, bool> result = data->nodeLists()->m_tagNodeListCache.add(QualifiedName(nullAtom, localNameAtom, namespaceURI).impl(), 0); + NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this); + + AtomicString localNameAtom = document()->isHTMLDocument() ? localName.lower() : localName; + + pair<NodeListsNodeData::TagNodeListCacheNS::iterator, bool> result = data->m_tagNodeListCacheNS.add(QualifiedName(nullAtom, localNameAtom, namespaceURI).impl(), 0); if (!result.second) - return PassRefPtr<TagNodeList>(result.first->second); - - RefPtr<TagNodeList> list = TagNodeList::create(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localNameAtom); + return PassRefPtr<TagNodeListNS>(result.first->second); + + RefPtr<TagNodeListNS> list = TagNodeListNS::create(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localNameAtom); result.first->second = list.get(); return list.release(); } PassRefPtr<NodeList> Node::getElementsByName(const String& elementName) { - NodeRareData* data = ensureRareData(); - if (!data->nodeLists()) { - data->setNodeLists(NodeListsNodeData::create()); - document()->addNodeListCache(); - } + NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this); - pair<NodeListsNodeData::NameNodeListCache::iterator, bool> result = data->nodeLists()->m_nameNodeListCache.add(elementName, 0); + pair<NodeListsNodeData::NameNodeListCache::iterator, bool> result = data->m_nameNodeListCache.add(elementName, 0); if (!result.second) return PassRefPtr<NodeList>(result.first->second); @@ -1745,13 +1817,9 @@ PassRefPtr<NodeList> Node::getElementsByName(const String& elementName) PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames) { - NodeRareData* data = ensureRareData(); - if (!data->nodeLists()) { - data->setNodeLists(NodeListsNodeData::create()); - document()->addNodeListCache(); - } + NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this); - pair<NodeListsNodeData::ClassNodeListCache::iterator, bool> result = data->nodeLists()->m_classNodeListCache.add(classNames, 0); + pair<NodeListsNodeData::ClassNodeListCache::iterator, bool> result = data->m_classNodeListCache.add(classNames, 0); if (!result.second) return PassRefPtr<NodeList>(result.first->second); @@ -1794,7 +1862,8 @@ PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode& } // FIXME: We can speed this up by implementing caching similar to the one use by getElementById - for (Node* n = firstChild(); n; n = n->traverseNextNode(this)) { + Node* last = lastDescendantNode(); + for (Node* n = firstChild(); n; n = n->traverseNextNodeFastPath()) { if (n->isElementNode()) { Element* element = static_cast<Element*>(n); for (CSSSelector* selector = querySelectorList.first(); selector; selector = CSSSelectorList::next(selector)) { @@ -1802,6 +1871,8 @@ PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode& return element; } } + if (n == last) + break; } return 0; @@ -2425,10 +2496,14 @@ void Node::formatForDebugger(char* buffer, unsigned length) const void NodeListsNodeData::invalidateCaches() { - m_childNodeListCaches->reset(); + if (m_childNodeListCache) + m_childNodeListCache->invalidateCache(); if (m_labelsNodeListCache) m_labelsNodeListCache->invalidateCache(); + TagNodeListCacheNS::const_iterator tagCacheEndNS = m_tagNodeListCacheNS.end(); + for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEndNS; ++it) + it->second->invalidateCache(); TagNodeListCache::const_iterator tagCacheEnd = m_tagNodeListCache.end(); for (TagNodeListCache::const_iterator it = m_tagNodeListCache.begin(); it != tagCacheEnd; ++it) it->second->invalidateCache(); @@ -2453,9 +2528,15 @@ bool NodeListsNodeData::isEmpty() const if (!m_listsWithCaches.isEmpty()) return false; - if (m_childNodeListCaches->refCount()) + if (m_childNodeListCache) return false; + TagNodeListCacheNS::const_iterator tagCacheEndNS = m_tagNodeListCacheNS.end(); + for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEndNS; ++it) { + if (it->second->refCount()) + return false; + } + TagNodeListCache::const_iterator tagCacheEnd = m_tagNodeListCache.end(); for (TagNodeListCache::const_iterator it = m_tagNodeListCache.begin(); it != tagCacheEnd; ++it) { if (it->second->refCount()) diff --git a/Source/WebCore/dom/Node.h b/Source/WebCore/dom/Node.h index 76355c3..886dd88 100644 --- a/Source/WebCore/dom/Node.h +++ b/Source/WebCore/dom/Node.h @@ -4,6 +4,7 @@ * (C) 2001 Dirk Mueller (mueller@kde.org) * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved. * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/) + * Copyright (C) 2012 The Linux Foundation All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -75,6 +76,7 @@ class RenderStyle; class SVGUseElement; #endif class TagNodeList; +class TagNodeListNS; class TreeScope; typedef int ExceptionCode; @@ -121,6 +123,8 @@ public: DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC = 0x20, }; + static const int cPrefetchTargetDepth; + static bool isSupported(const String& feature, const String& version); static void startIgnoringLeaks(); @@ -143,8 +147,8 @@ public: virtual NodeType nodeType() const = 0; ContainerNode* parentNode() const; Element* parentElement() const; - Node* previousSibling() const { return m_previous; } - Node* nextSibling() const { return m_next; } + ALWAYS_INLINE Node* previousSibling() const { return m_previous; } + ALWAYS_INLINE Node* nextSibling() const { return m_next; } PassRefPtr<NodeList> childNodes(); Node* firstChild() const; Node* lastChild() const; @@ -187,14 +191,14 @@ public: // Other methods (not part of DOM) - bool isElementNode() const { return getFlag(IsElementFlag); } - bool isContainerNode() const { return getFlag(IsContainerFlag); } + ALWAYS_INLINE bool isElementNode() const { return getFlag(IsElementFlag); } + ALWAYS_INLINE bool isContainerNode() const { return getFlag(IsContainerFlag); } bool isTextNode() const { return getFlag(IsTextFlag); } bool isHTMLElement() const { return getFlag(IsHTMLFlag); } - bool isSVGElement() const { return getFlag(IsSVGFlag); } - virtual bool isSVGShadowRoot() const { return false; } + ALWAYS_INLINE bool isSVGElement() const { return getFlag(IsSVGFlag); } + ALWAYS_INLINE bool isSVGShadowRoot() const { return getFlag(IsShadowRootOrSVGShadowRootFlag) && isSVGElement(); } #if ENABLE(SVG) SVGUseElement* svgShadowHost() const; #endif @@ -213,7 +217,7 @@ public: bool isCommentNode() const { return getFlag(IsCommentFlag); } virtual bool isCharacterDataNode() const { return false; } bool isDocumentNode() const; - bool isShadowRoot() const { return getFlag(IsShadowRootFlag); } + bool isShadowRoot() const { return getFlag(IsShadowRootOrSVGShadowRootFlag) && !isSVGElement(); } // FIXME: Remove this when all shadow roots are ShadowRoots. virtual bool isShadowBoundary() const { return false; } virtual bool canHaveLightChildRendererWithShadow() const { return false; } @@ -240,7 +244,26 @@ public: // These low-level calls give the caller responsibility for maintaining the integrity of the tree. void setPreviousSibling(Node* previous) { m_previous = previous; } - void setNextSibling(Node* next) { m_next = next; } + ALWAYS_INLINE void updatePrefetchTarget() { + if (m_next) { + int skew; + Node* from = this; + Node* n = from->traversePreviousNodePostOrder(); + for (skew = cPrefetchTargetDepth - 1; skew && n; skew--) { + from = n; + n = n->traversePreviousNodePostOrder(); + } + from->setPrefetchTarget(m_next); + } + } + void setPrefetchTarget(Node *prefetch) { m_prefetch = prefetch; } + void setNextSibling(Node* next) { m_next = next; updatePrefetchTarget(); } + void updatePreviousNode() { m_previousNode = traversePreviousNode(); if (m_previousNode) m_previousNode->setNextNode(this); } + void updateNextNode() { m_nextNode = traverseNextNode(); if (m_nextNode) m_nextNode->setPreviousNode(this); } + void updatePrevNextNodesInSubtree(); + + void setPreviousNode(Node* previous) { m_previousNode = previous; } + void setNextNode(Node* next) { m_nextNode = next; } // FIXME: These two functions belong in editing -- "atomic node" is an editing concept. Node* previousNodeConsideringAtomicNodes() const; @@ -314,6 +337,9 @@ public: void setIsLink() { setFlag(IsLinkFlag); } void clearIsLink() { clearFlag(IsLinkFlag); } + void setIeForbidsInsertHTML() { setFlag(IeForbidsInsertHTML); } + bool ieForbidsInsertHTML() const { return getFlag(IeForbidsInsertHTML); } + enum ShouldSetAttached { SetAttached, DoNotSetAttached @@ -392,12 +418,25 @@ public: // This can be used to restrict traversal to a particular sub-tree. Node* traverseNextNode(const Node* stayWithin = 0) const; + Node* traverseNextNodeFastPath() const { prefetchTarget(); return m_nextNode; } + + ALWAYS_INLINE void prefetchTarget() const { + if (m_prefetch) { + __builtin_prefetch(((char *) m_prefetch)); + __builtin_prefetch(((char *) m_prefetch) + 64); + } + } + + Node* lastDescendantNode(bool includeThis = false) const; + // Like traverseNextNode, but skips children and starts with the next sibling. Node* traverseNextSibling(const Node* stayWithin = 0) const; // Does a reverse pre-order traversal to find the node that comes before the current one in document order Node* traversePreviousNode(const Node* stayWithin = 0) const; + Node* traversePreviousNodeFastPath() const { return m_previousNode; } + // Like traverseNextNode, but visits parents after their children. Node* traverseNextNodePostOrder() const; @@ -515,9 +554,11 @@ public: void notifyLocalNodeListsLabelChanged(); void removeCachedClassNodeList(ClassNodeList*, const String&); void removeCachedNameNodeList(NameNodeList*, const String&); - void removeCachedTagNodeList(TagNodeList*, const QualifiedName&); + void removeCachedTagNodeList(TagNodeList*, const AtomicString&); + void removeCachedTagNodeListNS(TagNodeListNS*, const QualifiedName&); void removeCachedLabelsNodeList(DynamicNodeList*); - + void removeCachedChildNodeList(DynamicNodeList*); + PassRefPtr<NodeList> getElementsByTagName(const AtomicString&); PassRefPtr<NodeList> getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName); PassRefPtr<NodeList> getElementsByName(const String& elementName); @@ -593,7 +634,7 @@ private: InActiveChainFlag = 1 << 15, InDetachFlag = 1 << 16, HasRareDataFlag = 1 << 17, - IsShadowRootFlag = 1 << 18, + IsShadowRootOrSVGShadowRootFlag = 1 << 18, // These bits are used by derived classes, pulled up here so they can // be stored in the same memory word as the Node bits above. @@ -605,11 +646,14 @@ private: IsSynchronizingSVGAttributesFlag = 1 << 23, // SVGElement HasSVGRareDataFlag = 1 << 24, // SVGElement #endif - StyleChangeMask = 1 << nodeStyleChangeShift | 1 << (nodeStyleChangeShift + 1), SelfOrAncestorHasDirAutoFlag = 1 << 27, + IeForbidsInsertHTML = 1 << 28, + + NodeDetachClearFlags = IsActiveFlag | IsHoveredFlag | InActiveChainFlag | IsAttachedFlag | InDetachFlag, + #if ENABLE(SVG) DefaultNodeFlags = IsParsingChildrenFinishedFlag | IsStyleAttributeValidFlag | AreSVGAttributesValidFlag #else @@ -619,7 +663,7 @@ private: // 4 bits remaining - bool getFlag(NodeFlags mask) const { return m_nodeFlags & mask; } + ALWAYS_INLINE bool getFlag(NodeFlags mask) const { return m_nodeFlags & mask; } void setFlag(bool f, NodeFlags mask) const { m_nodeFlags = (m_nodeFlags & ~mask) | (-(int32_t)f & mask); } void setFlag(NodeFlags mask) const { m_nodeFlags |= mask; } void clearFlag(NodeFlags mask) const { m_nodeFlags &= ~mask; } @@ -631,9 +675,11 @@ protected: CreateComment = DefaultNodeFlags | IsCommentFlag, CreateContainer = DefaultNodeFlags | IsContainerFlag, CreateElement = CreateContainer | IsElementFlag, + CreateShadowRoot = CreateContainer | IsShadowRootOrSVGShadowRootFlag, CreateStyledElement = CreateElement | IsStyledElementFlag, CreateHTMLElement = CreateStyledElement | IsHTMLFlag, CreateSVGElement = CreateStyledElement | IsSVGFlag, + CreateSVGShadowRoot = CreateSVGElement | IsShadowRootOrSVGShadowRootFlag, }; Node(Document*, ConstructionType); @@ -690,8 +736,11 @@ private: Document* m_document; Node* m_previous; Node* m_next; + Node* m_prefetch; RenderObject* m_renderer; mutable uint32_t m_nodeFlags; + Node* m_previousNode; + Node* m_nextNode; protected: bool isParsingChildrenFinished() const { return getFlag(IsParsingChildrenFinishedFlag); } @@ -728,7 +777,7 @@ inline void addSubresourceURL(ListHashSet<KURL>& urls, const KURL& url) inline ContainerNode* Node::parentNode() const { - return getFlag(IsShadowRootFlag) || isSVGShadowRoot() ? 0 : parent(); + return getFlag(IsShadowRootOrSVGShadowRootFlag) ? 0 : parent(); } inline ContainerNode* Node::parentOrHostNode() const @@ -738,7 +787,7 @@ inline ContainerNode* Node::parentOrHostNode() const inline ContainerNode* Node::parentNodeGuaranteedHostFree() const { - ASSERT(!getFlag(IsShadowRootFlag) && !isSVGShadowRoot()); + ASSERT(!getFlag(IsShadowRootOrSVGShadowRootFlag)); return parentOrHostNode(); } diff --git a/Source/WebCore/dom/NodeRareData.h b/Source/WebCore/dom/NodeRareData.h index ac05d3e..b81dd3f 100644 --- a/Source/WebCore/dom/NodeRareData.h +++ b/Source/WebCore/dom/NodeRareData.h @@ -22,6 +22,7 @@ #ifndef NodeRareData_h #define NodeRareData_h +#include "ChildNodeList.h" #include "ClassNodeList.h" #include "DynamicNodeList.h" #include "NameNodeList.h" @@ -42,17 +43,20 @@ public: typedef HashSet<DynamicNodeList*> NodeListSet; NodeListSet m_listsWithCaches; - RefPtr<DynamicNodeList::Caches> m_childNodeListCaches; + RefPtr<ChildNodeList> m_childNodeListCache; typedef HashMap<String, ClassNodeList*> ClassNodeListCache; ClassNodeListCache m_classNodeListCache; typedef HashMap<String, NameNodeList*> NameNodeListCache; NameNodeListCache m_nameNodeListCache; - - typedef HashMap<RefPtr<QualifiedName::QualifiedNameImpl>, TagNodeList*> TagNodeListCache; + + typedef HashMap<AtomicStringImpl*, TagNodeList*> TagNodeListCache; TagNodeListCache m_tagNodeListCache; + typedef HashMap<RefPtr<QualifiedName::QualifiedNameImpl>, TagNodeListNS*> TagNodeListCacheNS; + TagNodeListCacheNS m_tagNodeListCacheNS; + RefPtr<DynamicNodeList> m_labelsNodeListCache; static PassOwnPtr<NodeListsNodeData> create() @@ -66,7 +70,8 @@ public: private: NodeListsNodeData() - : m_childNodeListCaches(DynamicNodeList::Caches::create()), m_labelsNodeListCache(0) + : m_childNodeListCache(0) + , m_labelsNodeListCache(0) { } }; @@ -106,6 +111,15 @@ public: void clearNodeLists() { m_nodeLists.clear(); } void setNodeLists(PassOwnPtr<NodeListsNodeData> lists) { m_nodeLists = lists; } NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); } + NodeListsNodeData* ensureNodeLists(Node* n) + { + if (!m_nodeLists) { + m_nodeLists = NodeListsNodeData::create(); + if (n->document()) + n->document()->addNodeListCache(); + } + return m_nodeLists.get(); + } short tabIndex() const { return m_tabIndex; } void setTabIndexExplicitly(short index) { m_tabIndex = index; m_tabIndexWasSetExplicitly = true; } diff --git a/Source/WebCore/dom/SelectorNodeList.cpp b/Source/WebCore/dom/SelectorNodeList.cpp index 7611488..82f1103 100644 --- a/Source/WebCore/dom/SelectorNodeList.cpp +++ b/Source/WebCore/dom/SelectorNodeList.cpp @@ -1,5 +1,6 @@ /* * Copyright (C) 2007, 2008 Apple Inc. All rights reserved. + * Copyright (C) 2012 The Linux Foundation All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -55,16 +56,25 @@ PassRefPtr<StaticNodeList> createSelectorNodeList(Node* rootNode, const CSSSelec if (element && (rootNode->isDocumentNode() || element->isDescendantOf(rootNode)) && selectorChecker.checkSelector(onlySelector, element)) nodes.append(element); } else { - for (Node* n = rootNode->firstChild(); n; n = n->traverseNextNode(rootNode)) { + Vector<CSSSelector*> querySelectors; + querySelectors.reserveInitialCapacity(16); + for (CSSSelector* selector = querySelectorList.first(); selector; selector = CSSSelectorList::next(selector)) + querySelectors.append(selector); + int querySelectorsCount = querySelectors.size(); + + Node* lastNode = rootNode->lastDescendantNode(); + for (Node* n = rootNode->firstChild(); n; n = n->traverseNextNodeFastPath()) { if (n->isElementNode()) { Element* element = static_cast<Element*>(n); - for (CSSSelector* selector = querySelectorList.first(); selector; selector = CSSSelectorList::next(selector)) { - if (selectorChecker.checkSelector(selector, element)) { + for (int i = 0; i < querySelectorsCount; i++) { + if (selectorChecker.checkSelector(querySelectors[i], element)) { nodes.append(n); break; } } } + if (n == lastNode) + break; } } diff --git a/Source/WebCore/dom/TagNodeList.cpp b/Source/WebCore/dom/TagNodeList.cpp index 4914e09..df51fe1 100644 --- a/Source/WebCore/dom/TagNodeList.cpp +++ b/Source/WebCore/dom/TagNodeList.cpp @@ -4,6 +4,7 @@ * (C) 2001 Dirk Mueller (mueller@kde.org) * Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved. * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies) + * Copyright (C) 2012 The Linux Foundation All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -29,25 +30,45 @@ namespace WebCore { -TagNodeList::TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName) +TagNodeListNS::TagNodeListNS(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName) : DynamicNodeList(rootNode) , m_namespaceURI(namespaceURI) , m_localName(localName) + , m_isStarAtomNamespaceURI(m_namespaceURI == starAtom) + , m_isStarAtomlocalName(m_localName == starAtom) { ASSERT(m_namespaceURI.isNull() || !m_namespaceURI.isEmpty()); } -TagNodeList::~TagNodeList() +TagNodeListNS::~TagNodeListNS() { - m_rootNode->removeCachedTagNodeList(this, QualifiedName(nullAtom, m_localName, m_namespaceURI)); -} + m_rootNode->removeCachedTagNodeListNS(this, QualifiedName(nullAtom, m_localName, m_namespaceURI)); +} -bool TagNodeList::nodeMatches(Element* testNode) const +bool TagNodeListNS::nodeMatches(Element* testNode) const { - if (m_namespaceURI != starAtom && m_namespaceURI != testNode->namespaceURI()) + if (!m_isStarAtomNamespaceURI && m_namespaceURI != testNode->namespaceURI()) return false; - return m_localName == starAtom || m_localName == testNode->localName(); + return m_isStarAtomlocalName || m_localName == testNode->localName(); } +TagNodeList::TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& localName) + : DynamicNodeList(rootNode) + , m_localName(localName) + , m_isStarAtomlocalName(m_localName == starAtom) +{ +} + +TagNodeList::~TagNodeList() +{ + m_rootNode->removeCachedTagNodeList(this, m_localName); +} + +bool TagNodeList::nodeMatches(Element* testNode) const +{ + return m_isStarAtomlocalName || m_localName == testNode->localName(); +} + + } // namespace WebCore diff --git a/Source/WebCore/dom/TagNodeList.h b/Source/WebCore/dom/TagNodeList.h index 9053b53..f255532 100644 --- a/Source/WebCore/dom/TagNodeList.h +++ b/Source/WebCore/dom/TagNodeList.h @@ -29,24 +29,45 @@ namespace WebCore { - // NodeList that limits to a particular tag. - class TagNodeList : public DynamicNodeList { - public: - static PassRefPtr<TagNodeList> create(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName) - { - return adoptRef(new TagNodeList(rootNode, namespaceURI, localName)); - } +// NodeList with namespace that limits to a particular tag. +class TagNodeListNS : public DynamicNodeList { +public: + static PassRefPtr<TagNodeListNS> create(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName) + { + return adoptRef(new TagNodeListNS(rootNode, namespaceURI, localName)); + } - virtual ~TagNodeList(); + virtual ~TagNodeListNS(); - private: - TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName); +private: + TagNodeListNS(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName); - virtual bool nodeMatches(Element*) const; + virtual bool nodeMatches(Element*) const; - AtomicString m_namespaceURI; - AtomicString m_localName; - }; + AtomicString m_namespaceURI; + AtomicString m_localName; + bool m_isStarAtomNamespaceURI : 1; + bool m_isStarAtomlocalName : 1; +}; + +// NodeList that limits to a particular tag. +class TagNodeList : public DynamicNodeList { +public: + static PassRefPtr<TagNodeList> create(PassRefPtr<Node> rootNode, const AtomicString& localName) + { + return adoptRef(new TagNodeList(rootNode, localName)); + } + + virtual ~TagNodeList(); + +private: + TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& localName); + + virtual bool nodeMatches(Element*) const; + + AtomicString m_localName; + bool m_isStarAtomlocalName; +}; } // namespace WebCore diff --git a/Source/WebCore/dom/Text.cpp b/Source/WebCore/dom/Text.cpp index c4ea0a6..01a454d 100644 --- a/Source/WebCore/dom/Text.cpp +++ b/Source/WebCore/dom/Text.cpp @@ -213,7 +213,7 @@ bool Text::rendererIsNeeded(RenderStyle *style) if (style->preserveNewline()) // pre/pre-wrap/pre-line always make renderers. return true; - RenderObject *prev = previousRenderer(); + RenderObject* prev = m_previousRenderer ? m_previousRenderer : previousRenderer(); if (prev && prev->isBR()) // <span><br/> <br/></span> return false; diff --git a/Source/WebCore/dom/Text.h b/Source/WebCore/dom/Text.h index 5995f1f..4db3bb3 100644 --- a/Source/WebCore/dom/Text.h +++ b/Source/WebCore/dom/Text.h @@ -43,9 +43,12 @@ public: virtual void attach(); + void setPreviousRenderer(RenderObject* renderer) { m_previousRenderer = renderer; } + protected: Text(Document* document, const String& data) : CharacterData(document, data, CreateText) + , m_previousRenderer(0) { } @@ -63,6 +66,8 @@ private: #ifndef NDEBUG virtual void formatForDebugger(char* buffer, unsigned length) const; #endif + + RenderObject* m_previousRenderer; }; } // namespace WebCore diff --git a/Source/WebCore/dom/TreeScope.cpp b/Source/WebCore/dom/TreeScope.cpp index a995a2d..45c7a8f 100644 --- a/Source/WebCore/dom/TreeScope.cpp +++ b/Source/WebCore/dom/TreeScope.cpp @@ -97,7 +97,7 @@ Element* TreeScope::getElementByAccessKey(const String& key) const if (key.isEmpty()) return 0; if (!m_accessKeyMapValid) { - for (Node* n = firstChild(); n; n = n->traverseNextNode()) { + for (Node* n = firstChild(); n; n = n->traverseNextNodeFastPath()) { if (!n->isElementNode()) continue; Element* element = static_cast<Element*>(n); @@ -149,7 +149,7 @@ Element* TreeScope::findAnchor(const String& name) return 0; if (Element* element = getElementById(name)) return element; - for (Node* node = this; node; node = node->traverseNextNode()) { + for (Node* node = this; node; node = node->traverseNextNodeFastPath()) { if (node->hasTagName(aTag)) { HTMLAnchorElement* anchor = static_cast<HTMLAnchorElement*>(node); if (document()->inQuirksMode()) { |