Back to index

lightning-sunbird  0.9+nobinonly
txNodeSorter.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is TransforMiiX XSLT processor code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Jonas Sicking.
00019  * Portions created by the Initial Developer are Copyright (C) 2001
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Jonas Sicking <sicking@bigfoot.com>
00024  *   Peter Van der Beken <peterv@propagandism.org>
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either the GNU General Public License Version 2 or later (the "GPL"), or
00028  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 #include "txNodeSorter.h"
00041 #include "txExecutionState.h"
00042 #include "txXPathResultComparator.h"
00043 #include "txAtoms.h"
00044 #include "txNodeSetContext.h"
00045 #include "ExprResult.h"
00046 #include "Expr.h"
00047 #include "txStringUtils.h"
00048 #include "prmem.h"
00049 #include "nsQuickSort.h"
00050 
00051 /*
00052  * Sorts Nodes as specified by the W3C XSLT 1.0 Recommendation
00053  */
00054 
00055 txNodeSorter::txNodeSorter() : mNKeys(0)
00056 {
00057 }
00058 
00059 txNodeSorter::~txNodeSorter()
00060 {
00061     txListIterator iter(&mSortKeys);
00062     while (iter.hasNext()) {
00063         SortKey* key = (SortKey*)iter.next();
00064         delete key->mComparator;
00065         delete key;
00066     }
00067 }
00068 
00069 nsresult
00070 txNodeSorter::addSortElement(Expr* aSelectExpr, Expr* aLangExpr,
00071                              Expr* aDataTypeExpr, Expr* aOrderExpr,
00072                              Expr* aCaseOrderExpr, txIEvalContext* aContext)
00073 {
00074     SortKey* key = new SortKey;
00075     NS_ENSURE_TRUE(key, NS_ERROR_OUT_OF_MEMORY);
00076     nsresult rv = NS_OK;
00077 
00078     // Select
00079     key->mExpr = aSelectExpr;
00080 
00081     // Order
00082     MBool ascending = MB_TRUE;
00083     if (aOrderExpr) {
00084         nsRefPtr<txAExprResult> exprRes;
00085         rv = aOrderExpr->evaluate(aContext, getter_AddRefs(exprRes));
00086         NS_ENSURE_SUCCESS(rv, rv);
00087 
00088         nsAutoString attrValue;
00089         exprRes->stringValue(attrValue);
00090         
00091         if (TX_StringEqualsAtom(attrValue, txXSLTAtoms::descending)) {
00092             ascending = MB_FALSE;
00093         }
00094         else if (!TX_StringEqualsAtom(attrValue, txXSLTAtoms::ascending)) {
00095             delete key;
00096             // XXX ErrorReport: unknown value for order attribute
00097             return NS_ERROR_XSLT_BAD_VALUE;
00098         }
00099     }
00100 
00101 
00102     // Create comparator depending on datatype
00103     nsAutoString dataType;
00104     if (aDataTypeExpr) {
00105         nsRefPtr<txAExprResult> exprRes;
00106         rv = aDataTypeExpr->evaluate(aContext, getter_AddRefs(exprRes));
00107         NS_ENSURE_SUCCESS(rv, rv);
00108 
00109         exprRes->stringValue(dataType);
00110     }
00111 
00112     if (!aDataTypeExpr || TX_StringEqualsAtom(dataType, txXSLTAtoms::text)) {
00113         // Text comparator
00114         
00115         // Language
00116         nsAutoString lang;
00117         if (aLangExpr) {
00118             nsRefPtr<txAExprResult> exprRes;
00119             rv = aLangExpr->evaluate(aContext, getter_AddRefs(exprRes));
00120             NS_ENSURE_SUCCESS(rv, rv);
00121 
00122             exprRes->stringValue(lang);
00123         }
00124 
00125         // Case-order 
00126         MBool upperFirst = PR_FALSE;
00127         if (aCaseOrderExpr) {
00128             nsRefPtr<txAExprResult> exprRes;
00129             rv = aCaseOrderExpr->evaluate(aContext, getter_AddRefs(exprRes));
00130             NS_ENSURE_SUCCESS(rv, rv);
00131 
00132             nsAutoString attrValue;
00133             exprRes->stringValue(attrValue);
00134 
00135             if (TX_StringEqualsAtom(attrValue, txXSLTAtoms::upperFirst)) {
00136                 upperFirst = PR_TRUE;
00137             }
00138             else if (!TX_StringEqualsAtom(attrValue,
00139                                           txXSLTAtoms::lowerFirst)) {
00140                 delete key;
00141                 // XXX ErrorReport: unknown value for case-order attribute
00142                 return NS_ERROR_XSLT_BAD_VALUE;
00143             }
00144         }
00145 
00146         key->mComparator = new txResultStringComparator(ascending,
00147                                                         upperFirst,
00148                                                         lang);
00149         NS_ENSURE_TRUE(key->mComparator, NS_ERROR_OUT_OF_MEMORY);
00150     }
00151     else if (TX_StringEqualsAtom(dataType, txXSLTAtoms::number)) {
00152         // Number comparator
00153         key->mComparator = new txResultNumberComparator(ascending);
00154         NS_ENSURE_TRUE(key->mComparator, NS_ERROR_OUT_OF_MEMORY);
00155     }
00156     else {
00157         // XXX ErrorReport: unknown data-type
00158         delete key;
00159 
00160         return NS_ERROR_XSLT_BAD_VALUE;
00161     }
00162 
00163     mSortKeys.add(key);
00164     mNKeys++;
00165 
00166     return NS_OK;
00167 }
00168 
00169 nsresult
00170 txNodeSorter::sortNodeSet(txNodeSet* aNodes, txExecutionState* aEs,
00171                           txNodeSet** aResult)
00172 {
00173     if (mNKeys == 0 || aNodes->isEmpty()) {
00174         NS_ADDREF(*aResult = aNodes);
00175 
00176         return NS_OK;
00177     }
00178 
00179     *aResult = nsnull;
00180 
00181     nsRefPtr<txNodeSet> sortedNodes;
00182     nsresult rv = aEs->recycler()->getNodeSet(getter_AddRefs(sortedNodes));
00183     NS_ENSURE_SUCCESS(rv, rv);
00184 
00185     txNodeSetContext* evalContext = new txNodeSetContext(aNodes, aEs);
00186     NS_ENSURE_TRUE(evalContext, NS_ERROR_OUT_OF_MEMORY);
00187 
00188     rv = aEs->pushEvalContext(evalContext);
00189     NS_ENSURE_SUCCESS(rv, rv);
00190 
00191     // Create and set up memoryblock for sort-values and indexarray
00192     PRUint32 len = NS_STATIC_CAST(PRUint32, aNodes->size());
00193     void* mem = PR_Malloc(len * (sizeof(PRUint32) + mNKeys * sizeof(TxObject*)));
00194     NS_ENSURE_TRUE(mem, NS_ERROR_OUT_OF_MEMORY);
00195 
00196     PRUint32* indexes = NS_STATIC_CAST(PRUint32*, mem);
00197     TxObject** sortValues = NS_REINTERPRET_CAST(TxObject**, indexes + len);
00198 
00199     PRUint32 i;
00200     for (i = 0; i < len; ++i) {
00201         indexes[i] = i;
00202     }
00203     memset(sortValues, 0, len * mNKeys * sizeof(TxObject*));
00204 
00205     // Sort the indexarray
00206     SortData sortData;
00207     sortData.mNodeSorter = this;
00208     sortData.mContext = evalContext;
00209     sortData.mSortValues = sortValues;
00210     sortData.mRv = NS_OK;
00211     NS_QuickSort(indexes, len, sizeof(PRUint32), compareNodes, &sortData);
00212 
00213     // Delete these here so we don't have to deal with them at every possible
00214     // failurepoint
00215     PRUint32 numSortValues = len * mNKeys;
00216     for (i = 0; i < numSortValues; ++i) {
00217         delete sortValues[i];
00218     }
00219 
00220     if (NS_FAILED(sortData.mRv)) {
00221         PR_Free(mem);
00222         // The txExecutionState owns the evalcontext so no need to handle it
00223         return sortData.mRv;
00224     }
00225 
00226     // Insert nodes in sorted order in new nodeset
00227     for (i = 0; i < len; ++i) {
00228         rv = sortedNodes->append(aNodes->get(indexes[i]));
00229         if (NS_FAILED(rv)) {
00230             PR_Free(mem);
00231             // The txExecutionState owns the evalcontext so no need to handle it
00232             return rv;
00233         }
00234     }
00235 
00236     PR_Free(mem);
00237     delete aEs->popEvalContext();
00238 
00239     NS_ADDREF(*aResult = sortedNodes);
00240 
00241     return NS_OK;
00242 }
00243 
00244 // static
00245 int
00246 txNodeSorter::compareNodes(const void* aIndexA, const void* aIndexB,
00247                            void* aSortData)
00248 {
00249     SortData* sortData = NS_STATIC_CAST(SortData*, aSortData);
00250     NS_ENSURE_SUCCESS(sortData->mRv, -1);
00251 
00252     txListIterator iter(&sortData->mNodeSorter->mSortKeys);
00253     PRUint32 indexA = *NS_STATIC_CAST(const PRUint32*, aIndexA);
00254     PRUint32 indexB = *NS_STATIC_CAST(const PRUint32*, aIndexB);
00255     TxObject** sortValuesA = sortData->mSortValues +
00256                              indexA * sortData->mNodeSorter->mNKeys;
00257     TxObject** sortValuesB = sortData->mSortValues +
00258                              indexB * sortData->mNodeSorter->mNKeys;
00259 
00260     int i;
00261     // Step through each key until a difference is found
00262     for (i = 0; i < sortData->mNodeSorter->mNKeys; ++i) {
00263         SortKey* key = (SortKey*)iter.next();
00264         // Lazy create sort values
00265         if (!sortValuesA[i] &&
00266             !calcSortValue(sortValuesA[i], key, sortData, indexA)) {
00267             return -1;
00268         }
00269         if (!sortValuesB[i] &&
00270             !calcSortValue(sortValuesB[i], key, sortData, indexB)) {
00271             return -1;
00272         }
00273 
00274         // Compare node values
00275         int compRes = key->mComparator->compareValues(sortValuesA[i],
00276                                                       sortValuesB[i]);
00277         if (compRes != 0)
00278             return compRes;
00279     }
00280     // All keys have the same value for these nodes
00281 
00282     return indexA - indexB;
00283 }
00284 
00285 //static
00286 PRBool
00287 txNodeSorter::calcSortValue(TxObject*& aSortValue, SortKey* aKey,
00288                             SortData* aSortData, PRUint32 aNodeIndex)
00289 {
00290     aSortData->mContext->setPosition(aNodeIndex + 1); // position is 1-based
00291     nsRefPtr<txAExprResult> res;
00292     nsresult rv = aKey->mExpr->evaluate(aSortData->mContext,
00293                                         getter_AddRefs(res));
00294     if (NS_FAILED(rv)) {
00295         aSortData->mRv = rv;
00296         return PR_FALSE;
00297     }
00298 
00299     aSortValue = aKey->mComparator->createSortableValue(res);
00300     if (!aSortValue) {
00301         aSortData->mRv = NS_ERROR_OUT_OF_MEMORY;
00302         return PR_FALSE;
00303     }
00304     
00305     return PR_TRUE;
00306 }