1//
2// LRUStrategy.h
3//
4// Library: Foundation
5// Package: Cache
6// Module: LRUStrategy
7//
8// Definition of the LRUStrategy class.
9//
10// Copyright (c) 2006, Applied Informatics Software Engineering GmbH.
11// and Contributors.
12//
13// SPDX-License-Identifier: BSL-1.0
14//
15
16
17#ifndef Foundation_LRUStrategy_INCLUDED
18#define Foundation_LRUStrategy_INCLUDED
19
20
21#include "Poco/KeyValueArgs.h"
22#include "Poco/ValidArgs.h"
23#include "Poco/AbstractStrategy.h"
24#include "Poco/EventArgs.h"
25#include "Poco/Exception.h"
26#include <list>
27#include <map>
28#include <cstddef>
29
30
31namespace Poco {
32
33
34template <class TKey, class TValue>
35class LRUStrategy: public AbstractStrategy<TKey, TValue>
36 /// An LRUStrategy implements least recently used cache replacement.
37{
38public:
39 typedef std::list<TKey> Keys;
40 typedef typename Keys::iterator Iterator;
41 typedef typename Keys::const_iterator ConstIterator;
42 typedef std::map<TKey, Iterator> KeyIndex;
43 typedef typename KeyIndex::iterator IndexIterator;
44 typedef typename KeyIndex::const_iterator ConstIndexIterator;
45
46public:
47 LRUStrategy(std::size_t size):
48 _size(size)
49 {
50 if (_size < 1) throw InvalidArgumentException("size must be > 0");
51 }
52
53 ~LRUStrategy()
54 {
55 }
56
57 void onAdd(const void*, const KeyValueArgs <TKey, TValue>& args)
58 {
59 _keys.push_front(args.key());
60 std::pair<IndexIterator, bool> stat = _keyIndex.insert(std::make_pair(args.key(), _keys.begin()));
61 if (!stat.second)
62 {
63 stat.first->second = _keys.begin();
64 }
65 }
66
67 void onRemove(const void*, const TKey& key)
68 {
69 IndexIterator it = _keyIndex.find(key);
70
71 if (it != _keyIndex.end())
72 {
73 _keys.erase(it->second);
74 _keyIndex.erase(it);
75 }
76 }
77
78 void onGet(const void*, const TKey& key)
79 {
80 // LRU: in case of an hit, move to begin
81 IndexIterator it = _keyIndex.find(key);
82
83 if (it != _keyIndex.end())
84 {
85 _keys.splice(_keys.begin(), _keys, it->second); //_keys.erase(it->second)+_keys.push_front(key);
86 it->second = _keys.begin();
87 }
88 }
89
90 void onClear(const void*, const EventArgs& args)
91 {
92 _keys.clear();
93 _keyIndex.clear();
94 }
95
96 void onIsValid(const void*, ValidArgs<TKey>& args)
97 {
98 if (_keyIndex.find(args.key()) == _keyIndex.end())
99 {
100 args.invalidate();
101 }
102 }
103
104 void onReplace(const void*, std::set<TKey>& elemsToRemove)
105 {
106 // Note: replace only informs the cache which elements
107 // it would like to remove!
108 // it does not remove them on its own!
109 std::size_t curSize = _keyIndex.size();
110
111 if (curSize < _size)
112 {
113 return;
114 }
115
116 std::size_t diff = curSize - _size;
117 Iterator it = --_keys.end(); //--keys can never be invoked on an empty list due to the minSize==1 requirement of LRU
118 std::size_t i = 0;
119
120 while (i++ < diff)
121 {
122 elemsToRemove.insert(*it);
123 if (it != _keys.begin())
124 {
125 --it;
126 }
127 }
128 }
129
130protected:
131 std::size_t _size; /// Number of keys the cache can store.
132 Keys _keys;
133 KeyIndex _keyIndex; /// For faster access to _keys
134};
135
136
137} // namespace Poco
138
139
140#endif // Foundation_LRUStrategy_INCLUDED
141