]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | #ifndef CEPH_LRU_MAP_H |
2 | #define CEPH_LRU_MAP_H | |
3 | ||
11fdf7f2 | 4 | #include "common/ceph_mutex.h" |
7c673cae | 5 | |
7c673cae FG |
6 | template <class K, class V> |
7 | class lru_map { | |
8 | struct entry { | |
9 | V value; | |
10 | typename std::list<K>::iterator lru_iter; | |
11 | }; | |
12 | ||
13 | std::map<K, entry> entries; | |
14 | std::list<K> entries_lru; | |
15 | ||
11fdf7f2 | 16 | ceph::mutex lock = ceph::make_mutex("lru_map::lock"); |
7c673cae FG |
17 | |
18 | size_t max; | |
19 | ||
20 | public: | |
21 | class UpdateContext { | |
22 | public: | |
23 | virtual ~UpdateContext() {} | |
24 | ||
25 | /* update should return true if object is updated */ | |
26 | virtual bool update(V *v) = 0; | |
27 | }; | |
28 | ||
29 | bool _find(const K& key, V *value, UpdateContext *ctx); | |
30 | void _add(const K& key, V& value); | |
31 | ||
32 | public: | |
11fdf7f2 | 33 | lru_map(int _max) : max(_max) {} |
7c673cae FG |
34 | virtual ~lru_map() {} |
35 | ||
36 | bool find(const K& key, V& value); | |
37 | ||
38 | /* | |
39 | * find_and_update() | |
40 | * | |
41 | * - will return true if object is found | |
42 | * - if ctx is set will return true if object is found and updated | |
43 | */ | |
44 | bool find_and_update(const K& key, V *value, UpdateContext *ctx); | |
45 | void add(const K& key, V& value); | |
46 | void erase(const K& key); | |
47 | }; | |
48 | ||
49 | template <class K, class V> | |
50 | bool lru_map<K, V>::_find(const K& key, V *value, UpdateContext *ctx) | |
51 | { | |
52 | typename std::map<K, entry>::iterator iter = entries.find(key); | |
53 | if (iter == entries.end()) { | |
54 | return false; | |
55 | } | |
56 | ||
57 | entry& e = iter->second; | |
58 | entries_lru.erase(e.lru_iter); | |
59 | ||
60 | bool r = true; | |
61 | ||
62 | if (ctx) | |
63 | r = ctx->update(&e.value); | |
64 | ||
65 | if (value) | |
66 | *value = e.value; | |
67 | ||
68 | entries_lru.push_front(key); | |
69 | e.lru_iter = entries_lru.begin(); | |
70 | ||
71 | return r; | |
72 | } | |
73 | ||
74 | template <class K, class V> | |
75 | bool lru_map<K, V>::find(const K& key, V& value) | |
76 | { | |
11fdf7f2 | 77 | std::lock_guard l(lock); |
7c673cae FG |
78 | return _find(key, &value, NULL); |
79 | } | |
80 | ||
81 | template <class K, class V> | |
82 | bool lru_map<K, V>::find_and_update(const K& key, V *value, UpdateContext *ctx) | |
83 | { | |
11fdf7f2 | 84 | std::lock_guard l(lock); |
7c673cae FG |
85 | return _find(key, value, ctx); |
86 | } | |
87 | ||
88 | template <class K, class V> | |
89 | void lru_map<K, V>::_add(const K& key, V& value) | |
90 | { | |
91 | typename std::map<K, entry>::iterator iter = entries.find(key); | |
92 | if (iter != entries.end()) { | |
93 | entry& e = iter->second; | |
94 | entries_lru.erase(e.lru_iter); | |
95 | } | |
96 | ||
97 | entries_lru.push_front(key); | |
98 | entry& e = entries[key]; | |
99 | e.value = value; | |
100 | e.lru_iter = entries_lru.begin(); | |
101 | ||
102 | while (entries.size() > max) { | |
103 | typename std::list<K>::reverse_iterator riter = entries_lru.rbegin(); | |
104 | iter = entries.find(*riter); | |
11fdf7f2 | 105 | // ceph_assert(iter != entries.end()); |
7c673cae FG |
106 | entries.erase(iter); |
107 | entries_lru.pop_back(); | |
108 | } | |
109 | } | |
110 | ||
111 | ||
112 | template <class K, class V> | |
113 | void lru_map<K, V>::add(const K& key, V& value) | |
114 | { | |
11fdf7f2 | 115 | std::lock_guard l(lock); |
7c673cae FG |
116 | _add(key, value); |
117 | } | |
118 | ||
119 | template <class K, class V> | |
120 | void lru_map<K, V>::erase(const K& key) | |
121 | { | |
11fdf7f2 | 122 | std::lock_guard l(lock); |
7c673cae FG |
123 | typename std::map<K, entry>::iterator iter = entries.find(key); |
124 | if (iter == entries.end()) | |
125 | return; | |
126 | ||
127 | entry& e = iter->second; | |
128 | entries_lru.erase(e.lru_iter); | |
129 | entries.erase(iter); | |
130 | } | |
131 | ||
132 | #endif |