LCOV - code coverage report
Current view: top level - stoc/source/security - lru_cache.h (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 50 0.0 %
Date: 2014-04-14 Functions: 0 8 0.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 _STOC_SEC_LRU_CACHE_H_
      20             : #define _STOC_SEC_LRU_CACHE_H_
      21             : 
      22             : #include <boost/unordered_map.hpp>
      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 ::boost::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 SAL_THROW(());
      56             : 
      57             : public:
      58             :     /** Default Ctor.  Does not cache.
      59             :     */
      60             :     inline lru_cache() SAL_THROW(());
      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 ) SAL_THROW(());
      66             : 
      67             :     /** Destructor: releases all cached elements and keys.
      68             :     */
      69             :     inline ~lru_cache() SAL_THROW(());
      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 SAL_THROW(());
      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 ) SAL_THROW(());
      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 SAL_THROW(());
      91             : 
      92             :     /** Clears the cache, releasing all cached elements and keys.
      93             :     */
      94             :     inline void clear() SAL_THROW(());
      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 ) SAL_THROW(());
     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 ) SAL_THROW(())
     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 ) SAL_THROW(())
     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           0 : inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lru_cache() SAL_THROW(())
     137             :     : m_size( 0 )
     138           0 :     , m_block( 0 )
     139             : {
     140           0 : }
     141             : 
     142             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     143           0 : inline lru_cache< t_key, t_val, t_hashKey, t_equalKey >::~lru_cache()
     144             :     SAL_THROW(())
     145             : {
     146           0 :     delete [] m_block;
     147           0 : }
     148             : 
     149             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     150           0 : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::toFront(
     151             :     Entry * entry ) const SAL_THROW(())
     152             : {
     153           0 :     if (entry != m_head)
     154             :     {
     155             :         // cut out element
     156           0 :         if (entry == m_tail)
     157             :         {
     158           0 :             m_tail = entry->m_pred;
     159             :         }
     160             :         else
     161             :         {
     162           0 :             entry->m_succ->m_pred = entry->m_pred;
     163           0 :             entry->m_pred->m_succ = entry->m_succ;
     164             :         }
     165             :         // push to front
     166           0 :         m_head->m_pred = entry;
     167           0 :         entry->m_succ = m_head;
     168           0 :         m_head = entry;
     169             :     }
     170           0 : }
     171             : 
     172             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     173             : inline bool lru_cache< t_key, t_val, t_hashKey, t_equalKey >::has(
     174             :     t_key const & key ) const SAL_THROW(())
     175             : {
     176             :     typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
     177             :     return (iFind != m_key2element.end());
     178             : }
     179             : 
     180             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     181           0 : inline t_val const * lru_cache< t_key, t_val, t_hashKey, t_equalKey >::lookup(
     182             :     t_key const & key ) const SAL_THROW(())
     183             : {
     184           0 :     if (0 < m_size)
     185             :     {
     186           0 :         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
     187           0 :         if (iFind != m_key2element.end())
     188             :         {
     189           0 :             Entry * entry = iFind->second;
     190           0 :             toFront( entry );
     191             : #ifdef __CACHE_DIAGNOSE
     192             :             OUStringBuffer buf( 48 );
     193             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> retrieved element \"") );
     194             :             buf.append( entry->m_key );
     195             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
     196             :             OString str( OUStringToOString(
     197             :                 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
     198             :             OSL_TRACE( "%s", str.getStr() );
     199             : #endif
     200           0 :             return &entry->m_val;
     201             :         }
     202             :     }
     203           0 :     return 0;
     204             : }
     205             : 
     206             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     207           0 : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::set(
     208             :     t_key const & key, t_val const & val ) SAL_THROW(())
     209             : {
     210           0 :     if (0 < m_size)
     211             :     {
     212           0 :         typename t_key2element::const_iterator const iFind( m_key2element.find( key ) );
     213             : 
     214             :         Entry * entry;
     215           0 :         if (iFind == m_key2element.end())
     216             :         {
     217           0 :             entry = m_tail; // erase last element
     218             : #ifdef __CACHE_DIAGNOSE
     219             :             if (entry->m_key.getLength())
     220             :             {
     221             :                 OUStringBuffer buf( 48 );
     222             :                 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> kicking element \"") );
     223             :                 buf.append( entry->m_key );
     224             :                 buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" from cache") );
     225             :                 OString str( OUStringToOString(
     226             :                     buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
     227             :                 OSL_TRACE( "%s", str.getStr() );
     228             :             }
     229             : #endif
     230           0 :             m_key2element.erase( entry->m_key );
     231           0 :             entry->m_key = key;
     232             :             ::std::pair< typename t_key2element::iterator, bool > insertion(
     233           0 :                 m_key2element.insert( typename t_key2element::value_type( key, entry ) ) );
     234             : #ifdef __CACHE_DIAGNOSE
     235             :             OSL_ENSURE( insertion.second, "### inserting new cache entry failed?!" );
     236             : #endif
     237             :             (void) insertion; // avoid warnings
     238             :         }
     239             :         else
     240             :         {
     241           0 :             entry = iFind->second;
     242             : #ifdef __CACHE_DIAGNOSE
     243             :             OUStringBuffer buf( 48 );
     244             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("> replacing element \"") );
     245             :             buf.append( entry->m_key );
     246             :             buf.appendAscii( RTL_CONSTASCII_STRINGPARAM("\" in cache") );
     247             :             OString str( OUStringToOString(
     248             :                 buf.makeStringAndClear(), RTL_TEXTENCODING_ASCII_US ) );
     249             :             OSL_TRACE( "%s", str.getStr() );
     250             : #endif
     251             :         }
     252           0 :         entry->m_val = val;
     253           0 :         toFront( entry );
     254             :     }
     255           0 : }
     256             : 
     257             : template< typename t_key, typename t_val, typename t_hashKey, typename t_equalKey >
     258             : inline void lru_cache< t_key, t_val, t_hashKey, t_equalKey >::clear() SAL_THROW(())
     259             : {
     260             :     m_key2element.clear();
     261             :     for ( ::std::size_t nPos = m_size; nPos--; )
     262             :     {
     263             :         m_block[ nPos ].m_key = t_key();
     264             :         m_block[ nPos ].m_val = t_val();
     265             :     }
     266             : #ifdef __CACHE_DIAGNOSE
     267             :     OSL_TRACE( "> cleared cache" );
     268             : #endif
     269             : }
     270             : 
     271             : }
     272             : 
     273             : #endif
     274             : 
     275             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10