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