25 #include <QtCore/QBitArray> 31 : hash(0), length(_key.length()), keyStr(_key), key(keyStr.unicode()), payload(_payload)
36 const QChar *
const key;
41 class KSycocaDictStringList :
public QList<string_entry*>
44 ~KSycocaDictStringList() {
49 class KSycocaDict::Private
70 KSycocaDictStringList *stringlist;
89 str->device()->seek(offset);
90 (*str) >> test1 >> test2;
91 if ((test1 > 0x000fffff) || (test2 > 1024))
99 str->device()->seek(offset);
100 (*str) >> d->hashTableSize;
101 (*str) >> d->hashList;
102 d->offset = str->device()->pos();
113 if (key.isEmpty())
return;
114 if (!payload)
return;
117 d->stringlist =
new KSycocaDictStringList;
120 string_entry *entry =
new string_entry(key, payload);
121 d->stringlist->append(entry);
127 if (!d || !d->stringlist) {
132 for(KSycocaDictStringList::Iterator it = d->stringlist->begin(); it != d->stringlist->end(); ++it) {
133 string_entry* entry = *it;
134 if (entry->keyStr == key) {
135 d->stringlist->erase(it);
142 kWarning(7011) <<
"key not found:" << key;
151 qint32 offset = d->offsetForKey(key);
163 d->stream->device()->seek(offset);
168 (*d->stream) >> offset;
169 if (offset == 0)
break;
171 (*d->stream) >> dupkey;
173 if (dupkey == key)
return offset;
183 qint32 offset = d->offsetForKey(key);
189 offsetList.append(offset);
196 d->stream->device()->seek(offset);
201 (*d->stream) >> offset;
202 if (offset == 0)
break;
204 (*d->stream) >> dupkey;
207 offsetList.append(offset);
214 if ( !d || !d->stringlist )
return 0;
216 return d->stringlist->count();
226 uint KSycocaDict::Private::hashKey(
const QString &key)
const 228 int len = key.length();
231 for(
int i = 0; i < hashList.count(); i++)
233 int pos = hashList[i];
236 }
else if (pos < 0) {
239 h = ((h * 13) + (key[len-pos].cell() % 29)) & 0x3ffffff;
243 h = ((h * 13) + (key[pos].cell() % 29)) & 0x3ffffff;
267 if (inPos == 0)
return 0;
268 QBitArray matrix(sz);
276 for(KSycocaDictStringList::const_iterator it = stringlist->constBegin(), end = stringlist->constEnd(); it != end; ++it)
278 string_entry* entry = *it;
279 int len = entry->length;
281 uint hash = ((entry->hash * 13) + (entry->key[len-pos].cell() % 29)) & 0x3ffffff;
282 matrix.setBit( hash % sz,
true );
289 for(KSycocaDictStringList::const_iterator it = stringlist->constBegin(), end = stringlist->constEnd(); it != end; ++it)
291 string_entry* entry = *it;
292 if (pos < entry->length) {
293 uint hash = ((entry->hash * 13) + (entry->key[pos].cell() % 29)) & 0x3ffffff;
294 matrix.setBit( hash % sz,
true );
300 return matrix.count(
true);
308 if (pos == 0)
return;
311 for(KSycocaDictStringList::const_iterator it = stringlist->constBegin(), end = stringlist->constEnd(); it != end; ++it)
313 string_entry* entry = *it;
314 int len = entry->length;
316 entry->hash = ((entry->hash * 13) + (entry->key[len-pos].cell() % 29)) & 0x3fffffff;
320 for(KSycocaDictStringList::const_iterator it = stringlist->constBegin(), end = stringlist->constEnd(); it != end; ++it)
322 string_entry* entry = *it;
323 if (pos < entry->length)
324 entry->hash = ((entry->hash * 13) + (entry->key[pos].cell() % 29)) & 0x3fffffff;
335 d->hashTableSize = 0;
337 str << d->hashTableSize;
342 d->offset = str.device()->pos();
350 for(KSycocaDictStringList::const_iterator it = d->stringlist->constBegin(); it != d->stringlist->constEnd(); ++it)
352 string_entry* entry = *it;
354 if (entry->length > maxLength)
355 maxLength = entry->length;
363 register unsigned int sz =
count()*4 + 1;
364 while(!(((sz % 3) && (sz % 5) && (sz % 7) && (sz % 11) && (sz % 13))))
385 QVector<int> oldvec(maxLength*2+1);
392 int divsum=0,divnum=0;
396 for (
int pos = -maxLength; pos <= maxLength; ++pos) {
398 if (oldvec[pos+maxLength] < mindiv) { oldvec[pos+maxLength]=0;
continue; }
401 if (diversity > maxDiv) {
405 oldvec[pos + maxLength] = diversity;
411 mindiv=(3*divsum)/(4*divnum);
413 if (maxDiv <= lastDiv)
418 d->hashList.append(maxPos);
422 for(KSycocaDictStringList::Iterator it = d->stringlist->begin(); it != d->stringlist->end(); ++it) {
423 (*it)->hash = d->hashKey((*it)->keyStr);
427 d->hashTableSize = sz;
431 struct hashtable_entry {
437 hashtable_entry *hashTable =
new hashtable_entry[ sz ];
440 for (
unsigned int i=0; i < sz; i++)
442 hashTable[i].entry = 0;
443 hashTable[i].duplicates = 0;
447 for(KSycocaDictStringList::const_iterator it = d->stringlist->constBegin(); it != d->stringlist->constEnd(); ++it)
449 string_entry* entry = *it;
451 int hash = entry->hash % sz;
452 if (!hashTable[hash].entry)
454 hashTable[hash].entry = entry;
458 if (!hashTable[hash].duplicates)
461 hashTable[hash].duplicates->append(hashTable[hash].entry);
462 hashTable[hash].duplicate_offset = 0;
464 hashTable[hash].duplicates->append(entry);
468 str << d->hashTableSize;
471 d->offset = str.device()->pos();
477 for(
int pass = 1; pass <= 2; pass++)
479 str.device()->seek(d->offset);
481 for(uint i=0; i < d->hashTableSize; i++)
484 if (!hashTable[i].entry)
486 else if (!hashTable[i].duplicates)
487 tmpid = (
qint32) hashTable[i].entry->payload->offset();
489 tmpid = (
qint32) -hashTable[i].duplicate_offset;
496 for(uint i=0; i < d->hashTableSize; i++)
501 hashTable[i].duplicate_offset = str.device()->pos();
507 const qint32 offset = (*dup)->payload->offset();
509 const QString storageId = (*dup)->payload->storageId();
510 kDebug() <<
"about to assert! dict=" <<
this <<
"storageId=" << storageId << (*dup)->payload.data();
516 Q_ASSERT_X( offset,
"KSycocaDict::save",
517 QByteArray(
"entry offset is 0, save() was not called on " 518 + (*dup)->payload->storageId().toLatin1()
520 + (*dup)->payload->entryPath().toLatin1())
524 str << (*dup)->keyStr;
533 for(uint i=0; i < d->hashTableSize; i++)
535 delete hashTable[i].duplicates;
540 qint32 KSycocaDict::Private::offsetForKey(
const QString& key)
const 542 if ( !stream || !offset )
544 kError() <<
"No ksycoca4 database available!" << endl;
548 if (hashTableSize == 0)
552 const uint hash = hashKey(key) % hashTableSize;
557 stream->device()->seek( off );
560 (*stream) >> retOffset;
Can be used to control the lifetime of an object that has derived QSharedData.
void add(const QString &key, const KSycocaEntry::Ptr &payload)
Adds a 'payload' to the dictionary with key 'key'.
void remove(const QString &key)
Removes the 'payload' from the dictionary with key 'key'.
QString storageId() const
Returns a normalized ID suitable for storing in configuration files.
static QDebug kError(bool cond, int area=KDE_DEFAULT_DEBUG_AREA)
QString entryPath() const
void save(QDataStream &str)
Save the dictionary to the stream A reasonable fast hash algorithm will be created.
int find_string(const QString &key) const
Looks up an entry identified by 'key'.
static void addDiversity(KSycocaDictStringList *stringlist, int pos)
uint count() const
The number of entries in the dictionary.
QList< int > findMultiString(const QString &key) const
Looks up all entries identified by 'key'.
static void flagError()
A read error occurs.
static int calcDiversity(KSycocaDictStringList *stringlist, int inPos, uint sz)
void clear()
Reset the dictionary.
static KSharedPtr< T > staticCast(const KSharedPtr< U > &o)
Convert KSharedPtr to KSharedPtr<T>, using a static_cast.
KSycocaDict()
Create an empty dict, for building the database.