1 ///###////////////////////////////////////////////////////////////////////////
2 //
3 // Burton Computer Corporation
4 // http://www.burton-computer.com
5 // http://www.cooldevtools.com
6 // $Id$
7 //
8 // Copyright (C) 2007 Burton Computer Corporation
9 // ALL RIGHTS RESERVED
10 //
11 // This program is open source software; you can redistribute it
12 // and/or modify it under the terms of the Q Public License (QPL)
13 // version 1.0. Use of this software in whole or in part, including
14 // linking it (modified or unmodified) into other programs is
15 // subject to the terms of the QPL.
16 //
17 // This program is distributed in the hope that it will be useful,
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 // Q Public License for more details.
21 //
22 // You should have received a copy of the Q Public License
23 // along with this program; see the file LICENSE.txt. If not, visit
24 // the Burton Computer Corporation or CoolDevTools web site
25 // QPL pages at:
26 //
27 // http://www.burton-computer.com/qpl.html
28 // http://www.cooldevtools.com/qpl.html
29 //
30
31 #ifndef _LRUCache_h
32 #define _LRUCache_h
33
34 #include <map>
35 #include <list>
36 #include "util.h"
37
38 template<class KeyType, class ValueType> class LRUCache
39 {
40 public:
41 struct LRUCacheNode;
42 typedef LRUCacheNode NodeType;
43 typedef Ref<NodeType> RefType;
44 typedef list<RefType> ListType;
45 typedef typename list<RefType>::iterator IterType;
46
47 class LRUCacheNodeKeyCompare;
48 typedef map<NodeType *,NodeType *,LRUCacheNodeKeyCompare> MapType;
49 typedef typename MapType::iterator MapIterType;
50
51 struct LRUCacheNode
52 {
53 KeyType key;
54 ValueType value;
55 bool isLocked;
56 IterType currentPosition;
57 };
58
59 class LRUCacheNodeKeyCompare : public binary_function<NodeType *, NodeType *, bool>
60 {
61 public:
operator()62 bool operator()(const NodeType *a,
63 const NodeType *b) const
64 {
65 return a->key < b->key;
66 }
67 };
68
69 class iterator
70 {
71 friend class LRUCache;
72
iterator(MapType * index,MapIterType iter)73 iterator(MapType *index,
74 MapIterType iter)
75 : m_index(index), m_iterator(iter)
76 {
77 }
78
79 public:
80 bool operator==(const iterator &other)
81 {
82 return m_iterator == other.m_iterator;
83 }
84
85 bool operator!=(const iterator &other)
86 {
87 return m_iterator != other.m_iterator;
88 }
89
90 iterator &operator++()
91 {
92 ++m_iterator;
93 return *this;
94 }
95
96 iterator operator++(int)
97 {
98 iterator old_value(m_index, m_iterator);
99 ++m_iterator;
100 return old_value;
101 }
102
key()103 const KeyType &key()
104 {
105 assert(m_iterator != m_index->end());
106 return m_iterator->second->key;
107 }
108
value()109 const ValueType &value()
110 {
111 assert(m_iterator != m_index->end());
112 return m_iterator->second->value;
113 }
114
isLocked()115 bool isLocked()
116 {
117 assert(m_iterator != m_index->end());
118 return m_iterator->second->isLocked;
119 }
120
121 private:
122 MapType *m_index;
123 MapIterType m_iterator;
124 };
125
126 public:
LRUCache(int max_size)127 LRUCache(int max_size)
128 : m_maxSize(max_size), m_normalCount(0), m_lockedCount(0)
129 {
130 }
131
~LRUCache()132 ~LRUCache()
133 {
134 }
135
136 bool get(const KeyType &key,
137 ValueType &value);
138
139 void put(const KeyType &key,
140 ValueType value,
141 bool is_locked);
142
143 void dump();
144
145 void clear();
146
begin()147 iterator begin()
148 {
149 return iterator(&m_index, m_index.begin());
150 }
151
end()152 iterator end()
153 {
154 return iterator(&m_index, m_index.end());
155 }
156
157 iterator find(const KeyType &key);
158
unlock(const KeyType & key)159 void unlock(const KeyType &key)
160 {
161 setLocked(findNode(key), false);
162 }
163
lock(const KeyType & key)164 void lock(const KeyType &key)
165 {
166 setLocked(findNode(key), true);
167 }
168
size()169 int size()
170 {
171 return m_normalCount + m_lockedCount;
172 }
173
maxSize()174 int maxSize()
175 {
176 return m_maxSize;
177 }
178
lockedCount()179 int lockedCount()
180 {
181 return m_lockedCount;
182 }
183
unlockedCount()184 int unlockedCount()
185 {
186 return m_normalCount;
187 }
188
189 private:
190 void addNewNode(const KeyType &key,
191 ValueType value,
192 bool is_locked);
193
194 NodeType *findNode(const KeyType &key);
195
196 void setLocked(NodeType *node,
197 bool is_locked);
198
199 void removeNode(NodeType *node);
200
201 void eliminateOldObjects();
202
203 void dump(ListType &nodes);
204
205 void dump(NodeType *node);
206
setLocked(const KeyType & key,bool is_locked)207 void setLocked(const KeyType &key,
208 bool is_locked)
209 {
210 setLocked(findNode(key), is_locked);
211 }
212
213 private:
214 int m_maxSize;
215 int m_lockedCount;
216 int m_normalCount;
217 ListType m_normalList;
218 ListType m_lockedList;
219 MapType m_index;
220 };
221
222 template<class KeyType, class ValueType>
get(const KeyType & key,ValueType & value)223 bool LRUCache<KeyType, ValueType>::get(const KeyType &key,
224 ValueType &value)
225 {
226 NodeType *node = findNode(key);
227 if (node == 0) {
228 return false;
229 }
230
231 if (!node->isLocked) {
232 m_normalList.splice(m_normalList.begin(), m_normalList, node->currentPosition);
233 node->currentPosition = m_normalList.begin();
234 assert((*node->currentPosition).ptr() == node);
235 }
236
237 value = node->value;
238 return true;
239 }
240
241 template<class KeyType, class ValueType>
put(const KeyType & key,ValueType value,bool is_locked)242 void LRUCache<KeyType, ValueType>::put(const KeyType &key,
243 ValueType value,
244 bool is_locked)
245 {
246 NodeType key_node;
247 key_node.key = key;
248 MapIterType i = m_index.find(&key_node);
249 if (i == m_index.end()) {
250 addNewNode(key, value, is_locked);
251 } else {
252 NodeType *node = i->second;
253 setLocked(node, is_locked);
254 node->value = value;
255 }
256 }
257
258 template<class KeyType, class ValueType>
dump()259 void LRUCache<KeyType, ValueType>::dump()
260 {
261 cerr << "locked: " << lockedCount() << ": ";
262 cerr << "locked: ";
263 dump(m_lockedList);
264 cerr << "normal: " << unlockedCount() << ": ";
265 dump(m_normalList);
266 }
267
268 template<class KeyType, class ValueType>
clear()269 void LRUCache<KeyType, ValueType>::clear()
270 {
271 m_index.clear();
272 m_normalList.clear();
273 m_lockedList.clear();
274 m_normalCount = 0;
275 m_lockedCount = 0;
276 }
277
278 template<class KeyType, class ValueType>
find(const KeyType & key)279 typename LRUCache<KeyType, ValueType>::iterator LRUCache<KeyType, ValueType>::find(const KeyType &key)
280 {
281 NodeType key_node;
282 key_node.key = key;
283 return iterator(&m_index, m_index.find(&key_node));
284 }
285
286 template<class KeyType, class ValueType>
addNewNode(const KeyType & key,ValueType value,bool is_locked)287 void LRUCache<KeyType, ValueType>::addNewNode(const KeyType &key,
288 ValueType value,
289 bool is_locked)
290 {
291 eliminateOldObjects();
292 RefType node(new NodeType);
293 node->key = key;
294 node->value = value;
295 node->isLocked = is_locked;
296 if (is_locked) {
297 node->currentPosition = m_lockedList.insert(m_lockedList.begin(), node);
298 m_lockedCount += 1;
299 } else {
300 node->currentPosition = m_normalList.insert(m_normalList.begin(), node);
301 m_normalCount += 1;
302 }
303 m_index.insert(make_pair(node.ptr(), node.ptr()));
304 }
305
306 template<class KeyType, class ValueType>
findNode(const KeyType & key)307 typename LRUCache<KeyType, ValueType>::NodeType *LRUCache<KeyType, ValueType>::findNode(const KeyType &key)
308 {
309 NodeType key_node;
310 key_node.key = key;
311 MapIterType map_iter = m_index.find(&key_node);
312 return (map_iter == m_index.end()) ? 0 : map_iter->second;
313 }
314
315 template<class KeyType, class ValueType>
setLocked(NodeType * node,bool is_locked)316 void LRUCache<KeyType, ValueType>::setLocked(NodeType *node,
317 bool is_locked)
318 {
319 if (node) {
320 if (is_locked) {
321 if (!node->isLocked) {
322 m_normalCount -= 1;
323 m_lockedCount += 1;
324 node->isLocked = true;
325 m_lockedList.splice(m_lockedList.begin(), m_normalList, node->currentPosition);
326 node->currentPosition = m_lockedList.begin();
327 assert((*node->currentPosition).ptr() == node);
328 }
329 } else {
330 if (node->isLocked) {
331 m_normalCount += 1;
332 m_lockedCount -= 1;
333 node->isLocked = false;
334 m_normalList.splice(m_normalList.begin(), m_lockedList, node->currentPosition);
335 node->currentPosition = m_normalList.begin();
336 assert((*node->currentPosition).ptr() == node);
337 }
338 }
339 }
340 }
341
342 template<class KeyType, class ValueType>
removeNode(NodeType * node)343 void LRUCache<KeyType, ValueType>::removeNode(NodeType *node)
344 {
345 if (node->isLocked) {
346 m_lockedCount -= 1;
347 m_index.erase(node);
348 m_lockedList.erase(node->currentPosition);
349 } else {
350 m_normalCount -= 1;
351 m_index.erase(node);
352 m_normalList.erase(node->currentPosition);
353 }
354 }
355
356 template<class KeyType, class ValueType>
eliminateOldObjects()357 void LRUCache<KeyType, ValueType>::eliminateOldObjects()
358 {
359 while (size() >= m_maxSize && m_normalCount > 0) {
360 RefType nr(m_normalList.back());
361 removeNode(nr.ptr());
362 }
363 }
364
365 template<class KeyType, class ValueType>
dump(ListType & nodes)366 void LRUCache<KeyType, ValueType>::dump(ListType &nodes)
367 {
368 for (IterType i = nodes.begin(); i != nodes.end(); ++i) {
369 dump((*i).ptr());
370 }
371 cerr << endl;
372 }
373
374 template<class KeyType, class ValueType>
dump(NodeType * node)375 void LRUCache<KeyType, ValueType>::dump(NodeType *node)
376 {
377 cerr << "Node(" << node->key << "," << node->value << "," << node->isLocked << ")";
378 }
379
380 #endif
381