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