| Index: Source/core/xml/XPathNodeSet.cpp
|
| diff --git a/Source/core/xml/XPathNodeSet.cpp b/Source/core/xml/XPathNodeSet.cpp
|
| index a0e111c5d6cb986cadcf52efd703507009fe4a09..44ee351ceb57b51d9226cb77a2c3a06273cf56ce 100644
|
| --- a/Source/core/xml/XPathNodeSet.cpp
|
| +++ b/Source/core/xml/XPathNodeSet.cpp
|
| @@ -34,8 +34,9 @@
|
| 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;
|
|
|
| typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector;
|
| @@ -57,7 +58,8 @@ static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents
|
|
|
| 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;
|
| @@ -87,22 +89,24 @@ static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector
|
| }
|
|
|
| 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) {
|
| @@ -117,8 +121,9 @@ static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector
|
| }
|
| }
|
|
|
| - // Children nodes of the common ancestor induce a subdivision of our node-set.
|
| - // Sort it according to this subdivision, and recursively sort each group.
|
| + // 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]));
|
| @@ -126,11 +131,13 @@ static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector
|
| 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);
|
| @@ -179,7 +186,8 @@ 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.
|
| + // 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)
|
| @@ -192,9 +200,9 @@ 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;
|
| }
|
| @@ -261,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();
|
| }
|
|
|
|
|