Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 10:07:21 

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