The Tor Browser: dom/xslt/xpath/txNodeSet.cpp@b8a032363ba2 (annotated)

dom/xslt/xpath/txNodeSet.cpp@b8a032363ba2 (annotated)

dom/xslt/xpath/txNodeSet.cpp

Thu, 22 Jan 2015 13:21:57 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 22 Jan 2015 13:21:57 +0100
branch: TOR_BUG_9701
changeset 15: b8a032363ba2
permissions: -rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 #include "txNodeSet.h"
 #include "txLog.h"
 #include "nsMemory.h"
 #include "txXPathTreeWalker.h"
 #include <algorithm>
 /**
  * Implementation of an XPath nodeset
  */
 #ifdef NS_BUILD_REFCNT_LOGGING
 #define LOG_CHUNK_MOVE(_start, _new_start, _count)            \
 {                                                             \
     txXPathNode *start = const_cast<txXPathNode*>(_start);    \
     while (start < _start + _count) {                         \
         NS_LogDtor(start, "txXPathNode", sizeof(*start));     \
         ++start;                                              \
     }                                                         \
     start = const_cast<txXPathNode*>(_new_start);             \
     while (start < _new_start + _count) {                     \
         NS_LogCtor(start, "txXPathNode", sizeof(*start));     \
         ++start;                                              \
     }                                                         \
 }
 #else
 #define LOG_CHUNK_MOVE(_start, _new_start, _count)
 #endif
 static const int32_t kTxNodeSetMinSize = 4;
 static const int32_t kTxNodeSetGrowFactor = 2;
 #define kForward   1
 #define kReversed -1
 txNodeSet::txNodeSet(txResultRecycler* aRecycler)
     : txAExprResult(aRecycler),
       mStart(nullptr),
       mEnd(nullptr),
       mStartBuffer(nullptr),
       mEndBuffer(nullptr),
       mDirection(kForward),
       mMarks(nullptr)
 {
 }
 txNodeSet::txNodeSet(const txXPathNode& aNode, txResultRecycler* aRecycler)
     : txAExprResult(aRecycler),
       mStart(nullptr),
       mEnd(nullptr),
       mStartBuffer(nullptr),
       mEndBuffer(nullptr),
       mDirection(kForward),
       mMarks(nullptr)
 {
     if (!ensureGrowSize(1)) {
         return;
     }
     new(mStart) txXPathNode(aNode);
     ++mEnd;
 }
 txNodeSet::txNodeSet(const txNodeSet& aSource, txResultRecycler* aRecycler)
     : txAExprResult(aRecycler),
       mStart(nullptr),
       mEnd(nullptr),
       mStartBuffer(nullptr),
       mEndBuffer(nullptr),
       mDirection(kForward),
       mMarks(nullptr)
 {
     append(aSource);
 }
 txNodeSet::~txNodeSet()
 {
     delete [] mMarks;
     if (mStartBuffer) {
         destroyElements(mStart, mEnd);
         nsMemory::Free(mStartBuffer);
     }
 }
 nsresult txNodeSet::add(const txXPathNode& aNode)
 {
     NS_ASSERTION(mDirection == kForward,
                  "only append(aNode) is supported on reversed nodesets");
     if (isEmpty()) {
         return append(aNode);
     }
     bool dupe;
     txXPathNode* pos = findPosition(aNode, mStart, mEnd, dupe);
     if (dupe) {
         return NS_OK;
     }
     // save pos, ensureGrowSize messes with the pointers
     int32_t moveSize = mEnd - pos;
     int32_t offset = pos - mStart;
     if (!ensureGrowSize(1)) {
         return NS_ERROR_OUT_OF_MEMORY;
     }
     // set pos to where it was
     pos = mStart + offset;
     if (moveSize > 0) {
         LOG_CHUNK_MOVE(pos, pos + 1, moveSize);
         memmove(pos + 1, pos, moveSize * sizeof(txXPathNode));
     }
     new(pos) txXPathNode(aNode);
     ++mEnd;
     return NS_OK;
 }
 nsresult txNodeSet::add(const txNodeSet& aNodes)
 {
     return add(aNodes, copyElements, nullptr);
 }
 nsresult txNodeSet::addAndTransfer(txNodeSet* aNodes)
 {
     // failure is out-of-memory, transfer didn't happen
     nsresult rv = add(*aNodes, transferElements, destroyElements);
     NS_ENSURE_SUCCESS(rv, rv);
 #ifdef TX_DONT_RECYCLE_BUFFER
     if (aNodes->mStartBuffer) {
         nsMemory::Free(aNodes->mStartBuffer);
         aNodes->mStartBuffer = aNodes->mEndBuffer = nullptr;
     }
 #endif
     aNodes->mStart = aNodes->mEnd = aNodes->mStartBuffer;
     return NS_OK;
 }
 /**
  * add(aNodeSet, aTransferOp)
  *
  * The code is optimized to make a minimum number of calls to
  * Node::compareDocumentPosition. The idea is this:
  * We have the two nodesets (number indicate "document position")
  *
  * 1 3 7             <- source 1
  * 2 3 6 8 9         <- source 2
  * _ _ _ _ _ _ _ _   <- result
  *
  *
  * When merging these nodesets into the result, the nodes are transfered
  * in chunks to the end of the buffer so that each chunk does not contain
  * a node from the other nodeset, in document order.
  *
  * We select the last non-transfered node in the first nodeset and find
  * where in the other nodeset it would be inserted. In this case we would
  * take the 7 from the first nodeset and find the position between the
  * 6 and 8 in the second. We then take the nodes after the insert-position
  * and transfer them to the end of the resulting nodeset. Which in this case
  * means that we first transfered the 8 and 9 nodes, giving us the following:
  *
  * 1 3 7             <- source 1
  * 2 3 6             <- source 2
  * _ _ _ _ _ _ 8 9   <- result
  *
  * The corresponding procedure is done for the second nodeset, that is
  * the insertion position of the 6 in the first nodeset is found, which
  * is between the 3 and the 7. The 7 is memmoved (as it stays within
  * the same nodeset) to the result buffer.
  *
  * As the result buffer is filled from the end, it is safe to share the
  * buffer between this nodeset and the result.
  *
  * This is repeated until both of the nodesets are empty.
  *
  * If we find a duplicate node when searching for where insertposition we
  * check for sequences of duplicate nodes, which can be optimized.
  *
  */
 nsresult txNodeSet::add(const txNodeSet& aNodes, transferOp aTransfer,
                         destroyOp aDestroy)
 {
     NS_ASSERTION(mDirection == kForward,
                  "only append(aNode) is supported on reversed nodesets");
     if (aNodes.isEmpty()) {
         return NS_OK;
     }
     if (!ensureGrowSize(aNodes.size())) {
         return NS_ERROR_OUT_OF_MEMORY;
     }
     // This is probably a rather common case, so lets try to shortcut.
     if (mStart == mEnd ||
         txXPathNodeUtils::comparePosition(mEnd[-1], *aNodes.mStart) < 0) {
         aTransfer(mEnd, aNodes.mStart, aNodes.mEnd);
         mEnd += aNodes.size();
         return NS_OK;
     }
     // Last element in this nodeset
     txXPathNode* thisPos = mEnd;
     // Last element of the other nodeset
     txXPathNode* otherPos = aNodes.mEnd;
     // Pointer to the insertion point in this nodeset
     txXPathNode* insertPos = mEndBuffer;
     bool dupe;
     txXPathNode* pos;
     int32_t count;
     while (thisPos > mStart || otherPos > aNodes.mStart) {
         // Find where the last remaining node of this nodeset would
         // be inserted in the other nodeset.
         if (thisPos > mStart) {
             pos = findPosition(thisPos[-1], aNodes.mStart, otherPos, dupe);
             if (dupe) {
                 const txXPathNode *deletePos = thisPos;
                 --thisPos; // this is already added
                 // check dupe sequence
                 while (thisPos > mStart && pos > aNodes.mStart &&
                        thisPos[-1] == pos[-1]) {
                     --thisPos;
                     --pos;
                 }
                 if (aDestroy) {
                     aDestroy(thisPos, deletePos);
                 }
             }
         }
         else {
             pos = aNodes.mStart;
         }
         // Transfer the otherNodes after the insertion point to the result
         count = otherPos - pos;
         if (count > 0) {
             insertPos -= count;
             aTransfer(insertPos, pos, otherPos);
             otherPos -= count;
         }
         // Find where the last remaining node of the otherNodeset would
         // be inserted in this nodeset.
         if (otherPos > aNodes.mStart) {
             pos = findPosition(otherPos[-1], mStart, thisPos, dupe);
             if (dupe) {
                 const txXPathNode *deletePos = otherPos;
                 --otherPos; // this is already added
                 // check dupe sequence
                 while (otherPos > aNodes.mStart && pos > mStart &&
                        otherPos[-1] == pos[-1]) {
                     --otherPos;
                     --pos;
                 }
                 if (aDestroy) {
                     aDestroy(otherPos, deletePos);
                 }
             }
         }
         else {
             pos = mStart;
         }
         // Move the nodes from this nodeset after the insertion point
         // to the result
         count = thisPos - pos;
         if (count > 0) {
             insertPos -= count;
             LOG_CHUNK_MOVE(pos, insertPos, count);
             memmove(insertPos, pos, count * sizeof(txXPathNode));
             thisPos -= count;
         }
     }
     mStart = insertPos;
     mEnd = mEndBuffer;
     return NS_OK;
 }
 /**
  * Append API
  * These functions should be used with care.
  * They are intended to be used when the caller assures that the resulting
  * nodeset remains in document order.
  * Abuse will break document order, and cause errors in the result.
  * These functions are significantly faster than the add API, as no
  * order info operations will be performed.
  */
 nsresult
 txNodeSet::append(const txXPathNode& aNode)
 {
     if (!ensureGrowSize(1)) {
         return NS_ERROR_OUT_OF_MEMORY;
     }
     if (mDirection == kForward) {
         new(mEnd) txXPathNode(aNode);
         ++mEnd;
         return NS_OK;
     }
     new(--mStart) txXPathNode(aNode);
     return NS_OK;
 }
 nsresult
 txNodeSet::append(const txNodeSet& aNodes)
 {
     NS_ASSERTION(mDirection == kForward,
                  "only append(aNode) is supported on reversed nodesets");
     if (aNodes.isEmpty()) {
         return NS_OK;
     }
     int32_t appended = aNodes.size();
     if (!ensureGrowSize(appended)) {
         return NS_ERROR_OUT_OF_MEMORY;
     }
     copyElements(mEnd, aNodes.mStart, aNodes.mEnd);
     mEnd += appended;
     return NS_OK;
 }
 nsresult
 txNodeSet::mark(int32_t aIndex)
 {
     NS_ASSERTION(aIndex >= 0 && mStart && mEnd - mStart > aIndex,
                  "index out of bounds");
     if (!mMarks) {
         int32_t length = size();
         mMarks = new bool[length];
         NS_ENSURE_TRUE(mMarks, NS_ERROR_OUT_OF_MEMORY);
         memset(mMarks, 0, length * sizeof(bool));
     }
     if (mDirection == kForward) {
         mMarks[aIndex] = true;
     }
     else {
         mMarks[size() - aIndex - 1] = true;
     }
     return NS_OK;
 }
 nsresult
 txNodeSet::sweep()
 {
     if (!mMarks) {
         // sweep everything
         clear();
     }
     int32_t chunk, pos = 0;
     int32_t length = size();
     txXPathNode* insertion = mStartBuffer;
     while (pos < length) {
         while (pos < length && !mMarks[pos]) {
             // delete unmarked
             mStart[pos].~txXPathNode();
             ++pos;
         }
         // find chunk to move
         chunk = 0;
         while (pos < length && mMarks[pos]) {
             ++pos;
             ++chunk;
         }
         // move chunk
         if (chunk > 0) {
             LOG_CHUNK_MOVE(mStart + pos - chunk, insertion, chunk);
             memmove(insertion, mStart + pos - chunk,
                     chunk * sizeof(txXPathNode));
             insertion += chunk;
         }
     }
     mStart = mStartBuffer;
     mEnd = insertion;
     delete [] mMarks;
     mMarks = nullptr;
     return NS_OK;
 }
 void
 txNodeSet::clear()
 {
     destroyElements(mStart, mEnd);
 #ifdef TX_DONT_RECYCLE_BUFFER
     if (mStartBuffer) {
         nsMemory::Free(mStartBuffer);
         mStartBuffer = mEndBuffer = nullptr;
     }
 #endif
     mStart = mEnd = mStartBuffer;
     delete [] mMarks;
     mMarks = nullptr;
     mDirection = kForward;
 }
 int32_t
 txNodeSet::indexOf(const txXPathNode& aNode, uint32_t aStart) const
 {
     NS_ASSERTION(mDirection == kForward,
                  "only append(aNode) is supported on reversed nodesets");
     if (!mStart || mStart == mEnd) {
         return -1;
     }
     txXPathNode* pos = mStart + aStart;
     for (; pos < mEnd; ++pos) {
         if (*pos == aNode) {
             return pos - mStart;
         }
     }
     return -1;
 }
 const txXPathNode&
 txNodeSet::get(int32_t aIndex) const
 {
     if (mDirection == kForward) {
         return mStart[aIndex];
     }
     return mEnd[-aIndex - 1];
 }
 short
 txNodeSet::getResultType()
 {
     return txAExprResult::NODESET;
 }
 bool
 txNodeSet::booleanValue()
 {
     return !isEmpty();
 }
 double
 txNodeSet::numberValue()
 {
     nsAutoString str;
     stringValue(str);
     return txDouble::toDouble(str);
 }
 void
 txNodeSet::stringValue(nsString& aStr)
 {
     NS_ASSERTION(mDirection == kForward,
                  "only append(aNode) is supported on reversed nodesets");
     if (isEmpty()) {
         return;
     }
     txXPathNodeUtils::appendNodeValue(get(0), aStr);
 }
 const nsString*
 txNodeSet::stringValuePointer()
 {
     return nullptr;
 }
 bool txNodeSet::ensureGrowSize(int32_t aSize)
 {
     // check if there is enough place in the buffer as is
     if (mDirection == kForward && aSize <= mEndBuffer - mEnd) {
         return true;
     }
     if (mDirection == kReversed && aSize <= mStart - mStartBuffer) {
         return true;
     }
     // check if we just have to align mStart to have enough space
     int32_t oldSize = mEnd - mStart;
     int32_t oldLength = mEndBuffer - mStartBuffer;
     int32_t ensureSize = oldSize + aSize;
     if (ensureSize <= oldLength) {
         // just move the buffer
         txXPathNode* dest = mStartBuffer;
         if (mDirection == kReversed) {
             dest = mEndBuffer - oldSize;
         }
         LOG_CHUNK_MOVE(mStart, dest, oldSize);
         memmove(dest, mStart, oldSize * sizeof(txXPathNode));
         mStart = dest;
         mEnd = dest + oldSize;
         return true;
     }
     // This isn't 100% safe. But until someone manages to make a 1gig nodeset
     // it should be ok.
     int32_t newLength = std::max(oldLength, kTxNodeSetMinSize);
     while (newLength < ensureSize) {
         newLength *= kTxNodeSetGrowFactor;
     }
     txXPathNode* newArr = static_cast<txXPathNode*>
                                      (nsMemory::Alloc(newLength *
                                                          sizeof(txXPathNode)));
     if (!newArr) {
         return false;
     }
     txXPathNode* dest = newArr;
     if (mDirection == kReversed) {
         dest += newLength - oldSize;
     }
     if (oldSize > 0) {
         LOG_CHUNK_MOVE(mStart, dest, oldSize);
         memcpy(dest, mStart, oldSize * sizeof(txXPathNode));
     }
     if (mStartBuffer) {
 #ifdef DEBUG
         memset(mStartBuffer, 0,
                (mEndBuffer - mStartBuffer) * sizeof(txXPathNode));
 #endif
         nsMemory::Free(mStartBuffer);
     }
     mStartBuffer = newArr;
     mEndBuffer = mStartBuffer + newLength;
     mStart = dest;
     mEnd = dest + oldSize;
     return true;
 }
 txXPathNode*
 txNodeSet::findPosition(const txXPathNode& aNode, txXPathNode* aFirst,
                         txXPathNode* aLast, bool& aDupe) const
 {
     aDupe = false;
     if (aLast - aFirst <= 2) {
         // If we search 2 nodes or less there is no point in further divides
         txXPathNode* pos = aFirst;
         for (; pos < aLast; ++pos) {
             int cmp = txXPathNodeUtils::comparePosition(aNode, *pos);
             if (cmp < 0) {
                 return pos;
             }
             if (cmp == 0) {
                 aDupe = true;
                 return pos;
             }
         }
         return pos;
     }
     // (cannot add two pointers)
     txXPathNode* midpos = aFirst + (aLast - aFirst) / 2;
     int cmp = txXPathNodeUtils::comparePosition(aNode, *midpos);
     if (cmp == 0) {
         aDupe = true;
         return midpos;
     }
     if (cmp > 0) {
         return findPosition(aNode, midpos + 1, aLast, aDupe);
     }
     // midpos excluded as end of range
     return findPosition(aNode, aFirst, midpos, aDupe);
 }
 /* static */
 void
 txNodeSet::copyElements(txXPathNode* aDest,
                         const txXPathNode* aStart, const txXPathNode* aEnd)
 {
     const txXPathNode* pos = aStart;
     while (pos < aEnd) {
         new(aDest) txXPathNode(*pos);
         ++aDest;
         ++pos;
     }
 }
 /* static */
 void
 txNodeSet::transferElements(txXPathNode* aDest,
                             const txXPathNode* aStart, const txXPathNode* aEnd)
 {
     LOG_CHUNK_MOVE(aStart, aDest, (aEnd - aStart));
     memcpy(aDest, aStart, (aEnd - aStart) * sizeof(txXPathNode));
 }

The Tor Browser / annotate

dom/xslt/xpath/txNodeSet.cpp@b8a032363ba2 (annotated)

dom/xslt/xpath/txNodeSet.cpp