gistfile1.hpp

#ifndef LRU_CACHE_HPP_
#define LRU_CACHE_HPP_

#include <cstddef>
#include <ctime>
#include <map>
#include <list>
#include <vector>
#include <stdint.h>

template <class K, class V>
class lru_cache {
public: // typedefs
    typedef K key_type;
    typedef V data_type;
    typedef std::pair<K, V> value_type;
public:
    typedef std::list<value_type> cache_list;
    typedef typename cache_list::iterator cache_iterator;
    typedef typename cache_list::const_iterator const_cache_iterator;
public:
    typedef std::vector<key_type> key_list;
    typedef typename key_list::iterator key_iterator;
    typedef typename key_list::const_iterator const_key_iterator;
public:
    typedef std::map<key_type, cache_iterator> index_map;
    typedef std::pair<key_type, cache_iterator> index_pair;
    typedef typename index_map::iterator index_iterator;
    typedef typename index_map::const_iterator const_index_iterator;
private: // data members
    std::size_t maxsize_;
    std::size_t cursize_;
    cache_list cache_;
    index_map index_;
public: // construction
    lru_cache(std::size_t maxsize) :
        maxsize_(maxsize),
        cursize_(0)
    {}
public: // api 
    inline const std::size_t count() const { return cache_.size(); }
    
    inline const std::size_t max_size() const { return maxsize_; }
    
    inline const std::size_t cur_size() const { return cursize_; }
    
    inline bool exists(const key_type& k) const { 
        return index_.find(k) != index_.end;
    }
    
    inline void remove(const key_type& k) {
        index_iterator it = index_.find(k);
        if (it == index_.end()) return;
        cursize_ -= lru_item_size(it->second->second);
        cache_.erase(it->second);
        index_.erase(it);
        lru_destroy(it->second->second);
    }
    
    inline void hit(const key_type& k) {
        index_iterator it = index_.find(k);
        if (it == index_.end()) return;
        cache_.splice(cache_.begin(), cache_, it->second);
    }
    
    inline data_type *fetch_pointer(const key_type& k) {
        index_iterator it = index_.find(k);
        if (it == index_.end()) return 0;
        hit(k);
        return &(it->second->second);
    }
    
    inline data_type fetch(const key_type& k) {
        index_iterator it = index_.find(k);
        if (it == index_.end()) return data_type();
        data_type tmp = it->second->second;
        hit(k);
        return tmp;
    }
    
    inline void insert(key_type k, data_type d) {
        hit(k);
        cursize_ += lru_item_size(d);
        index_iterator iit = index_.find(k);
        if (iit != index_.end()) {
            cache_.erase(iit->second);
            index_.erase(iit);
        }
        cache_.push_front(std::make_pair(k, d));
        cache_iterator cit = cache_.begin();
        index_.insert(std::make_pair(k, cit));
        while (cursize_ > maxsize_) {
            cit = cache_.end();
            --cit;
            remove(cit->first);
        }
    }
    
    inline const key_list get_keys() { 
        key_list r;
        for (const_cache_iterator cit=cache_.begin();
             cit!=cache_.end();cit++) {
            r.push_back(cit->first);
        }
        return r;
    }
private: // noncopyable
    lru_cache( const lru_cache& );
    const lru_cache& operator=( const lru_cache& );
};

#endif // include guard