Skip to content

Instantly share code, notes, and snippets.

@piti118
Created April 18, 2012 14:08
Show Gist options
  • Save piti118/2413834 to your computer and use it in GitHub Desktop.
Save piti118/2413834 to your computer and use it in GitHub Desktop.
POD caching class with persistent and expiration capability. (You can throw any POD struct at it)
#ifndef PODCACHE_H
#define PODCACHE_H
#include <tr1/unordered_map>
#include <cstring>
#include <limits.h>
#include <fstream>
#include <cassert>
#include <queue>
//simple serializable map for struct
template <class TK> class PODCache_bcmp{
public:
bool operator()(const TK& k1,const TK& k2) const{return memcmp((const void*)&k1,(const void*)&k2, sizeof(TK))==0;}
};
template <class TK> class PODCache_bhash{
public:
inline std::size_t ror(std::size_t x, std::size_t shift) const{
return (x >> shift) | (x << (sizeof(x)*CHAR_BIT - shift));
}
std::size_t operator()(const TK& k) const{
//call hash for every byte of k and xor the result
//may be I can assert alignment... for faster hash
std::size_t ret = 0;
std::tr1::hash<char> chash;
const char* ck = (char*)&k;
for(int i=0;i<sizeof(TK);i++){
ret ^= chash(ck[i]);
ret = ror(ret,i%sizeof(std::size_t));
}
return ret;
}
};
template <class TK,class TV> class PODCache{
public:
typedef std::tr1::unordered_map<TK,TV,PODCache_bhash<TK>,PODCache_bcmp<TK> > PODCacheUM;
typedef typename PODCacheUM::iterator iterator;
typedef typename PODCacheUM::iterator const_iterator;
int hit;
int miss;
int oversize;
PODCacheUM um;
unsigned int maxsize;//do the expiration
//max size is expiration value =0 indicate no limit
std::queue<const TK*> expque;
PODCache(unsigned int maxsize=0):hit(0),miss(0),oversize(0),um(),maxsize(maxsize){}
PODCache(const std::string& fname, unsigned int maxsize=0):hit(0),miss(0),oversize(0),um(),maxsize(maxsize){
read(fname);
}
void read(const std::string& fname){
using namespace std;
ifstream fin(fname.c_str(),ifstream::binary);
assert(fin.good());
//read header
unsigned int magic[3];
fin.read((char*)magic, sizeof(unsigned int)*3);
assert(magic[0]==0x0BADF00D);
assert(magic[1]==sizeof(TK));
assert(magic[2]==sizeof(TV));
while(!fin.eof()){
TK k;
TV v;
fin.read((char*)&k,sizeof(TK));
fin.read((char*)&v,sizeof(TV));
if(fin.eof()){break;}//has to over read to trigger eof
update(k,v);
}
fin.close();
}
const_iterator begin(){return um.begin();}
const_iterator end(){return um.end();}
void update(const TK& k, const TV& v){
std::pair<iterator,bool> insert_result = um.insert(std::make_pair(k,v));
if(!insert_result.second){//insertion fail duplicate key
assert(PODCache_bcmp<TV>()(insert_result.first->second,v));//trying to insert new value for old key why?
}else{
expque.push(&insert_result.first->first);
if(maxsize!=0 && expque.size()>maxsize){
const TK* k = expque.front();
expque.pop();
um.erase(*k);
oversize++;
}
}
}
bool lookup(const TK& k, TV& v){
using namespace std;
typename PODCacheUM::const_iterator it = um.find(k);
if(it!=um.end()){
v = it->second;
hit+=1;
return true;
}else{
miss+=1;
return false;
}
}
int size() const{return um.size();}
void write(const std::string& fname) const{
using namespace std;
ofstream fout(fname.c_str(),ofstream::binary);
assert(fout.good());
//first 12 bytes are the following
//0-3 bytes 0x0BADF00D for sanity check
//4-7 size of key in unsigned int bytes
//7-11 size of value in unsigned int bytes
//the size if for checking the file if we can open it semi-safely
//write header
unsigned int magic[3];
magic[0] = 0x0BADF00D;
magic[1] = sizeof(TK);
magic[2] = sizeof(TV);
fout.write((const char*)magic,3*sizeof(unsigned int));
//now the data is key value key value key value etc.
typename PODCacheUM::const_iterator it;
for(it=um.begin();it!=um.end();++it){
fout.write((const char*)(&(it->first)),sizeof(TK));
fout.write((const char*)(&(it->second)),sizeof(TV));
}
fout.close();
}
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment