Back to index

lightning-sunbird  0.9+nobinonly
txNodeSet.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  * The MITRE Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1999
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Keith Visco <kvisco@ziplink.net> (Original Author)
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "txNodeSet.h"
00040 #include "TxLog.h"
00041 #include "nsMemory.h"
00042 
00047 static const PRInt32 kTxNodeSetMinSize = 4;
00048 static const PRInt32 kTxNodeSetGrowFactor = 2;
00049 
00050 #define kForward   1
00051 #define kReversed -1
00052 
00053 txNodeSet::txNodeSet(txResultRecycler* aRecycler)
00054     : txAExprResult(aRecycler),
00055       mStart(nsnull),
00056       mEnd(nsnull),
00057       mStartBuffer(nsnull),
00058       mEndBuffer(nsnull),
00059       mDirection(kForward),
00060       mMarks(nsnull)
00061 {
00062 }
00063 
00064 txNodeSet::txNodeSet(const txXPathNode& aNode, txResultRecycler* aRecycler)
00065     : txAExprResult(aRecycler),
00066       mStart(nsnull),
00067       mEnd(nsnull),
00068       mStartBuffer(nsnull),
00069       mEndBuffer(nsnull),
00070       mDirection(kForward),
00071       mMarks(nsnull)
00072 {
00073     if (!ensureGrowSize(1)) {
00074         return;
00075     }
00076 
00077     new(mStart) txXPathNode(aNode);
00078     ++mEnd;
00079 }
00080 
00081 txNodeSet::txNodeSet(const txNodeSet& aSource, txResultRecycler* aRecycler)
00082     : txAExprResult(aRecycler),
00083       mStart(nsnull),
00084       mEnd(nsnull),
00085       mStartBuffer(nsnull),
00086       mEndBuffer(nsnull),
00087       mDirection(kForward),
00088       mMarks(nsnull)
00089 {
00090     append(aSource);
00091 }
00092 
00093 txNodeSet::~txNodeSet()
00094 {
00095     delete [] mMarks;
00096 
00097     if (mStartBuffer) {
00098         while (mStart < mEnd) {
00099             mStart->~txXPathNode();
00100             ++mStart;
00101         }
00102 
00103         nsMemory::Free(mStartBuffer);
00104     }
00105 }
00106 
00107 nsresult txNodeSet::add(const txXPathNode& aNode)
00108 {
00109     NS_ASSERTION(mDirection == kForward,
00110                  "only append(aNode) is supported on reversed nodesets");
00111 
00112     if (isEmpty()) {
00113         return append(aNode);
00114     }
00115 
00116     PRBool dupe;
00117     txXPathNode* pos = findPosition(aNode, mStart, mEnd, dupe);
00118 
00119     if (dupe) {
00120         return NS_OK;
00121     }
00122 
00123     // save pos, ensureGrowSize messes with the pointers
00124     PRInt32 moveSize = mEnd - pos;
00125     PRInt32 offset = pos - mStart;
00126     if (!ensureGrowSize(1)) {
00127         return NS_ERROR_OUT_OF_MEMORY;
00128     }
00129     // set pos to where it was
00130     pos = mStart + offset;
00131 
00132     if (moveSize > 0) {
00133         memmove(pos + 1, pos, moveSize * sizeof(txXPathNode));
00134     }
00135 
00136     new(pos) txXPathNode(aNode);
00137     ++mEnd;
00138 
00139     return NS_OK;
00140 }
00141 
00142 nsresult txNodeSet::add(const txNodeSet& aNodes)
00143 {
00144     return add(aNodes, copyElements);
00145 }
00146 
00147 nsresult txNodeSet::addAndTransfer(txNodeSet* aNodes)
00148 {
00149     // failure is out-of-memory, transfer didn't happen
00150     nsresult rv = add(*aNodes, transferElements);
00151     NS_ENSURE_SUCCESS(rv, rv);
00152 
00153 #ifdef TX_DONT_RECYCLE_BUFFER
00154     if (aNodes->mStartBuffer) {
00155         nsMemory::Free(aNodes->mStartBuffer);
00156         aNodes->mStartBuffer = aNodes->mEndBuffer = nsnull;
00157     }
00158 #endif
00159     aNodes->mStart = aNodes->mEnd = aNodes->mStartBuffer;
00160 
00161     return NS_OK;
00162 }
00163 
00205 nsresult txNodeSet::add(const txNodeSet& aNodes, transferOp aTransfer)
00206 {
00207     NS_ASSERTION(mDirection == kForward,
00208                  "only append(aNode) is supported on reversed nodesets");
00209 
00210     if (aNodes.isEmpty()) {
00211         return NS_OK;
00212     }
00213 
00214     if (!ensureGrowSize(aNodes.size())) {
00215         return NS_ERROR_OUT_OF_MEMORY;
00216     }
00217 
00218     // This is probably a rather common case, so lets try to shortcut.
00219     if (mStart == mEnd ||
00220         txXPathNodeUtils::comparePosition(mEnd[-1], *aNodes.mStart) < 0) {
00221         aTransfer(mEnd, aNodes.mStart, aNodes.mEnd);
00222         mEnd += aNodes.size();
00223 
00224         return NS_OK;
00225     }
00226 
00227     // Last element in this nodeset
00228     txXPathNode* thisPos = mEnd;
00229 
00230     // Last element of the other nodeset
00231     txXPathNode* otherPos = aNodes.mEnd;
00232 
00233     // Pointer to the insertion point in this nodeset
00234     txXPathNode* insertPos = mEndBuffer;
00235 
00236     PRBool dupe;
00237     txXPathNode* pos;
00238     PRInt32 count;
00239     while (thisPos > mStart || otherPos > aNodes.mStart) {
00240         // Find where the last remaining node of this nodeset would
00241         // be inserted in the other nodeset.
00242         if (thisPos > mStart) {
00243             pos = findPosition(thisPos[-1], aNodes.mStart, otherPos, dupe);
00244 
00245             if (dupe) {
00246                 --thisPos; // this is already added
00247                 // check dupe sequence
00248                 while (thisPos > mStart && pos > aNodes.mStart &&
00249                        thisPos[-1] == pos[-1]) {
00250                     --thisPos;
00251                     --pos;
00252                 }
00253             }
00254         }
00255         else {
00256             pos = aNodes.mStart;
00257         }
00258 
00259         // Transfer the otherNodes after the insertion point to the result
00260         count = otherPos - pos;
00261         if (count > 0) {
00262             insertPos -= count;
00263             aTransfer(insertPos, pos, otherPos);
00264             otherPos -= count;
00265         }
00266 
00267         // Find where the last remaining node of the otherNodeset would
00268         // be inserted in this nodeset.
00269         if (otherPos > aNodes.mStart) {
00270             pos = findPosition(otherPos[-1], mStart, thisPos, dupe);
00271 
00272             if (dupe) {
00273                 --otherPos; // this is already added
00274                 // check dupe sequence
00275                 while (otherPos > aNodes.mStart && pos > mStart &&
00276                        otherPos[-1] == pos[-1]) {
00277                     --otherPos;
00278                     --pos;
00279                 }
00280             }
00281         }
00282         else {
00283             pos = mStart;
00284         }
00285 
00286         // Move the nodes from this nodeset after the insertion point
00287         // to the result
00288         count = thisPos - pos;
00289         if (count > 0) {
00290             insertPos -= count;
00291             memmove(insertPos, pos, count * sizeof(txXPathNode));
00292             thisPos -= count;
00293         }
00294     }
00295     mStart = insertPos;
00296     mEnd = mEndBuffer;
00297     
00298     return NS_OK;
00299 }
00300 
00311 nsresult
00312 txNodeSet::append(const txXPathNode& aNode)
00313 {
00314     if (!ensureGrowSize(1)) {
00315         return NS_ERROR_OUT_OF_MEMORY;
00316     }
00317 
00318     if (mDirection == kForward) {
00319         new(mEnd) txXPathNode(aNode);
00320         ++mEnd;
00321 
00322         return NS_OK;
00323     }
00324 
00325     new(--mStart) txXPathNode(aNode);
00326 
00327     return NS_OK;
00328 }
00329 
00330 nsresult
00331 txNodeSet::append(const txNodeSet& aNodes)
00332 {
00333     NS_ASSERTION(mDirection == kForward,
00334                  "only append(aNode) is supported on reversed nodesets");
00335 
00336     if (aNodes.isEmpty()) {
00337         return NS_OK;
00338     }
00339 
00340     PRInt32 appended = aNodes.size();
00341     if (!ensureGrowSize(appended)) {
00342         return NS_ERROR_OUT_OF_MEMORY;
00343     }
00344 
00345     copyElements(mEnd, aNodes.mStart, aNodes.mEnd);
00346     mEnd += appended;
00347 
00348     return NS_OK;
00349 }
00350 
00351 nsresult
00352 txNodeSet::mark(PRInt32 aIndex)
00353 {
00354     NS_ASSERTION(aIndex >= 0 && mStart && mEnd - mStart > aIndex,
00355                  "index out of bounds");
00356     if (!mMarks) {
00357         PRInt32 length = size();
00358         mMarks = new PRPackedBool[length];
00359         NS_ENSURE_TRUE(mMarks, NS_ERROR_OUT_OF_MEMORY);
00360         memset(mMarks, 0, length * sizeof(PRPackedBool));
00361     }
00362     if (mDirection == kForward) {
00363         mMarks[aIndex] = PR_TRUE;
00364     }
00365     else {
00366         mMarks[size() - aIndex - 1] = PR_TRUE;
00367     }
00368 
00369     return NS_OK;
00370 }
00371 
00372 nsresult
00373 txNodeSet::sweep()
00374 {
00375     if (!mMarks) {
00376         // sweep everything
00377         clear();
00378     }
00379 
00380     PRInt32 chunk, pos = 0;
00381     PRInt32 length = size();
00382     txXPathNode* insertion = mStartBuffer;
00383 
00384     while (pos < length) {
00385         while (pos < length && !mMarks[pos]) {
00386             // delete unmarked
00387             mStart[pos].~txXPathNode();
00388             ++pos;
00389         }
00390         // find chunk to move
00391         chunk = 0;
00392         while (pos < length && mMarks[pos]) {
00393             ++pos;
00394             ++chunk;
00395         }
00396         // move chunk
00397         if (chunk > 0) {
00398             memmove(insertion, mStart + pos - chunk,
00399                     chunk * sizeof(txXPathNode));
00400             insertion += chunk;
00401         }
00402     }
00403     mStart = mStartBuffer;
00404     mEnd = insertion;
00405     delete [] mMarks;
00406     mMarks = nsnull;
00407 
00408     return NS_OK;
00409 }
00410 
00411 void
00412 txNodeSet::clear()
00413 {
00414     while (mStart < mEnd) {
00415         mStart->~txXPathNode();
00416         ++mStart;
00417     }
00418 #ifdef TX_DONT_RECYCLE_BUFFER
00419     if (mStartBuffer) {
00420         nsMemory::Free(mStartBuffer);
00421         mStartBuffer = mEndBuffer = nsnull;
00422     }
00423 #endif
00424     mStart = mEnd = mStartBuffer;
00425     delete [] mMarks;
00426     mMarks = nsnull;
00427     mDirection = kForward;
00428 }
00429 
00430 PRInt32
00431 txNodeSet::indexOf(const txXPathNode& aNode) const
00432 {
00433     NS_ASSERTION(mDirection == kForward,
00434                  "only append(aNode) is supported on reversed nodesets");
00435 
00436     if (!mStart || mStart == mEnd) {
00437         return -1;
00438     }
00439 
00440     PRInt32 counter = 0;
00441     txXPathNode* pos = mStart;
00442     for (; pos < mEnd; ++counter, ++pos) {
00443         if (*pos == aNode) {
00444             return counter;
00445         }
00446     }
00447 
00448     return -1;
00449 }
00450 
00451 const txXPathNode&
00452 txNodeSet::get(PRInt32 aIndex) const
00453 {
00454     if (mDirection == kForward) {
00455         return mStart[aIndex];
00456     }
00457 
00458     return mEnd[-aIndex - 1];
00459 }
00460 
00461 short
00462 txNodeSet::getResultType()
00463 {
00464     return txAExprResult::NODESET;
00465 }
00466 
00467 PRBool
00468 txNodeSet::booleanValue()
00469 {
00470     return !isEmpty();
00471 }
00472 double
00473 txNodeSet::numberValue()
00474 {
00475     nsAutoString str;
00476     stringValue(str);
00477 
00478     return Double::toDouble(str);
00479 }
00480 
00481 void
00482 txNodeSet::stringValue(nsAString& aStr)
00483 {
00484     NS_ASSERTION(mDirection == kForward,
00485                  "only append(aNode) is supported on reversed nodesets");
00486     if (isEmpty()) {
00487         return;
00488     }
00489     txXPathNodeUtils::appendNodeValue(get(0), aStr);
00490 }
00491 
00492 nsAString*
00493 txNodeSet::stringValuePointer()
00494 {
00495     return nsnull;
00496 }
00497 
00498 PRBool txNodeSet::ensureGrowSize(PRInt32 aSize)
00499 {
00500     // check if there is enough place in the buffer as is
00501     if (mDirection == kForward && aSize <= mEndBuffer - mEnd) {
00502         return PR_TRUE;
00503     }
00504 
00505     if (mDirection == kReversed && aSize <= mStart - mStartBuffer) {
00506         return PR_TRUE;
00507     }
00508 
00509     // check if we just have to align mStart to have enough space
00510     PRInt32 oldSize = mEnd - mStart;
00511     PRInt32 oldLength = mEndBuffer - mStartBuffer;
00512     PRInt32 ensureSize = oldSize + aSize;
00513     if (ensureSize <= oldLength) {
00514         // just move the buffer
00515         txXPathNode* dest = mStartBuffer;
00516         if (mDirection == kReversed) {
00517             dest = mEndBuffer - oldSize;
00518         }
00519         memmove(dest, mStart, oldSize * sizeof(txXPathNode));
00520         mStart = dest;
00521         mEnd = dest + oldSize;
00522             
00523         return PR_TRUE;
00524     }
00525 
00526     // This isn't 100% safe. But until someone manages to make a 1gig nodeset
00527     // it should be ok.
00528     PRInt32 newLength = PR_MAX(oldLength, kTxNodeSetMinSize);
00529 
00530     while (newLength < ensureSize) {
00531         newLength *= kTxNodeSetGrowFactor;
00532     }
00533 
00534     txXPathNode* newArr = NS_STATIC_CAST(txXPathNode*,
00535                                          nsMemory::Alloc(newLength *
00536                                                          sizeof(txXPathNode)));
00537     if (!newArr) {
00538         return PR_FALSE;
00539     }
00540 
00541     txXPathNode* dest = newArr;
00542     if (mDirection == kReversed) {
00543         dest += newLength - oldSize;
00544     }
00545 
00546     if (oldSize > 0) {
00547         memcpy(dest, mStart, oldSize * sizeof(txXPathNode));
00548     }
00549 
00550     if (mStartBuffer) {
00551 #ifdef DEBUG
00552         memset(mStartBuffer, 0,
00553                (mEndBuffer - mStartBuffer) * sizeof(txXPathNode));
00554 #endif
00555         nsMemory::Free(mStartBuffer);
00556     }
00557 
00558     mStartBuffer = newArr;
00559     mEndBuffer = mStartBuffer + newLength;
00560     mStart = dest;
00561     mEnd = dest + oldSize;
00562 
00563     return PR_TRUE;
00564 }
00565 
00566 txXPathNode*
00567 txNodeSet::findPosition(const txXPathNode& aNode, txXPathNode* aFirst,
00568                         txXPathNode* aLast, PRBool& aDupe) const
00569 {
00570     aDupe = PR_FALSE;
00571     if (aLast - aFirst <= 2) {
00572         // If we search 2 nodes or less there is no point in further divides
00573         txXPathNode* pos = aFirst;
00574         for (; pos < aLast; ++pos) {
00575             PRIntn cmp = txXPathNodeUtils::comparePosition(aNode, *pos);
00576             if (cmp < 0) {
00577                 return pos;
00578             }
00579 
00580             if (cmp == 0) {
00581                 aDupe = PR_TRUE;
00582 
00583                 return pos;
00584             }
00585         }
00586         return pos;
00587     }
00588 
00589     // (cannot add two pointers)
00590     txXPathNode* midpos = aFirst + (aLast - aFirst) / 2;
00591     PRIntn cmp = txXPathNodeUtils::comparePosition(aNode, *midpos);
00592     if (cmp == 0) {
00593         aDupe = PR_TRUE;
00594 
00595         return midpos;
00596     }
00597 
00598     if (cmp > 0) {
00599         return findPosition(aNode, midpos + 1, aLast, aDupe);
00600     }
00601 
00602     // midpos excluded as end of range
00603 
00604     return findPosition(aNode, aFirst, midpos, aDupe);
00605 }
00606 
00607 /* static */
00608 void
00609 txNodeSet::copyElements(txXPathNode* aDest,
00610                         const txXPathNode* aStart, const txXPathNode* aEnd)
00611 {
00612     const txXPathNode* pos = aStart;
00613     while (pos < aEnd) {
00614         new(aDest) txXPathNode(*pos);
00615         ++aDest;
00616         ++pos;
00617     }
00618 }
00619 
00620 /* static */
00621 void
00622 txNodeSet::transferElements(txXPathNode* aDest,
00623                             const txXPathNode* aStart, const txXPathNode* aEnd)
00624 {
00625     memcpy(aDest, aStart, (aEnd - aStart) * sizeof(txXPathNode));
00626 }