xref: /aoo41x/main/tools/workben/hashtbl.cxx (revision 89b56da7)
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