The Tor Browser: comparison dom/xslt/xpath/txNodeSet.cpp

--1:000000000000
+:1df78e66b4a8
+/* -*- 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 / file comparison

comparison: dom/xslt/xpath/txNodeSet.cpp

dom/xslt/xpath/txNodeSet.cpp