stoc/source/tdmanager/lrucache.hxx

   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: lrucache.hxx,v $
  10  * $Revision: 1.7 $
  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 _LRU_CACHE_HXX_
  31 #define _LRU_CACHE_HXX_
  32
  33 // __CACHE_DIAGNOSE forces cache size to 4 and works only for OUString keys
  34 //  #define __CACHE_DIAGNOSE 1
  35
  36 #include <osl/mutex.hxx>
  37 #include "rtl/ustring.hxx"
  38
  39 #include <hash_map>
  40
  41
  42 /** Implementation of a least recently used (lru) cache.
  43         <br>
  44         @author Daniel Boelzle
  45 */
  46 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
  47 class LRU_Cache
  48 {
  49         struct CacheEntry
  50         {
  51                 t_Key                           aKey;
  52                 t_Val                           aVal;
  53                 CacheEntry *            pPred;
  54                 CacheEntry *            pSucc;
  55         };
  56         typedef ::std::hash_map< t_Key, CacheEntry *, t_KeyHash, t_KeyEqual > t_Key2Element;
  57
  58         mutable ::osl::Mutex            _aCacheMutex;
  59         sal_Int32                                       _nCachedElements;
  60         t_Key2Element                           _aKey2Element;
  61
  62         CacheEntry *                            _pBlock;
  63         mutable CacheEntry *            _pHead;
  64         mutable CacheEntry *            _pTail;
  65         inline void toFront( CacheEntry * pEntry ) const;
  66
  67 public:
  68         /** Constructor:
  69                 <br>
  70                 @param nCachedElements number of elements to be cached; default param set to 128
  71         */
  72         inline LRU_Cache( sal_Int32 nCachedElements = 128 );
  73         /** Destructor: releases all cached elements and keys.
  74                 <br>
  75         */
  76         inline ~LRU_Cache();
  77
  78         /** Retrieves a value from the cache. Returns default constructed value,
  79                 if none was found.
  80                 <br>
  81                 @param rKey a key
  82                 @return value
  83         */
  84         inline t_Val getValue( t_Key const & rKey ) const;
  85         /** Sets a value to be cached for given key.
  86                 <br>
  87                 @param rKey a key
  88                 @param rValue a value
  89         */
  90         inline void setValue( t_Key const & rKey, t_Val const & rValue );
  91         /** Tests whether a value is cached for given key.
  92                 <br>
  93                 @param rKey a key
  94                 @return true, if value is cached
  95         */
  96         inline sal_Bool hasValue( t_Key const & rKey ) const;
  97         /** Clears the cache, thus releasing all cached elements and keys.
  98                 <br>
  99         */
 100         inline void clear();
 101 };
 102 //__________________________________________________________________________________________________
 103 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 104 inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::LRU_Cache( sal_Int32 nCachedElements )
 105 #ifdef __CACHE_DIAGNOSE
 106         : _nCachedElements( 4 )
 107 #else
 108         : _nCachedElements( nCachedElements )
 109 #endif
 110         , _pBlock( 0 )
 111 {
 112         if (_nCachedElements > 0)
 113         {
 114                 _pBlock = new CacheEntry[_nCachedElements];
 115                 _pHead  = _pBlock;
 116                 _pTail  = _pBlock + _nCachedElements -1;
 117                 for ( sal_Int32 nPos = _nCachedElements; nPos--; )
 118                 {
 119                         _pBlock[nPos].pPred = _pBlock + nPos -1;
 120                         _pBlock[nPos].pSucc = _pBlock + nPos +1;
 121                 }
 122         }
 123 }
 124 //__________________________________________________________________________________________________
 125 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 126 inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache()
 127 {
 128         delete [] _pBlock;
 129 }
 130 //__________________________________________________________________________________________________
 131 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 132 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront(
 133     CacheEntry * pEntry ) const
 134 {
 135         if (pEntry != _pHead)
 136         {
 137                 // cut out element
 138                 if (pEntry == _pTail)
 139                 {
 140                         _pTail = pEntry->pPred;
 141                 }
 142                 else
 143                 {
 144                         pEntry->pSucc->pPred = pEntry->pPred;
 145                         pEntry->pPred->pSucc = pEntry->pSucc;
 146                 }
 147                 // push to front
 148                 _pHead->pPred = pEntry;
 149                 pEntry->pSucc = _pHead;
 150                 _pHead            = pEntry;
 151         }
 152 }
 153 //__________________________________________________________________________________________________
 154 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 155 inline sal_Bool LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::hasValue(
 156     t_Key const & rKey ) const
 157 {
 158         ::osl::MutexGuard aGuard( _aCacheMutex );
 159         typename t_Key2Element::const_iterator const iFind( _aKey2Element.find( rKey ) );
 160         return (iFind != _aKey2Element.end());
 161 }
 162 //__________________________________________________________________________________________________
 163 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 164 inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue(
 165     t_Key const & rKey ) const
 166 {
 167         ::osl::MutexGuard aGuard( _aCacheMutex );
 168         const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
 169         if (iFind != _aKey2Element.end())
 170         {
 171                 CacheEntry * pEntry = (*iFind).second;
 172                 toFront( pEntry );
 173 #ifdef __CACHE_DIAGNOSE
 174                 OSL_TRACE( "> retrieved element \"" );
 175                 OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
 176                 OSL_TRACE( "\" from cache <\n" );
 177 #endif
 178                 return pEntry->aVal;
 179         }
 180         return t_Val();
 181 }
 182 //__________________________________________________________________________________________________
 183 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 184 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::setValue(
 185         t_Key const & rKey, t_Val const & rValue )
 186 {
 187         if (_nCachedElements > 0)
 188         {
 189                 ::osl::MutexGuard aGuard( _aCacheMutex );
 190                 typename t_Key2Element::const_iterator const iFind( _aKey2Element.find( rKey ) );
 191
 192                 CacheEntry * pEntry;
 193                 if (iFind == _aKey2Element.end())
 194                 {
 195                         pEntry = _pTail; // erase last element
 196 #ifdef __CACHE_DIAGNOSE
 197                         if (pEntry->aKey.getLength())
 198                         {
 199                                 OSL_TRACE( "> kicking element \"" );
 200                                 OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
 201                                 OSL_TRACE( "\" from cache <\n" );
 202                         }
 203 #endif
 204                         _aKey2Element.erase( pEntry->aKey );
 205                         _aKey2Element[ pEntry->aKey = rKey ] = pEntry;
 206                 }
 207                 else
 208                 {
 209                         pEntry = (*iFind).second;
 210 #ifdef __CACHE_DIAGNOSE
 211                         OSL_TRACE( "> replacing element \"" );
 212                         OSL_TRACE( ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
 213                         OSL_TRACE( "\" in cache <\n" );
 214 #endif
 215                 }
 216                 pEntry->aVal = rValue;
 217                 toFront( pEntry );
 218         }
 219 }
 220 //__________________________________________________________________________________________________
 221 template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
 222 inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::clear()
 223 {
 224         ::osl::MutexGuard aGuard( _aCacheMutex );
 225         _aKey2Element.clear();
 226         for ( sal_Int32 nPos = _nCachedElements; nPos--; )
 227         {
 228                 _pBlock[nPos].aKey = t_Key();
 229                 _pBlock[nPos].aVal = t_Val();
 230         }
 231 #ifdef __CACHE_DIAGNOSE
 232         OSL_TRACE( "> cleared cache <\n" );
 233 #endif
 234 }
 235
 236 //==================================================================================================
 237 struct FctHashOUString : public ::std::unary_function< ::rtl::OUString const &, size_t >
 238 {
 239         size_t operator()( ::rtl::OUString const & rKey ) const
 240                 { return (size_t)rKey.hashCode(); }
 241 };
 242
 243 /** Template instance for OUString keys, Any values.<br>
 244 */
 245 typedef LRU_Cache< ::rtl::OUString, ::com::sun::star::uno::Any,
 246                                    FctHashOUString, ::std::equal_to< ::rtl::OUString > >
 247         LRU_CacheAnyByOUString;
 248
 249
 250 #endif