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
* [email protected]
*
* 使用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;
}