- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# qcontiguouscache.h

Go to the documentation of this file.

    00001 /****************************************************************************
    00002 **
    00003 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
    00004 ** All rights reserved.
    00005 ** Contact: Nokia Corporation (qt-info@nokia.com)
    00006 **
    00007 ** This file is part of the QtCore module of the Qt Toolkit.
    00008 **
    00009 ** $QT_BEGIN_LICENSE:LGPL$
    00010 ** Commercial Usage
    00011 ** Licensees holding valid Qt Commercial licenses may use this file in
    00012 ** accordance with the Qt Commercial License Agreement provided with the
    00013 ** Software or, alternatively, in accordance with the terms contained in
    00014 ** a written agreement between you and Nokia.
    00015 **
    00016 ** GNU Lesser General Public License Usage
    00017 ** Alternatively, this file may be used under the terms of the GNU Lesser
    00018 ** General Public License version 2.1 as published by the Free Software
    00019 ** Foundation and appearing in the file LICENSE.LGPL included in the
    00020 ** packaging of this file.  Please review the following information to
    00021 ** ensure the GNU Lesser General Public License version 2.1 requirements
    00022 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
    00023 **
    00024 ** In addition, as a special exception, Nokia gives you certain additional
    00025 ** rights.  These rights are described in the Nokia Qt LGPL Exception
    00026 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this module.
    00027 **
    00028 ** GNU General Public License Usage
    00029 ** Alternatively, this file may be used under the terms of the GNU
    00030 ** General Public License version 3.0 as published by the Free Software
    00031 ** Foundation and appearing in the file LICENSE.GPL included in the
    00032 ** packaging of this file.  Please review the following information to
    00033 ** ensure the GNU General Public License version 3.0 requirements will be
    00034 ** met: http://www.gnu.org/copyleft/gpl.html.
    00035 **
    00036 ** If you have questions regarding the use of this file, please contact
    00037 ** Nokia at qt-info@nokia.com.
    00038 ** $QT_END_LICENSE$
    00039 **
    00040 ****************************************************************************/
    00041
    00042 #ifndef QCONTIGUOUSCACHE_H
    00043 #define QCONTIGUOUSCACHE_H
    00044
    00045 #include <QtCore/qatomic.h>
    00046 #include <limits.h>
    00047 #include <new>
    00048
    00049 QT_BEGIN_HEADER
    00050
    00051 QT_BEGIN_NAMESPACE
    00052
    00053 #undef QT_QCONTIGUOUSCACHE_DEBUG
    00054 QT_MODULE(Core)
    00055
    00056
    00057 struct Q_CORE_EXPORT QContiguousCacheData
    00058 {
    00059     QBasicAtomicInt ref;
    00060     int alloc;
    00061     int count;
    00062     int start;
    00063     int offset;
    00064     uint sharable : 1;
    00065     uint reserved : 31;
    00066
    00067     // total is 24 bytes (HP-UX aCC: 40 bytes)
    00068     // the next entry is already aligned to 8 bytes
    00069     // there will be an 8 byte gap here if T requires 16-byte alignment
    00070     //  (such as long double on 64-bit platforms, __int128, __float128)
    00071
    00072     static QContiguousCacheData *allocate(int size, int alignment);
    00073     static void free(QContiguousCacheData *data);
    00074
    00075 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
    00076     void dump() const;
    00077 #endif
    00078 };
    00079
    00080 template <typename T>
    00081 struct QContiguousCacheTypedData: private QContiguousCacheData
    00082 {
    00083     // private inheritance to avoid aliasing warningss
    00084     T array[1];
    00085
    00086     static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(data); }
    00087 };
    00088
    00089 template<typename T>
    00090 class QContiguousCache {
    00091     typedef QContiguousCacheTypedData<T> Data;
    00092     union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; };
    00093 public:
    00094     // STL compatibility
    00095     typedef T value_type;
    00096     typedef value_type* pointer;
    00097     typedef const value_type* const_pointer;
    00098     typedef value_type& reference;
    00099     typedef const value_type& const_reference;
    00100     typedef qptrdiff difference_type;
    00101     typedef int size_type;
    00102
    00103     explicit QContiguousCache(int capacity = 0);
    00104     QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
    00105
    00106     inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(p); }
    00107
    00108     inline void detach() { if (d->ref != 1) detach_helper(); }
    00109     inline bool isDetached() const { return d->ref == 1; }
    00110     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
    00111
    00112     QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
    00113     bool operator==(const QContiguousCache<T> &other) const;
    00114     inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
    00115
    00116     inline int capacity() const {return d->alloc; }
    00117     inline int count() const { return d->count; }
    00118     inline int size() const { return d->count; }
    00119
    00120     inline bool isEmpty() const { return d->count == 0; }
    00121     inline bool isFull() const { return d->count == d->alloc; }
    00122     inline int available() const { return d->alloc - d->count; }
    00123
    00124     void clear();
    00125     void setCapacity(int size);
    00126
    00127     const T &at(int pos) const;
    00128     T &operator[](int i);
    00129     const T &operator[](int i) const;
    00130
    00131     void append(const T &value);
    00132     void prepend(const T &value);
    00133     void insert(int pos, const T &value);
    00134
    00135     inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
    00136     inline int firstIndex() const { return d->offset; }
    00137     inline int lastIndex() const { return d->offset + d->count - 1; }
    00138
    00139     inline const T &first() const { Q_ASSERT(!isEmpty()); return p->array[d->start]; }
    00140     inline const T &last() const { Q_ASSERT(!isEmpty()); return p->array[(d->start + d->count -1) % d->alloc]; }
    00141     inline T &first() { Q_ASSERT(!isEmpty()); detach(); return p->array[d->start]; }
    00142     inline T &last() { Q_ASSERT(!isEmpty()); detach(); return p->array[(d->start + d->count -1) % d->alloc]; }
    00143
    00144     void removeFirst();
    00145     T takeFirst();
    00146     void removeLast();
    00147     T takeLast();
    00148
    00149     inline bool areIndexesValid() const
    00150     { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
    00151
    00152     inline void normalizeIndexes() { d->offset = d->start; }
    00153
    00154 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
    00155     void dump() const { p->dump(); }
    00156 #endif
    00157 private:
    00158     void detach_helper();
    00159
    00160     QContiguousCacheData *malloc(int aalloc);
    00161     void free(Data *x);
    00162     int sizeOfTypedData() {
    00163         // this is more or less the same as sizeof(Data), except that it doesn't
    00164         // count the padding at the end
    00165         return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
    00166     }
    00167     int alignOfTypedData() const
    00168     {
    00169 #ifdef Q_ALIGNOF
    00170         return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
    00171 #else
    00172         return 0;
    00173 #endif
    00174     }
    00175 };
    00176
    00177 template <typename T>
    00178 void QContiguousCache<T>::detach_helper()
    00179 {
    00180     union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
    00181
    00182     x.d = malloc(d->alloc);
    00183     x.d->ref = 1;
    00184     x.d->count = d->count;
    00185     x.d->start = d->start;
    00186     x.d->offset = d->offset;
    00187     x.d->alloc = d->alloc;
    00188     x.d->sharable = true;
    00189     x.d->reserved = 0;
    00190
    00191     T *dest = x.p->array + x.d->start;
    00192     T *src = p->array + d->start;
    00193     int oldcount = x.d->count;
    00194     while (oldcount--) {
    00195         if (QTypeInfo<T>::isComplex) {
    00196             new (dest) T(*src);
    00197         } else {
    00198             *dest = *src;
    00199         }
    00200         dest++;
    00201         if (dest == x.p->array + x.d->alloc)
    00202             dest = x.p->array;
    00203         src++;
    00204         if (src == p->array + d->alloc)
    00205             src = p->array;
    00206     }
    00207
    00208     if (!d->ref.deref())
    00209         free(p);
    00210     d = x.d;
    00211 }
    00212
    00213 template <typename T>
    00214 void QContiguousCache<T>::setCapacity(int asize)
    00215 {
    00216     if (asize == d->alloc)
    00217         return;
    00218     detach();
    00219     union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
    00220     x.d = malloc(asize);
    00221     x.d->alloc = asize;
    00222     x.d->count = qMin(d->count, asize);
    00223     x.d->offset = d->offset + d->count - x.d->count;
    00224     if(asize)
    00225         x.d->start = x.d->offset % x.d->alloc;
    00226     else
    00227         x.d->start = 0;
    00228
    00229     int oldcount = x.d->count;
    00230     if(oldcount)
    00231     {
    00232         T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc;
    00233         T *src = p->array + (d->start + d->count-1) % d->alloc;
    00234         while (oldcount--) {
    00235             if (QTypeInfo<T>::isComplex) {
    00236                 new (dest) T(*src);
    00237             } else {
    00238                 *dest = *src;
    00239             }
    00240             if (dest == x.p->array)
    00241                 dest = x.p->array + x.d->alloc;
    00242             dest--;
    00243             if (src == p->array)
    00244                 src = p->array + d->alloc;
    00245             src--;
    00246         }
    00247     }
    00248     /* free old */
    00249     free(p);
    00250     d = x.d;
    00251 }
    00252
    00253 template <typename T>
    00254 void QContiguousCache<T>::clear()
    00255 {
    00256     if (d->ref == 1) {
    00257         if (QTypeInfo<T>::isComplex) {
    00258             int oldcount = d->count;
    00259             T * i = p->array + d->start;
    00260             T * e = p->array + d->alloc;
    00261             while (oldcount--) {
    00262                 i->~T();
    00263                 i++;
    00264                 if (i == e)
    00265                     i = p->array;
    00266             }
    00267         }
    00268         d->count = d->start = d->offset = 0;
    00269     } else {
    00270         union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
    00271         x.d = malloc(d->alloc);
    00272         x.d->ref = 1;
    00273         x.d->alloc = d->alloc;
    00274         x.d->count = x.d->start = x.d->offset = 0;
    00275         x.d->sharable = true;
    00276         if (!d->ref.deref()) free(p);
    00277         d = x.d;
    00278     }
    00279 }
    00280
    00281 template <typename T>
    00282 inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
    00283 {
    00284     return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
    00285 }
    00286
    00287 template <typename T>
    00288 QContiguousCache<T>::QContiguousCache(int cap)
    00289 {
    00290     d = malloc(cap);
    00291     d->ref = 1;
    00292     d->alloc = cap;
    00293     d->count = d->start = d->offset = 0;
    00294     d->sharable = true;
    00295 }
    00296
    00297 template <typename T>
    00298 QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
    00299 {
    00300     other.d->ref.ref();
    00301     if (!d->ref.deref())
    00302         free(d);
    00303     d = other.d;
    00304     if (!d->sharable)
    00305         detach_helper();
    00306     return *this;
    00307 }
    00308
    00309 template <typename T>
    00310 bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
    00311 {
    00312     if (other.d == d)
    00313         return true;
    00314     if (other.d->start != d->start
    00315             || other.d->count != d->count
    00316             || other.d->offset != d->offset
    00317             || other.d->alloc != d->alloc)
    00318         return false;
    00319     for (int i = firstIndex(); i <= lastIndex(); ++i)
    00320         if (!(at(i) == other.at(i)))
    00321             return false;
    00322     return true;
    00323 }
    00324
    00325 template <typename T>
    00326 void QContiguousCache<T>::free(Data *x)
    00327 {
    00328     if (QTypeInfo<T>::isComplex) {
    00329         int oldcount = d->count;
    00330         T * i = p->array + d->start;
    00331         T * e = p->array + d->alloc;
    00332         while (oldcount--) {
    00333             i->~T();
    00334             i++;
    00335             if (i == e)
    00336                 i = p->array;
    00337         }
    00338     }
    00339     x->free(x);
    00340 }
    00341 template <typename T>
    00342 void QContiguousCache<T>::append(const T &value)
    00343 {
    00344     detach();
    00345     if (QTypeInfo<T>::isComplex) {
    00346         if (d->count == d->alloc)
    00347             (p->array + (d->start+d->count) % d->alloc)->~T();
    00348         new (p->array + (d->start+d->count) % d->alloc) T(value);
    00349     } else {
    00350         p->array[(d->start+d->count) % d->alloc] = value;
    00351     }
    00352
    00353     if (d->count == d->alloc) {
    00354         d->start++;
    00355         d->start %= d->alloc;
    00356         d->offset++;
    00357     } else {
    00358         d->count++;
    00359     }
    00360 }
    00361
    00362 template<typename T>
    00363 void QContiguousCache<T>::prepend(const T &value)
    00364 {
    00365     detach();
    00366     if (d->start)
    00367         d->start--;
    00368     else
    00369         d->start = d->alloc-1;
    00370     d->offset--;
    00371
    00372     if (d->count != d->alloc)
    00373         d->count++;
    00374     else
    00375         if (d->count == d->alloc)
    00376             (p->array + d->start)->~T();
    00377
    00378     if (QTypeInfo<T>::isComplex)
    00379         new (p->array + d->start) T(value);
    00380     else
    00381         p->array[d->start] = value;
    00382 }
    00383
    00384 template<typename T>
    00385 void QContiguousCache<T>::insert(int pos, const T &value)
    00386 {
    00387     Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
    00388     detach();
    00389     if (containsIndex(pos)) {
    00390         if(QTypeInfo<T>::isComplex)
    00391             new (p->array + pos % d->alloc) T(value);
    00392         else
    00393             p->array[pos % d->alloc] = value;
    00394     } else if (pos == d->offset-1)
    00395         prepend(value);
    00396     else if (pos == d->offset+d->count)
    00397         append(value);
    00398     else {
    00399         // we don't leave gaps.
    00400         clear();
    00401         d->offset = pos;
    00402         d->start = pos % d->alloc;
    00403         d->count = 1;
    00404         if (QTypeInfo<T>::isComplex)
    00405             new (p->array + d->start) T(value);
    00406         else
    00407             p->array[d->start] = value;
    00408     }
    00409 }
    00410
    00411 template <typename T>
    00412 inline const T &QContiguousCache<T>::at(int pos) const
    00413 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
    00414 template <typename T>
    00415 inline const T &QContiguousCache<T>::operator[](int pos) const
    00416 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
    00417
    00418 template <typename T>
    00419 inline T &QContiguousCache<T>::operator[](int pos)
    00420 {
    00421     detach();
    00422     if (!containsIndex(pos))
    00423         insert(pos, T());
    00424     return p->array[pos % d->alloc];
    00425 }
    00426
    00427 template <typename T>
    00428 inline void QContiguousCache<T>::removeFirst()
    00429 {
    00430     Q_ASSERT(d->count > 0);
    00431     detach();
    00432     d->count--;
    00433     if (QTypeInfo<T>::isComplex)
    00434         (p->array + d->start)->~T();
    00435     d->start = (d->start + 1) % d->alloc;
    00436     d->offset++;
    00437 }
    00438
    00439 template <typename T>
    00440 inline void QContiguousCache<T>::removeLast()
    00441 {
    00442     Q_ASSERT(d->count > 0);
    00443     detach();
    00444     d->count--;
    00445     if (QTypeInfo<T>::isComplex)
    00446         (p->array + (d->start + d->count) % d->alloc)->~T();
    00447 }
    00448
    00449 template <typename T>
    00450 inline T QContiguousCache<T>::takeFirst()
    00451 { T t = first(); removeFirst(); return t; }
    00452
    00453 template <typename T>
    00454 inline T QContiguousCache<T>::takeLast()
    00455 { T t = last(); removeLast(); return t; }
    00456
    00457 QT_END_NAMESPACE
    00458
    00459 QT_END_HEADER
    00460
    00461 #endif