2 Copyright 2008 David Nolden <david.nolden.kdevelop@art-master.de>
4 This library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Library General Public
6 License version 2 as published by the Free Software Foundation.
8 This library is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 Library General Public License for more details.
13 You should have received a copy of the GNU Library General Public License
14 along with this library; see the file COPYING.LIB. If not, write to
15 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
16 Boston, MA 02110-1301, USA.
19 #ifndef ITEMREPOSITORY_H
20 #define ITEMREPOSITORY_H
22 #include <QtCore/QString>
23 #include <QtCore/QVector>
24 #include <QtCore/QByteArray>
25 #include <QtCore/QMutex>
26 #include <QtCore/QList>
27 #include <QtCore/QDir>
28 #include <QtCore/QFile>
29 #include <QtCore/QAtomicInt>
30 #include <klockfile.h>
32 #include "../../languageexport.h"
34 //#define DEBUG_MONSTERBUCKETS
36 // #define DEBUG_ITEMREPOSITORY_LOADING
37 // #define ifDebugInfiniteRecursion(x) x
38 #define ifDebugInfiniteRecursion(x)
40 // #define ifDebugLostSpace(x) x
41 #define ifDebugLostSpace(x)
42 // #define DEBUG_INCORRECT_DELETE
44 //Makes sure that all items stay reachable through the basic hash
45 // #define DEBUG_ITEM_REACHABILITY
47 #ifdef DEBUG_ITEM_REACHABILITY
48 #define ENSURE_REACHABLE(bucket) Q_ASSERT(allItemsReachable(bucket));
50 #define ENSURE_REACHABLE(bucket)
53 ///When this is uncommented, a 64-bit test-value is written behind the area an item is allowed to write into before
54 ///createItem(..) is called, and an assertion triggers when it was changed during createItem(), which means createItem wrote too long.
55 ///The problem: This temporarily overwrites valid data in the following item, so it will cause serious problems if that data is accessed
56 ///during the call to createItem().
57 //#define DEBUG_WRITING_EXTENTS
62 * This file implements a generic bucket-based indexing repository, that can be used for example to index strings.
64 * All you need to do is define your item type that you want to store into the repository, and create a request item
65 * similar to ExampleRequestItem that compares and fills the defined item type.
67 * For example the string repository uses "unsigned short" as item-type, uses that actual value to store the length of the string,
68 * and uses the space behind to store the actual string content.
71 * @see stringrepository.h
72 * @see indexedstring.h
76 ///Returns a version-number that is used to reset the item-repository after incompatible layout changes
77 KDEVPLATFORMLANGUAGE_EXPORT uint
staticItemRepositoryVersion();
79 class KDEVPLATFORMLANGUAGE_EXPORT AbstractItemRepository
{
81 virtual ~AbstractItemRepository();
82 ///@param path is supposed to be a shared directory-name that the item-repository is to be loaded from
83 ///@param clear will be true if the old repository should be discarded and a new one started
84 ///If this returns false, that indicates that opening failed.
85 virtual bool open(const QString
& path
) = 0;
86 virtual void close(bool doStore
= false) = 0;
87 virtual void store() = 0;
91 * Manages a set of item-repositores and allows loading/storing them all at once from/to disk.
92 * Does not automatically store contained repositories on destruction.
93 * For the global standard registry, the storing is triggered from within duchain, so you don't need to care about it.
95 class KDEVPLATFORMLANGUAGE_EXPORT ItemRepositoryRegistry
{
97 ItemRepositoryRegistry(QString openPath
= QString(), KLockFile::Ptr lock
= KLockFile::Ptr());
98 ~ItemRepositoryRegistry();
100 ///Path is supposed to be a shared directory-name that the item-repositories are to be loaded from
101 ///@param clear Whether a fresh start should be done, and all repositories cleared
102 ///If this returns false, loading has failed, and all repositories have been discarded.
103 ///@note Currently the given path must reference a hidden directory, just to make sure we're
104 /// not accidentally deleting something important
105 bool open(const QString
& path
, bool clear
= false, KLockFile::Ptr lock
= KLockFile::Ptr());
106 ///@warning The current state is not stored to disk.
108 ///The registered repository will automatically be opened with the current path, if one is set.
109 void registerRepository(AbstractItemRepository
* repository
);
110 ///The registered repository will automatically be closed if it was open.
111 void unRegisterRepository(AbstractItemRepository
* repository
);
112 ///Returns the path currently set
113 QString
path() const;
114 ///Should be called on a regular basis: Stores all repositories to disk, and eventually unloads unneeded data to save memory
117 ///Call this to lock the directory for writing. When KDevelop crashes while the directory is locked for writing,
118 ///it will know that the directory content is inconsistent, and discard it while next startup.
119 void lockForWriting();
120 ///Call this when you're ready writing, after lockForWriting has been called
121 void unlockForWriting();
123 ///Returns a custom counter, identified by the given identity, that is persistently stored in the repository directory.
124 ///If the counter didn't exist before, it will be initialized with initialValue
125 QAtomicInt
& getCustomCounter(const QString
& identity
, int initialValue
);
127 void deleteDataDirectory();
129 QList
<AbstractItemRepository
*> m_repositories
;
130 QMap
<QString
, QAtomicInt
*> m_customCounters
;
131 KLockFile::Ptr m_lock
;
132 mutable QMutex m_mutex
;
135 ///The global item-repository registry that is used by default
136 KDEVPLATFORMLANGUAGE_EXPORT ItemRepositoryRegistry
& globalItemRepositoryRegistry();
138 ///This is the actual data that is stored in the repository. All the data that is not directly in the class-body,
139 ///like the text of a string, can be stored behind the item in the same memory region. The only important thing is
140 ///that the Request item(@see ExampleItemRequest) correctly advertises the space needed by this item.
142 //Every item has to implement this function, and return a valid hash.
143 //Must be exactly the same hash value as ExampleItemRequest::hash() has returned while creating the item.
144 unsigned int hash() const {
148 //Every item has to implement this function, and return the complete size this item takes in memory.
149 //Must be exactly the same value as ExampleItemRequest::itemSize() has returned while creating the item.
150 unsigned short int itemSize() const {
156 * A request represents the information that is searched in the repository.
157 * It must be able to compare itself to items stored in the repository, and it must be able to
158 * create items in the. The item-types can also be basic data-types, with additional information stored behind.
162 ItemRepositoryBucketSize
= 1<<16
165 class ExampleRequestItem
{
168 AverageSize
= 10 //This should be the approximate average size of an Item
171 typedef unsigned int HashType
;
173 //Should return the hash-value associated with this request(For example the hash of a string)
174 HashType
hash() const {
178 //Should return the size of an item created with createItem
179 size_t itemSize() const {
182 //Should create an item where the information of the requested item is permanently stored. The pointer
183 //@param item equals an allocated range with the size of itemSize().
184 ///@warning Never call non-constant functions on the repository from within this function!
185 void createItem(ExampleItem
* /*item*/) const {
188 //Should return whether the here requested item equals the given item
189 bool equals(const ExampleItem
* /*item*/) const {
194 template<class Item
, class ItemRequest
, class DynamicData
>
198 AdditionalSpacePerItem
= DynamicData::Size
+ 2
201 ObjectMapSize
= (ItemRepositoryBucketSize
/ ItemRequest::AverageSize
) + 1,
202 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
203 MaxFreeSizeForHide
= 0, //Only when the largest free size is smaller then this, the bucket is taken from the free list
204 MinFreeItemsForReuse
= 10,//When this count of free items in one bucket is reached, consider re-assigning them to new requests
205 MinFreeSizeForReuse
= ItemRepositoryBucketSize
/20 //When the largest free item is bigger then this, the bucket is automatically added to the free list
208 NextBucketHashSize
= ObjectMapSize
, //Affects the average count of bucket-chains that need to be walked in ItemRepository::index. Must be a multiple of ObjectMapSize
209 DataSize
= sizeof(unsigned int) * 3 + ItemRepositoryBucketSize
+ sizeof(short unsigned int) * (ObjectMapSize
+ NextBucketHashSize
+ 1)
212 CheckStart
= 0xff00ff1,
215 Bucket() : m_monsterBucketExtent(0), m_available(0), m_data(0), m_objectMap(0), m_objectMapSize(0), m_largestFreeItem(0), m_freeItemCount(0), m_nextBucketHash(0) {
219 delete[] m_nextBucketHash
;
220 delete[] m_objectMap
;
223 void initialize(uint monsterBucketExtent
) {
225 m_monsterBucketExtent
= monsterBucketExtent
;
226 m_available
= ItemRepositoryBucketSize
;
227 m_data
= new char[ItemRepositoryBucketSize
+ monsterBucketExtent
* DataSize
];
228 //The bigger we make the map, the lower the probability of a clash(and thus bad performance). However it increases memory usage.
229 m_objectMapSize
= ObjectMapSize
;
230 m_objectMap
= new short unsigned int[m_objectMapSize
];
231 memset(m_objectMap
, 0, m_objectMapSize
* sizeof(short unsigned int));
232 m_nextBucketHash
= new short unsigned int[NextBucketHashSize
];
233 memset(m_nextBucketHash
, 0, NextBucketHashSize
* sizeof(short unsigned int));
238 void initialize(QFile
* file
, size_t offset
) {
240 if(file
->size() > offset
) {
243 file
->read((char*)&m_monsterBucketExtent
, sizeof(unsigned int));
244 Q_ASSERT(file
->size() >= offset
+ (1+m_monsterBucketExtent
)*DataSize
);
246 initialize(m_monsterBucketExtent
);
248 file
->read((char*)&m_available
, sizeof(unsigned int));
249 file
->read((char*)m_objectMap
, sizeof(short unsigned int) * m_objectMapSize
);
250 file
->read((char*)m_nextBucketHash
, sizeof(short unsigned int) * NextBucketHashSize
);
251 file
->read((char*)&m_largestFreeItem
, sizeof(short unsigned int));
252 file
->read((char*)&m_freeItemCount
, sizeof(unsigned int));
253 file
->read(m_data
, ItemRepositoryBucketSize
+ m_monsterBucketExtent
* DataSize
);
254 Q_ASSERT(file
->pos() == offset
+ (1+m_monsterBucketExtent
)*DataSize
);
258 initialize(m_monsterBucketExtent
);
263 void store(QFile
* file
, size_t offset
) {
267 if(file
->size() < offset
+ (1+m_monsterBucketExtent
)*DataSize
)
268 file
->resize(offset
+ (1+m_monsterBucketExtent
)*DataSize
);
272 file
->write((char*)&m_monsterBucketExtent
, sizeof(unsigned int));
273 file
->write((char*)&m_available
, sizeof(unsigned int));
274 file
->write((char*)m_objectMap
, sizeof(short unsigned int) * m_objectMapSize
);
275 file
->write((char*)m_nextBucketHash
, sizeof(short unsigned int) * NextBucketHashSize
);
276 file
->write((char*)&m_largestFreeItem
, sizeof(short unsigned int));
277 file
->write((char*)&m_freeItemCount
, sizeof(unsigned int));
278 file
->write(m_data
, ItemRepositoryBucketSize
+ m_monsterBucketExtent
* DataSize
);
280 Q_ASSERT(file
->pos() == offset
+ (1+m_monsterBucketExtent
)*DataSize
);
282 #ifdef DEBUG_ITEMREPOSITORY_LOADING
287 uint available
, freeItemCount
, monsterBucketExtent
;
288 short unsigned int largestFree
;
290 short unsigned int* m
= new short unsigned int[m_objectMapSize
];
291 short unsigned int* h
= new short unsigned int[NextBucketHashSize
];
294 file
->read((char*)&monsterBucketExtent
, sizeof(unsigned int));
295 char* d
= new char[ItemRepositoryBucketSize
+ monsterBucketExtent
* DataSize
];
297 file
->read((char*)&available
, sizeof(unsigned int));
298 file
->read((char*)m
, sizeof(short unsigned int) * m_objectMapSize
);
299 file
->read((char*)h
, sizeof(short unsigned int) * NextBucketHashSize
);
300 file
->read((char*)&largestFree
, sizeof(short unsigned int));
301 file
->read((char*)&freeItemCount
, sizeof(unsigned int));
302 file
->read(d
, ItemRepositoryBucketSize
);
304 Q_ASSERT(monsterBucketExtent
== m_monsterBucketExtent
);
305 Q_ASSERT(available
== m_available
);
306 Q_ASSERT(memcmp(d
, m_data
, ItemRepositoryBucketSize
+ monsterBucketExtent
* DataSize
) == 0);
307 Q_ASSERT(memcmp(m
, m_objectMap
, sizeof(short unsigned int) * m_objectMapSize
) == 0);
308 Q_ASSERT(memcmp(h
, m_nextBucketHash
, sizeof(short unsigned int) * NextBucketHashSize
) == 0);
309 Q_ASSERT(m_largestFreeItem
== largestFree
);
310 Q_ASSERT(m_freeItemCount
== freeItemCount
);
312 Q_ASSERT(file
->pos() == offset
+ DataSize
+ m_monsterBucketExtent
* DataSize
);
321 //Tries to find the index this item has in this bucket, or returns zero if the item isn't there yet.
322 unsigned short findIndex(const ItemRequest
& request
, const DynamicData
* dynamic
) const {
325 unsigned short localHash
= request
.hash() % m_objectMapSize
;
326 unsigned short index
= m_objectMap
[localHash
];
328 unsigned short follower
= 0;
329 //Walk the chain of items with the same local hash
330 while(index
&& (follower
= followerIndex(index
)) && !(request
.equals(itemFromIndex(index
))))
333 if(index
&& request
.equals(itemFromIndex(index
))) {
335 itemFromIndex(index
, dynamic
);
336 return index
; //We have found the item
342 //Tries to get the index within this bucket, or returns zero. Will put the item into the bucket if there is room.
343 //Created indices will never begin with 0xffff____, so you can use that index-range for own purposes.
344 unsigned short index(const ItemRequest
& request
, const DynamicData
* dynamic
, unsigned int itemSize
) {
347 unsigned short localHash
= request
.hash() % m_objectMapSize
;
348 unsigned short index
= m_objectMap
[localHash
];
349 unsigned short insertedAt
= 0;
351 unsigned short follower
= 0;
352 //Walk the chain of items with the same local hash
353 while(index
&& (follower
= followerIndex(index
)) && !(request
.equals(itemFromIndex(index
))))
356 if(index
&& request
.equals(itemFromIndex(index
)))
357 return index
; //We have found the item
359 ifDebugLostSpace( Q_ASSERT(!lostSpace()); )
363 unsigned int totalSize
= itemSize
+ AdditionalSpacePerItem
;
365 if(m_monsterBucketExtent
) {
366 ///This is a monster-bucket. Other rules are applied here. Only one item can be allocated, and that must be bigger than the bucket data
367 Q_ASSERT(totalSize
> ItemRepositoryBucketSize
);
368 Q_ASSERT(m_available
);
371 insertedAt
= AdditionalSpacePerItem
;
372 DynamicData::initialize(m_data
);
373 setFollowerIndex(insertedAt
, 0);
374 Q_ASSERT(m_objectMap
[localHash
] == 0);
375 m_objectMap
[localHash
] = insertedAt
;
377 //Last thing we do, because createItem may recursively do even more transformation of the repository
378 request
.createItem((Item
*)(m_data
+ insertedAt
));
381 itemFromIndex(insertedAt
, dynamic
);
386 //The second condition is needed, else we can get problems with zero-length items and an overflow in insertedAt to zero
387 if(totalSize
> m_available
|| (!itemSize
&& totalSize
== m_available
)) {
388 //Try finding the smallest freed item that can hold the data
389 unsigned short currentIndex
= m_largestFreeItem
;
390 unsigned short previousIndex
= 0;
392 unsigned short freeChunkSize
= 0;
394 while(currentIndex
&& freeSize(currentIndex
) >= (totalSize
-AdditionalSpacePerItem
)) {
395 unsigned short follower
= followerIndex(currentIndex
);
396 if(follower
&& freeSize(follower
) >= (totalSize
-AdditionalSpacePerItem
)) {
397 //The item also fits into the smaller follower, so use that one
398 previousIndex
= currentIndex
;
399 currentIndex
= follower
;
401 //The item fits into currentIndex, but not into the follower. So use currentIndex
402 freeChunkSize
= freeSize(currentIndex
) - (totalSize
- AdditionalSpacePerItem
);
404 //We need 2 bytes to store the free size
405 if(freeChunkSize
!= 0 && freeChunkSize
< AdditionalSpacePerItem
+2) {
406 //we can not manage the resulting free chunk as a separate item, so we cannot use this position.
407 //Just pick the biggest free item, because there we can be sure that
408 //either we can manage the split, or we cannot do anything at all in this bucket.
410 freeChunkSize
= freeSize(m_largestFreeItem
) - (totalSize
- AdditionalSpacePerItem
);
412 if(freeChunkSize
== 0 || freeChunkSize
>= AdditionalSpacePerItem
+2) {
414 currentIndex
= m_largestFreeItem
;
423 if(!currentIndex
|| freeSize(currentIndex
) < (totalSize
-AdditionalSpacePerItem
))
427 setFollowerIndex(previousIndex
, followerIndex(currentIndex
));
429 m_largestFreeItem
= followerIndex(currentIndex
);
431 --m_freeItemCount
; //Took one free item out of the chain
433 ifDebugLostSpace( Q_ASSERT((uint
)lostSpace() == (uint
)(freeSize(currentIndex
) + AdditionalSpacePerItem
)); )
436 Q_ASSERT(freeChunkSize
>= AdditionalSpacePerItem
+2);
437 unsigned short freeItemSize
= freeChunkSize
- AdditionalSpacePerItem
;
439 unsigned short freeItemPosition
;
440 //Insert the resulting free chunk into the list of free items, so we don't lose it
441 if(isBehindFreeSpace(currentIndex
)) {
442 //Create the free item at the beginning of currentIndex, so it can be merged with the free space in front
443 freeItemPosition
= currentIndex
;
444 currentIndex
+= freeItemSize
+ AdditionalSpacePerItem
;
446 //Create the free item behind currentIndex
447 freeItemPosition
= currentIndex
+ totalSize
;
449 setFreeSize(freeItemPosition
, freeItemSize
);
450 insertFreeItem(freeItemPosition
);
453 insertedAt
= currentIndex
;
454 Q_ASSERT((bool)m_freeItemCount
== (bool)m_largestFreeItem
);
456 //We have to insert the item
457 insertedAt
= ItemRepositoryBucketSize
- m_available
;
459 insertedAt
+= AdditionalSpacePerItem
; //Room for the prepended follower-index
461 m_available
-= totalSize
;
464 ifDebugLostSpace( Q_ASSERT(lostSpace() == totalSize
); )
466 DynamicData::initialize(m_data
+ insertedAt
- AdditionalSpacePerItem
);
468 Q_ASSERT(!index
|| !followerIndex(index
));
470 Q_ASSERT(!m_objectMap
[localHash
] || index
);
473 setFollowerIndex(index
, insertedAt
);
474 setFollowerIndex(insertedAt
, 0);
476 if(m_objectMap
[localHash
] == 0)
477 m_objectMap
[localHash
] = insertedAt
;
480 #ifdef DEBUG_CREATEITEM_EXTENTS
481 char* borderBehind
= m_data
+ insertedAt
+ (totalSize
-AdditionalSpacePerItem
);
483 quint64 oldValueBehind
= 0;
484 if(m_available
>= 8) {
485 oldValueBehind
= *(quint64
*)borderBehind
;
486 *((quint64
*)borderBehind
) = 0xfafafafafafafafaLLU
;
490 //Last thing we do, because createItem may recursively do even more transformation of the repository
491 request
.createItem((Item
*)(m_data
+ insertedAt
));
493 #ifdef DEBUG_CREATEITEM_EXTENTS
494 if(m_available
>= 8) {
495 //If this assertion triggers, then the item writes a bigger range than it advertised in
496 Q_ASSERT(*((quint64
*)borderBehind
) == 0xfafafafafafafafaLLU
);
497 *((quint64
*)borderBehind
) = oldValueBehind
;
501 Q_ASSERT(itemFromIndex(insertedAt
)->hash() == request
.hash());
502 Q_ASSERT(itemFromIndex(insertedAt
)->itemSize() == itemSize
);
505 itemFromIndex(insertedAt
, dynamic
);
507 ifDebugLostSpace( if(lostSpace()) kDebug() << "lost space:" << lostSpace(); Q_ASSERT(!lostSpace()); )
511 ///@param modulo Returns whether this bucket contains an item with (hash % modulo) == (item.hash % modulo)
512 /// The default-parameter is the size of the next-bucket hash that is used by setNextBucketForHash and nextBucketForHash
513 /// @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.
514 /// This this allows efficiently computing the clashes using the local object map hash.
516 bool hasClashingItem(uint hash
, uint modulo
) {
518 Q_ASSERT(modulo
% ObjectMapSize
== 0);
522 uint hashMod
= hash
% modulo
;
523 unsigned short localHash
= hash
% m_objectMapSize
;
524 unsigned short currentIndex
= m_objectMap
[localHash
];
526 if(currentIndex
== 0)
529 while(currentIndex
) {
530 uint currentHash
= itemFromIndex(currentIndex
)->hash();
532 Q_ASSERT(currentHash
% m_objectMapSize
== localHash
);
534 if(currentHash
% modulo
== hashMod
)
536 currentIndex
= followerIndex(currentIndex
);
541 struct ClashVisitor
{
542 ClashVisitor(int _hash
, int _modulo
) : result(0), hash(_hash
), modulo(_modulo
) {
544 bool operator()(const Item
* item
) {
545 if((item
->hash() % modulo
) == (hash
% modulo
))
554 //A version of hasClashingItem that visits all items naively without using any assumptions.
555 //This was used to debug hasClashingItem, but should not be used otherwise.
556 bool hasClashingItemReal(uint hash
, uint modulo
) {
560 ClashVisitor
visitor(hash
, modulo
);
561 visitAllItems
<ClashVisitor
>(visitor
);
562 return (bool)visitor
.result
;
565 //Returns whether the given item is reachabe within this bucket, through its hash.
566 bool itemReachable(const Item
* item
, uint hash
) const {
568 unsigned short localHash
= hash
% m_objectMapSize
;
569 unsigned short currentIndex
= m_objectMap
[localHash
];
571 while(currentIndex
) {
572 if(itemFromIndex(currentIndex
) == item
)
575 currentIndex
= followerIndex(currentIndex
);
580 template<class Visitor
>
581 bool visitItemsWithHash(Visitor
& visitor
, uint hash
, unsigned short bucketIndex
) const {
584 unsigned short localHash
= hash
% m_objectMapSize
;
585 unsigned short currentIndex
= m_objectMap
[localHash
];
587 while(currentIndex
) {
588 if(!visitor(itemFromIndex(currentIndex
), (bucketIndex
<< 16) + currentIndex
))
591 currentIndex
= followerIndex(currentIndex
);
597 void deleteItem(unsigned short index
, unsigned int hash
) {
598 ifDebugLostSpace( Q_ASSERT(!lostSpace()); )
603 unsigned short size
= itemFromIndex(index
)->itemSize();
604 //Step 1: Remove the item from the data-structures that allow finding it: m_objectMap
605 unsigned short localHash
= hash
% m_objectMapSize
;
606 unsigned short currentIndex
= m_objectMap
[localHash
];
607 unsigned short previousIndex
= 0;
609 //Fix the follower-link by setting the follower of the previous item to the next one, or updating m_objectMap
610 while(currentIndex
!= index
) {
611 previousIndex
= currentIndex
;
612 currentIndex
= followerIndex(currentIndex
);
613 //If this assertion triggers, the deleted item was not registered under the given hash
614 Q_ASSERT(currentIndex
);
616 Q_ASSERT(currentIndex
== index
);
619 //The item was directly in the object map
620 m_objectMap
[localHash
] = followerIndex(index
);
622 setFollowerIndex(previousIndex
, followerIndex(index
));
624 memset(const_cast<Item
*>(itemFromIndex(index
)), 0, size
); //For debugging, so we notice the data is wrong
626 if(m_monsterBucketExtent
) {
627 ///This is a monster-bucket. Make it completely empty again.
628 Q_ASSERT(!m_available
);
629 m_available
= ItemRepositoryBucketSize
;
631 //Items are always inserted into monster-buckets at a fixed position
632 Q_ASSERT(currentIndex
== AdditionalSpacePerItem
);
633 Q_ASSERT(m_objectMap
[localHash
] == 0);
635 ///Put the space into the free-set
636 setFreeSize(index
, size
);
638 //Try merging the created free item to other free items around, else add it into the free list
639 insertFreeItem(index
);
641 if(m_freeItemCount
== 1 && freeSize(m_largestFreeItem
) + m_available
== ItemRepositoryBucketSize
) {
642 //Everything has been deleted, there is only free space left. Make the bucket empty again,
643 //so it can later also be used as a monster-bucket.
644 m_available
= ItemRepositoryBucketSize
;
646 m_largestFreeItem
= 0;
650 Q_ASSERT((bool)m_freeItemCount
== (bool)m_largestFreeItem
);
651 ifDebugLostSpace( Q_ASSERT(!lostSpace()); )
652 #ifdef DEBUG_INCORRECT_DELETE
653 //Make sure the item cannot be found any more
655 unsigned short localHash
= hash
% m_objectMapSize
;
656 unsigned short currentIndex
= m_objectMap
[localHash
];
658 while(currentIndex
&& currentIndex
!= index
) {
659 previousIndex
= currentIndex
;
660 currentIndex
= followerIndex(currentIndex
);
662 Q_ASSERT(!currentIndex
); //The item must not be found
667 inline const Item
* itemFromIndex(unsigned short index
) const {
669 return (Item
*)(m_data
+index
);
672 ///When dynamic is nonzero, and apply(..) returns false, the item is freed, and the returned item is invalid.
673 inline const Item
* itemFromIndex(unsigned short index
, const DynamicData
* dynamic
) const {
675 Item
* ret((Item
*)(m_data
+index
));
677 dynamic
->apply(m_data
+ index
- AdditionalSpacePerItem
);
681 bool isEmpty() const {
682 return m_available
== ItemRepositoryBucketSize
;
685 ///Returns true if this bucket has no nextBucketForHash links
686 bool noNextBuckets() const {
687 for(int a
= 0; a
< NextBucketHashSize
; ++a
)
688 if(m_nextBucketHash
[a
])
693 uint
available() const {
697 uint
usedMemory() const {
698 return ItemRepositoryBucketSize
- m_available
;
701 template<class Visitor
>
702 bool visitAllItems(Visitor
& visitor
) const {
704 for(uint a
= 0; a
< m_objectMapSize
; ++a
) {
705 uint currentIndex
= m_objectMap
[a
];
706 while(currentIndex
) {
707 if(!visitor((const Item
*)(m_data
+currentIndex
)))
710 currentIndex
= followerIndex(currentIndex
);
716 unsigned short nextBucketForHash(uint hash
) const {
718 return m_nextBucketHash
[hash
% NextBucketHashSize
];
721 void setNextBucketForHash(unsigned int hash
, unsigned short bucket
) {
724 m_nextBucketHash
[hash
% NextBucketHashSize
] = bucket
;
727 uint
freeItemCount() const {
728 return m_freeItemCount
;
731 short unsigned int totalFreeItemsSize() const {
732 short unsigned int ret
= 0;
733 short unsigned int currentIndex
= m_largestFreeItem
;
734 while(currentIndex
) {
735 ret
+= freeSize(currentIndex
);
736 currentIndex
= followerIndex(currentIndex
);
741 //Size of the largest item that could be inserted into this bucket
742 short unsigned int largestFreeSize() const {
743 short unsigned int ret
= 0;
744 if(m_largestFreeItem
)
745 ret
= freeSize(m_largestFreeItem
);
746 if(m_available
> (uint
)(AdditionalSpacePerItem
+ (uint
)ret
)) {
747 ret
= m_available
- AdditionalSpacePerItem
;
748 Q_ASSERT(ret
== (m_available
- AdditionalSpacePerItem
));
753 bool canAllocateItem(unsigned int size
) const {
754 short unsigned int currentIndex
= m_largestFreeItem
;
755 while(currentIndex
) {
756 short unsigned int currentFree
= freeSize(currentIndex
);
757 if(currentFree
< size
)
759 if(size
== currentFree
|| currentFree
- size
>= AdditionalSpacePerItem
+ 2)
761 currentIndex
= followerIndex(currentIndex
);
771 //How many ticks ago the item was last used
772 int lastUsed() const {
776 //Whether this bucket was changed since it was last stored
777 bool changed() const {
785 ///Returns the count of following buckets that were merged onto this buckets data array
786 uint
monsterBucketExtent() const {
787 return m_monsterBucketExtent
;
790 //Counts together the space that is neither accessible through m_objectMap nor through the free items
792 if(m_monsterBucketExtent
)
795 uint need
= ItemRepositoryBucketSize
- m_available
;
798 for(uint a
= 0; a
< m_objectMapSize
; ++a
) {
799 uint currentIndex
= m_objectMap
[a
];
800 while(currentIndex
) {
801 found
+= ((const Item
*)(m_data
+currentIndex
))->itemSize() + AdditionalSpacePerItem
;
803 currentIndex
= followerIndex(currentIndex
);
806 uint currentIndex
= m_largestFreeItem
;
807 while(currentIndex
) {
808 found
+= freeSize(currentIndex
) + AdditionalSpacePerItem
;
810 currentIndex
= followerIndex(currentIndex
);
817 ///Merges the given index item, which must have a freeSize() set, to surrounding free items, and inserts the result.
818 ///The given index itself should not be in the free items chain yet.
819 ///Returns whether the item was inserted somewhere.
820 void insertFreeItem(unsigned short index
) {
821 unsigned short currentIndex
= m_largestFreeItem
;
822 unsigned short previousIndex
= 0;
824 while(currentIndex
) {
827 if(currentIndex
== index
+ freeSize(index
) + AdditionalSpacePerItem
) {
829 //Remove currentIndex from the free chain, since it's merged backwards into index
831 setFollowerIndex(previousIndex
, followerIndex(currentIndex
));
833 m_largestFreeItem
= followerIndex(currentIndex
);
835 --m_freeItemCount
; //One was removed
837 //currentIndex is directly behind index, touching its space. Merge them.
838 setFreeSize(index
, freeSize(index
) + AdditionalSpacePerItem
+ freeSize(currentIndex
));
840 //Recurse to do even more merging
841 insertFreeItem(index
);
846 if(index
== currentIndex
+ freeSize(currentIndex
) + AdditionalSpacePerItem
) {
848 //Remove currentIndex from the free chain, since insertFreeItem wants
849 //it not to be in the chain, and it will be inserted in another place
851 setFollowerIndex(previousIndex
, followerIndex(currentIndex
));
853 m_largestFreeItem
= followerIndex(currentIndex
);
855 --m_freeItemCount
; //One was removed
857 //index is directly behind currentIndex, touching its space. Merge them.
858 setFreeSize(currentIndex
, freeSize(currentIndex
) + AdditionalSpacePerItem
+ freeSize(index
));
860 //Recurse to do even more merging
861 insertFreeItem(currentIndex
);
866 previousIndex
= currentIndex
;
867 currentIndex
= followerIndex(currentIndex
);
870 insertToFreeChain(index
);
873 ///Only inserts the item in the correct position into the free chain. index must not be in the chain yet.
874 void insertToFreeChain(unsigned short index
) {
875 //Insert the free item into the chain opened by m_largestFreeItem
876 unsigned short currentIndex
= m_largestFreeItem
;
877 unsigned short previousIndex
= 0;
879 unsigned short size
= freeSize(index
);
881 while(currentIndex
&& *(unsigned short*)(m_data
+ currentIndex
) > size
) {
882 Q_ASSERT(currentIndex
!= index
); //must not be in the chain yet
883 previousIndex
= currentIndex
;
884 currentIndex
= followerIndex(currentIndex
);
887 setFollowerIndex(index
, currentIndex
);
890 setFollowerIndex(previousIndex
, index
);
892 //This item is larger than all already registered free items, or there are none.
893 m_largestFreeItem
= index
;
898 ///Returns true if the given index is right behind free space, and thus can be merged to the free space.
899 bool isBehindFreeSpace(unsigned short index
) const {
900 unsigned short currentIndex
= m_largestFreeItem
;
902 while(currentIndex
) {
903 if(index
== currentIndex
+ freeSize(currentIndex
) + AdditionalSpacePerItem
)
906 currentIndex
= followerIndex(currentIndex
);
911 ///@param index the index of an item @return The index of the next item in the chain of items with a same local hash, or zero
912 inline unsigned short followerIndex(unsigned short index
) const {
913 Q_ASSERT(index
>= 2);
914 return *((unsigned short*)(m_data
+(index
-2)));
917 void setFollowerIndex(unsigned short index
, unsigned short follower
) {
918 Q_ASSERT(index
>= 2);
919 *((unsigned short*)(m_data
+(index
-2))) = follower
;
921 //Only returns the corrent value if the item is actually free
922 inline unsigned short freeSize(unsigned short index
) const {
923 return *((unsigned short*)(m_data
+index
));
926 //Convenience function to set the free-size, only for freed items
927 void setFreeSize(unsigned short index
, unsigned short size
) {
928 *((unsigned short*)(m_data
+index
)) = size
;
931 uint m_monsterBucketExtent
; //If this is a monster-bucket, this contains the count of follower-buckets that belong to this one
932 unsigned int m_available
;
933 char* m_data
; //Structure of the data: <Position of next item with same hash modulo ItemRepositoryBucketSize>(2 byte), <Item>(item.size() byte)
934 short unsigned int* m_objectMap
; //Points to the first object in m_data with (hash % m_objectMapSize) == index. Points to the item itself, so substract 1 to get the pointer to the next item with same local hash.
935 uint m_objectMapSize
;
936 short unsigned int m_largestFreeItem
; //Points to the largest item that is currently marked as free, or zero. That one points to the next largest one through followerIndex
937 unsigned int m_freeItemCount
;
939 unsigned short* m_nextBucketHash
;
941 bool m_changed
; //Whether this bucket was changed since it was last stored to disk
942 mutable int m_lastUsed
; //How many ticks ago this bucket was last accessed
946 struct Locker
{ //This is a dummy that does nothing
948 Locker(const T
& /*t*/) {
952 struct Locker
<true> {
953 Locker(QMutex
* mutex
) : m_mutex(mutex
) {
962 struct NoDynamicData
{
968 static void initialize(char* /*data*/) {
971 ///When this returns false, the item is deleted
972 bool apply(const char*) const {
977 struct ReferenceCounting
{
980 Size
= sizeof(unsigned int)
983 ReferenceCounting(bool increment
) : m_increment(increment
) {
986 static void initialize(char* data
) {
987 *((unsigned int*)data
) = 0;
990 ///When this returns false, the item is deleted
991 bool apply(char* data
) const {
993 ++*((unsigned int*)data
);
995 --*((unsigned int*)data
);
997 return *((unsigned int*)data
);
1003 ///@param Item @see ExampleItem
1004 ///@param ItemRequest @see ExampleReqestItem
1005 ///@param DynamicData Can be used to attach additional metadata of constant size to each item.
1006 /// That meta-data can be manipulated by giving manipulators to the ItemRepository Member functions.
1007 /// This can be used to implement reference-counting, @see ReferenceCounting
1008 ///@param threadSafe Whether class access should be thread-safe
1009 template<class Item
, class ItemRequest
, class DynamicData
= NoDynamicData
, bool threadSafe
= true, unsigned int targetBucketHashSize
= 524288>
1010 class ItemRepository
: public AbstractItemRepository
{
1012 typedef Locker
<threadSafe
> ThisLocker
;
1015 //Must be a multiple of Bucket::ObjectMapSize, so Bucket::hasClashingItem can be computed
1016 //Must also be a multiple of Bucket::NextBucketHashSize, for the same reason.(Currently those are same)
1017 bucketHashSize
= (targetBucketHashSize
/ Bucket
<Item
, ItemRequest
, DynamicData
>::ObjectMapSize
) * Bucket
<Item
, ItemRequest
, DynamicData
>::ObjectMapSize
1021 BucketStartOffset
= sizeof(uint
) * 7 + sizeof(short unsigned int) * bucketHashSize
//Position in the data where the bucket array starts
1025 ///@param registry May be zero, then the repository will not be registered at all. Else, the repository will register itself to that registry.
1026 /// If this is zero, you have to care about storing the data using store() and/or close() by yourself. It does not happen automatically.
1027 /// For the global standard registry, the storing/loading is triggered from within duchain, so you don't need to care about it.
1028 ItemRepository(QString repositoryName
, ItemRepositoryRegistry
* registry
= &globalItemRepositoryRegistry(), uint repositoryVersion
= 1) : m_mutex(QMutex::Recursive
), m_repositoryName(repositoryName
), m_registry(registry
), m_file(0), m_dynamicFile(0), m_repositoryVersion(repositoryVersion
) {
1029 m_unloadingEnabled
= true;
1030 m_metaDataChanged
= true;
1031 m_buckets
.resize(10);
1033 m_freeSpaceBucketsSize
= 0;
1034 m_fastBuckets
= m_buckets
.data();
1035 m_bucketCount
= m_buckets
.size();
1036 m_bucketHashSize
= bucketHashSize
;
1038 m_firstBucketForHash
= new short unsigned int[bucketHashSize
];
1039 memset(m_firstBucketForHash
, 0, bucketHashSize
* sizeof(short unsigned int));
1041 m_statBucketHashClashes
= m_statItemCount
= 0;
1042 m_currentBucket
= 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes
1044 m_registry
->registerRepository(this);
1049 m_registry
->unRegisterRepository(this);
1053 ///Unloading of buckets is enabled by default. Use this to disable it. When unloading is enabled, the data
1054 ///gotten from must only itemFromIndex must not be used for a long time.
1055 void setUnloadingEnabled(bool enabled
) {
1056 m_unloadingEnabled
= enabled
;
1059 ///Returns the index for the given item. If the item is not in the repository yet, it is inserted.
1060 ///The index can never be zero. Zero is reserved for your own usage as invalid
1061 ///@param dynamic will be applied to the dynamic data of the found item
1062 unsigned int index(const ItemRequest
& request
, const DynamicData
* dynamic
= 0) {
1064 ThisLocker
lock(&m_mutex
);
1066 unsigned int hash
= request
.hash();
1067 unsigned int size
= request
.itemSize();
1069 short unsigned int* bucketHashPosition
= m_firstBucketForHash
+ (hash
% bucketHashSize
);
1070 short unsigned int previousBucketNumber
= *bucketHashPosition
;
1071 short unsigned int previousPreviousBucketNumber
= 0;
1073 uint useBucket
= m_currentBucket
;
1074 bool pickedBucketInChain
= false; //Whether a bucket was picked for re-use that already is in the hash chain
1075 int reOrderFreeSpaceBucketIndex
= -1;
1077 while(previousBucketNumber
) {
1078 //We have a bucket that contains an item with the given hash % bucketHashSize, so check if the item is already there
1079 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[previousBucketNumber
];
1081 initializeBucket(previousBucketNumber
);
1082 bucketPtr
= m_fastBuckets
[previousBucketNumber
];
1085 unsigned short indexInBucket
= bucketPtr
->findIndex(request
, dynamic
);
1087 //We've found the item, it's already there
1088 return (previousBucketNumber
<< 16) + indexInBucket
; //Combine the index in the bucket, and the bucker number into one index
1090 if(!pickedBucketInChain
&& bucketPtr
->canAllocateItem(size
)) {
1091 //Remember that this bucket has enough space to store the item, if it isn't already stored.
1092 //This gives a better structure, and saves us from cyclic follower structures.
1093 useBucket
= previousBucketNumber
;
1094 reOrderFreeSpaceBucketIndex
= m_freeSpaceBuckets
.indexOf(useBucket
);
1095 pickedBucketInChain
= true;
1097 //The item isn't in bucket previousBucketNumber, but maybe the bucket has a pointer to the next bucket that might contain the item
1098 //Should happen rarely
1099 short unsigned int next
= bucketPtr
->nextBucketForHash(hash
);
1101 previousPreviousBucketNumber
= previousBucketNumber
;
1102 previousBucketNumber
= next
;
1108 m_metaDataChanged
= true;
1110 if(!pickedBucketInChain
&& useBucket
== m_currentBucket
) {
1111 //Try finding an existing bucket with deleted space to store the data into
1112 for(uint a
= 0; a
< m_freeSpaceBucketsSize
; ++a
) {
1113 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= bucketForIndex(m_freeSpaceBuckets
[a
]);
1115 if(bucketPtr
->canAllocateItem(size
)) {
1116 //The item fits into the bucket.
1117 useBucket
= m_freeSpaceBuckets
[a
];
1118 reOrderFreeSpaceBucketIndex
= a
;
1124 //The item isn't in the repository yet, find a new bucket for it
1126 if(useBucket
>= m_bucketCount
) {
1127 if(m_bucketCount
>= 0xfffe) { //We have reserved the last bucket index 0xffff for special purposes
1128 //the repository has overflown.
1129 kWarning() << "Found no room for an item in" << m_repositoryName
<< "size of the item:" << request
.itemSize();
1132 //Allocate new buckets
1133 uint oldBucketCount
= m_bucketCount
;
1134 m_bucketCount
+= 10;
1135 m_buckets
.resize(m_bucketCount
);
1136 m_fastBuckets
= m_buckets
.data();
1137 memset(m_fastBuckets
+ oldBucketCount
, 0, (m_bucketCount
-oldBucketCount
) * sizeof(void*));
1140 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[useBucket
];
1142 initializeBucket(useBucket
);
1143 bucketPtr
= m_fastBuckets
[useBucket
];
1146 ENSURE_REACHABLE(useBucket
);
1147 Q_ASSERT(!bucketPtr
->findIndex(request
, 0));
1149 unsigned short indexInBucket
= bucketPtr
->index(request
, dynamic
, size
);
1151 //If we could not allocate the item in an empty bucket, then we need to create a monster-bucket that
1152 //can hold the data.
1153 if(bucketPtr
->isEmpty() && !indexInBucket
) {
1154 ///@todo Move this compound statement into an own function
1155 uint totalSize
= size
+ Bucket
<Item
, ItemRequest
, DynamicData
>::AdditionalSpacePerItem
;
1157 Q_ASSERT((totalSize
> ItemRepositoryBucketSize
));
1160 //The item did not fit in, we need a monster-bucket(Merge consecutive buckets)
1161 ///Step one: Search whether we can merge multiple empty buckets in the free-list into one monster-bucket
1162 int rangeStart
= -1;
1164 for(int a
= 0; a
< (int)m_freeSpaceBucketsSize
; ++a
) {
1165 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= bucketForIndex(m_freeSpaceBuckets
[a
]);
1166 if(bucketPtr
->isEmpty()) {
1167 //This bucket is a candidate for monster-bucket merging
1168 int index
= (int)m_freeSpaceBuckets
[a
];
1169 if(rangeEnd
!= index
) {
1175 if(rangeStart
!= rangeEnd
) {
1176 uint extent
= rangeEnd
- rangeStart
- 1;
1177 uint totalAvailableSpace
= bucketForIndex(rangeStart
)->available() + Bucket
<Item
, ItemRequest
, DynamicData
>::DataSize
* (rangeEnd
- rangeStart
- 1);
1178 if(totalAvailableSpace
> totalSize
) {
1180 ///We can merge these buckets into one monster-bucket that can hold the data
1181 Q_ASSERT(m_freeSpaceBuckets
[a
-extent
] == rangeStart
);
1182 m_freeSpaceBuckets
.remove(a
-extent
, extent
+1);
1183 m_freeSpaceBucketsSize
= m_freeSpaceBuckets
.size();
1184 useBucket
= rangeStart
;
1185 convertMonsterBucket(rangeStart
, extent
);
1193 //Create a new monster-bucket at the end of the data
1194 uint needMonsterExtent
= (totalSize
- ItemRepositoryBucketSize
) / Bucket
<Item
, ItemRequest
, DynamicData
>::DataSize
+ 1;
1195 Q_ASSERT(needMonsterExtent
);
1196 if(m_currentBucket
+ needMonsterExtent
+ 1 > (uint
)m_buckets
.size()) {
1197 uint oldBucketCount
= m_bucketCount
;
1198 m_bucketCount
+= 10 + needMonsterExtent
+ 1;
1199 m_buckets
.resize(m_bucketCount
);
1200 m_fastBuckets
= m_buckets
.data();
1202 memset(m_fastBuckets
+ oldBucketCount
, 0, (m_bucketCount
-oldBucketCount
) * sizeof(void*));
1204 useBucket
= m_currentBucket
;
1206 convertMonsterBucket(useBucket
, needMonsterExtent
);
1207 m_currentBucket
+= 1 + needMonsterExtent
;
1208 Q_ASSERT(m_fastBuckets
[m_currentBucket
- 1 - needMonsterExtent
] && m_fastBuckets
[m_currentBucket
- 1 - needMonsterExtent
]->monsterBucketExtent() == needMonsterExtent
);
1210 Q_ASSERT(useBucket
);
1211 bucketPtr
= bucketForIndex(useBucket
);
1213 indexInBucket
= bucketPtr
->index(request
, dynamic
, size
);
1214 Q_ASSERT(indexInBucket
);
1220 if(!(*bucketHashPosition
)) {
1221 Q_ASSERT(!previousBucketNumber
);
1222 (*bucketHashPosition
) = useBucket
;
1223 ENSURE_REACHABLE(useBucket
);
1224 } else if(!pickedBucketInChain
&& previousBucketNumber
&& previousBucketNumber
!= useBucket
) {
1225 //Should happen rarely
1226 ++m_statBucketHashClashes
;
1228 ///Debug: Detect infinite recursion
1229 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, previousBucketNumber
));)
1231 //Find the position where the paths of useBucket and *bucketHashPosition intersect, and insert useBucket
1232 //there. That way, we don't create loops.
1233 QPair
<unsigned int, unsigned int> intersect
= hashChainIntersection(*bucketHashPosition
, useBucket
, hash
);
1235 Q_ASSERT(m_buckets
[previousBucketNumber
]->nextBucketForHash(hash
) == 0);
1237 if(!intersect
.second
) {
1238 ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition
, hash
, useBucket
));)
1239 ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(useBucket
, hash
, previousBucketNumber
));)
1241 Q_ASSERT(m_buckets
[previousBucketNumber
]->nextBucketForHash(hash
) == 0);
1243 m_buckets
[previousBucketNumber
]->setNextBucketForHash(hash
, useBucket
);
1244 ENSURE_REACHABLE(useBucket
);
1245 ENSURE_REACHABLE(previousBucketNumber
);
1247 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, useBucket
));)
1248 } else if(intersect
.first
) {
1249 ifDebugInfiniteRecursion(Q_ASSERT(bucketForIndex(intersect
.first
)->nextBucketForHash(hash
) == intersect
.second
);)
1250 ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition
, hash
, useBucket
));)
1251 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, intersect
.second
));)
1252 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, intersect
.first
));)
1253 ifDebugInfiniteRecursion(Q_ASSERT(bucketForIndex(intersect
.first
)->nextBucketForHash(hash
) == intersect
.second
);)
1255 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(useBucket
, hash
, intersect
.second
));)
1256 ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(useBucket
, hash
, intersect
.first
));)
1258 bucketForIndex(intersect
.first
)->setNextBucketForHash(hash
, useBucket
);
1260 ENSURE_REACHABLE(useBucket
);
1261 ENSURE_REACHABLE(intersect
.second
);
1263 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, useBucket
));)
1264 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, intersect
.second
));)
1266 //State: intersect.first == 0 && intersect.second != 0. This means that whole compleet
1267 //chain opened by *bucketHashPosition with the hash-value is also following useBucket,
1268 //so useBucket can just be inserted at the top
1270 ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition
, hash
, useBucket
));)
1271 ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(useBucket
, hash
, *bucketHashPosition
));)
1272 unsigned short oldStart
= *bucketHashPosition
;
1274 *bucketHashPosition
= useBucket
;
1276 ENSURE_REACHABLE(useBucket
);
1277 ENSURE_REACHABLE(oldStart
);
1282 if(reOrderFreeSpaceBucketIndex
!= -1)
1283 updateFreeSpaceOrder(reOrderFreeSpaceBucketIndex
);
1285 return (useBucket
<< 16) + indexInBucket
; //Combine the index in the bucket, and the bucker number into one index
1287 //This should never happen when we picked a bucket for re-use
1288 Q_ASSERT(!pickedBucketInChain
);
1289 Q_ASSERT(reOrderFreeSpaceBucketIndex
== -1);
1290 Q_ASSERT(useBucket
== m_currentBucket
);
1292 if(!bucketForIndex(useBucket
)->isEmpty())
1293 putIntoFreeList(useBucket
, bucketPtr
);
1296 useBucket
= m_currentBucket
;
1299 //We haven't found a bucket that already contains the item, so append it to the current bucket
1301 kWarning() << "Found no bucket for an item in" << m_repositoryName
;
1305 ///Returns zero if the item is not in the repository yet
1306 unsigned int findIndex(const ItemRequest
& request
) {
1308 ThisLocker
lock(&m_mutex
);
1310 unsigned int hash
= request
.hash();
1312 short unsigned int* bucketHashPosition
= m_firstBucketForHash
+ (hash
% bucketHashSize
);
1313 short unsigned int previousBucketNumber
= *bucketHashPosition
;
1315 while(previousBucketNumber
) {
1316 //We have a bucket that contains an item with the given hash % bucketHashSize, so check if the item is already there
1318 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[previousBucketNumber
];
1320 initializeBucket(previousBucketNumber
);
1321 bucketPtr
= m_fastBuckets
[previousBucketNumber
];
1324 unsigned short indexInBucket
= bucketPtr
->findIndex(request
, 0);
1326 //We've found the item, it's already there
1327 return (previousBucketNumber
<< 16) + indexInBucket
; //Combine the index in the bucket, and the bucker number into one index
1329 //The item isn't in bucket previousBucketNumber, but maybe the bucket has a pointer to the next bucket that might contain the item
1330 //Should happen rarely
1331 short unsigned int next
= bucketPtr
->nextBucketForHash(hash
);
1333 previousBucketNumber
= next
;
1342 ///Deletes the item from the repository.
1343 void deleteItem(unsigned int index
) {
1344 ThisLocker
lock(&m_mutex
);
1346 m_metaDataChanged
= true;
1348 unsigned short bucket
= (index
>> 16);
1349 Q_ASSERT(bucket
); //We don't use zero buckets
1351 unsigned int hash
= itemFromIndex(index
)->hash();
1353 short unsigned int* bucketHashPosition
= m_firstBucketForHash
+ (hash
% bucketHashSize
);
1354 short unsigned int previousBucketNumber
= *bucketHashPosition
;
1356 Q_ASSERT(previousBucketNumber
);
1358 if(previousBucketNumber
== bucket
)
1359 previousBucketNumber
= 0;
1361 Bucket
<Item
, ItemRequest
, DynamicData
>* previousBucketPtr
= 0;
1363 //Apart from removing the item itself, we may have to recreate the nextBucketForHash link, so we need the previous bucket
1365 while(previousBucketNumber
) {
1366 //We have a bucket that contains an item with the given hash % bucketHashSize, so check if the item is already there
1368 previousBucketPtr
= m_fastBuckets
[previousBucketNumber
];
1369 if(!previousBucketPtr
) {
1370 initializeBucket(previousBucketNumber
);
1371 previousBucketPtr
= m_fastBuckets
[previousBucketNumber
];
1374 short unsigned int nextBucket
= previousBucketPtr
->nextBucketForHash(hash
);
1375 Q_ASSERT(nextBucket
);
1376 if(nextBucket
== bucket
)
1377 break; //Now previousBucketNumber
1379 previousBucketNumber
= nextBucket
;
1382 //Make sure the index was reachable through the hashes
1383 Q_ASSERT(previousBucketNumber
|| *bucketHashPosition
== bucket
);
1385 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[bucket
];
1387 initializeBucket(bucket
);
1388 bucketPtr
= m_fastBuckets
[bucket
];
1393 bucketPtr
->deleteItem(index
, hash
);
1396 * Now check whether the link previousBucketNumber -> bucket is still needed.
1398 //return; ///@todo Find out what this problem is about. If we don't return here, some items become undiscoverable through hashes after some time
1399 if(previousBucketNumber
== 0) {
1400 //The item is directly in the m_firstBucketForHash hash
1401 //Put the next item in the nextBucketForHash chain into m_firstBucketForHash that has a hash clashing in that array.
1402 Q_ASSERT(*bucketHashPosition
== bucket
);
1403 unsigned short previous
= bucket
;
1404 while(!bucketPtr
->hasClashingItem(hash
, bucketHashSize
))
1406 // Q_ASSERT(!bucketPtr->hasClashingItemReal(hash, bucketHashSize));
1408 unsigned short next
= bucketPtr
->nextBucketForHash(hash
);
1409 ENSURE_REACHABLE(next
);
1410 ENSURE_REACHABLE(previous
);
1412 *bucketHashPosition
= next
;
1414 ENSURE_REACHABLE(previous
);
1415 ENSURE_REACHABLE(next
);
1420 bucketPtr
= m_fastBuckets
[next
];
1424 initializeBucket(next
);
1425 bucketPtr
= m_fastBuckets
[next
];
1432 if(!bucketPtr
->hasClashingItem(hash
, Bucket
<Item
, ItemRequest
, DynamicData
>::NextBucketHashSize
)) {
1433 // Q_ASSERT(!bucketPtr->hasClashingItemReal(hash, Bucket<Item, ItemRequest, DynamicData>::NextBucketHashSize));
1434 ///Debug: Check for infinite recursion
1435 walkBucketLinks(*bucketHashPosition
, hash
);
1437 Q_ASSERT(previousBucketPtr
->nextBucketForHash(hash
) == bucket
);
1439 ENSURE_REACHABLE(bucket
);
1441 previousBucketPtr
->setNextBucketForHash(hash
, bucketPtr
->nextBucketForHash(hash
));
1443 ENSURE_REACHABLE(bucket
);
1445 ///Debug: Check for infinite recursion
1446 Q_ASSERT(walkBucketLinks(*bucketHashPosition
, hash
, bucketPtr
->nextBucketForHash(hash
)));
1448 Q_ASSERT(bucketPtr
->nextBucketForHash(hash
) != previousBucketNumber
);
1452 ENSURE_REACHABLE(bucket
);
1454 if(bucketPtr
->monsterBucketExtent()) {
1455 //Convert the monster-bucket back to multiple normal buckets, and put them into the free list
1456 uint newBuckets
= bucketPtr
->monsterBucketExtent()+1;
1457 Q_ASSERT(bucketPtr
->isEmpty());
1458 convertMonsterBucket(bucket
, 0);
1459 for(uint created
= bucket
; created
< bucket
+ newBuckets
; ++created
) {
1460 putIntoFreeList(created
, bucketForIndex(created
));
1461 #ifdef DEBUG_MONSTERBUCKETS
1462 Q_ASSERT(m_freeSpaceBuckets
.indexOf(created
) != -1);
1466 putIntoFreeList(bucket
, bucketPtr
);
1470 ///This returns an editable version of the item. @warning: Never change an entry that affects the hash,
1471 ///or the equals(..) function. That would completely destroy the consistency.
1472 ///@param index The index. It must be valid(match an existing item), and nonzero.
1473 ///@param dynamic will be applied to the item.
1474 Item
* dynamicItemFromIndex(unsigned int index
, const DynamicData
* dynamic
= 0) {
1477 ThisLocker
lock(&m_mutex
);
1479 unsigned short bucket
= (index
>> 16);
1480 Q_ASSERT(bucket
); //We don't use zero buckets
1482 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[bucket
];
1483 Q_ASSERT(bucket
< m_bucketCount
);
1485 initializeBucket(bucket
);
1486 bucketPtr
= m_fastBuckets
[bucket
];
1488 bucketPtr
->setChanged();
1489 unsigned short indexInBucket
= index
& 0xffff;
1490 return const_cast<Item
*>(bucketPtr
->itemFromIndex(indexInBucket
, dynamic
));
1493 ///@param index The index. It must be valid(match an existing item), and nonzero.
1494 ///@param dynamic will be applied to the item.
1495 const Item
* itemFromIndex(unsigned int index
, const DynamicData
* dynamic
= 0) const {
1498 ThisLocker
lock(&m_mutex
);
1500 unsigned short bucket
= (index
>> 16);
1501 Q_ASSERT(bucket
); //We don't use zero buckets
1503 const Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[bucket
];
1504 Q_ASSERT(bucket
< m_bucketCount
);
1506 initializeBucket(bucket
);
1507 bucketPtr
= m_fastBuckets
[bucket
];
1509 unsigned short indexInBucket
= index
& 0xffff;
1510 return bucketPtr
->itemFromIndex(indexInBucket
, dynamic
);
1514 Statistics() : loadedBuckets(-1), currentBucket(-1), usedMemory(-1), loadedMonsterBuckets(-1), usedSpaceForBuckets(-1), freeSpaceInBuckets(-1), lostSpace(-1), freeUnreachableSpace(-1), hashClashedItems(-1), totalItems(-1) {
1520 uint loadedMonsterBuckets
;
1521 uint usedSpaceForBuckets
;
1522 uint freeSpaceInBuckets
;
1524 uint freeUnreachableSpace
;
1525 uint hashClashedItems
;
1529 QString
print() const {
1531 ret
+= QString("loaded buckets: %1 current bucket: %2 used memory: %3 loaded monster buckets: %4").arg(loadedBuckets
).arg(currentBucket
).arg(usedMemory
).arg(loadedMonsterBuckets
);
1532 ret
+= QString("\nbucket hash clashed items: %1 total items: %2").arg(hashClashedItems
).arg(totalItems
);
1533 ret
+= QString("\nused space for buckets: %1 free space in buckets: %2 lost space: %3").arg(usedSpaceForBuckets
).arg(freeSpaceInBuckets
).arg(lostSpace
);
1534 ret
+= QString("\nfree unreachable space: %1 empty buckets: %2").arg(freeUnreachableSpace
).arg(emptyBuckets
);
1537 operator QString() const {
1542 Statistics
statistics() const {
1544 uint loadedBuckets
= 0;
1545 for(uint a
= 0; a
< m_bucketCount
; ++a
)
1546 if(m_fastBuckets
[a
])
1549 #ifdef DEBUG_MONSTERBUCKETS
1550 for(int a
= 0; a
< m_freeSpaceBucketsSize
; ++a
) {
1553 uint prevLargestFree
= bucketForIndex(m_freeSpaceBuckets
[prev
])->largestFreeSize();
1554 uint largestFree
= bucketForIndex(m_freeSpaceBuckets
[a
])->largestFreeSize();
1555 Q_ASSERT( (prevLargestFree
< largestFree
) || (prevLargestFree
== largestFree
&&
1556 m_freeSpaceBuckets
[prev
] < m_freeSpaceBuckets
[a
]) );
1561 ret
.emptyBuckets
= 0;
1563 uint loadedMonsterBuckets
= 0;
1564 for(uint a
= 0; a
< m_bucketCount
; ++a
)
1565 if(m_fastBuckets
[a
] && m_fastBuckets
[a
]->monsterBucketExtent())
1566 loadedMonsterBuckets
+= m_fastBuckets
[a
]->monsterBucketExtent()+1;
1568 uint usedBucketSpace
= Bucket
<Item
, ItemRequest
, DynamicData
>::DataSize
* m_currentBucket
;
1569 uint freeBucketSpace
= 0, freeUnreachableSpace
= 0;
1570 uint lostSpace
= 0; //Should be zero, else something is wrong
1571 for(uint a
= 1; a
< m_currentBucket
+1; ++a
) {
1572 Bucket
<Item
, ItemRequest
, DynamicData
>* bucket
= bucketForIndex(a
);
1574 uint bucketFreeSpace
= bucket
->totalFreeItemsSize() + bucket
->available();
1575 freeBucketSpace
+= bucketFreeSpace
;
1576 if(m_freeSpaceBuckets
.indexOf(a
) == -1)
1577 freeUnreachableSpace
+= bucketFreeSpace
;
1579 if(bucket
->isEmpty()) {
1581 Q_ASSERT(!bucket
->monsterBucketExtent());
1582 Q_ASSERT(m_freeSpaceBuckets
.contains(a
));
1585 lostSpace
+= bucket
->lostSpace();
1586 a
+= bucket
->monsterBucketExtent();
1590 ret
.loadedBuckets
= loadedBuckets
;
1591 ret
.currentBucket
= m_currentBucket
;
1592 ret
.usedMemory
= usedMemory();
1593 ret
.loadedMonsterBuckets
= loadedMonsterBuckets
;
1595 ret
.hashClashedItems
= m_statBucketHashClashes
;
1596 ret
.totalItems
= m_statItemCount
;
1597 ret
.usedSpaceForBuckets
= usedBucketSpace
;
1598 ret
.freeSpaceInBuckets
= freeBucketSpace
;
1599 ret
.lostSpace
= lostSpace
;
1601 ret
.freeUnreachableSpace
= freeUnreachableSpace
;
1603 //If m_statBucketHashClashes is high, the bucket-hash needs to be bigger
1607 uint
usedMemory() const {
1609 for(int a
= 0; a
< m_buckets
.size(); ++a
) {
1611 used
+= m_buckets
[a
]->usedMemory();
1617 ///This can be used to safely iterate through all items in the repository
1618 ///@param visitor Should be an instance of a class that has a bool operator()(const Item*) member function,
1619 /// that returns whether more items are wanted.
1620 ///@param onlyInMemory If this is true, only items are visited that are currently in memory.
1621 template<class Visitor
>
1622 void visitAllItems(Visitor
& visitor
, bool onlyInMemory
= false) const {
1623 ThisLocker
lock(&m_mutex
);
1624 for(uint a
= 1; a
<= m_currentBucket
; ++a
) {
1625 if(!onlyInMemory
|| m_buckets
[a
]) {
1626 if(bucketForIndex(a
) && !bucketForIndex(a
)->visitAllItems(visitor
))
1632 ///Visits all items that have the given hash-value, plus an arbitrary count of other items with a clashing hash.
1633 ///@param visitor Should be an instance of a class that has a bool operator()(const Item*, uint index) member function,
1634 /// that returns whether more items are wanted.
1635 template<class Visitor
>
1636 void visitItemsWithHash(Visitor
& visitor
, uint hash
) const {
1637 ThisLocker
lock(&m_mutex
);
1639 short unsigned int bucket
= *(m_firstBucketForHash
+ (hash
% bucketHashSize
));
1643 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[bucket
];
1645 initializeBucket(bucket
);
1646 bucketPtr
= m_fastBuckets
[bucket
];
1649 if(!bucketPtr
->visitItemsWithHash(visitor
, hash
, bucket
))
1652 bucket
= bucketPtr
->nextBucketForHash(hash
);
1656 ///Synchronizes the state on disk to the one in memory, and does some memory-management.
1657 ///Should be called on a regular basis. Can be called centrally from the global item repository registry.
1658 virtual void store() {
1659 ThisLocker
lock(&m_mutex
);
1661 if(!m_file
->open( QFile::ReadWrite
) || !m_dynamicFile
->open( QFile::ReadWrite
)) {
1662 kWarning() << "cannot re-open repository file for storing";
1666 for(uint a
= 0; a
< m_bucketCount
; ++a
) {
1667 if(m_fastBuckets
[a
]) {
1668 if(m_fastBuckets
[a
]->changed()) {
1671 if(m_unloadingEnabled
) {
1672 const int unloadAfterTicks
= 2;
1673 if(m_fastBuckets
[a
]->lastUsed() > unloadAfterTicks
) {
1674 delete m_fastBuckets
[a
];
1675 m_fastBuckets
[a
] = 0;
1677 m_fastBuckets
[a
]->tick();
1683 if(m_metaDataChanged
) {
1684 Q_ASSERT(m_dynamicFile
);
1687 m_file
->write((char*)&m_repositoryVersion
, sizeof(uint
));
1688 uint hashSize
= bucketHashSize
;
1689 m_file
->write((char*)&hashSize
, sizeof(uint
));
1690 uint itemRepositoryVersion
= staticItemRepositoryVersion();
1691 m_file
->write((char*)&itemRepositoryVersion
, sizeof(uint
));
1692 m_file
->write((char*)&m_statBucketHashClashes
, sizeof(uint
));
1693 m_file
->write((char*)&m_statItemCount
, sizeof(uint
));
1695 uint bucketCount
= m_buckets
.size();
1696 m_file
->write((char*)&bucketCount
, sizeof(uint
));
1697 m_file
->write((char*)&m_currentBucket
, sizeof(uint
));
1698 m_file
->write((char*)m_firstBucketForHash
, sizeof(short unsigned int) * bucketHashSize
);
1699 Q_ASSERT(m_file
->pos() == BucketStartOffset
);
1701 Q_ASSERT(m_freeSpaceBucketsSize
== (uint
)m_freeSpaceBuckets
.size());
1702 m_dynamicFile
->seek(0);
1703 m_dynamicFile
->write((char*)&m_freeSpaceBucketsSize
, sizeof(uint
));
1704 m_dynamicFile
->write((char*)m_freeSpaceBuckets
.data(), sizeof(uint
) * m_freeSpaceBucketsSize
);
1706 // #ifdef DEBUG_ITEMREPOSITORY_LOADING
1710 // uint storedVersion, hashSize, itemRepositoryVersion, statBucketHashClashes, statItemCount;
1712 // m_file->read((char*)&storedVersion, sizeof(uint));
1713 // m_file->read((char*)&hashSize, sizeof(uint));
1714 // m_file->read((char*)&itemRepositoryVersion, sizeof(uint));
1715 // m_file->read((char*)&statBucketHashClashes, sizeof(uint));
1716 // m_file->read((char*)&statItemCount, sizeof(uint));
1717 // Q_ASSERT(storedVersion == m_repositoryVersion);
1718 // Q_ASSERT(hashSize == bucketHashSize);
1719 // Q_ASSERT(itemRepositoryVersion == ItemRepositoryVersion);
1720 // Q_ASSERT(statBucketHashClashes == m_statBucketHashClashes);
1721 // Q_ASSERT(statItemCount == m_statItemCount);
1723 // uint bucketCount, currentBucket;
1724 // m_file->read((char*)&bucketCount, sizeof(uint));
1725 // Q_ASSERT(bucketCount == (uint)m_buckets.size());
1726 // m_file->read((char*)¤tBucket, sizeof(uint));
1727 // Q_ASSERT(currentBucket == m_currentBucket);
1729 // short unsigned int* s = new short unsigned int[bucketHashSize];
1730 // m_file->read((char*)s, sizeof(short unsigned int) * bucketHashSize);
1731 // Q_ASSERT(memcmp(s, m_firstBucketForHash, sizeof(short unsigned int) * bucketHashSize) == 0);
1732 // Q_ASSERT(m_file->pos() == BucketStartOffset);
1737 //To protect us from inconsistency due to crashes. flush() is not enough.
1739 m_dynamicFile
->close();
1745 ///Makes sure the order within m_freeSpaceBuckets is correct, after largestFreeSize has been changed for m_freeSpaceBuckets[index].
1746 ///If too few space is free within the given bucket, it is removed from m_freeSpaceBuckets.
1747 void updateFreeSpaceOrder(uint index
) {
1748 m_metaDataChanged
= true;
1750 Q_ASSERT(index
< (uint
)m_freeSpaceBuckets
.size());
1751 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= bucketForIndex(m_freeSpaceBuckets
[index
]);
1753 unsigned short largestFreeSize
= bucketPtr
->largestFreeSize();
1755 if(largestFreeSize
== 0 || (bucketPtr
->freeItemCount() <= Bucket
<Item
, ItemRequest
, DynamicData
>::MaxFreeItemsForHide
&& largestFreeSize
<= Bucket
<Item
, ItemRequest
, DynamicData
>::MaxFreeSizeForHide
)) {
1756 //Remove the item from m_freeSpaceBuckets
1757 m_freeSpaceBuckets
.remove(index
);
1758 m_freeSpaceBucketsSize
= m_freeSpaceBuckets
.size();
1763 if(prev
>= 0 && (bucketForIndex(m_freeSpaceBuckets
[prev
])->largestFreeSize() > largestFreeSize
||
1764 (bucketForIndex(m_freeSpaceBuckets
[prev
])->largestFreeSize() == largestFreeSize
&& m_freeSpaceBuckets
[index
] < m_freeSpaceBuckets
[prev
]))
1766 //This item should be behind the successor, either because it has a lower largestFreeSize, or because the index is lower
1767 uint oldPrevValue
= m_freeSpaceBuckets
[prev
];
1768 m_freeSpaceBuckets
[prev
] = m_freeSpaceBuckets
[index
];
1769 m_freeSpaceBuckets
[index
] = oldPrevValue
;
1771 }else if(next
< m_freeSpaceBuckets
.size() && (bucketForIndex(m_freeSpaceBuckets
[next
])->largestFreeSize() < largestFreeSize
||
1772 (bucketForIndex(m_freeSpaceBuckets
[next
])->largestFreeSize() == largestFreeSize
&& m_freeSpaceBuckets
[index
] > m_freeSpaceBuckets
[next
]))) {
1773 //This item should be behind the successor, either because it has a higher largestFreeSize, or because the index is higher
1774 uint oldNextValue
= m_freeSpaceBuckets
[next
];
1775 m_freeSpaceBuckets
[next
] = m_freeSpaceBuckets
[index
];
1776 m_freeSpaceBuckets
[index
] = oldNextValue
;
1785 ///Does conversion from monster-bucket to normal bucket and from normal bucket to monster-bucket
1786 ///The bucket @param bucketNumber must already be loaded and empty. the "extent" buckets behind must also be loaded,
1787 ///and also be empty.
1788 ///The created buckets are not registered anywhere. When converting from monster-bucket to normal bucket,
1789 ///oldExtent+1 normal buckets are created, that must be registered somewhere.
1790 ///@warning During conversion, all the touched buckets are deleted and re-created
1791 ///@param extent When this is zero, the bucket is converted from monster-bucket to normal bucket.
1792 /// When it is nonzero, it is converted to a monster-bucket.
1793 Bucket
<Item
, ItemRequest
, DynamicData
>* convertMonsterBucket(short unsigned int bucketNumber
, unsigned int extent
) {
1794 Q_ASSERT(bucketNumber
);
1795 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[bucketNumber
];
1797 initializeBucket(bucketNumber
);
1798 bucketPtr
= m_fastBuckets
[bucketNumber
];
1802 //Convert to monster-bucket
1803 #ifdef DEBUG_MONSTERBUCKETS
1804 for(uint index
= bucketNumber
; index
< bucketNumber
+ 1 + extent
; ++index
) {
1805 Q_ASSERT(bucketPtr
->isEmpty());
1806 Q_ASSERT(!bucketPtr
->monsterBucketExtent());
1807 Q_ASSERT(m_freeSpaceBuckets
.indexOf(index
) == -1);
1810 for(uint index
= bucketNumber
; index
< bucketNumber
+ 1 + extent
; ++index
)
1811 deleteBucket(index
);
1813 m_fastBuckets
[bucketNumber
] = new Bucket
<Item
, ItemRequest
, DynamicData
>();
1815 m_fastBuckets
[bucketNumber
]->initialize(extent
);
1817 #ifdef DEBUG_MONSTERBUCKETS
1819 for(uint index
= bucketNumber
+1; index
< bucketNumber
+ 1 + extent
; ++index
) {
1820 Q_ASSERT(!m_fastBuckets
[index
]);
1825 Q_ASSERT(bucketPtr
->monsterBucketExtent());
1826 Q_ASSERT(bucketPtr
->isEmpty());
1827 uint oldExtent
= bucketPtr
->monsterBucketExtent();
1828 deleteBucket(bucketNumber
); //Delete the monster-bucket
1830 for(uint index
= bucketNumber
; index
< bucketNumber
+ 1 + oldExtent
; ++index
) {
1831 Q_ASSERT(!m_fastBuckets
[index
]);
1832 m_fastBuckets
[index
] = new Bucket
<Item
, ItemRequest
, DynamicData
>();
1834 m_fastBuckets
[index
]->initialize(0);
1835 Q_ASSERT(!m_fastBuckets
[index
]->monsterBucketExtent());
1838 return m_fastBuckets
[bucketNumber
];
1841 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketForIndex(short unsigned int index
) const {
1842 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[index
];
1844 initializeBucket(index
);
1845 bucketPtr
= m_fastBuckets
[index
];
1850 virtual bool open(const QString
& path
) {
1852 m_currentOpenPath
= path
;
1853 //kDebug() << "opening repository" << m_repositoryName << "at" << path;
1855 m_file
= new QFile(dir
.absoluteFilePath( m_repositoryName
));
1856 m_dynamicFile
= new QFile(dir
.absoluteFilePath( m_repositoryName
+ "_dynamic" ));
1857 if(!m_file
->open( QFile::ReadWrite
) || !m_dynamicFile
->open( QFile::ReadWrite
) ) {
1860 delete m_dynamicFile
;
1865 m_metaDataChanged
= true;
1866 if(m_file
->size() == 0) {
1869 m_file
->write((char*)&m_repositoryVersion
, sizeof(uint
));
1870 uint hashSize
= bucketHashSize
;
1871 m_file
->write((char*)&hashSize
, sizeof(uint
));
1872 uint itemRepositoryVersion
= staticItemRepositoryVersion();
1873 m_file
->write((char*)&itemRepositoryVersion
, sizeof(uint
));
1875 m_statBucketHashClashes
= m_statItemCount
= 0;
1877 m_file
->write((char*)&m_statBucketHashClashes
, sizeof(uint
));
1878 m_file
->write((char*)&m_statItemCount
, sizeof(uint
));
1880 m_buckets
.resize(10);
1882 uint bucketCount
= m_buckets
.size();
1883 m_file
->write((char*)&bucketCount
, sizeof(uint
));
1885 m_firstBucketForHash
= new short unsigned int[bucketHashSize
];
1886 memset(m_firstBucketForHash
, 0, bucketHashSize
* sizeof(short unsigned int));
1888 m_currentBucket
= 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes
1889 m_file
->write((char*)&m_currentBucket
, sizeof(uint
));
1890 m_file
->write((char*)m_firstBucketForHash
, sizeof(short unsigned int) * bucketHashSize
);
1891 //We have completely initialized the file now
1892 Q_ASSERT(m_file
->pos() == BucketStartOffset
);
1894 m_freeSpaceBucketsSize
= 0;
1895 m_dynamicFile
->write((char*)&m_freeSpaceBucketsSize
, sizeof(uint
));
1896 m_freeSpaceBuckets
.clear();
1898 //Check that the version is correct
1899 uint storedVersion
= 0, hashSize
= 0, itemRepositoryVersion
= 0;
1901 m_file
->read((char*)&storedVersion
, sizeof(uint
));
1902 m_file
->read((char*)&hashSize
, sizeof(uint
));
1903 m_file
->read((char*)&itemRepositoryVersion
, sizeof(uint
));
1904 m_file
->read((char*)&m_statBucketHashClashes
, sizeof(uint
));
1905 m_file
->read((char*)&m_statItemCount
, sizeof(uint
));
1907 if(storedVersion
!= m_repositoryVersion
|| hashSize
!= bucketHashSize
|| itemRepositoryVersion
!= staticItemRepositoryVersion()) {
1908 kDebug() << "repository" << m_repositoryName
<< "version mismatch in" << m_file
->fileName() << ", stored: version " << storedVersion
<< "hashsize" << hashSize
<< "repository-version" << itemRepositoryVersion
<< " current: version" << m_repositoryVersion
<< "hashsize" << bucketHashSize
<< "repository-version" << staticItemRepositoryVersion();
1911 delete m_dynamicFile
;
1915 m_metaDataChanged
= false;
1918 m_file
->read((char*)&bucketCount
, sizeof(uint
));
1919 m_buckets
.resize(bucketCount
);
1921 m_file
->read((char*)&m_currentBucket
, sizeof(uint
));
1923 m_firstBucketForHash
= new short unsigned int[bucketHashSize
];
1924 m_file
->read((char*)m_firstBucketForHash
, sizeof(short unsigned int) * bucketHashSize
);
1926 Q_ASSERT(m_file
->pos() == BucketStartOffset
);
1928 m_dynamicFile
->read((char*)&m_freeSpaceBucketsSize
, sizeof(uint
));
1929 m_freeSpaceBuckets
.resize(m_freeSpaceBucketsSize
);
1930 m_dynamicFile
->read((char*)m_freeSpaceBuckets
.data(), sizeof(uint
) * m_freeSpaceBucketsSize
);
1933 //To protect us from inconsistency due to crashes. flush() is not enough.
1935 m_dynamicFile
->close();
1937 m_fastBuckets
= m_buckets
.data();
1938 m_bucketCount
= m_buckets
.size();
1942 ///@warning by default, this does not store the current state to disk.
1943 virtual void close(bool doStore
= false) {
1944 if(!m_currentOpenPath
.isEmpty()) {
1946 m_currentOpenPath
= QString();
1957 m_dynamicFile
->close();
1958 delete m_dynamicFile
;
1961 delete[] m_firstBucketForHash
;
1964 m_firstBucketForHash
= 0;
1967 struct AllItemsReachableVisitor
{
1968 AllItemsReachableVisitor(ItemRepository
* rep
) : repository(rep
) {
1971 bool operator()(const Item
* item
) {
1972 return repository
->itemReachable(item
);
1975 ItemRepository
* repository
;
1978 //Returns whether the given item is reachable through its hash
1979 bool itemReachable(const Item
* item
) const {
1980 uint hash
= item
->hash();
1982 short unsigned int bucket
= *(m_firstBucketForHash
+ (hash
% bucketHashSize
));
1986 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= m_fastBuckets
[bucket
];
1988 initializeBucket(bucket
);
1989 bucketPtr
= m_fastBuckets
[bucket
];
1992 if(bucketPtr
->itemReachable(item
, hash
))
1995 bucket
= bucketPtr
->nextBucketForHash(hash
);
2001 //Returns true if all items in the given bucket are reachable through their hashes
2002 bool allItemsReachable(unsigned short bucket
) {
2006 Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
= bucketForIndex(bucket
);
2008 AllItemsReachableVisitor
visitor(this);
2009 return bucketPtr
->visitAllItems(visitor
);
2012 inline void initializeBucket(unsigned int bucketNumber
) const {
2013 Q_ASSERT(bucketNumber
);
2014 #ifdef DEBUG_MONSTERBUCKETS
2015 for(int offset
= 1; offset
< 5; ++offset
) {
2016 int test
= ((int)bucketNumber
) - offset
;
2017 if(test
>= 0 && m_fastBuckets
[test
]) {
2018 Q_ASSERT(m_fastBuckets
[test
]->monsterBucketExtent() < offset
);
2023 if(!m_fastBuckets
[bucketNumber
]) {
2024 m_fastBuckets
[bucketNumber
] = new Bucket
<Item
, ItemRequest
, DynamicData
>();
2026 if(m_file
->open( QFile::ReadOnly
)) {
2027 m_fastBuckets
[bucketNumber
]->initialize(m_file
, BucketStartOffset
+ (bucketNumber
-1) * Bucket
<Item
, ItemRequest
, DynamicData
>::DataSize
);
2030 kWarning() << "cannot open repository-file for reading";
2033 m_fastBuckets
[bucketNumber
]->initialize(0);
2037 ///Can only be called on empty buckets
2038 void deleteBucket(unsigned int bucketNumber
) {
2039 Q_ASSERT(bucketForIndex(bucketNumber
)->isEmpty());
2040 Q_ASSERT(bucketForIndex(bucketNumber
)->noNextBuckets());
2041 delete m_fastBuckets
[bucketNumber
];
2042 m_fastBuckets
[bucketNumber
] = 0;
2045 //m_file must be opened
2046 void storeBucket(unsigned int bucketNumber
) const {
2047 if(m_file
&& m_fastBuckets
[bucketNumber
]) {
2048 m_fastBuckets
[bucketNumber
]->store(m_file
, BucketStartOffset
+ (bucketNumber
-1) * Bucket
<Item
, ItemRequest
, DynamicData
>::DataSize
);
2052 ///Returns whether @param mustFindBucket was found
2053 ///If mustFindBucket is zero, the whole chain is just walked. This is good for debugging for infinite recursion.
2054 bool walkBucketLinks(uint checkBucket
, uint hash
, uint mustFindBucket
= 0) const {
2056 while(checkBucket
) {
2057 if(checkBucket
== mustFindBucket
)
2060 checkBucket
= bucketForIndex(checkBucket
)->nextBucketForHash(hash
);
2062 return found
|| (mustFindBucket
== 0);
2065 ///Computes the bucket where the chains opened by the buckets @param mainHead and @param intersectorHead
2066 ///with hash @param hash meet each other.
2067 ///@return <predecessor of first shared bucket in mainHead, first shared bucket>
2068 QPair
<unsigned int, unsigned int> hashChainIntersection(uint mainHead
, uint intersectorHead
, uint hash
) const {
2070 uint current
= mainHead
;
2072 ///@todo Make this more efficient
2073 if(walkBucketLinks(intersectorHead
, hash
, current
))
2074 return qMakePair(previous
, current
);
2077 current
= bucketForIndex(current
)->nextBucketForHash(hash
);
2079 return qMakePair(0u, 0u);
2082 void putIntoFreeList(unsigned short bucket
, Bucket
<Item
, ItemRequest
, DynamicData
>* bucketPtr
) {
2083 Q_ASSERT(!bucketPtr
->monsterBucketExtent());
2084 int indexInFree
= m_freeSpaceBuckets
.indexOf(bucket
);
2086 if(indexInFree
== -1 && (bucketPtr
->freeItemCount() >= Bucket
<Item
, ItemRequest
, DynamicData
>::MinFreeItemsForReuse
|| bucketPtr
->largestFreeSize() >= Bucket
<Item
, ItemRequest
, DynamicData
>::MinFreeSizeForReuse
)) {
2088 //Add the bucket to the list of buckets from where to re-assign free space
2089 //We only do it when a specific threshold of empty items is reached, because that way items can stay "somewhat" semantically ordered.
2090 Q_ASSERT(bucketPtr
->largestFreeSize());
2092 for(insertPos
= 0; insertPos
< m_freeSpaceBucketsSize
; ++insertPos
) {
2093 if(bucketForIndex(m_freeSpaceBuckets
[insertPos
])->largestFreeSize() > bucketPtr
->largestFreeSize())
2097 m_freeSpaceBuckets
.insert(insertPos
, bucket
);
2098 ++m_freeSpaceBucketsSize
;
2099 updateFreeSpaceOrder(insertPos
);
2100 }else if(indexInFree
!= -1) {
2101 ///Re-order so the order in m_freeSpaceBuckets is correct(sorted by largest free item size)
2102 updateFreeSpaceOrder(indexInFree
);
2104 #ifdef DEBUG_MONSTERBUCKETS
2105 if(bucketPtr
->isEmpty()) {
2106 Q_ASSERT(m_freeSpaceBuckets
.contains(bucket
));
2111 bool m_metaDataChanged
;
2112 mutable QMutex m_mutex
;
2113 QString m_repositoryName
;
2114 unsigned int m_size
;
2115 mutable uint m_currentBucket
;
2116 //List of buckets that have free space available that can be assigned. Sorted by size: Smallest space first. Second order sorting: Bucket index
2117 QVector
<uint
> m_freeSpaceBuckets
;
2118 uint m_freeSpaceBucketsSize
; //for speedup
2119 mutable QVector
<Bucket
<Item
, ItemRequest
, DynamicData
>* > m_buckets
;
2120 mutable Bucket
<Item
, ItemRequest
, DynamicData
>** m_fastBuckets
; //For faster access
2121 mutable uint m_bucketCount
;
2122 uint m_statBucketHashClashes
, m_statItemCount
;
2123 unsigned int m_bucketHashSize
;
2124 //Maps hash-values modulo 1<<bucketHashSizeBits to the first bucket such a hash-value appears in
2125 short unsigned int* m_firstBucketForHash
;
2127 QString m_currentOpenPath
;
2128 ItemRepositoryRegistry
* m_registry
;
2129 //File that contains the buckets
2131 //File that contains more dynamic data, like the list of buckets with deleted items
2132 QFile
* m_dynamicFile
;
2133 uint m_repositoryVersion
;
2134 bool m_unloadingEnabled
;