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