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             : 
      20             : #ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX
      21             : #define INCLUDED_BINARYURP_SOURCE_CACHE_HXX
      22             : 
      23             : #include "sal/config.h"
      24             : 
      25             : #include <cassert>
      26             : #include <cstddef>
      27             : #include <map>
      28             : #include <list>
      29             : 
      30             : #include "sal/types.h"
      31             : 
      32             : namespace binaryurp {
      33             : 
      34             : namespace cache {
      35             : 
      36             : enum { size = 256, ignore = 0xFFFF };
      37             : 
      38             : }
      39             : 
      40       22043 : template< typename T > class Cache {
      41             : public:
      42             :     typedef sal_uInt16 IdxType;
      43             : 
      44       22043 :     explicit Cache(std::size_t size):
      45       22043 :         size_(size)
      46             :     {
      47             :         assert(size < cache::ignore);
      48       22043 :     }
      49             : 
      50      369554 :     IdxType add( const T& rContent, bool* pbFound) {
      51             :         assert( pbFound != NULL);
      52      369554 :         if( !size_) {
      53           0 :             *pbFound = false;
      54           0 :             return cache::ignore;
      55             :         }
      56             :         // try to insert into the map
      57      369554 :         list_.push_front( rContent); // create a temp entry
      58             :         typedef std::pair<typename LruList::iterator, IdxType> MappedType;
      59             :         typedef std::pair<typename LruItMap::iterator,bool> MapPair;
      60      369554 :         MapPair aMP = map_.insert( MappedType( list_.begin(), 0));
      61      369554 :         *pbFound = !aMP.second;
      62             : 
      63      369554 :         if( !aMP.second) { // insertion not needed => found the entry
      64      168231 :             list_.pop_front(); // remove the temp entry
      65      168231 :             list_.splice( list_.begin(), list_, aMP.first->first); // the found entry is moved to front
      66      168231 :             return aMP.first->second;
      67             :         }
      68             : 
      69             :         // test insertion successful => it was new so we keep it
      70      201323 :         IdxType n = static_cast<IdxType>( map_.size() - 1);
      71      201323 :         if( n >= size_) { // cache full => replace the LRU entry
      72             :             // find the least recently used element in the map
      73      102353 :             typename LruItMap::iterator it = map_.find( --list_.end());
      74      102353 :             n = it->second;
      75      102353 :             map_.erase( it); // remove it from the map
      76      102353 :             list_.pop_back(); // remove from the list
      77             :         }
      78      201323 :         aMP.first->second = n;
      79      201323 :         return n;
      80             :     }
      81             : 
      82             : private:
      83             :     Cache(const Cache&) SAL_DELETED_FUNCTION;
      84             :     Cache& operator=(const Cache&) SAL_DELETED_FUNCTION;
      85             : 
      86             :     typedef std::list<T> LruList; // last recently used list
      87             :     typedef typename LruList::iterator LruListIt;
      88     2374391 :     struct CmpT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return (*rA<*rB);}};
      89             :     typedef ::std::map< LruListIt, IdxType, CmpT > LruItMap; // a map into a LruList
      90             : 
      91             :     std::size_t size_;
      92             :     LruItMap map_;
      93             :     LruList list_;
      94             : };
      95             : 
      96             : }
      97             : 
      98             : #endif
      99             : 
     100             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */