xref: /aoo42x/main/binaryurp/source/cache.hxx (revision 7f80ef06)
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