include/QtCore/qcontiguouscache.h

0001 // Copyright (C) 2016 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QCONTIGUOUSCACHE_H
0005 #define QCONTIGUOUSCACHE_H
0006
0007 #include <QtCore/qatomic.h>
0008 #include <QtCore/qassert.h>
0009 #include <QtCore/qtclasshelpermacros.h>
0010 #include <QtCore/qtcoreexports.h>
0011 #include <QtCore/qminmax.h>
0012 #include <QtCore/qttypetraits.h>
0013 #include <QtCore/qtypeinfo.h>
0014
0015 #include <climits>
0016 #include <limits>
0017 #include <new>
0018
0019 QT_BEGIN_NAMESPACE
0020
0021 #undef QT_QCONTIGUOUSCACHE_DEBUG
0022
0023
0024 struct Q_CORE_EXPORT QContiguousCacheData
0025 {
0026     QBasicAtomicInt ref;
0027     qsizetype alloc;
0028     qsizetype count;
0029     qsizetype start;
0030     qsizetype offset;
0031
0032     static QContiguousCacheData *allocateData(qsizetype size, qsizetype alignment);
0033     static void freeData(QContiguousCacheData *data);
0034
0035 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
0036     void dump() const;
0037 #endif
0038 };
0039
0040 template <typename T>
0041 struct QContiguousCacheTypedData : public QContiguousCacheData
0042 {
0043     T array[1];
0044 };
0045
0046 template<typename T>
0047 class QContiguousCache {
0048     static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
0049
0050     typedef QContiguousCacheTypedData<T> Data;
0051     Data *d;
0052 public:
0053     // STL compatibility
0054     typedef T value_type;
0055     typedef value_type* pointer;
0056     typedef const value_type* const_pointer;
0057     typedef value_type& reference;
0058     typedef const value_type& const_reference;
0059     typedef qptrdiff difference_type;
0060     typedef qsizetype size_type;
0061
0062     explicit QContiguousCache(qsizetype capacity = 0);
0063     QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); }
0064
0065     inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) freeData(d); }
0066
0067     inline void detach() { if (d->ref.loadRelaxed() != 1) detach_helper(); }
0068     inline bool isDetached() const { return d->ref.loadRelaxed() == 1; }
0069
0070     QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
0071     QT_MOVE_ASSIGNMENT_OPERATOR_IMPL_VIA_PURE_SWAP(QContiguousCache)
0072     void swap(QContiguousCache &other) noexcept { qt_ptr_swap(d, other.d); }
0073
0074 #ifndef Q_QDOC
0075     template <typename U = T>
0076     QTypeTraits::compare_eq_result<U> operator==(const QContiguousCache<T> &other) const
0077     {
0078         if (other.d == d)
0079             return true;
0080         if (other.d->start != d->start
0081                 || other.d->count != d->count
0082                 || other.d->offset != d->offset
0083                 || other.d->alloc != d->alloc)
0084             return false;
0085         for (qsizetype i = firstIndex(); i <= lastIndex(); ++i)
0086             if (!(at(i) == other.at(i)))
0087                 return false;
0088         return true;
0089     }
0090     template <typename U = T>
0091     QTypeTraits::compare_eq_result<U> operator!=(const QContiguousCache<T> &other) const
0092     { return !(*this == other); }
0093 #else
0094     bool operator==(const QContiguousCache &other) const;
0095     bool operator!=(const QContiguousCache &other) const;
0096 #endif // Q_QDOC
0097
0098     inline qsizetype capacity() const {return d->alloc; }
0099     inline qsizetype count() const { return d->count; }
0100     inline qsizetype size() const { return d->count; }
0101
0102     inline bool isEmpty() const { return d->count == 0; }
0103     inline bool isFull() const { return d->count == d->alloc; }
0104     inline qsizetype available() const { return d->alloc - d->count; }
0105
0106     void clear();
0107     void setCapacity(qsizetype size);
0108
0109     const T &at(qsizetype pos) const;
0110     T &operator[](qsizetype i);
0111     const T &operator[](qsizetype i) const;
0112
0113     void append(T &&value);
0114     void append(const T &value);
0115     void prepend(T &&value);
0116     void prepend(const T &value);
0117     void insert(qsizetype pos, T &&value);
0118     void insert(qsizetype pos, const T &value);
0119
0120
0121     inline bool containsIndex(qsizetype pos) const { return pos >= d->offset && pos - d->offset < d->count; }
0122     inline qsizetype firstIndex() const { return d->offset; }
0123     inline qsizetype lastIndex() const { return d->offset + d->count - 1; }
0124
0125     inline const T &first() const { Q_ASSERT(!isEmpty()); return d->array[d->start]; }
0126     inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; }
0127     inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; }
0128     inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->array[(d->start + d->count -1) % d->alloc]; }
0129
0130     void removeFirst();
0131     T takeFirst();
0132     void removeLast();
0133     T takeLast();
0134
0135     // Use extra parentheses around max to avoid expanding it if it is a macro.
0136     inline bool areIndexesValid() const
0137     { return d->offset >= 0 && d->offset < (std::numeric_limits<qsizetype>::max)() - d->count && (d->offset % d->alloc) == d->start; }
0138
0139     inline void normalizeIndexes() { d->offset = d->start; }
0140
0141 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
0142     void dump() const { d->dump(); }
0143 #endif
0144 private:
0145     void detach_helper();
0146
0147     Data *allocateData(qsizetype aalloc);
0148     void freeData(Data *x);
0149 };
0150
0151 template <typename T>
0152 void QContiguousCache<T>::detach_helper()
0153 {
0154     Data *x = allocateData(d->alloc);
0155     x->count = d->count;
0156     x->start = d->start;
0157     x->offset = d->offset;
0158     x->alloc = d->alloc;
0159
0160     T *dest = x->array + x->start;
0161     T *src = d->array + d->start;
0162     qsizetype oldcount = x->count;
0163     while (oldcount--) {
0164         new (dest) T(*src);
0165         dest++;
0166         if (dest == x->array + x->alloc)
0167             dest = x->array;
0168         src++;
0169         if (src == d->array + d->alloc)
0170             src = d->array;
0171     }
0172
0173     if (!d->ref.deref())
0174         freeData(d);
0175     d = x;
0176 }
0177
0178 template <typename T>
0179 void QContiguousCache<T>::setCapacity(qsizetype asize)
0180 {
0181     Q_ASSERT(asize >= 0);
0182     if (asize == d->alloc)
0183         return;
0184     detach();
0185     Data *x = allocateData(asize);
0186     x->alloc = asize;
0187     x->count = qMin(d->count, asize);
0188     x->offset = d->offset + d->count - x->count;
0189     if (asize)
0190         x->start = x->offset % x->alloc;
0191     else
0192         x->start = 0;
0193
0194     qsizetype oldcount = x->count;
0195     if (oldcount)
0196     {
0197         T *dest = x->array + (x->start + x->count-1) % x->alloc;
0198         T *src = d->array + (d->start + d->count-1) % d->alloc;
0199         while (oldcount--) {
0200             new (dest) T(*src);
0201             if (dest == x->array)
0202                 dest = x->array + x->alloc;
0203             dest--;
0204             if (src == d->array)
0205                 src = d->array + d->alloc;
0206             src--;
0207         }
0208     }
0209     /* free old */
0210     freeData(d);
0211     d = x;
0212 }
0213
0214 template <typename T>
0215 void QContiguousCache<T>::clear()
0216 {
0217     if (d->ref.loadRelaxed() == 1) {
0218         if (QTypeInfo<T>::isComplex) {
0219             qsizetype oldcount = d->count;
0220             T * i = d->array + d->start;
0221             T * e = d->array + d->alloc;
0222             while (oldcount--) {
0223                 i->~T();
0224                 i++;
0225                 if (i == e)
0226                     i = d->array;
0227             }
0228         }
0229         d->count = d->start = d->offset = 0;
0230     } else {
0231         Data *x = allocateData(d->alloc);
0232         x->alloc = d->alloc;
0233         x->count = x->start = x->offset = 0;
0234         if (!d->ref.deref())
0235             freeData(d);
0236         d = x;
0237     }
0238 }
0239
0240 template <typename T>
0241 inline typename QContiguousCache<T>::Data *QContiguousCache<T>::allocateData(qsizetype aalloc)
0242 {
0243     return static_cast<Data *>(QContiguousCacheData::allocateData(sizeof(Data) + (aalloc - 1) * sizeof(T), alignof(Data)));
0244 }
0245
0246 template <typename T>
0247 QContiguousCache<T>::QContiguousCache(qsizetype cap)
0248 {
0249     Q_ASSERT(cap >= 0);
0250     d = allocateData(cap);
0251     d->alloc = cap;
0252     d->count = d->start = d->offset = 0;
0253 }
0254
0255 template <typename T>
0256 QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
0257 {
0258     other.d->ref.ref();
0259     if (!d->ref.deref())
0260         freeData(d);
0261     d = other.d;
0262     return *this;
0263 }
0264
0265 template <typename T>
0266 void QContiguousCache<T>::freeData(Data *x)
0267 {
0268     if (QTypeInfo<T>::isComplex) {
0269         qsizetype oldcount = d->count;
0270         T * i = d->array + d->start;
0271         T * e = d->array + d->alloc;
0272         while (oldcount--) {
0273             i->~T();
0274             i++;
0275             if (i == e)
0276                 i = d->array;
0277         }
0278     }
0279     Data::freeData(x);
0280 }
0281 template <typename T>
0282 void QContiguousCache<T>::append(T &&value)
0283 {
0284     if (!d->alloc)
0285         return;     // zero capacity
0286     detach();
0287     if (d->count == d->alloc)
0288         (d->array + (d->start+d->count) % d->alloc)->~T();
0289     new (d->array + (d->start+d->count) % d->alloc) T(std::move(value));
0290
0291     if (d->count == d->alloc) {
0292         d->start++;
0293         d->start %= d->alloc;
0294         d->offset++;
0295     } else {
0296         d->count++;
0297     }
0298 }
0299
0300 template <typename T>
0301 void QContiguousCache<T>::append(const T &value)
0302 {
0303     if (!d->alloc)
0304         return;     // zero capacity
0305     detach();
0306     if (d->count == d->alloc)
0307         (d->array + (d->start+d->count) % d->alloc)->~T();
0308     new (d->array + (d->start+d->count) % d->alloc) T(value);
0309
0310     if (d->count == d->alloc) {
0311         d->start++;
0312         d->start %= d->alloc;
0313         d->offset++;
0314     } else {
0315         d->count++;
0316     }
0317 }
0318
0319 template<typename T>
0320 void QContiguousCache<T>::prepend(T &&value)
0321 {
0322     if (!d->alloc)
0323         return;     // zero capacity
0324     detach();
0325     if (d->start)
0326         d->start--;
0327     else
0328         d->start = d->alloc-1;
0329     d->offset--;
0330
0331     if (d->count != d->alloc)
0332         d->count++;
0333     else
0334         (d->array + d->start)->~T();
0335
0336     new (d->array + d->start) T(std::move(value));
0337 }
0338
0339 template<typename T>
0340 void QContiguousCache<T>::prepend(const T &value)
0341 {
0342     if (!d->alloc)
0343         return;     // zero capacity
0344     detach();
0345     if (d->start)
0346         d->start--;
0347     else
0348         d->start = d->alloc-1;
0349     d->offset--;
0350
0351     if (d->count != d->alloc)
0352         d->count++;
0353     else
0354         (d->array + d->start)->~T();
0355
0356     new (d->array + d->start) T(value);
0357 }
0358
0359 template<typename T>
0360 void QContiguousCache<T>::insert(qsizetype pos, T &&value)
0361 {
0362     Q_ASSERT_X(pos >= 0, "QContiguousCache<T>::insert", "index out of range");
0363     if (!d->alloc)
0364         return;     // zero capacity
0365     detach();
0366     if (containsIndex(pos)) {
0367         d->array[pos % d->alloc] = std::move(value);
0368     } else if (pos == d->offset-1)
0369         prepend(value);
0370     else if (pos == d->offset+d->count)
0371         append(value);
0372     else {
0373         // we don't leave gaps.
0374         clear();
0375         d->offset = pos;
0376         d->start = pos % d->alloc;
0377         d->count = 1;
0378         new (d->array + d->start) T(std::move(value));
0379     }
0380 }
0381
0382 template<typename T>
0383 void QContiguousCache<T>::insert(qsizetype pos, const T &value)
0384 {
0385     return insert(pos, T(value));
0386 }
0387 template <typename T>
0388 inline const T &QContiguousCache<T>::at(qsizetype pos) const
0389 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
0390 template <typename T>
0391 inline const T &QContiguousCache<T>::operator[](qsizetype pos) const
0392 { return at(pos); }
0393
0394 template <typename T>
0395 inline T &QContiguousCache<T>::operator[](qsizetype pos)
0396 {
0397     detach();
0398     if (!containsIndex(pos))
0399         insert(pos, T());
0400     return d->array[pos % d->alloc];
0401 }
0402
0403 template <typename T>
0404 inline void QContiguousCache<T>::removeFirst()
0405 {
0406     Q_ASSERT(d->count > 0);
0407     detach();
0408     d->count--;
0409     if (QTypeInfo<T>::isComplex)
0410         (d->array + d->start)->~T();
0411     d->start = (d->start + 1) % d->alloc;
0412     d->offset++;
0413 }
0414
0415 template <typename T>
0416 inline void QContiguousCache<T>::removeLast()
0417 {
0418     Q_ASSERT(d->count > 0);
0419     detach();
0420     d->count--;
0421     if (QTypeInfo<T>::isComplex)
0422         (d->array + (d->start + d->count) % d->alloc)->~T();
0423 }
0424
0425 template <typename T>
0426 inline T QContiguousCache<T>::takeFirst()
0427 { T t = std::move(first()); removeFirst(); return t; }
0428
0429 template <typename T>
0430 inline T QContiguousCache<T>::takeLast()
0431 { T t = std::move(last()); removeLast(); return t; }
0432
0433 QT_END_NAMESPACE
0434
0435 #endif