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

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