1*724893d4SAndrew Rist /**************************************************************
2cdf0e10cSrcweir *
3*724893d4SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
4*724893d4SAndrew Rist * or more contributor license agreements. See the NOTICE file
5*724893d4SAndrew Rist * distributed with this work for additional information
6*724893d4SAndrew Rist * regarding copyright ownership. The ASF licenses this file
7*724893d4SAndrew Rist * to you under the Apache License, Version 2.0 (the
8*724893d4SAndrew Rist * "License"); you may not use this file except in compliance
9*724893d4SAndrew Rist * with the License. You may obtain a copy of the License at
10*724893d4SAndrew Rist *
11*724893d4SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
12*724893d4SAndrew Rist *
13*724893d4SAndrew Rist * Unless required by applicable law or agreed to in writing,
14*724893d4SAndrew Rist * software distributed under the License is distributed on an
15*724893d4SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16*724893d4SAndrew Rist * KIND, either express or implied. See the License for the
17*724893d4SAndrew Rist * specific language governing permissions and limitations
18*724893d4SAndrew Rist * under the License.
19*724893d4SAndrew Rist *
20*724893d4SAndrew Rist *************************************************************/
21*724893d4SAndrew Rist
22*724893d4SAndrew Rist
23cdf0e10cSrcweir
24cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove
25cdf0e10cSrcweir #include "precompiled_idl.hxx"
26cdf0e10cSrcweir
27cdf0e10cSrcweir /****************** I N C L U D E S **************************************/
28cdf0e10cSrcweir // C and C++ Includes.
29cdf0e10cSrcweir #include <stdlib.h>
30cdf0e10cSrcweir #include <stdio.h>
31cdf0e10cSrcweir #include <ctype.h>
32cdf0e10cSrcweir
33cdf0e10cSrcweir // Programmabh�ngige Includes.
34cdf0e10cSrcweir #include <hash.hxx>
35cdf0e10cSrcweir #include <tools/debug.hxx>
36cdf0e10cSrcweir
37cdf0e10cSrcweir /****************** C O D E **********************************************/
38cdf0e10cSrcweir /*************************************************************************
39cdf0e10cSrcweir |*
40cdf0e10cSrcweir |* SvStringHashEntry::~SvStringHashEntry()
41cdf0e10cSrcweir |*
42cdf0e10cSrcweir |* Beschreibung
43cdf0e10cSrcweir |*
44cdf0e10cSrcweir *************************************************************************/
~SvStringHashEntry()45cdf0e10cSrcweir SvStringHashEntry::~SvStringHashEntry() { };
46cdf0e10cSrcweir
47cdf0e10cSrcweir /*************************************************************************
48cdf0e10cSrcweir |*
49cdf0e10cSrcweir |* SvHashTable::SvHashTable()
50cdf0e10cSrcweir |*
51cdf0e10cSrcweir |* Beschreibung
52cdf0e10cSrcweir |*
53cdf0e10cSrcweir *************************************************************************/
SvHashTable(sal_uInt32 nMaxEntries)54cdf0e10cSrcweir SvHashTable::SvHashTable( sal_uInt32 nMaxEntries )
55cdf0e10cSrcweir {
56cdf0e10cSrcweir nMax = nMaxEntries; // set max entries
57cdf0e10cSrcweir nFill = 0; // no entries
58cdf0e10cSrcweir lTry = 0;
59cdf0e10cSrcweir lAsk = 0;
60cdf0e10cSrcweir }
61cdf0e10cSrcweir
62cdf0e10cSrcweir /*************************************************************************
63cdf0e10cSrcweir |*
64cdf0e10cSrcweir |* SvHashTable::~SvHashTable()
65cdf0e10cSrcweir |*
66cdf0e10cSrcweir |* Beschreibung
67cdf0e10cSrcweir |*
68cdf0e10cSrcweir *************************************************************************/
~SvHashTable()69cdf0e10cSrcweir SvHashTable::~SvHashTable()
70cdf0e10cSrcweir {
71cdf0e10cSrcweir #ifdef DOS_NIE
72cdf0e10cSrcweir printf( "Maximum: %ld, F�llung: %ld\n", (sal_uLong)nMax, (sal_uLong)nFill );
73cdf0e10cSrcweir printf( "Anfragen: %ld, Versuche: %ld", (sal_uLong)lAsk, (sal_uLong)lTry );
74cdf0e10cSrcweir if( lTry != 0 )
75cdf0e10cSrcweir printf( ", V/E = %ld\n", lTry / lAsk );
76cdf0e10cSrcweir #endif
77cdf0e10cSrcweir }
78cdf0e10cSrcweir
79cdf0e10cSrcweir /*************************************************************************
80cdf0e10cSrcweir |*
81cdf0e10cSrcweir |* SvHashTable::Test_Insert()
82cdf0e10cSrcweir |*
83cdf0e10cSrcweir |* Beschreibung
84cdf0e10cSrcweir |*
85cdf0e10cSrcweir *************************************************************************/
Test_Insert(const void * pElement,sal_Bool bInsert,sal_uInt32 * pInsertPos)86cdf0e10cSrcweir sal_Bool SvHashTable::Test_Insert( const void * pElement, sal_Bool bInsert,
87cdf0e10cSrcweir sal_uInt32 * pInsertPos )
88cdf0e10cSrcweir {
89cdf0e10cSrcweir sal_uInt32 nHash;
90cdf0e10cSrcweir sal_uInt32 nIndex;
91cdf0e10cSrcweir sal_uInt32 nLoop;
92cdf0e10cSrcweir
93cdf0e10cSrcweir lAsk++;
94cdf0e10cSrcweir lTry++;
95cdf0e10cSrcweir
96cdf0e10cSrcweir nHash = HashFunc( pElement );
97cdf0e10cSrcweir nIndex = nHash % nMax;
98cdf0e10cSrcweir
99cdf0e10cSrcweir // const char* s = ((ByteString*) pElement)->GetStr();
100cdf0e10cSrcweir // fprintf(stderr,"### Hash: %lu , Name: %s\n",nIndex,s );
101cdf0e10cSrcweir
102cdf0e10cSrcweir nLoop = 0; // divide to range
103cdf0e10cSrcweir while( (nMax != nLoop) && IsEntry( nIndex ) )
104cdf0e10cSrcweir { // is place occupied
105cdf0e10cSrcweir if( COMPARE_EQUAL == Compare( pElement, nIndex ) )
106cdf0e10cSrcweir {
107cdf0e10cSrcweir if( pInsertPos )
108cdf0e10cSrcweir *pInsertPos = nIndex; // place of Element
109cdf0e10cSrcweir return sal_True;
110cdf0e10cSrcweir }
111cdf0e10cSrcweir nLoop++;
112cdf0e10cSrcweir lTry++;
113cdf0e10cSrcweir nIndex = (sal_uInt16)(nIndex + nHash + 7) % nMax;
114cdf0e10cSrcweir }
115cdf0e10cSrcweir
116cdf0e10cSrcweir if( bInsert )
117cdf0e10cSrcweir {
118cdf0e10cSrcweir DBG_ASSERT( nMax != nLoop, "Hash table full" );
119cdf0e10cSrcweir if( nMax != nLoop )
120cdf0e10cSrcweir {
121cdf0e10cSrcweir nFill++;
122cdf0e10cSrcweir *pInsertPos = nIndex; // return free place
123cdf0e10cSrcweir return sal_True;
124cdf0e10cSrcweir }
125cdf0e10cSrcweir }
126cdf0e10cSrcweir return( sal_False );
127cdf0e10cSrcweir }
128cdf0e10cSrcweir
129cdf0e10cSrcweir /************************************************************************/
130cdf0e10cSrcweir /*************************************************************************
131cdf0e10cSrcweir |*
132cdf0e10cSrcweir |* SvStringHashTable::SvStringHashTable()
133cdf0e10cSrcweir |*
134cdf0e10cSrcweir |* Beschreibung
135cdf0e10cSrcweir |*
136cdf0e10cSrcweir *************************************************************************/
SvStringHashTable(sal_uInt32 nMaxEntries)137cdf0e10cSrcweir SvStringHashTable::SvStringHashTable( sal_uInt32 nMaxEntries )
138cdf0e10cSrcweir : SvHashTable( nMaxEntries )
139cdf0e10cSrcweir {
140cdf0e10cSrcweir pEntries = new SvStringHashEntry[ nMaxEntries ];
141cdf0e10cSrcweir
142cdf0e10cSrcweir // RefCount auf eins setzen
143cdf0e10cSrcweir SvStringHashEntry * pPos, *pEnd;
144cdf0e10cSrcweir pPos = pEntries;
145cdf0e10cSrcweir pEnd = pEntries + nMaxEntries;
146cdf0e10cSrcweir while( pPos != pEnd )
147cdf0e10cSrcweir {
148cdf0e10cSrcweir pPos->AddRef();
149cdf0e10cSrcweir pPos++;
150cdf0e10cSrcweir }
151cdf0e10cSrcweir }
152cdf0e10cSrcweir
153cdf0e10cSrcweir /*************************************************************************
154cdf0e10cSrcweir |*
155cdf0e10cSrcweir |* ~SvStringHashTable::SvStringHashTable()
156cdf0e10cSrcweir |*
157cdf0e10cSrcweir |* Beschreibung
158cdf0e10cSrcweir |*
159cdf0e10cSrcweir *************************************************************************/
~SvStringHashTable()160cdf0e10cSrcweir SvStringHashTable::~SvStringHashTable()
161cdf0e10cSrcweir {
162cdf0e10cSrcweir // RefCount auf eins setzen
163cdf0e10cSrcweir SvStringHashEntry * pPos, *pEnd;
164cdf0e10cSrcweir pPos = pEntries;
165cdf0e10cSrcweir pEnd = pEntries + GetMax();
166cdf0e10cSrcweir #ifdef DBG_UTIL
167cdf0e10cSrcweir while( pPos != pEnd )
168cdf0e10cSrcweir {
169cdf0e10cSrcweir DBG_ASSERT( pPos->GetRefCount() == 1, "Reference count != 1" );
170cdf0e10cSrcweir pPos++;
171cdf0e10cSrcweir }
172cdf0e10cSrcweir #endif
173cdf0e10cSrcweir
174cdf0e10cSrcweir #ifdef MPW
175cdf0e10cSrcweir // der MPW-Compiler ruft sonst keine Dtoren!
176cdf0e10cSrcweir for ( sal_uInt16 n = 0; n < GetMax(); ++n )
177cdf0e10cSrcweir (pEntries+n)->SvStringHashEntry::~SvStringHashEntry();
178cdf0e10cSrcweir delete (void*) pEntries;
179cdf0e10cSrcweir #else
180cdf0e10cSrcweir delete [] pEntries;
181cdf0e10cSrcweir #endif
182cdf0e10cSrcweir }
183cdf0e10cSrcweir
184cdf0e10cSrcweir /*************************************************************************
185cdf0e10cSrcweir |*
186cdf0e10cSrcweir |* SvStringHashTable::HashFunc()
187cdf0e10cSrcweir |*
188cdf0e10cSrcweir |* Beschreibung
189cdf0e10cSrcweir |*
190cdf0e10cSrcweir *************************************************************************/
HashFunc(const void * pElement) const191cdf0e10cSrcweir sal_uInt32 SvStringHashTable::HashFunc( const void * pElement ) const
192cdf0e10cSrcweir {
193cdf0e10cSrcweir sal_uInt32 nHash = 0; // hash value
194cdf0e10cSrcweir const char * pStr = ((const ByteString * )pElement)->GetBuffer();
195cdf0e10cSrcweir
196cdf0e10cSrcweir int nShift = 0;
197cdf0e10cSrcweir while( *pStr )
198cdf0e10cSrcweir {
199cdf0e10cSrcweir if( isupper( *pStr ) )
200cdf0e10cSrcweir nHash ^= sal_uInt32(*pStr - 'A' + 26) << nShift;
201cdf0e10cSrcweir else
202cdf0e10cSrcweir nHash ^= sal_uInt32(*pStr - 'a') << nShift;
203cdf0e10cSrcweir if( nShift == 28 )
204cdf0e10cSrcweir nShift = 0;
205cdf0e10cSrcweir else
206cdf0e10cSrcweir nShift += 4;
207cdf0e10cSrcweir pStr++;
208cdf0e10cSrcweir }
209cdf0e10cSrcweir return( nHash );
210cdf0e10cSrcweir }
211cdf0e10cSrcweir
212cdf0e10cSrcweir /*************************************************************************
213cdf0e10cSrcweir |*
214cdf0e10cSrcweir |* SvStringHashTable::GetNearString()
215cdf0e10cSrcweir |*
216cdf0e10cSrcweir |* Beschreibung
217cdf0e10cSrcweir |*
218cdf0e10cSrcweir *************************************************************************/
GetNearString(const ByteString & rName) const219cdf0e10cSrcweir ByteString SvStringHashTable::GetNearString( const ByteString & rName ) const
220cdf0e10cSrcweir {
221cdf0e10cSrcweir for( sal_uInt32 i = 0; i < GetMax(); i++ )
222cdf0e10cSrcweir {
223cdf0e10cSrcweir SvStringHashEntry * pE = Get( i );
224cdf0e10cSrcweir if( pE )
225cdf0e10cSrcweir {
226cdf0e10cSrcweir if( pE->GetName().EqualsIgnoreCaseAscii( rName ) && !pE->GetName().Equals( rName ) )
227cdf0e10cSrcweir return pE->GetName();
228cdf0e10cSrcweir }
229cdf0e10cSrcweir }
230cdf0e10cSrcweir return ByteString();
231cdf0e10cSrcweir }
232cdf0e10cSrcweir
233cdf0e10cSrcweir /*************************************************************************
234cdf0e10cSrcweir |*
235cdf0e10cSrcweir |* SvStringHashTable::IsEntry()
236cdf0e10cSrcweir |*
237cdf0e10cSrcweir |* Beschreibung
238cdf0e10cSrcweir |*
239cdf0e10cSrcweir *************************************************************************/
IsEntry(sal_uInt32 nIndex) const240cdf0e10cSrcweir sal_Bool SvStringHashTable::IsEntry( sal_uInt32 nIndex ) const
241cdf0e10cSrcweir {
242cdf0e10cSrcweir if( nIndex >= GetMax() )
243cdf0e10cSrcweir return sal_False;
244cdf0e10cSrcweir return pEntries[ nIndex ].HasId();
245cdf0e10cSrcweir }
246cdf0e10cSrcweir
247cdf0e10cSrcweir /*************************************************************************
248cdf0e10cSrcweir |*
249cdf0e10cSrcweir |* SvStringHashTable::Insert()
250cdf0e10cSrcweir |*
251cdf0e10cSrcweir |* Beschreibung
252cdf0e10cSrcweir |*
253cdf0e10cSrcweir *************************************************************************/
Insert(const ByteString & rName,sal_uInt32 * pIndex)254cdf0e10cSrcweir sal_Bool SvStringHashTable::Insert( const ByteString & rName, sal_uInt32 * pIndex )
255cdf0e10cSrcweir {
256cdf0e10cSrcweir sal_uInt32 nIndex;
257cdf0e10cSrcweir
258cdf0e10cSrcweir if( !pIndex ) pIndex = &nIndex;
259cdf0e10cSrcweir
260cdf0e10cSrcweir if( !SvHashTable::Test_Insert( &rName, sal_True, pIndex ) )
261cdf0e10cSrcweir return sal_False;
262cdf0e10cSrcweir
263cdf0e10cSrcweir if( !IsEntry( *pIndex ) )
264cdf0e10cSrcweir pEntries[ *pIndex ] = SvStringHashEntry( rName, *pIndex );
265cdf0e10cSrcweir return sal_True;
266cdf0e10cSrcweir }
267cdf0e10cSrcweir
268cdf0e10cSrcweir /*************************************************************************
269cdf0e10cSrcweir |*
270cdf0e10cSrcweir |* SvStringHashTable::Test()
271cdf0e10cSrcweir |*
272cdf0e10cSrcweir |* Beschreibung
273cdf0e10cSrcweir |*
274cdf0e10cSrcweir *************************************************************************/
Test(const ByteString & rName,sal_uInt32 * pPos) const275cdf0e10cSrcweir sal_Bool SvStringHashTable::Test( const ByteString & rName, sal_uInt32 * pPos ) const
276cdf0e10cSrcweir {
277cdf0e10cSrcweir return ((SvStringHashTable *)this)->SvHashTable::
278cdf0e10cSrcweir Test_Insert( &rName, sal_False, pPos );
279cdf0e10cSrcweir }
280cdf0e10cSrcweir
281cdf0e10cSrcweir /*************************************************************************
282cdf0e10cSrcweir |*
283cdf0e10cSrcweir |* SvStringHashTable::Get()
284cdf0e10cSrcweir |*
285cdf0e10cSrcweir |* Beschreibung
286cdf0e10cSrcweir |*
287cdf0e10cSrcweir *************************************************************************/
Get(sal_uInt32 nIndex) const288cdf0e10cSrcweir SvStringHashEntry * SvStringHashTable::Get( sal_uInt32 nIndex ) const
289cdf0e10cSrcweir {
290cdf0e10cSrcweir if( IsEntry( nIndex ) )
291cdf0e10cSrcweir return pEntries + nIndex;
292cdf0e10cSrcweir return( NULL );
293cdf0e10cSrcweir }
294cdf0e10cSrcweir
295cdf0e10cSrcweir /*************************************************************************
296cdf0e10cSrcweir |*
297cdf0e10cSrcweir |* SvStringHashTable::Get()
298cdf0e10cSrcweir |*
299cdf0e10cSrcweir |* Beschreibung
300cdf0e10cSrcweir |*
301cdf0e10cSrcweir *************************************************************************/
Compare(const void * pElement,sal_uInt32 nIndex) const302cdf0e10cSrcweir StringCompare SvStringHashTable::Compare( const void * pElement,
303cdf0e10cSrcweir sal_uInt32 nIndex ) const
304cdf0e10cSrcweir {
305cdf0e10cSrcweir return ((const ByteString *)pElement)->CompareTo( pEntries[ nIndex ].GetName() );
306cdf0e10cSrcweir }
307cdf0e10cSrcweir
308cdf0e10cSrcweir /*************************************************************************
309cdf0e10cSrcweir |*
310cdf0e10cSrcweir |* SvStringHashTable::FillHashList()
311cdf0e10cSrcweir |*
312cdf0e10cSrcweir |* Beschreibung
313cdf0e10cSrcweir |*
314cdf0e10cSrcweir *************************************************************************/
FillHashList(SvStringHashList * pList) const315cdf0e10cSrcweir void SvStringHashTable::FillHashList( SvStringHashList * pList ) const
316cdf0e10cSrcweir {
317cdf0e10cSrcweir for( sal_uInt32 n = 0; n < GetMax(); n++ )
318cdf0e10cSrcweir {
319cdf0e10cSrcweir if( IsEntry( n ) )
320cdf0e10cSrcweir pList->Insert( Get( n ), LIST_APPEND );
321cdf0e10cSrcweir }
322cdf0e10cSrcweir // Hash Reihenfolge, jetzt sortieren
323cdf0e10cSrcweir }
324