1/****************************************************************************
2**
3** Copyright (C) 2014 Klaralvdalens Datakonsult AB (KDAB).
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the Qt3D 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 QT3DCORE_QCIRCULARBUFFER_H
41#define QT3DCORE_QCIRCULARBUFFER_H
42
43//
44// W A R N I N G
45// -------------
46//
47// This file is not part of the Qt API. It exists for the convenience
48// of other Qt classes. This header file may change from version to
49// version without notice, or even be removed.
50//
51// We mean it.
52//
53
54#include <Qt3DCore/qt3dcore_global.h>
55#include <QtCore/QtGlobal>
56#include <QtCore/qlist.h>
57#include <QtCore/qpair.h>
58#include <QtCore/qshareddata.h>
59#include <QtCore/qvector.h>
60
61#include <algorithm>
62#include <iterator>
63#include <limits>
64#include <memory>
65#include <new>
66
67
68#ifdef Q_COMPILER_INITIALIZER_LISTS
69# include <initializer_list>
70#endif
71
72QT_BEGIN_NAMESPACE
73
74namespace Qt3DCore {
75
76class CircularBufferData : public QSharedData
77{
78protected:
79 CircularBufferData()
80 : data(nullptr),
81 capacity(0),
82 size(0),
83 first(-1),
84 last(-1)
85 {}
86
87 ~CircularBufferData()
88 {
89 // Release the raw memory
90 deallocate(p: data);
91 }
92
93 int wraparound(int index) const
94 {
95 index = index < capacity ? index : (index - capacity);
96 Q_ASSERT(index < capacity); // make sure that wrapping around once was enough
97 return index;
98 }
99
100 void *allocate(int count, size_t sizeOfT)
101 { return operator new[](count * sizeOfT); }
102 void deallocate(void *p)
103 { operator delete[](p); }
104
105 void *data; // Array of the actual data
106public:
107 int capacity; // Size of the m_data array
108 int size; // Number of elements of m_data actually used
109 int first; // Index in m_data of the first element of the circular buffer
110 int last; // Index in m_data of the last element of the circular buffer
111};
112
113template <typename T>
114class TypedCircularBufferData : public CircularBufferData
115{
116 template <typename InputIterator>
117 explicit TypedCircularBufferData(InputIterator f, InputIterator l, std::input_iterator_tag) Q_DECL_EQ_DELETE;
118public:
119 TypedCircularBufferData() : CircularBufferData() {}
120 template <typename ForwardIterator>
121 explicit TypedCircularBufferData(ForwardIterator f, ForwardIterator l, std::forward_iterator_tag)
122 {
123 const int n = int(std::distance(f, l));
124 CircularBufferData::data = allocate(count: n);
125 std::uninitialized_copy(f, l, data());
126 first = 0;
127 last = n - 1;
128 size = capacity = n;
129 }
130 ~TypedCircularBufferData()
131 {
132 if (QTypeInfo<T>::isComplex && size != 0) {
133 // The type is complex so we manually call the destructor for each item
134 // since we used the placement new operator to instantiate them
135 if (first <= last) {
136 // Destroy items from first to last
137 T *b = data() + first;
138 T *i = b + size;
139 while (i-- != b)
140 i->~T();
141 } else {
142 // Destroy items at end of data array
143 T *b = data() + first;
144 T *i = data() + capacity;
145 while (i-- != b)
146 i->~T();
147
148 // Destroy items at beginning of data array
149 b = data();
150 i = b + last;
151 while (i-- != b)
152 i->~T();
153 }
154 }
155
156 }
157
158 using CircularBufferData::wraparound;
159 T *allocate(int count) { return static_cast<T*>(CircularBufferData::allocate(count, sizeOfT: sizeof(T))); }
160 using CircularBufferData::deallocate;
161 T *data() const { return static_cast<T*>(CircularBufferData::data); }
162 void setData(T *newdata) { CircularBufferData::data = static_cast<void*>(newdata); }
163};
164
165template <typename T>
166class QCircularBuffer
167{
168 typedef TypedCircularBufferData<T> Data;
169public:
170 typedef QPair<T*,int> array_range;
171 typedef QPair<const T*,int> const_array_range;
172 typedef array_range ArrayRange;
173 typedef const_array_range ConstArrayRange;
174
175 QCircularBuffer()
176 : d(new Data())
177 {}
178
179 explicit QCircularBuffer(int amount);
180 explicit QCircularBuffer(int amount, const T &val);
181 explicit QCircularBuffer(int amount, int initialSize, const T &value);
182#ifdef Q_COMPILER_INITIALIZER_LISTS
183 QCircularBuffer(std::initializer_list<T> list)
184 : d(new Data(list.begin(), list.end(), std::random_access_iterator_tag()))
185 {}
186#endif
187 template <typename ForwardIterator>
188 explicit QCircularBuffer(ForwardIterator f, ForwardIterator l)
189 : d(new Data(f, l, typename std::iterator_traits<ForwardIterator>::iterator_category()))
190 {}
191
192 QCircularBuffer(const QCircularBuffer<T> &other)
193 : d(other.d)
194 {}
195
196 void swap(QCircularBuffer &other) { d.swap(other.d); }
197
198 QCircularBuffer<T> &operator = (const QCircularBuffer<T> &other)
199 {
200 d = other.d;
201 return *this;
202 }
203
204 ~QCircularBuffer() {}
205
206 class iterator
207 {
208 public:
209 typedef std::random_access_iterator_tag iterator_category;
210 typedef ptrdiff_t difference_type;
211 typedef T value_type;
212 typedef T *pointer;
213 typedef T &reference;
214
215 Q_DECL_CONSTEXPR iterator() : buffer(nullptr), index(-1) {}
216 iterator(QCircularBuffer<T> *buf, int idx)
217 : buffer(buf), index(idx)
218 {}
219
220 T &operator*() const { return (*buffer)[ index ]; }
221 T *operator->() const { return &(*buffer)[index]; }
222 T &operator[](int j) const { return (*buffer)[ index + j ]; }
223
224 bool operator==(const iterator &other) const
225 {
226 return (buffer == other.buffer && index == other.index);
227 }
228
229 bool operator!=(const iterator &other) const
230 {
231 return (buffer != other.buffer || index != other.index);
232 }
233
234 bool operator<(const iterator &other) const
235 {
236 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::iterator::operator<", "iterators use different buffers");
237 return index < other.index;
238 }
239
240 bool operator<=(const iterator &other) const
241 {
242 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::iterator::operator<=", "iterators use different buffers");
243 return index <= other.index;
244 }
245
246 bool operator>(const iterator &other) const
247 {
248 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::iterator::operator>", "iterators use different buffers");
249 return index > other.index;
250 }
251
252 bool operator>=(const iterator &other) const
253 {
254 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::iterator::operator>=", "iterators use different buffers");
255 return index >= other.index;
256 }
257
258 iterator &operator++() { ++index; return *this; }
259 iterator operator++(int)
260 {
261 iterator ans = *this;
262 ++index;
263 return ans;
264 }
265
266 iterator &operator--() { --index; return *this; }
267 iterator operator--(int)
268 {
269 iterator ans = *this;
270 --index;
271 return ans;
272 }
273
274 iterator &operator+=(int j) { index += j; return *this; }
275 iterator &operator-=(int j) { index -= j; return *this; }
276 iterator operator+(int j) const { return iterator(buffer, index + j); }
277 iterator operator-(int j) const { return iterator(buffer, index - j); }
278 int operator-(iterator other) const
279 {
280 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::iterator::operator-", "iterators use different buffers");
281 return index - other.index;
282 }
283
284 private:
285 QCircularBuffer<T> *buffer;
286 int index;
287 friend class QCircularBuffer;
288 };
289 friend class iterator;
290
291 class const_iterator
292 {
293 public:
294 typedef std::random_access_iterator_tag iterator_category;
295 typedef ptrdiff_t difference_type;
296 typedef T value_type;
297 typedef const T *pointer;
298 typedef const T &reference;
299
300 Q_DECL_CONSTEXPR const_iterator() : buffer(nullptr), index(-1) {}
301 const_iterator(const QCircularBuffer<T> *buff, int idx)
302 : buffer(buff), index(idx)
303 {}
304 const_iterator(const iterator &other)
305 : buffer(other.buffer), index(other.index)
306 {}
307
308 const T &operator*() const { return buffer->at(index); }
309 const T *operator->() const { return &buffer->at(index); }
310 const T &operator[](int j) const { return buffer->at(index + j); }
311
312 bool operator==(const const_iterator &other) const
313 {
314 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator==", "iterators use different buffers");
315 return index == other.index;
316 }
317
318 bool operator!=(const const_iterator &other) const
319 {
320 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator!=", "iterators use different buffers");
321 return index != other.index;
322 }
323
324 bool operator<(const const_iterator &other) const
325 {
326 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator<", "iterators use different buffers");
327 return index < other.index;
328 }
329
330 bool operator<=(const const_iterator &other) const
331 {
332 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator<=", "iterators use different buffers");
333 return index <= other.index;
334 }
335
336 bool operator>(const const_iterator &other) const
337 {
338 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator>", "iterators use different buffers");
339 return index > other.index;
340 }
341
342 bool operator>=(const const_iterator &other) const
343 {
344 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator>=", "iterators use different buffers");
345 return index >= other.index;
346 }
347
348 const_iterator &operator++() { ++index; return *this; }
349 const_iterator operator++(int)
350 {
351 const_iterator ans = *this;
352 ++index;
353 return ans;
354 }
355
356 const_iterator &operator--() { --index; return *this; }
357 const_iterator operator--(int)
358 {
359 const_iterator ans = *this;
360 --index;
361 return ans;
362 }
363
364 const_iterator &operator+=(int j) { index += j; return *this; }
365 const_iterator &operator-=(int j) { index -= j; return *this; }
366 const_iterator operator+(int j) const { return const_iterator(buffer, index + j); }
367 const_iterator operator-(int j) const { return const_iterator(buffer, index - j); }
368 int operator-(const_iterator other) const
369 {
370 Q_ASSERT_X(buffer == other.buffer, "QCircularBuffer<T>::const_iterator::operator-", "iterators use different buffers");
371 return index - other.index;
372 }
373
374 private:
375 const QCircularBuffer<T> *buffer;
376 int index;
377 friend class QCircularBuffer;
378 };
379 friend class const_iterator;
380
381 typedef std::reverse_iterator<iterator> reverse_iterator;
382 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
383
384 iterator begin() { return iterator(this, 0); }
385 const_iterator begin() const { return const_iterator(this, 0); }
386 const_iterator cbegin() const { return const_iterator(this, 0); }
387 reverse_iterator rbegin() { return reverse_iterator(end()); }
388 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
389 const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
390 const_iterator constBegin() const { return const_iterator(this, 0); }
391 iterator end() { return iterator(this, d->size); }
392 const_iterator end() const { return const_iterator(this, d->size); }
393 const_iterator cend() const { return const_iterator(this, d->size); }
394 reverse_iterator rend() { return reverse_iterator(begin()); }
395 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
396 const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
397 const_iterator constEnd() const { return const_iterator(this, d->size); }
398 iterator insert(const_iterator before, int number, const T &val)
399 {
400 insert(before.index, number, val);
401 return iterator(this, before.index);
402 }
403 iterator insert(const_iterator before, const T &val) { return insert(before, 1, val); }
404 iterator erase(const_iterator b, const_iterator e)
405 {
406 int number = e - b;
407 remove(b.index, number);
408 return iterator(this, e.index - number);
409 }
410 iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
411
412 // STL compatibility
413 typedef T value_type;
414 typedef value_type *pointer;
415 typedef const value_type *const_pointer;
416 typedef value_type &reference;
417 typedef const value_type &const_reference;
418 typedef ptrdiff_t difference_type;
419 typedef iterator Iterator;
420 typedef const_iterator ConstIterator;
421 typedef int size_type;
422
423 void push_back(const T &t) { append(val: t); }
424 void push_front(const T &t) { prepend(val: t); }
425 void pop_back() { Q_ASSERT(!isEmpty()); erase(end() - 1); }
426 void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }
427 bool empty() const { return isEmpty(); }
428 T &front() { return first(); }
429 const T &front() const { return first(); }
430 T &back() { return last(); }
431 const T &back() const { return last(); }
432
433 QAtomicInt refCount() const { return d->ref; }
434
435 void append(const T &val);
436
437 const T &at(int i) const
438 {
439 Q_ASSERT_X(i >= 0 && i < d->size, "QCircularBuffer<T>::at", "index out of range");
440 return d->data()[d->wraparound(d->first + i)];
441 }
442
443 const T &operator[](int i) const
444 {
445 Q_ASSERT_X(i >= 0 && i < d->size, "QCircularBuffer<T>::operator[]", "index out of range");
446 return d->data()[d->wraparound(d->first + i)];
447 }
448
449 T &operator[](int i)
450 {
451 d.detach();
452 Q_ASSERT_X(i >= 0 && i < d->size, "QCircularBuffer<T>::operator[]", "index out of range");
453 return d->data()[d->wraparound(d->first + i)];
454 }
455
456 int capacity() const { return d->capacity; }
457
458 void clear() { *this = QCircularBuffer<T>(d->capacity); }
459
460 bool contains(const T &val) const;
461 int count(const T &val) const;
462 int count() const { return size(); }
463
464 array_range data()
465 {
466 d.detach();
467 if (d->size == 0)
468 return array_range(nullptr, 0);
469 if (!isLinearised())
470 linearise();
471 return array_range(d->data() + d->first, d->last - d->first + 1);
472 }
473 const_array_range data() const { return constData(); }
474 const_array_range constData() const
475 {
476 if (!isLinearised() || d->size == 0)
477 return const_array_range(nullptr, 0);
478 return const_array_range(d->data() + d->first, d->last - d->first + 1);
479 }
480
481 array_range dataOne()
482 {
483 d.detach();
484 if (d->size == 0)
485 return array_range(nullptr, 0);
486 if (isLinearised())
487 return array_range(d->data() + d->first, d->last - d->first + 1);
488 else
489 return array_range(d->data() + d->first, d->capacity - d->first);
490 }
491 const_array_range dataOne() const { return constDataOne(); }
492 const_array_range constDataOne() const
493 {
494 if (d->size == 0)
495 return const_array_range(nullptr, 0);
496 if (isLinearised())
497 return const_array_range(d->data() + d->first, d->last - d->first + 1);
498 else
499 return const_array_range(d->data() + d->first, d->capacity - d->first);
500 }
501
502 array_range dataTwo()
503 {
504 d.detach();
505 if (d->size == 0 || isLinearised())
506 return array_range(nullptr, 0);
507 return array_range(d->data(), d->last + 1);
508 }
509 const_array_range dataTwo() const { return constDataTwo(); }
510 const_array_range constDataTwo() const
511 {
512 if (d->size == 0 || isLinearised())
513 return const_array_range(nullptr, 0);
514 return const_array_range(d->data(), d->last + 1);
515 }
516
517 bool endsWith(const T &val) const { return !isEmpty() && last() == val; }
518 QCircularBuffer<T> &fill(const T &val, int number = -1);
519 T &first() { Q_ASSERT(!isEmpty()); d.detach(); return d->data()[ d->first ]; }
520 const T &first() const { Q_ASSERT(!isEmpty()); return d->data()[ d->first ]; }
521 int freeSize() const { return sizeAvailable(); }
522
523 static QCircularBuffer<T> fromList(const QList<T> &list)
524 { return QCircularBuffer(list.begin(), list.end()); }
525 static QCircularBuffer<T> fromVector(const QVector<T> &vector)
526 { return QCircularBuffer(vector.begin(), vector.end()); }
527
528 int indexOf(const T &val, int from = 0) const;
529 void insert(int i, const T &val) { insert(i, 1, val); }
530 void insert(int i, int number, const T &val);
531 bool isEmpty() const { return d->size == 0; }
532 bool isFull() const { return d->size == d->capacity; }
533 bool isLinearised() const { return (d->last >= d->first); }
534 T &last() { Q_ASSERT(!isEmpty()); return d->data()[ d->last ]; }
535 const T &last() const { Q_ASSERT(!isEmpty()); return d->data()[ d->last ]; }
536 int lastIndexOf(const T &val, int from = -1) const;
537 void linearise()
538 {
539 if (!isLinearised()) {
540 QCircularBuffer linearized(this->cbegin(), this->cend());
541 swap(other&: linearized);
542 }
543 }
544
545 void prepend(const T &val);
546 void remove(int i) { remove(i, 1); }
547 void remove(int i, int number);
548
549 void replace(int i, const T &val)
550 {
551 Q_ASSERT_X(i >= 0 && i < d->size, "QCircularBuffer<T>::replace", "index out of range");
552 const T copy(val);
553 (*this)[ i ] = copy;
554 }
555
556 void reserve(int amount) { setCapacity(amount); }
557 void resize(int newSize);
558 void setCapacity(int amount);
559 int size() const { return d->size; }
560 Q_DECL_CONSTEXPR int max_size() const { return std::numeric_limits<size_type>::max(); }
561 int sizeAvailable() const { return d->capacity - d->size; }
562 void squeeze() { setCapacity(size()); }
563 bool startsWith(const T &val) const { return !isEmpty() && first() == val; }
564
565 QList<T> toList() const;
566 QVector<T> toVector() const;
567
568 T value(int i) const
569 {
570 if (i < 0 || i >= d->size)
571 return T();
572 return at(i);
573 }
574
575 T value(int i, const T &defaultValue) const
576 {
577 if (i < 0 || i >= d->size)
578 return defaultValue;
579 return at(i);
580 }
581
582 QCircularBuffer<T> &operator+=(const T &other) { append(val: other); return *this; }
583 QCircularBuffer<T> &operator+=(const QCircularBuffer<T> &other);
584 QCircularBuffer<T> &operator+=(const QVector<T> &other);
585 QCircularBuffer<T> &operator+=(const QList<T> &other);
586
587 QCircularBuffer<T> &operator<<(const T &other) { append(val: other); return *this; }
588 QCircularBuffer<T> &operator<<(const QCircularBuffer<T> &other) { *this += other; return *this; }
589 QCircularBuffer<T> &operator<<(const QVector<T> &other) { *this += other; return *this; }
590 QCircularBuffer<T> &operator<<(const QList<T> &other) { *this += other; return *this; }
591
592 inline bool isSharedWith(const QCircularBuffer &other) const { return d == other.d; }
593
594private:
595 QExplicitlySharedDataPointer<Data> d;
596};
597
598template <typename T>
599QCircularBuffer<T> operator+(const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs);
600
601template <typename T>
602inline bool operator==(const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
603{ return lhs.isSharedWith(rhs) || (lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin())); }
604
605template <typename T>
606inline bool operator!=(const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
607{ return !operator==(lhs, rhs); }
608
609template <typename T>
610inline void swap(QCircularBuffer<T> &lhs, QCircularBuffer<T> &rhs)
611{ lhs.swap(rhs); }
612
613template <typename T>
614inline bool operator< (const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
615{ return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); }
616
617template <typename T>
618inline bool operator> (const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
619{ return operator<(rhs, lhs); }
620
621template <typename T>
622inline bool operator>=(const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
623{ return !operator<(lhs, rhs); }
624
625template <typename T>
626inline bool operator<=(const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
627{ return !operator>(lhs, rhs); }
628
629// out-of-line function implementations:
630
631#ifndef Q_QDOC
632
633template <typename T>
634QCircularBuffer<T>::QCircularBuffer(int amount)
635 : d(new Data())
636{
637 // Allocate some raw memory
638 d->setData(d->allocate(amount));
639 d->capacity = amount;
640
641 // Initialize memory block to zero
642 memset(d->data(), 0, amount * sizeof(T));
643}
644
645template <typename T>
646QCircularBuffer<T>::QCircularBuffer(int amount, const T &val)
647 : d(new Data())
648{
649 // Allocate some raw memory
650 d->setData(d->allocate(amount));
651 d->capacity = amount;
652
653 // Initialize the objects. In this case we always use the placement new operator
654 T *b = d->data();
655 T *i = b + d->capacity;
656 while (i != b)
657 new (--i) T(val);
658 d->first = 0;
659 d->last = d->capacity - 1;
660 d->size = d->capacity;
661}
662
663template <typename T>
664QCircularBuffer<T>::QCircularBuffer(int amount, int initialSize, const T &val)
665 : d(new Data())
666{
667 Q_ASSERT_X(amount >= initialSize, "QCircularBuffer<T>::QCircularBuffer(int capacity, int size, const T &value)", "size is greater than capacity");
668
669 // Allocate some raw memory
670 d->setData(d->allocate(amount));
671 d->capacity = amount;
672
673 // Initialize the objects that need to be set to the specified value.
674 // In this case we always use the placement new operator
675 T *b = d->data();
676 T *i = b + initialSize;
677 while (i != b)
678 new (--i) T(val);
679
680 // Initialize the remaining memory to zero
681 memset(d->data() + initialSize, 0, (amount - initialSize) * sizeof(T));
682
683 d->first = 0;
684 d->last = initialSize - 1;
685 d->size = initialSize;
686}
687
688template <typename T>
689void QCircularBuffer<T>::append(const T &val)
690{
691 // If we have no capacity we do nothing
692 if (!d->capacity)
693 return;
694 d.detach();
695 if (d->size == d->capacity) {
696 // Buffer is full. Overwrite earliest item and rotate
697 d->data()[ d->first ] = val;
698 d->first = d->wraparound(++d->first);
699 d->last = d->wraparound(++d->last);
700 } else if (d->size != 0) {
701 // Buffer is partially full. Append data to end of array using appropriate method
702 int index = d->wraparound(d->first + d->size);
703 if (QTypeInfo<T>::isComplex)
704 new (d->data() + index) T(val);
705 else
706 d->data()[ index ] = val;
707 ++d->size;
708 ++d->last;
709 } else {
710 // Buffer is empty. Append data to end of array using appropriate method
711 d->size = 1;
712 d->first = d->last = 0;
713 if (QTypeInfo<T>::isComplex)
714 new (d->data() + d->first) T(val);
715 else
716 d->data()[ d->first ] = val;
717 }
718}
719
720template <typename T>
721bool QCircularBuffer<T>::contains(const T &val) const
722{
723 if (isLinearised()) {
724 T *b = d->data() + d->first;
725 T *i = b + d->size;
726 while (i != b)
727 if (*--i == val)
728 return true;
729 return false;
730 } else {
731 // Check the array from m_first to the end
732 T *b = d->data() + d->first;
733 T *i = d->data() + d->capacity;
734 while (i != b)
735 if (*--i == val)
736 return true;
737
738 // Check array from 0 to m_end
739 b = d->data();
740 i = d->data() + d->last + 1;
741 while (i != b)
742 if (*--i == val)
743 return true;
744
745 return false;
746 }
747}
748
749template <typename T>
750int QCircularBuffer<T>::count(const T &val) const
751{
752 int c = 0;
753 if (isLinearised()) {
754 T *b = d->data() + d->first;
755 T *i = b + d->size;
756 while (i != b)
757 if (*--i == val)
758 ++c;
759 } else {
760 // Check the array from m_first to the end
761 T *b = d->data() + d->first;
762 T *i = d->data() + d->capacity;
763 while (i != b)
764 if (*--i == val)
765 ++c;
766
767 // Check array from 0 to m_end
768 b = d->data();
769 i = d->data() + d->last + 1;
770 while (i != b)
771 if (*--i == val)
772 ++c;
773 }
774 return c;
775}
776
777template <typename T>
778QCircularBuffer<T> &QCircularBuffer<T>::fill(const T &val, int number)
779{
780 Q_ASSERT_X(d->capacity >= number, "QCircularBuffer<T>::fill", "size is greater than capacity");
781 const T copy(val);
782 d.detach();
783 int oldSize = d->size;
784 d->size = (number < 0 ? d->size : number);
785 d->first = (number == 0 ? -1 : 0);
786 d->last = d->size - 1;
787
788 // Copy item into array size times
789 if (d->size) {
790 T *b = d->data();
791 T *i = d->data() + d->size;
792 while (i != b)
793 *--i = copy;
794 }
795
796 if (d->size < oldSize) {
797 // Cleanup old items beyond end of new array
798 T *b = d->data() + d->size;
799 T *i = d->data() + oldSize;
800 while (i-- != b) {
801 i->~T();
802 //TODO: Optimize to a single memset call
803 memset(i, 0, sizeof(T));
804 }
805 }
806
807 return *this;
808}
809
810template <typename T>
811int QCircularBuffer<T>::indexOf(const T &val, int from) const
812{
813 Q_ASSERT_X(from < d->size, "QCircularBuffer<T>::indexOf", "from is greater than last valid index");
814 if (from < 0)
815 from = qMax(from + d->size, 0);
816 else if (from >= d->size)
817 from = d->size - 1;
818 for (int i = from; i < d->size; ++i)
819 if (at(i) == val)
820 return i;
821 return -1;
822}
823
824template <typename T>
825void QCircularBuffer<T>::insert(int i, int number, const T &val)
826{
827 Q_ASSERT_X(i >= 0 && i <= d->size, "QCircularBuffer<T>::insert", "index out of range");
828 d.detach();
829 int freeCapacity = d->capacity - d->size;
830
831 // Calculate number of elements that will actually be inserted. This
832 // depends upon where the insertion has been requested and any spare
833 // capacity left in the buffer. This is because elements at higher
834 // indices will be pushed to the right and will potentially wrap around
835 // to overwrite earlier elements.
836 int numToInsert = qMin(a: number, b: i + freeCapacity);
837
838 // Calculate the number of elements at the beginning of the buffer that
839 // will be overwritten
840 int numToOverwrite = qMin(a: i, b: qMax(a: 0, b: number - freeCapacity));
841
842 // Decide which way to shift to minimize the amount of copying required.
843 if (i < d->size / 2) {
844 // Inserting in lower half of buffer so we shift earlier items down
845
846 // Shift data at the bottom end down. This may only be a subset if some
847 // of the early data is to be overwritten.
848 if (QTypeInfo<T>::isStatic) {
849 int b = d->first + numToOverwrite;
850 int e = d->first + i - 1;
851 for (int j = b; j <= e; ++j) {
852 int srcIndex = j % d->capacity;
853 int dstIndex = (j - numToInsert + d->capacity) % d->capacity;
854 T *src = d->data() + srcIndex;
855 T *dst = d->data() + dstIndex;
856
857 new (dst) T(*src);
858 }
859 } else {
860 // We have a movable type so a simple memcopy (or maybe two or
861 // three) will suffice to shift the data at the bottom end
862 int numToMove = i - numToOverwrite;
863 if (numToMove > 0) {
864 int srcBegin = (d->first + numToOverwrite) % d->capacity;
865 int srcEnd = (d->first + i - 1) % d->capacity;
866 int dstBegin = (srcBegin - numToInsert + d->capacity) % d->capacity;
867 int dstEnd = (srcEnd - numToInsert + d->capacity) % d->capacity;
868
869 // Do we have any wrap-around problems to deal with?
870 bool srcRegionWraps = (srcEnd < srcBegin);
871 bool dstRegionWraps = (dstEnd < dstBegin);
872 if (!srcRegionWraps && dstRegionWraps) {
873 // Destination region wraps so do the move in two steps
874 int wrapCount = abs(x: srcBegin - numToInsert);
875 memmove(d->data() + d->capacity - wrapCount, d->data() + srcBegin, wrapCount * sizeof(T));
876 memmove(d->data(), d->data() + srcBegin + wrapCount, (numToMove - wrapCount) * sizeof(T));
877 } else if (srcRegionWraps && !dstRegionWraps) {
878 // Source region wraps so do the move in two steps
879 int wrapCount = d->capacity - srcBegin;
880 memmove(d->data() + dstBegin, d->data() + d->capacity - wrapCount, wrapCount * sizeof(T));
881 memmove(d->data() + dstBegin + numToInsert, d->data(), (numToMove - wrapCount) * sizeof(T));
882 } else if (srcRegionWraps && dstRegionWraps) {
883 // Source and destination regions wrap so we have to do this in three steps
884 int srcWrapCount = d->capacity - srcBegin;
885 memmove(d->data() + dstBegin, d->data() + d->capacity - srcWrapCount, srcWrapCount * sizeof(T));
886 memmove(d->data() + d->capacity - numToInsert, d->data(), numToInsert * sizeof(T));
887 memmove(d->data(), d->data() + numToInsert, (numToMove - srcWrapCount - numToInsert) * sizeof(T));
888 } else {
889 // No wrap around - do a single memmove
890 memmove(d->data() + dstBegin, d->data() + srcBegin, numToMove * sizeof(T));
891 }
892 }
893 }
894
895 // Insert the new items
896 int e = d->first + i;
897 int b = e - numToInsert;
898 for (int j = b; j < e; ++j) {
899 T *p = d->data() + ((j + d->capacity) % d->capacity);
900 new (p) T(val);
901 }
902
903 // Adjust the first, last and size indices as needed.
904 // NB. The last index never changes in this regime.
905 d->size += qMin(a: number, b: freeCapacity);
906 d->first = (d->first - (numToInsert - numToOverwrite) + d->capacity) % d->capacity;
907 } else {
908 // Inserting in upper half of buffer so we shift later items up
909
910 // Shift data at the top end up which may or may not overwrite some
911 // of the earliest data
912 if (QTypeInfo<T>::isStatic) {
913 int b = d->first + d->size - 1;
914 int e = d->first + i;
915 for (int j = b; j >= e; j--) {
916 int srcIndex = j % d->capacity;
917 int dstIndex = (j + numToInsert) % d->capacity;
918 T *src = d->data() + srcIndex;
919 T *dst = d->data() + dstIndex;
920
921 new (dst) T(*src);
922 }
923 } else {
924 // We have a movable type so a simple memcopy (or maybe two or
925 // three) will suffice to shift the data at the top end
926 int numToMove = d->size - i;
927 if (numToMove > 0) {
928 int srcBegin = (d->first + i) % d->capacity;
929 int srcEnd = d->last;
930 int dstBegin = (srcBegin + numToInsert) % d->capacity;
931 int dstEnd = (srcEnd + numToInsert) % d->capacity;
932
933 // Do we have any wrap-around problems to deal with?
934 bool srcRegionWraps = (srcEnd < srcBegin);
935 bool dstRegionWraps = (dstEnd < dstBegin);
936 if (!srcRegionWraps && dstRegionWraps) {
937 // Destination region wraps so do the move in two steps
938 int wrapCount = srcEnd + numToInsert - d->capacity + 1;
939 memmove(d->data(), d->data() + srcEnd - wrapCount + 1, wrapCount * sizeof(T));
940 memmove(d->data() + dstBegin, d->data() + srcBegin, (numToMove - wrapCount) * sizeof(T));
941 } else if (srcRegionWraps && !dstRegionWraps) {
942 // Source region wraps so do the move in two steps
943 int wrapCount = d->last + 1;
944 memmove(d->data() + numToInsert, d->data(), wrapCount * sizeof(T));
945 memmove(d->data() + dstBegin, d->data() + srcBegin, (numToMove - wrapCount) * sizeof(T));
946 } else if (srcRegionWraps && dstRegionWraps) {
947 // Source and destination regions wrap so we have to do this in three steps
948 int srcWrapCount = d->last + 1;
949 memmove(d->data() + numToInsert, d->data(), srcWrapCount * sizeof(T));
950 memmove(d->data(), d->data() + d->capacity - numToInsert, numToInsert * sizeof(T));
951 memmove(d->data() + dstBegin, d->data() + srcBegin, (numToMove - srcWrapCount - numToInsert) * sizeof(T));
952 } else {
953 // No wrap around - do a single memmove
954 memmove(d->data() + dstBegin, d->data() + srcBegin, numToMove * sizeof(T));
955 }
956 }
957 }
958
959 // Insert the new items
960 for (int j = d->first + i; j < d->first + i + numToInsert; ++j) {
961 T *p = d->data() + (j % d->capacity);
962 new (p) T(val);
963 }
964
965 // Adjust the first, last and size indices as needed
966 d->size += qMin(a: number, b: freeCapacity);
967 d->first = (d->first + numToOverwrite) % d->capacity;
968 d->last = (d->last + numToInsert) % d->capacity;
969 }
970}
971
972template <typename T>
973int QCircularBuffer<T>::lastIndexOf(const T &val, int from) const
974{
975 if (from < 0)
976 from = qMax(from + d->size, 0);
977 else if (from >= d->size)
978 from = d->size - 1;
979 for (int i = from; i >= 0; --i)
980 if (at(i) == val)
981 return i;
982 return -1;
983}
984
985template <typename T>
986void QCircularBuffer<T>::prepend(const T &val)
987{
988 // If we have no capacity we do nothing
989 if (!d->capacity)
990 return;
991
992 d.detach();
993 if (d->size == d->capacity) {
994 // Buffer is full. Overwrite last item and rotate
995 d->data()[ d->last ] = val;
996 d->first = (--d->first + d->capacity) % d->capacity;
997 d->last = (--d->last + d->capacity) % d->capacity;
998 } else if (d->size != 0) {
999 // Buffer is partially full. Prepend data to start of array using appropriate method
1000 d->first = (--d->first + d->capacity) % d->capacity;
1001 ++d->size;
1002 if (QTypeInfo<T>::isComplex)
1003 new (d->data() + d->first) T(val);
1004 else
1005 d->data()[ d->first ] = val;
1006 } else {
1007 // Buffer is empty. Prepend data to start of array using appropriate method
1008 d->size = 1;
1009 d->first = d->last = d->capacity - 1;
1010 if (QTypeInfo<T>::isComplex)
1011 new (d->data() + d->first) T(val);
1012 else
1013 d->data()[ d->first ] = val;
1014 }
1015}
1016
1017template <typename T>
1018void QCircularBuffer<T>::remove(int i, int number)
1019{
1020 Q_ASSERT_X(i >= 0 && number > 0 && i + number <= d->size, "QCircularBuffer<T>::remove", "index out of range");
1021 d.detach();
1022
1023 // HACK (it actually makes sense, but requires some more thinking)
1024 if ( i == 0 && !QTypeInfo<T>::isComplex ) {
1025 d->first = d->wraparound( d->first + number );
1026 d->size -= number;
1027 return;
1028 }
1029
1030 // Calculate the number of items that need to be moved downward
1031 int numToMoveDown = d->size - number - i;
1032 int numToMoveUp = i;
1033
1034 if (numToMoveDown < numToMoveUp) {
1035 // Move higher items down
1036 int numToMove = numToMoveDown;
1037
1038 if (QTypeInfo<T>::isComplex) {
1039 // Copy items down from higher positions
1040 int b = d->first + i;
1041 int e = b + numToMove;
1042 for (int j = b; j < e ; ++j) {
1043 T *src = d->data() + ((j + number) % d->capacity);
1044 T *dst = d->data() + (j % d->capacity);
1045 new (dst) T(*src);
1046 }
1047
1048 // Clean up items at end of buffer
1049 for (int j = d->last; j > d->last - number; --j) {
1050 T *p = d->data() + ((j + d->capacity) % d->capacity);
1051 p->~T();
1052 //TODO: Optimize to a single memset call
1053 memset(p, 0, sizeof(T));
1054 }
1055 } else {
1056 if (isLinearised()) {
1057 // With a linearised buffer we can do a simple move and removal of items
1058 memmove(d->data() + d->last - numToMove - number + 1, d->data() + d->last - numToMove + 1, numToMove * sizeof(T));
1059 memset(d->data() + d->last - number + 1, 0, number * sizeof(T));
1060 } else {
1061 // With a non-linearised buffer we need to be careful of wrapping issues
1062 int srcBegin = (d->last - numToMove + 1 + d->capacity) % d->capacity;
1063 int srcEnd = d->last;
1064 int dstBegin = (d->first + i) % d->capacity;
1065 int dstEnd = (dstBegin + numToMove - 1) % d->capacity;
1066
1067 bool srcRegionWraps = (srcEnd < srcBegin);
1068 bool dstRegionWraps = (dstEnd < dstBegin);
1069 if (srcRegionWraps && !dstRegionWraps) {
1070 // Source region wraps so do the move in two steps
1071 int wrapCount = d->capacity - srcBegin;
1072 memmove(d->data() + dstBegin, d->data() + srcBegin, wrapCount * sizeof(T));
1073 memmove(d->data() + dstBegin + wrapCount, d->data(), (numToMove - wrapCount) * sizeof(T));
1074 } else if (!srcRegionWraps && dstRegionWraps) {
1075 // Destination region wraps so do the move in two steps
1076 int wrapCount = number - srcBegin;
1077 memmove(d->data() + d->capacity - wrapCount, d->data() + srcBegin, wrapCount * sizeof(T));
1078 memmove(d->data(), d->data() + srcBegin + wrapCount, (numToMove - wrapCount) * sizeof(T));
1079 } else if (srcRegionWraps && dstRegionWraps) {
1080 // Source and destination regions wrap so we have to do this in three steps
1081 int srcWrapCount = d->capacity - srcBegin;
1082 memmove(d->data() + dstBegin, d->data() + srcBegin, srcWrapCount * sizeof(T));
1083 memmove(d->data() + dstBegin + srcWrapCount, d->data(), number * sizeof(T));
1084 memmove(d->data(), d->data() + number, (numToMove - srcWrapCount - number) * sizeof(T));
1085 } else {
1086 // No wrap around, so we can do this in one hit
1087 memmove(d->data() + dstBegin, d->data() + srcBegin, numToMove * sizeof(T));
1088 }
1089
1090 // We potentially have a disjoint region that needs zeroing
1091 int zeroStart = (d->last - number + d->capacity + 1) % d->capacity;
1092 int zeroEnd = d->last;
1093 if (zeroEnd < zeroStart) {
1094 // Region to be zeroed wraps. Do it in two steps.
1095 memset(d->data(), 0, (d->last + 1) * sizeof(T));
1096 memset(d->data() + zeroStart, 0, (number - d->last - 1) * sizeof(T));
1097 } else {
1098 // Region to be zeroed is contiguous
1099 memset(d->data() + zeroStart, 0, number * sizeof(T));
1100 }
1101 }
1102 }
1103
1104 // Adjust the indices
1105 d->size -= number;
1106 d->last = (d->last - number + d->capacity) % d->capacity;
1107 } else {
1108 // Move lower items up
1109 int numToMove = numToMoveUp;
1110
1111 if (QTypeInfo<T>::isComplex) {
1112 // Copy items up from lower positions
1113 int b = d->first + i - 1;
1114 int e = b - numToMove;
1115 for (int j = b; j > e ; --j) {
1116 T *src = d->data() + ((j + d->capacity) % d->capacity);
1117 T *dst = d->data() + ((j + d->capacity + number) % d->capacity);
1118 new (dst) T(*src);
1119 }
1120
1121 // Clean up items at start of buffer
1122 for (int j = d->first; j < d->first + number; ++j) {
1123 T *p = d->data() + (j % d->capacity);
1124 p->~T();
1125 //TODO: Optimize to a single memset call
1126 memset(p, 0, sizeof(T));
1127 }
1128 } else {
1129 if (isLinearised()) {
1130 // With a linearised buffer we can do a simple move and removal of items
1131 memmove(d->data() + d->first + number, d->data() + d->first, numToMove * sizeof(T));
1132 memset(d->data() + d->first, 0, number * sizeof(T));
1133 } else {
1134 // With a non-linearised buffer we need to be careful of wrapping issues
1135 int srcBegin = d->first;
1136 int srcEnd = (srcBegin + numToMove - 1) % d->capacity;
1137 int dstBegin = (srcBegin + number) % d->capacity;
1138 int dstEnd = (dstBegin + numToMove - 1) % d->capacity;
1139
1140 bool srcRegionWraps = (srcEnd < srcBegin);
1141 bool dstRegionWraps = (dstEnd < dstBegin);
1142 if (srcRegionWraps && !dstRegionWraps) {
1143 // Source region wraps so do the move in two steps
1144 int wrapCount = srcEnd + 1;
1145 memmove(d->data() + dstEnd - wrapCount + 1, d->data(), wrapCount * sizeof(T));
1146 memmove(d->data() + dstBegin, d->data() + srcBegin, (numToMove - wrapCount) * sizeof(T));
1147 } else if (!srcRegionWraps && dstRegionWraps) {
1148 // Destination region wraps so do the move in two steps
1149 int wrapCount = dstEnd + 1;
1150 memmove(d->data(), d->data() + srcEnd - wrapCount + 1, wrapCount * sizeof(T));
1151 memmove(d->data() + dstBegin, d->data() + srcBegin, (numToMove - wrapCount) * sizeof(T));
1152 } else if (srcRegionWraps && dstRegionWraps) {
1153 // Source and destination regions wrap so we have to do this in three steps
1154 int srcWrapCount = srcEnd + 1;
1155 memmove(d->data() + dstEnd - srcWrapCount + 1, d->data(), srcWrapCount * sizeof(T));
1156 memmove(d->data(), d->data() + d->capacity - number, number * sizeof(T));
1157 memmove(d->data() + dstBegin, d->data() + srcBegin, (numToMove - srcWrapCount - number) * sizeof(T));
1158 } else {
1159 // No wrap around, so we can do this in one hit
1160 memmove(d->data() + dstBegin, d->data() + srcBegin, numToMove * sizeof(T));
1161 }
1162
1163 // We potentially have a disjoint region that needs zeroing
1164 int zeroStart = d->first;
1165 int zeroEnd = (zeroStart + number - 1) % d->capacity;
1166 if (zeroEnd < zeroStart) {
1167 // Region to be zeroed wraps. Do it in two steps.
1168 memset(d->data() + zeroStart, 0, (d->capacity - d->first) * sizeof(T));
1169 memset(d->data(), 0, (number - d->capacity + d->first) * sizeof(T));
1170 } else {
1171 // Region to be zeroed is contiguous
1172 memset(d->data() + zeroStart, 0, number * sizeof(T));
1173 }
1174 }
1175 }
1176
1177 // Adjust the indices
1178 d->size -= number;
1179 d->first = (d->first + number) % d->capacity;
1180 }
1181}
1182
1183template <typename T>
1184void QCircularBuffer<T>::setCapacity(int amount)
1185{
1186 if (amount == d->capacity)
1187 return;
1188
1189 d.detach();
1190 // Allocate some new raw memory
1191 T *newData = d->allocate(amount);
1192
1193 // How many items can we copy across?
1194 int newSize = qMin(d->size, amount);
1195
1196 if (QTypeInfo<T>::isComplex) {
1197 // Copy across the elements from the original array
1198 for (int i = 0; i < newSize; ++i) {
1199 T *src = d->data() + ((d->first + i) % d->capacity);
1200 T *dst = newData + i;
1201 new (dst) T(*src);
1202 }
1203
1204 // Destroy the original items.
1205 // The type is complex so we manually call the destructor for each item
1206 // since we used the placement new operator to instantiate them
1207 T *b = d->data();
1208 T *i = b + d->capacity;
1209 while (i-- != b)
1210 i->~T();
1211 } else {
1212 // Copy across the elements from the original array. The source region
1213 // potentially wraps so we may have to do this in one or two steps
1214 if (isLinearised()) {
1215 memmove(newData, d->data() + d->first, newSize * sizeof(T));
1216 } else {
1217 int step1Size = qMin(newSize, d->capacity - d->first);
1218 memmove(newData, d->data() + d->first, step1Size * sizeof(T));
1219 int step2Size = qMax(0, qMin(newSize - d->capacity + d->first, d->last + 1));
1220 memmove(newData + step1Size, d->data(), step2Size * sizeof(T));
1221 }
1222 }
1223
1224 // Initialize any memory outside of the valid buffer (ie the unused items)
1225 memset(newData + newSize, 0, (amount - newSize) * sizeof(T));
1226
1227 // Release the raw memory for the old array
1228 d->deallocate(d->data());
1229
1230 // Assign the new memory to be our buffer data and fix indices
1231 d->setData(newData);
1232 d->capacity = amount;
1233 d->first = 0;
1234 d->size = newSize;
1235 d->last = d->size - 1;
1236}
1237
1238template <typename T>
1239void QCircularBuffer<T>::resize(int newSize)
1240{
1241 Q_ASSERT_X(newSize >= 0 && newSize <= d->capacity, "QCircularBuffer<T>::resize", "size out of range");
1242 d.detach();
1243 if (newSize < d->size) {
1244 remove(newSize, d->size - newSize);
1245 } else if (newSize > d->size) {
1246 const T t = T();
1247 insert(d->size, newSize - d->size, t);
1248 }
1249}
1250
1251template <typename T>
1252QCircularBuffer<T> &QCircularBuffer<T>::operator+=(const QCircularBuffer<T> &other)
1253{
1254 d.detach();
1255 // How many items do we need to copy? No point in ever copying across a number
1256 // greater than capacity
1257 int numToCopy = qMin(other.size(), d->capacity);
1258 int offset = other.size() - numToCopy;
1259 for (int i = 0; i < numToCopy; ++i)
1260 append(val: other.at(offset + i));
1261 return *this;
1262}
1263
1264template <typename T>
1265QCircularBuffer<T> &QCircularBuffer<T>::operator+=(const QVector<T> &other)
1266{
1267 d.detach();
1268 // How many items do we need to copy? No point in ever copying across a number
1269 // greater than capacity
1270 int numToCopy = qMin(other.size(), d->capacity);
1271 int offset = other.size() - numToCopy;
1272 for (int i = 0; i < numToCopy; ++i)
1273 append(val: other.at(offset + i));
1274 return *this;
1275}
1276
1277template <typename T>
1278QCircularBuffer<T> &QCircularBuffer<T>::operator+=(const QList<T> &other)
1279{
1280 d.detach();
1281 // How many items do we need to copy? No point in ever copying across a number
1282 // greater than capacity
1283 int numToCopy = qMin(other.size(), d->capacity);
1284 int offset = other.size() - numToCopy;
1285 for (int i = 0; i < numToCopy; ++i)
1286 append(val: other.at(offset + i));
1287 return *this;
1288}
1289
1290template <typename T>
1291QList<T> QCircularBuffer<T>::toList() const
1292{
1293 QList<T> list;
1294 list.reserve(size());
1295 for (int i = 0; i < size(); ++i)
1296 list.append(at(i));
1297 return list;
1298}
1299
1300template <typename T>
1301QVector<T> QCircularBuffer<T>::toVector() const
1302{
1303 QVector<T> vector;
1304 vector.reserve(size());
1305 for (int i = 0; i < size(); ++i)
1306 vector.append(at(i));
1307 return vector;
1308}
1309
1310template <typename T>
1311QCircularBuffer<T> operator+(const QCircularBuffer<T> &lhs, const QCircularBuffer<T> &rhs)
1312{
1313 QCircularBuffer<T> circ(lhs.size() + rhs.size());
1314 for (int i = 0; i < lhs.size(); ++i)
1315 circ.append(lhs.at(i));
1316 for (int i = 0; i < rhs.size(); ++i)
1317 circ.append(rhs.at(i));
1318 return circ;
1319}
1320
1321#endif // Q_QDOC
1322
1323Q_DECLARE_SEQUENTIAL_ITERATOR(CircularBuffer)
1324Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(CircularBuffer)
1325
1326} //Qt3D
1327
1328QT_END_NAMESPACE
1329
1330#endif // QT3DCORE_QCIRCULARBUFFER_H
1331

source code of qt3d/src/core/resources/qcircularbuffer_p.h