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