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