Point Cloud Library (PCL) 1.12.0
Loading...
Searching...
No Matches
lru_cache.hpp
1
2#ifndef __PCL_OUTOFCORE_LRU_CACHE__
3#define __PCL_OUTOFCORE_LRU_CACHE__
4
5#include <cstddef>
6#include <cassert>
7#include <list>
8#include <map>
9#include <utility>
10
11template<typename T>
13{
14public:
15
16 virtual std::size_t
17 sizeOf () const
18 {
19 return sizeof (item);
20 }
21
22 virtual
24
26 std::size_t timestamp;
27};
28
29template<typename KeyT, typename CacheItemT>
31{
32public:
33
34 using KeyIndex = std::list<KeyT>;
35 using KeyIndexIterator = typename KeyIndex::iterator;
36
37 using Cache = std::map<KeyT, std::pair<CacheItemT, typename KeyIndex::iterator> >;
38 using CacheIterator = typename Cache::iterator;
39
40 LRUCache (std::size_t c) :
41 capacity_ (c), size_ (0)
42 {
43 assert(capacity_ != 0);
44 }
45
46 bool
47 hasKey (const KeyT& k)
48 {
49 return (cache_.find (k) != cache_.end ());
50 }
51
52 CacheItemT&
53 get (const KeyT& k)
54 {
55 // Get existing key
56 const CacheIterator it = cache_.find (k);
57 assert(it != cache_.end ());
58
59 // Move key to MRU key index
60 key_index_.splice (key_index_.end (), key_index_, (*it).second.second);
61
62 // Return the retrieved item
63 return it->second.first;
64 }
65
66 void
67 touch (const KeyT& key)
68 {
69 // Get existing key
70 const CacheIterator it = cache_.find (key);
71 assert(it != cache_.end ());
72
73 // Move key to MRU key index
74 key_index_.splice (key_index_.end (), key_index_, it->second.second);
75 }
76
77 // Record a fresh key-value pair in the cache
78 bool
79 insert (const KeyT& key, const CacheItemT& value)
80 {
81 if (cache_.find (key) != cache_.end ())
82 {
83 touch (key);
84 return true;
85 }
86
87 std::size_t size = size_;
88 std::size_t item_size = value.sizeOf ();
89 int evict_count = 0;
90
91 // Get LRU key iterator
92 KeyIndexIterator key_it = key_index_.begin ();
93
94 while (size + item_size >= capacity_)
95 {
96 const CacheIterator cache_it = cache_.find (*key_it);
97
98 // Get tail item (Least Recently Used)
99 std::size_t tail_timestamp = cache_it->second.first.timestamp;
100 std::size_t tail_size = cache_it->second.first.sizeOf ();
101
102 // Check timestamp to see if we've completely filled the cache in one go
103 if (value.timestamp == tail_timestamp)
104 {
105 return false;
106 }
107
108 size -= tail_size;
109 ++key_it;
110 ++evict_count;
111 }
112
113 // Evict enough items to make room for the new item
114 evict (evict_count);
115
116 size_ += item_size;
117
118 // Insert most-recently-used key at the end of our key index
119 KeyIndexIterator it = key_index_.insert (key_index_.end (), key);
120
121 // Add to cache
122 cache_.insert (std::make_pair (key, std::make_pair (value, it)));
123
124 return true;
125 }
126
127 void
128 setCapacity (std::size_t capacity)
129 {
130 capacity_ = capacity;
131 }
132
133 CacheItemT&
135 {
136 const CacheIterator it = cache_.find (key_index_.front ());
137 return it->second.first;
138 }
139
140 std::size_t
141 sizeOf (const CacheItemT& value)
142 {
143 return value.sizeOf ();
144 }
145
146 // Evict the least-recently-used item from the cache
147 bool
148 evict (int item_count=1)
149 {
150 for (int i=0; i < item_count; i++)
151 {
152 if (key_index_.empty ())
153 return false;
154
155 // Get LRU item
156 const CacheIterator it = cache_.find (key_index_.front ());
157 assert(it != cache_.end());
158
159 // Remove LRU item from cache and key index
160 size_ -= it->second.first.sizeOf ();
161 cache_.erase (it);
162 key_index_.pop_front ();
163 }
164
165 return true;
166 }
167
168 // Cache capacity in kilobytes
169 std::size_t capacity_;
170
171 // Current cache size in kilobytes
172 std::size_t size_;
173
174 // LRU key index LRU[0] ... MRU[N]
176
177 // LRU cache
179};
180
181#endif //__PCL_OUTOFCORE_LRU_CACHE__
bool insert(const KeyT &key, const CacheItemT &value)
Definition lru_cache.hpp:79
std::list< KeyT > KeyIndex
Definition lru_cache.hpp:34
bool hasKey(const KeyT &k)
Definition lru_cache.hpp:47
std::size_t capacity_
CacheItemT & get(const KeyT &k)
Definition lru_cache.hpp:53
void touch(const KeyT &key)
Definition lru_cache.hpp:67
void setCapacity(std::size_t capacity)
KeyIndex key_index_
std::map< KeyT, std::pair< CacheItemT, typename KeyIndex::iterator > > Cache
Definition lru_cache.hpp:37
typename KeyIndex::iterator KeyIndexIterator
Definition lru_cache.hpp:35
std::size_t size_
LRUCache(std::size_t c)
Definition lru_cache.hpp:40
std::size_t sizeOf(const CacheItemT &value)
bool evict(int item_count=1)
typename Cache::iterator CacheIterator
Definition lru_cache.hpp:38
Cache cache_
CacheItemT & tailItem()
virtual ~LRUCacheItem()
Definition lru_cache.hpp:23
std::size_t timestamp
Definition lru_cache.hpp:26
virtual std::size_t sizeOf() const
Definition lru_cache.hpp:17