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 >
LRU_Cache(sal_Int32 nCachedElements)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 >
~LRU_Cache()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 >
toFront(CacheEntry * pEntry) const125 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 >
hasValue(t_Key const & rKey) const148 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 >
getValue(t_Key const & rKey) const157 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 >
setValue(t_Key const & rKey,t_Val const & rValue)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 >
clear()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 {
operator ()FctHashOUString232 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