tor-browser

txNodeSet.cpp (15235B)

---

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* 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 <algorithm>

#include "txLog.h"
#include "txXPathTreeWalker.h"

/**
* 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);

   free(mStartBuffer);
 }
}

nsresult txNodeSet::add(txXPathNode&& aNode) {
 NS_ASSERTION(mDirection == kForward,
              "only append(aNode) is supported on reversed nodesets");

 if (isEmpty()) {
   return append(std::move(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);
   // This move is okay even though txXPathNode is not trivially copyable as
   // the created hole at `pos` is used for inplace new below.
   memmove((void*)(pos + 1), pos, moveSize * sizeof(txXPathNode));
 }

 new (pos) txXPathNode(std::move(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) {
   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((void*)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(txXPathNode&& aNode) {
 if (!ensureGrowSize(1)) {
   return NS_ERROR_OUT_OF_MEMORY;
 }

 if (mDirection == kForward) {
   new (mEnd) txXPathNode(std::move(aNode));
   ++mEnd;

   return NS_OK;
 }

 new (--mStart) txXPathNode(std::move(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];
   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((void*)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) {
   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((void*)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*>(moz_xmalloc(newLength * sizeof(txXPathNode)));

 txXPathNode* dest = newArr;
 if (mDirection == kReversed) {
   dest += newLength - oldSize;
 }

 if (oldSize > 0) {
   LOG_CHUNK_MOVE(mStart, dest, oldSize);
   memcpy((void*)dest, mStart, oldSize * sizeof(txXPathNode));
 }

 if (mStartBuffer) {
#ifdef DEBUG
   memset((void*)mStartBuffer, 0,
          (mEndBuffer - mStartBuffer) * sizeof(txXPathNode));
#endif
   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((void*)aDest, aStart, (aEnd - aStart) * sizeof(txXPathNode));
}