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>
12 class LRUCacheItem
13 {
14 public:
15 
16   virtual std::size_t
sizeOf() const17   sizeOf () const
18   {
19     return sizeof (item);
20   }
21 
22   virtual
~LRUCacheItem()23   ~LRUCacheItem () { }
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 
LRUCache(std::size_t c)40   LRUCache (std::size_t c) :
41       capacity_ (c), size_ (0)
42   {
43     assert(capacity_ != 0);
44   }
45 
46   bool
hasKey(const KeyT & k)47   hasKey (const KeyT& k)
48   {
49     return (cache_.find (k) != cache_.end ());
50   }
51 
52   CacheItemT&
get(const KeyT & k)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
touch(const KeyT & key)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
insert(const KeyT & key,const CacheItemT & value)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
setCapacity(std::size_t capacity)128   setCapacity (std::size_t capacity)
129   {
130     capacity_ = capacity;
131   }
132 
133   CacheItemT&
tailItem()134   tailItem ()
135   {
136     const CacheIterator it = cache_.find (key_index_.front ());
137     return it->second.first;
138   }
139 
140   std::size_t
sizeOf(const CacheItemT & value)141   sizeOf (const CacheItemT& value)
142   {
143     return value.sizeOf ();
144   }
145 
146   // Evict the least-recently-used item from the cache
147   bool
evict(int item_count=1)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]
175   KeyIndex key_index_;
176 
177   // LRU cache
178   Cache cache_;
179 };
180 
181 #endif //__PCL_OUTOFCORE_LRU_CACHE__
182