手机版
你好,游客 登录 注册
背景:
阅读新闻

LRU缓存设计

[日期:2014-03-25] 来源:Linux社区  作者:ryfdizuo [字体: ]

缓存的数据结构采用哈希表,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;
}

linux
相关资讯       LRU缓存  LRU 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款