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