// Least recently used
//
// Simplified code as example for the least recently used algorithm.
//
// by feyd//godX.de
#include <vector>
#include <list>
#include <string>
#include <stdio.h>
#include <cstdint>
template<class _TYPE>
class CLRUContainer;
template<class _TYPE>
class CLRUElement : public _TYPE
{
public:
CLRUElement(CLRUContainer<CLRUElement<_TYPE> >& container) : m_container(container) { m_container.Register(this); }
virtual ~CLRUElement() { m_container.Unregister(this); }
void Use()
{
m_container.MoveToFront(this);
}
virtual void Unuse()
{
delete this;
}
typename std::list<CLRUElement<_TYPE>* >::iterator GetIterator() const
{
return m_iterator;
}
void SetIterator(typename std::list<CLRUElement<_TYPE>* >::iterator iterator)
{
m_iterator = iterator;
}
private:
CLRUContainer<CLRUElement<_TYPE> >& m_container;
typename std::list<CLRUElement<_TYPE>* >::iterator m_iterator;
};
// Base class
template<class _TYPE>
class CLRUContainer : public std::list<_TYPE*>
{
public:
CLRUContainer(size_t nSize) : m_nSize(nSize) {}
virtual ~CLRUContainer()
{
while(std::list<_TYPE*>::size()>0)
(*std::list<_TYPE*>::begin())->Unuse();
}
void Register(_TYPE* pElement)
{
if(std::list<_TYPE*>::size()>=m_nSize)
(*std::list<_TYPE*>::rbegin())->Unuse();
std::list<_TYPE*>::push_front(pElement);
pElement->SetIterator(std::list<_TYPE*>::begin());
}
void Unregister(_TYPE* pElement)
{
std::list<_TYPE*>::erase(pElement->GetIterator());
}
void MoveToFront(_TYPE* pElement)
{
// TODO: Just unlink and relink the list field for speed
Unregister(pElement);
Register(pElement);
}
private:
size_t m_nSize;
};
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
printf("LRU test...\r\n\r\n");
{
CLRUContainer<CLRUElement<std::string> > container(5);
// Find or add elements
for(int n=1; n<argc; n++)
{
CLRUElement<std::string>* pString = nullptr;
for(auto it=container.begin(); it!=container.end(); ++it)
if((**it).compare(argv[n])==0)
pString = (*it);
if(!pString)
pString = new CLRUElement<std::string>(container);
pString->assign(argv[n]);
pString->Use();
}
printf(" %d elements:\r\n", (int)container.size());
int n = 0;
for(auto it=container.begin(); it!=container.end(); ++it, n++)
printf(" %d. %s\r\n", (int)n+1, (**it).c_str());
printf("\r\n");
}
}
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