[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: [kdevplatform] serialization: Revert "Correctly remove stale next bucket links when items are remove
From: Olivier JG <olivier.jg () gmail ! com>
Date: 2015-10-07 16:20:28
Message-ID: E1ZjrS8-0000ZR-W3 () scm ! kde ! org
[Download RAW message or body]
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, because \
(b-a) | (x * h1) => (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 = 0) const
- {
- m_lastUsed = 0;
+ Q_ASSERT(modulo % ObjectMapSize == 0);
- ushort currentIndex = m_objectMap[hash % m_objectMapSize];
+ m_lastUsed = 0;
- if (!searchMod || !currentIndex)
- return currentIndex ? LocalClash : NoClash;
+ uint hashMod = hash % modulo;
+ unsigned short localHash = hash % m_objectMapSize;
+ unsigned short currentIndex = m_objectMap[localHash];
- Q_ASSERT(searchMod % ObjectMapSize == 0);
- const uint hashModSearch = hash % searchMod;
+ if(currentIndex == 0)
+ return false;
while(currentIndex) {
uint currentHash = itemFromIndex(currentIndex)->hash();
- if(currentHash % searchMod == hashModSearch)
- return SearchClash;
+ Q_ASSERT(currentHash % m_objectMapSize == localHash);
+
+ if(currentHash % modulo == hashMod)
+ return true; //Clash
currentIndex = followerIndex(currentIndex);
}
- return LocalClash;
+ return false;
}
void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, \
uint& longestInBucketFollowerChain) { @@ -1394,32 +1391,19 @@ class ItemRepository : \
public AbstractItemRepository { 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::NextBucketHashSize, skipped here
- bool removedLastLocalClash = false;
- m_firstBucketForHash[hash % bucketHashSize] =
- walkBucketChain(hash, [=, &removedLastLocalClash](ushort bucketIdx, MyBucket \
*bucketPtr) -> ushort {
- auto clashType = bucketPtr->hasClashingItem(hash, bucketHashSize);
- if (clashType == MyBucket::SearchClash) {
- return bucketIdx; // found bucket clashing with the root mod, this \
bucket becomes the new root
- }
- if (clashType == MyBucket::NoClash) {
- // This should only be possible for the bucket from which the item was \
just deleted
- // An item with no local clashes for a hash may not participate in the \
chain for it
- Q_ASSERT(bucketIdx == bucket);
- removedLastLocalClash = true;
+ m_firstBucketForHash[hash % bucketHashSize] = walkBucketChain(hash, \
[hash](ushort bucketIdx, MyBucket *bucketPtr){ + if \
(bucketPtr->hasClashingItem(hash, bucketHashSize)) { + return bucketIdx;
}
- return 0;
+ return static_cast<ushort>(0);
});
- if (removedLastLocalClash) {
- bucketPtr->setNextBucketForHash(hash, 0);
- }
- } else if(bucketPtr->hasClashingItem(hash) == MyBucket::NoClash) {
+ } else if(!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSize)) {
// TODO: Skip clashing items reachable from m_firstBucketForHash
// (see note in usePermissiveModuloWhenRemovingClashLinks() test)
ENSURE_REACHABLE(bucket);
previousBucketPtr->setNextBucketForHash(hash, \
bucketPtr->nextBucketForHash(hash));
- bucketPtr->setNextBucketForHash(hash, 0);
Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] != previousBucketPtr);
}
@@ -1430,6 +1414,13 @@ class ItemRepository : public AbstractItemRepository {
//Convert the monster-bucket back to multiple normal buckets, and put them \
into the free list uint newBuckets = bucketPtr->monsterBucketExtent()+1;
Q_ASSERT(bucketPtr->isEmpty());
+ if (!previousBucketPtr) {
+ // see https://bugs.kde.org/show_bug.cgi?id=272408
+ // 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 = bucket; created < bucket + newBuckets; ++created) {
putIntoFreeList(created, bucketForIndex(created));
diff --git a/serialization/tests/test_itemrepository.cpp \
b/serialization/tests/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 = KDevelop::ItemRepositoryBucketSize * 0.55 - 1;
const uint smallItemSize = KDevelop::ItemRepositoryBucketSize * 0.25 - 1;
- const uint monsterItemSize = 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<TestItem> firstChainFirstLink(createItem(clashValue, \
bigItemSize)); @@ -350,31 +349,6 @@ class TestItemRepository : public QObject {
* So TODO: Don't preserve links to items accessible from root buckets. 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<TestItem> \
firstChainSecondLinkMonster(createItem(bucketHashSize + clashValue, \
monsterItemSize));
- const uint firstChainSecondLinkMonsterIndex = \
repository.index(*firstChainSecondLinkMonster);
- QCOMPARE(bucketNumberForIndex(firstChainSecondLinkMonsterIndex), 3u);
-
- // And link another monster to that one
- const QScopedPointer<TestItem> firstChainThirdLink(createItem(bucketHashSize * \
2 + clashValue, monsterItemSize));
- const uint firstChainThirdLinkIndex = repository.index(*firstChainThirdLink);
- 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 links. 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 are removed, \
this will succeed.
- *
- * See also deleteClashingMonsterBucket() above, which tests this condition \
for root buckets
- */
- repository.deleteItem(firstChainSecondLinkMonsterIndex);
- QCOMPARE(repository.findIndex(*firstChainThirdLink), \
firstChainThirdLinkIndex); }
};
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic