summaryrefslogtreecommitdiffstats
path: root/dom/xslt/xpath/txNodeSet.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'dom/xslt/xpath/txNodeSet.cpp')
-rw-r--r--dom/xslt/xpath/txNodeSet.cpp622
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));
+}