Differential D285 Diff 925 serialization/itemrepository.h

Changeset View

Standalone View

View Options

serialization/itemrepository.h

Context not available.
1104 1104​
1105 ThisLocker lock(m_mutex); 1105​ ThisLocker lock(m_mutex);
1106 1106​
1107 unsigned int hash = request.hash(); 1107​ const uint hash = request.hash();
1108 unsigned int size = request.itemSize(); 1108​ const uint size = request.itemSize();
1109 1109​
1110 short unsigned int* bucketHashPosition = m_firstBucketForHash + (hash % bucketHashSize); 1110​ // Bucket indexes tracked while walking the bucket chain for this request hash
1111 short unsigned int previousBucketNumber = *bucketHashPosition; 1111​ unsigned short bucketInChainWithSpace = 0;
1112 1112​ unsigned short lastBucketWalked = 0;
1113 int useBucket = m_currentBucket; ​
1114 bool pickedBucketInChain = false; //Whether a bucket was picked for re-use that already is in the hash chain ​
1115 int reOrderFreeSpaceBucketIndex = -1; ​
1116 1113​
1117 while(previousBucketNumber) { 1114​ const ushort foundIndexInBucket = walkBucketChain(hash, [&](ushort bucketIdx, const MyBucket* bucketPtr) {
1118 //We have a bucket that contains an item with the given hash % bucketHashSize, so check if the item is already there 1115​ lastBucketWalked = bucketIdx;
1119 MyBucket* bucketPtr = m_buckets[previousBucketNumber]; ​
1120 if(!bucketPtr) { ​
1121 initializeBucket(previousBucketNumber); ​
1122 bucketPtr = m_buckets[previousBucketNumber]; ​
1123 } ​
1124 1116​
1125 unsigned short indexInBucket = bucketPtr->findIndex(request); 1117​ const ushort found = bucketPtr->findIndex(request);
1126 if(indexInBucket) { ​
1127 //We've found the item, it's already there ​
1128 uint index = (previousBucketNumber << 16) + indexInBucket; ​
1129 verifyIndex(index); ​
1130 return index; //Combine the index in the bucket, and the bucker number into one index ​
1131 } else { ​
1132#ifdef DEBUG_HASH_SEQUENCES ​
1133 if(previousBucketNumber==*bucketHashPosition) ​
1134 Q_ASSERT(bucketPtr->hasClashingItem(hash, bucketHashSize)); ​
1135 else ​
1136 Q_ASSERT(bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSize)); ​
1137#endif ​
1138 1118​
1139 if(!pickedBucketInChain && bucketPtr->canAllocateItem(size)) { 1119​ if (!found && !bucketInChainWithSpace && bucketPtr->canAllocateItem(size)) {
1140 //Remember that this bucket has enough space to store the item, if it isn't already stored. 1120​ bucketInChainWithSpace = bucketIdx;
1141 //This gives a better structure, and saves us from cyclic follower structures. ​
1142 useBucket = previousBucketNumber; ​
1143 reOrderFreeSpaceBucketIndex = m_freeSpaceBuckets.indexOf(useBucket); ​
1144 pickedBucketInChain = true; ​
1145 } ​
1146 //The item isn't in bucket previousBucketNumber, but maybe the bucket has a pointer to the next bucket that might contain the item ​
1147 //Should happen rarely ​
1148 short unsigned int next = bucketPtr->nextBucketForHash(hash); ​
1149 if(next) { ​
1150 previousBucketNumber = next; ​
1151 } else ​
1152 break; ​
1153 } 1121​ }
1154 } 1122​
1123​ return found;
1124​ });
1125​
1126​ if (foundIndexInBucket) {
1127​ // 'request' is already present, return the existing index
1128​ return createIndex(lastBucketWalked, foundIndexInBucket);
1129​ }
1130​
1131​ /*
1132​ * Disclaimer: Writer of comment != writer of code, believe with caution
1133​ *
1134​ * Requested item does not yet exist. Need to find a place to put it...
1135​ *
1136​ * First choice is to place it in an existing bucket in the chain for the request hash
1137​ * Second choice is to find an existing bucket anywhere with enough space
1138​ * Otherwise use m_currentBucket (the latest unused bucket)
1139​ *
1140​ * If the chosen bucket fails to allocate the item, merge buckets to create a monster (dragon?)
1141​ *
1142​ * Finally, if the first option failed or the selected bucket failed to allocate, add the
1143​ * bucket which the item ended up in to the chain of buckets for the request's hash
1144​ */
1155 1145​
1156 m_metaDataChanged = true; 1146​ m_metaDataChanged = true;
1157 1147​
1158 if(!pickedBucketInChain && useBucket == m_currentBucket) { 1148​ const bool pickedBucketInChain = bucketInChainWithSpace;
1149​ int useBucket = bucketInChainWithSpace;
1150​ int reOrderFreeSpaceBucketIndex = -1;
1151​
1152​ if (!pickedBucketInChain) {
1159 //Try finding an existing bucket with deleted space to store the data into 1153​ //Try finding an existing bucket with deleted space to store the data into
1160 for(int a = 0; a < m_freeSpaceBuckets.size(); ++a) { 1154​ for(int a = 0; a < m_freeSpaceBuckets.size(); ++a) {
1161 MyBucket* bucketPtr = bucketForIndex(m_freeSpaceBuckets[a]); 1155​ MyBucket* bucketPtr = bucketForIndex(m_freeSpaceBuckets[a]);
Context not available.
1168 break; 1162​ break;
1169 } 1163​ }
1170 } 1164​ }
1165​
1166​ if (!useBucket) {
1167​ useBucket = m_currentBucket;
1168​ }
1169​ } else {
1170​ reOrderFreeSpaceBucketIndex = m_freeSpaceBuckets.indexOf(useBucket);
1171 } 1171​ }
1172 1172​
1173 //The item isn't in the repository yet, find a new bucket for it 1173​ //The item isn't in the repository yet, find a new bucket for it
Context not available.
1257 if(indexInBucket) { 1257​ if(indexInBucket) {
1258 ++m_statItemCount; 1258​ ++m_statItemCount;
1259 1259​
1260​ const int previousBucketNumber = lastBucketWalked;
1261​ unsigned short* const bucketHashPosition = m_firstBucketForHash + (hash % bucketHashSize);
1262​
1260 if(!(*bucketHashPosition)) { 1263​ if(!(*bucketHashPosition)) {
1261 Q_ASSERT(!previousBucketNumber); 1264​ Q_ASSERT(!previousBucketNumber);
1262 (*bucketHashPosition) = useBucket; 1265​ (*bucketHashPosition) = useBucket;
Context not available.
1322 if(reOrderFreeSpaceBucketIndex != -1) 1325​ if(reOrderFreeSpaceBucketIndex != -1)
1323 updateFreeSpaceOrder(reOrderFreeSpaceBucketIndex); 1326​ updateFreeSpaceOrder(reOrderFreeSpaceBucketIndex);
1324 1327​
1325 //Combine the index in the bucket, and the bucker number into one index 1328​ return createIndex(useBucket, indexInBucket);
1326 uint index = (useBucket << 16) + indexInBucket; ​
1327 verifyIndex(index); ​
1328 return index; ​
1329 }else{ 1329​ }else{
1330 //This should never happen when we picked a bucket for re-use 1330​ //This should never happen when we picked a bucket for re-use
1331 Q_ASSERT(!pickedBucketInChain); 1331​ Q_ASSERT(!pickedBucketInChain);
Context not available.
1351 1351​
1352 ThisLocker lock(m_mutex); 1352​ ThisLocker lock(m_mutex);
1353 1353​
1354 unsigned int hash = request.hash(); 1354​ return walkBucketChain(request.hash(), [this, &request](ushort bucketIdx, const MyBucket* bucketPtr) {
1355 1355​ const ushort indexInBucket = bucketPtr->findIndex(request);
1356 short unsigned int* bucketHashPosition = m_firstBucketForHash + (hash % bucketHashSize); 1356​ return indexInBucket ? createIndex(bucketIdx, indexInBucket) : 0u;
1357 short unsigned int previousBucketNumber = *bucketHashPosition; 1357​ });
mwolffUnsubmitted
Not Done

replace [&] with [this, request].

and as I say below, I find it odd that the return value decides both whether the loop is stopped, and the return value of the walkBucketChain method.

mwolff: replace `[&]` with `[this, request]`. and as I say below, I find it odd that the return value…
1358 ​
1359 while(previousBucketNumber) { ​
1360 //We have a bucket that contains an item with the given hash % bucketHashSize, so check if the item is already there ​
1361 ​
1362 MyBucket* bucketPtr = m_buckets[previousBucketNumber]; ​
1363 if(!bucketPtr) { ​
1364 initializeBucket(previousBucketNumber); ​
1365 bucketPtr = m_buckets[previousBucketNumber]; ​
1366 } ​
1367 ​
1368 unsigned short indexInBucket = bucketPtr->findIndex(request); ​
1369 if(indexInBucket) { ​
1370 //We've found the item, it's already there ​
1371 uint index = (previousBucketNumber << 16) + indexInBucket; //Combine the index in the bucket, and the bucker number into one index ​
1372 verifyIndex(index); ​
1373 return index; ​
1374 } else { ​
1375 //The item isn't in bucket previousBucketNumber, but maybe the bucket has a pointer to the next bucket that might contain the item ​
1376 //Should happen rarely ​
1377 short unsigned int next = bucketPtr->nextBucketForHash(hash); ​
1378 if(next) ​
1379 previousBucketNumber = next; ​
1380 else ​
1381 break; ​
1382 } ​
1383 } ​
1384 ​
1385 return 0; ​
1386 } 1358​ }
1387 1359​
1388 ///Deletes the item from the repository. 1360​ ///Deletes the item from the repository.
Context not available.
1850 1822​
1851 private: 1823​ private:
1852 1824​
1825​ uint createIndex(ushort bucketIndex, ushort indexInBucket) {
mwolffUnsubmitted
Not Done

put brace on newline

mwolff: put brace on newline
1826​ //Combine the index in the bucket, and the bucket number into one index
1827​ const uint index = (bucketIndex << 16) + indexInBucket;
1828​ verifyIndex(index);
1829​ return index;
1830​ }
1831​
1832​ /**
1833​ * Walks through all buckets clashing with @param hash
mwolffUnsubmitted
Not Done

some documentation please. and I find the choice of return types a bit odd.

the lambda should always return true/false, no? and that would then tell the loop to break or not. the walkBucketChain could then return void. The return value of the lambda could be given out via a captured variable?

mwolff: some documentation please. and I find the choice of return types a bit odd. the lambda should…
olivierjgAuthorUnsubmitted
Not Done

I do understand what you're saying by return types being odd, but having walkBucketChain return void or bool is not really a readability improvement in any situation.

We don't want void, since that means we /require/ a sentinel value to tell us if we broke early or found nothing, which won't necessarily be useful otherwise. Ie, in deleteItem, if found we set one value, else another one, so we'd either have to initialize it to zero and then set it again if found, or add another bool to tell us that it was found.

We could just have walkBucketChain return, but aside from just being noisier, it seems like premature pessimization. I think for this case where we are always working with pointers or zero-invalid bucket indexes, it makes some sense to have it as it is. Of course if you still find it undesirable, I'll change it.

olivierjg: I do understand what you're saying by return types being odd, but having walkBucketChain return…
1834​ *
1835​ * Will return the value returned by the lambda, returning early if truthy
1836​ */
1837​ template<typename Visitor>
1838​ auto walkBucketChain(unsigned int hash, const Visitor& visitor) -> decltype(visitor(0, nullptr)) {
1839​ unsigned short bucketIndex = m_firstBucketForHash[hash % bucketHashSize];
1840​
1841​ while (bucketIndex) {
1842​ const auto* bucketPtr = m_buckets[bucketIndex];
1843​ if (!bucketPtr) {
1844​ initializeBucket(bucketIndex);
1845​ bucketPtr = m_buckets[bucketIndex];
1846​ }
1847​
1848​ if (auto visitResult = visitor(bucketIndex, bucketPtr)) {
1849​ return visitResult;
1850​ }
1851​
1852​ bucketIndex = bucketPtr->nextBucketForHash(hash);
1853​ }
1854​
1855​ return {};
1856​ }
1857​
1853 ///Makes sure the order within m_freeSpaceBuckets is correct, after largestFreeSize has been changed for m_freeSpaceBuckets[index]. 1858​ ///Makes sure the order within m_freeSpaceBuckets is correct, after largestFreeSize has been changed for m_freeSpaceBuckets[index].
1854 ///If too few space is free within the given bucket, it is removed from m_freeSpaceBuckets. 1859​ ///If too few space is free within the given bucket, it is removed from m_freeSpaceBuckets.
1855 void updateFreeSpaceOrder(uint index) { 1860​ void updateFreeSpaceOrder(uint index) {
Context not available.