http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
之前在网上看到过网友的一个C++实现，感觉不错，所以核心代码就采用了他的设计。
原作者通过两个MAP对象来记录缓存数据和LRU队列，注意其中的LRU队列并不是按照常用的方式使用LIST链表，而是使用MAP来代替LIST，有关这一点原作者已做了说明。
另外还有人将MRU与LRU组合在一起使用，当然如果清楚了设计原理，那么就很容易理解了。
考虑到缓存实现多数使用单例模式，这里使用C++的模版方式设计了一个Singlton基类，这样以后只要继承该类，子类就会支持单例模式了。其代码如下：
代码如下:
//
// SingltonT.h
//
#ifndef SingltonT_h
#define SingltonT_h
#include
#include
using namespace std;
using namespace std::tr1;
template
class Singlton {
public:
static T* instance();
void print() {
cout read,1);
if (lock->write) {//当已是写锁时，则去掉读锁记数器
__sync_sub_and_fetch(&lock->read,1);
} else {
break;
}
}
}
static inline void
rwlock_wlock(struct rwlock *lock) {
__sync_lock_test_and_set(&lock->write,1);
while(lock->read) {
//http://blog.itmem.com/?m=201204
//http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/Atomic-Builtins.html
__sync_synchronize();//很重要，如果去掉，g++ -O3 优化编译后的生成的程序会产生死锁
}
}
static inline void
rwlock_wunlock(struct rwlock *lock) {
__sync_lock_release(&lock->write);
}
static inline void
rwlock_runlock(struct rwlock *lock) {
__sync_sub_and_fetch(&lock->read,1);
}
这里并未使用pthread_mutex_t来设计锁，而是使用了__sync_fetch_and_add指令体系，当然最终是否如上面链接中作者所说的比pthread_mutex_t性能要高7-8倍，我没测试过，感兴趣的朋友也可以帮助测试一下。
有了这两个类之后，我又补充了原文作者中所提到了KEY比较方法的定义，同时引入了id来支持object-c的对象缓存，最终代码修改如下：
代码如下:
#ifndef _MAP_LRU_CACHE_H_
#define _MAP_LRU_CACHE_H_
#include
#include
#include "rwlock.h"
#include
#include
using namespace std;
namespace lru_cache {
static const int DEF_CAPACITY = 100000;//默认缓存记录数
typedef unsigned long long virtual_time;
typedef struct _HashKey
{
NSString* key;
}HashKey;
typedef struct _HashValue
{
id value_;
virtual_time access_;
}HashValue;
//仅针对HashKey比较器
template
struct hashkey_compare{
bool operator()(key_t x, key_t y) const{
return x < y;
}
};
template
struct hashkey_compare
{
bool operator()(HashKey __x, HashKey __y) const{
string x = [__x.key UTF8String];
string y = [__y.key UTF8String];
return x < y;
}
};
//自定义map类型
template
class lru_map: public map{};
class CLRUCache
{
public:
CLRUCache() : _now(0){
_lru_list = shared_ptr(new lru_map);
_hash_table = shared_ptr (new lru_map);
}
~CLRUCache(){
_lru_list->clear();
_hash_table->clear();
}
int set( const HashKey& key, const id &value )
{
HashValue hash_value;
hash_value.value_ = value;
hash_value.access_ = get_virtual_time();
pair< map::iterator, bool > ret = _hash_table->insert(make_pair(key, hash_value));
if ( !ret.second ){
// key already exist
virtual_time old_access = (*_hash_table)[key].access_;
map::iterator iter = _lru_list->find(old_access);
if(iter != _lru_list->end())
{
_lru_list->erase(iter);
}
_lru_list->insert(make_pair(hash_value.access_, key));
(*_hash_table)[key] = hash_value;
}
else {
_lru_list->insert(make_pair(hash_value.access_, key));
if ( _hash_table->size() > DEF_CAPACITY )
{
// get the least recently used key
map::iterator iter = _lru_list->begin();
_hash_table->erase( iter->second );
// remove last key from list
_lru_list->erase(iter);
}
}
return 0;
}
HashValue* get( const HashKey& key )
{
map::iterator iter = _hash_table->find(key);
if ( iter != _hash_table->end() )
{
virtual_time old_access = iter->second.access_;
iter->second.access_ = get_virtual_time();
//调整当前key在LRU列表中的位置
map::iterator it = _lru_list->find(old_access);
if(it != _lru_list->end()) {
_lru_list->erase(it);
}
_lru_list->insert(make_pair(iter->second.access_, key));
return &(iter->second);
}
else{
return NULL;
}
}
unsigned get_lru_list_size(){ return (unsigned)_lru_list->size(); }
unsigned get_hash_table_size() { return (unsigned)_hash_table->size(); }
virtual_time get_now() { return _now; }
private:
virtual_time get_virtual_time()
{
return ++_now;
}
shared_ptr _lru_list;
shared_ptr _hash_table;
virtual_time _now;
};
#endif
接下来看一下如果结合单例和rwlock来设计最终的缓存功能，如下：
代码如下:
using namespace lru_cache;
class DZCache: public Singlton
{
friend class Singlton;
private:
shared_ptr clu_cache;
rwlock *lock;
DZCache(){
lock =(rwlock*) malloc(sizeof(rwlock));
rwlock_init(lock);
clu_cache = shared_ptr(new CLRUCache());
cout get(hash_key);
if(value == NULL){
return nil;
}
else{
return value->value_;
}
}
};
#endif
最后看一下如何使用：
代码如下:
void testLRUCache(){
//指针方式
DZCache::instance()->set(@"name", @"daizhj");//设置
NSString* name = (NSString*)DZCache::instance()->get(@"name");//获取
std::cout