LCOV - code coverage report
Current view: top level - stoc/source/corereflection - lrucache.hxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 52 53 98.1 %
Date: 2015-06-13 12:38:46 Functions: 8 8 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 INCLUDED_STOC_SOURCE_COREREFLECTION_LRUCACHE_HXX
      20             : #define INCLUDED_STOC_SOURCE_COREREFLECTION_LRUCACHE_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             : #include <sal/log.hxx>
      28             : 
      29             : #include <unordered_map>
      30             : 
      31             : /** Implementation of a least recently used (lru) cache.
      32             :     <br>
      33             :     @author Daniel Boelzle
      34             : */
      35             : template< class t_Key, class t_Val, class t_KeyHash >
      36             : class LRU_Cache
      37             : {
      38       56320 :     struct CacheEntry
      39             :     {
      40             :         t_Key               aKey;
      41             :         t_Val               aVal;
      42             :         CacheEntry *        pPred;
      43             :         CacheEntry *        pSucc;
      44             :     };
      45             :     typedef std::unordered_map< t_Key, CacheEntry *, t_KeyHash > t_Key2Element;
      46             : 
      47             :     mutable ::osl::Mutex        _aCacheMutex;
      48             :     sal_Int32                   _nCachedElements;
      49             :     t_Key2Element               _aKey2Element;
      50             : 
      51             :     CacheEntry *                _pBlock;
      52             :     mutable CacheEntry *        _pHead;
      53             :     mutable CacheEntry *        _pTail;
      54             :     inline void toFront( CacheEntry * pEntry ) const;
      55             : 
      56             : public:
      57             :     /** Constructor:
      58             :         <br>
      59             :         @param nCachedElements number of elements to be cached; default param set to 128
      60             :     */
      61             :     inline LRU_Cache( sal_Int32 nCachedElements = 128 );
      62             :     /** Destructor: releases all cached elements and keys.
      63             :         <br>
      64             :     */
      65             :     inline ~LRU_Cache();
      66             : 
      67             :     /** Retrieves a value from the cache. Returns default constructed value,
      68             :         if none was found.
      69             :         <br>
      70             :         @param rKey a key
      71             :         @return value
      72             :     */
      73             :     inline t_Val getValue( const t_Key & rKey ) const;
      74             :     /** Sets a value to be cached for given key.
      75             :         <br>
      76             :         @param rKey a key
      77             :         @param rValue a value
      78             :     */
      79             :     inline void setValue( const t_Key & rKey, const t_Val & rValue );
      80             :     /** Tests whether a value is cached for given key.
      81             :         <br>
      82             :         @param rKey a key
      83             :         @return true, if value is cached
      84             :     */
      85             :     inline bool hasValue( const t_Key & rKey ) const;
      86             :     /** Clears the cache, thus releasing all cached elements and keys.
      87             :         <br>
      88             :     */
      89             :     inline void clear();
      90             : };
      91             : 
      92             : template< class t_Key, class t_Val, class t_KeyHash >
      93         129 : inline LRU_Cache< t_Key, t_Val, t_KeyHash >::LRU_Cache( sal_Int32 nCachedElements )
      94             : #ifdef __CACHE_DIAGNOSE
      95             :     : _nCachedElements( 4 )
      96             : #else
      97             :     : _nCachedElements( nCachedElements )
      98             : #endif
      99             :     , _pBlock( 0 )
     100             :     , _pHead( 0 )
     101         129 :     , _pTail( 0 )
     102             : {
     103         129 :     if (_nCachedElements > 0)
     104             :     {
     105         129 :         _pBlock = new CacheEntry[_nCachedElements];
     106         129 :         _pHead  = _pBlock;
     107         129 :         _pTail  = _pBlock + _nCachedElements -1;
     108       33282 :         for ( sal_Int32 nPos = _nCachedElements; nPos--; )
     109             :         {
     110       33024 :             _pBlock[nPos].pPred = _pBlock + nPos -1;
     111       33024 :             _pBlock[nPos].pSucc = _pBlock + nPos +1;
     112             :         }
     113             :     }
     114         129 : }
     115             : 
     116             : template< class t_Key, class t_Val, class t_KeyHash >
     117          91 : inline LRU_Cache< t_Key, t_Val, t_KeyHash >::~LRU_Cache()
     118             : {
     119          91 :     delete [] _pBlock;
     120          91 : }
     121             : 
     122             : template< class t_Key, class t_Val, class t_KeyHash >
     123      648572 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::toFront( CacheEntry * pEntry ) const
     124             : {
     125      648572 :     if (pEntry != _pHead)
     126             :     {
     127             :         // cut out element
     128      571486 :         if (pEntry == _pTail)
     129             :         {
     130       13986 :             _pTail = pEntry->pPred;
     131             :         }
     132             :         else
     133             :         {
     134      557500 :             pEntry->pSucc->pPred = pEntry->pPred;
     135      557500 :             pEntry->pPred->pSucc = pEntry->pSucc;
     136             :         }
     137             :         // push to front
     138      571486 :         _pHead->pPred = pEntry;
     139      571486 :         pEntry->pSucc = _pHead;
     140      571486 :         _pHead        = pEntry;
     141             :     }
     142      648572 : }
     143             : 
     144             : template< class t_Key, class t_Val, class t_KeyHash >
     145             : inline bool LRU_Cache< t_Key, t_Val, t_KeyHash >::hasValue( const t_Key & rKey ) const
     146             : {
     147             :     ::osl::MutexGuard aGuard( _aCacheMutex );
     148             :     const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
     149             :     return (iFind != _aKey2Element.end());
     150             : }
     151             : 
     152             : template< class t_Key, class t_Val, class t_KeyHash >
     153      648579 : inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash >::getValue( const t_Key & rKey ) const
     154             : {
     155      648579 :     ::osl::MutexGuard aGuard( _aCacheMutex );
     156      648579 :     const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
     157      648579 :     if (iFind != _aKey2Element.end())
     158             :     {
     159      634586 :         CacheEntry * pEntry = (*iFind).second;
     160      634586 :         toFront( pEntry );
     161             : #ifdef __CACHE_DIAGNOSE
     162             :         SAL_INFO("stoc.corerefl", "> retrieved element \"" );
     163             :         SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
     164             :         SAL_INFO("stoc.corerefl", "\" from cache <" );
     165             : #endif
     166      634586 :         return pEntry->aVal;
     167             :     }
     168       13993 :     return t_Val();
     169             : }
     170             : 
     171             : template< class t_Key, class t_Val, class t_KeyHash >
     172       13986 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::setValue(
     173             :     const t_Key & rKey, const t_Val & rValue )
     174             : {
     175       13986 :     ::osl::MutexGuard aGuard( _aCacheMutex );
     176       13986 :     if (_nCachedElements > 0)
     177             :     {
     178       13986 :         const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
     179             : 
     180             :         CacheEntry * pEntry;
     181       13986 :         if (iFind == _aKey2Element.end())
     182             :         {
     183       13986 :             pEntry = _pTail; // erase last element
     184             : #ifdef __CACHE_DIAGNOSE
     185             :             if (pEntry->aKey.getLength())
     186             :             {
     187             :                 SAL_INFO("stoc.corerefl", "> kicking element \"" );
     188             :                 SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
     189             :                 SAL_INFO("stoc.corerefl", "\" from cache <" );
     190             :             }
     191             : #endif
     192       13986 :             _aKey2Element.erase( pEntry->aKey );
     193       13986 :             _aKey2Element[ pEntry->aKey = rKey ] = pEntry;
     194             :         }
     195             :         else
     196             :         {
     197           0 :             pEntry = (*iFind).second;
     198             : #ifdef __CACHE_DIAGNOSE
     199             :             SAL_INFO("stoc.corerefl", "> replacing element \"" );
     200             :             SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
     201             :             SAL_INFO("stoc.corerefl", "\" in cache <" );
     202             : #endif
     203             :         }
     204       13986 :         pEntry->aVal = rValue;
     205       13986 :         toFront( pEntry );
     206       13986 :     }
     207       13986 : }
     208             : 
     209             : template< class t_Key, class t_Val, class t_KeyHash >
     210         127 : inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::clear()
     211             : {
     212         127 :     ::osl::MutexGuard aGuard( _aCacheMutex );
     213         127 :     _aKey2Element.clear();
     214       32766 :     for ( sal_Int32 nPos = _nCachedElements; nPos--; )
     215             :     {
     216       32512 :         _pBlock[nPos].aKey = t_Key();
     217       32512 :         _pBlock[nPos].aVal = t_Val();
     218             :     }
     219         127 :     _nCachedElements = 0;
     220             : #ifdef __CACHE_DIAGNOSE
     221             :     SAL_INFO("stoc.corerefl", "> cleared cache <" );
     222             : #endif
     223         127 : }
     224             : 
     225             : 
     226             : /** Template instance for OUString keys, Any values.<br>
     227             : */
     228             : typedef LRU_Cache< OUString, css::uno::Any, OUStringHash >
     229             :     LRU_CacheAnyByOUString;
     230             : 
     231             : 
     232             : #endif
     233             : 
     234             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.11