1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#ifndef VGSTOOLS_CACHE_H
#define VGSTOOLS_CACHE_H
#include "stdext.h"
#include <cassert>
#include <list>
#include <map>
/* Interface for TValue:
* size_t weight()
* bool is_newer( time_t )
* bool load()
*
*/
namespace vgstools {
template<typename TKey, typename TValue, typename KeyComp = std::less<TKey>>
class cache
{
public:
typedef TKey key_type;
typedef TValue mapped_type;
typedef std::shared_ptr<mapped_type> ptr_type;
private:
typedef std::pair<key_type, ptr_type> value_type;
typedef std::list<value_type> ValueList;
typedef std::map<key_type, typename ValueList::iterator, KeyComp> KeyMap;
public:
cache( size_t maxWeight )
: m_maxWeight( maxWeight )
, m_currentWeight( 0 ) {}
size_t weight() const { return m_currentWeight; }
size_t count() const { return m_values.size(); }
ptr_type get( key_type const& key )
{
assert( m_lookup.size() == m_values.size() );
typename KeyMap::iterator it = m_lookup.find( key );
ptr_type result = it != m_lookup.end() ? it->second->second : ptr_type( new mapped_type( key ) );
if ( it != m_lookup.end() ) {
if ( result->is_current() ) {
if ( it->second != m_values.begin() ) {
m_values.erase( it->second );
it->second = m_values.insert( m_values.begin(), std::make_pair( key, result ) );
}
return result;
}
m_currentWeight -= result->weight();
m_values.erase( it->second );
}
if ( !result->load() ) {
if ( it != m_lookup.end() )
m_lookup.erase( it );
return ptr_type();
}
// put new object into cache
if ( result->weight() < m_maxWeight ) {
m_currentWeight += result->weight();
typename ValueList::iterator element = m_values.insert( m_values.begin(), std::make_pair( key, result ) );
if ( it != m_lookup.end() )
it->second = element;
else
m_lookup.insert( std::make_pair( key, element ) );
while ( m_currentWeight > m_maxWeight ) {
value_type& value = m_values.back();
m_currentWeight -= value.second->weight();
m_lookup.erase( m_lookup.find( value.first ) );
m_values.pop_back();
}
}
return result;
}
private:
std::size_t m_maxWeight;
std::size_t m_currentWeight;
ValueList m_values;
KeyMap m_lookup;
};
} // namespace vgstools
#endif // VGSTOOLS_CACHE_H
|
