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 #ifndef _LRU_CACHE_HXX_ 28 #define _LRU_CACHE_HXX_ 29 30 // __CACHE_DIAGNOSE forces cache size to 4 and works only for OUString keys 31 // #define __CACHE_DIAGNOSE 1 32 33 #include <osl/mutex.hxx> 34 #include "rtl/ustring.hxx" 35 36 #include <hash_map> 37 38 /** Implementation of a least recently used (lru) cache. 39 <br> 40 @author Daniel Boelzle 41 */ 42 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 43 class LRU_Cache 44 { 45 struct CacheEntry 46 { 47 t_Key aKey; 48 t_Val aVal; 49 CacheEntry * pPred; 50 CacheEntry * pSucc; 51 }; 52 typedef ::std::hash_map< t_Key, CacheEntry *, t_KeyHash, t_KeyEqual > t_Key2Element; 53 54 mutable ::osl::Mutex _aCacheMutex; 55 sal_Int32 _nCachedElements; 56 t_Key2Element _aKey2Element; 57 58 CacheEntry * _pBlock; 59 mutable CacheEntry * _pHead; 60 mutable CacheEntry * _pTail; 61 inline void toFront( CacheEntry * pEntry ) const; 62 63 public: 64 /** Constructor: 65 <br> 66 @param nCachedElements number of elements to be cached; default param set to 128 67 */ 68 inline LRU_Cache( sal_Int32 nCachedElements = 128 ); 69 /** Destructor: releases all cached elements and keys. 70 <br> 71 */ 72 inline ~LRU_Cache(); 73 74 /** Retrieves a value from the cache. Returns default constructed value, 75 if none was found. 76 <br> 77 @param rKey a key 78 @return value 79 */ 80 inline t_Val getValue( const t_Key & rKey ) const; 81 /** Sets a value to be cached for given key. 82 <br> 83 @param rKey a key 84 @param rValue a value 85 */ 86 inline void setValue( const t_Key & rKey, const t_Val & rValue ); 87 /** Tests whether a value is cached for given key. 88 <br> 89 @param rKey a key 90 @return true, if value is cached 91 */ 92 inline sal_Bool hasValue( const t_Key & rKey ) const; 93 /** Clears the cache, thus releasing all cached elements and keys. 94 <br> 95 */ 96 inline void clear(); 97 }; 98 //__________________________________________________________________________________________________ 99 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 100 inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::LRU_Cache( sal_Int32 nCachedElements ) 101 #ifdef __CACHE_DIAGNOSE 102 : _nCachedElements( 4 ) 103 #else 104 : _nCachedElements( nCachedElements ) 105 #endif 106 , _pBlock( 0 ) 107 { 108 if (_nCachedElements > 0) 109 { 110 _pBlock = new CacheEntry[_nCachedElements]; 111 _pHead = _pBlock; 112 _pTail = _pBlock + _nCachedElements -1; 113 for ( sal_Int32 nPos = _nCachedElements; nPos--; ) 114 { 115 _pBlock[nPos].pPred = _pBlock + nPos -1; 116 _pBlock[nPos].pSucc = _pBlock + nPos +1; 117 } 118 } 119 } 120 //__________________________________________________________________________________________________ 121 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 122 inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache() 123 { 124 delete [] _pBlock; 125 } 126 //__________________________________________________________________________________________________ 127 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 128 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront( CacheEntry * pEntry ) const 129 { 130 if (pEntry != _pHead) 131 { 132 // cut out element 133 if (pEntry == _pTail) 134 { 135 _pTail = pEntry->pPred; 136 } 137 else 138 { 139 pEntry->pSucc->pPred = pEntry->pPred; 140 pEntry->pPred->pSucc = pEntry->pSucc; 141 } 142 // push to front 143 _pHead->pPred = pEntry; 144 pEntry->pSucc = _pHead; 145 _pHead = pEntry; 146 } 147 } 148 //__________________________________________________________________________________________________ 149 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 150 inline sal_Bool LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::hasValue( const t_Key & rKey ) const 151 { 152 ::osl::MutexGuard aGuard( _aCacheMutex ); 153 const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) ); 154 return (iFind != _aKey2Element.end()); 155 } 156 //__________________________________________________________________________________________________ 157 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 158 inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue( const t_Key & rKey ) const 159 { 160 ::osl::MutexGuard aGuard( _aCacheMutex ); 161 const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) ); 162 if (iFind != _aKey2Element.end()) 163 { 164 CacheEntry * pEntry = (*iFind).second; 165 toFront( pEntry ); 166 #ifdef __CACHE_DIAGNOSE 167 OSL_TRACE( "> retrieved element \"" ); 168 OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() ); 169 OSL_TRACE( "\" from cache <\n" ); 170 #endif 171 return pEntry->aVal; 172 } 173 return t_Val(); 174 } 175 //__________________________________________________________________________________________________ 176 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 177 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::setValue( 178 const t_Key & rKey, const t_Val & rValue ) 179 { 180 ::osl::MutexGuard aGuard( _aCacheMutex ); 181 if (_nCachedElements > 0) 182 { 183 const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) ); 184 185 CacheEntry * pEntry; 186 if (iFind == _aKey2Element.end()) 187 { 188 pEntry = _pTail; // erase last element 189 #ifdef __CACHE_DIAGNOSE 190 if (pEntry->aKey.getLength()) 191 { 192 OSL_TRACE( "> kicking element \"" ); 193 OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() ); 194 OSL_TRACE( "\" from cache <\n" ); 195 } 196 #endif 197 _aKey2Element.erase( pEntry->aKey ); 198 _aKey2Element[ pEntry->aKey = rKey ] = pEntry; 199 } 200 else 201 { 202 pEntry = (*iFind).second; 203 #ifdef __CACHE_DIAGNOSE 204 OSL_TRACE( "> replacing element \"" ); 205 OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() ); 206 OSL_TRACE( "\" in cache <\n" ); 207 #endif 208 } 209 pEntry->aVal = rValue; 210 toFront( pEntry ); 211 } 212 } 213 //__________________________________________________________________________________________________ 214 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 215 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::clear() 216 { 217 ::osl::MutexGuard aGuard( _aCacheMutex ); 218 _aKey2Element.clear(); 219 for ( sal_Int32 nPos = _nCachedElements; nPos--; ) 220 { 221 _pBlock[nPos].aKey = t_Key(); 222 _pBlock[nPos].aVal = t_Val(); 223 } 224 _nCachedElements = 0; 225 #ifdef __CACHE_DIAGNOSE 226 OSL_TRACE( "> cleared cache <\n" ); 227 #endif 228 } 229 230 //================================================================================================== 231 struct FctHashOUString : public ::std::unary_function< const ::rtl::OUString &, size_t > 232 { 233 size_t operator()( const ::rtl::OUString & rKey ) const 234 { return rKey.hashCode(); } 235 }; 236 237 /** Template instance for OUString keys, Any values.<br> 238 */ 239 typedef LRU_Cache< ::rtl::OUString, ::com::sun::star::uno::Any, 240 FctHashOUString, ::std::equal_to< ::rtl::OUString > > 241 LRU_CacheAnyByOUString; 242 243 244 #endif 245