From kde-commits Wed Oct 07 16:20:28 2015 From: Olivier JG Date: Wed, 07 Oct 2015 16:20:28 +0000 To: kde-commits Subject: [kdevplatform] serialization: Revert "Correctly remove stale next bucket links when items are remove Message-Id: X-MARC-Message: https://marc.info/?l=kde-commits&m=144423483925413 Git commit 0fe0ff4092ddf77452b5dff76cd072c3e33df72f by Olivier JG. Committed on 07/10/2015 at 16:24. Pushed by olivierjg into branch 'master'. Revert "Correctly remove stale next bucket links when items are removed" Newly added assertion triggers, this isn't working correctly This reverts commit b120aa6d0d6d1f76f81dfca0b668b20bf22461d9. M +25 -34 serialization/itemrepository.h M +0 -26 serialization/tests/test_itemrepository.cpp http://commits.kde.org/kdevplatform/0fe0ff4092ddf77452b5dff76cd072c3e33df72f diff --git a/serialization/itemrepository.h b/serialization/itemrepository.h index e670187..cb3b723 100644 --- a/serialization/itemrepository.h +++ b/serialization/itemrepository.h @@ -469,32 +469,29 @@ class Bucket { /// @param modulo MUST be a multiple of ObjectMapSize, be= cause (b-a) | (x * h1) =3D> (b-a) | h2, where a|b means a is a multiple of = b. /// This this allows efficiently computing = the clashes using the local object map hash. = - enum ClashType { - NoClash, - LocalClash, - SearchClash, - }; + bool hasClashingItem(uint hash, uint modulo) { = - ClashType hasClashingItem(uint hash, uint searchMod =3D 0) const - { - m_lastUsed =3D 0; + Q_ASSERT(modulo % ObjectMapSize =3D=3D 0); = - ushort currentIndex =3D m_objectMap[hash % m_objectMapSize]; + m_lastUsed =3D 0; = - if (!searchMod || !currentIndex) - return currentIndex ? LocalClash : NoClash; + uint hashMod =3D hash % modulo; + unsigned short localHash =3D hash % m_objectMapSize; + unsigned short currentIndex =3D m_objectMap[localHash]; = - Q_ASSERT(searchMod % ObjectMapSize =3D=3D 0); - const uint hashModSearch =3D hash % searchMod; + if(currentIndex =3D=3D 0) + return false; = while(currentIndex) { uint currentHash =3D itemFromIndex(currentIndex)->hash(); = - if(currentHash % searchMod =3D=3D hashModSearch) - return SearchClash; + Q_ASSERT(currentHash % m_objectMapSize =3D=3D localHash); + + if(currentHash % modulo =3D=3D hashMod) + return true; //Clash currentIndex =3D followerIndex(currentIndex); } - return LocalClash; + return false; } = void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& s= lotCount, uint& longestInBucketFollowerChain) { @@ -1394,32 +1391,19 @@ class ItemRepository : public AbstractItemRepositor= y { if (!previousBucketPtr) { // This bucket is linked in the m_firstBucketForHash array, find the= next clashing bucket in the chain // There may be items in the chain that clash only with MyBucket::Ne= xtBucketHashSize, skipped here - bool removedLastLocalClash =3D false; - m_firstBucketForHash[hash % bucketHashSize] =3D - walkBucketChain(hash, [=3D, &removedLastLocalClash](ushort bucketI= dx, MyBucket *bucketPtr) -> ushort { - auto clashType =3D bucketPtr->hasClashingItem(hash, bucketHashSize= ); - if (clashType =3D=3D MyBucket::SearchClash) { - return bucketIdx; // found bucket clashing with the root mod, = this bucket becomes the new root - } - if (clashType =3D=3D MyBucket::NoClash) { - // This should only be possible for the bucket from which the it= em was just deleted - // An item with no local clashes for a hash may not participate = in the chain for it - Q_ASSERT(bucketIdx =3D=3D bucket); - removedLastLocalClash =3D true; + m_firstBucketForHash[hash % bucketHashSize] =3D walkBucketChain(hash= , [hash](ushort bucketIdx, MyBucket *bucketPtr){ + if (bucketPtr->hasClashingItem(hash, bucketHashSize)) { + return bucketIdx; } - return 0; + return static_cast(0); }); - if (removedLastLocalClash) { - bucketPtr->setNextBucketForHash(hash, 0); - } - } else if(bucketPtr->hasClashingItem(hash) =3D=3D MyBucket::NoClash) { + } else if(!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSi= ze)) { // TODO: Skip clashing items reachable from m_firstBucketForHash // (see note in usePermissiveModuloWhenRemovingClashLinks() test) = ENSURE_REACHABLE(bucket); = previousBucketPtr->setNextBucketForHash(hash, bucketPtr->nextBucketF= orHash(hash)); - bucketPtr->setNextBucketForHash(hash, 0); = Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] !=3D previous= BucketPtr); } @@ -1430,6 +1414,13 @@ class ItemRepository : public AbstractItemRepository= { //Convert the monster-bucket back to multiple normal buckets, and pu= t them into the free list uint newBuckets =3D bucketPtr->monsterBucketExtent()+1; Q_ASSERT(bucketPtr->isEmpty()); + if (!previousBucketPtr) { + // see https://bugs.kde.org/show_bug.cgi?id=3D272408 + // the monster bucket will be deleted and new smaller ones created + // the next bucket for this hash is invalid anyways as done above + // but calling the below unconditionally leads to other issues... + bucketPtr->setNextBucketForHash(hash, 0); + } convertMonsterBucket(bucket, 0); for(uint created =3D bucket; created < bucket + newBuckets; ++create= d) { putIntoFreeList(created, bucketForIndex(created)); diff --git a/serialization/tests/test_itemrepository.cpp b/serialization/te= sts/test_itemrepository.cpp index a2cb9fa..0fbce93 100644 --- a/serialization/tests/test_itemrepository.cpp +++ b/serialization/tests/test_itemrepository.cpp @@ -259,7 +259,6 @@ class TestItemRepository : public QObject { // Choose sizes that ensure that the items fit in the desired buckets const uint bigItemSize =3D KDevelop::ItemRepositoryBucketSize * 0.55= - 1; const uint smallItemSize =3D KDevelop::ItemRepositoryBucketSize * 0.= 25 - 1; - const uint monsterItemSize =3D KDevelop::ItemRepositoryBucketSize * = 1.1; = // Will get placed in bucket 1 (bucket zero is invalid), so the root= bucket table at position 'clashValue' will be '1' const QScopedPointer firstChainFirstLink(createItem(clashV= alue, bigItemSize)); @@ -350,31 +349,6 @@ class TestItemRepository : public QObject { * So TODO: Don't preserve links to items accessible from root bucke= ts. This cannot * be done correctly using only Bucket::hasClashingItem as of now. */ - - // Re-using the first chain above, we link a monster to the end - const QScopedPointer firstChainSecondLinkMonster(createIte= m(bucketHashSize + clashValue, monsterItemSize)); - const uint firstChainSecondLinkMonsterIndex =3D repository.index(*fi= rstChainSecondLinkMonster); - QCOMPARE(bucketNumberForIndex(firstChainSecondLinkMonsterIndex), 3u); - - // And link another monster to that one - const QScopedPointer firstChainThirdLink(createItem(bucket= HashSize * 2 + clashValue, monsterItemSize)); - const uint firstChainThirdLinkIndex =3D repository.index(*firstChain= ThirdLink); - QCOMPARE(bucketNumberForIndex(firstChainThirdLinkIndex), 5u); - - /* - * Now we cut the second monster out of the chain. - * - * What this test really cares about is that the stale link has been= removed before the monster is destroyed. - * - * Monsters that are destroyed assert that they have no further link= s. That wouldn't make sense, as monsters - * can only contain a single item, so removing it means it should be= completely cut from the chain. - * - * If stale links are correctly detected and destroyed when items ar= e removed, this will succeed. - * - * See also deleteClashingMonsterBucket() above, which tests this co= ndition for root buckets - */ - repository.deleteItem(firstChainSecondLinkMonsterIndex); - QCOMPARE(repository.findIndex(*firstChainThirdLink), firstChainThird= LinkIndex); } }; =20