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