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