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 test suite 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 #include <QObject>

    43 #include <QTest>

    44 #include <QCache>

    45 #include <QContiguousCache>

    46 

    47 #include <QDebug>

    48 #include <stdio.h>

    49 

    50 class tst_QContiguousCache : public QObject

    51 {

    52     Q_OBJECT

    53 public:

    54     tst_QContiguousCache() {}

    55     virtual ~tst_QContiguousCache() {}

    56 private slots:

    57     void empty();

    58     void append_data();

    59     void append();

    60 

    61     void prepend_data();

    62     void prepend();

    63 

    64     void asScrollingList();

    65 

    66     void complexType();

    67 

    68     void operatorAt();

    69 

    70     void cacheBenchmark();

    71     void contiguousCacheBenchmark();

    72 

    73     void setCapacity();

    74 };

    75 

    76 QTEST_MAIN(tst_QContiguousCache)

    77 

    78 void tst_QContiguousCache::empty()

    79 {

    80     QContiguousCache<int> c(10);

    81     QCOMPARE(c.capacity(), 10);

    82     QCOMPARE(c.count(), 0);

    83     QVERIFY(c.isEmpty());

    84     c.append(1);

    85     QCOMPARE(c.count(), 1);

    86     QVERIFY(!c.isEmpty());

    87     c.clear();

    88     QCOMPARE(c.capacity(), 10);

    89     QCOMPARE(c.count(), 0);

    90     QVERIFY(c.isEmpty());

    91     c.prepend(1);

    92     QCOMPARE(c.count(), 1);

    93     QVERIFY(!c.isEmpty());

    94     c.clear();

    95     QCOMPARE(c.count(), 0);

    96     QVERIFY(c.isEmpty());

    97     QCOMPARE(c.capacity(), 10);

    98 }

    99 

   100 void tst_QContiguousCache::append_data()

   101 {

   102     QTest::addColumn<int>("start");

   103     QTest::addColumn<int>("count");

   104     QTest::addColumn<int>("cacheSize");

   105     QTest::addColumn<bool>("invalidIndexes");

   106 

   107     QTest::newRow("0+30[10]") << 0 << 30 << 10 << false;

   108     QTest::newRow("300+30[10]") << 300 << 30 << 10 << false;

   109     QTest::newRow("MAX-10+30[10]") << INT_MAX-10 << 30 << 10 << true;

   110 }

   111 

   112 void tst_QContiguousCache::append()

   113 {

   114     QFETCH(int, start);

   115     QFETCH(int, count);

   116     QFETCH(int, cacheSize);

   117     QFETCH(bool, invalidIndexes);

   118 

   119     int i, j;

   120     QContiguousCache<int> c(cacheSize);

   121 

   122     i = 1;

   123     QCOMPARE(c.available(), cacheSize);

   124     if (start == 0)

   125         c.append(i++);

   126     else

   127         c.insert(start, i++);

   128     while (i < count) {

   129         c.append(i);

   130         QCOMPARE(c.available(), qMax(0, cacheSize - i));

   131         QCOMPARE(c.first(), qMax(1, i-cacheSize+1));

   132         QCOMPARE(c.last(), i);

   133         QCOMPARE(c.count(), qMin(i, cacheSize));

   134         QCOMPARE(c.isFull(), i >= cacheSize);

   135         i++;

   136     }

   137 

   138     QCOMPARE(c.areIndexesValid(), !invalidIndexes);

   139     if (invalidIndexes)

   140         c.normalizeIndexes();

   141     QVERIFY(c.areIndexesValid());

   142 

   143     // test taking from end until empty.

   144     for (j = 0; j < cacheSize; j++, i--) {

   145         QCOMPARE(c.takeLast(), i-1);

   146         QCOMPARE(c.count(), cacheSize-j-1);

   147         QCOMPARE(c.available(), j+1);

   148         QVERIFY(!c.isFull());

   149         QCOMPARE(c.isEmpty(), j==cacheSize-1);

   150     }

   151 

   152 }

   153 

   154 void tst_QContiguousCache::prepend_data()

   155 {

   156     QTest::addColumn<int>("start");

   157     QTest::addColumn<int>("count");

   158     QTest::addColumn<int>("cacheSize");

   159     QTest::addColumn<bool>("invalidIndexes");

   160 

   161     QTest::newRow("30-30[10]") << 30 << 30 << 10 << false;

   162     QTest::newRow("300-30[10]") << 300 << 30 << 10 << false;

   163     QTest::newRow("10-30[10]") << 10 << 30 << 10 << true;

   164 }

   165 

   166 void tst_QContiguousCache::prepend()

   167 {

   168     QFETCH(int, start);

   169     QFETCH(int, count);

   170     QFETCH(int, cacheSize);

   171     QFETCH(bool, invalidIndexes);

   172 

   173     int i, j;

   174     QContiguousCache<int> c(cacheSize);

   175 

   176     i = 1;

   177     QCOMPARE(c.available(), cacheSize);

   178     c.insert(start, i++);

   179     while(i < count) {

   180         c.prepend(i);

   181         QCOMPARE(c.available(), qMax(0, cacheSize - i));

   182         QCOMPARE(c.last(), qMax(1, i-cacheSize+1));

   183         QCOMPARE(c.first(), i);

   184         QCOMPARE(c.count(), qMin(i, cacheSize));

   185         QCOMPARE(c.isFull(), i >= cacheSize);

   186         i++;

   187     }

   188 

   189     QCOMPARE(c.areIndexesValid(), !invalidIndexes);

   190     if (invalidIndexes)

   191         c.normalizeIndexes();

   192     QVERIFY(c.areIndexesValid());

   193 

   194     // test taking from start until empty.

   195     for (j = 0; j < cacheSize; j++, i--) {

   196         QCOMPARE(c.takeFirst(), i-1);

   197         QCOMPARE(c.count(), cacheSize-j-1);

   198         QCOMPARE(c.available(), j+1);

   199         QVERIFY(!c.isFull());

   200         QCOMPARE(c.isEmpty(), j==cacheSize-1);

   201     }

   202 }

   203 

   204 void tst_QContiguousCache::asScrollingList()

   205 {

   206     int i;

   207     QContiguousCache<int> c(10);

   208 

   209     // Once allocated QContiguousCache should not

   210     // allocate any additional memory for non

   211     // complex data types.

   212     QBENCHMARK {

   213         // simulate scrolling in a list of items;

   214         for(i = 0; i < 10; ++i) {

   215             QCOMPARE(c.available(), 10-i);

   216             c.append(i);

   217         }

   218 

   219         QCOMPARE(c.firstIndex(), 0);

   220         QCOMPARE(c.lastIndex(), 9);

   221         QCOMPARE(c.first(), 0);

   222         QCOMPARE(c.last(), 9);

   223         QVERIFY(!c.containsIndex(-1));

   224         QVERIFY(!c.containsIndex(10));

   225         QCOMPARE(c.available(), 0);

   226 

   227         for (i = 0; i < 10; ++i) {

   228             QVERIFY(c.containsIndex(i));

   229             QCOMPARE(c.at(i), i);

   230             QCOMPARE(c[i], i);

   231             QCOMPARE(((const QContiguousCache<int>)c)[i], i);

   232         }

   233 

   234         for (i = 10; i < 30; ++i)

   235             c.append(i);

   236 

   237         QCOMPARE(c.firstIndex(), 20);

   238         QCOMPARE(c.lastIndex(), 29);

   239         QCOMPARE(c.first(), 20);

   240         QCOMPARE(c.last(), 29);

   241         QVERIFY(!c.containsIndex(19));

   242         QVERIFY(!c.containsIndex(30));

   243         QCOMPARE(c.available(), 0);

   244 

   245         for (i = 20; i < 30; ++i) {

   246             QVERIFY(c.containsIndex(i));

   247             QCOMPARE(c.at(i), i);

   248             QCOMPARE(c[i], i);

   249             QCOMPARE(((const QContiguousCache<int> )c)[i], i);

   250         }

   251 

   252         for (i = 19; i >= 10; --i)

   253             c.prepend(i);

   254 

   255         QCOMPARE(c.firstIndex(), 10);

   256         QCOMPARE(c.lastIndex(), 19);

   257         QCOMPARE(c.first(), 10);

   258         QCOMPARE(c.last(), 19);

   259         QVERIFY(!c.containsIndex(9));

   260         QVERIFY(!c.containsIndex(20));

   261         QCOMPARE(c.available(), 0);

   262 

   263         for (i = 10; i < 20; ++i) {

   264             QVERIFY(c.containsIndex(i));

   265             QCOMPARE(c.at(i), i);

   266             QCOMPARE(c[i], i);

   267             QCOMPARE(((const QContiguousCache<int> )c)[i], i);

   268         }

   269 

   270         for (i = 200; i < 220; ++i)

   271             c.insert(i, i);

   272 

   273         QCOMPARE(c.firstIndex(), 210);

   274         QCOMPARE(c.lastIndex(), 219);

   275         QCOMPARE(c.first(), 210);

   276         QCOMPARE(c.last(), 219);

   277         QVERIFY(!c.containsIndex(209));

   278         QVERIFY(!c.containsIndex(300));

   279         QCOMPARE(c.available(), 0);

   280 

   281         for (i = 210; i < 220; ++i) {

   282             QVERIFY(c.containsIndex(i));

   283             QCOMPARE(c.at(i), i);

   284             QCOMPARE(c[i], i);

   285             QCOMPARE(((const QContiguousCache<int> )c)[i], i);

   286         }

   287         c.clear(); // needed to reset benchmark

   288     }

   289 

   290     // from a specific bug that was encountered.  100 to 299 cached, attempted to cache 250 - 205 via insert, failed.

   291     // bug was that item at 150 would instead be item that should have been inserted at 250

   292     c.setCapacity(200);

   293     for(i = 100; i < 300; ++i)

   294         c.insert(i, i);

   295     for (i = 250; i <= 306; ++i)

   296         c.insert(i, 1000+i);

   297     for (i = 107; i <= 306; ++i) {

   298         QVERIFY(c.containsIndex(i));

   299         QCOMPARE(c.at(i), i < 250 ? i : 1000+i);

   300     }

   301 }

   302 

   303 struct RefCountingClassData

   304 {

   305     QBasicAtomicInt ref;

   306     static RefCountingClassData shared_null;

   307 };

   308 

   309 RefCountingClassData RefCountingClassData::shared_null = {

   310     Q_BASIC_ATOMIC_INITIALIZER(1)

   311 };

   312 

   313 class RefCountingClass

   314 {

   315 public:

   316     RefCountingClass() : d(&RefCountingClassData::shared_null) { d->ref.ref(); }

   317 

   318     RefCountingClass(const RefCountingClass &other)

   319     {

   320         d = other.d;

   321         d->ref.ref();

   322     }

   323 

   324     ~RefCountingClass()

   325     {

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

   327             delete d;

   328     }

   329 

   330     RefCountingClass &operator=(const RefCountingClass &other)

   331     {

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

   333             delete d;

   334         d = other.d;

   335         d->ref.ref();

   336         return *this;

   337     }

   338 

   339     int refCount() const { return d->ref; }

   340 private:

   341     RefCountingClassData *d;

   342 };

   343 

   344 void tst_QContiguousCache::complexType()

   345 {

   346     RefCountingClass original;

   347 

   348     QContiguousCache<RefCountingClass> contiguousCache(10);

   349     contiguousCache.append(original);

   350     QCOMPARE(original.refCount(), 3);

   351     contiguousCache.removeFirst();

   352     QCOMPARE(original.refCount(), 2); // shared null, 'original'.

   353     contiguousCache.append(original);

   354     QCOMPARE(original.refCount(), 3);

   355     contiguousCache.clear();

   356     QCOMPARE(original.refCount(), 2);

   357 

   358     for(int i = 0; i < 100; ++i)

   359         contiguousCache.insert(i, original);

   360 

   361     QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache.

   362 

   363     contiguousCache.clear();

   364     QCOMPARE(original.refCount(), 2);

   365     for (int i = 0; i < 100; i++)

   366         contiguousCache.append(original);

   367 

   368     QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache.

   369     contiguousCache.clear();

   370     QCOMPARE(original.refCount(), 2);

   371 

   372     for (int i = 0; i < 100; i++)

   373         contiguousCache.prepend(original);

   374 

   375     QCOMPARE(original.refCount(), 12); // shared null, 'original', + 10 in contiguousCache.

   376     contiguousCache.clear();

   377     QCOMPARE(original.refCount(), 2);

   378 

   379     for (int i = 0; i < 100; i++)

   380         contiguousCache.append(original);

   381 

   382     contiguousCache.takeLast();

   383     QCOMPARE(original.refCount(), 11);

   384 

   385     contiguousCache.takeFirst();

   386     QCOMPARE(original.refCount(), 10);

   387 }

   388 

   389 void tst_QContiguousCache::operatorAt()

   390 {

   391     RefCountingClass original;

   392     QContiguousCache<RefCountingClass> contiguousCache(10);

   393 

   394     for (int i = 25; i < 35; ++i)

   395         contiguousCache[i] = original;

   396 

   397     QCOMPARE(original.refCount(), 12); // shared null, orig, items in cache

   398 

   399     // verify const access does not copy items.

   400     const QContiguousCache<RefCountingClass> copy(contiguousCache);

   401     for (int i = 25; i < 35; ++i)

   402         QCOMPARE(copy[i].refCount(), 12);

   403 

   404     // verify modifying the original increments ref count (e.g. does a detach)

   405     contiguousCache[25] = original;

   406     QCOMPARE(original.refCount(), 22);

   407 }

   408 

   409 /*

   410     Benchmarks must be near identical in tasks to be fair.

   411     QCache uses pointers to ints as its a requirement of QCache,

   412     whereas QContiguousCache doesn't support pointers (won't free them).

   413     Given the ability to use simple data types is a benefit, its

   414     fair.  Although this obviously must take into account we are

   415     testing QContiguousCache use cases here, QCache has its own

   416     areas where it is the more sensible class to use.

   417 */

   418 void tst_QContiguousCache::cacheBenchmark()

   419 {

   420     QBENCHMARK {

   421         QCache<int, int> cache;

   422         cache.setMaxCost(100);

   423 

   424         for (int i = 0; i < 1000; i++)

   425             cache.insert(i, new int(i));

   426     }

   427 }

   428 

   429 void tst_QContiguousCache::contiguousCacheBenchmark()

   430 {

   431     QBENCHMARK {

   432         QContiguousCache<int> contiguousCache(100);

   433         for (int i = 0; i < 1000; i++)

   434             contiguousCache.insert(i, i);

   435     }

   436 }

   437 

   438 void tst_QContiguousCache::setCapacity()

   439 {

   440     int i;

   441     QContiguousCache<int> contiguousCache(100);

   442     for (i = 280; i < 310; ++i)

   443         contiguousCache.insert(i, i);

   444     QCOMPARE(contiguousCache.capacity(), 100);

   445     QCOMPARE(contiguousCache.count(), 30);

   446     QCOMPARE(contiguousCache.firstIndex(), 280);

   447     QCOMPARE(contiguousCache.lastIndex(), 309);

   448 

   449     for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) {

   450         QVERIFY(contiguousCache.containsIndex(i));

   451         QCOMPARE(contiguousCache.at(i), i);

   452     }

   453 

   454     contiguousCache.setCapacity(150);

   455 

   456     QCOMPARE(contiguousCache.capacity(), 150);

   457     QCOMPARE(contiguousCache.count(), 30);

   458     QCOMPARE(contiguousCache.firstIndex(), 280);

   459     QCOMPARE(contiguousCache.lastIndex(), 309);

   460 

   461     for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) {

   462         QVERIFY(contiguousCache.containsIndex(i));

   463         QCOMPARE(contiguousCache.at(i), i);

   464     }

   465 

   466     contiguousCache.setCapacity(20);

   467 

   468     QCOMPARE(contiguousCache.capacity(), 20);

   469     QCOMPARE(contiguousCache.count(), 20);

   470     QCOMPARE(contiguousCache.firstIndex(), 290);

   471     QCOMPARE(contiguousCache.lastIndex(), 309);

   472 

   473     for (i = contiguousCache.firstIndex(); i <= contiguousCache.lastIndex(); ++i) {

   474         QVERIFY(contiguousCache.containsIndex(i));

   475         QCOMPARE(contiguousCache.at(i), i);

   476     }

   477 }

   478 

   479 #include "tst_qcontiguouscache.moc"