kdevplatform/serialization
itemrepository.h
Go to the documentation of this file.
60 //Only use it to verify values, it should not call any functions, since else the function will even be called in release mode
117 MaxFreeItemsForHide = 0, //When less than this count of free items in one buckets is reached, the bucket is removed from the global list of buckets with free items
118 MaxFreeSizeForHide = fixedItemSize ? fixedItemSize : 0, //Only when the largest free size is smaller then this, the bucket is taken from the free list
119 MinFreeItemsForReuse = 10,//When this count of free items in one bucket is reached, consider re-assigning them to new requests
120 MinFreeSizeForReuse = ItemRepositoryBucketSize / 20 //When the largest free item is bigger then this, the bucket is automatically added to the free list
123 NextBucketHashSize = ObjectMapSize, //Affects the average count of bucket-chains that need to be walked in ItemRepository::index. Must be a multiple of ObjectMapSize
124 DataSize = sizeof(char) + sizeof(unsigned int) * 3 + ItemRepositoryBucketSize + sizeof(short unsigned int) *
152 //The bigger we make the map, the lower the probability of a clash(and thus bad performance). However it increases memory usage.
205 file->write(reinterpret_cast<const char*>(m_objectMap), sizeof(short unsigned int) * ObjectMapSize);
206 file->write(reinterpret_cast<const char*>(m_nextBucketHash), sizeof(short unsigned int) * NextBucketHashSize);
213 KMessageBox::error(nullptr, i18n("Failed writing to %1, probably the disk is full", file->fileName()));
250 Q_ASSERT(static_cast<size_t>(file->pos()) == offset + DataSize + m_monsterBucketExtent * DataSize);
269 //Tries to find the index this item has in this bucket, or returns zero if the item isn't there yet.
289 //Tries to get the index within this bucket, or returns zero. Will put the item into the bucket if there is room.
290 //Created indices will never begin with 0xffff____, so you can use that index-range for own purposes.
300 const OptionalDUChainReferenceCountingEnabler<markForReferenceCounting> optionalRc(m_data, dataSize());
332 //The second condition is needed, else we can get problems with zero-length items and an overflow in insertedAt to zero
353 //we can not manage the resulting free chunk as a separate item, so we cannot use this position.
380 ifDebugLostSpace(Q_ASSERT(( uint )lostSpace() == ( uint )(freeSize(currentIndex) + AdditionalSpacePerItem));
390 //Create the free item at the beginning of currentIndex, so it can be merged with the free space in front
435 //Last thing we do, because createItem may recursively do even more transformation of the repository
449 ifDebugLostSpace(if (lostSpace()) qDebug() << "lost space:" << lostSpace(); Q_ASSERT(!lostSpace()); )
483 void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, uint& longestInBucketFollowerChain)
536 //Fix the follower-link by setting the follower of the previous item to the next one, or updating m_objectMap
554 const OptionalDUChainReferenceCountingEnabler<markForReferenceCounting> optionalRc(m_data, dataSize());
559 #if defined(__GNUC__) && !defined(__INTEL_COMPILER) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 800)
564 #if defined(__GNUC__) && !defined(__INTEL_COMPILER) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 800)
584 if (m_freeItemCount == 1 && freeSize(m_largestFreeItem) + m_available == ItemRepositoryBucketSize) {
789 //Counts together the space that is neither accessible through m_objectMap nor through the free items
801 found += reinterpret_cast<const Item*>(m_data + currentIndex)->itemSize() + AdditionalSpacePerItem;
839 //If the item-size is fixed, we don't need to do any management. Just keep a list of free items. Items of other size will never be requested.
986 int m_monsterBucketExtent = 0; //If this is a monster-bucket, this contains the count of follower-buckets that belong to this one
988 char* m_data = nullptr; //Structure of the data: <Position of next item with same hash modulo ItemRepositoryBucketSize>(2 byte), <Item>(item.size() byte)
989 char* m_mappedData = nullptr; //Read-only memory-mapped data. If this equals m_data, m_data must not be written
990 short unsigned int* m_objectMap = nullptr; //Points to the first object in m_data with (hash % ObjectMapSize) == index. Points to the item itself, so subtract 1 to get the pointer to the next item with same local hash.
991 short unsigned int m_largestFreeItem = 0; //Points to the largest item that is currently marked as free, or zero. That one points to the next largest one through followerIndex
1056 template <class Item, class ItemRequest, bool markForReferenceCounting = true, bool threadSafe = true,
1067 //Must also be a multiple of Bucket::NextBucketHashSize, for the same reason.(Currently those are same)
1072 BucketStartOffset = sizeof(uint) * 7 + sizeof(short unsigned int) * bucketHashSize //Position in the data where the bucket array starts
1099 m_currentBucket = 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes
1132 const ushort foundIndexInBucket = walkBucketChain(hash, [&](ushort bucketIdx, const MyBucket* bucketPtr) {
1194 if (m_buckets.size() >= 0xfffe) { //We have reserved the last bucket index 0xffff for special purposes
1213 "found item in unexpected bucket, ensure your ItemRequest::equals method is correct. Note: For custom AbstractType's e.g. ensure you have a proper equals() override");
1217 //If we could not allocate the item in an empty bucket, then we need to create a monster-bucket that
1292 } else if (!pickedBucketInChain && previousBucketNumber && previousBucketNumber != useBucket) {
1297 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, previousBucketNumber));
1300 //Find the position where the paths of useBucket and *bucketHashPosition intersect, and insert useBucket
1302 QPair<unsigned int, unsigned int> intersect = hashChainIntersection(*bucketHashPosition, useBucket,
1322 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.second));
1324 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.first));
1338 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.second));
1386 return walkBucketChain(request.hash(), [this, &request](ushort bucketIdx, const MyBucket* bucketPtr) {
1403 //Apart from removing the item itself, we may have to recreate the nextBucketForHash link, so we need the previous bucket
1427 // This bucket is linked in the m_firstBucketForHash array, find the next clashing bucket in the chain
1428 // There may be items in the chain that clash only with MyBucket::NextBucketHashSize, skipped here
1566 uint totalBucketFollowerSlots = -1; //Total count of used slots in the nextBucketForHash structure
1567 float averageNextBucketForHashSequenceLength = -1; //Average sequence length of a nextBucketForHash sequence(If not empty)
1573 QStringLiteral("loaded buckets: %1 current bucket: %2 used memory: %3 loaded monster buckets: %4").arg(
1575 ret += QStringLiteral("\nbucket hash clashed items: %1 total items: %2").arg(hashClashedItems).arg(
1577 ret += QStringLiteral("\nused space for buckets: %1 free space in buckets: %2 lost space: %3").arg(
1579 ret += QStringLiteral("\nfree unreachable space: %1 empty buckets: %2").arg(freeUnreachableSpace).arg(
1583 "\naverage in-bucket hash size: %1 average in-bucket used hash slot count: %2 average in-bucket slot chain length: %3 longest in-bucket follower chain: %4")
1584 .arg(averageInBucketHashSize).arg(averageInBucketUsedSlotCount).arg(averageInBucketSlotChainLength).
1588 "\ntotal count of used next-bucket-for-hash slots: %1 average next-bucket-for-hash sequence length: %2 longest next-bucket chain: %3")
1589 .arg(totalBucketFollowerSlots).arg(averageNextBucketForHashSequenceLength).arg(longestNextBucketChain);
1710 ret.averageInBucketSlotChainLength = float( totalInBucketChainLengths ) / totalInBucketUsedSlotCount;
1787 m_file->write(reinterpret_cast<const char*>(m_firstBucketForHash), sizeof(short unsigned int) * bucketHashSize);
1793 m_dynamicFile->write(reinterpret_cast<const char*>(m_freeSpaceBuckets.data()), sizeof(uint) * freeSpaceBucketsSize);
1841 auto walkBucketChain(unsigned int hash, const Visitor& visitor) const->decltype(visitor(0, nullptr))
1884 if (prev >= 0 && (bucketForIndex(freeSpaceBuckets[prev])->largestFreeSize() > largestFreeSize ||
1888 //This item should be behind the successor, either because it has a lower largestFreeSize, or because the index is lower
1897 //This item should be behind the successor, either because it has a higher largestFreeSize, or because the index is higher
2015 m_currentBucket = 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes
2017 m_file->write(reinterpret_cast<const char*>(m_firstBucketForHash), sizeof(short unsigned int) * bucketHashSize);
2030 bool res = m_file->open(QFile::ReadOnly); //Re-open in read-only mode, so we create a read-only m_fileMap
2060 m_file->read(reinterpret_cast<char*>(m_firstBucketForHash), sizeof(short unsigned int) * bucketHashSize);
2067 m_dynamicFile->read(reinterpret_cast<char*>(m_freeSpaceBuckets.data()), sizeof(uint) * freeSpaceBucketsSize);
2162 a += bucket->monsterBucketExtent(); //Skip buckets that are attached as tail to monster-buckets
2233 m_buckets[bucketNumber]->store(m_file, BucketStartOffset + (bucketNumber - 1) * MyBucket::DataSize);
2254 QPair<unsigned int, unsigned int> hashChainIntersection(uint mainHead, uint intersectorHead, uint hash) const
2278 //We only do it when a specific threshold of empty items is reached, because that way items can stay "somewhat" semantically ordered.
2282 if (bucketForIndex(m_freeSpaceBuckets[insertPos])->largestFreeSize() > bucketPtr->largestFreeSize())
2322 //List of buckets that have free space available that can be assigned. Sorted by size: Smallest space first. Second order sorting: Bucket index
Definition: itemrepository.h:129
virtual bool seek(qint64 pos)
uint freeSpaceInBuckets
Definition: itemrepository.h:1552
virtual void close()
bool resize(qint64 sz)
unsigned short nextBucketForHash(uint hash) const
Definition: itemrepository.h:696
virtual bool open(QFlags< QIODevice::OpenModeFlag > mode)
void insert(int i, const T &value)
void setMutex(QMutex *mutex)
With this, you can replace the internal mutex with another one.
Definition: itemrepository.h:1815
int monsterBucketExtent() const
Returns the count of following buckets that were merged onto this buckets data array.
Definition: itemrepository.h:784
bool flush()
uint freeUnreachableSpace
Definition: itemrepository.h:1554
int indexOf(const T &value, int from) const
Definition: itemrepository.h:1002
MyDynamicItem dynamicItemFromIndex(unsigned int index)
This returns an editable version of the item.
Definition: itemrepository.h:1479
float averageInBucketSlotChainLength
Definition: itemrepository.h:1562
uint currentBucket
Definition: itemrepository.h:1548
void deleteItem(unsigned short index, unsigned int hash, Repository &repository)
Definition: itemrepository.h:523
void initializeFromMap(char *current)
Definition: itemrepository.h:170
bool canAllocateItem(unsigned int size) const
Definition: itemrepository.h:738
T * data()
const Item * itemFromIndex(unsigned int index) const
Definition: itemrepository.h:1524
void remove(int i)
Definition: itemrepository.h:124
QString fileName() const
uint longestInBucketChain
Definition: itemrepository.h:1563
uint staticItemRepositoryVersion()
Returns a version-number that is used to reset the item-repository after incompatible layout changes.
Definition: abstractitemrepository.cpp:24
Definition: itemrepository.h:128
ItemRepository(const QString &repositoryName, ItemRepositoryRegistry *registry=&globalItemRepositoryRegistry(), uint repositoryVersion=1, AbstractRepositoryManager *manager=nullptr)
Definition: itemrepository.h:1079
DynamicItem(Item *i, const void *start, unsigned size)
Definition: itemrepository.h:1034
void clear()
const Item * itemFromIndex(unsigned short index) const
Definition: itemrepository.h:614
uint longestNextBucketChain
Definition: itemrepository.h:1565
void countFollowerIndexLengths(uint &usedSlots, uint &lengths, uint &slotCount, uint &longestInBucketFollowerChain)
Definition: itemrepository.h:483
QString printStatistics() const override
Definition: itemrepository.h:1597
bool isOpen() const
void visitAllItems(Visitor &visitor, bool onlyInMemory=false) const
This can be used to safely iterate through all items in the repository.
Definition: itemrepository.h:1733
bool visitAllItems(Visitor &visitor) const
Definition: itemrepository.h:646
bool contains(const T &value) const
ItemRepositoryRegistry & globalItemRepositoryRegistry()
The global item-repository registry that is used by default.
Definition: itemrepositoryregistry.cpp:206
virtual qint64 pos() const
bool hasClashingItem(uint hash, uint modulo)
Definition: itemrepository.h:458
short unsigned int largestFreeSize() const
Definition: itemrepository.h:726
void resize(int size)
bool itemReachable(const Item *item, uint hash) const
Definition: itemrepository.h:508
DynamicItem< Item, markForReferenceCounting > MyDynamicItem
Definition: itemrepository.h:1472
bool noNextBuckets() const
Returns true if this bucket has no nextBucketForHash links.
Definition: itemrepository.h:626
void unRegisterRepository(AbstractItemRepository *repository)
Remove a repository.
Definition: itemrepositoryregistry.cpp:265
Internal helper class that wraps around a repository object and manages its lifetime.
Definition: abstractitemrepository.h:51
Item * dynamicItemFromIndexSimple(unsigned int index)
This returns an editable version of the item.
Definition: itemrepository.h:1505
uint loadedMonsterBuckets
Definition: itemrepository.h:1550
virtual qint64 size() const
void initialize(int monsterBucketExtent)
Definition: itemrepository.h:143
qint64 read(char *data, qint64 maxSize)
uint averageInBucketUsedSlotCount
Definition: itemrepository.h:1561
uint hashClashedItems
Definition: itemrepository.h:1555
unsigned short index(const ItemRequest &request, unsigned int itemSize)
Definition: itemrepository.h:291
void setNextBucketForHash(unsigned int hash, unsigned short bucket)
Definition: itemrepository.h:702
uchar * map(qint64 offset, qint64 size, MemoryMapFlags flags)
uint loadedBuckets
Definition: itemrepository.h:1547
This object needs to be kept alive as long as you change the contents of an item stored in the reposi...
Definition: itemrepository.h:1031
void setUnloadingEnabled(bool enabled)
Unloading of buckets is enabled by default.
Definition: itemrepository.h:1113
Definition: itemrepository.h:1058
void registerRepository(AbstractItemRepository *repository, AbstractRepositoryManager *manager)
Add a new repository.
Definition: itemrepositoryregistry.cpp:211
QString repositoryName() const override
Definition: itemrepository.h:1820
The interface class for an item-repository object.
Definition: abstractitemrepository.h:33
Definition: abstractitemrepository.cpp:23
void store() override
Synchronizes the state on disk to the one in memory, and does some memory-management.
Definition: itemrepository.h:1746
int size() const
uint totalBucketFollowerSlots
Definition: itemrepository.h:1566
void deleteItem(unsigned int index)
Deletes the item from the repository.
Definition: itemrepository.h:1393
uint averageInBucketHashSize
Definition: itemrepository.h:1560
QString arg(qlonglong a, int fieldWidth, int base, const QChar &fillChar) const
unsigned int index(const ItemRequest &request)
Returns the index for the given item.
Definition: itemrepository.h:1121
~ItemRepository() override
Definition: itemrepository.h:1104
Buckets are the memory-units that are used to store the data in an ItemRepository.
Definition: itemrepository.h:109
unsigned int findIndex(const ItemRequest &request)
Returns zero if the item is not in the repository yet.
Definition: itemrepository.h:1382
int finalCleanup(Repository &repository)
Returns whether something was changed.
Definition: itemrepository.h:667
unsigned short findIndex(const ItemRequest &request) const
Definition: itemrepository.h:270
char * data()
uint usedSpaceForBuckets
Definition: itemrepository.h:1551
Manages a set of item-repositories and allows loading/storing them all at once from/to disk.
Definition: itemrepositoryregistry.h:41
qint64 write(const char *data, qint64 maxSize)
short unsigned int totalFreeItemsSize() const
Definition: itemrepository.h:714
float averageNextBucketForHashSequenceLength
Definition: itemrepository.h:1567
QMutex * mutex() const
This mutex is used for the thread-safe locking when threadSafe is true.
Definition: itemrepository.h:1809
uint emptyBuckets
Definition: itemrepository.h:1557
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Tue Apr 13 2021 23:30:33 by doxygen 1.8.16 written by Dimitri van Heesch, © 1997-2006
Documentation copyright © 1996-2021 The KDE developers.
Generated on Tue Apr 13 2021 23:30:33 by doxygen 1.8.16 written by Dimitri van Heesch, © 1997-2006
KDE's Doxygen guidelines are available online.