C++ to develop the LRUCache cache function running in IOS environment

This article focuses on how to use C++ in XCODE to develop a cache that runs in an IOS environment. The algorithm is based on LRU (least recently used). See details on lru:
http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used
I have seen a friend's C++ implementation on the Internet before, feeling good, so the core code adopted his design.
The original author USES two MAP objects to record the cached data and the LRU queue. Note that the LRU queue does not use the LIST LIST in the usual way, but USES a MAP instead of a LIST, which the original author has explained.

Others combine MRU with LRU, which is easy to understand if the design principle is clear.
Considering that most cache implementations use the singleton pattern, a Singlton base class is designed using a C++ template so that subclasses can support the singleton pattern by simply inheriting from it. The code is as follows:

 
// 
// 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(); 
} 

In addition, considering that the static singleton object is operated on by multiple threads, the problem of concurrent access and synchronization will occur, so the read-write mutex is used to synchronize the set (set data). As follows:

 
#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 (;;) {//Loop until the read counter accumulates successfully
while(lock->write) { 
__sync_synchronize(); 
} 
__sync_add_and_fetch(&lock->read,1); 
if (lock->write) {//When a write lock is in place, the read lock counter is removed
__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();//Very important, if removed, the g++ -o3 optimized compiled generated program will generate deadlocks
} 
} 
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); 
} 

Instead of using pthread_mutex_t to design the lock, you use the system of instructions with s/s _sync_fetch_and_add. Of course, I haven't tested whether the function is 7-8 times better than pthread_mutex_t, as the author of the above link says.
After having these two classes, I added the definition of KEY comparison method mentioned in the original author, and introduced the id to support the object cache of object-c. The final code was modified as follows:

 
#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;//Default number of cache records
typedef unsigned long long virtual_time; 
typedef struct _HashKey 
{ 
NSString* key; 
}HashKey; 
typedef struct _HashValue 
{ 
id value_; 
virtual_time access_; 
}HashValue; 
//Only for the HashKey comparator
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; 
} 
}; 
//Customize the map type
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(); 
//Adjust the position of the current key in the LRU list
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 

Let's take a look at how to combine singletons and rwlock to design the final caching function, as follows:

 
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){ 
//lock
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 

Finally, here's how to use it:

 
void testLRUCache(){ 
//Pointer to the way
DZCache::instance()->set(@"name", @"daizhj");//Set up the
NSString* name = (NSString*)DZCache::instance()->get(@"name");//To obtain
std::cout<<[name UTF8String]<<endl; 
NSNumber * age=[NSNumber numberWithInt:123123]; 
DZCache::instance()->set(@"age", age); 
age = (NSNumber*)DZCache::instance()->get(@"age"); 
//Object way
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"); 
} 

Well, that's all for today.