在一個(gè)服務(wù)程序運(yùn)行的時(shí)候，它往往要把數(shù)據(jù)寫入共享內(nèi)存以便在進(jìn)城需要重新啟動(dòng)的時(shí)候可以直接從共享內(nèi)存中讀取數(shù)據(jù)，另一方面，在服務(wù)進(jìn)程因某種原因掛掉的時(shí)候，共享內(nèi)存中的數(shù)據(jù)仍然存在，這樣就可以減少帶來(lái)的損失。關(guān)于共享內(nèi)存的內(nèi)容請(qǐng)google之，在這里，實(shí)現(xiàn)了一種在共享內(nèi)存中存取數(shù)據(jù)的hash表，它采用了多級(jí)存儲(chǔ)求模取余的方法，具體內(nèi)容請(qǐng)看以下代碼：
http://lmlf001.blog.sohu.com/
//hash_shm.h
#ifndef _STORMLI_HASH_SHM_H_
#define _STORMLI_HASH_SHM_H_
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<sys/shm.h>
using namespace std;
template<typename valueType,unsigned long maxLine,int lines>
class hash_shm
{
public:
int find(unsigned long _key); //if _key in the table,return 0,and set lastFound the position,otherwise return -1
int remove(unsigned long _key); //if _key not in the table,return-1,else remove the node,set the node key 0 and return 0
//insert node into the table,if the _key exists,return 1,if insert success,return 0;and if fail return -1
int insert(unsigned long _key,const valueType &_value);
void clear(); //remove all the data
public: //some statistic function
double getFullRate()const; //the rate of the space used
public:
//constructor,with the share memory start position and the space size,if the space is not enough,the program will exit
hash_shm(void *startShm,unsigned long shmSize=sizeof(hash_node)*maxLine*lines);
//constructor,with the share memory key,it will get share memory,if fail,exit
hash_shm(key_t shm_key);
~hash_shm(){} //destroy the class
private:
void *mem; //the start position of the share memory // the mem+memSize space used to storage the runtime data:currentSize
unsigned long memSize; //the size of the share memory
unsigned long modTable[lines]; //modtable,the largest primes
unsigned long maxSize; //the size of the table
unsigned long *currentSize; //current size of the table ,the pointer of the shm mem+memSize
void *lastFound; //write by the find function,record the last find place
struct hash_node{ //the node of the hash table
unsigned long key; //when key==0,the node is empty
valueType value; //name-value pair
};
private:
bool getShm(key_t shm_key); //get share memory,used by the constructor
void getMode(); //get the largest primes blow maxLine,use by the constructor
void *getPos(unsigned int _row,unsigned long _col);//get the positon with the (row,col)
};
template<typename vT,unsigned long maxLine,int lines>
hash_shm<vT,maxLine,lines>::hash_shm(void *startShm,unsigned long shmSize)
{
if(startShm!=NULL){
cerr<<"Argument error
\n Please check the shm address\n";
exit(-1);
}
getMode();
maxSize=0;
int i;
for(i=0;i<lines;i++) //count the maxSize
maxSize+=modTable[i];
if(shmSize<sizeof(hash_node)*(maxSize+1)){ //check the share memory size
cerr<<"Not enough share memory space\n";
exit(-1);
}
memSize=shmSize;
if(*(currentSize=(unsigned long *)((long)mem+memSize))<0)
*currentSize=0;;
}
template<typename vT,unsigned long maxLine,int lines>
hash_shm<vT,maxLine,lines>::hash_shm(key_t shm_key)
{ //constructor with get share memory
getMode();
maxSize=0;
for(int i=0;i<lines;i++)
maxSize+=modTable[i];
memSize=sizeof(hash_node)*maxSize;
if(!getShm(shm_key)){
exit(-1);
}
// memset(mem,0,memSize);
if(*(currentSize=(unsigned long *)((long)mem+memSize))<0)
*currentSize=0;
}
template<typename vT,unsigned long maxLine,int lines>
int hash_shm<vT,maxLine,lines>::find(unsigned long _key)
{
unsigned long hash;
hash_node *pH=NULL;
for(int i=0;i<lines;i++)
{
hash=(_key+maxLine)%modTable[i]; //calculate the col position
pH=(hash_node *)getPos(i,hash);
// if(pH==NULL)return -2; //almost not need
if(pH->key==_key){
lastFound=pH;
return 0;
}
}
return -1;
}
template<typename vT,unsigned long maxLine,int lines>
int hash_shm<vT,maxLine,lines>::remove(unsigned long _key)
{
if(find(_key)==-1)return -1; //not found
hash_node *pH=(hash_node *)lastFound;
pH->key=0; //only set the key 0
(*currentSize)--;
return 0;
}
template<typename vT,unsigned long maxLine,int lines>
int hash_shm<vT,maxLine,lines>::insert(unsigned long _key,const vT &_value)
{
if(find(_key)==0)return 1; //if the key exists
unsigned long hash;
hash_node *pH=NULL;
for(int i=0;i<lines;i++){
hash=(_key+maxLine)%modTable[i];
pH=(hash_node *)getPos(i,hash);
if(pH->key==0){ //find the insert position,insert the value
pH->key=_key;
pH->value=_value;
(*currentSize)++;
return 0;
}
}
return -1; //all the appropriate position filled
}
template<typename vT,unsigned long maxLine,int lines>
void hash_shm<vT,maxLine,lines>::clear()
{
memset(mem,0,memSize);
*currentSize=0;
}
template<typename vT,unsigned long maxLine,int lines>
bool hash_shm<vT,maxLine,lines>::getShm(key_t shm_key)
{
int shm_id=shmget(shm_key,memSize,0666);
if(shm_id==-1) //check if the shm exists
{
shm_id=shmget(shm_key,memSize,0666|IPC_CREAT);//create the shm
if(shm_id==-1){
cerr<<"Share memory get failed\n";
return false;
}
}
mem=shmat(shm_id,NULL,0); //mount the shm
if(int(mem)==-1){
cerr<<"shmat system call failed\n";
return false;
}
return true;
}
template<typename vT,unsigned long maxLine,int lines>
void hash_shm<vT,maxLine,lines>::getMode()
{ //采用 6n+1 6n-1 素?cái)?shù)集中原理
if(maxLine<5){exit(-1);}
unsigned long t,m,n,p;
int i,j,a,b,k;
int z=0;
for(t=maxLine/6;t>=0,z<lines;t--)
{
i=1;j=1; k=t%10;
m=6*t; /**i,j的值 是是否進(jìn)行驗(yàn)證的標(biāo)志也是對(duì)應(yīng)的6t-1和6t+1的素性標(biāo)志**/
if(((k-4)==0)||((k-9)==0)||((m+1)%3==0))j=0;/*此處是簡(jiǎn)單驗(yàn)證6*t-1,6*t+1 是不是素?cái)?shù)，借以提高素?cái)?shù)純度**/
if(((k-6)==0)||((m-1)%3==0))i=0; /***先通過(guò)初步判斷去除末尾是5，及被3整除的數(shù)***/
for(p=1;p*6<=sqrt(m+1)+2;p++ )
{
n=p*6; /**將6*p-1和6*p+1看作偽素?cái)?shù)來(lái)試除*****/
k=p%10;
a=1;b=1; /**同樣此處a,b的值也是用來(lái)判斷除數(shù)是否為素?cái)?shù)提高除數(shù)的素?cái)?shù)純度**/
if(((k-4)==0)||((k-9)==0))a=0;
if(((k-6)==0))b=0;
if(i){ /*如果i非零就對(duì)m-1即所謂6*t-1進(jìn)行驗(yàn)證，當(dāng)然還要看除數(shù)n+1,n-1,素性純度*/
if(a){if((m-1)%(n+1)==0)i=0;} /***一旦被整除就說(shuō)明不是素?cái)?shù)故素性為零即將i 賦值為零***/
if(b){if((m-1)%(n-1)==0)i=0;}
}
if(j){ /**如果j非零就對(duì)m+1即所謂6*t+1進(jìn)行驗(yàn)證，當(dāng)然還要看除數(shù)n+1,n-1,素性純度*/
if(a){if((m+1)%(n+1)==0)j=0;} /***一旦被整除就說(shuō)明不是素?cái)?shù)故素性為零即將j 賦值為零***/
if(b){if((m+1)%(n-1)==0)j=0;}
}
if((i+j)==0)break; /**如果已經(jīng)知道6*t-1,6*t+1都不是素?cái)?shù)了那就結(jié)束試除循環(huán)***/
}
if(j){modTable[z++]=m+1;if(z>= lines)return;}
if(i){modTable[z++]=m-1;if(z>= lines)return;}
}
}
template<typename vT,unsigned long maxLine,int lines>
void *hash_shm<vT,maxLine,lines>::getPos(unsigned int _row,unsigned long _col)
{
unsigned long pos=0UL;
for(int i=0;i<_row;i++) //calculate the positon from the start
pos+=modTable[i];
pos+=_col;
if(pos>=maxSize)return NULL;
return (void *)((long)mem+pos*sizeof(hash_node));
}
template<typename vT,unsigned long maxLine,int lines>
double hash_shm<vT,maxLine,lines>::getFullRate()const
{
return double(*currentSize)/maxSize;
}
#endif
//test.cpp
#include"hash_shm.h"
#include<cstdlib>
using namespace std;
int main()
{
hash_shm<int,1000,100> ht(key_t(999));
double rate=0.0;
// ht.clear();
for(int i=0;i<100;i++){
srand(time(NULL)+i);
while(true){
if(ht.insert(rand(),0)==-1)break;
}
cout<<ht.getFullRate()<<endl;
rate+=ht.getFullRate();
ht.clear();
}
cout<<"\n\n\n";
cout<<rate/100<<endl;
}
這段代碼作測(cè)試的時(shí)候發(fā)現(xiàn)了一些問(wèn)題，用gprof查看函數(shù)時(shí)間的時(shí)候發(fā)現(xiàn)，getPos函數(shù)占用了大部分的執(zhí)行時(shí)間，始主要的性能瓶頸，后來(lái)又新設(shè)立了一個(gè)數(shù)組，用來(lái)記錄每行開始時(shí)的位置，性能提高了很多，改動(dòng)部分的代碼如下：
template<typename valueType,unsigned long maxLine,int lines>
class hash_shm
{
private:
void *mem; //the start position of the share memory // the mem+memSize space used to storage the runtime data:currentSize
unsigned long memSize; //the size of the share memory
unsigned long modTable[lines]; //modtable,the largest primes
unsigned long modTotal[lines]; //modTotal[i] is the summary of the modTable when x<=i
//used by getPos to improve the performance
...
};
template<typename vT,unsigned long maxLine,int lines>
hash_shm<vT,maxLine,lines>::hash_shm(void *startShm,unsigned long shmSize)
{
...
int i;
for(i=0;i<lines;i++){ //count the maxSize
maxSize+=modTable[i];
if(i!=0)modTotal[i]=modTotal[i-1]+modTable[i-1];
else modTotal[i]=0; //caculate the modTotal
}
...
}
template<typename vT,unsigned long maxLine,int lines>
hash_shm<vT,maxLine,lines>::hash_shm(key_t shm_key)
{ //constructor with get share memory
getMode();
maxSize=0;
for(int i=0;i<lines;i++){
maxSize+=modTable[i];
if(i!=0)modTotal[i]=modTotal[i-1]+modTable[i-1];
else modTotal[i]=0;
}
...
}
template<typename vT,unsigned long maxLine,int lines>
void *hash_shm<vT,maxLine,lines>::getPos(unsigned int _row,unsigned long _col)
{
unsigned long pos=_col+modTotal[_row];
//for(int i=0;i<_row;i++) //calculate the positon from the start
// pos+=modTable[i];
if(pos<maxSize)
return (void *)((long)mem+pos*sizeof(hash_node));
return NULL;
}
新增了一個(gè)用于遍歷的函數(shù)foreach
template<typename vT,unsigned long maxLine,int lines>
void hash_shm<vT,maxLine,lines>::foreach(void (*fn)(unsigned long _key,vT &_value))
{
typedef unsigned long u_long;
u_long beg=(u_long)mem;
u_long end=(u_long)mem+sizeof(hash_node)*(modTable[lines-1]+modTotal[lines-1]);
hash_node *p=NULL;
for(u_long pos=beg;pos<end;pos+=sizeof(hash_node))
{
p=(hash_node *)pos;
if(p->key!=0)fn(p->key,p->value);
}
}
為了利于使用新增一個(gè)用于查找的函數(shù)find,該函數(shù)同find(_key)類似，如果找到_key節(jié)點(diǎn)，把它賦給_value以返回
int find(unsigned long _key,vT &_value);