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

source code of qtbase/src/corelib/kernel/qiterable.h