xref: /aoo41x/main/stoc/source/security/lru_cache.h (revision 2123d757)
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 _STOC_SEC_LRU_CACHE_H_
24 #define _STOC_SEC_LRU_CACHE_H_
25 
26 #include <hash_map>
27 
28 // __CACHE_DIAGNOSE works only for OUString keys
29 #ifdef __CACHE_DIAGNOSE
30 #include <osl/diagnose.h>
31 #include <rtl/ustrbuf.hxx>
32 #include <rtl/ustring.hxx>
33 #include <rtl/string.hxx>
34 #endif
35 
36 
37 namespace stoc_sec
38 {
39 
40 /** Implementation of a least recently used (lru) cache.
41 */
42 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
43 class lru_cache
44 {
45     struct Entry
46     {
47         t_key m_key;
48         t_val m_val;
49         Entry * m_pred;
50         Entry * m_succ;
51     };
52     typedef ::std::hash_map< t_key, Entry *, t_hashKey, t_equalKey > t_key2element;
53     t_key2element m_key2element;
54     ::std::size_t m_size;
55 
56     Entry * m_block;
57     mutable Entry * m_head;
58     mutable Entry * m_tail;
59     inline void toFront( Entry * entry ) const SAL_THROW( () );
60 
61 public:
62     /** Default Ctor.  Does not cache.
63     */
64     inline lru_cache() SAL_THROW( () );
65     /** Ctor.
66 
67         @param size number of elements to be cached; default param set to 128
68     */
69     inline lru_cache( ::std::size_t size ) SAL_THROW( () );
70 
71     /** Destructor: releases all cached elements and keys.
72     */
73     inline ~lru_cache() SAL_THROW( () );
74 
75     /** Retrieves a pointer to value in cache.  Returns 0, if none was found.
76 
77         @param key a key
78         @return pointer to value or 0
79     */
80     inline t_val const * lookup( t_key const & key ) const SAL_THROW( () );
81 
82     /** Sets a value to be cached for given key.
83 
84         @param key a key
85         @param val a value
86     */
87     inline void set( t_key const & key, t_val const & val ) SAL_THROW( () );
88 
89     /** Tests whether a value is cached for given key.
90 
91         @param key a key
92         @return true, if value is cached
93     */
94     inline bool has( t_key const & key ) const SAL_THROW( () );
95 
96     /** Clears the cache, releasing all cached elements and keys.
97     */
98     inline void clear() SAL_THROW( () );
99 
100     /** Sets the number of elements to be cached.  This will clear previous entries.
101 
102         @param cacheSize number of elements to be cached
103     */
104     inline void setSize( ::std::size_t size ) SAL_THROW( () );
105 };
106 //__________________________________________________________________________________________________
107 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
setSize(::std::size_t size)108 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::setSize(
109     ::std::size_t size ) SAL_THROW( () )
110 {
111     m_key2element.clear();
112     delete [] m_block;
113     m_block = 0;
114     m_size = size;
115 
116     if (0 < m_size)
117     {
118         m_block = new Entry[ m_size ];
119         m_head = m_block;
120         m_tail = m_block + m_size -1;
121         for ( ::std::size_t nPos = m_size; nPos--; )
122         {
123             m_block[ nPos ].m_pred = m_block + nPos -1;
124             m_block[ nPos ].m_succ = m_block + nPos +1;
125         }
126     }
127 }
128 //__________________________________________________________________________________________________
129 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
lru_cache(::std::size_t size)130 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache(
131     ::std::size_t size ) SAL_THROW( () )
132     : m_size( 0 )
133     , m_block( 0 )
134 {
135     setSize( size );
136 }
137 //__________________________________________________________________________________________________
138 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
lru_cache()139 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache() SAL_THROW( () )
140     : m_size( 0 )
141     , m_block( 0 )
142 {
143 }
144 //__________________________________________________________________________________________________
145 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
~lru_cache()146 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::~lru_cache()
147     SAL_THROW( () )
148 {
149     delete [] m_block;
150 }
151 //__________________________________________________________________________________________________
152 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
toFront(Entry * entry) const153 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::toFront(
154     Entry * entry ) const SAL_THROW( () )
155 {
156     if (entry != m_head)
157     {
158         // cut out element
159         if (entry == m_tail)
160         {
161             m_tail = entry->m_pred;
162         }
163         else
164         {
165             entry->m_succ->m_pred = entry->m_pred;
166             entry->m_pred->m_succ = entry->m_succ;
167         }
168         // push to front
169         m_head->m_pred = entry;
170         entry->m_succ = m_head;
171         m_head = entry;
172     }
173 }
174 //__________________________________________________________________________________________________
175 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
has(t_key const & key) const176 inline bool lru_cache< t_key, t_val, t_hashKey, t_equalKey >::has(
177     t_key const & key ) const SAL_THROW( () )
178 {
179     typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
180     return (iFind != m_key2element.end());
181 }
182 //__________________________________________________________________________________________________
183 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
lookup(t_key const & key) const184 inline t_val const * lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lookup(
185     t_key const & key ) const SAL_THROW( () )
186 {
187     if (0 < m_size)
188     {
189         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
190         if (iFind != m_key2element.end())
191         {
192             Entry * entry = iFind->second;
193             toFront( entry );
194 #ifdef __CACHE_DIAGNOSE
195             ::rtl::OUStringBuffer buf( 48 );
196             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> retrieved element \"") );
197             buf.append( entry->m_key );
198             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
199             ::rtl::OString str( ::rtl::OUStringToOString(
200                 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
201             OSL_TRACE( str.getStr() );
202 #endif
203             return &entry->m_val;
204         }
205     }
206     return 0;
207 }
208 //__________________________________________________________________________________________________
209 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
set(t_key const & key,t_val const & val)210 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::set(
211     t_key const & key, t_val const & val ) SAL_THROW( () )
212 {
213     if (0 < m_size)
214     {
215         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
216 
217         Entry * entry;
218         if (iFind == m_key2element.end())
219         {
220             entry = m_tail; // erase last element
221 #ifdef __CACHE_DIAGNOSE
222             if (entry->m_key.getLength())
223             {
224                 ::rtl::OUStringBuffer buf( 48 );
225                 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> kicking element \"") );
226                 buf.append( entry->m_key );
227                 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
228                 ::rtl::OString str( ::rtl::OUStringToOString(
229                     buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
230                 OSL_TRACE( str.getStr() );
231             }
232 #endif
233             m_key2element.erase( entry->m_key );
234             entry->m_key = key;
235             ::std::pair< typename t_key2element::iterator, bool > insertion(
236                 m_key2element.insert( typename t_key2element::value_type( key, entry ) ) );
237 #ifdef __CACHE_DIAGNOSE
238             OSL_ENSURE( insertion.second, "### inserting new cache entry failed?!" );
239 #endif
240         }
241         else
242         {
243             entry = iFind->second;
244 #ifdef __CACHE_DIAGNOSE
245             ::rtl::OUStringBuffer buf( 48 );
246             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> replacing element \"") );
247             buf.append( entry->m_key );
248             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" in cache") );
249             ::rtl::OString str( ::rtl::OUStringToOString(
250                 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
251             OSL_TRACE( str.getStr() );
252 #endif
253         }
254         entry->m_val = val;
255         toFront( entry );
256     }
257 }
258 //__________________________________________________________________________________________________
259 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
clear()260 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::clear() SAL_THROW( () )
261 {
262     m_key2element.clear();
263     for ( ::std::size_t nPos = m_size; nPos--; )
264     {
265         m_block[ nPos ].m_key = t_key();
266         m_block[ nPos ].m_val = t_val();
267     }
268 #ifdef __CACHE_DIAGNOSE
269     OSL_TRACE( "> cleared cache\n" );
270 #endif
271 }
272 
273 }
274 
275 #endif
276