在一個服務程序運行的時候，它往往要把數據寫入共享內存以便在進城需要重新啟動的時候可以直接從共享內存中讀取數據，另一方面，在服務進程因某種原因掛掉的時候，共享內存中的數據仍然存在，這樣就可以減少帶來的損失。關于共享內存的內容請google之，在這里，實現了一種在共享內存中存取數據的hash表，它采用了多級存儲求模取余的方法，具體內容請看以下代碼：
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 素數集中原理
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的值 是是否進行驗證的標志也是對應的6t-1和6t+1的素性標志**/
if(((k-4)==0)||((k-9)==0)||((m+1)%3==0))j=0;/*此處是簡單驗證6*t-1,6*t+1 是不是素數，借以提高素數純度**/
if(((k-6)==0)||((m-1)%3==0))i=0; /***先通過初步判斷去除末尾是5，及被3整除的數***/
for(p=1;p*6<=sqrt(m+1)+2;p++ )
{
n=p*6; /**將6*p-1和6*p+1看作偽素數來試除*****/
k=p%10;
a=1;b=1; /**同樣此處a,b的值也是用來判斷除數是否為素數提高除數的素數純度**/
if(((k-4)==0)||((k-9)==0))a=0;
if(((k-6)==0))b=0;
if(i){ /*如果i非零就對m-1即所謂6*t-1進行驗證，當然還要看除數n+1,n-1,素性純度*/
if(a){if((m-1)%(n+1)==0)i=0;} /***一旦被整除就說明不是素數故素性為零即將i 賦值為零***/
if(b){if((m-1)%(n-1)==0)i=0;}
}
if(j){ /**如果j非零就對m+1即所謂6*t+1進行驗證，當然還要看除數n+1,n-1,素性純度*/
if(a){if((m+1)%(n+1)==0)j=0;} /***一旦被整除就說明不是素數故素性為零即將j 賦值為零***/
if(b){if((m+1)%(n-1)==0)j=0;}
}
if((i+j)==0)break; /**如果已經知道6*t-1,6*t+1都不是素數了那就結束試除循環***/
}
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;
}
這段代碼作測試的時候發現了一些問題，用gprof查看函數時間的時候發現，getPos函數占用了大部分的執行時間，始主要的性能瓶頸，后來又新設立了一個數組，用來記錄每行開始時的位置，性能提高了很多，改動部分的代碼如下：
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;
}
新增了一個用于遍歷的函數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);
}
}
為了利于使用新增一個用于查找的函數find,該函數同find(_key)類似，如果找到_key節點，把它賦給_value以返回
int find(unsigned long _key,vT &_value);