• Skip to content
  • Skip to link menu
KDE API Reference
  • KDE API Reference
  • kdevelop API Reference
  • KDE Home
  • Contact Us
 

kdevplatform/serialization

  • sources
  • kfour-appscomplete
  • kdevelop
  • kdevplatform
  • serialization
itemrepository.h
Go to the documentation of this file.
1 /*
2  Copyright 2008 David Nolden <[email protected]>
3 
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.
7 
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.
12 
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.
17  */
18 
19 #ifndef KDEVPLATFORM_ITEMREPOSITORY_H
20 #define KDEVPLATFORM_ITEMREPOSITORY_H
21 
22 #include <QDebug>
23 #include <QDir>
24 #include <QFile>
25 
26 #include <KMessageBox>
27 #include <KLocalizedString>
28 
29 #include "referencecounting.h"
30 #include "abstractitemrepository.h"
31 #include "repositorymanager.h"
32 #include "itemrepositoryregistry.h"
33 
34 //#define DEBUG_MONSTERBUCKETS
35 
36 // #define DEBUG_ITEMREPOSITORY_LOADING
37 // #define ifDebugInfiniteRecursion(x) x
38 #define ifDebugInfiniteRecursion(x)
39 
40 // #define ifDebugLostSpace(x) x
41 #define ifDebugLostSpace(x)
42 // #define DEBUG_INCORRECT_DELETE
43 
44 //Makes sure that all items stay reachable through the basic hash
45 // #define DEBUG_ITEM_REACHABILITY
46 
48 
49 #ifdef DEBUG_ITEM_REACHABILITY
50 #define ENSURE_REACHABLE(bucket) Q_ASSERT(allItemsReachable(bucket));
51 #define IF_ENSURE_REACHABLE(x) x
52 #else
53 #define ENSURE_REACHABLE(bucket)
54 #define IF_ENSURE_REACHABLE(x)
55 #endif
56 
57 #define ITEMREPOSITORY_USE_MMAP_LOADING
58 
59 //Assertion macro that prevents warnings if debugging is disabled
60 //Only use it to verify values, it should not call any functions, since else the function will even be called in release mode
61 #ifdef QT_NO_DEBUG
62 #define VERIFY(X) if (!(X)) {qWarning() << "Failed to verify expression" << # X;}
63 #else
64 #define VERIFY(X) Q_ASSERT(X)
65 #endif
66 
71 // #define DEBUG_WRITING_EXTENTS
72 
73 class TestItemRepository;
74 
75 namespace KDevelop {
96 enum {
97  ItemRepositoryBucketSize = 1 << 16,
98  ItemRepositoryBucketLimit = 1 << 16
99 };
100 
108 template <class Item, class ItemRequest, bool markForReferenceCounting, uint fixedItemSize>
109 class Bucket
110 {
111 public:
112  enum {
113  AdditionalSpacePerItem = 2
114  };
115  enum {
116  ObjectMapSize = ((ItemRepositoryBucketSize / ItemRequest::AverageSize) * 3) / 2 + 1,
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
121  };
122  enum {
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) *
125  (ObjectMapSize + NextBucketHashSize + 1)
126  };
127  enum {
128  CheckStart = 0xff00ff1,
129  CheckEnd = 0xfafcfb
130  };
131  Bucket()
132  {
133  }
134  ~Bucket()
135  {
136  if (m_data != m_mappedData) {
137  delete[] m_data;
138  delete[] m_nextBucketHash;
139  delete[] m_objectMap;
140  }
141  }
142 
143  void initialize(int monsterBucketExtent)
144  {
145  if (!m_data) {
146  m_monsterBucketExtent = monsterBucketExtent;
147  m_available = ItemRepositoryBucketSize;
148  m_data = new char[ItemRepositoryBucketSize + monsterBucketExtent * DataSize];
149 #ifndef QT_NO_DEBUG
150  memset(m_data, 0, (ItemRepositoryBucketSize + monsterBucketExtent * DataSize) * sizeof(char));
151 #endif
152  //The bigger we make the map, the lower the probability of a clash(and thus bad performance). However it increases memory usage.
153  m_objectMap = new short unsigned int[ObjectMapSize];
154  memset(m_objectMap, 0, ObjectMapSize * sizeof(short unsigned int));
155  m_nextBucketHash = new short unsigned int[NextBucketHashSize];
156  memset(m_nextBucketHash, 0, NextBucketHashSize * sizeof(short unsigned int));
157  m_changed = true;
158  m_dirty = false;
159  m_lastUsed = 0;
160  }
161  }
162 
163  template <class T>
164  void readValue(char*& from, T& to)
165  {
166  to = *reinterpret_cast<T*>(from);
167  from += sizeof(T);
168  }
169 
170  void initializeFromMap(char* current)
171  {
172  if (!m_data) {
173  char* start = current;
174  readValue(current, m_monsterBucketExtent);
175  Q_ASSERT(current - start == 4);
176  readValue(current, m_available);
177  m_objectMap = reinterpret_cast<short unsigned int*>(current);
178  current += sizeof(short unsigned int) * ObjectMapSize;
179  m_nextBucketHash = reinterpret_cast<short unsigned int*>(current);
180  current += sizeof(short unsigned int) * NextBucketHashSize;
181  readValue(current, m_largestFreeItem);
182  readValue(current, m_freeItemCount);
183  readValue(current, m_dirty);
184  m_data = current;
185  m_mappedData = current;
186 
187  m_changed = false;
188  m_lastUsed = 0;
189  VERIFY(current - start == (DataSize - ItemRepositoryBucketSize));
190  }
191  }
192 
193  void store(QFile* file, size_t offset)
194  {
195  if (!m_data)
196  return;
197 
198  if (static_cast<size_t>(file->size()) < offset + (1 + m_monsterBucketExtent) * DataSize)
199  file->resize(offset + (1 + m_monsterBucketExtent) * DataSize);
200 
201  file->seek(offset);
202 
203  file->write(reinterpret_cast<const char*>(&m_monsterBucketExtent), sizeof(unsigned int));
204  file->write(reinterpret_cast<const char*>(&m_available), sizeof(unsigned int));
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);
207  file->write(reinterpret_cast<const char*>(&m_largestFreeItem), sizeof(short unsigned int));
208  file->write(reinterpret_cast<const char*>(&m_freeItemCount), sizeof(unsigned int));
209  file->write(reinterpret_cast<const char*>(&m_dirty), sizeof(bool));
210  file->write(m_data, ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize);
211 
212  if (static_cast<size_t>(file->pos()) != offset + (1 + m_monsterBucketExtent) * DataSize) {
213  KMessageBox::error(nullptr, i18n("Failed writing to %1, probably the disk is full", file->fileName()));
214  abort();
215  }
216 
217  m_changed = false;
218 #ifdef DEBUG_ITEMREPOSITORY_LOADING
219  {
220  file->flush();
221  file->seek(offset);
222 
223  uint available, freeItemCount, monsterBucketExtent;
224  short unsigned int largestFree;
225  bool dirty;
226 
227  short unsigned int* m = new short unsigned int[ObjectMapSize];
228  short unsigned int* h = new short unsigned int[NextBucketHashSize];
229 
230  file->read(reinterpret_cast<char*>(&monsterBucketExtent), sizeof(unsigned int));
231  char* d = new char[ItemRepositoryBucketSize + monsterBucketExtent * DataSize];
232 
233  file->read(reinterpret_cast<char*>(&available), sizeof(unsigned int));
234  file->read(reinterpret_cast<char*>(m), sizeof(short unsigned int) * ObjectMapSize);
235  file->read(reinterpret_cast<char*>(h), sizeof(short unsigned int) * NextBucketHashSize);
236  file->read(reinterpret_cast<char*>(&largestFree), sizeof(short unsigned int));
237  file->read(reinterpret_cast<char*>(&freeItemCount), sizeof(unsigned int));
238  file->read(reinterpret_cast<char*>(&dirty), sizeof(bool));
239  file->read(d, ItemRepositoryBucketSize);
240 
241  Q_ASSERT(monsterBucketExtent == m_monsterBucketExtent);
242  Q_ASSERT(available == m_available);
243  Q_ASSERT(memcmp(d, m_data, ItemRepositoryBucketSize + monsterBucketExtent * DataSize) == 0);
244  Q_ASSERT(memcmp(m, m_objectMap, sizeof(short unsigned int) * ObjectMapSize) == 0);
245  Q_ASSERT(memcmp(h, m_nextBucketHash, sizeof(short unsigned int) * NextBucketHashSize) == 0);
246  Q_ASSERT(m_largestFreeItem == largestFree);
247  Q_ASSERT(m_freeItemCount == freeItemCount);
248  Q_ASSERT(m_dirty == dirty);
249 
250  Q_ASSERT(static_cast<size_t>(file->pos()) == offset + DataSize + m_monsterBucketExtent * DataSize);
251 
252  delete[] d;
253  delete[] m;
254  delete[] h;
255  }
256 #endif
257  }
258 
259  inline char* data()
260  {
261  return m_data;
262  }
263 
264  inline uint dataSize() const
265  {
266  return ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize;
267  }
268 
269  //Tries to find the index this item has in this bucket, or returns zero if the item isn't there yet.
270  unsigned short findIndex(const ItemRequest& request) const
271  {
272  m_lastUsed = 0;
273 
274  unsigned short localHash = request.hash() % ObjectMapSize;
275  unsigned short index = m_objectMap[localHash];
276 
277  unsigned short follower = 0;
278  //Walk the chain of items with the same local hash
279  while (index && (follower = followerIndex(index)) && !(request.equals(itemFromIndex(index))))
280  index = follower;
281 
282  if (index && request.equals(itemFromIndex(index))) {
283  return index; //We have found the item
284  }
285 
286  return 0;
287  }
288 
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.
291  unsigned short index(const ItemRequest& request, unsigned int itemSize)
292  {
293  m_lastUsed = 0;
294 
295  unsigned short localHash = request.hash() % ObjectMapSize;
296  unsigned short index = m_objectMap[localHash];
297  unsigned short insertedAt = 0;
298 
299  const auto createInsertedItem = [&]() {
300  const OptionalDUChainReferenceCountingEnabler<markForReferenceCounting> optionalRc(m_data, dataSize());
301  request.createItem(reinterpret_cast<Item*>(m_data + insertedAt));
302  };
303 
304  unsigned short follower = 0;
305  //Walk the chain of items with the same local hash
306  while (index && (follower = followerIndex(index)) && !(request.equals(itemFromIndex(index))))
307  index = follower;
308 
309  if (index && request.equals(itemFromIndex(index)))
310  return index; //We have found the item
311 
312  ifDebugLostSpace(Q_ASSERT(!lostSpace()); )
313 
314  prepareChange();
315 
316  unsigned int totalSize = itemSize + AdditionalSpacePerItem;
317 
318  if (m_monsterBucketExtent) {
320  Q_ASSERT(totalSize > ItemRepositoryBucketSize);
321  Q_ASSERT(m_available);
322  m_available = 0;
323 
324  insertedAt = AdditionalSpacePerItem;
325  setFollowerIndex(insertedAt, 0);
326  Q_ASSERT(m_objectMap[localHash] == 0);
327  m_objectMap[localHash] = insertedAt;
328  createInsertedItem();
329  return insertedAt;
330  }
331 
332  //The second condition is needed, else we can get problems with zero-length items and an overflow in insertedAt to zero
333  if (totalSize > m_available || (!itemSize && totalSize == m_available)) {
334  //Try finding the smallest freed item that can hold the data
335  unsigned short currentIndex = m_largestFreeItem;
336  unsigned short previousIndex = 0;
337 
338  unsigned short freeChunkSize = 0;
339 
341  while (currentIndex && freeSize(currentIndex) > itemSize) {
342  unsigned short follower = followerIndex(currentIndex);
343  if (follower && freeSize(follower) >= itemSize) {
344  //The item also fits into the smaller follower, so use that one
345  previousIndex = currentIndex;
346  currentIndex = follower;
347  } else {
348  //The item fits into currentIndex, but not into the follower. So use currentIndex
349  freeChunkSize = freeSize(currentIndex) - itemSize;
350 
351  //We need 2 bytes to store the free size
352  if (freeChunkSize != 0 && freeChunkSize < AdditionalSpacePerItem + 2) {
353  //we can not manage the resulting free chunk as a separate item, so we cannot use this position.
354  //Just pick the biggest free item, because there we can be sure that
355  //either we can manage the split, or we cannot do anything at all in this bucket.
356 
357  freeChunkSize = freeSize(m_largestFreeItem) - itemSize;
358 
359  if (freeChunkSize == 0 || freeChunkSize >= AdditionalSpacePerItem + 2) {
360  previousIndex = 0;
361  currentIndex = m_largestFreeItem;
362  } else {
363  currentIndex = 0;
364  }
365  }
366  break;
367  }
368  }
369 
370  if (!currentIndex || freeSize(currentIndex) < (totalSize - AdditionalSpacePerItem))
371  return 0;
372 
373  if (previousIndex)
374  setFollowerIndex(previousIndex, followerIndex(currentIndex));
375  else
376  m_largestFreeItem = followerIndex(currentIndex);
377 
378  --m_freeItemCount; //Took one free item out of the chain
379 
380  ifDebugLostSpace(Q_ASSERT(( uint )lostSpace() == ( uint )(freeSize(currentIndex) + AdditionalSpacePerItem));
381  )
382 
383  if (freeChunkSize) {
384  Q_ASSERT(freeChunkSize >= AdditionalSpacePerItem + 2);
385  unsigned short freeItemSize = freeChunkSize - AdditionalSpacePerItem;
386 
387  unsigned short freeItemPosition;
388  //Insert the resulting free chunk into the list of free items, so we don't lose it
389  if (isBehindFreeSpace(currentIndex)) {
390  //Create the free item at the beginning of currentIndex, so it can be merged with the free space in front
391  freeItemPosition = currentIndex;
392  currentIndex += freeItemSize + AdditionalSpacePerItem;
393  } else {
394  //Create the free item behind currentIndex
395  freeItemPosition = currentIndex + itemSize + AdditionalSpacePerItem;
396  }
397  setFreeSize(freeItemPosition, freeItemSize);
398  insertFreeItem(freeItemPosition);
399  }
400 
401  insertedAt = currentIndex;
402  Q_ASSERT(( bool )m_freeItemCount == ( bool )m_largestFreeItem);
403  } else {
404  //We have to insert the item
405  insertedAt = ItemRepositoryBucketSize - m_available;
406 
407  insertedAt += AdditionalSpacePerItem; //Room for the prepended follower-index
408 
409  m_available -= totalSize;
410  }
411 
412  ifDebugLostSpace(Q_ASSERT(lostSpace() == totalSize); )
413 
414  Q_ASSERT(!index || !followerIndex(index));
415 
416  Q_ASSERT(!m_objectMap[localHash] || index);
417 
418  if (index)
419  setFollowerIndex(index, insertedAt);
420  setFollowerIndex(insertedAt, 0);
421 
422  if (m_objectMap[localHash] == 0)
423  m_objectMap[localHash] = insertedAt;
424 
425 #ifdef DEBUG_CREATEITEM_EXTENTS
426  char* borderBehind = m_data + insertedAt + (totalSize - AdditionalSpacePerItem);
427 
428  quint64 oldValueBehind = 0;
429  if (m_available >= 8) {
430  oldValueBehind = *( quint64* )borderBehind;
431  *(( quint64* )borderBehind) = 0xfafafafafafafafaLLU;
432  }
433 #endif
434 
435  //Last thing we do, because createItem may recursively do even more transformation of the repository
436  createInsertedItem();
437 
438 #ifdef DEBUG_CREATEITEM_EXTENTS
439  if (m_available >= 8) {
440  //If this assertion triggers, then the item writes a bigger range than it advertised in
441  Q_ASSERT(*(( quint64* )borderBehind) == 0xfafafafafafafafaLLU);
442  *(( quint64* )borderBehind) = oldValueBehind;
443  }
444 #endif
445 
446  Q_ASSERT(itemFromIndex(insertedAt)->hash() == request.hash());
447  Q_ASSERT(itemFromIndex(insertedAt)->itemSize() == itemSize);
448 
449  ifDebugLostSpace(if (lostSpace()) qDebug() << "lost space:" << lostSpace(); Q_ASSERT(!lostSpace()); )
450 
451  return insertedAt;
452  }
453 
458  bool hasClashingItem(uint hash, uint modulo)
459  {
460  Q_ASSERT(modulo % ObjectMapSize == 0);
461 
462  m_lastUsed = 0;
463 
464  uint hashMod = hash % modulo;
465  unsigned short localHash = hash % ObjectMapSize;
466  unsigned short currentIndex = m_objectMap[localHash];
467 
468  if (currentIndex == 0)
469  return false;
470 
471  while (currentIndex) {
472  uint currentHash = itemFromIndex(currentIndex)->hash();
473 
474  Q_ASSERT(currentHash % ObjectMapSize == localHash);
475 
476  if (currentHash % modulo == hashMod)
477  return true; //Clash
478  currentIndex = followerIndex(currentIndex);
479  }
480  return false;
481  }
482 
483  void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, uint& longestInBucketFollowerChain)
484  {
485  for (uint a = 0; a < ObjectMapSize; ++a) {
486  unsigned short currentIndex = m_objectMap[a];
487  ++slotCount;
488  uint length = 0;
489 
490  if (currentIndex) {
491  ++usedSlots;
492 
493  while (currentIndex) {
494  ++length;
495  ++lengths;
496  currentIndex = followerIndex(currentIndex);
497  }
498  if (length > longestInBucketFollowerChain) {
499 // qDebug() << "follower-chain at" << a << ":" << length;
500 
501  longestInBucketFollowerChain = length;
502  }
503  }
504  }
505  }
506 
507  //Returns whether the given item is reachabe within this bucket, through its hash.
508  bool itemReachable(const Item* item, uint hash) const
509  {
510  unsigned short localHash = hash % ObjectMapSize;
511  unsigned short currentIndex = m_objectMap[localHash];
512 
513  while (currentIndex) {
514  if (itemFromIndex(currentIndex) == item)
515  return true;
516 
517  currentIndex = followerIndex(currentIndex);
518  }
519  return false;
520  }
521 
522  template <class Repository>
523  void deleteItem(unsigned short index, unsigned int hash, Repository& repository)
524  {
525  ifDebugLostSpace(Q_ASSERT(!lostSpace()); )
526 
527  m_lastUsed = 0;
528  prepareChange();
529 
530  unsigned int size = itemFromIndex(index)->itemSize();
531  //Step 1: Remove the item from the data-structures that allow finding it: m_objectMap
532  unsigned short localHash = hash % ObjectMapSize;
533  unsigned short currentIndex = m_objectMap[localHash];
534  unsigned short previousIndex = 0;
535 
536  //Fix the follower-link by setting the follower of the previous item to the next one, or updating m_objectMap
537  while (currentIndex != index) {
538  previousIndex = currentIndex;
539  currentIndex = followerIndex(currentIndex);
540  //If this assertion triggers, the deleted item was not registered under the given hash
541  Q_ASSERT(currentIndex);
542  }
543  Q_ASSERT(currentIndex == index);
544 
545  if (!previousIndex)
546  //The item was directly in the object map
547  m_objectMap[localHash] = followerIndex(index);
548  else
549  setFollowerIndex(previousIndex, followerIndex(index));
550 
551  Item* item = const_cast<Item*>(itemFromIndex(index));
552 
553  {
554  const OptionalDUChainReferenceCountingEnabler<markForReferenceCounting> optionalRc(m_data, dataSize());
555  ItemRequest::destroy(item, repository);
556  }
557 
558 #ifndef QT_NO_DEBUG
559 #if defined(__GNUC__) && !defined(__INTEL_COMPILER) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 800)
560 #pragma GCC diagnostic push
561 #pragma GCC diagnostic ignored "-Wclass-memaccess"
562 #endif
563  memset(item, 0, size); //For debugging, so we notice the data is wrong
564 #if defined(__GNUC__) && !defined(__INTEL_COMPILER) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 800)
565 #pragma GCC diagnostic pop
566 #endif
567 #endif
568 
569  if (m_monsterBucketExtent) {
571  Q_ASSERT(!m_available);
572  m_available = ItemRepositoryBucketSize;
573 
574  //Items are always inserted into monster-buckets at a fixed position
575  Q_ASSERT(currentIndex == AdditionalSpacePerItem);
576  Q_ASSERT(m_objectMap[localHash] == 0);
577  } else {
579  setFreeSize(index, size);
580 
581  //Try merging the created free item to other free items around, else add it into the free list
582  insertFreeItem(index);
583 
584  if (m_freeItemCount == 1 && freeSize(m_largestFreeItem) + m_available == ItemRepositoryBucketSize) {
585  //Everything has been deleted, there is only free space left. Make the bucket empty again,
586  //so it can later also be used as a monster-bucket.
587  m_available = ItemRepositoryBucketSize;
588  m_freeItemCount = 0;
589  m_largestFreeItem = 0;
590  }
591  }
592 
593  Q_ASSERT(( bool )m_freeItemCount == ( bool )m_largestFreeItem);
594  ifDebugLostSpace(Q_ASSERT(!lostSpace()); )
595 #ifdef DEBUG_INCORRECT_DELETE
596  //Make sure the item cannot be found any more
597  {
598  unsigned short localHash = hash % ObjectMapSize;
599  unsigned short currentIndex = m_objectMap[localHash];
600 
601  while (currentIndex && currentIndex != index) {
602  previousIndex = currentIndex;
603  currentIndex = followerIndex(currentIndex);
604  }
605  Q_ASSERT(!currentIndex); //The item must not be found
606  }
607 #endif
608 // Q_ASSERT(canAllocateItem(size));
609  }
610 
614  inline const Item* itemFromIndex(unsigned short index) const
615  {
616  m_lastUsed = 0;
617  return reinterpret_cast<Item*>(m_data + index);
618  }
619 
620  bool isEmpty() const
621  {
622  return m_available == ItemRepositoryBucketSize;
623  }
624 
626  bool noNextBuckets() const
627  {
628  for (int a = 0; a < NextBucketHashSize; ++a)
629  if (m_nextBucketHash[a])
630  return false;
631 
632  return true;
633  }
634 
635  uint available() const
636  {
637  return m_available;
638  }
639 
640  uint usedMemory() const
641  {
642  return ItemRepositoryBucketSize - m_available;
643  }
644 
645  template <class Visitor>
646  bool visitAllItems(Visitor& visitor) const
647  {
648  m_lastUsed = 0;
649  for (uint a = 0; a < ObjectMapSize; ++a) {
650  uint currentIndex = m_objectMap[a];
651  while (currentIndex) {
652  //Get the follower early, so there is no problems when the current
653  //index is removed
654 
655  if (!visitor(reinterpret_cast<const Item*>(m_data + currentIndex)))
656  return false;
657 
658  currentIndex = followerIndex(currentIndex);
659  }
660  }
661 
662  return true;
663  }
664 
666  template <class Repository>
667  int finalCleanup(Repository& repository)
668  {
669  int changed = 0;
670 
671  while (m_dirty) {
672  m_dirty = false;
673 
674  for (uint a = 0; a < ObjectMapSize; ++a) {
675  uint currentIndex = m_objectMap[a];
676  while (currentIndex) {
677  //Get the follower early, so there is no problems when the current
678  //index is removed
679 
680  const Item* item = reinterpret_cast<const Item*>(m_data + currentIndex);
681 
682  if (!ItemRequest::persistent(item)) {
683  changed += item->itemSize();
684  deleteItem(currentIndex, item->hash(), repository);
685  m_dirty = true; //Set to dirty so we re-iterate
686  break;
687  }
688 
689  currentIndex = followerIndex(currentIndex);
690  }
691  }
692  }
693  return changed;
694  }
695 
696  unsigned short nextBucketForHash(uint hash) const
697  {
698  m_lastUsed = 0;
699  return m_nextBucketHash[hash % NextBucketHashSize];
700  }
701 
702  void setNextBucketForHash(unsigned int hash, unsigned short bucket)
703  {
704  m_lastUsed = 0;
705  prepareChange();
706  m_nextBucketHash[hash % NextBucketHashSize] = bucket;
707  }
708 
709  uint freeItemCount() const
710  {
711  return m_freeItemCount;
712  }
713 
714  short unsigned int totalFreeItemsSize() const
715  {
716  short unsigned int ret = 0;
717  short unsigned int currentIndex = m_largestFreeItem;
718  while (currentIndex) {
719  ret += freeSize(currentIndex);
720  currentIndex = followerIndex(currentIndex);
721  }
722  return ret;
723  }
724 
725  //Size of the largest item that could be inserted into this bucket
726  short unsigned int largestFreeSize() const
727  {
728  short unsigned int ret = 0;
729  if (m_largestFreeItem)
730  ret = freeSize(m_largestFreeItem);
731  if (m_available > ( uint )(AdditionalSpacePerItem + ( uint )ret)) {
732  ret = m_available - AdditionalSpacePerItem;
733  Q_ASSERT(ret == (m_available - AdditionalSpacePerItem));
734  }
735  return ret;
736  }
737 
738  bool canAllocateItem(unsigned int size) const
739  {
740  short unsigned int currentIndex = m_largestFreeItem;
741  while (currentIndex) {
742  short unsigned int currentFree = freeSize(currentIndex);
743  if (currentFree < size)
744  return false;
745  //Either we need an exact match, or 2 additional bytes to manage the resulting gap
746  if (size == currentFree || currentFree - size >= AdditionalSpacePerItem + 2)
747  return true;
748  currentIndex = followerIndex(currentIndex);
749  }
750 
751  return false;
752  }
753 
754  void tick() const
755  {
756  ++m_lastUsed;
757  }
758 
759  //How many ticks ago the item was last used
760  int lastUsed() const
761  {
762  return m_lastUsed;
763  }
764 
765  //Whether this bucket was changed since it was last stored
766  bool changed() const
767  {
768  return m_changed;
769  }
770 
771  void prepareChange()
772  {
773  m_changed = true;
774  m_dirty = true;
775  makeDataPrivate();
776  }
777 
778  bool dirty() const
779  {
780  return m_dirty;
781  }
782 
784  int monsterBucketExtent() const
785  {
786  return m_monsterBucketExtent;
787  }
788 
789  //Counts together the space that is neither accessible through m_objectMap nor through the free items
790  uint lostSpace()
791  {
792  if (m_monsterBucketExtent)
793  return 0;
794 
795  uint need = ItemRepositoryBucketSize - m_available;
796  uint found = 0;
797 
798  for (uint a = 0; a < ObjectMapSize; ++a) {
799  uint currentIndex = m_objectMap[a];
800  while (currentIndex) {
801  found += reinterpret_cast<const Item*>(m_data + currentIndex)->itemSize() + AdditionalSpacePerItem;
802 
803  currentIndex = followerIndex(currentIndex);
804  }
805  }
806 
807  uint currentIndex = m_largestFreeItem;
808  while (currentIndex) {
809  found += freeSize(currentIndex) + AdditionalSpacePerItem;
810 
811  currentIndex = followerIndex(currentIndex);
812  }
813  return need - found;
814  }
815 
816 private:
817 
818  void makeDataPrivate()
819  {
820  if (m_mappedData == m_data) {
821  short unsigned int* oldObjectMap = m_objectMap;
822  short unsigned int* oldNextBucketHash = m_nextBucketHash;
823 
824  m_data = new char[ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize];
825  m_objectMap = new short unsigned int[ObjectMapSize];
826  m_nextBucketHash = new short unsigned int[NextBucketHashSize];
827 
828  memcpy(m_data, m_mappedData, ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize);
829  memcpy(m_objectMap, oldObjectMap, ObjectMapSize * sizeof(short unsigned int));
830  memcpy(m_nextBucketHash, oldNextBucketHash, NextBucketHashSize * sizeof(short unsigned int));
831  }
832  }
833 
837  void insertFreeItem(unsigned short index)
838  {
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.
840  if (!fixedItemSize) {
841  unsigned short currentIndex = m_largestFreeItem;
842  unsigned short previousIndex = 0;
843 
844  while (currentIndex) {
845  Q_ASSERT(currentIndex != index);
846 
847 #ifndef QT_NO_DEBUG
848  unsigned short currentFreeSize = freeSize(currentIndex);
849 #endif
850 
852  //Merge behind index
853  if (currentIndex == index + freeSize(index) + AdditionalSpacePerItem) {
854  //Remove currentIndex from the free chain, since it's merged backwards into index
855  if (previousIndex && followerIndex(currentIndex))
856  Q_ASSERT(freeSize(previousIndex) >= freeSize(followerIndex(currentIndex)));
857 
858  if (previousIndex)
859  setFollowerIndex(previousIndex, followerIndex(currentIndex));
860  else
861  m_largestFreeItem = followerIndex(currentIndex);
862 
863  --m_freeItemCount; //One was removed
864 
865  //currentIndex is directly behind index, touching its space. Merge them.
866  setFreeSize(index, freeSize(index) + AdditionalSpacePerItem + freeSize(currentIndex));
867 
868  //Recurse to do even more merging
869  insertFreeItem(index);
870  return;
871  }
872 
873  //Merge before index
874  if (index == currentIndex + freeSize(currentIndex) + AdditionalSpacePerItem) {
875  if (previousIndex && followerIndex(currentIndex))
876  Q_ASSERT(freeSize(previousIndex) >= freeSize(followerIndex(currentIndex)));
877 
878  //Remove currentIndex from the free chain, since insertFreeItem wants
879  //it not to be in the chain, and it will be inserted in another place
880  if (previousIndex)
881  setFollowerIndex(previousIndex, followerIndex(currentIndex));
882  else
883  m_largestFreeItem = followerIndex(currentIndex);
884 
885  --m_freeItemCount; //One was removed
886 
887  //index is directly behind currentIndex, touching its space. Merge them.
888  setFreeSize(currentIndex, freeSize(currentIndex) + AdditionalSpacePerItem + freeSize(index));
889 
890  //Recurse to do even more merging
891  insertFreeItem(currentIndex);
892  return;
893  }
894 
895  previousIndex = currentIndex;
896  currentIndex = followerIndex(currentIndex);
897 #ifndef QT_NO_DEBUG
898  if (currentIndex)
899  Q_ASSERT(freeSize(currentIndex) <= currentFreeSize);
900 #endif
901  }
902  }
903  insertToFreeChain(index);
904  }
905 
907  void insertToFreeChain(unsigned short index)
908  {
909  if (!fixedItemSize) {
911  //Insert the free item into the chain opened by m_largestFreeItem
912  unsigned short currentIndex = m_largestFreeItem;
913  unsigned short previousIndex = 0;
914 
915  unsigned short size = freeSize(index);
916 
917  while (currentIndex && freeSize(currentIndex) > size) {
918  Q_ASSERT(currentIndex != index); //must not be in the chain yet
919  previousIndex = currentIndex;
920  currentIndex = followerIndex(currentIndex);
921  }
922 
923  if (currentIndex)
924  Q_ASSERT(freeSize(currentIndex) <= size);
925 
926  setFollowerIndex(index, currentIndex);
927 
928  if (previousIndex) {
929  Q_ASSERT(freeSize(previousIndex) >= size);
930  setFollowerIndex(previousIndex, index);
931  } else
932  //This item is larger than all already registered free items, or there are none.
933  m_largestFreeItem = index;
934  } else {
935  Q_ASSERT(freeSize(index) == fixedItemSize);
936  //When all items have the same size, just prepent to the front.
937  setFollowerIndex(index, m_largestFreeItem);
938  m_largestFreeItem = index;
939  }
940 
941  ++m_freeItemCount;
942  }
943 
945  bool isBehindFreeSpace(unsigned short index) const
946  {
947  // TODO: Without iteration!
948  unsigned short currentIndex = m_largestFreeItem;
949 
950  while (currentIndex) {
951  if (index == currentIndex + freeSize(currentIndex) + AdditionalSpacePerItem)
952  return true;
953 
954  currentIndex = followerIndex(currentIndex);
955  }
956  return false;
957  }
958 
960  inline unsigned short followerIndex(unsigned short index) const
961  {
962  Q_ASSERT(index >= 2);
963  return *reinterpret_cast<unsigned short*>(m_data + (index - 2));
964  }
965 
966  void setFollowerIndex(unsigned short index, unsigned short follower)
967  {
968  Q_ASSERT(index >= 2);
969  *reinterpret_cast<unsigned short*>(m_data + (index - 2)) = follower;
970  }
971  // Only returns the current value if the item is actually free
972  inline unsigned short freeSize(unsigned short index) const
973  {
974  return *reinterpret_cast<unsigned short*>(m_data + index);
975  }
976 
977  //Convenience function to set the free-size, only for freed items
978  void setFreeSize(unsigned short index, unsigned short size)
979  {
980  *reinterpret_cast<unsigned short*>(m_data + index) = size;
981  }
982 
983 private:
984  Q_DISABLE_COPY(Bucket)
985 
986  int m_monsterBucketExtent = 0; //If this is a monster-bucket, this contains the count of follower-buckets that belong to this one
987  unsigned int m_available = 0;
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
992  unsigned int m_freeItemCount = 0;
993 
994  unsigned short* m_nextBucketHash = nullptr;
995 
996  bool m_dirty = false; //Whether the data was changed since the last finalCleanup
997  bool m_changed = false; //Whether this bucket was changed since it was last stored to disk
998  mutable int m_lastUsed = 0; //How many ticks ago this bucket was last accessed
999 };
1000 
1001 template <bool lock>
1002 struct Locker //This is a dummy that does nothing
1003 {
1004  template <class T>
1005  explicit Locker(const T& /*t*/)
1006  {
1007  }
1008 };
1009 template <>
1010 struct Locker<true>
1011 {
1012  explicit Locker(QMutex* mutex) : m_mutex(mutex)
1013  {
1014  m_mutex->lock();
1015  }
1016  ~Locker()
1017  {
1018  m_mutex->unlock();
1019  }
1020 
1021 private:
1022  Q_DISABLE_COPY(Locker)
1023 
1024  QMutex* m_mutex;
1025 };
1026 
1030 template <class Item, bool markForReferenceCounting>
1031 class DynamicItem : public OptionalDUChainReferenceCountingEnabler<markForReferenceCounting>
1032 {
1033 public:
1034  explicit DynamicItem(Item* i, const void* start, unsigned size)
1035  : OptionalDUChainReferenceCountingEnabler<markForReferenceCounting>(start, size)
1036  , m_item{i}
1037  {
1038 // qDebug() << "enabling" << i << "to" << (void*)(((char*)i)+size);
1039  }
1040 
1041  Item* operator->() const { return m_item; }
1042 
1043 private:
1044  Item* const m_item;
1045 };
1046 
1056 template <class Item, class ItemRequest, bool markForReferenceCounting = true, bool threadSafe = true,
1057  uint fixedItemSize = 0, unsigned int targetBucketHashSize = 524288 * 2>
1058 class ItemRepository
1059  : public AbstractItemRepository
1060 {
1061  using ThisLocker = Locker<threadSafe>;
1062 
1063  using MyBucket = Bucket<Item, ItemRequest, markForReferenceCounting, fixedItemSize>;
1064 
1065  enum {
1066  //Must be a multiple of Bucket::ObjectMapSize, so Bucket::hasClashingItem can be computed
1067  //Must also be a multiple of Bucket::NextBucketHashSize, for the same reason.(Currently those are same)
1068  bucketHashSize = (targetBucketHashSize / MyBucket::ObjectMapSize) * MyBucket::ObjectMapSize
1069  };
1070 
1071  enum {
1072  BucketStartOffset = sizeof(uint) * 7 + sizeof(short unsigned int) * bucketHashSize //Position in the data where the bucket array starts
1073  };
1074 
1075 public:
1079  explicit ItemRepository(const QString& repositoryName,
1080  ItemRepositoryRegistry* registry = & globalItemRepositoryRegistry(),
1081  uint repositoryVersion = 1, AbstractRepositoryManager* manager = nullptr)
1082  : m_ownMutex(QMutex::Recursive)
1083  , m_mutex(&m_ownMutex)
1084  , m_repositoryName(repositoryName)
1085  , m_registry(registry)
1086  , m_file(nullptr)
1087  , m_dynamicFile(nullptr)
1088  , m_repositoryVersion(repositoryVersion)
1089  , m_manager(manager)
1090  {
1091  m_unloadingEnabled = true;
1092  m_metaDataChanged = true;
1093  m_buckets.resize(10);
1094  m_buckets.fill(nullptr);
1095 
1096  memset(m_firstBucketForHash, 0, bucketHashSize * sizeof(short unsigned int));
1097 
1098  m_statBucketHashClashes = m_statItemCount = 0;
1099  m_currentBucket = 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes
1100  if (m_registry)
1101  m_registry->registerRepository(this, m_manager);
1102  }
1103 
1104  ~ItemRepository() override
1105  {
1106  if (m_registry)
1107  m_registry->unRegisterRepository(this);
1108  close();
1109  }
1110 
1113  void setUnloadingEnabled(bool enabled)
1114  {
1115  m_unloadingEnabled = enabled;
1116  }
1117 
1121  unsigned int index(const ItemRequest& request)
1122  {
1123  ThisLocker lock(m_mutex);
1124 
1125  const uint hash = request.hash();
1126  const uint size = request.itemSize();
1127 
1128  // Bucket indexes tracked while walking the bucket chain for this request hash
1129  unsigned short bucketInChainWithSpace = 0;
1130  unsigned short lastBucketWalked = 0;
1131 
1132  const ushort foundIndexInBucket = walkBucketChain(hash, [&](ushort bucketIdx, const MyBucket* bucketPtr) {
1133  lastBucketWalked = bucketIdx;
1134 
1135  const ushort found = bucketPtr->findIndex(request);
1136 
1137  if (!found && !bucketInChainWithSpace && bucketPtr->canAllocateItem(size)) {
1138  bucketInChainWithSpace = bucketIdx;
1139  }
1140 
1141  return found;
1142  });
1143 
1144  if (foundIndexInBucket) {
1145  // 'request' is already present, return the existing index
1146  return createIndex(lastBucketWalked, foundIndexInBucket);
1147  }
1148 
1149  /*
1150  * Disclaimer: Writer of comment != writer of code, believe with caution
1151  *
1152  * Requested item does not yet exist. Need to find a place to put it...
1153  *
1154  * First choice is to place it in an existing bucket in the chain for the request hash
1155  * Second choice is to find an existing bucket anywhere with enough space
1156  * Otherwise use m_currentBucket (the latest unused bucket)
1157  *
1158  * If the chosen bucket fails to allocate the item, merge buckets to create a monster (dragon?)
1159  *
1160  * Finally, if the first option failed or the selected bucket failed to allocate, add the
1161  * bucket which the item ended up in to the chain of buckets for the request's hash
1162  */
1163 
1164  m_metaDataChanged = true;
1165 
1166  const bool pickedBucketInChain = bucketInChainWithSpace;
1167  int useBucket = bucketInChainWithSpace;
1168  int reOrderFreeSpaceBucketIndex = -1;
1169 
1170  if (!pickedBucketInChain) {
1171  //Try finding an existing bucket with deleted space to store the data into
1172  for (int a = 0; a < m_freeSpaceBuckets.size(); ++a) {
1173  MyBucket* bucketPtr = bucketForIndex(m_freeSpaceBuckets[a]);
1174  Q_ASSERT(bucketPtr->largestFreeSize());
1175 
1176  if (bucketPtr->canAllocateItem(size)) {
1177  //The item fits into the bucket.
1178  useBucket = m_freeSpaceBuckets[a];
1179  reOrderFreeSpaceBucketIndex = a;
1180  break;
1181  }
1182  }
1183 
1184  if (!useBucket) {
1185  useBucket = m_currentBucket;
1186  }
1187  } else {
1188  reOrderFreeSpaceBucketIndex = m_freeSpaceBuckets.indexOf(useBucket);
1189  }
1190 
1191  //The item isn't in the repository yet, find a new bucket for it
1192  while (1) {
1193  if (useBucket >= m_buckets.size()) {
1194  if (m_buckets.size() >= 0xfffe) { //We have reserved the last bucket index 0xffff for special purposes
1195  //the repository has overflown.
1196  qWarning() << "Found no room for an item in" << m_repositoryName << "size of the item:" <<
1197  request.itemSize();
1198  return 0;
1199  } else {
1200  //Allocate new buckets
1201  m_buckets.resize(m_buckets.size() + 10);
1202  }
1203  }
1204  MyBucket* bucketPtr = m_buckets.at(useBucket);
1205  if (!bucketPtr) {
1206  initializeBucket(useBucket);
1207  bucketPtr = m_buckets.at(useBucket);
1208  }
1209 
1210  ENSURE_REACHABLE(useBucket);
1211  Q_ASSERT_X(!bucketPtr->findIndex(
1212  request), Q_FUNC_INFO,
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");
1214 
1215  unsigned short indexInBucket = bucketPtr->index(request, size);
1216 
1217  //If we could not allocate the item in an empty bucket, then we need to create a monster-bucket that
1218  //can hold the data.
1219  if (bucketPtr->isEmpty() && !indexInBucket) {
1221  uint totalSize = size + MyBucket::AdditionalSpacePerItem;
1222 
1223  Q_ASSERT((totalSize > ItemRepositoryBucketSize));
1224 
1225  useBucket = 0;
1226  //The item did not fit in, we need a monster-bucket(Merge consecutive buckets)
1228  int rangeStart = -1;
1229  int rangeEnd = -1;
1230  for (int a = 0; a < m_freeSpaceBuckets.size(); ++a) {
1231  MyBucket* bucketPtr = bucketForIndex(m_freeSpaceBuckets[a]);
1232  if (bucketPtr->isEmpty()) {
1233  //This bucket is a candidate for monster-bucket merging
1234  int index = ( int )m_freeSpaceBuckets[a];
1235  if (rangeEnd != index) {
1236  rangeStart = index;
1237  rangeEnd = index + 1;
1238  } else {
1239  ++rangeEnd;
1240  }
1241  if (rangeStart != rangeEnd) {
1242  uint extent = rangeEnd - rangeStart - 1;
1243  uint totalAvailableSpace = bucketForIndex(rangeStart)->available() +
1244  MyBucket::DataSize* (rangeEnd - rangeStart - 1);
1245  if (totalAvailableSpace > totalSize) {
1246  Q_ASSERT(extent);
1248  Q_ASSERT(( uint )m_freeSpaceBuckets[a - extent] == ( uint )rangeStart);
1249  m_freeSpaceBuckets.remove(a - extent, extent + 1);
1250  useBucket = rangeStart;
1251  convertMonsterBucket(rangeStart, extent);
1252 
1253  break;
1254  }
1255  }
1256  }
1257  }
1258 
1259  if (!useBucket) {
1260  //Create a new monster-bucket at the end of the data
1261  int needMonsterExtent = (totalSize - ItemRepositoryBucketSize) / MyBucket::DataSize + 1;
1262  Q_ASSERT(needMonsterExtent);
1263  if (m_currentBucket + needMonsterExtent + 1 > m_buckets.size()) {
1264  m_buckets.resize(m_buckets.size() + 10 + needMonsterExtent + 1);
1265  }
1266  useBucket = m_currentBucket;
1267 
1268  convertMonsterBucket(useBucket, needMonsterExtent);
1269  m_currentBucket += 1 + needMonsterExtent;
1270  Q_ASSERT(m_currentBucket < ItemRepositoryBucketLimit);
1271  Q_ASSERT(m_buckets[m_currentBucket - 1 - needMonsterExtent] &&
1272  m_buckets[m_currentBucket - 1 - needMonsterExtent]->monsterBucketExtent() ==
1273  needMonsterExtent);
1274  }
1275  Q_ASSERT(useBucket);
1276  bucketPtr = bucketForIndex(useBucket);
1277 
1278  indexInBucket = bucketPtr->index(request, size);
1279  Q_ASSERT(indexInBucket);
1280  }
1281 
1282  if (indexInBucket) {
1283  ++m_statItemCount;
1284 
1285  const int previousBucketNumber = lastBucketWalked;
1286  unsigned short* const bucketHashPosition = m_firstBucketForHash + (hash % bucketHashSize);
1287 
1288  if (!(*bucketHashPosition)) {
1289  Q_ASSERT(!previousBucketNumber);
1290  (*bucketHashPosition) = useBucket;
1291  ENSURE_REACHABLE(useBucket);
1292  } else if (!pickedBucketInChain && previousBucketNumber && previousBucketNumber != useBucket) {
1293  //Should happen rarely
1294  ++m_statBucketHashClashes;
1295 
1297  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, previousBucketNumber));
1298  )
1299 
1300  //Find the position where the paths of useBucket and *bucketHashPosition intersect, and insert useBucket
1301  //there. That way, we don't create loops.
1302  QPair<unsigned int, unsigned int> intersect = hashChainIntersection(*bucketHashPosition, useBucket,
1303  hash);
1304 
1305  Q_ASSERT(m_buckets[previousBucketNumber]->nextBucketForHash(hash) == 0);
1306 
1307  if (!intersect.second) {
1308  ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition, hash, useBucket)); )
1309  ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(useBucket, hash, previousBucketNumber)); )
1310 
1311  Q_ASSERT(m_buckets[previousBucketNumber]->nextBucketForHash(hash) == 0);
1312 
1313  m_buckets[previousBucketNumber]->setNextBucketForHash(hash, useBucket);
1314  ENSURE_REACHABLE(useBucket);
1315  ENSURE_REACHABLE(previousBucketNumber);
1316 
1317  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, useBucket)); )
1318  } else if (intersect.first) {
1319  ifDebugInfiniteRecursion(Q_ASSERT(bucketForIndex(intersect.first)->nextBucketForHash(hash) ==
1320  intersect.second); )
1321  ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition, hash, useBucket)); )
1322  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.second));
1323  )
1324  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.first));
1325  )
1326  ifDebugInfiniteRecursion(Q_ASSERT(bucketForIndex(intersect.first)->nextBucketForHash(hash) ==
1327  intersect.second); )
1328 
1329  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(useBucket, hash, intersect.second)); )
1330  ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(useBucket, hash, intersect.first)); )
1331 
1332  bucketForIndex(intersect.first)->setNextBucketForHash(hash, useBucket);
1333 
1334  ENSURE_REACHABLE(useBucket);
1335  ENSURE_REACHABLE(intersect.second);
1336 
1337  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, useBucket)); )
1338  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.second));
1339  )
1340  } else {
1341  //State: intersect.first == 0 && intersect.second != 0. This means that whole complete
1342  //chain opened by *bucketHashPosition with the hash-value is also following useBucket,
1343  //so useBucket can just be inserted at the top
1344 
1345  ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition, hash, useBucket)); )
1346  ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(useBucket, hash, *bucketHashPosition)); )
1347  unsigned short oldStart = *bucketHashPosition;
1348 
1349  *bucketHashPosition = useBucket;
1350 
1351  ENSURE_REACHABLE(useBucket);
1352  ENSURE_REACHABLE(oldStart);
1353  Q_UNUSED(oldStart);
1354  }
1355  }
1356 
1357  if (reOrderFreeSpaceBucketIndex != -1)
1358  updateFreeSpaceOrder(reOrderFreeSpaceBucketIndex);
1359 
1360  return createIndex(useBucket, indexInBucket);
1361  } else {
1362  //This should never happen when we picked a bucket for re-use
1363  Q_ASSERT(!pickedBucketInChain);
1364  Q_ASSERT(reOrderFreeSpaceBucketIndex == -1);
1365  Q_ASSERT(useBucket == m_currentBucket);
1366 
1367  if (!bucketForIndex(useBucket)->isEmpty())
1368  putIntoFreeList(useBucket, bucketPtr);
1369 
1370  ++m_currentBucket;
1371  Q_ASSERT(m_currentBucket < ItemRepositoryBucketLimit);
1372  useBucket = m_currentBucket;
1373  }
1374  }
1375  //We haven't found a bucket that already contains the item, so append it to the current bucket
1376 
1377  qWarning() << "Found no bucket for an item in" << m_repositoryName;
1378  return 0;
1379  }
1380 
1382  unsigned int findIndex(const ItemRequest& request)
1383  {
1384  ThisLocker lock(m_mutex);
1385 
1386  return walkBucketChain(request.hash(), [this, &request](ushort bucketIdx, const MyBucket* bucketPtr) {
1387  const ushort indexInBucket = bucketPtr->findIndex(request);
1388  return indexInBucket ? createIndex(bucketIdx, indexInBucket) : 0u;
1389  });
1390  }
1391 
1393  void deleteItem(unsigned int index)
1394  {
1395  verifyIndex(index);
1396  ThisLocker lock(m_mutex);
1397 
1398  m_metaDataChanged = true;
1399 
1400  const uint hash = itemFromIndex(index)->hash();
1401  const ushort bucket = (index >> 16);
1402 
1403  //Apart from removing the item itself, we may have to recreate the nextBucketForHash link, so we need the previous bucket
1404  MyBucket* previousBucketPtr = nullptr;
1405  MyBucket* const bucketPtr = walkBucketChain(hash,
1406  [bucket, &previousBucketPtr](ushort bucketIdx,
1407  MyBucket* bucketPtr) -> MyBucket* {
1408  if (bucket != bucketIdx) {
1409  previousBucketPtr = bucketPtr;
1410  return nullptr;
1411  }
1412  return bucketPtr; // found bucket, stop looking
1413  });
1414 
1415  //Make sure the index was reachable through the hash chain
1416  Q_ASSERT(bucketPtr);
1417 
1418  --m_statItemCount;
1419 
1420  bucketPtr->deleteItem(index, hash, *this);
1421 
1426  if (!previousBucketPtr) {
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
1429  m_firstBucketForHash[hash %
1430  bucketHashSize] = walkBucketChain(hash, [hash](ushort bucketIdx, MyBucket* bucketPtr) {
1431  if (bucketPtr->hasClashingItem(hash, bucketHashSize)) {
1432  return bucketIdx;
1433  }
1434  return static_cast<ushort>(0);
1435  });
1436  } else if (!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSize)) {
1437  // TODO: Skip clashing items reachable from m_firstBucketForHash
1438  // (see note in usePermissiveModuloWhenRemovingClashLinks() test)
1439 
1440  ENSURE_REACHABLE(bucket);
1441 
1442  previousBucketPtr->setNextBucketForHash(hash, bucketPtr->nextBucketForHash(hash));
1443 
1444  Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] != previousBucketPtr);
1445  }
1446 
1447  ENSURE_REACHABLE(bucket);
1448 
1449  if (bucketPtr->monsterBucketExtent()) {
1450  //Convert the monster-bucket back to multiple normal buckets, and put them into the free list
1451  uint newBuckets = bucketPtr->monsterBucketExtent() + 1;
1452  Q_ASSERT(bucketPtr->isEmpty());
1453  if (!previousBucketPtr) {
1454  // see https://bugs.kde.org/show_bug.cgi?id=272408
1455  // the monster bucket will be deleted and new smaller ones created
1456  // the next bucket for this hash is invalid anyways as done above
1457  // but calling the below unconditionally leads to other issues...
1458  bucketPtr->setNextBucketForHash(hash, 0);
1459  }
1460  convertMonsterBucket(bucket, 0);
1461  for (uint created = bucket; created < bucket + newBuckets; ++created) {
1462  putIntoFreeList(created, bucketForIndex(created));
1463 #ifdef DEBUG_MONSTERBUCKETS
1464  Q_ASSERT(m_freeSpaceBuckets.indexOf(created) != -1);
1465 #endif
1466  }
1467  } else {
1468  putIntoFreeList(bucket, bucketPtr);
1469  }
1470  }
1471 
1472  using MyDynamicItem = DynamicItem<Item, markForReferenceCounting>;
1473 
1479  MyDynamicItem dynamicItemFromIndex(unsigned int index)
1480  {
1481  verifyIndex(index);
1482 
1483  ThisLocker lock(m_mutex);
1484 
1485  unsigned short bucket = (index >> 16);
1486 
1487  MyBucket* bucketPtr = m_buckets.at(bucket);
1488  if (!bucketPtr) {
1489  initializeBucket(bucket);
1490  bucketPtr = m_buckets.at(bucket);
1491  }
1492  bucketPtr->prepareChange();
1493  unsigned short indexInBucket = index & 0xffff;
1494  return MyDynamicItem(const_cast<Item*>(bucketPtr->itemFromIndex(indexInBucket)),
1495  bucketPtr->data(), bucketPtr->dataSize());
1496  }
1497 
1505  Item* dynamicItemFromIndexSimple(unsigned int index)
1506  {
1507  verifyIndex(index);
1508 
1509  ThisLocker lock(m_mutex);
1510 
1511  unsigned short bucket = (index >> 16);
1512 
1513  MyBucket* bucketPtr = m_buckets.at(bucket);
1514  if (!bucketPtr) {
1515  initializeBucket(bucket);
1516  bucketPtr = m_buckets.at(bucket);
1517  }
1518  bucketPtr->prepareChange();
1519  unsigned short indexInBucket = index & 0xffff;
1520  return const_cast<Item*>(bucketPtr->itemFromIndex(indexInBucket));
1521  }
1522 
1524  const Item* itemFromIndex(unsigned int index) const
1525  {
1526  verifyIndex(index);
1527 
1528  ThisLocker lock(m_mutex);
1529 
1530  unsigned short bucket = (index >> 16);
1531 
1532  const MyBucket* bucketPtr = m_buckets.at(bucket);
1533  if (!bucketPtr) {
1534  initializeBucket(bucket);
1535  bucketPtr = m_buckets.at(bucket);
1536  }
1537  unsigned short indexInBucket = index & 0xffff;
1538  return bucketPtr->itemFromIndex(indexInBucket);
1539  }
1540 
1541  struct Statistics
1542  {
1543  Statistics()
1544  {
1545  }
1546 
1547  uint loadedBuckets = -1;
1548  uint currentBucket = -1;
1549  uint usedMemory = -1;
1550  uint loadedMonsterBuckets = -1;
1551  uint usedSpaceForBuckets = -1;
1552  uint freeSpaceInBuckets = -1;
1553  uint lostSpace = -1;
1554  uint freeUnreachableSpace = -1;
1555  uint hashClashedItems = -1;
1556  uint totalItems = -1;
1557  uint emptyBuckets;
1558  uint hashSize = -1; //How big the hash is
1559  uint hashUse = -1; //How many slots in the hash are used
1560  uint averageInBucketHashSize = -1;
1561  uint averageInBucketUsedSlotCount = -1;
1562  float averageInBucketSlotChainLength = -1;
1563  uint longestInBucketChain = -1;
1564 
1565  uint longestNextBucketChain = -1;
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)
1568 
1569  QString print() const
1570  {
1571  QString ret;
1572  ret +=
1573  QStringLiteral("loaded buckets: %1 current bucket: %2 used memory: %3 loaded monster buckets: %4").arg(
1574  loadedBuckets).arg(currentBucket).arg(usedMemory).arg(loadedMonsterBuckets);
1575  ret += QStringLiteral("\nbucket hash clashed items: %1 total items: %2").arg(hashClashedItems).arg(
1576  totalItems);
1577  ret += QStringLiteral("\nused space for buckets: %1 free space in buckets: %2 lost space: %3").arg(
1578  usedSpaceForBuckets).arg(freeSpaceInBuckets).arg(lostSpace);
1579  ret += QStringLiteral("\nfree unreachable space: %1 empty buckets: %2").arg(freeUnreachableSpace).arg(
1580  emptyBuckets);
1581  ret += QStringLiteral("\nhash size: %1 hash slots used: %2").arg(hashSize).arg(hashUse);
1582  ret += QStringLiteral(
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).
1585  arg(
1586  longestInBucketChain);
1587  ret += QStringLiteral(
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);
1590  return ret;
1591  }
1592  operator QString() const {
1593  return print();
1594  }
1595  };
1596 
1597  QString printStatistics() const override
1598  {
1599  return statistics().print();
1600  }
1601 
1602  Statistics statistics() const
1603  {
1604  Statistics ret;
1605  uint loadedBuckets = 0;
1606  for (auto* bucket : m_buckets) {
1607  if (bucket) {
1608  ++loadedBuckets;
1609  }
1610  }
1611 
1612 #ifdef DEBUG_MONSTERBUCKETS
1613  for (int a = 0; a < m_freeSpaceBuckets.size(); ++a) {
1614  if (a > 0) {
1615  uint prev = a - 1;
1616  uint prevLargestFree = bucketForIndex(m_freeSpaceBuckets[prev])->largestFreeSize();
1617  uint largestFree = bucketForIndex(m_freeSpaceBuckets[a])->largestFreeSize();
1618  Q_ASSERT((prevLargestFree < largestFree) || (prevLargestFree == largestFree &&
1619  m_freeSpaceBuckets[prev] < m_freeSpaceBuckets[a]));
1620  }
1621  }
1622 
1623 #endif
1624  ret.hashSize = bucketHashSize;
1625  ret.hashUse = 0;
1626  for (uint a = 0; a < bucketHashSize; ++a)
1627  if (m_firstBucketForHash[a])
1628  ++ret.hashUse;
1629 
1630  ret.emptyBuckets = 0;
1631 
1632  uint loadedMonsterBuckets = 0;
1633  for (auto* bucket : m_buckets) {
1634  if (bucket && bucket->monsterBucketExtent()) {
1635  loadedMonsterBuckets += bucket->monsterBucketExtent() + 1;
1636  }
1637  }
1638 
1639  uint usedBucketSpace = MyBucket::DataSize* m_currentBucket;
1640  uint freeBucketSpace = 0, freeUnreachableSpace = 0;
1641  uint lostSpace = 0; //Should be zero, else something is wrong
1642  uint totalInBucketHashSize = 0, totalInBucketUsedSlotCount = 0, totalInBucketChainLengths = 0;
1643  uint bucketCount = 0;
1644 
1645  ret.totalBucketFollowerSlots = 0;
1646  ret.averageNextBucketForHashSequenceLength = 0;
1647  ret.longestNextBucketChain = 0;
1648  ret.longestInBucketChain = 0;
1649 
1650  for (int a = 1; a < m_currentBucket + 1; ++a) {
1651  MyBucket* bucket = bucketForIndex(a);
1652  if (bucket) {
1653  ++bucketCount;
1654 
1655  bucket->countFollowerIndexLengths(totalInBucketUsedSlotCount, totalInBucketChainLengths,
1656  totalInBucketHashSize, ret.longestInBucketChain);
1657 
1658  for (uint aa = 0; aa < MyBucket::NextBucketHashSize; ++aa) {
1659  uint length = 0;
1660  uint next = bucket->nextBucketForHash(aa);
1661  if (next) {
1662  ++ret.totalBucketFollowerSlots;
1663  while (next) {
1664  ++length;
1665  ++ret.averageNextBucketForHashSequenceLength;
1666  next = bucketForIndex(next)->nextBucketForHash(aa);
1667  }
1668  }
1669  if (length > ret.longestNextBucketChain) {
1670 // qDebug() << "next-bucket-chain in" << a << aa << ":" << length;
1671  ret.longestNextBucketChain = length;
1672  }
1673  }
1674 
1675  uint bucketFreeSpace = bucket->totalFreeItemsSize() + bucket->available();
1676  freeBucketSpace += bucketFreeSpace;
1677  if (m_freeSpaceBuckets.indexOf(a) == -1)
1678  freeUnreachableSpace += bucketFreeSpace;
1679 
1680  if (bucket->isEmpty()) {
1681  ++ret.emptyBuckets;
1682  Q_ASSERT(!bucket->monsterBucketExtent());
1683 #ifdef DEBUG_MONSTERBUCKETS
1684  Q_ASSERT(m_freeSpaceBuckets.contains(a));
1685 #endif
1686  }
1687 
1688  lostSpace += bucket->lostSpace();
1689  a += bucket->monsterBucketExtent();
1690  }
1691  }
1692 
1693  if (ret.totalBucketFollowerSlots)
1694  ret.averageNextBucketForHashSequenceLength /= ret.totalBucketFollowerSlots;
1695 
1696  ret.loadedBuckets = loadedBuckets;
1697  ret.currentBucket = m_currentBucket;
1698  ret.usedMemory = usedMemory();
1699  ret.loadedMonsterBuckets = loadedMonsterBuckets;
1700 
1701  ret.hashClashedItems = m_statBucketHashClashes;
1702  ret.totalItems = m_statItemCount;
1703  ret.usedSpaceForBuckets = usedBucketSpace;
1704  ret.freeSpaceInBuckets = freeBucketSpace;
1705  ret.lostSpace = lostSpace;
1706 
1707  ret.freeUnreachableSpace = freeUnreachableSpace;
1708  ret.averageInBucketHashSize = totalInBucketHashSize / bucketCount;
1709  ret.averageInBucketUsedSlotCount = totalInBucketUsedSlotCount / bucketCount;
1710  ret.averageInBucketSlotChainLength = float( totalInBucketChainLengths ) / totalInBucketUsedSlotCount;
1711 
1712  //If m_statBucketHashClashes is high, the bucket-hash needs to be bigger
1713  return ret;
1714  }
1715 
1716  uint usedMemory() const
1717  {
1718  uint used = 0;
1719  for (auto* bucket : m_buckets) {
1720  if (bucket) {
1721  used += bucket->usedMemory();
1722  }
1723  }
1724 
1725  return used;
1726  }
1727 
1732  template <class Visitor>
1733  void visitAllItems(Visitor& visitor, bool onlyInMemory = false) const
1734  {
1735  ThisLocker lock(m_mutex);
1736  for (int a = 1; a <= m_currentBucket; ++a) {
1737  if (!onlyInMemory || m_buckets.at(a)) {
1738  if (bucketForIndex(a) && !bucketForIndex(a)->visitAllItems(visitor))
1739  return;
1740  }
1741  }
1742  }
1743 
1746  void store() override
1747  {
1748  QMutexLocker lock(m_mutex);
1749  if (m_file) {
1750  if (!m_file->open(QFile::ReadWrite) || !m_dynamicFile->open(QFile::ReadWrite)) {
1751  qFatal("cannot re-open repository file for storing");
1752  return;
1753  }
1754 
1755  for (int a = 0; a < m_buckets.size(); ++a) {
1756  if (m_buckets[a]) {
1757  if (m_buckets[a]->changed()) {
1758  storeBucket(a);
1759  }
1760  if (m_unloadingEnabled) {
1761  const int unloadAfterTicks = 2;
1762  if (m_buckets[a]->lastUsed() > unloadAfterTicks) {
1763  delete m_buckets[a];
1764  m_buckets[a] = nullptr;
1765  } else {
1766  m_buckets[a]->tick();
1767  }
1768  }
1769  }
1770  }
1771 
1772  if (m_metaDataChanged) {
1773  Q_ASSERT(m_dynamicFile);
1774 
1775  m_file->seek(0);
1776  m_file->write(reinterpret_cast<const char*>(&m_repositoryVersion), sizeof(uint));
1777  uint hashSize = bucketHashSize;
1778  m_file->write(reinterpret_cast<const char*>(&hashSize), sizeof(uint));
1779  uint itemRepositoryVersion = staticItemRepositoryVersion();
1780  m_file->write(reinterpret_cast<const char*>(&itemRepositoryVersion), sizeof(uint));
1781  m_file->write(reinterpret_cast<const char*>(&m_statBucketHashClashes), sizeof(uint));
1782  m_file->write(reinterpret_cast<const char*>(&m_statItemCount), sizeof(uint));
1783 
1784  const uint bucketCount = static_cast<uint>(m_buckets.size());
1785  m_file->write(reinterpret_cast<const char*>(&bucketCount), sizeof(uint));
1786  m_file->write(reinterpret_cast<const char*>(&m_currentBucket), sizeof(uint));
1787  m_file->write(reinterpret_cast<const char*>(m_firstBucketForHash), sizeof(short unsigned int) * bucketHashSize);
1788  Q_ASSERT(m_file->pos() == BucketStartOffset);
1789 
1790  m_dynamicFile->seek(0);
1791  const uint freeSpaceBucketsSize = static_cast<uint>(m_freeSpaceBuckets.size());
1792  m_dynamicFile->write(reinterpret_cast<const char*>(&freeSpaceBucketsSize), sizeof(uint));
1793  m_dynamicFile->write(reinterpret_cast<const char*>(m_freeSpaceBuckets.data()), sizeof(uint) * freeSpaceBucketsSize);
1794  }
1795  //To protect us from inconsistency due to crashes. flush() is not enough. We need to close.
1796  m_file->close();
1797  m_dynamicFile->close();
1798  Q_ASSERT(!m_file->isOpen());
1799  Q_ASSERT(!m_dynamicFile->isOpen());
1800  }
1801  }
1802 
1809  QMutex* mutex() const
1810  {
1811  return m_mutex;
1812  }
1813 
1815  void setMutex(QMutex* mutex)
1816  {
1817  m_mutex = mutex;
1818  }
1819 
1820  QString repositoryName() const override
1821  {
1822  return m_repositoryName;
1823  }
1824 
1825 private:
1826 
1827  uint createIndex(ushort bucketIndex, ushort indexInBucket)
1828  {
1829  //Combine the index in the bucket, and the bucket number into one index
1830  const uint index = (bucketIndex << 16) + indexInBucket;
1831  verifyIndex(index);
1832  return index;
1833  }
1834 
1840  template <typename Visitor>
1841  auto walkBucketChain(unsigned int hash, const Visitor& visitor) const->decltype(visitor(0, nullptr))
1842  {
1843  unsigned short bucketIndex = m_firstBucketForHash[hash % bucketHashSize];
1844 
1845  while (bucketIndex) {
1846  auto* bucketPtr = m_buckets.at(bucketIndex);
1847  if (!bucketPtr) {
1848  initializeBucket(bucketIndex);
1849  bucketPtr = m_buckets.at(bucketIndex);
1850  }
1851 
1852  if (auto visitResult = visitor(bucketIndex, bucketPtr)) {
1853  return visitResult;
1854  }
1855 
1856  bucketIndex = bucketPtr->nextBucketForHash(hash);
1857  }
1858 
1859  return {}; // clazy:exclude=returning-void-expression
1860  }
1861 
1864  void updateFreeSpaceOrder(uint index)
1865  {
1866  m_metaDataChanged = true;
1867 
1868  unsigned int* freeSpaceBuckets = m_freeSpaceBuckets.data();
1869 
1870  Q_ASSERT(index < static_cast<uint>(m_freeSpaceBuckets.size()));
1871  MyBucket* bucketPtr = bucketForIndex(freeSpaceBuckets[index]);
1872 
1873  unsigned short largestFreeSize = bucketPtr->largestFreeSize();
1874 
1875  if (largestFreeSize == 0 ||
1876  (bucketPtr->freeItemCount() <= MyBucket::MaxFreeItemsForHide &&
1877  largestFreeSize <= MyBucket::MaxFreeSizeForHide)) {
1878  //Remove the item from freeSpaceBuckets
1879  m_freeSpaceBuckets.remove(index);
1880  } else {
1881  while (1) {
1882  int prev = index - 1;
1883  int next = index + 1;
1884  if (prev >= 0 && (bucketForIndex(freeSpaceBuckets[prev])->largestFreeSize() > largestFreeSize ||
1885  (bucketForIndex(freeSpaceBuckets[prev])->largestFreeSize() == largestFreeSize &&
1886  freeSpaceBuckets[index] < freeSpaceBuckets[prev]))
1887  ) {
1888  //This item should be behind the successor, either because it has a lower largestFreeSize, or because the index is lower
1889  uint oldPrevValue = freeSpaceBuckets[prev];
1890  freeSpaceBuckets[prev] = freeSpaceBuckets[index];
1891  freeSpaceBuckets[index] = oldPrevValue;
1892  index = prev;
1893  } else if (next < m_freeSpaceBuckets.size()
1894  && (bucketForIndex(freeSpaceBuckets[next])->largestFreeSize() < largestFreeSize
1895  || (bucketForIndex(freeSpaceBuckets[next])->largestFreeSize() == largestFreeSize
1896  && freeSpaceBuckets[index] > freeSpaceBuckets[next]))) {
1897  //This item should be behind the successor, either because it has a higher largestFreeSize, or because the index is higher
1898  uint oldNextValue = freeSpaceBuckets[next];
1899  freeSpaceBuckets[next] = freeSpaceBuckets[index];
1900  freeSpaceBuckets[index] = oldNextValue;
1901  index = next;
1902  } else {
1903  break;
1904  }
1905  }
1906  }
1907  }
1908 
1917  MyBucket* convertMonsterBucket(int bucketNumber, int extent)
1918  {
1919  Q_ASSERT(bucketNumber);
1920  MyBucket* bucketPtr = m_buckets.at(bucketNumber);
1921  if (!bucketPtr) {
1922  initializeBucket(bucketNumber);
1923  bucketPtr = m_buckets.at(bucketNumber);
1924  }
1925 
1926  if (extent) {
1927  //Convert to monster-bucket
1928 #ifdef DEBUG_MONSTERBUCKETS
1929  for (int index = bucketNumber; index < bucketNumber + 1 + extent; ++index) {
1930  Q_ASSERT(bucketPtr->isEmpty());
1931  Q_ASSERT(!bucketPtr->monsterBucketExtent());
1932  Q_ASSERT(m_freeSpaceBuckets.indexOf(index) == -1);
1933  }
1934 
1935 #endif
1936  for (int index = bucketNumber; index < bucketNumber + 1 + extent; ++index)
1937  deleteBucket(index);
1938 
1939  m_buckets[bucketNumber] = new MyBucket();
1940 
1941  m_buckets[bucketNumber]->initialize(extent);
1942 
1943 #ifdef DEBUG_MONSTERBUCKETS
1944 
1945  for (uint index = bucketNumber + 1; index < bucketNumber + 1 + extent; ++index) {
1946  Q_ASSERT(!m_buckets[index]);
1947  }
1948 
1949 #endif
1950  } else {
1951  Q_ASSERT(bucketPtr->monsterBucketExtent());
1952  Q_ASSERT(bucketPtr->isEmpty());
1953  const int oldExtent = bucketPtr->monsterBucketExtent();
1954  deleteBucket(bucketNumber); //Delete the monster-bucket
1955 
1956  for (int index = bucketNumber; index < bucketNumber + 1 + oldExtent; ++index) {
1957  Q_ASSERT(!m_buckets[index]);
1958  m_buckets[index] = new MyBucket();
1959 
1960  m_buckets[index]->initialize(0);
1961  Q_ASSERT(!m_buckets[index]->monsterBucketExtent());
1962  }
1963  }
1964  return m_buckets[bucketNumber];
1965  }
1966 
1967  MyBucket* bucketForIndex(short unsigned int index) const
1968  {
1969  MyBucket* bucketPtr = m_buckets.at(index);
1970  if (!bucketPtr) {
1971  initializeBucket(index);
1972  bucketPtr = m_buckets.at(index);
1973  }
1974  return bucketPtr;
1975  }
1976 
1977  bool open(const QString& path) override
1978  {
1979  QMutexLocker lock(m_mutex);
1980 
1981  close();
1982  //qDebug() << "opening repository" << m_repositoryName << "at" << path;
1983  QDir dir(path);
1984  m_file = new QFile(dir.absoluteFilePath(m_repositoryName));
1985  m_dynamicFile = new QFile(dir.absoluteFilePath(m_repositoryName + QLatin1String("_dynamic")));
1986  if (!m_file->open(QFile::ReadWrite) || !m_dynamicFile->open(QFile::ReadWrite)) {
1987  delete m_file;
1988  m_file = nullptr;
1989  delete m_dynamicFile;
1990  m_dynamicFile = nullptr;
1991  return false;
1992  }
1993 
1994  m_metaDataChanged = true;
1995  if (m_file->size() == 0) {
1996  m_file->resize(0);
1997  m_file->write(reinterpret_cast<const char*>(&m_repositoryVersion), sizeof(uint));
1998  uint hashSize = bucketHashSize;
1999  m_file->write(reinterpret_cast<const char*>(&hashSize), sizeof(uint));
2000  uint itemRepositoryVersion = staticItemRepositoryVersion();
2001  m_file->write(reinterpret_cast<const char*>(&itemRepositoryVersion), sizeof(uint));
2002 
2003  m_statBucketHashClashes = m_statItemCount = 0;
2004 
2005  m_file->write(reinterpret_cast<const char*>(&m_statBucketHashClashes), sizeof(uint));
2006  m_file->write(reinterpret_cast<const char*>(&m_statItemCount), sizeof(uint));
2007 
2008  m_buckets.resize(10);
2009  m_buckets.fill(nullptr);
2010  uint bucketCount = m_buckets.size();
2011  m_file->write(reinterpret_cast<const char*>(&bucketCount), sizeof(uint));
2012 
2013  memset(m_firstBucketForHash, 0, bucketHashSize * sizeof(short unsigned int));
2014 
2015  m_currentBucket = 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes
2016  m_file->write(reinterpret_cast<const char*>(&m_currentBucket), sizeof(uint));
2017  m_file->write(reinterpret_cast<const char*>(m_firstBucketForHash), sizeof(short unsigned int) * bucketHashSize);
2018  //We have completely initialized the file now
2019  if (m_file->pos() != BucketStartOffset) {
2020  KMessageBox::error(nullptr,
2021  i18n("Failed writing to %1, probably the disk is full", m_file->fileName()));
2022  abort();
2023  }
2024 
2025  const uint freeSpaceBucketsSize = 0;
2026  m_dynamicFile->write(reinterpret_cast<const char*>(&freeSpaceBucketsSize), sizeof(uint));
2027  m_freeSpaceBuckets.clear();
2028  } else {
2029  m_file->close();
2030  bool res = m_file->open(QFile::ReadOnly); //Re-open in read-only mode, so we create a read-only m_fileMap
2031  VERIFY(res);
2032  //Check that the version is correct
2033  uint storedVersion = 0, hashSize = 0, itemRepositoryVersion = 0;
2034 
2035  m_file->read(reinterpret_cast<char*>(&storedVersion), sizeof(uint));
2036  m_file->read(reinterpret_cast<char*>(&hashSize), sizeof(uint));
2037  m_file->read(reinterpret_cast<char*>(&itemRepositoryVersion), sizeof(uint));
2038  m_file->read(reinterpret_cast<char*>(&m_statBucketHashClashes), sizeof(uint));
2039  m_file->read(reinterpret_cast<char*>(&m_statItemCount), sizeof(uint));
2040 
2041  if (storedVersion != m_repositoryVersion || hashSize != bucketHashSize ||
2042  itemRepositoryVersion != staticItemRepositoryVersion()) {
2043  qDebug() << "repository" << m_repositoryName << "version mismatch in" << m_file->fileName() <<
2044  ", stored: version " << storedVersion << "hashsize" << hashSize << "repository-version" <<
2045  itemRepositoryVersion << " current: version" << m_repositoryVersion << "hashsize" <<
2046  bucketHashSize << "repository-version" << staticItemRepositoryVersion();
2047  delete m_file;
2048  m_file = nullptr;
2049  delete m_dynamicFile;
2050  m_dynamicFile = nullptr;
2051  return false;
2052  }
2053  m_metaDataChanged = false;
2054 
2055  uint bucketCount = 0;
2056  m_file->read(reinterpret_cast<char*>(&bucketCount), sizeof(uint));
2057  m_buckets.resize(bucketCount);
2058  m_file->read(reinterpret_cast<char*>(&m_currentBucket), sizeof(uint));
2059 
2060  m_file->read(reinterpret_cast<char*>(m_firstBucketForHash), sizeof(short unsigned int) * bucketHashSize);
2061 
2062  Q_ASSERT(m_file->pos() == BucketStartOffset);
2063 
2064  uint freeSpaceBucketsSize = 0;
2065  m_dynamicFile->read(reinterpret_cast<char*>(&freeSpaceBucketsSize), sizeof(uint));
2066  m_freeSpaceBuckets.resize(freeSpaceBucketsSize);
2067  m_dynamicFile->read(reinterpret_cast<char*>(m_freeSpaceBuckets.data()), sizeof(uint) * freeSpaceBucketsSize);
2068  }
2069 
2070  m_fileMapSize = 0;
2071  m_fileMap = nullptr;
2072 
2073 #ifdef ITEMREPOSITORY_USE_MMAP_LOADING
2074  if (m_file->size() > BucketStartOffset) {
2075  m_fileMap = m_file->map(BucketStartOffset, m_file->size() - BucketStartOffset);
2076  Q_ASSERT(m_file->isOpen());
2077  Q_ASSERT(m_file->size() >= BucketStartOffset);
2078  if (m_fileMap) {
2079  m_fileMapSize = m_file->size() - BucketStartOffset;
2080  } else {
2081  qWarning() << "mapping" << m_file->fileName() << "FAILED!";
2082  }
2083  }
2084 #endif
2085  //To protect us from inconsistency due to crashes. flush() is not enough.
2086  m_file->close();
2087  m_dynamicFile->close();
2088 
2089  return true;
2090  }
2091 
2093  void close(bool doStore = false) override
2094  {
2095  if (doStore)
2096  store();
2097 
2098  if (m_file)
2099  m_file->close();
2100  delete m_file;
2101  m_file = nullptr;
2102  m_fileMap = nullptr;
2103  m_fileMapSize = 0;
2104 
2105  if (m_dynamicFile)
2106  m_dynamicFile->close();
2107  delete m_dynamicFile;
2108  m_dynamicFile = nullptr;
2109 
2110  qDeleteAll(m_buckets);
2111  m_buckets.clear();
2112 
2113  memset(m_firstBucketForHash, 0, bucketHashSize * sizeof(short unsigned int));
2114  }
2115 
2116  struct AllItemsReachableVisitor
2117  {
2118  explicit AllItemsReachableVisitor(ItemRepository* rep) : repository(rep)
2119  {
2120  }
2121 
2122  bool operator()(const Item* item)
2123  {
2124  return repository->itemReachable(item);
2125  }
2126 
2127  ItemRepository* repository;
2128  };
2129 
2130  //Returns whether the given item is reachable through its hash
2131  bool itemReachable(const Item* item) const
2132  {
2133  const uint hash = item->hash();
2134 
2135  return walkBucketChain(hash, [ = ](ushort /*bucketIndex*/, const MyBucket* bucketPtr) {
2136  return bucketPtr->itemReachable(item, hash);
2137  });
2138  }
2139 
2140  //Returns true if all items in the given bucket are reachable through their hashes
2141  bool allItemsReachable(unsigned short bucket)
2142  {
2143  if (!bucket)
2144  return true;
2145 
2146  MyBucket* bucketPtr = bucketForIndex(bucket);
2147 
2148  AllItemsReachableVisitor visitor(this);
2149  return bucketPtr->visitAllItems(visitor);
2150  }
2151 
2152  int finalCleanup() override
2153  {
2154  ThisLocker lock(m_mutex);
2155 
2156  int changed = 0;
2157  for (int a = 1; a <= m_currentBucket; ++a) {
2158  MyBucket* bucket = bucketForIndex(a);
2159  if (bucket && bucket->dirty()) {
2160  changed += bucket->finalCleanup(*this);
2161  }
2162  a += bucket->monsterBucketExtent(); //Skip buckets that are attached as tail to monster-buckets
2163  }
2164 
2165  return changed;
2166  }
2167 
2168  inline void initializeBucket(int bucketNumber) const
2169  {
2170  Q_ASSERT(bucketNumber);
2171 #ifdef DEBUG_MONSTERBUCKETS
2172  for (uint offset = 1; offset < 5; ++offset) {
2173  int test = bucketNumber - offset;
2174  if (test >= 0 && m_buckets[test]) {
2175  Q_ASSERT(m_buckets[test]->monsterBucketExtent() < offset);
2176  }
2177  }
2178 
2179 #endif
2180 
2181  if (!m_buckets[bucketNumber]) {
2182  m_buckets[bucketNumber] = new MyBucket();
2183 
2184  bool doMMapLoading = ( bool )m_fileMap;
2185 
2186  uint offset = ((bucketNumber - 1) * MyBucket::DataSize);
2187  if (m_file && offset < m_fileMapSize && doMMapLoading &&
2188  *reinterpret_cast<uint*>(m_fileMap + offset) == 0) {
2189 // qDebug() << "loading bucket mmap:" << bucketNumber;
2190  m_buckets[bucketNumber]->initializeFromMap(reinterpret_cast<char*>(m_fileMap + offset));
2191  } else if (m_file) {
2192  //Either memory-mapping is disabled, or the item is not in the existing memory-map,
2193  //so we have to load it the classical way.
2194  bool res = m_file->open(QFile::ReadOnly);
2195 
2196  if (offset + BucketStartOffset < m_file->size()) {
2197  VERIFY(res);
2198  offset += BucketStartOffset;
2199  m_file->seek(offset);
2200  uint monsterBucketExtent;
2201  m_file->read(reinterpret_cast<char*>((&monsterBucketExtent)), sizeof(unsigned int));
2202  m_file->seek(offset);
2204  QByteArray data = m_file->read((1 + monsterBucketExtent) * MyBucket::DataSize);
2205  m_buckets[bucketNumber]->initializeFromMap(data.data());
2206  m_buckets[bucketNumber]->prepareChange();
2207  } else {
2208  m_buckets[bucketNumber]->initialize(0);
2209  }
2210 
2211  m_file->close();
2212  } else {
2213  m_buckets[bucketNumber]->initialize(0);
2214  }
2215  } else {
2216  m_buckets[bucketNumber]->initialize(0);
2217  }
2218  }
2219 
2221  void deleteBucket(int bucketNumber)
2222  {
2223  Q_ASSERT(bucketForIndex(bucketNumber)->isEmpty());
2224  Q_ASSERT(bucketForIndex(bucketNumber)->noNextBuckets());
2225  delete m_buckets[bucketNumber];
2226  m_buckets[bucketNumber] = nullptr;
2227  }
2228 
2229  //m_file must be opened
2230  void storeBucket(int bucketNumber) const
2231  {
2232  if (m_file && m_buckets[bucketNumber]) {
2233  m_buckets[bucketNumber]->store(m_file, BucketStartOffset + (bucketNumber - 1) * MyBucket::DataSize);
2234  }
2235  }
2236 
2239  bool walkBucketLinks(uint checkBucket, uint hash, uint mustFindBucket = 0) const
2240  {
2241  bool found = false;
2242  while (checkBucket) {
2243  if (checkBucket == mustFindBucket)
2244  found = true;
2245 
2246  checkBucket = bucketForIndex(checkBucket)->nextBucketForHash(hash);
2247  }
2248  return found || (mustFindBucket == 0);
2249  }
2250 
2254  QPair<unsigned int, unsigned int> hashChainIntersection(uint mainHead, uint intersectorHead, uint hash) const
2255  {
2256  uint previous = 0;
2257  uint current = mainHead;
2258  while (current) {
2260  if (walkBucketLinks(intersectorHead, hash, current))
2261  return qMakePair(previous, current);
2262 
2263  previous = current;
2264  current = bucketForIndex(current)->nextBucketForHash(hash);
2265  }
2266  return qMakePair(0u, 0u);
2267  }
2268 
2269  void putIntoFreeList(unsigned short bucket, MyBucket* bucketPtr)
2270  {
2271  Q_ASSERT(!bucketPtr->monsterBucketExtent());
2272  int indexInFree = m_freeSpaceBuckets.indexOf(bucket);
2273 
2274  if (indexInFree == -1 &&
2275  (bucketPtr->freeItemCount() >= MyBucket::MinFreeItemsForReuse ||
2276  bucketPtr->largestFreeSize() >= MyBucket::MinFreeSizeForReuse)) {
2277  //Add the bucket to the list of buckets from where to re-assign free space
2278  //We only do it when a specific threshold of empty items is reached, because that way items can stay "somewhat" semantically ordered.
2279  Q_ASSERT(bucketPtr->largestFreeSize());
2280  int insertPos;
2281  for (insertPos = 0; insertPos < m_freeSpaceBuckets.size(); ++insertPos) {
2282  if (bucketForIndex(m_freeSpaceBuckets[insertPos])->largestFreeSize() > bucketPtr->largestFreeSize())
2283  break;
2284  }
2285 
2286  m_freeSpaceBuckets.insert(insertPos, bucket);
2287  updateFreeSpaceOrder(insertPos);
2288  } else if (indexInFree != -1) {
2290  updateFreeSpaceOrder(indexInFree);
2291  }
2292 #ifdef DEBUG_MONSTERBUCKETS
2293  if (bucketPtr->isEmpty()) {
2294  Q_ASSERT(m_freeSpaceBuckets.contains(bucket));
2295  }
2296 #endif
2297  }
2298 
2299  void verifyIndex(uint index) const
2300  {
2301  // We don't use zero indices
2302  Q_ASSERT(index);
2303  int bucket = (index >> 16);
2304  // nor zero buckets
2305  Q_ASSERT(bucket);
2306  Q_ASSERT_X(bucket < m_buckets.size(), Q_FUNC_INFO,
2307  qPrintable(QStringLiteral("index %1 gives invalid bucket number %2, current count is: %3")
2308  .arg(index)
2309  .arg(bucket)
2310  .arg(m_buckets.size())));
2311 
2312  // don't trigger compile warnings in release mode
2313  Q_UNUSED(bucket);
2314  Q_UNUSED(index);
2315  }
2316 
2317  bool m_metaDataChanged;
2318  mutable QMutex m_ownMutex;
2319  mutable QMutex* m_mutex;
2320  QString m_repositoryName;
2321  mutable int m_currentBucket;
2322  //List of buckets that have free space available that can be assigned. Sorted by size: Smallest space first. Second order sorting: Bucket index
2323  QVector<uint> m_freeSpaceBuckets;
2324  mutable QVector<MyBucket*> m_buckets;
2325  uint m_statBucketHashClashes, m_statItemCount;
2326  //Maps hash-values modulo 1<<bucketHashSizeBits to the first bucket such a hash-value appears in
2327  short unsigned int m_firstBucketForHash[bucketHashSize];
2328 
2329  ItemRepositoryRegistry* m_registry;
2330  //File that contains the buckets
2331  QFile* m_file;
2332  uchar* m_fileMap;
2333  uint m_fileMapSize;
2334  //File that contains more dynamic data, like the list of buckets with deleted items
2335  QFile* m_dynamicFile;
2336  uint m_repositoryVersion;
2337  bool m_unloadingEnabled;
2338  AbstractRepositoryManager* m_manager;
2339  friend class ::TestItemRepository;
2340 };
2341 }
2342 
2343 #endif
KDevelop::Bucket::CheckEnd
Definition: itemrepository.h:129
QMutex
KDevelop::Locker< true >::Locker
Locker(QMutex *mutex)
Definition: itemrepository.h:1012
KDevelop::Bucket::readValue
void readValue(char *&from, T &to)
Definition: itemrepository.h:164
QFile::seek
virtual bool seek(qint64 pos)
KDevelop::ItemRepository::Statistics::freeSpaceInBuckets
uint freeSpaceInBuckets
Definition: itemrepository.h:1552
QFile::close
virtual void close()
KDevelop::Bucket::ObjectMapSize
Definition: itemrepository.h:116
QFile::resize
bool resize(qint64 sz)
KDevelop::Bucket::changed
bool changed() const
Definition: itemrepository.h:766
VERIFY
#define VERIFY(X)
Definition: itemrepository.h:64
KDevelop::Bucket::nextBucketForHash
unsigned short nextBucketForHash(uint hash) const
Definition: itemrepository.h:696
KDevelop::Locker< true >::~Locker
~Locker()
Definition: itemrepository.h:1016
QFile::open
virtual bool open(QFlags< QIODevice::OpenModeFlag > mode)
QVector::insert
void insert(int i, const T &value)
KDevelop::Bucket::MaxFreeItemsForHide
Definition: itemrepository.h:117
KDevelop::ItemRepository::setMutex
void setMutex(QMutex *mutex)
With this, you can replace the internal mutex with another one.
Definition: itemrepository.h:1815
KDevelop::OptionalDUChainReferenceCountingEnabler
Definition: referencecounting.h:148
QDir
KDevelop::Bucket::monsterBucketExtent
int monsterBucketExtent() const
Returns the count of following buckets that were merged onto this buckets data array.
Definition: itemrepository.h:784
QFile::flush
bool flush()
KDevelop::ItemRepositoryBucketSize
Definition: itemrepository.h:97
KDevelop::ItemRepository::Statistics::freeUnreachableSpace
uint freeUnreachableSpace
Definition: itemrepository.h:1554
QVector::indexOf
int indexOf(const T &value, int from) const
KDevelop::Locker
Definition: itemrepository.h:1002
KDevelop::ItemRepository::dynamicItemFromIndex
MyDynamicItem dynamicItemFromIndex(unsigned int index)
This returns an editable version of the item.
Definition: itemrepository.h:1479
KDevelop::Bucket::tick
void tick() const
Definition: itemrepository.h:754
KDevelop::ItemRepository::Statistics::averageInBucketSlotChainLength
float averageInBucketSlotChainLength
Definition: itemrepository.h:1562
KDevelop::ItemRepository::Statistics::currentBucket
uint currentBucket
Definition: itemrepository.h:1548
itemrepositoryregistry.h
KDevelop::Bucket::deleteItem
void deleteItem(unsigned short index, unsigned int hash, Repository &repository)
Definition: itemrepository.h:523
KDevelop::Bucket::initializeFromMap
void initializeFromMap(char *current)
Definition: itemrepository.h:170
KDevelop::Bucket::dataSize
uint dataSize() const
Definition: itemrepository.h:264
KDevelop::ItemRepository::Statistics::hashSize
uint hashSize
Definition: itemrepository.h:1558
KDevelop::Bucket::canAllocateItem
bool canAllocateItem(unsigned int size) const
Definition: itemrepository.h:738
KDevelop::Bucket::usedMemory
uint usedMemory() const
Definition: itemrepository.h:640
QVector::data
T * data()
KDevelop::Bucket::isEmpty
bool isEmpty() const
Definition: itemrepository.h:620
KDevelop::Bucket::lastUsed
int lastUsed() const
Definition: itemrepository.h:760
KDevelop::ItemRepository::itemFromIndex
const Item * itemFromIndex(unsigned int index) const
Definition: itemrepository.h:1524
QVector::remove
void remove(int i)
KDevelop::Bucket::DataSize
Definition: itemrepository.h:124
QFile::fileName
QString fileName() const
KDevelop::Bucket::NextBucketHashSize
Definition: itemrepository.h:123
KDevelop::ItemRepository::Statistics::totalItems
uint totalItems
Definition: itemrepository.h:1556
KDevelop::ItemRepository::Statistics::longestInBucketChain
uint longestInBucketChain
Definition: itemrepository.h:1563
KDevelop::staticItemRepositoryVersion
uint staticItemRepositoryVersion()
Returns a version-number that is used to reset the item-repository after incompatible layout changes.
Definition: abstractitemrepository.cpp:24
KDevelop::Bucket::MinFreeItemsForReuse
Definition: itemrepository.h:119
KDevelop::Bucket::CheckStart
Definition: itemrepository.h:128
KDevelop::ItemRepository::ItemRepository
ItemRepository(const QString &repositoryName, ItemRepositoryRegistry *registry=&globalItemRepositoryRegistry(), uint repositoryVersion=1, AbstractRepositoryManager *manager=nullptr)
Definition: itemrepository.h:1079
KDevelop::DynamicItem::DynamicItem
DynamicItem(Item *i, const void *start, unsigned size)
Definition: itemrepository.h:1034
QVector::clear
void clear()
KDevelop::Bucket::itemFromIndex
const Item * itemFromIndex(unsigned short index) const
Definition: itemrepository.h:614
KDevelop::ItemRepository::Statistics::longestNextBucketChain
uint longestNextBucketChain
Definition: itemrepository.h:1565
KDevelop::Bucket::countFollowerIndexLengths
void countFollowerIndexLengths(uint &usedSlots, uint &lengths, uint &slotCount, uint &longestInBucketFollowerChain)
Definition: itemrepository.h:483
KDevelop::Bucket::MaxFreeSizeForHide
Definition: itemrepository.h:118
QString
KDevelop::ItemRepository::printStatistics
QString printStatistics() const override
Definition: itemrepository.h:1597
QIODevice::isOpen
bool isOpen() const
repositorymanager.h
KDevelop::Bucket::data
char * data()
Definition: itemrepository.h:259
KDevelop::ItemRepository::visitAllItems
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
KDevelop::Bucket::visitAllItems
bool visitAllItems(Visitor &visitor) const
Definition: itemrepository.h:646
QVector::contains
bool contains(const T &value) const
KDevelop::globalItemRepositoryRegistry
ItemRepositoryRegistry & globalItemRepositoryRegistry()
The global item-repository registry that is used by default.
Definition: itemrepositoryregistry.cpp:206
KDevelop::ItemRepository::statistics
Statistics statistics() const
Definition: itemrepository.h:1602
QFile::pos
virtual qint64 pos() const
KDevelop::ItemRepository::Statistics::usedMemory
uint usedMemory
Definition: itemrepository.h:1549
KDevelop::Bucket::dirty
bool dirty() const
Definition: itemrepository.h:778
KDevelop::Bucket::hasClashingItem
bool hasClashingItem(uint hash, uint modulo)
Definition: itemrepository.h:458
KDevelop::Bucket::largestFreeSize
short unsigned int largestFreeSize() const
Definition: itemrepository.h:726
QVector::resize
void resize(int size)
KDevelop::Bucket::AdditionalSpacePerItem
Definition: itemrepository.h:113
KDevelop::Bucket::itemReachable
bool itemReachable(const Item *item, uint hash) const
Definition: itemrepository.h:508
KDevelop::ItemRepository::MyDynamicItem
DynamicItem< Item, markForReferenceCounting > MyDynamicItem
Definition: itemrepository.h:1472
KDevelop::Bucket::freeItemCount
uint freeItemCount() const
Definition: itemrepository.h:709
QLatin1String
KDevelop::Bucket::noNextBuckets
bool noNextBuckets() const
Returns true if this bucket has no nextBucketForHash links.
Definition: itemrepository.h:626
KDevelop::ItemRepositoryRegistry::unRegisterRepository
void unRegisterRepository(AbstractItemRepository *repository)
Remove a repository.
Definition: itemrepositoryregistry.cpp:265
KDevelop::AbstractRepositoryManager
Internal helper class that wraps around a repository object and manages its lifetime.
Definition: abstractitemrepository.h:51
KDevelop::ItemRepository::dynamicItemFromIndexSimple
Item * dynamicItemFromIndexSimple(unsigned int index)
This returns an editable version of the item.
Definition: itemrepository.h:1505
KDevelop::ItemRepository::Statistics::loadedMonsterBuckets
uint loadedMonsterBuckets
Definition: itemrepository.h:1550
KDevelop::Bucket::Bucket
Bucket()
Definition: itemrepository.h:131
QFile::size
virtual qint64 size() const
KDevelop::Bucket::initialize
void initialize(int monsterBucketExtent)
Definition: itemrepository.h:143
QIODevice::read
qint64 read(char *data, qint64 maxSize)
KDevelop::ItemRepository::Statistics::averageInBucketUsedSlotCount
uint averageInBucketUsedSlotCount
Definition: itemrepository.h:1561
KDevelop::ItemRepository::Statistics::hashClashedItems
uint hashClashedItems
Definition: itemrepository.h:1555
KDevelop::Locker::Locker
Locker(const T &)
Definition: itemrepository.h:1005
KDevelop::Bucket::index
unsigned short index(const ItemRequest &request, unsigned int itemSize)
Definition: itemrepository.h:291
KDevelop::ItemRepository::Statistics::Statistics
Statistics()
Definition: itemrepository.h:1543
KDevelop::Bucket::setNextBucketForHash
void setNextBucketForHash(unsigned int hash, unsigned short bucket)
Definition: itemrepository.h:702
KDevelop::Bucket::available
uint available() const
Definition: itemrepository.h:635
KDevelop::Bucket::prepareChange
void prepareChange()
Definition: itemrepository.h:771
QFile::map
uchar * map(qint64 offset, qint64 size, MemoryMapFlags flags)
KDevelop::ItemRepository::Statistics::loadedBuckets
uint loadedBuckets
Definition: itemrepository.h:1547
KDevelop::DynamicItem::operator->
Item * operator->() const
Definition: itemrepository.h:1041
KDevelop::DynamicItem
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
KDevelop::ItemRepository::setUnloadingEnabled
void setUnloadingEnabled(bool enabled)
Unloading of buckets is enabled by default.
Definition: itemrepository.h:1113
KDevelop::ItemRepository
Definition: itemrepository.h:1058
KDevelop::Bucket::store
void store(QFile *file, size_t offset)
Definition: itemrepository.h:193
KDevelop::ItemRepositoryRegistry::registerRepository
void registerRepository(AbstractItemRepository *repository, AbstractRepositoryManager *manager)
Add a new repository.
Definition: itemrepositoryregistry.cpp:211
KDevelop::ItemRepository::repositoryName
QString repositoryName() const override
Definition: itemrepository.h:1820
KDevelop::AbstractItemRepository
The interface class for an item-repository object.
Definition: abstractitemrepository.h:33
referencecounting.h
KDevelop::ItemRepositoryBucketLimit
Definition: itemrepository.h:98
KDevelop
Definition: abstractitemrepository.cpp:23
ENSURE_REACHABLE
#define ENSURE_REACHABLE(bucket)
Definition: itemrepository.h:53
KDevelop::ItemRepository::store
void store() override
Synchronizes the state on disk to the one in memory, and does some memory-management.
Definition: itemrepository.h:1746
QVector::size
int size() const
KDevelop::ItemRepository::Statistics::totalBucketFollowerSlots
uint totalBucketFollowerSlots
Definition: itemrepository.h:1566
KDevelop::ItemRepository::Statistics
Definition: itemrepository.h:1541
QMutexLocker
KDevelop::ItemRepository::deleteItem
void deleteItem(unsigned int index)
Deletes the item from the repository.
Definition: itemrepository.h:1393
QVector< uint >
KDevelop::ItemRepository::Statistics::averageInBucketHashSize
uint averageInBucketHashSize
Definition: itemrepository.h:1560
QString::arg
QString arg(qlonglong a, int fieldWidth, int base, const QChar &fillChar) const
KDevelop::Bucket::MinFreeSizeForReuse
Definition: itemrepository.h:120
KDevelop::ItemRepository::index
unsigned int index(const ItemRequest &request)
Returns the index for the given item.
Definition: itemrepository.h:1121
KDevelop::ItemRepository::Statistics::lostSpace
uint lostSpace
Definition: itemrepository.h:1553
KDevelop::ItemRepository::~ItemRepository
~ItemRepository() override
Definition: itemrepository.h:1104
ifDebugLostSpace
#define ifDebugLostSpace(x)
Definition: itemrepository.h:41
KDevelop::Bucket
Buckets are the memory-units that are used to store the data in an ItemRepository.
Definition: itemrepository.h:109
KDevelop::ItemRepository::usedMemory
uint usedMemory() const
Definition: itemrepository.h:1716
abstractitemrepository.h
ifDebugInfiniteRecursion
#define ifDebugInfiniteRecursion(x)
Definition: itemrepository.h:38
QFile
KDevelop::ItemRepository::findIndex
unsigned int findIndex(const ItemRequest &request)
Returns zero if the item is not in the repository yet.
Definition: itemrepository.h:1382
KDevelop::ItemRepository::Statistics::hashUse
uint hashUse
Definition: itemrepository.h:1559
QPair
KDevelop::Bucket::finalCleanup
int finalCleanup(Repository &repository)
Returns whether something was changed.
Definition: itemrepository.h:667
KDevelop::Bucket::findIndex
unsigned short findIndex(const ItemRequest &request) const
Definition: itemrepository.h:270
KDevelop::Bucket::lostSpace
uint lostSpace()
Definition: itemrepository.h:790
QByteArray::data
char * data()
KDevelop::ItemRepository::Statistics::usedSpaceForBuckets
uint usedSpaceForBuckets
Definition: itemrepository.h:1551
KDevelop::ItemRepositoryRegistry
Manages a set of item-repositories and allows loading/storing them all at once from/to disk.
Definition: itemrepositoryregistry.h:41
QByteArray
QIODevice::write
qint64 write(const char *data, qint64 maxSize)
KDevelop::Bucket::~Bucket
~Bucket()
Definition: itemrepository.h:134
KDevelop::Bucket::totalFreeItemsSize
short unsigned int totalFreeItemsSize() const
Definition: itemrepository.h:714
KDevelop::ItemRepository::Statistics::print
QString print() const
Definition: itemrepository.h:1569
KDevelop::ItemRepository::Statistics::averageNextBucketForHashSequenceLength
float averageNextBucketForHashSequenceLength
Definition: itemrepository.h:1567
KDevelop::ItemRepository::mutex
QMutex * mutex() const
This mutex is used for the thread-safe locking when threadSafe is true.
Definition: itemrepository.h:1809
KDevelop::ItemRepository::Statistics::emptyBuckets
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

KDE's Doxygen guidelines are available online.

kdevplatform/serialization

Skip menu "kdevplatform/serialization"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdevelop API Reference

Skip menu "kdevelop API Reference"
  • kdevplatform
  •   debugger
  •   documentation
  •   interfaces
  •   language
  •     assistant
  •     backgroundparser
  •     checks
  •     classmodel
  •     codecompletion
  •     codegen
  •     duchain
  •     editor
  •     highlighting
  •     interfaces
  •     util
  •   outputview
  •   project
  •   serialization
  •   shell
  •   sublime
  •   tests
  •   util
  •   vcs

Search



Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal