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 35 /** Implementation of a least recently used (lru) cache. 36 <br> 37 @author Daniel Boelzle 38 */ 39 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 40 class LRU_Cache 41 { 42 struct CacheEntry 43 { 44 t_Key aKey; 45 t_Val aVal; 46 CacheEntry * pPred; 47 CacheEntry * pSucc; 48 }; 49 typedef ::std::hash_map< t_Key, CacheEntry *, t_KeyHash, t_KeyEqual > t_Key2Element; 50 51 mutable ::osl::Mutex _aCacheMutex; 52 sal_Int32 _nCachedElements; 53 t_Key2Element _aKey2Element; 54 55 CacheEntry * _pBlock; 56 mutable CacheEntry * _pHead; 57 mutable CacheEntry * _pTail; 58 inline void toFront( CacheEntry * pEntry ) const; 59 60 public: 61 /** Constructor: 62 <br> 63 @param nCachedElements number of elements to be cached; default param set to 128 64 */ 65 inline LRU_Cache( sal_Int32 nCachedElements = 128 ); 66 /** Destructor: releases all cached elements and keys. 67 <br> 68 */ 69 inline ~LRU_Cache(); 70 71 /** Retrieves a value from the cache. Returns default constructed value, 72 if none was found. 73 <br> 74 @param rKey a key 75 @return value 76 */ 77 inline t_Val getValue( t_Key const & rKey ) const; 78 /** Sets a value to be cached for given key. 79 <br> 80 @param rKey a key 81 @param rValue a value 82 */ 83 inline void setValue( t_Key const & rKey, t_Val const & rValue ); 84 /** Tests whether a value is cached for given key. 85 <br> 86 @param rKey a key 87 @return true, if value is cached 88 */ 89 inline sal_Bool hasValue( t_Key const & rKey ) const; 90 /** Clears the cache, thus releasing all cached elements and keys. 91 <br> 92 */ 93 inline void clear(); 94 }; 95 //__________________________________________________________________________________________________ 96 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 97 inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::LRU_Cache( sal_Int32 nCachedElements ) 98 #ifdef __CACHE_DIAGNOSE 99 : _nCachedElements( 4 ) 100 #else 101 : _nCachedElements( nCachedElements ) 102 #endif 103 , _pBlock( 0 ) 104 { 105 if (_nCachedElements > 0) 106 { 107 _pBlock = new CacheEntry[_nCachedElements]; 108 _pHead = _pBlock; 109 _pTail = _pBlock + _nCachedElements -1; 110 for ( sal_Int32 nPos = _nCachedElements; nPos--; ) 111 { 112 _pBlock[nPos].pPred = _pBlock + nPos -1; 113 _pBlock[nPos].pSucc = _pBlock + nPos +1; 114 } 115 } 116 } 117 //__________________________________________________________________________________________________ 118 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 119 inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache() 120 { 121 delete [] _pBlock; 122 } 123 //__________________________________________________________________________________________________ 124 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 125 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront( 126 CacheEntry * pEntry ) const 127 { 128 if (pEntry != _pHead) 129 { 130 // cut out element 131 if (pEntry == _pTail) 132 { 133 _pTail = pEntry->pPred; 134 } 135 else 136 { 137 pEntry->pSucc->pPred = pEntry->pPred; 138 pEntry->pPred->pSucc = pEntry->pSucc; 139 } 140 // push to front 141 _pHead->pPred = pEntry; 142 pEntry->pSucc = _pHead; 143 _pHead = pEntry; 144 } 145 } 146 //__________________________________________________________________________________________________ 147 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 148 inline sal_Bool LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::hasValue( 149 t_Key const & rKey ) const 150 { 151 ::osl::MutexGuard aGuard( _aCacheMutex ); 152 typename t_Key2Element::const_iterator const iFind( _aKey2Element.find( rKey ) ); 153 return (iFind != _aKey2Element.end()); 154 } 155 //__________________________________________________________________________________________________ 156 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual > 157 inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue( 158 t_Key const & 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 t_Key const & rKey, t_Val const & rValue ) 179 { 180 if (_nCachedElements > 0) 181 { 182 ::osl::MutexGuard aGuard( _aCacheMutex ); 183 typename t_Key2Element::const_iterator const 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 #ifdef __CACHE_DIAGNOSE 225 OSL_TRACE( "> cleared cache <\n" ); 226 #endif 227 } 228 229 //================================================================================================== 230 struct FctHashOUString : public ::std::unary_function< ::rtl::OUString const &, size_t > 231 { 232 size_t operator()( ::rtl::OUString const & rKey ) const 233 { return (size_t)rKey.hashCode(); } 234 }; 235 236 /** Template instance for OUString keys, Any values.<br> 237 */ 238 typedef LRU_Cache< ::rtl::OUString, ::com::sun::star::uno::Any, 239 FctHashOUString, ::std::equal_to< ::rtl::OUString > > 240 LRU_CacheAnyByOUString; 241 242 243 #endif 244