LRU_MAP设计与实现

• std::map 存储数据，其中value: {原始value,以及此value在std::list中的位置}
• std::list 实现LRU，存储key

lru_map数据结构如下：

• std::map<K,entry> entries; /*实现key-value数据的存储*/
• std::list<K> entries_lru; /*维护lru数据*/
• std::mutex; /*线程安全*/
• size_t max; /*LRU缓存大小*/

其中entry结构如下：

struct entry{
  V value;
  typename std::list<K>LLiterator lru_iter; /*用来表示此 key 在entries_lru的位置*/
};

提供接口函数

• bool find(const K& key, V* value)
• void add(const K& key, V& value)
• void erase(const K& key)

find(const K& key, V& value):
主要逻辑：

• 加锁
• 在map中根据key检索
• 根据检索到的entry定位 key 在entries_lru的位置，位置存储在entry.lru_iter变量中
• 更新key在entries_lru的位置
• 返回检索值

std::lock_guard<std::mutex> lock(lock);
typename std::map<K, entry>::iterator iter = entries.find(key);
if(iter == entries.end())
  return false;

entry& e = iter->second;
entries_lru.erase(e.lru_iter);

if (value)
  value = e.value;

entries_lru.push_front(key);
e.lru_iter = entries_lru.begin();

return true;

void add(const K& key, V& value):
主要逻辑：

• 加锁
• 检索此key是否存在，存在获取现有key 对应的entries，并删除entries_lru的key
• entries_lru在头部插入此key
• map中插入<key,entry>对
• 更新entry.lru_iter
• 判断entries_lru size是否超过max
• 若超过，则删除entries_lru末尾，同时删除entries中的元素

实现代码如下：

std::lock_guard<std::mutex> lock(lock);
typename std::map<K,entry>::iterator iter = entries.find(key);
if (iter != entries.end()){
  entry& e = iter->second;
  entries_lru.erase(e.lru_iter);
}
entries_lru.push_front(key);
/*entries[key]: 不存在，则会新建(key,entry)*/
entry& e = entries[key]; 
/*更新entry*/
e.value = value;
e.lru_iter = entries_lru.begin();

/*处理size过大情况*/
if (entries_lru.size()>max){
  typename std::list<K>::reverse_iterator citer = entries_lru.rbegin();
  iter = entries.find(*riter);
  entries.erase(iter);
  entries_lru.pop_back();
}

erase(const K& key)
主要逻辑：

• 加锁
• entries根据key检索 entry: e
• entries_lru删除e->lru_iter
• entries删除对应(key,e)

实现代码：

std::lock_guard<std::mutex> lock(lock)；
typename std::map<K,V>::iterator iter = entries.find(key);
if (iter != entries.end()){
  entries_lru.erase(iter->second.lru_iter);
  entries.erase(iter);
}

完整的代码如下

lru_map.hpp:

#ifndef _LRU_MAP_H
#define _LRU_MAP_H

#include <iostream>
#include <mutex>
#include <list>
#include <map>

template<typename K, typename V>
class lru_map{
private:
    struct entry{
        V value;
        typename std::list<K>::iterator lru_iter;
    };
    std::mutex mtx;
public:
    std::map<K,entry> entries;
    std::list<K> entries_lru;
    size_t max;

public:
    lru_map(int max):max(max){}
    virtual ~lru_map(){}

    bool find(const K& key, V *value);
    void add(const K& key, V& value);
    void erase(const K& key);
    void dump();
};

template<typename K,typename V>
bool lru_map<K,V>::find(const K& key,V *value){
    std::lock_guard<std::mutex> lock(mtx);
    typename std::map<K,entry>::iterator iter = entries.find(key);
    if (iter == entries.end()){
        return false;
    }
    entry& e = iter->second;
    if (value){
        *value = e.value;
    }
    entries_lru.erase(e.lru_iter);
    entries_lru.push_front(key);
    e.lru_iter = entries_lru.begin();
    return true;
}

template<typename K,typename V>
void lru_map<K,V>::add(const K& key, V& value){
    std::lock_guard<std::mutex> lock(mtx);
    typename std::map<K,entry>::iterator miter = entries.find(key);
    if (miter != entries.end()){
        entries_lru.erase(miter->second.lru_iter);
    }
    entries_lru.push_front(key);
    entry& e = entries[key];
    e.value = value;
    e.lru_iter = entries_lru.begin();

    if (entries_lru.size() > max){
        typename std::list<K>::reverse_iterator citer = entries_lru.rbegin();
        miter = entries.find(*citer);
        entries.erase(miter);
        entries_lru.pop_back();
    }
}


template<typename K,typename V>
void lru_map<K,V>::erase(const K& key){
    std::lock_guard<std::mutex> lock(mtx);
    typename std::map<K,entry>::iterator iter = entries.find(key);
    if (iter != entries.end()){
        entries_lru.erase(iter->second.lru_iter);
        entries.erase(iter);
    }
}

template<typename K,typename V>
void lru_map<K,V>::dump(){
    if (!entries_lru.empty()){
        std::cout<<"LRU_CACHE KEY SEQ"<<std::endl;;
        for (const auto& it:entries_lru){
            std::cout<<"Key: "<<it<<std::endl;
        }
        std::cout<<"MAP MEM"<<std::endl;
        for (const auto& it:entries){
            std::cout<<"key: "<<it.first<<",Value: "<<it.second.value<<std::endl;
        }
    }
}

#endif

测试下testlru.cc:

#include <iostream>
#include "lru_map.hpp"

int main(int argc,char *argv[]){
    lru_map<int,char> lm(3);
    char a = 'a';
    char b = 'b';
    char c = 'c';
    char e = 'e';
    lm.add(2,b);
    lm.add(1,a);
    lm.add(5,e);
    lm.add(3,c);
    lm.dump();
    char* value = new char;
    lm.find(5,value);
    lm.dump();
    delete value;

}

输出如下：

LRU_CACHE KEY SEQ
Key: 3
Key: 5
Key: 1
MAP MEM
key: 1,Value: a
key: 3,Value: c
key: 5,Value: e
LRU_CACHE KEY SEQ
Key: 5
Key: 3
Key: 1
MAP MEM
key: 1,Value: a
key: 3,Value: c
key: 5,Value: e