1/*
2 This file is part of the KDE libraries
3 SPDX-FileCopyrightText: 1999 Waldo Bastian <bastian@kde.org>
4
5 SPDX-License-Identifier: LGPL-2.0-only
6*/
7
8#include "ksycoca.h"
9#include "ksycocadict_p.h"
10#include "ksycocaentry.h"
11#include "sycocadebug.h"
12#include <kservice.h>
13
14#include <QBitArray>
15#include <QIODevice>
16#include <QList>
17
18namespace
19{
20struct string_entry {
21 string_entry(const QString &_key, const KSycocaEntry::Ptr &_payload)
22 : hash(0)
23 , length(_key.length())
24 , keyStr(_key)
25 , key(keyStr.unicode())
26 , payload(_payload)
27 {
28 }
29 uint hash;
30 const int length;
31 const QString keyStr;
32 const QChar *const key; // always points to keyStr.unicode(); just an optimization
33 const KSycocaEntry::Ptr payload;
34};
35}
36
37class KSycocaDictPrivate
38{
39public:
40 KSycocaDictPrivate()
41 : stream(nullptr)
42 , offset(0)
43 , hashTableSize(0)
44 {
45 }
46
47 ~KSycocaDictPrivate()
48 {
49 }
50
51 // Helper for find_string and findMultiString
52 qint32 offsetForKey(const QString &key) const;
53
54 // Calculate hash - can be used during loading and during saving.
55 quint32 hashKey(const QString &key) const;
56
57 std::vector<std::unique_ptr<string_entry>> m_stringentries;
58 QDataStream *stream;
59 qint64 offset;
60 quint32 hashTableSize;
61 QList<qint32> hashList;
62};
63
64KSycocaDict::KSycocaDict()
65 : d(new KSycocaDictPrivate)
66{
67}
68
69KSycocaDict::KSycocaDict(QDataStream *str, int offset)
70 : d(new KSycocaDictPrivate)
71{
72 d->stream = str;
73 d->offset = offset;
74
75 quint32 test1;
76 quint32 test2;
77 str->device()->seek(pos: offset);
78 (*str) >> test1 >> test2;
79 if ((test1 > 0x000fffff) || (test2 > 1024)) {
80 KSycoca::flagError();
81 d->hashTableSize = 0;
82 d->offset = 0;
83 return;
84 }
85
86 str->device()->seek(pos: offset);
87 (*str) >> d->hashTableSize;
88 (*str) >> d->hashList;
89 d->offset = str->device()->pos(); // Start of hashtable
90}
91
92KSycocaDict::~KSycocaDict() = default;
93
94void KSycocaDict::add(const QString &key, const KSycocaEntry::Ptr &payload)
95{
96 if (key.isEmpty()) {
97 return; // Not allowed (should never happen)
98 }
99 if (!payload) {
100 return; // Not allowed!
101 }
102
103 d->m_stringentries.push_back(x: std::make_unique<string_entry>(args: key, args: payload));
104}
105
106void KSycocaDict::remove(const QString &key)
107{
108 if (!d) {
109 return;
110 }
111
112 auto it = std::find_if(first: d->m_stringentries.begin(), last: d->m_stringentries.end(), pred: [&key](const std::unique_ptr<string_entry> &entry) {
113 return entry->keyStr == key;
114 });
115
116 if (it != d->m_stringentries.end()) {
117 d->m_stringentries.erase(position: it);
118 } else {
119 qCDebug(SYCOCA) << "key not found:" << key;
120 }
121}
122
123int KSycocaDict::find_string(const QString &key) const
124{
125 Q_ASSERT(d);
126
127 // qCDebug(SYCOCA) << QString("KSycocaDict::find_string(%1)").arg(key);
128 qint32 offset = d->offsetForKey(key);
129
130 // qCDebug(SYCOCA) << QString("offset is %1").arg(offset,8,16);
131 if (offset == 0) {
132 return 0;
133 }
134
135 if (offset > 0) {
136 return offset; // Positive ID
137 }
138
139 // Lookup duplicate list.
140 offset = -offset;
141
142 d->stream->device()->seek(pos: offset);
143 // qCDebug(SYCOCA) << QString("Looking up duplicate list at %1").arg(offset,8,16);
144
145 while (true) {
146 (*d->stream) >> offset;
147 if (offset == 0) {
148 break;
149 }
150 QString dupkey;
151 (*d->stream) >> dupkey;
152 // qCDebug(SYCOCA) << QString(">> %1 %2").arg(offset,8,16).arg(dupkey);
153 if (dupkey == key) {
154 return offset;
155 }
156 }
157 // qCDebug(SYCOCA) << "Not found!";
158
159 return 0;
160}
161
162QList<int> KSycocaDict::findMultiString(const QString &key) const
163{
164 qint32 offset = d->offsetForKey(key);
165 QList<int> offsetList;
166 if (offset == 0) {
167 return offsetList;
168 }
169
170 if (offset > 0) { // Positive ID: one entry found
171 offsetList.append(t: offset);
172 return offsetList;
173 }
174
175 // Lookup duplicate list.
176 offset = -offset;
177
178 d->stream->device()->seek(pos: offset);
179 // qCDebug(SYCOCA) << QString("Looking up duplicate list at %1").arg(offset,8,16);
180
181 while (true) {
182 (*d->stream) >> offset;
183 if (offset == 0) {
184 break;
185 }
186 QString dupkey;
187 (*d->stream) >> dupkey;
188 // qCDebug(SYCOCA) << QString(">> %1 %2").arg(offset,8,16).arg(dupkey);
189 if (dupkey == key) {
190 offsetList.append(t: offset);
191 }
192 }
193 return offsetList;
194}
195
196uint KSycocaDict::count() const
197{
198 if (!d) {
199 return 0;
200 }
201
202 return d->m_stringentries.size();
203}
204
205void KSycocaDict::clear()
206{
207 d.reset();
208}
209
210uint KSycocaDictPrivate::hashKey(const QString &key) const
211{
212 int len = key.length();
213 uint h = 0;
214
215 for (int i = 0; i < hashList.count(); i++) {
216 int pos = hashList[i];
217 if (pos == 0) {
218 continue;
219 } else if (pos < 0) {
220 pos = -pos;
221 if (pos < len) {
222 h = ((h * 13) + (key[len - pos].cell() % 29)) & 0x3ffffff;
223 }
224 } else {
225 pos = pos - 1;
226 if (pos < len) {
227 h = ((h * 13) + (key[pos].cell() % 29)) & 0x3ffffff;
228 }
229 }
230 }
231 return h;
232}
233
234// If we have the strings
235// hello
236// world
237// kde
238// Then we end up with
239// ABCDE
240// where A = diversity of 'h' + 'w' + 'k' etc.
241// Also, diversity(-2) == 'l'+'l'+'d' (second character from the end)
242
243// The hasList is used for hashing:
244// hashList = (-2, 1, 3) means that the hash key comes from
245// the 2nd character from the right, then the 1st from the left, then the 3rd from the left.
246
247// Calculate the diversity of the strings at position 'pos'
248// NOTE: this code is slow, it takes 12% of the _overall_ `kbuildsycoca5 --noincremental` running time
249static int calcDiversity(std::vector<std::unique_ptr<string_entry>> *stringlist, int inPos, uint sz)
250{
251 if (inPos == 0) {
252 return 0;
253 }
254 QBitArray matrix(sz);
255 int pos;
256
257 // static const int s_maxItems = 50;
258 // int numItem = 0;
259
260 if (inPos < 0) {
261 pos = -inPos;
262 for (const auto &entryPtr : *stringlist) {
263 const int rpos = entryPtr->length - pos;
264 if (rpos > 0) {
265 const uint hash = ((entryPtr->hash * 13) + (entryPtr->key[rpos].cell() % 29)) & 0x3ffffff;
266 matrix.setBit(i: hash % sz, val: true);
267 }
268 // if (++numItem == s_maxItems)
269 // break;
270 }
271 } else {
272 pos = inPos - 1;
273 for (const auto &entryPtr : *stringlist) {
274 if (pos < entryPtr->length) {
275 const uint hash = ((entryPtr->hash * 13) + (entryPtr->key[pos].cell() % 29)) & 0x3ffffff;
276 matrix.setBit(i: hash % sz, val: true);
277 }
278 // if (++numItem == s_maxItems)
279 // break;
280 }
281 }
282 return matrix.count(on: true);
283}
284
285//
286// Add the diversity of the strings at position 'pos'
287static void addDiversity(std::vector<std::unique_ptr<string_entry>> *stringlist, int pos)
288{
289 if (pos == 0) {
290 return;
291 }
292
293 if (pos < 0) {
294 pos = -pos;
295 for (auto &entryPtr : *stringlist) {
296 const int rpos = entryPtr->length - pos;
297 if (rpos > 0) {
298 entryPtr->hash = ((entryPtr->hash * 13) + (entryPtr->key[rpos].cell() % 29)) & 0x3fffffff;
299 }
300 }
301 } else {
302 pos = pos - 1;
303 for (auto &entryPtr : *stringlist) {
304 if (pos < entryPtr->length) {
305 entryPtr->hash = ((entryPtr->hash * 13) + (entryPtr->key[pos].cell() % 29)) & 0x3fffffff;
306 }
307 }
308 }
309}
310
311void KSycocaDict::save(QDataStream &str)
312{
313 if (count() == 0) {
314 d->hashTableSize = 0;
315 d->hashList.clear();
316 str << d->hashTableSize;
317 str << d->hashList;
318 return;
319 }
320
321 d->offset = str.device()->pos();
322
323 // qCDebug(SYCOCA) << "KSycocaDict:" << count() << "entries.";
324
325 // qCDebug(SYCOCA) << "Calculating hash keys..";
326
327 int maxLength = 0;
328 // qCDebug(SYCOCA) << "Finding maximum string length";
329 for (auto &entryPtr : d->m_stringentries) {
330 entryPtr->hash = 0;
331 if (entryPtr->length > maxLength) {
332 maxLength = entryPtr->length;
333 }
334 }
335
336 // qCDebug(SYCOCA) << "Max string length=" << maxLength << "existing hashList=" << d->hashList;
337
338 // use "almost prime" number for sz (to calculate diversity) and later
339 // for the table size of big tables
340 // int sz = d->stringlist.count()*5-1;
341 unsigned int sz = count() * 4 + 1;
342 while (!(((sz % 3) && (sz % 5) && (sz % 7) && (sz % 11) && (sz % 13)))) {
343 sz += 2;
344 }
345
346 d->hashList.clear();
347
348 // Times (with warm caches, i.e. after multiple runs)
349 // kbuildsycoca5 --noincremental 2.83s user 0.20s system 95% cpu 3.187 total
350 // kbuildsycoca5 --noincremental 2.74s user 0.25s system 93% cpu 3.205 total
351 // unittest: 0.50-60 msec per iteration / 0.40-50 msec per iteration
352
353 // Now that MimeTypes are not parsed anymore:
354 // kbuildsycoca5 --noincremental 2.18s user 0.30s system 91% cpu 2.719 total
355 // kbuildsycoca5 --noincremental 2.07s user 0.34s system 89% cpu 2.681 total
356
357 // If I enabled s_maxItems = 50, it goes down to
358 // but I don't know if that's a good idea.
359 // kbuildsycoca5 --noincremental 1.73s user 0.31s system 85% cpu 2.397 total
360 // kbuildsycoca5 --noincremental 1.84s user 0.29s system 95% cpu 2.230 total
361
362 // try to limit diversity scan by "predicting" positions
363 // with high diversity
364 QList<int> oldvec(maxLength * 2 + 1);
365 oldvec.fill(t: 0);
366 int mindiv = 0;
367 int lastDiv = 0;
368
369 while (true) {
370 int divsum = 0;
371 int divnum = 0;
372
373 int maxDiv = 0;
374 int maxPos = 0;
375 for (int pos = -maxLength; pos <= maxLength; ++pos) {
376 // cut off
377 if (oldvec[pos + maxLength] < mindiv) {
378 oldvec[pos + maxLength] = 0;
379 continue;
380 }
381
382 const int diversity = calcDiversity(stringlist: &(d->m_stringentries), inPos: pos, sz);
383 if (diversity > maxDiv) {
384 maxDiv = diversity;
385 maxPos = pos;
386 }
387 oldvec[pos + maxLength] = diversity;
388 divsum += diversity;
389 ++divnum;
390 }
391 // arbitrary cut-off value 3/4 of average seems to work
392 if (divnum) {
393 mindiv = (3 * divsum) / (4 * divnum);
394 }
395
396 if (maxDiv <= lastDiv) {
397 break;
398 }
399 // qCDebug(SYCOCA) << "Max Div=" << maxDiv << "at pos" << maxPos;
400 lastDiv = maxDiv;
401 addDiversity(stringlist: &(d->m_stringentries), pos: maxPos);
402 d->hashList.append(t: maxPos);
403 }
404
405 for (auto &entryPtr : d->m_stringentries) {
406 entryPtr->hash = d->hashKey(key: entryPtr->keyStr);
407 }
408 // fprintf(stderr, "Calculating minimum table size..\n");
409
410 d->hashTableSize = sz;
411
412 // qCDebug(SYCOCA) << "hashTableSize=" << sz << "hashList=" << d->hashList << "oldvec=" << oldvec;
413
414 struct hashtable_entry {
415 string_entry *entry;
416 QList<string_entry *> *duplicates;
417 qint64 duplicate_offset;
418 };
419
420 hashtable_entry *hashTable = new hashtable_entry[sz];
421
422 // qCDebug(SYCOCA) << "Clearing hashtable...";
423 for (unsigned int i = 0; i < sz; i++) {
424 hashTable[i].entry = nullptr;
425 hashTable[i].duplicates = nullptr;
426 }
427
428 // qCDebug(SYCOCA) << "Filling hashtable...";
429 for (const auto &entryPtr : d->m_stringentries) {
430 // qCDebug(SYCOCA) << "entry keyStr=" << entry->keyStr << entry->payload.data() << entry->payload->entryPath();
431 const int hash = entryPtr->hash % sz;
432 if (!hashTable[hash].entry) {
433 // First entry
434 hashTable[hash].entry = entryPtr.get();
435 } else {
436 if (!hashTable[hash].duplicates) {
437 // Second entry, build duplicate list.
438 hashTable[hash].duplicates = new QList<string_entry *>;
439 hashTable[hash].duplicates->append(t: hashTable[hash].entry);
440 hashTable[hash].duplicate_offset = 0;
441 }
442 hashTable[hash].duplicates->append(t: entryPtr.get());
443 }
444 }
445
446 str << d->hashTableSize;
447 str << d->hashList;
448
449 d->offset = str.device()->pos(); // d->offset points to start of hashTable
450 // qCDebug(SYCOCA) << QString("Start of Hash Table, offset = %1").arg(d->offset,8,16);
451
452 // Write the hashtable + the duplicates twice.
453 // The duplicates are after the normal hashtable, but the offset of each
454 // duplicate entry is written into the normal hashtable.
455 for (int pass = 1; pass <= 2; pass++) {
456 str.device()->seek(pos: d->offset);
457 // qCDebug(SYCOCA) << QString("Writing hash table (pass #%1)").arg(pass);
458 for (uint i = 0; i < d->hashTableSize; i++) {
459 qint32 tmpid;
460 if (!hashTable[i].entry) {
461 tmpid = 0;
462 } else if (!hashTable[i].duplicates) {
463 tmpid = hashTable[i].entry->payload->offset(); // Positive ID
464 } else {
465 tmpid = -hashTable[i].duplicate_offset; // Negative ID
466 }
467 str << tmpid;
468 // qCDebug(SYCOCA) << QString("Hash table : %1").arg(tmpid,8,16);
469 }
470 // qCDebug(SYCOCA) << QString("End of Hash Table, offset = %1").arg(str.device()->at(),8,16);
471
472 // qCDebug(SYCOCA) << QString("Writing duplicate lists (pass #%1)").arg(pass);
473 for (uint i = 0; i < d->hashTableSize; i++) {
474 const QList<string_entry *> *dups = hashTable[i].duplicates;
475 if (dups) {
476 hashTable[i].duplicate_offset = str.device()->pos();
477
478 /*qCDebug(SYCOCA) << QString("Duplicate lists: Offset = %1 list_size = %2") .arg(hashTable[i].duplicate_offset,8,16).arg(dups->count());
479 */
480 for (string_entry *dup : std::as_const(t: *dups)) {
481 const qint32 offset = dup->payload->offset();
482 if (!offset) {
483 const QString storageId = dup->payload->storageId();
484 qCDebug(SYCOCA) << "about to assert! dict=" << this << "storageId=" << storageId << dup->payload.data();
485 if (dup->payload->isType(t: KST_KService)) {
486 KService::Ptr service(static_cast<KService *>(dup->payload.data()));
487 qCDebug(SYCOCA) << service->storageId() << service->entryPath();
488 }
489 // save() must have been called on the entry
490 Q_ASSERT_X(offset,
491 "KSycocaDict::save",
492 QByteArray("entry offset is 0, save() was not called on " + dup->payload->storageId().toLatin1()
493 + " entryPath=" + dup->payload->entryPath().toLatin1())
494 .constData());
495 }
496 str << offset; // Positive ID
497 str << dup->keyStr; // Key (QString)
498 }
499 str << qint32(0); // End of list marker (0)
500 }
501 }
502 // qCDebug(SYCOCA) << QString("End of Dict, offset = %1").arg(str.device()->at(),8,16);
503 }
504
505 // qCDebug(SYCOCA) << "Cleaning up hash table.";
506 for (uint i = 0; i < d->hashTableSize; i++) {
507 delete hashTable[i].duplicates;
508 }
509 delete[] hashTable;
510}
511
512qint32 KSycocaDictPrivate::offsetForKey(const QString &key) const
513{
514 if (!stream || !offset) {
515 qCWarning(SYCOCA) << "No ksycoca database available! Tried running" << KBUILDSYCOCA_EXENAME << "?";
516 return 0;
517 }
518
519 if (hashTableSize == 0) {
520 return 0; // Unlikely to find anything :-]
521 }
522
523 // Read hash-table data
524 const uint hash = hashKey(key) % hashTableSize;
525 // qCDebug(SYCOCA) << "hash is" << hash;
526
527 const qint64 off = offset + sizeof(qint32) * hash;
528 // qCDebug(SYCOCA) << QString("off is %1").arg(off,8,16);
529 stream->device()->seek(pos: off);
530
531 qint32 retOffset;
532 (*stream) >> retOffset;
533 return retOffset;
534}
535

source code of kservice/src/sycoca/ksycocadict.cpp