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