1*2123d757SAndrew Rist /**************************************************************
2cdf0e10cSrcweir *
3*2123d757SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
4*2123d757SAndrew Rist * or more contributor license agreements. See the NOTICE file
5*2123d757SAndrew Rist * distributed with this work for additional information
6*2123d757SAndrew Rist * regarding copyright ownership. The ASF licenses this file
7*2123d757SAndrew Rist * to you under the Apache License, Version 2.0 (the
8*2123d757SAndrew Rist * "License"); you may not use this file except in compliance
9*2123d757SAndrew Rist * with the License. You may obtain a copy of the License at
10*2123d757SAndrew Rist *
11*2123d757SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
12*2123d757SAndrew Rist *
13*2123d757SAndrew Rist * Unless required by applicable law or agreed to in writing,
14*2123d757SAndrew Rist * software distributed under the License is distributed on an
15*2123d757SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16*2123d757SAndrew Rist * KIND, either express or implied. See the License for the
17*2123d757SAndrew Rist * specific language governing permissions and limitations
18*2123d757SAndrew Rist * under the License.
19*2123d757SAndrew Rist *
20*2123d757SAndrew Rist *************************************************************/
21*2123d757SAndrew Rist
22*2123d757SAndrew Rist
23cdf0e10cSrcweir #ifndef _STOC_SEC_LRU_CACHE_H_
24cdf0e10cSrcweir #define _STOC_SEC_LRU_CACHE_H_
25cdf0e10cSrcweir
26cdf0e10cSrcweir #include <hash_map>
27cdf0e10cSrcweir
28cdf0e10cSrcweir // __CACHE_DIAGNOSE works only for OUString keys
29cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
30cdf0e10cSrcweir #include <osl/diagnose.h>
31cdf0e10cSrcweir #include <rtl/ustrbuf.hxx>
32cdf0e10cSrcweir #include <rtl/ustring.hxx>
33cdf0e10cSrcweir #include <rtl/string.hxx>
34cdf0e10cSrcweir #endif
35cdf0e10cSrcweir
36cdf0e10cSrcweir
37cdf0e10cSrcweir namespace stoc_sec
38cdf0e10cSrcweir {
39cdf0e10cSrcweir
40cdf0e10cSrcweir /** Implementation of a least recently used (lru) cache.
41cdf0e10cSrcweir */
42cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
43cdf0e10cSrcweir class lru_cache
44cdf0e10cSrcweir {
45cdf0e10cSrcweir struct Entry
46cdf0e10cSrcweir {
47cdf0e10cSrcweir t_key m_key;
48cdf0e10cSrcweir t_val m_val;
49cdf0e10cSrcweir Entry * m_pred;
50cdf0e10cSrcweir Entry * m_succ;
51cdf0e10cSrcweir };
52cdf0e10cSrcweir typedef ::std::hash_map< t_key, Entry *, t_hashKey, t_equalKey > t_key2element;
53cdf0e10cSrcweir t_key2element m_key2element;
54cdf0e10cSrcweir ::std::size_t m_size;
55cdf0e10cSrcweir
56cdf0e10cSrcweir Entry * m_block;
57cdf0e10cSrcweir mutable Entry * m_head;
58cdf0e10cSrcweir mutable Entry * m_tail;
59cdf0e10cSrcweir inline void toFront( Entry * entry ) const SAL_THROW( () );
60cdf0e10cSrcweir
61cdf0e10cSrcweir public:
62cdf0e10cSrcweir /** Default Ctor. Does not cache.
63cdf0e10cSrcweir */
64cdf0e10cSrcweir inline lru_cache() SAL_THROW( () );
65cdf0e10cSrcweir /** Ctor.
66cdf0e10cSrcweir
67cdf0e10cSrcweir @param size number of elements to be cached; default param set to 128
68cdf0e10cSrcweir */
69cdf0e10cSrcweir inline lru_cache( ::std::size_t size ) SAL_THROW( () );
70cdf0e10cSrcweir
71cdf0e10cSrcweir /** Destructor: releases all cached elements and keys.
72cdf0e10cSrcweir */
73cdf0e10cSrcweir inline ~lru_cache() SAL_THROW( () );
74cdf0e10cSrcweir
75cdf0e10cSrcweir /** Retrieves a pointer to value in cache. Returns 0, if none was found.
76cdf0e10cSrcweir
77cdf0e10cSrcweir @param key a key
78cdf0e10cSrcweir @return pointer to value or 0
79cdf0e10cSrcweir */
80cdf0e10cSrcweir inline t_val const * lookup( t_key const & key ) const SAL_THROW( () );
81cdf0e10cSrcweir
82cdf0e10cSrcweir /** Sets a value to be cached for given key.
83cdf0e10cSrcweir
84cdf0e10cSrcweir @param key a key
85cdf0e10cSrcweir @param val a value
86cdf0e10cSrcweir */
87cdf0e10cSrcweir inline void set( t_key const & key, t_val const & val ) SAL_THROW( () );
88cdf0e10cSrcweir
89cdf0e10cSrcweir /** Tests whether a value is cached for given key.
90cdf0e10cSrcweir
91cdf0e10cSrcweir @param key a key
92cdf0e10cSrcweir @return true, if value is cached
93cdf0e10cSrcweir */
94cdf0e10cSrcweir inline bool has( t_key const & key ) const SAL_THROW( () );
95cdf0e10cSrcweir
96cdf0e10cSrcweir /** Clears the cache, releasing all cached elements and keys.
97cdf0e10cSrcweir */
98cdf0e10cSrcweir inline void clear() SAL_THROW( () );
99cdf0e10cSrcweir
100cdf0e10cSrcweir /** Sets the number of elements to be cached. This will clear previous entries.
101cdf0e10cSrcweir
102cdf0e10cSrcweir @param cacheSize number of elements to be cached
103cdf0e10cSrcweir */
104cdf0e10cSrcweir inline void setSize( ::std::size_t size ) SAL_THROW( () );
105cdf0e10cSrcweir };
106cdf0e10cSrcweir //__________________________________________________________________________________________________
107cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
setSize(::std::size_t size)108cdf0e10cSrcweir inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::setSize(
109cdf0e10cSrcweir ::std::size_t size ) SAL_THROW( () )
110cdf0e10cSrcweir {
111cdf0e10cSrcweir m_key2element.clear();
112cdf0e10cSrcweir delete [] m_block;
113cdf0e10cSrcweir m_block = 0;
114cdf0e10cSrcweir m_size = size;
115cdf0e10cSrcweir
116cdf0e10cSrcweir if (0 < m_size)
117cdf0e10cSrcweir {
118cdf0e10cSrcweir m_block = new Entry[ m_size ];
119cdf0e10cSrcweir m_head = m_block;
120cdf0e10cSrcweir m_tail = m_block + m_size -1;
121cdf0e10cSrcweir for ( ::std::size_t nPos = m_size; nPos--; )
122cdf0e10cSrcweir {
123cdf0e10cSrcweir m_block[ nPos ].m_pred = m_block + nPos -1;
124cdf0e10cSrcweir m_block[ nPos ].m_succ = m_block + nPos +1;
125cdf0e10cSrcweir }
126cdf0e10cSrcweir }
127cdf0e10cSrcweir }
128cdf0e10cSrcweir //__________________________________________________________________________________________________
129cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
lru_cache(::std::size_t size)130cdf0e10cSrcweir inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache(
131cdf0e10cSrcweir ::std::size_t size ) SAL_THROW( () )
132cdf0e10cSrcweir : m_size( 0 )
133cdf0e10cSrcweir , m_block( 0 )
134cdf0e10cSrcweir {
135cdf0e10cSrcweir setSize( size );
136cdf0e10cSrcweir }
137cdf0e10cSrcweir //__________________________________________________________________________________________________
138cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
lru_cache()139cdf0e10cSrcweir inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache() SAL_THROW( () )
140cdf0e10cSrcweir : m_size( 0 )
141cdf0e10cSrcweir , m_block( 0 )
142cdf0e10cSrcweir {
143cdf0e10cSrcweir }
144cdf0e10cSrcweir //__________________________________________________________________________________________________
145cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
~lru_cache()146cdf0e10cSrcweir inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::~lru_cache()
147cdf0e10cSrcweir SAL_THROW( () )
148cdf0e10cSrcweir {
149cdf0e10cSrcweir delete [] m_block;
150cdf0e10cSrcweir }
151cdf0e10cSrcweir //__________________________________________________________________________________________________
152cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
toFront(Entry * entry) const153cdf0e10cSrcweir inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::toFront(
154cdf0e10cSrcweir Entry * entry ) const SAL_THROW( () )
155cdf0e10cSrcweir {
156cdf0e10cSrcweir if (entry != m_head)
157cdf0e10cSrcweir {
158cdf0e10cSrcweir // cut out element
159cdf0e10cSrcweir if (entry == m_tail)
160cdf0e10cSrcweir {
161cdf0e10cSrcweir m_tail = entry->m_pred;
162cdf0e10cSrcweir }
163cdf0e10cSrcweir else
164cdf0e10cSrcweir {
165cdf0e10cSrcweir entry->m_succ->m_pred = entry->m_pred;
166cdf0e10cSrcweir entry->m_pred->m_succ = entry->m_succ;
167cdf0e10cSrcweir }
168cdf0e10cSrcweir // push to front
169cdf0e10cSrcweir m_head->m_pred = entry;
170cdf0e10cSrcweir entry->m_succ = m_head;
171cdf0e10cSrcweir m_head = entry;
172cdf0e10cSrcweir }
173cdf0e10cSrcweir }
174cdf0e10cSrcweir //__________________________________________________________________________________________________
175cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
has(t_key const & key) const176cdf0e10cSrcweir inline bool lru_cache< t_key, t_val, t_hashKey, t_equalKey >::has(
177cdf0e10cSrcweir t_key const & key ) const SAL_THROW( () )
178cdf0e10cSrcweir {
179cdf0e10cSrcweir typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
180cdf0e10cSrcweir return (iFind != m_key2element.end());
181cdf0e10cSrcweir }
182cdf0e10cSrcweir //__________________________________________________________________________________________________
183cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
lookup(t_key const & key) const184cdf0e10cSrcweir inline t_val const * lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lookup(
185cdf0e10cSrcweir t_key const & key ) const SAL_THROW( () )
186cdf0e10cSrcweir {
187cdf0e10cSrcweir if (0 < m_size)
188cdf0e10cSrcweir {
189cdf0e10cSrcweir typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
190cdf0e10cSrcweir if (iFind != m_key2element.end())
191cdf0e10cSrcweir {
192cdf0e10cSrcweir Entry * entry = iFind->second;
193cdf0e10cSrcweir toFront( entry );
194cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
195cdf0e10cSrcweir ::rtl::OUStringBuffer buf( 48 );
196cdf0e10cSrcweir buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> retrieved element \"") );
197cdf0e10cSrcweir buf.append( entry->m_key );
198cdf0e10cSrcweir buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
199cdf0e10cSrcweir ::rtl::OString str( ::rtl::OUStringToOString(
200cdf0e10cSrcweir buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
201cdf0e10cSrcweir OSL_TRACE( str.getStr() );
202cdf0e10cSrcweir #endif
203cdf0e10cSrcweir return &entry->m_val;
204cdf0e10cSrcweir }
205cdf0e10cSrcweir }
206cdf0e10cSrcweir return 0;
207cdf0e10cSrcweir }
208cdf0e10cSrcweir //__________________________________________________________________________________________________
209cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
set(t_key const & key,t_val const & val)210cdf0e10cSrcweir inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::set(
211cdf0e10cSrcweir t_key const & key, t_val const & val ) SAL_THROW( () )
212cdf0e10cSrcweir {
213cdf0e10cSrcweir if (0 < m_size)
214cdf0e10cSrcweir {
215cdf0e10cSrcweir typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
216cdf0e10cSrcweir
217cdf0e10cSrcweir Entry * entry;
218cdf0e10cSrcweir if (iFind == m_key2element.end())
219cdf0e10cSrcweir {
220cdf0e10cSrcweir entry = m_tail; // erase last element
221cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
222cdf0e10cSrcweir if (entry->m_key.getLength())
223cdf0e10cSrcweir {
224cdf0e10cSrcweir ::rtl::OUStringBuffer buf( 48 );
225cdf0e10cSrcweir buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> kicking element \"") );
226cdf0e10cSrcweir buf.append( entry->m_key );
227cdf0e10cSrcweir buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
228cdf0e10cSrcweir ::rtl::OString str( ::rtl::OUStringToOString(
229cdf0e10cSrcweir buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
230cdf0e10cSrcweir OSL_TRACE( str.getStr() );
231cdf0e10cSrcweir }
232cdf0e10cSrcweir #endif
233cdf0e10cSrcweir m_key2element.erase( entry->m_key );
234cdf0e10cSrcweir entry->m_key = key;
235cdf0e10cSrcweir ::std::pair< typename t_key2element::iterator, bool > insertion(
236cdf0e10cSrcweir m_key2element.insert( typename t_key2element::value_type( key, entry ) ) );
237cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
238cdf0e10cSrcweir OSL_ENSURE( insertion.second, "### inserting new cache entry failed?!" );
239cdf0e10cSrcweir #endif
240cdf0e10cSrcweir }
241cdf0e10cSrcweir else
242cdf0e10cSrcweir {
243cdf0e10cSrcweir entry = iFind->second;
244cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
245cdf0e10cSrcweir ::rtl::OUStringBuffer buf( 48 );
246cdf0e10cSrcweir buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> replacing element \"") );
247cdf0e10cSrcweir buf.append( entry->m_key );
248cdf0e10cSrcweir buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" in cache") );
249cdf0e10cSrcweir ::rtl::OString str( ::rtl::OUStringToOString(
250cdf0e10cSrcweir buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
251cdf0e10cSrcweir OSL_TRACE( str.getStr() );
252cdf0e10cSrcweir #endif
253cdf0e10cSrcweir }
254cdf0e10cSrcweir entry->m_val = val;
255cdf0e10cSrcweir toFront( entry );
256cdf0e10cSrcweir }
257cdf0e10cSrcweir }
258cdf0e10cSrcweir //__________________________________________________________________________________________________
259cdf0e10cSrcweir template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
clear()260cdf0e10cSrcweir inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::clear() SAL_THROW( () )
261cdf0e10cSrcweir {
262cdf0e10cSrcweir m_key2element.clear();
263cdf0e10cSrcweir for ( ::std::size_t nPos = m_size; nPos--; )
264cdf0e10cSrcweir {
265cdf0e10cSrcweir m_block[ nPos ].m_key = t_key();
266cdf0e10cSrcweir m_block[ nPos ].m_val = t_val();
267cdf0e10cSrcweir }
268cdf0e10cSrcweir #ifdef __CACHE_DIAGNOSE
269cdf0e10cSrcweir OSL_TRACE( "> cleared cache\n" );
270cdf0e10cSrcweir #endif
271cdf0e10cSrcweir }
272cdf0e10cSrcweir
273cdf0e10cSrcweir }
274cdf0e10cSrcweir
275cdf0e10cSrcweir #endif
276