當C++遇到IOS應用開發—LRUCache緩存 – iPhone手機開發技術文章 iPhone軟體開發教學課程

       考慮到緩存實現多數使用單例模式,這裡使用C++的模版方式設計瞭一個Singlton基類,這樣以後隻要繼承該類,子類就會支持單例模式瞭。其代碼如下:
 
[cpp] 
// 
//  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(); 
      ~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單例對象進行操作,會出現並發訪問同步的問題,所以這裡使用瞭讀寫互斥鎖來進行set(設置數據)的同步。如下:
[cpp] 
#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 (;;) {//不斷循環,直到對讀計數器累加成功 
        while(lock->write) { 
            __sync_synchronize(); 
        } 
        __sync_add_and_fetch(&lock->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) { 
        //https://blog.itmem.com/?m=201204 
        //https://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的對象緩存,最終代碼修改如下:

[cpp] 
#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;//默認緩存記錄數 
 
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(); 
            //調整當前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 

 

      接下來看一下如果結合單例和rwlock來設計最終的緩存功能,如下:

[cpp] 
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 

 

    最後看一下如何使用:
[cpp]
void testLRUCache(){ 
    //指針方式 
    DZCache::instance()->set(@"name", @"daizhj");//設置 
    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"); 

 

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。