--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/WebCore/xml/XPathNodeSet.cpp Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,206 @@
+/*
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#if ENABLE(XPATH)
+#include "XPathNodeSet.h"
+
+#include "Attr.h"
+#include "Element.h"
+#include "Node.h"
+
+namespace WebCore {
+namespace XPath {
+
+static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
+{
+ ASSERT(parents.size() >= depth + 1);
+ return parents[parents.size() - 1 - depth];
+}
+
+static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parentMatrix, bool mayContainAttributeNodes)
+{
+ ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.
+ unsigned minDepth = UINT_MAX;
+ for (unsigned i = from; i < to; ++i) {
+ unsigned depth = parentMatrix[i].size() - 1;
+ if (minDepth > depth)
+ minDepth = depth;
+ }
+
+ // Find the common ancestor.
+ unsigned commonAncestorDepth = minDepth;
+ Node* commonAncestor;
+ while (true) {
+ commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
+ if (commonAncestorDepth == 0)
+ break;
+
+ bool allEqual = true;
+ for (unsigned i = from + 1; i < to; ++i) {
+ if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
+ allEqual = false;
+ break;
+ }
+ }
+ if (allEqual)
+ break;
+
+ --commonAncestorDepth;
+ }
+
+ 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)
+ 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.
+ unsigned sortedEnd = from;
+ // FIXME: namespace nodes are not implemented.
+ for (unsigned i = sortedEnd; i < to; ++i) {
+ Node* n = parentMatrix[i][0];
+ if (n->isAttributeNode() && static_cast<Attr*>(n)->ownerElement() == commonAncestor)
+ parentMatrix[i].swap(parentMatrix[sortedEnd++]);
+ }
+ if (sortedEnd != from) {
+ if (to - sortedEnd > 1)
+ sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
+ return;
+ }
+ }
+
+ // Children nodes of the common ancestor induce a subdivision of our node-set.
+ // Sort it according to this subdivision, and recursively sort each group.
+ HashSet<Node*> parentNodes;
+ for (unsigned i = from; i < to; ++i)
+ parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
+
+ 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(n)) {
+ 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);
+
+ ASSERT(previousGroupEnd != groupEnd);
+ previousGroupEnd = groupEnd;
+#ifndef NDEBUG
+ parentNodes.remove(n);
+#endif
+ }
+ }
+
+ ASSERT(parentNodes.isEmpty());
+}
+
+void NodeSet::sort() const
+{
+ if (m_isSorted)
+ return;
+
+ unsigned nodeCount = m_nodes.size();
+ if (nodeCount < 2) {
+ const_cast<bool&>(m_isSorted) = true;
+ return;
+ }
+
+ bool containsAttributeNodes = false;
+
+ Vector<Vector<Node*> > parentMatrix(nodeCount);
+ for (unsigned i = 0; i < nodeCount; ++i) {
+ Vector<Node*>& parentsVector = parentMatrix[i];
+ Node* n = m_nodes[i].get();
+ parentsVector.append(n);
+ if (n->isAttributeNode()) {
+ n = static_cast<Attr*>(n)->ownerElement();
+ parentsVector.append(n);
+ containsAttributeNodes = true;
+ }
+ while ((n = n->parent()))
+ parentsVector.append(n);
+ }
+ 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.
+ Vector<RefPtr<Node> > sortedNodes;
+ sortedNodes.reserveInitialCapacity(nodeCount);
+ for (unsigned i = 0; i < nodeCount; ++i)
+ sortedNodes.append(parentMatrix[i][0]);
+
+ const_cast<Vector<RefPtr<Node> >& >(m_nodes).swap(sortedNodes);
+}
+
+void NodeSet::reverse()
+{
+ if (m_nodes.isEmpty())
+ return;
+
+ unsigned from = 0;
+ unsigned to = m_nodes.size() - 1;
+ while (from < to) {
+ m_nodes[from].swap(m_nodes[to]);
+ ++from;
+ --to;
+ }
+}
+
+Node* NodeSet::firstNode() const
+{
+ if (isEmpty())
+ return 0;
+
+ sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
+ return m_nodes.at(0).get();
+}
+
+Node* NodeSet::anyNode() const
+{
+ if (isEmpty())
+ return 0;
+
+ return m_nodes.at(0).get();
+}
+
+}
+}
+
+#endif // ENABLE(XPATH)