C++開發(fā)在IOS環(huán)境下運行的LRUCache緩存功能
更新時間：2012年11月13日 15:47:12 作者：
本文著重介紹如何在XCODE中，通過C++開發(fā)在IOS環(huán)境下運行的緩存功能。算法基于LRU,最近最少使用,需要的朋友可以參考下
本文著重介紹如何在XCODE中，通過C++開發(fā)在IOS環(huán)境下運行的緩存功能。算法基于LRU（最近最少使用）。有關(guān)lru詳見：
http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
之前在網(wǎng)上看到過網(wǎng)友的一個C++實現(xiàn)，感覺不錯，所以核心代碼就采用了他的設(shè)計。
原作者通過兩個MAP對象來記錄緩存數(shù)據(jù)和LRU隊列，注意其中的LRU隊列并不是按照常用的方式使用LIST鏈表，而是使用MAP來代替LIST，有關(guān)這一點原作者已做了說明。
另外還有人將MRU與LRU組合在一起使用，當(dāng)然如果清楚了設(shè)計原理，那么就很容易理解了。
考慮到緩存實現(xiàn)多數(shù)使用單例模式，這里使用C++的模版方式設(shè)計了一個Singlton基類，這樣以后只要繼承該類，子類就會支持單例模式了。其代碼如下：
//
// SingltonT.h
//
#ifndef SingltonT_h
#define SingltonT_h
#include <iostream>
#include <tr1/memory>
using namespace std;
using namespace std::tr1;
template <typename T>
class Singlton {
public:
static T* instance();
void print() {
cout << "haha" << endl;
}
~Singlton() {
cout << "destruct singlton" << endl;
}
protected:
Singlton();
//private:
protected:
static std::tr1::shared_ptr<T> s_instance;
//Singlton();
};
template <typename T>
std::tr1::shared_ptr<T> Singlton<T>::s_instance;
template <typename T>
Singlton<T>::Singlton() {
cout << "construct singlton" << endl;
}
template <typename T>
T* Singlton<T>::instance() {
if (!s_instance.get())
s_instance.reset(new T);
return s_instance.get();
}
另外考慮到在多線程下對static單例對象進(jìn)行操作，會出現(xiàn)并發(fā)訪問同步的問題，所以這里使用了讀寫互斥鎖來進(jìn)行set（設(shè)置數(shù)據(jù)）的同步。如下：
#ifndef _RWLOCK_H_
#define _RWLOCK_H_
#define LOCK(q) while (__sync_lock_test_and_set(&(q)->lock,1)) {}
#define UNLOCK(q) __sync_lock_release(&(q)->lock);
struct rwlock {
int write;
int read;
};
static inline void
rwlock_init(struct rwlock *lock) {
lock->write = 0;
lock->read = 0;
}
static inline void
rwlock_rlock(struct rwlock *lock) {
for (;;) {//不斷循環(huán)，直到對讀計數(shù)器累加成功
while(lock->write) {
__sync_synchronize();
}
__sync_add_and_fetch(&lock->read,1);
if (lock->write) {//當(dāng)已是寫鎖時，則去掉讀鎖記數(shù)器
__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 優(yōu)化編譯后的生成的程序會產(chǎn)生死鎖
}
}
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來設(shè)計鎖，而是使用了__sync_fetch_and_add指令體系，當(dāng)然最終是否如上面鏈接中作者所說的比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>
using namespace std;
namespace lru_cache {
static const int DEF_CAPACITY = 100000;//默認(rèn)緩存記錄數(shù)
typedef unsigned long long virtual_time;
typedef struct _HashKey
{
NSString* key;
}HashKey;
typedef struct _HashValue
{
id value_;
virtual_time access_;
}HashValue;
//僅針對HashKey比較器
template <class key_t>
struct hashkey_compare{
bool operator()(key_t x, key_t y) const{
return x < y;
}
};
template <>
struct hashkey_compare<HashKey>
{
bool operator()(HashKey __x, HashKey __y) const{
string x = [__x.key UTF8String];
string y = [__y.key UTF8String];
return x < y;
}
};
//自定義map類型
template <typename K, typename V, typename _Compare = hashkey_compare<K>,
typename _Alloc = std::allocator<std::pair<const K, V> > >
class lru_map: public map<K, V, _Compare, _Alloc>{};
class CLRUCache
{
public:
CLRUCache() : _now(0){
_lru_list = shared_ptr<lru_map<virtual_time, HashKey> >(new lru_map<virtual_time, HashKey>);
_hash_table = shared_ptr<lru_map<HashKey, HashValue> > (new lru_map<HashKey, HashValue>);
}
~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<HashKey, HashValue>::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<virtual_time, HashKey>::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<virtual_time, HashKey>::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<HashKey, HashValue>::iterator iter = _hash_table->find(key);
if ( iter != _hash_table->end() )
{
virtual_time old_access = iter->second.access_;
iter->second.access_ = get_virtual_time();
//調(diào)整當(dāng)前key在LRU列表中的位置
map<virtual_time, HashKey>::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_map<virtual_time, HashKey> > _lru_list;
shared_ptr<lru_map<HashKey, HashValue> > _hash_table;
virtual_time _now;
};
#endif
接下來看一下如果結(jié)合單例和rwlock來設(shè)計最終的緩存功能，如下：
using namespace lru_cache;
class DZCache: public Singlton<DZCache>
{
friend class Singlton<DZCache>;
private:
shared_ptr<CLRUCache> clu_cache;
rwlock *lock;
DZCache(){
lock =(rwlock*) malloc(sizeof(rwlock));
rwlock_init(lock);
clu_cache = shared_ptr<CLRUCache>(new CLRUCache());
cout << "construct JobList" << endl;
}
DZCache * Instance() {
return s_instance.get();
}
public:
~DZCache(){
free(lock);
}
static DZCache& getInstance(){
return *instance();
}
void set(NSString* key, id value){
//加鎖
rwlock_wlock(lock);
HashKey hash_key;
hash_key.key = key;
clu_cache->set(hash_key, value);
rwlock_wunlock(lock);
}
id get(NSString* key){
HashKey hash_key;
hash_key.key = key;
HashValue* value = clu_cache->get(hash_key);
if(value == NULL){
return nil;
}
else{
return value->value_;
}
}
};
#endif
最后看一下如何使用：
void testLRUCache(){
//指針方式
DZCache::instance()->set(@"name", @"daizhj");//設(shè)置
NSString* name = (NSString*)DZCache::instance()->get(@"name");//獲取
std::cout<<[name UTF8String]<<endl;
NSNumber * age=[NSNumber numberWithInt: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<<[name UTF8String]<<endl;
age = [NSNumber numberWithInt:123456];
DZCache::getInstance().set(@"age", age);
age = (NSNumber*)DZCache::getInstance().get(@"age");
}
好了，今天的內(nèi)容就先到這里了。
http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
之前在網(wǎng)上看到過網(wǎng)友的一個C++實現(xiàn)，感覺不錯，所以核心代碼就采用了他的設(shè)計。
原作者通過兩個MAP對象來記錄緩存數(shù)據(jù)和LRU隊列，注意其中的LRU隊列并不是按照常用的方式使用LIST鏈表，而是使用MAP來代替LIST，有關(guān)這一點原作者已做了說明。
另外還有人將MRU與LRU組合在一起使用，當(dāng)然如果清楚了設(shè)計原理，那么就很容易理解了。
考慮到緩存實現(xiàn)多數(shù)使用單例模式，這里使用C++的模版方式設(shè)計了一個Singlton基類，這樣以后只要繼承該類，子類就會支持單例模式了。其代碼如下：
復(fù)制代碼 代碼如下:
//
// SingltonT.h
//
#ifndef SingltonT_h
#define SingltonT_h
#include <iostream>
#include <tr1/memory>
using namespace std;
using namespace std::tr1;
template <typename T>
class Singlton {
public:
static T* instance();
void print() {
cout << "haha" << endl;
}
~Singlton() {
cout << "destruct singlton" << endl;
}
protected:
Singlton();
//private:
protected:
static std::tr1::shared_ptr<T> s_instance;
//Singlton();
};
template <typename T>
std::tr1::shared_ptr<T> Singlton<T>::s_instance;
template <typename T>
Singlton<T>::Singlton() {
cout << "construct singlton" << endl;
}
template <typename T>
T* Singlton<T>::instance() {
if (!s_instance.get())
s_instance.reset(new T);
return s_instance.get();
}
另外考慮到在多線程下對static單例對象進(jìn)行操作，會出現(xiàn)并發(fā)訪問同步的問題，所以這里使用了讀寫互斥鎖來進(jìn)行set（設(shè)置數(shù)據(jù)）的同步。如下：
復(fù)制代碼 代碼如下:
#ifndef _RWLOCK_H_
#define _RWLOCK_H_
#define LOCK(q) while (__sync_lock_test_and_set(&(q)->lock,1)) {}
#define UNLOCK(q) __sync_lock_release(&(q)->lock);
struct rwlock {
int write;
int read;
};
static inline void
rwlock_init(struct rwlock *lock) {
lock->write = 0;
lock->read = 0;
}
static inline void
rwlock_rlock(struct rwlock *lock) {
for (;;) {//不斷循環(huán)，直到對讀計數(shù)器累加成功
while(lock->write) {
__sync_synchronize();
}
__sync_add_and_fetch(&lock->read,1);
if (lock->write) {//當(dāng)已是寫鎖時，則去掉讀鎖記數(shù)器
__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 優(yōu)化編譯后的生成的程序會產(chǎn)生死鎖
}
}
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來設(shè)計鎖，而是使用了__sync_fetch_and_add指令體系，當(dāng)然最終是否如上面鏈接中作者所說的比pthread_mutex_t性能要高7-8倍，我沒測試過，感興趣的朋友也可以幫助測試一下。
有了這兩個類之后，我又補充了原文作者中所提到了KEY比較方法的定義，同時引入了id來支持object-c的對象緩存，最終代碼修改如下：
復(fù)制代碼 代碼如下:
#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>
using namespace std;
namespace lru_cache {
static const int DEF_CAPACITY = 100000;//默認(rèn)緩存記錄數(shù)
typedef unsigned long long virtual_time;
typedef struct _HashKey
{
NSString* key;
}HashKey;
typedef struct _HashValue
{
id value_;
virtual_time access_;
}HashValue;
//僅針對HashKey比較器
template <class key_t>
struct hashkey_compare{
bool operator()(key_t x, key_t y) const{
return x < y;
}
};
template <>
struct hashkey_compare<HashKey>
{
bool operator()(HashKey __x, HashKey __y) const{
string x = [__x.key UTF8String];
string y = [__y.key UTF8String];
return x < y;
}
};
//自定義map類型
template <typename K, typename V, typename _Compare = hashkey_compare<K>,
typename _Alloc = std::allocator<std::pair<const K, V> > >
class lru_map: public map<K, V, _Compare, _Alloc>{};
class CLRUCache
{
public:
CLRUCache() : _now(0){
_lru_list = shared_ptr<lru_map<virtual_time, HashKey> >(new lru_map<virtual_time, HashKey>);
_hash_table = shared_ptr<lru_map<HashKey, HashValue> > (new lru_map<HashKey, HashValue>);
}
~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<HashKey, HashValue>::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<virtual_time, HashKey>::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<virtual_time, HashKey>::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<HashKey, HashValue>::iterator iter = _hash_table->find(key);
if ( iter != _hash_table->end() )
{
virtual_time old_access = iter->second.access_;
iter->second.access_ = get_virtual_time();
//調(diào)整當(dāng)前key在LRU列表中的位置
map<virtual_time, HashKey>::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_map<virtual_time, HashKey> > _lru_list;
shared_ptr<lru_map<HashKey, HashValue> > _hash_table;
virtual_time _now;
};
#endif
接下來看一下如果結(jié)合單例和rwlock來設(shè)計最終的緩存功能，如下：
復(fù)制代碼 代碼如下:
using namespace lru_cache;
class DZCache: public Singlton<DZCache>
{
friend class Singlton<DZCache>;
private:
shared_ptr<CLRUCache> clu_cache;
rwlock *lock;
DZCache(){
lock =(rwlock*) malloc(sizeof(rwlock));
rwlock_init(lock);
clu_cache = shared_ptr<CLRUCache>(new CLRUCache());
cout << "construct JobList" << endl;
}
DZCache * Instance() {
return s_instance.get();
}
public:
~DZCache(){
free(lock);
}
static DZCache& getInstance(){
return *instance();
}
void set(NSString* key, id value){
//加鎖
rwlock_wlock(lock);
HashKey hash_key;
hash_key.key = key;
clu_cache->set(hash_key, value);
rwlock_wunlock(lock);
}
id get(NSString* key){
HashKey hash_key;
hash_key.key = key;
HashValue* value = clu_cache->get(hash_key);
if(value == NULL){
return nil;
}
else{
return value->value_;
}
}
};
#endif
最后看一下如何使用：
復(fù)制代碼 代碼如下:
void testLRUCache(){
//指針方式
DZCache::instance()->set(@"name", @"daizhj");//設(shè)置
NSString* name = (NSString*)DZCache::instance()->get(@"name");//獲取
std::cout<<[name UTF8String]<<endl;
NSNumber * age=[NSNumber numberWithInt: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<<[name UTF8String]<<endl;
age = [NSNumber numberWithInt:123456];
DZCache::getInstance().set(@"age", age);
age = (NSNumber*)DZCache::getInstance().get(@"age");
}
好了，今天的內(nèi)容就先到這里了。
相關(guān)文章
這篇文章主要介紹了C++實現(xiàn)頁面的緩沖區(qū)管理器，文章圍繞主題展開詳細(xì)的內(nèi)容介紹具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要給大家介紹了關(guān)于C++實現(xiàn)LFU的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Redis具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2021-09-09
由Microsoft Visual C++編譯的程序動態(tài)鏈接到C運行時（/MD 或 /MDd）,它必須運行DLL的一份拷貝（通常被叫作MSVCRT.DLL 或 MSVCRxx.DLL,其中xx代表Visual C++的版本）2013-04-04
C語言的getc()函數(shù)和gets()函數(shù)的使用對比
這篇文章主要介紹了C語言的getc()函數(shù)和gets()函數(shù)的使用對比,從數(shù)據(jù)流中一個是讀取字符一個是讀取字符串,需要的朋友可以參考下2015-08-08
在C語言中,unsigned是一種無符號整數(shù)修飾符,本文主要介紹了c語言中unsigned修飾符的使用,具有一定的參考價值,感興趣的可以了解一下2023-11-11
本篇文章是對紅黑樹的使用詳解。需要的朋友參考下2013-05-05
C語言實現(xiàn)父進(jìn)程主動終止子進(jìn)程的方法總結(jié)
一般的情況,子進(jìn)程自己運行完后,執(zhí)行exit 或者return 后,父進(jìn)程wait. waitpid收回子進(jìn)程,但子進(jìn)程是一個循環(huán)等待狀態(tài)不主動退出,父進(jìn)程可以采用文中介紹的幾種方法,需要的朋友可以參考下2023-10-10
一般情況下，由鍵盤輸入的字符并沒有直接送入程序，而是被存儲在一個緩沖區(qū)當(dāng)中。下面這篇文章主要給大家介紹了關(guān)于C語言中輸入輸出流與緩沖區(qū)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-09-09
在 C語言中，EOF 是一個宏定義，EOF 常常用于文件的輸入輸出中，當(dāng)讀取到文件結(jié)束時，會返回 EOF，本文就詳細(xì)的介紹一下具體使用方法，感興趣的可以一起來了解一下2023-05-05
本文主要介紹了QT6中添加串口模塊SerialPort的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09