1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 #ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX 25 #define INCLUDED_BINARYURP_SOURCE_CACHE_HXX 26 27 #include "sal/config.h" 28 29 #include <cstddef> 30 #include <list> 31 #ifdef USE_UNORDERED_MAP 32 #include <unordered_map> 33 #else 34 #include <map> 35 #endif 36 37 #include "boost/noncopyable.hpp" 38 #include "osl/diagnose.h" 39 #include "sal/types.h" 40 41 namespace binaryurp { 42 43 namespace cache { 44 45 enum { size = 256, ignore = 0xFFFF }; 46 47 } 48 49 template< typename T > class Cache : private boost::noncopyable { 50 public: 51 typedef sal_uInt16 IdxType; 52 Cache(std::size_t size)53 explicit Cache(std::size_t size): 54 size_(size) 55 { 56 OSL_ASSERT(size < cache::ignore); 57 } 58 add(const T & rContent,bool * pbFound)59 IdxType add( const T& rContent, bool* pbFound) { 60 OSL_ASSERT( pbFound != NULL); 61 if( !size_) { 62 *pbFound = false; 63 return cache::ignore; 64 } 65 // try to insert into the map 66 list_.push_front( rContent); // create a temp entry 67 typedef std::pair<typename LruList::iterator, IdxType> MappedType; 68 typedef std::pair<typename LruItMap::iterator,bool> MapPair; 69 MapPair aMP = map_.insert( MappedType( list_.begin(), 0)); 70 *pbFound = !aMP.second; 71 72 if( !aMP.second) { // insertion not needed => found the entry 73 list_.pop_front(); // remove the temp entry 74 list_.splice( list_.begin(), list_, aMP.first->first); // the found entry is moved to front 75 return aMP.first->second; 76 } 77 78 // test insertion successful => it was new so we keep it 79 IdxType n = static_cast<IdxType>( map_.size() - 1); 80 if( n >= size_) { // cache full => replace the LRU entry 81 // find the least recently used element in the map 82 typename LruItMap::iterator it = map_.find( --list_.end()); 83 n = it->second; 84 map_.erase( it); // remove it from the map 85 list_.pop_back(); // remove from the list 86 } 87 aMP.first->second = n; 88 return n; 89 } 90 91 private: 92 typedef std::list<T> LruList; // last recently used list 93 typedef typename LruList::iterator LruListIt; 94 #ifdef URPCACHE_USES_UNORDERED_MAP operator ()binaryurp::Cache::HashT95 struct HashT{ size_t operator()( const LruListIt& rA) const { return hash(*rA;);}; 96 struct EqualT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return *rA==*rB;}}; 97 typedef ::std::unordered_map< LruListIt, IdxType, HashT, EqualT > LruItMap; // a map into a LruList 98 #else 99 struct CmpT{ bool operator()( const LruListIt& rA, const LruListIt& rB) const { return (*rA<*rB);}}; 100 typedef ::std::map< LruListIt, IdxType, CmpT > LruItMap; // a map into a LruList 101 #endif 102 103 std::size_t size_; 104 LruItMap map_; 105 LruList list_; 106 }; 107 108 } 109 110 #endif 111 112