src/corelib/tools/qcontiguouscache.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  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
  55
  56 struct Q_CORE_EXPORT QContiguousCacheData
  57 {
  58     QBasicAtomicInt ref;
  59     int alloc;
  60     int count;
  61     int start;
  62     int offset;
  63     uint sharable : 1;
  64     uint reserved : 31;
  65
  66     // total is 24 bytes (HP-UX aCC: 40 bytes)
  67     // the next entry is already aligned to 8 bytes
  68     // there will be an 8 byte gap here if T requires 16-byte alignment
  69     //  (such as long double on 64-bit platforms, __int128, __float128)
  70
  71     static QContiguousCacheData *allocate(int size, int alignment);
  72     static void free(QContiguousCacheData *data);
  73
  74 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
  75     void dump() const;
  76 #endif
  77 };
  78
  79 template <typename T>
  80 struct QContiguousCacheTypedData: private QContiguousCacheData
  81 {
  82     // private inheritance to avoid aliasing warningss
  83     T array[1];
  84
  85     static inline void free(QContiguousCacheTypedData *data) { QContiguousCacheData::free(data); }
  86 };
  87
  88 template<typename T>
  89 class QContiguousCache {
  90     typedef QContiguousCacheTypedData<T> Data;
  91     union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; };
  92 public:
  93     // STL compatibility
  94     typedef T value_type;
  95     typedef value_type* pointer;
  96     typedef const value_type* const_pointer;
  97     typedef value_type& reference;
  98     typedef const value_type& const_reference;
  99     typedef qptrdiff difference_type;
 100     typedef int size_type;
 101
 102     explicit QContiguousCache(int capacity = 0);
 103     QContiguousCache(const QContiguousCache<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
 104
 105     inline ~QContiguousCache() { if (!d) return; if (!d->ref.deref()) free(p); }
 106
 107     inline void detach() { if (d->ref.load() != 1) detach_helper(); }
 108     inline bool isDetached() const { return d->ref.load() == 1; }
 109     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
 110
 111     QContiguousCache<T> &operator=(const QContiguousCache<T> &other);
 112 #ifdef Q_COMPILER_RVALUE_REFS
 113     inline QContiguousCache<T> &operator=(QContiguousCache<T> &&other)
 114     { qSwap(d, other.d); return *this; }
 115 #endif
 116     inline void swap(QContiguousCache<T> &other) { qSwap(d, other.d); }
 117     bool operator==(const QContiguousCache<T> &other) const;
 118     inline bool operator!=(const QContiguousCache<T> &other) const { return !(*this == other); }
 119
 120     inline int capacity() const {return d->alloc; }
 121     inline int count() const { return d->count; }
 122     inline int size() const { return d->count; }
 123
 124     inline bool isEmpty() const { return d->count == 0; }
 125     inline bool isFull() const { return d->count == d->alloc; }
 126     inline int available() const { return d->alloc - d->count; }
 127
 128     void clear();
 129     void setCapacity(int size);
 130
 131     const T &at(int pos) const;
 132     T &operator[](int i);
 133     const T &operator[](int i) const;
 134
 135     void append(const T &value);
 136     void prepend(const T &value);
 137     void insert(int pos, const T &value);
 138
 139     inline bool containsIndex(int pos) const { return pos >= d->offset && pos - d->offset < d->count; }
 140     inline int firstIndex() const { return d->offset; }
 141     inline int lastIndex() const { return d->offset + d->count - 1; }
 142
 143     inline const T &first() const { Q_ASSERT(!isEmpty()); return p->array[d->start]; }
 144     inline const T &last() const { Q_ASSERT(!isEmpty()); return p->array[(d->start + d->count -1) % d->alloc]; }
 145     inline T &first() { Q_ASSERT(!isEmpty()); detach(); return p->array[d->start]; }
 146     inline T &last() { Q_ASSERT(!isEmpty()); detach(); return p->array[(d->start + d->count -1) % d->alloc]; }
 147
 148     void removeFirst();
 149     T takeFirst();
 150     void removeLast();
 151     T takeLast();
 152
 153     inline bool areIndexesValid() const
 154     { return d->offset >= 0 && d->offset < INT_MAX - d->count && (d->offset % d->alloc) == d->start; }
 155
 156     inline void normalizeIndexes() { d->offset = d->start; }
 157
 158 #ifdef QT_QCONTIGUOUSCACHE_DEBUG
 159     void dump() const { p->dump(); }
 160 #endif
 161 private:
 162     void detach_helper();
 163
 164     QContiguousCacheData *malloc(int aalloc);
 165     void free(Data *x);
 166     int sizeOfTypedData() {
 167         // this is more or less the same as sizeof(Data), except that it doesn't
 168         // count the padding at the end
 169         return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
 170     }
 171     int alignOfTypedData() const
 172     {
 173         return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
 174     }
 175 };
 176
 177 template <typename T>
 178 void QContiguousCache<T>::detach_helper()
 179 {
 180     union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
 181
 182     x.d = malloc(d->alloc);
 183     x.d->ref.store(1);
 184     x.d->count = d->count;
 185     x.d->start = d->start;
 186     x.d->offset = d->offset;
 187     x.d->alloc = d->alloc;
 188     x.d->sharable = true;
 189     x.d->reserved = 0;
 190
 191     T *dest = x.p->array + x.d->start;
 192     T *src = p->array + d->start;
 193     int oldcount = x.d->count;
 194     while (oldcount--) {
 195         if (QTypeInfo<T>::isComplex) {
 196             new (dest) T(*src);
 197         } else {
 198             *dest = *src;
 199         }
 200         dest++;
 201         if (dest == x.p->array + x.d->alloc)
 202             dest = x.p->array;
 203         src++;
 204         if (src == p->array + d->alloc)
 205             src = p->array;
 206     }
 207
 208     if (!d->ref.deref())
 209         free(p);
 210     d = x.d;
 211 }
 212
 213 template <typename T>
 214 void QContiguousCache<T>::setCapacity(int asize)
 215 {
 216     if (asize == d->alloc)
 217         return;
 218     detach();
 219     union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
 220     x.d = malloc(asize);
 221     x.d->alloc = asize;
 222     x.d->count = qMin(d->count, asize);
 223     x.d->offset = d->offset + d->count - x.d->count;
 224     if(asize)
 225         x.d->start = x.d->offset % x.d->alloc;
 226     else
 227         x.d->start = 0;
 228
 229     int oldcount = x.d->count;
 230     if(oldcount)
 231     {
 232         T *dest = x.p->array + (x.d->start + x.d->count-1) % x.d->alloc;
 233         T *src = p->array + (d->start + d->count-1) % d->alloc;
 234         while (oldcount--) {
 235             if (QTypeInfo<T>::isComplex) {
 236                 new (dest) T(*src);
 237             } else {
 238                 *dest = *src;
 239             }
 240             if (dest == x.p->array)
 241                 dest = x.p->array + x.d->alloc;
 242             dest--;
 243             if (src == p->array)
 244                 src = p->array + d->alloc;
 245             src--;
 246         }
 247     }
 248     /* free old */
 249     free(p);
 250     d = x.d;
 251 }
 252
 253 template <typename T>
 254 void QContiguousCache<T>::clear()
 255 {
 256     if (d->ref.load() == 1) {
 257         if (QTypeInfo<T>::isComplex) {
 258             int oldcount = d->count;
 259             T * i = p->array + d->start;
 260             T * e = p->array + d->alloc;
 261             while (oldcount--) {
 262                 i->~T();
 263                 i++;
 264                 if (i == e)
 265                     i = p->array;
 266             }
 267         }
 268         d->count = d->start = d->offset = 0;
 269     } else {
 270         union { QContiguousCacheData *d; QContiguousCacheTypedData<T> *p; } x;
 271         x.d = malloc(d->alloc);
 272         x.d->ref.store(1);
 273         x.d->alloc = d->alloc;
 274         x.d->count = x.d->start = x.d->offset = 0;
 275         x.d->sharable = true;
 276         if (!d->ref.deref()) free(p);
 277         d = x.d;
 278     }
 279 }
 280
 281 template <typename T>
 282 inline QContiguousCacheData *QContiguousCache<T>::malloc(int aalloc)
 283 {
 284     return QContiguousCacheData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
 285 }
 286
 287 template <typename T>
 288 QContiguousCache<T>::QContiguousCache(int cap)
 289 {
 290     d = malloc(cap);
 291     d->ref.store(1);
 292     d->alloc = cap;
 293     d->count = d->start = d->offset = 0;
 294     d->sharable = true;
 295 }
 296
 297 template <typename T>
 298 QContiguousCache<T> &QContiguousCache<T>::operator=(const QContiguousCache<T> &other)
 299 {
 300     other.d->ref.ref();
 301     if (!d->ref.deref())
 302         free(d);
 303     d = other.d;
 304     if (!d->sharable)
 305         detach_helper();
 306     return *this;
 307 }
 308
 309 template <typename T>
 310 bool QContiguousCache<T>::operator==(const QContiguousCache<T> &other) const
 311 {
 312     if (other.d == d)
 313         return true;
 314     if (other.d->start != d->start
 315             || other.d->count != d->count
 316             || other.d->offset != d->offset
 317             || other.d->alloc != d->alloc)
 318         return false;
 319     for (int i = firstIndex(); i <= lastIndex(); ++i)
 320         if (!(at(i) == other.at(i)))
 321             return false;
 322     return true;
 323 }
 324
 325 template <typename T>
 326 void QContiguousCache<T>::free(Data *x)
 327 {
 328     if (QTypeInfo<T>::isComplex) {
 329         int oldcount = d->count;
 330         T * i = p->array + d->start;
 331         T * e = p->array + d->alloc;
 332         while (oldcount--) {
 333             i->~T();
 334             i++;
 335             if (i == e)
 336                 i = p->array;
 337         }
 338     }
 339     x->free(x);
 340 }
 341 template <typename T>
 342 void QContiguousCache<T>::append(const T &value)
 343 {
 344     detach();
 345     if (QTypeInfo<T>::isComplex) {
 346         if (d->count == d->alloc)
 347             (p->array + (d->start+d->count) % d->alloc)->~T();
 348         new (p->array + (d->start+d->count) % d->alloc) T(value);
 349     } else {
 350         p->array[(d->start+d->count) % d->alloc] = value;
 351     }
 352
 353     if (d->count == d->alloc) {
 354         d->start++;
 355         d->start %= d->alloc;
 356         d->offset++;
 357     } else {
 358         d->count++;
 359     }
 360 }
 361
 362 template<typename T>
 363 void QContiguousCache<T>::prepend(const T &value)
 364 {
 365     detach();
 366     if (d->start)
 367         d->start--;
 368     else
 369         d->start = d->alloc-1;
 370     d->offset--;
 371
 372     if (d->count != d->alloc)
 373         d->count++;
 374     else
 375         if (d->count == d->alloc)
 376             (p->array + d->start)->~T();
 377
 378     if (QTypeInfo<T>::isComplex)
 379         new (p->array + d->start) T(value);
 380     else
 381         p->array[d->start] = value;
 382 }
 383
 384 template<typename T>
 385 void QContiguousCache<T>::insert(int pos, const T &value)
 386 {
 387     Q_ASSERT_X(pos >= 0 && pos < INT_MAX, "QContiguousCache<T>::insert", "index out of range");
 388     detach();
 389     if (containsIndex(pos)) {
 390         if(QTypeInfo<T>::isComplex)
 391             new (p->array + pos % d->alloc) T(value);
 392         else
 393             p->array[pos % d->alloc] = value;
 394     } else if (pos == d->offset-1)
 395         prepend(value);
 396     else if (pos == d->offset+d->count)
 397         append(value);
 398     else {
 399         // we don't leave gaps.
 400         clear();
 401         d->offset = pos;
 402         d->start = pos % d->alloc;
 403         d->count = 1;
 404         if (QTypeInfo<T>::isComplex)
 405             new (p->array + d->start) T(value);
 406         else
 407             p->array[d->start] = value;
 408     }
 409 }
 410
 411 template <typename T>
 412 inline const T &QContiguousCache<T>::at(int pos) const
 413 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
 414 template <typename T>
 415 inline const T &QContiguousCache<T>::operator[](int pos) const
 416 { Q_ASSERT_X(pos >= d->offset && pos - d->offset < d->count, "QContiguousCache<T>::at", "index out of range"); return p->array[pos % d->alloc]; }
 417
 418 template <typename T>
 419 inline T &QContiguousCache<T>::operator[](int pos)
 420 {
 421     detach();
 422     if (!containsIndex(pos))
 423         insert(pos, T());
 424     return p->array[pos % d->alloc];
 425 }
 426
 427 template <typename T>
 428 inline void QContiguousCache<T>::removeFirst()
 429 {
 430     Q_ASSERT(d->count > 0);
 431     detach();
 432     d->count--;
 433     if (QTypeInfo<T>::isComplex)
 434         (p->array + d->start)->~T();
 435     d->start = (d->start + 1) % d->alloc;
 436     d->offset++;
 437 }
 438
 439 template <typename T>
 440 inline void QContiguousCache<T>::removeLast()
 441 {
 442     Q_ASSERT(d->count > 0);
 443     detach();
 444     d->count--;
 445     if (QTypeInfo<T>::isComplex)
 446         (p->array + (d->start + d->count) % d->alloc)->~T();
 447 }
 448
 449 template <typename T>
 450 inline T QContiguousCache<T>::takeFirst()
 451 { T t = first(); removeFirst(); return t; }
 452
 453 template <typename T>
 454 inline T QContiguousCache<T>::takeLast()
 455 { T t = last(); removeLast(); return t; }
 456
 457 QT_END_NAMESPACE
 458
 459 QT_END_HEADER
 460
 461 #endif