Point Cloud Library (PCL)
1.7.0
|
00001 00002 #ifndef __PCL_OUTOFCORE_LRU_CACHE__ 00003 #define __PCL_OUTOFCORE_LRU_CACHE__ 00004 00005 #include <cassert> 00006 #include <list> 00007 00008 template<typename T> 00009 class LRUCacheItem 00010 { 00011 public: 00012 00013 virtual size_t 00014 sizeOf () const 00015 { 00016 return sizeof (item); 00017 } 00018 00019 virtual 00020 ~LRUCacheItem () { } 00021 00022 T item; 00023 size_t timestamp; 00024 }; 00025 00026 template<typename KeyT, typename CacheItemT> 00027 class LRUCache 00028 { 00029 public: 00030 00031 typedef std::list<KeyT> KeyIndex; 00032 typedef typename KeyIndex::iterator KeyIndexIterator; 00033 00034 typedef std::map<KeyT, std::pair<CacheItemT, typename KeyIndex::iterator> > Cache; 00035 typedef typename Cache::iterator CacheIterator; 00036 00037 LRUCache (size_t c) : 00038 capacity_ (c), size_ (0) 00039 { 00040 assert(capacity_ != 0); 00041 } 00042 00043 bool 00044 hasKey (const KeyT& k) 00045 { 00046 return (cache_.find (k) != cache_.end ()); 00047 } 00048 00049 CacheItemT& 00050 get (const KeyT& k) 00051 { 00052 // Get existing key 00053 const CacheIterator it = cache_.find (k); 00054 assert(it != cache_.end ()); 00055 00056 // Move key to MRU key index 00057 key_index_.splice (key_index_.end (), key_index_, (*it).second.second); 00058 00059 // Return the retrieved item 00060 return it->second.first; 00061 } 00062 00063 void 00064 touch (const KeyT& key) 00065 { 00066 // Get existing key 00067 const CacheIterator it = cache_.find (key); 00068 assert(it != cache_.end ()); 00069 00070 // Move key to MRU key index 00071 key_index_.splice (key_index_.end (), key_index_, it->second.second); 00072 } 00073 00074 // Record a fresh key-value pair in the cache 00075 bool 00076 insert (const KeyT& key, const CacheItemT& value) 00077 { 00078 if (cache_.find (key) != cache_.end ()) 00079 { 00080 touch (key); 00081 return true; 00082 } 00083 00084 size_t size = size_; 00085 size_t item_size = value.sizeOf (); 00086 int evict_count = 0; 00087 00088 // Get LRU key iterator 00089 KeyIndexIterator key_it = key_index_.begin (); 00090 00091 while (size + item_size >= capacity_) 00092 { 00093 const CacheIterator cache_it = cache_.find (*key_it); 00094 00095 // Get tail item (Least Recently Used) 00096 size_t tail_timestamp = cache_it->second.first.timestamp; 00097 size_t tail_size = cache_it->second.first.sizeOf (); 00098 00099 // Check timestamp to see if we've completely filled the cache in one go 00100 if (value.timestamp == tail_timestamp) 00101 { 00102 return false; 00103 } 00104 00105 size -= tail_size; 00106 key_it++; 00107 evict_count++; 00108 } 00109 00110 // Evict enough items to make room for the new item 00111 evict (evict_count); 00112 00113 size_ += item_size; 00114 00115 // Insert most-recently-used key at the end of our key index 00116 KeyIndexIterator it = key_index_.insert (key_index_.end (), key); 00117 00118 // Add to cache 00119 cache_.insert (std::make_pair (key, std::make_pair (value, it))); 00120 00121 return true; 00122 } 00123 00124 void 00125 setCapacity (size_t capacity) 00126 { 00127 capacity_ = capacity; 00128 } 00129 00130 CacheItemT& 00131 tailItem () 00132 { 00133 const CacheIterator it = cache_.find (key_index_.front ()); 00134 return it->second.first; 00135 } 00136 00137 size_t 00138 sizeOf (const CacheItemT& value) 00139 { 00140 return value.sizeOf (); 00141 } 00142 00143 // Evict the least-recently-used item from the cache 00144 bool 00145 evict (int item_count=1) 00146 { 00147 for (int i=0; i < item_count; i++) 00148 { 00149 if (key_index_.empty ()) 00150 return false; 00151 00152 // Get LRU item 00153 const CacheIterator it = cache_.find (key_index_.front ()); 00154 assert(it != cache_.end()); 00155 00156 // Remove LRU item from cache and key index 00157 size_ -= it->second.first.sizeOf (); 00158 cache_.erase (it); 00159 key_index_.pop_front (); 00160 } 00161 00162 return true; 00163 } 00164 00165 // Cache capacity in kilobytes 00166 size_t capacity_; 00167 00168 // Current cache size in kilobytes 00169 size_t size_; 00170 00171 // LRU key index LRU[0] ... MRU[N] 00172 KeyIndex key_index_; 00173 00174 // LRU cache 00175 Cache cache_; 00176 }; 00177 00178 #endif //__PCL_OUTOFCORE_LRU_CACHE__