• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • tdecore
 

tdecore

  • tdecore
tdesycocadict.cpp
1 /* This file is part of the KDE libraries
2  * Copyright (C) 1999 Waldo Bastian <bastian@kde.org>
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 #include "tdesycocadict.h"
20 #include "tdesycocaentry.h"
21 #include "tdesycoca.h"
22 
23 #include <tqptrlist.h>
24 #include <tqvaluelist.h>
25 #include <kdebug.h>
26 #include <stdlib.h>
27 
28 namespace
29 {
30 struct string_entry {
31  string_entry(TQString _key, KSycocaEntry *_payload)
32  { keyStr = _key; key = keyStr.unicode(); length = keyStr.length(); payload = _payload; hash = 0; }
33  uint hash;
34  int length;
35  const TQChar *key;
36  TQString keyStr;
37  KSycocaEntry *payload;
38 };
39 }
40 
41 template class TQPtrList<string_entry>;
42 
43 class KSycocaDictStringList : public TQPtrList<string_entry>
44 {
45 public:
46  KSycocaDictStringList();
47 };
48 
49 KSycocaDictStringList::KSycocaDictStringList()
50 {
51  setAutoDelete(true);
52 }
53 
54 KSycocaDict::KSycocaDict()
55  : d(0), mStr(0), mOffset(0)
56 {
57 }
58 
59 KSycocaDict::KSycocaDict(TQDataStream *str, int offset)
60  : d(0), mStr(str), mOffset(offset)
61 {
62  TQ_UINT32 test1, test2;
63  str->device()->at(offset);
64  (*str) >> test1 >> test2;
65  if ((test1 > 0x000fffff) || (test2 > 1024))
66  {
67  KSycoca::flagError();
68  mHashTableSize = 0;
69  mOffset = 0;
70  return;
71  }
72 
73  str->device()->at(offset);
74  (*str) >> mHashTableSize;
75  (*str) >> mHashList;
76  mOffset = str->device()->at(); // Start of hashtable
77 }
78 
79 KSycocaDict::~KSycocaDict()
80 {
81  delete d;
82 }
83 
84 void
85 KSycocaDict::add(const TQString &key, KSycocaEntry *payload)
86 {
87  if (key.isEmpty()) return; // Not allowed (should never happen)
88  if (!payload) return; // Not allowed!
89  if (!d)
90  {
91  d = new KSycocaDictStringList();
92  }
93 
94  string_entry *entry= new string_entry(key, payload);
95  d->append(entry);
96 }
97 
98 void
99 KSycocaDict::remove(const TQString &key)
100 {
101  if (d)
102  {
103  for(string_entry *entry=d->first(); entry; entry = d->next())
104  {
105  if (entry->keyStr == key)
106  {
107  d->remove();
108  break;
109  }
110  }
111  }
112 }
113 
114 int
115 KSycocaDict::find_string(const TQString &key )
116 {
117  //kdDebug(7011) << TQString("KSycocaDict::find_string(%1)").arg(key) << endl;
118 
119  if (!mStr || !mOffset)
120  {
121  kdError(7011) << "No database available!" << endl;
122  return 0;
123  }
124 
125  if (mHashTableSize == 0)
126  return 0; // Unlikely to find anything :-]
127 
128  // Read hash-table data
129  uint hash = hashKey(key) % mHashTableSize;
130  //kdDebug(7011) << TQString("hash is %1").arg(hash) << endl;
131 
132  uint off = mOffset+sizeof(TQ_INT32)*hash;
133  //kdDebug(7011) << TQString("off is %1").arg(off,8,16) << endl;
134  mStr->device()->at( off );
135 
136  TQ_INT32 offset;
137  (*mStr) >> offset;
138 
139  //kdDebug(7011) << TQString("offset is %1").arg(offset,8,16) << endl;
140  if (offset == 0)
141  return 0;
142 
143  if (offset > 0)
144  return offset; // Positive ID
145 
146  // Lookup duplicate list.
147  offset = -offset;
148 
149  mStr->device()->at(offset);
150  //kdDebug(7011) << TQString("Looking up duplicate list at %1").arg(offset,8,16) << endl;
151 
152  while(true)
153  {
154  (*mStr) >> offset;
155  if (offset == 0) break;
156  TQString dupkey;
157  (*mStr) >> dupkey;
158  //kdDebug(7011) << TQString(">> %1 %2").arg(offset,8,16).arg(dupkey) << endl;
159  if (dupkey == key) return offset;
160  }
161  //kdWarning(7011) << "Not found!" << endl;
162 
163  return 0;
164 }
165 
166 uint
167 KSycocaDict::count()
168 {
169  if (!d) return 0;
170 
171  return d->count();
172 }
173 
174 void
175 KSycocaDict::clear()
176 {
177  delete d;
178  d = 0;
179 }
180 
181 uint
182 KSycocaDict::hashKey( const TQString &key)
183 {
184  int l = key.length();
185  uint h = 0;
186 
187  for(uint i = 0; i < mHashList.count(); i++)
188  {
189  int pos = mHashList[i];
190  if (pos < 0)
191  {
192  pos = -pos-1;
193  if (pos < l)
194  h = ((h * 13) + (key[l-pos].cell() % 29)) & 0x3ffffff;
195  }
196  else
197  {
198  pos = pos-1;
199  if (pos < l)
200  h = ((h * 13) + (key[pos].cell() % 29)) & 0x3ffffff;
201  }
202  }
203  return h;
204 }
205 
206 //
207 // Calculate the diversity of the strings at position 'pos'
208 static int
209 calcDiversity(KSycocaDictStringList *d, int pos, int sz)
210 {
211  if (pos == 0) return 0;
212  bool *matrix = (bool *) calloc(sz, sizeof(bool));
213  uint usz = sz;
214 
215  if (pos < 0)
216  {
217  pos = -pos-1;
218  for(string_entry *entry=d->first(); entry; entry = d->next())
219  {
220  int l = entry->length;
221  if (pos < l && pos != 0)
222  {
223  uint hash = ((entry->hash * 13) + (entry->key[l-pos].cell() % 29)) & 0x3ffffff;
224  matrix[ hash % usz ] = true;
225  }
226  }
227  }
228  else
229  {
230  pos = pos-1;
231  for(string_entry *entry=d->first(); entry; entry = d->next())
232  {
233  if (pos < entry->length)
234  {
235  uint hash = ((entry->hash * 13) + (entry->key[pos].cell() % 29)) & 0x3ffffff;
236  matrix[ hash % usz ] = true;
237  }
238  }
239  }
240  int diversity = 0;
241  for(int i=0;i< sz;i++)
242  if (matrix[i]) diversity++;
243 
244  free((void *) matrix);
245 
246  return diversity;
247 }
248 
249 //
250 // Add the diversity of the strings at position 'pos'
251 static void
252 addDiversity(KSycocaDictStringList *d, int pos)
253 {
254  if (pos == 0) return;
255  if (pos < 0)
256  {
257  pos = -pos-1;
258  for(string_entry *entry=d->first(); entry; entry = d->next())
259  {
260  int l = entry->length;
261  if (pos < l)
262  entry->hash = ((entry->hash * 13) + (entry->key[l-pos].cell() % 29)) & 0x3fffffff;
263  }
264  }
265  else
266  {
267  pos = pos - 1;
268  for(string_entry *entry=d->first(); entry; entry = d->next())
269  {
270  if (pos < entry->length)
271  entry->hash = ((entry->hash * 13) + (entry->key[pos].cell() % 29)) & 0x3fffffff;
272  }
273  }
274 }
275 
276 
277 void
278 KSycocaDict::save(TQDataStream &str)
279 {
280  if (count() == 0)
281  {
282  mHashTableSize = 0;
283  mHashList.clear();
284  str << mHashTableSize;
285  str << mHashList;
286  return;
287  }
288 
289  mOffset = str.device()->at();
290 
291  //kdDebug(7011) << TQString("KSycocaDict: %1 entries.").arg(count()) << endl;
292 
293  //kdDebug(7011) << "Calculating hash keys.." << endl;
294 
295  int maxLength = 0;
296  //kdDebug(7011) << "Finding maximum string length" << endl;
297  for(string_entry *entry=d->first(); entry; entry = d->next())
298  {
299  entry->hash = 0;
300  if (entry->length > maxLength)
301  maxLength = entry->length;
302  }
303 
304  //kdDebug(7011) << TQString("Max string length = %1").arg(maxLength) << endl;
305 
306  // use "almost prime" number for sz (to calculate diversity) and later
307  // for the table size of big tables
308  // int sz = d->count()*5-1;
309  unsigned int sz = count()*4 + 1;
310  while(!(((sz % 3) && (sz % 5) && (sz % 7) && (sz % 11) && (sz % 13)))) sz+=2;
311 
312  int maxDiv = 0;
313  int maxPos = 0;
314  int lastDiv = 0;
315 
316  mHashList.clear();
317 
318  // try to limit diversity scan by "predicting" positions
319  // with high diversity
320  int *oldvec=new int[maxLength*2+1];
321  for (int i=0; i<(maxLength*2+1); i++) oldvec[i]=0;
322  int mindiv=0;
323 
324  while(true)
325  {
326  int divsum=0,divnum=0;
327 
328  maxDiv = 0;
329  maxPos = 0;
330  for(int pos=-maxLength; pos <= maxLength; pos++)
331  {
332  // cut off
333  if (oldvec[pos+maxLength]<mindiv)
334  { oldvec[pos+maxLength]=0; continue; }
335 
336  int diversity = calcDiversity(d, pos, sz);
337  if (diversity > maxDiv)
338  {
339  maxDiv = diversity;
340  maxPos = pos;
341  }
342  oldvec[pos+maxLength]=diversity;
343  divsum+=diversity; divnum++;
344  }
345  // arbitrary cut-off value 3/4 of average seems to work
346  if (divnum)
347  mindiv=(3*divsum)/(4*divnum);
348 
349  if (maxDiv <= lastDiv)
350  break;
351  // tqWarning("Max Div = %d at pos %d", maxDiv, maxPos);
352  lastDiv = maxDiv;
353  addDiversity(d, maxPos);
354  mHashList.append(maxPos);
355  }
356 
357  delete [] oldvec;
358 
359  for(string_entry *entry=d->first(); entry; entry = d->next())
360  {
361  entry->hash = hashKey(entry->keyStr);
362  }
363 // fprintf(stderr, "Calculating minimum table size..\n");
364 
365  mHashTableSize = sz;
366 
367  struct hashtable_entry {
368  string_entry *entry;
369  TQPtrList<string_entry> *duplicates;
370  int duplicate_offset;
371  };
372 
373  hashtable_entry *hashTable = new hashtable_entry[ sz ];
374 
375  //kdDebug(7011) << "Clearing hashtable..." << endl;
376  for (unsigned int i=0; i < sz; i++)
377  {
378  hashTable[i].entry = 0;
379  hashTable[i].duplicates = 0;
380  }
381 
382  //kdDebug(7011) << "Filling hashtable..." << endl;
383  for(string_entry *entry=d->first(); entry; entry = d->next())
384  {
385  int hash = entry->hash % sz;
386  if (!hashTable[hash].entry)
387  { // First entry
388  hashTable[hash].entry = entry;
389  }
390  else
391  {
392  if (!hashTable[hash].duplicates)
393  { // Second entry, build duplicate list.
394  hashTable[hash].duplicates = new TQPtrList<string_entry>();
395  hashTable[hash].duplicates->append(hashTable[hash].entry);
396  hashTable[hash].duplicate_offset = 0;
397  }
398  hashTable[hash].duplicates->append(entry);
399  }
400  }
401 
402  str << mHashTableSize;
403  str << mHashList;
404 
405  mOffset = str.device()->at(); // mOffset points to start of hashTable
406  //kdDebug(7011) << TQString("Start of Hash Table, offset = %1").arg(mOffset,8,16) << endl;
407 
408  for(int pass = 1; pass <= 2; pass++)
409  {
410  str.device()->at(mOffset);
411  //kdDebug(7011) << TQString("Writing hash table (pass #%1)").arg(pass) << endl;
412  for(uint i=0; i < mHashTableSize; i++)
413  {
414  TQ_INT32 tmpid;
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(); // Positive ID
419  else
420  tmpid = (TQ_INT32) -hashTable[i].duplicate_offset; // Negative ID
421  str << tmpid;
422  //kdDebug(7011) << TQString("Hash table : %1").arg(tmpid,8,16) << endl;
423  }
424  //kdDebug(7011) << TQString("End of Hash Table, offset = %1").arg(str.device()->at(),8,16) << endl;
425 
426  //kdDebug(7011) << TQString("Writing duplicate lists (pass #%1)").arg(pass) << endl;
427  for(uint i=0; i < mHashTableSize; i++)
428  {
429  if (hashTable[i].duplicates)
430  {
431  TQPtrList<string_entry> *dups = hashTable[i].duplicates;
432  hashTable[i].duplicate_offset = str.device()->at();
433 
434  /*kdDebug(7011) << TQString("Duplicate lists: Offset = %1 list_size = %2") .arg(hashTable[i].duplicate_offset,8,16).arg(dups->count()) << endl;
435 */
436  for(string_entry *dup = dups->first(); dup; dup=dups->next())
437  {
438  str << (TQ_INT32) dup->payload->offset(); // Positive ID
439  str << dup->keyStr; // Key (TQString)
440  }
441  str << (TQ_INT32) 0; // End of list marker (0)
442  }
443  }
444  //kdDebug(7011) << TQString("End of Dict, offset = %1").arg(str.device()->at(),8,16) << endl;
445  }
446 
447  //kdDebug(7011) << "Cleaning up hash table." << endl;
448  for(uint i=0; i < mHashTableSize; i++)
449  {
450  delete hashTable[i].duplicates;
451  }
452  delete [] hashTable;
453 }
454 
TDEStdAccel::key
int key(StdAccel id)
Definition: tdestdaccel.cpp:383
TDEGlobal::kdError
kdbgstream kdError(int area=0)
Definition: kdebug.cpp:372
KSycocaEntry
Base class for all Sycoca entries.
Definition: tdesycocaentry.h:37
TDEGlobal::endl
kdbgstream & endl(kdbgstream &s)
Definition: kdebug.h:430

tdecore

Skip menu "tdecore"
  • Main Page
  • Modules
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

tdecore

Skip menu "tdecore"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  •     tdecore
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  • tdeioslave
  •   http
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for tdecore by doxygen 1.8.8
This website is maintained by Timothy Pearson.