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