19#include "tdesycocadict.h"
20#include "tdesycocaentry.h"
24#include <tqvaluelist.h>
32 { keyStr = _key;
key = keyStr.unicode(); length = keyStr.length(); payload = _payload; hash = 0; }
41template class TQPtrList<string_entry>;
43class KSycocaDictStringList :
public TQPtrList<string_entry>
46 KSycocaDictStringList();
49KSycocaDictStringList::KSycocaDictStringList()
54KSycocaDict::KSycocaDict()
55 : d(0), mStr(0), mOffset(0)
59KSycocaDict::KSycocaDict(TQDataStream *str,
int offset)
60 : d(0), mStr(str), mOffset(offset)
62 TQ_UINT32 test1, test2;
63 str->device()->at(offset);
64 (*str) >> test1 >> test2;
65 if ((test1 > 0x000fffff) || (test2 > 1024))
73 str->device()->at(offset);
74 (*str) >> mHashTableSize;
76 mOffset = str->device()->at();
79KSycocaDict::~KSycocaDict()
85KSycocaDict::add(
const TQString &key,
KSycocaEntry *payload)
87 if (
key.isEmpty())
return;
91 d =
new KSycocaDictStringList();
94 string_entry *entry=
new string_entry(key, payload);
99KSycocaDict::remove(
const TQString &key)
103 for(string_entry *entry=d->first(); entry; entry = d->next())
105 if (entry->keyStr == key)
115KSycocaDict::find_string(
const TQString &key )
119 if (!mStr || !mOffset)
125 if (mHashTableSize == 0)
129 uint hash = hashKey(key) % mHashTableSize;
132 uint off = mOffset+
sizeof(TQ_INT32)*hash;
134 mStr->device()->at( off );
149 mStr->device()->at(offset);
155 if (offset == 0)
break;
159 if (dupkey == key)
return offset;
182KSycocaDict::hashKey(
const TQString &key)
184 int l =
key.length();
187 for(uint i = 0; i < mHashList.count(); i++)
189 int pos = mHashList[i];
194 h = ((h * 13) + (key[l-pos].cell() % 29)) & 0x3ffffff;
200 h = ((h * 13) + (key[pos].cell() % 29)) & 0x3ffffff;
209calcDiversity(KSycocaDictStringList *d,
int pos,
int sz)
211 if (pos == 0)
return 0;
212 bool *matrix = (
bool *) calloc(sz,
sizeof(
bool));
218 for(string_entry *entry=d->first(); entry; entry = d->next())
220 int l = entry->length;
221 if (pos < l && pos != 0)
223 uint hash = ((entry->hash * 13) + (entry->key[l-pos].cell() % 29)) & 0x3ffffff;
224 matrix[ hash % usz ] =
true;
231 for(string_entry *entry=d->first(); entry; entry = d->next())
233 if (pos < entry->length)
235 uint hash = ((entry->hash * 13) + (entry->key[pos].cell() % 29)) & 0x3ffffff;
236 matrix[ hash % usz ] =
true;
241 for(
int i=0;i< sz;i++)
242 if (matrix[i]) diversity++;
244 free((
void *) matrix);
252addDiversity(KSycocaDictStringList *d,
int pos)
254 if (pos == 0)
return;
258 for(string_entry *entry=d->first(); entry; entry = d->next())
260 int l = entry->length;
262 entry->hash = ((entry->hash * 13) + (entry->key[l-pos].cell() % 29)) & 0x3fffffff;
268 for(string_entry *entry=d->first(); entry; entry = d->next())
270 if (pos < entry->length)
271 entry->hash = ((entry->hash * 13) + (entry->key[pos].cell() % 29)) & 0x3fffffff;
278KSycocaDict::save(TQDataStream &str)
284 str << mHashTableSize;
289 mOffset = str.device()->at();
297 for(string_entry *entry=d->first(); entry; entry = d->next())
300 if (entry->length > maxLength)
301 maxLength = entry->length;
309 unsigned int sz = count()*4 + 1;
310 while(!(((sz % 3) && (sz % 5) && (sz % 7) && (sz % 11) && (sz % 13)))) sz+=2;
320 int *oldvec=
new int[maxLength*2+1];
321 for (
int i=0; i<(maxLength*2+1); i++) oldvec[i]=0;
326 int divsum=0,divnum=0;
330 for(
int pos=-maxLength; pos <= maxLength; pos++)
333 if (oldvec[pos+maxLength]<mindiv)
334 { oldvec[pos+maxLength]=0;
continue; }
336 int diversity = calcDiversity(d, pos, sz);
337 if (diversity > maxDiv)
342 oldvec[pos+maxLength]=diversity;
343 divsum+=diversity; divnum++;
347 mindiv=(3*divsum)/(4*divnum);
349 if (maxDiv <= lastDiv)
353 addDiversity(d, maxPos);
354 mHashList.append(maxPos);
359 for(string_entry *entry=d->first(); entry; entry = d->next())
361 entry->hash = hashKey(entry->keyStr);
367 struct hashtable_entry {
369 TQPtrList<string_entry> *duplicates;
370 int duplicate_offset;
373 hashtable_entry *hashTable =
new hashtable_entry[ sz ];
376 for (
unsigned int i=0; i < sz; i++)
378 hashTable[i].entry = 0;
379 hashTable[i].duplicates = 0;
383 for(string_entry *entry=d->first(); entry; entry = d->next())
385 int hash = entry->hash % sz;
386 if (!hashTable[hash].entry)
388 hashTable[hash].entry = entry;
392 if (!hashTable[hash].duplicates)
394 hashTable[hash].duplicates =
new TQPtrList<string_entry>();
395 hashTable[hash].duplicates->append(hashTable[hash].entry);
396 hashTable[hash].duplicate_offset = 0;
398 hashTable[hash].duplicates->append(entry);
402 str << mHashTableSize;
405 mOffset = str.device()->at();
408 for(
int pass = 1; pass <= 2; pass++)
410 str.device()->at(mOffset);
412 for(uint i=0; i < mHashTableSize; i++)
415 if (!hashTable[i].entry)
416 tmpid = (TQ_INT32) 0;
417 else if (!hashTable[i].duplicates)
418 tmpid = (TQ_INT32) hashTable[i].entry->payload->offset();
420 tmpid = (TQ_INT32) -hashTable[i].duplicate_offset;
427 for(uint i=0; i < mHashTableSize; i++)
429 if (hashTable[i].duplicates)
431 TQPtrList<string_entry> *dups = hashTable[i].duplicates;
432 hashTable[i].duplicate_offset = str.device()->at();
436 for(string_entry *dup = dups->first(); dup; dup=dups->next())
438 str << (TQ_INT32) dup->payload->offset();
448 for(uint i=0; i < mHashTableSize; i++)
450 delete hashTable[i].duplicates;
Base class for all Sycoca entries.
kdbgstream kdError(int area=0)
Returns an error stream.
kdbgstream & endl(kdbgstream &s)
Prints an "\n".