00001
00002 #pragma once
00003 #include <vector>
00004 #include <map>
00005 #include <algorithm>
00006 #include <boost/shared_ptr.hpp>
00007 #include <boost/thread.hpp>
00008 #include <sys/time.h>
00009
00010
00011 #ifndef SPTR
00012 #define SPTR boost::shared_ptr
00013 #endif
00014
00015 namespace lru_cache
00016 {
00017
00018 template<typename KEY, typename VAL>
00019 class LRU_Cache
00020 {
00021 public:
00022 typedef boost::unordered_map<KEY,uint32_t> map_t;
00023 private:
00024 struct Record
00025 {
00026 uint32_t prev,next;
00027 KEY key;
00028
00029 typename boost::shared_ptr<VAL> ptr;
00030 };
00031
00032 mutable boost::shared_mutex m_lock;
00033 uint32_t m_qfront, m_qback;
00034 std::vector<Record> m_recs;
00035 map_t m_idx;
00036
00037 void
00038 update_queue(KEY const& key, uint32_t const p)
00039 {
00040
00041
00042
00043
00044 Record& r = m_recs[p];
00045 if (m_recs.size() == 1)
00046 r.next = r.prev = m_qback = m_qfront = 0;
00047
00048 if (r.key != key || p == m_qback) return;
00049
00050 if (m_qfront == p)
00051 m_qfront = m_recs[r.next].prev = r.next;
00052 else
00053 {
00054 m_recs[r.prev].next = r.next;
00055 m_recs[r.next].prev = r.prev;
00056 }
00057 r.prev = m_qback;
00058 m_recs[r.prev].next = m_qback = r.next = p;
00059 }
00060
00061 public:
00062 LRU_Cache(size_t capacity=1) : m_qfront(0), m_qback(0) { reserve(capacity); }
00063 size_t capacity() const { return m_recs.capacity(); }
00064 size_t size() const { return m_idx.size(); }
00065 void reserve(size_t s) { m_recs.reserve(s); }
00066
00067 SPTR<VAL>
00068 get(KEY const& key)
00069 {
00070 uint32_t p;
00071 {
00072 boost::shared_lock<boost::shared_mutex> rlock(m_lock);
00073 typename map_t::const_iterator i = m_idx.find(key);
00074 if (i == m_idx.end()) return SPTR<VAL>();
00075 p = i->second;
00076 }
00077 boost::lock_guard<boost::shared_mutex> guard(m_lock);
00078 update_queue(key,p);
00079 return m_recs[p].ptr;
00080 }
00081
00082 void
00083 set(KEY const& key, SPTR<VAL> const& ptr)
00084 {
00085 boost::lock_guard<boost::shared_mutex> lock(m_lock);
00086 std::pair<typename map_t::iterator,bool> foo;
00087 foo = m_idx.insert(make_pair(key,m_recs.size()));
00088 uint32_t p = foo.first->second;
00089 if (foo.second)
00090 {
00091 if (m_recs.size() < m_recs.capacity())
00092 m_recs.push_back(Record());
00093 else
00094 {
00095 foo.first->second = p = m_qfront;
00096 m_idx.erase(m_recs[p].key);
00097 }
00098 m_recs[p].key = key;
00099 }
00100 update_queue(key,p);
00101 m_recs[p].ptr = ptr;
00102 }
00103 };
00104 }