OLD | NEW |
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 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
44 { | 44 { |
45 NodeSet* nodeSet = NodeSet::create(); | 45 NodeSet* nodeSet = NodeSet::create(); |
46 nodeSet->m_isSorted = other.m_isSorted; | 46 nodeSet->m_isSorted = other.m_isSorted; |
47 nodeSet->m_subtreesAreDisjoint = other.m_subtreesAreDisjoint; | 47 nodeSet->m_subtreesAreDisjoint = other.m_subtreesAreDisjoint; |
48 nodeSet->m_nodes.appendVector(other.m_nodes); | 48 nodeSet->m_nodes.appendVector(other.m_nodes); |
49 return nodeSet; | 49 return nodeSet; |
50 } | 50 } |
51 | 51 |
52 static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents
) | 52 static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents
) |
53 { | 53 { |
54 ASSERT(parents.size() >= depth + 1); | 54 DCHECK_GE(parents.size(), depth + 1); |
55 return parents[parents.size() - 1 - depth]; | 55 return parents[parents.size() - 1 - depth]; |
56 } | 56 } |
57 | 57 |
58 static void sortBlock(unsigned from, unsigned to, HeapVector<NodeSetVector>& par
entMatrix, bool mayContainAttributeNodes) | 58 static void sortBlock(unsigned from, unsigned to, HeapVector<NodeSetVector>& par
entMatrix, bool mayContainAttributeNodes) |
59 { | 59 { |
60 // Should not call this function with less that two nodes to sort. | 60 // Should not call this function with less that two nodes to sort. |
61 ASSERT(from + 1 < to); | 61 DCHECK_LT(from + 1, to); |
62 unsigned minDepth = UINT_MAX; | 62 unsigned minDepth = UINT_MAX; |
63 for (unsigned i = from; i < to; ++i) { | 63 for (unsigned i = from; i < to; ++i) { |
64 unsigned depth = parentMatrix[i].size() - 1; | 64 unsigned depth = parentMatrix[i].size() - 1; |
65 if (minDepth > depth) | 65 if (minDepth > depth) |
66 minDepth = depth; | 66 minDepth = depth; |
67 } | 67 } |
68 | 68 |
69 // Find the common ancestor. | 69 // Find the common ancestor. |
70 unsigned commonAncestorDepth = minDepth; | 70 unsigned commonAncestorDepth = minDepth; |
71 Node* commonAncestor; | 71 Node* commonAncestor; |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
134 // children in the node-set to the beginning. | 134 // children in the node-set to the beginning. |
135 if (parentNodes.contains(n)) { | 135 if (parentNodes.contains(n)) { |
136 for (unsigned i = groupEnd; i < to; ++i) { | 136 for (unsigned i = groupEnd; i < to; ++i) { |
137 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) ==
n) | 137 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) ==
n) |
138 parentMatrix[i].swap(parentMatrix[groupEnd++]); | 138 parentMatrix[i].swap(parentMatrix[groupEnd++]); |
139 } | 139 } |
140 | 140 |
141 if (groupEnd - previousGroupEnd > 1) | 141 if (groupEnd - previousGroupEnd > 1) |
142 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAt
tributeNodes); | 142 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAt
tributeNodes); |
143 | 143 |
144 ASSERT(previousGroupEnd != groupEnd); | 144 DCHECK_NE(previousGroupEnd, groupEnd); |
145 previousGroupEnd = groupEnd; | 145 previousGroupEnd = groupEnd; |
146 #if ENABLE(ASSERT) | 146 #if DCHECK_IS_ON() |
147 parentNodes.remove(n); | 147 parentNodes.remove(n); |
148 #endif | 148 #endif |
149 } | 149 } |
150 } | 150 } |
151 | 151 |
152 ASSERT(parentNodes.isEmpty()); | 152 DCHECK(parentNodes.isEmpty()); |
153 } | 153 } |
154 | 154 |
155 void NodeSet::sort() const | 155 void NodeSet::sort() const |
156 { | 156 { |
157 if (m_isSorted) | 157 if (m_isSorted) |
158 return; | 158 return; |
159 | 159 |
160 unsigned nodeCount = m_nodes.size(); | 160 unsigned nodeCount = m_nodes.size(); |
161 if (nodeCount < 2) { | 161 if (nodeCount < 2) { |
162 const_cast<bool&>(m_isSorted) = true; | 162 const_cast<bool&>(m_isSorted) = true; |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
207 } | 207 } |
208 return node; | 208 return node; |
209 } | 209 } |
210 | 210 |
211 void NodeSet::traversalSort() const | 211 void NodeSet::traversalSort() const |
212 { | 212 { |
213 HeapHashSet<Member<Node>> nodes; | 213 HeapHashSet<Member<Node>> nodes; |
214 bool containsAttributeNodes = false; | 214 bool containsAttributeNodes = false; |
215 | 215 |
216 unsigned nodeCount = m_nodes.size(); | 216 unsigned nodeCount = m_nodes.size(); |
217 ASSERT(nodeCount > 1); | 217 DCHECK_GT(nodeCount, 1u); |
218 for (unsigned i = 0; i < nodeCount; ++i) { | 218 for (unsigned i = 0; i < nodeCount; ++i) { |
219 Node* node = m_nodes[i].get(); | 219 Node* node = m_nodes[i].get(); |
220 nodes.add(node); | 220 nodes.add(node); |
221 if (node->isAttributeNode()) | 221 if (node->isAttributeNode()) |
222 containsAttributeNodes = true; | 222 containsAttributeNodes = true; |
223 } | 223 } |
224 | 224 |
225 HeapVector<Member<Node>> sortedNodes; | 225 HeapVector<Member<Node>> sortedNodes; |
226 sortedNodes.reserveInitialCapacity(nodeCount); | 226 sortedNodes.reserveInitialCapacity(nodeCount); |
227 | 227 |
228 for (Node& n : NodeTraversal::startsAt(*findRootNode(m_nodes.first()))) { | 228 for (Node& n : NodeTraversal::startsAt(*findRootNode(m_nodes.first()))) { |
229 if (nodes.contains(&n)) | 229 if (nodes.contains(&n)) |
230 sortedNodes.append(&n); | 230 sortedNodes.append(&n); |
231 | 231 |
232 if (!containsAttributeNodes || !n.isElementNode()) | 232 if (!containsAttributeNodes || !n.isElementNode()) |
233 continue; | 233 continue; |
234 | 234 |
235 Element* element = toElement(&n); | 235 Element* element = toElement(&n); |
236 AttributeCollection attributes = element->attributes(); | 236 AttributeCollection attributes = element->attributes(); |
237 for (auto& attribute : attributes) { | 237 for (auto& attribute : attributes) { |
238 Attr* attr = element->attrIfExists(attribute.name()); | 238 Attr* attr = element->attrIfExists(attribute.name()); |
239 if (attr && nodes.contains(attr)) | 239 if (attr && nodes.contains(attr)) |
240 sortedNodes.append(attr); | 240 sortedNodes.append(attr); |
241 } | 241 } |
242 } | 242 } |
243 | 243 |
244 ASSERT(sortedNodes.size() == nodeCount); | 244 DCHECK_EQ(sortedNodes.size(), nodeCount); |
245 const_cast<HeapVector<Member<Node>>&>(m_nodes).swap(sortedNodes); | 245 const_cast<HeapVector<Member<Node>>&>(m_nodes).swap(sortedNodes); |
246 } | 246 } |
247 | 247 |
248 void NodeSet::reverse() | 248 void NodeSet::reverse() |
249 { | 249 { |
250 if (m_nodes.isEmpty()) | 250 if (m_nodes.isEmpty()) |
251 return; | 251 return; |
252 | 252 |
253 unsigned from = 0; | 253 unsigned from = 0; |
254 unsigned to = m_nodes.size() - 1; | 254 unsigned to = m_nodes.size() - 1; |
(...skipping 18 matching lines...) Expand all Loading... |
273 Node* NodeSet::anyNode() const | 273 Node* NodeSet::anyNode() const |
274 { | 274 { |
275 if (isEmpty()) | 275 if (isEmpty()) |
276 return nullptr; | 276 return nullptr; |
277 | 277 |
278 return m_nodes.at(0).get(); | 278 return m_nodes.at(0).get(); |
279 } | 279 } |
280 | 280 |
281 } // namespace XPath | 281 } // namespace XPath |
282 } // namespace blink | 282 } // namespace blink |
OLD | NEW |