| /**************************************************************************** |
| ** |
| ** Copyright (C) 2015 The Qt Company Ltd. |
| ** Contact: http://www.qt.io/licensing/ |
| ** |
| ** This file is part of the QtCore module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL21$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see http://www.qt.io/terms-conditions. For further |
| ** information use the contact form at http://www.qt.io/contact-us. |
| ** |
| ** GNU Lesser General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU Lesser |
| ** General Public License version 2.1 or version 3 as published by the Free |
| ** Software Foundation and appearing in the file LICENSE.LGPLv21 and |
| ** LICENSE.LGPLv3 included in the packaging of this file. Please review the |
| ** following information to ensure the GNU Lesser General Public License |
| ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and |
| ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
| ** |
| ** As a special exception, The Qt Company gives you certain additional |
| ** rights. These rights are described in The Qt Company LGPL Exception |
| ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #ifndef QCONTIGUOUSCACHE_H |
| #define QCONTIGUOUSCACHE_H |
| |
| #include <QtCore/qatomic.h> |
| #include <limits.h> |
| #include <new> |
| |
| QT_BEGIN_NAMESPACE |
| |
| #undef QT_QCONTIGUOUSCACHE_DEBUG |
| |
| |
| struct Q_CORE_EXPORT QContiguousCacheData |
| { |
| QBasicAtomicInt ref; |
| int alloc; |
| int count; |
| int start; |
| int offset; |
| uint sharable : 1; |
| uint reserved : 31; |
| |
| // total is 24 bytes (HP-UX aCC: 40 bytes) |
| // the next entry is already aligned to 8 bytes |
| // there will be an 8 byte gap here if T requires 16-byte alignment |
| // (such as long double on 64-bit platforms, __int128, __float128) |
| |
| static QContiguousCacheData *allocateData(int size, int alignment); |
| static void freeData(QContiguousCacheData *data); |
| |
| #ifdef QT_QCONTIGUOUSCACHE_DEBUG |
| void dump() const; |
| #endif |
| }; |
| |
| template <typename T> |
| struct QContiguousCacheTypedData: private QContiguousCacheData |
| { |
| // private inheritance to avoid aliasing warningss |
| T array[1]; |
| |
| static inline void freeData(QContiguousCacheTypedData *data) { QContiguousCacheData::freeData(data); } |
| }; |
| |
| template<typename T> |
| class QContiguousCache { |
| typedef QContiguousCacheTypedData<T> Data; |
| union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; }; |
| public: |
| // STL compatibility |
| typedef T value_type; |
| typedef value_type* pointer; |
| typedef const value_type* const_pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef qptrdiff difference_type; |
| typedef int size_type; |
| |
| explicit QContiguousCache(int capacity = 0); |
| QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } |
| |
| inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) freeData(p); } |
| |
| inline void detach() { if (d->ref.load() != 1) detach_helper(); } |
| inline bool isDetached() const { return d->ref.load() == 1; } |
| #if QT_SUPPORTS(UNSHARABLE_CONTAINERS) |
| inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
| #endif |
| |
| QContiguousCache<T> &operator=(const QContiguousCache<T> &other); |
| #ifdef Q_COMPILER_RVALUE_REFS |
| inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other) |
| { qSwap(d, other.d); return *this; } |
| #endif |
| inline void swap(QContiguousCache<T> &other) { qSwap(d, other.d); } |
| bool operator==(const QContiguousCache<T> &other) const; |
| inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); } |
| |
| inline int capacity() const {return d->alloc; } |
| inline int count() const { return d->count; } |
| inline int size() const { return d->count; } |
| |
| inline bool isEmpty() const { return d->count == 0; } |
| inline bool isFull() const { return d->count == d->alloc; } |
| inline int available() const { return d->alloc - d->count; } |
| |
| void clear(); |
| void setCapacity(int size); |
| |
| const T &at(int pos) const; |
| T &operator[](int i); |
| const T &operator[](int i) const; |
| |
| void append(const T &value); |
| void prepend(const T &value); |
| void insert(int pos, const T &value); |
| |
| inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; } |
| inline int firstIndex() const { return d->offset; } |
| inline int lastIndex() const { return d->offset + d->count - 1; } |
| |
| inline const T &first() const { Q_ASSERT(!isEmpty()); return p->array[d->start]; } |
| inline const T &last() const { Q_ASSERT(!isEmpty()); return p->array[(d->start + d->count -1) % d->alloc]; } |
| inline T &first() { Q_ASSERT(!isEmpty()); detach(); return p->array[d->start]; } |
| inline T &last() { Q_ASSERT(!isEmpty()); detach(); return p->array[(d->start + d->count -1) % d->alloc]; } |
| |
| void removeFirst(); |
| T takeFirst(); |
| void removeLast(); |
| T takeLast(); |
| |
| inline bool areIndexesValid() const |
| { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; } |
| |
| inline void normalizeIndexes() { d->offset = d->start; } |
| |
| #ifdef QT_QCONTIGUOUSCACHE_DEBUG |
| void dump() const { p->dump(); } |
| #endif |
| private: |
| void detach_helper(); |
| |
| QContiguousCacheData *allocateData(int aalloc); |
| void freeData(Data *x); |
| int sizeOfTypedData() { |
| // this is more or less the same as sizeof(Data), except that it doesn't |
| // count the padding at the end |
| return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this); |
| } |
| int alignOfTypedData() const |
| { |
| return qMax<int>(sizeof(void*), Q_ALIGNOF(Data)); |
| } |
| }; |
| |
| template <typename T> |
| void QContiguousCache<T>::detach_helper() |
| { |
| union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
| |
| x.d = allocateData(d->alloc); |
| x.d->ref.store(1); |
| x.d->count = d->count; |
| x.d->start = d->start; |
| x.d->offset = d->offset; |
| x.d->alloc = d->alloc; |
| x.d->sharable = true; |
| x.d->reserved = 0; |
| |
| T *dest = x.p->array + x.d->start; |
| T *src = p->array + d->start; |
| int oldcount = x.d->count; |
| while (oldcount--) { |
| if (QTypeInfo<T>::isComplex) { |
| new (dest) T(*src); |
| } else { |
| *dest = *src; |
| } |
| dest++; |
| if (dest == x.p->array + x.d->alloc) |
| dest = x.p->array; |
| src++; |
| if (src == p->array + d->alloc) |
| src = p->array; |
| } |
| |
| if (!d->ref.deref()) |
| freeData(p); |
| d = x.d; |
| } |
| |
| template <typename T> |
| void QContiguousCache<T>::setCapacity(int asize) |
| { |
| if (asize == d->alloc) |
| return; |
| detach(); |
| union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
| x.d = allocateData(asize); |
| x.d->alloc = asize; |
| x.d->count = qMin(d->count, asize); |
| x.d->offset = d->offset + d->count - x.d->count; |
| if(asize) |
| x.d->start = x.d->offset % x.d->alloc; |
| else |
| x.d->start = 0; |
| |
| int oldcount = x.d->count; |
| if(oldcount) |
| { |
| T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc; |
| T *src = p->array + (d->start + d->count-1) % d->alloc; |
| while (oldcount--) { |
| if (QTypeInfo<T>::isComplex) { |
| new (dest) T(*src); |
| } else { |
| *dest = *src; |
| } |
| if (dest == x.p->array) |
| dest = x.p->array + x.d->alloc; |
| dest--; |
| if (src == p->array) |
| src = p->array + d->alloc; |
| src--; |
| } |
| } |
| /* free old */ |
| freeData(p); |
| d = x.d; |
| } |
| |
| template <typename T> |
| void QContiguousCache<T>::clear() |
| { |
| if (d->ref.load() == 1) { |
| if (QTypeInfo<T>::isComplex) { |
| int oldcount = d->count; |
| T * i = p->array + d->start; |
| T * e = p->array + d->alloc; |
| while (oldcount--) { |
| i->~T(); |
| i++; |
| if (i == e) |
| i = p->array; |
| } |
| } |
| d->count = d->start = d->offset = 0; |
| } else { |
| union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x; |
| x.d = allocateData(d->alloc); |
| x.d->ref.store(1); |
| x.d->alloc = d->alloc; |
| x.d->count = x.d->start = x.d->offset = 0; |
| x.d->sharable = true; |
| if (!d->ref.deref()) freeData(p); |
| d = x.d; |
| } |
| } |
| |
| template <typename T> |
| inline QContiguousCacheData *QContiguousCache<T>::allocateData(int aalloc) |
| { |
| return QContiguousCacheData::allocateData(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); |
| } |
| |
| template <typename T> |
| QContiguousCache<T>::QContiguousCache(int cap) |
| { |
| d = allocateData(cap); |
| d->ref.store(1); |
| d->alloc = cap; |
| d->count = d->start = d->offset = 0; |
| d->sharable = true; |
| } |
| |
| template <typename T> |
| QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other) |
| { |
| other.d->ref.ref(); |
| if (!d->ref.deref()) |
| freeData(p); |
| d = other.d; |
| if (!d->sharable) |
| detach_helper(); |
| return *this; |
| } |
| |
| template <typename T> |
| bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const |
| { |
| if (other.d == d) |
| return true; |
| if (other.d->start != d->start |
| || other.d->count != d->count |
| || other.d->offset != d->offset |
| || other.d->alloc != d->alloc) |
| return false; |
| for (int i = firstIndex(); i <= lastIndex(); ++i) |
| if (!(at(i) == other.at(i))) |
| return false; |
| return true; |
| } |
| |
| template <typename T> |
| void QContiguousCache<T>::freeData(Data *x) |
| { |
| if (QTypeInfo<T>::isComplex) { |
| int oldcount = d->count; |
| T * i = p->array + d->start; |
| T * e = p->array + d->alloc; |
| while (oldcount--) { |
| i->~T(); |
| i++; |
| if (i == e) |
| i = p->array; |
| } |
| } |
| x->freeData(x); |
| } |
| template <typename T> |
| void QContiguousCache<T>::append(const T &value) |
| { |
| if (!d->alloc) |
| return; // zero capacity |
| detach(); |
| if (QTypeInfo<T>::isComplex) { |
| if (d->count == d->alloc) |
| (p->array + (d->start+d->count) % d->alloc)->~T(); |
| new (p->array + (d->start+d->count) % d->alloc) T(value); |
| } else { |
| p->array[(d->start+d->count) % d->alloc] = value; |
| } |
| |
| if (d->count == d->alloc) { |
| d->start++; |
| d->start %= d->alloc; |
| d->offset++; |
| } else { |
| d->count++; |
| } |
| } |
| |
| template<typename T> |
| void QContiguousCache<T>::prepend(const T &value) |
| { |
| if (!d->alloc) |
| return; // zero capacity |
| detach(); |
| if (d->start) |
| d->start--; |
| else |
| d->start = d->alloc-1; |
| d->offset--; |
| |
| if (d->count != d->alloc) |
| d->count++; |
| else |
| if (d->count == d->alloc) |
| (p->array + d->start)->~T(); |
| |
| if (QTypeInfo<T>::isComplex) |
| new (p->array + d->start) T(value); |
| else |
| p->array[d->start] = value; |
| } |
| |
| template<typename T> |
| void QContiguousCache<T>::insert(int pos, const T &value) |
| { |
| Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range"); |
| if (!d->alloc) |
| return; // zero capacity |
| detach(); |
| if (containsIndex(pos)) { |
| if (QTypeInfo<T>::isComplex) { |
| (p->array + pos % d->alloc)->~T(); |
| new (p->array + pos % d->alloc) T(value); |
| } else { |
| p->array[pos % d->alloc] = value; |
| } |
| } else if (pos == d->offset-1) |
| prepend(value); |
| else if (pos == d->offset+d->count) |
| append(value); |
| else { |
| // we don't leave gaps. |
| clear(); |
| d->offset = pos; |
| d->start = pos % d->alloc; |
| d->count = 1; |
| if (QTypeInfo<T>::isComplex) |
| new (p->array + d->start) T(value); |
| else |
| p->array[d->start] = value; |
| } |
| } |
| |
| template <typename T> |
| inline const T &QContiguousCache<T>::at(int pos) const |
| { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; } |
| template <typename T> |
| inline const T &QContiguousCache<T>::operator[](int pos) const |
| { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; } |
| |
| template <typename T> |
| inline T &QContiguousCache<T>::operator[](int pos) |
| { |
| detach(); |
| if (!containsIndex(pos)) |
| insert(pos, T()); |
| return p->array[pos % d->alloc]; |
| } |
| |
| template <typename T> |
| inline void QContiguousCache<T>::removeFirst() |
| { |
| Q_ASSERT(d->count > 0); |
| detach(); |
| d->count--; |
| if (QTypeInfo<T>::isComplex) |
| (p->array + d->start)->~T(); |
| d->start = (d->start + 1) % d->alloc; |
| d->offset++; |
| } |
| |
| template <typename T> |
| inline void QContiguousCache<T>::removeLast() |
| { |
| Q_ASSERT(d->count > 0); |
| detach(); |
| d->count--; |
| if (QTypeInfo<T>::isComplex) |
| (p->array + (d->start + d->count) % d->alloc)->~T(); |
| } |
| |
| template <typename T> |
| inline T QContiguousCache<T>::takeFirst() |
| { T t = first(); removeFirst(); return t; } |
| |
| template <typename T> |
| inline T QContiguousCache<T>::takeLast() |
| { T t = last(); removeLast(); return t; } |
| |
| QT_END_NAMESPACE |
| |
| #endif |