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->ref.storeRelaxed(1);
0156     x->count = d->count;
0157     x->start = d->start;
0158     x->offset = d->offset;
0159     x->alloc = d->alloc;
0160
0161     T *dest = x->array + x->start;
0162     T *src = d->array + d->start;
0163     qsizetype oldcount = x->count;
0164     while (oldcount--) {
0165         new (dest) T(*src);
0166         dest++;
0167         if (dest == x->array + x->alloc)
0168             dest = x->array;
0169         src++;
0170         if (src == d->array + d->alloc)
0171             src = d->array;
0172     }
0173
0174     if (!d->ref.deref())
0175         freeData(d);
0176     d = x;
0177 }
0178
0179 template <typename T>
0180 void QContiguousCache<T>::setCapacity(qsizetype asize)
0181 {
0182     Q_ASSERT(asize >= 0);
0183     if (asize == d->alloc)
0184         return;
0185     detach();
0186     Data *x = allocateData(asize);
0187     x->ref.storeRelaxed(1);
0188     x->alloc = asize;
0189     x->count = qMin(d->count, asize);
0190     x->offset = d->offset + d->count - x->count;
0191     if (asize)
0192         x->start = x->offset % x->alloc;
0193     else
0194         x->start = 0;
0195
0196     qsizetype oldcount = x->count;
0197     if (oldcount)
0198     {
0199         T *dest = x->array + (x->start + x->count-1) % x->alloc;
0200         T *src = d->array + (d->start + d->count-1) % d->alloc;
0201         while (oldcount--) {
0202             new (dest) T(*src);
0203             if (dest == x->array)
0204                 dest = x->array + x->alloc;
0205             dest--;
0206             if (src == d->array)
0207                 src = d->array + d->alloc;
0208             src--;
0209         }
0210     }
0211     /* free old */
0212     freeData(d);
0213     d = x;
0214 }
0215
0216 template <typename T>
0217 void QContiguousCache<T>::clear()
0218 {
0219     if (d->ref.loadRelaxed() == 1) {
0220         if (QTypeInfo<T>::isComplex) {
0221             qsizetype oldcount = d->count;
0222             T * i = d->array + d->start;
0223             T * e = d->array + d->alloc;
0224             while (oldcount--) {
0225                 i->~T();
0226                 i++;
0227                 if (i == e)
0228                     i = d->array;
0229             }
0230         }
0231         d->count = d->start = d->offset = 0;
0232     } else {
0233         Data *x = allocateData(d->alloc);
0234         x->ref.storeRelaxed(1);
0235         x->alloc = d->alloc;
0236         x->count = x->start = x->offset = 0;
0237         if (!d->ref.deref())
0238             freeData(d);
0239         d = x;
0240     }
0241 }
0242
0243 template <typename T>
0244 inline typename QContiguousCache<T>::Data *QContiguousCache<T>::allocateData(qsizetype aalloc)
0245 {
0246     return static_cast<Data *>(QContiguousCacheData::allocateData(sizeof(Data) + (aalloc - 1) * sizeof(T), alignof(Data)));
0247 }
0248
0249 template <typename T>
0250 QContiguousCache<T>::QContiguousCache(qsizetype cap)
0251 {
0252     Q_ASSERT(cap >= 0);
0253     d = allocateData(cap);
0254     d->ref.storeRelaxed(1);
0255     d->alloc = cap;
0256     d->count = d->start = d->offset = 0;
0257 }
0258
0259 template <typename T>
0260 QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
0261 {
0262     other.d->ref.ref();
0263     if (!d->ref.deref())
0264         freeData(d);
0265     d = other.d;
0266     return *this;
0267 }
0268
0269 template <typename T>
0270 void QContiguousCache<T>::freeData(Data *x)
0271 {
0272     if (QTypeInfo<T>::isComplex) {
0273         qsizetype oldcount = d->count;
0274         T * i = d->array + d->start;
0275         T * e = d->array + d->alloc;
0276         while (oldcount--) {
0277             i->~T();
0278             i++;
0279             if (i == e)
0280                 i = d->array;
0281         }
0282     }
0283     Data::freeData(x);
0284 }
0285 template <typename T>
0286 void QContiguousCache<T>::append(T &&value)
0287 {
0288     if (!d->alloc)
0289         return;     // zero capacity
0290     detach();
0291     if (d->count == d->alloc)
0292         (d->array + (d->start+d->count) % d->alloc)->~T();
0293     new (d->array + (d->start+d->count) % d->alloc) T(std::move(value));
0294
0295     if (d->count == d->alloc) {
0296         d->start++;
0297         d->start %= d->alloc;
0298         d->offset++;
0299     } else {
0300         d->count++;
0301     }
0302 }
0303
0304 template <typename T>
0305 void QContiguousCache<T>::append(const T &value)
0306 {
0307     if (!d->alloc)
0308         return;     // zero capacity
0309     detach();
0310     if (d->count == d->alloc)
0311         (d->array + (d->start+d->count) % d->alloc)->~T();
0312     new (d->array + (d->start+d->count) % d->alloc) T(value);
0313
0314     if (d->count == d->alloc) {
0315         d->start++;
0316         d->start %= d->alloc;
0317         d->offset++;
0318     } else {
0319         d->count++;
0320     }
0321 }
0322
0323 template<typename T>
0324 void QContiguousCache<T>::prepend(T &&value)
0325 {
0326     if (!d->alloc)
0327         return;     // zero capacity
0328     detach();
0329     if (d->start)
0330         d->start--;
0331     else
0332         d->start = d->alloc-1;
0333     d->offset--;
0334
0335     if (d->count != d->alloc)
0336         d->count++;
0337     else
0338         (d->array + d->start)->~T();
0339
0340     new (d->array + d->start) T(std::move(value));
0341 }
0342
0343 template<typename T>
0344 void QContiguousCache<T>::prepend(const T &value)
0345 {
0346     if (!d->alloc)
0347         return;     // zero capacity
0348     detach();
0349     if (d->start)
0350         d->start--;
0351     else
0352         d->start = d->alloc-1;
0353     d->offset--;
0354
0355     if (d->count != d->alloc)
0356         d->count++;
0357     else
0358         (d->array + d->start)->~T();
0359
0360     new (d->array + d->start) T(value);
0361 }
0362
0363 template<typename T>
0364 void QContiguousCache<T>::insert(qsizetype pos, T &&value)
0365 {
0366     Q_ASSERT_X(pos >= 0, "QContiguousCache<T>::insert", "index out of range");
0367     if (!d->alloc)
0368         return;     // zero capacity
0369     detach();
0370     if (containsIndex(pos)) {
0371         d->array[pos % d->alloc] = std::move(value);
0372     } else if (pos == d->offset-1)
0373         prepend(value);
0374     else if (pos == d->offset+d->count)
0375         append(value);
0376     else {
0377         // we don't leave gaps.
0378         clear();
0379         d->offset = pos;
0380         d->start = pos % d->alloc;
0381         d->count = 1;
0382         new (d->array + d->start) T(std::move(value));
0383     }
0384 }
0385
0386 template<typename T>
0387 void QContiguousCache<T>::insert(qsizetype pos, const T &value)
0388 {
0389     return insert(pos, T(value));
0390 }
0391 template <typename T>
0392 inline const T &QContiguousCache<T>::at(qsizetype pos) const
0393 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }
0394 template <typename T>
0395 inline const T &QContiguousCache<T>::operator[](qsizetype pos) const
0396 { return at(pos); }
0397
0398 template <typename T>
0399 inline T &QContiguousCache<T>::operator[](qsizetype pos)
0400 {
0401     detach();
0402     if (!containsIndex(pos))
0403         insert(pos, T());
0404     return d->array[pos % d->alloc];
0405 }
0406
0407 template <typename T>
0408 inline void QContiguousCache<T>::removeFirst()
0409 {
0410     Q_ASSERT(d->count > 0);
0411     detach();
0412     d->count--;
0413     if (QTypeInfo<T>::isComplex)
0414         (d->array + d->start)->~T();
0415     d->start = (d->start + 1) % d->alloc;
0416     d->offset++;
0417 }
0418
0419 template <typename T>
0420 inline void QContiguousCache<T>::removeLast()
0421 {
0422     Q_ASSERT(d->count > 0);
0423     detach();
0424     d->count--;
0425     if (QTypeInfo<T>::isComplex)
0426         (d->array + (d->start + d->count) % d->alloc)->~T();
0427 }
0428
0429 template <typename T>
0430 inline T QContiguousCache<T>::takeFirst()
0431 { T t = std::move(first()); removeFirst(); return t; }
0432
0433 template <typename T>
0434 inline T QContiguousCache<T>::takeLast()
0435 { T t = std::move(last()); removeLast(); return t; }
0436
0437 QT_END_NAMESPACE
0438
0439 #endif