/**************************************************************************** ** ** 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:LGPL$ ** 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. ** ** GNU General Public License Usage ** Alternatively, this file may be used under the terms of the GNU ** General Public License version 3.0 as published by the Free Software ** Foundation and appearing in the file LICENSE.GPL included in the ** packaging of this file. Please review the following information to ** ensure the GNU General Public License version 3.0 requirements will be ** met: http://www.gnu.org/copyleft/gpl.html. ** ** $QT_END_LICENSE$ ** ****************************************************************************/ #ifndef QCONTIGUOUSCACHE_H #define QCONTIGUOUSCACHE_H #include #include #include QT_BEGIN_HEADER QT_BEGIN_NAMESPACE #undef QT_QCONTIGUOUSCACHE_DEBUG QT_MODULE(Core) 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 *allocate(int size, int alignment); static void free(QContiguousCacheData *data); #ifdef QT_QCONTIGUOUSCACHE_DEBUG void dump() const; #endif }; template struct QContiguousCacheTypedData: private QContiguousCacheData { // private inheritance to avoid aliasing warningss T array[1]; static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(data); } }; template class QContiguousCache { typedef QContiguousCacheTypedData Data; union { QContiguousCacheData *d; QContiguousCacheTypedData *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 &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); } inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(p); } inline void detach() { if (d->ref != 1) detach_helper(); } inline bool isDetached() const { return d->ref == 1; } inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } QContiguousCache &operator=(const QContiguousCache &other); #ifdef Q_COMPILER_RVALUE_REFS inline QContiguousCache &operator=(QContiguousCache &&other) { qSwap(d, other.d); return *this; } #endif inline void swap(QContiguousCache &other) { qSwap(d, other.d); } bool operator==(const QContiguousCache &other) const; inline bool operator!=(const QContiguousCache &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 *malloc(int aalloc); void free(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(&(reinterpret_cast(this))->array[1]) - reinterpret_cast(this); } int alignOfTypedData() const { #ifdef Q_ALIGNOF return qMax(sizeof(void*), Q_ALIGNOF(Data)); #else return 0; #endif } }; template void QContiguousCache::detach_helper() { union { QContiguousCacheData *d; QContiguousCacheTypedData *p; } x; x.d = malloc(d->alloc); x.d->ref = 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::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()) free(p); d = x.d; } template void QContiguousCache::setCapacity(int asize) { if (asize == d->alloc) return; detach(); union { QContiguousCacheData *d; QContiguousCacheTypedData *p; } x; x.d = malloc(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::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 */ free(p); d = x.d; } template void QContiguousCache::clear() { if (d->ref == 1) { if (QTypeInfo::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 *p; } x; x.d = malloc(d->alloc); x.d->ref = 1; x.d->alloc = d->alloc; x.d->count = x.d->start = x.d->offset = 0; x.d->sharable = true; if (!d->ref.deref()) free(p); d = x.d; } } template inline QContiguousCacheData *QContiguousCache::malloc(int aalloc) { return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); } template QContiguousCache::QContiguousCache(int cap) { d = malloc(cap); d->ref = 1; d->alloc = cap; d->count = d->start = d->offset = 0; d->sharable = true; } template QContiguousCache &QContiguousCache::operator=(const QContiguousCache &other) { other.d->ref.ref(); if (!d->ref.deref()) free(d); d = other.d; if (!d->sharable) detach_helper(); return *this; } template bool QContiguousCache::operator==(const QContiguousCache &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 void QContiguousCache::free(Data *x) { if (QTypeInfo::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->free(x); } template void QContiguousCache::append(const T &value) { if (!d->alloc) return; // zero capacity detach(); if (QTypeInfo::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 void QContiguousCache::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::isComplex) new (p->array + d->start) T(value); else p->array[d->start] = value; } template void QContiguousCache::insert(int pos, const T &value) { Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache::insert", "index out of range"); if (!d->alloc) return; // zero capacity detach(); if (containsIndex(pos)) { if (QTypeInfo::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::isComplex) new (p->array + d->start) T(value); else p->array[d->start] = value; } } template inline const T &QContiguousCache::at(int pos) const { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache::at", "index out of range"); return p->array[pos % d->alloc]; } template inline const T &QContiguousCache::operator[](int pos) const { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache::at", "index out of range"); return p->array[pos % d->alloc]; } template inline T &QContiguousCache::operator[](int pos) { detach(); if (!containsIndex(pos)) insert(pos, T()); return p->array[pos % d->alloc]; } template inline void QContiguousCache::removeFirst() { Q_ASSERT(d->count > 0); detach(); d->count--; if (QTypeInfo::isComplex) (p->array + d->start)->~T(); d->start = (d->start + 1) % d->alloc; d->offset++; } template inline void QContiguousCache::removeLast() { Q_ASSERT(d->count > 0); detach(); d->count--; if (QTypeInfo::isComplex) (p->array + (d->start + d->count) % d->alloc)->~T(); } template inline T QContiguousCache::takeFirst() { T t = first(); removeFirst(); return t; } template inline T QContiguousCache::takeLast() { T t = last(); removeLast(); return t; } QT_END_NAMESPACE QT_END_HEADER #endif