Point Cloud Library (PCL)  1.14.1-dev
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 
11 template<typename T>
13 {
14 public:
15 
16  virtual std::size_t
17  sizeOf () const
18  {
19  return sizeof (item);
20  }
21 
22  virtual
23  ~LRUCacheItem () = default;
24 
25  T item;
26  std::size_t timestamp;
27 };
28 
29 template<typename KeyT, typename CacheItemT>
30 class LRUCache
31 {
32 public:
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)
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  auto 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  auto 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_{0};
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_
Definition: lru_cache.hpp:169
void touch(const KeyT &key)
Definition: lru_cache.hpp:67
void setCapacity(std::size_t capacity)
Definition: lru_cache.hpp:128
KeyIndex key_index_
Definition: lru_cache.hpp:175
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_
Definition: lru_cache.hpp:172
LRUCache(std::size_t c)
Definition: lru_cache.hpp:40
std::size_t sizeOf(const CacheItemT &value)
Definition: lru_cache.hpp:141
CacheItemT & get(const KeyT &k)
Definition: lru_cache.hpp:53
CacheItemT & tailItem()
Definition: lru_cache.hpp:134
bool evict(int item_count=1)
Definition: lru_cache.hpp:148
typename Cache::iterator CacheIterator
Definition: lru_cache.hpp:38
Cache cache_
Definition: lru_cache.hpp:178
virtual ~LRUCacheItem()=default
std::size_t timestamp
Definition: lru_cache.hpp:26
virtual std::size_t sizeOf() const
Definition: lru_cache.hpp:17