stoc/source/security/lru_cache.h

   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_SECURITY_LRU_CACHE_H
  20 #define INCLUDED_STOC_SOURCE_SECURITY_LRU_CACHE_H
  21
  22 #include <memory>
  23 #include <unordered_map>
  24
  25 // __CACHE_DIAGNOSE works only for OUString keys
  26 #ifdef __CACHE_DIAGNOSE
  27 #include <osl/diagnose.h>
  28 #include <rtl/ustrbuf.hxx>
  29 #include <rtl/ustring.hxx>
  30 #include <rtl/string.hxx>
  31 #include <sal/log.hxx>
  32 #endif
  33
  34
  35 namespace stoc_sec
  36 {
  37
  38 /** Implementation of a least recently used (lru) cache.
  39 */
  40 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
  41 class lru_cache
  42 {
  43     struct Entry
  44     {
  45         t_key m_key;
  46         t_val m_val;
  47         Entry * m_pred;
  48         Entry * m_succ;
  49     };
  50     typedef std::unordered_map< t_key, Entry *, t_hashKey, t_equalKey > t_key2element;
  51     t_key2element m_key2element;
  52     ::std::size_t m_size;
  53
  54     std::unique_ptr<Entry[]> m_block;
  55     mutable Entry * m_head;
  56     mutable Entry * m_tail;
  57     inline void toFront( Entry * entry ) const;
  58
  59 public:
  60     /** Default Ctor.  Does not cache.
  61     */
  62     inline lru_cache();
  63
  64     /** Retrieves a pointer to value in cache.  Returns 0, if none was found.
  65
  66         @param key a key
  67         @return pointer to value or 0
  68     */
  69     inline t_val const * lookup( t_key const & key ) const;
  70
  71     /** Sets a value to be cached for given key.
  72
  73         @param key a key
  74         @param val a value
  75     */
  76     inline void set( t_key const & key, t_val const & val );
  77
  78     /** Sets the number of elements to be cached.  This will clear previous entries.
  79
  80         @param cacheSize number of elements to be cached
  81     */
  82     inline void setSize( ::std::size_t size );
  83 };
  84
  85 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
  86 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::setSize(
  87     ::std::size_t size )
  88 {
  89     m_key2element.clear();
  90     m_block.reset();
  91     m_size = size;
  92
  93     if (0 < m_size)
  94     {
  95         m_block.reset( new Entry[ m_size ] );
  96         m_head = m_block.get();
  97         m_tail = m_block.get() + m_size -1;
  98         for ( ::std::size_t nPos = m_size; nPos--; )
  99         {
 100             m_block[ nPos ].m_pred = m_block.get() + nPos -1;
 101             m_block[ nPos ].m_succ = m_block.get() + nPos +1;
 102         }
 103     }
 104 }
 105
 106 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
 107 inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache()
 108     : m_size( 0 )
 109     , m_block( nullptr )
 110     , m_head( nullptr )
 111     , m_tail( nullptr )
 112 {
 113 }
 114
 115 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
 116 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::toFront(
 117     Entry * entry ) const
 118 {
 119     if (entry != m_head)
 120     {
 121         // cut out element
 122         if (entry == m_tail)
 123         {
 124             m_tail = entry->m_pred;
 125         }
 126         else
 127         {
 128             entry->m_succ->m_pred = entry->m_pred;
 129             entry->m_pred->m_succ = entry->m_succ;
 130         }
 131         // push to front
 132         m_head->m_pred = entry;
 133         entry->m_succ = m_head;
 134         m_head = entry;
 135     }
 136 }
 137
 138 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
 139 inline t_val const * lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lookup(
 140     t_key const & key ) const
 141 {
 142     if (0 < m_size)
 143     {
 144         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
 145         if (iFind != m_key2element.end())
 146         {
 147             Entry * entry = iFind->second;
 148             toFront( entry );
 149 #ifdef __CACHE_DIAGNOSE
 150             OUStringBuffer buf( 48 );
 151             buf.appendAscii( "> retrieved element \"" );
 152             buf.append( entry->m_key );
 153             buf.appendAscii( "\" from cache" );
 154             SAL_INFO("stoc", buf.makeStringAndClear() );
 155 #endif
 156             return &entry->m_val;
 157         }
 158     }
 159     return nullptr;
 160 }
 161
 162 template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
 163 inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::set(
 164     t_key const & key, t_val const & val )
 165 {
 166     if (0 < m_size)
 167     {
 168         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
 169
 170         Entry * entry;
 171         if (iFind == m_key2element.end())
 172         {
 173             entry = m_tail; // erase last element
 174 #ifdef __CACHE_DIAGNOSE
 175             if (entry->m_key.getLength())
 176             {
 177                 OUStringBuffer buf( 48 );
 178                 buf.appendAscii( "> kicking element \"" );
 179                 buf.append( entry->m_key );
 180                 buf.appendAscii( "\" from cache" );
 181                 SAL_INFO("stoc", buf.makeStringAndClear() );
 182             }
 183 #endif
 184             m_key2element.erase( entry->m_key );
 185             entry->m_key = key;
 186             ::std::pair< typename t_key2element::iterator, bool > insertion(
 187                 m_key2element.emplace( key, entry ) );
 188             OSL_ENSURE( insertion.second, "### inserting new cache entry failed?!" );
 189         }
 190         else
 191         {
 192             entry = iFind->second;
 193 #ifdef __CACHE_DIAGNOSE
 194             OUStringBuffer buf( 48 );
 195             buf.appendAscii( "> replacing element \"" );
 196             buf.append( entry->m_key );
 197             buf.appendAscii( "\" in cache" );
 198             SAL_INFO("stoc", buf.makeStringAndClear() );
 199 #endif
 200         }
 201         entry->m_val = val;
 202         toFront( entry );
 203     }
 204 }
 205
 206 }
 207
 208 #endif
 209
 210 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */