LRU缓存设计

缓存的数据结构采用哈希表，key到value的映射。网上有些资料采用记录数据的使用时刻实现LRU策略，此处采用双向链表实现LRU策略。LRU Least Recently Used，MRUMost Recently Used双向链表，lruPtr头指向最近最少使用的元素，mruPtr头指向最近最多使用的元素。LRUCache<int, int> tc（3）; //最大三个元素
tc.insert（1, 101）;
tc.insert（2, 102）;
tc.insert（3, 103）;最终存储结构如下图：哈希表中的元素：

黄色是 key域，哈希的键
蓝色是value域，存储的数据值
红色是newerPtr 域，指向下一个更新的 哈希项
绿色是oldPtr域，指向前一个更旧的 哈希项

LRUCache缓存中保存mruPtr和lruPtr，缓存的查找、更新元素首先从hash_table中发起，然后同步更新到双向链表中。 lru.hpp/*
* Implementation of an LRU cache with a maximum size.
*
* See http://code.google.com/p/lru-cache-cpp/ for usage and limitations.
*
* Licensed under the GNU LGPL: http://www.gnu.org/copyleft/lesser.html
*
* Pierre-Luc Brunelle, 2011
* pierre-luc.brunelle@polytml.ca
*
* 使用stl中的map替换hash_table
* Peteryfren China, 2012
*/#include <map>
#include <sstream>
#include <cassert>namespace lru{ //-------------------------------------------------------------
// Bucket
//------------------------------------------------------------- template<class K, class V>
struct LRUCacheH4Value
{
typedef std::pair<const K, LRUCacheH4Value<K, V> > Val; LRUCacheH4Value（）
: _v（）, _older（NULL）, _newer（NULL） { } LRUCacheH4Value（const V & v, Val * older, Val * newer）
: _v（v）, _older（older）, _newer（newer） { } V _v;
Val * _older;
Val * _newer;
};
//-------------------------------------------------------------
// Const Iterator
//------------------------------------------------------------- template<class K, class V>
class LRUCacheH4ConstIterator
{
public:
typedef std::pair<const K, LRUCacheH4Value<K, V> > Val;
typedef LRUCacheH4ConstIterator<K, V> const_iterator;
typedef Val & reference;
typedef Val * pointer; enum DIRECTION {
MRU_TO_LRU = 0,
LRU_TO_MRU
}; LRUCacheH4ConstIterator（const Val * ptr = NULL, DIRECTION dir = MRU_TO_LRU）; const_iterator & operator++（）;
const_iterator operator++（int）; bool operator==（const const_iterator & other）;
bool operator！=（const const_iterator & other）; const K & key（） const;
const V & value（） const; private:
const Val * _ptr;
DIRECTION _dir;
};
template<class K, class V>
LRUCacheH4ConstIterator<K, V>::LRUCacheH4ConstIterator（
const typename LRUCacheH4ConstIterator<K, V>::Val * ptr,
typename LRUCacheH4ConstIterator<K, V>::DIRECTION dir）
: _ptr（ptr）, _dir（dir）
{
}
template<class K, class V>
LRUCacheH4ConstIterator<K, V> & LRUCacheH4ConstIterator<K, V>::operator++（）
{
assert（_ptr）;
_ptr = （_dir == LRUCacheH4ConstIterator<K, V>::MRU_TO_LRU ？ _ptr->second._older : _ptr->second._newer）;
return *this;
}
template<class K, class V>
LRUCacheH4ConstIterator<K, V> LRUCacheH4ConstIterator<K, V>::operator++（int）
{
const_iterator ret = *this;
++*this;
return ret;
}
template<class K, class V>
bool LRUCacheH4ConstIterator<K, V>::operator==（const const_iterator & other）
{
return _ptr == other._ptr;
}
template<class K, class V>
bool LRUCacheH4ConstIterator<K, V>::operator！=（const const_iterator & other）
{
return _ptr ！= other._ptr;
}
template<class K, class V>
const K & LRUCacheH4ConstIterator<K, V>::key（） const
{
assert（_ptr）;
return _ptr->first;
}
template<class K, class V>
const V & LRUCacheH4ConstIterator<K, V>::value（） const
{
assert（_ptr）;
return _ptr->second._v;
}
} // file scope
namespace lru { //-------------------------------------------------------------
// LRU Cache
//------------------------------------------------------------- template<class K, class V>
class LRUCacheH4
{
public:
typedef LRUCacheH4ConstIterator<K, V> const_iterator; public:
LRUCacheH4（int maxsize）; // Pre-condition: maxsize >= 1
LRUCacheH4（const LRUCacheH4 & other）;
~LRUCacheH4（） { _map.clear（）; } V & operator[]（const K & key）;
void insert（const K & key, const V & value）; int size（） const;
int maxsize（） const;
bool empty（） const; const_iterator find（const K & key）; // updates the MRU
const_iterator find（const K & key） const; // does not update the MRU
const_iterator mru_begin（） const; // from MRU to LRU
const_iterator lru_begin（） const; // from LRU to MRU
const_iterator end（） const; void dump_mru_to_lru（std::ostream & os） const; private:
typedef std::pair<const K, LRUCacheH4Value<K, V> > Val; typedef std::map<K, LRUCacheH4Value<K,V> > MAP_TYPE; private:
Val * _update_or_insert（const K & key）;
Val * _update（typename MAP_TYPE::iterator it）;
Val * _insert（const K & key）; private:
MAP_TYPE _map;
Val * _mru;
Val * _lru;
int _maxsize;
};
// Reserve enough space to avoid resizing later on and thus invalidate iterators
template<class K, class V>
LRUCacheH4<K, V>::LRUCacheH4（int maxsize）
: _mru（NULL）,
_lru（NULL）,
_maxsize（maxsize）
{
if （_maxsize <= 0）
throw "LRUCacheH4: expecting cache size >= 1";
}
template<class K, class V>
LRUCacheH4<K, V>::LRUCacheH4（const LRUCacheH4<K, V> & other）
: _maxsize（other._maxsize）,
_mru（NULL）,
_lru（NULL）
{
for （const_iterator it = other.lru_begin（）; it ！= other.end（）; ++it）
this->insert（it.key（）, it.value（））;
}
template<class K, class V>
V & LRUCacheH4<K, V>::operator[]（const K & key）
{
return _update_or_insert（key）->second._v;
}
template<class K, class V>
void LRUCacheH4<K, V>::insert（const K & key, const V & value）
{
_update_or_insert（key）->second._v = value;
}
template<class K, class V>
int LRUCacheH4<K, V>::size（） const
{
return _map.size（）;
}
template<class K, class V>
int LRUCacheH4<K, V>::maxsize（） const
{
return _maxsize;
}
template<class K, class V>
bool LRUCacheH4<K, V>::empty（） const
{
return size（） > 0;
}
// updates MRU
template<class K, class V>
typename LRUCacheH4<K, V>::const_iterator LRUCacheH4<K, V>::find（const K & key）
{
typename MAP_TYPE::iterator it = _map.find（key）; if （it ！= _map.end（））
return const_iterator（_update（it）, const_iterator::MRU_TO_LRU）;
else
return end（）;
}
// does not update MRU
template<class K, class V>
typename LRUCacheH4<K, V>::const_iterator LRUCacheH4<K, V>::find（const K & key） const
{
typename MAP_TYPE::iterator it = _map.find（key）; if （it ！= _map.end（））
return const_iterator（&*it, const_iterator::MRU_TO_LRU）;
else
return end（）;
}
template<class K, class V>
void LRUCacheH4<K, V>::dump_mru_to_lru（std::ostream & os） const
{
os << "LRUCacheH4（" << size（） << "/" << maxsize（） << "）: MRU --> LRU: " << std::endl;
for （const_iterator it = mru_begin（）; it ！= end（）; ++it）
os << it.key（） << ": " << it.value（） << std::endl;
}
template<class K, class V>
typename LRUCacheH4<K, V>::const_iterator LRUCacheH4<K, V>::mru_begin（） const
{
return const_iterator（_mru, const_iterator::MRU_TO_LRU）;
}
template<class K, class V>
typename LRUCacheH4<K, V>::const_iterator LRUCacheH4<K, V>::lru_begin（） const
{
return const_iterator（_lru, const_iterator::LRU_TO_MRU）;
}
template<class K, class V>
typename LRUCacheH4<K, V>::const_iterator LRUCacheH4<K, V>::end（） const
{
return const_iterator（）;
}
template<class K, class V>
typename LRUCacheH4<K, V>::Val * LRUCacheH4<K, V>::_update_or_insert（const K & key）
{
typename MAP_TYPE::iterator it = _map.find（key）;
if （it ！= _map.end（））
return _update（it）;
else
return _insert（key）;
}
template<class K, class V>
typename LRUCacheH4<K, V>::Val * LRUCacheH4<K, V>::_update（typename MAP_TYPE::iterator it）
{
LRUCacheH4Value<K, V> & v = it->second;
Val * older = v._older;
Val * newer = v._newer;
Val * moved = &*it; // possibly update the LRU
if （moved == _lru && _lru->second._newer）
_lru = _lru->second._newer; if （moved ！= _mru） {
// "remove" key from current position
if （older）
older->second._newer = newer;
if （newer）
newer->second._older = older; // "insert" key to MRU position
v._older = _mru;
v._newer = NULL;
_mru->second._newer = moved;
_mru = moved;
} return moved;
}
template<class K, class V>
typename LRUCacheH4<K, V>::Val * LRUCacheH4<K, V>::_insert（const K & key）
{
// if we have grown too large, remove LRU
if （_map.size（） >= _maxsize） {
Val * old_lru = _lru;
if （_lru->second._newer） {
_lru = _lru->second._newer;
_lru->second._older = NULL;
}
_map.erase（old_lru->first）;
} // insert key to MRU position
std::pair<typename MAP_TYPE::iterator, bool> ret
= _map.insert（ Val（key, LRUCacheH4Value<K, V>（V（）, _mru, NULL）））; Val * inserted = &*ret.first;
if （_mru）
_mru->second._newer = inserted;
_mru = inserted; // possibly update the LRU
if （！_lru）
_lru = _mru;
else if （！_lru->second._newer）
_lru->second._newer = _mru; return inserted;
}
} // namespace lru测试代码：#include <iostream>#include "lru.hpp"using namespace lru;
using namespace std;int main（）
{
typedef LRUCacheH4<int, int> CacheType; CacheType tc（3）; tc.insert（1, 101）;
tc.insert（2, 102）;
tc.insert（3, 103）;

tc.insert（2, 1002）; cout << tc[1] << endl; cout << "================" << endl; for （CacheType::const_iterator it = tc.mru_begin（）; it ！= tc.end（）; ++it）
cout << it.key（） << " " << it.value（） << endl; cout << "================" << endl; for （CacheType::const_iterator it = tc.lru_begin（）; it ！= tc.end（）; ++it）
cout << it.key（） << " " << it.value（） << endl; system（"PAUSE"）;
return 0;
}