You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xalan.apache.org by db...@apache.org on 2001/05/10 19:59:16 UTC
cvs commit: xml-xalan/c/src/XSLT NodeSorter.cpp NodeSorter.hpp
dbertoni 01/05/10 10:59:16
Modified: c/src/XSLT NodeSorter.cpp NodeSorter.hpp
Log:
New and improved sort caching implementation.
Revision Changes Path
1.21 +146 -180 xml-xalan/c/src/XSLT/NodeSorter.cpp
Index: NodeSorter.cpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/XSLT/NodeSorter.cpp,v
retrieving revision 1.20
retrieving revision 1.21
diff -u -r1.20 -r1.21
--- NodeSorter.cpp 2001/04/11 02:34:12 1.20
+++ NodeSorter.cpp 2001/05/10 17:59:11 1.21
@@ -81,7 +81,11 @@
-NodeSorter::NodeSorter()
+NodeSorter::NodeSorter() :
+ m_numberResultsCache(),
+ m_stringResultsCache(),
+ m_keys(),
+ m_scratchVector()
{
}
@@ -94,26 +98,30 @@
void
-NodeSorter::sort(
- StylesheetExecutionContext& executionContext,
- const MutableNodeRefList& theList,
- NodeVectorType& v,
- const NodeSortKeyVectorType& keys) const
+NodeSorter::sort(StylesheetExecutionContext& executionContext)
{
+ assert(m_scratchVector.size() > 0);
+
+ // Make sure the caches are cleared when we're done...
+ CollectionClearGuard<NumberResultsCacheType> guard1(m_numberResultsCache);
+ CollectionClearGuard<StringResultsCacheType> guard2(m_stringResultsCache);
+
+ NodeSortKeyCompare theComparer(
+ executionContext,
+ *this,
+ m_scratchVector,
+ m_keys);
+
#if !defined(XALAN_NO_NAMESPACES)
using std::stable_sort;
#endif
- NodeSortKeyCompare theComparer(executionContext,
- theList,
- v,
- keys);
-
// Use the stl sort algorithm, which will use our compare functor,
// which returns true if first less than second
- stable_sort(v.begin(),
- v.end(),
- theComparer);
+ stable_sort(
+ m_scratchVector.begin(),
+ m_scratchVector.end(),
+ theComparer);
}
@@ -121,40 +129,41 @@
void
NodeSorter::sort(
StylesheetExecutionContext& executionContext,
- MutableNodeRefList& theList,
- const NodeSortKeyVectorType& keys) const
+ MutableNodeRefList& theList)
{
- const unsigned int theLength = theList.getLength();
+ if (m_keys.size() > 0)
+ {
+ const unsigned int theLength = theList.getLength();
- // Copy the nodes to a vector...
- NodeVectorType theNodes;
+ // Copy the nodes to a vector...
+ assert(m_scratchVector.size() == 0);
- theNodes.reserve(theLength);
+ // Make sure the scratch vector is cleared when we're done...
+ CollectionClearGuard<NodeVectorType> guard(m_scratchVector);
- unsigned int i = 0;
+ m_scratchVector.reserve(theLength);
- for (; i < theLength; ++i)
- {
- theNodes.push_back(theList.item(i));
- }
+ unsigned int i = 0;
- // Do the sort...
- sort(
- executionContext,
- theList,
- theNodes,
- keys);
- assert(theNodes.size() == NodeVectorType::size_type(theLength));
+ for (; i < theLength; ++i)
+ {
+ m_scratchVector.push_back(NodeVectorType::value_type(theList.item(i), i));
+ }
- // Copy the nodes back to the list in sorted order.
- theList.clear();
+ // Do the sort...
+ sort(executionContext);
+ assert(m_scratchVector.size() == NodeVectorType::size_type(theLength));
- for (i = 0; i < theLength; ++i)
- {
- theList.addNode(theNodes[i]);
- }
+ // Copy the nodes back to the list in sorted order.
+ theList.clear();
- assert(theList.getLength() == theLength);
+ for (i = 0; i < theLength; ++i)
+ {
+ theList.addNode(m_scratchVector[i].m_node);
+ }
+
+ assert(theList.getLength() == theLength);
+ }
}
@@ -183,21 +192,24 @@
-NodeSorter::NodeSortKeyCompare::result_type
-NodeSorter::NodeSortKeyCompare::operator()(
- first_argument_type theLHS,
- second_argument_type theRHS,
- unsigned int theKeyIndex) const
+int
+NodeSorter::NodeSortKeyCompare::compare(
+ first_argument_type theLHS,
+ second_argument_type theRHS,
+ unsigned int theKeyIndex) const
{
- result_type theResult = false;
+ assert(theLHS.m_node != 0 && theRHS.m_node != 0);
+ assert(theKeyIndex < m_nodeSortKeys.size());
+ int theResult = 0;
+
const NodeSortKey& theKey = m_nodeSortKeys[theKeyIndex];
// Compare as numbers
if(theKey.getTreatAsNumbers() == true)
{
- double n1Num = getNumberResult(theKey, theLHS);
- double n2Num = getNumberResult(theKey, theRHS);
+ double n1Num = getNumberResult(theKey, theKeyIndex, theLHS);
+ double n2Num = getNumberResult(theKey, theKeyIndex, theRHS);
if (DoubleSupport::isNaN(n1Num))
n1Num = 0.0;
@@ -205,100 +217,38 @@
if (DoubleSupport::isNaN(n2Num))
n2Num = 0.0;
- if(n1Num == n2Num &&
- (theKeyIndex + 1 ) < m_nodeSortKeys.size())
+ if (DoubleSupport::lessThan(n1Num, n2Num) == true)
{
- theResult = operator()(theLHS, theRHS, theKeyIndex + 1);
+ theResult = -1;
}
- else
+ else if (DoubleSupport::greaterThan(n1Num, n2Num) == true)
{
- const double diff = n1Num - n2Num;
-
- if (diff == 0.0)
- {
- // The nodes are equal, so if theLHS is
- // before theRHS, return true.
- theResult = isNodeBefore(theLHS, theRHS);
- }
- else if (theKey.getDescending() == true)
- {
- theResult = diff < 0.0 ? false : true;
- }
- else
- {
- theResult = diff < 0.0 ? true : false;
- }
+ theResult = 1;
}
}
// Compare as strings
else
{
-
- const int theCompareResult = doCollationCompare(
+ theResult = doCollationCompare(
m_executionContext,
-#if defined(XALAN_SORT_CACHE_RESULTS)
- getStringResult(theKey, theLHS),
- getStringResult(theKey, theRHS),
-#else
- getStringResult(theKey, theLHS)->str(),
- getStringResult(theKey, theRHS)->str(),
-#endif
+ getStringResult(theKey, theKeyIndex, theLHS)->str(),
+ getStringResult(theKey, theKeyIndex, theRHS)->str(),
theKey.getLanguageString());
+ }
- if(0 == theCompareResult)
- {
- if ((theKeyIndex + 1 ) < m_nodeSortKeys.size())
- {
- theResult = operator()(theLHS, theRHS, theKeyIndex + 1);
- }
- }
- else
+ // If they're not equal, the flip things if the
+ // order is descending...
+ if (theResult != 0)
+ {
+ if (theKey.getDescending() == true)
{
- if (theCompareResult == 0)
- {
- // The nodes are equal, so if theLHS is
- // before theRHS, return true.
- theResult = isNodeBefore(theLHS, theRHS);
- }
- else if (theKey.getDescending() == true)
- {
- theResult = theCompareResult < 0 ? false : true;
- }
- else
- {
- theResult = theCompareResult < 0 ? true : false;
- }
+ theResult = -theResult;
}
}
-
- return theResult;
-}
-
-
-
-bool
-NodeSorter::NodeSortKeyCompare::isNodeBefore(
- const XalanNode* node1,
- const XalanNode* node2) const
-{
- bool theResult = true;
-
- const unsigned int theLength = m_list.getLength();
-
- for(unsigned int i = 0; i < theLength; ++i)
+ else if(theKeyIndex + 1 < m_nodeSortKeys.size())
{
- const XalanNode* const theCurrentNode = m_list.item(i);
-
- if (theCurrentNode == node1)
- {
- break;
- }
- else if (theCurrentNode == node2)
- {
- theResult = false;
-
- break;
- }
+ // They're equal, so process the next key, if any...
+ theResult = compare(theLHS, theRHS, theKeyIndex + 1);
}
return theResult;
@@ -308,93 +258,109 @@
double
NodeSorter::NodeSortKeyCompare::getNumberResult(
- const NodeSortKey& theKey,
- XalanNode* node) const
+ const NodeSortKey& theKey,
+ unsigned int theKeyIndex,
+ first_argument_type theEntry) const
{
const XPath* const xpath = theKey.getSelectPattern();
assert(xpath != 0);
-#if !defined(XALAN_SORT_CACHE_RESULTS)
- return xpath->execute(node, *theKey.getPrefixResolver(), m_executionContext)->num();
-#else
- const NumberResultsCacheMapType::const_iterator i =
- m_numberResultsCache.find(xpath);
+ typedef NodeSorter::NumberResultsCacheType NumberResultsCacheType;
- if (i != m_numberResultsCache.end())
+ NumberResultsCacheType& theCache =
+ m_sorter.m_numberResultsCache;
+
+ if (theCache.size() == 0)
{
- const NumberResultsNodeCacheMapType::const_iterator j =
- (*i).second.find(node);
+ theCache.resize(m_nodeSortKeys.size());
+ }
- if (j != (*i).second.end())
+ // We need a dummy value to indicate that a slot has
+ // never been evaluated. 0 is probably a bad idea,
+ // as is NaN, since that would be fairly common with
+ // values that are not convertible to a number. This
+ // is just a not-so-random number...
+ const double theDummyValue = 135792468.0L;
+
+ if (theCache[theKeyIndex].size() != 0)
+ {
+ if (DoubleSupport::equal(theCache[theKeyIndex][theEntry.m_position], theDummyValue) == true)
{
- // Yuck!!!! Big ugly return here!!!
- return (*j).second;
+ theCache[theKeyIndex][theEntry.m_position] =
+ xpath->execute(theEntry.m_node, *theKey.getPrefixResolver(), m_executionContext)->num();
}
+
+ return theCache[theKeyIndex][theEntry.m_position];
}
+ else
+ {
+ theCache[theKeyIndex].resize(m_nodes.size());
- const XObjectPtr result(xpath->execute(node, *theKey.getPrefixResolver(), m_executionContext));
- assert(result.null() == false);
+#if !defined(XALAN_NO_NAMESPACES)
+ using std::fill;
+#endif
- const double theResult = result->num();
+ // Fill with the dummy value...
+ fill(
+ theCache[theKeyIndex].begin(),
+ theCache[theKeyIndex].end(),
+ theDummyValue);
-#if defined(XALAN_NO_MUTABLE)
- ((NodeSortKeyCompare*)this)->m_numberResultsCache[xpath][node] = theResult;
-#else
- m_numberResultsCache[xpath][node] = theResult;
-#endif
+ const XObjectPtr result(xpath->execute(theEntry.m_node, *theKey.getPrefixResolver(), m_executionContext));
+ assert(result.null() == false);
- return theResult;
-#endif
+ const double theResult = result->num();
+
+ theCache[theKeyIndex][theEntry.m_position] = theResult;
+
+ return theResult;
+ }
}
-#if !defined(XALAN_SORT_CACHE_RESULTS)
-const XObjectPtr
-#else
-const XalanDOMString&
-#endif
+const XObjectPtr&
NodeSorter::NodeSortKeyCompare::getStringResult(
- const NodeSortKey& theKey,
- XalanNode* node) const
+ const NodeSortKey& theKey,
+ unsigned int theKeyIndex,
+ first_argument_type theEntry) const
{
assert(theKey.getPrefixResolver() != 0);
const XPath* const xpath = theKey.getSelectPattern();
assert(xpath != 0);
-#if !defined(XALAN_SORT_CACHE_RESULTS)
- return xpath->execute(node, *theKey.getPrefixResolver(), m_executionContext);
-#else
- const StringResultsCacheMapType::const_iterator i =
- m_stringResultsCache.find(xpath);
+ typedef NodeSorter::StringResultsCacheType StringResultsCacheType;
- if (i != m_stringResultsCache.end())
+ StringResultsCacheType& theCache =
+ m_sorter.m_stringResultsCache;
+
+ if (theCache.size() == 0)
{
- const StringResultsNodeCacheMapType::const_iterator j =
- (*i).second.find(node);
+ theCache.resize(m_nodeSortKeys.size());
+ }
- if (j != (*i).second.end())
+ if (theCache[theKeyIndex].size() != 0)
+ {
+ if (theCache[theKeyIndex][theEntry.m_position].null() == true)
{
- // Yuck!!!! Big ugly return here!!!
- return (*j).second;
+ theCache[theKeyIndex][theEntry.m_position] =
+ xpath->execute(theEntry.m_node, *theKey.getPrefixResolver(), m_executionContext);
}
- }
- const XObjectPtr result(xpath->execute(node, *theKey.getPrefixResolver(), m_executionContext));
- assert(result.null() == false);
+ assert(theCache[theKeyIndex][theEntry.m_position].null() == false);
- const XalanDOMString& theResult = result->str();
+ return theCache[theKeyIndex][theEntry.m_position];
+ }
+ else
+ {
+ theCache[theKeyIndex].resize(m_nodes.size());
- XalanDOMString& theString =
-#if defined(XALAN_NO_MUTABLE)
- ((NodeSortKeyCompare*)this)->m_stringResultsCache[xpath][node];
-#else
- m_stringResultsCache[xpath][node];
-#endif
+ theCache[theKeyIndex][theEntry.m_position] =
+ xpath->execute(theEntry.m_node, *theKey.getPrefixResolver(), m_executionContext);
- assign(theString, theResult);
+ assert(theCache[theKeyIndex][theEntry.m_position].null() == false);
- return theString;
-#endif
+ return theCache[theKeyIndex][theEntry.m_position];
+ }
}
1.12 +96 -86 xml-xalan/c/src/XSLT/NodeSorter.hpp
Index: NodeSorter.hpp
===================================================================
RCS file: /home/cvs/xml-xalan/c/src/XSLT/NodeSorter.hpp,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- NodeSorter.hpp 2001/04/11 02:34:12 1.11
+++ NodeSorter.hpp 2001/05/10 17:59:12 1.12
@@ -70,74 +70,86 @@
#include <functional>
-#include <map>
#include <vector>
-#include "NodeSortKey.hpp"
+#include <XPath/XObject.hpp>
+#include <XSLT/NodeSortKey.hpp>
+
+
+
class MutableNodeRefList;
class StylesheetExecutionContext;
class XalanNode;
-class XObjectPtr;
class XPath;
/**
- * This class can sort vectors of DOM nodes according to a select pattern.
+ * This class can sort vectors of nodes according to a select pattern.
*/
- // TODO: Optimize this so it can reuse queries for each of the nodes.
class NodeSorter
{
public:
+ struct VectorEntry
+ {
+ public:
+
+ VectorEntry(
+ XalanNode* theNode,
+ unsigned int thePosition) :
+ m_node(theNode),
+ m_position(thePosition)
+ {
+ }
+
+ XalanNode* m_node;
+ unsigned int m_position;
+ };
+
#if defined(XALAN_NO_NAMESPACES)
- typedef vector<XalanNode*> NodeVectorType;
+ typedef vector<VectorEntry> NodeVectorType;
typedef vector<NodeSortKey> NodeSortKeyVectorType;
#else
- typedef std::vector<XalanNode*> NodeVectorType;
+ typedef std::vector<VectorEntry> NodeVectorType;
typedef std::vector<NodeSortKey> NodeSortKeyVectorType;
#endif
- /**
- * Construct a NodeSorter, passing in the XSL Processor so it can know how
- * to get the node data according to the proper whitespace rules.
- */
explicit
NodeSorter();
~NodeSorter();
+ NodeSortKeyVectorType&
+ getSortKeys()
+ {
+ return m_keys;
+ }
+
/**
* Given a list of nodes, sort each node according to the criteria in the
* keys. The list is assumed to be in document order.
*
* @param executionContext current execution context
* @param v list of Nodes
- * @param keys vector of NodeSortKeys
*/
void
sort(
StylesheetExecutionContext& executionContext,
- MutableNodeRefList& theList,
- const NodeSortKeyVectorType& keys) const;
-
- /*
- * TODO: Optimize compare -- cache the getStringExpr results,
- * key by m_selectPat + hash of node.
- */
+ MutableNodeRefList& theList);
/**
* Return the results of a compare of two nodes.
*/
#if defined(XALAN_NO_NAMESPACES)
- struct NodeSortKeyCompare : public binary_function<XalanNode*, XalanNode*, bool>
+ struct NodeSortKeyCompare : public binary_function<const NodeVectorType::value_type&, const NodeVectorType::value_type&, bool>
#else
- struct NodeSortKeyCompare : public std::binary_function<XalanNode*, XalanNode*, bool>
+ struct NodeSortKeyCompare : public std::binary_function<const NodeVectorType::value_type&, const NodeVectorType::value_type&, bool>
#endif
{
public:
@@ -151,90 +163,86 @@
*/
NodeSortKeyCompare(
StylesheetExecutionContext& executionContext,
- const MutableNodeRefList& theList,
+ NodeSorter& theSorter,
const NodeVectorType& theNodes,
const NodeSortKeyVectorType& theNodeSortKeys) :
m_executionContext(executionContext),
- m_list(theList),
+ m_sorter(theSorter),
m_nodes(theNodes),
m_nodeSortKeys(theNodeSortKeys)
-#if defined(XALAN_SORT_CACHE_RESULTS)
- ,
- m_numberResultsCache(),
- m_stringResultsCache()
-#endif
{
}
- /**
- * Compare two nodes
- *
- * @param executionContext current execution context
- * @param theNodes vector or nodes to be sorted
- * @param theNodeSortKeys vector of keys upon which to sort
- */
+ /**
+ * Compare two nodes, returning a value to indicate the
+ * result
+ *
+ * @param theLHS the first node to compare
+ * @param theRHS the second node to compare
+ * @param theKeyIndex the index of the key to use
+ * @result < 0 if theLHS is less than theRHS, 0 if they are equal, and > 0 if theLHS is greater than theRHS
+ */
+ int
+ compare(
+ first_argument_type theLHS,
+ second_argument_type theRHS,
+ unsigned int theKeyIndex = 0) const;
+
+ /**
+ * Compare two nodes as a less predicate.
+ *
+ * @param theLHS the first node to compare
+ * @param theRHS the second node to compare
+ * @param theKeyIndex the index of the key to use
+ * @return true if theLHS is less than theRHS
+ */
result_type
- operator()(first_argument_type theLHS,
- second_argument_type theRHS,
- unsigned int theKeyIndex = 0) const;
+ operator()(
+ first_argument_type theLHS,
+ second_argument_type theRHS,
+ unsigned int theKeyIndex = 0) const
+ {
+ return compare(theLHS, theRHS, theKeyIndex) < 0 ? true : false;
+ }
protected:
- bool
- isNodeBefore(
- const XalanNode* node1,
- const XalanNode* node2) const;
-
double
getNumberResult(
- const NodeSortKey& theKey,
- XalanNode* node) const;
+ const NodeSortKey& theKey,
+ unsigned int theKeyIndex,
+ first_argument_type theEntry) const;
-#if !defined(XALAN_SORT_CACHE_RESULTS)
- const XObjectPtr
-#else
- const XalanDOMString&
-#endif
+ const XObjectPtr&
getStringResult(
- const NodeSortKey& theKey,
- XalanNode* node) const;
+ const NodeSortKey& theKey,
+ unsigned int theKeyIndex,
+ first_argument_type theEntry) const;
private:
StylesheetExecutionContext& m_executionContext;
- const MutableNodeRefList& m_list;
+ NodeSorter& m_sorter;
const NodeVectorType& m_nodes;
const NodeSortKeyVectorType& m_nodeSortKeys;
+ };
+ friend struct NodeSortKeyCompare;
+
#if defined(XALAN_NO_NAMESPACES)
- typedef map<const XalanNode*,
- double,
- less<const XalanNode*> > NumberResultsNodeCacheMapType;
-
- typedef map<const XalanNode*,
- XalanDOMString,
- less<const XalanNode*> > StringResultsNodeCacheMapType;
-
- typedef map<const XPath*,
- NumberResultsNodeCacheMapType,
- less<const XPath*> > NumberResultsCacheMapType;
-
- typedef map<const XPath*,
- StringResultsNodeCacheMapType,
- less<const XPath*> > StringResultsCacheMapType;
-#else
- typedef std::map<const XalanNode*, double> NumberResultsNodeCacheMapType;
- typedef std::map<const XalanNode*, XalanDOMString> StringResultsNodeCacheMapType;
+ typedef vector<double> NumberResultsCacheVectorType;
- typedef std::map<const XPath*, NumberResultsNodeCacheMapType> NumberResultsCacheMapType;
- typedef std::map<const XPath*, StringResultsNodeCacheMapType> StringResultsCacheMapType;
-#endif
+ typedef vector<XObjectPtr> StringResultsCacheMapType;
+
+ typedef vector<NumberResultsCacheVectorType> NumberResultsCacheType;
+ typedef vector<StringResultsCacheVectorType> StringResultsCacheType;
+#else
+ typedef std::vector<double> NumberResultsCacheVectorType;
+ typedef std::vector<XObjectPtr> StringResultsCacheVectorType;
-#if defined(XALAN_SORT_CACHE_RESULTS)
- mutable NumberResultsCacheMapType m_numberResultsCache;
- mutable StringResultsCacheMapType m_stringResultsCache;
+ typedef std::vector<NumberResultsCacheVectorType> NumberResultsCacheType;
+ typedef std::vector<StringResultsCacheVectorType> StringResultsCacheType;
#endif
- };
private:
@@ -243,16 +251,18 @@
* keys.
*
* @param executionContext current execution context
- * @param theList the original node list.
- * @param v vector of Nodes
- * @param keys vector of NodeSortKeys
*/
void
- sort(
- StylesheetExecutionContext& executionContext,
- const MutableNodeRefList& theList,
- NodeVectorType& v,
- const NodeSortKeyVectorType& keys) const;
+ sort(StylesheetExecutionContext& executionContext);
+
+ // Data members...
+ NumberResultsCacheType m_numberResultsCache;
+
+ StringResultsCacheType m_stringResultsCache;
+
+ NodeSortKeyVectorType m_keys;
+
+ NodeVectorType m_scratchVector;
};
---------------------------------------------------------------------
To unsubscribe, e-mail: xalan-cvs-unsubscribe@xml.apache.org
For additional commands, e-mail: xalan-cvs-help@xml.apache.org