LCOV - code coverage report
Current view: top level - libreoffice/stoc/source/corereflection - lrucache.hxx (source / functions) Hit Total Coverage
Test: libreoffice_filtered.info Lines: 53 54 98.1 %
Date: 2012-12-27 Functions: 9 9 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : #ifndef _LRU_CACHE_HXX_
      20             : #define _LRU_CACHE_HXX_
      21             : 
      22             : // __CACHE_DIAGNOSE forces cache size to 4 and works only for OUString keys
      23             : //  #define __CACHE_DIAGNOSE 1
      24             : 
      25             : #include <osl/mutex.hxx>
      26             : #include "rtl/ustring.hxx"
      27             : 
      28             : #include <boost/unordered_map.hpp>
      29             : 
      30             : /** Implementation of a least recently used (lru) cache.
      31             :     <br>
      32             :     @author Daniel Boelzle
      33             : */
      34             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
      35             : class LRU_Cache
      36             : {
      37      449280 :     struct CacheEntry
      38             :     {
      39             :         t_Key               aKey;
      40             :         t_Val               aVal;
      41             :         CacheEntry *        pPred;
      42             :         CacheEntry *        pSucc;
      43             :     };
      44             :     typedef ::boost::unordered_map< t_Key, CacheEntry *, t_KeyHash, t_KeyEqual > t_Key2Element;
      45             : 
      46             :     mutable ::osl::Mutex        _aCacheMutex;
      47             :     sal_Int32                   _nCachedElements;
      48             :     t_Key2Element               _aKey2Element;
      49             : 
      50             :     CacheEntry *                _pBlock;
      51             :     mutable CacheEntry *        _pHead;
      52             :     mutable CacheEntry *        _pTail;
      53             :     inline void toFront( CacheEntry * pEntry ) const;
      54             : 
      55             : public:
      56             :     /** Constructor:
      57             :         <br>
      58             :         @param nCachedElements number of elements to be cached; default param set to 128
      59             :     */
      60             :     inline LRU_Cache( sal_Int32 nCachedElements = 128 );
      61             :     /** Destructor: releases all cached elements and keys.
      62             :         <br>
      63             :     */
      64             :     inline ~LRU_Cache();
      65             : 
      66             :     /** Retrieves a value from the cache. Returns default constructed value,
      67             :         if none was found.
      68             :         <br>
      69             :         @param rKey a key
      70             :         @return value
      71             :     */
      72             :     inline t_Val getValue( const t_Key & rKey ) const;
      73             :     /** Sets a value to be cached for given key.
      74             :         <br>
      75             :         @param rKey a key
      76             :         @param rValue a value
      77             :     */
      78             :     inline void setValue( const t_Key & rKey, const t_Val & rValue );
      79             :     /** Tests whether a value is cached for given key.
      80             :         <br>
      81             :         @param rKey a key
      82             :         @return true, if value is cached
      83             :     */
      84             :     inline sal_Bool hasValue( const t_Key & rKey ) const;
      85             :     /** Clears the cache, thus releasing all cached elements and keys.
      86             :         <br>
      87             :     */
      88             :     inline void clear();
      89             : };
      90             : //__________________________________________________________________________________________________
      91             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
      92         978 : inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::LRU_Cache( sal_Int32 nCachedElements )
      93             : #ifdef __CACHE_DIAGNOSE
      94             :     : _nCachedElements( 4 )
      95             : #else
      96             :     : _nCachedElements( nCachedElements )
      97             : #endif
      98         978 :     , _pBlock( 0 )
      99             : {
     100         978 :     if (_nCachedElements > 0)
     101             :     {
     102         978 :         _pBlock = new CacheEntry[_nCachedElements];
     103         978 :         _pHead  = _pBlock;
     104         978 :         _pTail  = _pBlock + _nCachedElements -1;
     105      252324 :         for ( sal_Int32 nPos = _nCachedElements; nPos--; )
     106             :         {
     107      250368 :             _pBlock[nPos].pPred = _pBlock + nPos -1;
     108      250368 :             _pBlock[nPos].pSucc = _pBlock + nPos +1;
     109             :         }
     110             :     }
     111         978 : }
     112             : //__________________________________________________________________________________________________
     113             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
     114         777 : inline LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::~LRU_Cache()
     115             : {
     116         777 :     delete [] _pBlock;
     117         777 : }
     118             : //__________________________________________________________________________________________________
     119             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
     120       67127 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::toFront( CacheEntry * pEntry ) const
     121             : {
     122       67127 :     if (pEntry != _pHead)
     123             :     {
     124             :         // cut out element
     125       47754 :         if (pEntry == _pTail)
     126             :         {
     127        2512 :             _pTail = pEntry->pPred;
     128             :         }
     129             :         else
     130             :         {
     131       45242 :             pEntry->pSucc->pPred = pEntry->pPred;
     132       45242 :             pEntry->pPred->pSucc = pEntry->pSucc;
     133             :         }
     134             :         // push to front
     135       47754 :         _pHead->pPred = pEntry;
     136       47754 :         pEntry->pSucc = _pHead;
     137       47754 :         _pHead        = pEntry;
     138             :     }
     139       67127 : }
     140             : //__________________________________________________________________________________________________
     141             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
     142             : inline sal_Bool LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::hasValue( const t_Key & rKey ) const
     143             : {
     144             :     ::osl::MutexGuard aGuard( _aCacheMutex );
     145             :     const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
     146             :     return (iFind != _aKey2Element.end());
     147             : }
     148             : //__________________________________________________________________________________________________
     149             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
     150       67133 : inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::getValue( const t_Key & rKey ) const
     151             : {
     152       67133 :     ::osl::MutexGuard aGuard( _aCacheMutex );
     153       67133 :     const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
     154       67133 :     if (iFind != _aKey2Element.end())
     155             :     {
     156       64615 :         CacheEntry * pEntry = (*iFind).second;
     157       64615 :         toFront( pEntry );
     158             : #ifdef __CACHE_DIAGNOSE
     159             :         OSL_TRACE( "> retrieved element \"" );
     160             :         OSL_TRACE( "%s", ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
     161             :         OSL_TRACE( "\" from cache <" );
     162             : #endif
     163       64615 :         return pEntry->aVal;
     164             :     }
     165        2518 :     return t_Val();
     166             : }
     167             : //__________________________________________________________________________________________________
     168             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
     169        2518 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::setValue(
     170             :     const t_Key & rKey, const t_Val & rValue )
     171             : {
     172        2518 :     ::osl::MutexGuard aGuard( _aCacheMutex );
     173        2518 :     if (_nCachedElements > 0)
     174             :     {
     175        2512 :         const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
     176             : 
     177             :         CacheEntry * pEntry;
     178        2512 :         if (iFind == _aKey2Element.end())
     179             :         {
     180        2512 :             pEntry = _pTail; // erase last element
     181             : #ifdef __CACHE_DIAGNOSE
     182             :             if (pEntry->aKey.getLength())
     183             :             {
     184             :                 OSL_TRACE( "> kicking element \"" );
     185             :                 OSL_TRACE( "%s", ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
     186             :                 OSL_TRACE( "\" from cache <" );
     187             :             }
     188             : #endif
     189        2512 :             _aKey2Element.erase( pEntry->aKey );
     190        2512 :             _aKey2Element[ pEntry->aKey = rKey ] = pEntry;
     191             :         }
     192             :         else
     193             :         {
     194           0 :             pEntry = (*iFind).second;
     195             : #ifdef __CACHE_DIAGNOSE
     196             :             OSL_TRACE( "> replacing element \"" );
     197             :             OSL_TRACE( "%s", ::rtl::OUStringToOString( pEntry->aKey, RTL_TEXTENCODING_ASCII_US ).getStr() );
     198             :             OSL_TRACE( "\" in cache <" );
     199             : #endif
     200             :         }
     201        2512 :         pEntry->aVal = rValue;
     202        2512 :         toFront( pEntry );
     203             :     }
     204        2518 : }
     205             : //__________________________________________________________________________________________________
     206             : template< class t_Key, class t_Val, class t_KeyHash, class t_KeyEqual >
     207         965 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash, t_KeyEqual >::clear()
     208             : {
     209         965 :     ::osl::MutexGuard aGuard( _aCacheMutex );
     210         965 :     _aKey2Element.clear();
     211      248970 :     for ( sal_Int32 nPos = _nCachedElements; nPos--; )
     212             :     {
     213      247040 :         _pBlock[nPos].aKey = t_Key();
     214      247040 :         _pBlock[nPos].aVal = t_Val();
     215             :     }
     216         965 :     _nCachedElements = 0;
     217             : #ifdef __CACHE_DIAGNOSE
     218             :     OSL_TRACE( "> cleared cache <" );
     219             : #endif
     220         965 : }
     221             : 
     222             : //==================================================================================================
     223             : struct FctHashOUString : public ::std::unary_function< const ::rtl::OUString &, size_t >
     224             : {
     225       71771 :     size_t operator()( const ::rtl::OUString & rKey ) const
     226       71771 :         { return rKey.hashCode(); }
     227             : };
     228             : 
     229             : /** Template instance for OUString keys, Any values.<br>
     230             : */
     231             : typedef LRU_Cache< ::rtl::OUString, ::com::sun::star::uno::Any,
     232             :                    FctHashOUString, ::std::equal_to< ::rtl::OUString > >
     233             :     LRU_CacheAnyByOUString;
     234             : 
     235             : 
     236             : #endif
     237             : 
     238             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10