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
  20 #pragma once
  21
  22 // __CACHE_DIAGNOSE forces cache size to 4 and works only for OUString keys
  23 //  #define __CACHE_DIAGNOSE 1
  24
  25 #include <rtl/ustring.hxx>
  26
  27 #include <memory>
  28 #include <mutex>
  29 #include <unordered_map>
  30
  31 namespace com::sun::star::uno { class Any; }
  32
  33 /** Implementation of a least recently used (lru) cache.
  34     <br>
  35 */
  36 template< class t_Key, class t_Val, class t_KeyHash >
  37 class LRU_Cache
  38 {
  39     struct CacheEntry
  40     {
  41         t_Key               aKey;
  42         t_Val               aVal;
  43         CacheEntry *        pPred;
  44         CacheEntry *        pSucc;
  45     };
  46     typedef std::unordered_map< t_Key, CacheEntry *, t_KeyHash > t_Key2Element;
  47
  48     mutable std::mutex        _aCacheMutex;
  49     sal_Int32                   _nCachedElements;
  50     t_Key2Element               _aKey2Element;
  51
  52     std::unique_ptr<CacheEntry[]> _pBlock;
  53     mutable CacheEntry *        _pHead;
  54     mutable CacheEntry *        _pTail;
  55     inline void toFront( CacheEntry * pEntry ) const;
  56
  57 public:
  58     /** Constructor:
  59         <br>
  60         @param nCachedElements number of elements to be cached; default param set to 128
  61     */
  62     explicit inline LRU_Cache();
  63
  64     /** Retrieves a value from the cache. Returns default constructed value,
  65         if none was found.
  66         <br>
  67         @param rKey a key
  68         @return value
  69     */
  70     inline t_Val getValue( const t_Key & rKey ) const;
  71     /** Sets a value to be cached for given key.
  72         <br>
  73         @param rKey a key
  74         @param rValue a value
  75     */
  76     inline void setValue( const t_Key & rKey, const t_Val & rValue );
  77     /** Clears the cache, thus releasing all cached elements and keys.
  78         <br>
  79     */
  80     inline void clear();
  81 };
  82
  83 template< class t_Key, class t_Val, class t_KeyHash >
  84 inline LRU_Cache< t_Key, t_Val, t_KeyHash >::LRU_Cache()
  85 #ifdef __CACHE_DIAGNOSE
  86     : _nCachedElements( 4 )
  87 #else
  88     : _nCachedElements( 256 )
  89 #endif
  90     , _pBlock( nullptr )
  91     , _pHead( nullptr )
  92     , _pTail( nullptr )
  93 {
  94     _pBlock.reset(new CacheEntry[_nCachedElements]);
  95     _pHead = _pBlock.get();
  96     _pTail = _pBlock.get() + _nCachedElements - 1;
  97     for (sal_Int32 nPos = _nCachedElements; nPos--;)
  98     {
  99         _pBlock[nPos].pPred = _pBlock.get() + nPos - 1;
 100         _pBlock[nPos].pSucc = _pBlock.get() + nPos + 1;
 101     }
 102 }
 103
 104 template< class t_Key, class t_Val, class t_KeyHash >
 105 inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::toFront( CacheEntry * pEntry ) const
 106 {
 107     if (pEntry != _pHead)
 108     {
 109         // cut out element
 110         if (pEntry == _pTail)
 111         {
 112             _pTail = pEntry->pPred;
 113         }
 114         else
 115         {
 116             pEntry->pSucc->pPred = pEntry->pPred;
 117             pEntry->pPred->pSucc = pEntry->pSucc;
 118         }
 119         // push to front
 120         _pHead->pPred = pEntry;
 121         pEntry->pSucc = _pHead;
 122         _pHead        = pEntry;
 123     }
 124 }
 125
 126 template< class t_Key, class t_Val, class t_KeyHash >
 127 inline t_Val LRU_Cache< t_Key, t_Val, t_KeyHash >::getValue( const t_Key & rKey ) const
 128 {
 129     std::scoped_lock aGuard( _aCacheMutex );
 130     const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
 131     if (iFind != _aKey2Element.end())
 132     {
 133         CacheEntry * pEntry = (*iFind).second;
 134         toFront( pEntry );
 135 #ifdef __CACHE_DIAGNOSE
 136         SAL_INFO("stoc.corerefl", "> retrieved element \"" );
 137         SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
 138         SAL_INFO("stoc.corerefl", "\" from cache <" );
 139 #endif
 140         return pEntry->aVal;
 141     }
 142     return t_Val();
 143 }
 144
 145 template< class t_Key, class t_Val, class t_KeyHash >
 146 inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::setValue(
 147     const t_Key & rKey, const t_Val & rValue )
 148 {
 149     std::scoped_lock aGuard( _aCacheMutex );
 150     if (_nCachedElements > 0)
 151     {
 152         const typename t_Key2Element::const_iterator iFind( _aKey2Element.find( rKey ) );
 153
 154         CacheEntry * pEntry;
 155         if (iFind == _aKey2Element.end())
 156         {
 157             pEntry = _pTail; // erase last element
 158 #ifdef __CACHE_DIAGNOSE
 159             if (pEntry->aKey.getLength())
 160             {
 161                 SAL_INFO("stoc.corerefl", "> kicking element \"" );
 162                 SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
 163                 SAL_INFO("stoc.corerefl", "\" from cache <" );
 164             }
 165 #endif
 166             _aKey2Element.erase( pEntry->aKey );
 167             pEntry->aKey = rKey;
 168             _aKey2Element[ rKey ] = pEntry;
 169         }
 170         else
 171         {
 172             pEntry = (*iFind).second;
 173 #ifdef __CACHE_DIAGNOSE
 174             SAL_INFO("stoc.corerefl", "> replacing element \"" );
 175             SAL_INFO("stoc.corerefl", "" << pEntry->aKey);
 176             SAL_INFO("stoc.corerefl", "\" in cache <" );
 177 #endif
 178         }
 179         pEntry->aVal = rValue;
 180         toFront( pEntry );
 181     }
 182 }
 183
 184 template< class t_Key, class t_Val, class t_KeyHash >
 185 inline void LRU_Cache< t_Key, t_Val, t_KeyHash >::clear()
 186 {
 187     std::scoped_lock aGuard( _aCacheMutex );
 188     _aKey2Element.clear();
 189     for ( sal_Int32 nPos = _nCachedElements; nPos--; )
 190     {
 191         _pBlock[nPos].aKey = t_Key();
 192         _pBlock[nPos].aVal = t_Val();
 193     }
 194     _nCachedElements = 0;
 195 #ifdef __CACHE_DIAGNOSE
 196     SAL_INFO("stoc.corerefl", "> cleared cache <" );
 197 #endif
 198 }
 199
 200
 201 /** Template instance for OUString keys, Any values.<br>
 202 */
 203 typedef LRU_Cache< OUString, css::uno::Any, OUStringHash >
 204     LRU_CacheAnyByOUString;
 205
 206 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */