ceph/src/common/lru_map.h

   1 #ifndef CEPH_LRU_MAP_H
   2 #define CEPH_LRU_MAP_H
   3
   4 #include <list>
   5 #include <map>
   6 #include "common/Mutex.h"
   7
   8
   9 template <class K, class V>
  10 class lru_map {
  11   struct entry {
  12     V value;
  13     typename std::list<K>::iterator lru_iter;
  14   };
  15
  16   std::map<K, entry> entries;
  17   std::list<K> entries_lru;
  18
  19   Mutex lock;
  20
  21   size_t max;
  22
  23 public:
  24   class UpdateContext {
  25     public:
  26       virtual ~UpdateContext() {}
  27
  28       /* update should return true if object is updated */
  29       virtual bool update(V *v) = 0;
  30   };
  31
  32   bool _find(const K& key, V *value, UpdateContext *ctx);
  33   void _add(const K& key, V& value);
  34
  35 public:
  36   lru_map(int _max) : lock("lru_map"), max(_max) {}
  37   virtual ~lru_map() {}
  38
  39   bool find(const K& key, V& value);
  40
  41   /*
  42    * find_and_update()
  43    *
  44    * - will return true if object is found
  45    * - if ctx is set will return true if object is found and updated
  46    */
  47   bool find_and_update(const K& key, V *value, UpdateContext *ctx);
  48   void add(const K& key, V& value);
  49   void erase(const K& key);
  50 };
  51
  52 template <class K, class V>
  53 bool lru_map<K, V>::_find(const K& key, V *value, UpdateContext *ctx)
  54 {
  55   typename std::map<K, entry>::iterator iter = entries.find(key);
  56   if (iter == entries.end()) {
  57     return false;
  58   }
  59
  60   entry& e = iter->second;
  61   entries_lru.erase(e.lru_iter);
  62
  63   bool r = true;
  64
  65   if (ctx)
  66     r = ctx->update(&e.value);
  67
  68   if (value)
  69     *value = e.value;
  70
  71   entries_lru.push_front(key);
  72   e.lru_iter = entries_lru.begin();
  73
  74   return r;
  75 }
  76
  77 template <class K, class V>
  78 bool lru_map<K, V>::find(const K& key, V& value)
  79 {
  80   Mutex::Locker l(lock);
  81   return _find(key, &value, NULL);
  82 }
  83
  84 template <class K, class V>
  85 bool lru_map<K, V>::find_and_update(const K& key, V *value, UpdateContext *ctx)
  86 {
  87   Mutex::Locker l(lock);
  88   return _find(key, value, ctx);
  89 }
  90
  91 template <class K, class V>
  92 void lru_map<K, V>::_add(const K& key, V& value)
  93 {
  94   typename std::map<K, entry>::iterator iter = entries.find(key);
  95   if (iter != entries.end()) {
  96     entry& e = iter->second;
  97     entries_lru.erase(e.lru_iter);
  98   }
  99
 100   entries_lru.push_front(key);
 101   entry& e = entries[key];
 102   e.value = value;
 103   e.lru_iter = entries_lru.begin();
 104
 105   while (entries.size() > max) {
 106     typename std::list<K>::reverse_iterator riter = entries_lru.rbegin();
 107     iter = entries.find(*riter);
 108     // assert(iter != entries.end());
 109     entries.erase(iter);
 110     entries_lru.pop_back();
 111   }
 112 }
 113
 114
 115 template <class K, class V>
 116 void lru_map<K, V>::add(const K& key, V& value)
 117 {
 118   Mutex::Locker l(lock);
 119   _add(key, value);
 120 }
 121
 122 template <class K, class V>
 123 void lru_map<K, V>::erase(const K& key)
 124 {
 125   Mutex::Locker l(lock);
 126   typename std::map<K, entry>::iterator iter = entries.find(key);
 127   if (iter == entries.end())
 128     return;
 129
 130   entry& e = iter->second;
 131   entries_lru.erase(e.lru_iter);
 132   entries.erase(iter);
 133 }
 134
 135 #endif