txNodeSet.cpp
/* -*- 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));
}
