C++开发在IOS环境下运行的LRUCache缓存功能
2023-06-13 09:14:40 时间
本文着重介绍如何在XCODE中，通过C++开发在IOS环境下运行的缓存功能。算法基于LRU（最近最少使用）。有关lru详见：
http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
之前在网上看到过网友的一个C++实现，感觉不错，所以核心代码就采用了他的设计。
原作者通过两个MAP对象来记录缓存数据和LRU队列，注意其中的LRU队列并不是按照常用的方式使用LIST链表，而是使用MAP来代替LIST，有关这一点原作者已做了说明。
另外还有人将MRU与LRU组合在一起使用，当然如果清楚了设计原理，那么就很容易理解了。
考虑到缓存实现多数使用单例模式，这里使用C++的模版方式设计了一个Singlton基类，这样以后只要继承该类，子类就会支持单例模式了。其代码如下：
复制代码代码如下:
http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
之前在网上看到过网友的一个C++实现，感觉不错，所以核心代码就采用了他的设计。
原作者通过两个MAP对象来记录缓存数据和LRU队列，注意其中的LRU队列并不是按照常用的方式使用LIST链表，而是使用MAP来代替LIST，有关这一点原作者已做了说明。
另外还有人将MRU与LRU组合在一起使用，当然如果清楚了设计原理，那么就很容易理解了。
考虑到缓存实现多数使用单例模式，这里使用C++的模版方式设计了一个Singlton基类，这样以后只要继承该类，子类就会支持单例模式了。其代码如下：
//
//SingltonT.h
//
#ifndefSingltonT_h
#defineSingltonT_h
#include<iostream>
#include<tr1/memory>
usingnamespacestd;
usingnamespacestd::tr1;
template<typenameT>
classSinglton{
public:
staticT*instance();
voidprint(){
cout<<"haha"<<endl;
}
~Singlton(){
cout<<"destructsinglton"<<endl;
}
protected:
Singlton();
//private:
protected:
staticstd::tr1::shared_ptr<T>s_instance;
//Singlton();
};
template<typenameT>
std::tr1::shared_ptr<T>Singlton<T>::s_instance;
template<typenameT>
Singlton<T>::Singlton(){
cout<<"constructsinglton"<<endl;
}
template<typenameT>
T*Singlton<T>::instance(){
if(!s_instance.get())
s_instance.reset(newT);
returns_instance.get();
}
另外考虑到在多线程下对static单例对象进行操作，会出现并发访问同步的问题，所以这里使用了读写互斥锁来进行set（设置数据）的同步。如下：
#ifndef_RWLOCK_H_
#define_RWLOCK_H_
#defineLOCK(q)while(__sync_lock_test_and_set(&(q)->lock,1)){}
#defineUNLOCK(q)__sync_lock_release(&(q)->lock);
structrwlock{
intwrite;
intread;
};
staticinlinevoid
rwlock_init(structrwlock*lock){
lock->write=0;
lock->read=0;
}
staticinlinevoid
rwlock_rlock(structrwlock*lock){
for(;;){//不断循环，直到对读计数器累加成功
while(lock->write){
__sync_synchronize();
}
__sync_add_and_fetch(&lock->read,1);
if(lock->write){//当已是写锁时，则去掉读锁记数器
__sync_sub_and_fetch(&lock->read,1);
}else{
break;
}
}
}
staticinlinevoid
rwlock_wlock(structrwlock*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优化编译后的生成的程序会产生死锁
}
}
staticinlinevoid
rwlock_wunlock(structrwlock*lock){
__sync_lock_release(&lock->write);
}
staticinlinevoid
rwlock_runlock(structrwlock*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<string.h>
#include<iostream>
#include"rwlock.h"
#include<stdio.h>
#include<sys/malloc.h>
usingnamespacestd;
namespacelru_cache{
staticconstintDEF_CAPACITY=100000;//默认缓存记录数
typedefunsignedlonglongvirtual_time;
typedefstruct_HashKey
{
NSString*key;
}HashKey;
typedefstruct_HashValue
{
idvalue_;
virtual_timeaccess_;
}HashValue;
//仅针对HashKey比较器
template<classkey_t>
structhashkey_compare{
booloperator()(key_tx,key_ty)const{
returnx<y;
}
};
template<>
structhashkey_compare<HashKey>
{
booloperator()(HashKey__x,HashKey__y)const{
stringx=[__x.keyUTF8String];
stringy=[__y.keyUTF8String];
returnx<y;
}
};
//自定义map类型
template<typenameK,typenameV,typename_Compare=hashkey_compare<K>,
typename_Alloc=std::allocator<std::pair<constK,V>>>
classlru_map:publicmap<K,V,_Compare,_Alloc>{};
classCLRUCache
{
public:
CLRUCache():_now(0){
_lru_list=shared_ptr<lru_map<virtual_time,HashKey>>(newlru_map<virtual_time,HashKey>);
_hash_table=shared_ptr<lru_map<HashKey,HashValue>>(newlru_map<HashKey,HashValue>);
}
~CLRUCache(){
_lru_list->clear();
_hash_table->clear();
}
intset(constHashKey&key,constid&value)
{
HashValuehash_value;
hash_value.value_=value;
hash_value.access_=get_virtual_time();
pair<map<HashKey,HashValue>::iterator,bool>ret=_hash_table->insert(make_pair(key,hash_value));
if(!ret.second){
//keyalreadyexist
virtual_timeold_access=(*_hash_table)[key].access_;
map<virtual_time,HashKey>::iteratoriter=_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)
{
//gettheleastrecentlyusedkey
map<virtual_time,HashKey>::iteratoriter=_lru_list->begin();
_hash_table->erase(iter->second);
//removelastkeyfromlist
_lru_list->erase(iter);
}
}
return0;
}
HashValue*get(constHashKey&key)
{
map<HashKey,HashValue>::iteratoriter=_hash_table->find(key);
if(iter!=_hash_table->end())
{
virtual_timeold_access=iter->second.access_;
iter->second.access_=get_virtual_time();
//调整当前key在LRU列表中的位置
map<virtual_time,HashKey>::iteratorit=_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{
returnNULL;
}
}
unsignedget_lru_list_size(){return(unsigned)_lru_list->size();}
unsignedget_hash_table_size(){return(unsigned)_hash_table->size();}
virtual_timeget_now(){return_now;}
private:
virtual_timeget_virtual_time()
{
return++_now;
}
shared_ptr<lru_map<virtual_time,HashKey>>_lru_list;
shared_ptr<lru_map<HashKey,HashValue>>_hash_table;
virtual_time_now;
};
#endif
接下来看一下如果结合单例和rwlock来设计最终的缓存功能，如下：
usingnamespacelru_cache;
classDZCache:publicSinglton<DZCache>
{
friendclassSinglton<DZCache>;
private:
shared_ptr<CLRUCache>clu_cache;
rwlock*lock;
DZCache(){
lock=(rwlock*)malloc(sizeof(rwlock));
rwlock_init(lock);
clu_cache=shared_ptr<CLRUCache>(newCLRUCache());
cout<<"constructJobList"<<endl;
}
DZCache*Instance(){
returns_instance.get();
}
public:
~DZCache(){
free(lock);
}
staticDZCache&getInstance(){
return*instance();
}
voidset(NSString*key,idvalue){
//加锁
rwlock_wlock(lock);
HashKeyhash_key;
hash_key.key=key;
clu_cache->set(hash_key,value);
rwlock_wunlock(lock);
}
idget(NSString*key){
HashKeyhash_key;
hash_key.key=key;
HashValue*value=clu_cache->get(hash_key);
if(value==NULL){
returnnil;
}
else{
returnvalue->value_;
}
}
};
#endif
最后看一下如何使用：
voidtestLRUCache(){
//指针方式
DZCache::instance()->set(@"name",@"daizhj");//设置
NSString*name=(NSString*)DZCache::instance()->get(@"name");//获取
std::cout<<[nameUTF8String]<<endl;
NSNumber*age=[NSNumbernumberWithInt:123123];
DZCache::instance()->set(@"age",age);
age=(NSNumber*)DZCache::instance()->get(@"age");
//对象方式
DZCache::getInstance().set(@"name",@"daizhenjun");
name=(NSString*)DZCache::getInstance().get(@"name");
std::cout<<[nameUTF8String]<<endl;
age=[NSNumbernumberWithInt:123456];
DZCache::getInstance().set(@"age",age);
age=(NSNumber*)DZCache::getInstance().get(@"age");
}
好了，今天的内容就先到这里了。
相关文章
- C++学习——c++逗号操作符说明（附加全部运算符优先级）
- iOS小技能： Target-Action设计模式的运用
- iOS编译简析
- C++构造函数的作用_c++什么是构造函数
- 《幻塔》重回iOS畅销榜前十，《沙石镇时光》登顶steam榜单
- IOS 上架流程简洁版
- C++stl库_c++库
- iOS证书(.p12)和描述文件(.mobileprovision)制作
- iOS屏幕旋转处理
- C++字符串加密_c++字符串连接函数
- IOS – OpenGL ES 调节图像RGB通道 GPUImageRGBFilter
- 【IOS实用玩机技巧】爱思助手 IPA 签名功能常见问题汇总（iOS上架）
- 让你快速创建 iOS 7 图标的模板资源
- AnyTrans for iOS for mac(ios数据传输管理工具)
- iOS字符串NSString常用方法详解手机开发
- iOS get请求的block方法详解手机开发
- iOS 根据Label长度 拉伸imageView长度详解手机开发
- iOS多图片上传详解手机开发
- 在iOS上搭建MySQL数据库连接（ios连接mysql数据库）
- appLinux开发探索之路：从iOS APP开始（linux开发ios）
- MacOS 与 iOS：由浅入深的连接（macos和ios）
- Linux技术可以开发IOS系统?（linux能开发ios吗）
- Linux与iOS：同源不同道（linux与ios的关系）
- 比较iOS和Linux：谁更具优势？（ios和linux）
- Linux与iOS：越来越亲密的合作伙伴（linux与ios）
- 苹果推出iOS 14.4.2/12.5.2版紧急安全更新修复被积极利用的安全漏洞
- 你好小娜 再见小娜！微软宣布明年年初开始结束对安卓和iOS版小娜的支持
- iOS访问MySQL数据库的实战技术（ios访问mysql）
- IOS开发之路--C语言基础知识