1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 // MARKER(update_precomp.py): autogen include statement, do not remove 29 #include "precompiled_idl.hxx" 30 31 /****************** I N C L U D E S **************************************/ 32 // C and C++ Includes. 33 #include <stdlib.h> 34 #include <stdio.h> 35 #include <ctype.h> 36 37 // Programmabh�ngige Includes. 38 #include <hash.hxx> 39 #include <tools/debug.hxx> 40 41 /****************** C O D E **********************************************/ 42 /************************************************************************* 43 |* 44 |* SvStringHashEntry::~SvStringHashEntry() 45 |* 46 |* Beschreibung 47 |* 48 *************************************************************************/ 49 SvStringHashEntry::~SvStringHashEntry() { }; 50 51 /************************************************************************* 52 |* 53 |* SvHashTable::SvHashTable() 54 |* 55 |* Beschreibung 56 |* 57 *************************************************************************/ 58 SvHashTable::SvHashTable( sal_uInt32 nMaxEntries ) 59 { 60 nMax = nMaxEntries; // set max entries 61 nFill = 0; // no entries 62 lTry = 0; 63 lAsk = 0; 64 } 65 66 /************************************************************************* 67 |* 68 |* SvHashTable::~SvHashTable() 69 |* 70 |* Beschreibung 71 |* 72 *************************************************************************/ 73 SvHashTable::~SvHashTable() 74 { 75 #ifdef DOS_NIE 76 printf( "Maximum: %ld, F�llung: %ld\n", (sal_uLong)nMax, (sal_uLong)nFill ); 77 printf( "Anfragen: %ld, Versuche: %ld", (sal_uLong)lAsk, (sal_uLong)lTry ); 78 if( lTry != 0 ) 79 printf( ", V/E = %ld\n", lTry / lAsk ); 80 #endif 81 } 82 83 /************************************************************************* 84 |* 85 |* SvHashTable::Test_Insert() 86 |* 87 |* Beschreibung 88 |* 89 *************************************************************************/ 90 sal_Bool SvHashTable::Test_Insert( const void * pElement, sal_Bool bInsert, 91 sal_uInt32 * pInsertPos ) 92 { 93 sal_uInt32 nHash; 94 sal_uInt32 nIndex; 95 sal_uInt32 nLoop; 96 97 lAsk++; 98 lTry++; 99 100 nHash = HashFunc( pElement ); 101 nIndex = nHash % nMax; 102 103 // const char* s = ((ByteString*) pElement)->GetStr(); 104 // fprintf(stderr,"### Hash: %lu , Name: %s\n",nIndex,s ); 105 106 nLoop = 0; // divide to range 107 while( (nMax != nLoop) && IsEntry( nIndex ) ) 108 { // is place occupied 109 if( COMPARE_EQUAL == Compare( pElement, nIndex ) ) 110 { 111 if( pInsertPos ) 112 *pInsertPos = nIndex; // place of Element 113 return sal_True; 114 } 115 nLoop++; 116 lTry++; 117 nIndex = (sal_uInt16)(nIndex + nHash + 7) % nMax; 118 } 119 120 if( bInsert ) 121 { 122 DBG_ASSERT( nMax != nLoop, "Hash table full" ); 123 if( nMax != nLoop ) 124 { 125 nFill++; 126 *pInsertPos = nIndex; // return free place 127 return sal_True; 128 } 129 } 130 return( sal_False ); 131 } 132 133 /************************************************************************/ 134 /************************************************************************* 135 |* 136 |* SvStringHashTable::SvStringHashTable() 137 |* 138 |* Beschreibung 139 |* 140 *************************************************************************/ 141 SvStringHashTable::SvStringHashTable( sal_uInt32 nMaxEntries ) 142 : SvHashTable( nMaxEntries ) 143 { 144 pEntries = new SvStringHashEntry[ nMaxEntries ]; 145 146 // RefCount auf eins setzen 147 SvStringHashEntry * pPos, *pEnd; 148 pPos = pEntries; 149 pEnd = pEntries + nMaxEntries; 150 while( pPos != pEnd ) 151 { 152 pPos->AddRef(); 153 pPos++; 154 } 155 } 156 157 /************************************************************************* 158 |* 159 |* ~SvStringHashTable::SvStringHashTable() 160 |* 161 |* Beschreibung 162 |* 163 *************************************************************************/ 164 SvStringHashTable::~SvStringHashTable() 165 { 166 // RefCount auf eins setzen 167 SvStringHashEntry * pPos, *pEnd; 168 pPos = pEntries; 169 pEnd = pEntries + GetMax(); 170 #ifdef DBG_UTIL 171 while( pPos != pEnd ) 172 { 173 DBG_ASSERT( pPos->GetRefCount() == 1, "Reference count != 1" ); 174 pPos++; 175 } 176 #endif 177 178 #ifdef MPW 179 // der MPW-Compiler ruft sonst keine Dtoren! 180 for ( sal_uInt16 n = 0; n < GetMax(); ++n ) 181 (pEntries+n)->SvStringHashEntry::~SvStringHashEntry(); 182 delete (void*) pEntries; 183 #else 184 delete [] pEntries; 185 #endif 186 } 187 188 /************************************************************************* 189 |* 190 |* SvStringHashTable::HashFunc() 191 |* 192 |* Beschreibung 193 |* 194 *************************************************************************/ 195 sal_uInt32 SvStringHashTable::HashFunc( const void * pElement ) const 196 { 197 sal_uInt32 nHash = 0; // hash value 198 const char * pStr = ((const ByteString * )pElement)->GetBuffer(); 199 200 int nShift = 0; 201 while( *pStr ) 202 { 203 if( isupper( *pStr ) ) 204 nHash ^= sal_uInt32(*pStr - 'A' + 26) << nShift; 205 else 206 nHash ^= sal_uInt32(*pStr - 'a') << nShift; 207 if( nShift == 28 ) 208 nShift = 0; 209 else 210 nShift += 4; 211 pStr++; 212 } 213 return( nHash ); 214 } 215 216 /************************************************************************* 217 |* 218 |* SvStringHashTable::GetNearString() 219 |* 220 |* Beschreibung 221 |* 222 *************************************************************************/ 223 ByteString SvStringHashTable::GetNearString( const ByteString & rName ) const 224 { 225 for( sal_uInt32 i = 0; i < GetMax(); i++ ) 226 { 227 SvStringHashEntry * pE = Get( i ); 228 if( pE ) 229 { 230 if( pE->GetName().EqualsIgnoreCaseAscii( rName ) && !pE->GetName().Equals( rName ) ) 231 return pE->GetName(); 232 } 233 } 234 return ByteString(); 235 } 236 237 /************************************************************************* 238 |* 239 |* SvStringHashTable::IsEntry() 240 |* 241 |* Beschreibung 242 |* 243 *************************************************************************/ 244 sal_Bool SvStringHashTable::IsEntry( sal_uInt32 nIndex ) const 245 { 246 if( nIndex >= GetMax() ) 247 return sal_False; 248 return pEntries[ nIndex ].HasId(); 249 } 250 251 /************************************************************************* 252 |* 253 |* SvStringHashTable::Insert() 254 |* 255 |* Beschreibung 256 |* 257 *************************************************************************/ 258 sal_Bool SvStringHashTable::Insert( const ByteString & rName, sal_uInt32 * pIndex ) 259 { 260 sal_uInt32 nIndex; 261 262 if( !pIndex ) pIndex = &nIndex; 263 264 if( !SvHashTable::Test_Insert( &rName, sal_True, pIndex ) ) 265 return sal_False; 266 267 if( !IsEntry( *pIndex ) ) 268 pEntries[ *pIndex ] = SvStringHashEntry( rName, *pIndex ); 269 return sal_True; 270 } 271 272 /************************************************************************* 273 |* 274 |* SvStringHashTable::Test() 275 |* 276 |* Beschreibung 277 |* 278 *************************************************************************/ 279 sal_Bool SvStringHashTable::Test( const ByteString & rName, sal_uInt32 * pPos ) const 280 { 281 return ((SvStringHashTable *)this)->SvHashTable:: 282 Test_Insert( &rName, sal_False, pPos ); 283 } 284 285 /************************************************************************* 286 |* 287 |* SvStringHashTable::Get() 288 |* 289 |* Beschreibung 290 |* 291 *************************************************************************/ 292 SvStringHashEntry * SvStringHashTable::Get( sal_uInt32 nIndex ) const 293 { 294 if( IsEntry( nIndex ) ) 295 return pEntries + nIndex; 296 return( NULL ); 297 } 298 299 /************************************************************************* 300 |* 301 |* SvStringHashTable::Get() 302 |* 303 |* Beschreibung 304 |* 305 *************************************************************************/ 306 StringCompare SvStringHashTable::Compare( const void * pElement, 307 sal_uInt32 nIndex ) const 308 { 309 return ((const ByteString *)pElement)->CompareTo( pEntries[ nIndex ].GetName() ); 310 } 311 312 /************************************************************************* 313 |* 314 |* SvStringHashTable::FillHashList() 315 |* 316 |* Beschreibung 317 |* 318 *************************************************************************/ 319 void SvStringHashTable::FillHashList( SvStringHashList * pList ) const 320 { 321 for( sal_uInt32 n = 0; n < GetMax(); n++ ) 322 { 323 if( IsEntry( n ) ) 324 pList->Insert( Get( n ), LIST_APPEND ); 325 } 326 // Hash Reihenfolge, jetzt sortieren 327 } 328