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 >
LRU_Cache(sal_Int32 nCachedElements)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 >
~LRU_Cache()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 >
toFront(CacheEntry * pEntry) const124 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 >
hasValue(const t_Key & rKey) const146 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 >
getValue(const t_Key & rKey) const154 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 >
setValue(const t_Key & rKey,const t_Val & rValue)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 >
clear()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 {
operator ()FctHashOUString229 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