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_idl.hxx"
26
27 /****************** I N C L U D E S **************************************/
28 // C and C++ Includes.
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <ctype.h>
32
33 // Programmabh�ngige Includes.
34 #include <hash.hxx>
35 #include <tools/debug.hxx>
36
37 /****************** C O D E **********************************************/
38 /*************************************************************************
39 |*
40 |* SvStringHashEntry::~SvStringHashEntry()
41 |*
42 |* Beschreibung
43 |*
44 *************************************************************************/
~SvStringHashEntry()45 SvStringHashEntry::~SvStringHashEntry() { };
46
47 /*************************************************************************
48 |*
49 |* SvHashTable::SvHashTable()
50 |*
51 |* Beschreibung
52 |*
53 *************************************************************************/
SvHashTable(sal_uInt32 nMaxEntries)54 SvHashTable::SvHashTable( sal_uInt32 nMaxEntries )
55 {
56 nMax = nMaxEntries; // set max entries
57 nFill = 0; // no entries
58 lTry = 0;
59 lAsk = 0;
60 }
61
62 /*************************************************************************
63 |*
64 |* SvHashTable::~SvHashTable()
65 |*
66 |* Beschreibung
67 |*
68 *************************************************************************/
~SvHashTable()69 SvHashTable::~SvHashTable()
70 {
71 #ifdef DOS_NIE
72 printf( "Maximum: %ld, F�llung: %ld\n", (sal_uLong)nMax, (sal_uLong)nFill );
73 printf( "Anfragen: %ld, Versuche: %ld", (sal_uLong)lAsk, (sal_uLong)lTry );
74 if( lTry != 0 )
75 printf( ", V/E = %ld\n", lTry / lAsk );
76 #endif
77 }
78
79 /*************************************************************************
80 |*
81 |* SvHashTable::Test_Insert()
82 |*
83 |* Beschreibung
84 |*
85 *************************************************************************/
Test_Insert(const void * pElement,sal_Bool bInsert,sal_uInt32 * pInsertPos)86 sal_Bool SvHashTable::Test_Insert( const void * pElement, sal_Bool bInsert,
87 sal_uInt32 * pInsertPos )
88 {
89 sal_uInt32 nHash;
90 sal_uInt32 nIndex;
91 sal_uInt32 nLoop;
92
93 lAsk++;
94 lTry++;
95
96 nHash = HashFunc( pElement );
97 nIndex = nHash % nMax;
98
99 // const char* s = ((ByteString*) pElement)->GetStr();
100 // fprintf(stderr,"### Hash: %lu , Name: %s\n",nIndex,s );
101
102 nLoop = 0; // divide to range
103 while( (nMax != nLoop) && IsEntry( nIndex ) )
104 { // is place occupied
105 if( COMPARE_EQUAL == Compare( pElement, nIndex ) )
106 {
107 if( pInsertPos )
108 *pInsertPos = nIndex; // place of Element
109 return sal_True;
110 }
111 nLoop++;
112 lTry++;
113 nIndex = (sal_uInt16)(nIndex + nHash + 7) % nMax;
114 }
115
116 if( bInsert )
117 {
118 DBG_ASSERT( nMax != nLoop, "Hash table full" );
119 if( nMax != nLoop )
120 {
121 nFill++;
122 *pInsertPos = nIndex; // return free place
123 return sal_True;
124 }
125 }
126 return( sal_False );
127 }
128
129 /************************************************************************/
130 /*************************************************************************
131 |*
132 |* SvStringHashTable::SvStringHashTable()
133 |*
134 |* Beschreibung
135 |*
136 *************************************************************************/
SvStringHashTable(sal_uInt32 nMaxEntries)137 SvStringHashTable::SvStringHashTable( sal_uInt32 nMaxEntries )
138 : SvHashTable( nMaxEntries )
139 {
140 pEntries = new SvStringHashEntry[ nMaxEntries ];
141
142 // RefCount auf eins setzen
143 SvStringHashEntry * pPos, *pEnd;
144 pPos = pEntries;
145 pEnd = pEntries + nMaxEntries;
146 while( pPos != pEnd )
147 {
148 pPos->AddRef();
149 pPos++;
150 }
151 }
152
153 /*************************************************************************
154 |*
155 |* ~SvStringHashTable::SvStringHashTable()
156 |*
157 |* Beschreibung
158 |*
159 *************************************************************************/
~SvStringHashTable()160 SvStringHashTable::~SvStringHashTable()
161 {
162 // RefCount auf eins setzen
163 SvStringHashEntry * pPos, *pEnd;
164 pPos = pEntries;
165 pEnd = pEntries + GetMax();
166 #ifdef DBG_UTIL
167 while( pPos != pEnd )
168 {
169 DBG_ASSERT( pPos->GetRefCount() == 1, "Reference count != 1" );
170 pPos++;
171 }
172 #endif
173
174 #ifdef MPW
175 // der MPW-Compiler ruft sonst keine Dtoren!
176 for ( sal_uInt16 n = 0; n < GetMax(); ++n )
177 (pEntries+n)->SvStringHashEntry::~SvStringHashEntry();
178 delete (void*) pEntries;
179 #else
180 delete [] pEntries;
181 #endif
182 }
183
184 /*************************************************************************
185 |*
186 |* SvStringHashTable::HashFunc()
187 |*
188 |* Beschreibung
189 |*
190 *************************************************************************/
HashFunc(const void * pElement) const191 sal_uInt32 SvStringHashTable::HashFunc( const void * pElement ) const
192 {
193 sal_uInt32 nHash = 0; // hash value
194 const char * pStr = ((const ByteString * )pElement)->GetBuffer();
195
196 int nShift = 0;
197 while( *pStr )
198 {
199 if( isupper( *pStr ) )
200 nHash ^= sal_uInt32(*pStr - 'A' + 26) << nShift;
201 else
202 nHash ^= sal_uInt32(*pStr - 'a') << nShift;
203 if( nShift == 28 )
204 nShift = 0;
205 else
206 nShift += 4;
207 pStr++;
208 }
209 return( nHash );
210 }
211
212 /*************************************************************************
213 |*
214 |* SvStringHashTable::GetNearString()
215 |*
216 |* Beschreibung
217 |*
218 *************************************************************************/
GetNearString(const ByteString & rName) const219 ByteString SvStringHashTable::GetNearString( const ByteString & rName ) const
220 {
221 for( sal_uInt32 i = 0; i < GetMax(); i++ )
222 {
223 SvStringHashEntry * pE = Get( i );
224 if( pE )
225 {
226 if( pE->GetName().EqualsIgnoreCaseAscii( rName ) && !pE->GetName().Equals( rName ) )
227 return pE->GetName();
228 }
229 }
230 return ByteString();
231 }
232
233 /*************************************************************************
234 |*
235 |* SvStringHashTable::IsEntry()
236 |*
237 |* Beschreibung
238 |*
239 *************************************************************************/
IsEntry(sal_uInt32 nIndex) const240 sal_Bool SvStringHashTable::IsEntry( sal_uInt32 nIndex ) const
241 {
242 if( nIndex >= GetMax() )
243 return sal_False;
244 return pEntries[ nIndex ].HasId();
245 }
246
247 /*************************************************************************
248 |*
249 |* SvStringHashTable::Insert()
250 |*
251 |* Beschreibung
252 |*
253 *************************************************************************/
Insert(const ByteString & rName,sal_uInt32 * pIndex)254 sal_Bool SvStringHashTable::Insert( const ByteString & rName, sal_uInt32 * pIndex )
255 {
256 sal_uInt32 nIndex;
257
258 if( !pIndex ) pIndex = &nIndex;
259
260 if( !SvHashTable::Test_Insert( &rName, sal_True, pIndex ) )
261 return sal_False;
262
263 if( !IsEntry( *pIndex ) )
264 pEntries[ *pIndex ] = SvStringHashEntry( rName, *pIndex );
265 return sal_True;
266 }
267
268 /*************************************************************************
269 |*
270 |* SvStringHashTable::Test()
271 |*
272 |* Beschreibung
273 |*
274 *************************************************************************/
Test(const ByteString & rName,sal_uInt32 * pPos) const275 sal_Bool SvStringHashTable::Test( const ByteString & rName, sal_uInt32 * pPos ) const
276 {
277 return ((SvStringHashTable *)this)->SvHashTable::
278 Test_Insert( &rName, sal_False, pPos );
279 }
280
281 /*************************************************************************
282 |*
283 |* SvStringHashTable::Get()
284 |*
285 |* Beschreibung
286 |*
287 *************************************************************************/
Get(sal_uInt32 nIndex) const288 SvStringHashEntry * SvStringHashTable::Get( sal_uInt32 nIndex ) const
289 {
290 if( IsEntry( nIndex ) )
291 return pEntries + nIndex;
292 return( NULL );
293 }
294
295 /*************************************************************************
296 |*
297 |* SvStringHashTable::Get()
298 |*
299 |* Beschreibung
300 |*
301 *************************************************************************/
Compare(const void * pElement,sal_uInt32 nIndex) const302 StringCompare SvStringHashTable::Compare( const void * pElement,
303 sal_uInt32 nIndex ) const
304 {
305 return ((const ByteString *)pElement)->CompareTo( pEntries[ nIndex ].GetName() );
306 }
307
308 /*************************************************************************
309 |*
310 |* SvStringHashTable::FillHashList()
311 |*
312 |* Beschreibung
313 |*
314 *************************************************************************/
FillHashList(SvStringHashList * pList) const315 void SvStringHashTable::FillHashList( SvStringHashList * pList ) const
316 {
317 for( sal_uInt32 n = 0; n < GetMax(); n++ )
318 {
319 if( IsEntry( n ) )
320 pList->Insert( Get( n ), LIST_APPEND );
321 }
322 // Hash Reihenfolge, jetzt sortieren
323 }
324