Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-08-27 09:33:02 

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

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!