/**************************************************************************** ** ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). ** Contact: Nokia Corporation (qt-info@nokia.com) ** ** This file is part of the QtCore module of the Qt Toolkit. ** ** $QT_BEGIN_LICENSE:LGPL$ ** No Commercial Usage ** This file contains pre-release code and may not be distributed. ** You may use this file in accordance with the terms and conditions ** contained in the Technology Preview License Agreement accompanying ** this package. ** ** 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 as published by the Free Software ** Foundation and appearing in the file LICENSE.LGPL included in the ** packaging of this file. Please review the following information to ** ensure the GNU Lesser General Public License version 2.1 requirements ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. ** ** In addition, as a special exception, Nokia gives you certain ** additional rights. These rights are described in the Nokia Qt LGPL ** Exception version 1.1, included in the file LGPL_EXCEPTION.txt in this ** package. ** ** If you have questions regarding the use of this file, please contact ** Nokia at qt-info@nokia.com. ** ** ** ** ** ** ** ** ** $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; #ifdef QT_QCONTIGUOUSCACHE_DEBUG void dump() const; #endif }; template struct QContiguousCacheTypedData { QBasicAtomicInt ref; int alloc; int count; int start; int offset; uint sharable : 1; // uint unused : 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) T array[1]; }; template class QContiguousCache { typedef QContiguousCacheTypedData Data; union { QContiguousCacheData *p; QContiguousCacheTypedData *d; }; public: 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(d); } 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); 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 d->array[d->start]; } inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; } inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; } inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->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); } }; template void QContiguousCache::detach_helper() { union { QContiguousCacheData *p; QContiguousCacheTypedData *d; } x; x.p = 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; T *dest = x.d->array + x.d->start; T *src = d->array + d->start; int oldcount = x.d->count; while (oldcount--) { if (QTypeInfo::isComplex) { new (dest) T(*src); } else { *dest = *src; } dest++; if (dest == x.d->array + x.d->alloc) dest = x.d->array; src++; if (src == d->array + d->alloc) src = d->array; } if (!d->ref.deref()) free(d); d = x.d; } template void QContiguousCache::setCapacity(int asize) { if (asize == d->alloc) return; detach(); union { QContiguousCacheData *p; QContiguousCacheTypedData *d; } x; x.p = malloc(asize); x.d->alloc = asize; x.d->count = qMin(d->count, asize); x.d->offset = d->offset + d->count - x.d->count; x.d->start = x.d->offset % x.d->alloc; T *dest = x.d->array + (x.d->start + x.d->count-1) % x.d->alloc; T *src = d->array + (d->start + d->count-1) % d->alloc; int oldcount = x.d->count; while (oldcount--) { if (QTypeInfo::isComplex) { new (dest) T(*src); } else { *dest = *src; } if (dest == x.d->array) dest = x.d->array + x.d->alloc; dest--; if (src == d->array) src = d->array + d->alloc; src--; } /* free old */ free(d); d = x.d; } template void QContiguousCache::clear() { if (d->ref == 1) { if (QTypeInfo::isComplex) { int oldcount = d->count; T * i = d->array + d->start; T * e = d->array + d->alloc; while (oldcount--) { i->~T(); i++; if (i == e) i = d->array; } } d->count = d->start = d->offset = 0; } else { union { QContiguousCacheData *p; QContiguousCacheTypedData *d; } x; x.p = 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(d); d = x.d; } } template inline QContiguousCacheData *QContiguousCache::malloc(int aalloc) { return static_cast(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T))); } template QContiguousCache::QContiguousCache(int cap) { p = 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 = d->array + d->start; T * e = d->array + d->alloc; while (oldcount--) { i->~T(); i++; if (i == e) i = d->array; } } qFree(x); } template void QContiguousCache::append(const T &value) { detach(); if (QTypeInfo::isComplex) { if (d->count == d->alloc) (d->array + (d->start+d->count) % d->alloc)->~T(); new (d->array + (d->start+d->count) % d->alloc) T(value); } else { d->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) { 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) (d->array + d->start)->~T(); if (QTypeInfo::isComplex) new (d->array + d->start) T(value); else d->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"); detach(); if (containsIndex(pos)) { if(QTypeInfo::isComplex) new (d->array + pos % d->alloc) T(value); else d->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 (d->array + d->start) T(value); else d->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 d->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 d->array[pos % d->alloc]; } template inline T &QContiguousCache::operator[](int pos) { detach(); if (!containsIndex(pos)) insert(pos, T()); return d->array[pos % d->alloc]; } template inline void QContiguousCache::removeFirst() { Q_ASSERT(d->count > 0); detach(); d->count--; if (QTypeInfo::isComplex) (d->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) (d->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