1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/dom/xslt/xpath/txNodeSet.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,623 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "txNodeSet.h"
1.10 +#include "txLog.h"
1.11 +#include "nsMemory.h"
1.12 +#include "txXPathTreeWalker.h"
1.13 +#include <algorithm>
1.14 +
1.15 +/**
1.16 + * Implementation of an XPath nodeset
1.17 + */
1.18 +
1.19 +#ifdef NS_BUILD_REFCNT_LOGGING
1.20 +#define LOG_CHUNK_MOVE(_start, _new_start, _count) \
1.21 +{ \
1.22 + txXPathNode *start = const_cast<txXPathNode*>(_start); \
1.23 + while (start < _start + _count) { \
1.24 + NS_LogDtor(start, "txXPathNode", sizeof(*start)); \
1.25 + ++start; \
1.26 + } \
1.27 + start = const_cast<txXPathNode*>(_new_start); \
1.28 + while (start < _new_start + _count) { \
1.29 + NS_LogCtor(start, "txXPathNode", sizeof(*start)); \
1.30 + ++start; \
1.31 + } \
1.32 +}
1.33 +#else
1.34 +#define LOG_CHUNK_MOVE(_start, _new_start, _count)
1.35 +#endif
1.36 +
1.37 +static const int32_t kTxNodeSetMinSize = 4;
1.38 +static const int32_t kTxNodeSetGrowFactor = 2;
1.39 +
1.40 +#define kForward 1
1.41 +#define kReversed -1
1.42 +
1.43 +txNodeSet::txNodeSet(txResultRecycler* aRecycler)
1.44 + : txAExprResult(aRecycler),
1.45 + mStart(nullptr),
1.46 + mEnd(nullptr),
1.47 + mStartBuffer(nullptr),
1.48 + mEndBuffer(nullptr),
1.49 + mDirection(kForward),
1.50 + mMarks(nullptr)
1.51 +{
1.52 +}
1.53 +
1.54 +txNodeSet::txNodeSet(const txXPathNode& aNode, txResultRecycler* aRecycler)
1.55 + : txAExprResult(aRecycler),
1.56 + mStart(nullptr),
1.57 + mEnd(nullptr),
1.58 + mStartBuffer(nullptr),
1.59 + mEndBuffer(nullptr),
1.60 + mDirection(kForward),
1.61 + mMarks(nullptr)
1.62 +{
1.63 + if (!ensureGrowSize(1)) {
1.64 + return;
1.65 + }
1.66 +
1.67 + new(mStart) txXPathNode(aNode);
1.68 + ++mEnd;
1.69 +}
1.70 +
1.71 +txNodeSet::txNodeSet(const txNodeSet& aSource, txResultRecycler* aRecycler)
1.72 + : txAExprResult(aRecycler),
1.73 + mStart(nullptr),
1.74 + mEnd(nullptr),
1.75 + mStartBuffer(nullptr),
1.76 + mEndBuffer(nullptr),
1.77 + mDirection(kForward),
1.78 + mMarks(nullptr)
1.79 +{
1.80 + append(aSource);
1.81 +}
1.82 +
1.83 +txNodeSet::~txNodeSet()
1.84 +{
1.85 + delete [] mMarks;
1.86 +
1.87 + if (mStartBuffer) {
1.88 + destroyElements(mStart, mEnd);
1.89 +
1.90 + nsMemory::Free(mStartBuffer);
1.91 + }
1.92 +}
1.93 +
1.94 +nsresult txNodeSet::add(const txXPathNode& aNode)
1.95 +{
1.96 + NS_ASSERTION(mDirection == kForward,
1.97 + "only append(aNode) is supported on reversed nodesets");
1.98 +
1.99 + if (isEmpty()) {
1.100 + return append(aNode);
1.101 + }
1.102 +
1.103 + bool dupe;
1.104 + txXPathNode* pos = findPosition(aNode, mStart, mEnd, dupe);
1.105 +
1.106 + if (dupe) {
1.107 + return NS_OK;
1.108 + }
1.109 +
1.110 + // save pos, ensureGrowSize messes with the pointers
1.111 + int32_t moveSize = mEnd - pos;
1.112 + int32_t offset = pos - mStart;
1.113 + if (!ensureGrowSize(1)) {
1.114 + return NS_ERROR_OUT_OF_MEMORY;
1.115 + }
1.116 + // set pos to where it was
1.117 + pos = mStart + offset;
1.118 +
1.119 + if (moveSize > 0) {
1.120 + LOG_CHUNK_MOVE(pos, pos + 1, moveSize);
1.121 + memmove(pos + 1, pos, moveSize * sizeof(txXPathNode));
1.122 + }
1.123 +
1.124 + new(pos) txXPathNode(aNode);
1.125 + ++mEnd;
1.126 +
1.127 + return NS_OK;
1.128 +}
1.129 +
1.130 +nsresult txNodeSet::add(const txNodeSet& aNodes)
1.131 +{
1.132 + return add(aNodes, copyElements, nullptr);
1.133 +}
1.134 +
1.135 +nsresult txNodeSet::addAndTransfer(txNodeSet* aNodes)
1.136 +{
1.137 + // failure is out-of-memory, transfer didn't happen
1.138 + nsresult rv = add(*aNodes, transferElements, destroyElements);
1.139 + NS_ENSURE_SUCCESS(rv, rv);
1.140 +
1.141 +#ifdef TX_DONT_RECYCLE_BUFFER
1.142 + if (aNodes->mStartBuffer) {
1.143 + nsMemory::Free(aNodes->mStartBuffer);
1.144 + aNodes->mStartBuffer = aNodes->mEndBuffer = nullptr;
1.145 + }
1.146 +#endif
1.147 + aNodes->mStart = aNodes->mEnd = aNodes->mStartBuffer;
1.148 +
1.149 + return NS_OK;
1.150 +}
1.151 +
1.152 +/**
1.153 + * add(aNodeSet, aTransferOp)
1.154 + *
1.155 + * The code is optimized to make a minimum number of calls to
1.156 + * Node::compareDocumentPosition. The idea is this:
1.157 + * We have the two nodesets (number indicate "document position")
1.158 + *
1.159 + * 1 3 7 <- source 1
1.160 + * 2 3 6 8 9 <- source 2
1.161 + * _ _ _ _ _ _ _ _ <- result
1.162 + *
1.163 + *
1.164 + * When merging these nodesets into the result, the nodes are transfered
1.165 + * in chunks to the end of the buffer so that each chunk does not contain
1.166 + * a node from the other nodeset, in document order.
1.167 + *
1.168 + * We select the last non-transfered node in the first nodeset and find
1.169 + * where in the other nodeset it would be inserted. In this case we would
1.170 + * take the 7 from the first nodeset and find the position between the
1.171 + * 6 and 8 in the second. We then take the nodes after the insert-position
1.172 + * and transfer them to the end of the resulting nodeset. Which in this case
1.173 + * means that we first transfered the 8 and 9 nodes, giving us the following:
1.174 + *
1.175 + * 1 3 7 <- source 1
1.176 + * 2 3 6 <- source 2
1.177 + * _ _ _ _ _ _ 8 9 <- result
1.178 + *
1.179 + * The corresponding procedure is done for the second nodeset, that is
1.180 + * the insertion position of the 6 in the first nodeset is found, which
1.181 + * is between the 3 and the 7. The 7 is memmoved (as it stays within
1.182 + * the same nodeset) to the result buffer.
1.183 + *
1.184 + * As the result buffer is filled from the end, it is safe to share the
1.185 + * buffer between this nodeset and the result.
1.186 + *
1.187 + * This is repeated until both of the nodesets are empty.
1.188 + *
1.189 + * If we find a duplicate node when searching for where insertposition we
1.190 + * check for sequences of duplicate nodes, which can be optimized.
1.191 + *
1.192 + */
1.193 +nsresult txNodeSet::add(const txNodeSet& aNodes, transferOp aTransfer,
1.194 + destroyOp aDestroy)
1.195 +{
1.196 + NS_ASSERTION(mDirection == kForward,
1.197 + "only append(aNode) is supported on reversed nodesets");
1.198 +
1.199 + if (aNodes.isEmpty()) {
1.200 + return NS_OK;
1.201 + }
1.202 +
1.203 + if (!ensureGrowSize(aNodes.size())) {
1.204 + return NS_ERROR_OUT_OF_MEMORY;
1.205 + }
1.206 +
1.207 + // This is probably a rather common case, so lets try to shortcut.
1.208 + if (mStart == mEnd ||
1.209 + txXPathNodeUtils::comparePosition(mEnd[-1], *aNodes.mStart) < 0) {
1.210 + aTransfer(mEnd, aNodes.mStart, aNodes.mEnd);
1.211 + mEnd += aNodes.size();
1.212 +
1.213 + return NS_OK;
1.214 + }
1.215 +
1.216 + // Last element in this nodeset
1.217 + txXPathNode* thisPos = mEnd;
1.218 +
1.219 + // Last element of the other nodeset
1.220 + txXPathNode* otherPos = aNodes.mEnd;
1.221 +
1.222 + // Pointer to the insertion point in this nodeset
1.223 + txXPathNode* insertPos = mEndBuffer;
1.224 +
1.225 + bool dupe;
1.226 + txXPathNode* pos;
1.227 + int32_t count;
1.228 + while (thisPos > mStart || otherPos > aNodes.mStart) {
1.229 + // Find where the last remaining node of this nodeset would
1.230 + // be inserted in the other nodeset.
1.231 + if (thisPos > mStart) {
1.232 + pos = findPosition(thisPos[-1], aNodes.mStart, otherPos, dupe);
1.233 +
1.234 + if (dupe) {
1.235 + const txXPathNode *deletePos = thisPos;
1.236 + --thisPos; // this is already added
1.237 + // check dupe sequence
1.238 + while (thisPos > mStart && pos > aNodes.mStart &&
1.239 + thisPos[-1] == pos[-1]) {
1.240 + --thisPos;
1.241 + --pos;
1.242 + }
1.243 +
1.244 + if (aDestroy) {
1.245 + aDestroy(thisPos, deletePos);
1.246 + }
1.247 + }
1.248 + }
1.249 + else {
1.250 + pos = aNodes.mStart;
1.251 + }
1.252 +
1.253 + // Transfer the otherNodes after the insertion point to the result
1.254 + count = otherPos - pos;
1.255 + if (count > 0) {
1.256 + insertPos -= count;
1.257 + aTransfer(insertPos, pos, otherPos);
1.258 + otherPos -= count;
1.259 + }
1.260 +
1.261 + // Find where the last remaining node of the otherNodeset would
1.262 + // be inserted in this nodeset.
1.263 + if (otherPos > aNodes.mStart) {
1.264 + pos = findPosition(otherPos[-1], mStart, thisPos, dupe);
1.265 +
1.266 + if (dupe) {
1.267 + const txXPathNode *deletePos = otherPos;
1.268 + --otherPos; // this is already added
1.269 + // check dupe sequence
1.270 + while (otherPos > aNodes.mStart && pos > mStart &&
1.271 + otherPos[-1] == pos[-1]) {
1.272 + --otherPos;
1.273 + --pos;
1.274 + }
1.275 +
1.276 + if (aDestroy) {
1.277 + aDestroy(otherPos, deletePos);
1.278 + }
1.279 + }
1.280 + }
1.281 + else {
1.282 + pos = mStart;
1.283 + }
1.284 +
1.285 + // Move the nodes from this nodeset after the insertion point
1.286 + // to the result
1.287 + count = thisPos - pos;
1.288 + if (count > 0) {
1.289 + insertPos -= count;
1.290 + LOG_CHUNK_MOVE(pos, insertPos, count);
1.291 + memmove(insertPos, pos, count * sizeof(txXPathNode));
1.292 + thisPos -= count;
1.293 + }
1.294 + }
1.295 + mStart = insertPos;
1.296 + mEnd = mEndBuffer;
1.297 +
1.298 + return NS_OK;
1.299 +}
1.300 +
1.301 +/**
1.302 + * Append API
1.303 + * These functions should be used with care.
1.304 + * They are intended to be used when the caller assures that the resulting
1.305 + * nodeset remains in document order.
1.306 + * Abuse will break document order, and cause errors in the result.
1.307 + * These functions are significantly faster than the add API, as no
1.308 + * order info operations will be performed.
1.309 + */
1.310 +
1.311 +nsresult
1.312 +txNodeSet::append(const txXPathNode& aNode)
1.313 +{
1.314 + if (!ensureGrowSize(1)) {
1.315 + return NS_ERROR_OUT_OF_MEMORY;
1.316 + }
1.317 +
1.318 + if (mDirection == kForward) {
1.319 + new(mEnd) txXPathNode(aNode);
1.320 + ++mEnd;
1.321 +
1.322 + return NS_OK;
1.323 + }
1.324 +
1.325 + new(--mStart) txXPathNode(aNode);
1.326 +
1.327 + return NS_OK;
1.328 +}
1.329 +
1.330 +nsresult
1.331 +txNodeSet::append(const txNodeSet& aNodes)
1.332 +{
1.333 + NS_ASSERTION(mDirection == kForward,
1.334 + "only append(aNode) is supported on reversed nodesets");
1.335 +
1.336 + if (aNodes.isEmpty()) {
1.337 + return NS_OK;
1.338 + }
1.339 +
1.340 + int32_t appended = aNodes.size();
1.341 + if (!ensureGrowSize(appended)) {
1.342 + return NS_ERROR_OUT_OF_MEMORY;
1.343 + }
1.344 +
1.345 + copyElements(mEnd, aNodes.mStart, aNodes.mEnd);
1.346 + mEnd += appended;
1.347 +
1.348 + return NS_OK;
1.349 +}
1.350 +
1.351 +nsresult
1.352 +txNodeSet::mark(int32_t aIndex)
1.353 +{
1.354 + NS_ASSERTION(aIndex >= 0 && mStart && mEnd - mStart > aIndex,
1.355 + "index out of bounds");
1.356 + if (!mMarks) {
1.357 + int32_t length = size();
1.358 + mMarks = new bool[length];
1.359 + NS_ENSURE_TRUE(mMarks, NS_ERROR_OUT_OF_MEMORY);
1.360 + memset(mMarks, 0, length * sizeof(bool));
1.361 + }
1.362 + if (mDirection == kForward) {
1.363 + mMarks[aIndex] = true;
1.364 + }
1.365 + else {
1.366 + mMarks[size() - aIndex - 1] = true;
1.367 + }
1.368 +
1.369 + return NS_OK;
1.370 +}
1.371 +
1.372 +nsresult
1.373 +txNodeSet::sweep()
1.374 +{
1.375 + if (!mMarks) {
1.376 + // sweep everything
1.377 + clear();
1.378 + }
1.379 +
1.380 + int32_t chunk, pos = 0;
1.381 + int32_t length = size();
1.382 + txXPathNode* insertion = mStartBuffer;
1.383 +
1.384 + while (pos < length) {
1.385 + while (pos < length && !mMarks[pos]) {
1.386 + // delete unmarked
1.387 + mStart[pos].~txXPathNode();
1.388 + ++pos;
1.389 + }
1.390 + // find chunk to move
1.391 + chunk = 0;
1.392 + while (pos < length && mMarks[pos]) {
1.393 + ++pos;
1.394 + ++chunk;
1.395 + }
1.396 + // move chunk
1.397 + if (chunk > 0) {
1.398 + LOG_CHUNK_MOVE(mStart + pos - chunk, insertion, chunk);
1.399 + memmove(insertion, mStart + pos - chunk,
1.400 + chunk * sizeof(txXPathNode));
1.401 + insertion += chunk;
1.402 + }
1.403 + }
1.404 + mStart = mStartBuffer;
1.405 + mEnd = insertion;
1.406 + delete [] mMarks;
1.407 + mMarks = nullptr;
1.408 +
1.409 + return NS_OK;
1.410 +}
1.411 +
1.412 +void
1.413 +txNodeSet::clear()
1.414 +{
1.415 + destroyElements(mStart, mEnd);
1.416 +#ifdef TX_DONT_RECYCLE_BUFFER
1.417 + if (mStartBuffer) {
1.418 + nsMemory::Free(mStartBuffer);
1.419 + mStartBuffer = mEndBuffer = nullptr;
1.420 + }
1.421 +#endif
1.422 + mStart = mEnd = mStartBuffer;
1.423 + delete [] mMarks;
1.424 + mMarks = nullptr;
1.425 + mDirection = kForward;
1.426 +}
1.427 +
1.428 +int32_t
1.429 +txNodeSet::indexOf(const txXPathNode& aNode, uint32_t aStart) const
1.430 +{
1.431 + NS_ASSERTION(mDirection == kForward,
1.432 + "only append(aNode) is supported on reversed nodesets");
1.433 +
1.434 + if (!mStart || mStart == mEnd) {
1.435 + return -1;
1.436 + }
1.437 +
1.438 + txXPathNode* pos = mStart + aStart;
1.439 + for (; pos < mEnd; ++pos) {
1.440 + if (*pos == aNode) {
1.441 + return pos - mStart;
1.442 + }
1.443 + }
1.444 +
1.445 + return -1;
1.446 +}
1.447 +
1.448 +const txXPathNode&
1.449 +txNodeSet::get(int32_t aIndex) const
1.450 +{
1.451 + if (mDirection == kForward) {
1.452 + return mStart[aIndex];
1.453 + }
1.454 +
1.455 + return mEnd[-aIndex - 1];
1.456 +}
1.457 +
1.458 +short
1.459 +txNodeSet::getResultType()
1.460 +{
1.461 + return txAExprResult::NODESET;
1.462 +}
1.463 +
1.464 +bool
1.465 +txNodeSet::booleanValue()
1.466 +{
1.467 + return !isEmpty();
1.468 +}
1.469 +double
1.470 +txNodeSet::numberValue()
1.471 +{
1.472 + nsAutoString str;
1.473 + stringValue(str);
1.474 +
1.475 + return txDouble::toDouble(str);
1.476 +}
1.477 +
1.478 +void
1.479 +txNodeSet::stringValue(nsString& aStr)
1.480 +{
1.481 + NS_ASSERTION(mDirection == kForward,
1.482 + "only append(aNode) is supported on reversed nodesets");
1.483 + if (isEmpty()) {
1.484 + return;
1.485 + }
1.486 + txXPathNodeUtils::appendNodeValue(get(0), aStr);
1.487 +}
1.488 +
1.489 +const nsString*
1.490 +txNodeSet::stringValuePointer()
1.491 +{
1.492 + return nullptr;
1.493 +}
1.494 +
1.495 +bool txNodeSet::ensureGrowSize(int32_t aSize)
1.496 +{
1.497 + // check if there is enough place in the buffer as is
1.498 + if (mDirection == kForward && aSize <= mEndBuffer - mEnd) {
1.499 + return true;
1.500 + }
1.501 +
1.502 + if (mDirection == kReversed && aSize <= mStart - mStartBuffer) {
1.503 + return true;
1.504 + }
1.505 +
1.506 + // check if we just have to align mStart to have enough space
1.507 + int32_t oldSize = mEnd - mStart;
1.508 + int32_t oldLength = mEndBuffer - mStartBuffer;
1.509 + int32_t ensureSize = oldSize + aSize;
1.510 + if (ensureSize <= oldLength) {
1.511 + // just move the buffer
1.512 + txXPathNode* dest = mStartBuffer;
1.513 + if (mDirection == kReversed) {
1.514 + dest = mEndBuffer - oldSize;
1.515 + }
1.516 + LOG_CHUNK_MOVE(mStart, dest, oldSize);
1.517 + memmove(dest, mStart, oldSize * sizeof(txXPathNode));
1.518 + mStart = dest;
1.519 + mEnd = dest + oldSize;
1.520 +
1.521 + return true;
1.522 + }
1.523 +
1.524 + // This isn't 100% safe. But until someone manages to make a 1gig nodeset
1.525 + // it should be ok.
1.526 + int32_t newLength = std::max(oldLength, kTxNodeSetMinSize);
1.527 +
1.528 + while (newLength < ensureSize) {
1.529 + newLength *= kTxNodeSetGrowFactor;
1.530 + }
1.531 +
1.532 + txXPathNode* newArr = static_cast<txXPathNode*>
1.533 + (nsMemory::Alloc(newLength *
1.534 + sizeof(txXPathNode)));
1.535 + if (!newArr) {
1.536 + return false;
1.537 + }
1.538 +
1.539 + txXPathNode* dest = newArr;
1.540 + if (mDirection == kReversed) {
1.541 + dest += newLength - oldSize;
1.542 + }
1.543 +
1.544 + if (oldSize > 0) {
1.545 + LOG_CHUNK_MOVE(mStart, dest, oldSize);
1.546 + memcpy(dest, mStart, oldSize * sizeof(txXPathNode));
1.547 + }
1.548 +
1.549 + if (mStartBuffer) {
1.550 +#ifdef DEBUG
1.551 + memset(mStartBuffer, 0,
1.552 + (mEndBuffer - mStartBuffer) * sizeof(txXPathNode));
1.553 +#endif
1.554 + nsMemory::Free(mStartBuffer);
1.555 + }
1.556 +
1.557 + mStartBuffer = newArr;
1.558 + mEndBuffer = mStartBuffer + newLength;
1.559 + mStart = dest;
1.560 + mEnd = dest + oldSize;
1.561 +
1.562 + return true;
1.563 +}
1.564 +
1.565 +txXPathNode*
1.566 +txNodeSet::findPosition(const txXPathNode& aNode, txXPathNode* aFirst,
1.567 + txXPathNode* aLast, bool& aDupe) const
1.568 +{
1.569 + aDupe = false;
1.570 + if (aLast - aFirst <= 2) {
1.571 + // If we search 2 nodes or less there is no point in further divides
1.572 + txXPathNode* pos = aFirst;
1.573 + for (; pos < aLast; ++pos) {
1.574 + int cmp = txXPathNodeUtils::comparePosition(aNode, *pos);
1.575 + if (cmp < 0) {
1.576 + return pos;
1.577 + }
1.578 +
1.579 + if (cmp == 0) {
1.580 + aDupe = true;
1.581 +
1.582 + return pos;
1.583 + }
1.584 + }
1.585 + return pos;
1.586 + }
1.587 +
1.588 + // (cannot add two pointers)
1.589 + txXPathNode* midpos = aFirst + (aLast - aFirst) / 2;
1.590 + int cmp = txXPathNodeUtils::comparePosition(aNode, *midpos);
1.591 + if (cmp == 0) {
1.592 + aDupe = true;
1.593 +
1.594 + return midpos;
1.595 + }
1.596 +
1.597 + if (cmp > 0) {
1.598 + return findPosition(aNode, midpos + 1, aLast, aDupe);
1.599 + }
1.600 +
1.601 + // midpos excluded as end of range
1.602 +
1.603 + return findPosition(aNode, aFirst, midpos, aDupe);
1.604 +}
1.605 +
1.606 +/* static */
1.607 +void
1.608 +txNodeSet::copyElements(txXPathNode* aDest,
1.609 + const txXPathNode* aStart, const txXPathNode* aEnd)
1.610 +{
1.611 + const txXPathNode* pos = aStart;
1.612 + while (pos < aEnd) {
1.613 + new(aDest) txXPathNode(*pos);
1.614 + ++aDest;
1.615 + ++pos;
1.616 + }
1.617 +}
1.618 +
1.619 +/* static */
1.620 +void
1.621 +txNodeSet::transferElements(txXPathNode* aDest,
1.622 + const txXPathNode* aStart, const txXPathNode* aEnd)
1.623 +{
1.624 + LOG_CHUNK_MOVE(aStart, aDest, (aEnd - aStart));
1.625 + memcpy(aDest, aStart, (aEnd - aStart) * sizeof(txXPathNode));
1.626 +}
