1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtQml module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | #include "qqmllistcompositor_p.h" |
41 | |
42 | #include <QtCore/qvarlengtharray.h> |
43 | |
44 | //#define QT_QML_VERIFY_MINIMAL |
45 | //#define QT_QML_VERIFY_INTEGRITY |
46 | |
47 | QT_BEGIN_NAMESPACE |
48 | |
49 | /*! |
50 | \class QQmlListCompositor |
51 | \brief The QQmlListCompositor class provides a lookup table for filtered, or re-ordered list |
52 | indexes. |
53 | \internal |
54 | |
55 | QQmlListCompositor is intended as an aid for developing proxy models. It doesn't however |
56 | directly proxy a list or model, instead a range of indexes from one or many lists can be |
57 | inserted into the compositor and then categorized and shuffled around and it will manage the |
58 | task of translating from an index in the combined space into an index in a particular list. |
59 | |
60 | Within a compositor indexes are categorized into groups where a group is a sub-set of the |
61 | total indexes referenced by the compositor, each with an address space ranging from 0 to |
62 | the number of indexes in the group - 1. Group memberships are independent of each other with |
63 | the one exception that items always retain the same order so if an index is moved within a |
64 | group, its position in other groups will change as well. |
65 | |
66 | The iterator classes encapsulate information about a specific position in a compositor group. |
67 | This includes a source list, the index of an item within that list and the groups that item |
68 | is a member of. The iterator for a specific position in a group can be retrieved with the |
69 | find() function and the addition and subtraction operators of the iterators can be used to |
70 | navigate to adjacent items in the same group. |
71 | |
72 | Items can be added to the compositor with the append() and insert() functions, group |
73 | membership can be changed with the setFlags() and clearFlags() functions, and the position |
74 | of items in the compositor can be changed with the move() function. Each of these functions |
75 | optionally returns a list of the changes made to indexes within each group which can then |
76 | be propagated to view so that it can correctly refresh its contents; e.g. 3 items |
77 | removed at index 6, and 5 items inserted at index 1. The notification changes are always |
78 | ordered from the start of the list to the end and accumulate, so if 5 items are removed at |
79 | index 4, one is skipped and then 3 move are removed, the changes returned are 5 items removed |
80 | at index 4, followed by 3 items removed at index 4. |
81 | |
82 | When the contents of a source list change, the mappings within the compositor can be updated |
83 | with the listItemsInserted(), listItemsRemoved(), listItemsMoved(), and listItemsChanged() |
84 | functions. Like the direct manipulation functions these too return a list of group indexes |
85 | affected by the change. If items are removed from a source list they are also removed from |
86 | any groups they belong to with the one exception being items belonging to the \l Cache group. |
87 | When items belonging to this group are removed the list, index, and other group membership |
88 | information are discarded but Cache membership is retained until explicitly removed. This |
89 | allows the cache index to be retained until cached resources for that item are actually |
90 | released. |
91 | |
92 | Internally the index mapping is stored as a list of Range objects, each has a list identifier, |
93 | a start index, a count, and a set of flags which represent group membership and some other |
94 | properties. The group index of a range is the sum of all preceding ranges that are members of |
95 | that group. To avoid the inefficiency of iterating over potentially all ranges when looking |
96 | for a specific index, each time a lookup is done the range and its indexes are cached and the |
97 | next lookup is done relative to this. This works out to near constant time in most relevant |
98 | use cases because successive index lookups are most frequently adjacent. The total number of |
99 | ranges is often quite small, which helps as well. If there is a need for faster random access |
100 | then a skip list like index may be an appropriate addition. |
101 | |
102 | \sa DelegateModel |
103 | */ |
104 | |
105 | #ifdef QT_QML_VERIFY_MINIMAL |
106 | #define QT_QML_VERIFY_INTEGRITY |
107 | /* |
108 | Diagnostic to verify there are no consecutive ranges, or that the compositor contains the |
109 | most compact representation possible. |
110 | |
111 | Returns false and prints a warning if any range has a starting index equal to the end |
112 | (index + count) index of the previous range, and both ranges also have the same flags and list |
113 | property. |
114 | |
115 | If there are no consecutive ranges this will return true. |
116 | */ |
117 | |
118 | static bool qt_verifyMinimal( |
119 | const QQmlListCompositor::iterator &begin, |
120 | const QQmlListCompositor::iterator &end) |
121 | { |
122 | bool minimal = true; |
123 | int index = 0; |
124 | |
125 | for (const QQmlListCompositor::Range *range = begin->next; range != *end; range = range->next, ++index) { |
126 | if (range->previous->list == range->list |
127 | && range->previous->flags == (range->flags & ~QQmlListCompositor::AppendFlag) |
128 | && range->previous->end() == range->index) { |
129 | qWarning() << index << "Consecutive ranges" ; |
130 | qWarning() << *range->previous; |
131 | qWarning() << *range; |
132 | minimal = false; |
133 | } |
134 | } |
135 | |
136 | return minimal; |
137 | } |
138 | |
139 | #endif |
140 | |
141 | #ifdef QT_QML_VERIFY_INTEGRITY |
142 | static bool qt_printInfo(const QQmlListCompositor &compositor) |
143 | { |
144 | qWarning() << compositor; |
145 | return true; |
146 | } |
147 | |
148 | /* |
149 | Diagnostic to verify the integrity of a compositor. |
150 | |
151 | Per range this verifies there are no invalid range combinations, that non-append ranges have |
152 | positive non-zero counts, and that list ranges have non-negative indexes. |
153 | |
154 | Accumulatively this verifies that the cached total group counts match the sum of counts |
155 | of member ranges. |
156 | */ |
157 | |
158 | static bool qt_verifyIntegrity( |
159 | const QQmlListCompositor::iterator &begin, |
160 | const QQmlListCompositor::iterator &end, |
161 | const QQmlListCompositor::iterator &cachedIt) |
162 | { |
163 | bool valid = true; |
164 | |
165 | int index = 0; |
166 | QQmlListCompositor::iterator it; |
167 | for (it = begin; *it != *end; *it = it->next) { |
168 | if (it->count == 0 && !it->append()) { |
169 | qWarning() << index << "Empty non-append range" ; |
170 | valid = false; |
171 | } |
172 | if (it->count < 0) { |
173 | qWarning() << index << "Negative count" ; |
174 | valid = false; |
175 | } |
176 | if (it->list && it->flags != QQmlListCompositor::CacheFlag && it->index < 0) { |
177 | qWarning() << index <<"Negative index" ; |
178 | valid = false; |
179 | } |
180 | if (it->previous->next != it.range) { |
181 | qWarning() << index << "broken list: it->previous->next != it.range" ; |
182 | valid = false; |
183 | } |
184 | if (it->next->previous != it.range) { |
185 | qWarning() << index << "broken list: it->next->previous != it.range" ; |
186 | valid = false; |
187 | } |
188 | if (*it == *cachedIt) { |
189 | for (int i = 0; i < end.groupCount; ++i) { |
190 | int groupIndex = it.index[i]; |
191 | if (cachedIt->flags & (1 << i)) |
192 | groupIndex += cachedIt.offset; |
193 | if (groupIndex != cachedIt.index[i]) { |
194 | qWarning() << index |
195 | << "invalid cached index" |
196 | << QQmlListCompositor::Group(i) |
197 | << "Expected:" |
198 | << groupIndex |
199 | << "Actual" |
200 | << cachedIt.index[i] |
201 | << cachedIt; |
202 | valid = false; |
203 | } |
204 | } |
205 | } |
206 | it.incrementIndexes(it->count); |
207 | ++index; |
208 | } |
209 | |
210 | for (int i = 0; i < end.groupCount; ++i) { |
211 | if (end.index[i] != it.index[i]) { |
212 | qWarning() << "Group" << i << "count invalid. Expected:" << end.index[i] << "Actual:" << it.index[i]; |
213 | valid = false; |
214 | } |
215 | } |
216 | return valid; |
217 | } |
218 | #endif |
219 | |
220 | #if defined(QT_QML_VERIFY_MINIMAL) |
221 | # define QT_QML_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!(qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \ |
222 | && qt_verifyMinimal(iterator(m_ranges.next, 0, Default, m_groupCount), m_end)) \ |
223 | && qt_printInfo(*this))); |
224 | #elif defined(QT_QML_VERIFY_INTEGRITY) |
225 | # define QT_QML_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \ |
226 | && qt_printInfo(*this))); |
227 | #else |
228 | # define QT_QML_VERIFY_LISTCOMPOSITOR |
229 | #endif |
230 | |
231 | //#define QT_QML_TRACE_LISTCOMPOSITOR(args) qDebug() << m_end.index[1] << m_end.index[0] << Q_FUNC_INFO args; |
232 | #define QT_QML_TRACE_LISTCOMPOSITOR(args) |
233 | |
234 | QQmlListCompositor::iterator &QQmlListCompositor::iterator::operator +=(int difference) |
235 | { |
236 | // Update all indexes to the start of the range. |
237 | decrementIndexes(difference: offset); |
238 | |
239 | // If the iterator group isn't a member of the current range ignore the current offset. |
240 | if (!(range->flags & groupFlag)) |
241 | offset = 0; |
242 | |
243 | offset += difference; |
244 | |
245 | // Iterate backwards looking for a range with a positive offset. |
246 | while (offset <= 0 && range->previous->flags) { |
247 | range = range->previous; |
248 | if (range->flags & groupFlag) |
249 | offset += range->count; |
250 | decrementIndexes(difference: range->count); |
251 | } |
252 | |
253 | // Iterate forwards looking for the first range which contains both the offset and the |
254 | // iterator group. |
255 | while (range->flags && (offset >= range->count || !(range->flags & groupFlag))) { |
256 | if (range->flags & groupFlag) |
257 | offset -= range->count; |
258 | incrementIndexes(difference: range->count); |
259 | range = range->next; |
260 | } |
261 | |
262 | // Update all the indexes to inclue the remaining offset. |
263 | incrementIndexes(difference: offset); |
264 | |
265 | return *this; |
266 | } |
267 | |
268 | QQmlListCompositor::insert_iterator &QQmlListCompositor::insert_iterator::operator +=(int difference) |
269 | { |
270 | iterator::operator +=(difference); |
271 | |
272 | // If the previous range contains the append flag move the iterator to the tail of the previous |
273 | // range so that appended appear after the insert position. |
274 | if (offset == 0 && range->previous->append()) { |
275 | range = range->previous; |
276 | offset = range->inGroup() ? range->count : 0; |
277 | } |
278 | |
279 | return *this; |
280 | } |
281 | |
282 | |
283 | /*! |
284 | Constructs an empty list compositor. |
285 | */ |
286 | |
287 | QQmlListCompositor::QQmlListCompositor() |
288 | : m_end(m_ranges.next, 0, Default, 2) |
289 | , m_cacheIt(m_end) |
290 | , m_groupCount(2) |
291 | , m_defaultFlags(PrependFlag | DefaultFlag) |
292 | , m_removeFlags(AppendFlag | PrependFlag | GroupMask) |
293 | , m_moveId(0) |
294 | { |
295 | } |
296 | |
297 | /*! |
298 | Destroys a list compositor. |
299 | */ |
300 | |
301 | QQmlListCompositor::~QQmlListCompositor() |
302 | { |
303 | for (Range *next, *range = m_ranges.next; range != &m_ranges; range = next) { |
304 | next = range->next; |
305 | delete range; |
306 | } |
307 | } |
308 | |
309 | /*! |
310 | Inserts a range with the given source \a list, start \a index, \a count and \a flags, in front |
311 | of the existing range \a before. |
312 | */ |
313 | |
314 | inline QQmlListCompositor::Range *QQmlListCompositor::insert( |
315 | Range *before, void *list, int index, int count, uint flags) |
316 | { |
317 | return new Range(before, list, index, count, flags); |
318 | } |
319 | |
320 | /*! |
321 | Erases a \a range from the compositor. |
322 | |
323 | Returns a pointer to the next range in the compositor. |
324 | */ |
325 | |
326 | inline QQmlListCompositor::Range *QQmlListCompositor::erase( |
327 | Range *range) |
328 | { |
329 | Range *next = range->next; |
330 | next->previous = range->previous; |
331 | next->previous->next = range->next; |
332 | delete range; |
333 | return next; |
334 | } |
335 | |
336 | /*! |
337 | Sets the number (\a count) of possible groups that items may belong to in a compositor. |
338 | */ |
339 | |
340 | void QQmlListCompositor::setGroupCount(int count) |
341 | { |
342 | m_groupCount = count; |
343 | m_end = iterator(&m_ranges, 0, Default, m_groupCount); |
344 | m_cacheIt = m_end; |
345 | } |
346 | |
347 | /*! |
348 | Returns the number of items that belong to a \a group. |
349 | */ |
350 | |
351 | int QQmlListCompositor::count(Group group) const |
352 | { |
353 | return m_end.index[group]; |
354 | } |
355 | |
356 | /*! |
357 | Returns an iterator representing the item at \a index in a \a group. |
358 | |
359 | The index must be between 0 and count(group) - 1. |
360 | */ |
361 | |
362 | QQmlListCompositor::iterator QQmlListCompositor::find(Group group, int index) |
363 | { |
364 | QT_QML_TRACE_LISTCOMPOSITOR(<< group << index) |
365 | Q_ASSERT(index >=0 && index < count(group)); |
366 | if (m_cacheIt == m_end) { |
367 | m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount); |
368 | m_cacheIt += index; |
369 | } else { |
370 | const int offset = index - m_cacheIt.index[group]; |
371 | m_cacheIt.setGroup(group); |
372 | m_cacheIt += offset; |
373 | } |
374 | Q_ASSERT(m_cacheIt.index[group] == index); |
375 | Q_ASSERT(m_cacheIt->inGroup(group)); |
376 | QT_QML_VERIFY_LISTCOMPOSITOR |
377 | return m_cacheIt; |
378 | } |
379 | |
380 | /*! |
381 | Returns an iterator representing the item at \a index in a \a group. |
382 | |
383 | The index must be between 0 and count(group) - 1. |
384 | */ |
385 | |
386 | QQmlListCompositor::iterator QQmlListCompositor::find(Group group, int index) const |
387 | { |
388 | return const_cast<QQmlListCompositor *>(this)->find(group, index); |
389 | } |
390 | |
391 | /*! |
392 | Returns an iterator representing an insert position in front of the item at \a index in a |
393 | \a group. |
394 | |
395 | The iterator for an insert position can sometimes resolve to a different Range than a regular |
396 | iterator. This is because when items are inserted on a boundary between Ranges, if the first |
397 | range has the Append flag set then the items should be inserted into that range to ensure |
398 | that the append position for the existing range remains after the insert position. |
399 | |
400 | The index must be between 0 and count(group) - 1. |
401 | */ |
402 | |
403 | QQmlListCompositor::insert_iterator QQmlListCompositor::findInsertPosition(Group group, int index) |
404 | { |
405 | QT_QML_TRACE_LISTCOMPOSITOR(<< group << index) |
406 | Q_ASSERT(index >=0 && index <= count(group)); |
407 | insert_iterator it; |
408 | if (m_cacheIt == m_end) { |
409 | it = iterator(m_ranges.next, 0, group, m_groupCount); |
410 | it += index; |
411 | } else { |
412 | const int offset = index - m_cacheIt.index[group]; |
413 | it = m_cacheIt; |
414 | it.setGroup(group); |
415 | it += offset; |
416 | } |
417 | Q_ASSERT(it.index[group] == index); |
418 | return it; |
419 | } |
420 | |
421 | /*! |
422 | Appends a range of \a count indexes starting at \a index from a \a list into a compositor |
423 | with the given \a flags. |
424 | |
425 | If supplied the \a inserts list will be populated with the positions of the inserted items |
426 | in each group. |
427 | */ |
428 | |
429 | void QQmlListCompositor::append( |
430 | void *list, int index, int count, uint flags, QVector<Insert> *inserts) |
431 | { |
432 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count << flags) |
433 | insert(before: m_end, list, index, count, flags, inserts); |
434 | } |
435 | |
436 | /*! |
437 | Inserts a range of \a count indexes starting at \a index from a \a list with the given \a flags |
438 | into a \a group at index \a before. |
439 | |
440 | If supplied the \a inserts list will be populated with the positions of items inserted into |
441 | each group. |
442 | */ |
443 | |
444 | void QQmlListCompositor::insert( |
445 | Group group, int before, void *list, int index, int count, uint flags, QVector<Insert> *inserts) |
446 | { |
447 | QT_QML_TRACE_LISTCOMPOSITOR(<< group << before << list << index << count << flags) |
448 | insert(before: findInsertPosition(group, index: before), list, index, count, flags, inserts); |
449 | } |
450 | |
451 | /*! |
452 | Inserts a range of \a count indexes starting at \a index from a \a list with the given \a flags |
453 | into a compositor at position \a before. |
454 | |
455 | If supplied the \a inserts list will be populated with the positions of items inserted into |
456 | each group. |
457 | */ |
458 | |
459 | QQmlListCompositor::iterator QQmlListCompositor::insert( |
460 | iterator before, void *list, int index, int count, uint flags, QVector<Insert> *inserts) |
461 | { |
462 | QT_QML_TRACE_LISTCOMPOSITOR(<< before << list << index << count << flags) |
463 | if (inserts) { |
464 | inserts->append(t: Insert(before, count, flags & GroupMask)); |
465 | } |
466 | if (before.offset > 0) { |
467 | // Inserting into the middle of a range. Split it two and update the iterator so it's |
468 | // positioned at the start of the second half. |
469 | *before = insert( |
470 | before: *before, list: before->list, index: before->index, count: before.offset, flags: before->flags & ~AppendFlag)->next; |
471 | before->index += before.offset; |
472 | before->count -= before.offset; |
473 | before.offset = 0; |
474 | } |
475 | |
476 | |
477 | if (!(flags & AppendFlag) && *before != m_ranges.next |
478 | && before->previous->list == list |
479 | && before->previous->flags == flags |
480 | && (!list || before->previous->end() == index)) { |
481 | // The insert arguments represent a continuation of the previous range so increment |
482 | // its count instead of inserting a new range. |
483 | before->previous->count += count; |
484 | before.incrementIndexes(difference: count, flags); |
485 | } else { |
486 | *before = insert(before: *before, list, index, count, flags); |
487 | before.offset = 0; |
488 | } |
489 | |
490 | if (!(flags & AppendFlag) && before->next != &m_ranges |
491 | && before->list == before->next->list |
492 | && before->flags == before->next->flags |
493 | && (!list || before->end() == before->next->index)) { |
494 | // The current range and the next are continuous so add their counts and delete one. |
495 | before->next->index = before->index; |
496 | before->next->count += before->count; |
497 | *before = erase(range: *before); |
498 | } |
499 | |
500 | m_end.incrementIndexes(difference: count, flags); |
501 | m_cacheIt = before; |
502 | QT_QML_VERIFY_LISTCOMPOSITOR |
503 | return before; |
504 | } |
505 | |
506 | /*! |
507 | Sets the given flags \a flags on \a count items belonging to \a group starting at the position |
508 | identified by \a fromGroup and the index \a from. |
509 | |
510 | If supplied the \a inserts list will be populated with insert notifications for affected groups. |
511 | */ |
512 | |
513 | void QQmlListCompositor::setFlags( |
514 | Group fromGroup, int from, int count, Group group, int flags, QVector<Insert> *inserts) |
515 | { |
516 | QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << count << group << flags) |
517 | setFlags(from: find(group: fromGroup, index: from), count, group, flags, inserts); |
518 | } |
519 | |
520 | /*! |
521 | Sets the given flags \a flags on \a count items belonging to \a group starting at the position |
522 | \a from. |
523 | |
524 | If supplied the \a inserts list will be populated with insert notifications for affected groups. |
525 | */ |
526 | |
527 | void QQmlListCompositor::setFlags( |
528 | iterator from, int count, Group group, uint flags, QVector<Insert> *inserts) |
529 | { |
530 | QT_QML_TRACE_LISTCOMPOSITOR(<< from << count << flags) |
531 | if (!flags || !count) |
532 | return; |
533 | |
534 | if (from != group) { |
535 | // Skip to the next full range if the start one is not a member of the target group. |
536 | from.incrementIndexes(difference: from->count - from.offset); |
537 | from.offset = 0; |
538 | *from = from->next; |
539 | } else if (from.offset > 0) { |
540 | // If the start position is mid range split off the portion unaffected. |
541 | *from = insert(before: *from, list: from->list, index: from->index, count: from.offset, flags: from->flags & ~AppendFlag)->next; |
542 | from->index += from.offset; |
543 | from->count -= from.offset; |
544 | from.offset = 0; |
545 | } |
546 | |
547 | for (; count > 0; *from = from->next) { |
548 | if (from != from.group) { |
549 | // Skip ranges that are not members of the target group. |
550 | from.incrementIndexes(difference: from->count); |
551 | continue; |
552 | } |
553 | // Find the number of items affected in the current range. |
554 | const int difference = qMin(a: count, b: from->count); |
555 | count -= difference; |
556 | |
557 | // Determine the actual changes made to the range and increment counts accordingly. |
558 | const uint insertFlags = ~from->flags & flags; |
559 | const uint setFlags = (from->flags | flags) & ~AppendFlag; |
560 | if (insertFlags && inserts) |
561 | inserts->append(t: Insert(from, difference, insertFlags | (from->flags & CacheFlag))); |
562 | m_end.incrementIndexes(difference, flags: insertFlags); |
563 | from.incrementIndexes(difference, flags: setFlags); |
564 | |
565 | if (from->previous != &m_ranges |
566 | && from->previous->list == from->list |
567 | && (!from->list || from->previous->end() == from->index) |
568 | && from->previous->flags == setFlags) { |
569 | // If the additional flags make the current range a continuation of the previous |
570 | // then move the affected items over to the previous range. |
571 | from->previous->count += difference; |
572 | from->index += difference; |
573 | from->count -= difference; |
574 | if (from->count == 0) { |
575 | // Delete the current range if it is now empty, preserving the append flag |
576 | // in the previous range. |
577 | if (from->append()) |
578 | from->previous->flags |= AppendFlag; |
579 | *from = erase(range: *from)->previous; |
580 | continue; |
581 | } else { |
582 | break; |
583 | } |
584 | } else if (!insertFlags) { |
585 | // No new flags, so roll onto the next range. |
586 | from.incrementIndexes(difference: from->count - difference); |
587 | continue; |
588 | } else if (difference < from->count) { |
589 | // Create a new range with the updated flags, and remove the affected items |
590 | // from the current range. |
591 | *from = insert(before: *from, list: from->list, index: from->index, count: difference, flags: setFlags)->next; |
592 | from->index += difference; |
593 | from->count -= difference; |
594 | } else { |
595 | // The whole range is affected so simply update the flags. |
596 | from->flags |= flags; |
597 | continue; |
598 | } |
599 | from.incrementIndexes(difference: from->count); |
600 | } |
601 | |
602 | if (from->previous != &m_ranges |
603 | && from->previous->list == from->list |
604 | && (!from->list || from->previous->end() == from->index) |
605 | && from->previous->flags == (from->flags & ~AppendFlag)) { |
606 | // If the following range is now a continuation, merge it with its previous range. |
607 | from.offset = from->previous->count; |
608 | from->previous->count += from->count; |
609 | from->previous->flags = from->flags; |
610 | *from = erase(range: *from)->previous; |
611 | } |
612 | m_cacheIt = from; |
613 | QT_QML_VERIFY_LISTCOMPOSITOR |
614 | } |
615 | |
616 | /*! |
617 | Clears the given flags \a flags on \a count items belonging to \a group starting at the position |
618 | \a from. |
619 | |
620 | If supplied the \a removes list will be populated with remove notifications for affected groups. |
621 | */ |
622 | |
623 | void QQmlListCompositor::clearFlags( |
624 | Group fromGroup, int from, int count, Group group, uint flags, QVector<Remove> *removes) |
625 | { |
626 | QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << count << group << flags) |
627 | clearFlags(from: find(group: fromGroup, index: from), count, group, flags, removals: removes); |
628 | } |
629 | |
630 | /*! |
631 | Clears the given flags \a flags on \a count items belonging to \a group starting at the position |
632 | identified by \a fromGroup and the index \a from. |
633 | |
634 | If supplied the \a removes list will be populated with remove notifications for affected groups. |
635 | */ |
636 | |
637 | void QQmlListCompositor::clearFlags( |
638 | iterator from, int count, Group group, uint flags, QVector<Remove> *removes) |
639 | { |
640 | QT_QML_TRACE_LISTCOMPOSITOR(<< from << count << flags) |
641 | if (!flags || !count) |
642 | return; |
643 | |
644 | const bool clearCache = flags & CacheFlag; |
645 | |
646 | if (from != group) { |
647 | // Skip to the next full range if the start one is not a member of the target group. |
648 | from.incrementIndexes(difference: from->count - from.offset); |
649 | from.offset = 0; |
650 | *from = from->next; |
651 | } else if (from.offset > 0) { |
652 | // If the start position is mid range split off the portion unaffected. |
653 | *from = insert(before: *from, list: from->list, index: from->index, count: from.offset, flags: from->flags & ~AppendFlag)->next; |
654 | from->index += from.offset; |
655 | from->count -= from.offset; |
656 | from.offset = 0; |
657 | } |
658 | |
659 | for (; count > 0; *from = from->next) { |
660 | if (from != group) { |
661 | // Skip ranges that are not members of the target group. |
662 | from.incrementIndexes(difference: from->count); |
663 | continue; |
664 | } |
665 | // Find the number of items affected in the current range. |
666 | const int difference = qMin(a: count, b: from->count); |
667 | count -= difference; |
668 | |
669 | |
670 | // Determine the actual changes made to the range and decrement counts accordingly. |
671 | const uint removeFlags = from->flags & flags & ~(AppendFlag | PrependFlag); |
672 | const uint clearedFlags = from->flags & ~(flags | AppendFlag | UnresolvedFlag); |
673 | if (removeFlags && removes) { |
674 | const int maskedFlags = clearCache |
675 | ? (removeFlags & ~CacheFlag) |
676 | : (removeFlags | (from->flags & CacheFlag)); |
677 | if (maskedFlags) |
678 | removes->append(t: Remove(from, difference, maskedFlags)); |
679 | } |
680 | m_end.decrementIndexes(difference, flags: removeFlags); |
681 | from.incrementIndexes(difference, flags: clearedFlags); |
682 | |
683 | if (from->previous != &m_ranges |
684 | && from->previous->list == from->list |
685 | && (!from->list || clearedFlags == CacheFlag || from->previous->end() == from->index) |
686 | && from->previous->flags == clearedFlags) { |
687 | // If the removed flags make the current range a continuation of the previous |
688 | // then move the affected items over to the previous range. |
689 | from->previous->count += difference; |
690 | from->index += difference; |
691 | from->count -= difference; |
692 | if (from->count == 0) { |
693 | // Delete the current range if it is now empty, preserving the append flag |
694 | if (from->append()) |
695 | from->previous->flags |= AppendFlag; |
696 | *from = erase(range: *from)->previous; |
697 | } else { |
698 | from.incrementIndexes(difference: from->count); |
699 | } |
700 | } else if (difference < from->count) { |
701 | // Create a new range with the reduced flags, and remove the affected items from |
702 | // the current range. |
703 | if (clearedFlags) |
704 | *from = insert(before: *from, list: from->list, index: from->index, count: difference, flags: clearedFlags)->next; |
705 | from->index += difference; |
706 | from->count -= difference; |
707 | from.incrementIndexes(difference: from->count); |
708 | } else if (clearedFlags) { |
709 | // The whole range is affected so simply update the flags. |
710 | from->flags &= ~flags; |
711 | } else { |
712 | // All flags have been removed from the range so remove it. |
713 | *from = erase(range: *from)->previous; |
714 | } |
715 | } |
716 | |
717 | if (*from != &m_ranges && from->previous != &m_ranges |
718 | && from->previous->list == from->list |
719 | && (!from->list || from->previous->end() == from->index) |
720 | && from->previous->flags == (from->flags & ~AppendFlag)) { |
721 | // If the following range is now a continuation, merge it with its previous range. |
722 | from.offset = from->previous->count; |
723 | from->previous->count += from->count; |
724 | from->previous->flags = from->flags; |
725 | *from = erase(range: *from)->previous; |
726 | } |
727 | m_cacheIt = from; |
728 | QT_QML_VERIFY_LISTCOMPOSITOR |
729 | } |
730 | |
731 | bool QQmlListCompositor::verifyMoveTo( |
732 | Group fromGroup, int from, Group toGroup, int to, int count, Group group) const |
733 | { |
734 | if (group != toGroup) { |
735 | // determine how many items from the destination group intersect with the source group. |
736 | iterator fromIt = find(group: fromGroup, index: from); |
737 | |
738 | int intersectingCount = 0; |
739 | |
740 | for (; count > 0; *fromIt = fromIt->next) { |
741 | if (*fromIt == &m_ranges) |
742 | return false; |
743 | if (!fromIt->inGroup(group)) |
744 | continue; |
745 | if (fromIt->inGroup(group: toGroup)) |
746 | intersectingCount += qMin(a: count, b: fromIt->count - fromIt.offset); |
747 | count -= fromIt->count - fromIt.offset; |
748 | fromIt.offset = 0; |
749 | } |
750 | count = intersectingCount; |
751 | } |
752 | |
753 | return to >= 0 && to + count <= m_end.index[toGroup]; |
754 | } |
755 | |
756 | /*! |
757 | \internal |
758 | |
759 | Moves \a count items belonging to \a moveGroup from the index \a from in \a fromGroup |
760 | to the index \a to in \a toGroup. |
761 | |
762 | If \a removes and \a inserts are not null they will be populated with per group notifications |
763 | of the items moved. |
764 | */ |
765 | |
766 | void QQmlListCompositor::move( |
767 | Group fromGroup, |
768 | int from, |
769 | Group toGroup, |
770 | int to, |
771 | int count, |
772 | Group moveGroup, |
773 | QVector<Remove> *removes, |
774 | QVector<Insert> *inserts) |
775 | { |
776 | QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << toGroup << to << count) |
777 | Q_ASSERT(count > 0); |
778 | Q_ASSERT(from >=0); |
779 | Q_ASSERT(verifyMoveTo(fromGroup, from, toGroup, to, count, moveGroup)); |
780 | |
781 | // Find the position of the first item to move. |
782 | iterator fromIt = find(group: fromGroup, index: from); |
783 | |
784 | if (fromIt != moveGroup) { |
785 | // If the range at the from index doesn't contain items from the move group; skip |
786 | // to the next range. |
787 | fromIt.incrementIndexes(difference: fromIt->count - fromIt.offset); |
788 | fromIt.offset = 0; |
789 | *fromIt = fromIt->next; |
790 | } else if (fromIt.offset > 0) { |
791 | // If the range at the from index contains items from the move group and the index isn't |
792 | // at the start of the range; split the range at the index and move the iterator to start |
793 | // of the second range. |
794 | *fromIt = insert( |
795 | before: *fromIt, list: fromIt->list, index: fromIt->index, count: fromIt.offset, flags: fromIt->flags & ~AppendFlag)->next; |
796 | fromIt->index += fromIt.offset; |
797 | fromIt->count -= fromIt.offset; |
798 | fromIt.offset = 0; |
799 | } |
800 | |
801 | // Remove count items belonging to the move group from the list. |
802 | Range movedFlags; |
803 | for (int moveId = m_moveId; count > 0;) { |
804 | if (fromIt != moveGroup) { |
805 | // Skip ranges not containing items from the move group. |
806 | fromIt.incrementIndexes(difference: fromIt->count); |
807 | *fromIt = fromIt->next; |
808 | continue; |
809 | } |
810 | int difference = qMin(a: count, b: fromIt->count); |
811 | |
812 | // Create a new static range containing the moved items from an existing range. |
813 | new Range( |
814 | &movedFlags, |
815 | fromIt->list, |
816 | fromIt->index, |
817 | difference, |
818 | fromIt->flags & ~(PrependFlag | AppendFlag)); |
819 | // Remove moved items from the count, the existing range, and a remove notification. |
820 | if (removes) |
821 | removes->append(t: Remove(fromIt, difference, fromIt->flags, ++moveId)); |
822 | count -= difference; |
823 | fromIt->count -= difference; |
824 | |
825 | // If the existing range contains the prepend flag replace the removed items with |
826 | // a placeholder range for new items inserted into the source model. |
827 | int removeIndex = fromIt->index; |
828 | if (fromIt->prepend() |
829 | && fromIt->previous != &m_ranges |
830 | && fromIt->previous->flags == PrependFlag |
831 | && fromIt->previous->list == fromIt->list |
832 | && fromIt->previous->end() == fromIt->index) { |
833 | // Grow the previous range instead of creating a new one if possible. |
834 | fromIt->previous->count += difference; |
835 | } else if (fromIt->prepend()) { |
836 | *fromIt = insert(before: *fromIt, list: fromIt->list, index: removeIndex, count: difference, flags: PrependFlag)->next; |
837 | } |
838 | fromIt->index += difference; |
839 | |
840 | if (fromIt->count == 0) { |
841 | // If the existing range has no items remaining; remove it from the list. |
842 | if (fromIt->append()) |
843 | fromIt->previous->flags |= AppendFlag; |
844 | *fromIt = erase(range: *fromIt); |
845 | |
846 | // If the ranges before and after the removed range can be joined, do so. |
847 | if (*fromIt != m_ranges.next && fromIt->flags == PrependFlag |
848 | && fromIt->previous != &m_ranges |
849 | && fromIt->previous->flags == PrependFlag |
850 | && fromIt->previous->list == fromIt->list |
851 | && fromIt->previous->end() == fromIt->index) { |
852 | fromIt.incrementIndexes(difference: fromIt->count); |
853 | fromIt->previous->count += fromIt->count; |
854 | *fromIt = erase(range: *fromIt); |
855 | } |
856 | } else if (count > 0) { |
857 | *fromIt = fromIt->next; |
858 | } |
859 | } |
860 | |
861 | // Try and join the range following the removed items to the range preceding it. |
862 | if (*fromIt != m_ranges.next |
863 | && *fromIt != &m_ranges |
864 | && fromIt->previous->list == fromIt->list |
865 | && (!fromIt->list || fromIt->previous->end() == fromIt->index) |
866 | && fromIt->previous->flags == (fromIt->flags & ~AppendFlag)) { |
867 | if (fromIt == fromIt.group) |
868 | fromIt.offset = fromIt->previous->count; |
869 | fromIt.offset = fromIt->previous->count; |
870 | fromIt->previous->count += fromIt->count; |
871 | fromIt->previous->flags = fromIt->flags; |
872 | *fromIt = erase(range: *fromIt)->previous; |
873 | } |
874 | |
875 | // Find the destination position of the move. |
876 | insert_iterator toIt = fromIt; |
877 | toIt.setGroup(toGroup); |
878 | |
879 | const int difference = to - toIt.index[toGroup]; |
880 | toIt += difference; |
881 | |
882 | // If the insert position is part way through a range; split it and move the iterator to the |
883 | // start of the second range. |
884 | if (toIt.offset > 0) { |
885 | *toIt = insert(before: *toIt, list: toIt->list, index: toIt->index, count: toIt.offset, flags: toIt->flags & ~AppendFlag)->next; |
886 | toIt->index += toIt.offset; |
887 | toIt->count -= toIt.offset; |
888 | toIt.offset = 0; |
889 | } |
890 | |
891 | // Insert the moved ranges before the insert iterator, growing the previous range if that |
892 | // is an option. |
893 | for (Range *range = movedFlags.previous; range != &movedFlags; range = range->previous) { |
894 | if (*toIt != &m_ranges |
895 | && range->list == toIt->list |
896 | && (!range->list || range->end() == toIt->index) |
897 | && range->flags == (toIt->flags & ~AppendFlag)) { |
898 | toIt->index -= range->count; |
899 | toIt->count += range->count; |
900 | } else { |
901 | *toIt = insert(before: *toIt, list: range->list, index: range->index, count: range->count, flags: range->flags); |
902 | } |
903 | } |
904 | |
905 | // Try and join the range after the inserted ranges to the last range inserted. |
906 | if (*toIt != m_ranges.next |
907 | && toIt->previous->list == toIt->list |
908 | && (!toIt->list || (toIt->previous->end() == toIt->index && toIt->previous->flags == (toIt->flags & ~AppendFlag)))) { |
909 | toIt.offset = toIt->previous->count; |
910 | toIt->previous->count += toIt->count; |
911 | toIt->previous->flags = toIt->flags; |
912 | *toIt = erase(range: *toIt)->previous; |
913 | } |
914 | // Create insert notification for the ranges moved. |
915 | Insert insert(toIt, 0, 0, 0); |
916 | for (Range *next, *range = movedFlags.next; range != &movedFlags; range = next) { |
917 | insert.count = range->count; |
918 | insert.flags = range->flags; |
919 | if (inserts) { |
920 | insert.moveId = ++m_moveId; |
921 | inserts->append(t: insert); |
922 | } |
923 | for (int i = 0; i < m_groupCount; ++i) { |
924 | if (insert.inGroup(group: i)) |
925 | insert.index[i] += range->count; |
926 | } |
927 | |
928 | next = range->next; |
929 | delete range; |
930 | } |
931 | |
932 | m_cacheIt = toIt; |
933 | |
934 | QT_QML_VERIFY_LISTCOMPOSITOR |
935 | } |
936 | |
937 | /*! |
938 | Clears the contents of a compositor. |
939 | */ |
940 | |
941 | void QQmlListCompositor::clear() |
942 | { |
943 | QT_QML_TRACE_LISTCOMPOSITOR("" ) |
944 | for (Range *range = m_ranges.next; range != &m_ranges; range = erase(range)) {} |
945 | m_end = iterator(m_ranges.next, 0, Default, m_groupCount); |
946 | m_cacheIt = m_end; |
947 | } |
948 | |
949 | void QQmlListCompositor::listItemsInserted( |
950 | QVector<Insert> *translatedInsertions, |
951 | void *list, |
952 | const QVector<QQmlChangeSet::Change> &insertions, |
953 | const QVector<MovedFlags> *movedFlags) |
954 | { |
955 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << insertions) |
956 | for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) { |
957 | if (it->list != list || it->flags == CacheFlag) { |
958 | // Skip ranges that don't reference list. |
959 | it.incrementIndexes(difference: it->count); |
960 | continue; |
961 | } else if (it->flags & MovedFlag) { |
962 | // Skip ranges that were already moved in listItemsRemoved. |
963 | it->flags &= ~MovedFlag; |
964 | it.incrementIndexes(difference: it->count); |
965 | continue; |
966 | } |
967 | for (const QQmlChangeSet::Change &insertion : insertions) { |
968 | int offset = insertion.index - it->index; |
969 | if ((offset > 0 && offset < it->count) |
970 | || (offset == 0 && it->prepend()) |
971 | || (offset == it->count && it->append())) { |
972 | // The insert index is within the current range. |
973 | if (it->prepend()) { |
974 | // The range has the prepend flag set so we insert new items into the range. |
975 | uint flags = m_defaultFlags; |
976 | if (insertion.isMove()) { |
977 | // If the insert was part of a move replace the default flags with |
978 | // the flags from the source range. |
979 | for (QVector<MovedFlags>::const_iterator move = movedFlags->begin(); |
980 | move != movedFlags->end(); |
981 | ++move) { |
982 | if (move->moveId == insertion.moveId) { |
983 | flags = move->flags; |
984 | break; |
985 | } |
986 | } |
987 | } |
988 | if (flags & ~(AppendFlag | PrependFlag)) { |
989 | // If any items are added to groups append an insert notification. |
990 | Insert translatedInsert(it, insertion.count, flags, insertion.moveId); |
991 | for (int i = 0; i < m_groupCount; ++i) { |
992 | if (it->inGroup(group: i)) |
993 | translatedInsert.index[i] += offset; |
994 | } |
995 | translatedInsertions->append(t: translatedInsert); |
996 | } |
997 | if ((it->flags & ~AppendFlag) == flags) { |
998 | // Accumulate items on the current range it its flags are the same as |
999 | // the insert flags. |
1000 | it->count += insertion.count; |
1001 | } else if (offset == 0 |
1002 | && it->previous != &m_ranges |
1003 | && it->previous->list == list |
1004 | && it->previous->end() == insertion.index |
1005 | && it->previous->flags == flags) { |
1006 | // Attempt to append to the previous range if the insert position is at |
1007 | // the start of the current range. |
1008 | it->previous->count += insertion.count; |
1009 | it->index += insertion.count; |
1010 | it.incrementIndexes(difference: insertion.count); |
1011 | } else { |
1012 | if (offset > 0) { |
1013 | // Divide the current range at the insert position. |
1014 | it.incrementIndexes(difference: offset); |
1015 | *it = insert(before: *it, list: it->list, index: it->index, count: offset, flags: it->flags & ~AppendFlag)->next; |
1016 | } |
1017 | // Insert a new range, and increment the start index of the current range. |
1018 | *it = insert(before: *it, list: it->list, index: insertion.index, count: insertion.count, flags)->next; |
1019 | it.incrementIndexes(difference: insertion.count, flags); |
1020 | it->index += offset + insertion.count; |
1021 | it->count -= offset; |
1022 | } |
1023 | m_end.incrementIndexes(difference: insertion.count, flags); |
1024 | } else { |
1025 | // The range doesn't have the prepend flag set so split the range into parts; |
1026 | // one before the insert position and one after the last inserted item. |
1027 | if (offset > 0) { |
1028 | *it = insert(before: *it, list: it->list, index: it->index, count: offset, flags: it->flags)->next; |
1029 | it->index += offset; |
1030 | it->count -= offset; |
1031 | } |
1032 | it->index += insertion.count; |
1033 | } |
1034 | } else if (offset <= 0) { |
1035 | // The insert position was before the current range so increment the start index. |
1036 | it->index += insertion.count; |
1037 | } |
1038 | } |
1039 | it.incrementIndexes(difference: it->count); |
1040 | } |
1041 | m_cacheIt = m_end; |
1042 | QT_QML_VERIFY_LISTCOMPOSITOR |
1043 | } |
1044 | |
1045 | /*! |
1046 | Updates the contents of a compositor when \a count items are inserted into a \a list at |
1047 | \a index. |
1048 | |
1049 | This corrects the indexes of each range for that list in the compositor, splitting the range |
1050 | in two if the insert index is in the middle of that range. If a range at the insert position |
1051 | has the Prepend flag set then a new range will be inserted at that position with the groups |
1052 | specified in defaultGroups(). If the insert index corresponds to the end of a range with |
1053 | the Append flag set a new range will be inserted before the end of the append range. |
1054 | |
1055 | The \a translatedInsertions list is populated with insert notifications for affected |
1056 | groups. |
1057 | */ |
1058 | |
1059 | void QQmlListCompositor::listItemsInserted( |
1060 | void *list, int index, int count, QVector<Insert> *translatedInsertions) |
1061 | { |
1062 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count) |
1063 | Q_ASSERT(count > 0); |
1064 | |
1065 | QVector<QQmlChangeSet::Change> insertions; |
1066 | insertions.append(t: QQmlChangeSet::Change(index, count)); |
1067 | |
1068 | listItemsInserted(translatedInsertions, list, insertions); |
1069 | } |
1070 | |
1071 | void QQmlListCompositor::listItemsRemoved( |
1072 | QVector<Remove> *translatedRemovals, |
1073 | void *list, |
1074 | QVector<QQmlChangeSet::Change> *removals, |
1075 | QVector<QQmlChangeSet::Change> *insertions, |
1076 | QVector<MovedFlags> *movedFlags) |
1077 | { |
1078 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << *removals) |
1079 | |
1080 | for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) { |
1081 | if (it->list != list || it->flags == CacheFlag) { |
1082 | // Skip ranges that don't reference list. |
1083 | it.incrementIndexes(difference: it->count); |
1084 | continue; |
1085 | } |
1086 | bool removed = false; |
1087 | for (QVector<QQmlChangeSet::Change>::iterator removal = removals->begin(); |
1088 | !removed && removal != removals->end(); |
1089 | ++removal) { |
1090 | int relativeIndex = removal->index - it->index; |
1091 | int itemsRemoved = removal->count; |
1092 | if (relativeIndex + removal->count > 0 && relativeIndex < it->count) { |
1093 | // If the current range intersects the remove; remove the intersecting items. |
1094 | const int offset = qMax(a: 0, b: relativeIndex); |
1095 | int removeCount = qMin(a: it->count, b: relativeIndex + removal->count) - offset; |
1096 | it->count -= removeCount; |
1097 | int removeFlags = it->flags & m_removeFlags; |
1098 | Remove translatedRemoval(it, removeCount, it->flags); |
1099 | for (int i = 0; i < m_groupCount; ++i) { |
1100 | if (it->inGroup(group: i)) |
1101 | translatedRemoval.index[i] += offset; |
1102 | } |
1103 | if (removal->isMove()) { |
1104 | // If the removal was part of a move find the corresponding insert. |
1105 | QVector<QQmlChangeSet::Change>::iterator insertion = insertions->begin(); |
1106 | for (; insertion != insertions->end() && insertion->moveId != removal->moveId; |
1107 | ++insertion) {} |
1108 | Q_ASSERT(insertion != insertions->end()); |
1109 | Q_ASSERT(insertion->count == removal->count); |
1110 | |
1111 | if (relativeIndex < 0) { |
1112 | // If the remove started before the current range, split it and the |
1113 | // corresponding insert so we're only working with intersecting part. |
1114 | int splitMoveId = ++m_moveId; |
1115 | removal = removals->insert(before: removal, t: QQmlChangeSet::Change( |
1116 | removal->index, -relativeIndex, splitMoveId)); |
1117 | ++removal; |
1118 | removal->count -= -relativeIndex; |
1119 | insertion = insertions->insert(before: insertion, t: QQmlChangeSet::Change( |
1120 | insertion->index, -relativeIndex, splitMoveId)); |
1121 | ++insertion; |
1122 | insertion->index += -relativeIndex; |
1123 | insertion->count -= -relativeIndex; |
1124 | } |
1125 | |
1126 | if (it->prepend()) { |
1127 | // If the current range has the prepend flag preserve its flags to transfer |
1128 | // to its new location. |
1129 | removeFlags |= it->flags & CacheFlag; |
1130 | translatedRemoval.moveId = ++m_moveId; |
1131 | movedFlags->append(t: MovedFlags(m_moveId, it->flags & ~AppendFlag)); |
1132 | |
1133 | if (removeCount < removal->count) { |
1134 | // If the remove doesn't encompass all of the current range, |
1135 | // split it and the corresponding insert. |
1136 | removal = removals->insert(before: removal, t: QQmlChangeSet::Change( |
1137 | removal->index, removeCount, translatedRemoval.moveId)); |
1138 | ++removal; |
1139 | insertion = insertions->insert(before: insertion, t: QQmlChangeSet::Change( |
1140 | insertion->index, removeCount, translatedRemoval.moveId)); |
1141 | ++insertion; |
1142 | |
1143 | removal->count -= removeCount; |
1144 | insertion->index += removeCount; |
1145 | insertion->count -= removeCount; |
1146 | } else { |
1147 | // If there's no need to split the move simply replace its moveId |
1148 | // with that of the translated move. |
1149 | removal->moveId = translatedRemoval.moveId; |
1150 | insertion->moveId = translatedRemoval.moveId; |
1151 | } |
1152 | } else { |
1153 | // If the current range doesn't have prepend flags then insert a new range |
1154 | // with list indexes from the corresponding insert location. The MoveFlag |
1155 | // is to notify listItemsInserted that it can skip evaluation of that range. |
1156 | if (offset > 0) { |
1157 | *it = insert(before: *it, list: it->list, index: it->index, count: offset, flags: it->flags & ~AppendFlag)->next; |
1158 | it->index += offset; |
1159 | it->count -= offset; |
1160 | it.incrementIndexes(difference: offset); |
1161 | } |
1162 | if (it->previous != &m_ranges |
1163 | && it->previous->list == it->list |
1164 | && it->end() == insertion->index |
1165 | && it->previous->flags == (it->flags | MovedFlag)) { |
1166 | it->previous->count += removeCount; |
1167 | } else { |
1168 | *it = insert(before: *it, list: it->list, index: insertion->index, count: removeCount, flags: it->flags | MovedFlag)->next; |
1169 | } |
1170 | // Clear the changed flags as the item hasn't been removed. |
1171 | translatedRemoval.flags = 0; |
1172 | removeFlags = 0; |
1173 | } |
1174 | } else if (it->inCache()) { |
1175 | // If not moving and the current range has the cache flag, insert a new range |
1176 | // with just the cache flag set to retain caching information for the removed |
1177 | // range. |
1178 | if (offset > 0) { |
1179 | *it = insert(before: *it, list: it->list, index: it->index, count: offset, flags: it->flags & ~AppendFlag)->next; |
1180 | it->index += offset; |
1181 | it->count -= offset; |
1182 | it.incrementIndexes(difference: offset); |
1183 | } |
1184 | if (it->previous != &m_ranges |
1185 | && it->previous->list == it->list |
1186 | && it->previous->flags == CacheFlag) { |
1187 | it->previous->count += removeCount; |
1188 | } else { |
1189 | *it = insert(before: *it, list: it->list, index: -1, count: removeCount, flags: CacheFlag)->next; |
1190 | } |
1191 | it.index[Cache] += removeCount; |
1192 | } |
1193 | if (removeFlags & GroupMask) |
1194 | translatedRemovals->append(t: translatedRemoval); |
1195 | m_end.decrementIndexes(difference: removeCount, flags: removeFlags); |
1196 | if (it->count == 0 && !it->append()) { |
1197 | // Erase empty non-append ranges. |
1198 | *it = erase(range: *it)->previous; |
1199 | removed = true; |
1200 | } else if (relativeIndex <= 0) { |
1201 | // If the remove started before the current range move the start index of |
1202 | // the range to the remove index. |
1203 | it->index = removal->index; |
1204 | } |
1205 | } else if (relativeIndex < 0) { |
1206 | // If the remove was before the current range decrement the start index by the |
1207 | // number of items removed. |
1208 | it->index -= itemsRemoved; |
1209 | |
1210 | if (it->previous != &m_ranges |
1211 | && it->previous->list == it->list |
1212 | && it->previous->end() == it->index |
1213 | && it->previous->flags == (it->flags & ~AppendFlag)) { |
1214 | // Compress ranges made continuous by the removal of separating ranges. |
1215 | it.decrementIndexes(difference: it->previous->count); |
1216 | it->previous->count += it->count; |
1217 | it->previous->flags = it->flags; |
1218 | *it = erase(range: *it)->previous; |
1219 | } |
1220 | } |
1221 | } |
1222 | if (it->flags == CacheFlag && it->next->flags == CacheFlag && it->next->list == it->list) { |
1223 | // Compress consecutive cache only ranges. |
1224 | it.index[Cache] += it->next->count; |
1225 | it->count += it->next->count; |
1226 | erase(range: it->next); |
1227 | } else if (!removed) { |
1228 | it.incrementIndexes(difference: it->count); |
1229 | } |
1230 | } |
1231 | m_cacheIt = m_end; |
1232 | QT_QML_VERIFY_LISTCOMPOSITOR |
1233 | } |
1234 | |
1235 | |
1236 | /*! |
1237 | Updates the contents of a compositor when \a count items are removed from a \a list at |
1238 | \a index. |
1239 | |
1240 | Ranges that intersect the specified range are removed from the compositor and the indexes of |
1241 | ranges after index + count are updated. |
1242 | |
1243 | The \a translatedRemovals list is populated with remove notifications for the affected |
1244 | groups. |
1245 | */ |
1246 | |
1247 | |
1248 | void QQmlListCompositor::listItemsRemoved( |
1249 | void *list, int index, int count, QVector<Remove> *translatedRemovals) |
1250 | { |
1251 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count) |
1252 | Q_ASSERT(count >= 0); |
1253 | |
1254 | QVector<QQmlChangeSet::Change> removals; |
1255 | removals.append(t: QQmlChangeSet::Change(index, count)); |
1256 | listItemsRemoved(translatedRemovals, list, removals: &removals, insertions: nullptr, movedFlags: nullptr); |
1257 | } |
1258 | |
1259 | /*! |
1260 | Updates the contents of a compositor when \a count items are removed from a \a list at |
1261 | \a index. |
1262 | |
1263 | Ranges that intersect the specified range are removed from the compositor and the indexes of |
1264 | ranges after index + count are updated. |
1265 | |
1266 | The \a translatedRemovals and translatedInserts lists are populated with move |
1267 | notifications for the affected groups. |
1268 | */ |
1269 | |
1270 | void QQmlListCompositor::listItemsMoved( |
1271 | void *list, |
1272 | int from, |
1273 | int to, |
1274 | int count, |
1275 | QVector<Remove> *translatedRemovals, |
1276 | QVector<Insert> *translatedInsertions) |
1277 | { |
1278 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << from << to << count) |
1279 | Q_ASSERT(count >= 0); |
1280 | |
1281 | QVector<QQmlChangeSet::Change> removals; |
1282 | QVector<QQmlChangeSet::Change> insertions; |
1283 | QVector<MovedFlags> movedFlags; |
1284 | removals.append(t: QQmlChangeSet::Change(from, count, 0)); |
1285 | insertions.append(t: QQmlChangeSet::Change(to, count, 0)); |
1286 | |
1287 | listItemsRemoved(translatedRemovals, list, removals: &removals, insertions: &insertions, movedFlags: &movedFlags); |
1288 | listItemsInserted(translatedInsertions, list, insertions, movedFlags: &movedFlags); |
1289 | } |
1290 | |
1291 | void QQmlListCompositor::listItemsChanged( |
1292 | QVector<Change> *translatedChanges, |
1293 | void *list, |
1294 | const QVector<QQmlChangeSet::Change> &changes) |
1295 | { |
1296 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << changes) |
1297 | for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) { |
1298 | if (it->list != list || it->flags == CacheFlag) { |
1299 | it.incrementIndexes(difference: it->count); |
1300 | continue; |
1301 | } else if (!it->inGroup()) { |
1302 | continue; |
1303 | } |
1304 | for (const QQmlChangeSet::Change &change : changes) { |
1305 | const int offset = change.index - it->index; |
1306 | if (offset + change.count > 0 && offset < it->count) { |
1307 | const int changeOffset = qMax(a: 0, b: offset); |
1308 | const int changeCount = qMin(a: it->count, b: offset + change.count) - changeOffset; |
1309 | |
1310 | Change translatedChange(it, changeCount, it->flags); |
1311 | for (int i = 0; i < m_groupCount; ++i) { |
1312 | if (it->inGroup(group: i)) |
1313 | translatedChange.index[i] += changeOffset; |
1314 | } |
1315 | translatedChanges->append(t: translatedChange); |
1316 | } |
1317 | } |
1318 | it.incrementIndexes(difference: it->count); |
1319 | } |
1320 | } |
1321 | |
1322 | |
1323 | /*! |
1324 | Translates the positions of \a count changed items at \a index in a \a list. |
1325 | |
1326 | The \a translatedChanges list is populated with change notifications for the |
1327 | affected groups. |
1328 | */ |
1329 | |
1330 | void QQmlListCompositor::listItemsChanged( |
1331 | void *list, int index, int count, QVector<Change> *translatedChanges) |
1332 | { |
1333 | QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count) |
1334 | Q_ASSERT(count >= 0); |
1335 | QVector<QQmlChangeSet::Change> changes; |
1336 | changes.append(t: QQmlChangeSet::Change(index, count)); |
1337 | listItemsChanged(translatedChanges, list, changes); |
1338 | } |
1339 | |
1340 | void QQmlListCompositor::transition( |
1341 | Group from, |
1342 | Group to, |
1343 | QVector<QQmlChangeSet::Change> *removes, |
1344 | QVector<QQmlChangeSet::Change> *inserts) |
1345 | { |
1346 | int removeCount = 0; |
1347 | for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) { |
1348 | if (it == from && it != to) { |
1349 | removes->append(t: QQmlChangeSet::Change(it.index[from]- removeCount, it->count)); |
1350 | removeCount += it->count; |
1351 | } else if (it != from && it == to) { |
1352 | inserts->append(t: QQmlChangeSet::Change(it.index[to], it->count)); |
1353 | } |
1354 | it.incrementIndexes(difference: it->count); |
1355 | } |
1356 | } |
1357 | |
1358 | /*! |
1359 | \internal |
1360 | Writes the name of \a group to \a debug. |
1361 | */ |
1362 | |
1363 | QDebug operator <<(QDebug debug, const QQmlListCompositor::Group &group) |
1364 | { |
1365 | switch (group) { |
1366 | case QQmlListCompositor::Cache: return debug << "Cache" ; |
1367 | case QQmlListCompositor::Default: return debug << "Default" ; |
1368 | default: return (debug.nospace() << "Group" << int(group)).space(); |
1369 | } |
1370 | |
1371 | } |
1372 | |
1373 | /*! |
1374 | \internal |
1375 | Writes the contents of \a range to \a debug. |
1376 | */ |
1377 | |
1378 | QDebug operator <<(QDebug debug, const QQmlListCompositor::Range &range) |
1379 | { |
1380 | (debug.nospace() |
1381 | << "Range(" |
1382 | << range.list) << ' ' |
1383 | << range.index << ' ' |
1384 | << range.count << ' ' |
1385 | << (range.isUnresolved() ? 'U' : '0') |
1386 | << (range.append() ? 'A' : '0') |
1387 | << (range.prepend() ? 'P' : '0'); |
1388 | for (int i = QQmlListCompositor::MaximumGroupCount - 1; i >= 2; --i) |
1389 | debug << (range.inGroup(group: i) ? '1' : '0'); |
1390 | return (debug |
1391 | << (range.inGroup(group: QQmlListCompositor::Default) ? 'D' : '0') |
1392 | << (range.inGroup(group: QQmlListCompositor::Cache) ? 'C' : '0')); |
1393 | } |
1394 | |
1395 | static void qt_print_indexes(QDebug &debug, int count, const int *indexes) |
1396 | { |
1397 | for (int i = count - 1; i >= 0; --i) |
1398 | debug << indexes[i]; |
1399 | } |
1400 | |
1401 | /*! |
1402 | \internal |
1403 | Writes the contents of \a it to \a debug. |
1404 | */ |
1405 | |
1406 | QDebug operator <<(QDebug debug, const QQmlListCompositor::iterator &it) |
1407 | { |
1408 | (debug.nospace() << "iterator(" << it.group).space() << "offset:" << it.offset; |
1409 | qt_print_indexes(debug, count: it.groupCount, indexes: it.index); |
1410 | return ((debug << **it).nospace() << ')').space(); |
1411 | } |
1412 | |
1413 | static QDebug qt_print_change(QDebug debug, const char *name, const QQmlListCompositor::Change &change) |
1414 | { |
1415 | debug.nospace() << name << '(' << change.moveId << ' ' << change.count << ' '; |
1416 | for (int i = QQmlListCompositor::MaximumGroupCount - 1; i >= 2; --i) |
1417 | debug << (change.inGroup(group: i) ? '1' : '0'); |
1418 | debug << (change.inGroup(group: QQmlListCompositor::Default) ? 'D' : '0') |
1419 | << (change.inGroup(group: QQmlListCompositor::Cache) ? 'C' : '0'); |
1420 | int i = QQmlListCompositor::MaximumGroupCount - 1; |
1421 | for (; i >= 0 && !change.inGroup(group: i); --i) {} |
1422 | for (; i >= 0; --i) |
1423 | debug << ' ' << change.index[i]; |
1424 | return (debug << ')').maybeSpace(); |
1425 | } |
1426 | |
1427 | /*! |
1428 | \internal |
1429 | Writes the contents of \a change to \a debug. |
1430 | */ |
1431 | |
1432 | QDebug operator <<(QDebug debug, const QQmlListCompositor::Change &change) |
1433 | { |
1434 | return qt_print_change(debug, name: "Change" , change); |
1435 | } |
1436 | |
1437 | /*! |
1438 | \internal |
1439 | Writes the contents of \a remove to \a debug. |
1440 | */ |
1441 | |
1442 | QDebug operator <<(QDebug debug, const QQmlListCompositor::Remove &remove) |
1443 | { |
1444 | return qt_print_change(debug, name: "Remove" , change: remove); |
1445 | } |
1446 | |
1447 | /*! |
1448 | \internal |
1449 | Writes the contents of \a insert to \a debug. |
1450 | */ |
1451 | |
1452 | QDebug operator <<(QDebug debug, const QQmlListCompositor::Insert &insert) |
1453 | { |
1454 | return qt_print_change(debug, name: "Insert" , change: insert); |
1455 | } |
1456 | |
1457 | /*! |
1458 | \internal |
1459 | Writes the contents of \a list to \a debug. |
1460 | */ |
1461 | |
1462 | QDebug operator <<(QDebug debug, const QQmlListCompositor &list) |
1463 | { |
1464 | int indexes[QQmlListCompositor::MaximumGroupCount]; |
1465 | for (int i = 0; i < QQmlListCompositor::MaximumGroupCount; ++i) |
1466 | indexes[i] = 0; |
1467 | debug.nospace() << "QQmlListCompositor(" ; |
1468 | qt_print_indexes(debug, count: list.m_groupCount, indexes: list.m_end.index); |
1469 | for (QQmlListCompositor::Range *range = list.m_ranges.next; range != &list.m_ranges; range = range->next) { |
1470 | (debug << '\n').space(); |
1471 | qt_print_indexes(debug, count: list.m_groupCount, indexes); |
1472 | debug << ' ' << *range; |
1473 | |
1474 | for (int i = 0; i < list.m_groupCount; ++i) { |
1475 | if (range->inGroup(group: i)) |
1476 | indexes[i] += range->count; |
1477 | } |
1478 | } |
1479 | return (debug << ')').maybeSpace(); |
1480 | } |
1481 | |
1482 | QT_END_NAMESPACE |
1483 | |