mmidy 00/02/04 12:41:51
Modified: src/org/apache/xalan/xslt NodeSorter.java
Log:
Changes to improve performance of xsl:sort
Revision Changes Path
1.6 +154 -27 xml-xalan/src/org/apache/xalan/xslt/NodeSorter.java
Index: NodeSorter.java
===================================================================
RCS file: /home/cvs/xml-xalan/src/org/apache/xalan/xslt/NodeSorter.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- NodeSorter.java 2000/01/31 20:52:31 1.5
+++ NodeSorter.java 2000/02/04 20:41:51 1.6
@@ -76,7 +76,7 @@
/**
* TODO: Adjust this for locale.
*/
- NumberFormat m_formatter = NumberFormat.getNumberInstance();
+ NumberFormat m_formatter = NumberFormat.getNumberInstance();
/**
* Construct a NodeSorter, passing in the XSL Processor
@@ -103,30 +103,70 @@
m_keys = keys;
// QuickSort2(v, 0, v.size() - 1 );
int n = v.size();
- NodeVector scratchVector = new NodeVector(n);
- mergesort(v, scratchVector, 0, n - 1, support);
+
+ // Create a vector of node compare elements
+ // based on the input vector of nodes
+ Vector nodes = new Vector();
+ for (int i = 0; i<n; i++)
+ {
+ NodeCompareElem elem = new NodeCompareElem((Node)v.elementAt(i));
+ nodes.addElement(elem);
+ }
+ Vector scratchVector = new Vector();
+ mergesort(nodes, scratchVector, 0, n - 1, support);
+
+ // return sorted vector of nodes
+ for (int i = 0; i<n; i++)
+ {
+ v.setElementAt(((NodeCompareElem)nodes.elementAt(i)).m_node, i);
+ }
+ // old code...
+ //NodeVector scratchVector = new NodeVector(n);
+ //mergesort(v, scratchVector, 0, n - 1, support);
}
/**
* Return the results of a compare of two nodes.
* TODO: Optimize compare -- cache the getStringExpr results, key by
m_selectPat + hash of node.
*/
- int compare(Node n1, Node n2, int kIndex, XPathSupport support)
+ int compare(NodeCompareElem n1, NodeCompareElem n2, int kIndex,
XPathSupport support)
throws org.xml.sax.SAXException,
java.net.MalformedURLException,
java.io.FileNotFoundException,
java.io.IOException
{
int result = 0;
- NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex);
- XObject r1 = k.m_selectPat.execute(m_execContext, n1,
k.m_namespaceContext);
- XObject r2 = k.m_selectPat.execute(m_execContext, n2,
k.m_namespaceContext);
-
+
+ NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex);
if(k.m_treatAsNumbers)
{
- double n1Num = r1.num();
- double n2Num = r2.num();
-
+ double n1Num, n2Num;
+ if (kIndex ==0)
+ {
+ n1Num = ((Double)n1.m_key1Value).doubleValue();
+ n2Num = ((Double)n2.m_key1Value).doubleValue();
+ }
+ else if (kIndex ==1)
+ {
+ n1Num = ((Double)n1.m_key2Value).doubleValue();
+ n2Num = ((Double)n2.m_key2Value).doubleValue();
+ }
+ /* Leave this in case we decide to use an array later
+ if (kIndex < maxkey)
+ {
+ double n1Num = (double)n1.m_keyValue[kIndex];
+ double n2Num = (double)n2.m_keyValue[kIndex];
+ }*/
+ else
+ {
+ // Get values dynamically
+ XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
k.m_namespaceContext);
+ XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
k.m_namespaceContext);
+
+ n1Num = r1.num();
+ n2Num = r2.num();
+ }
+
if((n1Num == n2Num) && ((kIndex+1) < m_keys.size()))
{
result = compare(n1, n2, kIndex+1, support);
@@ -134,24 +174,51 @@
else
{
double diff = n1Num - n2Num;
+ // process order parameter
result = (int)((diff < 0.0)
? (k.m_descending ? 1 : -1)
: (diff > 0.0) ? (k.m_descending ? -1 : 1)
: 0);
}
- }
+ }// end treat as numbers
else
{
- String n1String = r1.str();
- String n2String = r2.str();
-
- result = k.m_col.compare(n1String, n2String);
-
+ CollationKey n1String, n2String;
+ if (kIndex == 0)
+ {
+ n1String = (CollationKey)n1.m_key1Value;
+ n2String = (CollationKey)n2.m_key1Value;
+ }
+ else if (kIndex == 1)
+ {
+ n1String = (CollationKey)n1.m_key2Value;
+ n2String = (CollationKey)n2.m_key2Value;
+ }
+ /* Leave this in case we decide to use an array later
+ if (kIndex < maxkey)
+ {
+ String n1String = (String)n1.m_keyValue[kIndex];
+ String n2String = (String)n2.m_keyValue[kIndex];
+ }*/
+ else
+ {
+ // Get values dynamically
+ XObject r1 = k.m_selectPat.execute(m_execContext, n1.m_node,
k.m_namespaceContext);
+ XObject r2 = k.m_selectPat.execute(m_execContext, n2.m_node,
k.m_namespaceContext);
+
+ n1String = k.m_col.getCollationKey(r1.str());
+ n2String = k.m_col.getCollationKey(r2.str());
+ }
+
+ // Use collation keys for faster compare, but note that whitespaces
+ // etc... are treated differently from if we were comparing Strings.
+ result = n1String.compareTo(n2String);
+
//Process caseOrder parameter
if (k.m_caseOrderUpper)
{
- String tempN1 = n1String.toLowerCase();
- String tempN2 = n2String.toLowerCase();
+ String tempN1 = n1String.getSourceString().toLowerCase();
+ String tempN2 = n2String.getSourceString().toLowerCase();
if (tempN1.equals(tempN2))
{
//java defaults to upper case is greater.
@@ -164,7 +231,8 @@
{
result = -result;
}
- }
+ }//end else
+
if(0 == result)
{
if((kIndex+1) < m_keys.size())
@@ -179,7 +247,7 @@
// if(r1.getType() == r1.CLASS_NODESET)
// {
- result = MutableNodeListImpl.isNodeAfter(n1, n2, support) ? -1 : 1;
+ result = MutableNodeListImpl.isNodeAfter(n1.m_node, n2.m_node,
support) ? -1 : 1;
// }
}
return result;
@@ -192,7 +260,7 @@
* maintains the original document order of the input if
* the order isn't changed by the sort.
*/
- void mergesort(NodeVector a, NodeVector b, int l, int r, XPathSupport
support)
+ void mergesort(Vector a, Vector b, int l, int r, XPathSupport support)
throws org.xml.sax.SAXException,
java.net.MalformedURLException,
java.io.FileNotFoundException,
@@ -207,20 +275,30 @@
for(i = m; i >= l; i--)
{
// b[i] = a[i];
- b.setElementAt(a.elementAt(i), i);
+ // Use insert if we need to increment vector size.
+ if (i >= b.size())
+ b.insertElementAt(a.elementAt(i), i);
+ else
+ b.setElementAt(a.elementAt(i), i);
}
i=l;
for(j = (m + 1); j <= r; j++)
{
// b[r+m+1-j] = a[j];
- b.setElementAt(a.elementAt(j), r+m+1-j);
+ if (r+m+1-j>= b.size())
+ b.insertElementAt(a.elementAt(j), r+m+1-j);
+ else
+ b.setElementAt(a.elementAt(j), r+m+1-j);
}
j=r;
int compVal;
for(k = l; k <= r; k++)
{
// if(b[i] < b[j])
- compVal = compare((Node)b.elementAt(i), (Node)b.elementAt(j), 0,
support);
+ if (i == j)
+ compVal = -1;
+ else
+ compVal = compare((NodeCompareElem)b.elementAt(i),
(NodeCompareElem)b.elementAt(j), 0, support);
if(compVal < 0)
{
@@ -252,7 +330,7 @@
* @param lo0 left boundary of array partition
* @param hi0 right boundary of array partition
*/
- private void QuickSort2(Vector v, int lo0, int hi0, XPathSupport support)
+/* private void QuickSort2(Vector v, int lo0, int hi0, XPathSupport support)
throws org.xml.sax.SAXException,
java.net.MalformedURLException,
java.io.FileNotFoundException,
@@ -307,7 +385,7 @@
QuickSort2( v, lo, hi0, support );
}
}
- } // end QuickSort2
+ } // end QuickSort2 */
/**
* Simple function to swap two elements in
@@ -319,6 +397,55 @@
v.setElementAt(v.elementAt(j), i);
v.setElementAt(node, j);
}
+
+ class NodeCompareElem
+ {
+ Node m_node;
+ // This maxkey value was chosen arbitrarily. We are assuming that the
+ // maxkey + 1 keys will only hit fairly rarely and therefore, we
+ // will get the node values for those keys dynamically.
+ int maxkey = 2;
+ // Keep this in case we decide to use an array. Right now
+ // using two variables is cheaper.
+ //Object[] m_KeyValue = new Object[2];
+ Object m_key1Value;
+ Object m_key2Value;
+
+ NodeCompareElem(Node node) throws org.xml.sax.SAXException
+ {
+ m_node = node;
+ if (!m_keys.isEmpty())
+ {
+ NodeSortKey k1 = (NodeSortKey)m_keys.elementAt(0);
+ XObject r = k1.m_selectPat.execute(m_execContext, node,
k1.m_namespaceContext);
+ if(k1.m_treatAsNumbers)
+ m_key1Value = new Double(r.num());
+ else
+ m_key1Value = k1.m_col.getCollationKey(r.str());
+
+ if (m_keys.size()>1)
+ {
+ NodeSortKey k2 = (NodeSortKey)m_keys.elementAt(1);
+ XObject r2 = k2.m_selectPat.execute(m_execContext, node,
k2.m_namespaceContext);
+ if(k2.m_treatAsNumbers)
+ m_key2Value = new Double(r2.num());
+ else
+ m_key2Value = k2.m_col.getCollationKey(r2.str());
+ }
+ /* Leave this in case we decide to use an array later
+ while (kIndex <= m_keys.size() && kIndex < maxkey)
+ {
+ NodeSortKey k = (NodeSortKey)m_keys.elementAt(kIndex);
+ XObject r = k.m_selectPat.execute(m_execContext, node,
k.m_namespaceContext);
+ if(k.m_treatAsNumbers)
+ m_KeyValue[kIndex] = r.num();
+ else
+ m_KeyValue[kIndex] = r.str();
+ } */
+
+ } // end if not empty
+ }
+ } // end NodeCompareElem class
}
