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