1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef QCONTIGUOUSCACHE_H

    43 #define QCONTIGUOUSCACHE_H

    44 

    45 #include <QtCore/qatomic.h>

    46 #include <limits.h>

    47 #include <new>

    48 

    49 QT_BEGIN_HEADER

    50 

    51 QT_BEGIN_NAMESPACE

    52 

    53 #undef QT_QCONTIGUOUSCACHE_DEBUG

    54 QT_MODULE(Core)

    55 

    56 

    57 struct Q_CORE_EXPORT QContiguousCacheData

    58 {

    59     QBasicAtomicInt ref;

    60     int alloc;

    61     int count;

    62     int start;

    63     int offset;

    64     uint sharable : 1;

    65 

    66 #ifdef QT_QCONTIGUOUSCACHE_DEBUG

    67     void dump() const;

    68 #endif

    69 };

    70 

    71 template <typename T>

    72 struct QContiguousCacheTypedData

    73 {

    74     QBasicAtomicInt ref;

    75     int alloc;

    76     int count;

    77     int start;

    78     int offset;

    79     uint sharable : 1;

    80     // uint unused : 31;

    81 

    82     // total is 24 bytes (HP-UX aCC: 40 bytes)

    83     // the next entry is already aligned to 8 bytes

    84     // there will be an 8 byte gap here if T requires 16-byte alignment

    85     //  (such as long double on 64-bit platforms, __int128, __float128)

    86 

    87     T array[1];

    88 };

    89 

    90 template<typename T>

    91 class QContiguousCache {

    92     typedef QContiguousCacheTypedData<T> Data;

    93     union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; };

    94 public:

    95     explicit QContiguousCache(int capacity = 0);

    96     QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }

    97 

    98     inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(d); }

    99 

   100     inline void detach() { if (d->ref != 1) detach_helper(); }

   101     inline bool isDetached() const { return d->ref == 1; }

   102     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }

   103 

   104     QContiguousCache<T> &operator=(const QContiguousCache<T> &other);

   105     bool operator==(const QContiguousCache<T> &other) const;

   106     inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }

   107 

   108     inline int capacity() const {return d->alloc; }

   109     inline int count() const { return d->count; }

   110     inline int size() const { return d->count; }

   111 

   112     inline bool isEmpty() const { return d->count == 0; }

   113     inline bool isFull() const { return d->count == d->alloc; }

   114     inline int available() const { return d->alloc - d->count; }

   115 

   116     void clear();

   117     void setCapacity(int size);

   118 

   119     const T &at(int pos) const;

   120     T &operator[](int i);

   121     const T &operator[](int i) const;

   122 

   123     void append(const T &value);

   124     void prepend(const T &value);

   125     void insert(int pos, const T &value);

   126 

   127     inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }

   128     inline int firstIndex() const { return d->offset; }

   129     inline int lastIndex() const { return d->offset + d->count - 1; }

   130 

   131     inline const T &first() const { Q_ASSERT(!isEmpty()); return d->array[d->start]; }

   132     inline const T &last() const { Q_ASSERT(!isEmpty()); return d->array[(d->start + d->count -1) % d->alloc]; }

   133     inline T &first() { Q_ASSERT(!isEmpty()); detach(); return d->array[d->start]; }

   134     inline T &last() { Q_ASSERT(!isEmpty()); detach(); return d->array[(d->start + d->count -1) % d->alloc]; }

   135 

   136     void removeFirst();

   137     T takeFirst();

   138     void removeLast();

   139     T takeLast();

   140 

   141     inline bool areIndexesValid() const

   142     { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }

   143 

   144     inline void normalizeIndexes() { d->offset = d->start; }

   145 

   146 #ifdef QT_QCONTIGUOUSCACHE_DEBUG

   147     void dump() const { p->dump(); }

   148 #endif

   149 private:

   150     void detach_helper();

   151 

   152     QContiguousCacheData *malloc(int aalloc);

   153     void free(Data *x);

   154     int sizeOfTypedData() {

   155         // this is more or less the same as sizeof(Data), except that it doesn't

   156         // count the padding at the end

   157         return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);

   158     }

   159 };

   160 

   161 template <typename T>

   162 void QContiguousCache<T>::detach_helper()

   163 {

   164     union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;

   165 

   166     x.p = malloc(d->alloc);

   167     x.d->ref = 1;

   168     x.d->count = d->count;

   169     x.d->start = d->start;

   170     x.d->offset = d->offset;

   171     x.d->alloc = d->alloc;

   172     x.d->sharable = true;

   173 

   174     T *dest = x.d->array + x.d->start;

   175     T *src = d->array + d->start;

   176     int oldcount = x.d->count;

   177     while (oldcount--) {

   178         if (QTypeInfo<T>::isComplex) {

   179             new (dest) T(*src);

   180         } else {

   181             *dest = *src;

   182         }

   183         dest++;

   184         if (dest == x.d->array + x.d->alloc)

   185             dest = x.d->array;

   186         src++;

   187         if (src == d->array + d->alloc)

   188             src = d->array;

   189     }

   190 

   191     if (!d->ref.deref())

   192         free(d);

   193     d = x.d;

   194 }

   195 

   196 template <typename T>

   197 void QContiguousCache<T>::setCapacity(int asize)

   198 {

   199     if (asize == d->alloc)

   200         return;

   201     detach();

   202     union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;

   203     x.p = malloc(asize);

   204     x.d->alloc = asize;

   205     x.d->count = qMin(d->count, asize);

   206     x.d->offset = d->offset + d->count - x.d->count;

   207     x.d->start = x.d->offset % x.d->alloc;

   208     T *dest = x.d->array + (x.d->start + x.d->count-1) % x.d->alloc;

   209     T *src = d->array + (d->start + d->count-1) % d->alloc;

   210     int oldcount = x.d->count;

   211     while (oldcount--) {

   212         if (QTypeInfo<T>::isComplex) {

   213             new (dest) T(*src);

   214         } else {

   215             *dest = *src;

   216         }

   217         if (dest == x.d->array)

   218             dest = x.d->array + x.d->alloc;

   219         dest--;

   220         if (src == d->array)

   221             src = d->array + d->alloc;

   222         src--;

   223     }

   224     /* free old */

   225     free(d);

   226     d = x.d;

   227 }

   228 

   229 template <typename T>

   230 void QContiguousCache<T>::clear()

   231 {

   232     if (d->ref == 1) {

   233         if (QTypeInfo<T>::isComplex) {

   234             int oldcount = d->count;

   235             T * i = d->array + d->start;

   236             T * e = d->array + d->alloc;

   237             while (oldcount--) {

   238                 i->~T();

   239                 i++;

   240                 if (i == e)

   241                     i = d->array;

   242             }

   243         }

   244         d->count = d->start = d->offset = 0;

   245     } else {

   246         union { QContiguousCacheData *p; QContiguousCacheTypedData<T> *d; } x;

   247         x.p = malloc(d->alloc);

   248         x.d->ref = 1;

   249         x.d->alloc = d->alloc;

   250         x.d->count = x.d->start = x.d->offset = 0;

   251         x.d->sharable = true;

   252         if (!d->ref.deref()) free(d);

   253         d = x.d;

   254     }

   255 }

   256 

   257 template <typename T>

   258 inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)

   259 {

   260     return static_cast<QContiguousCacheData *>(qMalloc(sizeOfTypedData() + (aalloc - 1) * sizeof(T)));

   261 }

   262 

   263 template <typename T>

   264 QContiguousCache<T>::QContiguousCache(int cap)

   265 {

   266     p = malloc(cap);

   267     d->ref = 1;

   268     d->alloc = cap;

   269     d->count = d->start = d->offset = 0;

   270     d->sharable = true;

   271 }

   272 

   273 template <typename T>

   274 QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)

   275 {

   276     other.d->ref.ref();

   277     if (!d->ref.deref())

   278         free(d);

   279     d = other.d;

   280     if (!d->sharable)

   281         detach_helper();

   282     return *this;

   283 }

   284 

   285 template <typename T>

   286 bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const

   287 {

   288     if (other.d == d)

   289         return true;

   290     if (other.d->start != d->start

   291             || other.d->count != d->count

   292             || other.d->offset != d->offset

   293             || other.d->alloc != d->alloc)

   294         return false;

   295     for (int i = firstIndex(); i <= lastIndex(); ++i)

   296         if (!(at(i) == other.at(i)))

   297             return false;

   298     return true;

   299 }

   300 

   301 template <typename T>

   302 void QContiguousCache<T>::free(Data *x)

   303 {

   304     if (QTypeInfo<T>::isComplex) {

   305         int oldcount = d->count;

   306         T * i = d->array + d->start;

   307         T * e = d->array + d->alloc;

   308         while (oldcount--) {

   309             i->~T();

   310             i++;

   311             if (i == e)

   312                 i = d->array;

   313         }

   314     }

   315     qFree(x);

   316 }

   317 template <typename T>

   318 void QContiguousCache<T>::append(const T &value)

   319 {

   320     detach();

   321     if (QTypeInfo<T>::isComplex) {

   322         if (d->count == d->alloc)

   323             (d->array + (d->start+d->count) % d->alloc)->~T();

   324         new (d->array + (d->start+d->count) % d->alloc) T(value);

   325     } else {

   326         d->array[(d->start+d->count) % d->alloc] = value;

   327     }

   328 

   329     if (d->count == d->alloc) {

   330         d->start++;

   331         d->start %= d->alloc;

   332         d->offset++;

   333     } else {

   334         d->count++;

   335     }

   336 }

   337 

   338 template<typename T>

   339 void QContiguousCache<T>::prepend(const T &value)

   340 {

   341     detach();

   342     if (d->start)

   343         d->start--;

   344     else

   345         d->start = d->alloc-1;

   346     d->offset--;

   347 

   348     if (d->count != d->alloc)

   349         d->count++;

   350     else

   351         if (d->count == d->alloc)

   352             (d->array + d->start)->~T();

   353 

   354     if (QTypeInfo<T>::isComplex)

   355         new (d->array + d->start) T(value);

   356     else

   357         d->array[d->start] = value;

   358 }

   359 

   360 template<typename T>

   361 void QContiguousCache<T>::insert(int pos, const T &value)

   362 {

   363     Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");

   364     detach();

   365     if (containsIndex(pos)) {

   366         if(QTypeInfo<T>::isComplex)

   367             new (d->array + pos % d->alloc) T(value);

   368         else

   369             d->array[pos % d->alloc] = value;

   370     } else if (pos == d->offset-1)

   371         prepend(value);

   372     else if (pos == d->offset+d->count)

   373         append(value);

   374     else {

   375         // we don't leave gaps.

   376         clear();

   377         d->offset = pos;

   378         d->start = pos % d->alloc;

   379         d->count = 1;

   380         if (QTypeInfo<T>::isComplex)

   381             new (d->array + d->start) T(value);

   382         else

   383             d->array[d->start] = value;

   384     }

   385 }

   386 

   387 template <typename T>

   388 inline const T &QContiguousCache<T>::at(int pos) const

   389 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }

   390 template <typename T>

   391 inline const T &QContiguousCache<T>::operator[](int pos) const

   392 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return d->array[pos % d->alloc]; }

   393 

   394 template <typename T>

   395 inline T &QContiguousCache<T>::operator[](int pos)

   396 {

   397     detach();

   398     if (!containsIndex(pos))

   399         insert(pos, T());

   400     return d->array[pos % d->alloc];

   401 }

   402 

   403 template <typename T>

   404 inline void QContiguousCache<T>::removeFirst()

   405 {

   406     Q_ASSERT(d->count > 0);

   407     detach();

   408     d->count--;

   409     if (QTypeInfo<T>::isComplex)

   410         (d->array + d->start)->~T();

   411     d->start = (d->start + 1) % d->alloc;

   412     d->offset++;

   413 }

   414 

   415 template <typename T>

   416 inline void QContiguousCache<T>::removeLast()

   417 {

   418     Q_ASSERT(d->count > 0);

   419     detach();

   420     d->count--;

   421     if (QTypeInfo<T>::isComplex)

   422         (d->array + (d->start + d->count) % d->alloc)->~T();

   423 }

   424 

   425 template <typename T>

   426 inline T QContiguousCache<T>::takeFirst()

   427 { T t = first(); removeFirst(); return t; }

   428 

   429 template <typename T>

   430 inline T QContiguousCache<T>::takeLast()

   431 { T t = last(); removeLast(); return t; }

   432 

   433 QT_END_NAMESPACE

   434 

   435 QT_END_HEADER

   436 

   437 #endif