diff options
Diffstat (limited to 'src/corelib/tools/qcontiguouscache.h')
| -rw-r--r-- | src/corelib/tools/qcontiguouscache.h | 466 |
1 files changed, 466 insertions, 0 deletions
diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h new file mode 100644 index 0000000000..7880c2e411 --- /dev/null +++ b/src/corelib/tools/qcontiguouscache.h @@ -0,0 +1,466 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** 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 <QtCore/qatomic.h> +#include <limits.h> +#include <new> + +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 <typename T> +struct QContiguousCacheTypedData: private QContiguousCacheData +{ + // private inheritance to avoid aliasing warningss + T array[1]; + + static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(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()) 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<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 *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<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this); + } + int alignOfTypedData() const + { +#ifdef Q_ALIGNOF + return qMax<int>(sizeof(void*), Q_ALIGNOF(Data)); +#else + return 0; +#endif + } +}; + +template <typename T> +void QContiguousCache<T>::detach_helper() +{ + union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *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<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()) + free(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 = 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<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 */ + free(p); + d = x.d; +} + +template <typename T> +void QContiguousCache<T>::clear() +{ + if (d->ref == 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 = 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 <typename T> +inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc) +{ + return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData()); +} + +template <typename T> +QContiguousCache<T>::QContiguousCache(int cap) +{ + d = malloc(cap); + d->ref = 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()) + free(d); + 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>::free(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->free(x); +} +template <typename T> +void QContiguousCache<T>::append(const T &value) +{ + 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) +{ + 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"); + detach(); + if (containsIndex(pos)) { + if(QTypeInfo<T>::isComplex) + 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 + +QT_END_HEADER + +#endif |