1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 #include <tools/gen.hxx>
25 #include <tools/debug.hxx>
26 #include <soldep/hashtbl.hxx>
27
28 // -------------------------------------------------------------
29 // class HashItem
30 //
31 class HashItem
32 {
33 enum ETag { TAG_EMPTY, TAG_USED, TAG_DELETED };
34
35 void* m_pObject;
36 ETag m_Tag;
37 ByteString m_Key;
38
39 public:
HashItem()40 HashItem() { m_Tag = TAG_EMPTY; m_pObject = NULL; }
41
IsDeleted() const42 sal_Bool IsDeleted() const
43 { return m_Tag == TAG_DELETED; }
44
IsEmpty() const45 sal_Bool IsEmpty() const
46 { return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; }
47
IsFree() const48 sal_Bool IsFree() const
49 { return m_Tag == TAG_EMPTY; }
50
IsUsed() const51 sal_Bool IsUsed() const
52 { return m_Tag == TAG_USED; }
53
Delete()54 void Delete()
55 { m_Tag = TAG_DELETED; m_Key = ""; m_pObject = NULL; }
56
GetKey() const57 ByteString const& GetKey() const
58 { return m_Key; }
59
GetObject() const60 void* GetObject() const
61 { return m_pObject; }
62
SetObject(ByteString const Key,void * pObject)63 void SetObject(ByteString const Key, void *pObject)
64 { m_Tag = TAG_USED; m_Key = Key; m_pObject = pObject; }
65 };
66
67 #define MIN(a,b) (a)<(b)?(a):(b)
68 #define MAX(a,b) (a)>(b)?(a):(b)
69
70 // -------------------------------------------------------------
71 // class HashTable
72 //
73
74 /*static*/ double HashTable::m_defMaxLoadFactor = 0.8;
75 /*static*/ double HashTable::m_defDefGrowFactor = 2.0;
76
HashTable(sal_uIntPtr lSize,sal_Bool bOwner,double dMaxLoadFactor,double dGrowFactor)77 HashTable::HashTable(sal_uIntPtr lSize, sal_Bool bOwner, double dMaxLoadFactor, double dGrowFactor)
78 {
79 m_lSize = lSize;
80 m_bOwner = bOwner;
81 m_lElem = 0;
82 m_dMaxLoadFactor = MAX(0.5,MIN(1.0,dMaxLoadFactor)); // 0.5 ... 1.0
83 m_dGrowFactor = MAX(1.3,MIN(5.0,dGrowFactor)); // 1.3 ... 5.0
84 m_pData = new HashItem [lSize];
85
86 // Statistik
87 #ifdef DBG_UTIL
88 m_aStatistic.m_lSingleHash = 0;
89 m_aStatistic.m_lDoubleHash = 0;
90 m_aStatistic.m_lProbe = 0;
91 #endif
92 }
93
~HashTable()94 HashTable::~HashTable()
95 {
96 // Wenn die HashTable der Owner der Objecte ist,
97 // m�ssen die Destruktoren separat gerufen werden.
98 // Dies geschieht �ber die virtuelle Methode OnDeleteObject()
99 //
100 // Problem: Virtuelle Funktionen sind im Destructor nicht virtuell!!
101 // Der Code mu� deshalb ins Macro
102
103 /*
104 if (m_bOwner)
105 {
106 for (sal_uIntPtr i=0; i<GetSize(); i++)
107 {
108 void *pObject = GetObjectAt(i);
109
110 if (pObject != NULL)
111 OnDeleteObject(pObject());
112 }
113 }
114 */
115
116 // Speicher f�r HashItems freigeben
117 delete [] m_pData;
118 }
119
GetObjectAt(sal_uIntPtr lPos) const120 void* HashTable::GetObjectAt(sal_uIntPtr lPos) const
121 // Gibt Objekt zur�ck, wenn es eines gibt, sonst NULL;
122 {
123 DBG_ASSERT(lPos<m_lSize, "HashTable::GetObjectAt()");
124
125 HashItem *pItem = &m_pData[lPos];
126
127 return pItem->IsUsed() ? pItem->GetObject() : NULL;
128 }
129
OnDeleteObject(void *)130 void HashTable::OnDeleteObject(void*)
131 {
132 DBG_ERROR("HashTable::OnDeleteObject(void*) nicht �berladen");
133 }
134
Hash(ByteString const & Key) const135 sal_uIntPtr HashTable::Hash(ByteString const& Key) const
136 {
137 /*
138 sal_uIntPtr lHash = 0;
139 sal_uIntPtr i,n;
140
141 for (i=0,n=Key.Len(); i<n; i++)
142 {
143 lHash *= 256L;
144 lHash += (sal_uIntPtr)(sal_uInt16)Key.GetStr()[i];
145 lHash %= m_lSize;
146 }
147 return lHash;
148 */
149
150 // Hashfunktion von P.J. Weinberger
151 // aus dem "Drachenbuch" von Aho/Sethi/Ullman
152 sal_uIntPtr i,n;
153 sal_uIntPtr h = 0;
154 sal_uIntPtr g = 0;
155
156 for (i=0,n=Key.Len(); i<n; i++)
157 {
158 h = (h<<4) + (sal_uIntPtr)(sal_uInt16)Key.GetBuffer()[i];
159 g = h & 0xf0000000;
160
161 if (g != 0)
162 {
163 h = h ^ (g >> 24);
164 h = h ^ g;
165 }
166 }
167
168 return h % m_lSize;
169 }
170
DHash(ByteString const & Key,sal_uIntPtr lOldHash) const171 sal_uIntPtr HashTable::DHash(ByteString const& Key, sal_uIntPtr lOldHash) const
172 {
173 sal_uIntPtr lHash = lOldHash;
174 sal_uIntPtr i,n;
175
176 for (i=0,n=Key.Len(); i<n; i++)
177 {
178 lHash *= 256L;
179 lHash += (sal_uIntPtr)(sal_uInt16)Key.GetBuffer()[i];
180 lHash %= m_lSize;
181 }
182 return lHash;
183
184 /* return
185 (
186 lHash
187 + (char)Key.GetStr()[0] * 256
188 + (char)Key.GetStr()[Key.Len()-1]
189 + 1
190 )
191 % m_lSize;
192 */
193 }
194
Probe(sal_uIntPtr lPos) const195 sal_uIntPtr HashTable::Probe(sal_uIntPtr lPos) const
196 // gibt den Folgewert von lPos zur�ck
197 {
198 lPos++; if (lPos==m_lSize) lPos=0;
199 return lPos;
200 }
201
IsFull() const202 sal_Bool HashTable::IsFull() const
203 {
204 return m_lElem>=m_lSize;
205 }
206
Insert(ByteString const & Key,void * pObject)207 sal_Bool HashTable::Insert(ByteString const& Key, void* pObject)
208 // pre: Key ist nicht im Dictionary enthalten, sonst return FALSE
209 // Dictionary ist nicht voll, sonst return FALSE
210 // post: pObject ist unter Key im Dictionary; m_nElem wurde erh�ht
211 {
212 SmartGrow();
213
214 if (IsFull())
215 {
216 DBG_ERROR("HashTable::Insert() is full");
217 return sal_False;
218 }
219
220 if (FindPos(Key) != NULL )
221 return sal_False;
222
223 sal_uIntPtr lPos = Hash(Key);
224 HashItem *pItem = &m_pData[lPos];
225
226 // first hashing
227 //
228 if (pItem->IsEmpty())
229 {
230 pItem->SetObject(Key, pObject);
231 m_lElem++;
232
233 #ifdef DBG_UTIL
234 m_aStatistic.m_lSingleHash++;
235 #endif
236
237 return sal_True;
238 }
239
240 // double hashing
241 //
242 lPos = DHash(Key,lPos);
243 pItem = &m_pData[lPos];
244
245 if (pItem->IsEmpty())
246 {
247 pItem->SetObject(Key, pObject);
248 m_lElem++;
249
250 #ifdef DBG_UTIL
251 m_aStatistic.m_lDoubleHash++;
252 #endif
253
254 return sal_True;
255 }
256
257 // linear probing
258 //
259 do
260 {
261 #ifdef DBG_UTIL
262 m_aStatistic.m_lProbe++;
263 #endif
264
265 lPos = Probe(lPos);
266 pItem = &m_pData[lPos];
267 }
268 while(!pItem->IsEmpty());
269
270 pItem->SetObject(Key, pObject);
271 m_lElem++;
272 return sal_True;
273 }
274
FindPos(ByteString const & Key) const275 HashItem* HashTable::FindPos(ByteString const& Key) const
276 // sucht den Key; gibt Refrenz auf den Eintrag (gefunden)
277 // oder NULL (nicht gefunden) zur�ck
278 //
279 // pre: -
280 // post: -
281 {
282 // first hashing
283 //
284 sal_uIntPtr lPos = Hash(Key);
285 HashItem *pItem = &m_pData[lPos];
286
287 if (pItem->IsUsed()
288 && pItem->GetKey() == Key)
289 {
290 return pItem;
291 }
292
293 // double hashing
294 //
295 if (pItem->IsDeleted() || pItem->IsUsed())
296 {
297 lPos = DHash(Key,lPos);
298 pItem = &m_pData[lPos];
299
300 if (pItem->IsUsed()
301 && pItem->GetKey() == Key)
302 {
303 return pItem;
304 }
305
306 // linear probing
307 //
308 if (pItem->IsDeleted() || pItem->IsUsed())
309 {
310 sal_uIntPtr n = 0;
311 sal_Bool bFound = sal_False;
312 sal_Bool bEnd = sal_False;
313
314 do
315 {
316 n++;
317 lPos = Probe(lPos);
318 pItem = &m_pData[lPos];
319
320 bFound = pItem->IsUsed()
321 && pItem->GetKey() == Key;
322
323 bEnd = !(n<m_lSize || pItem->IsFree());
324 }
325 while(!bFound && !bEnd);
326
327 return bFound ? pItem : NULL;
328 }
329 }
330
331 // nicht gefunden
332 //
333 return NULL;
334 }
335
Find(ByteString const & Key) const336 void* HashTable::Find(ByteString const& Key) const
337 // Gibt Verweis des Objektes zur�ck, das unter Key abgespeichert ist,
338 // oder NULL wenn nicht vorhanden.
339 //
340 // pre: -
341 // post: -
342 {
343 HashItem *pItem = FindPos(Key);
344
345 if (pItem != NULL
346 && pItem->GetKey() == Key)
347 return pItem->GetObject();
348 else
349 return NULL;
350 }
351
Delete(ByteString const & Key)352 void* HashTable::Delete(ByteString const& Key)
353 // L�scht Objekt, das unter Key abgespeichert ist und gibt Verweis
354 // darauf zur�ck.
355 // Gibt NULL zur�ck, wenn Key nicht vorhanden ist.
356 //
357 // pre: -
358 // post: Objekt ist nicht mehr enthalten; m_lElem dekrementiert
359 // Wenn die HashTable der Owner ist, wurde das Object gel�scht
360 {
361 HashItem *pItem = FindPos(Key);
362
363 if (pItem != NULL
364 && pItem->GetKey() == Key)
365 {
366 void* pObject = pItem->GetObject();
367
368 if (m_bOwner)
369 OnDeleteObject(pObject);
370
371 pItem->Delete();
372 m_lElem--;
373 return pObject;
374 }
375 else
376 {
377 return NULL;
378 }
379 }
380
CalcLoadFactor() const381 double HashTable::CalcLoadFactor() const
382 // prozentuale Belegung der Hashtabelle berechnen
383 {
384 return double(m_lElem) / double(m_lSize);
385 }
386
SmartGrow()387 void HashTable::SmartGrow()
388 // Achtung: da die Objekte umkopiert werden, darf die OnDeleteObject-Methode
389 // nicht gerufen werden
390 {
391 double dLoadFactor = CalcLoadFactor();
392
393 if (dLoadFactor <= m_dMaxLoadFactor)
394 return; // nothing to grow
395
396 sal_uIntPtr lOldSize = m_lSize; // alte Daten sichern
397 HashItem* pOldData = m_pData;
398
399 m_lSize = sal_uIntPtr (m_dGrowFactor * m_lSize); // neue Gr��e
400 m_pData = new HashItem[m_lSize]; // neue Daten holen
401
402 // kein Speicher:
403 // Zustand "Tabelle voll" wird in Insert abgefangen
404 //
405 if (m_pData == NULL)
406 {
407 m_lSize = lOldSize;
408 m_pData = pOldData;
409 return;
410 }
411
412 m_lElem = 0; // noch keine neuen Daten
413
414 // Umkopieren der Daten
415 //
416 for (sal_uIntPtr i=0; i<lOldSize; i++)
417 {
418 HashItem *pItem = &pOldData[i];
419
420 if (pItem->IsUsed())
421 Insert(pItem->GetKey(),pItem->GetObject());
422 }
423
424 delete [] pOldData;
425 }
426
427 // Iterator ---------------------------------------------------------
428 //
429
HashTableIterator(HashTable const & aTable)430 HashTableIterator::HashTableIterator(HashTable const& aTable)
431 : m_aTable(aTable)
432 {
433 m_lAt = 0;
434 }
435
GetFirst()436 void* HashTableIterator::GetFirst()
437 {
438 m_lAt = 0;
439 return FindValidObject(sal_True /* forward */);
440 }
441
GetLast()442 void* HashTableIterator::GetLast()
443 {
444 m_lAt = m_aTable.GetSize() -1;
445 return FindValidObject(sal_False /* backward */);
446 }
447
GetNext()448 void* HashTableIterator::GetNext()
449 {
450 if (m_lAt+1 >= m_aTable.GetSize())
451 return NULL;
452
453 m_lAt++;
454 return FindValidObject(sal_True /* forward */);
455 }
456
GetPrev()457 void* HashTableIterator::GetPrev()
458 {
459 if (m_lAt <= 0)
460 return NULL;
461
462 m_lAt--;
463 return FindValidObject(sal_False /* backward */);
464 }
465
FindValidObject(sal_Bool bForward)466 void* HashTableIterator::FindValidObject(sal_Bool bForward)
467 // Sucht nach einem vorhandenen Objekt ab der aktuellen
468 // Position.
469 //
470 // pre: ab inkl. m_lAt soll die Suche beginnen
471 // post: if not found then
472 // if bForward == sal_True then
473 // m_lAt == m_aTable.GetSize() -1
474 // else
475 // m_lAt == 0
476 // else
477 // m_lAt ist die gefundene Position
478 {
479 void *pObject = m_aTable.GetObjectAt(m_lAt);
480
481 if (pObject != NULL)
482 return pObject;
483
484 while (pObject == NULL
485 && (bForward ? ((m_lAt+1) < m_aTable.GetSize())
486 : m_lAt > 0))
487 {
488 if (bForward)
489 m_lAt++;
490 else
491 m_lAt--;
492
493 pObject = m_aTable.GetObjectAt(m_lAt);
494 }
495
496 #ifdef DBG_UTIL
497
498 if (pObject == NULL)
499 {
500 DBG_ASSERT(bForward ? m_lAt == m_aTable.GetSize() -1 : m_lAt == 0,
501 "HashTableIterator::FindValidObject()");
502 }
503
504 #endif
505
506 return pObject;
507 }
508