1/****************************************************************************
2**
3** Copyright (C) 2020 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore 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#ifndef QITERABLE_H
41#define QITERABLE_H
42
43#include <QtCore/qglobal.h>
44#include <QtCore/qtypeinfo.h>
45#include <QtCore/qmetacontainer.h>
46#include <QtCore/qtaggedpointer.h>
47
48QT_BEGIN_NAMESPACE
49
50namespace QtPrivate {
51 template<typename Type, typename Storage = Type>
52 class QConstPreservingPointer
53 {
54 enum Tag : bool { Const, Mutable };
55 QTaggedPointer<Storage, Tag> m_pointer;
56
57 public:
58 QConstPreservingPointer(std::nullptr_t) : m_pointer(nullptr, Const) {}
59
60 QConstPreservingPointer(const void *pointer, qsizetype alignment)
61 : m_pointer(reinterpret_cast<Storage *>(const_cast<void *>(pointer)), Const)
62 {
63 Q_UNUSED(alignment);
64 Q_ASSERT(alignment > qsizetype(alignof(Storage)));
65 }
66
67 QConstPreservingPointer(void *pointer, qsizetype alignment)
68 : m_pointer(reinterpret_cast<Storage *>(pointer), Mutable)
69 {
70 Q_UNUSED(alignment);
71 Q_ASSERT(alignment > qsizetype(alignof(Storage)));
72 }
73
74 template<typename InputType>
75 QConstPreservingPointer(const InputType *pointer)
76 : m_pointer(reinterpret_cast<Storage *>(const_cast<InputType *>(pointer)), Const)
77 {
78 static_assert(alignof(InputType) >= alignof(Storage));
79 }
80
81 template<typename InputType>
82 QConstPreservingPointer(InputType *pointer)
83 : m_pointer(reinterpret_cast<Storage *>(pointer), Mutable)
84 {
85 static_assert(alignof(InputType) >= alignof(Storage));
86 }
87
88 QConstPreservingPointer() = default;
89
90 const Type *constPointer() const
91 {
92 return reinterpret_cast<const Type *>(m_pointer.data());
93 }
94
95 Type *mutablePointer() const
96 {
97 return m_pointer.tag() == Mutable ? reinterpret_cast<Type *>(m_pointer.data()) : nullptr;
98 }
99 };
100}
101
102template<class Iterator, typename IteratorCategory>
103class QTaggedIterator : public Iterator
104{
105public:
106 using iterator_category = IteratorCategory;
107 QTaggedIterator(Iterator &&it) : Iterator(std::move(it))
108 {
109 const QMetaContainer metaContainer = this->metaContainer();
110 if (std::is_base_of_v<std::random_access_iterator_tag, IteratorCategory>
111 && !metaContainer.hasRandomAccessIterator()) {
112 qFatal("You cannot use this iterator as a random access iterator");
113 this->clearIterator();
114 }
115
116 if (std::is_base_of_v<std::bidirectional_iterator_tag, IteratorCategory>
117 && !metaContainer.hasBidirectionalIterator()) {
118 qFatal("You cannot use this iterator as a bidirectional iterator");
119 this->clearIterator();
120 }
121
122 if (std::is_base_of_v<std::forward_iterator_tag, IteratorCategory>
123 && !metaContainer.hasForwardIterator()) {
124 qFatal("You cannot use this iterator as a forward iterator");
125 this->clearIterator();
126 }
127
128 if (std::is_base_of_v<std::input_iterator_tag, IteratorCategory>
129 && !metaContainer.hasInputIterator()) {
130 qFatal("You cannot use this iterator as an input iterator");
131 this->clearIterator();
132 }
133 }
134
135 bool operator==(const QTaggedIterator &o) const { return Iterator::operator==(o); }
136 bool operator!=(const QTaggedIterator &o) const { return Iterator::operator!=(o); }
137 QTaggedIterator &operator++() { Iterator::operator++(); return *this; }
138 QTaggedIterator operator++(int x) { return QTaggedIterator(Iterator::operator++(x)); };
139 QTaggedIterator &operator--() { Iterator::operator--(); return *this; }
140 QTaggedIterator operator--(int x) { return QTaggedIterator(Iterator::operator--(x)); };
141 QTaggedIterator &operator+=(qsizetype j) { Iterator::operator+=(j); return *this; }
142 QTaggedIterator &operator-=(qsizetype j) { Iterator::operator-=(j); return *this; }
143 QTaggedIterator operator+(qsizetype j) const { return QTaggedIterator(Iterator::operator+(j)); }
144 QTaggedIterator operator-(qsizetype j) const { return QTaggedIterator(Iterator::operator-(j)); }
145 qsizetype operator-(const QTaggedIterator &j) const { return Iterator::operator-(j); }
146
147 bool operator<(const QTaggedIterator &j) { return operator-(j) < 0; }
148 bool operator>=(const QTaggedIterator &j) { return !operator<(j); }
149 bool operator>(const QTaggedIterator &j) { return operator-(j) > 0; }
150 bool operator<=(const QTaggedIterator &j) { return !operator>(j); }
151
152 friend inline QTaggedIterator operator+(qsizetype j, const QTaggedIterator &k) { return k + j; }
153};
154
155template<class Container>
156class QIterable;
157
158template<class Container>
159class QBaseIterator
160{
161private:
162 QtPrivate::QConstPreservingPointer<QIterable<Container>> m_iterable;
163 void *m_iterator = nullptr;
164
165protected:
166 QBaseIterator() = default;
167 QBaseIterator(const QIterable<Container> *iterable, void *iterator)
168 : m_iterable(iterable), m_iterator(iterator)
169 {}
170
171 QBaseIterator(QIterable<Container> *iterable, void *iterator)
172 : m_iterable(iterable), m_iterator(iterator)
173 {}
174
175 QBaseIterator(QBaseIterator &&other)
176 : m_iterable(std::move(other.m_iterable)), m_iterator(std::move(other.m_iterator))
177 {
178 other.m_iterator = nullptr;
179 }
180
181 QBaseIterator(const QBaseIterator &other)
182 : m_iterable(other.m_iterable)
183 {
184 initIterator(other.m_iterator);
185 }
186
187 ~QBaseIterator() { clearIterator(); }
188
189 QBaseIterator &operator=(QBaseIterator &&other)
190 {
191 if (this != &other) {
192 clearIterator();
193 m_iterable = std::move(other.m_iterable);
194 m_iterator = std::move(other.m_iterator);
195 other.m_iterator = nullptr;
196 }
197 return *this;
198 }
199
200 QBaseIterator &operator=(const QBaseIterator &other)
201 {
202 if (this != &other) {
203 clearIterator();
204 m_iterable = other.m_iterable;
205 initIterator(other.m_iterator);
206 }
207 return *this;
208 }
209
210 QIterable<Container> *mutableIterable() const
211 {
212 return m_iterable.mutablePointer();
213 }
214
215 const QIterable<Container> *constIterable() const
216 {
217 return m_iterable.constPointer();
218 }
219
220 void initIterator(const void *copy)
221 {
222 if (!copy)
223 return;
224 if (auto *mutableIt = mutableIterable()) {
225 m_iterator = metaContainer().begin(mutableIt->mutableIterable());
226 metaContainer().copyIterator(m_iterator, copy);
227 } else if (auto *constIt = constIterable()) {
228 m_iterator = metaContainer().constBegin(constIt->constIterable());
229 metaContainer().copyConstIterator(m_iterator, copy);
230 }
231 }
232
233 void clearIterator()
234 {
235 if (!m_iterator)
236 return;
237 if (mutableIterable())
238 metaContainer().destroyIterator(m_iterator);
239 else
240 metaContainer().destroyConstIterator(m_iterator);
241 }
242
243public:
244 void *mutableIterator() { return m_iterator; }
245 const void *constIterator() const { return m_iterator; }
246 Container metaContainer() const { return constIterable()->m_metaContainer; }
247};
248
249template<class Container>
250struct QIterator : public QBaseIterator<Container>
251{
252public:
253 using difference_type = qsizetype;
254
255 explicit QIterator(QIterable<Container> *iterable, void *iterator)
256 : QBaseIterator<Container>(iterable, iterator)
257 {
258 Q_ASSERT(iterable != nullptr);
259 }
260
261 bool operator==(const QIterator &o) const
262 {
263 return this->metaContainer().compareIterator(this->constIterator(), o.constIterator());
264 }
265
266 bool operator!=(const QIterator &o) const
267 {
268 return !this->metaContainer().compareIterator(this->constIterator(), o.constIterator());
269 }
270
271 QIterator &operator++()
272 {
273 this->metaContainer().advanceIterator(this->mutableIterator(), 1);
274 return *this;
275 }
276
277 QIterator operator++(int)
278 {
279 QIterable<Container> *iterable = this->mutableIterable();
280 const Container metaContainer = this->metaContainer();
281 QIterator result(iterable, metaContainer.begin(iterable->mutableIterable()));
282 metaContainer.copyIterator(result.mutableIterator(), this->constIterator());
283 metaContainer.advanceIterator(this->mutableIterator(), 1);
284 return result;
285 }
286
287 QIterator &operator--()
288 {
289 this->metaContainer().advanceIterator(this->mutableIterator(), -1);
290 return *this;
291 }
292
293 QIterator operator--(int)
294 {
295 QIterable<Container> *iterable = this->mutableIterable();
296 const Container metaContainer = this->metaContainer();
297 QIterator result(iterable, metaContainer.begin(iterable->mutableIterable()));
298 metaContainer.copyIterator(result.mutableIterator(), this->constIterator());
299 metaContainer.advanceIterator(this->mutableIterator(), -1);
300 return result;
301 }
302
303 QIterator &operator+=(qsizetype j)
304 {
305 this->metaContainer().advanceIterator(this->mutableIterator(), j);
306 return *this;
307 }
308
309 QIterator &operator-=(qsizetype j)
310 {
311 this->metaContainer().advanceIterator(this->mutableIterator(), -j);
312 return *this;
313 }
314
315 QIterator operator+(qsizetype j) const
316 {
317 QIterable<Container> *iterable = this->mutableIterable();
318 const Container metaContainer = this->metaContainer();
319 QIterator result(iterable, metaContainer.begin(iterable->mutableIterable()));
320 metaContainer.copyIterator(result.mutableIterator(), this->constIterator());
321 metaContainer.advanceIterator(result.mutableIterator(), j);
322 return result;
323 }
324
325 QIterator operator-(qsizetype j) const
326 {
327 QIterable<Container> *iterable = this->mutableIterable();
328 const Container metaContainer = this->metaContainer();
329 QIterator result(iterable, metaContainer.begin(iterable->mutableIterable()));
330 metaContainer.copyIterator(result.mutableIterator(), this->constIterator());
331 metaContainer.advanceIterator(result.mutableIterator(), -j);
332 return result;
333 }
334
335 qsizetype operator-(const QIterator &j) const
336 {
337 return this->metaContainer().diffIterator(this->constIterator(), j.constIterator());
338 }
339
340 friend inline QIterator operator+(qsizetype j, const QIterator &k) { return k + j; }
341};
342
343template<class Container>
344struct QConstIterator : public QBaseIterator<Container>
345{
346public:
347 using difference_type = qsizetype;
348
349 explicit QConstIterator(const QIterable<Container> *iterable, void *iterator)
350 : QBaseIterator<Container>(iterable, iterator)
351 {
352 }
353
354 bool operator==(const QConstIterator &o) const
355 {
356 return this->metaContainer().compareConstIterator(
357 this->constIterator(), o.constIterator());
358 }
359
360 bool operator!=(const QConstIterator &o) const
361 {
362 return !this->metaContainer().compareConstIterator(
363 this->constIterator(), o.constIterator());
364 }
365
366 QConstIterator &operator++()
367 {
368 this->metaContainer().advanceConstIterator(this->mutableIterator(), 1);
369 return *this;
370 }
371
372 QConstIterator operator++(int)
373 {
374 const Container metaContainer = this->metaContainer();
375 QConstIterator result(this->constIterable(), metaContainer.constBegin(
376 this->constIterable()->constIterable()));
377 metaContainer.copyConstIterator(result.mutableIterator(), this->constIterator());
378 metaContainer.advanceConstIterator(this->mutableIterator(), 1);
379 return result;
380 }
381
382 QConstIterator &operator--()
383 {
384 this->metaContainer().advanceConstIterator(this->mutableIterator(), -1);
385 return *this;
386 }
387
388 QConstIterator operator--(int)
389 {
390 const Container metaContainer = this->metaContainer();
391 QConstIterator result(this->constIterable(), metaContainer.constBegin(
392 this->constIterable()->constIterable()));
393 metaContainer.copyConstIterator(result.mutableIterator(), this->constIterator());
394 metaContainer.advanceConstIterator(this->mutableIterator(), -1);
395 return result;
396 }
397
398 QConstIterator &operator+=(qsizetype j)
399 {
400 this->metaContainer().advanceConstIterator(this->mutableIterator(), j);
401 return *this;
402 }
403
404 QConstIterator &operator-=(qsizetype j)
405 {
406 this->metaContainer().advanceConstIterator(this->mutableIterator(), -j);
407 return *this;
408 }
409
410 QConstIterator operator+(qsizetype j) const
411 {
412 const Container metaContainer = this->metaContainer();
413 QConstIterator result(
414 this->constIterable(),
415 metaContainer.constBegin(this->constIterable()->constIterable()));
416 metaContainer.copyConstIterator(result.mutableIterator(), this->constIterator());
417 metaContainer.advanceConstIterator(result.mutableIterator(), j);
418 return result;
419 }
420
421 QConstIterator operator-(qsizetype j) const
422 {
423 const Container metaContainer = this->metaContainer();
424 QConstIterator result(this->constIterable(), metaContainer.constBegin(
425 this->constIterable()->constIterable()));
426 metaContainer.copyConstIterator(result.mutableIterator(), this->constIterator());
427 metaContainer.advanceConstIterator(result.mutableIterator(), -j);
428 return result;
429 }
430
431 qsizetype operator-(const QConstIterator &j) const
432 {
433 return this->metaContainer().diffIterator(this->constIterator(), j.constIterator());
434 }
435
436 friend inline QConstIterator operator+(qsizetype j, const QConstIterator &k)
437 {
438 return k + j;
439 }
440};
441
442template<class Container>
443class QIterable
444{
445 friend class QBaseIterator<Container>;
446
447protected:
448 uint m_revision = 0;
449 QtPrivate::QConstPreservingPointer<void, quint16> m_iterable;
450 Container m_metaContainer;
451
452public:
453 template<class T>
454 QIterable(const Container &metaContainer, const T *p)
455 : m_iterable(p), m_metaContainer(metaContainer)
456 {
457 }
458
459 template<class T>
460 QIterable(const Container &metaContainer, T *p)
461 : m_iterable(p), m_metaContainer(metaContainer)
462 {
463 }
464
465 template<typename Pointer>
466 QIterable(const Container &metaContainer, Pointer iterable)
467 : m_iterable(iterable), m_metaContainer(metaContainer)
468 {
469 }
470
471 QIterable(const Container &metaContainer, qsizetype alignment, const void *p)
472 : m_iterable(p, alignment), m_metaContainer(metaContainer)
473 {
474 }
475
476 QIterable(const Container &metaContainer, qsizetype alignment, void *p)
477 : m_iterable(p, alignment), m_metaContainer(metaContainer)
478 {
479 }
480
481 bool canInputIterate() const
482 {
483 return m_metaContainer.hasInputIterator();
484 }
485
486 bool canForwardIterate() const
487 {
488 return m_metaContainer.hasForwardIterator();
489 }
490
491 bool canReverseIterate() const
492 {
493 return m_metaContainer.hasBidirectionalIterator();
494 }
495
496 bool canRandomAccessIterate() const
497 {
498 return m_metaContainer.hasRandomAccessIterator();
499 }
500
501 const void *constIterable() const { return m_iterable.constPointer(); }
502 void *mutableIterable() { return m_iterable.mutablePointer(); }
503
504 QConstIterator<Container> constBegin() const
505 {
506 return QConstIterator(this, m_metaContainer.constBegin(constIterable()));
507 }
508
509 QConstIterator<Container> constEnd() const
510 {
511 return QConstIterator(this, m_metaContainer.constEnd(constIterable()));
512 }
513
514 QIterator<Container> mutableBegin()
515 {
516 return QIterator(this, m_metaContainer.begin(mutableIterable()));
517 }
518
519 QIterator<Container> mutableEnd()
520 {
521 return QIterator(this, m_metaContainer.end(mutableIterable()));
522 }
523
524 qsizetype size() const
525 {
526 const void *container = constIterable();
527 if (m_metaContainer.hasSize())
528 return m_metaContainer.size(container);
529 if (!m_metaContainer.hasConstIterator())
530 return -1;
531
532 const void *begin = m_metaContainer.constBegin(container);
533 const void *end = m_metaContainer.constEnd(container);
534 const qsizetype size = m_metaContainer.diffConstIterator(end, begin);
535 m_metaContainer.destroyConstIterator(begin);
536 m_metaContainer.destroyConstIterator(end);
537 return size;
538 }
539
540 Container metaContainer() const
541 {
542 return m_metaContainer;
543 };
544};
545
546QT_END_NAMESPACE
547
548#endif // QITERABLE_H
549