| 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 109 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 120 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes); | 120 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes); |
| 121 return; | 121 return; |
| 122 } | 122 } |
| 123 } | 123 } |
| 124 | 124 |
| 125 // Children nodes of the common ancestor induce a subdivision of our | 125 // Children nodes of the common ancestor induce a subdivision of our |
| 126 // node-set. Sort it according to this subdivision, and recursively sort | 126 // node-set. Sort it according to this subdivision, and recursively sort |
| 127 // each group. | 127 // each group. |
| 128 HeapHashSet<Member<Node>> parentNodes; | 128 HeapHashSet<Member<Node>> parentNodes; |
| 129 for (unsigned i = from; i < to; ++i) | 129 for (unsigned i = from; i < to; ++i) |
| 130 parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i])); | 130 parentNodes.insert( |
| 131 parentWithDepth(commonAncestorDepth + 1, parentMatrix[i])); |
| 131 | 132 |
| 132 unsigned previousGroupEnd = from; | 133 unsigned previousGroupEnd = from; |
| 133 unsigned groupEnd = from; | 134 unsigned groupEnd = from; |
| 134 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) { | 135 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) { |
| 135 // If parentNodes contains the node, perform a linear search to move its | 136 // If parentNodes contains the node, perform a linear search to move its |
| 136 // children in the node-set to the beginning. | 137 // children in the node-set to the beginning. |
| 137 if (parentNodes.contains(n)) { | 138 if (parentNodes.contains(n)) { |
| 138 for (unsigned i = groupEnd; i < to; ++i) { | 139 for (unsigned i = groupEnd; i < to; ++i) { |
| 139 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n) | 140 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n) |
| 140 parentMatrix[i].swap(parentMatrix[groupEnd++]); | 141 parentMatrix[i].swap(parentMatrix[groupEnd++]); |
| (...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 210 } | 211 } |
| 211 | 212 |
| 212 void NodeSet::traversalSort() const { | 213 void NodeSet::traversalSort() const { |
| 213 HeapHashSet<Member<Node>> nodes; | 214 HeapHashSet<Member<Node>> nodes; |
| 214 bool containsAttributeNodes = false; | 215 bool containsAttributeNodes = false; |
| 215 | 216 |
| 216 unsigned nodeCount = m_nodes.size(); | 217 unsigned nodeCount = m_nodes.size(); |
| 217 DCHECK_GT(nodeCount, 1u); | 218 DCHECK_GT(nodeCount, 1u); |
| 218 for (unsigned i = 0; i < nodeCount; ++i) { | 219 for (unsigned i = 0; i < nodeCount; ++i) { |
| 219 Node* node = m_nodes[i].get(); | 220 Node* node = m_nodes[i].get(); |
| 220 nodes.add(node); | 221 nodes.insert(node); |
| 221 if (node->isAttributeNode()) | 222 if (node->isAttributeNode()) |
| 222 containsAttributeNodes = true; | 223 containsAttributeNodes = true; |
| 223 } | 224 } |
| 224 | 225 |
| 225 HeapVector<Member<Node>> sortedNodes; | 226 HeapVector<Member<Node>> sortedNodes; |
| 226 sortedNodes.reserveInitialCapacity(nodeCount); | 227 sortedNodes.reserveInitialCapacity(nodeCount); |
| 227 | 228 |
| 228 for (Node& n : NodeTraversal::startsAt(*findRootNode(m_nodes.front()))) { | 229 for (Node& n : NodeTraversal::startsAt(*findRootNode(m_nodes.front()))) { |
| 229 if (nodes.contains(&n)) | 230 if (nodes.contains(&n)) |
| 230 sortedNodes.push_back(&n); | 231 sortedNodes.push_back(&n); |
| (...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 270 | 271 |
| 271 Node* NodeSet::anyNode() const { | 272 Node* NodeSet::anyNode() const { |
| 272 if (isEmpty()) | 273 if (isEmpty()) |
| 273 return nullptr; | 274 return nullptr; |
| 274 | 275 |
| 275 return m_nodes.at(0).get(); | 276 return m_nodes.at(0).get(); |
| 276 } | 277 } |
| 277 | 278 |
| 278 } // namespace XPath | 279 } // namespace XPath |
| 279 } // namespace blink | 280 } // namespace blink |
| OLD | NEW |