diff options
Diffstat (limited to 'dom/xslt/xpath/txNodeSet.cpp')
| -rw-r--r-- | dom/xslt/xpath/txNodeSet.cpp | 622 |
1 files changed, 622 insertions, 0 deletions
diff --git a/dom/xslt/xpath/txNodeSet.cpp b/dom/xslt/xpath/txNodeSet.cpp new file mode 100644 index 000000000..a55317e33 --- /dev/null +++ b/dom/xslt/xpath/txNodeSet.cpp @@ -0,0 +1,622 @@ +/* -*- 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); + + 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) { + 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]; + 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) { + 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*> + (moz_xmalloc(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 + 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)); +} |