1*cdf0e10cSrcweir /************************************************************************* 2*cdf0e10cSrcweir * 3*cdf0e10cSrcweir * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4*cdf0e10cSrcweir * 5*cdf0e10cSrcweir * Copyright 2000, 2010 Oracle and/or its affiliates. 6*cdf0e10cSrcweir * 7*cdf0e10cSrcweir * OpenOffice.org - a multi-platform office productivity suite 8*cdf0e10cSrcweir * 9*cdf0e10cSrcweir * This file is part of OpenOffice.org. 10*cdf0e10cSrcweir * 11*cdf0e10cSrcweir * OpenOffice.org is free software: you can redistribute it and/or modify 12*cdf0e10cSrcweir * it under the terms of the GNU Lesser General Public License version 3 13*cdf0e10cSrcweir * only, as published by the Free Software Foundation. 14*cdf0e10cSrcweir * 15*cdf0e10cSrcweir * OpenOffice.org is distributed in the hope that it will be useful, 16*cdf0e10cSrcweir * but WITHOUT ANY WARRANTY; without even the implied warranty of 17*cdf0e10cSrcweir * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18*cdf0e10cSrcweir * GNU Lesser General Public License version 3 for more details 19*cdf0e10cSrcweir * (a copy is included in the LICENSE file that accompanied this code). 20*cdf0e10cSrcweir * 21*cdf0e10cSrcweir * You should have received a copy of the GNU Lesser General Public License 22*cdf0e10cSrcweir * version 3 along with OpenOffice.org. If not, see 23*cdf0e10cSrcweir * <http://www.openoffice.org/license.html> 24*cdf0e10cSrcweir * for a copy of the LGPLv3 License. 25*cdf0e10cSrcweir * 26*cdf0e10cSrcweir ************************************************************************/ 27*cdf0e10cSrcweir #ifndef _LRU_CACHE_HXX_ 28*cdf0e10cSrcweir #define _LRU_CACHE_HXX_ 29*cdf0e10cSrcweir 30*cdf0e10cSrcweir // __CACHE_DIAGNOSE forces cache size to 4 and works only for OUString keys 31*cdf0e10cSrcweir // #define __CACHE_DIAGNOSE 1 32*cdf0e10cSrcweir 33*cdf0e10cSrcweir #include <osl/mutex.hxx> 34*cdf0e10cSrcweir #include "rtl/ustring.hxx" 35*cdf0e10cSrcweir 36*cdf0e10cSrcweir #include <hash_map> 37*cdf0e10cSrcweir 38*cdf0e10cSrcweir /** Implementation of a least recently used (lru) cache. 39*cdf0e10cSrcweir <br> 40*cdf0e10cSrcweir @author Daniel Boelzle 41*cdf0e10cSrcweir */ 42*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 43*cdf0e10cSrcweir class LRU_Cache 44*cdf0e10cSrcweir { 45*cdf0e10cSrcweir struct CacheEntry 46*cdf0e10cSrcweir { 47*cdf0e10cSrcweir t_Key aKey; 48*cdf0e10cSrcweir t_Val aVal; 49*cdf0e10cSrcweir CacheEntry * pPred; 50*cdf0e10cSrcweir CacheEntry * pSucc; 51*cdf0e10cSrcweir }; 52*cdf0e10cSrcweir typedef ::std::hash_map< t_Key, CacheEntry *, t_KeyHash, t_KeyEqual > t_Key2Element; 53*cdf0e10cSrcweir 54*cdf0e10cSrcweir mutable ::osl::Mutex _aCacheMutex; 55*cdf0e10cSrcweir sal_Int32 _nCachedElements; 56*cdf0e10cSrcweir t_Key2Element _aKey2Element; 57*cdf0e10cSrcweir 58*cdf0e10cSrcweir CacheEntry * _pBlock; 59*cdf0e10cSrcweir mutable CacheEntry * _pHead; 60*cdf0e10cSrcweir mutable CacheEntry * _pTail; 61*cdf0e10cSrcweir inline void toFront( CacheEntry * pEntry ) const; 62*cdf0e10cSrcweir 63*cdf0e10cSrcweir public: 64*cdf0e10cSrcweir /** Constructor: 65*cdf0e10cSrcweir <br> 66*cdf0e10cSrcweir @param nCachedElements number of elements to be cached; default param set to 128 67*cdf0e10cSrcweir */ 68*cdf0e10cSrcweir inline LRU_Cache( sal_Int32 nCachedElements = 128 ); 69*cdf0e10cSrcweir /** Destructor: releases all cached elements and keys. 70*cdf0e10cSrcweir <br> 71*cdf0e10cSrcweir */ 72*cdf0e10cSrcweir inline ~LRU_Cache(); 73*cdf0e10cSrcweir 74*cdf0e10cSrcweir /** Retrieves a value from the cache. Returns default constructed value, 75*cdf0e10cSrcweir if none was found. 76*cdf0e10cSrcweir <br> 77*cdf0e10cSrcweir @param rKey a key 78*cdf0e10cSrcweir @return value 79*cdf0e10cSrcweir */ 80*cdf0e10cSrcweir inline t_Val getValue( const t_Key & rKey ) const; 81*cdf0e10cSrcweir /** Sets a value to be cached for given key. 82*cdf0e10cSrcweir <br> 83*cdf0e10cSrcweir @param rKey a key 84*cdf0e10cSrcweir @param rValue a value 85*cdf0e10cSrcweir */ 86*cdf0e10cSrcweir inline void setValue( const t_Key & rKey, const t_Val & rValue ); 87*cdf0e10cSrcweir /** Tests whether a value is cached for given key. 88*cdf0e10cSrcweir <br> 89*cdf0e10cSrcweir @param rKey a key 90*cdf0e10cSrcweir @return true, if value is cached 91*cdf0e10cSrcweir */ 92*cdf0e10cSrcweir inline sal_Bool hasValue( const t_Key & rKey ) const; 93*cdf0e10cSrcweir /** Clears the cache, thus releasing all cached elements and keys. 94*cdf0e10cSrcweir <br> 95*cdf0e10cSrcweir */ 96*cdf0e10cSrcweir inline void clear(); 97*cdf0e10cSrcweir }; 98*cdf0e10cSrcweir //__________________________________________________________________________________________________ 99*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 100*cdf0e10cSrcweir inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::LRU_Cache( sal_Int32 nCachedElements ) 101*cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE 102*cdf0e10cSrcweir : _nCachedElements( 4 ) 103*cdf0e10cSrcweir #else 104*cdf0e10cSrcweir : _nCachedElements( nCachedElements ) 105*cdf0e10cSrcweir #endif 106*cdf0e10cSrcweir , _pBlock( 0 ) 107*cdf0e10cSrcweir { 108*cdf0e10cSrcweir if (_nCachedElements > 0) 109*cdf0e10cSrcweir { 110*cdf0e10cSrcweir _pBlock = new CacheEntry[_nCachedElements]; 111*cdf0e10cSrcweir _pHead = _pBlock; 112*cdf0e10cSrcweir _pTail = _pBlock + _nCachedElements -1; 113*cdf0e10cSrcweir for ( sal_Int32 nPos = _nCachedElements; nPos--; ) 114*cdf0e10cSrcweir { 115*cdf0e10cSrcweir _pBlock[nPos].pPred = _pBlock + nPos -1; 116*cdf0e10cSrcweir _pBlock[nPos].pSucc = _pBlock + nPos +1; 117*cdf0e10cSrcweir } 118*cdf0e10cSrcweir } 119*cdf0e10cSrcweir } 120*cdf0e10cSrcweir //__________________________________________________________________________________________________ 121*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 122*cdf0e10cSrcweir inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache() 123*cdf0e10cSrcweir { 124*cdf0e10cSrcweir delete [] _pBlock; 125*cdf0e10cSrcweir } 126*cdf0e10cSrcweir //__________________________________________________________________________________________________ 127*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 128*cdf0e10cSrcweir inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront( CacheEntry * pEntry ) const 129*cdf0e10cSrcweir { 130*cdf0e10cSrcweir if (pEntry != _pHead) 131*cdf0e10cSrcweir { 132*cdf0e10cSrcweir // cut out element 133*cdf0e10cSrcweir if (pEntry == _pTail) 134*cdf0e10cSrcweir { 135*cdf0e10cSrcweir _pTail = pEntry->pPred; 136*cdf0e10cSrcweir } 137*cdf0e10cSrcweir else 138*cdf0e10cSrcweir { 139*cdf0e10cSrcweir pEntry->pSucc->pPred = pEntry->pPred; 140*cdf0e10cSrcweir pEntry->pPred->pSucc = pEntry->pSucc; 141*cdf0e10cSrcweir } 142*cdf0e10cSrcweir // push to front 143*cdf0e10cSrcweir _pHead->pPred = pEntry; 144*cdf0e10cSrcweir pEntry->pSucc = _pHead; 145*cdf0e10cSrcweir _pHead = pEntry; 146*cdf0e10cSrcweir } 147*cdf0e10cSrcweir } 148*cdf0e10cSrcweir //__________________________________________________________________________________________________ 149*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 150*cdf0e10cSrcweir inline sal_Bool LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::hasValue( const t_Key & rKey ) const 151*cdf0e10cSrcweir { 152*cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex ); 153*cdf0e10cSrcweir const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) ); 154*cdf0e10cSrcweir return (iFind != _aKey2Element.end()); 155*cdf0e10cSrcweir } 156*cdf0e10cSrcweir //__________________________________________________________________________________________________ 157*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 158*cdf0e10cSrcweir inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue( const t_Key & rKey ) const 159*cdf0e10cSrcweir { 160*cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex ); 161*cdf0e10cSrcweir const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) ); 162*cdf0e10cSrcweir if (iFind != _aKey2Element.end()) 163*cdf0e10cSrcweir { 164*cdf0e10cSrcweir CacheEntry * pEntry = (*iFind).second; 165*cdf0e10cSrcweir toFront( pEntry ); 166*cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE 167*cdf0e10cSrcweir OSL_TRACE( "> retrieved element \"" ); 168*cdf0e10cSrcweir OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() ); 169*cdf0e10cSrcweir OSL_TRACE( "\" from cache <\n" ); 170*cdf0e10cSrcweir #endif 171*cdf0e10cSrcweir return pEntry->aVal; 172*cdf0e10cSrcweir } 173*cdf0e10cSrcweir return t_Val(); 174*cdf0e10cSrcweir } 175*cdf0e10cSrcweir //__________________________________________________________________________________________________ 176*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 177*cdf0e10cSrcweir inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::setValue( 178*cdf0e10cSrcweir const t_Key & rKey, const t_Val & rValue ) 179*cdf0e10cSrcweir { 180*cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex ); 181*cdf0e10cSrcweir if (_nCachedElements > 0) 182*cdf0e10cSrcweir { 183*cdf0e10cSrcweir const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) ); 184*cdf0e10cSrcweir 185*cdf0e10cSrcweir CacheEntry * pEntry; 186*cdf0e10cSrcweir if (iFind == _aKey2Element.end()) 187*cdf0e10cSrcweir { 188*cdf0e10cSrcweir pEntry = _pTail; // erase last element 189*cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE 190*cdf0e10cSrcweir if (pEntry->aKey.getLength()) 191*cdf0e10cSrcweir { 192*cdf0e10cSrcweir OSL_TRACE( "> kicking element \"" ); 193*cdf0e10cSrcweir OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() ); 194*cdf0e10cSrcweir OSL_TRACE( "\" from cache <\n" ); 195*cdf0e10cSrcweir } 196*cdf0e10cSrcweir #endif 197*cdf0e10cSrcweir _aKey2Element.erase( pEntry->aKey ); 198*cdf0e10cSrcweir _aKey2Element[ pEntry->aKey = rKey ] = pEntry; 199*cdf0e10cSrcweir } 200*cdf0e10cSrcweir else 201*cdf0e10cSrcweir { 202*cdf0e10cSrcweir pEntry = (*iFind).second; 203*cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE 204*cdf0e10cSrcweir OSL_TRACE( "> replacing element \"" ); 205*cdf0e10cSrcweir OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() ); 206*cdf0e10cSrcweir OSL_TRACE( "\" in cache <\n" ); 207*cdf0e10cSrcweir #endif 208*cdf0e10cSrcweir } 209*cdf0e10cSrcweir pEntry->aVal = rValue; 210*cdf0e10cSrcweir toFront( pEntry ); 211*cdf0e10cSrcweir } 212*cdf0e10cSrcweir } 213*cdf0e10cSrcweir //__________________________________________________________________________________________________ 214*cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 215*cdf0e10cSrcweir inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::clear() 216*cdf0e10cSrcweir { 217*cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex ); 218*cdf0e10cSrcweir _aKey2Element.clear(); 219*cdf0e10cSrcweir for ( sal_Int32 nPos = _nCachedElements; nPos--; ) 220*cdf0e10cSrcweir { 221*cdf0e10cSrcweir _pBlock[nPos].aKey = t_Key(); 222*cdf0e10cSrcweir _pBlock[nPos].aVal = t_Val(); 223*cdf0e10cSrcweir } 224*cdf0e10cSrcweir _nCachedElements = 0; 225*cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE 226*cdf0e10cSrcweir OSL_TRACE( "> cleared cache <\n" ); 227*cdf0e10cSrcweir #endif 228*cdf0e10cSrcweir } 229*cdf0e10cSrcweir 230*cdf0e10cSrcweir //================================================================================================== 231*cdf0e10cSrcweir struct FctHashOUString : public ::std::unary_function< const ::rtl::OUString &, size_t > 232*cdf0e10cSrcweir { 233*cdf0e10cSrcweir size_t operator()( const ::rtl::OUString & rKey ) const 234*cdf0e10cSrcweir { return rKey.hashCode(); } 235*cdf0e10cSrcweir }; 236*cdf0e10cSrcweir 237*cdf0e10cSrcweir /** Template instance for OUString keys, Any values.<br> 238*cdf0e10cSrcweir */ 239*cdf0e10cSrcweir typedef LRU_Cache< ::rtl::OUString, ::com::sun::star::uno::Any, 240*cdf0e10cSrcweir FctHashOUString, ::std::equal_to< ::rtl::OUString > > 241*cdf0e10cSrcweir LRU_CacheAnyByOUString; 242*cdf0e10cSrcweir 243*cdf0e10cSrcweir 244*cdf0e10cSrcweir #endif 245