summaryrefslogtreecommitdiffstats
path: root/chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp')
-rw-r--r--chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp85
1 files changed, 54 insertions, 31 deletions
diff --git a/chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp b/chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp
index b0966c66301..cfb758645b2 100644
--- a/chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp
+++ b/chromium/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp
@@ -27,25 +27,39 @@
#include "core/xml/XPathNodeSet.h"
#include "core/dom/Attr.h"
+#include "core/dom/Document.h"
#include "core/dom/Element.h"
#include "core/dom/NodeTraversal.h"
namespace WebCore {
namespace XPath {
-// When a node set is large, sorting it by traversing the whole document is better (we can
-// assume that we aren't dealing with documents that we cannot even traverse in reasonable time).
+// When a node set is large, sorting it by traversing the whole document is
+// better (we can assume that we aren't dealing with documents that we cannot
+// even traverse in reasonable time).
const unsigned traversalSortCutoff = 10000;
-static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
+typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector;
+
+PassOwnPtrWillBeRawPtr<NodeSet> NodeSet::create(const NodeSet& other)
+{
+ OwnPtrWillBeRawPtr<NodeSet> nodeSet = NodeSet::create();
+ nodeSet->m_isSorted = other.m_isSorted;
+ nodeSet->m_subtreesAreDisjoint = other.m_subtreesAreDisjoint;
+ nodeSet->m_nodes.appendVector(other.m_nodes);
+ return nodeSet.release();
+}
+
+static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents)
{
ASSERT(parents.size() >= depth + 1);
return parents[parents.size() - 1 - depth];
}
-static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parentMatrix, bool mayContainAttributeNodes)
+static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector>& parentMatrix, bool mayContainAttributeNodes)
{
- ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.
+ // Should not call this function with less that two nodes to sort.
+ ASSERT(from + 1 < to);
unsigned minDepth = UINT_MAX;
for (unsigned i = from; i < to; ++i) {
unsigned depth = parentMatrix[i].size() - 1;
@@ -75,22 +89,24 @@ static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parent
}
if (commonAncestorDepth == minDepth) {
- // One of the nodes is the common ancestor => it is the first in document order.
- // Find it and move it to the beginning.
- for (unsigned i = from; i < to; ++i)
+ // One of the nodes is the common ancestor => it is the first in
+ // document order. Find it and move it to the beginning.
+ for (unsigned i = from; i < to; ++i) {
if (commonAncestor == parentMatrix[i][0]) {
parentMatrix[i].swap(parentMatrix[from]);
if (from + 2 < to)
sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
return;
}
+ }
}
if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
- // The attribute nodes and namespace nodes of an element occur before the children of the element.
- // The namespace nodes are defined to occur before the attribute nodes.
- // The relative order of namespace nodes is implementation-dependent.
- // The relative order of attribute nodes is implementation-dependent.
+ // The attribute nodes and namespace nodes of an element occur before
+ // the children of the element. The namespace nodes are defined to occur
+ // before the attribute nodes. The relative order of namespace nodes is
+ // implementation-dependent. The relative order of attribute nodes is
+ // implementation-dependent.
unsigned sortedEnd = from;
// FIXME: namespace nodes are not implemented.
for (unsigned i = sortedEnd; i < to; ++i) {
@@ -105,20 +121,23 @@ static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parent
}
}
- // Children nodes of the common ancestor induce a subdivision of our node-set.
- // Sort it according to this subdivision, and recursively sort each group.
- HashSet<Node*> parentNodes;
+ // Children nodes of the common ancestor induce a subdivision of our
+ // node-set. Sort it according to this subdivision, and recursively sort
+ // each group.
+ WillBeHeapHashSet<RawPtrWillBeMember<Node> > parentNodes;
for (unsigned i = from; i < to; ++i)
parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
unsigned previousGroupEnd = from;
unsigned groupEnd = from;
for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
- // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning.
+ // If parentNodes contains the node, perform a linear search to move its
+ // children in the node-set to the beginning.
if (parentNodes.contains(n)) {
- for (unsigned i = groupEnd; i < to; ++i)
+ for (unsigned i = groupEnd; i < to; ++i) {
if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
parentMatrix[i].swap(parentMatrix[groupEnd++]);
+ }
if (groupEnd - previousGroupEnd > 1)
sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);
@@ -152,9 +171,9 @@ void NodeSet::sort() const
bool containsAttributeNodes = false;
- Vector<Vector<Node*> > parentMatrix(nodeCount);
+ WillBeHeapVector<NodeSetVector> parentMatrix(nodeCount);
for (unsigned i = 0; i < nodeCount; ++i) {
- Vector<Node*>& parentsVector = parentMatrix[i];
+ NodeSetVector& parentsVector = parentMatrix[i];
Node* n = m_nodes[i].get();
parentsVector.append(n);
if (n->isAttributeNode()) {
@@ -167,22 +186,23 @@ void NodeSet::sort() const
}
sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
- // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed.
- Vector<RefPtr<Node> > sortedNodes;
+ // It is not possible to just assign the result to m_nodes, because some
+ // nodes may get dereferenced and destroyed.
+ WillBeHeapVector<RefPtrWillBeMember<Node> > sortedNodes;
sortedNodes.reserveInitialCapacity(nodeCount);
for (unsigned i = 0; i < nodeCount; ++i)
sortedNodes.append(parentMatrix[i][0]);
- const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
+ const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sortedNodes);
}
static Node* findRootNode(Node* node)
{
if (node->isAttributeNode())
node = toAttr(node)->ownerElement();
- if (node->inDocument())
+ if (node->inDocument()) {
node = &node->document();
- else {
+ } else {
while (Node* parent = node->parentNode())
node = parent;
}
@@ -191,7 +211,7 @@ static Node* findRootNode(Node* node)
void NodeSet::traversalSort() const
{
- HashSet<Node*> nodes;
+ WillBeHeapHashSet<RawPtrWillBeMember<Node> > nodes;
bool containsAttributeNodes = false;
unsigned nodeCount = m_nodes.size();
@@ -203,7 +223,7 @@ void NodeSet::traversalSort() const
containsAttributeNodes = true;
}
- Vector<RefPtr<Node> > sortedNodes;
+ WillBeHeapVector<RefPtrWillBeMember<Node> > sortedNodes;
sortedNodes.reserveInitialCapacity(nodeCount);
for (Node* n = findRootNode(m_nodes.first().get()); n; n = NodeTraversal::next(*n)) {
@@ -217,16 +237,17 @@ void NodeSet::traversalSort() const
if (!element->hasAttributes())
continue;
- unsigned attributeCount = element->attributeCount();
- for (unsigned i = 0; i < attributeCount; ++i) {
- RefPtr<Attr> attr = element->attrIfExists(element->attributeItem(i)->name());
+ AttributeCollection attributes = element->attributes();
+ AttributeCollection::const_iterator end = attributes.end();
+ for (AttributeCollection::const_iterator it = attributes.begin(); it != end; ++it) {
+ RefPtrWillBeRawPtr<Attr> attr = element->attrIfExists(it->name());
if (attr && nodes.contains(attr.get()))
sortedNodes.append(attr);
}
}
ASSERT(sortedNodes.size() == nodeCount);
- const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
+ const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sortedNodes);
}
void NodeSet::reverse()
@@ -248,7 +269,9 @@ Node* NodeSet::firstNode() const
if (isEmpty())
return 0;
- sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
+ // FIXME: fully sorting the node-set just to find its first node is
+ // wasteful.
+ sort();
return m_nodes.at(0).get();
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-07 14:01:56 +0000