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(); |
} |