xref: /aoo42x/main/stoc/source/tdmanager/lrucache.hxx (revision 1c4c525f)
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