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

Generated by: LCOV version 1.10