123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139 |
- #ifndef BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP
- #define BOOST_COMPUTE_DETAIL_LRU_CACHE_HPP
- #include <map>
- #include <list>
- #include <utility>
- #include <boost/optional.hpp>
- namespace boost {
- namespace compute {
- namespace detail {
- template<class Key, class Value>
- class lru_cache
- {
- public:
- typedef Key key_type;
- typedef Value value_type;
- typedef std::list<key_type> list_type;
- typedef std::map<
- key_type,
- std::pair<value_type, typename list_type::iterator>
- > map_type;
- lru_cache(size_t capacity)
- : m_capacity(capacity)
- {
- }
- ~lru_cache()
- {
- }
- size_t size() const
- {
- return m_map.size();
- }
- size_t capacity() const
- {
- return m_capacity;
- }
- bool empty() const
- {
- return m_map.empty();
- }
- bool contains(const key_type &key)
- {
- return m_map.find(key) != m_map.end();
- }
- void insert(const key_type &key, const value_type &value)
- {
- typename map_type::iterator i = m_map.find(key);
- if(i == m_map.end()){
-
- if(size() >= m_capacity){
-
- evict();
- }
-
- m_list.push_front(key);
- m_map[key] = std::make_pair(value, m_list.begin());
- }
- }
- boost::optional<value_type> get(const key_type &key)
- {
-
- typename map_type::iterator i = m_map.find(key);
- if(i == m_map.end()){
-
- return boost::none;
- }
-
-
- typename list_type::iterator j = i->second.second;
- if(j != m_list.begin()){
-
- m_list.erase(j);
- m_list.push_front(key);
-
- j = m_list.begin();
- const value_type &value = i->second.first;
- m_map[key] = std::make_pair(value, j);
-
- return value;
- }
- else {
-
-
- return i->second.first;
- }
- }
- void clear()
- {
- m_map.clear();
- m_list.clear();
- }
- private:
- void evict()
- {
-
- typename list_type::iterator i = --m_list.end();
- m_map.erase(*i);
- m_list.erase(i);
- }
- private:
- map_type m_map;
- list_type m_list;
- size_t m_capacity;
- };
- }
- }
- }
- #endif
|