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 *************************************************************************/ 45 SvStringHashEntry::~SvStringHashEntry() { }; 46 47 /************************************************************************* 48 |* 49 |* SvHashTable::SvHashTable() 50 |* 51 |* Beschreibung 52 |* 53 *************************************************************************/ 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 *************************************************************************/ 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 *************************************************************************/ 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 *************************************************************************/ 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 *************************************************************************/ 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 *************************************************************************/ 191 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 *************************************************************************/ 219 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 *************************************************************************/ 240 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 *************************************************************************/ 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 *************************************************************************/ 275 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 *************************************************************************/ 288 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 *************************************************************************/ 302 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 *************************************************************************/ 315 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