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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| #include <memory>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <boost/noncopyable.hpp>
#include "tree.hh"
template<typename Key = std::string, typename Value = std::string>
struct cache : boost::noncopyable
{
struct cache_node;
typedef Key key_type;
typedef Value value_type;
typedef std::shared_ptr<cache_node> shared_node;
typedef std::weak_ptr<cache_node> weak_node;
typedef tree<shared_node> tree_type;
typedef std::unordered_map<key_type, weak_node> table_type;
typedef typename tree_type::iterator iterator;
struct cache_node : boost::noncopyable
{
cache_node(const key_type& key, const value_type& value, table_type& lookup)
: key(key), value(value), lookup(lookup)
{ }
~cache_node() {
typename table_type::iterator it = lookup.find(key);
if (it != lookup.end()) {
lookup.erase(it);
}
}
key_type key;
value_type value;
table_type& lookup;
};
void add(const key_type& key, const value_type& value)
{
typename table_type::const_iterator it = table.find(key);
if (it != table.end()) {
quick_del(it);
}
typename tree_type::iterator top = nodes.begin();
shared_node p(new cache_node(key, value, table));
nodes.insert(top, p);
table[key] = weak_node(p);
}
void add(iterator& parent, const key_type& key, const value_type& value)
{
typename table_type::const_iterator it = table.find(key);
if (it != table.end()) {
quick_del(it);
}
shared_node p(new cache_node(key, value, table));
nodes.append_child(parent, p);
table[key] = weak_node(p);
}
void add(const key_type& parent, const key_type& key, const value_type& value)
{
iterator itp = location(parent);
if (valid(itp)) {
add(itp, key, value);
}
}
iterator location(const key_type& key) const
{
iterator itr = nodes.end();
typename table_type::const_iterator it = table.find(key);
if (it != table.end()) {
shared_node s = it->second.lock();
itr = find(nodes.begin(), nodes.end(), s);
}
return itr;
}
bool valid(const iterator& it) const
{
return it != nodes.end();
}
void del(const key_type& key)
{
typename table_type::const_iterator it = table.find(key);
if (it != table.end()) {
quick_del(it);
}
}
value_type get(const key_type& key) const
{
typename table_type::const_iterator it = table.find(key);
if (it != table.end()) {
shared_node s = it->second.lock();
return s->value;
}
return value_type();
}
bool has(const key_type& key) const
{
return table.find(key) != table.end();
}
void clear()
{
nodes.clear();
}
private:
void quick_del(const typename table_type::const_iterator& it)
{
typename tree_type::iterator itr;
{
shared_node s = it->second.lock();
itr = find(nodes.begin(), nodes.end(), s);
}
if (itr != nodes.end()) {
nodes.erase(itr);
}
}
private:
table_type table;
tree_type nodes;
}; |
