stoc/source/security/lru_cache.h

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