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 > 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 > 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 > 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 > 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 > 153 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 > 176 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 > 184 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 > 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 > 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