piecetable/tests/piecetabletest.cpp

0001 /*
0002     This file is part of the Okteta Core library, made within the KDE community.
0003
0004     SPDX-FileCopyrightText: 2008 Friedrich W. H. Kossebau <kossebau@kde.org>
0005
0006     SPDX-License-Identifier: LGPL-2.1-only OR LGPL-3.0-only OR LicenseRef-KDE-Accepted-LGPL
0007 */
0008
0009 #include "piecetabletest.hpp"
0010
0011 // test object
0012 #include <piecetable/piecetable.hpp>
0013 // Qt
0014 #include <QTest>
0015
0016 namespace KPieceTable {
0017
0018 // local variables
0019 static constexpr Address Start = 15;
0020 static constexpr Address End = 27;
0021 static constexpr Size HalfBaseSize = 50;
0022 static constexpr Size BaseSize = 2 * HalfBaseSize;
0023
0024 static constexpr Size Width = End - Start + 1;
0025
0026 static constexpr Address ChangeStart = 8;
0027 static constexpr Address ChangeEnd = ChangeStart + Width - 1;
0028
0029 void PieceTableTest::testSimpleConstructor()
0030 {
0031     PieceTable pieceTable;
0032     QCOMPARE(pieceTable.size(), 0);
0033 }
0034
0035 void PieceTableTest::testInit()
0036 {
0037     PieceTable pieceTable;
0038
0039     pieceTable.init(BaseSize);
0040     int storageId;
0041     Address storageOffset;
0042
0043     bool result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0044     QVERIFY(result);
0045     QCOMPARE(storageOffset, 0);
0046     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0047
0048     result = pieceTable.getStorageData(&storageId, &storageOffset, Start);
0049     QVERIFY(result);
0050     QCOMPARE(storageOffset, Start);
0051     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0052
0053     result = pieceTable.getStorageData(&storageId, &storageOffset, End);
0054     QVERIFY(result);
0055     QCOMPARE(storageOffset, End);
0056     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0057
0058     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - 1);
0059     QVERIFY(result);
0060     QCOMPARE(storageOffset, BaseSize - 1);
0061     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0062
0063     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize);
0064     QVERIFY(!result);
0065 }
0066
0067 static void fillWithSize(PieceTable* pieceTable, int count)
0068 {
0069     pieceTable->init(0);
0070     for (int i = 0; i < count; ++i) {
0071         pieceTable->insert(0, BaseSize, BaseSize * i);
0072     }
0073
0074 }
0075
0076 void PieceTableTest::testInsert()
0077 {
0078     PieceTable pieceTable;
0079
0080     int storageId;
0081     Address storageOffset;
0082     bool result;
0083
0084     // inserting to empty
0085     pieceTable.init(0);
0086     pieceTable.insert(0, Width, ChangeStart);
0087
0088     QCOMPARE(pieceTable.size(), Width);
0089     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0090     QVERIFY(result);
0091     QCOMPARE(storageOffset, ChangeStart);
0092     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0093
0094     result = pieceTable.getStorageData(&storageId, &storageOffset, Width - 1);
0095     QVERIFY(result);
0096     QCOMPARE(storageOffset, ChangeEnd);
0097     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0098
0099     result = pieceTable.getStorageData(&storageId, &storageOffset, Width);
0100     QVERIFY(!result);
0101
0102     // inserting one at the begin
0103     pieceTable.init(BaseSize);
0104     pieceTable.insert(0, Width, ChangeStart);
0105
0106     QCOMPARE(pieceTable.size(), BaseSize + Width);
0107     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0108     QVERIFY(result);
0109     QCOMPARE(storageOffset, ChangeStart);
0110     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0111
0112     result = pieceTable.getStorageData(&storageId, &storageOffset, Width - 1);
0113     QVERIFY(result);
0114     QCOMPARE(storageOffset, ChangeEnd);
0115     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0116
0117     result = pieceTable.getStorageData(&storageId, &storageOffset, Width);
0118     QVERIFY(result);
0119     QCOMPARE(storageOffset, 0);
0120     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0121
0122     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize + Width - 1);
0123     QVERIFY(result);
0124     QCOMPARE(storageOffset, BaseSize - 1);
0125     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0126
0127     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize + Width);
0128     QVERIFY(!result);
0129
0130     // inserting one in the middle
0131     pieceTable.init(BaseSize);
0132     pieceTable.insert(Start, Width, ChangeStart);
0133
0134     QCOMPARE(pieceTable.size(), BaseSize + Width);
0135     result = pieceTable.getStorageData(&storageId, &storageOffset, Start - 1);
0136     QVERIFY(result);
0137     QCOMPARE(storageOffset, Start - 1);
0138     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0139
0140     result = pieceTable.getStorageData(&storageId, &storageOffset, Start);
0141     QVERIFY(result);
0142     QCOMPARE(storageOffset, ChangeStart);
0143     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0144
0145     result = pieceTable.getStorageData(&storageId, &storageOffset, End);
0146     QVERIFY(result);
0147     QCOMPARE(storageOffset, ChangeEnd);
0148     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0149
0150     result = pieceTable.getStorageData(&storageId, &storageOffset, End + 1);
0151     QVERIFY(result);
0152     QCOMPARE(storageOffset, Start);
0153     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0154
0155     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize + Width - 1);
0156     QVERIFY(result);
0157     QCOMPARE(storageOffset, BaseSize - 1);
0158     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0159
0160     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize + Width);
0161     QVERIFY(!result);
0162
0163     // inserting one at the end
0164     pieceTable.init(BaseSize);
0165     pieceTable.insert(BaseSize, Width, ChangeStart);
0166
0167     QCOMPARE(pieceTable.size(), BaseSize + Width);
0168     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - 1);
0169     QVERIFY(result);
0170     QCOMPARE(storageOffset, BaseSize - 1);
0171     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0172
0173     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize);
0174     QVERIFY(result);
0175     QCOMPARE(storageOffset, ChangeStart);
0176     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0177
0178     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize + Width - 1);
0179     QVERIFY(result);
0180     QCOMPARE(storageOffset, ChangeEnd);
0181     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0182
0183     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize + Width);
0184     QVERIFY(!result);
0185
0186     // inserting a lot:
0187     // inserting before, after and in another inserted section, two recursions
0188     // 121110  8 7 6  4 3 2
0189     // \/\/\/ \/\/\/ \/\/\/
0190     //  |-9-|  |-5-|  |-1-|
0191     //  \  /   \  /   \  /
0192     //   \/     \/     \/
0193     //    |-----0-------|
0194     // TODO: do this also in forward sequences
0195     pieceTable.init(BaseSize);   // 0
0196     const Address Mid = BaseSize / 2;
0197     Address changeStarts[13];
0198     Address changeStart = 0;
0199     changeStarts[1] = changeStart;
0200     pieceTable.insert(BaseSize, BaseSize, changeStart);   // 1
0201     changeStart += BaseSize;
0202     changeStarts[2] = changeStart;
0203     pieceTable.insert(BaseSize + BaseSize, BaseSize, changeStart); // 2
0204     changeStart += BaseSize;
0205     changeStarts[3] = changeStart;
0206     pieceTable.insert(BaseSize + Mid, BaseSize, changeStart); // 3
0207     changeStart += BaseSize;
0208     changeStarts[4] = changeStart;
0209     pieceTable.insert(BaseSize, BaseSize, changeStart);   // 4
0210
0211     changeStart += BaseSize;
0212     changeStarts[5] = changeStart;
0213     pieceTable.insert(Mid, BaseSize, changeStart);   // 5
0214     changeStart += BaseSize;
0215     changeStarts[6] = changeStart;
0216     pieceTable.insert(Mid + BaseSize, BaseSize, changeStart); // 6
0217     changeStart += BaseSize;
0218     changeStarts[7] = changeStart;
0219     pieceTable.insert(Mid + Mid, BaseSize, changeStart); // 7
0220     changeStart += BaseSize;
0221     changeStarts[8] = changeStart;
0222     pieceTable.insert(Mid, BaseSize, changeStart);   // 8
0223
0224     changeStart += BaseSize;
0225     changeStarts[9] = changeStart;
0226     pieceTable.insert(0, BaseSize, changeStart);   // 9
0227     changeStart += BaseSize;
0228     changeStarts[10] = changeStart;
0229     pieceTable.insert(BaseSize, BaseSize, changeStart);   // 10
0230     changeStart += BaseSize;
0231     changeStarts[11] = changeStart;
0232     pieceTable.insert(Mid, BaseSize, changeStart);   // 11
0233     changeStart += BaseSize;
0234     changeStarts[12] = changeStart;
0235     pieceTable.insert(0, BaseSize, changeStart);   // 12
0236
0237     // test
0238     QCOMPARE(pieceTable.size(), BaseSize + 12 * BaseSize);
0239     // all borders
0240     // 12: begin
0241     Address byteArrayOffset = 0;
0242     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0243     QVERIFY(result);
0244     QCOMPARE(storageOffset, changeStarts[12]);
0245     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0246
0247     // 12: end
0248     byteArrayOffset += BaseSize;
0249     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0250     QVERIFY(result);
0251     QCOMPARE(storageOffset, changeStarts[12] + BaseSize - 1);
0252     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0253     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0254     QVERIFY(result);
0255     QCOMPARE(storageOffset, changeStarts[9]);
0256     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0257
0258     // 11: begin
0259     byteArrayOffset += HalfBaseSize;
0260     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0261     QVERIFY(result);
0262     QCOMPARE(storageOffset, changeStarts[9] + HalfBaseSize - 1);
0263     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0264     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0265     QVERIFY(result);
0266     QCOMPARE(storageOffset, changeStarts[11]);
0267     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0268
0269     // 11: end
0270     byteArrayOffset += BaseSize;
0271     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0272     QVERIFY(result);
0273     QCOMPARE(storageOffset, changeStarts[11] + BaseSize - 1);
0274     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0275     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0276     QVERIFY(result);
0277     QCOMPARE(storageOffset, changeStarts[9] + HalfBaseSize);
0278     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0279
0280     // 10: begin
0281     byteArrayOffset += HalfBaseSize;
0282     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0283     QVERIFY(result);
0284     QCOMPARE(storageOffset, changeStarts[9] + BaseSize - 1);
0285     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0286     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0287     QVERIFY(result);
0288     QCOMPARE(storageOffset, changeStarts[10]);
0289     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0290
0291     // 10: end
0292     byteArrayOffset += BaseSize;
0293     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0294     QVERIFY(result);
0295     QCOMPARE(storageOffset, changeStarts[10] + BaseSize - 1);
0296     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0297     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0298     QVERIFY(result);
0299     QCOMPARE(storageOffset, 0);
0300     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0301
0302     // 8: begin
0303     byteArrayOffset += HalfBaseSize;
0304     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0305     QVERIFY(result);
0306     QCOMPARE(storageOffset, HalfBaseSize - 1);
0307     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0308     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0309     QVERIFY(result);
0310     QCOMPARE(storageOffset, changeStarts[8]);
0311     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0312
0313     // 8: end
0314     byteArrayOffset += BaseSize;
0315     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0316     QVERIFY(result);
0317     QCOMPARE(storageOffset, changeStarts[8] + BaseSize - 1);
0318     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0319     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0320     QVERIFY(result);
0321     QCOMPARE(storageOffset, changeStarts[5]);
0322     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0323
0324     // 7: begin
0325     byteArrayOffset += HalfBaseSize;
0326     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0327     QVERIFY(result);
0328     QCOMPARE(storageOffset, changeStarts[5] + HalfBaseSize - 1);
0329     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0330     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0331     QVERIFY(result);
0332     QCOMPARE(storageOffset, changeStarts[7]);
0333     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0334
0335     // 7: end
0336     byteArrayOffset += BaseSize;
0337     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0338     QVERIFY(result);
0339     QCOMPARE(storageOffset, changeStarts[7] + BaseSize - 1);
0340     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0341     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0342     QVERIFY(result);
0343     QCOMPARE(storageOffset, changeStarts[5] + HalfBaseSize);
0344     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0345
0346     // 6: begin
0347     byteArrayOffset += HalfBaseSize;
0348     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0349     QVERIFY(result);
0350     QCOMPARE(storageOffset, changeStarts[5] + BaseSize - 1);
0351     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0352     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0353     QVERIFY(result);
0354     QCOMPARE(storageOffset, changeStarts[6]);
0355     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0356
0357     // 6: end
0358     byteArrayOffset += BaseSize;
0359     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0360     QVERIFY(result);
0361     QCOMPARE(storageOffset, changeStarts[6] + BaseSize - 1);
0362     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0363     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0364     QVERIFY(result);
0365     QCOMPARE(storageOffset, HalfBaseSize);
0366     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0367
0368     // 4: begin
0369     byteArrayOffset += HalfBaseSize;
0370     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0371     QVERIFY(result);
0372     QCOMPARE(storageOffset, BaseSize - 1);
0373     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0374     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0375     QVERIFY(result);
0376     QCOMPARE(storageOffset, changeStarts[4]);
0377     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0378
0379     // 4: end
0380     byteArrayOffset += BaseSize;
0381     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0382     QVERIFY(result);
0383     QCOMPARE(storageOffset, changeStarts[4] + BaseSize - 1);
0384     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0385     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0386     QVERIFY(result);
0387     QCOMPARE(storageOffset, changeStarts[1]);
0388     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0389
0390     // 3: begin
0391     byteArrayOffset += HalfBaseSize;
0392     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0393     QVERIFY(result);
0394     QCOMPARE(storageOffset, changeStarts[1] + HalfBaseSize - 1);
0395     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0396     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0397     QVERIFY(result);
0398     QCOMPARE(storageOffset, changeStarts[3]);
0399     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0400
0401     // 3: end
0402     byteArrayOffset += BaseSize;
0403     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0404     QVERIFY(result);
0405     QCOMPARE(storageOffset, changeStarts[3] + BaseSize - 1);
0406     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0407     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0408     QVERIFY(result);
0409     QCOMPARE(storageOffset, changeStarts[1] + HalfBaseSize);
0410     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0411
0412     // 2: begin
0413     byteArrayOffset += HalfBaseSize;
0414     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0415     QVERIFY(result);
0416     QCOMPARE(storageOffset, changeStarts[1] + BaseSize - 1);
0417     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0418     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0419     QVERIFY(result);
0420     QCOMPARE(storageOffset, changeStarts[2]);
0421     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0422
0423     // 2: end
0424     byteArrayOffset += BaseSize;
0425     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset - 1);
0426     QVERIFY(result);
0427     QCOMPARE(storageOffset, changeStarts[2] + BaseSize - 1);
0428     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0429
0430     result = pieceTable.getStorageData(&storageId, &storageOffset, byteArrayOffset);
0431     QVERIFY(!result);
0432 }
0433
0434 void PieceTableTest::testRemove()
0435 {
0436     PieceTable pieceTable;
0437
0438     Address changeStarts[6];
0439     int storageId;
0440     Address storageOffset;
0441     bool result;
0442
0443     // removing at begin
0444     pieceTable.init(BaseSize);
0445     pieceTable.remove(AddressRange(0, Start - 1));
0446
0447     QCOMPARE(pieceTable.size(), BaseSize - Start);
0448     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0449     QVERIFY(result);
0450     QCOMPARE(storageOffset, Start);
0451     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0452
0453     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - Start - 1);
0454     QVERIFY(result);
0455     QCOMPARE(storageOffset, BaseSize - 1);
0456     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0457
0458     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - Start);
0459     QVERIFY(!result);
0460
0461     // removing at middle
0462     pieceTable.init(BaseSize);
0463     pieceTable.remove(AddressRange(Start, End));
0464
0465     QCOMPARE(pieceTable.size(), BaseSize - Width);
0466     result = pieceTable.getStorageData(&storageId, &storageOffset, Start - 1);
0467     QVERIFY(result);
0468     QCOMPARE(storageOffset, Start - 1);
0469     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0470
0471     result = pieceTable.getStorageData(&storageId, &storageOffset, Start);
0472     QVERIFY(result);
0473     QCOMPARE(storageOffset, End + 1);
0474     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0475
0476     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - Width - 1);
0477     QVERIFY(result);
0478     QCOMPARE(storageOffset, BaseSize - 1);
0479     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0480
0481     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - Width);
0482     QVERIFY(!result);
0483
0484     // removing at end
0485     pieceTable.init(BaseSize);
0486     pieceTable.remove(AddressRange(End + 1, BaseSize - 1));
0487
0488     QCOMPARE(pieceTable.size(), End + 1);
0489     result = pieceTable.getStorageData(&storageId, &storageOffset, End);
0490     QVERIFY(result);
0491     QCOMPARE(storageOffset, End);
0492     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0493
0494     result = pieceTable.getStorageData(&storageId, &storageOffset, End + 1);
0495     QVERIFY(!result);
0496
0497     // removing all
0498     pieceTable.init(BaseSize);
0499     pieceTable.remove(AddressRange::fromWidth(BaseSize));
0500
0501     QCOMPARE(pieceTable.size(), 0);
0502     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0503     QVERIFY(!result);
0504
0505     // removing a lot:
0506     const int pieceCount = 5;
0507     const int mid = (pieceCount + 1) / 2;
0508     const Address midPieceOffset = BaseSize * (mid - 1);
0509     const Size fullSize = pieceCount * BaseSize;
0510     // for this five equally sized pieces are inserted, reverse to offset in ChangeStore
0511     for (int i = 0; i < pieceCount; ++i) {
0512         changeStarts[pieceCount - i] = BaseSize * i;
0513     }
0514
0515     // removing inside a piece in the middle
0516     fillWithSize(&pieceTable, pieceCount);
0517     pieceTable.remove(AddressRange::fromWidth(midPieceOffset + Start, Width));
0518
0519     QCOMPARE(pieceTable.size(), fullSize - Width);
0520
0521     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset + Start - 1);
0522     QVERIFY(result);
0523     QCOMPARE(storageOffset, changeStarts[mid] + Start - 1);
0524     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0525
0526     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset + Start);
0527     QVERIFY(result);
0528     QCOMPARE(storageOffset, changeStarts[mid] + End + 1);
0529     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0530
0531     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - Width - 1);
0532     QVERIFY(result);
0533     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0534     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0535
0536     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - Width);
0537     QVERIFY(!result);
0538
0539     // removing start of a piece in the middle
0540     fillWithSize(&pieceTable, pieceCount);
0541     pieceTable.remove(AddressRange::fromWidth(midPieceOffset, Start));
0542
0543     QCOMPARE(pieceTable.size(), fullSize - Start);
0544
0545     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - 1);
0546     QVERIFY(result);
0547     QCOMPARE(storageOffset, changeStarts[mid - 1] + BaseSize - 1);
0548     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0549
0550     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset);
0551     QVERIFY(result);
0552     QCOMPARE(storageOffset, changeStarts[mid] + Start);
0553     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0554
0555     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - Start - 1);
0556     QVERIFY(result);
0557     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0558     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0559
0560     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - Start);
0561     QVERIFY(!result);
0562
0563     // removing end of a piece in the middle
0564     fillWithSize(&pieceTable, pieceCount);
0565     pieceTable.remove(AddressRange::fromWidth(midPieceOffset + End + 1, BaseSize - (End + 1)));
0566
0567     QCOMPARE(pieceTable.size(), fullSize - (BaseSize - End - 1));
0568
0569     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset + End);
0570     QVERIFY(result);
0571     QCOMPARE(storageOffset, changeStarts[mid] + End);
0572     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0573
0574     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset + End + 1);
0575     QVERIFY(result);
0576     QCOMPARE(storageOffset, changeStarts[mid + 1]);
0577     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0578
0579     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - (BaseSize - End - 1) - 1);
0580     QVERIFY(result);
0581     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0582     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0583
0584     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - (BaseSize - End - 1));
0585     QVERIFY(!result);
0586
0587     // removing whole piece in the middle
0588     fillWithSize(&pieceTable, pieceCount);
0589     pieceTable.remove(AddressRange::fromWidth(midPieceOffset, BaseSize));
0590
0591     QCOMPARE(pieceTable.size(), fullSize - BaseSize);
0592
0593     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - 1);
0594     QVERIFY(result);
0595     QCOMPARE(storageOffset, changeStarts[mid - 1] + BaseSize - 1);
0596     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0597
0598     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset);
0599     QVERIFY(result);
0600     QCOMPARE(storageOffset, changeStarts[mid + 1]);
0601     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0602
0603     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - 1);
0604     QVERIFY(result);
0605     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0606     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0607
0608     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize);
0609     QVERIFY(!result);
0610
0611     // removing whole piece and start of next in the middke
0612     fillWithSize(&pieceTable, pieceCount);
0613     pieceTable.remove(AddressRange::fromWidth(midPieceOffset, BaseSize + Start));
0614
0615     QCOMPARE(pieceTable.size(), fullSize - BaseSize - Start);
0616
0617     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - 1);
0618     QVERIFY(result);
0619     QCOMPARE(storageOffset, changeStarts[mid - 1] + BaseSize - 1);
0620     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0621
0622     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset);
0623     QVERIFY(result);
0624     QCOMPARE(storageOffset, changeStarts[mid + 1] + Start);
0625     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0626
0627     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - Start - 1);
0628     QVERIFY(result);
0629     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0630     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0631
0632     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - Start);
0633     QVERIFY(!result);
0634
0635     // removing whole piece and end of previous in the middle
0636     fillWithSize(&pieceTable, pieceCount);
0637     pieceTable.remove(AddressRange::fromWidth(midPieceOffset - (BaseSize - End - 1), BaseSize + BaseSize - (End + 1)));
0638
0639     QCOMPARE(pieceTable.size(), fullSize - BaseSize - (BaseSize - End - 1));
0640
0641     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - (BaseSize - End - 1) - 1);
0642     QVERIFY(result);
0643     QCOMPARE(storageOffset, changeStarts[mid - 1] + End);
0644     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0645
0646     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - (BaseSize - End - 1));
0647     QVERIFY(result);
0648     QCOMPARE(storageOffset, changeStarts[mid + 1]);
0649     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0650
0651     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - (BaseSize - End - 1) - 1);
0652     QVERIFY(result);
0653     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0654     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0655
0656     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - (BaseSize - End - 1));
0657     QVERIFY(!result);
0658
0659     // removing end of previous, whole and start of next in the middle
0660     fillWithSize(&pieceTable, pieceCount);
0661     pieceTable.remove(AddressRange::fromWidth(midPieceOffset - (BaseSize - End - 1), Start + BaseSize + BaseSize - (End + 1)));
0662
0663     QCOMPARE(pieceTable.size(), fullSize - BaseSize - (BaseSize - End - 1) - Start);
0664
0665     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - (BaseSize - End - 1) - 1);
0666     QVERIFY(result);
0667     QCOMPARE(storageOffset, changeStarts[mid - 1] + BaseSize - (BaseSize - End - 1) - 1);
0668     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0669
0670     result = pieceTable.getStorageData(&storageId, &storageOffset, midPieceOffset - (BaseSize - End - 1));
0671     QVERIFY(result);
0672     QCOMPARE(storageOffset, changeStarts[mid + 1] + Start);
0673     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0674
0675     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - (BaseSize - End - 1) - Start - 1);
0676     QVERIFY(result);
0677     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0678     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0679
0680     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - (BaseSize - End - 1) - Start);
0681     QVERIFY(!result);
0682
0683     // removing start of piece at start
0684     fillWithSize(&pieceTable, pieceCount);
0685     pieceTable.remove(AddressRange::fromWidth(Start));
0686
0687     QCOMPARE(pieceTable.size(), fullSize - Start);
0688
0689     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0690     QVERIFY(result);
0691     QCOMPARE(storageOffset, changeStarts[1] + Start);
0692     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0693
0694     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - Start - 1);
0695     QVERIFY(result);
0696     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0697     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0698
0699     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - Start);
0700     QVERIFY(!result);
0701
0702     // removing whole piece at start
0703     fillWithSize(&pieceTable, pieceCount);
0704     pieceTable.remove(AddressRange::fromWidth(BaseSize));
0705
0706     QCOMPARE(pieceTable.size(), fullSize - BaseSize);
0707
0708     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0709     QVERIFY(result);
0710     QCOMPARE(storageOffset, changeStarts[2]);
0711     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0712
0713     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - 1);
0714     QVERIFY(result);
0715     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0716     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0717
0718     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize);
0719     QVERIFY(!result);
0720
0721     // removing whole piece and start of next at start
0722     fillWithSize(&pieceTable, pieceCount);
0723     pieceTable.remove(AddressRange::fromWidth(BaseSize + Start));
0724
0725     QCOMPARE(pieceTable.size(), fullSize - BaseSize - Start);
0726
0727     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0728     QVERIFY(result);
0729     QCOMPARE(storageOffset, changeStarts[2] + Start);
0730     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0731
0732     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - Start - 1);
0733     QVERIFY(result);
0734     QCOMPARE(storageOffset, changeStarts[pieceCount] + BaseSize - 1);
0735     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0736
0737     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - Start);
0738     QVERIFY(!result);
0739
0740     // removing end of piece at end
0741     fillWithSize(&pieceTable, pieceCount);
0742     pieceTable.remove(AddressRange::fromWidth(fullSize - BaseSize + End + 1, BaseSize - (End + 1)));
0743
0744     QCOMPARE(pieceTable.size(), fullSize - (BaseSize - End - 1));
0745
0746     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize + End);
0747     QVERIFY(result);
0748     QCOMPARE(storageOffset, changeStarts[pieceCount] + End);
0749     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0750
0751     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - (BaseSize - End - 1));
0752     QVERIFY(!result);
0753
0754     // removing whole piece at end
0755     fillWithSize(&pieceTable, pieceCount);
0756     pieceTable.remove(AddressRange::fromWidth(fullSize - BaseSize, BaseSize));
0757
0758     QCOMPARE(pieceTable.size(), fullSize - BaseSize);
0759
0760     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - 1);
0761     QVERIFY(result);
0762     QCOMPARE(storageOffset, changeStarts[pieceCount - 1] + BaseSize - 1);
0763     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0764
0765     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize);
0766     QVERIFY(!result);
0767
0768     // removing whole piece and end of previous at end
0769     fillWithSize(&pieceTable, pieceCount);
0770     pieceTable.remove(AddressRange::fromWidth(fullSize - BaseSize - (BaseSize - End - 1), BaseSize + BaseSize - (End + 1)));
0771
0772     QCOMPARE(pieceTable.size(), fullSize - BaseSize - (BaseSize - End - 1));
0773
0774     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - (BaseSize - End - 1) - 1);
0775     QVERIFY(result);
0776     QCOMPARE(storageOffset, changeStarts[pieceCount - 1] + End);
0777     QCOMPARE(storageId, (int)Piece::ChangeStorage);
0778
0779     result = pieceTable.getStorageData(&storageId, &storageOffset, fullSize - BaseSize - (BaseSize - End - 1));
0780     QVERIFY(!result);
0781
0782     // removing all
0783     fillWithSize(&pieceTable, pieceCount);
0784     pieceTable.remove(AddressRange::fromWidth(fullSize));
0785
0786     QCOMPARE(pieceTable.size(), 0);
0787     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0788     QVERIFY(!result);
0789 }
0790
0791 void PieceTableTest::testSwap()
0792 {
0793     PieceTable pieceTable;
0794
0795     int storageId;
0796     Address storageOffset;
0797     bool result;
0798
0799     // moving end at begin
0800     pieceTable.init(BaseSize);
0801     pieceTable.swap(0, AddressRange::fromWidth(End + 1, BaseSize - (End + 1)));
0802
0803     QCOMPARE(pieceTable.size(), BaseSize);
0804
0805     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0806     QVERIFY(result);
0807     QCOMPARE(storageOffset, End + 1);
0808     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0809
0810     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - End - 2);
0811     QVERIFY(result);
0812     QCOMPARE(storageOffset, BaseSize - 1);
0813     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0814
0815     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - End - 1);
0816     QVERIFY(result);
0817     QCOMPARE(storageOffset, 0);
0818     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0819
0820     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - 1);
0821     QVERIFY(result);
0822     QCOMPARE(storageOffset, End);
0823     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0824
0825     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize);
0826     QVERIFY(!result);
0827
0828     // moving end at mid
0829     pieceTable.init(BaseSize);
0830     pieceTable.swap(Start, AddressRange::fromWidth(End + 1, BaseSize - (End + 1)));
0831
0832     QCOMPARE(pieceTable.size(), BaseSize);
0833
0834     result = pieceTable.getStorageData(&storageId, &storageOffset, Start - 1);
0835     QVERIFY(result);
0836     QCOMPARE(storageOffset, Start - 1);
0837     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0838
0839     QCOMPARE(pieceTable.size(), BaseSize);
0840     result = pieceTable.getStorageData(&storageId, &storageOffset, Start);
0841     QVERIFY(result);
0842     QCOMPARE(storageOffset, End + 1);
0843     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0844
0845     result = pieceTable.getStorageData(&storageId, &storageOffset, Start + BaseSize - End - 2);
0846     QVERIFY(result);
0847     QCOMPARE(storageOffset, BaseSize - 1);
0848     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0849
0850     result = pieceTable.getStorageData(&storageId, &storageOffset, Start + BaseSize - End - 1);
0851     QVERIFY(result);
0852     QCOMPARE(storageOffset, Start);
0853     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0854
0855     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize - 1);
0856     QVERIFY(result);
0857     QCOMPARE(storageOffset, End);
0858     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0859
0860     result = pieceTable.getStorageData(&storageId, &storageOffset, BaseSize);
0861     QVERIFY(!result);
0862
0863     // moving mid at begin
0864     pieceTable.init(BaseSize);
0865     pieceTable.swap(0, AddressRange::fromWidth(Start, Width));
0866
0867     QCOMPARE(pieceTable.size(), BaseSize);
0868
0869     QCOMPARE(pieceTable.size(), BaseSize);
0870     result = pieceTable.getStorageData(&storageId, &storageOffset, 0);
0871     QVERIFY(result);
0872     QCOMPARE(storageOffset, Start);
0873     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0874
0875     result = pieceTable.getStorageData(&storageId, &storageOffset, Width - 1);
0876     QVERIFY(result);
0877     QCOMPARE(storageOffset, End);
0878     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0879
0880     result = pieceTable.getStorageData(&storageId, &storageOffset, Width);
0881     QVERIFY(result);
0882     QCOMPARE(storageOffset, 0);
0883     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0884
0885     result = pieceTable.getStorageData(&storageId, &storageOffset, End);
0886     QVERIFY(result);
0887     QCOMPARE(storageOffset, Start - 1);
0888     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0889
0890     result = pieceTable.getStorageData(&storageId, &storageOffset, End + 1);
0891     QVERIFY(result);
0892     QCOMPARE(storageOffset, End + 1);
0893     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0894
0895     // moving mid at mid
0896     pieceTable.init(BaseSize);
0897     Address mid = (End + Start) / 2;
0898     pieceTable.swap(Start, AddressRange::fromWidth(mid, End - mid + 1));
0899
0900     QCOMPARE(pieceTable.size(), BaseSize);
0901
0902     result = pieceTable.getStorageData(&storageId, &storageOffset, Start - 1);
0903     QVERIFY(result);
0904     QCOMPARE(storageOffset, Start - 1);
0905     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0906
0907     result = pieceTable.getStorageData(&storageId, &storageOffset, Start);
0908     QVERIFY(result);
0909     QCOMPARE(storageOffset, mid);
0910     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0911
0912     result = pieceTable.getStorageData(&storageId, &storageOffset, Start + End - mid);
0913     QVERIFY(result);
0914     QCOMPARE(storageOffset, End);
0915     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0916
0917     result = pieceTable.getStorageData(&storageId, &storageOffset, Start + End - mid + 1);
0918     QVERIFY(result);
0919     QCOMPARE(storageOffset, Start);
0920     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0921
0922     result = pieceTable.getStorageData(&storageId, &storageOffset, End);
0923     QVERIFY(result);
0924     QCOMPARE(storageOffset, mid - 1);
0925     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0926
0927     result = pieceTable.getStorageData(&storageId, &storageOffset, End + 1);
0928     QVERIFY(result);
0929     QCOMPARE(storageOffset, End + 1);
0930     QCOMPARE(storageId, (int)Piece::OriginalStorage);
0931
0932     // moving a lot:
0933     const int pieceCount = 5;
0934     const Size fullSize = pieceCount * BaseSize;
0935
0936     // moving start of piece at start
0937     fillWithSize(&pieceTable, pieceCount);
0938     pieceTable.swap(Start, AddressRange::fromWidth(mid, End - mid + 1));
0939
0940     QCOMPARE(pieceTable.size(), fullSize);
0941     // TODO: add other tests
0942 }
0943
0944 }
0945
0946 QTEST_GUILESS_MAIN(KPieceTable::PieceTableTest)
0947
0948 #include "moc_piecetabletest.cpp"