Back to index

lightning-sunbird  0.9+nobinonly
nsXULSortService.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
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 mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Scott Putterman          <putterman@netscape.com>
00024  *   Pierre Phaneuf           <pp@ludusdesign.com>
00025  *   Chase Tingley            <tingley@sundell.net>
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either of the GNU General Public License Version 2 or later (the "GPL"),
00029  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK *****
00040  *
00041  * This Original Code has been modified by IBM Corporation.
00042  * Modifications made by IBM described herein are
00043  * Copyright (c) International Business Machines
00044  * Corporation, 2000
00045  *
00046  * Modifications to Mozilla code or documentation
00047  * identified per MPL Section 3.3
00048  *
00049  * Date         Modified by     Description of modification
00050  * 03/27/2000   IBM Corp.       Added PR_CALLBACK for Optlink
00051  *                               use in OS2
00052  */
00053 
00054 /*
00055   This file provides the implementation for the sort service manager.
00056  */
00057 
00058 #include "nsCOMPtr.h"
00059 #include "nsCRT.h"
00060 #include "nsIAtom.h"
00061 #include "nsIContent.h"
00062 #include "nsIDOMElement.h"
00063 #include "nsIDOMNode.h"
00064 #include "nsIDocument.h"
00065 #include "nsINameSpaceManager.h"
00066 #include "nsIRDFCompositeDataSource.h"
00067 #include "nsIRDFNode.h"
00068 #include "nsIRDFObserver.h"
00069 #include "nsIRDFService.h"
00070 #include "nsIServiceManager.h"
00071 #include "nsISupportsArray.h"
00072 #include "nsIURL.h"
00073 #include "nsRDFCID.h"
00074 #include "nsXULContentUtils.h"
00075 #include "nsString.h"
00076 #include "nsXPIDLString.h"
00077 #include "nsUnicharUtils.h"
00078 #include "rdf.h"
00079 #include "nsRDFSort.h"
00080 #include "nsVoidArray.h"
00081 #include "nsQuickSort.h"
00082 #include "nsIXULSortService.h"
00083 #include "prlog.h"
00084 #include "nsICollation.h"
00085 #include "nsCollationCID.h"
00086 #include "nsLayoutCID.h"
00087 #include "nsIDOMXULElement.h"
00088 #include "nsILocale.h"
00089 #include "nsILocaleService.h"
00090 #include "nsIRDFContainerUtils.h"
00091 #include "nsXULAtoms.h"
00092 #include "nsINodeInfo.h"
00093 
00094 
00096 
00097 static NS_DEFINE_CID(kRDFServiceCID,          NS_RDFSERVICE_CID);
00098 static NS_DEFINE_CID(kCollationFactoryCID,    NS_COLLATIONFACTORY_CID);
00099 static NS_DEFINE_CID(kRDFInMemoryDataSourceCID, NS_RDFINMEMORYDATASOURCE_CID);
00100 static NS_DEFINE_CID(kRDFContainerUtilsCID,   NS_RDFCONTAINERUTILS_CID);
00101 
00102 DEFINE_RDF_VOCAB(NC_NAMESPACE_URI, NC, BookmarkSeparator);
00103 
00104 typedef struct  _sortStruct  {
00105   PRBool firstFlag;
00106   nsCOMPtr<nsIRDFResource> sortProperty, sortProperty2;
00107   nsCOMPtr<nsIRDFResource> sortPropertyColl, sortPropertyColl2;
00108   nsCOMPtr<nsIRDFResource> sortPropertySort, sortPropertySort2;
00109 
00110   PRBool cacheFirstHint;
00111   nsCOMPtr<nsIRDFNode> cacheFirstNode;
00112   PRBool cacheIsFirstNodeCollationKey;
00113 
00114   nsCOMPtr<nsIRDFCompositeDataSource> db;
00115   nsCOMPtr<nsIRDFDataSource> mInner;
00116   nsCOMPtr<nsIContent> parentContainer;
00117   PRBool descendingSort;
00118   PRBool naturalOrderSort;
00119   PRBool inbetweenSeparatorSort;
00120 
00121 } sortStruct, *sortPtr;
00122 
00123 typedef struct {
00124   nsIContent * content;
00125   nsCOMPtr<nsIRDFResource> resource; 
00126   nsCOMPtr<nsIRDFNode> collationNode1;
00127   nsCOMPtr<nsIRDFNode> collationNode2;
00128   nsCOMPtr<nsIRDFNode> sortNode1;
00129   nsCOMPtr<nsIRDFNode> sortNode2;
00130   nsCOMPtr<nsIRDFNode> node1;
00131   nsCOMPtr<nsIRDFNode> node2;
00132   PRBool checkedCollation1;
00133   PRBool checkedCollation2;
00134   PRBool checkedSort1;
00135   PRBool checkedSort2;
00136   PRBool checkedNode1;
00137   PRBool checkedNode2;
00138 } contentSortInfo;
00139 
00140 int PR_CALLBACK inplaceSortCallback(const void *data1, const void *data2, void *privateData);
00141 int PR_CALLBACK testSortCallback(const void * data1, const void *data2, void *privateData);
00142 
00144 // ServiceImpl
00145 //
00146 //   This is the sort service.
00147 //
00148 class XULSortServiceImpl : public nsIXULSortService
00149 {
00150 protected:
00151   XULSortServiceImpl(void);
00152   virtual ~XULSortServiceImpl(void);
00153 
00154   static nsICollation *gCollation;
00155 
00156   friend nsresult NS_NewXULSortService(nsIXULSortService** mgr);
00157 
00158 private:
00159   static nsrefcnt gRefCnt;
00160   static nsString *kTrueStr;
00161   static nsString *kNaturalStr;
00162   static nsString *kAscendingStr;
00163   static nsString *kDescendingStr;
00164 
00165   static nsIRDFService *gRDFService;
00166   static nsIRDFContainerUtils *gRDFC;
00167 
00168 nsresult FindDatabaseElement(nsIContent* aElement, nsIContent** aDatabaseElement);
00169 nsresult FindSortableContainer(nsIContent *tree, nsIContent **treeBody);
00170 nsresult SetSortHints(nsIContent *tree, const nsAString &sortResource, const nsAString &sortDirection, const nsAString &sortResource2, PRBool inbetweenSeparatorSort, PRBool found);
00171 nsresult SetSortColumnHints(nsIContent *content, const nsAString &sortResource, const nsAString &sortDirection);
00172 nsresult GetSortColumnInfo(nsIContent *tree, nsAString &sortResource, nsAString &sortDirection, nsAString &sortResource2, PRBool &inbetweenSeparatorSort);
00173 
00174 nsresult SortContainer(nsIContent *container, sortPtr sortInfo, PRBool merelyInvertFlag);
00175 nsresult InvertSortInfo(contentSortInfo **data, PRInt32 numItems);
00176 
00177 static nsresult  GetCachedTarget(sortPtr sortInfo, PRBool useCache, nsIRDFResource* aSource, nsIRDFResource *aProperty, PRBool aTruthValue, nsIRDFNode **aResult);
00178 static nsresult GetTarget(contentSortInfo *contentSortInfo, sortPtr sortInfo,  PRBool first, PRBool onlyCollationHint, PRBool truthValue,nsIRDFNode **target, PRBool &isCollationKey);
00179 static nsresult GetResourceValue(nsIRDFResource *res1, sortPtr sortInfo, PRBool first, PRBool useCache, PRBool onlyCollationHint, nsIRDFNode **, PRBool &isCollationKey);
00180 static nsresult GetResourceValue(contentSortInfo *contentSortInfo, sortPtr sortInfo, PRBool first, PRBool useCache,  PRBool onlyCollationHint, nsIRDFNode **target, PRBool &isCollationKey);
00181 static nsresult GetNodeValue(nsIContent *node1, sortPtr sortInfo, PRBool first, PRBool onlyCollationHint, nsIRDFNode **, PRBool &isCollationKey);
00182 static nsresult GetNodeValue(contentSortInfo *info1, sortPtr sortInfo, PRBool first, PRBool onlyCollationHint, nsIRDFNode **theNode, PRBool &isCollationKey);
00183 
00184 public:
00185   // nsISupports
00186   NS_DECL_ISUPPORTS
00187 
00188   // nsISortService
00189   NS_DECL_NSIXULSORTSERVICE
00190 
00191   static nsresult InplaceSort(nsIContent *node1, nsIContent *node2, sortPtr sortInfo, PRInt32 & sortOrder);
00192   static nsresult InplaceSort(contentSortInfo *info1, contentSortInfo *info2, sortPtr sortInfo, PRInt32 & sortOrder);
00193   static nsresult CompareNodes(nsIRDFNode *cellNode1, PRBool isCollationKey1,
00194                                nsIRDFNode *cellNode2, PRBool isCollationKey2,
00195                                PRBool &bothValid, PRInt32 & sortOrder);
00196 };
00197 
00198 nsICollation *XULSortServiceImpl::gCollation = nsnull;
00199 nsIRDFService *XULSortServiceImpl::gRDFService = nsnull;
00200 nsIRDFContainerUtils *XULSortServiceImpl::gRDFC = nsnull;
00201 nsrefcnt XULSortServiceImpl::gRefCnt = 0;
00202 
00203 nsString* XULSortServiceImpl::kTrueStr = nsnull;
00204 nsString* XULSortServiceImpl::kNaturalStr = nsnull;
00205 nsString* XULSortServiceImpl::kAscendingStr = nsnull;
00206 nsString* XULSortServiceImpl::kDescendingStr = nsnull;
00207 
00209 
00210 XULSortServiceImpl::XULSortServiceImpl(void)
00211 {
00212   if (gRefCnt == 0) {
00213     kTrueStr = new nsString(NS_LITERAL_STRING("true"));
00214     kNaturalStr = new nsString(NS_LITERAL_STRING("natural"));
00215     kAscendingStr = new nsString(NS_LITERAL_STRING("ascending"));
00216     kDescendingStr = new nsString(NS_LITERAL_STRING("descending"));
00217  
00218     nsresult rv = CallGetService(kRDFServiceCID, &gRDFService);
00219 
00220     NS_ASSERTION(NS_SUCCEEDED(rv), "couldn't create rdf service");
00221 
00222     rv = CallGetService(kRDFContainerUtilsCID, &gRDFC);
00223 
00224     NS_ASSERTION(NS_SUCCEEDED(rv), "couldn't create rdf container utils");
00225 
00226     // get a locale service 
00227     nsCOMPtr<nsILocaleService> localeService = do_GetService(NS_LOCALESERVICE_CONTRACTID, &rv);
00228     if (NS_SUCCEEDED(rv)) {
00229       nsCOMPtr<nsILocale>  locale;
00230       if (NS_SUCCEEDED(rv = localeService->GetApplicationLocale(getter_AddRefs(locale))) && (locale)) {
00231         nsCOMPtr<nsICollationFactory> colFactory = do_CreateInstance(kCollationFactoryCID);
00232         if (colFactory) {
00233           rv = colFactory->CreateCollation(locale, &gCollation);
00234 
00235           NS_ASSERTION(NS_SUCCEEDED(rv), "couldn't create collation instance");
00236         } else
00237           NS_ERROR("couldn't create instance of collation factory");
00238       } else
00239         NS_ERROR("unable to get application locale");
00240     } else
00241       NS_ERROR("couldn't get locale factory");
00242   }
00243 
00244   ++gRefCnt;
00245 }
00246 
00247 XULSortServiceImpl::~XULSortServiceImpl(void) {
00248 #ifdef DEBUG_REFS
00249     --gInstanceCount;
00250     fprintf(stdout, "%d - RDF: XULSortServiceImpl\n", gInstanceCount);
00251 #endif
00252 
00253   --gRefCnt;
00254   if (gRefCnt == 0) {
00255     delete kTrueStr;
00256     kTrueStr = nsnull;
00257     delete kAscendingStr;
00258     kAscendingStr = nsnull;
00259     delete kDescendingStr;
00260     kDescendingStr = nsnull;
00261     delete kNaturalStr;
00262     kNaturalStr = nsnull;
00263 
00264     NS_IF_RELEASE(gCollation);
00265 
00266     NS_IF_RELEASE(gRDFService);
00267     NS_IF_RELEASE(gRDFC);
00268   }
00269 }
00270 
00271 NS_IMPL_ISUPPORTS1(XULSortServiceImpl, nsIXULSortService)
00272 
00273 
00274 
00275 nsresult
00276 XULSortServiceImpl::FindDatabaseElement(nsIContent *aElement, nsIContent **aDatabaseElement)
00277 {
00278   *aDatabaseElement = nsnull;
00279 
00280   // so look from the current node upwards until we find a node with a database
00281   for (nsIContent* content = aElement; content; content = content->GetParent()) {
00282     nsCOMPtr<nsIDOMXULElement> element = do_QueryInterface(content);
00283     nsCOMPtr<nsIRDFCompositeDataSource> db;
00284     element->GetDatabase(getter_AddRefs(db));
00285     if (db) {
00286       NS_ADDREF(*aDatabaseElement = content);
00287       return NS_OK;
00288     }
00289   }
00290 
00291   return NS_ERROR_FAILURE;
00292 }
00293 
00294 nsresult
00295 XULSortServiceImpl::FindSortableContainer(nsIContent *aRoot,
00296                                           nsIContent **aContainer)
00297 {
00298   *aContainer = nsnull;
00299 
00300   nsresult rv;
00301 
00302   nsIAtom *tag = aRoot->Tag();
00303 
00304   if (aRoot->IsContentOfType(nsIContent::eXUL)) {
00305     if (tag == nsXULAtoms::templateAtom) // ignore content within templates
00306       return NS_OK;    
00307 
00308     if (tag == nsXULAtoms::listbox ||
00309         tag == nsXULAtoms::treechildren ||
00310         tag == nsXULAtoms::menupopup) {
00311       *aContainer = aRoot;
00312       NS_ADDREF(*aContainer);
00313 
00314       return NS_OK;
00315     }
00316   }
00317 
00318   PRUint32 numChildren = aRoot->GetChildCount();
00319 
00320   for (PRUint32 childIndex = 0; childIndex < numChildren; childIndex++) {
00321     nsIContent *child = aRoot->GetChildAt(childIndex);
00322 
00323     if (child->IsContentOfType(nsIContent::eXUL)) {
00324       rv = FindSortableContainer(child, aContainer);
00325       if (*aContainer)
00326         return rv;
00327     }
00328   }
00329 
00330   return NS_ERROR_FAILURE;
00331 }
00332 
00333 nsresult
00334 XULSortServiceImpl::SetSortHints(nsIContent *tree,
00335                                  const nsAString &sortResource,
00336                                  const nsAString &sortDirection,
00337                                  const nsAString &sortResource2,
00338                                  PRBool inbetweenSeparatorSort, PRBool found)
00339 {
00340   if (found) {
00341     // set hints on tree root node
00342     tree->SetAttr(kNameSpaceID_None, nsXULAtoms::sortActive, *kTrueStr, PR_FALSE);
00343     tree->SetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection, sortDirection, PR_FALSE);
00344     tree->SetAttr(kNameSpaceID_None, nsXULAtoms::sortResource, sortResource, PR_FALSE);
00345 
00346     if (!sortResource2.IsEmpty())
00347       tree->SetAttr(kNameSpaceID_None, nsXULAtoms::sortResource2, sortResource2, PR_FALSE);
00348     else
00349       tree->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortResource2, PR_FALSE);
00350   } else {
00351     tree->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortActive, PR_FALSE);
00352     tree->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection, PR_FALSE);
00353     tree->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortResource, PR_FALSE);
00354     tree->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortResource2, PR_FALSE);
00355   }
00356 
00357   // optional hint
00358   if (inbetweenSeparatorSort == PR_TRUE)
00359     tree->SetAttr(kNameSpaceID_None, nsXULAtoms::sortSeparators, *kTrueStr, PR_FALSE);
00360   else
00361     tree->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortSeparators, PR_FALSE);
00362 
00363   SetSortColumnHints(tree, sortResource, sortDirection);
00364 
00365   return NS_OK;
00366 }
00367 
00368 nsresult
00369 XULSortServiceImpl::SetSortColumnHints(nsIContent *content,
00370                                        const nsAString &sortResource,
00371                                        const nsAString &sortDirection)
00372 {
00373   nsresult rv;
00374 
00375   PRUint32 numChildren = content->GetChildCount();
00376 
00377   for (PRUint32 childIndex = 0; childIndex < numChildren; ++childIndex) {
00378     nsIContent *child = content->GetChildAt(childIndex);
00379 
00380     if (child->IsContentOfType(nsIContent::eXUL)) {
00381       nsIAtom *tag = child->Tag();
00382 
00383       if (tag == nsXULAtoms::treecols ||
00384           tag == nsXULAtoms::listcols ||
00385           tag == nsXULAtoms::listhead) {
00386         rv = SetSortColumnHints(child, sortResource, sortDirection);
00387       } else if (tag == nsXULAtoms::treecol ||
00388                  tag == nsXULAtoms::listcol ||
00389                  tag == nsXULAtoms::listheader) {
00390         nsAutoString value;
00391 
00392         if (NS_SUCCEEDED(rv = child->GetAttr(kNameSpaceID_None,
00393                                              nsXULAtoms::resource, value))
00394             && rv == NS_CONTENT_ATTR_HAS_VALUE)
00395         {
00396           if (value == sortResource) {
00397             child->SetAttr(kNameSpaceID_None, nsXULAtoms::sortActive,
00398                            *kTrueStr, PR_TRUE);
00399             child->SetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection,
00400                            sortDirection, PR_TRUE);
00401             // Note: don't break out of loop; want to set/unset
00402             // attribs on ALL sort columns
00403           } else {
00404             child->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortActive,
00405                              PR_TRUE);
00406             child->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection,
00407                              PR_TRUE);
00408           }
00409         }
00410       }
00411     }
00412   }
00413   
00414   return NS_OK;
00415 }
00416 
00417 nsresult
00418 XULSortServiceImpl::GetSortColumnInfo(nsIContent *tree,
00419                                       nsAString &sortResource,
00420                                       nsAString &sortDirection,
00421                                       nsAString &sortResource2,
00422                                       PRBool &inbetweenSeparatorSort)
00423 {
00424   nsresult rv = NS_ERROR_FAILURE;
00425   inbetweenSeparatorSort = PR_FALSE;
00426 
00427   nsAutoString value;
00428   if (NS_SUCCEEDED(rv = tree->GetAttr(kNameSpaceID_None,
00429                                       nsXULAtoms::sortActive, value))
00430     && (rv == NS_CONTENT_ATTR_HAS_VALUE))
00431   {
00432     if (value.EqualsLiteral("true"))
00433     {
00434       if (NS_SUCCEEDED(rv = tree->GetAttr(kNameSpaceID_None,
00435                                           nsXULAtoms::sortResource,
00436                                           sortResource))
00437           && (rv == NS_CONTENT_ATTR_HAS_VALUE))
00438       {
00439         if (NS_SUCCEEDED(rv = tree->GetAttr(kNameSpaceID_None,
00440                                             nsXULAtoms::sortDirection,
00441                                             sortDirection))
00442             && (rv == NS_CONTENT_ATTR_HAS_VALUE))
00443         {
00444           rv = NS_OK;
00445 
00446           // sort separator flag is optional
00447           if (NS_SUCCEEDED(rv = tree->GetAttr(kNameSpaceID_None,
00448                                               nsXULAtoms::sortSeparators,
00449                                               value)) &&
00450               (rv == NS_CONTENT_ATTR_HAS_VALUE))
00451           {
00452             if (value.EqualsLiteral("true"))
00453             {
00454               inbetweenSeparatorSort = PR_TRUE;
00455             }
00456           }
00457 
00458           // secondary sort info is optional
00459           if (NS_FAILED(rv = tree->GetAttr(kNameSpaceID_None,
00460                                            nsXULAtoms::sortResource2,
00461                                            sortResource2)) ||
00462               (rv != NS_CONTENT_ATTR_HAS_VALUE))
00463           {
00464             sortResource2.Truncate();
00465           }
00466         }
00467       }
00468     }
00469   }
00470   
00471   return rv;
00472 }
00473 
00474 nsresult
00475 XULSortServiceImpl::CompareNodes(nsIRDFNode *cellNode1, PRBool isCollationKey1,
00476                                  nsIRDFNode *cellNode2, PRBool isCollationKey2,
00477                                  PRBool &bothValid, PRInt32 & sortOrder)
00478 {
00479   bothValid = PR_FALSE;
00480   sortOrder = 0;
00481 
00482   // First, check for blobs.  This is the preferred way to do a raw key comparison.
00483   {
00484     nsCOMPtr<nsIRDFBlob> l = do_QueryInterface(cellNode1);
00485     if (l)
00486     {
00487       nsCOMPtr<nsIRDFBlob> r = do_QueryInterface(cellNode2);
00488       if (r)
00489       {
00490         const PRUint8 *lkey, *rkey;
00491         PRInt32 llen, rlen;
00492         l->GetValue(&lkey);
00493         l->GetLength(&llen);
00494         r->GetValue(&rkey);
00495         r->GetLength(&rlen);
00496         bothValid = PR_TRUE;
00497         if (gCollation)
00498           return gCollation->CompareRawSortKey(lkey, llen, rkey, rlen, &sortOrder);
00499       }
00500     }
00501   }
00502 
00503   // Next, literals.  If isCollationKey1 and 2 are both set, do
00504   // an unsafe raw comparison. (XXX Remove this code someday.)
00505   {
00506     nsCOMPtr<nsIRDFLiteral> l = do_QueryInterface(cellNode1);
00507     if (l)
00508     {
00509       nsCOMPtr<nsIRDFLiteral> r = do_QueryInterface(cellNode2);
00510       if (r)
00511       {
00512         const PRUnichar *luni, *runi;
00513         l->GetValueConst(&luni);
00514         r->GetValueConst(&runi);
00515         bothValid = PR_TRUE;
00516         if (isCollationKey1 && isCollationKey2)
00517           return gCollation->CompareRawSortKey(NS_REINTERPRET_CAST(const PRUint8*, luni),
00518                                                nsCRT::strlen(luni)*sizeof(PRUnichar),
00519                                                NS_REINTERPRET_CAST(const PRUint8*, runi),
00520                                                nsCRT::strlen(runi)*sizeof(PRUnichar),
00521                                                &sortOrder);
00522         else
00523         {
00524           nsresult rv = NS_ERROR_FAILURE;
00525           nsDependentString lstr(luni), rstr(runi);
00526           if (gCollation)
00527             rv = gCollation->CompareString(nsICollation::kCollationCaseInSensitive, lstr, rstr, &sortOrder);
00528           if (NS_FAILED(rv))
00529             sortOrder = Compare(lstr, rstr, nsCaseInsensitiveStringComparator());
00530           return NS_OK;
00531         }
00532       }
00533     }
00534   }
00535 
00536   // Integers.
00537   {
00538     nsCOMPtr<nsIRDFInt> l = do_QueryInterface(cellNode1);
00539     if (l)
00540     {
00541       nsCOMPtr<nsIRDFInt> r = do_QueryInterface(cellNode2);
00542       if (r)
00543       {
00544         PRInt32 lint, rint;
00545         l->GetValue(&lint);
00546         r->GetValue(&rint);
00547         bothValid = PR_TRUE;
00548         sortOrder = 0;
00549         if (lint < rint)
00550           sortOrder = -1;
00551         else if (lint > rint)
00552           sortOrder = 1;
00553         return NS_OK;
00554       }
00555     }
00556   }
00557 
00558   // Dates.
00559   {
00560     nsCOMPtr<nsIRDFDate> l = do_QueryInterface(cellNode1);
00561     if (l)
00562     {
00563       nsCOMPtr<nsIRDFDate> r = do_QueryInterface(cellNode2);
00564       if (r)
00565       {
00566         PRInt64 ldate, rdate, delta;
00567         l->GetValue(&ldate);
00568         r->GetValue(&rdate);
00569         bothValid = PR_TRUE;
00570         LL_SUB(delta, ldate, rdate);
00571 
00572         if (LL_IS_ZERO(delta))
00573           sortOrder = 0;
00574         else if (LL_GE_ZERO(delta))
00575           sortOrder = 1;
00576         else
00577           sortOrder = -1;
00578         return NS_OK;
00579       }
00580     }
00581   }
00582 
00583   // Rats.
00584   return NS_OK;
00585 }
00586 
00587 nsresult
00588 XULSortServiceImpl::GetResourceValue(nsIRDFResource *res1, sortPtr sortInfo,
00589                                      PRBool first, PRBool useCache,
00590                                      PRBool onlyCollationHint, nsIRDFNode **target, PRBool &isCollationKey)
00591 {
00592   nsresult rv = NS_OK;
00593 
00594   *target = nsnull;
00595   isCollationKey = PR_FALSE;
00596 
00597   if (res1 && !sortInfo->naturalOrderSort) {
00598     nsCOMPtr<nsIRDFResource>  modSortRes;
00599 
00600     // for any given property, first ask the graph for its value with "?collation=true" appended
00601     // to indicate that if there is a collation key available for this value, we want it
00602 
00603     modSortRes = (first) ? sortInfo->sortPropertyColl : sortInfo->sortPropertyColl2;
00604     if (modSortRes) {
00605       if (NS_SUCCEEDED(rv = GetCachedTarget(sortInfo, useCache, res1, modSortRes, PR_TRUE, target))
00606           && (rv != NS_RDF_NO_VALUE))
00607       {
00608         isCollationKey = PR_TRUE;
00609       }
00610     }
00611     if (!*target && !onlyCollationHint) {
00612       // if no collation key, ask the graph for its value with "?sort=true" appended
00613       // to indicate that if there is any distinction between its display value and sorting
00614       // value, we want the sorting value (so that, for example, a mail datasource could strip
00615       // off a "Re:" on a mail message subject)
00616       modSortRes = first ? sortInfo->sortPropertySort : sortInfo->sortPropertySort2;
00617       if (modSortRes)
00618         rv = GetCachedTarget(sortInfo, useCache, res1, modSortRes, PR_TRUE, target);
00619     }
00620     if (!*target && !onlyCollationHint) {
00621       // if no collation key and no special sorting value, just get the property value
00622       modSortRes = first ? sortInfo->sortProperty : sortInfo->sortProperty2;
00623       if (modSortRes)
00624         rv = GetCachedTarget(sortInfo, useCache, res1, modSortRes, PR_TRUE, target);
00625     }
00626   }
00627   
00628   return rv;
00629 }
00630 
00631 nsresult
00632 XULSortServiceImpl::GetResourceValue(contentSortInfo *contentSortInfo, sortPtr sortInfo,
00633                                      PRBool first, PRBool useCache,
00634                                      PRBool onlyCollationHint, nsIRDFNode **target, PRBool &isCollationKey)
00635 {
00636   nsresult    rv = NS_OK;
00637 
00638   *target = nsnull;
00639   isCollationKey = PR_FALSE;
00640 
00641   nsIRDFResource *res1 = contentSortInfo->resource;
00642 
00643   if (res1 && sortInfo->naturalOrderSort == PR_FALSE)
00644     rv = GetTarget(contentSortInfo, sortInfo, first, onlyCollationHint, PR_TRUE, target, isCollationKey);
00645 
00646   return rv;
00647 }
00648 
00649 nsresult
00650 XULSortServiceImpl::GetCachedTarget(sortPtr sortInfo, PRBool useCache, nsIRDFResource* aSource,
00651     nsIRDFResource *aProperty, PRBool aTruthValue, nsIRDFNode **aResult)
00652 {
00653   nsresult  rv;
00654   *aResult = nsnull;
00655 
00656   if (!(sortInfo->mInner)) {
00657     // if we don't have a mInner, create one
00658     sortInfo->mInner = do_CreateInstance(kRDFInMemoryDataSourceCID, &rv);
00659     if (NS_FAILED(rv)) return  rv;
00660   }
00661 
00662   rv = NS_RDF_NO_VALUE;
00663   if (sortInfo->mInner) {
00664     if (useCache) {
00665       // if we do have a mInner, look for the resource in it
00666       rv = sortInfo->mInner->GetTarget(aSource, aProperty, aTruthValue, aResult);
00667     } else if (sortInfo->db) {
00668       // if we don't have a cached value, look it up in the document's DB
00669       if (NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(aSource, aProperty, aTruthValue, aResult))
00670           && (rv != NS_RDF_NO_VALUE))
00671       {
00672         // and if we have a value, cache it away in our mInner also (ignore errors)
00673         sortInfo->mInner->Assert(aSource, aProperty, *aResult, PR_TRUE);
00674       }
00675     }
00676   }
00677   
00678   return rv;
00679 }
00680 
00681 nsresult 
00682 XULSortServiceImpl::GetTarget(contentSortInfo *contentSortInfo, sortPtr sortInfo,
00683                               PRBool first, PRBool onlyCollationHint, PRBool truthValue,
00684                               nsIRDFNode **target, PRBool &isCollationKey)
00685 {
00686   nsresult rv;
00687   nsIRDFResource *resource = contentSortInfo->resource;
00688 
00689   if (first) {
00690     if (contentSortInfo->collationNode1) {
00691       *target = contentSortInfo->collationNode1;
00692       NS_IF_ADDREF(*target);
00693     } else if (!contentSortInfo->checkedCollation1
00694                && NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(resource, sortInfo->sortPropertyColl, truthValue, target)))
00695     {
00696       if (rv != NS_RDF_NO_VALUE)
00697         contentSortInfo->collationNode1 = *target;
00698       contentSortInfo->checkedCollation1 = PR_TRUE;
00699     }
00700   
00701     if (*target) {
00702       isCollationKey = PR_TRUE;
00703       return NS_OK;
00704     }
00705 
00706     if (onlyCollationHint == PR_FALSE)
00707     {
00708       if (contentSortInfo->sortNode1) {
00709         *target = contentSortInfo->sortNode1;
00710         NS_IF_ADDREF(*target);
00711       } else if (!contentSortInfo->checkedSort1 
00712                  && NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(resource, sortInfo->sortPropertySort, truthValue, target)))
00713       {
00714         if (rv != NS_RDF_NO_VALUE)
00715           contentSortInfo->sortNode1 = *target;
00716         contentSortInfo->checkedSort1 = PR_TRUE;
00717       }
00718 
00719       if (*target)
00720         return NS_OK;
00721 
00722       if (contentSortInfo->node1) {
00723         *target = contentSortInfo->node1;
00724         NS_IF_ADDREF(*target);
00725       } else if (!contentSortInfo->checkedNode1 
00726                  && NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(resource, sortInfo->sortProperty, truthValue, target)))
00727       {
00728         if (rv != NS_RDF_NO_VALUE)
00729           contentSortInfo->node1 = *target;
00730         contentSortInfo->checkedNode1 = PR_TRUE;
00731       }
00732 
00733       if (*target)
00734         return NS_OK;
00735     }
00736   } else {
00737     if (contentSortInfo->collationNode2) {
00738       *target = contentSortInfo->collationNode2;
00739       NS_IF_ADDREF(*target);
00740     } else if (!contentSortInfo->checkedCollation2
00741                && NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(resource, sortInfo->sortPropertyColl2, truthValue, target)))
00742     {
00743       if (rv != NS_RDF_NO_VALUE)
00744         contentSortInfo->collationNode2 = *target;
00745       contentSortInfo->checkedCollation2 = PR_TRUE;
00746     }
00747   
00748     if (*target) {
00749       isCollationKey = PR_TRUE;
00750       return NS_OK;
00751     }
00752 
00753     if (onlyCollationHint == PR_FALSE) {
00754       if (contentSortInfo->sortNode2) {
00755         *target = contentSortInfo->sortNode2;
00756         NS_IF_ADDREF(*target);
00757       } else if (!contentSortInfo->checkedSort2
00758                  && NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(resource, sortInfo->sortPropertySort2, truthValue, target)))
00759       {
00760         if (rv != NS_RDF_NO_VALUE)
00761           contentSortInfo->sortNode2 = *target;
00762         contentSortInfo->checkedSort2 = PR_TRUE;
00763       }
00764 
00765       if (*target)
00766         return NS_OK;
00767 
00768       if (contentSortInfo->node2) {
00769         *target = contentSortInfo->node2;
00770         NS_IF_ADDREF(*target);
00771       } else if (!contentSortInfo->checkedNode2
00772                  && NS_SUCCEEDED(rv = (sortInfo->db)->GetTarget(resource, sortInfo->sortProperty2, truthValue, target)))
00773       {
00774         if (rv != NS_RDF_NO_VALUE)
00775           contentSortInfo->node2 = *target;
00776         contentSortInfo->checkedNode2 = PR_TRUE;
00777       }
00778 
00779       if (*target)
00780         return NS_OK;
00781     }
00782   }
00783       
00784   return NS_RDF_NO_VALUE;
00785 }
00786 
00787 nsresult
00788 XULSortServiceImpl::GetNodeValue(nsIContent *node1, sortPtr sortInfo, PRBool first,
00789         PRBool onlyCollationHint, nsIRDFNode **theNode, PRBool &isCollationKey)
00790 {
00791   nsresult rv;
00792   nsCOMPtr<nsIRDFResource>  res1;
00793 
00794   *theNode = nsnull;
00795   isCollationKey = PR_FALSE;
00796 
00797   nsCOMPtr<nsIDOMXULElement>  dom1 = do_QueryInterface(node1);
00798   if (dom1) {
00799     if (NS_FAILED(rv = dom1->GetResource(getter_AddRefs(res1))))
00800       res1 = nsnull;
00801     // Note: don't check for res1 QI failure here.  It only succeeds for RDF nodes,
00802     // but for XUL nodes it will failure; in the failure case, the code below gets
00803     // the cell's text value straight from the DOM
00804   } else {
00805     nsCOMPtr<nsIDOMElement>  htmlDom = do_QueryInterface(node1);
00806     if (htmlDom) {
00807       nsAutoString htmlID;
00808       if (NS_SUCCEEDED(rv = node1->GetAttr(kNameSpaceID_None, nsXULAtoms::id, htmlID)) 
00809           && (rv == NS_CONTENT_ATTR_HAS_VALUE))
00810       {
00811         if (NS_FAILED(rv = gRDFService->GetUnicodeResource(htmlID, getter_AddRefs(res1))))
00812           res1 = nsnull;
00813       }
00814     }
00815     else
00816     {
00817       return NS_ERROR_FAILURE;
00818     }
00819   }
00820   
00821   if ((sortInfo->naturalOrderSort == PR_FALSE) && (sortInfo->sortProperty)) {
00822     if (res1) {
00823       rv = GetResourceValue(res1, sortInfo, first, PR_TRUE, onlyCollationHint, theNode, isCollationKey);
00824       if ((rv == NS_RDF_NO_VALUE) || (!*theNode))
00825         rv = GetResourceValue(res1, sortInfo, first, PR_FALSE, onlyCollationHint, theNode, isCollationKey);
00826     }
00827     else
00828       rv = NS_RDF_NO_VALUE;
00829 
00830   } else if ((sortInfo->naturalOrderSort == PR_TRUE) && (sortInfo->parentContainer)) {
00831     nsAutoString    cellPosVal1;
00832 
00833     // check to see if this is a RDF_Seq
00834     // Note: this code doesn't handle the aggregated Seq case especially well
00835     if ((res1) && (sortInfo->db))
00836     {
00837       nsCOMPtr<nsIRDFResource>  parentResource;
00838       nsCOMPtr<nsIDOMXULElement>  parentDOMNode = do_QueryInterface(sortInfo->parentContainer);
00839       if (parentDOMNode)
00840       {
00841         if (NS_FAILED(rv = parentDOMNode->GetResource(getter_AddRefs(parentResource))))
00842         {
00843           parentResource = nsnull;
00844         }
00845       }
00846 
00847       if (parentResource)
00848       {
00849         PRInt32 index;
00850         rv = gRDFC->IndexOf(sortInfo->db, parentResource,
00851                 res1, &index);
00852         if (index != -1)
00853         {
00854           nsCOMPtr<nsIRDFInt> intLit;
00855           rv = gRDFService->GetIntLiteral(index, getter_AddRefs(intLit));
00856           CallQueryInterface(intLit, theNode);
00857           isCollationKey = PR_FALSE;
00858         }
00859       }
00860     }
00861   }
00862   return rv;
00863 }
00864 
00865 nsresult
00866 XULSortServiceImpl::GetNodeValue(contentSortInfo *info1, sortPtr sortInfo, PRBool first,
00867                                  PRBool onlyCollationHint, nsIRDFNode **theNode,
00868                                  PRBool &isCollationKey)
00869 {
00870   nsresult rv = NS_OK;
00871   nsCOMPtr<nsIRDFResource>  res1;
00872 
00873   nsIContent *node1 = info1->content;
00874   *theNode = nsnull;
00875   isCollationKey = PR_FALSE;
00876 
00877   // determine the rdf resource
00878   nsCOMPtr<nsIDOMXULElement>  dom1 = do_QueryInterface(node1);
00879   if (dom1)
00880     res1 = info1->resource;
00881   else {
00882     // If this isn't a XUL element, get its id and fetch the resource directly
00883     nsCOMPtr<nsIDOMElement>  htmlDom = do_QueryInterface(node1);
00884     if (htmlDom) {
00885       nsAutoString htmlID;
00886       if (NS_SUCCEEDED(rv = node1->GetAttr(kNameSpaceID_None, nsXULAtoms::id, htmlID))
00887         && (rv == NS_CONTENT_ATTR_HAS_VALUE))
00888       {
00889         if (NS_FAILED(rv = gRDFService->GetUnicodeResource(htmlID, getter_AddRefs(res1))))
00890           res1 = nsnull;
00891         info1->resource = res1;
00892       }
00893     }
00894     else
00895       return NS_ERROR_FAILURE;
00896   }
00897   
00898   if ((!sortInfo->naturalOrderSort) && (sortInfo->sortProperty)) {
00899     if (res1) {
00900       rv = GetResourceValue(info1, sortInfo, first, PR_TRUE, onlyCollationHint, theNode, isCollationKey);
00901       if ((rv == NS_RDF_NO_VALUE) || (!*theNode)) {
00902         rv = GetResourceValue(info1, sortInfo, first, PR_FALSE, onlyCollationHint, theNode, isCollationKey);
00903       }
00904     }
00905     else
00906       rv = NS_RDF_NO_VALUE;
00907 
00908   } else if ((sortInfo->naturalOrderSort == PR_TRUE) && (sortInfo->parentContainer)) {
00909     nsAutoString  cellPosVal1;
00910 
00911     // check to see if this is a RDF_Seq
00912     // Note: this code doesn't handle the aggregated Seq case especially well
00913     if ((res1) && (sortInfo->db))
00914     {
00915       nsCOMPtr<nsIRDFResource>  parentResource;
00916       nsCOMPtr<nsIDOMXULElement>  parentDOMNode = do_QueryInterface(sortInfo->parentContainer);
00917       if (parentDOMNode)
00918       {
00919         if (NS_FAILED(rv = parentDOMNode->GetResource(getter_AddRefs(parentResource))))
00920         {
00921           parentResource = nsnull;
00922         }
00923       }
00924 
00925       if (parentResource)
00926       {
00927         PRInt32 index;
00928         rv = gRDFC->IndexOf(sortInfo->db, parentResource,
00929                 res1, &index);
00930         if (index != -1)
00931         {
00932           nsCOMPtr<nsIRDFInt> intLit;
00933           rv = gRDFService->GetIntLiteral(index, getter_AddRefs(intLit));
00934           CallQueryInterface(intLit, theNode);
00935           isCollationKey = PR_FALSE;
00936         }
00937       }
00938     }
00939   }
00940   else
00941     // XXX Is this right?
00942     rv = NS_ERROR_NULL_POINTER;
00943 
00944   return rv;
00945 }
00946 
00947 nsresult
00948 XULSortServiceImpl::InplaceSort(nsIContent *node1, nsIContent *node2, sortPtr sortInfo, PRInt32 & sortOrder)
00949 {
00950   PRBool isCollationKey1 = PR_FALSE, isCollationKey2 = PR_FALSE;
00951   nsresult rv;
00952 
00953   sortOrder = 0;
00954 
00955   nsCOMPtr<nsIRDFNode> cellNode1, cellNode2;
00956 
00957   // rjc: in some cases, the first node is static while the second node changes
00958   // per comparison; in these circumstances, we can cache the first node
00959   if ((sortInfo->cacheFirstHint == PR_TRUE) && (sortInfo->cacheFirstNode))
00960   {
00961     cellNode1 = sortInfo->cacheFirstNode;
00962     isCollationKey1 = sortInfo->cacheIsFirstNodeCollationKey;
00963   }
00964   else
00965   {
00966     GetNodeValue(node1, sortInfo, PR_TRUE, PR_FALSE, getter_AddRefs(cellNode1), isCollationKey1);
00967     if (sortInfo->cacheFirstHint == PR_TRUE)
00968     {
00969       sortInfo->cacheFirstNode = cellNode1;
00970       sortInfo->cacheIsFirstNodeCollationKey = isCollationKey1;
00971     }
00972   }
00973   GetNodeValue(node2, sortInfo, PR_TRUE, isCollationKey1, getter_AddRefs(cellNode2), isCollationKey2);
00974 
00975   PRBool  bothValid = PR_FALSE;
00976   rv = CompareNodes(cellNode1, isCollationKey1, cellNode2, isCollationKey2, bothValid, sortOrder);
00977 
00978   if (sortOrder == 0)
00979   {
00980     // nodes appear to be equivalent, check for secondary sort criteria
00981     if (sortInfo->sortProperty2 != nsnull)
00982     {
00983       cellNode1 = nsnull;
00984       cellNode2 = nsnull;
00985       isCollationKey1 = PR_FALSE;
00986       isCollationKey2 = PR_FALSE;
00987       
00988       GetNodeValue(node1, sortInfo, PR_FALSE, PR_FALSE, getter_AddRefs(cellNode1), isCollationKey1);
00989       GetNodeValue(node2, sortInfo, PR_FALSE, isCollationKey1, getter_AddRefs(cellNode2), isCollationKey2);
00990 
00991       bothValid = PR_FALSE;
00992       rv = CompareNodes(cellNode1, isCollationKey1, cellNode2, isCollationKey2, bothValid, sortOrder);
00993     }
00994   }
00995 
00996   if ((bothValid == PR_TRUE) && (sortInfo->descendingSort == PR_TRUE))
00997   {
00998     // descending sort is being imposed, so reverse the sort order
00999     sortOrder = -sortOrder;
01000   }
01001 
01002   return NS_OK;
01003 }
01004 
01005 nsresult
01006 XULSortServiceImpl::InplaceSort(contentSortInfo *info1, contentSortInfo *info2, sortPtr sortInfo, PRInt32 & sortOrder)
01007 {
01008   PRBool isCollationKey1 = PR_FALSE, isCollationKey2 = PR_FALSE;
01009   nsresult rv;
01010 
01011   sortOrder = 0;
01012 
01013   nsCOMPtr<nsIRDFNode> cellNode1, cellNode2;
01014 
01015   // rjc: in some cases, the first node is static while the second node changes
01016   // per comparison; in these circumstances, we can cache the first node
01017   if ((sortInfo->cacheFirstHint == PR_TRUE) && (sortInfo->cacheFirstNode))
01018   {
01019     cellNode1 = sortInfo->cacheFirstNode;
01020     isCollationKey1 = sortInfo->cacheIsFirstNodeCollationKey;
01021   }
01022   else
01023   {
01024     GetNodeValue(info1, sortInfo, PR_TRUE, PR_FALSE, getter_AddRefs(cellNode1), isCollationKey1);
01025     if (sortInfo->cacheFirstHint == PR_TRUE)
01026     {
01027       sortInfo->cacheFirstNode = cellNode1;
01028       sortInfo->cacheIsFirstNodeCollationKey = isCollationKey1;
01029     }
01030   }
01031   GetNodeValue(info2, sortInfo, PR_TRUE, isCollationKey1, getter_AddRefs(cellNode2), isCollationKey2);
01032 
01033   PRBool  bothValid = PR_FALSE;
01034   rv = CompareNodes(cellNode1, isCollationKey1, cellNode2, isCollationKey2, bothValid, sortOrder);
01035 
01036   if (sortOrder == 0) {
01037     // nodes appear to be equivalent, check for secondary sort criteria
01038     if (sortInfo->sortProperty2 != nsnull) {
01039       cellNode1 = nsnull;
01040       cellNode2 = nsnull;
01041       isCollationKey1 = PR_FALSE;
01042       isCollationKey2 = PR_FALSE;
01043     
01044       GetNodeValue(info1, sortInfo, PR_FALSE, PR_FALSE, getter_AddRefs(cellNode1), isCollationKey1);
01045       GetNodeValue(info2, sortInfo, PR_FALSE, isCollationKey1, getter_AddRefs(cellNode2), isCollationKey2);
01046 
01047       bothValid = PR_FALSE;
01048       rv = CompareNodes(cellNode1, isCollationKey1, cellNode2, isCollationKey2, bothValid, sortOrder);
01049     }
01050   }
01051 
01052   if ((bothValid == PR_TRUE) && (sortInfo->descendingSort == PR_TRUE))
01053   {
01054     // descending sort is being imposed, so reverse the sort order
01055     sortOrder = -sortOrder;
01056   }
01057 
01058   return NS_OK;
01059 }
01060 
01061 int PR_CALLBACK
01062 inplaceSortCallback(const void *data1, const void *data2, void *privateData)
01063 {
01065   _sortStruct *sortInfo = (_sortStruct *)privateData;
01066   nsIContent *node1 = *(nsIContent **)data1;
01067   nsIContent *node2 = *(nsIContent **)data2;
01068   PRInt32 sortOrder = 0;
01069 
01070   if (nsnull != sortInfo)
01071     XULSortServiceImpl::InplaceSort(node1, node2, sortInfo, sortOrder);
01072 
01073   return sortOrder;
01074 }
01075 
01076 int PR_CALLBACK
01077 testSortCallback(const void *data1, const void *data2, void *privateData)
01078 {
01080   _sortStruct *sortInfo = (_sortStruct *)privateData;
01081   contentSortInfo *info1 = *(contentSortInfo **)data1;
01082   contentSortInfo *info2 = *(contentSortInfo **)data2;
01083   PRInt32 sortOrder = 0;
01084 
01085   if (nsnull != sortInfo)
01086     XULSortServiceImpl::InplaceSort(info1, info2, sortInfo, sortOrder);
01087 
01088   return sortOrder;
01089 }
01090 
01091 static contentSortInfo *
01092 CreateContentSortInfo(nsIContent *content, nsIRDFResource * resource)
01093 {
01094   contentSortInfo * info = new contentSortInfo;
01095   if (!info)
01096     return nsnull;
01097 
01098   info->content = content;
01099   NS_IF_ADDREF(info->content);
01100 
01101   info->resource = resource;
01102 
01103   info->checkedCollation1 = PR_FALSE;
01104   info->checkedCollation2 = PR_FALSE;
01105   info->checkedSort1 = PR_FALSE;
01106   info->checkedSort2 = PR_FALSE;
01107   info->checkedNode1 = PR_FALSE;
01108   info->checkedNode2 = PR_FALSE;
01109 
01110   return info;
01111 }
01112 
01113 nsresult
01114 XULSortServiceImpl::SortContainer(nsIContent *container, sortPtr sortInfo,
01115                                   PRBool merelyInvertFlag)
01116 {
01117   PRUint32 loop, numElements = 0, currentElement;
01118 
01119   PRUint32 numChildren = container->GetChildCount();
01120   if (numChildren < 1)
01121     return NS_OK;
01122 
01123   nsIDocument *doc = container->GetDocument();
01124   if (!doc)
01125     return NS_ERROR_UNEXPECTED;
01126 
01127   // Note: This is a straight allocation (not a COMPtr) so we
01128   // can't return out of this routine until/unless we free it!
01129   contentSortInfo ** contentSortInfoArray = new contentSortInfo*[numChildren + 1];
01130   if (!contentSortInfoArray)
01131     return NS_ERROR_OUT_OF_MEMORY;
01132 
01133   // Note: walk backwards (and add nodes into the array backwards) because
01134   // we also remove the nodes in this loop [via RemoveChildAt()] and if we
01135   // were to do this in a forward-looking manner it would be harder
01136   // (since we also skip over non XUL:treeitem nodes)
01137 
01138   nsresult rv;
01139   currentElement = numChildren;
01140   PRUint32 childIndex;
01141   // childIndex is unsigned, so childIndex >= 0 would always test true
01142   for (childIndex = numChildren; childIndex > 0; ) {
01143     --childIndex;
01144     nsIContent *child = container->GetChildAt(childIndex);
01145 
01146     if (child->IsContentOfType(nsIContent::eXUL)) {
01147       nsIAtom *tag = child->Tag();
01148 
01149       if (tag == nsXULAtoms::listitem ||
01150           tag == nsXULAtoms::treeitem ||
01151           tag == nsXULAtoms::menu ||
01152           tag == nsXULAtoms::menuitem) {
01153         --currentElement;
01154 
01155         nsCOMPtr<nsIRDFResource>  resource;
01156         nsCOMPtr<nsIDOMXULElement> xulElement(do_QueryInterface(child));
01157         xulElement->GetResource(getter_AddRefs(resource));
01158         contentSortInfo *contentInfo = CreateContentSortInfo(child, resource);
01159         if (contentInfo)
01160           contentSortInfoArray[currentElement] = contentInfo;
01161 
01162         ++numElements;
01163       }
01164     }
01165   }
01166   
01167   if (numElements > 0) {
01168     /* smart sorting (sort within separators) on name column */
01169     if (sortInfo->inbetweenSeparatorSort) {
01170       PRUint32 startIndex = currentElement;
01171       nsAutoString  type;
01172       for (loop = currentElement; loop < currentElement + numElements;
01173            ++loop) {
01174         if (NS_SUCCEEDED(rv = contentSortInfoArray[loop]->content->GetAttr(kNameSpaceID_RDF,
01175             nsXULAtoms::type, type)) && (rv == NS_CONTENT_ATTR_HAS_VALUE))
01176         {
01177           if (type.EqualsASCII(kURINC_BookmarkSeparator)) {
01178             if (loop > startIndex + 1) {
01179               if (merelyInvertFlag)
01180                 InvertSortInfo(&contentSortInfoArray[startIndex], loop-startIndex);
01181               else
01182                 NS_QuickSort((void*)&contentSortInfoArray[startIndex], loop-startIndex,
01183                              sizeof(contentSortInfo*), testSortCallback, (void*)sortInfo);
01184               startIndex = loop+1;
01185             }
01186           }
01187         }
01188       }
01189       
01190       if (loop > startIndex+1) {
01191         if (merelyInvertFlag)
01192           InvertSortInfo(&contentSortInfoArray[startIndex], loop-startIndex);
01193         else
01194           NS_QuickSort((void*)&contentSortInfoArray[startIndex], loop-startIndex,
01195                        sizeof(contentSortInfo*), testSortCallback, (void*)sortInfo);
01196         startIndex = loop+1;
01197       }
01198     } else {
01199       if (merelyInvertFlag)
01200         InvertSortInfo(&contentSortInfoArray[currentElement], numElements);
01201       else
01202         NS_QuickSort((void*)(&contentSortInfoArray[currentElement]), numElements,
01203                      sizeof(contentSortInfo*), testSortCallback, (void*)sortInfo);
01204     }
01205 
01206     // childIndex is unsigned, so childIndex >= 0 would always test true
01207     for (childIndex = numChildren; childIndex > 0; )
01208     {
01209       --childIndex;
01210       nsIContent *child = container->GetChildAt(childIndex);
01211 
01212       if (child->IsContentOfType(nsIContent::eXUL)) {
01213         nsIAtom *tag = child->Tag();
01214 
01215         if (tag == nsXULAtoms::listitem ||
01216             tag == nsXULAtoms::treeitem ||
01217             tag == nsXULAtoms::menu ||
01218             tag == nsXULAtoms::menuitem) {
01219           // immediately remove the child node, and ignore any errors
01220           container->RemoveChildAt(childIndex, PR_FALSE);
01221         }
01222       }
01223     }
01224 
01225     // put the items back in sorted order
01226     nsAutoString value;
01227     PRUint32 childPos = container->GetChildCount();
01228     for (loop = currentElement; loop < currentElement + numElements; loop++) {
01229       contentSortInfo * contentSortInfo = contentSortInfoArray[loop];
01230       nsIContent *parentNode = (nsIContent *)contentSortInfo->content;
01231       nsIContent* kid = parentNode;
01232       container->InsertChildAt(kid, childPos++, PR_FALSE);
01233 
01234       NS_RELEASE(contentSortInfo->content);
01235       delete contentSortInfo;
01236 
01237       // if it's a container, find its treechildren nodes, and sort those
01238       if (NS_FAILED(rv = parentNode->GetAttr(kNameSpaceID_None, nsXULAtoms::container, value)) ||
01239         (rv != NS_CONTENT_ATTR_HAS_VALUE) || !value.EqualsLiteral("true"))
01240         continue;
01241         
01242       numChildren = parentNode->GetChildCount();
01243 
01244       for (childIndex = 0; childIndex < numChildren; childIndex++) {
01245         nsIContent *child = parentNode->GetChildAt(childIndex);
01246 
01247         nsINodeInfo *ni = child->GetNodeInfo();
01248 
01249         if (ni && (ni->Equals(nsXULAtoms::treechildren, kNameSpaceID_XUL) ||
01250                    ni->Equals(nsXULAtoms::menupopup, kNameSpaceID_XUL))) {
01251           sortInfo->parentContainer = parentNode;
01252           SortContainer(child, sortInfo, merelyInvertFlag);
01253         }
01254       }
01255     }
01256   }
01257   
01258   delete [] contentSortInfoArray;
01259   contentSortInfoArray = nsnull;
01260 
01261   return NS_OK;
01262 }
01263 
01264 nsresult
01265 XULSortServiceImpl::InvertSortInfo(contentSortInfo **data, PRInt32 numItems)
01266 {
01267   if (numItems > 1) {
01268     PRInt32 upPoint = (numItems + 1)/2, downPoint = (numItems - 2)/2;
01269     PRInt32 half = numItems/2;
01270     while (half-- > 0) {
01271       contentSortInfo *temp = data[downPoint];
01272       data[downPoint--] = data[upPoint];
01273       data[upPoint++] = temp;
01274     }
01275   }
01276   return NS_OK;
01277 }
01278 
01279 NS_IMETHODIMP
01280 XULSortServiceImpl::InsertContainerNode(nsIRDFCompositeDataSource *db, nsRDFSortState *sortState,
01281                                         nsIContent *root, nsIContent *trueParent, nsIContent *container,
01282                                         nsIContent *node, PRBool aNotify)
01283 {
01284   nsresult rv;
01285   nsAutoString sortResource, sortDirection, sortResource2;
01286   _sortStruct sortInfo;
01287 
01288   // get composite db for tree
01289   sortInfo.db = db;
01290   sortInfo.parentContainer = trueParent;
01291   sortInfo.sortProperty = nsnull;
01292   sortInfo.sortProperty2 = nsnull;
01293   sortInfo.inbetweenSeparatorSort = PR_FALSE;
01294   sortInfo.cacheFirstHint = PR_TRUE;
01295 
01296   if (sortState->mCache)
01297        sortInfo.mInner = sortState->mCache;
01298   else
01299        sortInfo.mInner = nsnull;
01300 
01301   if (container != sortState->lastContainer.get()) {
01302     sortState->lastContainer = container;
01303     sortState->lastWasFirst = PR_FALSE;
01304     sortState->lastWasLast = PR_FALSE;
01305   }
01306 
01307   PRBool sortInfoAvailable = PR_FALSE;
01308 
01309   // look for sorting info on root node
01310 
01311   if (NS_SUCCEEDED(rv = root->GetAttr(kNameSpaceID_None, nsXULAtoms::sortResource, sortResource))
01312       && (rv == NS_CONTENT_ATTR_HAS_VALUE))
01313   {
01314     if (NS_SUCCEEDED(rv = root->GetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection, sortDirection))
01315         && (rv == NS_CONTENT_ATTR_HAS_VALUE))
01316     {
01317       sortInfoAvailable = PR_TRUE;
01318 
01319       if (NS_FAILED(rv = root->GetAttr(kNameSpaceID_None, nsXULAtoms::sortResource2, sortResource2)) 
01320           || (rv != NS_CONTENT_ATTR_HAS_VALUE))
01321       {
01322         sortResource2.Truncate();
01323       }
01324     }
01325   }
01326 
01327   if (sortInfoAvailable) {
01328     if (sortState->sortResource.Equals(sortResource) 
01329         && sortState->sortResource2.Equals(sortResource2))
01330     {
01331       sortInfo.sortProperty = sortState->sortProperty;
01332       sortInfo.sortProperty2 = sortState->sortProperty2;
01333       sortInfo.sortPropertyColl = sortState->sortPropertyColl;
01334       sortInfo.sortPropertyColl2 = sortState->sortPropertyColl2;
01335       sortInfo.sortPropertySort = sortState->sortPropertySort;
01336       sortInfo.sortPropertySort2 = sortState->sortPropertySort2;
01337     }
01338     else {
01339       // either first time, or must have changing sorting info, so flush state cache
01340       sortState->sortProperty = nsnull;
01341       sortState->sortProperty2 = nsnull;
01342       sortState->sortPropertyColl = nsnull;
01343       sortState->sortPropertyColl2 = nsnull;
01344       sortState->sortPropertySort = nsnull;
01345       sortState->sortPropertySort2 = nsnull;
01346 
01347       rv = gRDFService->GetUnicodeResource(sortResource, getter_AddRefs(sortInfo.sortProperty));
01348       if (NS_FAILED(rv)) return rv;
01349       sortState->sortResource = sortResource;
01350       sortState->sortProperty = sortInfo.sortProperty;
01351       
01352       nsAutoString resourceUrl = sortResource;
01353       resourceUrl.AppendLiteral("?collation=true");
01354       rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertyColl));
01355       if (NS_FAILED(rv)) return rv;
01356       sortState->sortPropertyColl = sortInfo.sortPropertyColl;
01357 
01358       resourceUrl = sortResource;
01359       resourceUrl.AppendLiteral("?sort=true");
01360       rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertySort));
01361       if (NS_FAILED(rv)) return rv;
01362       sortState->sortPropertySort = sortInfo.sortPropertySort;
01363 
01364       if (!sortResource2.IsEmpty()) {
01365         rv = gRDFService->GetUnicodeResource(sortResource2, getter_AddRefs(sortInfo.sortProperty2));
01366         if (NS_FAILED(rv)) return rv;
01367         sortState->sortResource2 = sortResource2;
01368         sortState->sortProperty2 = sortInfo.sortProperty2;
01369 
01370         resourceUrl = sortResource2;
01371         resourceUrl.AppendLiteral("?collation=true");
01372         rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertyColl2));
01373         if (NS_FAILED(rv)) return rv;
01374         sortState->sortPropertyColl2 = sortInfo.sortPropertyColl2;
01375 
01376         resourceUrl = sortResource2;
01377         resourceUrl.AppendLiteral("?sort=true");
01378         rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertySort2));
01379         if (NS_FAILED(rv)) return rv;
01380         sortState->sortPropertySort2 = sortInfo.sortPropertySort2;
01381       }
01382     }
01383   } else {
01384     // either first time, or must have changing sorting info, so flush state cache
01385     sortState->sortResource.Truncate();
01386     sortState->sortResource2.Truncate();
01387 
01388     sortState->sortProperty = nsnull;
01389     sortState->sortProperty2 = nsnull;
01390     sortState->sortPropertyColl = nsnull;
01391     sortState->sortPropertyColl2 = nsnull;
01392     sortState->sortPropertySort = nsnull;
01393     sortState->sortPropertySort2 = nsnull;
01394   }
01395 
01396   // set up sort order info
01397   sortInfo.naturalOrderSort = PR_FALSE;
01398   sortInfo.descendingSort = PR_FALSE;
01399   if (sortDirection.Equals(*kDescendingStr))
01400     sortInfo.descendingSort = PR_TRUE;
01401   else if (!sortDirection.Equals(*kAscendingStr))
01402     sortInfo.naturalOrderSort = PR_TRUE;
01403 
01404   PRBool isContainerRDFSeq = PR_FALSE;
01405   
01406   if (sortInfo.db && sortInfo.naturalOrderSort) {
01407     // walk up the content model to find the REAL
01408     // parent container to determine if its a RDF_Seq
01409     if (container) {
01410       nsAutoString id;
01411 
01412       rv = trueParent->GetAttr(kNameSpaceID_None, nsXULAtoms::ref, id);
01413       if (id.IsEmpty())
01414         rv = trueParent->GetAttr(kNameSpaceID_None, nsXULAtoms::id, id);
01415 
01416       if (!id.IsEmpty()) {
01417         nsCOMPtr<nsIRDFResource> containerRes;
01418         rv = gRDFService->GetUnicodeResource(id, getter_AddRefs(containerRes));
01419         if (NS_SUCCEEDED(rv))
01420           rv = gRDFC->IsSeq(sortInfo.db, containerRes,  &isContainerRDFSeq);
01421       }
01422     }
01423   }
01424 
01425   PRBool childAdded = PR_FALSE;
01426   PRUint32 numChildren = container->GetChildCount();
01427 
01428   if ((sortInfo.naturalOrderSort == PR_FALSE) ||
01429       ((sortInfo.naturalOrderSort == PR_TRUE) &&
01430        (isContainerRDFSeq == PR_TRUE)))
01431   {
01432     // because numChildren gets modified
01433     PRInt32 realNumChildren = numChildren;
01434     nsIContent *child = nsnull;
01435 
01436     // rjc says: determine where static XUL ends and generated XUL/RDF begins
01437     PRInt32 staticCount = 0;
01438 
01439     nsAutoString staticValue;
01440     if (NS_SUCCEEDED(rv = container->GetAttr(kNameSpaceID_None, nsXULAtoms::staticHint, staticValue))
01441         && (rv == NS_CONTENT_ATTR_HAS_VALUE))
01442     {
01443       // found "static" XUL element count hint
01444       PRInt32 strErr=0;
01445       staticCount = staticValue.ToInteger(&strErr);
01446       if (strErr)
01447         staticCount = 0;
01448     } else {
01449       // compute the "static" XUL element count
01450       nsAutoString  valueStr;
01451       for (PRUint32 childLoop = 0; childLoop < numChildren; ++childLoop) {
01452         child = container->GetChildAt(childLoop);
01453         if (!child) break;
01454 
01455         if (NS_SUCCEEDED(rv = child->GetAttr(kNameSpaceID_None, nsXULAtoms::templateAtom, valueStr))
01456             && (rv == NS_CONTENT_ATTR_HAS_VALUE))
01457           break;
01458         else
01459           ++staticCount;
01460       }
01461       
01462       if (NS_SUCCEEDED(rv = root->GetAttr(kNameSpaceID_None, nsXULAtoms::sortStaticsLast, valueStr))
01463           && (rv == NS_CONTENT_ATTR_HAS_VALUE) && valueStr.EqualsLiteral("true"))
01464       {
01465         // indicate that static XUL comes after RDF-generated content by making negative
01466         staticCount = -staticCount;
01467       }
01468 
01469       // save the "static" XUL element count hint
01470       valueStr.Truncate();
01471       valueStr.AppendInt(staticCount);
01472       container->SetAttr(kNameSpaceID_None, nsXULAtoms::staticHint, valueStr, PR_FALSE);
01473     }
01474 
01475     if (staticCount <= 0) {
01476       numChildren += staticCount;
01477       staticCount = 0;
01478     } else if (staticCount > (PRInt32)numChildren) {
01479       staticCount = numChildren;
01480       numChildren -= staticCount;
01481     }
01482 
01483     // figure out where to insert the node when a sort order is being imposed
01484     if (numChildren > 0) {
01485       nsIContent *temp;
01486       PRInt32 direction;
01487 
01488       // rjc says: The following is an implementation of a fairly optimal
01489       // binary search insertion sort... with interpolation at either end-point.
01490 
01491       if (sortState->lastWasFirst) {
01492         child = container->GetChildAt(staticCount);
01493         temp = child;
01494         direction = inplaceSortCallback(&node, &temp, &sortInfo);
01495         if (direction < 0) {
01496           container->InsertChildAt(node, staticCount, aNotify);
01497           childAdded = PR_TRUE;
01498         } else
01499           sortState->lastWasFirst = PR_FALSE;
01500       } else if (sortState->lastWasLast) {
01501         child = container->GetChildAt(realNumChildren - 1);
01502         temp = child;
01503         direction = inplaceSortCallback(&node, &temp, &sortInfo);
01504         if (direction > 0) {
01505           container->InsertChildAt(node, realNumChildren, aNotify);
01506           childAdded = PR_TRUE;
01507         } else
01508           sortState->lastWasLast = PR_FALSE;
01509       }
01510 
01511       PRInt32 left = staticCount+1, right = realNumChildren, x;
01512       while (!childAdded && right >= left) {
01513         x = (left + right) / 2;
01514         child = container->GetChildAt(x - 1);
01515         temp = child;
01516 
01517         // rjc says: since cacheFirstHint is PR_TRUE, the first node passed
01518         // into inplaceSortCallback() must be the node that doesn't change
01519 
01520         direction = inplaceSortCallback(&node, &temp, &sortInfo);
01521         if (((x == left) && (direction < 0)) || (((x == right))
01522              && (direction >= 0)) || (left == right))
01523         {
01524           PRInt32 thePos = ((direction > 0) ? x : x-1);
01525           container->InsertChildAt(node, thePos, aNotify);
01526           childAdded = PR_TRUE;
01527           
01528           sortState->lastWasFirst = (thePos == staticCount) ? PR_TRUE: PR_FALSE;
01529           sortState->lastWasLast = (thePos >= realNumChildren) ? PR_TRUE: PR_FALSE;
01530           
01531           break;
01532         }
01533         if (direction < 0)
01534           right = x-1;
01535         else
01536           left = x+1;
01537       }
01538     }
01539   }
01540 
01541   if (!childAdded)
01542     container->InsertChildAt(node, numChildren, aNotify);
01543 
01544   if (!sortState->mCache && sortInfo.mInner)
01545     sortState->mCache = sortInfo.mInner;
01546 
01547   return NS_OK;
01548 }
01549 
01550 NS_IMETHODIMP
01551 XULSortServiceImpl::Sort(nsIDOMNode* node, const nsAString& sortResource, const nsAString& sortDirection)
01552 {
01553   nsresult rv;
01554   _sortStruct  sortInfo;
01555 
01556   // get root content node
01557   nsCOMPtr<nsIContent>  contentNode = do_QueryInterface(node);
01558   if (!contentNode) return NS_ERROR_FAILURE;
01559   nsCOMPtr<nsIContent> dbNode;
01560   if (NS_FAILED(rv = FindDatabaseElement(contentNode, getter_AddRefs(dbNode))))
01561     return rv;
01562   nsCOMPtr<nsIDOMXULElement> dbXULNode = do_QueryInterface(dbNode);
01563   if (!dbXULNode) return NS_ERROR_FAILURE;
01564 
01565   // get composite db
01566   sortInfo.db = nsnull;
01567   sortInfo.mInner = nsnull;
01568   sortInfo.parentContainer = dbNode;
01569   sortInfo.inbetweenSeparatorSort = PR_FALSE;
01570   sortInfo.cacheFirstHint = PR_FALSE;
01571 
01572   // optimization - if we're about to merely invert the current sort
01573   // then just reverse-index the current tree
01574   PRBool invertTreeFlag = PR_FALSE;
01575   nsAutoString value;
01576   if (NS_SUCCEEDED(rv = dbNode->GetAttr(kNameSpaceID_None, nsXULAtoms::sortActive, value))
01577       && (rv == NS_CONTENT_ATTR_HAS_VALUE) 
01578       && value.EqualsLiteral("true"))
01579   {
01580     if (NS_SUCCEEDED(rv = dbNode->GetAttr(kNameSpaceID_None, nsXULAtoms::sortResource, value))
01581         && (rv == NS_CONTENT_ATTR_HAS_VALUE) 
01582         && (value.Equals(sortResource)))
01583     {
01584       if (NS_SUCCEEDED(rv = dbNode->GetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection, value))
01585           && (rv == NS_CONTENT_ATTR_HAS_VALUE))
01586       {
01587         if ((value.Equals(*kDescendingStr) && sortDirection.Equals(*kAscendingStr)) 
01588             || (value.Equals(*kAscendingStr) && sortDirection.Equals(*kDescendingStr))) 
01589         {
01590           invertTreeFlag = PR_TRUE;
01591         }
01592       }
01593     }
01594   }
01595 
01596   // remove any sort hints on tree root node
01597   dbNode->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortActive, PR_FALSE);
01598   dbNode->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortDirection, PR_FALSE);
01599   dbNode->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortSeparators, PR_FALSE);
01600   dbNode->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortResource, PR_FALSE);
01601   dbNode->UnsetAttr(kNameSpaceID_None, nsXULAtoms::sortResource2, PR_FALSE);
01602 
01603   nsCOMPtr<nsIRDFCompositeDataSource>  cds;
01604   if (NS_SUCCEEDED(rv = dbXULNode->GetDatabase(getter_AddRefs(cds))))
01605     sortInfo.db = cds;
01606 
01607   // determine new sort resource and direction to use
01608   if (sortDirection.Equals(*kNaturalStr)) {
01609     sortInfo.naturalOrderSort = PR_TRUE;
01610     sortInfo.descendingSort = PR_FALSE;
01611   } else {
01612     sortInfo.naturalOrderSort = PR_FALSE;
01613     if (sortDirection.Equals(*kAscendingStr))
01614       sortInfo.descendingSort = PR_FALSE;
01615     else if (sortDirection.Equals(*kDescendingStr))
01616       sortInfo.descendingSort = PR_TRUE;
01617   }
01618   
01619   // look for additional sort info from content
01620   nsAutoString sortResource2, unused;
01621   GetSortColumnInfo(contentNode, unused, unused, sortResource2, sortInfo.inbetweenSeparatorSort);
01622 
01623   // build resource url for first sort resource
01624   rv = gRDFService->GetUnicodeResource(sortResource, getter_AddRefs(sortInfo.sortProperty));
01625   if (NS_FAILED(rv)) return rv;
01626 
01627   nsAutoString resourceUrl;
01628   resourceUrl.Assign(sortResource);
01629   resourceUrl.AppendLiteral("?collation=true");
01630   rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertyColl));
01631   if (NS_FAILED(rv)) return rv;
01632 
01633   resourceUrl.Assign(sortResource);
01634   resourceUrl.AppendLiteral("?sort=true");
01635   rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertySort));
01636   if (NS_FAILED(rv)) return rv;
01637 
01638   // build resource url for second sort resource
01639   if (!sortResource2.IsEmpty()) {
01640     rv = gRDFService->GetUnicodeResource(sortResource2, getter_AddRefs(sortInfo.sortProperty2));
01641     if (NS_FAILED(rv)) return rv;
01642 
01643     resourceUrl = sortResource2;
01644     resourceUrl.AppendLiteral("?collation=true");
01645     rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertyColl2));
01646     if (NS_FAILED(rv)) return rv;
01647 
01648     resourceUrl = sortResource2;
01649     resourceUrl.AppendLiteral("?sort=true");
01650     rv = gRDFService->GetUnicodeResource(resourceUrl, getter_AddRefs(sortInfo.sortPropertySort2));
01651     if (NS_FAILED(rv)) return rv;
01652   }
01653 
01654   // store sort info in attributes on content
01655   SetSortHints(dbNode, sortResource, sortDirection, sortResource2, sortInfo.inbetweenSeparatorSort, PR_TRUE);
01656 
01657   // start sorting the content
01658   nsCOMPtr<nsIContent> container;
01659   if (NS_FAILED(rv = FindSortableContainer(dbNode, getter_AddRefs(container)))) return rv;
01660   SortContainer(container, &sortInfo, invertTreeFlag);
01661   
01662   // Now remove the db node and re-insert it to force the frames to be rebuilt.
01663   nsCOMPtr<nsIContent> containerParent = container->GetParent();
01664   PRInt32 containerIndex = containerParent->IndexOf(container);
01665   PRInt32 childCount = containerParent->GetChildCount();
01666   rv = containerParent->RemoveChildAt(containerIndex, PR_TRUE);
01667   NS_ENSURE_SUCCESS(rv, rv);
01668   
01669   if (containerIndex+1 < childCount) {
01670     rv = containerParent->InsertChildAt(container, containerIndex, PR_TRUE);
01671   } else {
01672     rv = containerParent->AppendChildTo(container, PR_TRUE);
01673   }
01674   
01675   return rv;
01676 }
01677 
01678 nsresult
01679 NS_NewXULSortService(nsIXULSortService** mgr)
01680 {
01681   XULSortServiceImpl *sortService = new XULSortServiceImpl();
01682   if (!sortService)
01683     return NS_ERROR_OUT_OF_MEMORY;
01684 
01685   *mgr = sortService;
01686   NS_ADDREF(*mgr);
01687 
01688   return NS_OK;
01689 }