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/. */
5
6 #include "txNodeSet.h"
7 #include "txLog.h"
8 #include "nsMemory.h"
9 #include "txXPathTreeWalker.h"
10 #include <algorithm>
11
12 /**
13 * Implementation of an XPath nodeset
14 */
15
16 #ifdef NS_BUILD_REFCNT_LOGGING
17 # define LOG_CHUNK_MOVE(_start, _new_start, _count) \
18 { \
19 txXPathNode* start = const_cast<txXPathNode*>(_start); \
20 while (start < _start + _count) { \
21 NS_LogDtor(start, "txXPathNode", sizeof(*start)); \
22 ++start; \
23 } \
24 start = const_cast<txXPathNode*>(_new_start); \
25 while (start < _new_start + _count) { \
26 NS_LogCtor(start, "txXPathNode", sizeof(*start)); \
27 ++start; \
28 } \
29 }
30 #else
31 # define LOG_CHUNK_MOVE(_start, _new_start, _count)
32 #endif
33
34 static const int32_t kTxNodeSetMinSize = 4;
35 static const int32_t kTxNodeSetGrowFactor = 2;
36
37 #define kForward 1
38 #define kReversed -1
39
txNodeSet(txResultRecycler * aRecycler)40 txNodeSet::txNodeSet(txResultRecycler* aRecycler)
41 : txAExprResult(aRecycler),
42 mStart(nullptr),
43 mEnd(nullptr),
44 mStartBuffer(nullptr),
45 mEndBuffer(nullptr),
46 mDirection(kForward),
47 mMarks(nullptr) {}
48
txNodeSet(const txXPathNode & aNode,txResultRecycler * aRecycler)49 txNodeSet::txNodeSet(const txXPathNode& aNode, txResultRecycler* aRecycler)
50 : txAExprResult(aRecycler),
51 mStart(nullptr),
52 mEnd(nullptr),
53 mStartBuffer(nullptr),
54 mEndBuffer(nullptr),
55 mDirection(kForward),
56 mMarks(nullptr) {
57 if (!ensureGrowSize(1)) {
58 return;
59 }
60
61 new (mStart) txXPathNode(aNode);
62 ++mEnd;
63 }
64
txNodeSet(const txNodeSet & aSource,txResultRecycler * aRecycler)65 txNodeSet::txNodeSet(const txNodeSet& aSource, txResultRecycler* aRecycler)
66 : txAExprResult(aRecycler),
67 mStart(nullptr),
68 mEnd(nullptr),
69 mStartBuffer(nullptr),
70 mEndBuffer(nullptr),
71 mDirection(kForward),
72 mMarks(nullptr) {
73 append(aSource);
74 }
75
~txNodeSet()76 txNodeSet::~txNodeSet() {
77 delete[] mMarks;
78
79 if (mStartBuffer) {
80 destroyElements(mStart, mEnd);
81
82 free(mStartBuffer);
83 }
84 }
85
add(const txXPathNode & aNode)86 nsresult txNodeSet::add(const txXPathNode& aNode) {
87 NS_ASSERTION(mDirection == kForward,
88 "only append(aNode) is supported on reversed nodesets");
89
90 if (isEmpty()) {
91 return append(aNode);
92 }
93
94 bool dupe;
95 txXPathNode* pos = findPosition(aNode, mStart, mEnd, dupe);
96
97 if (dupe) {
98 return NS_OK;
99 }
100
101 // save pos, ensureGrowSize messes with the pointers
102 int32_t moveSize = mEnd - pos;
103 int32_t offset = pos - mStart;
104 if (!ensureGrowSize(1)) {
105 return NS_ERROR_OUT_OF_MEMORY;
106 }
107 // set pos to where it was
108 pos = mStart + offset;
109
110 if (moveSize > 0) {
111 LOG_CHUNK_MOVE(pos, pos + 1, moveSize);
112 memmove(pos + 1, pos, moveSize * sizeof(txXPathNode));
113 }
114
115 new (pos) txXPathNode(aNode);
116 ++mEnd;
117
118 return NS_OK;
119 }
120
add(const txNodeSet & aNodes)121 nsresult txNodeSet::add(const txNodeSet& aNodes) {
122 return add(aNodes, copyElements, nullptr);
123 }
124
addAndTransfer(txNodeSet * aNodes)125 nsresult txNodeSet::addAndTransfer(txNodeSet* aNodes) {
126 // failure is out-of-memory, transfer didn't happen
127 nsresult rv = add(*aNodes, transferElements, destroyElements);
128 NS_ENSURE_SUCCESS(rv, rv);
129
130 #ifdef TX_DONT_RECYCLE_BUFFER
131 if (aNodes->mStartBuffer) {
132 free(aNodes->mStartBuffer);
133 aNodes->mStartBuffer = aNodes->mEndBuffer = nullptr;
134 }
135 #endif
136 aNodes->mStart = aNodes->mEnd = aNodes->mStartBuffer;
137
138 return NS_OK;
139 }
140
141 /**
142 * add(aNodeSet, aTransferOp)
143 *
144 * The code is optimized to make a minimum number of calls to
145 * Node::compareDocumentPosition. The idea is this:
146 * We have the two nodesets (number indicate "document position")
147 *
148 * 1 3 7 <- source 1
149 * 2 3 6 8 9 <- source 2
150 * _ _ _ _ _ _ _ _ <- result
151 *
152 *
153 * When merging these nodesets into the result, the nodes are transfered
154 * in chunks to the end of the buffer so that each chunk does not contain
155 * a node from the other nodeset, in document order.
156 *
157 * We select the last non-transfered node in the first nodeset and find
158 * where in the other nodeset it would be inserted. In this case we would
159 * take the 7 from the first nodeset and find the position between the
160 * 6 and 8 in the second. We then take the nodes after the insert-position
161 * and transfer them to the end of the resulting nodeset. Which in this case
162 * means that we first transfered the 8 and 9 nodes, giving us the following:
163 *
164 * 1 3 7 <- source 1
165 * 2 3 6 <- source 2
166 * _ _ _ _ _ _ 8 9 <- result
167 *
168 * The corresponding procedure is done for the second nodeset, that is
169 * the insertion position of the 6 in the first nodeset is found, which
170 * is between the 3 and the 7. The 7 is memmoved (as it stays within
171 * the same nodeset) to the result buffer.
172 *
173 * As the result buffer is filled from the end, it is safe to share the
174 * buffer between this nodeset and the result.
175 *
176 * This is repeated until both of the nodesets are empty.
177 *
178 * If we find a duplicate node when searching for where insertposition we
179 * check for sequences of duplicate nodes, which can be optimized.
180 *
181 */
add(const txNodeSet & aNodes,transferOp aTransfer,destroyOp aDestroy)182 nsresult txNodeSet::add(const txNodeSet& aNodes, transferOp aTransfer,
183 destroyOp aDestroy) {
184 NS_ASSERTION(mDirection == kForward,
185 "only append(aNode) is supported on reversed nodesets");
186
187 if (aNodes.isEmpty()) {
188 return NS_OK;
189 }
190
191 if (!ensureGrowSize(aNodes.size())) {
192 return NS_ERROR_OUT_OF_MEMORY;
193 }
194
195 // This is probably a rather common case, so lets try to shortcut.
196 if (mStart == mEnd ||
197 txXPathNodeUtils::comparePosition(mEnd[-1], *aNodes.mStart) < 0) {
198 aTransfer(mEnd, aNodes.mStart, aNodes.mEnd);
199 mEnd += aNodes.size();
200
201 return NS_OK;
202 }
203
204 // Last element in this nodeset
205 txXPathNode* thisPos = mEnd;
206
207 // Last element of the other nodeset
208 txXPathNode* otherPos = aNodes.mEnd;
209
210 // Pointer to the insertion point in this nodeset
211 txXPathNode* insertPos = mEndBuffer;
212
213 bool dupe;
214 txXPathNode* pos;
215 int32_t count;
216 while (thisPos > mStart || otherPos > aNodes.mStart) {
217 // Find where the last remaining node of this nodeset would
218 // be inserted in the other nodeset.
219 if (thisPos > mStart) {
220 pos = findPosition(thisPos[-1], aNodes.mStart, otherPos, dupe);
221
222 if (dupe) {
223 const txXPathNode* deletePos = thisPos;
224 --thisPos; // this is already added
225 // check dupe sequence
226 while (thisPos > mStart && pos > aNodes.mStart &&
227 thisPos[-1] == pos[-1]) {
228 --thisPos;
229 --pos;
230 }
231
232 if (aDestroy) {
233 aDestroy(thisPos, deletePos);
234 }
235 }
236 } else {
237 pos = aNodes.mStart;
238 }
239
240 // Transfer the otherNodes after the insertion point to the result
241 count = otherPos - pos;
242 if (count > 0) {
243 insertPos -= count;
244 aTransfer(insertPos, pos, otherPos);
245 otherPos -= count;
246 }
247
248 // Find where the last remaining node of the otherNodeset would
249 // be inserted in this nodeset.
250 if (otherPos > aNodes.mStart) {
251 pos = findPosition(otherPos[-1], mStart, thisPos, dupe);
252
253 if (dupe) {
254 const txXPathNode* deletePos = otherPos;
255 --otherPos; // this is already added
256 // check dupe sequence
257 while (otherPos > aNodes.mStart && pos > mStart &&
258 otherPos[-1] == pos[-1]) {
259 --otherPos;
260 --pos;
261 }
262
263 if (aDestroy) {
264 aDestroy(otherPos, deletePos);
265 }
266 }
267 } else {
268 pos = mStart;
269 }
270
271 // Move the nodes from this nodeset after the insertion point
272 // to the result
273 count = thisPos - pos;
274 if (count > 0) {
275 insertPos -= count;
276 LOG_CHUNK_MOVE(pos, insertPos, count);
277 memmove(insertPos, pos, count * sizeof(txXPathNode));
278 thisPos -= count;
279 }
280 }
281 mStart = insertPos;
282 mEnd = mEndBuffer;
283
284 return NS_OK;
285 }
286
287 /**
288 * Append API
289 * These functions should be used with care.
290 * They are intended to be used when the caller assures that the resulting
291 * nodeset remains in document order.
292 * Abuse will break document order, and cause errors in the result.
293 * These functions are significantly faster than the add API, as no
294 * order info operations will be performed.
295 */
296
append(const txXPathNode & aNode)297 nsresult txNodeSet::append(const txXPathNode& aNode) {
298 if (!ensureGrowSize(1)) {
299 return NS_ERROR_OUT_OF_MEMORY;
300 }
301
302 if (mDirection == kForward) {
303 new (mEnd) txXPathNode(aNode);
304 ++mEnd;
305
306 return NS_OK;
307 }
308
309 new (--mStart) txXPathNode(aNode);
310
311 return NS_OK;
312 }
313
append(const txNodeSet & aNodes)314 nsresult txNodeSet::append(const txNodeSet& aNodes) {
315 NS_ASSERTION(mDirection == kForward,
316 "only append(aNode) is supported on reversed nodesets");
317
318 if (aNodes.isEmpty()) {
319 return NS_OK;
320 }
321
322 int32_t appended = aNodes.size();
323 if (!ensureGrowSize(appended)) {
324 return NS_ERROR_OUT_OF_MEMORY;
325 }
326
327 copyElements(mEnd, aNodes.mStart, aNodes.mEnd);
328 mEnd += appended;
329
330 return NS_OK;
331 }
332
mark(int32_t aIndex)333 nsresult txNodeSet::mark(int32_t aIndex) {
334 NS_ASSERTION(aIndex >= 0 && mStart && mEnd - mStart > aIndex,
335 "index out of bounds");
336 if (!mMarks) {
337 int32_t length = size();
338 mMarks = new bool[length];
339 memset(mMarks, 0, length * sizeof(bool));
340 }
341 if (mDirection == kForward) {
342 mMarks[aIndex] = true;
343 } else {
344 mMarks[size() - aIndex - 1] = true;
345 }
346
347 return NS_OK;
348 }
349
sweep()350 nsresult txNodeSet::sweep() {
351 if (!mMarks) {
352 // sweep everything
353 clear();
354 }
355
356 int32_t chunk, pos = 0;
357 int32_t length = size();
358 txXPathNode* insertion = mStartBuffer;
359
360 while (pos < length) {
361 while (pos < length && !mMarks[pos]) {
362 // delete unmarked
363 mStart[pos].~txXPathNode();
364 ++pos;
365 }
366 // find chunk to move
367 chunk = 0;
368 while (pos < length && mMarks[pos]) {
369 ++pos;
370 ++chunk;
371 }
372 // move chunk
373 if (chunk > 0) {
374 LOG_CHUNK_MOVE(mStart + pos - chunk, insertion, chunk);
375 memmove(insertion, mStart + pos - chunk, chunk * sizeof(txXPathNode));
376 insertion += chunk;
377 }
378 }
379 mStart = mStartBuffer;
380 mEnd = insertion;
381 delete[] mMarks;
382 mMarks = nullptr;
383
384 return NS_OK;
385 }
386
clear()387 void txNodeSet::clear() {
388 destroyElements(mStart, mEnd);
389 #ifdef TX_DONT_RECYCLE_BUFFER
390 if (mStartBuffer) {
391 free(mStartBuffer);
392 mStartBuffer = mEndBuffer = nullptr;
393 }
394 #endif
395 mStart = mEnd = mStartBuffer;
396 delete[] mMarks;
397 mMarks = nullptr;
398 mDirection = kForward;
399 }
400
indexOf(const txXPathNode & aNode,uint32_t aStart) const401 int32_t txNodeSet::indexOf(const txXPathNode& aNode, uint32_t aStart) const {
402 NS_ASSERTION(mDirection == kForward,
403 "only append(aNode) is supported on reversed nodesets");
404
405 if (!mStart || mStart == mEnd) {
406 return -1;
407 }
408
409 txXPathNode* pos = mStart + aStart;
410 for (; pos < mEnd; ++pos) {
411 if (*pos == aNode) {
412 return pos - mStart;
413 }
414 }
415
416 return -1;
417 }
418
get(int32_t aIndex) const419 const txXPathNode& txNodeSet::get(int32_t aIndex) const {
420 if (mDirection == kForward) {
421 return mStart[aIndex];
422 }
423
424 return mEnd[-aIndex - 1];
425 }
426
getResultType()427 short txNodeSet::getResultType() { return txAExprResult::NODESET; }
428
booleanValue()429 bool txNodeSet::booleanValue() { return !isEmpty(); }
numberValue()430 double txNodeSet::numberValue() {
431 nsAutoString str;
432 stringValue(str);
433
434 return txDouble::toDouble(str);
435 }
436
stringValue(nsString & aStr)437 void txNodeSet::stringValue(nsString& aStr) {
438 NS_ASSERTION(mDirection == kForward,
439 "only append(aNode) is supported on reversed nodesets");
440 if (isEmpty()) {
441 return;
442 }
443 txXPathNodeUtils::appendNodeValue(get(0), aStr);
444 }
445
stringValuePointer()446 const nsString* txNodeSet::stringValuePointer() { return nullptr; }
447
ensureGrowSize(int32_t aSize)448 bool txNodeSet::ensureGrowSize(int32_t aSize) {
449 // check if there is enough place in the buffer as is
450 if (mDirection == kForward && aSize <= mEndBuffer - mEnd) {
451 return true;
452 }
453
454 if (mDirection == kReversed && aSize <= mStart - mStartBuffer) {
455 return true;
456 }
457
458 // check if we just have to align mStart to have enough space
459 int32_t oldSize = mEnd - mStart;
460 int32_t oldLength = mEndBuffer - mStartBuffer;
461 int32_t ensureSize = oldSize + aSize;
462 if (ensureSize <= oldLength) {
463 // just move the buffer
464 txXPathNode* dest = mStartBuffer;
465 if (mDirection == kReversed) {
466 dest = mEndBuffer - oldSize;
467 }
468 LOG_CHUNK_MOVE(mStart, dest, oldSize);
469 memmove(dest, mStart, oldSize * sizeof(txXPathNode));
470 mStart = dest;
471 mEnd = dest + oldSize;
472
473 return true;
474 }
475
476 // This isn't 100% safe. But until someone manages to make a 1gig nodeset
477 // it should be ok.
478 int32_t newLength = std::max(oldLength, kTxNodeSetMinSize);
479
480 while (newLength < ensureSize) {
481 newLength *= kTxNodeSetGrowFactor;
482 }
483
484 txXPathNode* newArr =
485 static_cast<txXPathNode*>(moz_xmalloc(newLength * sizeof(txXPathNode)));
486
487 txXPathNode* dest = newArr;
488 if (mDirection == kReversed) {
489 dest += newLength - oldSize;
490 }
491
492 if (oldSize > 0) {
493 LOG_CHUNK_MOVE(mStart, dest, oldSize);
494 memcpy(dest, mStart, oldSize * sizeof(txXPathNode));
495 }
496
497 if (mStartBuffer) {
498 #ifdef DEBUG
499 memset(mStartBuffer, 0, (mEndBuffer - mStartBuffer) * sizeof(txXPathNode));
500 #endif
501 free(mStartBuffer);
502 }
503
504 mStartBuffer = newArr;
505 mEndBuffer = mStartBuffer + newLength;
506 mStart = dest;
507 mEnd = dest + oldSize;
508
509 return true;
510 }
511
findPosition(const txXPathNode & aNode,txXPathNode * aFirst,txXPathNode * aLast,bool & aDupe) const512 txXPathNode* txNodeSet::findPosition(const txXPathNode& aNode,
513 txXPathNode* aFirst, txXPathNode* aLast,
514 bool& aDupe) const {
515 aDupe = false;
516 if (aLast - aFirst <= 2) {
517 // If we search 2 nodes or less there is no point in further divides
518 txXPathNode* pos = aFirst;
519 for (; pos < aLast; ++pos) {
520 int cmp = txXPathNodeUtils::comparePosition(aNode, *pos);
521 if (cmp < 0) {
522 return pos;
523 }
524
525 if (cmp == 0) {
526 aDupe = true;
527
528 return pos;
529 }
530 }
531 return pos;
532 }
533
534 // (cannot add two pointers)
535 txXPathNode* midpos = aFirst + (aLast - aFirst) / 2;
536 int cmp = txXPathNodeUtils::comparePosition(aNode, *midpos);
537 if (cmp == 0) {
538 aDupe = true;
539
540 return midpos;
541 }
542
543 if (cmp > 0) {
544 return findPosition(aNode, midpos + 1, aLast, aDupe);
545 }
546
547 // midpos excluded as end of range
548
549 return findPosition(aNode, aFirst, midpos, aDupe);
550 }
551
552 /* static */
copyElements(txXPathNode * aDest,const txXPathNode * aStart,const txXPathNode * aEnd)553 void txNodeSet::copyElements(txXPathNode* aDest, const txXPathNode* aStart,
554 const txXPathNode* aEnd) {
555 const txXPathNode* pos = aStart;
556 while (pos < aEnd) {
557 new (aDest) txXPathNode(*pos);
558 ++aDest;
559 ++pos;
560 }
561 }
562
563 /* static */
transferElements(txXPathNode * aDest,const txXPathNode * aStart,const txXPathNode * aEnd)564 void txNodeSet::transferElements(txXPathNode* aDest, const txXPathNode* aStart,
565 const txXPathNode* aEnd) {
566 LOG_CHUNK_MOVE(aStart, aDest, (aEnd - aStart));
567 memcpy(aDest, aStart, (aEnd - aStart) * sizeof(txXPathNode));
568 }
569