1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 #ifndef _STOC_SEC_LRU_CACHE_H_ 28 #define _STOC_SEC_LRU_CACHE_H_ 29 30 #include <hash_map> 31 32 // __CACHE_DIAGNOSE works only for OUString keys 33 #ifdef __CACHE_DIAGNOSE 34 #include <osl/diagnose.h> 35 #include <rtl/ustrbuf.hxx> 36 #include <rtl/ustring.hxx> 37 #include <rtl/string.hxx> 38 #endif 39 40 41 namespace stoc_sec 42 { 43 44 /** Implementation of a least recently used (lru) cache. 45 */ 46 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 47 class lru_cache 48 { 49 struct Entry 50 { 51 t_key m_key; 52 t_val m_val; 53 Entry * m_pred; 54 Entry * m_succ; 55 }; 56 typedef ::std::hash_map< t_key, Entry *, t_hashKey, t_equalKey > t_key2element; 57 t_key2element m_key2element; 58 ::std::size_t m_size; 59 60 Entry * m_block; 61 mutable Entry * m_head; 62 mutable Entry * m_tail; 63 inline void toFront( Entry * entry ) const SAL_THROW( () ); 64 65 public: 66 /** Default Ctor. Does not cache. 67 */ 68 inline lru_cache() SAL_THROW( () ); 69 /** Ctor. 70 71 @param size number of elements to be cached; default param set to 128 72 */ 73 inline lru_cache( ::std::size_t size ) SAL_THROW( () ); 74 75 /** Destructor: releases all cached elements and keys. 76 */ 77 inline ~lru_cache() SAL_THROW( () ); 78 79 /** Retrieves a pointer to value in cache. Returns 0, if none was found. 80 81 @param key a key 82 @return pointer to value or 0 83 */ 84 inline t_val const * lookup( t_key const & key ) const SAL_THROW( () ); 85 86 /** Sets a value to be cached for given key. 87 88 @param key a key 89 @param val a value 90 */ 91 inline void set( t_key const & key, t_val const & val ) SAL_THROW( () ); 92 93 /** Tests whether a value is cached for given key. 94 95 @param key a key 96 @return true, if value is cached 97 */ 98 inline bool has( t_key const & key ) const SAL_THROW( () ); 99 100 /** Clears the cache, releasing all cached elements and keys. 101 */ 102 inline void clear() SAL_THROW( () ); 103 104 /** Sets the number of elements to be cached. This will clear previous entries. 105 106 @param cacheSize number of elements to be cached 107 */ 108 inline void setSize( ::std::size_t size ) SAL_THROW( () ); 109 }; 110 //__________________________________________________________________________________________________ 111 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 112 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::setSize( 113 ::std::size_t size ) SAL_THROW( () ) 114 { 115 m_key2element.clear(); 116 delete [] m_block; 117 m_block = 0; 118 m_size = size; 119 120 if (0 < m_size) 121 { 122 m_block = new Entry[ m_size ]; 123 m_head = m_block; 124 m_tail = m_block + m_size -1; 125 for ( ::std::size_t nPos = m_size; nPos--; ) 126 { 127 m_block[ nPos ].m_pred = m_block + nPos -1; 128 m_block[ nPos ].m_succ = m_block + nPos +1; 129 } 130 } 131 } 132 //__________________________________________________________________________________________________ 133 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 134 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache( 135 ::std::size_t size ) SAL_THROW( () ) 136 : m_size( 0 ) 137 , m_block( 0 ) 138 { 139 setSize( size ); 140 } 141 //__________________________________________________________________________________________________ 142 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 143 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache() SAL_THROW( () ) 144 : m_size( 0 ) 145 , m_block( 0 ) 146 { 147 } 148 //__________________________________________________________________________________________________ 149 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 150 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::~lru_cache() 151 SAL_THROW( () ) 152 { 153 delete [] m_block; 154 } 155 //__________________________________________________________________________________________________ 156 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 157 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::toFront( 158 Entry * entry ) const SAL_THROW( () ) 159 { 160 if (entry != m_head) 161 { 162 // cut out element 163 if (entry == m_tail) 164 { 165 m_tail = entry->m_pred; 166 } 167 else 168 { 169 entry->m_succ->m_pred = entry->m_pred; 170 entry->m_pred->m_succ = entry->m_succ; 171 } 172 // push to front 173 m_head->m_pred = entry; 174 entry->m_succ = m_head; 175 m_head = entry; 176 } 177 } 178 //__________________________________________________________________________________________________ 179 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 180 inline bool lru_cache< t_key, t_val, t_hashKey, t_equalKey >::has( 181 t_key const & key ) const SAL_THROW( () ) 182 { 183 typename t_key2element::const_iterator const iFind( m_key2element.find( key ) ); 184 return (iFind != m_key2element.end()); 185 } 186 //__________________________________________________________________________________________________ 187 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 188 inline t_val const * lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lookup( 189 t_key const & key ) const SAL_THROW( () ) 190 { 191 if (0 < m_size) 192 { 193 typename t_key2element::const_iterator const iFind( m_key2element.find( key ) ); 194 if (iFind != m_key2element.end()) 195 { 196 Entry * entry = iFind->second; 197 toFront( entry ); 198 #ifdef __CACHE_DIAGNOSE 199 ::rtl::OUStringBuffer buf( 48 ); 200 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> retrieved element \"") ); 201 buf.append( entry->m_key ); 202 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") ); 203 ::rtl::OString str( ::rtl::OUStringToOString( 204 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) ); 205 OSL_TRACE( str.getStr() ); 206 #endif 207 return &entry->m_val; 208 } 209 } 210 return 0; 211 } 212 //__________________________________________________________________________________________________ 213 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 214 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::set( 215 t_key const & key, t_val const & val ) SAL_THROW( () ) 216 { 217 if (0 < m_size) 218 { 219 typename t_key2element::const_iterator const iFind( m_key2element.find( key ) ); 220 221 Entry * entry; 222 if (iFind == m_key2element.end()) 223 { 224 entry = m_tail; // erase last element 225 #ifdef __CACHE_DIAGNOSE 226 if (entry->m_key.getLength()) 227 { 228 ::rtl::OUStringBuffer buf( 48 ); 229 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> kicking element \"") ); 230 buf.append( entry->m_key ); 231 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") ); 232 ::rtl::OString str( ::rtl::OUStringToOString( 233 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) ); 234 OSL_TRACE( str.getStr() ); 235 } 236 #endif 237 m_key2element.erase( entry->m_key ); 238 entry->m_key = key; 239 ::std::pair< typename t_key2element::iterator, bool > insertion( 240 m_key2element.insert( typename t_key2element::value_type( key, entry ) ) ); 241 #ifdef __CACHE_DIAGNOSE 242 OSL_ENSURE( insertion.second, "### inserting new cache entry failed?!" ); 243 #endif 244 } 245 else 246 { 247 entry = iFind->second; 248 #ifdef __CACHE_DIAGNOSE 249 ::rtl::OUStringBuffer buf( 48 ); 250 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> replacing element \"") ); 251 buf.append( entry->m_key ); 252 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" in cache") ); 253 ::rtl::OString str( ::rtl::OUStringToOString( 254 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) ); 255 OSL_TRACE( str.getStr() ); 256 #endif 257 } 258 entry->m_val = val; 259 toFront( entry ); 260 } 261 } 262 //__________________________________________________________________________________________________ 263 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey > 264 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::clear() SAL_THROW( () ) 265 { 266 m_key2element.clear(); 267 for ( ::std::size_t nPos = m_size; nPos--; ) 268 { 269 m_block[ nPos ].m_key = t_key(); 270 m_block[ nPos ].m_val = t_val(); 271 } 272 #ifdef __CACHE_DIAGNOSE 273 OSL_TRACE( "> cleared cache\n" ); 274 #endif 275 } 276 277 } 278 279 #endif 280