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