cache.hxx (3638366c) cache.hxx (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

--- 13 unchanged lines hidden (view full) ---

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>
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

--- 13 unchanged lines hidden (view full) ---

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 <map>
30#include <list>
31#ifdef USE_UNORDERED_MAP
32 #include <unordered_map>
33#else
34 #include <map>
35#endif
31
32#include "boost/noncopyable.hpp"
33#include "osl/diagnose.h"
34#include "sal/types.h"
35
36namespace binaryurp {
37
38namespace cache {
39
40enum { size = 256, ignore = 0xFFFF };
41
42}
43
36
37#include "boost/noncopyable.hpp"
38#include "osl/diagnose.h"
39#include "sal/types.h"
40
41namespace binaryurp {
42
43namespace cache {
44
45enum { size = 256, ignore = 0xFFFF };
46
47}
48
44template< typename T > class Cache: private boost::noncopyable {
49template< typename T > class Cache : private boost::noncopyable {
45public:
50public:
51 typedef sal_uInt16 IdxType;
52
46 explicit Cache(std::size_t size):
53 explicit Cache(std::size_t size):
47 size_(size), first_(map_.end()), last_(map_.end())
54 size_(size)
48 {
49 OSL_ASSERT(size < cache::ignore);
50 }
51
55 {
56 OSL_ASSERT(size < cache::ignore);
57 }
58
52 sal_uInt16 add(T const & content, bool * found) {
53 OSL_ASSERT(found != 0);
54 typename Map::iterator i(map_.find(content));
55 *found = i != map_.end();
56 if (i == map_.end()) {
57 typename Map::size_type n = map_.size();
58 if (n < size_) {
59 i =
60 (map_.insert(
61 typename Map::value_type(
62 content,
63 Entry(
64 static_cast< sal_uInt16 >(n), map_.end(),
65 first_)))).
66 first;
67 if (first_ == map_.end()) {
68 last_ = i;
69 } else {
70 first_->second.prev = i;
71 }
72 first_ = i;
73 } else if (last_ != map_.end()) {
74 i =
75 (map_.insert(
76 typename Map::value_type(
77 content,
78 Entry(last_->second.index, map_.end(), first_)))).
79 first;
80 first_->second.prev = i;
81 first_ = i;
82 typename Map::iterator j(last_);
83 last_ = last_->second.prev;
84 last_->second.next = map_.end();
85 map_.erase(j);
86 } else {
87 // Reached iff size_ == 0:
88 return cache::ignore;
89 }
90 } else if (i != first_) {
91 // Move to front (reached only if size_ > 1):
92 i->second.prev->second.next = i->second.next;
93 if (i->second.next == map_.end()) {
94 last_ = i->second.prev;
95 } else {
96 i->second.next->second.prev = i->second.prev;
97 }
98 i->second.prev = map_.end();
99 i->second.next = first_;
100 first_->second.prev = i;
101 first_ = i;
102 }
103 return i->second.index;
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;
104 }
105
106private:
89 }
90
91private:
107 struct Entry;
92 typedef std::list<T> LruList; // last recently used list
93 typedef typename LruList::iterator LruListIt;
94#ifdef URPCACHE_USES_UNORDERED_MAP
95 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
108
102
109 typedef std::map< T, Entry > Map;
110
111 struct Entry {
112 sal_uInt16 index;
113 typename Map::iterator prev;
114 typename Map::iterator next;
115
116 Entry(
117 sal_uInt16 theIndex, typename Map::iterator thePrev,
118 typename Map::iterator theNext):
119 index(theIndex), prev(thePrev), next(theNext) {}
120 };
121
122 std::size_t size_;
103 std::size_t size_;
123 Map map_;
124 typename Map::iterator first_;
125 typename Map::iterator last_;
104 LruItMap map_;
105 LruList list_;
126};
127
128}
129
130#endif
106};
107
108}
109
110#endif
111