1*1c4c525fSAndrew Rist /**************************************************************
2cdf0e10cSrcweir *
3*1c4c525fSAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
4*1c4c525fSAndrew Rist * or more contributor license agreements. See the NOTICE file
5*1c4c525fSAndrew Rist * distributed with this work for additional information
6*1c4c525fSAndrew Rist * regarding copyright ownership. The ASF licenses this file
7*1c4c525fSAndrew Rist * to you under the Apache License, Version 2.0 (the
8*1c4c525fSAndrew Rist * "License"); you may not use this file except in compliance
9*1c4c525fSAndrew Rist * with the License. You may obtain a copy of the License at
10*1c4c525fSAndrew Rist *
11*1c4c525fSAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
12*1c4c525fSAndrew Rist *
13*1c4c525fSAndrew Rist * Unless required by applicable law or agreed to in writing,
14*1c4c525fSAndrew Rist * software distributed under the License is distributed on an
15*1c4c525fSAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16*1c4c525fSAndrew Rist * KIND, either express or implied. See the License for the
17*1c4c525fSAndrew Rist * specific language governing permissions and limitations
18*1c4c525fSAndrew Rist * under the License.
19*1c4c525fSAndrew Rist *
20*1c4c525fSAndrew Rist *************************************************************/
21*1c4c525fSAndrew Rist
22*1c4c525fSAndrew Rist
23cdf0e10cSrcweir #ifndef _LRU_CACHE_HXX_
24cdf0e10cSrcweir #define _LRU_CACHE_HXX_
25cdf0e10cSrcweir
26cdf0e10cSrcweir // __CACHE_DIAGNOSE forces cache size to 4 and works only for OUString keys
27cdf0e10cSrcweir // #define __CACHE_DIAGNOSE 1
28cdf0e10cSrcweir
29cdf0e10cSrcweir #include <osl/mutex.hxx>
30cdf0e10cSrcweir #include "rtl/ustring.hxx"
31cdf0e10cSrcweir
32cdf0e10cSrcweir #include <hash_map>
33cdf0e10cSrcweir
34cdf0e10cSrcweir /** Implementation of a least recently used (lru) cache.
35cdf0e10cSrcweir <br>
36cdf0e10cSrcweir @author Daniel Boelzle
37cdf0e10cSrcweir */
38cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
39cdf0e10cSrcweir class LRU_Cache
40cdf0e10cSrcweir {
41cdf0e10cSrcweir struct CacheEntry
42cdf0e10cSrcweir {
43cdf0e10cSrcweir t_Key aKey;
44cdf0e10cSrcweir t_Val aVal;
45cdf0e10cSrcweir CacheEntry * pPred;
46cdf0e10cSrcweir CacheEntry * pSucc;
47cdf0e10cSrcweir };
48cdf0e10cSrcweir typedef ::std::hash_map< t_Key, CacheEntry *, t_KeyHash, t_KeyEqual > t_Key2Element;
49cdf0e10cSrcweir
50cdf0e10cSrcweir mutable ::osl::Mutex _aCacheMutex;
51cdf0e10cSrcweir sal_Int32 _nCachedElements;
52cdf0e10cSrcweir t_Key2Element _aKey2Element;
53cdf0e10cSrcweir
54cdf0e10cSrcweir CacheEntry * _pBlock;
55cdf0e10cSrcweir mutable CacheEntry * _pHead;
56cdf0e10cSrcweir mutable CacheEntry * _pTail;
57cdf0e10cSrcweir inline void toFront( CacheEntry * pEntry ) const;
58cdf0e10cSrcweir
59cdf0e10cSrcweir public:
60cdf0e10cSrcweir /** Constructor:
61cdf0e10cSrcweir <br>
62cdf0e10cSrcweir @param nCachedElements number of elements to be cached; default param set to 128
63cdf0e10cSrcweir */
64cdf0e10cSrcweir inline LRU_Cache( sal_Int32 nCachedElements = 128 );
65cdf0e10cSrcweir /** Destructor: releases all cached elements and keys.
66cdf0e10cSrcweir <br>
67cdf0e10cSrcweir */
68cdf0e10cSrcweir inline ~LRU_Cache();
69cdf0e10cSrcweir
70cdf0e10cSrcweir /** Retrieves a value from the cache. Returns default constructed value,
71cdf0e10cSrcweir if none was found.
72cdf0e10cSrcweir <br>
73cdf0e10cSrcweir @param rKey a key
74cdf0e10cSrcweir @return value
75cdf0e10cSrcweir */
76cdf0e10cSrcweir inline t_Val getValue( const t_Key & rKey ) const;
77cdf0e10cSrcweir /** Sets a value to be cached for given key.
78cdf0e10cSrcweir <br>
79cdf0e10cSrcweir @param rKey a key
80cdf0e10cSrcweir @param rValue a value
81cdf0e10cSrcweir */
82cdf0e10cSrcweir inline void setValue( const t_Key & rKey, const t_Val & rValue );
83cdf0e10cSrcweir /** Tests whether a value is cached for given key.
84cdf0e10cSrcweir <br>
85cdf0e10cSrcweir @param rKey a key
86cdf0e10cSrcweir @return true, if value is cached
87cdf0e10cSrcweir */
88cdf0e10cSrcweir inline sal_Bool hasValue( const t_Key & rKey ) const;
89cdf0e10cSrcweir /** Clears the cache, thus releasing all cached elements and keys.
90cdf0e10cSrcweir <br>
91cdf0e10cSrcweir */
92cdf0e10cSrcweir inline void clear();
93cdf0e10cSrcweir };
94cdf0e10cSrcweir //__________________________________________________________________________________________________
95cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
LRU_Cache(sal_Int32 nCachedElements)96cdf0e10cSrcweir inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::LRU_Cache( sal_Int32 nCachedElements )
97cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
98cdf0e10cSrcweir : _nCachedElements( 4 )
99cdf0e10cSrcweir #else
100cdf0e10cSrcweir : _nCachedElements( nCachedElements )
101cdf0e10cSrcweir #endif
102cdf0e10cSrcweir , _pBlock( 0 )
103cdf0e10cSrcweir {
104cdf0e10cSrcweir if (_nCachedElements > 0)
105cdf0e10cSrcweir {
106cdf0e10cSrcweir _pBlock = new CacheEntry[_nCachedElements];
107cdf0e10cSrcweir _pHead = _pBlock;
108cdf0e10cSrcweir _pTail = _pBlock + _nCachedElements -1;
109cdf0e10cSrcweir for ( sal_Int32 nPos = _nCachedElements; nPos--; )
110cdf0e10cSrcweir {
111cdf0e10cSrcweir _pBlock[nPos].pPred = _pBlock + nPos -1;
112cdf0e10cSrcweir _pBlock[nPos].pSucc = _pBlock + nPos +1;
113cdf0e10cSrcweir }
114cdf0e10cSrcweir }
115cdf0e10cSrcweir }
116cdf0e10cSrcweir //__________________________________________________________________________________________________
117cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
~LRU_Cache()118cdf0e10cSrcweir inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache()
119cdf0e10cSrcweir {
120cdf0e10cSrcweir delete [] _pBlock;
121cdf0e10cSrcweir }
122cdf0e10cSrcweir //__________________________________________________________________________________________________
123cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
toFront(CacheEntry * pEntry) const124cdf0e10cSrcweir inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront( CacheEntry * pEntry ) const
125cdf0e10cSrcweir {
126cdf0e10cSrcweir if (pEntry != _pHead)
127cdf0e10cSrcweir {
128cdf0e10cSrcweir // cut out element
129cdf0e10cSrcweir if (pEntry == _pTail)
130cdf0e10cSrcweir {
131cdf0e10cSrcweir _pTail = pEntry->pPred;
132cdf0e10cSrcweir }
133cdf0e10cSrcweir else
134cdf0e10cSrcweir {
135cdf0e10cSrcweir pEntry->pSucc->pPred = pEntry->pPred;
136cdf0e10cSrcweir pEntry->pPred->pSucc = pEntry->pSucc;
137cdf0e10cSrcweir }
138cdf0e10cSrcweir // push to front
139cdf0e10cSrcweir _pHead->pPred = pEntry;
140cdf0e10cSrcweir pEntry->pSucc = _pHead;
141cdf0e10cSrcweir _pHead = pEntry;
142cdf0e10cSrcweir }
143cdf0e10cSrcweir }
144cdf0e10cSrcweir //__________________________________________________________________________________________________
145cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
hasValue(const t_Key & rKey) const146cdf0e10cSrcweir inline sal_Bool LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::hasValue( const t_Key & rKey ) const
147cdf0e10cSrcweir {
148cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex );
149cdf0e10cSrcweir const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
150cdf0e10cSrcweir return (iFind != _aKey2Element.end());
151cdf0e10cSrcweir }
152cdf0e10cSrcweir //__________________________________________________________________________________________________
153cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
getValue(const t_Key & rKey) const154cdf0e10cSrcweir inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue( const t_Key & rKey ) const
155cdf0e10cSrcweir {
156cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex );
157cdf0e10cSrcweir const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
158cdf0e10cSrcweir if (iFind != _aKey2Element.end())
159cdf0e10cSrcweir {
160cdf0e10cSrcweir CacheEntry * pEntry = (*iFind).second;
161cdf0e10cSrcweir toFront( pEntry );
162cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
163cdf0e10cSrcweir OSL_TRACE( "> retrieved element \"" );
164cdf0e10cSrcweir OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
165cdf0e10cSrcweir OSL_TRACE( "\" from cache <\n" );
166cdf0e10cSrcweir #endif
167cdf0e10cSrcweir return pEntry->aVal;
168cdf0e10cSrcweir }
169cdf0e10cSrcweir return t_Val();
170cdf0e10cSrcweir }
171cdf0e10cSrcweir //__________________________________________________________________________________________________
172cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
setValue(const t_Key & rKey,const t_Val & rValue)173cdf0e10cSrcweir inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::setValue(
174cdf0e10cSrcweir const t_Key & rKey, const t_Val & rValue )
175cdf0e10cSrcweir {
176cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex );
177cdf0e10cSrcweir if (_nCachedElements > 0)
178cdf0e10cSrcweir {
179cdf0e10cSrcweir const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
180cdf0e10cSrcweir
181cdf0e10cSrcweir CacheEntry * pEntry;
182cdf0e10cSrcweir if (iFind == _aKey2Element.end())
183cdf0e10cSrcweir {
184cdf0e10cSrcweir pEntry = _pTail; // erase last element
185cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
186cdf0e10cSrcweir if (pEntry->aKey.getLength())
187cdf0e10cSrcweir {
188cdf0e10cSrcweir OSL_TRACE( "> kicking element \"" );
189cdf0e10cSrcweir OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
190cdf0e10cSrcweir OSL_TRACE( "\" from cache <\n" );
191cdf0e10cSrcweir }
192cdf0e10cSrcweir #endif
193cdf0e10cSrcweir _aKey2Element.erase( pEntry->aKey );
194cdf0e10cSrcweir _aKey2Element[ pEntry->aKey = rKey ] = pEntry;
195cdf0e10cSrcweir }
196cdf0e10cSrcweir else
197cdf0e10cSrcweir {
198cdf0e10cSrcweir pEntry = (*iFind).second;
199cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
200cdf0e10cSrcweir OSL_TRACE( "> replacing element \"" );
201cdf0e10cSrcweir OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
202cdf0e10cSrcweir OSL_TRACE( "\" in cache <\n" );
203cdf0e10cSrcweir #endif
204cdf0e10cSrcweir }
205cdf0e10cSrcweir pEntry->aVal = rValue;
206cdf0e10cSrcweir toFront( pEntry );
207cdf0e10cSrcweir }
208cdf0e10cSrcweir }
209cdf0e10cSrcweir //__________________________________________________________________________________________________
210cdf0e10cSrcweir template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
clear()211cdf0e10cSrcweir inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::clear()
212cdf0e10cSrcweir {
213cdf0e10cSrcweir ::osl::MutexGuard aGuard( _aCacheMutex );
214cdf0e10cSrcweir _aKey2Element.clear();
215cdf0e10cSrcweir for ( sal_Int32 nPos = _nCachedElements; nPos--; )
216cdf0e10cSrcweir {
217cdf0e10cSrcweir _pBlock[nPos].aKey = t_Key();
218cdf0e10cSrcweir _pBlock[nPos].aVal = t_Val();
219cdf0e10cSrcweir }
220cdf0e10cSrcweir _nCachedElements = 0;
221cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
222cdf0e10cSrcweir OSL_TRACE( "> cleared cache <\n" );
223cdf0e10cSrcweir #endif
224cdf0e10cSrcweir }
225cdf0e10cSrcweir
226cdf0e10cSrcweir //==================================================================================================
227cdf0e10cSrcweir struct FctHashOUString : public ::std::unary_function< const ::rtl::OUString &, size_t >
228cdf0e10cSrcweir {
operator ()FctHashOUString229cdf0e10cSrcweir size_t operator()( const ::rtl::OUString & rKey ) const
230cdf0e10cSrcweir { return rKey.hashCode(); }
231cdf0e10cSrcweir };
232cdf0e10cSrcweir
233cdf0e10cSrcweir /** Template instance for OUString keys, Any values.<br>
234cdf0e10cSrcweir */
235cdf0e10cSrcweir typedef LRU_Cache< ::rtl::OUString, ::com::sun::star::uno::Any,
236cdf0e10cSrcweir FctHashOUString, ::std::equal_to< ::rtl::OUString > >
237cdf0e10cSrcweir LRU_CacheAnyByOUString;
238cdf0e10cSrcweir
239cdf0e10cSrcweir
240cdf0e10cSrcweir #endif
241