Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(734)

Side by Side Diff: Source/core/xml/XPathNodeSet.cpp

Issue 344553002: Fix style erros in XPath-related files. (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 6 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/core/xml/XPathNodeSet.h ('k') | Source/core/xml/XPathParser.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org> 2 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
3 * 3 *
4 * Redistribution and use in source and binary forms, with or without 4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions 5 * modification, are permitted provided that the following conditions
6 * are met: 6 * are met:
7 * 7 *
8 * 1. Redistributions of source code must retain the above copyright 8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer. 9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright 10 * 2. Redistributions in binary form must reproduce the above copyright
(...skipping 16 matching lines...) Expand all
27 #include "core/xml/XPathNodeSet.h" 27 #include "core/xml/XPathNodeSet.h"
28 28
29 #include "core/dom/Attr.h" 29 #include "core/dom/Attr.h"
30 #include "core/dom/Document.h" 30 #include "core/dom/Document.h"
31 #include "core/dom/Element.h" 31 #include "core/dom/Element.h"
32 #include "core/dom/NodeTraversal.h" 32 #include "core/dom/NodeTraversal.h"
33 33
34 namespace WebCore { 34 namespace WebCore {
35 namespace XPath { 35 namespace XPath {
36 36
37 // When a node set is large, sorting it by traversing the whole document is bett er (we can 37 // When a node set is large, sorting it by traversing the whole document is
38 // assume that we aren't dealing with documents that we cannot even traverse in reasonable time). 38 // better (we can assume that we aren't dealing with documents that we cannot
39 // even traverse in reasonable time).
39 const unsigned traversalSortCutoff = 10000; 40 const unsigned traversalSortCutoff = 10000;
40 41
41 typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector; 42 typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector;
42 43
43 PassOwnPtrWillBeRawPtr<NodeSet> NodeSet::create(const NodeSet& other) 44 PassOwnPtrWillBeRawPtr<NodeSet> NodeSet::create(const NodeSet& other)
44 { 45 {
45 OwnPtrWillBeRawPtr<NodeSet> nodeSet = NodeSet::create(); 46 OwnPtrWillBeRawPtr<NodeSet> nodeSet = NodeSet::create();
46 nodeSet->m_isSorted = other.m_isSorted; 47 nodeSet->m_isSorted = other.m_isSorted;
47 nodeSet->m_subtreesAreDisjoint = other.m_subtreesAreDisjoint; 48 nodeSet->m_subtreesAreDisjoint = other.m_subtreesAreDisjoint;
48 nodeSet->m_nodes.appendVector(other.m_nodes); 49 nodeSet->m_nodes.appendVector(other.m_nodes);
49 return nodeSet.release(); 50 return nodeSet.release();
50 } 51 }
51 52
52 static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents ) 53 static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents )
53 { 54 {
54 ASSERT(parents.size() >= depth + 1); 55 ASSERT(parents.size() >= depth + 1);
55 return parents[parents.size() - 1 - depth]; 56 return parents[parents.size() - 1 - depth];
56 } 57 }
57 58
58 static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector >& parentMatrix, bool mayContainAttributeNodes) 59 static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector >& parentMatrix, bool mayContainAttributeNodes)
59 { 60 {
60 ASSERT(from + 1 < to); // Should not call this function with less that two n odes to sort. 61 // Should not call this function with less that two nodes to sort.
62 ASSERT(from + 1 < to);
61 unsigned minDepth = UINT_MAX; 63 unsigned minDepth = UINT_MAX;
62 for (unsigned i = from; i < to; ++i) { 64 for (unsigned i = from; i < to; ++i) {
63 unsigned depth = parentMatrix[i].size() - 1; 65 unsigned depth = parentMatrix[i].size() - 1;
64 if (minDepth > depth) 66 if (minDepth > depth)
65 minDepth = depth; 67 minDepth = depth;
66 } 68 }
67 69
68 // Find the common ancestor. 70 // Find the common ancestor.
69 unsigned commonAncestorDepth = minDepth; 71 unsigned commonAncestorDepth = minDepth;
70 Node* commonAncestor; 72 Node* commonAncestor;
71 while (true) { 73 while (true) {
72 commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from] ); 74 commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from] );
73 if (commonAncestorDepth == 0) 75 if (commonAncestorDepth == 0)
74 break; 76 break;
75 77
76 bool allEqual = true; 78 bool allEqual = true;
77 for (unsigned i = from + 1; i < to; ++i) { 79 for (unsigned i = from + 1; i < to; ++i) {
78 if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMat rix[i])) { 80 if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMat rix[i])) {
79 allEqual = false; 81 allEqual = false;
80 break; 82 break;
81 } 83 }
82 } 84 }
83 if (allEqual) 85 if (allEqual)
84 break; 86 break;
85 87
86 --commonAncestorDepth; 88 --commonAncestorDepth;
87 } 89 }
88 90
89 if (commonAncestorDepth == minDepth) { 91 if (commonAncestorDepth == minDepth) {
90 // One of the nodes is the common ancestor => it is the first in documen t order. 92 // One of the nodes is the common ancestor => it is the first in
91 // Find it and move it to the beginning. 93 // document order. Find it and move it to the beginning.
92 for (unsigned i = from; i < to; ++i) 94 for (unsigned i = from; i < to; ++i) {
93 if (commonAncestor == parentMatrix[i][0]) { 95 if (commonAncestor == parentMatrix[i][0]) {
94 parentMatrix[i].swap(parentMatrix[from]); 96 parentMatrix[i].swap(parentMatrix[from]);
95 if (from + 2 < to) 97 if (from + 2 < to)
96 sortBlock(from + 1, to, parentMatrix, mayContainAttributeNod es); 98 sortBlock(from + 1, to, parentMatrix, mayContainAttributeNod es);
97 return; 99 return;
98 } 100 }
101 }
99 } 102 }
100 103
101 if (mayContainAttributeNodes && commonAncestor->isElementNode()) { 104 if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
102 // The attribute nodes and namespace nodes of an element occur before th e children of the element. 105 // The attribute nodes and namespace nodes of an element occur before
103 // The namespace nodes are defined to occur before the attribute nodes. 106 // the children of the element. The namespace nodes are defined to occur
104 // The relative order of namespace nodes is implementation-dependent. 107 // before the attribute nodes. The relative order of namespace nodes is
105 // The relative order of attribute nodes is implementation-dependent. 108 // implementation-dependent. The relative order of attribute nodes is
109 // implementation-dependent.
106 unsigned sortedEnd = from; 110 unsigned sortedEnd = from;
107 // FIXME: namespace nodes are not implemented. 111 // FIXME: namespace nodes are not implemented.
108 for (unsigned i = sortedEnd; i < to; ++i) { 112 for (unsigned i = sortedEnd; i < to; ++i) {
109 Node* n = parentMatrix[i][0]; 113 Node* n = parentMatrix[i][0];
110 if (n->isAttributeNode() && toAttr(n)->ownerElement() == commonAnces tor) 114 if (n->isAttributeNode() && toAttr(n)->ownerElement() == commonAnces tor)
111 parentMatrix[i].swap(parentMatrix[sortedEnd++]); 115 parentMatrix[i].swap(parentMatrix[sortedEnd++]);
112 } 116 }
113 if (sortedEnd != from) { 117 if (sortedEnd != from) {
114 if (to - sortedEnd > 1) 118 if (to - sortedEnd > 1)
115 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes) ; 119 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes) ;
116 return; 120 return;
117 } 121 }
118 } 122 }
119 123
120 // Children nodes of the common ancestor induce a subdivision of our node-se t. 124 // Children nodes of the common ancestor induce a subdivision of our
121 // Sort it according to this subdivision, and recursively sort each group. 125 // node-set. Sort it according to this subdivision, and recursively sort
126 // each group.
122 WillBeHeapHashSet<RawPtrWillBeMember<Node> > parentNodes; 127 WillBeHeapHashSet<RawPtrWillBeMember<Node> > parentNodes;
123 for (unsigned i = from; i < to; ++i) 128 for (unsigned i = from; i < to; ++i)
124 parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i] )); 129 parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i] ));
125 130
126 unsigned previousGroupEnd = from; 131 unsigned previousGroupEnd = from;
127 unsigned groupEnd = from; 132 unsigned groupEnd = from;
128 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) { 133 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
129 // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning. 134 // If parentNodes contains the node, perform a linear search to move its
135 // children in the node-set to the beginning.
130 if (parentNodes.contains(n)) { 136 if (parentNodes.contains(n)) {
131 for (unsigned i = groupEnd; i < to; ++i) 137 for (unsigned i = groupEnd; i < to; ++i) {
132 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n) 138 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
133 parentMatrix[i].swap(parentMatrix[groupEnd++]); 139 parentMatrix[i].swap(parentMatrix[groupEnd++]);
140 }
134 141
135 if (groupEnd - previousGroupEnd > 1) 142 if (groupEnd - previousGroupEnd > 1)
136 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAt tributeNodes); 143 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAt tributeNodes);
137 144
138 ASSERT(previousGroupEnd != groupEnd); 145 ASSERT(previousGroupEnd != groupEnd);
139 previousGroupEnd = groupEnd; 146 previousGroupEnd = groupEnd;
140 #ifndef NDEBUG 147 #ifndef NDEBUG
141 parentNodes.remove(n); 148 parentNodes.remove(n);
142 #endif 149 #endif
143 } 150 }
(...skipping 28 matching lines...) Expand all
172 if (n->isAttributeNode()) { 179 if (n->isAttributeNode()) {
173 n = toAttr(n)->ownerElement(); 180 n = toAttr(n)->ownerElement();
174 parentsVector.append(n); 181 parentsVector.append(n);
175 containsAttributeNodes = true; 182 containsAttributeNodes = true;
176 } 183 }
177 while ((n = n->parentNode())) 184 while ((n = n->parentNode()))
178 parentsVector.append(n); 185 parentsVector.append(n);
179 } 186 }
180 sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes); 187 sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
181 188
182 // It is not possible to just assign the result to m_nodes, because some nod es may get dereferenced and destroyed. 189 // It is not possible to just assign the result to m_nodes, because some
190 // nodes may get dereferenced and destroyed.
183 WillBeHeapVector<RefPtrWillBeMember<Node> > sortedNodes; 191 WillBeHeapVector<RefPtrWillBeMember<Node> > sortedNodes;
184 sortedNodes.reserveInitialCapacity(nodeCount); 192 sortedNodes.reserveInitialCapacity(nodeCount);
185 for (unsigned i = 0; i < nodeCount; ++i) 193 for (unsigned i = 0; i < nodeCount; ++i)
186 sortedNodes.append(parentMatrix[i][0]); 194 sortedNodes.append(parentMatrix[i][0]);
187 195
188 const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sorte dNodes); 196 const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sorte dNodes);
189 } 197 }
190 198
191 static Node* findRootNode(Node* node) 199 static Node* findRootNode(Node* node)
192 { 200 {
193 if (node->isAttributeNode()) 201 if (node->isAttributeNode())
194 node = toAttr(node)->ownerElement(); 202 node = toAttr(node)->ownerElement();
195 if (node->inDocument()) 203 if (node->inDocument()) {
196 node = &node->document(); 204 node = &node->document();
197 else { 205 } else {
198 while (Node* parent = node->parentNode()) 206 while (Node* parent = node->parentNode())
199 node = parent; 207 node = parent;
200 } 208 }
201 return node; 209 return node;
202 } 210 }
203 211
204 void NodeSet::traversalSort() const 212 void NodeSet::traversalSort() const
205 { 213 {
206 WillBeHeapHashSet<RawPtrWillBeMember<Node> > nodes; 214 WillBeHeapHashSet<RawPtrWillBeMember<Node> > nodes;
207 bool containsAttributeNodes = false; 215 bool containsAttributeNodes = false;
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
254 ++from; 262 ++from;
255 --to; 263 --to;
256 } 264 }
257 } 265 }
258 266
259 Node* NodeSet::firstNode() const 267 Node* NodeSet::firstNode() const
260 { 268 {
261 if (isEmpty()) 269 if (isEmpty())
262 return 0; 270 return 0;
263 271
264 sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful. 272 // FIXME: fully sorting the node-set just to find its first node is
273 // wasteful.
274 sort();
265 return m_nodes.at(0).get(); 275 return m_nodes.at(0).get();
266 } 276 }
267 277
268 Node* NodeSet::anyNode() const 278 Node* NodeSet::anyNode() const
269 { 279 {
270 if (isEmpty()) 280 if (isEmpty())
271 return 0; 281 return 0;
272 282
273 return m_nodes.at(0).get(); 283 return m_nodes.at(0).get();
274 } 284 }
275 285
276 } 286 }
277 } 287 }
OLDNEW
« no previous file with comments | « Source/core/xml/XPathNodeSet.h ('k') | Source/core/xml/XPathParser.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698