xref: /aoo41x/main/soldep/bootstrp/hashtbl.cxx (revision d9e04f7d)
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