1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
8 #include "txXPathTreeWalker.h"
12 * Implementation of an XPath nodeset
15 #ifdef NS_BUILD_REFCNT_LOGGING
16 # define LOG_CHUNK_MOVE(_start, _new_start, _count) \
18 txXPathNode* start = const_cast<txXPathNode*>(_start); \
19 while (start < _start + _count) { \
20 NS_LogDtor(start, "txXPathNode", sizeof(*start)); \
23 start = const_cast<txXPathNode*>(_new_start); \
24 while (start < _new_start + _count) { \
25 NS_LogCtor(start, "txXPathNode", sizeof(*start)); \
30 # define LOG_CHUNK_MOVE(_start, _new_start, _count)
33 static const int32_t kTxNodeSetMinSize
= 4;
34 static const int32_t kTxNodeSetGrowFactor
= 2;
39 txNodeSet::txNodeSet(txResultRecycler
* aRecycler
)
40 : txAExprResult(aRecycler
),
43 mStartBuffer(nullptr),
48 txNodeSet::txNodeSet(const txXPathNode
& aNode
, txResultRecycler
* aRecycler
)
49 : txAExprResult(aRecycler
),
52 mStartBuffer(nullptr),
56 if (!ensureGrowSize(1)) {
60 new (mStart
) txXPathNode(aNode
);
64 txNodeSet::txNodeSet(const txNodeSet
& aSource
, txResultRecycler
* aRecycler
)
65 : txAExprResult(aRecycler
),
68 mStartBuffer(nullptr),
75 txNodeSet::~txNodeSet() {
79 destroyElements(mStart
, mEnd
);
85 nsresult
txNodeSet::add(const txXPathNode
& aNode
) {
86 NS_ASSERTION(mDirection
== kForward
,
87 "only append(aNode) is supported on reversed nodesets");
94 txXPathNode
* pos
= findPosition(aNode
, mStart
, mEnd
, dupe
);
100 // save pos, ensureGrowSize messes with the pointers
101 int32_t moveSize
= mEnd
- pos
;
102 int32_t offset
= pos
- mStart
;
103 if (!ensureGrowSize(1)) {
104 return NS_ERROR_OUT_OF_MEMORY
;
106 // set pos to where it was
107 pos
= mStart
+ offset
;
110 LOG_CHUNK_MOVE(pos
, pos
+ 1, moveSize
);
111 memmove(pos
+ 1, pos
, moveSize
* sizeof(txXPathNode
));
114 new (pos
) txXPathNode(aNode
);
120 nsresult
txNodeSet::add(const txNodeSet
& aNodes
) {
121 return add(aNodes
, copyElements
, nullptr);
124 nsresult
txNodeSet::addAndTransfer(txNodeSet
* aNodes
) {
125 // failure is out-of-memory, transfer didn't happen
126 nsresult rv
= add(*aNodes
, transferElements
, destroyElements
);
127 NS_ENSURE_SUCCESS(rv
, rv
);
129 #ifdef TX_DONT_RECYCLE_BUFFER
130 if (aNodes
->mStartBuffer
) {
131 free(aNodes
->mStartBuffer
);
132 aNodes
->mStartBuffer
= aNodes
->mEndBuffer
= nullptr;
135 aNodes
->mStart
= aNodes
->mEnd
= aNodes
->mStartBuffer
;
141 * add(aNodeSet, aTransferOp)
143 * The code is optimized to make a minimum number of calls to
144 * Node::compareDocumentPosition. The idea is this:
145 * We have the two nodesets (number indicate "document position")
148 * 2 3 6 8 9 <- source 2
149 * _ _ _ _ _ _ _ _ <- result
152 * When merging these nodesets into the result, the nodes are transfered
153 * in chunks to the end of the buffer so that each chunk does not contain
154 * a node from the other nodeset, in document order.
156 * We select the last non-transfered node in the first nodeset and find
157 * where in the other nodeset it would be inserted. In this case we would
158 * take the 7 from the first nodeset and find the position between the
159 * 6 and 8 in the second. We then take the nodes after the insert-position
160 * and transfer them to the end of the resulting nodeset. Which in this case
161 * means that we first transfered the 8 and 9 nodes, giving us the following:
165 * _ _ _ _ _ _ 8 9 <- result
167 * The corresponding procedure is done for the second nodeset, that is
168 * the insertion position of the 6 in the first nodeset is found, which
169 * is between the 3 and the 7. The 7 is memmoved (as it stays within
170 * the same nodeset) to the result buffer.
172 * As the result buffer is filled from the end, it is safe to share the
173 * buffer between this nodeset and the result.
175 * This is repeated until both of the nodesets are empty.
177 * If we find a duplicate node when searching for where insertposition we
178 * check for sequences of duplicate nodes, which can be optimized.
181 nsresult
txNodeSet::add(const txNodeSet
& aNodes
, transferOp aTransfer
,
182 destroyOp aDestroy
) {
183 NS_ASSERTION(mDirection
== kForward
,
184 "only append(aNode) is supported on reversed nodesets");
186 if (aNodes
.isEmpty()) {
190 if (!ensureGrowSize(aNodes
.size())) {
191 return NS_ERROR_OUT_OF_MEMORY
;
194 // This is probably a rather common case, so lets try to shortcut.
195 if (mStart
== mEnd
||
196 txXPathNodeUtils::comparePosition(mEnd
[-1], *aNodes
.mStart
) < 0) {
197 aTransfer(mEnd
, aNodes
.mStart
, aNodes
.mEnd
);
198 mEnd
+= aNodes
.size();
203 // Last element in this nodeset
204 txXPathNode
* thisPos
= mEnd
;
206 // Last element of the other nodeset
207 txXPathNode
* otherPos
= aNodes
.mEnd
;
209 // Pointer to the insertion point in this nodeset
210 txXPathNode
* insertPos
= mEndBuffer
;
215 while (thisPos
> mStart
|| otherPos
> aNodes
.mStart
) {
216 // Find where the last remaining node of this nodeset would
217 // be inserted in the other nodeset.
218 if (thisPos
> mStart
) {
219 pos
= findPosition(thisPos
[-1], aNodes
.mStart
, otherPos
, dupe
);
222 const txXPathNode
* deletePos
= thisPos
;
223 --thisPos
; // this is already added
224 // check dupe sequence
225 while (thisPos
> mStart
&& pos
> aNodes
.mStart
&&
226 thisPos
[-1] == pos
[-1]) {
232 aDestroy(thisPos
, deletePos
);
239 // Transfer the otherNodes after the insertion point to the result
240 count
= otherPos
- pos
;
243 aTransfer(insertPos
, pos
, otherPos
);
247 // Find where the last remaining node of the otherNodeset would
248 // be inserted in this nodeset.
249 if (otherPos
> aNodes
.mStart
) {
250 pos
= findPosition(otherPos
[-1], mStart
, thisPos
, dupe
);
253 const txXPathNode
* deletePos
= otherPos
;
254 --otherPos
; // this is already added
255 // check dupe sequence
256 while (otherPos
> aNodes
.mStart
&& pos
> mStart
&&
257 otherPos
[-1] == pos
[-1]) {
263 aDestroy(otherPos
, deletePos
);
270 // Move the nodes from this nodeset after the insertion point
272 count
= thisPos
- pos
;
275 LOG_CHUNK_MOVE(pos
, insertPos
, count
);
276 memmove(insertPos
, pos
, count
* sizeof(txXPathNode
));
288 * These functions should be used with care.
289 * They are intended to be used when the caller assures that the resulting
290 * nodeset remains in document order.
291 * Abuse will break document order, and cause errors in the result.
292 * These functions are significantly faster than the add API, as no
293 * order info operations will be performed.
296 nsresult
txNodeSet::append(const txXPathNode
& aNode
) {
297 if (!ensureGrowSize(1)) {
298 return NS_ERROR_OUT_OF_MEMORY
;
301 if (mDirection
== kForward
) {
302 new (mEnd
) txXPathNode(aNode
);
308 new (--mStart
) txXPathNode(aNode
);
313 nsresult
txNodeSet::append(const txNodeSet
& aNodes
) {
314 NS_ASSERTION(mDirection
== kForward
,
315 "only append(aNode) is supported on reversed nodesets");
317 if (aNodes
.isEmpty()) {
321 int32_t appended
= aNodes
.size();
322 if (!ensureGrowSize(appended
)) {
323 return NS_ERROR_OUT_OF_MEMORY
;
326 copyElements(mEnd
, aNodes
.mStart
, aNodes
.mEnd
);
332 nsresult
txNodeSet::mark(int32_t aIndex
) {
333 NS_ASSERTION(aIndex
>= 0 && mStart
&& mEnd
- mStart
> aIndex
,
334 "index out of bounds");
336 int32_t length
= size();
337 mMarks
= new bool[length
];
338 memset(mMarks
, 0, length
* sizeof(bool));
340 if (mDirection
== kForward
) {
341 mMarks
[aIndex
] = true;
343 mMarks
[size() - aIndex
- 1] = true;
349 nsresult
txNodeSet::sweep() {
355 int32_t chunk
, pos
= 0;
356 int32_t length
= size();
357 txXPathNode
* insertion
= mStartBuffer
;
359 while (pos
< length
) {
360 while (pos
< length
&& !mMarks
[pos
]) {
362 mStart
[pos
].~txXPathNode();
365 // find chunk to move
367 while (pos
< length
&& mMarks
[pos
]) {
373 LOG_CHUNK_MOVE(mStart
+ pos
- chunk
, insertion
, chunk
);
374 memmove(insertion
, mStart
+ pos
- chunk
, chunk
* sizeof(txXPathNode
));
378 mStart
= mStartBuffer
;
386 void txNodeSet::clear() {
387 destroyElements(mStart
, mEnd
);
388 #ifdef TX_DONT_RECYCLE_BUFFER
391 mStartBuffer
= mEndBuffer
= nullptr;
394 mStart
= mEnd
= mStartBuffer
;
397 mDirection
= kForward
;
400 int32_t txNodeSet::indexOf(const txXPathNode
& aNode
, uint32_t aStart
) const {
401 NS_ASSERTION(mDirection
== kForward
,
402 "only append(aNode) is supported on reversed nodesets");
404 if (!mStart
|| mStart
== mEnd
) {
408 txXPathNode
* pos
= mStart
+ aStart
;
409 for (; pos
< mEnd
; ++pos
) {
418 const txXPathNode
& txNodeSet::get(int32_t aIndex
) const {
419 if (mDirection
== kForward
) {
420 return mStart
[aIndex
];
423 return mEnd
[-aIndex
- 1];
426 short txNodeSet::getResultType() { return txAExprResult::NODESET
; }
428 bool txNodeSet::booleanValue() { return !isEmpty(); }
429 double txNodeSet::numberValue() {
433 return txDouble::toDouble(str
);
436 void txNodeSet::stringValue(nsString
& aStr
) {
437 NS_ASSERTION(mDirection
== kForward
,
438 "only append(aNode) is supported on reversed nodesets");
442 txXPathNodeUtils::appendNodeValue(get(0), aStr
);
445 const nsString
* txNodeSet::stringValuePointer() { return nullptr; }
447 bool txNodeSet::ensureGrowSize(int32_t aSize
) {
448 // check if there is enough place in the buffer as is
449 if (mDirection
== kForward
&& aSize
<= mEndBuffer
- mEnd
) {
453 if (mDirection
== kReversed
&& aSize
<= mStart
- mStartBuffer
) {
457 // check if we just have to align mStart to have enough space
458 int32_t oldSize
= mEnd
- mStart
;
459 int32_t oldLength
= mEndBuffer
- mStartBuffer
;
460 int32_t ensureSize
= oldSize
+ aSize
;
461 if (ensureSize
<= oldLength
) {
462 // just move the buffer
463 txXPathNode
* dest
= mStartBuffer
;
464 if (mDirection
== kReversed
) {
465 dest
= mEndBuffer
- oldSize
;
467 LOG_CHUNK_MOVE(mStart
, dest
, oldSize
);
468 memmove(dest
, mStart
, oldSize
* sizeof(txXPathNode
));
470 mEnd
= dest
+ oldSize
;
475 // This isn't 100% safe. But until someone manages to make a 1gig nodeset
477 int32_t newLength
= std::max(oldLength
, kTxNodeSetMinSize
);
479 while (newLength
< ensureSize
) {
480 newLength
*= kTxNodeSetGrowFactor
;
483 txXPathNode
* newArr
=
484 static_cast<txXPathNode
*>(moz_xmalloc(newLength
* sizeof(txXPathNode
)));
486 txXPathNode
* dest
= newArr
;
487 if (mDirection
== kReversed
) {
488 dest
+= newLength
- oldSize
;
492 LOG_CHUNK_MOVE(mStart
, dest
, oldSize
);
493 memcpy(dest
, mStart
, oldSize
* sizeof(txXPathNode
));
498 memset(mStartBuffer
, 0, (mEndBuffer
- mStartBuffer
) * sizeof(txXPathNode
));
503 mStartBuffer
= newArr
;
504 mEndBuffer
= mStartBuffer
+ newLength
;
506 mEnd
= dest
+ oldSize
;
511 txXPathNode
* txNodeSet::findPosition(const txXPathNode
& aNode
,
512 txXPathNode
* aFirst
, txXPathNode
* aLast
,
515 if (aLast
- aFirst
<= 2) {
516 // If we search 2 nodes or less there is no point in further divides
517 txXPathNode
* pos
= aFirst
;
518 for (; pos
< aLast
; ++pos
) {
519 int cmp
= txXPathNodeUtils::comparePosition(aNode
, *pos
);
533 // (cannot add two pointers)
534 txXPathNode
* midpos
= aFirst
+ (aLast
- aFirst
) / 2;
535 int cmp
= txXPathNodeUtils::comparePosition(aNode
, *midpos
);
543 return findPosition(aNode
, midpos
+ 1, aLast
, aDupe
);
546 // midpos excluded as end of range
548 return findPosition(aNode
, aFirst
, midpos
, aDupe
);
552 void txNodeSet::copyElements(txXPathNode
* aDest
, const txXPathNode
* aStart
,
553 const txXPathNode
* aEnd
) {
554 const txXPathNode
* pos
= aStart
;
556 new (aDest
) txXPathNode(*pos
);
563 void txNodeSet::transferElements(txXPathNode
* aDest
, const txXPathNode
* aStart
,
564 const txXPathNode
* aEnd
) {
565 LOG_CHUNK_MOVE(aStart
, aDest
, (aEnd
- aStart
));
566 memcpy(aDest
, aStart
, (aEnd
- aStart
) * sizeof(txXPathNode
));