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 979712 : 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 2094 : 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 2094 : , _pBlock( 0 )
99 : {
100 2094 : if (_nCachedElements > 0)
101 : {
102 2094 : _pBlock = new CacheEntry[_nCachedElements];
103 2094 : _pHead = _pBlock;
104 2094 : _pTail = _pBlock + _nCachedElements -1;
105 540252 : for ( sal_Int32 nPos = _nCachedElements; nPos--; )
106 : {
107 536064 : _pBlock[nPos].pPred = _pBlock + nPos -1;
108 536064 : _pBlock[nPos].pSucc = _pBlock + nPos +1;
109 : }
110 : }
111 2094 : }
112 : //__________________________________________________________________________________________________
113 : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
114 1733 : inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache()
115 : {
116 1733 : delete [] _pBlock;
117 1733 : }
118 : //__________________________________________________________________________________________________
119 : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
120 167060 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront( CacheEntry * pEntry ) const
121 : {
122 167060 : if (pEntry != _pHead)
123 : {
124 : // cut out element
125 114667 : if (pEntry == _pTail)
126 : {
127 8162 : _pTail = pEntry->pPred;
128 : }
129 : else
130 : {
131 106505 : pEntry->pSucc->pPred = pEntry->pPred;
132 106505 : pEntry->pPred->pSucc = pEntry->pSucc;
133 : }
134 : // push to front
135 114667 : _pHead->pPred = pEntry;
136 114667 : pEntry->pSucc = _pHead;
137 114667 : _pHead = pEntry;
138 : }
139 167060 : }
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 167076 : inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue( const t_Key & rKey ) const
151 : {
152 167076 : ::osl::MutexGuard aGuard( _aCacheMutex );
153 167076 : const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
154 167076 : if (iFind != _aKey2Element.end())
155 : {
156 158898 : CacheEntry * pEntry = (*iFind).second;
157 158898 : 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 158898 : return pEntry->aVal;
164 : }
165 8178 : return t_Val();
166 : }
167 : //__________________________________________________________________________________________________
168 : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
169 8178 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::setValue(
170 : const t_Key & rKey, const t_Val & rValue )
171 : {
172 8178 : ::osl::MutexGuard aGuard( _aCacheMutex );
173 8178 : if (_nCachedElements > 0)
174 : {
175 8162 : const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
176 :
177 : CacheEntry * pEntry;
178 8162 : if (iFind == _aKey2Element.end())
179 : {
180 8162 : 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 8162 : _aKey2Element.erase( pEntry->aKey );
190 8162 : _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 8162 : pEntry->aVal = rValue;
202 8162 : toFront( pEntry );
203 : }
204 8178 : }
205 : //__________________________________________________________________________________________________
206 : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
207 2044 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::clear()
208 : {
209 2044 : ::osl::MutexGuard aGuard( _aCacheMutex );
210 2044 : _aKey2Element.clear();
211 527352 : for ( sal_Int32 nPos = _nCachedElements; nPos--; )
212 : {
213 523264 : _pBlock[nPos].aKey = t_Key();
214 523264 : _pBlock[nPos].aVal = t_Val();
215 : }
216 2044 : _nCachedElements = 0;
217 : #ifdef __CACHE_DIAGNOSE
218 : OSL_TRACE( "> cleared cache <" );
219 : #endif
220 2044 : }
221 :
222 : //==================================================================================================
223 : struct FctHashOUString : public ::std::unary_function< const ::rtl::OUString &, size_t >
224 : {
225 185383 : size_t operator()( const ::rtl::OUString & rKey ) const
226 185383 : { 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: */
|
