Differential D380 Diff 929 serialization/itemrepository.h

Changeset View

Standalone View

View Options

serialization/itemrepository.h

Context not available.
467 /// @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. 467​ /// @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.
468 /// This this allows efficiently computing the clashes using the local object map hash. 468​ /// This this allows efficiently computing the clashes using the local object map hash.
469 469​
470 bool hasClashingItem(uint hash, uint modulo) { 470​ enum ClashType {
471​ NoClash,
472​ LocalClash,
473​ SearchClash,
474​ };
471 475​
472 Q_ASSERT(modulo % ObjectMapSize == 0); 476​ ClashType hasClashingItem(uint hash, uint searchMod = 0) {
mwolffUnsubmitted
Not Done

put brace on newline, make const?

mwolff: put brace on newline, make const?
473 477​
474 m_lastUsed = 0; 478​ m_lastUsed = 0;
475 479​
476 uint hashMod = hash % modulo; 480​ ushort currentIndex = m_objectMap[hash % m_objectMapSize];
477 unsigned short localHash = hash % m_objectMapSize; ​
478 unsigned short currentIndex = m_objectMap[localHash]; ​
479 481​
480 if(currentIndex == 0) 482​ if (!searchMod || !currentIndex)
481 return false; 483​ return currentIndex ? LocalClash : NoClash;
484​
485​ Q_ASSERT(searchMod % ObjectMapSize == 0);
486​ const uint hashModSearch = hash % searchMod;
482 487​
483 while(currentIndex) { 488​ while(currentIndex) {
484 uint currentHash = itemFromIndex(currentIndex)->hash(); 489​ uint currentHash = itemFromIndex(currentIndex)->hash();
485 490​
486 Q_ASSERT(currentHash % m_objectMapSize == localHash); 491​ if(currentHash % searchMod == hashModSearch)
487 492​ return SearchClash;
488 if(currentHash % modulo == hashMod) ​
489 return true; //Clash ​
490 currentIndex = followerIndex(currentIndex); 493​ currentIndex = followerIndex(currentIndex);
491 } 494​ }
492 return false; 495​ return LocalClash;
493 } 496​ }
494 497​
495 void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, uint& longestInBucketFollowerChain) { 498​ void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, uint& longestInBucketFollowerChain) {
Context not available.
1389 if (!previousBucketPtr) { 1392​ if (!previousBucketPtr) {
1390 // This bucket is linked in the m_firstBucketForHash array, find the next clashing bucket in the chain 1393​ // This bucket is linked in the m_firstBucketForHash array, find the next clashing bucket in the chain
1391 // There may be items in the chain that clash only with MyBucket::NextBucketHashSize, skipped here 1394​ // There may be items in the chain that clash only with MyBucket::NextBucketHashSize, skipped here
1392 m_firstBucketForHash[hash % bucketHashSize] = walkBucketChain(hash, [hash](ushort bucketIdx, MyBucket *bucketPtr){ 1395​ bool removedLastLocalClash = false;
1393 if (bucketPtr->hasClashingItem(hash, bucketHashSize)) { 1396​ m_firstBucketForHash[hash % bucketHashSize] =
1394 return bucketIdx; 1397​ walkBucketChain(hash, [=, &removedLastLocalClash](ushort bucketIdx, MyBucket *bucketPtr) -> ushort {
1398​ auto clashType = bucketPtr->hasClashingItem(hash, bucketHashSize);
1399​ if (clashType == MyBucket::SearchClash) {
1400​ return bucketIdx; // found bucket clashing with the root mod, this bucket becomes the new root
1395 } 1401​ }
1396 return static_cast<ushort>(0); 1402​ if (clashType == MyBucket::NoClash) {
1403​ // This should only be possible for the bucket from which the item was just deleted
1404​ // An item with no local clashes for a hash may not participate in the chain for it
1405​ Q_ASSERT(bucketIdx == bucket);
1406​ removedLastLocalClash = true;
1407​ }
1408​ return 0;
1397 }); 1409​ });
1398 } else if(!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSize)) { 1410​ if (removedLastLocalClash) {
1411​ bucketPtr->setNextBucketForHash(hash, 0);
1412​ }
1413​ } else if(bucketPtr->hasClashingItem(hash) == MyBucket::NoClash) {
1399 // TODO: Skip clashing items reachable from m_firstBucketForHash 1414​ // TODO: Skip clashing items reachable from m_firstBucketForHash
1400 // (see note in usePermissiveModuloWhenRemovingClashLinks() test) 1415​ // (see note in usePermissiveModuloWhenRemovingClashLinks() test)
1401 1416​
1402 ENSURE_REACHABLE(bucket); 1417​ ENSURE_REACHABLE(bucket);
1403 1418​
1404 previousBucketPtr->setNextBucketForHash(hash, bucketPtr->nextBucketForHash(hash)); 1419​ previousBucketPtr->setNextBucketForHash(hash, bucketPtr->nextBucketForHash(hash));
1420​ bucketPtr->setNextBucketForHash(hash, 0);
1405 1421​
1406 Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] != previousBucketPtr); 1422​ Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] != previousBucketPtr);
1407 } 1423​ }
Context not available.
1412 //Convert the monster-bucket back to multiple normal buckets, and put them into the free list 1428​ //Convert the monster-bucket back to multiple normal buckets, and put them into the free list
1413 uint newBuckets = bucketPtr->monsterBucketExtent()+1; 1429​ uint newBuckets = bucketPtr->monsterBucketExtent()+1;
1414 Q_ASSERT(bucketPtr->isEmpty()); 1430​ Q_ASSERT(bucketPtr->isEmpty());
1415 if (!previousBucketPtr) { ​
1416 // see https://bugs.kde.org/show_bug.cgi?id=272408 ​
1417 // the monster bucket will be deleted and new smaller ones created ​
1418 // the next bucket for this hash is invalid anyways as done above ​
1419 // but calling the below unconditionally leads to other issues... ​
1420 bucketPtr->setNextBucketForHash(hash, 0); ​
1421 } ​
1422 convertMonsterBucket(bucket, 0); 1431​ convertMonsterBucket(bucket, 0);
1423 for(uint created = bucket; created < bucket + newBuckets; ++created) { 1432​ for(uint created = bucket; created < bucket + newBuckets; ++created) {
1424 putIntoFreeList(created, bucketForIndex(created)); 1433​ putIntoFreeList(created, bucketForIndex(created));
Context not available.