stoc/source/corereflection/lrucache.hxx

   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     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     explicit inline LRU_Cache();
  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     /** Clears the cache, thus releasing all cached elements and keys.
  81         <br>
  82     */
  83     inline void clear();
  84 };
  85
  86 template< class t_Key, class t_Val, class t_KeyHash >
  87 inline LRU_Cache< t_Key, t_Val, t_KeyHash >::LRU_Cache()
  88 #ifdef __CACHE_DIAGNOSE
  89     : _nCachedElements( 4 )
  90 #else
  91     : _nCachedElements( 256 )
  92 #endif
  93     , _pBlock( nullptr )
  94     , _pHead( nullptr )
  95     , _pTail( nullptr )
  96 {
  97     if (_nCachedElements > 0)
  98     {
  99         _pBlock = new CacheEntry[_nCachedElements];
 100         _pHead  = _pBlock;
 101         _pTail  = _pBlock + _nCachedElements -1;
 102         for ( sal_Int32 nPos = _nCachedElements; nPos--; )
 103         {
 104             _pBlock[nPos].pPred = _pBlock + nPos -1;
 105             _pBlock[nPos].pSucc = _pBlock + nPos +1;
 106         }
 107     }
 108 }
 109
 110 template< class t_Key, class t_Val, class t_KeyHash >
 111 inline LRU_Cache< t_Key, t_Val, t_KeyHash >::~LRU_Cache()
 112 {
 113     delete [] _pBlock;
 114 }
 115
 116 template< class t_Key, class t_Val, class t_KeyHash >
 117 inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::toFront( CacheEntry * pEntry ) const
 118 {
 119     if (pEntry != _pHead)
 120     {
 121         // cut out element
 122         if (pEntry == _pTail)
 123         {
 124             _pTail = pEntry->pPred;
 125         }
 126         else
 127         {
 128             pEntry->pSucc->pPred = pEntry->pPred;
 129             pEntry->pPred->pSucc = pEntry->pSucc;
 130         }
 131         // push to front
 132         _pHead->pPred = pEntry;
 133         pEntry->pSucc = _pHead;
 134         _pHead        = pEntry;
 135     }
 136 }
 137
 138 template< class t_Key, class t_Val, class t_KeyHash >
 139 inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash >::getValue( const t_Key & rKey ) const
 140 {
 141     ::osl::MutexGuard aGuard( _aCacheMutex );
 142     const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
 143     if (iFind != _aKey2Element.end())
 144     {
 145         CacheEntry * pEntry = (*iFind).second;
 146         toFront( pEntry );
 147 #ifdef __CACHE_DIAGNOSE
 148         SAL_INFO("stoc.corerefl", "> retrieved element \"" );
 149         SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
 150         SAL_INFO("stoc.corerefl", "\" from cache <" );
 151 #endif
 152         return pEntry->aVal;
 153     }
 154     return t_Val();
 155 }
 156
 157 template< class t_Key, class t_Val, class t_KeyHash >
 158 inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::setValue(
 159     const t_Key & rKey, const t_Val & rValue )
 160 {
 161     ::osl::MutexGuard aGuard( _aCacheMutex );
 162     if (_nCachedElements > 0)
 163     {
 164         const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
 165
 166         CacheEntry * pEntry;
 167         if (iFind == _aKey2Element.end())
 168         {
 169             pEntry = _pTail; // erase last element
 170 #ifdef __CACHE_DIAGNOSE
 171             if (pEntry->aKey.getLength())
 172             {
 173                 SAL_INFO("stoc.corerefl", "> kicking element \"" );
 174                 SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
 175                 SAL_INFO("stoc.corerefl", "\" from cache <" );
 176             }
 177 #endif
 178             _aKey2Element.erase( pEntry->aKey );
 179             _aKey2Element[ pEntry->aKey = rKey ] = pEntry;
 180         }
 181         else
 182         {
 183             pEntry = (*iFind).second;
 184 #ifdef __CACHE_DIAGNOSE
 185             SAL_INFO("stoc.corerefl", "> replacing element \"" );
 186             SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
 187             SAL_INFO("stoc.corerefl", "\" in cache <" );
 188 #endif
 189         }
 190         pEntry->aVal = rValue;
 191         toFront( pEntry );
 192     }
 193 }
 194
 195 template< class t_Key, class t_Val, class t_KeyHash >
 196 inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::clear()
 197 {
 198     ::osl::MutexGuard aGuard( _aCacheMutex );
 199     _aKey2Element.clear();
 200     for ( sal_Int32 nPos = _nCachedElements; nPos--; )
 201     {
 202         _pBlock[nPos].aKey = t_Key();
 203         _pBlock[nPos].aVal = t_Val();
 204     }
 205     _nCachedElements = 0;
 206 #ifdef __CACHE_DIAGNOSE
 207     SAL_INFO("stoc.corerefl", "> cleared cache <" );
 208 #endif
 209 }
 210
 211
 212 /** Template instance for OUString keys, Any values.<br>
 213 */
 214 typedef LRU_Cache< OUString, css::uno::Any, OUStringHash >
 215     LRU_CacheAnyByOUString;
 216
 217
 218 #endif
 219
 220 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */