LRU缓存cache

代码采用LRU算法实现cache,采用了内嵌链表方式提高性能.使用container_of宏找到地址.
说明:代码分两部分.new目录下通用性高,可使用;另一部分可以做练习.

文件:	cache.tar.gz
大小:	3KB
下载:	下载

////cache-new.h

#ifndef __LUR_CACHE_H__
#define __LUR_CACHE_H__
#include
#include
#include
using namespace std;
using namespace __gnu_cxx;

#define MAX_KEY_SIZE     128
#define MAX_VALUE_SIZE     1024*1024

//求得结构成员偏移地址
//#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

//根据成员地址求得结构体地址
#define container_of(ptr, type, member) ({ \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) );})


typedef struct list_head {
    struct list_head *next, *prev;
}LIST_HEAD;

//modify
//用户数据
typedef struct _app_data {
    unsigned long size;
    char data[MAX_VALUE_SIZE];   
}APP_DATA;

typedef struct _node_data {
    char szKey[MAX_KEY_SIZE];
    APP_DATA stValue;   
}NODE_DATA;
//end

typedef struct _cache_page {
    NODE_DATA *pData;
    struct list_head list;
}CACHE_PAGE;

struct compare_str{
        bool operator()(const char* p1, const char*p2) const{
                return strcmp(p1,p2)==0;
        }
};  
typedef hash_map, compare_str> HASH_MAP;
typedef HASH_MAP::iterator HASH_ITERATOR;
typedef __gnu_cxx::pair HASH_INSERT_PAIR;   
typedef __gnu_cxx::pair HASH_PAIR;


class CLUR_CACHE
{
    public:
        //初始化LRU  cache
        int init_LRUCache(int size);
        //命中情况。若命中，在函数内部adjust_LRUCache调用 ，自动调整
        APP_DATA * hitLRUCache(const char*key);
        //向cache 内插入
        int insert_LRUCache(const char*key,int nKeyLen,const APP_DATA*value); //find_cache没有命中
        void destroy_LRUCache();
        void test();
    private:
        int  m_pageNum;
        //int  m_maxPageNum;
        HASH_MAP m_hash;
       
        LIST_HEAD *m_pageListHead;   
        LIST_HEAD *m_pageListEnd;   
    private:   
        int adjust_LRUCache(CACHE_PAGE *pTempPage);         //find_cache命中
        CACHE_PAGE*find_cache(const char*key);
};
#endif


///cache-new.cpp

#include
#include "cache-new.h"

int CLUR_CACHE::init_LRUCache(int size)
{
    if(size < 1)
        return -1;
    int i;
    m_pageNum = size;
   
    CACHE_PAGE *prePage = NULL;
    CACHE_PAGE *pPage = NULL;
   
    //设置头指针
    pPage = (CACHE_PAGE*)new CACHE_PAGE;
    NODE_DATA *pData = (NODE_DATA*) new NODE_DATA;
    memset(pData,0,sizeof(NODE_DATA));
    pPage->pData= pData;
   
    m_pageListHead = &(pPage->list);
    m_pageListHead->next=NULL;
    m_pageListHead->prev = NULL;
   
    prePage = pPage;

    for(i=0;i    {
        pPage = (CACHE_PAGE*)new CACHE_PAGE;
        pData = (NODE_DATA* )new NODE_DATA;
        memset(pData,0,sizeof(NODE_DATA));
        pPage->pData= pData;
   
        pPage->list.next=NULL;
        pPage->list.prev = &(prePage->list);
       
        prePage->list.next  = &(pPage->list);
        prePage =  pPage;
       
    }   
    m_pageListEnd = &(pPage->list);   
    return 0;   
}

void CLUR_CACHE::destroy_LRUCache()
{
    int i=0;
    LIST_HEAD* pNextList =NULL;
    LIST_HEAD* pList =m_pageListHead;
    CACHE_PAGE* tmp =NULL;
    for(i=0;i    {
        tmp = container_of(pList,CACHE_PAGE,list);   
        pNextList = pList->next;
        if(tmp!=NULL)
        {   
            //cout<pData->szValue<            delete tmp;
            tmp =NULL;
        }
        pList = pNextList;       
    }       
   
}
/*****************************************************************
find_cache命中函数
*****************************************************************/   
CACHE_PAGE*CLUR_CACHE::find_cache(const char*key)
{
    HASH_ITERATOR iter = m_hash.find(key);
    if(iter!=m_hash.end())
        return(iter->second);
    else
        return NULL;   
}

/*****************************************************************
find_cache没有命中后的处理：
在取出m_list头部节点A，在m_hash查找该节点A，
1、若找到则删除m_hash内的A节点信息. 然后用新数据填充该A节点。   
    然后插入m_hash,然后修改m_list的A指针放到尾部。
2、若没找到，   
    用新数据填充该节点。   
    然后插入m_hash,然后修改m_list节点指针放到尾部。
*****************************************************************/       
int CLUR_CACHE::insert_LRUCache(const char*key,int nKeyLen,const APP_DATA*value)
{
list_head *pListTemp  =NULL;
    CACHE_PAGE* tmp =NULL;
    HASH_INSERT_PAIR Insert_Pair ;
    //取出头节点对应页地址
    tmp = container_of(m_pageListHead, CACHE_PAGE, list);   
    //在hash表中查找头节点
    HASH_ITERATOR iter = m_hash.find(tmp->pData->szKey);
    if(iter!=m_hash.end())
    {
        //删除头节点
        m_hash.erase(tmp->pData->szKey);
        //插入新节点
        Insert_Pair = m_hash.insert(HASH_PAIR(key,tmp));
        if(!Insert_Pair.second)
        {   
            cout<<"insert hash error"<            return -1;
        }
        //修改新节点数据
        memset(tmp->pData,0,sizeof(NODE_DATA));
        memmove( tmp->pData->szKey,key,nKeyLen );
        memmove( &(tmp->pData->stValue),value, sizeof(APP_DATA) );   
       
        //修改头节点指针
        pListTemp = m_pageListHead;
        m_pageListHead = m_pageListHead->next;
        m_pageListHead->prev = NULL;
       
        //处理尾节点
        m_pageListEnd ->next  = pListTemp;
        pListTemp->prev= m_pageListEnd;
        pListTemp->next=NULL;
        m_pageListEnd = pListTemp;
       
    }
    else
    {
        //插入新节点
        Insert_Pair = m_hash.insert(HASH_PAIR(key,tmp));
        if(!Insert_Pair.second)
        {   
            cout<<"insert hash error"<            return -1;
        }
        //修改新节点数据
        memset(tmp->pData,0,sizeof(NODE_DATA));
        memmove(tmp->pData->szKey,key,nKeyLen);
        memmove(&(tmp->pData->stValue),value, sizeof(APP_DATA) );   
       
        //修改头节点指针
        pListTemp = m_pageListHead;
        m_pageListHead = m_pageListHead->next;
        m_pageListHead->prev = NULL;
       
        //处理尾节点
        m_pageListEnd ->next  = pListTemp;
        pListTemp->prev= m_pageListEnd;
        pListTemp->next=NULL;
        m_pageListEnd = pListTemp;
    }       
   
    return 0;
}   

/*****************************************************************
find_cache命中后的处理，直接修改命中的节点指针放到队尾
*****************************************************************/   
int CLUR_CACHE::adjust_LRUCache(CACHE_PAGE *pTempPage)
{
    LIST_HEAD *pTempList = &(pTempPage->list);
    if(pTempList == m_pageListHead)
    {
        m_pageListHead = m_pageListHead->next;
        m_pageListHead->prev = NULL;
       
        m_pageListEnd->next= pTempList;
        pTempList->prev = m_pageListEnd;
        pTempList->next=NULL;
        m_pageListEnd = pTempList;
        return 0;           
    }   
    if(pTempList == m_pageListEnd)
        return 0;
       
    pTempList->prev->next = pTempList->next;
    pTempList->next->prev = pTempList->prev;
   
    //处理尾节点
    m_pageListEnd ->next  = pTempList;
    pTempList->prev= m_pageListEnd;
    pTempList->next=NULL;
    m_pageListEnd = pTempList;
    return 0;
   
}

APP_DATA * CLUR_CACHE::hitLRUCache(const char*key)
{
    CACHE_PAGE* page = find_cache(key);
    if(page ==NULL)
        return NULL;
    adjust_LRUCache(page);
    return(&page->pData->stValue);
   
}   
void CLUR_CACHE::test()
{
    LIST_HEAD *pTempList = m_pageListHead;
    CACHE_PAGE* tmp =NULL;
    int num =0;
    do
    {
       
        tmp = container_of(pTempList, CACHE_PAGE, list);   
        //cout<<"num="<        //cout<<"value="<pData->szValue<        printf("value[%d]=%s\n",num,tmp->pData->stValue.data);
        num++;
        pTempList=pTempList->next;
    }while(pTempList !=NULL);   
}

///test.cpp
//采用hash和内嵌链表，实现高效的cache. 理论上时间复杂度是o(1)
//g++ -g cache.cpp test.cpp
#include
#include
#include "cache-new.h"
int main()
{
    APP_DATA *p ;
    CLUR_CACHE cache;
    int ret = cache.init_LRUCache(3);
    p = cache.hitLRUCache("wwm");
    if(p==NULL)
        cout <<"not find"<       
    APP_DATA app_data;
    app_data.size=5;
    memmove(&app_data.data,"hello",5);   
    cache.insert_LRUCache("wwm",3,&app_data);

    cache.test();
    cout<<"\r\n"<   
    app_data.size=6;
    memmove(&app_data.data,"hello1",6);   
    cache.insert_LRUCache("wwm1",4,&app_data);   
    cache.test();
    cout<<"\r\n"<   
   
    app_data.size=6;
    memmove(&app_data.data,"hello2",6);   
    cache.insert_LRUCache("wwm2",4,&app_data);   
    cache.test();
    cout<<"\r\n"<   
   
    app_data.size=6;
    memmove(&app_data.data,"hello3",6);   
    cache.insert_LRUCache("wwm3",4,&app_data);
    cache.test();
    cout<<"\r\n"<   
    p = cache.hitLRUCache("wwm2");
    if(p==NULL)
        cout <<"not find again"<    else
        cout<<"hiting data: "<data<       
    cache.test();   
   
   
    p = cache.hitLRUCache("wwm1");
    if(p==NULL)
        cout <<"not find again"<    else
        cout<<"hiting data: "<data<       
    cache.test();   
   
    cache.destroy_LRUCache();   
return 0;
}