• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            洗塵齋

            三懸明鏡垂鴻韻,九撩清泉洗塵心

            常用鏈接

            統(tǒng)計(jì)

            最新評(píng)論

            使用共享內(nèi)存的多級(jí)哈希表的一種實(shí)現(xiàn)

            在一個(gè)服務(wù)程序運(yùn)行的時(shí)候,它往往要把數(shù)據(jù)寫(xiě)入共享內(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)記錄每行開(kā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)類(lèi)似,如果找到_key節(jié)點(diǎn),把它賦給_value以返回
            int find(unsigned long _key,vT &_value);

            posted on 2007-09-08 21:17 芥之舟 閱讀(7679) 評(píng)論(3)  編輯 收藏 引用 所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu)和算法

            評(píng)論

            # re: 使用共享內(nèi)存的多級(jí)哈希表的一種實(shí)現(xiàn) 2012-06-16 16:44 ydsec

            不錯(cuò),能發(fā)進(jìn)一步改進(jìn),value如果是一個(gè)結(jié)構(gòu)體,如何實(shí)現(xiàn)呢??jī)?nèi)存用格式表示數(shù)據(jù)  回復(fù)  更多評(píng)論   

            # re: 使用共享內(nèi)存的多級(jí)哈希表的一種實(shí)現(xiàn) 2014-08-28 13:14 null

            if(*(currentSize=(unsigned long *)((long)mem+memSize))<0)
            這一句不是很明白,  回復(fù)  更多評(píng)論   

            # re: 使用共享內(nèi)存的多級(jí)哈希表的一種實(shí)現(xiàn) 2014-10-13 10:51 abc

            p*6<=sqrt(m+1)+2 這個(gè)是什么原理?  回復(fù)  更多評(píng)論   

            久久天天躁夜夜躁狠狠躁2022| 欧美成人免费观看久久| 亚洲国产精品一区二区久久| 久久WWW免费人成一看片| 亚洲国产精品成人AV无码久久综合影院 | 久久久久无码精品国产| 久久婷婷五月综合97色直播| 日韩欧美亚洲综合久久影院d3| 久久国产欧美日韩精品| 久久久久久久97| 久久精品亚洲乱码伦伦中文| 亚洲午夜久久久精品影院| 精品久久久久久无码免费| 亚洲国产精品久久久久婷婷软件 | 久久毛片免费看一区二区三区| 亚洲人成无码网站久久99热国产| 亚洲AV无码久久精品成人| 久久久久久国产精品美女| 激情伊人五月天久久综合| 久久av无码专区亚洲av桃花岛| 国产精品久久亚洲不卡动漫| 999久久久无码国产精品| 久久久久这里只有精品| 99精品国产在热久久无毒不卡| 久久国产香蕉一区精品| 久久久久99精品成人片直播| 91亚洲国产成人久久精品网址| 国产69精品久久久久9999APGF| 亚洲成色WWW久久网站| 久久亚洲精品中文字幕三区| 久久精品国产久精国产一老狼| 青青草国产精品久久| 亚洲中文字幕无码久久2017| 久久久无码精品亚洲日韩软件| 99久久99这里只有免费费精品| 亚洲午夜福利精品久久| 久久国产乱子伦精品免费午夜| 色偷偷88888欧美精品久久久| 成人久久精品一区二区三区| 2021国内久久精品| 成人综合伊人五月婷久久|