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