summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qcontiguouscache.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qcontiguouscache.h')
-rw-r--r--src/corelib/tools/qcontiguouscache.h314
1 files changed, 155 insertions, 159 deletions
diff --git a/src/corelib/tools/qcontiguouscache.h b/src/corelib/tools/qcontiguouscache.h
index 7b74b4f526..81361f219a 100644
--- a/src/corelib/tools/qcontiguouscache.h
+++ b/src/corelib/tools/qcontiguouscache.h
@@ -52,19 +52,12 @@ QT_BEGIN_NAMESPACE
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);
+ qsizetype alloc;
+ qsizetype count;
+ qsizetype start;
+ qsizetype offset;
+
+ static QContiguousCacheData *allocateData(qsizetype size, qsizetype alignment);
static void freeData(QContiguousCacheData *data);
#ifdef QT_QCONTIGUOUSCACHE_DEBUG
@@ -73,18 +66,15 @@ struct Q_CORE_EXPORT QContiguousCacheData
};
template <typename T>
-struct QContiguousCacheTypedData: private QContiguousCacheData
+struct QContiguousCacheTypedData : public 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; };
+ Data *d;
public:
// STL compatibility
typedef T value_type;
@@ -93,18 +83,15 @@ public:
typedef value_type& reference;
typedef const value_type& const_reference;
typedef qptrdiff difference_type;
- typedef int size_type;
+ typedef qsizetype size_type;
- explicit QContiguousCache(int capacity = 0);
- QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
+ explicit QContiguousCache(qsizetype capacity = 0);
+ QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); }
- inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) freeData(p); }
+ inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) freeData(d); }
inline void detach() { if (d->ref.loadRelaxed() != 1) detach_helper(); }
inline bool isDetached() const { return d->ref.loadRelaxed() == 1; }
-#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
- inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
-#endif
QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other) noexcept
@@ -113,139 +100,122 @@ public:
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 qsizetype capacity() const {return d->alloc; }
+ inline qsizetype count() const { return d->count; }
+ inline qsizetype 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; }
+ inline qsizetype available() const { return d->alloc - d->count; }
void clear();
- void setCapacity(int size);
+ void setCapacity(qsizetype size);
- const T &at(int pos) const;
- T &operator[](int i);
- const T &operator[](int i) const;
+ const T &at(qsizetype pos) const;
+ T &operator[](qsizetype i);
+ const T &operator[](qsizetype i) const;
+ void append(T &&value);
void append(const T &value);
+ void prepend(T &&value);
void prepend(const T &value);
- void insert(int pos, const T &value);
+ void insert(qsizetype pos, T &&value);
+ void insert(qsizetype 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 bool containsIndex(qsizetype pos) const { return pos >= d->offset && pos - d->offset < d->count; }
+ inline qsizetype firstIndex() const { return d->offset; }
+ inline qsizetype 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]; }
+ 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();
+ // Use extra parentheses around max to avoid expanding it if it is a macro.
inline bool areIndexesValid() const
- { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
+ { return d->offset >= 0 && d->offset < (std::numeric_limits<qsizetype>::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(); }
+ void dump() const { d->dump(); }
#endif
private:
void detach_helper();
- QContiguousCacheData *allocateData(int aalloc);
+ Data *allocateData(qsizetype 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.storeRelaxed(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;
+ Data *x = allocateData(d->alloc);
+ x->ref.storeRelaxed(1);
+ x->count = d->count;
+ x->start = d->start;
+ x->offset = d->offset;
+ x->alloc = d->alloc;
+
+ T *dest = x->array + x->start;
+ T *src = d->array + d->start;
+ qsizetype oldcount = x->count;
while (oldcount--) {
- if (QTypeInfo<T>::isComplex) {
- new (dest) T(*src);
- } else {
- *dest = *src;
- }
+ new (dest) T(*src);
dest++;
- if (dest == x.p->array + x.d->alloc)
- dest = x.p->array;
+ if (dest == x->array + x->alloc)
+ dest = x->array;
src++;
- if (src == p->array + d->alloc)
- src = p->array;
+ if (src == d->array + d->alloc)
+ src = d->array;
}
if (!d->ref.deref())
- freeData(p);
- d = x.d;
+ freeData(d);
+ d = x;
}
template <typename T>
-void QContiguousCache<T>::setCapacity(int asize)
+void QContiguousCache<T>::setCapacity(qsizetype asize)
{
Q_ASSERT(asize >= 0);
if (asize == d->alloc)
return;
detach();
- union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
- x.d = allocateData(asize);
- x.d->ref.storeRelaxed(1);
- x.d->alloc = asize;
- x.d->count = qMin(d->count, asize);
- x.d->offset = d->offset + d->count - x.d->count;
+ Data *x = allocateData(asize);
+ x->ref.storeRelaxed(1);
+ x->alloc = asize;
+ x->count = qMin(d->count, asize);
+ x->offset = d->offset + d->count - x->count;
if(asize)
- x.d->start = x.d->offset % x.d->alloc;
+ x->start = x->offset % x->alloc;
else
- x.d->start = 0;
+ x->start = 0;
- int oldcount = x.d->count;
+ qsizetype oldcount = x->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;
+ T *dest = x->array + (x->start + x->count-1) % x->alloc;
+ T *src = d->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;
+ new (dest) T(*src);
+ if (dest == x->array)
+ dest = x->array + x->alloc;
dest--;
- if (src == p->array)
- src = p->array + d->alloc;
+ if (src == d->array)
+ src = d->array + d->alloc;
src--;
}
}
/* free old */
- freeData(p);
- d = x.d;
+ freeData(d);
+ d = x;
}
template <typename T>
@@ -253,44 +223,42 @@ void QContiguousCache<T>::clear()
{
if (d->ref.loadRelaxed() == 1) {
if (QTypeInfo<T>::isComplex) {
- int oldcount = d->count;
- T * i = p->array + d->start;
- T * e = p->array + d->alloc;
+ qsizetype oldcount = d->count;
+ T * i = d->array + d->start;
+ T * e = d->array + d->alloc;
while (oldcount--) {
i->~T();
i++;
if (i == e)
- i = p->array;
+ i = d->array;
}
}
d->count = d->start = d->offset = 0;
} else {
- union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
- x.d = allocateData(d->alloc);
- x.d->ref.storeRelaxed(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;
+ Data *x = allocateData(d->alloc);
+ x->ref.storeRelaxed(1);
+ x->alloc = d->alloc;
+ x->count = x->start = x->offset = 0;
+ if (!d->ref.deref())
+ freeData(d);
+ d = x;
}
}
template <typename T>
-inline QContiguousCacheData *QContiguousCache<T>::allocateData(int aalloc)
+inline typename QContiguousCache<T>::Data *QContiguousCache<T>::allocateData(qsizetype aalloc)
{
- return QContiguousCacheData::allocateData(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
+ return static_cast<Data *>(QContiguousCacheData::allocateData(sizeof(Data) + (aalloc - 1) * sizeof(T), alignof(Data)));
}
template <typename T>
-QContiguousCache<T>::QContiguousCache(int cap)
+QContiguousCache<T>::QContiguousCache(qsizetype cap)
{
Q_ASSERT(cap >= 0);
d = allocateData(cap);
d->ref.storeRelaxed(1);
d->alloc = cap;
d->count = d->start = d->offset = 0;
- d->sharable = true;
}
template <typename T>
@@ -298,10 +266,8 @@ QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &o
{
other.d->ref.ref();
if (!d->ref.deref())
- freeData(p);
+ freeData(d);
d = other.d;
- if (!d->sharable)
- detach_helper();
return *this;
}
@@ -315,7 +281,7 @@ bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
|| other.d->offset != d->offset
|| other.d->alloc != d->alloc)
return false;
- for (int i = firstIndex(); i <= lastIndex(); ++i)
+ for (qsizetype i = firstIndex(); i <= lastIndex(); ++i)
if (!(at(i) == other.at(i)))
return false;
return true;
@@ -325,31 +291,46 @@ 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;
+ qsizetype oldcount = d->count;
+ T * i = d->array + d->start;
+ T * e = d->array + d->alloc;
while (oldcount--) {
i->~T();
i++;
if (i == e)
- i = p->array;
+ i = d->array;
}
}
- x->freeData(x);
+ Data::freeData(x);
}
template <typename T>
-void QContiguousCache<T>::append(const T &value)
+void QContiguousCache<T>::append(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);
+ if (d->count == d->alloc)
+ (d->array + (d->start+d->count) % d->alloc)->~T();
+ new (d->array + (d->start+d->count) % d->alloc) T(std::move(value));
+
+ if (d->count == d->alloc) {
+ d->start++;
+ d->start %= d->alloc;
+ d->offset++;
} else {
- p->array[(d->start+d->count) % d->alloc] = value;
+ d->count++;
}
+}
+
+template <typename T>
+void QContiguousCache<T>::append(const T &value)
+{
+ if (!d->alloc)
+ return; // zero capacity
+ detach();
+ 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);
if (d->count == d->alloc) {
d->start++;
@@ -361,7 +342,7 @@ void QContiguousCache<T>::append(const T &value)
}
template<typename T>
-void QContiguousCache<T>::prepend(const T &value)
+void QContiguousCache<T>::prepend(T &&value)
{
if (!d->alloc)
return; // zero capacity
@@ -376,28 +357,41 @@ void QContiguousCache<T>::prepend(const T &value)
d->count++;
else
if (d->count == d->alloc)
- (p->array + d->start)->~T();
+ (d->array + d->start)->~T();
- if (QTypeInfo<T>::isComplex)
- new (p->array + d->start) T(value);
+ new (d->array + d->start) T(std::move(value));
+}
+
+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
- p->array[d->start] = value;
+ if (d->count == d->alloc)
+ (d->array + d->start)->~T();
+
+ new (d->array + d->start) T(value);
}
template<typename T>
-void QContiguousCache<T>::insert(int pos, const T &value)
+void QContiguousCache<T>::insert(qsizetype pos, T &&value)
{
- Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
+ Q_ASSERT_X(pos >= 0, "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;
- }
+ d->array[pos % d->alloc] = std::move(value);
} else if (pos == d->offset-1)
prepend(value);
else if (pos == d->offset+d->count)
@@ -408,27 +402,29 @@ void QContiguousCache<T>::insert(int pos, const T &value)
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;
+ new (d->array + d->start) T(std::move(value));
}
}
+template<typename T>
+void QContiguousCache<T>::insert(qsizetype pos, const T &value)
+{
+ return insert(pos, T(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]; }
+inline const T &QContiguousCache<T>::at(qsizetype pos) const
+{ Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->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]; }
+inline const T &QContiguousCache<T>::operator[](qsizetype pos) const
+{ return at(pos); }
template <typename T>
-inline T &QContiguousCache<T>::operator[](int pos)
+inline T &QContiguousCache<T>::operator[](qsizetype pos)
{
detach();
if (!containsIndex(pos))
insert(pos, T());
- return p->array[pos % d->alloc];
+ return d->array[pos % d->alloc];
}
template <typename T>
@@ -438,7 +434,7 @@ inline void QContiguousCache<T>::removeFirst()
detach();
d->count--;
if (QTypeInfo<T>::isComplex)
- (p->array + d->start)->~T();
+ (d->array + d->start)->~T();
d->start = (d->start + 1) % d->alloc;
d->offset++;
}
@@ -450,16 +446,16 @@ inline void QContiguousCache<T>::removeLast()
detach();
d->count--;
if (QTypeInfo<T>::isComplex)
- (p->array + (d->start + d->count) % d->alloc)->~T();
+ (d->array + (d->start + d->count) % d->alloc)->~T();
}
template <typename T>
inline T QContiguousCache<T>::takeFirst()
-{ T t = first(); removeFirst(); return t; }
+{ T t = std::move(first()); removeFirst(); return t; }
template <typename T>
inline T QContiguousCache<T>::takeLast()
-{ T t = last(); removeLast(); return t; }
+{ T t = std::move(last()); removeLast(); return t; }
QT_END_NAMESPACE
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-19 19:32:55 +0000