LCOV - code coverage report
Current view: top level - stoc/source/security - lru_cache.h (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 6 50 12.0 %
Date: 2015-06-13 12:38:46 Functions: 2 8 25.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_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           0 :     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             :     /** Ctor.
      62             : 
      63             :         @param size number of elements to be cached; default param set to 128
      64             :     */
      65             :     inline lru_cache( ::std::size_t size );
      66             : 
      67             :     /** Destructor: releases all cached elements and keys.
      68             :     */
      69             :     inline ~lru_cache();
      70             : 
      71             :     /** Retrieves a pointer to value in cache.  Returns 0, if none was found.
      72             : 
      73             :         @param key a key
      74             :         @return pointer to value or 0
      75             :     */
      76             :     inline t_val const * lookup( t_key const & key ) const;
      77             : 
      78             :     /** Sets a value to be cached for given key.
      79             : 
      80             :         @param key a key
      81             :         @param val a value
      82             :     */
      83             :     inline void set( t_key const & key, t_val const & val );
      84             : 
      85             :     /** Tests whether a value is cached for given key.
      86             : 
      87             :         @param key a key
      88             :         @return true, if value is cached
      89             :     */
      90             :     inline bool has( t_key const & key ) const;
      91             : 
      92             :     /** Clears the cache, releasing all cached elements and keys.
      93             :     */
      94             :     inline void clear();
      95             : 
      96             :     /** Sets the number of elements to be cached.  This will clear previous entries.
      97             : 
      98             :         @param cacheSize number of elements to be cached
      99             :     */
     100             :     inline void setSize( ::std::size_t size );
     101             : };
     102             : 
     103             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     104           0 : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::setSize(
     105             :     ::std::size_t size )
     106             : {
     107           0 :     m_key2element.clear();
     108           0 :     delete [] m_block;
     109           0 :     m_block = 0;
     110           0 :     m_size = size;
     111             : 
     112           0 :     if (0 < m_size)
     113             :     {
     114           0 :         m_block = new Entry[ m_size ];
     115           0 :         m_head = m_block;
     116           0 :         m_tail = m_block + m_size -1;
     117           0 :         for ( ::std::size_t nPos = m_size; nPos--; )
     118             :         {
     119           0 :             m_block[ nPos ].m_pred = m_block + nPos -1;
     120           0 :             m_block[ nPos ].m_succ = m_block + nPos +1;
     121             :         }
     122             :     }
     123           0 : }
     124             : 
     125             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     126             : inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache(
     127             :     ::std::size_t size )
     128             :     : m_size( 0 )
     129             :     , m_block( 0 )
     130             :     , m_tail( 0 )
     131             : {
     132             :     setSize( size );
     133             : }
     134             : 
     135             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     136           2 : inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache()
     137             :     : m_size( 0 )
     138             :     , m_block( 0 )
     139             :     , m_head( 0 )
     140           2 :     , m_tail( 0 )
     141             : {
     142           2 : }
     143             : 
     144             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     145           2 : inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::~lru_cache()
     146             : {
     147           2 :     delete [] m_block;
     148           2 : }
     149             : 
     150             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     151           0 : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::toFront(
     152             :     Entry * entry ) const
     153             : {
     154           0 :     if (entry != m_head)
     155             :     {
     156             :         // cut out element
     157           0 :         if (entry == m_tail)
     158             :         {
     159           0 :             m_tail = entry->m_pred;
     160             :         }
     161             :         else
     162             :         {
     163           0 :             entry->m_succ->m_pred = entry->m_pred;
     164           0 :             entry->m_pred->m_succ = entry->m_succ;
     165             :         }
     166             :         // push to front
     167           0 :         m_head->m_pred = entry;
     168           0 :         entry->m_succ = m_head;
     169           0 :         m_head = entry;
     170             :     }
     171           0 : }
     172             : 
     173             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     174             : inline bool lru_cache< t_key, t_val, t_hashKey, t_equalKey >::has(
     175             :     t_key const & key ) const
     176             : {
     177             :     typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
     178             :     return (iFind != m_key2element.end());
     179             : }
     180             : 
     181             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     182           0 : inline t_val const * lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lookup(
     183             :     t_key const & key ) const
     184             : {
     185           0 :     if (0 < m_size)
     186             :     {
     187           0 :         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
     188           0 :         if (iFind != m_key2element.end())
     189             :         {
     190           0 :             Entry * entry = iFind->second;
     191           0 :             toFront( entry );
     192             : #ifdef __CACHE_DIAGNOSE
     193             :             OUStringBuffer buf( 48 );
     194             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> retrieved element \"") );
     195             :             buf.append( entry->m_key );
     196             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
     197             :             OString str( OUStringToOString(
     198             :                 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
     199             :             OSL_TRACE( "%s", str.getStr() );
     200             : #endif
     201           0 :             return &entry->m_val;
     202             :         }
     203             :     }
     204           0 :     return 0;
     205             : }
     206             : 
     207             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     208           0 : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::set(
     209             :     t_key const & key, t_val const & val )
     210             : {
     211           0 :     if (0 < m_size)
     212             :     {
     213           0 :         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
     214             : 
     215             :         Entry * entry;
     216           0 :         if (iFind == m_key2element.end())
     217             :         {
     218           0 :             entry = m_tail; // erase last element
     219             : #ifdef __CACHE_DIAGNOSE
     220             :             if (entry->m_key.getLength())
     221             :             {
     222             :                 OUStringBuffer buf( 48 );
     223             :                 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> kicking element \"") );
     224             :                 buf.append( entry->m_key );
     225             :                 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
     226             :                 OString str( OUStringToOString(
     227             :                     buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
     228             :                 OSL_TRACE( "%s", str.getStr() );
     229             :             }
     230             : #endif
     231           0 :             m_key2element.erase( entry->m_key );
     232           0 :             entry->m_key = key;
     233             :             ::std::pair< typename t_key2element::iterator, bool > insertion(
     234           0 :                 m_key2element.insert( typename t_key2element::value_type( key, entry ) ) );
     235             : #ifdef __CACHE_DIAGNOSE
     236             :             OSL_ENSURE( insertion.second, "### inserting new cache entry failed?!" );
     237             : #endif
     238             :             (void) insertion; // avoid warnings
     239             :         }
     240             :         else
     241             :         {
     242           0 :             entry = iFind->second;
     243             : #ifdef __CACHE_DIAGNOSE
     244             :             OUStringBuffer buf( 48 );
     245             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> replacing element \"") );
     246             :             buf.append( entry->m_key );
     247             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" in cache") );
     248             :             OString str( OUStringToOString(
     249             :                 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
     250             :             OSL_TRACE( "%s", str.getStr() );
     251             : #endif
     252             :         }
     253           0 :         entry->m_val = val;
     254           0 :         toFront( entry );
     255             :     }
     256           0 : }
     257             : 
     258             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     259             : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::clear()
     260             : {
     261             :     m_key2element.clear();
     262             :     for ( ::std::size_t nPos = m_size; nPos--; )
     263             :     {
     264             :         m_block[ nPos ].m_key = t_key();
     265             :         m_block[ nPos ].m_val = t_val();
     266             :     }
     267             : #ifdef __CACHE_DIAGNOSE
     268             :     OSL_TRACE( "> cleared cache" );
     269             : #endif
     270             : }
     271             : 
     272             : }
     273             : 
     274             : #endif
     275             : 
     276             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.11