File indexing completed on 2024-10-06 06:42:38
0001 /* 0002 This file is part of the KDE libraries 0003 SPDX-FileCopyrightText: 1999 Waldo Bastian <bastian@kde.org> 0004 0005 SPDX-License-Identifier: LGPL-2.0-only 0006 */ 0007 0008 #include "ksycoca.h" 0009 #include "ksycocadict_p.h" 0010 #include "ksycocaentry.h" 0011 #include "sycocadebug.h" 0012 #include <kservice.h> 0013 0014 #include <QBitArray> 0015 #include <QIODevice> 0016 #include <QList> 0017 0018 namespace 0019 { 0020 struct string_entry { 0021 string_entry(const QString &_key, const KSycocaEntry::Ptr &_payload) 0022 : hash(0) 0023 , length(_key.length()) 0024 , keyStr(_key) 0025 , key(keyStr.unicode()) 0026 , payload(_payload) 0027 { 0028 } 0029 uint hash; 0030 const int length; 0031 const QString keyStr; 0032 const QChar *const key; // always points to keyStr.unicode(); just an optimization 0033 const KSycocaEntry::Ptr payload; 0034 }; 0035 } 0036 0037 class KSycocaDictPrivate 0038 { 0039 public: 0040 KSycocaDictPrivate() 0041 : stream(nullptr) 0042 , offset(0) 0043 , hashTableSize(0) 0044 { 0045 } 0046 0047 ~KSycocaDictPrivate() 0048 { 0049 } 0050 0051 // Helper for find_string and findMultiString 0052 qint32 offsetForKey(const QString &key) const; 0053 0054 // Calculate hash - can be used during loading and during saving. 0055 quint32 hashKey(const QString &key) const; 0056 0057 std::vector<std::unique_ptr<string_entry>> m_stringentries; 0058 QDataStream *stream; 0059 qint64 offset; 0060 quint32 hashTableSize; 0061 QList<qint32> hashList; 0062 }; 0063 0064 KSycocaDict::KSycocaDict() 0065 : d(new KSycocaDictPrivate) 0066 { 0067 } 0068 0069 KSycocaDict::KSycocaDict(QDataStream *str, int offset) 0070 : d(new KSycocaDictPrivate) 0071 { 0072 d->stream = str; 0073 d->offset = offset; 0074 0075 quint32 test1; 0076 quint32 test2; 0077 str->device()->seek(offset); 0078 (*str) >> test1 >> test2; 0079 if ((test1 > 0x000fffff) || (test2 > 1024)) { 0080 KSycoca::flagError(); 0081 d->hashTableSize = 0; 0082 d->offset = 0; 0083 return; 0084 } 0085 0086 str->device()->seek(offset); 0087 (*str) >> d->hashTableSize; 0088 (*str) >> d->hashList; 0089 d->offset = str->device()->pos(); // Start of hashtable 0090 } 0091 0092 KSycocaDict::~KSycocaDict() = default; 0093 0094 void KSycocaDict::add(const QString &key, const KSycocaEntry::Ptr &payload) 0095 { 0096 if (key.isEmpty()) { 0097 return; // Not allowed (should never happen) 0098 } 0099 if (!payload) { 0100 return; // Not allowed! 0101 } 0102 0103 d->m_stringentries.push_back(std::make_unique<string_entry>(key, payload)); 0104 } 0105 0106 void KSycocaDict::remove(const QString &key) 0107 { 0108 if (!d) { 0109 return; 0110 } 0111 0112 auto it = std::find_if(d->m_stringentries.begin(), d->m_stringentries.end(), [&key](const std::unique_ptr<string_entry> &entry) { 0113 return entry->keyStr == key; 0114 }); 0115 0116 if (it != d->m_stringentries.end()) { 0117 d->m_stringentries.erase(it); 0118 } else { 0119 qCDebug(SYCOCA) << "key not found:" << key; 0120 } 0121 } 0122 0123 int KSycocaDict::find_string(const QString &key) const 0124 { 0125 Q_ASSERT(d); 0126 0127 // qCDebug(SYCOCA) << QString("KSycocaDict::find_string(%1)").arg(key); 0128 qint32 offset = d->offsetForKey(key); 0129 0130 // qCDebug(SYCOCA) << QString("offset is %1").arg(offset,8,16); 0131 if (offset == 0) { 0132 return 0; 0133 } 0134 0135 if (offset > 0) { 0136 return offset; // Positive ID 0137 } 0138 0139 // Lookup duplicate list. 0140 offset = -offset; 0141 0142 d->stream->device()->seek(offset); 0143 // qCDebug(SYCOCA) << QString("Looking up duplicate list at %1").arg(offset,8,16); 0144 0145 while (true) { 0146 (*d->stream) >> offset; 0147 if (offset == 0) { 0148 break; 0149 } 0150 QString dupkey; 0151 (*d->stream) >> dupkey; 0152 // qCDebug(SYCOCA) << QString(">> %1 %2").arg(offset,8,16).arg(dupkey); 0153 if (dupkey == key) { 0154 return offset; 0155 } 0156 } 0157 // qCDebug(SYCOCA) << "Not found!"; 0158 0159 return 0; 0160 } 0161 0162 QList<int> KSycocaDict::findMultiString(const QString &key) const 0163 { 0164 qint32 offset = d->offsetForKey(key); 0165 QList<int> offsetList; 0166 if (offset == 0) { 0167 return offsetList; 0168 } 0169 0170 if (offset > 0) { // Positive ID: one entry found 0171 offsetList.append(offset); 0172 return offsetList; 0173 } 0174 0175 // Lookup duplicate list. 0176 offset = -offset; 0177 0178 d->stream->device()->seek(offset); 0179 // qCDebug(SYCOCA) << QString("Looking up duplicate list at %1").arg(offset,8,16); 0180 0181 while (true) { 0182 (*d->stream) >> offset; 0183 if (offset == 0) { 0184 break; 0185 } 0186 QString dupkey; 0187 (*d->stream) >> dupkey; 0188 // qCDebug(SYCOCA) << QString(">> %1 %2").arg(offset,8,16).arg(dupkey); 0189 if (dupkey == key) { 0190 offsetList.append(offset); 0191 } 0192 } 0193 return offsetList; 0194 } 0195 0196 uint KSycocaDict::count() const 0197 { 0198 if (!d) { 0199 return 0; 0200 } 0201 0202 return d->m_stringentries.size(); 0203 } 0204 0205 void KSycocaDict::clear() 0206 { 0207 d.reset(); 0208 } 0209 0210 uint KSycocaDictPrivate::hashKey(const QString &key) const 0211 { 0212 int len = key.length(); 0213 uint h = 0; 0214 0215 for (int i = 0; i < hashList.count(); i++) { 0216 int pos = hashList[i]; 0217 if (pos == 0) { 0218 continue; 0219 } else if (pos < 0) { 0220 pos = -pos; 0221 if (pos < len) { 0222 h = ((h * 13) + (key[len - pos].cell() % 29)) & 0x3ffffff; 0223 } 0224 } else { 0225 pos = pos - 1; 0226 if (pos < len) { 0227 h = ((h * 13) + (key[pos].cell() % 29)) & 0x3ffffff; 0228 } 0229 } 0230 } 0231 return h; 0232 } 0233 0234 // If we have the strings 0235 // hello 0236 // world 0237 // kde 0238 // Then we end up with 0239 // ABCDE 0240 // where A = diversity of 'h' + 'w' + 'k' etc. 0241 // Also, diversity(-2) == 'l'+'l'+'d' (second character from the end) 0242 0243 // The hasList is used for hashing: 0244 // hashList = (-2, 1, 3) means that the hash key comes from 0245 // the 2nd character from the right, then the 1st from the left, then the 3rd from the left. 0246 0247 // Calculate the diversity of the strings at position 'pos' 0248 // NOTE: this code is slow, it takes 12% of the _overall_ `kbuildsycoca5 --noincremental` running time 0249 static int calcDiversity(std::vector<std::unique_ptr<string_entry>> *stringlist, int inPos, uint sz) 0250 { 0251 if (inPos == 0) { 0252 return 0; 0253 } 0254 QBitArray matrix(sz); 0255 int pos; 0256 0257 // static const int s_maxItems = 50; 0258 // int numItem = 0; 0259 0260 if (inPos < 0) { 0261 pos = -inPos; 0262 for (const auto &entryPtr : *stringlist) { 0263 const int rpos = entryPtr->length - pos; 0264 if (rpos > 0) { 0265 const uint hash = ((entryPtr->hash * 13) + (entryPtr->key[rpos].cell() % 29)) & 0x3ffffff; 0266 matrix.setBit(hash % sz, true); 0267 } 0268 // if (++numItem == s_maxItems) 0269 // break; 0270 } 0271 } else { 0272 pos = inPos - 1; 0273 for (const auto &entryPtr : *stringlist) { 0274 if (pos < entryPtr->length) { 0275 const uint hash = ((entryPtr->hash * 13) + (entryPtr->key[pos].cell() % 29)) & 0x3ffffff; 0276 matrix.setBit(hash % sz, true); 0277 } 0278 // if (++numItem == s_maxItems) 0279 // break; 0280 } 0281 } 0282 return matrix.count(true); 0283 } 0284 0285 // 0286 // Add the diversity of the strings at position 'pos' 0287 static void addDiversity(std::vector<std::unique_ptr<string_entry>> *stringlist, int pos) 0288 { 0289 if (pos == 0) { 0290 return; 0291 } 0292 0293 if (pos < 0) { 0294 pos = -pos; 0295 for (auto &entryPtr : *stringlist) { 0296 const int rpos = entryPtr->length - pos; 0297 if (rpos > 0) { 0298 entryPtr->hash = ((entryPtr->hash * 13) + (entryPtr->key[rpos].cell() % 29)) & 0x3fffffff; 0299 } 0300 } 0301 } else { 0302 pos = pos - 1; 0303 for (auto &entryPtr : *stringlist) { 0304 if (pos < entryPtr->length) { 0305 entryPtr->hash = ((entryPtr->hash * 13) + (entryPtr->key[pos].cell() % 29)) & 0x3fffffff; 0306 } 0307 } 0308 } 0309 } 0310 0311 void KSycocaDict::save(QDataStream &str) 0312 { 0313 if (count() == 0) { 0314 d->hashTableSize = 0; 0315 d->hashList.clear(); 0316 str << d->hashTableSize; 0317 str << d->hashList; 0318 return; 0319 } 0320 0321 d->offset = str.device()->pos(); 0322 0323 // qCDebug(SYCOCA) << "KSycocaDict:" << count() << "entries."; 0324 0325 // qCDebug(SYCOCA) << "Calculating hash keys.."; 0326 0327 int maxLength = 0; 0328 // qCDebug(SYCOCA) << "Finding maximum string length"; 0329 for (auto &entryPtr : d->m_stringentries) { 0330 entryPtr->hash = 0; 0331 if (entryPtr->length > maxLength) { 0332 maxLength = entryPtr->length; 0333 } 0334 } 0335 0336 // qCDebug(SYCOCA) << "Max string length=" << maxLength << "existing hashList=" << d->hashList; 0337 0338 // use "almost prime" number for sz (to calculate diversity) and later 0339 // for the table size of big tables 0340 // int sz = d->stringlist.count()*5-1; 0341 unsigned int sz = count() * 4 + 1; 0342 while (!(((sz % 3) && (sz % 5) && (sz % 7) && (sz % 11) && (sz % 13)))) { 0343 sz += 2; 0344 } 0345 0346 d->hashList.clear(); 0347 0348 // Times (with warm caches, i.e. after multiple runs) 0349 // kbuildsycoca5 --noincremental 2.83s user 0.20s system 95% cpu 3.187 total 0350 // kbuildsycoca5 --noincremental 2.74s user 0.25s system 93% cpu 3.205 total 0351 // unittest: 0.50-60 msec per iteration / 0.40-50 msec per iteration 0352 0353 // Now that MimeTypes are not parsed anymore: 0354 // kbuildsycoca5 --noincremental 2.18s user 0.30s system 91% cpu 2.719 total 0355 // kbuildsycoca5 --noincremental 2.07s user 0.34s system 89% cpu 2.681 total 0356 0357 // If I enabled s_maxItems = 50, it goes down to 0358 // but I don't know if that's a good idea. 0359 // kbuildsycoca5 --noincremental 1.73s user 0.31s system 85% cpu 2.397 total 0360 // kbuildsycoca5 --noincremental 1.84s user 0.29s system 95% cpu 2.230 total 0361 0362 // try to limit diversity scan by "predicting" positions 0363 // with high diversity 0364 QList<int> oldvec(maxLength * 2 + 1); 0365 oldvec.fill(0); 0366 int mindiv = 0; 0367 int lastDiv = 0; 0368 0369 while (true) { 0370 int divsum = 0; 0371 int divnum = 0; 0372 0373 int maxDiv = 0; 0374 int maxPos = 0; 0375 for (int pos = -maxLength; pos <= maxLength; ++pos) { 0376 // cut off 0377 if (oldvec[pos + maxLength] < mindiv) { 0378 oldvec[pos + maxLength] = 0; 0379 continue; 0380 } 0381 0382 const int diversity = calcDiversity(&(d->m_stringentries), pos, sz); 0383 if (diversity > maxDiv) { 0384 maxDiv = diversity; 0385 maxPos = pos; 0386 } 0387 oldvec[pos + maxLength] = diversity; 0388 divsum += diversity; 0389 ++divnum; 0390 } 0391 // arbitrary cut-off value 3/4 of average seems to work 0392 if (divnum) { 0393 mindiv = (3 * divsum) / (4 * divnum); 0394 } 0395 0396 if (maxDiv <= lastDiv) { 0397 break; 0398 } 0399 // qCDebug(SYCOCA) << "Max Div=" << maxDiv << "at pos" << maxPos; 0400 lastDiv = maxDiv; 0401 addDiversity(&(d->m_stringentries), maxPos); 0402 d->hashList.append(maxPos); 0403 } 0404 0405 for (auto &entryPtr : d->m_stringentries) { 0406 entryPtr->hash = d->hashKey(entryPtr->keyStr); 0407 } 0408 // fprintf(stderr, "Calculating minimum table size..\n"); 0409 0410 d->hashTableSize = sz; 0411 0412 // qCDebug(SYCOCA) << "hashTableSize=" << sz << "hashList=" << d->hashList << "oldvec=" << oldvec; 0413 0414 struct hashtable_entry { 0415 string_entry *entry; 0416 QList<string_entry *> *duplicates; 0417 qint64 duplicate_offset; 0418 }; 0419 0420 hashtable_entry *hashTable = new hashtable_entry[sz]; 0421 0422 // qCDebug(SYCOCA) << "Clearing hashtable..."; 0423 for (unsigned int i = 0; i < sz; i++) { 0424 hashTable[i].entry = nullptr; 0425 hashTable[i].duplicates = nullptr; 0426 } 0427 0428 // qCDebug(SYCOCA) << "Filling hashtable..."; 0429 for (const auto &entryPtr : d->m_stringentries) { 0430 // qCDebug(SYCOCA) << "entry keyStr=" << entry->keyStr << entry->payload.data() << entry->payload->entryPath(); 0431 const int hash = entryPtr->hash % sz; 0432 if (!hashTable[hash].entry) { 0433 // First entry 0434 hashTable[hash].entry = entryPtr.get(); 0435 } else { 0436 if (!hashTable[hash].duplicates) { 0437 // Second entry, build duplicate list. 0438 hashTable[hash].duplicates = new QList<string_entry *>; 0439 hashTable[hash].duplicates->append(hashTable[hash].entry); 0440 hashTable[hash].duplicate_offset = 0; 0441 } 0442 hashTable[hash].duplicates->append(entryPtr.get()); 0443 } 0444 } 0445 0446 str << d->hashTableSize; 0447 str << d->hashList; 0448 0449 d->offset = str.device()->pos(); // d->offset points to start of hashTable 0450 // qCDebug(SYCOCA) << QString("Start of Hash Table, offset = %1").arg(d->offset,8,16); 0451 0452 // Write the hashtable + the duplicates twice. 0453 // The duplicates are after the normal hashtable, but the offset of each 0454 // duplicate entry is written into the normal hashtable. 0455 for (int pass = 1; pass <= 2; pass++) { 0456 str.device()->seek(d->offset); 0457 // qCDebug(SYCOCA) << QString("Writing hash table (pass #%1)").arg(pass); 0458 for (uint i = 0; i < d->hashTableSize; i++) { 0459 qint32 tmpid; 0460 if (!hashTable[i].entry) { 0461 tmpid = 0; 0462 } else if (!hashTable[i].duplicates) { 0463 tmpid = hashTable[i].entry->payload->offset(); // Positive ID 0464 } else { 0465 tmpid = -hashTable[i].duplicate_offset; // Negative ID 0466 } 0467 str << tmpid; 0468 // qCDebug(SYCOCA) << QString("Hash table : %1").arg(tmpid,8,16); 0469 } 0470 // qCDebug(SYCOCA) << QString("End of Hash Table, offset = %1").arg(str.device()->at(),8,16); 0471 0472 // qCDebug(SYCOCA) << QString("Writing duplicate lists (pass #%1)").arg(pass); 0473 for (uint i = 0; i < d->hashTableSize; i++) { 0474 const QList<string_entry *> *dups = hashTable[i].duplicates; 0475 if (dups) { 0476 hashTable[i].duplicate_offset = str.device()->pos(); 0477 0478 /*qCDebug(SYCOCA) << QString("Duplicate lists: Offset = %1 list_size = %2") .arg(hashTable[i].duplicate_offset,8,16).arg(dups->count()); 0479 */ 0480 for (string_entry *dup : std::as_const(*dups)) { 0481 const qint32 offset = dup->payload->offset(); 0482 if (!offset) { 0483 const QString storageId = dup->payload->storageId(); 0484 qCDebug(SYCOCA) << "about to assert! dict=" << this << "storageId=" << storageId << dup->payload.data(); 0485 if (dup->payload->isType(KST_KService)) { 0486 KService::Ptr service(static_cast<KService *>(dup->payload.data())); 0487 qCDebug(SYCOCA) << service->storageId() << service->entryPath(); 0488 } 0489 // save() must have been called on the entry 0490 Q_ASSERT_X(offset, 0491 "KSycocaDict::save", 0492 QByteArray("entry offset is 0, save() was not called on " + dup->payload->storageId().toLatin1() 0493 + " entryPath=" + dup->payload->entryPath().toLatin1()) 0494 .constData()); 0495 } 0496 str << offset; // Positive ID 0497 str << dup->keyStr; // Key (QString) 0498 } 0499 str << qint32(0); // End of list marker (0) 0500 } 0501 } 0502 // qCDebug(SYCOCA) << QString("End of Dict, offset = %1").arg(str.device()->at(),8,16); 0503 } 0504 0505 // qCDebug(SYCOCA) << "Cleaning up hash table."; 0506 for (uint i = 0; i < d->hashTableSize; i++) { 0507 delete hashTable[i].duplicates; 0508 } 0509 delete[] hashTable; 0510 } 0511 0512 qint32 KSycocaDictPrivate::offsetForKey(const QString &key) const 0513 { 0514 if (!stream || !offset) { 0515 qCWarning(SYCOCA) << "No ksycoca database available! Tried running" << KBUILDSYCOCA_EXENAME << "?"; 0516 return 0; 0517 } 0518 0519 if (hashTableSize == 0) { 0520 return 0; // Unlikely to find anything :-] 0521 } 0522 0523 // Read hash-table data 0524 const uint hash = hashKey(key) % hashTableSize; 0525 // qCDebug(SYCOCA) << "hash is" << hash; 0526 0527 const qint64 off = offset + sizeof(qint32) * hash; 0528 // qCDebug(SYCOCA) << QString("off is %1").arg(off,8,16); 0529 stream->device()->seek(off); 0530 0531 qint32 retOffset; 0532 (*stream) >> retOffset; 0533 return retOffset; 0534 }