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 16 matching lines...) Expand all Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |