1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
7 ** This file is part of the QtDeclarative module of the Qt Toolkit.
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** GNU Lesser General Public License Usage
11 ** This file may be used under the terms of the GNU Lesser General Public
12 ** License version 2.1 as published by the Free Software Foundation and
13 ** appearing in the file LICENSE.LGPL included in the packaging of this
14 ** file. Please review the following information to ensure the GNU Lesser
15 ** General Public License version 2.1 requirements will be met:
16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
18 ** In addition, as a special exception, Nokia gives you certain additional
19 ** rights. These rights are described in the Nokia Qt LGPL Exception
20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
22 ** GNU General Public License Usage
23 ** Alternatively, this file may be used under the terms of the GNU General
24 ** Public License version 3.0 as published by the Free Software Foundation
25 ** and appearing in the file LICENSE.GPL included in the packaging of this
26 ** file. Please review the following information to ensure the GNU General
27 ** Public License version 3.0 requirements will be met:
28 ** http://www.gnu.org/copyleft/gpl.html.
31 ** Alternatively, this file may be used in accordance with the terms and
32 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
42 #include "qdeclarativelistcompositor_p.h"
44 #include <QtCore/qvarlengtharray.h>
46 //#define QT_DECLARATIVE_VERIFY_MINIMAL
47 //#define QT_DECLARATIVE_VERIFY_INTEGRITY
51 #ifdef QT_DECLARATIVE_VERIFY_MINIMAL
52 #define QT_DECLARATIVE_VERIFY_INTEGRITY
53 static bool qt_verifyMinimal(
54 const QDeclarativeListCompositor::iterator &begin,
55 const QDeclarativeListCompositor::iterator &end)
60 for (const QDeclarativeListCompositor::Range *range = begin->next; range != *end; range = range->next, ++index) {
61 if (range->previous->list == range->list
62 && range->previous->flags == (range->flags & ~QDeclarativeListCompositor::AppendFlag)
63 && range->previous->end() == range->index) {
64 qWarning() << index << "Consecutive ranges";
65 qWarning() << *range->previous;
76 #ifdef QT_DECLARATIVE_VERIFY_INTEGRITY
77 static bool qt_printInfo(const QDeclarativeListCompositor &compositor)
79 qWarning() << compositor;
83 static bool qt_verifyIntegrity(
84 const QDeclarativeListCompositor::iterator &begin,
85 const QDeclarativeListCompositor::iterator &end,
86 const QDeclarativeListCompositor::iterator &cachedIt)
91 QDeclarativeListCompositor::iterator it;
92 for (it = begin; *it != *end; *it = it->next) {
93 if (it->count == 0 && !it->append()) {
94 qWarning() << index << "Empty non-append range";
98 qWarning() << index << "Negative count";
101 if (it->list && it->flags != QDeclarativeListCompositor::CacheFlag && it->index < 0) {
102 qWarning() << index <<"Negative index";
105 if (it->previous->next != it.range) {
106 qWarning() << index << "broken list: it->previous->next != it.range";
109 if (it->next->previous != it.range) {
110 qWarning() << index << "broken list: it->next->previous != it.range";
113 if (*it == *cachedIt) {
114 for (int i = 0; i < end.groupCount; ++i) {
115 int groupIndex = it.index[i];
116 if (cachedIt->flags & (1 << i))
117 groupIndex += cachedIt.offset;
118 if (groupIndex != cachedIt.index[i]) {
120 << "invalid cached index"
121 << QDeclarativeListCompositor::Group(i)
131 it.incrementIndexes(it->count);
135 for (int i = 0; i < end.groupCount; ++i) {
136 if (end.index[i] != it.index[i]) {
137 qWarning() << "Group" << i << "count invalid. Expected:" << end.index[i] << "Actual:" << it.index[i];
145 #if defined(QT_DECLARATIVE_VERIFY_MINIMAL)
146 # define QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!(qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \
147 && qt_verifyMinimal(iterator(m_ranges.next, 0, Default, m_groupCount), m_end)) \
148 && qt_printInfo(*this)));
149 #elif defined(QT_DECLARATIVE_VERIFY_INTEGRITY)
150 # define QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \
151 && qt_printInfo(*this)));
153 # define QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
156 //#define QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(args) qDebug() << m_end.index[1] << m_end.index[0] << Q_FUNC_INFO args;
157 #define QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(args)
159 QDeclarativeListCompositor::iterator &QDeclarativeListCompositor::iterator::operator +=(int difference)
161 Q_ASSERT(difference >= 0);
162 while (!(range->flags & groupFlag)) {
163 incrementIndexes(range->count - offset);
167 decrementIndexes(offset);
168 offset += difference;
169 while (offset >= range->count || !(range->flags & groupFlag)) {
170 if (range->flags & groupFlag)
171 offset -= range->count;
172 incrementIndexes(range->count);
175 incrementIndexes(offset);
179 QDeclarativeListCompositor::iterator &QDeclarativeListCompositor::iterator::operator -=(int difference)
181 Q_ASSERT(difference >= 0);
182 while (!(range->flags & groupFlag)) {
183 decrementIndexes(offset);
184 range = range->previous;
185 offset = range->count;
187 decrementIndexes(offset);
188 offset -= difference;
190 range = range->previous;
191 if (range->flags & groupFlag)
192 offset += range->count;
193 decrementIndexes(range->count);
195 incrementIndexes(offset);
199 QDeclarativeListCompositor::insert_iterator &QDeclarativeListCompositor::insert_iterator::operator +=(int difference)
201 Q_ASSERT(difference >= 0);
202 while (!(range->flags & groupFlag)) {
203 incrementIndexes(range->count - offset);
207 decrementIndexes(offset);
208 offset += difference;
209 while (offset > range->count
210 || (offset == range->count && !range->append() && offset > 0)
211 || (!(range->flags & groupFlag) && offset > 0)) {
212 Q_ASSERT(range->flags);
213 if (range->flags & groupFlag)
214 offset -= range->count;
215 incrementIndexes(range->count);
218 incrementIndexes(offset);
222 QDeclarativeListCompositor::insert_iterator &QDeclarativeListCompositor::insert_iterator::operator -=(int difference)
224 Q_ASSERT(difference >= 0);
225 while (!(range->flags & groupFlag) && range->previous->flags) {
226 decrementIndexes(offset);
227 range = range->previous;
228 offset = (range->flags & (GroupMask | CacheFlag)) ? range->count : 0;
230 decrementIndexes(offset);
231 offset -= difference;
233 range = range->previous;
234 if (range->flags & groupFlag)
235 offset += range->count;
236 decrementIndexes(range->count);
238 incrementIndexes(offset);
239 for (Range *previous = range->previous; offset == 0 && previous->prepend(); previous = previous->previous) {
240 if (previous->append() && previous->inGroup()) {
241 offset = previous->count;
243 } else if (!previous->inGroup()) {
251 QDeclarativeListCompositor::QDeclarativeListCompositor()
252 : m_end(m_ranges.next, 0, Default, 2)
255 , m_defaultFlags(PrependFlag | DefaultFlag)
256 , m_removeFlags(AppendFlag | PrependFlag | GroupMask)
260 QDeclarativeListCompositor::~QDeclarativeListCompositor()
262 for (Range *next, *range = m_ranges.next; range != &m_ranges; range = next) {
268 inline QDeclarativeListCompositor::Range *QDeclarativeListCompositor::insert(
269 Range *before, void *list, int index, int count, uint flags)
271 return new Range(before, list, index, count, flags);
274 inline QDeclarativeListCompositor::Range *QDeclarativeListCompositor::erase(
277 Range *next = range->next;
278 next->previous = range->previous;
279 next->previous->next = range->next;
284 void QDeclarativeListCompositor::setGroupCount(int count)
286 m_groupCount = count;
287 m_end = iterator(&m_ranges, 0, Default, m_groupCount);
291 int QDeclarativeListCompositor::count(Group group) const
293 return m_end.index[group];
296 QDeclarativeListCompositor::iterator QDeclarativeListCompositor::find(Group group, int index)
298 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index)
299 Q_ASSERT(index >=0 && index < count(group));
300 if (m_cacheIt == m_end) {
301 m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
304 const int offset = index - m_cacheIt.index[group];
305 m_cacheIt.setGroup(group);
308 } else if (offset < 0) {
309 m_cacheIt -= -offset;
310 } else if (offset == 0) {
315 Q_ASSERT(m_cacheIt.index[group] == index);
316 Q_ASSERT(m_cacheIt->inGroup(group));
317 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
321 QDeclarativeListCompositor::iterator QDeclarativeListCompositor::find(Group group, int index) const
323 return const_cast<QDeclarativeListCompositor *>(this)->find(group, index);
326 QDeclarativeListCompositor::insert_iterator QDeclarativeListCompositor::findInsertPosition(Group group, int index)
328 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index)
329 Q_ASSERT(index >=0 && index <= count(group));
331 if (m_cacheIt == m_end) {
332 it = iterator(m_ranges.next, 0, group, m_groupCount);
335 const int offset = index - m_cacheIt.index[group];
340 } else if (offset < 0) {
342 } else if (offset == 0) {
347 Q_ASSERT(it.index[group] == index);
351 QDeclarativeListCompositor::iterator QDeclarativeListCompositor::begin(Group group)
353 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group)
354 m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
359 void QDeclarativeListCompositor::append(
360 void *list, int index, int count, uint flags, QVector<Insert> *inserts)
362 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count << flags)
363 insert(m_end, list, index, count, flags, inserts);
366 void QDeclarativeListCompositor::insert(
367 Group group, int before, void *list, int index, int count, uint flags, QVector<Insert> *inserts)
369 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << before << list << index << count << flags)
370 insert(findInsertPosition(group, before), list, index, count, flags, inserts);
373 QDeclarativeListCompositor::iterator QDeclarativeListCompositor::insert(
374 iterator before, void *list, int index, int count, uint flags, QVector<Insert> *inserts)
376 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< before << list << index << count << flags)
378 inserts->append(Insert(before, count, flags & GroupMask));
380 if (before.offset > 0) {
382 *before, before->list, before->index, before.offset, before->flags & ~AppendFlag)->next;
383 before->index += before.offset;
384 before->count -= before.offset;
388 if (!(flags & AppendFlag) && *before != m_ranges.next
389 && before->previous->list == list
390 && before->previous->flags == flags
391 && (!list || before->previous->end() == index)) {
392 before->previous->count += count;
393 before.incrementIndexes(count, flags);
395 *before = insert(*before, list, index, count, flags);
399 if (!(flags & AppendFlag) && before->next != &m_ranges
400 && before->list == before->next->list
401 && before->flags == before->next->flags
402 && (!list || before->end() == before->next->index)) {
403 before->next->index = before->index;
404 before->next->count += before->count;
405 *before = erase(*before);
408 m_end.incrementIndexes(count, flags);
410 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
414 void QDeclarativeListCompositor::setFlags(
415 Group fromGroup, int from, int count, Group group, int flags, QVector<Insert> *inserts)
417 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index << count << flags)
418 setFlags(find(fromGroup, from), count, group, flags, inserts);
421 void QDeclarativeListCompositor::setFlags(
422 iterator from, int count, Group group, uint flags, QVector<Insert> *inserts)
424 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< from << count << flags)
425 if (!flags || !count)
429 from.incrementIndexes(from->count - from.offset);
432 } else if (from.offset > 0) {
433 *from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
434 from->index += from.offset;
435 from->count -= from.offset;
439 for (; count > 0; *from = from->next) {
440 if (from != from.group) {
441 from.incrementIndexes(from->count);
444 const int difference = qMin(count, from->count);
447 const uint insertFlags = ~from->flags & flags;
448 const uint setFlags = (from->flags | flags) & ~AppendFlag;
449 if (insertFlags && inserts)
450 inserts->append(Insert(from, difference, insertFlags | (from->flags & CacheFlag)));
451 m_end.incrementIndexes(difference, insertFlags);
452 from.incrementIndexes(difference, setFlags);
454 if (from->previous != &m_ranges
455 && from->previous->list == from->list
456 && (!from->list || from->previous->end() == from->index)
457 && from->previous->flags == setFlags) {
458 from->previous->count += difference;
459 from->index += difference;
460 from->count -= difference;
461 if (from->count == 0) {
463 from->previous->flags |= AppendFlag;
464 *from = erase(*from)->previous;
469 } else if (!insertFlags) {
470 from.incrementIndexes(from->count - difference);
472 } else if (difference < from->count) {
473 *from = insert(*from, from->list, from->index, difference, setFlags)->next;
474 from->index += difference;
475 from->count -= difference;
477 from->flags |= flags;
480 from.incrementIndexes(from->count);
483 if (from->previous != &m_ranges
484 && from->previous->list == from->list
485 && (!from->list || from->previous->end() == from->index)
486 && from->previous->flags == (from->flags & ~AppendFlag)) {
487 from.offset = from->previous->count;
488 from->previous->count += from->count;
489 from->previous->flags = from->flags;
490 *from = erase(*from)->previous;
493 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
496 void QDeclarativeListCompositor::clearFlags(
497 Group fromGroup, int from, int count, Group group, uint flags, QVector<Remove> *removes)
499 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index << count << flags)
500 clearFlags(find(fromGroup, from), count, group, flags, removes);
503 void QDeclarativeListCompositor::clearFlags(
504 iterator from, int count, Group group, uint flags, QVector<Remove> *removes)
506 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< from << count << flags)
507 if (!flags || !count)
510 const bool clearCache = flags & CacheFlag;
513 from.incrementIndexes(from->count - from.offset);
516 } else if (from.offset > 0) {
517 *from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
518 from->index += from.offset;
519 from->count -= from.offset;
523 for (; count > 0; *from = from->next) {
525 from.incrementIndexes(from->count);
528 const int difference = qMin(count, from->count);
531 const uint removeFlags = from->flags & flags & ~(AppendFlag | PrependFlag);
532 const uint clearedFlags = from->flags & ~(flags | AppendFlag | UnresolvedFlag);
533 if (removeFlags && removes) {
534 const int maskedFlags = clearCache
535 ? (removeFlags & ~CacheFlag)
536 : (removeFlags | (from->flags & CacheFlag));
538 removes->append(Remove(from, difference, maskedFlags));
540 m_end.decrementIndexes(difference, removeFlags);
541 from.incrementIndexes(difference, clearedFlags);
543 if (from->previous != &m_ranges
544 && from->previous->list == from->list
545 && (!from->list || clearedFlags == CacheFlag || from->previous->end() == from->index)
546 && from->previous->flags == clearedFlags) {
547 from->previous->count += difference;
548 from->index += difference;
549 from->count -= difference;
550 if (from->count == 0) {
552 from->previous->flags |= AppendFlag;
553 *from = erase(*from)->previous;
555 from.incrementIndexes(from->count);
557 } else if (difference < from->count) {
559 *from = insert(*from, from->list, from->index, difference, clearedFlags)->next;
560 from->index += difference;
561 from->count -= difference;
562 from.incrementIndexes(from->count);
563 } else if (clearedFlags) {
564 from->flags &= ~flags;
566 *from = erase(*from)->previous;
570 if (*from != &m_ranges && from->previous != &m_ranges
571 && from->previous->list == from->list
572 && (!from->list || from->previous->end() == from->index)
573 && from->previous->flags == (from->flags & ~AppendFlag)) {
574 from.offset = from->previous->count;
575 from->previous->count += from->count;
576 from->previous->flags = from->flags;
577 *from = erase(*from)->previous;
580 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
583 void QDeclarativeListCompositor::removeList(void *list, QVector<Remove> *removes, bool destroyed)
585 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << destroyed)
586 for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
587 if (it->list == list) {
588 const int flags = it->flags & (GroupMask | CacheFlag);
590 removes->append(Remove(it, it->count, flags));
591 m_end.decrementIndexes(it->count, flags);
596 it->flags = CacheFlag;
597 it.cacheIndex += it->count;
599 *it = erase(*it)->previous;
602 it.incrementIndexes(it->count);
606 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
609 bool QDeclarativeListCompositor::verifyMoveTo(
610 Group fromGroup, int from, Group toGroup, int to, int count, Group group) const
612 if (group != toGroup) {
613 // determine how many items from the destination group intersect with the source group.
614 iterator fromIt = find(fromGroup, from);
616 int intersectingCount = 0;
618 for (; count > 0; *fromIt = fromIt->next) {
619 if (*fromIt == &m_ranges)
621 if (!fromIt->inGroup(group))
623 if (fromIt->inGroup(toGroup))
624 intersectingCount += qMin(count, fromIt->count - fromIt.offset);
625 count -= fromIt->count - fromIt.offset;
628 count = intersectingCount;
631 return to >= 0 && to + count <= m_end.index[toGroup];
634 void QDeclarativeListCompositor::move(
641 QVector<Remove> *removes,
642 QVector<Insert> *inserts)
644 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< fromGroup << from << toGroup << to << count)
645 Q_ASSERT(count != 0);
646 Q_ASSERT(from >=0 && from + count <= m_end.index[toGroup]);
647 Q_ASSERT(verifyMoveTo(fromGroup, from, toGroup, to, count, group));
649 iterator fromIt = find(fromGroup, from);
650 if (fromIt != group) {
651 fromIt.incrementIndexes(fromIt->count - fromIt.offset);
653 *fromIt = fromIt->next;
654 } else if (fromIt.offset > 0) {
656 *fromIt, fromIt->list, fromIt->index, fromIt.offset, fromIt->flags & ~AppendFlag)->next;
657 fromIt->index += fromIt.offset;
658 fromIt->count -= fromIt.offset;
663 for (int moveId = 0; count > 0;) {
664 if (fromIt != group) {
665 fromIt.incrementIndexes(fromIt->count);
666 *fromIt = fromIt->next;
669 int difference = qMin(count, fromIt->count);
676 fromIt->flags & ~(PrependFlag | AppendFlag));
678 removes->append(Remove(fromIt, difference, fromIt->flags, moveId++));
680 fromIt->count -= difference;
682 int removeIndex = fromIt->index;
683 if (fromIt->prepend()
684 && fromIt->previous != &m_ranges
685 && fromIt->previous->flags == PrependFlag
686 && fromIt->previous->list == fromIt->list
687 && fromIt->previous->end() == fromIt->index) {
688 fromIt->previous->count += difference;
689 } else if (fromIt->prepend()) {
690 *fromIt = insert(*fromIt, fromIt->list, removeIndex, difference, PrependFlag)->next;
692 fromIt->index += difference;
694 if (fromIt->count == 0) {
695 if (fromIt->append())
696 fromIt->previous->flags |= AppendFlag;
697 *fromIt = erase(*fromIt);
699 if (*fromIt != m_ranges.next && fromIt->flags == PrependFlag
700 && fromIt->previous != &m_ranges
701 && fromIt->previous->flags == PrependFlag
702 && fromIt->previous->list == fromIt->list
703 && fromIt->previous->end() == fromIt->index) {
704 fromIt.incrementIndexes(fromIt->count);
705 fromIt->previous->count += fromIt->count;
706 *fromIt = erase(*fromIt);
708 } else if (count > 0) {
709 *fromIt = fromIt->next;
713 if (*fromIt != m_ranges.next
714 && *fromIt != &m_ranges
715 && fromIt->previous->list == fromIt->list
716 && (!fromIt->list || fromIt->previous->end() == fromIt->index)
717 && fromIt->previous->flags == (fromIt->flags & ~AppendFlag)) {
718 if (fromIt == fromIt.group)
719 fromIt.offset = fromIt->previous->count;
720 fromIt.offset = fromIt->previous->count;
721 fromIt->previous->count += fromIt->count;
722 fromIt->previous->flags = fromIt->flags;
723 *fromIt = erase(*fromIt)->previous;
726 insert_iterator toIt = fromIt;
727 toIt.setGroup(toGroup);
728 const int difference = to - toIt.index[toGroup];
734 if (toIt.offset > 0) {
735 *toIt = insert(*toIt, toIt->list, toIt->index, toIt.offset, toIt->flags & ~AppendFlag)->next;
736 toIt->index += toIt.offset;
737 toIt->count -= toIt.offset;
741 for (Range *range = movedFlags.previous; range != &movedFlags; range = range->previous) {
742 if (*toIt != &m_ranges
743 && range->list == toIt->list
744 && (!range->list || range->end() == toIt->index)
745 && range->flags == (toIt->flags & ~AppendFlag)) {
746 toIt->index -= range->count;
747 toIt->count += range->count;
749 *toIt = insert(*toIt, range->list, range->index, range->count, range->flags);
753 if (*toIt != m_ranges.next
754 && toIt->previous->list == toIt->list
755 && (!toIt->list || (toIt->previous->end() == toIt->index && toIt->previous->flags == (toIt->flags & ~AppendFlag)))) {
756 toIt.offset = toIt->previous->count;
757 toIt->previous->count += toIt->count;
758 toIt->previous->flags = toIt->flags;
759 *toIt = erase(*toIt)->previous;
761 Insert insert(toIt, 0, 0, 0);
762 for (Range *next, *range = movedFlags.next; range != &movedFlags; range = next) {
763 insert.count = range->count;
764 insert.flags = range->flags;
766 inserts->append(insert);
767 for (int i = 0; i < m_groupCount; ++i) {
768 if (insert.inGroup(i))
769 insert.index[i] += range->count;
777 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
780 void QDeclarativeListCompositor::clear()
782 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR( )
783 for (Range *range = m_ranges.next; range != &m_ranges; range = erase(range)) {}
784 m_end = iterator(m_ranges.next, 0, Default, m_groupCount);
788 void QDeclarativeListCompositor::listItemsInserted(
789 QVector<Insert> *translatedInsertions,
791 const QVector<QDeclarativeChangeSet::Insert> &insertions,
792 const QVector<MovedFlags> *movedFlags)
794 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << insertions)
795 for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
796 if (it->list != list || it->flags == CacheFlag) {
797 it.incrementIndexes(it->count);
799 } else if (it->flags & MovedFlag) {
800 it->flags &= ~MovedFlag;
801 it.incrementIndexes(it->count);
804 foreach (const QDeclarativeChangeSet::Insert &insertion, insertions) {
805 int offset = insertion.index - it->index;
806 if ((offset > 0 && offset < it->count)
807 || (offset == 0 && it->prepend())
808 || (offset == it->count && it->append())) {
810 uint flags = m_defaultFlags;
811 if (insertion.isMove()) {
812 for (QVector<MovedFlags>::const_iterator move = movedFlags->begin();
813 move != movedFlags->end();
815 if (move->moveId == insertion.moveId) {
821 if (flags & ~(AppendFlag | PrependFlag)) {
822 Insert translatedInsert(it, insertion.count, flags, insertion.moveId);
823 for (int i = 0; i < m_groupCount; ++i) {
825 translatedInsert.index[i] += offset;
827 translatedInsertions->append(translatedInsert);
829 if ((it->flags & ~AppendFlag) == flags) {
830 it->count += insertion.count;
831 } else if (offset == 0
832 && it->previous != &m_ranges
833 && it->previous->list == list
834 && it->previous->end() == insertion.index
835 && it->previous->flags == flags) {
836 it->previous->count += insertion.count;
837 it->index += insertion.count;
838 it.incrementIndexes(insertion.count);
841 it.incrementIndexes(offset);
842 *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
844 *it = insert(*it, it->list, insertion.index, insertion.count, flags)->next;
845 it.incrementIndexes(insertion.count, flags);
846 it->index += offset + insertion.count;
849 m_end.incrementIndexes(insertion.count, flags);
852 *it = insert(*it, it->list, it->index, offset, it->flags)->next;
856 it->index += insertion.count;
858 } else if (offset <= 0) {
859 it->index += insertion.count;
862 it.incrementIndexes(it->count);
865 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
868 void QDeclarativeListCompositor::listItemsInserted(
869 void *list, int index, int count, QVector<Insert> *translatedInsertions)
871 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count)
874 QVector<QDeclarativeChangeSet::Insert> insertions;
875 insertions.append(QDeclarativeChangeSet::Insert(index, count));
877 listItemsInserted(translatedInsertions, list, insertions);
880 void QDeclarativeListCompositor::listItemsRemoved(
881 QVector<Remove> *translatedRemovals,
883 QVector<QDeclarativeChangeSet::Remove> *removals,
884 QVector<QDeclarativeChangeSet::Insert> *insertions,
885 QVector<MovedFlags> *movedFlags, int moveId)
887 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << *removals)
889 for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
890 if (it->list != list || it->flags == CacheFlag) {
891 it.incrementIndexes(it->count);
894 bool removed = false;
895 for (QVector<QDeclarativeChangeSet::Remove>::iterator removal = removals->begin();
896 !removed && removal != removals->end();
898 int relativeIndex = removal->index - it->index;
899 int itemsRemoved = removal->count;
900 if (relativeIndex + removal->count > 0 && relativeIndex < it->count) {
901 const int offset = qMax(0, relativeIndex);
902 int removeCount = qMin(it->count, relativeIndex + removal->count) - offset;
903 it->count -= removeCount;
904 int removeFlags = it->flags & m_removeFlags;
905 Remove translatedRemoval(it, removeCount, it->flags);
906 for (int i = 0; i < m_groupCount; ++i) {
908 translatedRemoval.index[i] += offset;
910 if (removal->isMove()) {
911 QVector<QDeclarativeChangeSet::Insert>::iterator insertion = insertions->begin();
912 for (; insertion != insertions->end() && insertion->moveId != removal->moveId;
914 Q_ASSERT(insertion != insertions->end());
915 Q_ASSERT(insertion->count == removal->count);
917 if (relativeIndex < 0) {
918 int splitMoveId = ++moveId;
919 removal = removals->insert(removal, QDeclarativeChangeSet::Remove(
920 removal->index, -relativeIndex, splitMoveId));
922 removal->count -= -relativeIndex;
923 insertion = insertions->insert(insertion, QDeclarativeChangeSet::Insert(
924 insertion->index, -relativeIndex, splitMoveId));
926 insertion->index += -relativeIndex;
927 insertion->count -= -relativeIndex;
931 removeFlags |= it->flags & CacheFlag;
932 translatedRemoval.moveId = ++moveId;
933 movedFlags->append(MovedFlags(moveId, it->flags & ~AppendFlag));
935 if (removeCount < removal->count) {
936 removal = removals->insert(removal, QDeclarativeChangeSet::Remove(
937 removal->index, removeCount, translatedRemoval.moveId));
939 insertion = insertions->insert(insertion, QDeclarativeChangeSet::Insert(
940 insertion->index, removeCount, translatedRemoval.moveId));
943 removal->count -= removeCount;
944 insertion->index += removeCount;
945 insertion->count -= removeCount;
947 removal->moveId = translatedRemoval.moveId;
948 insertion->moveId = translatedRemoval.moveId;
952 *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
955 it.incrementIndexes(offset);
957 if (it->previous != &m_ranges
958 && it->previous->list == it->list
959 && it->end() == insertion->index
960 && it->previous->flags == (it->flags | MovedFlag)) {
961 it->previous->count += removeCount;
963 *it = insert(*it, it->list, insertion->index, removeCount, it->flags | MovedFlag)->next;
965 translatedRemoval.flags = 0;
968 } else if (it->inCache()) {
970 *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
973 it.incrementIndexes(offset);
975 if (it->previous != &m_ranges
976 && it->previous->list == it->list
977 && it->previous->flags == CacheFlag) {
978 it->previous->count += removeCount;
980 *it = insert(*it, it->list, -1, removeCount, CacheFlag)->next;
982 it.index[Cache] += removeCount;
984 if (removeFlags & GroupMask)
985 translatedRemovals->append(translatedRemoval);
986 m_end.decrementIndexes(removeCount, removeFlags);
987 if (it->count == 0 && !it->append()) {
988 *it = erase(*it)->previous;
990 } else if (relativeIndex <= 0) {
991 it->index = removal->index;
993 } else if (relativeIndex < 0) {
994 it->index -= itemsRemoved;
996 if (it->previous != &m_ranges
997 && it->previous->list == it->list
998 && it->previous->end() == it->index
999 && it->previous->flags == (it->flags & ~AppendFlag)) {
1000 it.decrementIndexes(it->previous->count);
1001 it->previous->count += it->count;
1002 it->previous->flags = it->flags;
1003 *it = erase(*it)->previous;
1007 if (it->flags == CacheFlag && it->next->flags == CacheFlag && it->next->list == it->list) {
1008 it.index[Cache] += it->next->count;
1009 it->count += it->next->count;
1011 } else if (!removed) {
1012 it.incrementIndexes(it->count);
1016 QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
1019 void QDeclarativeListCompositor::listItemsRemoved(
1020 void *list, int index, int count, QVector<Remove> *translatedRemovals)
1022 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count)
1023 Q_ASSERT(count >= 0);
1025 QVector<QDeclarativeChangeSet::Remove> removals;
1026 removals.append(QDeclarativeChangeSet::Remove(index, count));
1027 listItemsRemoved(translatedRemovals, list, &removals, 0, 0, 0);
1030 void QDeclarativeListCompositor::listItemsMoved(
1035 QVector<Remove> *translatedRemovals,
1036 QVector<Insert> *translatedInsertions)
1038 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << from << to << count)
1039 Q_ASSERT(count >= 0);
1041 QVector<QDeclarativeChangeSet::Remove> removals;
1042 QVector<QDeclarativeChangeSet::Insert> insertions;
1043 QVector<MovedFlags> movedFlags;
1044 removals.append(QDeclarativeChangeSet::Remove(from, count, 0));
1045 insertions.append(QDeclarativeChangeSet::Insert(to, count, 0));
1047 listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags, 0);
1048 listItemsInserted(translatedInsertions, list, insertions, &movedFlags);
1051 void QDeclarativeListCompositor::listItemsChanged(
1052 QVector<Change> *translatedChanges,
1054 const QVector<QDeclarativeChangeSet::Change> &changes)
1056 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << changes)
1057 for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
1058 if (it->list != list || it->flags == CacheFlag) {
1059 it.incrementIndexes(it->count);
1061 } else if (!it->inGroup()) {
1064 foreach (const QDeclarativeChangeSet::Change &change, changes) {
1065 const int offset = change.index - it->index;
1066 if (offset + change.count > 0 && offset < it->count) {
1067 const int changeOffset = qMax(0, offset);
1068 const int changeCount = qMin(it->count, offset + change.count) - changeOffset;
1070 Change translatedChange(it, changeCount, it->flags);
1071 for (int i = 0; i < m_groupCount; ++i) {
1073 translatedChange.index[i] += changeOffset;
1075 translatedChanges->append(translatedChange);
1078 it.incrementIndexes(it->count);
1082 void QDeclarativeListCompositor::listItemsChanged(
1083 void *list, int index, int count, QVector<Change> *translatedChanges)
1085 QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count)
1086 Q_ASSERT(count >= 0);
1087 QVector<QDeclarativeChangeSet::Change> changes;
1088 changes.append(QDeclarativeChangeSet::Change(index, count));
1089 listItemsChanged(translatedChanges, list, changes);
1092 void QDeclarativeListCompositor::listChanged(
1094 const QDeclarativeChangeSet &changeSet,
1095 QVector<Remove> *translatedRemovals,
1096 QVector<Insert> *translatedInsertions,
1097 QVector<Change> *translatedChanges)
1099 QVector<QDeclarativeChangeSet::Remove> removals = changeSet.removes();
1100 QVector<QDeclarativeChangeSet::Insert> insertions = changeSet.inserts();
1101 QVector<MovedFlags> movedFlags;
1102 listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags, changeSet.moveCounter());
1103 listItemsInserted(translatedInsertions, list, insertions, &movedFlags);
1104 listItemsChanged(translatedChanges, list, changeSet.changes());
1107 void QDeclarativeListCompositor::transition(
1110 QVector<QDeclarativeChangeSet::Remove> *removes,
1111 QVector<QDeclarativeChangeSet::Insert> *inserts)
1113 int removeCount = 0;
1114 for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
1115 if (it == from && it != to) {
1116 removes->append(QDeclarativeChangeSet::Remove(it.index[from]- removeCount, it->count));
1117 removeCount += it->count;
1118 } else if (it != from && it == to) {
1119 inserts->append(QDeclarativeChangeSet::Insert(it.index[to], it->count));
1121 it.incrementIndexes(it->count);
1125 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Group &group)
1128 case QDeclarativeListCompositor::Cache: return debug << "Cache";
1129 case QDeclarativeListCompositor::Default: return debug << "Default";
1130 default: return (debug.nospace() << "Group" << int(group)).space();
1135 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Range &range)
1139 << range.list) << " "
1140 << range.index << " "
1141 << range.count << " "
1142 << (range.isUnresolved() ? "U" : "0")
1143 << (range.append() ? "A" : "0")
1144 << (range.prepend() ? "P" : "0");
1145 for (int i = QDeclarativeListCompositor::MaximumGroupCount - 1; i >= 2; --i)
1146 debug << (range.inGroup(i) ? "1" : "0");
1148 << (range.inGroup(QDeclarativeListCompositor::Default) ? "D" : "0")
1149 << (range.inGroup(QDeclarativeListCompositor::Cache) ? "C" : "0"));
1152 static void qt_print_indexes(QDebug &debug, int count, const int *indexes)
1154 for (int i = count - 1; i >= 0; --i)
1155 debug << indexes[i];
1158 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::iterator &it)
1160 (debug.nospace() << "iterator(" << it.group).space() << "offset:" << it.offset;
1161 qt_print_indexes(debug, it.groupCount, it.index);
1162 return ((debug << **it).nospace() << ")").space();
1165 static QDebug qt_print_change(QDebug debug, const char *name, const QDeclarativeListCompositor::Change &change)
1167 debug.nospace() << name << "(" << change.moveId << " " << change.count << " ";
1168 for (int i = QDeclarativeListCompositor::MaximumGroupCount - 1; i >= 2; --i)
1169 debug << (change.inGroup(i) ? "1" : "0");
1170 debug << (change.inGroup(QDeclarativeListCompositor::Default) ? "D" : "0")
1171 << (change.inGroup(QDeclarativeListCompositor::Cache) ? "C" : "0");
1172 int i = QDeclarativeListCompositor::MaximumGroupCount - 1;
1173 for (; i >= 0 && !change.inGroup(i); --i) {}
1175 debug << " " << change.index[i];
1176 return (debug << ")").maybeSpace();
1179 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Change &change)
1181 return qt_print_change(debug, "Change", change);
1184 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Remove &remove)
1186 return qt_print_change(debug, "Remove", remove);
1189 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Insert &insert)
1191 return qt_print_change(debug, "Insert", insert);
1194 QDebug operator <<(QDebug debug, const QDeclarativeListCompositor &list)
1196 int indexes[QDeclarativeListCompositor::MaximumGroupCount];
1197 for (int i = 0; i < QDeclarativeListCompositor::MaximumGroupCount; ++i)
1199 debug.nospace() << "QDeclarativeListCompositor(";
1200 qt_print_indexes(debug, list.m_groupCount, list.m_end.index);
1201 for (QDeclarativeListCompositor::Range *range = list.m_ranges.next; range != &list.m_ranges; range = range->next) {
1202 (debug << "\n").space();
1203 qt_print_indexes(debug, list.m_groupCount, indexes);
1204 debug << " " << *range;
1206 for (int i = 0; i < list.m_groupCount; ++i) {
1207 if (range->inGroup(i))
1208 indexes[i] += range->count;
1211 return (debug << ")").maybeSpace();