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
#ifndef PCAPPP_LRU_LIST
#define PCAPPP_LRU_LIST
#include <map>
#include <list>
#if __cplusplus > 199711L || _MSC_VER >= 1800
#include <utility>
#endif
/// @file
/**
* \namespace pcpp
* \brief The main namespace for the PcapPlusPlus lib
*/
namespace pcpp
{
/**
* @class LRUList
* A template class that implements a LRU cache with limited size. Each time the user puts an element it goes to head of the
* list as the most recently used element (if the element was already in the list it advances to the head of the list).
* The last element in the list is the one least recently used and will be pulled out of the list if it reaches its max size
* and a new element comes in. All actions on this LRU list are O(1)
*/
template<typename T>
class LRUList
{
public:
typedef typename std::list<T>::iterator ListIterator;
typedef typename std::map<T, ListIterator>::iterator MapIterator;
/**
* A c'tor for this class
* @param[in] maxSize The max size this list can go
*/
explicit LRUList(size_t maxSize)
{
m_MaxSize = maxSize;
}
/**
* Puts an element in the list. This element will be inserted (or advanced if it already exists) to the head of the
* list as the most recently used element. If the list already reached its max size and the element is new this method
* will remove the least recently used element and return a value in deletedValue. Method complexity is O(log(getSize())).
* This is a optimized version of the method T* put(const T&).
* @param[in] element The element to insert or to advance to the head of the list (if already exists)
* @param[out] deletedValue The value of deleted element if a pointer is not NULL. This parameter is optional.
* @return 0 if the list didn't reach its max size, 1 otherwise. In case the list already reached its max size
* and deletedValue is not NULL the value of deleted element is copied into the place the deletedValue points to.
*/
int put(const T& element, T* deletedValue = NULL)
{
m_CacheItemsList.push_front(element);
// Inserting a new element. If an element with an equivalent key already exists the method returns an iterator to the element that prevented the insertion
std::pair<MapIterator, bool> pair = m_CacheItemsMap.insert(std::make_pair(element, m_CacheItemsList.begin()));
if (pair.second == false) // already exists
{
m_CacheItemsList.erase(pair.first->second);
pair.first->second = m_CacheItemsList.begin();
}
if (m_CacheItemsMap.size() > m_MaxSize)
{
ListIterator lruIter = m_CacheItemsList.end();
lruIter--;
if (deletedValue != NULL)
#if __cplusplus > 199711L || _MSC_VER >= 1800
*deletedValue = std::move(*lruIter);
#else
*deletedValue = *lruIter;
#endif
m_CacheItemsMap.erase(*lruIter);
m_CacheItemsList.erase(lruIter);
return 1;
}
return 0;
}
/**
* Get the most recently used element (the one at the beginning of the list)
* @return The most recently used element
*/
const T& getMRUElement() const
{
return m_CacheItemsList.front();
}
/**
* Get the least recently used element (the one at the end of the list)
* @return The least recently used element
*/
const T& getLRUElement() const
{
return m_CacheItemsList.back();
}
/**
* Erase an element from the list. If element isn't found in the list nothing happens
* @param[in] element The element to erase
*/
void eraseElement(const T& element)
{
MapIterator iter = m_CacheItemsMap.find(element);
if (iter == m_CacheItemsMap.end())
return;
m_CacheItemsList.erase(iter->second);
m_CacheItemsMap.erase(iter);
}
/**
* @return The max size of this list as determined in the c'tor
*/
size_t getMaxSize() const { return m_MaxSize; }
/**
* @return The number of elements currently in this list
*/
size_t getSize() const { return m_CacheItemsMap.size(); }
private:
std::list<T> m_CacheItemsList;
std::map<T, ListIterator> m_CacheItemsMap;
size_t m_MaxSize;
};
} // namespace pcpp
#endif /* PCAPPP_LRU_LIST */