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